IOP: prove evaluation of a multi-linear extension polynomial
a cyclic group in base Field \( \mathbb{H} \) (STARK trace domain)
base Field \(\mathcal{F}\)
4th degree extension of base Field, Secure Field \(\mathcal{SF}\)
\(a(w)\) is a univariate polynomial of degree \(2^d\) (STARK trace), \(w\in \mathbb{H}\)
\(f(b_0,b_1,…,b_d)\) is a multi-variate function (STARK trace), \(\{0,1\}^d \rightarrow\mathcal{F} \) where \(f(b_0,b_1,…,b_d)=a(w) | g^{\sum\limits_{i=0}^{i=d}b_0 \cdot 2^i} =w\), \(\tilde{f}(x_0,x_1,…,x_d), x_i\in \mathcal{F}\) is its multi-linear extension
single MLE example
Prove \(\tilde{f}(\rho_0,\rho_1,…,\rho_d)=Claim_{\tilde{f}(\rho_0,\rho_1,…,\rho_d)}\) where \(\rho_i\in \mathcal{SF}\)
where \(\rho_i\in \mathcal{SF}\)
Input:
- evaluation point \((\rho_0,\rho_1,…,\rho_d)\)
- commitment to \(a(w)\) which is equivalent to commitment on \(f(b_0,b_1,…,b_d)\)
- evaluation claim \(Claim_{\tilde{f}(\rho_0,\rho_1,…,\rho_d)}\)
Problem reduced to
a out of domain point evaluation check, the needed info is:
- evaluation point \(\alpha \in \mathcal{SF}\)
- evaluation of \(a(w)\) on point ood \(a(\alpha)\)
multi MLEs example, linear batching claims with randomness
Prove :
\(\tilde{f}_1(\rho_0,\rho_1,…,\rho_d)=Claim_1\)
\(\tilde{f}_2(\rho_0,\rho_1,…,\rho_d)=Claim_2\)
\(\tilde{f}_3(\rho_0,\rho_1,…,\rho_d)=Claim_3\)
\(\tilde{f}_4(\rho_0,\rho_1,…,\rho_d)=Claim_4\)
where \(\rho_i\in \mathcal{SF}\)
batching
generate challenge \(\beta=\text{hash}(Claim_1,Claim_2,Claim_3,Claim_4)\)
compute combined claim \(Claim=Claim_1+ \beta Claim_2+\beta^2 Claim_3+\beta^3 Claim_4\)
combine MLEs that is actually into IOP:
\(\tilde{f}(x_0,x_1,…,x_d)=\tilde{f}_1(x_0,x_1,…,x_d)+\tilde{f}_2(x_0,x_1,…,x_d)\)
\(+\tilde{f}_3(x_0,x_1,…,x_d)+\tilde{f}_4(x_0,x_1,…,x_d)\)
Input for single MLE, normal case:
- evaluation point \((\rho_0,\rho_1,…,\rho_d)\)
- commitment to \(a(w)\) which is equivalent to commitment on \(f(b_0,b_1,…,b_d)\)
- evaluation claim \(Claim\)
Now due to batch, we don’t have commitment to \(a(w)\) directly, but we have commitment to \(a_1(w)\) ,\(a_2(w)\) ,\(a_3(w)\) ,\(a_3(w)\) that are corresponding to the commitments to \(\tilde{f}_i(x_0,x_1,…,x_d)\) respectively, the verifier has each single claim and the combine factor \(\beta\)
Problem reduced to
a out of domain point evaluation check, the needed info is:
- evaluation point \(\alpha \in \mathcal{SF}\)
- evaluation of \(a(w)\) on point ood \(a(\alpha)\)
this evaluation can be computed from the combination of evaluations of \(a_1(w)\) ,\(a_2(w)\) ,\(a_3(w)\) ,\(a_3(w)\) on point ood \(a(\alpha)\)
which further reduced to
a out of domain point evaluation linear combination check, the needed info is:
- evaluation point \(\alpha \in \mathcal{SF}\)
- evaluation of \(a_1(w)\) ,\(a_2(w)\) ,\(a_3(w)\) ,\(a_3(w)\) on point ood \(a(\alpha)\)
This is exactly how I batch the gkr instance at the beginning.
multi MLEs example, non-linear batching claims with randomness
Prove :
\(\frac{1}{\tilde{f}_1(\rho_0,\rho_1,…,\rho_d)}+\lambda\frac{1}{\tilde{f}_2(\rho_0,\rho_1,…,\rho_d)}=claim\)
where \(\rho_i\in \mathcal{SF}\)
the \(\lambda\) here is not for checking the MLEs evaluation claim, it is for distinguish the different buses, make sure that if all of them add together is 0, means individual bus accumulation is 0. this is batching the buses before GKR MLE prove.
very important!: if use both batch before gkr MLE and gkr instances, their challenge are different, cause gkr instances batching challenge is based on the individual claim.
MLE that is actually into IOP:
\(f_{mle}(x_0,x_1,…,x_d)=\frac{1}{\tilde{f}_1(x_0,x_1,…,x_d)}+\lambda\frac{1}{\tilde{f}_2(x_0,x_1,…,x_d)}=claim\)
Input for single MLE, normal case:
- evaluation point \((\rho_0,\rho_1,…,\rho_d)\)
- commitment to \(a_{mle}(w)\) which is equivalent to commitment on \(f_{mle}(b_0,b_1,…,b_d)\)
- evaluation claim \(Claim\)
question:
commitment to \(a_{mle}(w)\) which is equivalent to commitment on \(f_{mle}(b_0,b_1,…,b_d)\) is not available, but commitment to \(a_1(w)\) ,\(a_2(w)\) is available, they are equivalent to commitment to \(\tilde{f}_1(x_0,x_1,…,x_d)\), and \(\tilde{f}_2(x_0,x_1,…,x_d)\)
so are these commitment equivalent and it also produce the correct values further needed for the proof?
Problem reduced to
a out of domain point evaluation check, the needed info is:
- evaluation point \(\alpha \in \mathcal{SF}\)
- evaluation of \(a_{mle}(w)\) on point ood \(a(\alpha)\)
Is this evaluation can be computed from the combination of evaluations of \(a_1(w)\) ,\(a_2(w)\) on point ood \(a(\alpha)\), which is
\(\frac{1}{a_1(\alpha)}+\frac{1}{a_2(\alpha)}\)?
which further reduced to
a out of domain point evaluation linear combination check, the needed info is:
- evaluation point \(\alpha \in \mathcal{SF}\)
- evaluation of \(a_1(w)\) ,\(a_2(w)\) ,\(a_3(w)\) ,\(a_3(w)\) on point ood \(a(\alpha)\)