이 메모에서는 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}는 F에 대한 정규 버전의 \mathtt{FRI} 프로토콜을 실행합니다. 차이점은 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 \cdot M 개의 최대 차수 d인 다항식이 M 개의 \mathtt{Provers} 사이에 분산되어 있는 분산 설정을 고려해 보겠습니다. 프로토콜의 출력은 모든 다항식 f_1, \dots, f_n이 \mathsf{RS} 코드에 충분히 가깝다는 증명이어야 합니다. 순진한 접근 방식은 모든 다항식을 일반 텍스트로 한 프로버에게 보내고 해당 프로버가 배치 \mathtt{FRI} 프로토콜을 실행하는 것입니다. 이 문제를 보다 효율적으로 해결하는 방법을 살펴보겠습니다.
\mathtt{Provers}프로버스프로버스 generate \mathsf{Merkle~ Tree}머클 트리머클 트리 commitments to their polynomials and send them to the \mathtt{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}마스터 프로버마스터 프로버 gets a random challenge \thetaθ from the \mathtt{Verifier}검증자검증자 and broadcasts it among all \mathtt{Provers}프로버스프로버스. Now each \mathtt{Prover}프로버프로버 P_iPi, knowing its number ii, can generate its "part of the linear combination" and send it to the \mathtt{Master~Prover}마스터 프로버마스터 프로버.
\mathtt{Master~Prover}마스터 프로버마스터 프로버 runs a regular version of \mathtt{FRI}FRIFRI 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}프로버프로버 for each of them.
\mathtt{Master~prover}마스터 프로버마스터 프로버 can easily detect malicious behavior of individual \mathtt{Provers}프로버스프로버스. This is achieved due to the fact that the partial linear combinations F_iFi belong to \mathsf{RS}RSRS 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}프로버스프로버스 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.
더 자세한 설명은 여기 2에서 확인할 수 있습니다. 의견을 자유롭게 공유해 주세요!
이더리움(ETH), 폴카닷(DOT), 솔라나(SOL), 유니스왑(UNI), 크립토닷컴 코인(CRO), 후오비 토큰(HT), 쎄타 토큰(THETA), 이캐시(XEC), 미나 프로토콜(MINA), 베이직어텐션토큰(BAT), 옵티미즘(OP), 컴파운드(COMP), 이더리움 네임서비스(ENS), 알위브(AR), 치아(XCH), 앰프(AMP), 알케미페이(ACH), 플레이댑(PLA), Ronin(RON), 리퀘스트(REQ), 온톨로지가스(ONG), 신고가, 트론(TRON), 덴트(Dent), 렌(Ren), 해시, 초당 거래 수(TPS), 인터컨티넨탈 거래소, 자산 수익률(ROA).
