following the previous posts about spartan: 1 and 2
Chapter 5, A family of NIZKs with succinct interactive argument of knowledge
from post 1 we get a goal to check
\(\mathcal{Q}_{io}(\tau)=\sum\limits_{x\in \{0,1\}^s}\mathcal{G}_{io,\tau}(x)=\sum\limits_{x\in \{0,1\}^s}\widetilde{F}_{io}(x)\cdot \widetilde{eq}(\tau,x)=0\)
where \(\tau\) is a random checking point.
recall we have:
\(\widetilde{F}_{io}(x)=\left(\sum\limits_{y\in\{0,1\}^s}\widetilde{A}(x,y)\cdot Z(y)\right)\cdot \left(\sum\limits_{y\in\{0,1\}^s}\widetilde{B}(x,y)\cdot Z(y)\right)\)
let’s start from here to do further reduction.
reduction step 1: use sum-check protocol to check \(\sum\limits_{x\in \{0,1\}^s}\mathcal{G}_{io,\tau}(x)=\sum\limits_{x\in \{0,1\}^s}\widetilde{F}_{io}(x)\cdot \widetilde{eq}(\tau,x)=0\)
the last step of a sum-check protocol is an evaluation of a function in a random point. so the above claim can be reduced via sumcheck protocol to \(e_x\stackrel{?}{=}\mathcal{G}_{io,\tau}(r_x)\) where \(r_x\in \mathbb{F}^s\)
to compute \(\mathcal{G}_{io,\tau}(r_x)\) is equivalent to compute \(\mathcal{G}_{io,\tau}(r_x)=\widetilde{F}_{io}(r_x)\cdot \widetilde{eq}(\tau,r_x)\)
so let’s talk about computing \(\widetilde{F}_{io}(r_x)\)
\(\widetilde{F}_{io}(r_x)=\left(\sum\limits_{y\in\{0,1\}^s}\widetilde{A}(r_x,y)\cdot Z(y)\right)\cdot \left(\sum\limits_{y\in\{0,1\}^s}\widetilde{B}(r_x,y)\cdot Z(y)\right)\)
$$-\left(\sum\limits_{y\in\{0,1\}^s}\widetilde{C}(r_x,y)\cdot Z(y)\right)$$
The prover can then make three separate claims to \(\mathcal{V}\) :
$$\bar{A}(r_x)=v_A,\bar{B}(r_x)=v_B,\bar{C}(r_x)=v_C$$
(why the tilde becomes bar? because the values here is the product of matrix and witness, namely \(\bar{A}(r_x)=\sum\limits_{y\in\{0,1\}^s}\widetilde{A}(r_x,y)\cdot Z(y)\))
Then \(\mathcal{V}\) can evaluate
$$\mathcal{G}_{io,\tau}(r_x)=(v_A\cdot v_B – v_C)\cdot \tilde{eq}(r_x,\tau)$$
Then \( \mathcal{V}\) needs to use three sum-check protocol to check \(v_A,v_B,v_C\) are correct.
reduction step 2: use random linear combination to make several proofs into one.
There is a way to combine three checks into one. Namely, \(\mathcal{V}\) samples \(r_A,r_B,r_C\) computes
$$c=r_A\cdot v_A+r_B\cdot v_B+r_C\cdot v_C$$
At this point, there should be polynomial commitment scheme involved already, but I didn’t figure out, so let’s continue without it first.
prover checks with the prover
$$r_A\cdot \bar{A}(r_x)+r_B\cdot \bar{B}(r_x)+r_C\cdot \bar{C}(r_x)\stackrel{?}{=}c$$
which means, the combined sum-check is for
\(L(r_x)= \sum\limits_{y\in\{0,1\}^s}\left(r_A\widetilde{A}(r_x,y)+ r_B \cdot\widetilde{B}(r_x,y)+ r_C \cdot\widetilde{C}(r_x,y)\right)\cdot \widetilde{Z}(y)\)
\(= \sum\limits_{y\in\{0,1\}^s}M_{r_x}(y)\)
now we reach here
til now we have two sumchecks:
- \(\sum\limits_{x\in \{0,1\}^s}\mathcal{G}_{io,\tau}(x)=\sum\limits_{x\in \{0,1\}^s}\widetilde{F}_{io}(x)\cdot \widetilde{eq}(\tau,x)=0\)
- \(\sum\limits_{y\in\{0,1\}^s}M_{r_x}(y)\)
the second sumcheck protocol is the step to finish the first sumcheck protocol.
Problems need to be solved and the content of the rest of the paper:
from this equation:
\(L(r_x)= \sum\limits_{y\in\{0,1\}^s}\left(r_A\widetilde{A}(r_x,y)+ r_B \cdot\widetilde{B}(r_x,y)+ r_C \cdot\widetilde{C}(r_x,y)\right)\cdot \widetilde{Z}(y)\)
\(= \sum\limits_{y\in\{0,1\}^s}M_{r_x}(y)\)
At then end of the second sum-check protocol, verifier needs to evaluate
\(M_{r_x}(r_y)\) for \(r_y \in \mathbb{F}^s\), namely:
\(L(r_x)= \left(r_A\widetilde{A}(r_x,r_y)+ r_B \cdot\widetilde{B}(r_x,r_y)+ r_C \cdot\widetilde{C}(r_x,r_y)\right)\cdot \widetilde{Z}(r_y)\)
=\(\widetilde{M}_{r_x}(r_y)\)
observations:
- use extractable polynomial commitment for multiliear polynomial \(\widetilde{Z}(r_y)\) to avoid \(O(|w|)\) communications
- other terms can be computed locally by verifier, namely, \(\widetilde{A},\widetilde{B},\widetilde{C}\) it is circuit information. section 6 of the paper discusses how to make the computation sublinear
the whole process
I didn’t complete the whole process yet, but let’s move to the spark part first.