嘿哈布爾！
В 在本文中，我們討論了為什麼可能有必要為彼此不信任的參與者產生隨機數，對此類隨機數產生器提出了哪些要求，並考慮了兩種實作方法。
在本文的這一部分中，我們將仔細研究另一種使用閾值簽名的方法。
一點密碼學
為了了解門限簽名的工作原理，您需要了解一些基本的密碼學。我們將使用兩個概念：標量或簡單的數字，我們將用小寫字母表示（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不僅僅是隨機數產生器的輸出，任何知道的參與者都可以驗證 克、赫 и p(0)G。 H0 也是用作種子的訊息上的簽名，確認 k и n 參與者簽署了該訊息。因此，如果 種子 – 是區塊鏈協議中區塊的哈希值，那麼 H0 既是一個區塊的多重簽名，也是一個非常好的隨機數。
總之
本文是技術部落格系列的一部分 。 NEAR 是一個用於開發去中心化應用程式的區塊鏈協議和平台，重點是易於開發且易於最終用戶使用。
協議代碼是開放的，我們的實作是用Rust寫的，可以找到 .
您可以查看 NEAR 的開發情況並在線上 IDE 中進行實驗 .
您可以關注俄語的所有新聞： 和 ，以及官方的英文 .
待會見！
來源： www.habr.com