TSS Wallet (MPC) — Interactive Explainer

x = a_1 + a_2 + \cdots + a_n \pmod q

Y = x \cdot G

x_i = f(i)

f(z) = a_0 + a_1 z + a_2 z^2 + \cdots + a_{t-1} z^{t-1} \pmod q

a_0 = f(0)

s_i = f(i), \qquad i = 1,\dots,n

f_i(z) = a_{i,0} + a_{i,1} z + \cdots + a_{i,t-1} z^{t-1}

C_{i,k} = a_{i,k} \cdot G

s_{i \to j} = f_i(j)

s_{i \to j} \cdot G \overset{?}{=} \sum_{k=0}^{t-1} j^{k} \cdot C_{i,k}

x = \sum_{i=1}^{n} a_{i,0} \pmod q

Y = \sum_{i=1}^{n} C_{i,0} = x \cdot G

F(z) = \sum_{i=1}^{n} f_i(z)

x_j = \sum_{i=1}^{n} s_{i \to j} = \sum_{i=1}^{n} f_i(j) = F(j) \pmod q

\lambda_i = \prod_{\substack{j \in S \\ j \neq i}} \frac{j}{j - i} \pmod q

x = \sum_{i \in S} \lambda_i \, x_i \pmod q

\begin{aligned} F(z) &= 7 + 3z \qquad (q = 11,\ t = 2,\ n = 3) \\ x_1 &= F(1) = 10, \quad x_2 = F(2) = 13 \bmod 11 = 2, \quad x_3 = F(3) = 16 \bmod 11 = 5 \\ S &= \{1, 3\}: \quad \lambda_1 = \frac{3}{3-1} = 3 \cdot 2^{-1} = 3 \cdot 6 = 18 \bmod 11 = 7 \\ &\phantom{= \{1, 3\}:} \quad \lambda_3 = \frac{1}{1-3} = (-2)^{-1} = 9^{-1} = 5 \\ x &= 7 \cdot 10 + 5 \cdot 5 = 95 \bmod 11 = 7 \quad \checkmark \end{aligned}

f(x) = s + a_1 x + a_2 x^2 + \cdots + a_{t-1} x^{t-1} \pmod p

a_1, \dots, a_{t-1}

(x_1, y_1) = (1, f(1)), \quad (x_2, y_2) = (2, f(2)), \quad (x_3, y_3) = (3, f(3)), \ \dots

f(x) = \sum_{j=1}^{t} y_j \cdot \ell_j(x)

\ell_j(x) = \prod_{\substack{1 \le m \le t \\ m \neq j}} \frac{x - x_m}{x_j - x_m}

\ell_j(x_j) = 1

\ell_j(x_m) = 0 \quad (m \neq j)

\Rightarrow\ f(x_j) = \sum_m y_m\,\ell_m(x_j) = y_j \cdot 1 + \sum_{m \ne j} y_m \cdot 0 = y_j \quad \checkmark

s = f(0) = \sum_{j=1}^{t} y_j \cdot \ell_j(0)

\ell_j(0) = \prod_{m \neq j} \frac{0 - x_m}{x_j - x_m} = \prod_{m \neq j} \frac{-x_m}{x_j - x_m} = \prod_{m \neq j} \frac{x_m}{x_m - x_j} \pmod p

\lambda_j := \ell_j(0), \qquad s = \sum_{j \in S} \lambda_j\, y_j

f(x) = 5 + 7x + 3x^2 \pmod{17}, \qquad s = 5,\ t = 3,\ p = 17

	x		share (x, y)
P1	1	5 + 7·1 + 3·1 = 15	(1, 15)
P2	2	5 + 14 + 12 = 31 ≡ 14	(2, 14)
P3	3	5 + 21 + 27 = 53 ≡ 2	(3, 2)
P4	4	5 + 28 + 48 = 81 ≡ 13	(4, 13)

\begin{aligned} \ell_1(0) &= \frac{x_2}{x_2 - x_1}\cdot\frac{x_3}{x_3 - x_1} = \frac{2}{1}\cdot\frac{3}{2} = 3 \\ \ell_2(0) &= \frac{x_1}{x_1 - x_2}\cdot\frac{x_3}{x_3 - x_2} = \frac{1}{-1}\cdot\frac{3}{1} = -3 \equiv 14 \\ \ell_3(0) &= \frac{x_1}{x_1 - x_3}\cdot\frac{x_2}{x_2 - x_3} = \frac{1}{-2}\cdot\frac{2}{-1} = 1 \\[4pt] s &= 15 \cdot 3 + 14 \cdot 14 + 2 \cdot 1 = 45 + 196 + 2 = 243 \equiv 5 \pmod{17} \quad \checkmark \end{aligned}

