分散式 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'必须翻译为'证明器'。