FRI-based Polynomial Commitments
Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang
A polynomial commitment scheme SNARK for general circuits A polynomial interactive oracle proof (IOP) ZKP MOOC •  P's first message in the protocol is a polynomial h . •  V does not learn h in full. • The description size of h is as large as the circuit. •  Rather, V is permitted to evaluate h at, say, one point. •  After that, P and V execute a standard interactive proof.
▪ High-level idea: . P binds itself to a polynomial h by sending a short string Com( h ). ▪ V can choose x and ask P to evaluate h(x). ◾ P sends y, the purported evaluation, plus a proof π that y is consistent with Com(h) and x . ▪ Goals: . P cannot produce a convincing proof for an incorrect evaluation. . Com(h) and π are short and easy to generate; π is easy to check.
◾ There are several different polynomial IOPs in the literature. ◾ And several different polynomial commitments. ◾ Can mix-and-match to get different tradeoffs between P time, proof size, setup assumptions, etc. ◾ Transparency and plausible post-quantum security determined entirely by the polynomial commitment scheme used.
1. Based on interactive proofs (IPs). 2. Based on multi-prover interactive proofs (MIPs). 3. Based on constant-round polynomial IOPs. . Examples: Marlin, PlonK. ◾ Above SNARKs roughly listed in increasing order of P costs and decreasing order of proof length and V cost. ◾ Categories 1 and 2 covered in Lecture 4, Category 3 (PlonK) in Lecture 5.
1. Based on pairings + trusted setup (not transparent nor post-quantum). ◾  e.g., KZG10 (Lecture 5 + 6). ▪ Unique property: constant sized evaluation proofs. 2. Based on discrete logarithm (transparent, not post-quantum). . Examples: IPA/Bulletproofs (Lecture 6), Hyrax, Dory. 3. Based on IOPs + hashing (transparent and post-quantum) . e.g., FRI (will be covered today), Ligero, Brakedown, Orion (Lecture 7).
1. Based on pairings + trusted setup (not transparent nor post-quantum). ◾  e.g., KZG10 (Lecture 5 + 6). ▪ Unique property: constant sized evaluation proofs. 2. Based on discrete logarithm (transparent, not post-quantum). . Examples: IPA/Bulletproofs (Lecture 6), Hyrax, Dory. . Classes 1. and 2. are homomorphic. . Leads to efficient batching/amortization of P and V costs (e.g., when proving knowledge of several different witnesses). Some specimens from the zoo
1.   [Any polynomial IOP] + IPA/Bulletproofs polynomial commitment. ▪ Ex: Halo2-ZCash . Pros: Shortest proofs among transparent SNARKs. ▪ Cons: Slow V
ZKP MOOC

2.  [Any polynomial IOP] + FRI polynomial commitment. ▪   Ex: STARKs, Fractal, Aurora, Virgo, Ligero++ . Pros: Shortest proofs amongst plausibly post-quantum SNARKs. ▪ Cons: Proofs are large (100s of KBs depending on security)
ZKP MOOC

3.   MIPs and IPs + [fast-prover polynomial commitments]. ▪ Ex: Spartan, Brakedown, Orion, Orion+. . Pros: Fastest P in the literature, plausibly post-quantum + transparent if polynomial commitment is. ◾ Cons: Bigger proofs than 1. and 2. above.
ZKPIMOOC

1.  Linear-PCP based: ▪ Ex: Groth16 ▪ Pros: Shortest proofs (3 group elements), fastest V. ◾ Cons: Circuit-specific trusted setup, slow and space-intensive P, not post- quantum
ZKP MOOC

2. Constant-round polynomial IOP + KZG polynomial commitment: ▪ Ex: Marlin-KZG, PlonK-KZG ▪ Pros: Universal trusted setup. ◾ Cons: Proofs are ~4x-6x larger than Groth16, P is slower than Groth16, also not post-quantum. ▪  Counterpoint for P: can use more flexible intermediate representations than circuits and R1CS. FRI (Univariate) Polynomial Commitment
1. Let q be a degree-(k — 1) polynomial over field F n . E.g., k = 5 and q(X) = 1 + 2X + 4X²+ X² . 2. Want P to succinctly commit to q , later reveal q ( r ) for an r ∈ F p chosen by V. . Along with associated “evaluation proof”. Recall: Initial Attempt from Lecture 4 ◾  P Merkle-commits to all evaluations of the polynomial q . ◾  When V requests q(r), P reveals the associated leaf along with opening information.
ZKP MOOC

