引介

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

Ajian   |     |   581 次阅读

区块链协议中的随机性


回顾 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 签名,可以利用配对运算来实现上述签名。

(完)


原文链接: https://nearprotocol.com/blog/randomness-threshold-signatures/
作者: ALEXANDER SKIDANOV
翻译&校对: IAN LIU & 阿剑

本文由作者授权 EthFans 翻译及再出版。


你可能还会喜欢:

密码学极速入门,Part-1

理解 BLS 签名算法

详解 MimbleWimble 协议

 
0 人喜欢