夸克区块链NEAR：基于门限签名的随机信标如何工作

早在 2015 年，DFinity 就设计了一种随机信标，让技术社区的人们感到极度振奋。该信标利用了 BLS(Boneh-Lynn-Shacham) 门限签名技术来产生无偏见且不可预测的随机输出。

到了 2020 年，建立无偏见且不可预测的随机信标仍然极具挑战性，在很少的协议里获得实际的使用。门限签名并不是唯一的方案，我们先前已发布了一篇博文，是有关其他各种随机性方法的简短概述，其中包括一个我们当时考虑过的方法。想要详细了解随机信标是什么，无偏见和不可预测的含义以及除了门限签名之外还有哪些方法，请参考这篇博文。

经过多次设计的迭代，我们最终完成了随机信标，与 DFinity 的设计有很多相似之处，这是深入了解此类随机信标到底如何工作的绝佳机会。

在这篇博文中，我们将以非常简单的方式描述使用门限签名生成随机数的这个复杂协议。让我们开始吧

Crypto?Fundamentals 密码学基础

为了理解本文中描述的随机信标，我们需要知道一些非常基础的密码学知识。我们要区分两个概念：标量，或者叫做普通数字，我们通篇用小写字母表示（例如：x，y）；以及椭圆曲线上的点，我们用大写字母表示。

除了以下几点，我们无需了解更多有关椭圆曲线点的特性:

椭圆曲线上的点可以相加，也可以乘以一个标量（我们将其记为 xG，也常用 G^x 表示）。这两种操作的结果都将是另一个椭圆曲线上的点。

知道 G 和 xG 是无法推导出 x 的。

给定阶数为 k-1 的多项式 p(x)，众所周知，如果知道任意 k 个不同 x 对应的 p(x) 值，他们就可以计算任意其他 x 所对应的 p(x) 值。对于相同的多项式和某些椭圆曲线点 G，如果知道 x 的任意 k 个不同值对应的 p(x)G 值，他们也可以计算其他 x 对应的 p(x)G。

本文只需要在较高层面上了解随机信标的工作方式，所以知道这些关于椭圆曲线的性质就足够了。

The Randomness Beacon 随机信标

假设有 n 位参与者，而我们要达到这样的特性：至少需要 k 位参与者才能生成一个随机数，而控制不超过 k-1 位参与者的对手无法预测随机信标的输出，并且也不能以任何方式影响它。

假设存在一个 k-1 阶的多项式 p(x)，第一个参与者知道 p(1)，第二个参与者知道 p(2)，第 n 个参与者知道 p(n)。另外假设，对于某个商定的椭圆曲线点 G，对于 x 的所有值，所有参与者都知道 p(x)G。我们将 p(i) 称为参与者 i 的私有份额（因为只有参与者 i 知道），而将 p(i)G 称为参与者 i 的公开份额（因为每个人都知道）。回想上一节所说的特性，从 p(i)G 不足以推出 p(i)。

生成这样一种多项式，即，让每个参与者了解自己的私有份额而看不到其他参与者的私有份额，这是随机信标最复杂的部分，也就是所谓的 DKG（分布式密钥生成）。我们将在下一节中介绍它。现在，假设存在这样的多项式，并且所有参与者都知道他们的份额。

让我们看看如何在区块链协议上下文中使用它来生成随机信标。假设生成块的哈希为 h，并且参与者希望一起生成以 h 为种子的随机数。方法是，首先使用某个商定的函数将 h 转换为椭圆曲线点：

H = scalarToPoint(h)

然后，每个参与者 i 计算 H_i = p(i)H，因为知道 p(i) 和 H，所以他们可以这样做。展示 H_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 进行插值，这只有在展示了至少 k 个 p(i)H 时才有可能。展示任何少于该数量的 p(i)H 都无法推出 p(0)H 的值。

上面的信标具有我们期望的所有属性：控制 k-1 个或更少参与者的对手无法了解随机信标的最终输出，而任何 k 个参与者都可以计算最终输出，并且 k 个或更多参与者的任何子集 将始终得到相同的值。