◾  P Merkle-commits to all evaluations of the polynomial q. ◾  When V requests q(r), P reveals the associated leaf along with opening information. ◾ Two problems: 1. The number of leaves is |F|, which means the time to compute the commitment is at least |F|. ◾ Big problem when working over large fields (say, | F| ≈ 2 64 or | F| ≈ 2 128 ). ▪ Want time proportional to the degree bound d. V does not know if f has degree at most k! 2. Fixing the first problem (Want P time linear in degree, not field size) ▪ Rather than P Merkle-committing to all ( p — 1) evaluations of q , P only Merkle-commits to evaluations q(x) for those x in a carefully chosen subset Ω of Fp・
ZKP MOOC

▪ Rather than P Merkle-committing to all ( p — 1) evaluations of q , P only Merkle-commits to evaluations q ( x ) for those x in a carefully chosen subset Ω of Fp・ ◾  Ω has size ρ− 1 k for some constant ρ ≤ 1/2, where k is the degree of q. ◾ ρ−¹ ≥ 2 is called the “FRI blowup factor”. ◾ ρ is called the “rate of the Reed-Solomon code” used.
ZKPIMOOC

▪ Rather than P Merkle-committing to all ( p — 1) evaluations of q , P only Merkle-commits to evaluations q ( x ) for those x in a carefully chosen subset Ω of Fp・ ◾  Ω has size ρ− 1 k for some constant ρ ≤ 1/2, where k is the degree of q. ◾ ρ−¹ ≥ 2 is called the “FRI blowup factor”. ▪ Strong tension between P time and verification costs: ▪ The bigger the blowup factor, the slower P is, because it has to evaluate q on more inputs and Merkle-hash the results. ◾ But the smaller the verification costs will be.
▪ Rather than P Merkle-committing to all ( p — 1) evaluations of q , P only Merkle-commits to evaluations q ( x ) for those x in a carefully chosen subset Ω of Fr・ ◾  Ω has size ρ− 1 k for some constant ρ ≤ 1/2, where k is the degree of q. ◾ ρ−¹ ≥ 2 is called the “FRI blowup factor”. ◾ Strong tension between P time and verification costs: ▪ The bigger the blowup factor, the slower P is, because it has to evaluate q on more inputs and Merkle-hash the results. ▪  Proof length will be about (λ/log (ρ− 1 )) · log² (k) hash values. ◾ λ is the security parameter a.k.a. “λ bits of security” (more on this later)
ZKP MOOC

◾ Let n = ρ−¹ k. Assume n is a power of 2. ◾ The key subset Ω comprises all nth roots of unity in Fp. ◾ x such that x n = 1. Equivalently, x n — 1 = 0.
ZKP MOOC

◾ Fact: Let ω ∈ F n be a primitive n'th root of unity. That is, n is the smallest integer such that ω n = 1. Then Ω = { 1, ω, ω², …, ωn-1 }.
ZKP MOOC

▪ Fact: Let ω ∈ F n be a primitive n'th root of unity. That is, n is the smallest integer such that ω n = 1. Then Ω = { 1, ω, ω², …, ωn-1 }. ▪ Fact: Ω is a “multiplicative subgroup” of Fp. ◾ If x and y are both n'th roots of unity, then so is xy. ▪ Special case 1 (since n is even): If x is a n'th root of unity, x² is a (n/2)'th root of unity. ▪ Special case 2 (since n is even): if x is a n'th root of unity, so is −x.
▪ Fact: Let ω ∈ F n be a primitive n'th root of unity. That is, n is the smallest integer such that ω n = 1. Then Ω = { 1, ω, ω², …, ωn-1 }. ▪ Fact: Ω is a “multiplicative subgroup” of Fp. ◾ If x and y are both n'th roots of unity, then so is xy. ▪ Special case 1 (since n is even): If x is a n'th root of unity, x² is a (n/2)'th root of unity. ▪ Special case 2 (since n is even): if x is a n'th root of unity, so is −x. ▪ Fact: Ω has size n if and only if n divides p — 1.
▪ Fact: Let ω ∈ F n be a primitive n'th root of unity. That is, n is the smallest integer such that ω n = 1. Then Ω = { 1, ω, ω², …, ωn-1 }. ▪ Fact: Ω is a “multiplicative subgroup” of Fp. ◾ If x and y are both n'th roots of unity, then so is xy. ▪ Special case 1 (since n is even): If x is a n'th root of unity, x² is a (n/2)'th root of unity. ▪ Special case 2 (since n is even): if x is a n'th root of unity, so is −x. ◾ Fact: Ω has size n if and only if n divides p — 1. ▪ This is why many FRI-based SNARKs work over fields like F p with p = 2 64 — 2 32 + 1 •  p — 1 is divisible by 232. • Running FRI over the field can support any power-of-two value of n up to 232.
ZKPIMOOC

