嘿哈布尔！
В 在本文中，我们讨论了为什么可能有必要为彼此不信任的参与者生成随机数，对此类随机数生成器提出了哪些要求，并考虑了两种实现方法。
在本文的这一部分中，我们将仔细研究另一种使用阈值签名的方法。
一点密码学
为了了解门限签名的工作原理，您需要了解一些基本的密码学。 我们将使用两个概念：标量或简单的数字，我们将用小写字母表示（x，y）和椭圆曲线上的点，我们将用大写字母表示。
要了解阈值签名的基础知识，您不需要了解椭圆曲线的工作原理，只需了解一些基本知识即可：
-
椭圆曲线上的点可以与标量相加或相乘（我们将与标量相乘表示为 xG，虽然符号 Gx 也经常在文献中使用）。 标量加法和乘法的结果是椭圆曲线上的点。
-
只知道重点 G 及其标量的乘积 xG 无法计算 x.
我们还将使用多项式的概念 p(x) 度 k-1。 特别是，我们将使用多项式的以下属性：如果我们知道值 p(x) 对于任何 k 不同 x （我们没有更多关于 p(x)），我们可以计算 p(x) 对于其他人 x.
有趣的是，对于任意多项式 p(x) 和曲线上的某个点 G知道其意义 p(x)G 对于任何 k 不同的含义 x，我们还可以计算 p(x)G 对于任何 x.
这些信息足以深入了解门限签名如何工作以及如何使用它们生成随机数的细节。
阈值签名的随机数生成器
这么说吧 n 参与者想要生成一个随机数，我们希望任何人都参与 k 它们的数量足以产生一个数字，但这样控制的攻击者 k-1 或更少的参与者无法预测或影响生成的数字。
假设有这样一个多项式 p(x) 度 k-1 第一个参与者知道什么 P（1），第二个知道 p(2), 等等 （n-th知道 p(n)）。 我们还假设对于某个预定点 G 大家都知道 p(x)G 对于所有值 x。 我们会打电话 p(i) “私有组件” ith 参与者（因为只有 i第 个参与者认识她），并且 猪 “公共组件” i-th 参与者（因为所有参与者都认识她）。 正如你所记得的，知识 猪 不足以恢复 p(i)。
创建这样一个多项式，以便仅 i-第一个参与者并且没有其他人知道他的私有组件 - 这是协议中最复杂和有趣的部分，我们将在下面对其进行分析。 现在，我们假设我们有这样一个多项式，并且所有参与者都知道他们的私有组件。
我们如何使用这样的多项式来生成随机数？ 首先，我们需要一些以前未用作生成器输入的字符串。 对于区块链，最后一个区块的哈希值 h 是这样一条线的良好候选者。 让参与者想要创建一个随机数 h 像种子一样。 参与者首先转化 h 使用任何预定义函数到曲线上的点：
H = 标量到点(h)
然后每个参与者 i 计算并发布 Hi = p(i)H, 他们能做什么，因为他们知道 p(i) 和 H. 泄露 H我不允许其他参与者恢复私有组件 ith 参与者，因此可以从一个块到另一个块使用一组私有组件。 因此，下面描述的昂贵的多项式生成算法只需要执行一次。
何时 k 对参与者进行尸检 Hi = p(i)H, 每个人都可以计算 Hx = p(x)H 为了所有人 x 感谢我们在上一节中讨论的多项式的性质。 此时此刻，所有参与者都在计算 H0 = 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 对于相同的种子，参与者总是会得到相同的结果。
上面我们小心翼翼地避免了一个问题。 为了使插值工作，重要的是该值 Hi 由每个参与者发布 i 确实是一样的 p(i)H。 既然没有人除了 i第-个参与者不知道 p(i), 没有人除了 i-th 参与者无法验证 Hi 实际上计算正确，并且没有任何正确性的加密证明 H我攻击者可以将任何值发布为 嗨， 并任意影响随机数生成器的输出:
第一个参与者发送的H_1的不同值导致不同的结果H_0
至少有两种方法可以证明正确性 Hi，我们在分析多项式的生成之后再考虑它们。
多项式生成
在上一节中我们假设我们有这样一个多项式 p(x) 度 k-1 表示参与者 i 他知道 p(i)，并且没有其他人知道有关该值的任何信息。 在下一节中，我们还需要针对某些预定点 G 每个人都知道 p(x)G 为了所有人 x.
在本节中，我们假设每个参与者本地都有一些私钥 熙, 这样每个人都知道相应的公钥 Xi.
一种可能的多项式生成协议如下：
-
每位参与者 i 本地创建任意多项式 pi(x) k-1 度。 然后他们向每个参与者发送 j 值 pi(j)，用公钥加密 Xj。 因此只有 i-日 и j-日 参与者知道 p我（j）。 参加者 i 还公开宣布 pi(j)G 为了所有人 j 从 1 对 k 包括在内。
-
所有参与者都使用某种共识来选择 k 将使用其多项式的参与者。 由于部分参与者可能离线，我们无法等到所有人 n 参与者将发布多项式。 这一步的结果是一个集合 Z 至少由 k 步骤 (1) 中创建的多项式.
-
参与者确保他们知道的价值观 pi(j)对应于公开宣布的 pi(j)G。 进入这一步后 Z 仅私有传输的多项式 pi(j)对应于公开宣布的 pi(j)G。
-
每位参与者 j 计算其私有部分 p(j) 作为总和 pi(j) 对于所有 i в Z。 每个参与者还计算所有值 p(x)G 作为总和 pi(x)G 对于所有 i в Z.
请注意， p(x) – 这确实是一个多项式 k-1, 因为它是个体的总和 pi(x)，其中每个都是次数多项式 k-1。 然后，请注意，虽然每个参与者 j 他知道 p(j), 他们没有关于 p(x) 为 x ≠ j。 事实上，要计算这个值，他们需要知道一切 圆周率 (x), 并且只要参与者 j 不知道至少一个选定的多项式，他们没有足够的信息 p(x)。
这是上一节中所需的整个多项式生成过程。 上面的步骤1、2和4有一个相当明显的实现。 但第 3 步并不是那么简单。
具体来说，我们需要能够证明加密的 pi(j) 确实与已发布的相符 pi(j)G。 如果我们无法证明这一点，攻击者 i 可能会发送垃圾 pi(j) 给参与者 j，以及参与者 j 将无法获得真正的价值 圆周率 (j), 并且将无法计算其私有部分.
有一个加密协议允许您创建附加消息 证明i(j)，使得任何参与者都具有一定的价值 e, 以及 证明i(j) и pi(j)G，可以本地验证 e - 是真的 圆周率 (j), 使用参与者的密钥加密 j. 不幸的是，此类证据的规模非常大，而且考虑到有必要发表 O（nk） 此类证据不能用于此目的。
而不是证明这一点 圆周率(j) 对应于 pi(j)G 我们可以在多项式生成协议中分配一个非常长的时间段，在此期间所有参与者检查接收到的加密数据 圆周率 (j), 如果解密的消息不对应于公众 pi(j)G，他们发布了一个加密证明，证明他们收到的加密消息是不正确的。 证明该消息 没有 对应于 猪） 比证明它匹配容易得多。 应该指出的是，这要求每个参与者在分配的创建此类证据的时间内至少在线出现一次，并且依赖于这样的假设：如果他们发布这样的证明，它将在相同的分配时间内到达所有其他参与者。
如果一名参与者在这段时间内没有出现在线，并且他确实有至少一个不正确的成分，那么该特定参与者将无法参与进一步的号码生成。 然而，如果至少有 k 刚刚收到正确组件或在规定时间内留下错误证明的参与者。
H_i 正确性证明
最后还有待讨论的是如何证明已发布的正确性 H我，即 Hi = p(i)H, 无需打开 p(i)。
让我们记住这些价值观 H、G、p(i)G 公开并为所有人所知。 接收操作 p(i) 会心 猪 и G 称为离散对数，或 日志， 我们想证明：
dlog(p(i)G, G) = dlog(Hi, H)
不公开 p(i)。 例如，存在此类证明的构造.
通过这种设计，每个参与者以及 Hi 根据设计发送正确性证明。
随机数一旦生成，通常需要由生成它的人以外的参与者使用。 此类参与者必须连同号码一起发送所有 Hi 及相关证据。
好奇的读者可能会问：既然最终的随机数是 H0, 和 p(0)G – 这是公开信息，为什么我们需要每个人的证据 H我，为什么不发送证明
日志（p(0)G, G) = dlog(H0, H)
问题是这样的证明无法使用 Schnorr 协议创建，因为没有人知道其价值 P（0），创建证明所必需的，而且，整个随机数生成器基于无人知道该值的事实。 因此必须拥有所有的值 Hi 以及他们的个人证据来证明正确性 H0.
然而，如果对椭圆曲线上的点进行一些语义上类似于乘法的运算，则正确性证明 H0 这很简单，我们只需确保
H0× G = p(0)G×H
如果所选曲线支持 ，这个证明有效。 在这种情况下 H0不仅仅是随机数生成器的输出，任何知道的参与者都可以验证 G，H и p(0)G。 H0 也是用作种子的消息上的签名，确认 k и n 参与者签署了该消息。 因此，如果 种子—— 是区块链协议中区块的哈希值，那么 H0 既是一个区块的多重签名，又是一个非常好的随机数。
总之
本文是技术博客系列的一部分 。 NEAR 是一个用于开发去中心化应用程序的区块链协议和平台，重点是易于开发和易于最终用户使用。
协议代码是开放的，我们的实现是用Rust写的，可以找到 .
您可以查看 NEAR 的开发情况并在在线 IDE 中进行实验 .
您可以关注俄语的所有新闻： 和 ，以及官方的英文 .
再见！
来源： habr.com