有一个问题是我们目前忽略了的。就是为了使插值有效，我们需要确保第 i 个参与者展示的 H_i 确实等于 p(i)H。由于没有其他参与者知道 p(i)，他们自然无法验证 H_i 的正确性，并且如果没有对 H_i 附带任何密码学证明，恶意行为者便可以展示任意值，其他参与者将无法检测出来。

至少有两种方法可以提供 H_i 正确的密码学证明，在下两节之后，即讨论了 DKG 之后，我们将介绍这两种方法。

为了使上一节中的随机信标起作用，我们需要 n 个参与者共同得出阶为 k-1 的多项式 p(x)，以使每个参与者 i 都知道 p(i) 的值，且其他参与者无法得知。同时，为了下一节中的构造，对于某个商定的 G 和所有 x，所有参与者都必须知道 p(x)G。

在本节中，我们假设每个参与者都拥有一个私钥 x_i，并且所有参与者都知道与该私钥相对应的公钥 X_i。

Oney way to go about DKG is then the following:

DKG 的一种实现方式如下：

1. 每个参与者 i 在本地计算阶为 k-1 的多项式 p_i(x)。然后，他们向其他每个参与者，假定为第 j 个，发送使用其对应公钥 X_j 加密过的 p_i(j)，以便只有第 j 个参与者可以解码 p_i(j)。参与者 i 还公开宣布 j 从 1 到 k 的所有 p_i(j)G

2. 所有参与者共同同意至少 k 个按上述方法提交的多项式集。由于某些参与者可能离线，因此他们无法等待所有的 n 个参与者全部提交，但是只要至少 k 个参与者提交了，他们就可以使用任何形式的共识算法（例如 Tendermint）在至少 k 个多项式的子集 Z 上达成共识。

3. 参与者共同验证加密的 p_i(j) 对应于公开发布的 p_i(j)G。并从 Z 中删除不符合的多项式。

4. 每个参与者 j 计算其私有份额 p(j) 为 Z 中每个 i 的 p_i(j) 之和。每个参与者还可以计算任意参与者 x 的公共份额 p(x)G 为 Z 中每个 i 的 p_i(x)G 之和。

注意到 p(x) 实际上是阶为 k-1 的多项式，因为它是各个 p_i(x) 的和，而每个 p_i(x) 是阶为 k-1 的多项式。然后，请注意，尽管每个参与者 j 都知道 p(j)，但他们对 x ≠ j 的其他 p(x) 的值都不了解。确实，要知道这样的值，他们需要知道所有的 p_i(x)，并且只要参与者 j 少知道至少一个提交的多项式，他就无法知道 p(x)。

这就是 DKG 的整个过程。上面的步骤 1、2 和 4 比较简单。步骤 3 是让 DKG 变得棘手的地方。

具体来说，我们需要某种方法来证明每个加密的 p_i(j) 确实对应于公开的 p_i(j)G。如果没有验证方法，对手 i 可以将一些胡乱信息发送给参与者 j，而不是实际加密的 p_i(j)，这样参与者 j 将无法在以后计算其私有份额。

有一种方法可以创建一个密码学证明，以证明加密过份额的正确性。但是，这种证明的尺寸过大，由于需要公开的量级高达 O(nk)，因此证明的大小成为瓶颈。

我们没有在 NEAR 中以密码学证明 p_i(j) 对应于 p_i(j)G，而是在 DKG 期间，在达成多项式集共识的那一刻与汇总最终份额的那一刻之间留出了一大段时间。在此期间，每个参与者可以提交密码学证明，表示发送给他们的加密共享 p_i(j) 与公开广播的 p_i(j)G 不对应。它假设每个参与者在该时间段（大约半天）内至少会上网一次，使他们提交的挑战上链。对于出块人，这两个假设都是相当现实的。因为预计出块人将在整个时期保持在线状态，并且如果要对消息进行删剪，需要串谋大多数的出块人，让他们不要将挑战计入块中。如有他们已经有这样的能力，那就已经拥有更多更有利可图的方式去攻击系统了。