◾ Consider the prime field F41 of size 41. ■　1st roots of unity: {1} ■   2nd roots of unity: {1, -1} . 4th roots of unity: {1, -1, 9, -9}. ◾ 8th roots of unity: {1, -1, 9, -9, 3, -3, 14, -14}
ZKP MOOC

◾ V needs to know that the committed vector is all evaluations over domain Ω of some degree-(k − 1) polynomial. ▪   Idea from the PCP literature: V “inspects” only a few entries of the vector to “get a sense” of whether it is low-degree. ◾   Each query will add a Merkle-authentication path (i.e., log( n ) hash values) to the proof. ▪ This turns out to be impractical. ◾ Instead, the FRI “low-degree test” will be interactive. ◾ The test will consist of a “folding phase” followed by a “query phase”. ◾ The folding phase is log( k ) rounds. The query phase is one round.
◾ Folding Phase: ◾ "Randomly fold the committed vector in half". ▪ This means pair up entries of the committed vector, have V pick a random field element r , and use r to “randomly combine” every two paired up entries. . This halves the length of the vector. . Have P Merkle-commit to the folded vector.
◾ Folding Phase: ◾ "Randomly fold the committed vector in half". ▪ This means pair up entries of the committed vector, have V pick a random field element r , and use r to “randomly combine” every two paired up entries. ▪ This halves the length of the vector. . Have P Merkle-commit to the folded vector. ▪ The random combining technique is chosen so that the folded vector will have half the degree of the original vector. . Repeat the folding until the degree should fall to 0. ▪ At this point, the length of the folded vector is still ρ− 1 ≥ 2. But since the degree should be 0, P can specify the folded vector with a single field element.
. P may have “lied” at some step of the folding phase, by not performing the fold correctly. ◾  i.e., sending a vector that is not the prescribed folding of the previous vector. ◾  To “artificially” reduce the degree of the (claimed) folded vector. ◾ V attempts to “detect” such inconsistencies during the query phase.
. P may have “lied” at some step of the folding phase, by not performing the fold correctly. ◾  i.e., sending a vector that is not the prescribed folding of the previous vector. ◾ To “artificially” reduce the degree of the (claimed) folded vector. ◾ V attempts to “detect” such inconsistencies during the query phase. . Query phase: V picks about (λ/log(ρ− 1 )) entries of each folded vector and confirming each is the prescribed linear combination of the relevant two entries of the previous vector.
◾   P may have “lied” at some step of the folding phase, by not performing the fold correctly. ◾  i.e., sending a vector that is not the prescribed folding of the previous vector. ◾  To “artificially” reduce the degree of the (claimed) folded vector. ◾ V attempts to “detect” such inconsistencies during the query phase. . Query phase: V picks about (λ/log(ρ−1)) entries of each folded vector and confirming each is the prescribed linear combination of the relevant two entries of the previous vector. .  Proof length (and V time): roughly (λ/log(ρ− 1 ))  log(k)²  hash evaluations. Back to the folding phase: more details Credit: Esithia Shuwarstock
◾ Split q(X) into “even and odd parts” in the following sense. ▪ q(X) = qe(X²) + X qo(X²) ▪ E.g., if q(X) = 1 + 2X + 3X² + 4X³. ▪ Then q e (X) = 1 + 3X and q o (X) = 2 + 4X. ◾ Note that both q e and q o have (at most) half the degree of q . ◾ V picks a random field element r and sends r to P. ◾ The prescribed “folding” q is: qfold(Z) = qe(Z) + rqo(Z) ◾ Clearly deg(qfoιd) is half the degree of q itself. The (interactive) low-degree test: Folding Phase ▪ Recall: q(X) = qe(X2) + X qo(X2) ◾ Recall: The prescribed "folding" q is: qfold(Z) = qe(Z) + rqo(Z).
ZKP MOOC
The (interactive) low-degree test: Folding Phase ▪ Recall: q(X) = qe(X2) + X qo(X2) ◾ Recall: The prescribed “folding” q is: qfold(Z) = qe(Z) + rqo(Z).

