Firstly we need to look into domain D, which the polynomial p(x) defines over.
Traditional Domain
Usually the domain D is a cyclic multiplicative sub-group H defined over finite prime field Fp, say F13, then ∣F13×∣=∣⟨6⟩∣=12, there is a order-4 subgroup:
H=⟨63⟩
generally speaking:
D=H=⟨gm⟩=⟨gm⟩
where g is generator of multiplicative group Fp×, and gm is the generator of D or H.
Therefore we have the belowing evaluation table Y=p(X), where X∈D:
XY1e0gme1gm2e2......gmn−1en−1
Obviousely p(X) is a univariate polynomial, as X is one-diamentional coordinate, and evaluation domain D is a multiplicative group.
Circle Domain
While in circle domain, X is not one-diamentional coordinate anymore, it's two-diamentional coordinates, it's a bivariate polynomial p(x,y), and its domain D is a additive group rather a multiplicative group.
Assuming there's a additive cyclic group G:
G={(x,y);x2+y2=1,x,y∈Fp}
where ∣G∣=∣⟨g⟩∣=64. There is subgroup:
D=H={g+[i]g2,i<32}
where g2=[2]g, we must have ∣D∣=32.
Therefore we have the following evaluation table Y=p(X), where X∈H:
you'll notice that, it's not a additive cyclic group, as it does not even have a generator! So we must correct it, we can not call D as a group anymore, maybe domain is more accurate.
FFT
Secondly, given a vector of evaluations:
e=[e0,e1,e2,e3,...,e31]
we want to get its coefficient represented polynomial p(x), aka polynomial coefficient vector, through a interpolation algorithm, say:
c=[c0,c1,c2,c3,...,c31]
This is what FFT does.
Traditional FFT
First Round
Given univairate polynomial evaluation table Y=p(X),X∈D={gmi,i<n}:
XY1e0gme1gm2e2......gmn−1en−1
we need to solve the coefficients of polynomial p(X) through FFT interpolation.
Divide p(X) into two sub-polynomials f0(X) and f1(X):
Then coefficient vector of f0(X) is reduced into f00(X2) and f01(X2) with halved domain size again after applying FFT algorithm, similarily works for f1(X):
similarily we need to solve the coefficients of polynomial p(X) through interpolation.
But the problem in front of us is that X is a two-diamentional coordinates, say X=(x,y), so the polynomial would be more complex than the one with one-diamentional coordinates. say:
p(X)=p(x,y)=3x+2x2+y⋅5x2+y2⋅4+y3⋅4x3
Luckly any p(x,y) can also be converted into two sub-polynomials f0(x) and f1(x) as traditional FFT does:
p(x,y)=f0(x)+y⋅f1(x)
since (x,y) is circle points satisfying:
x2+y2=1
we must have y2=1−x2. so the above toy polynomial case can be divided into:
f0(x)f1(x)=3x+2x2+(1−x2)⋅4=5x2+(1−x2)⋅4x3
It's a amazing property for circle domain, isn't it?
The bivariate polynomial p(x,y) can also be splitted into two univariate polynomials f0(x) and f1(x):
apply iFFT algorithm recursively we will finally get the evaluations over entire circle domain D:
p(x,y)e0e1e2...en−1
FRI
How FRI Works
Originally, FRI prover needs to prove that p0(x,y) (evaluation vector) is close to a low-degree (trace) polynomial t(x) with certain degree-bound d, where the evaluation domain size ∣D∣ is blow-up factor s times of d, say ∣D∣=s⋅d.
For the purpose of hidden for witness, say p0(x,y), prover compress this evaluation vector into ONE field element through merkle commitment, say C0. Concequently, prover prove that C0 is close to a low-degree (trace) polynomial t(x) with degree-bound d. Accordingly, verifier need to check consistency of commitment C0 as well.
Unfortunately, degree d is too big, low degree testing on this would be much too costy, so FRI operator comes. FRI operator reduce evaluation vector p0(x,y) into half-sized p1(x,y), then prover need to prove p1(x,y) is close to low-degree polynomial t1(x) with degree-bound d/2. Recursively apply FRI operator more times until the final degree-bound d/2k is small enough, prover only need to prove that pk(x,y) is close to low-degree polynomial tk(x) with degree-bound d/2k .
Actually the folding process of FRI operator is non-succinct, prover need to prove the folding is correctly executed. And the verifier need to check ths consistency of folding as well, besides lower-degree testing.
Sum up, prover needs to finish three tasks:
commit evaluation vector pi(x,y) into Ck with merkle hash, and provide merkle proofs for openings (merkle tree path)
FRI operator, fold original evaluation vector p0(x,y) into pk(x,y), and provide folding proofs for openings (leaves of folding tree), and also need to provide merkle proof for these folding proofs (leaves of folding tree)
low degree testing, check whether the final evaluation vector pk(x,y) is close to polynomial tk(x) with low degree-bound d/2k.
Verifier needs to finish three tasks:
check consistency of merkle commititment Ck, with provided merkle proof
check consistency of FRI folding, through pre-defined query times' folding non-succinctly with provided folding proofs
check consistency of low degree testing on pk(x,y), through one time FFT interpolation
Circle FRI
Circle FRI is a FRI protocol based on circle domain (satisfying x2+y2=1), not single prime field based domain anymore.
Merkle Commitment and FRI Operator
Mainly consists two parts, preparaion of folding and fold:
prepare domain/evaluation vector to be folded
assuming there's a evaluation domain with cardinality-32:
D={g+[i]g2,i<32}={g,g3,g5,...,g63}
half-sized circle domain
DL={g,g5,g9,...,g61}
Due to symmetry of circle domain, there's no need to store all elements of domain, half-sized circle domain is enough.
The remaining part is reversed of circle domain DL, say DR=−DL={g63,g59,g55,...,g3}
the univariate polynomial p1(X.x) can be splitted into two univariate polynomials f0(X2.x) and f1(X2.x) where X2 is the doubled of X in circle domain. Similarily we do the linear folding as well, obtain a new half-sized univariate polynomial p2(X.x).
Decommitment
Verifier sample m points q={q0,q1,...,qm−1} within evaluation domain and send them to prover, prover provide two kinds of proofs for these points, and proof of low-degree test:
folding proof for consistency check of sample values
If FRI operator continues until low-degree bound reaches the bottom, say d/2k=1, then the maximum number of folding would be N=logd. We get the exact number of folding proof, say 2N−1.
The total size of folding proof of m-queries would be m⋅(2N−1).
merkle proof for authentication of sample values and their folding proof (consistency of merkle commitment)
If we also take the ultimate folding, we need to provide merkle proof for each folding proof, including the sample values themselves. Therefore we can also get the exact number of merkle proof for this, say N+(N−1)+(N−2)+...+1=2(1+N)N .
The total size of merkle proof of m-queries would be m⋅2(1+N)N .
low-degree test proof, that's the final folded evaluation vector pk(x,y)
If we take the ultimate folding as well, we can get the exact number of low-degree test proof, that is what we called blow-up factor .
In summary, the time complexity of single query is O(N2)=O(log2d). Actually there's no need to do the ultimate folding, it's all fine as long as the low-degree bound d/2k is small enough.
Quotient Polynomial
Recall that, there's a polynomial f(x) (x is defined over some evaluation domain D), prover want to prove f(u)=v. Then the quotient polynomial comes:
q(x)=x−uf(x)−v;u,v∈D
where x∈F, and D⊂F. Prover need to prove existence of the quotient polynomial.
If polynomial f(x) is not a univariate-based domain anymore, how about f(X) and X is a bivariate-based domain, say circle domain?
Circle Quotient
Let's take a toy example, say:
f(X)=f(x,y)=3x+4y,X∈D={g+[i]g2,i<n}
evaluate on one point P, we get f(P)=v, namely:
3P.x+4P.y−v=0
Similarily the quotient polynomial comes:
q(X)=X−Pf(X)−v;P∈D
where X∈F, and F is the entire circle domain.
The problem is how to represent this quotient polynomial, which is a line through one point P? It seems impossible, since there are uncountable lines through one point. Indeed it is true in univariate coordinate space. But it also holds in bivariate coordinate, what we need is a trick.
Let's fix the x-part of f(x,y), say:
f(y)=4y=v−3x
this is what'd love to see, as f(y) is a univariate polynomial, not a bivariate one anymore. So, evaluation on P.y, it would be like:
f(P.y)=4P.y=v0
But it is not enough to determine f(P)=v, since there are two solutions P.x and −P.x for P.y in circle domain, satisfying x2+y2=1. So we need another point P′ (Vitalik call it dummy point), who's relevant to P, to make this line uniqueness.
Actually there're many solutions to this, in Stwo implementation, they provide a extreme cheap method Conjugation, namely to say:
P′=Pˉ=(P.xˉ,P.yˉ)
as P.x,P.y are QM31 field elements, conjugation of P.yˉ is just a negation of CM31 field, cheaper enough! So, we can interpolate the polynomial f(X) with these points P and Pˉ:
∣∣f(X)f(P)f(Pˉ)XPPˉ111∣∣
Theoretically [2]P, [3]P, ..., [k]P all are fine, let's take [2]P as a example:
[2]P=(2⋅P.x2−1,2⋅P.x⋅P.y)
it requires one multiplication of QM31 field, much more expensive than conjugation, so we choose conjugation method instead.
The circle quotient is formalized as:
q(X)=VP(X)f(X)−f(P)
but how to compute this it anyway? Let's split it into two parts, nominator part f(X)−f(P), and denominator part VP(X).
Nominator of Circle Quotient
f(X)−f(P) is a bivariate polynomial who vanishes at single point P, f(X) can be converted into a univariate line through (P.y,v) and (Pˉ.y,vˉ) as what we've already illustrated above:
In folding paradigm, we often see one word non-succinct. Yes, the folding helps prover compress a big proof into a much smaller proof, so verifier can verify it efficiently. But what we must not ignore is the overhead folding induces. And folding is not always succinct, in FRI, verifier need to do the same folding as prover did, fortunately verifier only need to do few times' folding depending on the number of queries.
If the cost of verifying original proof π0 is t0, verifying the final compressed proof π2 is t2, and cost of folding on query points is tk. Then we must have:
t0≪t2+tk
Thanks
Special thanks to weikengchen for his input on circle quotients, and learns a lot from his work on Bitcoin Wildlife Sanctuary, finally give great thanks to victor from starkware for his inputs during implementing stwo with bitcoin scripts.