如果某个特定的出块人确实收到了无效的份额，然后在 DKG 期间没有出现并挑战它，则他们将无法在同一个 epoch 中参与生成随机数。请注意，只要有 k 个其他诚实参与者拥有其份额（要么是未接收任何无效份额，要么是及时挑战了所有无效份额），该协议仍将起有效。

Proofs 证明

回想一下，所有人都已知值 H、G、p(i)G。在给定 p(i)G 和 G 计算 p(i) 的运算被称为离散对数，或简称 dlog，每个参与者想要向他人证明的是：

dlog(p(i)G, G) = dlog(H_i, H)

回想一下，随机信标的最终输出是 H_0。对于未参与生成该信息的外部参与者，需要与 H_0 一起分发哪些信息以便能验证其正确性？由于每个人都可以在本地插值 G_0，因此证明：

dlog(G_0, G) = dlog(H_0, H)

回想一下，随机信标的最终输出是 H_0。对于未参与生成该信息的外部参与者，需要与 H_0 一起分发哪些信息以便能验证其正确性？由于每个人都可以在本地插值 G_0，因此证明：

dlog(G_0, G) = dlog(H_0, H)

H_0 × G = G_0 × H

但是，如果有某种运算类似于椭圆曲线点上的乘法，通过证明以下等式就能证明 H_0 计算正确：

H_0 × G = G_0 × H

如果所选的椭圆曲线支持所谓的椭圆曲线配对，则这样的证明变得可能。在这种情况下，H_0 不仅可以作为随机信标的输出，让知道 G、H 和 G_0 的任何人轻松验证，而且它还可以用作集体多签，证明 n 个区块生产者中至少有 k 个签名了区块。

尽管 NEAR 现在没有使用椭圆曲线配对，但将来是有可能使用的，并且上面讨论的技巧将替代 NEAR 现在使用的单签。另一方面，DFinity 设计中使用了 BLS 签名并可以利用椭圆曲线配对来让多重签名工作。

随机信标在我们参考客户端实现中几乎已经完成，但很可能不会随第一版 NEAR 协议发布，以留出更多时间完善其稳定性。一旦随机信标发布，所有 NEAR 平台上的智能合约将能够享受到中立且不可预测的随机数生成器，这将带来更多目前在其他区块链上无法实现的使用场景。

NEAR 协议的首个发布版本将使用更简单的随机信标，其中的随机值只是当前区块生产者的随机信标的先前输出，然后通过可验证随机函数输出的值。这个随机信标虽然不可预测，但不是中立的：当前区块生产者会产生影响，因为他们可以选择不生产区块。这恰好和以太坊?2.0 在 VDFs 信标可用之前所使用的随机信标非常相似（随机输出是当前区块生产者在 epoch hash 的 VRF），也和 Elrond 的随机信标机制相同。

如果你对区块链协议如何工作感兴趣，欢迎来了解 Whiteboard Series with NEAR 视频系列，我们会在节目中和其他协议（比如以太坊 Serenity、Cosmos、Polkadot 等）的创始人和核心开发者聊技术的细节。

NEAR 是 Open Web 的基础架构，也是一个分片区块链协议。你可以通过分片设计论文、深度视频系列、或我们的 Rust 参考客户端实现来深入了解我们的技术。

夸克区块链也采用了这样的技术，夸克区块链是一个可开放的公共区块链，类似互联网基础设施，有底层协议核心区块链技术，使用与比特币安全强度一致加密算法，支持第三方应用开发，与其他类似激励机制项目，其落地场景就是想利用区块链技术去中心化的共识方式，在社交领域建立一个为社交贡献定价，并提供权益回报的网络，使内容生产者、投资者、筛选者和生态建设者都能得到合理的激励与回报。并且落地产品已经快开发完成。场内场外，落地APP，项目白皮书，区块链浏览器，对接主流交易所，主链开发，基金会发起，海内外数字牌照上有一整套技术解决方案。

—-

编译者/作者：链家子

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。