ZKPIMOOC
The (interactive) low-degree test: Folding Phase ▪ Recall: q(X) = qe(X2) + X qo(X2) ◾ Recall: The prescribed “folding” q is: qfold(Z) = qe(Z) + rqo(Z). ◾ Fact: Let x and — x be n'th roots of unity and z = x². Then: ▪ Proof: Clearly q(x) = qe(z) + xqo(z). ▪ In other words, if r = x then q fold (z)= q (x). ◾ Similarly, if r = −x then qfoιd(z) = q(−x).
▪ Recall: q(X) = qe(X2) + X qo(X2) ◾ Recall: The prescribed “folding” q is: qfold(Z) = qe(Z) + rqo(Z). ◾ Fact: Let x and — x be n'th roots of unity and z = x². Then: ▪ Proof: Clearly q(x) = qe(z) + xqo(z). ◾ In other words, if r = x then q foιd (z)= q(x). ◾ Similarly, if r = −x then qfoιd(z) = q(−x). ◾ The fact follows because it gives a degree-1 function of r with exactly this behavior at r = − x and r = x, and any two degree-1 functions of r that agree at two or more inputs must be the same function.
▪ Recall: q(X) = qe(X2) + X qo(X2) . Recall: The prescribed “folding” q is: qfold(Z) = qe(Z) + rqo(Z). ◾ The fact that the map x → x² is 2-to-1 on Ω = { 1, ω, ω², …, ω²-1 } ensures that the relevant domain halves in size with each fold. ◾ Other domains, like {0, 1, 2, … n — 1}, don't have this property.
▪ Lecture 7 covered a variety of polynomial commitments (Ligero, Brakedown, Orion) that are similar to FRI. . All use error-correcting codes. . The only cryptography used is hashing (Merkle-hashing + Fiat-Shamir).
ZKPIMOOC

▪ Lecture 7 covered a variety of polynomial commitments (Ligero, Brakedown, Orion) that are similar to FRI. ◾ All use error-correcting codes. ◾ The only cryptography used is hashing (Merkle-hashing + Fiat-Shamir). ▪ The Lecture 7 schemes viewed a degree-d polynomial as d 1 /2 vectors each of length about d 1/2 and performed “a single random fold on all these vectors”. ◾ This resulted in larger proofs (size roughly d 1/2 ), but some advantages (e.g., linear- time prover, field-agnostic). ▪ Proof size can be reduced via SNARK composition (will be discussed in Lecture 10). ▪ FRI views a degree-d polynomial as a single vector of length O(d) and “randomly folds it in half” logarithmically many times.
ZKP MOOC
Sketch of the security analysis
. Recall: at the start of the FRI polynomial commitment, P Merkle-commits to a vector w claimed to equal q’s evaluations over Ω. ◾ Here, Ω is the set of n'th roots of unity in F p , where n = ρ− 1 k. ▪ And q is claimed to have degree less than k. The security analysis ◾ Let δ be the “relative Hamming distance” of q from the closest polynomial h of degree k — 1. ◾ δ is the fraction of x ∈ Ω such that h(x) ≠ q(x). The security analysis ◾ Let δ be the “relative Hamming distance” of q from the closest polynomial h of degree k — 1. ◾ δ is the fraction of x ∈ Ω such that h(x) ≠ q(x). ◾ Claim: P “passes” all t “FRI verifier queries” with probability at most蛍+ (1 − δ) f . f.
ZKP MODC

