编者按：
本文为 Numen Cyber 安全架构师 Dr. Simon Shieh 所撰写，关于 MPC 钱包原理，主要分为五大部分，分别为：
1.MPC 简介
2.TSS 原理
3.主流 TSS 简介
4.对 Ledger Key Recover 的建议
5.总结
Dr. Simon Shieh 表示，对于 MPC 钱包的核心技术 TSS，如果使用得当，TSS 的引入对于降低用户门槛和提高安全性方面有很大的帮助。
但如果 TSS 使用不当，例如零知识证明缺失、私钥分片存储不当等问题，仍然可能会造成私钥的泄露和资产的丢失。
全文共 7059 字，全文阅读需 40min。
世界最大冷钱包公司 Ledger 技术长查尔斯（Charles Guillemet）5月16 日深夜发表 Ledger 新产品“Ledger Recover”。
使用者只要通过双重身份验证（护照和身份证），输入或创建个人钱包私钥后，该私钥将拆分成三个碎片分给三间公司独立保管，使用者若私钥丢失后，即可透过 Ledger Recover 向其中任意两家保管公司申请，恢复新的私钥登入自己的虚拟钱包。
本来是出于资产安全和降低操作门槛的考虑，却引起了用户的强烈不满，认为私钥不应离开加密芯片，且该功能有三家公司合伙作恶和侵犯隐私的嫌疑。
那么 Ledger 的这项新服务到底是什么技术原理？该技术安全性如何？应该如何打消用户的疑虑呢？本文将向大家详细介绍这项新服务背后的技术原理。
“Not your keys, not your assets，不是你的私钥就不是你的资产”。
如果你拥有或曾经拥有过加密资产，这句话你一定听说过。作为行业内最重要的忠告之一，这句话要求用户保管好自己的私钥，从而自行保管好自己的加密资产。
但目前主流的去中心化加密钱包，都需要用户记录长长的助记词或保管好自己的私钥文件，使用起来麻烦不说，因遗失私钥和助记词而丢失资产也时有发生，且黑客会利用各种骚操作来偷来骗用户的私钥和助记词。
这就使得用户进入 Web3 的门槛变得非常高，而且时刻有损失资产的风险，从而导致 Web3 生态发展停滞，增量消失。
那么，怎么解决这一问题呢？近期多个头部平台、钱包开发商不约而同地上线 MPC 钱包方案，并宣称 MPC 钱包相比传统钱包更安全，用户操作门槛更低，其中就包括 Ledger 上线的 key recover 服务。
这是什么原理呢？MPC 又是什么黑科技呢？
MPC，即多方计算，全称为 Multi-Party Computation，有时也叫 SMPC，多方安全计算（Secure Multi-Party Computation）。
是指在一个互不信任的多用户网络中，在无可信第三方的情况下，多个参与方协同计算一个约定函数，除计算结果以外，各参与方无法通过计算过程中的交互数据推断出其他参与方的原始数据。
1982年，姚期智院士提出著名的“姚式百万富翁问题”：两个百万富翁 Alice 和 Bob 在街上相遇，他们都想知道谁更富有，但又不愿意让对方知道自己具体财富多少。如何在没有第三方的情况下，让对方知道谁更有钱？
那么可以假设 Alice 有一个私人数字 a， Bob 有一个私人数字 b，双方的目标是解不等式 a 是否 ≤b。或者更精准的说，除了得到不等式了 a≤b 或 a>b 外，不会得出任何与 a 或 b 相关的其他信息。
姚院士使用了混淆电路和不经意传输技术解决了这一问题，开创了隐私计算的 MPC 学派。
相对于现实中的问题来说，比较大小可能只是最简单的一类问题，在 MPC 发展的过程中，归集、并集，数学计算，多重签名等问题被提出，并得到相应的解决。
其中 TSS（Threshold Signature scheme，门限签名）就是解决多签问题的方案，也是现在 MPC 钱包的技术基础。
门限签名（Threshold Signature Scheme）首先是一类签名方案的统称。它的核心思想是将私钥 K 分割成多个部分，然后由一定数量的分割部分（达到设定的阈值）联合进行签名，可以达到和完整私钥K来签名相同的效果。
这种策略提高了数据保护的强度，同时减少了单点故障的风险。
门限签名的基本原理源于门限密码学，这是密码学的一个分支，关注的是如何将秘密信息分割成多个部分，并要求至少有t个部分（t 为阈值）才能恢复原始的秘密信息。
在{t,n}表示的门限签名中，私钥被分割成 n 个部分，然后至少需要 t 个部分才能有效签名，而不论多少个私钥分片在一起，都只能完成签名，而无法泄露完整私钥和其他私钥分片信息。
在这个过程中，需要解决的问题主要有两个部分：
1.如何在没有第三方的情况下生成私钥分片；
2.如何在不暴露私钥分片的情况下完成门限签名。
其中第一个部分又称为 DKG（Distributed Key Generation，分布式密钥生成）过程。本质上，DKG 过程中采用的秘密分享算法和秘密参数的不同，造就了不同风格的门限签名算法。
DKG 过程本质上是个没有中心化分发者（Dealer）的秘密分享过程。在解读 DKG 过程之前，我们先来了解下秘密分享。
2.1.1、秘密分享
秘密分享是信息安全和数据保密中的重要手段，它在重要信息和秘密数据的安全保存、传输及合法利用中起着非常关键的作用。
秘密分享的概念最早是由 Adi Shamir（2002 年图灵奖获得者）于1979年提出的。为了解决把一个秘密值拆分为 n 个部分，当有 t (t≤n) 个成员提供他们保管的信息后就能恢复出秘密值的问题，他提出了秘密分享算法。
秘密分享实际由两个算法组成——秘密份额的分配算法和秘密的恢复算法。
在执行秘密份额的分配算法时,分发者（Dealer）将秘密分割成若干个份额（share，或小块 piece，或影子 shadow）在一组参与者中进行分配,使得每一个参与者都得到关于该秘密的一个秘密份额。
秘密的恢复算法保证只有参与者的一些特定的子集（称为合格子集）才能有效地恢复，而其它子集不能有效地恢复秘密，甚至得不到关于秘密的任何有用信息。
Shamir's Secret Sharing（SSS）算法的核心原理在于： 2 个点可以唯一确定一个 1 次多项式（直线），3 个点可以唯一确定一个 2 次多项式（抛物线），依此类推， t 个点可以唯一地确定一个 t−1 次多项式。
这样，我们就可以构造一个 t-1 次多项式，n 个成员相当于在多项式上取 n 个点，而恢复 t−1 次多项式仅仅需要 t 个点就够了，这样就实现了任意 t 个成员都可恢复出同一个 t−1 次多项式，我们事先把秘密值编码到多项式中（具体做法就是 xx取 0 时的 yy值作为秘密值，也就是多项式的常数项=秘密值），就可以恢复秘密值了。
下图就是一个{3,4}秘密分享的原理示意图。
因为 t=3，所以可以构造一个 2（t-1）次多项式:
其中 为秘密值， 和 都是随机数。然后令 =1,2,3,4 这样得到的 分别记为部分秘密 ，由一个可信赖的第三方（一般称为 Dealer）分配给 4 个成员。也就是说每个成员被分配了多项式上的一个点，横坐标分别为1,2,3,4。
这样，秘密值 由 3个部分秘密重建的步骤为： 3个成员拿出他们的部分秘密 例如点 (1, ),(2, ),(3, ) 重建为一个唯一的 2 次多项式，记为 。如何重建？当然是用我们的拉格朗日插值大法了，这里就不详细展开了。
SSS 方案中，有个假设：Dealer 是可信的。如果 Dealer 做恶，比如分配给各个参与者的部分秘密是错误的值，那么造成的结果是灾难性的：可能无法恢复出正确的秘密值。
1987年 Feldman 在论文 A Practical Scheme for Non-interactive Verifiable Secret Sharing 中首次提出了可实用的 VSS（Verifiable Secret Sharing） 方案用于检测出做恶的 Dealer （注：VSS这个概念本身是由Benny Chor, Shafi Goldwasser, Silvio Micali 等人在1985年论文
Verifiable secret sharing and achieving simultaneity in the presence of faults中首次提出的）。
在该论文中，Feldman 使用了基于多项式系数承诺（commitment）的方案，在分配私钥片段的同时，广播承诺：
每个参与者 验证自己收到的 ，利用离散对数运算的性质，如果
1991 年 Pedersen 在论文 Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing 中提出了 Pedersen’s VSS 方案。
和 Feldman 的方案不同的是，Pedersen 方案采用了形如
的 Pedersen 承诺，其中 来自密钥构造多项式 系数，而 来自 dealer 另外构造的一个随机多项式 的系数，承诺集合 是一种公开可获取的系数“证据”，用于证明 dealer 只承认一个合法的密钥多项式。
在安全性上 Pedersen’s VSS 属于无条件安全，而 Feldman 由于 被公开，属于计算安全。当然在效率上，Feldman 要高于 Pedersen。
真正的 DKG 需要去掉 VSS 里的那个中心，在分布式协作下生成秘密，避免单点泄漏风险，其原理也很简单。
相当于 n 个节点同时各自选择秘密值并运行自己的 VSS，每个节点收集来自其他节点的秘密份额完成组装，组装后的结果便是真正私钥的份额，而各个合法节点各自分发的秘密值聚合起来便是最终的构造私钥，最后在进行承诺验证。
以{2，3}门限签名为例，这个门限签名使用的多项式为 相信大家都很熟悉了。
下面我们假设每个人都生成一个类似上面的多项式，分别为：
实际上，这三个多项式相加就会形成最终的密钥多项式 ，其中15就是最终的主密钥，如果存在 dealer 的话，这个多项式就是 dealer 生成的密钥分享多项式。
然而，A，B，C 三方只知道这个多项式存在，但是并不知道这个多项式是什么。这就构成了当前的密钥分享方案能够在不知道主密钥多项式的情况下，进行密钥分享过程。
简单来说，就是每个节点都把自己当做 dealer 去给其他节点分发私钥分片，最后节点再把收到的多个分片组装起来形成新的私钥分片，从而形成一个没有中心化 dealer 的方案。
按照当前流行的签名算法，主流的 TSS 算法主要分为基于 ECDSA 和基于 Schnorr 的两类。
我们以 ECDSA 为例，首先来看看一个标准的（只涉及一方）签名过程是怎样的：
与 ECDSA 不同，Schnorr 最终得到的签名为 , 其中 为混淆公钥。
TSS 的签名阶段简单来讲是基于上面得到的密钥份额各自完成签署自己的签名份额，最后再完成统一组装，得到最终门限签名，这过程中，每次签名都伴随着一次随机数 这个秘密值的 DKG 过程。
具体到实现流程上，与所基于的数字签名算法有很大关系，例如 Schnorr 算法在计算签名 值时所依赖的秘密值 在常数项，所以可以简单的将秘密值份额相加。
而 ECDSA 中的 是非线性的，存在两个秘密值（ 和 ）的运算，所以需要对公式进行变形，重新定义组合秘密值 , ，并分布式完成 , 的秘密份额计算以及分发。
2001 年，MacKenzie 和 Reiter 在论文 Two-Party Generation of DSA Signatures（full version）中提出了一个 Two-party ECDSA 签名方案，基本为后续的 TSS 方案奠定了框架基础，后面的基于 ECDSA 的 TSS 方案，都是在其基础上进行了可用性和安全性的改造。
MacKenzie 和 Reiter 提出的思路如下：
参与方 随机生成 , （和标准的 ECDSA 一样，其中 是需要保存的，而 是一次一用的），类似地参与方 也随机生成 , ，这两方所组成的秘密 和 分别由 和 得到，由于 不能泄露 , ，同样 也不能泄露 , ，所以不能直接得到总秘密的 和 。而是要通过一个 Diffie-Hellman 密钥交换过程来直接求得总公钥 和总混淆公钥 :
以上还都比较容易理解，基于 ECDSA 的门限签名困难的地方在于公共 的生成：
如何在 不泄露 , ， 也不泄露 , 的情况下，计算 呢？论文中使用了 Pailliar 同态加密 Paillier Cryptosystem
然后注意到红色的部分只有 知道，那么我们就可以利用 Pailliar 同态加密，来加密这两个部分后，再在加密结果上进行运算，最后再用 的Pailliar私钥解密即可。
2.2.3、防止流氓私钥攻击（Rogue Key Attack）
到目前为止，我们上边所涉及的协议流程，都是在分片参与者诚实的假设前提下进行的，而现实环境中， 有可能通过恶意构造 和 来获取 参与者的 , 信息，这就是流氓私钥攻击（Rogue Key Attack）。
要防止该攻击， 需要在不泄露 和 的情况下证明他向 提供的加密数据中确实包含了 和 。
还需要证明的是， 确实知道 Pailliar 公钥加密所对应的私钥。
此处都是通过零知识证明来完成的，一般都会使用 Schnorr Proof 协议来做证明，关于零知识证明的具体内容，可以参考往期文章（点击标题即可跳转）：
Numen｜零知识证明引论Part 1
Numen | 零知识证明引论Part 2
Numen | 零知识证明引论Part 3
Numen | 零知识证明引论Part 4
注意，这里的零知识证明是必不可少，否则会导致完整私钥泄露等严重的安全问题，这里有个省略零知识证明造成私钥泄露的例子：
https://www.fireblocks.com/blog/bitgo-wallet-zero-proof-vulnerability/
同时，上节通过 Pailliar 算法完成的将乘法转变为加法的过程，也叫 MtA（Multiplicative-to-Additive）过程，该过程需要 能够证明 和 确实是用分发的 Pailliar 私钥加密而来的，而不是通过骚操作构造出来的。
这是因为，Paillier 加密算法要求待加密的明文必须小于 Paillier 公钥 （Paillier 解密算法最后有个 mod 运算，这要求待加密的明文不能超过 Paillier 运算空间的阶，又叫 order）。
如果攻击者通过构造大数来参与协议，很可能造成完整私钥泄露，相关攻击可参考论文：
Alpha-Rays: Key Extraction Attacks on Threshold ECDSA Implementations 。
这种情况就需要引入零知识证明中的 Range Proof 了，来证明被加密的明文<加密空间的阶。
在区块链实践中， 需要加密的 和 都是在 Secp256k1 空间的阶的范围内的，是 256bit 长度的，而 Pailliar 的阶一般是 2048 bit 长度的，所以有的用于区块链的 TSS 库会省略掉 Range Proof 的部分。
当然，有些新的 TSS 算法不使用 Pailliar 同态加密来完成 MtA 过程，就可以省略掉 Range Proof 的部分，例如 CCLST 是使用 CL Scheme 同态加密算法，不存在明文会超出阶的问题，所以就无需使用 Range Proof。
由于 MacKenzie-Reiter 算法在 DKG 阶段的零知识证明过程是很复杂的，涉及很多运算，代价比较大，所以并没有达到可工程落地的标准。
但近几年随着零知识证明的发展，一些新的 TSS 算法被提出，并广泛的应用到了区块链的多签钱包方案中。下面将按照基础签名算法的不同来一一介绍应用较为广泛的 TSS 算法。
2017 年，Yehuda Lindell （Coinbase 首席密码学家）在论文 Fast Secure Two-party ECDSA Signing 提出一个更快的两方 ECDSA 方案。其通过在构造 的过程中引入随机数 ，在增加安全性的同时，减少了零知识证明过程的代价：
在 multi-party-ecdsa 中有 Lindell 17方案的完整开源实现，参考：https://github.com/ZenGo-X/gotham-city/blob/master/white-paper/white-paper.pdf
blockchain-crypto-mpc 这个库则实现了 Lindell 17方案的加法形式，这样可以更方便的做 key resharing，同时也实现了 MtA 过程中的 Range Proof。
https://github.com/okx/threshold-lib
基于业务场景，使用了 Feldman’s VSS 来构造了一个基于 Lindell 17的{2,n}门限签名算法。不过，在该代码库中未发现 Range Proof 的实现。
由于 Lindell 17方案的实用性，基于此，很多{t,n}签名方案被提出，2018 年 Rosario Gennaro（纽约市立学院教授，Protocol Labs的密码学家） 和 Steven Goldfeder （Arbitrum 的 CEO）在论文 Fast Multiparty Threshold ECDSA with Fast Trustless Setup 中提出了一个通用的{t, n}签名方案，并统一了 DSA 和 ECDSA 的表达形式，简称 GG18 方案。
GG18 方案是第一个有影响力的、进入实用阶段的 ECDSA {t,n}门限多签协议。大部分后续提出的门限多签协议，都可以看作是 GG18 不同角度的优化版本。
相比于 two-party ECDSA 签名，GG18 在 DKG 阶段需要经过4轮操作，其中包括3轮密钥分发和1轮公钥验证：每个参与者先把自己的秘密值通过 {t, n} Feldman-VSS 方法分享给其它所有参与者，然后在 Pedersen's DKG 的基础上使用 Schnorr proof 来确保各个参与者的公私钥对应。
在签名阶段，GG18 一共需要进行9轮操作，每两个参与者之间都要进行两次 MtA 过程。
有的 GG18 实现（如 Binance 的实现和 Safeheron 的实现）包含了 Range Proof，而有的 GG18 实现（ZenGo 的实现）则没有包含 Range Proof。
继GG18之后，Rosario Gennaro 和 Steven Goldfeder 于 2020 年发表论文 One Round Threshold ECDSA with Identifiable Abort，被称为 GG20，它比 GG18 更优秀：
签名轮数更少：GG18 的签名过程需要 9 轮，而 GG20 的签名过程，被整理为离线预处理阶段和线上签名简短，只需要 7 轮，而且前 6 轮的离线预处理和待签名的 无关，可提前进行 。
可识别恶意参与者：GG18 协议，如果有恶意参与者，那么协议会终止，但却不知道谁是恶意参与者。在 GG20 协议中，引入了带有 Identifiable Abort 的承诺形式，只要失败，就可识别出是谁的责任，从而防止一直有参与方作恶导致协议 DDoS 的情况。
-
Thorchain: https://gitlab.com/thorchain/tss/tss-lib
-
ZenGo:https://github.com/ZenGo-X/multi-party-ecdsa
-
Safeheron: https://github.com/Safeheron/multi-party-ecdsa-cpp
值得注意的是，ZenGo 的代码库中未发现针对 GG18 和 GG20 的 Range Proof 实现，但是在其 Lindell 17的代码库中，实现了 Range Proof。
以上其他的两个项目库都可以找到 MtA 过程中的 Range Proof 实现。
相比基于 ECDSA 的门限签名方案，基于 Schnorr 的门限签名方案发展比较晚，目前最优的方案是2020 年，ChelseaKomlo 和 Ian Goldberg 在论文 FROST: Flexible Round-Optimized Schnorr Threshold Signatures 中提出的 FROST 方案。
FROST 的 DKG 过程和基于 ECDSA 的协议没有什么区别，而签名过程则简单的多，是一个两轮协议。由于第一轮操作不会涉及到待签名消息 ，所以它可以提前进行。
我们从标准的 Schnorr 签名可以看出最终的签名 相对于秘密 和 来说是线性可加的。所以最终的签名只要把 t 个参与方的签名相加就可以得到。这个过程由于没有了同态加密和 MtA，所以节省了很多同态运算和 Range Proof 的资源。
从以上描述来看，FROST 签名的好处很多，其实在门限签名方面，FROST 签名方案是最简单高效的，而且安全性上也没有什么问题。唯一的缺点就是每个节点都要维护一棵 Merkle Tree，这个数据存储量会随着{t, n}的增大而增大。
那么 FROST 签名还没有完全流行，是因为目前只有 Taproot 更新后的比特币和少数几个非主流区块链项目使用了 Schnorr 签名，该方案还无法兼容更主流的 ECDSA 签名场景。
https://github.com/ZcashFoundation/frost
4、对 Ledger Key Recover 的建议
我想，如果理解了以上 TSS 算法，那么从 Ledger 官方的描述来看，不难判断出，Ledger Key Recover 应该是使用了某种{2,3}秘密分享方案，并且以用户自己作为一个 Dealer，给三家公司通过秘密共享的方式派发了私钥分片。
为了仍然保留单私钥的操作体验，用户在平时签名时，仍然使用的是单私钥签名，只有当私钥丢失的情况下，才会请求三家公司中的两家来恢复私钥。
-
-
用户作为 dealer 派发私钥分片时，有被全部截获的风险
-
-
那么在目前的情况下，我们建议用户还是谨慎使用该功能。
我们建议作为硬件钱包，应当尽量减少用户使用过程中网络信息的传输，具体到MPC方案，可以使用经过安全审计的开源方案帮助并指导用户在本地进行私钥分片的备份，或者让用户自行选择私钥分片灾备的服务商。
本文介绍了 MPC 钱包的核心技术原理 TSS，如果使用得当，TSS 的引入对于降低用户门槛和提高安全性方面有很大的帮助。
但如果 TSS 使用不当，例如零知识证明缺失、私钥分片存储不当等问题，仍然可能会造成私钥的泄露和资产的丢失。
Numen Cyber 建议用户选择代码公开透明且经过安全审计的 MPC 钱包来存储自己的加密资产；也建议钱包项目方关注 TSS 代码的安全性，选择适合自己业务场景的 TSS 算法。
同时，Numen Cyber 已经成为 Cobo MPC 托管方案的灾备分片存储供应商，作为可信第三方，帮助用户存储其在 Cobo 平台生成灾备私钥分片，在B 端托管领域已经有不少成功案例。
我们也正在寻找 C端 MPC 钱包的合作伙伴，希望能够通过我们的安全和灾备能力，共建安全、高效的钱包生态。
注：感谢aandds.com博客对本文的帮助，引用文献可在阅读原文中获取（需工具）。
https://github.com/NumenCyber
https://twitter.com/@numencyber
https://medium.com/@numencyberlabs
https://www.linkedin.com/company/numencyber/
评论