MPC 101：安全多方计算与多方签名
2022-06-15
最后更新于
2022-06-15
最后更新于
By Max
1982年，姚期智先生，图灵奖获得者，在他的论文中提出了安全多方计算这一重要概念。为了形象地介绍安全多方计算这个概念，他提出了著名的「百万富翁问题」。
两个百万富翁在街头碰面，为了争一口气，希望 PK 出谁更加富有，同时希望能让对方不知道自己资产的真实数额。
这篇论文开创了一个重要的领域——安全多方计算领域。下面我们介绍一下安全多方计算的概念。
安全多方计算（Secure Multi-Party Computation）的研究主要是针对在无可信第三方的情况下，如何安全地计算一个约定函数的问题。安全多方计算是电子投票、门限签名以及网上拍卖等诸多应用得以实践、落地的密码学基础。安全多方计算通常缩写为 SMPC 或者 MPC。
关于安全多方计算的安全性：一个安全多方计算协议，如果对于拥有无限计算能力攻击者而言是安全的，则称作是信息论安全的或无条件安全的；如果对于拥有多项式计算能力的攻击者是安全的，则称为是密码学安全的或条件安全的。
关于安全多方计算涉及到的技术种类很多。比如姚先生提出的混淆电路（Garbled Circuits）、不经意传输（Oblivious Transfer）、零知识证明（Zero Knowledge Proof）、同态加密（Homomorphic Encryption）等等，未来会通过 Blog 逐篇介绍。
安全多方计算研究的是各参与方在协作计算时如何对各方隐私数据进行保护，重点关注各参与方之间的隐私安全性问题，即在安全多方计算过程中必须保证各方私密输入独立，计算时不泄露任何本地数据。
多方计算参与各方就某一约定计算任务，通过约定 MPC 协议进行协同计算，计算结束后，各方得到正确的数据反馈。
传统的分布式计算由中心节点协调各用户的计算进程，收集各用户的输入信息，而在安全多方计算中，提供一种去中心化的计算模式，各参与方地位平等，不存在任何有特权的参与方或第三方。
在传统的私钥生成中， 生成一个公私钥对，其中公钥公开，对应着资产账户，私钥由特权人员管理。分布式私钥分片生成，与传统的私钥生成完全不同。私钥并不是由单个人在本地独自生成，而是所有参与者根据预先指定的门限 t 和参与人数 n，执行一个 MPC 密钥生成协议。当协议结束以后，所有人都能得到自己的私钥分片，以及一个共同的公钥。这个公钥对应着资产账户，对应私钥从未出现过。因此，公钥对应的资产由所有参与者共同管理。当密钥 分片完成后，每个人都只掌握一个私钥分片，为了获取真正的私钥，攻击者需要获取不低于门限数的私钥分片，才能恢复真正的私钥。
为了进一步提高安全性，一套密钥分片每隔一段时间会执行一次密钥刷新协议。协议结束后，每个人会得到一份新的私钥分片，同时旧的私钥分片全部作废。这种操作能有效的防止攻击者分别窃取每个人的私钥分片从而恢复私钥。因为，每次密钥刷新后，旧的私钥分片全部作废，导致攻击者前功尽弃，必须重新开始窃取攻击，从而指数级的提升了攻击难度。
为了获得有效的签名，生成有效的单签名交易，必须由满足门限数的参与者共同运行 MPC 多签协议。协议结束以后，所有人将获得一个相同的、有效的签名。在协议运行期间，所有参与者的私钥分片都不会泄漏。
在 MPC 多方签名领域中，根据应用场景的不同，我们需要实现各种各样的 MPC 协议，包括但不限于：
MPC-ECDSA 协议
MPC-EdDSA 协议
MPC-BLS 协议
MPC-Schnorr 协议
MPC-HMAC 协议
首先要提到的是 MPC-ECDSA 协议。由于大多数区块链都使用了基于椭圆曲线 Secp256k1 的Ecdsa 作为其签名算法，因此 MPC-ECDSA 始终是关注度最高的 MPC 协议。因为 ECDSA 的多方协议的研究难度要明显高于其他签名，因此 MPC-ECDSA 协议是经过了很长的时间研究出来的。
最快取得突破的是两方 ECDSA 协议。Lindell 提出了一个不错的两方 MPC 协议，参考论文 《Fast Secure Two-Party ECDSA Signing》，这里付诸实用的比较有代表性的是 ZenGo 的无私钥钱包。另一个设计两方 MPC-ECDSA 协议的方向是使用姚期智先生提出的混淆电路，Unbound Security 实现和落地了这样的方案。
紧接着，在通用门限签名领域的 MPC-ECDSA 协议也取得了进展，做出重要贡献的有 Gennaro and Goldfeder、Lindell、Doerner、Canetti 等人。基于以上几人的贡献，有密码学科研实力的公司开始实现他们自己的算法，正式开启了新的时代。
由于越来越多的、新的区块链的推出和应用，人们开始对更多的 MPC 多签协议有了需求，包括但不限于 MPC-EdDSA 协议、MPC-BLS 协议、MPC-Schnorr 协议。相比于 ECDSA，尽管 EdDSA、BLS、Schnorr 等签名算法对应的 MPC 协议要容易一些，在实现算法时依然要小心谨慎，因为需要避免很多的安全陷阱。
此外，如果需要在同一个地方管理不同平台上的资产，人们还需要实现更多的协议，比如 MPC-HMAC 协议。MPC-HMAC 协议的实现面临很严重的性能问题，需要对其多次优化。
为了满足区块链领域对各种各样 MPC 多签协议的需求，为了满足算法适应于多平台（Windows、Linux、macOS、Intel SGX、Android、iOS、WASM）的需求，Safeheron 开发了一系列的基础密码学算法库和多种应用级 MPC 协议。
在不远的未来，Safeheron 会逐步开源自己的算法库，各方可以检视算法的安全性。
基于安全多方计算的多方签名技术，在链上只有一个私钥存在，通过密码学技术，彻底去除了私钥单点风险。从始至终，单点私钥都未出现。通过多个私钥分片，不同参与方在签名时通过 MPC 协议计算出最终签名，且此签名能通过对应的单个公钥的验签。这一类技术称为 MPC 多签。
作为最新一代的签名技术，MPC 多签的地位变得越来越重要，Safeheron 将继续在该领域开展研究，并做出自己应有的贡献。