◾ Let δ be the “relative Hamming distance” of q from the closest polynomial h of degree k — 1. ◾ δ is the fraction of x ∈ Ω such that h(x) ≠ q(x). ◾ Claim: P “passes” all t “FRI verifier queries” with probability at most ૈ + (1 − δ) f . ▪ Caveat: this is only known to hold for δ up to 1 — ρ 1 /2 , but is conjectured to hold for δ up to 1 – p. ◾ Most FRI deployments' security are analyzed under this conjecture. ▪ Informal interpretation: FRI V accepts with probability at most about (1 − (1 − ρ)) ξ = ρ ξ . ◾ In other words, each of the t queries contributes about Log2(1/ρ) “bits of security”.
◾ Let δ be the “relative Hamming distance” of q from the closest polynomial h of degree k — 1. ◾ δ is the fraction of x ∈ Ω such that h(x) ≠ q(x). ◾ Claim: P “passes” all t “FRI verifier queries” with probability at most挙+ (1 − δ) f . ▪ Caveat: this is only known to hold for δ up to 1 — ρ 1 /2 , but is conjectured to hold for δ up to 1 − ρ. ◾ Most FRI deployments' security are analyzed under this conjecture. ▪ Informal interpretation: FRI V accepts with probability at most about (1 − (1 − ρ)) ξ = ρ ξ . ◾ In other words, each of the t queries contributes about Log2(1/ρ) “bits of security”. ◾ E.g., if ρ = ξ , each FRI verifier queries contributes about 2 bits of security. ◾ At the cost of roughly log(n)² hash values included in the proof.
◾ Let δ be the “relative Hamming distance” of q from the closest polynomial h of degree k — 1. ◾ δ is the fraction of x ∈ Ω such that h(x) ≠ q(x). ◾ Claim: P “passes” all t “FRI verifier queries” with probability at most ξ + (1 − δ) f . ▪ Recall: qfold(Z) = qe(Z) + rqo(Z). ◾ Can check: since q is δ-far from every degree-( k — 1) polynomial h,  at least one of q e or q, must be δ-far from every degree-(k/2 − 1) polynomial over the (n /2)-roots of unity. ▪ Idea: A “random linear combination” of two functions, at least one of which is δ-far from degree-d polynomials, will also be is δ-far from degree-d with overwhelming probability. ◾ The ξ term bounds the probability that P “gets a lucky fold”. ◾ q fold is close to degree-(k/2 — 1) even though q is not close to degree-(k-1).
ZKP MOOC

◾ Let δ be the “relative Hamming distance” of q from the closest polynomial h of degree k — 1. ◾ δ is the fraction of x ∈ Ω such that h(x) ≠ q(x). ◾ Claim: P “passes” all t “FRI verifier queries” with probability at most ૈ + (1 − δ) c . ◾ Idea 2: If P does “not get a lucky fold”, then the “true” final folded function is δ-far from any degree-0 function. ◾ But P is forced to send a degree-0 function as the final fold. ▪ So at least one “fold” is done dishonestly by P. ▪ In this case, each “FRI verifier query” detects a discrepancy in a fold with probability at least δ. ▪ So all FRI verifier queries fail to detect the discrepancy with probability at most (1 − δ) t.
. Recall: at the start of the FRI polynomial commitment, P Merkle-commits to a vector w claimed to equal q’s evaluations over Ω. ◾ Here, Ω is the set of n'th roots of unity in Fp, where n = ρ− 1 k. . And q is claimed to have degree less than k. ▪ The following P strategy works for any q (even ones maximally far from degree-k) and passes all FRI verifier checks with probability ρ t . ▪ Recall: at the start of the FRI polynomial commitment, P Merkle-commits to a vector w claimed to equal q’s evaluations over Ω. ◾ Here, Ω is the set of n'th roots of unity in Fp, where n = ρ− 1 k. ◾ And q is claimed to have degree less than k. ▪ The following P strategy works for any q (even ones maximally far from degree-k) and passes all FRI verifier checks with probability ρ t . ◾ P picks a set T of k = ρπ elements of Ω and computes a polynomial s of degree k — 1 that agrees with q at those points. ◾ P folds s rather than q during the folding phase. ◾ All t FRI verifier queries lie in T with probability ρ t . Polynomial Commitment from FRI ◾ P Merkle-commits to all evaluations of the polynomial q. ◾  When V requests q(r), P reveals the associated leaf along with opening information. ▪  New Problems with FRI: ◾ P has only Merkle-committed to evaluations of q over domain Ω, not the whole field. ▪  V only knows that q is "not too far" from low-degree, not exactly low-degree.
. Recall the following FACT used in KZG commitments: ◾ FACT: For any degree-d univariate polynomial q, the assertion “q(r) = ν” is equivalent to the existence of a polynomial w of degree at most d  such that ◾ q(X) − v = w(X)(X − r). ▪ So to confirm that q(r) = ν, V applies FRI's fold+query procedure to the function (q(X) − v) (X − r)−¹ using degree bound d − 1.
ZKPTMOOC

