In this note we discuss the distributed computation of the FRI protocol. In practice, we often need to distribute the prover’s work across many servers. In the case of using a FRI-based proof system, this leads to the expensive recursive aggregation of the obtained proofs or exchanging data, the size of which is comparable to the size of the circuit. Below, we describe a technical trick that allows us to optimize obtaining a single final proof.
Batched FRI
The batched version of the \mathtt{FRI}FRI protocol allows one to estimate the closeness of each of the functions f_1, \dots, f_Lf1,…,fL to the \mathsf{RS}RS code. To do this, the \mathtt{Verifier}Verifier samples and sends a random \theta \in \mathbb{F}_pθ∈Fp to the \mathtt{Prover}Prover. The latter calculates a linear combination
Then the \mathtt{Prover}Prover and \mathtt{Verifier}Verifier execute the regular version of the \mathtt{FRI}FRI protocol for testing FF. The only difference is that each time FF is queried at point xx, the \mathtt{Verifier}Verifier also performs a consistency check:
If the \mathtt{Verifier}Verifier accepted in the end of the protocol, then all f_ifi are close to \mathsf{RS}RS.
Distributed FRI
Let us now consider a distributed setting in which n=L \cdot Mn=L⋅M polynomials of degree at most dd are divided among MM \mathtt{Provers}Provers. The output of the protocol should be a proof that all the polynomials f_1, \dots, f_nf1,…,fn are close enough to the \mathsf{RS}RS code. A naive approach would be to send all polynomials in plaintext to one of the provers, who in turn would execute the batched \mathtt{FRI}FRI protocol. Let us consider how this problem can be solved more efficiently.
\mathtt{Provers}Provers generate \mathsf{Merkle~ Tree}Merkle Tree commitments to their polynomials and send them to the \mathtt{Master~Prover}Master Prover (this function can be performed by one of the provers, for simplicity we will assume that this is a separate entity). The \mathtt{Master~Prover}Master Prover gets a random challenge \thetaθ from the \mathtt{Verifier}Verifier and broadcasts it among all \mathtt{Provers}Provers. Now each \mathtt{Prover}Prover P_iPi, knowing its number ii, can generate its “part of the linear combination” and send it to the \mathtt{Master~Prover}Master Prover.
\mathtt{Master~Prover}Master Prover runs a regular version of \mathtt{FRI}FRI for the polynomial \sum_{i=1}^{M}F_i∑Mi=1Fi. However, it cannot provide polynomial evaluations and Merkle auth paths for consistency checks in the query phase of the protocol for individual polynomials, so it asks the corresponding \mathtt{Prover}Prover for each of them.
\mathtt{Master~prover}Master prover can easily detect malicious behavior of individual \mathtt{Provers}Provers. This is achieved due to the fact that the partial linear combinations F_iFi belong to \mathsf{RS}RS code. This property is especially useful in a distributed SNARK generation process, as it allows for the implementation of economic measures to penalize participants for misbehaving.
It is easy to see that the time complexity of the \mathtt{Provers}Provers is O(d\log d)O(dlogd). The communication cost (this is communication between provers and master prover) is dominated by sending a partial linear combination, whose size is O(d)O(d) elements from \mathbb{F}_pFp. Moreover, the number of hash invocations required to verify the final proof is significantly less than that needed to verify MM independent proofs.
You can find a more detailed description here 2. Feel free to share your comments!
