8

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

 5 years ago
source link: https://news.huoxing24.com/20200307164559860780.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

作者: ALEXANDER SKIDANOV

翻译 &校对: IAN LIU &阿剑

来源：以太坊爱好者

回顾 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 人，你也不能预知随机信标的输出结果、无法操纵结果。

ryyQR3A.jpg!web

假设 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 的值。

aqiAZfJ.jpg!web

基于此技术构建的信标延续了这些我们所需的特性：如果攻击者只掌控了少于 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 的值，而其他人没有办法辨别真伪。

iE73Ajv.jpg!web

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

分布式密钥生成（DKG）

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

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

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

VrEbQj6.jpg!web

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。

iaA7reV.jpg!web

因为 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 中都要在线；如果大多数区块生产者密谋不接收这条消息，其实整个系统就已经不安全，攻击者其实有更好的方式攻击整个系统（而不仅仅是拒收挑战消息）。

iABfInI.jpg!web

假如某个区块生产者收到无效的公开份额，而且没有及时在 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 签名，可以利用配对运算来实现上述签名。

原文链接： https://nearprotocol.com/blog/randomness-threshold-signatures/


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK