分散式 FRI 計算

10-18

本文為機器翻譯

展示原文

在本說明中,我們討論了FRI協議的分散式計算。在實踐中,我們通常需要將證明器的工作分佈在多個伺服器上。在使用基於FRI的證明系統的情況下,這會導致昂貴的遞迴聚合獲得的證明或交換資料,其大小與電路大小相當。下面,我們描述了一種技術性的技巧,可以最佳化獲得單個最終證明。批次FRI \mathtt{FRI}協議的批次版本允許估計每個函式f_1, \dots, f_L與\mathsf{RS}碼的接近程度。為此,\mathtt{Verifier}取樣併發送一個隨機\theta \in \mathbb{F}_p給\mathtt{Prover}。後者計算一個線性組合 F = \theta^1 \cdot f_1 + \theta^2 \cdot f_2 + \dots + \theta^L \cdot f_L 然後\mathtt{Prover}和\mathtt{Verifier}執行\mathtt{FRI}協議的常規版本來測試F。唯一的區別是,每次查詢F在點x處時,\mathtt{Verifier}也執行一致性檢查: F(x) = \theta^1 \cdot f_1(x) + \theta^2 \cdot f_2(x) + \dots + \theta^L \cdot f_L(x)。如果\mathtt{Verifier}最終接受,那麼所有的f_i都足夠接近\mathsf{RS}碼。分散式FRI 現在讓我們考慮一個分散式的設定,其中n=L·M個最多為d度的多項式被分佈在M個\mathtt{Provers}之間。協議的輸出應該是一個證明,即所有多項式f_1, \dots, f_n都足夠接近\mathsf{RS}碼。一種簡單的方法是將所有多項式以明文形式傳送給其中一個證明器,由其執行批次\mathtt{FRI}協議。讓我們考慮如何更有效地解決這個問題。

\mathtt{證明器}Provers生成\mathsf{Merkle~ Tree}Merkle Tree承諾並將其傳送給\mathtt{主證明器}Master Prover(這個功能可以由一個證明器執行,為簡單起見,我們假設這是一個單獨的實體)。\mathtt{主證明器}Master Prover從\mathtt{驗證器}Verifier那裡獲得一個隨機挑戰\thetaθ,並將其廣播給所有\mathtt{證明器}Provers。現在每個\mathtt{證明器}ProverP_iPi,知道它的編號ii,可以生成它的"部分線性組合",並將其傳送給\mathtt{主證明器}Master Prover。

F_i = \sum_{j=1}^{L}\theta^{(i-1) \cdot L + j}f_{(i-1) \cdot L + j}.

Fi=L∑j=1θ(i−1)⋅L+jf(i−1)⋅L+j.

\mathtt{主證明器}Master Prover執行\mathtt{FRI}FRI的常規版本,用於多項式\sum_{i=1}^{M}F_i∑Mi=1Fi。但是,它無法在協議的查詢階段提供多項式評估和Merkle認證路徑進行一致性檢查,因此它要求相應的\mathtt{證明器}Prover提供每個多項式的這些資訊。

\mathtt{主證明器}Master prover可以輕鬆檢測個別\mathtt{證明器}Provers的惡意行為。這是由於部分線性組合F_iFi屬於\mathsf{RS}RS碼。這個屬性在分散式SNARK生成過程中特別有用,因為它允許實施經濟措施來懲罰參與者的不當行為。

很容易看出,\mathtt{證明器}Provers的時間複雜度是O(d\log d)O(dlogd)。通訊成本(這是證明器和主證明器之間的通訊)主要由傳送部分線性組合決定,其大小為O(d)O(d)個來自\mathbb{F}_pFp的元素。此外,驗證最終證明所需的雜湊呼叫次數明顯少於驗證MM個獨立證明所需的次數。

您可以在這裡2找到更詳細的描述。歡迎分享您的評論!

'ETH'必須翻譯為'ETH'。 'DOT'必須翻譯為'DOT'。 'SOL'必須翻譯為'SOL'。 'UNI'必須翻譯為'UNI'。 'CRO'必須翻譯為'CRO'。 'HT'必須翻譯為'HT'。 'THETA'必須翻譯為'THETA'。 'XEC'必須翻譯為'XEC'。 'MINA'必須翻譯為'MINA'。 'BAT'必須翻譯為'BAT'。 'OP'必須翻譯為'OP'。 'COMP'必須翻譯為'COMP'。 'ENS'必須翻譯為'ENS'。 'AR'必須翻譯為'AR'。 'XCH'必須翻譯為'XCH'。 'AMP'必須翻譯為'AMP'。 'ACH'必須翻譯為'ACH'。 'PLA'必須翻譯為'PLA'。 'RON'必須翻譯為'RON'。 'REQ'必須翻譯為'REQ'。 'ONG'必須翻譯為'ONG'。 'ATH'必須翻譯為'歷史高點'。 'TRON'必須翻譯為'TRON'。 'Mina'必須翻譯為'Mina'。 'Amp'必須翻譯為'Amp'。 'Dent'必須翻譯為'Dent'。 'Ren'必須翻譯為'Ren'。 'long'必須翻譯為'做多'。 'ETH'必須翻譯為'姨太'。 'ETH'必須翻譯為'E太'。 'ETH'必須翻譯為'以太'。 'Prover'必須翻譯為'證明器'。