原文标题：《NEAR 前沿｜基于门限签名的随机信标如何工作》
原文来源：NEAR 中文社区
原作者简介：
Alexander Skidanov 是 NEAR Protocol 的两位联合创始人之一，曾在 2008 年获得 ACM-ICPC 金牌（注：ICPC 是世界最高级别的大学生编程竞赛）。Alex 曾就职于微软，并作为第一位工程师加入了 MemSQL，参与编写、构架了世界上最快的分布式关系数据库，被 Uber、高盛、索尼、Intel 等公司采用。
小编：NEAR 联合创始人 Alex 和前 Cosmos 联合创始人 Zaki 在白板前共同讨论状态分片等目前底层区款链技术面对的各种技术难题
正文：
Back in 2015 DFinity made the community extremely excited with their design of a randomness beacon that was leveraging BLS threshold signatures to produce a randomness output that is both unbiasable and unpredictable.
早在 2015 年，DFinity 就设计了一种随机信标，让技术社区的人们感到极度振奋。该信标利用了 BLS(Boneh-Lynn-Shacham) 门限签名技术来产生无偏见且不可预测的随机输出。
As of 2020 building an unbiasable and unpredictable randomness beacon remains extremely challenging, and very few protocols have one live. Threshold signatures is not the only proposed approach, and we previously published a short overview of various other approaches to randomness, including an approach that we considered back then in this blog post. Refer to it for the details on what the randomness beacon is, what it means to be unbiasable and unpredictable, and what approaches besides threshold signatures were proposed.
到了 2020 年，建立无偏见且不可预测的随机信标仍然极具挑战性，在很少的协议里获得实际的使用。门限签名并不是唯一的方案，我们先前已发布了一篇博文，是有关其他各种随机性方法的简短概述，其中包括一个我们当时考虑过的方法。想要详细了解随机信标是什么，无偏见和不可预测的含义以及除了门限签名之外还有哪些方法，请参考这篇博文。
After multiple iterations of design, we ultimately ended up building something very similar to what DFinity uses, and that is a great opportunity to dive deep into how such randomness beacons work.
经过多次设计的迭代，我们最终完成了随机信标，与 DFinity 的设计有很多相似之处，这是深入了解此类随机信标到底如何工作的绝佳机会。
In this post we will describe the complex protocol of using threshold signatures to generate random numbers in very simple terms. Let』s dive in!
在这篇博文中，我们将以非常简单的方式描述使用门限签名生成随机数的这个复杂协议。让我们开始吧！
Crypto Fundamentals 密码学基础
For the purpose of understanding randomness beacons in this article, we will need to understand some very basic cryptography. We need to differentiate between two concepts: scalars, or just regular numbers, which throughout this article we will denote with lowercase letters (e.g. x, y) and elliptic curve points, which we will denote with uppercase letters.
为了理解本文中描述的随机信标，我们需要知道一些非常基础的密码学知识。我们要区分两个概念：标量，或者叫做普通数字，我们通篇用小写字母表示（例如：x，y）；以及椭圆曲线上的点，我们用大写字母表示。
We don』t need to understand much about elliptic curve points, besides a few properties:
Elliptic curve points can be added together, and an elliptic curve point can be multiplied by a scalar (we will denote it as xG, though a notation G^x is also very common). The result of both operations is another elliptic curve point.
Knowing G and xG it is computationally infeasible to derive x.
Given a polynomial p(x) of degree k-1, it is well known that if one knows the value of p(x) at any k distinct values of x, they can also evaluate p(x) at any other x as well. For the same polynomial, and some elliptic curve point G, if one knows the value of p(x)G at any k distinct values of x, they can also evaluate p(x)G at any other x.
除了以下几点，我们无需了解更多有关椭圆曲线点的特性:
椭圆曲线上的点可以相加，也可以乘以一个标量（我们将其记为 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。
Those are the only properties of elliptic curve points we will need to understand on the high level how randomness beacons work.
本文只需要在较高层面上了解随机信标的工作方式，所以知道这些关于椭圆曲线的性质就足够了。
The Randomness Beacon 随机信标
Say there are n participants, and say we want to require that it takes at least k of them to generate a random number, and that an adversary that controls up to k-1 of the participants cannot predict the output of the randomness beacon, and cannot influence it in any way.
假设有 n 位参与者，而我们要达到这样的特性：至少需要 k 位参与者才能生成一个随机数，而控制不超过 k-1 位参与者的对手无法预测随机信标的输出，并且也不能以任何方式影响它。
Say there exists some polynomial p(x) of degree k-1 such that the first participant knows p(1), the second participant knows p(2), and the n-th participant knows p(n). Also say that for some agreed-upon elliptic curve point G everybody knows p(x)G for all values of x. We will call p(i) a private share of participant i (because only participant i knows it), and p(i)G public share of participant i (because everybody knows it). Recall from the previous section that the knowledge of p(i)G is not sufficient to derive p(i).
假设存在一个 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)。
Generating such a polynomial in a way that each participant knows their private share, but has no insight into the private shares of other participants is the most complex part of the randomness beacon, and is what is called Distributed Key Generation. We will cover it in the next section. For now let』s assume such a polynomial exists, and all the participants know their shares.
生成这样一种多项式，即，让每个参与者了解自己的私有份额而看不到其他参与者的私有份额，这是随机信标最复杂的部分，也就是所谓的 DKG（分布式密钥生成）。我们将在下一节中介绍它。现在，假设存在这样的多项式，并且所有参与者都知道他们的份额。
Let』s see how to use it to have a randomness beacon in the context of a blockchain protocol. Say a block with hash h is produced, and the participants collectively want to generate a random number seeded by h. The way they proceed is first use some agreed upon function to convert h into an elliptic curve point:
让我们看看如何在区块链协议上下文中使用它来生成随机信标。假设生成块的哈希为 h，并且参与者希望一起生成以 h 为种子的随机数。方法是，首先使用某个商定的函数将 h 转换为椭圆曲线点：
H = scalarToPoint(h)
Then each participant i computes H_i = p(i)H, which they can do because they know p(i) and H. Revealing H_i will not reveal their private share, so the same private shares can be reused for each block, thus the DKG only needs to be performed once.
然后，每个参与者 i 计算 H_i = p(i)H，因为知道 p(i) 和 H，所以他们可以这样做。展示 H_i 不会泄露其私有份额，相同的私有份额可以在每个块中重复使用，因此 DKG 只需要执行一次。
When at least k participants revealed their shares H_i = p(i)H, everyone can reconstruct any share H_x = p(x)H for any x due to the third property in the previous section. At this point each participant can locally compute H_0 = p(0)H, and use the hash of it as the randomness beacon output. Note that since no participant knows p(0), the only way to compute p(0)H is to interpolate p(x)H, which is only possible if at least k of p(i)H were revealed. Revealing any smaller number of p(i)H gives no insight into the value of p(0)H.
当至少 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 的值。
The beacon above has all the properties we desire: an adversary controlling k-1 or fewer participants cannot get any insight into the final output of the randomness beacon, while any k participants can compute the final output, and any subset of k or more participants will always arrive at the same value.
上面的信标具有我们期望的所有属性：控制 k-1 个或更少参与者的对手无法了解随机信标的最终输出，而任何 k 个参与者都可以计算最终输出，并且 k 个或更多参与者的任何子集 将始终得到相同的值。
There is one issue we ignored above. For the interpolation to work, we need to make sure that the value H_i that the i-th participant revealed is indeed equal to p(i)H. Since no other participant knows p(i), they cannot naively verify that H_i is indeed correct, and without some cryptographic proof alongside H_i a malicious actor can reveal arbitrary value, and other participants will have no way of detecting it.
有一个问题是我们目前忽略了的。就是为了使插值有效，我们需要确保第 i 个参与者展示的 H_i 确实等于 p(i)H。由于没有其他参与者知道 p(i)，他们自然无法验证 H_i 的正确性，并且如果没有对 H_i 附带任何密码学证明，恶意行为者便可以展示任意值，其他参与者将无法检测出来。
There are at least two ways to provide a cryptographic proof of H_i being correct, we will cover both of them two sections below, after we talk about DKG.
至少有两种方法可以提供 H_i 正确的密码学证明，在下两节之后，即讨论了 DKG 之后，我们将介绍这两种方法。
Distributed Key Generation 分布式秘钥生成
For the randomness beacon in the previous section to work, we needed n participants to collectively come up with a polynomial p(x) of degree k-1 such that each participant i knows the value of p(i), but no other participant has any insight into that value. For the constructions in the next section it will also be necessary that all the participants know p(x)G for some agreed upon G and all x.
为了使上一节中的随机信标起作用，我们需要 n 个参与者共同得出阶为 k-1 的多项式 p(x)，以使每个参与者 i 都知道 p(i) 的值，且其他参与者无法得知。同时，为了下一节中的构造，对于某个商定的 G 和所有 x，所有参与者都必须知道 p(x)G。
Throughout this section we assume that every participant has some private key x_i associated with them, and all the participants know the public key X_i that corresponds to such a private key.
在本节中，我们假设每个参与者都拥有一个私钥 x_i，并且所有参与者都知道与该私钥相对应的公钥 X_i。
Oney way to go about DKG is then the following:
DKG 的一种实现方式如下：
1.Each participant i locally computes some polynomial p_i(x) of degree k-1. They then send p_i(j) to each participant j encrypted with the public key X_j, so that only j-th participant can decode p_i(j). Participant i also publicly announces p_i(j)G for all j from 1 to k inclusive.
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.All the participants collectively agree on some set of at least k such committed polynomials. Since some participants can be offline, they can』t wait until all n of them commit, but once at least k have committed, they can use any sort of consensus algorithm (for example Tendermint) to agree on some subset Z of at least k polynomials.
2. 所有参与者共同同意至少 k 个按上述方法提交的多项式集。由于某些参与者可能离线，因此他们无法等待所有的 n 个参与者全部提交，但是只要至少 k 个参与者提交了，他们就可以使用任何形式的共识算法（例如 Tendermint）在至少 k 个多项式的子集 Z 上达成共识。
3.The participants collectively verify that the encrypted p_i(j) corresponds to the publicly announced p_i(j)G. The polynomials for which it is not the case are removed from Z.
3. 参与者共同验证加密的 p_i(j) 对应于公开发布的 p_i(j)G。并从 Z 中删除不符合的多项式。
4.Each participant j computes their private share p(j) as the sum of p_i(j) for each i in Z. Each participant can also compute each public share p(x)G as the sum of p_i(x)G for each i in Z.
4. 每个参与者 j 计算其私有份额 p(j) 为 Z 中每个 i 的 p_i(j) 之和。每个参与者还可以计算任意参与者 x 的公共份额 p(x)G 为 Z 中每个 i 的 p_i(x)G 之和。
Observe that p(x) is indeed a polynomial of degree k-1, because it is the sum of individual p_i(x), each of which is a polynomial of degree k-1. Then, note that while each participant j knows p(j), they have no insight into the values of other p(x) for x ≠ j. Indeed, to know such a value they』d need to know all p_i(x), and for as long as the participant j doesn』t know at least one of the committed polynomials, they don』t have any information about p(x).
注意到 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)。
This constitutes the entirety of the DKG process. Steps 1, 2 and 4 above are relatively straightforward. Step 3 is where DKG gets tricky.
这就是 DKG 的整个过程。上面的步骤 1、2 和 4 比较简单。步骤 3 是让 DKG 变得棘手的地方。
Specifically, we need some way to prove that each encrypted p_i(j) indeed corresponds to the publicly broadcasted p_i(j)G. Without a way to verify it, an adversary i can send some gibberish information to participant j instead of actual encrypted p_i(j), and participant j will have no way to compute their private share later.
具体来说，我们需要某种方法来证明每个加密的 p_i(j) 确实对应于公开的 p_i(j)G。如果没有验证方法，对手 i 可以将一些胡乱信息发送给参与者 j，而不是实际加密的 p_i(j)，这样参与者 j 将无法在以后计算其私有份额。
There』s a way to create a cryptographic proof of correctness of the encrypted share. However, the size of such a proof is prohibitively large, and given that O(nk) such proofs need to be published, the size of the proof becomes a bottleneck.
有一种方法可以创建一个密码学证明，以证明加密过份额的正确性。但是，这种证明的尺寸过大，由于需要公开的量级高达 O(nk)，因此证明的大小成为瓶颈。
Instead of proving cryptographically that p_i(j) corresponds to p_i(j)G in NEAR we instead allocate a lot of time during DKG between the moment the set of polynomials is agreed upon and the moment the final shares are aggregated, during which each participant can provide a cryptographic proof that the encrypted share p_i(j) sent to them doesn』t correspond to the publicly broadcasted p_i(j)G. It makes an assumption that each participant will go online at least once during that time frame (which spans approximately half a day), and that the challenge they submit will make it to the blockchain. In the case of block producers both assumptions are rather realistic, since the block producers are expected to remain online throughout the epoch, and for a message to be censored majority of block producers need to collude and not include it in their blocks, in which case they have significantly more profitable ways to attack the system.
我们没有在 NEAR 中以密码学证明 p_i(j) 对应于 p_i(j)G，而是在 DKG 期间，在达成多项式集共识的那一刻与汇总最终份额的那一刻之间留出了一大段时间。在此期间，每个参与者可以提交密码学证明，表示发送给他们的加密共享 p_i(j) 与公开广播的 p_i(j)G 不对应。它假设每个参与者在该时间段（大约半天）内至少会上网一次，使他们提交的挑战上链。对于出块人，这两个假设都是相当现实的。因为预计出块人将在整个时期保持在线状态，并且如果要对消息进行删剪，需要串谋大多数的出块人，让他们不要将挑战计入块中。如有他们已经有这样的能力，那就已经拥有更多更有利可图的方式去攻击系统了。
If a particular block producer does receive an invalid share, and then fails to show up during DKG and challenge it, they will not be able to participate in generating random numbers during the same epoch. Note that for as long as k other honest participants have their shares (by either not receiving any invalid shares, or challenging all the invalid shares in time), the protocol will still function.
如果某个特定的出块人确实收到了无效的份额，然后在 DKG 期间没有出现并挑战它，则他们将无法在同一个 epoch 中参与生成随机数。请注意，只要有 k 个其他诚实参与者拥有其份额（要么是未接收任何无效份额，要么是及时挑战了所有无效份额），该协议仍将起有效。
Proofs 证明
The last part of the randomness beacon that is still left uncovered is how one can prove that a published value H_i is equal to p(i)H without revealing p(i).
随机信标最后一部分未揭晓的内容是如何可以在没有披露 p(i) 的情况下，证明公开值 H_i 等于 p(i)H。
Recall that the values H, G, p(i)G are all known to everybody. The operation that computes p(i) given p(i)G and G is called discrete logarithm, or dlog for short, and what each participant wants to prove to others is that
dlog(p(i)G, G) = dlog(H_i, H)
回想一下，所有人都已知值 H、G、p(i)G。在给定 p(i)G 和 G 计算 p(i) 的运算被称为离散对数，或简称 dlog，每个参与者想要向他人证明的是：
dlog(p(i)G, G) = dlog(H_i, H)
Without revealing p(i). Constructions for such proof do exist, one such construction is called Schnorr Protocol. With such a construction, whenever a participant submits H_i, they also submit a proof of correctness of H_i.
在不披露 p(i) 的情况下，构造如此证明的确存在，其中一例就叫作 Schnorr 协议。通过这种构造，每当参与者提交 H_i 时，他们也提交了 H_i 正确性的证明。
Recall that the final randomness beacon output is the interpolated value of H_0. What information needs to be distributed along with H_0 for external participants that didn』t participate in the generation of it to be able to verify its correctness? Since everybody can locally interpolate G_0, a proof that
dlog(G_0, G) = dlog(H_0, H)
回想一下，随机信标的最终输出是 H_0。对于未参与生成该信息的外部参与者，需要与 H_0 一起分发哪些信息以便能验证其正确性？由于每个人都可以在本地插值 G_0，因此证明：
dlog(G_0, G) = dlog(H_0, H)
Would suffice, but we cannot use the Schnorr Protocol to create such a proof, since it requires the knowledge of p(0), and the randomness beacon relies on nobody knowing the value. Thus, one needs to keep all the values of H_i along with the corresponding proofs to prove the correctness of H_0 to external observers.
但我们不能使用 Schnorr 协议来推出如此证明，因为它需要 p(0) 知识，并且随机信标依赖于没人知道其值。因此需要保留所有 H_i 的值以及向外部观察者证明 H_0 正确性的对应证据。
However, if there was some operation that semantically resembled multiplication on elliptic curve points, proving that H_0 was computed correctly would become trivial, by just verifying that
H_0 × G = G_0 × H
但是，如果有某种运算类似于椭圆曲线点上的乘法，通过证明以下等式就能证明 H_0 计算正确：
H_0 × G = G_0 × H
If the chosen elliptic curve supports so-called elliptic curve pairings, such a proof becomes possible. In such a case H_0 not only serves as output of the randomness beacon that can be trivially verified by anyone who knows G, H and G_0, but also it serves as a collective multi-signature that attests that at least k out of n block producer signed the block.
如果所选的椭圆曲线支持所谓的椭圆曲线配对，则这样的证明变得可能。在这种情况下，H_0 不仅可以作为随机信标的输出，让知道 G、H 和 G_0 的任何人轻松验证，而且它还可以用作集体多签，证明 n 个区块生产者中至少有 k 个签名了区块。
We do not use elliptic curve pairings in NEAR today, though we might use them in the future, and then the neat trick discussed above would replace the individual signatures we use today. DFinity, on the other hand, uses BLS signatures and can leverage the pairings to make such multi-signatures work.
尽管 NEAR 现在没有使用椭圆曲线配对，但将来是有可能使用的，并且上面讨论的技巧将替代 NEAR 现在使用的单签。另一方面，DFinity 设计中使用了 BLS 签名并可以利用椭圆曲线配对来让多重签名工作。
Outro 结束语
The implementation of the randomness beacon is mostly complete in our reference client implementation (see this commit), however, the first version of NEAR Protocol will likely launch without it, to allow more time for stabilization of the beacon. Once it is shipped, however, all the contracts on NEAR will enjoy access to unbiasable and unpredictable random number generator, which enables many uses cases not possible today on other networks.
随机信标在我们参考客户端实现中几乎已经完成，但很可能不会随第一版 NEAR 协议发布，以留出更多时间完善其稳定性。一旦随机信标发布，所有 NEAR 平台上的智能合约将能够享受到中立且不可预测的随机数生成器，这将带来更多目前在其他区块链上无法实现的使用场景。
The first release of NEAR Protocol will use a significantly simpler randomness beacon (see this pull request), where the random value is just the output of a verifiable random function on the previous output of the random beacon by the current block producer. Such a randomness beacon is unpredictable, but is not unbiasable: the current block producer has one bit of influence because they can choose not to produce a block. It happens to be very similar to the randomness beacon that Ethereum 2.0 will use before they have the VDFs beacon available (the randomness output is the VRF by the current block producer on the epoch hash), and is also the way the randomness beacon works in Elrond.
NEAR 协议的首个发布版本将使用更简单的随机信标，其中的随机值只是当前区块生产者的随机信标的先前输出，然后通过可验证随机函数输出的值。这个随机信标虽然不可预测，但不是中立的：当前区块生产者会产生影响，因为他们可以选择不生产区块。这恰好和以太坊 2.0 在 VDFs 信标可用之前所使用的随机信标非常相似（随机输出是当前区块生产者在 epoch hash 的 VRF），也和 Elrond 的随机信标机制相同。
If you are interested in how blockchain protocols work, check out our Whiteboard Series with NEAR, in which we talk to the founders and core developers of other protocols, such asEthereum Serenity, Cosmos, Polkadot, and many others, and dive deep into the details of their technology. All the video episodes are conveniently assembled into a playlist here.
如果你对区块链协议如何工作感兴趣，欢迎来了解 Whiteboard Series with NEAR 视频系列，我们会在节目中和其他协议（比如以太坊 Serenity、Cosmos、Polkadot 等）的创始人和核心开发者聊技术的细节。
NEAR Protocol is an infrastructure for open web and a sharded blockchain protocol. You can learn more about our technology in our sharding design paper, through deep-dive videos, or by exploring our Rust reference client implementation.
NEAR 是 Open Web 的基础架构，也是一个分片区块链协议。你可以通过分片设计论文、深度视频系列、或我们的 Rust 参考客户端实现来深入了解我们的技术。
作者 Alexander Skidanov
翻译 Marco, Yan Zhu
校对 Bowen
编辑 Amos
来源链接：weixin.qq.com
区块律动 BlockBeats 提醒，根据银保监会等五部门于 2018 年 8 月发布《关于防范以「虚拟货币」「区块链」名义进行非法集资的风险提示》的文件，请广大公众理性看待区块链，不要盲目相信天花乱坠的承诺，树立正确的货币观念和投资理念，切实提高风险意识；对发现的违法犯罪线索，可积极向有关部门举报反映。
NEAR 分片 随机信标 开发者