源码：tss-lib
假设 TSS 为 3-3
keygen
round_1
- 选择随机数 $u_i \in [1, n-1]$ 作为共享秘密 $sk$
选择随机数 $a_i, b_i \in [1, n-1]$，构造 2 阶多项式 $p_i(x)=u_i + a_i\cdot x + b_i \cdot x^2$，并对其承诺：
计算 Feldman 校验元组 $PK_i = u_i \cdot G, \space A_i = a_i \cdot G, \space B_i = b_i \cdot G$
计算承诺与打开承诺 $(KGC_i, KGD_i) = Com([PK_i, A_i, B_i])$
- 生成 Paillier 密钥对 $( N_i, p_i, q_i)$
- 生成 signing MtA range proof 会用到的参数 $\hat{N_i}, h_{1i}, h_{2i}$， $h_{1i}$ 的 dln proof1, $h_{2i}$ 的 dln proof2
- 广播承诺 $KGC_i$、Paillier 公钥 $N_i$、$\hat{N_i}, h_{1i}, h_{2i}$、dln proof1, dln proof2
round_2
- 对 round_1 数据进行验证（如 verify dln proof），存储到内存
- 将其它 party 的 $p_i(id)$ 通过 p2p 方式发送给对方
- 广播 $KGD_i$
round_3
- 收到了其它 party 发来的 $p_i(id)$ ，计算私钥分片 $x_i= \sum^3_{i=1}p_i(id)$ mod $n$
- 根据 $KGC_i, KGD_i$ 得到 $[PK_i, A_i, B_i]$
进行 Feldman 校验（PjShare.Verify）
$$ \begin{align} &p_1(id) \cdot G = PK_1 + id \cdot A_1 + id^2 \cdot B_1 \\ &p_2(id) \cdot G = PK_2 + id \cdot A_2 + id^2 \cdot B_2 \\ &p_3(id) \cdot G = PK_3 + id \cdot A_3 + id^2 \cdot B_3 \end{align} $$
计算公钥分片 $X_i = x_i \cdot G = PK + \sum_{i=1}^3(id \cdot A_i + id^2 \cdot B_i) $
公共公钥 $PK$ 和公钥分片 $X_1, X_2, X_3$ 之间满足拉格朗日插值校验
$$ PK = \lambda_1 \cdot X_1 + \lambda_2 + X_2 + \lambda_3 \cdot X_3 $$
根据三方的 Party ID 为 1, 2, 3，则对应的拉格朗日插值系数为
$$ \lambda_1 = \frac{0-2}{1-2}\frac{0-3}{1-3}, \lambda_2=\frac{0-1}{2-1}\frac{0-3}{2-3}, \lambda_3 = \frac{0-1}{0-2}\frac{3-1}{3-2} $$
推导如下
$$ \begin{align} &\lambda_1 \cdot X_1 + \lambda_2 \cdot X_2 + \lambda_3 \cdot X_3 \\ &= 3X_1 - 3X_2 + X_3 \\ &=3(PK + (\sum_{i=1}^{3}(a_i+b_i)\cdot G)-3(PK + \sum_{i=1}^{3}(2a_i+4b_i)\cdot G) + (PK + (\sum_{i=1}^{3}(3a_i+9b_i)\cdot G) \\ &= PK \end{align} $$
公共私钥 $sk$ 和私钥分片 $x_1, x_2, x_3$ 之间也满足拉格朗日插值
$$ sk = \lambda_1 \cdot x_1 + \lambda_2 + x_2 + \lambda_3 \cdot x_3 $$
- 广播 $X_i$ 及其 Paiiler proof
round_4
- 验证 $X_i$
- 将数据发送到外部业务层paillier_pub
例子
对于 3 / 3，各方构造随机多项式：
$p_1(x) = 1 + 2x + 3x^2$
$p_2(x) = 2 + 3x + x^2$
$p_3(x) = 3 + x + 2x^2$
各方算出 $p_i(j)$：
$p_1(1)=6, \space p_1(2)=17, \space p_1(3) = 34$
$p_2(1)=6,\space p_2(2)=12, \space p_2(3) = 20$
$p_3(1)=6, \space p_3(2)=13, \space p_3(3) = 24$
各方算出私钥分片：
$x_1 = 6 + 6 + 6 =18$
$x_2 = 17 + 12 + 13 = 42$
$x_3 = 34 + 20 + 24 = 78$
共享私钥为每个多项式的常数项之和：$x = 1 + 2 + 3 = 6$
拉格朗日插值多项式 $\lambda_i(x) = \prod_{j=1, j \ne i}^t\frac{x-j}{i-j}$，令 $x=0$，则 $\lambda_i(x) = \prod_{j=1, j \ne i}^t\frac{-j}{i-j}$ 为拉格朗日插值系数
共享私钥和私钥分片之间满足拉格朗日插值：
$$ \begin{align} 6 &= \frac{x-2}{1-2}\frac{x-3}{1-3} \cdot 18 + \frac{x-1}{2-1} \frac{x-3}{2-3} \cdot 42 + \frac{x-1}{3-1}\frac{x-2}{3-2} \cdot 78 \\ &= \frac{0-2}{1-2}\frac{0-3}{1-3} \cdot 18 + \frac{0-1}{2-1} \frac{0-3}{2-3} \cdot 42 + \frac{0-1}{3-1}\frac{0-2}{3-2} \cdot 78 \\ &= 3 \times 18 - 3 \times 42 + 1 \times 78 \end{align} $$
refresh 例子
黑客拥有超强的攻击能力，每隔一段时间就能攻破一个私钥分片，如果给他足够多的时间，就可以攻破 t 个私钥分片，从而得到完整的组私钥。如果每隔一个周期进行刷新，就意味着黑客必须在一个周期内攻破 t 个参与方，对黑客的要求更高了。
refresh 时
- a 产生新的常数项为 0 的随机多项式： $f_1(x) = 2x + x^2$
- b 产生新的常数项为 0 的随机多项式：$f_2(x)= x + 3x^2$
- c 产生新的常数项为 0 的随机多项式：$f_3(x) = x + 2x^2$
- refresh 前根私钥分片：18, 42, 78
refresh 前根私钥：
$$ \begin{align} 6 &= \frac{x-2}{1-2}\frac{x-3}{1-3} \cdot 18 + \frac{x-1}{2-1} \frac{x-3}{2-3} \cdot 42 + \frac{x-1}{3-1}\frac{x-2}{3-2} \cdot 78 \\ &= \frac{0-2}{1-2}\frac{0-3}{1-3} \cdot 18 + \frac{0-1}{2-1} \frac{0-3}{2-3} \cdot 42 + \frac{0-1}{3-1}\frac{0-2}{3-2} \cdot 78 \\ &= 3 \times 18 - 3 \times 42 + 1 \times 78 \end{align} $$
refresh 后根私钥分片：
- $18 + f_1(1) + f_2(1) + f_3(1) = 28$
- $42 + f_1(2) + f_2(2) + f_3(2) = 74$
- $78 + f_1(3) + f_2(3) + f_3(3) = 144$
- refresh 后根私钥： $6 = 3 \times 28 -3 \times 74 + 1 \times 144 $
resharing
目的：如果有新成员进来或旧成员离去，重新共享秘密 $sk$
round_1 旧的委员会执行
选择新随机数 $a_i', b_i' \in F_r $，构造新的 2 阶多项式 $p_i'(x) = w_i + a_i'x + b_i'x^2$，注意：所有的常数项 $w_i$ 加起来的和等于之前所有的 $u_i$ 加起来的和。计算承诺：
计算 Feldman 校验元组 $PK_i = w_i \cdot G, \space A'_i = a'_i \cdot G, \space B'_i = b'_i \cdot G$
计算承诺与打开承诺 $(KGC'_i, KGD'_i) = Com([A'_i, B'_i])$
- 广播承诺 $KGC'_i$ 和旧的公钥
round_2 新的委员会执行
- 广播 old committee 的 ACK
- 生成 Paillier 密钥对 $( N'_i, p'_i, q'_i)$
- 生成 signing MtA range proof 会用到的参数 $\hat{N'_i}, h'_{1i}, h'_{2i}, h'_{1i}$ 的 dln proof1, $h'_{2i}$ 的 dln proof2
- 广播 Paillier 公钥 $N'_i$、$\hat{N'_i}, h'_{1i}, h'_{2i}$ 和 dln proof1, dln proof2
round_3 旧的委员会执行
- 将其它 party 的公钥分片 $p'_i(id)$ 通过 p2p 方式发送给对方
- 广播 $KGD'_i$
round_4 新的委员会执行
- 对 round_2 数据进行验证（如 verify dln proof），存储到内存
- 收到了其它 party 发来的公钥分片 $p'_i(id)$ 后，计算新的私钥分片 $x'_i= \sum^3_{i=1}p'_i(id)$ mod $n$
- 根据 $KGC'_i, KGD'_i$ 得到 $[A'_i, B'_i]$
进行 Feldman 校验（sharej.Verify）
$$ \begin{align} &p'_1(id) \cdot G = PK_1 + id \cdot A'_1 + id^2 \cdot B'_1 \\ &p'_2(id) \cdot G = PK_2 + id \cdot A'_2 + id^2 \cdot B'_2 \\ &p'_3(id) \cdot G = PK_3 + id \cdot A'_3 + id^2 \cdot B'_3 \end{align} $$
- 更新公钥分片 $X'_i = x'_i \cdot G = PK + \sum_{i=1}^3(id \cdot A'_i + id^2 \cdot B'_i)$
- 广播自己和其它 party 之间的 fac proof
- 向新的委员会和旧的委员会都发送 ACK
round_5 新的委员会执行
- 验证 fac proof
- 将数据发送到外部业务层
signing
round_1 ~ round_5 计算公共随机点 $R$，三方各自输入输入 3 份原始随机数 $( k_i , \gamma_i , w_i )$
round_5 计算 $s_i$
round_5 ~ round_9 是在秘密情况下校验别的 party 的 $s_i$
prepare
- 生成随机数 $w_i \in [1, n-1]$
round_1
- 选择随机数 $(k_i, \gamma_i) \in [1, n-1]$
- 计算椭圆曲线随机点 $\Gamma_i = \gamma_i \cdot G$，承诺和打开承诺 $(C_i, D_i) = Com(\Gamma_i)$
MtA Alice
- 对 $k_i$ 进行 Paillier 加密，得到 $c_{i}$
- 发送 $c_{i}$ 及 $k_i$ 的 rang proof
- 广播承诺 $C_i$
round_2
MtA Bob
- 接收 $c_{i}$ 及 $k_i$ 的 rang proof，校验 rang proof
- 选择随机数 $\beta' \in Z_n$，同态计算 $c_j = (c_i \bigotimes \gamma_j) \bigoplus Enc_{pk}(\beta')$，则 $c_j = Enc_{pk}(k_i\gamma_j + \beta')$ mod $n$，获得加性份额 $\beta = -\beta'$ mod $n$
- 选择随机数 $v' \in Z_n$，同态计算 $\hat{c_j} = (c_i \bigotimes w_j) \bigoplus Enc_{pk}(v')$，则 $\hat{c_j} = Enc_{pk}(k_iw_j + v')$ mod $n$，获得加性份额 $v = -v'$ mod $n$
- 发送 $c_j, \beta$ 及 $\beta$ 的 rang proof， $\hat{c_j}, v$ 及 $v$ 的 range proof
round_3
MtA Alice
- 发送 $c_j,\beta$ 及 $\beta$ 的 rang proof， $\hat{c_j}, v$ 及 $v$ 的 range proof，校验 range proof
- 解密 $c_j$ 获得 $\alpha$，其中 $\alpha = k_i\gamma_j + \beta'$ mod $n$
- 解密 $\hat{c_j}$ 获得 $u$，其中 $u = k_iw_j + v'$ mod $n$
分析：Alice 和 Bob 不知道对方的保密数据，但是保密数据满足
$\alpha + \beta = (k_i\gamma_j + \beta') + (-\beta') = k_i\gamma_j$
$ u+v = (k_iw_j + v') + (-v') = k_iw_j$
假如当前 party id 为 1，计算
$\delta_1 = k_1\gamma_1 + \alpha_{1,2} + \alpha_{1,3} + \beta_{1,2} + \beta_{1,3}$ mod $n$
$\sigma_1 = k_1w_1 + u_{1,2} + u_{1,3} + v_{1,2} + v_{1,3}$ mod $n$
- 广播 $\delta_1$
round_4
- 三方均计算 $\delta^{-1}=(\delta_1 + \delta_2 + \delta_3)^{-1}$ mod $n$
- 广播打开承诺 $D_i$ 和 zk-Schnorr 证明 $ZK \left\{\gamma_i|\Gamma_i=\gamma_i \cdot G \right\}$
round_5
- 收到 $C_i$ 和 $D_i$，得到 $\Gamma_i$，验证 $ZK$
计算公共点 $R=\delta^{-1}(\Gamma_1 + \Gamma_2 + \Gamma_3)$，推导如下
$$ \begin{align} R &= k^{-1}\cdot G \\ &=(k\gamma)^{-1} \cdot (\gamma \cdot G) \\ &=((k_1 + k_2 + k_3)(\gamma_1 + \gamma_2 + \gamma_3))^{-1} \cdot (\gamma_1 + \gamma_2 + \gamma_3) \cdot G \\ &= \begin{pmatrix} k_1\gamma_1 + k_1\gamma_2 + k_1\gamma_3 + \\ k_2\gamma_1 + k_2\gamma_2 + k_2\gamma_3 + \\ k_3\gamma_1 + k_3\gamma_2 + k_3\gamma_3\end{pmatrix}^{-1} \cdot (\gamma_1\cdot G + \gamma_2\cdot G + \gamma_3\cdot G)\\ &= \begin{pmatrix} k_1\gamma_1 + (\alpha_{1,2}+\beta_{2,1}) + (\alpha_{1,3}+\beta_{3,1}) + \\ (\alpha_{2,1}+\beta_{1,2}) + k_2\gamma_2 + (\alpha_{2,3}+\beta_{3,2}) + \\ (\alpha_{3,1}+\beta_{3,2}) + (\alpha_{3,2}+\beta_{2,3}) + k_3\gamma_3\end{pmatrix}^{-1} \cdot (\gamma_1\cdot G + \gamma_2\cdot G + \gamma_3\cdot G)\\ &= \begin{pmatrix} k_1\gamma_1 + \alpha_{1,2}+\beta_{2,1} + \alpha_{1,3}+\beta_{3,1}) + \\ \alpha_{2,1}+\beta_{1,2} + k_2\gamma_2 + \alpha_{2,3}+\beta_{3,2} + \\ \alpha_{3,1}+\beta_{3,2} + \alpha_{3,2}+\beta_{2,3} + k_3\gamma_3\end{pmatrix}^{-1} \cdot (\Gamma_1 + \Gamma_2 + \Gamma_3)\\ &=(\delta_1 + \delta_2 + \delta_3)^{-1}\cdot(\Gamma_1 + \Gamma_2 + \Gamma_3)\\ &=\delta^{-1} (\Gamma_1 + \Gamma_2 + \Gamma_3) \end{align} $$
- 计算 $s_i = mk_i + r\sigma_i$，其中 $m$ 是消息，$r$ 是 $R$ 的横坐标
- 选择随机数 $l_i, \rho_i \in [1, n-1]$，计算 $V_i = s_i \cdot R + l_i \cdot G$$, \space \Upsilon_i = \rho_i \cdot G$
- 计算承诺与打开承诺 $(C'_i, D'_i) = Com(V_i, \Upsilon_i)$
- 广播承诺 $D'_i$
round_6
- 广播打开承诺 $C'_i$ 与 zk-Simga* 和 zk-Simga 证明 $ZK \left\{s_i, l_i, \rho_i|V_i = s_i \cdot R + l_i \cdot G, \space \Upsilon_i = \rho_i \cdot G\right\}$
round_7
- 三方均校验另外两方的打开承诺 $D'_1, D'_2, D'_3$ 与零知识证明的正确性
- 计算 $V=(-m)\cdot G + (-r) \cdot Pk + V_1 + V_2 + V_3$，$\Upsilon = \Upsilon_1 + \Upsilon_2 + \Upsilon_3$
- 计算 $\Omega_i = \rho_i \cdot V$，$\Psi_i = l_i \cdot \Upsilon$
- 计算承诺与打开承诺 $C''_i, D''_i = Com(\Omega_i, \Psi_i)$
- 广播承诺 $C''_i$
round_8
- 广播打开承诺 $D''_i$
round_9
- 根据 $C''_i, D''_i$ 解出 $\Omega_i, \Psi_i$
校验 $\Omega_1 + \Omega_2 + \Omega_3 = \Psi_1 + \Psi_2 + \Psi_3$，推导如下
$$ \begin{align} &\Omega_1 + \Omega_2 + \Omega_3 = (\rho_1 + \rho_2 + \rho_3) \cdot ((-m)\cdot G + (-r) \cdot Pk + V_1 + V_2 + V_3) \\ &=(-m \rho) \cdot G + (-r \rho)\cdot Pk + \rho(V_1 + V_2 + V_3) \\ &= (-m \rho) \cdot G + (-r \rho)\cdot Pk + \rho(s_1\cdot R + l_1 \cdot G + s_2 \cdot R + l_2 \cdot G + s_3 \cdot R + l_3 \cdot G)\\ &=(-m \rho) \cdot G + (-r \rho)\cdot Pk + \rho(s\cdot R + l \cdot G)\\ &=(-m \rho) \cdot G + (-r \rho)\cdot Pk + \rho s \cdot R + l \rho \cdot G)\\ &=-\rho(m\cdot G + r \cdot Pk - sR) + l \rho \cdot G \\ &= l \rho \cdot G \\ &\\ &\Psi_1 + \Psi_2 + \Psi_3 = (l_1 + l_2 + l_3) \cdot \Upsilon = l(\Upsilon_1 + \Upsilon_2 + \Upsilon_3) = l \rho \cdot G \\ \end{align} $$
- 广播 $s_i$
最后可算出签名 $s = s_1 + s_2 + s_3$，推导如下
$$ \begin{align} s &= k(m+xr) \\ &=mk + rkx \\ &=m(k_1 + k_2 + k_3) + r(k_1 + k_2 + k_3)(w_1 + w_2 + w_3) \\ &= m(k_1 + k_2 + k_3) + r\begin{pmatrix} k_1w_1 + k_1w_2 + k_1w_3 + \\ k_2w_1 + k_2w_2 + k_2w_3 + \\ k_3w_1 + k_3w_2 + k_3w_3\end{pmatrix}^{-1} \\ &= m(k_1 + k_2 + k_3) + r\begin{pmatrix} k_1w_1 + (u_{1,2}+v_{2,1}) + (u_{1,3}+v_{3,1}) + \\ (u_{2,1}+v_{1,2}) + k_2w_2 + (u_{2,3}+v_{3,2}) + \\ (u_{3,1}+v_{3,2}) + (u_{3,2}+v_{2,3}) + k_3w_3\end{pmatrix}^{-1} \\ &= m(k_1 + k_2 + k_3) + r\begin{pmatrix} k_1w_1 + u_{1,2}+v_{2,1} + u_{1,3}+v_{3,1}) + \\ u_{2,1}+v_{1,2} + k_2w_2 + u_{2,3}+v_{3,2} + \\ u_{3,1}+v_{3,2} + u_{3,2}+v_{2,3} + k_3w_3\end{pmatrix}^{-1} \\ &= m(k_1 + k_2 + k_3) + r(\delta_1 + \delta_2 + \delta_3)\\ &= (mk_1 + r\delta_1) + (mk_2 + r\delta_2) + (mk_3 + r\delta_3) \end{align} $$
没有评论