MPC之源码分析3 -- ECDSA Sign

SAGA 9月 08, 2022

前边我们已经分析过了MPC的私钥生成过程，今天分析一下签名操作的整体流程。因为代码可读性问题，我们改为分析Zen Go的代码库，来学习签名的整体流程，实际上两个代码库的整体思路是一致的，所以不影响我们对整个算法对学习。

挑选参与的Party

工作开始前的第一步就是通过一个随机的操作，挑选出 t+1个Party，来参与整体的签名操作；然后将Party对应的私钥数据等加载进来，进入真正的签名流程中。

Start

签名操作的过程总过分为了7个round，我们按照这个流程逐步来跟踪计算的过程，这个过程中，源码还涉及了大量的对各自收到消息对证明和验证工作，这里我们对这部分先不做深入探讨，只对正常流程进行分析。

Round0

生成SignKeys对象，其中比较关键的是，通过拉格朗日公式，计算出 $w_i$

$w_i = \xi * \sum_{j=0}^n lagrange\_basis(0, j, x_j)$

其中 $\xi$ 就是各方持有的ss分片；

各方的 $w_i$ 相加，就能得到真正的私钥，即

$sk = \sum_{i=0}^nw_i$

同时，各方分别生成随机数 $k_i$ ,并通过Paillier算法加密后，生成MessageA，广播给其他各方。

Round1

在收到其他Party发送过来的MessageA之后，我们继续进行计算，因为Party之间相互持有各自的Paillier算法私钥，所以可以进行相应的同态计算。
比如，A收到B发过来的Message之后，因为A持有B的Paillier私钥，同时Message中包含的也是私钥加密之后的 $k_i$ , 所以A就可以在此基础上进行进一步计算，根据Paillier公式的原理，A进行了如下操作：

$m\gamma_b = k_b * \gamma_a + tag_a$

其中 $\gamma_a$ 是A生成的一个随机数，tag也是计算过程中的随机数，这个随机数很重要，保证了各方都无法单独还原出私钥等敏感信息。

同理

$mw_b = k_b * w_a + tag_a$

各方均进行此计算，并将结果通过P2P返回给发送方；

Round2

在收到其他各方返回的消息之后，各个Party对消息进行进一步的处理

$\delta_i = \sum_{j=0}^n m\gamma_j - \sum_{i=0}^n tag_ij = \sum_{j=0}^nk_i * \gamma_j - \sum_{i=0}^n tag_ij= k_i * \gamma - rand$

其中

$\gamma = \sum_{i=0}^n \gamma_i$

同理可得

$\sigma_i = k_i * w - \sum_{i=0}^n tag_ij = k_i * sk - rand$

这里的随机数很重要，如果没有此随机数，则sk可以被直接破解。同时， $\sigma_i$ 相加，又可以把这里的随机数消除掉，具体的实现需要看一下代码，比较绕。

将 $\delta_i$ 广播给其他各方。

Round3

$\delta\_inv = \frac{1}{\sum_{i=0}^n \delta_i} = \frac{1}{\delta}$

Round4

$R = \sum_{i=0}^n (\gamma_i * G) * \delta\_inv = \frac{\gamma * G}{\delta} = \frac{\gamma}{k * \gamma} * G = \frac{1}{k} * G$

其中 $\gamma_i * G$ 是通过各方消息广播收到的，因为是*G之后的值，所以并未泄露任何信息。
这里的R，也就是ECDSA签名中用到的r的完整形态。

Round5/Round6

这两个轮次里，主要是在做一些参数证明和验证，我们暂不深入探讨；到这里之后，我们就已经具备了进行签名计算的所有要素，然后我们进入最后一个Round

Round7

这里拿到用户的输入message，进行局部签名计算，得到

$s_i = Hash(message) * k_i + R.x * \sigma_i$

相互交换彼此的 $s_i$ 后，

$s = \sum_{i=0}^n s_i = H(m) *k + R.x * \sigma = H(m) * k + R.x * k * sk = k * (H(m) + R.x * sk)$

最后(s, R.x) 即为签名信息。