. Recall the following FACT used in KZG commitments: ◾ FACT: For any degree-d univariate polynomial q, the assertion “q(r) = ν” is equivalent to the existence of a polynomial w of degree at most d  such that ◾ q(X) − v = w(X)(X − r). ▪ So to confirm that q(r) = ν, V applies FRI's fold+query procedure to the function (q(X) − v) (X − r)−¹ using degree bound d − 1. ▪   Whenever the FRI verifier queries this function at a point in Ω, the evaluation can be obtained with one query to q at the same point.
ZKPIMOOC

. Recall the following FACT used in KZG commitments: ◾ FACT: For any degree-d univariate polynomial q, the assertion “q(r) = ν” is equivalent to the existence of a polynomial w of degree at most d  such that ◾ q(X) − v = w(X)(X − r). ▪ So to confirm that q(r) = ν, V applies FRI's fold+query procedure to the function (q(X) − v) (X − r)−¹ using degree bound d − 1. ▪   Whenever the FRI verifier queries this function at a point in Ω, the evaluation can be obtained with one query to q at the same point. ▪ Can show: To pass V's checks in this polynomial commitment with noticeable probability, ν has to equal h(r), where h is the degree-d polynomial that is closest to q.
ZKP MOOC

◾ Recall the following FACT used in KZG commitments: ◾ FACT: For any degree-d univariate polynomial q, the assertion “q(r) = ν” is equivalent to the existence of a polynomial w of degree at most d  such that ◾ q(X) − v = w(X)(X − r). ▪ So to confirm that q(r) = ν, V applies FRI's fold+query procedure to the function (q(X) − v) (X − r)−¹ using degree bound d − 1. ▪ Whenever the FRI verifier queries this function at a point in Ω, the evaluation can be obtained with one query to q at the same point. ▪ Caveat: The security analysis requires δ to be (at most) (1 − ρ)/2. Each FRI verifier queries brings (less than) 1 bit of security, not log2(1/ρ) bits.
ZKPTMOOC

