如何利用门限签名来生成随机信标？

作者: ALEXANDER SKIDANOV

回顾 2015，DFinity 项目提出了令整个社区都为之兴奋的随机信标方案 —— 使用 BLS 门限签名产生随机输出，同时保证输出的无偏性及不可预测性。然而，时至 2020 年的今天，构建无偏且不可预测的随机信标仍然困难重重，还在研究的项目少之又少。

其实门限签名只是构建随机信标的可行方法之一，我们前面发表过一篇概览文章，介绍其他可能的解决方法，其中包含本文要重点提到的一种。其他细节 —— 随机信标是什么？什么是无偏性及不可预测性？除了门限签名还有什么方法 —— 这些问题都能在上述概览中得到解答。

经过了多次设计迭代，我们最终提出类似 DFinity 的方案，这也是我们进一步深入理解随机信标的大好契机。

本文将以浅显的形式，讲述门限签名生成随机数的一系列协议。

密码学基础知识

为了更好地了解本文中提到的随机信标，我们需要掌握一些基础密码学知识。首先，我们必须区分两个概念：1. 在本文中以小写字母（例如 x、y）表示标量，或者说普通常量；2. 用大写字母表示椭圆曲线上的点（elliptic curve point）。

我们不需要对椭圆曲线点了解得很透彻，只要掌握下面两点：

1、椭圆曲线点可以相加，也可以跟标量相乘（本文里用 xG 表示，用 Gx 表示也很常见），然后得到另一个椭圆曲线点。

2、即使知道 G 和 xG 的值，也不可能计算出 x 的值。

