MPC 101：安全多方计算与多方签名

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 协议，包括但不限于：

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 协议的实现面临很严重的性能问题，需要对其多次优化。