◾ Recall the following FACT used in KZG commitments: ◾ FACT: For any degree-d univariate polynomial q, the assertion “q(r) = ν” is equivalent to the existence of a polynomial w of degree at most d  such that ◾ q(X) − ν = w(X)(X − r). ▪ So to confirm that q(r) = ν, V applies FRI's fold+query procedure to the function (q(X) − v) (X − r)−¹ using degree bound d − 1. ▪   Whenever the FRI verifier queries this function at a point in Ω, the evaluation can be obtained with one query to q at the same point. ▪ People are using FRI today as a weaker primitive than a polynomial commitment, which still suffices for SNARK security. ◾ P is bound to a “small set” of low-degree polynomials rather than to a single one.
ZKP MOOC
The Fiat-Shamir Transformation and Concrete Security Credit: Esithia Shuwarstock
Public-Coin Interactive Protocol P Non-Interactive Argument ZKP MOOC
Public-Coin Interactive Protocol Grinding attack on Fiat-Shamir: . P FS iterates over first-messages α until it finds one such that R(x,α) is “lucky” Non-Interactive Argument P ZKP MOOC Recall: Fiat-Shamir transformation Grinding attack on Fiat-Shamir: . P FS iterates over first-messages α until it finds one such that R(x, α) is “lucky” ZKP MOOC
Grinding attack on Fiat-Shamir: •    P ſ iterates over first-messages α until it finds one such that R(x, α) is “lucky” . Example: Suppose you apply Fiat-Shamir to an interactive protocol with 80 bits of statistical security (soundness error 2-80) •    With 2 b  hash evaluations, grinding attack will succeed with probability 2-80+b •    E.g., with 270 hashes, successfully attack with probability about 2-10.
Grinding attack on Fiat-Shamir: . •    P ſ iterates over first-messages α until it finds one such that R(x, α) is “lucky” Example: Suppose you apply Fiat-Shamir to an interactive protocol with 80 bits of statistical security (soundness error 2-80) •   With 2 b  hash evaluations, grinding attack will succeed with probability 2-80+b •    E.g., with 270 hashes, successfully attack with probability about 2-10. Comparison: For a collision-resistant hash function (CRHF) configured to 80 bits of security, the fastest collision-finding procedure should be a birthday attack.
Grinding attack on Fiat-Shamir: . •    P ſ iterates over first-messages α until it finds one such that R(x, α) is “lucky” Example: Suppose you apply Fiat-Shamir to an interactive protocol with 80 bits of statistical security (soundness error 2-80) •    With 2 b  hash evaluations, grinding attack will succeed with probability 2-80+b •    E.g., with 270 hashes, successfully attack with probability about 2-10. Comparison: With 2k hash evaluations,  finds a collision with a probability of only 2k-160. For example, 2 70 hash evaluations will yield a collision with a probability of 2-20.
1.  Today, the bitcoin network performs 280 SHA-256 hashes roughly every hour. ◾ At current prices, those hashes typically earn less than $1 million worth of block rewards.
1.  Today, the bitcoin network performs 280 SHA-256 hashes roughly every hour. ◾ At current prices, those hashes typically earn less than $1 million worth of block rewards. In January 2020, the cost of computing just shy of 2. 264 SHA-1 evaluations using GPUs was $45,000. ◾ This puts 2 70 hashes at about $3,000,000. ◾ Likely less today, post-Ethereum-merge. Interactive vs. Non- Interactive Security Credit: Esithia Shuwarstock
. A polynomial commitment scheme such as FRI, when run interactively at “λ bits of security”, has the following security guarantee . Assuming P cannot find a collision in the hash function used to build Merkle trees, a lying P cannot pass the verifier’s checks with probability better than 2-λ. . A lying P must actually interact with V to learn V’s challenges, in order to find out if it receives a “lucky” challenge!
. For example, if λ = 60, then with probability at least 1- 2−30, V will reject (at least) 230 times before a lying P succeeds in convincing V to accept. . It seems unlikely that V would continue interacting with a P that has been caught in a lie 230 times. . In many settings, interactive with V may take long enough that P wouldn't have time to make 1 billion attempts even if V were willing to consider each one. . E.g., One billion Ethereum blocks take 3 years to create (at one block per 12 seconds).
. Suppose Fiat-Shamir is applied to an interactive protocol such as FRI that was run at λ bits of interactive security. . . The resulting non-interactive protocol has the following much weaker guarantee: A lying P willing to perform 2 k hash evaluations can successfully attack the protocol with probability 2k-λ . A lying P can attempt the attack “silently”. . Unlike in the interactive case, P can perform a "grinding attack" without interacting with V until P receives a lucky challenge.
■ Suppose Fiat-Shamir is applied to an interactive protocol such as FRI that was run at λ bits of interactive security. . . . The resulting non-interactive protocol has the following much weaker guarantee: A lying P willing to perform 2 k hash evaluations can successfully attack the protocol with probability 2k-λ A lying P can attempt the attack “silently”. . . . Unlike in the interactive case, P can perform a "grinding attack" without interacting with V until P receives a lucky challenge. Higher security levels λ are necessary in this setting. 60 bits of interactive security is fine in many contexts. . 60 bits of non-interactive security is not okay unless the payoff of a successful attack is minimal. Fiat-Shamir security loss for many-round protocols can be huge Credit: Esithia Shuwarstock
. Consider the following (silly) interactive protocol for the empty language (i.e., V should always reject). . P sends a message (a nonce) which V ignores. . V tosses a random coin, rejecting if it comes up heads and accepting if it comes up tails. . The soundness error of this protocol is 1/2. . If you sequentially repeat it λ times and accept only if every run accepts, the soundness error falls to 1/2 λ .
. Recall: If you sequentially repeat it λ times and accept only if every run accepts, the soundness error falls to 1/2 λ . . . Consider Fiat-Shamir-ing this λ -round protocol to render it non-interactive. A cheating prover  P ξ can find a convincing “proof” for the non-interactive protocol with O(λ) hash evaluations.
. Recall: If you sequentially repeat it λ times and accept only if every run accepts, the soundness error falls to 1/2 λ . . . Consider Fiat-Shamir-ing this λ -round protocol to render it non-interactive. A cheating prover  P FS can find a convincing “proof” for the non-interactive protocol with O( λ ) hash evaluations. . Idea:  P ες grinds on the first repetition alone (i.e., iterate over nonces in the first repetition until one is found that hashes to tails. This requires 2 attempts in expectation until success.) Fix this first nonce m₁ for the remainder of the attack.
. Recall: If you sequentially repeat it λ times and accept only if every run accepts, the soundness error falls to 1/2 λ . . . . Consider Fiat-Shamir-ing this λ -round protocol to render it non-interactive. A cheating prover  P FS can find a convincing “proof” for the non-interactive protocol with O( λ ) hash evaluations. Idea:  P fs  grinds on the first repetition alone (i.e., iterate over nonces in the first repetition until one is found that hashes to tails. This requires 2 attempts in expectation until success.) Fix this first nonce m₁ for the remainder of the attack. . Then  P ες grinds on the second repetition alone until it finds an m, such that (m 1 , m 2 ) hashes to tails. Fix m 2 for the remainder of the attack. . Then  P FS  grinds on the third repetition, and so on.
. Applying Fiat-Shamir to a many-round interactive protocol can lead to a huge loss in security, whereby the resulting non-interactive protocol is totally insecure.
. Applying Fiat-Shamir to a many-round interactive protocol can lead to a huge loss in security, whereby the resulting non-interactive protocol is totally insecure. . Fortunately, this security loss can be ruled out if the interactive protocol satisfies a stronger notion of soundness called round-by-round soundness.
. Applying Fiat-Shamir to a many-round interactive protocol can lead to a huge loss in security, whereby the resulting non-interactive protocol is totally insecure. . Fortunately, this security loss can be ruled out if the interactive protocol satisfies a stronger notion of soundness called round-by-round soundness. . . . This means an attacker in the interactive protocol has to “get very lucky all at once” (in a single round)… it can’t succeed by getting “a little bit lucky many times”. The sequential repetition of soundness error 1/2 is not round-by-round sound. . The attacker can “get a little lucky” each round and succeed (i.e., in each round with probability 1/2 it gets the “lucky” challenge Tails each round). The sum-check protocol (Lecture 4) is an example of a logarithmic-round protocol that is known to be round-by-round sound. . Something analogous is known for Bulletproofs [AFK22, Wik21].
. Applying Fiat-Shamir to a many-round interactive protocol can lead to a huge loss in security, whereby the resulting non-interactive protocol is totally insecure. . Fortunately, this security loss can be ruled out if the interactive protocol satisfies a stronger notion of soundness called round-by-round soundness. . FRI is a logarithmic-round interactive protocol that is always deployed non- interactively today. It has not been shown to be round-by-round sound. .
. Applying Fiat-Shamir to a many-round interactive protocol can lead to a huge loss in security, whereby the resulting non-interactive protocol is totally insecure. . . Fortunately, this security loss can be ruled out if the interactive protocol satisfies a stronger notion of soundness called round-by-round soundness. FRI is a logarithmic-round interactive protocol that is always deployed non- interactively today. . It has not been shown to be round-by-round sound. . SNARK designers applying Fiat-Shamir to interactive protocols with more than 3 messages should show that the protocol is round-by-round sound if they want to rule out a major security loss. END OF LECTURE Next lecture: SNARKs from Linear PCPs (e.g., Groth16)
1. Recall from Lecture 5: n'th roots of unity Let ω ∈ F p be a primitive k -th root of unity (so that  ω k = 1). ◾ if Ω = { 1, ω, ω², …, ωk-1 } ⊆ F p   then   Z Ω(X) = Xk − 1