\begin{aligned} k &\xleftarrow{\$} \mathbb{Z}_q, \qquad R = k \cdot G \\ e &= H(R \,\|\, Y \,\|\, m) \\ z &= k + e \cdot x \pmod q \end{aligned}

\sigma = (R,\ z)

z \cdot G \overset{?}{=} R + e \cdot Y

k_i \xleftarrow{\$} \mathbb{Z}_q, \quad R_i = k_i \cdot G

R = \sum_{i \in S} R_i, \quad e = H(R \,\|\, Y \,\|\, m)

z_i = k_i + e \cdot \lambda_i \cdot x_i

z = \sum_{i \in S} z_i, \quad \sigma = (R,\ z)

\begin{aligned} z &= \sum_{i \in S} z_i = \sum_{i \in S} k_i + e \sum_{i \in S} \lambda_i x_i = k + e \cdot x \\ z \cdot G &= k \cdot G + e \cdot x \cdot G = R + e \cdot Y \quad \checkmark \end{aligned}

x \xleftarrow{\$} [1,\ q-1]

Y = x \cdot G

\text{addr} = \text{last}_{20}\big(\text{keccak256}(Y)\big)\ \text{(Ethereum)} \quad /\quad \text{hash160}(Y)\ \text{(Bitcoin)}

m = H(\text{tx})

k \xleftarrow{\$} \mathbb{Z}_q^{*}\ (\text{or RFC 6979}), \quad R = k \cdot G

r = R_x \bmod q, \quad r \neq 0

s = k^{-1}\,(m + r \cdot x) \bmod q

\sigma = (r,\ s) \quad (+\ v\ \text{recovery id on Ethereum})

\begin{aligned} w &= s^{-1}, \qquad u_1 = m \cdot w, \qquad u_2 = r \cdot w \\ R' &= u_1 \cdot G + u_2 \cdot Y \end{aligned}

\iff R'_x \bmod q = r

R = k \cdot G

r = R_x \bmod q

s = k^{-1}\,(m + r x) \bmod q

u_1 = m \cdot s^{-1}, \quad u_2 = r \cdot s^{-1}

R' = u_1 \cdot G + u_2 \cdot Y

\iff R'_x \bmod q = r

\begin{aligned} R' &= u_1 G + u_2 Y \\ &= (m\,s^{-1})\,G + (r\,s^{-1})\,(x\,G) \qquad (Y = xG) \\ &= s^{-1}\,(m + r\,x)\,G \end{aligned}

s = k^{-1}(m + r x) \ \Longrightarrow\ s^{-1}(m + r x) = k

\therefore\quad R' = k\,G = R \quad \checkmark

\underbrace{k\,G}_{R} \;=\; \underbrace{m\,s^{-1}\,G + r\,s^{-1}\,Y}_{R'}

R — · R′ —

s = k^{-1}\,m + k^{-1}\,x\,r

\begin{aligned} k_i,\ \gamma_i &\xleftarrow{\$} \mathbb{Z}_q, \qquad \Gamma_i = \gamma_i \cdot G \\ k &= \textstyle\sum_i k_i, \qquad \gamma = \textstyle\sum_i \gamma_i \end{aligned}

\begin{aligned} k_i \cdot \gamma_j &= \alpha_{ij} + \beta_{ij} \\ k_i \cdot w_j &= \mu_{ij} + \nu_{ij}, \qquad w_j = \lambda_j x_j \end{aligned}

\begin{aligned} \delta_i &= k_i \gamma_i + \textstyle\sum_{j \neq i} (\alpha_{ij} + \beta_{ji}) &&\Rightarrow\ \textstyle\sum_i \delta_i = k\gamma \\ \sigma_i &= k_i w_i + \textstyle\sum_{j \neq i} (\mu_{ij} + \nu_{ji}) &&\Rightarrow\ \textstyle\sum_i \sigma_i = kx \end{aligned}

\begin{aligned} \delta &= \textstyle\sum_i \delta_i \quad (\text{public}) \\ R &= \delta^{-1} \cdot \textstyle\sum_i \Gamma_i = (k\gamma)^{-1} \gamma \cdot G = k^{-1} \cdot G \\ r &= R_x \bmod q \end{aligned}

\begin{aligned} s_i &= m \cdot k_i + r \cdot \sigma_i \\ s &= \textstyle\sum_i s_i = m\,k + r\,kx = k\,(m + r x) \end{aligned}

→