在本文中，我们还将用到 k-1 阶多项式 p(x) ；关于 p(x），你不用想太多，只要把它当成一个方程就好，而且：只要你知道在 k 个不同的 x 下 p(x) 的值，你就能推导出所有 x 的 p(x) 值。

以此类推，对于同一个函数 p(x) 和基点 G，如果你知道 p(x)G 代入 k 个不同的 x 值后的值，就可以推导出所有 x 所对应的 p(x)G 值。

只要明白了有关椭圆曲线点的这些属性，就能深度理解随机信标的工作原理了。

随机信标

假设 1：系统中有 n 个参与者，至少需要其中的 k 位才能产生随机数。就算控制其中的 k-1 人，你也不能预知随机信标的输出结果、无法操纵结果。

假设 2：现在有个 k-1 阶多项式 p(x)，参与者 1 知道 p(1) 的值、参与者 2 知道 p(2) 的值、…… 、参与者 n 知道 p(n) 的值；大家约好使用 G 作为椭圆曲线基点，所有参与者都知道 p(x)G 代入所有 x 的值。我们将 p(i) 视为参与者 i 的 “私人份额（不公开，只有参与者自己知道）” ，而 p(i)G 是其 “公开份额”（所有参与者都能知道这个值）（回想一下前文，我们说过无法从 p(i)G 倒推出 p(i)，所以只有参与者 i 知道 p(i) 的值）

要设计好的随机信标，最困难的部分，就是要找到这么一个多项式，使得每个参与者都能知道自己的私人份额，但是无法知道他人的私人份额——这也被称为分布式密钥生成（DKG，Distributed Key Generation）。DKG 会放在下个章节讨论，现在就先假设存在这么个多项式，而所有人都知道各自的私人份额。

我们接着讨论，如何使用这套假设在区块链协议中产生一个随机信标？假设网络产生一个区块，区块哈希为 h。现在参与者们想用 h 作为种子以生成随机数，首先用约定好的函数，将 h 转换为某条椭圆曲线上的一个点：

H = scalarToPoint(h)

对于参与者 i 来说，因为他知道 p(i) 和 H，所以可以自行计算出 H_i = p(i)H。对外公布 H_i 并不会导致参与者 i 的私人份额 p(i) 暴露，因此在每个区块中都能重用同样的私人份额，因此 DKG 只需要进行一次。

根据前面提到的第三点特性，当至少有 k 位参与者公布他们各自的 H_i = p(i)H 之后，其他人就能知道代入任何一个 x 之后，H_x = p(x)H 是什么。然后所有参与者都可以在自己本地计算 H_0 = p(0)H，并以这个结果的哈希值作为随机信标的输出；请注意，因为没有参与者知道 p(0)，所以唯一能得到 p(0)H 的方法就是对p(x)H 进行内插法（intepolate）计算，要完成内插计算需要知道至少 k 个p(i)H 的值。如果公布的人不足 k 位，则其他人无法推出 p(0)H 的值。

基于此技术构建的信标延续了这些我们所需的特性：如果攻击者只掌控了少于 k-1 位参与者，则他无法操控随机信标的输出；其他 k 位参与者才能计算出最终输出，他们的子集或其他更多的参与者，都能得出相同的输出。

我们还忽略了一件事。为了使用插值法计算 p(0)H，必须保证参与者 i 所公开的 H_i 真的等于 p(i)H。但是因为除了参与者 i，其他参与者都不知道 p(i) 是什么，所以没法直接验证参与者 i 公布的 H_i 是否的确等于 p(i)H；如果不要求为 H_i 附上密码学证明，攻击者可以直接声称某个 H_i 的值，而其他人没有办法辨别真伪。

有至少两种密码学证明办法，可以用来判别 H_i 的真伪。我们会在聊完 DKG 之后介绍。

分布式密钥生成（DKG）

根据前面章节对随机信标的介绍，我们需要 n 位参与者共同使用某个 k-1 阶多项式 p(x)，使得每个参与者 i 知道自己的 p(i)，而其他人无法得知。下一步，需要所有参与者都知道：给定 G 时，所有的 x 所对应的 p(x)g 值。

在本章节，我们假设每个人都有自己的私钥 x_i，而且其他人都知道 x_i 对应的公钥 X_i。

那么运行 DKG 的一种方式如下：

1、每个参与者 i 在本地运行 k-1 阶多项式 p_i(x) 的计算。接着用公钥 X_j 将每个 p_i(j) 加密（ j≠i ）， 并发送给对应的参与者 j 。如此一来，只有参与者 j 能解密出 p_i(j)；参与者 i 还要公布所有 p_i(j)G ，j∈1~k。

2、所有参与者要对一个至少由 k 个多项式组成的集合达成共识。因为有些参与者可能掉线，所以他们不可能等到 n 个验证者都作出如此承诺再进行下一步；只要至少 k 个验证者都作出 “收到至少 k 个这样的多项式” 的承诺之后，他们就可以使用某种形式的共识算法（如，Tendermint）对他们所收到多项式的子集 Z 达成共识（Z 包含至少 k 个多项式）。

3、所有参与者共同验证加密的 p_i(j) 与公开的 p_i(j)G 是否对应，并从 Z 中移除不合格的多项式。

4、对于集合 Z 中的每个多项式 p_i(x) ，每个参与者 j 自行计算 p_i(j) 的总和作为私人份额 p(j) ；同样的，对于集合 Z 中的每个 p_i(x)G ，参与者可以计算 p_i(x)G 的总和作为公开份额 p(x)G。

因为 p(x) 是每个独立的 p_i(x) 的总和，每个 p_i(x) 都是 k-1 阶多项式，所以要观察 p(x) 是否也是 k-1 阶多项式。其次要注意，每个参与者 j 只知道 p(j) 的值，但不知道其他 p(x) （x ≠ j ）的值。实际上，为了知道 p(x）的值，TA 需要知道所有的 p_i(x），只要至少一个被承诺多项式的值属于未知，TA 就不可能知道 p(x)。

上述步骤组成了完整的 DKG 过程。步骤 1、2、4 相对直观，但第 3 步就比较复杂了。

具体来解释第三步 —— 我们需要找个方法，证明每个加密的 p_i(j) 与公开的 p_i(j)G 存在对应关系。如果没有这种验证，攻击者 i 可以向参与者 j 胡乱发送消息，而不是发送正确的加密 p_i(j)，导致参与者 j 无法进一步计算自己的私人份额。

虽然有办法可以制作出加密份额的形式正确性密码学证明。但是，这样的证明数据过大，并且要向全网公布这样的证明，时间复杂度可能高达 O(nk)，证明的 size 是严重的瓶颈。

在 NEAR 协议中，我们不去证明 p_i(j) 与公开的 p_i(j)G 的关系，而是在 DKG 过程中给予每个参与者充分的时间（也就是对多项式集合 Z 取得共识、到最终聚合出私有份额，两个事件之间的时间间隔），去证明“他们收到的 p_i(j) 与公开广播的 p_i(j)G 对不上”。协议中假设每个参与者在窗口期内（大约半天）至少会上线一次，而他们提交的挑战就能进入区块链。对于区块生产者来说，这两个假设都很合理，因为要做区块生产者，一般来说在整个 epoch 中都要在线；如果大多数区块生产者密谋不接收这条消息，其实整个系统就已经不安全，攻击者其实有更好的方式攻击整个系统（而不仅仅是拒收挑战消息）。

假如某个区块生产者收到无效的公开份额，而且没有及时在 DKG 过程中提出挑战，则该矿工也无法在该时段中参与随机数生成。请注意，只要其他 k 个诚实的参与者都能正确计算出份额（通过不接收任何无效份额，或及时挑战所有无效份额），协议仍将正常运作。

证明

还剩下最后一个问题：我们如何以不透露 p(i) 为前提，证明自己公布的 H_i 等于 p(i)H？

回想一下，每个参与者都知道 H、G 、p(i)G 的值。在给定 p(i)G 和 G 的情况下回推 p(i) 的运算被称为离散对数问题，又简称为 dlog 。那么每个参与者想做的都是：既能向他人证明 dlog(p(i)G, G) = dlog(H_i, H)，又不会透露 p(i)。的确存在这么一种方法构建上述证明，其中之一就是 —— Schnorr 协议；通过 Schnorr 协议，参与者能在发布 H_i 时附上 H_i 的正确性证明。

回想一下，随机信标连的输出是 H_0 的内插值（interpolated value）。对于没有参与生成随机信标输出的人来说，除了 H_0，还需要哪些信息来验证这个值的正确性？因为每个人都能自行在本地计算中加入 G_0，所以只要证明 dlog(G_0, G) = dlog(H_0, H) 就行了。但因为信标的特性，我们无法得知 p(0)，也就无法通过 Schnorr 协议生成这样的证明。所以如果你要向其他人证明 H_0 的正确性，就必须保留所有 H_i 的值及其相应的证明。

不过，好消息是，如果有些计算类似于椭圆曲线点乘法，则只需验证 H_0 × G = G_0 × H 即可证明 H_0 的计算正确无误。

如果所选的椭圆曲线支持椭圆曲线配对运算（elliptic curve pairings），则这种证明是可行的。在这种情况下，任何知道 G，H 和 G_0 的人都可以核实 H_0（随机信标的输出）；而且 H_0 也可视作一个集体的多重签名，证明区块 n 的正确性得到至少 k 位参与者的检查认证。

目前我们还未在 NEAR 中使用椭圆曲线配对运算，但未来我们可能会使用，然后利用上文讨论的小技巧取代我们当前使用的单一签名方法。另一方面，DFinity 使用 BLS 签名，可以利用配对运算来实现上述签名。