MPC之源码分析4 -- ECDDSA Ed25519

SAGA 12月 13, 2022

前言

因为我们的主要目的还是讲解如何实现通用的多签方案，所以这里不会非常细致的讲解ED25519的各种优缺点，以及各种细节内容，主要是希望在讲解多签之前，大家对这个算法有个简单的认知。

首先ED25519是EDDSA的一种特殊实例。类似secp256k1之于ECDSA。

他的椭圆曲线公式如下

$-x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2$

25519的公私钥生成与256k1有一些不同，步骤如下：

生成私钥： $k=rand(N)$
计算私钥哈希值： $H(k)=(h_{0},h_{1},...,h_{2b-1})$
生成整数: $a=2^{b-2}+\sum_{3\leqslant i\leqslant b-3}2^ih_{i}\in \{2^{b-2},2^{b-2}+8,...,2^{b-1}-8\}\displaystyle \large$
生成公钥： $A = a B \displaystyle \large$

B 是基点。
这里 $H(k)$ 是对k进行sha256运算。

可以看到，这里的a，更像是我们认知里的私钥，这里我们先不展开，后续多签讲解的时候会再继续聊。

验证 $RB = rB + H(R, A, M)aB = R + H(R,A,M)A$ 是否成立

以上就是25519的基础知识，部分地方可能不够详细，大家可再自行查阅。

在讲如何使用MPC对25519签名进行分解之前，我们先回看下整个签名和验签的过程，会发现以下几点：

a的生成算法，对于整体签名和验签并无影响，也就是说，a完全可以通过随机数随机生成后，简单调整即可。
随机数r的生成，25519的定义里采用了一个确定性随机数算法，当私钥和消息确定时，r也就确定了，但是后续的过程中我们可以看到: r如何产生的，后续的过程并不关心。我们只要保证r不泄漏，并且不重复使用即可（如果重复或者泄漏，会造成a被攻破）。

根据以上两点，ZenGo在具体实现过程中进行了一些变更，与协议并不完全贴合。具体实现步骤如下：

私钥的生成
- 各方分别生成公私钥和随机数 $k_i = rand(N), H(k_i) -> [a_i, p_i], A_i = a_i B$
- 将 $a_i$ 通过秘密分享的方式，各方进行交换（秘密分享的内容可参考ECDSA Generate部分的讲解），将得到的秘密进行加和，得到 $x_i$ 。对应的多签公钥则是， $A=\sum A_i$
签名计算
- 参与签名的各方分别进行随机数计算 $r_i = H(p_i, m, rng), R_i = r_i B$ 这里就与标准协议有所不同了，引入了随机数rng。随后各方通过秘密分享的形式将 $r_i$ 进行分解，各方得到 $nonce_i$ 。这里需要注意的一点就是，这里进行秘密分享时，只有参与签名的各方会加入。同样我们可以得到 $R = \sum R_i$ ；
- 各方继续分别计算 $s_i = nonce_i + H(R, A, m) x_i$
- 最后我们收集各方签名，然后通过拉格朗日插值法，就可以得到 $S = largrange(s_i)$ 。最终签名 $(R, S)$