ROAST - Robust asynchronous Schnorr threshold signatures
演讲者: Tim Ruffing
日期: October 14, 2022
记录者: Bryan Bishop
译者: Ajian
标签: Schnorr signatures, Threshold signature
幻灯片：https://slides.com/real-or-random/roast-tabconf22/
哈咯各位，我叫 Tim，在 Blockstream 工作。本次演讲的内容是我跟几位合作者联合工作的成果。
比特币中的 Schnorr 签名
最近，我们已经在比特币中支持了 Schnorr 签名，由 taproot 软分叉激活的 BIP340 引入。我们希望引入 Schnorr 签名并倾向于使用它而不是 ECDSA，有三大理由：一，Schnorr 签名的安全性有明确的证明，可以给理论工作者更强的信心；二，Schnorr 签名效率更高；三，最主要是，在 Schnorr 上我们可以更容易构造更高级的签名协议。
想象
比特币已经支持 Shnorr 签名的验证。一旦我们把验证能力做进了协议，我们就可以在此基础上开发许多东西并应用在链上。举个例子，你可以开发门限签名，还可以实现像 MuSig 和 MuSig2 这样的多签名协议。只要一个签名看起来是一个 Schnorr 签名，你就可以把它放到链上，是可以兼容的。为了支持 Schnorr 签名，我们必须更改共识层。但是，一旦有了 Schnorr 签名，我们就不再需要为使用更高级的签名协议而改造共识层，这是个好事情，因为改变共识层更难。
此外，有了这些协议，假设你在链上看到了一个 Schnorr 签名，你并不能知道它是否使用了门限签名协议或者多签名协议。这也提供了紧凑性，无论在构造签名的过程中发生了什么，最终发送到链上的都只有 32 字节。这也很好，因为区块空间是稀缺的。
门限签名
可能你在之前听说过 “multisig（多签名）” 这个词。“Multisig” 这个词更多用在比特币工程社区中，而 “门限签名” 更多用在学术社区中。假定我们有一个 “t-of-n” 的门限签名设置，这意味着 n 个签名者共有一个公钥，并且至少要 t 个签名人在线，才能签发一条消息。作为一种特殊情况，的确有一种 n-of-n 的情况，需要所有签名者都在场，这在学术文献中称为 “多签名”。但在这里，我们的用词会灵活一点，然后我们就讨论 t-of-n 的情形。
不可伪造性是最主要的安全特性，也就是说 t 个签名人应该可以创建一个签名，但如果到场的不足 t 个人，就不应能够创建出签名，即使 (t-1) 个恶意签名人彼此串通，也无法生成有效的签名。另一个重要特性是健壮性（robustness）：要是 t 个签名人真的想创建一个签名，就一定能做到。这是一种抗 Dod 特性，即使 (t-1) （译者注：原文如此，疑应为 “(n - t)”）希望阻止签名，这 t 个签名人也能生成签名。这就是我们希望实现的几个主要特性。
为什么要使用门限签名？
门限签名有许多应用。假设你有一个 2-of-3 的设置来保护自己放在家里的个人钱包，它不是只使用一个设备，而且把同一个私钥分成了 3 份，分别保存在不同的设备里面。这是安全性的提升，因为即使攻击者偷走了你的一份私钥，也无法偷走你的资金。这同时提升了安全性和可靠性。
如果你有许多币，可能你会像 Bitfinex 那样使用 3-of-6 的方案来获得更高的安全性。另一个应用是 Liquid 这样的侧链的观察员，他们集体使用 11-of-15 的门限 multisig。虽然这些币是在 Liquid 链上流通到，但它们是由这些观察员保管在比特币区块链上的。在这里我们已经拥有了 11-of-15 的安全性级别，但实际上我们还想要更高。
比特币中的 “Multisig”
以前，你可以在比特币上使用 OP_CHECKMULTISIGVERIFY 实现 Multisig。现在，有了 taproot 之后，你可以使用 OP_CHECKSIGADD 。它将要求你提供 n 个公钥和 t 个签名。因此，t 个签名就构成了一个有效的门限签名。
这种技术非常简单，而且简单对实现者来说也有好处。私钥生成无需签名人交互。每一个签名人都可以生成自己的密钥对，而且无需告诉彼此。签名的流程也是非交互的。另一种有趣的特性是，这样的协议是可追责的，因为你可以看出来是哪 t 个签名花费了这些资金。即使 t 个恶意方最终偷走了你的钱，至少你可以辨认出哪些人签了名。
但不幸的是，因为你需要把 n 个公钥放到链上，而且在你花费的时候需要提供 t 个签名。这里的 t 和 n 都将非常有限，因为区块空间本身很有限。此外，这样的交易或者说支付会在链上被辨认出来。你可以看到 n 个公钥或者 t 的签名，所以人们可以看出这套门限 multisig 的参数，只是未必知道签名人的确切身份。它显然不是使用普通钱包创建的普通交易 —— 这不利于用户的隐私性。
原生门限签名
理想情况下，门限签名看起来应该跟普通签名一样。
FROST
FROST 是灵活的（flexible）最优轮次的（round-optimized） Schnorr 门限签名（Komlo and Goldberg 2020）。这是一个很棒的方案，已经证明了其安全性，而且在并发的签名会话中是不可伪造的；而在有必要的时候，单个签名人可以运行并行的签名会话。假设了有一套合适的私钥生成协议。
FROST 协议非常简单，但它并没有提供上述的抗 DoS 特性那样的健壮性。我希望修复这一点。
FROST：启动
在这个例子中，我们有 4 个签名人，所以 n=4 。FROST 假设我们有中心化的协调员。这听起来有点糟糕，但我可以告诉你为什么它不是那么糟糕。这里的签名人通过协调员来跟彼此通信，也就是签名人彼此直接没有点对点的通信。而不是那么糟糕的原因就在于，不需要信任协调员就能实现不可伪造性。即使这个协调员是完全恶意的，并且可以串通其他恶意签名人，TA 也无法窃取你的资金。但是，我们需要依赖协调员来实现健壮性。
四个签名人希望创建一条签名，比如说是一个 2-of-4 的设置，也就是需要两个签名人到场。他们需要彼此通信，不然就无法生成一条签名。如果你假设有一个协调员，这就有点像假设有一个可用的网络。要是没有可用的网络，我们就无法彼此通信，也无法运行协议。
目标：健壮性
假设所有 n 个签名人运行一次签名协议。假设所有的签名人对待签名的消息达成了共识。这里，t 个签名人是诚实的，而且希望签名。但是，剩下的 (n-t) 个签名人是恶意的，希望防止诚实的签名人得到签名。即使是在这种情况下，我们也希望拥有健壮性，也就是即使有 (n-t) 个恶意签名人，协议依然能够产生一个签名。只要协调员能输出一个有效的签名，我们就满足了：这实际上只是一种简化，只要协调员拥有一个签名，TA 就能发送给其他人，或者直接发送到区块链上。
异步的网络
我们要为健壮性使用的网络假设是，这是一个异步的网络。这里的想法是，我们只对网络做了一个非常弱的假设：我们只要求诚实签名人和协调员之间的消息最终能送达，但没有固定的终止时间。不要假设消息达到的时间，互联网本身也不保证消息能送达。在实践中，假设一个签名人希望向协调员发送一条消息，协调员未必能收到这条消息。也许只是网速比较慢，后来会送达；又或者，这个签名人实际上是恶意的，从来就没发送过。协调员并不能知道这个签名人是宕机了、恶意的还是离线了，因为消息可能会在稍后送达。这也意味着，我们这套协议中没有超时这个概念。要是有超时机制，协调员就能断定签名人离线了，永远不会响应了；但实际上，签名人可能在几秒后就会回到线上、响应请求。
贡献：ROAST
我们的学术工作的贡献就是 ROAST。在一定意义上，ROAST 是 FROST 的一个封装器，将 FROST 转化为一个健壮的门限签名协议。FROST 没有健壮性。ROAST 以一种健壮的方式来使用 FROST。另一个评论是，一些人已经在问 FROST 和 ROAST 的关系。它们不是竞争关系。ROAST 利用了 FROST 并做得更好，但你是不是真的需要 ROAST 取决于你的设定。
设定 ROAST 的阶段
假设有 4 个签名人，也即 n=4，其中有一个协调人。在接下来的演讲中我们有一些基本的约定：这是一个 2-of-4 的 multisig；当我说 “我们” 的时候，总是从协调员的角度出发。这样讲起来会比较容易。我们（协调员）收到的所有消息都是有效的。这听起来是一个很强的假设，但实际上不是，因为在 FROST 中，我们收到消息后立即就能辨别它是有效的还是无效的。如果我们得到了一条无效的消息，我们可以忽略它，假装它从未发生过。虽然在实践中，你可能希望断开连接，或者给你的对等节点施加一些惩罚，等等。但出于本演讲的目的，我们就假设可以忽视掉无效的消息。当我说 “会话” 的时候，我指的总是 “FROST 会话”。
FROST 会话
一次 FROST 会话有两轮通信。在第一轮通信中，所有的签名人都发送一个我们称为 “nonce” 的数据。你不需要知道 nonce 的含义，就把它当成一个名称就好，我用它来指称在第一轮中发送的消息。假设 1 号签名人先发送了一个 nonce 值。协调员要做的就是等待 t 个 nonce 值。然后 3 号签名人也发送了一个 nonce 值。这意味着我们有了两个 nonce 值。而 t = 2，所以现在足够了。作为协调员，我们跟这两位签名人分别开启一轮新的 FROST 会话。这里的一个关键事情是，作为一个协调员，我要承诺已经结束了跟两位签名人的第一轮会话。我们要聚合第一轮中得到的 nonce，形成一个 “聚合 nonce”，然后把它发回给两位签名人。如果遵守协议，这两位（t 位）签名人会在第二轮中发送自己的签名碎片给协调员。
FROST 不健壮
假设现在 4 号签名人跳出来并发出一个 nonce 值；这时候我们无法处理，因为我们已经承诺了使用前面两位签名人的 nonce 值。所以，我们只能忽略到这条 nonce 消息，因为它没用。协调员可以收到两条签名碎片，这已经足以完成协议了。所以，在这种情况下，万事大吉，协调员输出了一个签名。这是成功的一次 FROST 协议。
但是，也许来自 1 号签名人的签名碎片，……（译者注：参考上下文，应该是没收到 3 号签名人的签名。） 我们无法断定 TA 是不是一个恶意节点，或者 TA 迟一些时候会响应，又或者 TA 会永远停机。即使后来有个签名人愿意发送一个 nonce 值过来也无济于事，因为我们已经承诺了使用一个聚合 nonce 值。
简单的 “解决方案”
我们可以为任意规模为 t 的签名人子集运行一次 FROST 会话。甚至可以并行运行。这当然可以。一般来说，这需要 $C_n^t$ 个会话，随着数值的增大，这很快就会变成不可行的方案。（2-of-4）需要 6 次会话。（11-of-15）需要 1365 次。（67-of-100）需要 294692427022540 …… 等等。
走向一个更好的解决方案
那么我们还能怎么做呢？这就是我们要从 1 号签名人处收集签名碎片、而不从 3 号签名人处收集签名碎片的关键。我们作一些基本的推理。
我们运行了一次会话，而且没有理由中止这次会话，因为我们不知道其他签名人是否会响应，所以没有理由放弃这次会话。
那个待机的签名人，3 号签名人，如果你要开始一次新的会话，你也不应该把 TA 加进来，因为 TA 看起来很慢。没有理由要跟 TA 开始另一次会话。
另一个关键是，我们需要开始新的会话以保证协议会推进，因为我们不知道较慢的参与者能不能推进协议。所以，我们能做的事情只有一件：开启另一次会话。
我们也看到了，也许 4 号签名人会响应一条 nonce 值，要是 1 号签名人在发送签名时也提供了一个新的 nonce 值就好了；他们可能已经为新的会话准备好了一个 nonce 值以备不时之需。当 4 号签名人的 nonce 值送达时，你就可以立即开始一轮新的会话，因为你已经有了来自两个签名人的 nonce 值了。
假设我们在每一个签名碎片上都附带一个全新的 nonce 值 ……
ROAST
一个想法是，我们要保持会话开启。我们应该维护一组 “待机（无响应）” 的签名人。在开启新的会话时，不要把这些人包括进来。无论什么时候，只要我们有 t 个不处于待机状态的签名人，我们就应该把他们拉进一个会话中。最后，每个签名碎片都要附带一个全新的 nonce 值。
执行案例
假设我们有 4 个签名人，他们在协议开始之时全都处于待机状态。他们全都发送了第一条消息（一个 nonce 值）。1 号签名人的 nonce 值先送达，然后这个签名人就不会被标记为待机状态了。另一个签名人，3 号签名人的 nonce 值也送达了，所以 TA 也不是待机状态了。现在，协调员将这两位签名人分到同一个会话中。这就是我们开启的第一轮会话。
现在，我们发回一个 acknonce 值。也许某个签名人会响应一个签名碎片。一旦这个签名人完成了第一次会话，我们就可以说，这个参与者就不再处于这个会话中了。只要你有两个不是待机状态的签名人，你就把他们放在一轮新的会话中。
这时候，我认为，下一条消息就可以结束执行。我们已经知道了 2 个诚实的签名人愿意签名，而且他们的消息最终会送达。无论这两个签名人是谁，至少你有一个会话会完成。不论恰好是哪一个会话走完，都不重要。
现在，我们可以保证我们总是能完成协议了。
关键的不变量
让这套协议可以工作的关键不变量在于，每一个签名人都最多只能在一次会话中待机。它基于一个事实：无论什么时候我们把一个签名人标记为待机状态，我们都可以确保不在未来的会话中引入这个签名人。每个签名人都最多只能挂起一个会话，因为一旦 TA 这么做了，我们的下一次会话就不会包括这个签名人了。
健壮性
这里，一个不那么正式的健壮性定义是，协调员在初始化至多 (n - t + 1) 次 FROST 会话之后，总能输出一个有效的签名。为了证明这一点，我们要使用一个来自关键不变量的想法：我们已知每个签名人最多只能挂起一个会话。这就意味着，(n - t) 个恶意签名人最多只能挂起 (n - t) 次会话，但因为我们启动了 (n - t + 1) 次会话，所以至少有一次会走完。
若要形成一个准确的证明，我们还需要证明的另一件事情是，我们总能开启一个新的会话。我们知道其中一个签名者最终会响应，因为网络是异步的。所以最终我们总是可以开启一个新的会话，因为有 t 个签名人不是待机掠夺。
这就是基本的原理。写有证明的那篇论文有更多细节。但这些就是让整个协议可以工作的大体想法。
实验性的评估
我们为 ROAST 实现了一个并非最优的 python 原型。椭圆曲线操作是使用一个叫做 “fastecdsa” 的 python 库完成的。在内核上，它使用了 GMP，这是一个通用的 C 语言库。GMP 也不是最优化的，是非常慢的代码。
至于网络设置，我们让旧金山的一台服务器来充当协调员，所有签名者都放在法兰克福的一台服务器上。往返时间为 153 毫秒。这并没有完全反映互联网的条件，只是因为签名人只跟协调员交谈，而不是彼此通信。每一条消息都至少穿越大西洋至少一次。
在此基础上，我们模拟了一个攻击者，比如说，让 (n - t) 个恶意签名人都在第一轮之后宕机。这不是我们能够想象的最强攻击，只是模拟了节点的随机崩溃。或者说他们的网络崩溃。
在此基础上，只要崩溃的签名人没有串通起来，也就是说因为他们不能直接通信，所以无法以 “聪明” 的方式崩溃，那么，如果我们使用的是 11-of-15 的门限签名，那么我们的尚未优化的原型可以在一秒内完成。甚至 67-of-100 这样大规模的参与者集，也可以在 0.7 秒内完成。
我们也模拟了崩溃的签名人可以直接通信并尝试破坏尽可能多会话的情形，但即使在这种最强的攻击之下，我们的 100 个签名人也可以在 1 到 7 秒内结束。这意味着有 33 个签名人主动阻止你获得签名。如果你遇到这种情形，你可能会考虑迁移到一个新的联盟，但即使如此我们也能在 7 秒内完成。
去除协调员
我已经讲了许多，你无需信任协调员，只需要在网络假设上依赖他们。但是，如果你还是不喜欢一个受信任的协调员，认为他们可以让协议停滞，那么你可以剔除掉协调员，只需要为通信投入更多的精力就行。我们知道，至多有 (n - t) 个恶意的签名人，所以只要你运行 (n - t + 1) 次重复的 ROAST 协议，并使用 (n - t +1) 个签名人作为协调员，那么我们知道至少有一个协调员会是值得信任的 …… 因此我们知道这一样走得通，因为有一个诚实的协调员。这提高了通信次数 (n - t + 1) 倍，但可以去除中心化的协调员。
总结
ROAST 将 FROST 转化成了一个在异步网络中也能保持健壮性（抗 DoS 的）门限签名协议。它依然简洁。而且实际上做的只不过是开启多次 FROST 会话。它的优雅之处在于，它并不难实现，你不需要是一个密码学工程师就能实现它。要实现 ROAST，你只需要聪明地调用 FROST 协议，不需要暴露在你可能搞错的密码学细节中。