We give a commit-and-prove zero-knowledge argument Protocol for the satisfiability of a QAP for an arithmetic circuit \(C\). For wires in the circuit \(\{a_i\}_{i=0}^n\), we denote the input witnesses are \(\{a_i\}_{i=0}^k\), the inner circuit witnesses are \(\{a_{i}\}_{i=k+1}^l\) and the statements wires are \(\{a_{i}\}_{i=l+1}^n\). The quadratic arithmetic program, Pedersen commitment and vector Pedersen commitment give a relation of the form
$$R=(\mathbb{G},\mathbb{Z}_p,k,l,\{u_i(X), v_i(X),w_i(X)\}_{i=0}^n, z(X),\{a_i\}_{i=0}^n,$$
such that with \(a_0=1\)
$$\sum\limits_{i=1}^na_iu_i(X) \cdot\sum\limits_{i=1}^na_iv_i(X)=\sum\limits_{i=1}^na_iw_i(X)+h(X)z(X)$$
$$\wedge \{c_i=g^{a_i}h_i^\gamma\}_{i=1}^k \ \wedge \ c_l=h^r\prod\limits_{i=k+1}^lg_i^{a_i} \wedge c_h=h^t\prod\limits_{i=0}^{n-2}g_i^{e_i}$$
where \(e_0,…,e_{n-2}\) are the coefficients of \(h(X)\).
The zero knowledge proof algorithm I used to prove the above relationship, is not efficient, but it really help me understand both Groth16 and the inner product argument in bulletproof.
High level idea
Divide the QAP into 4 parts, each parts is a inner product of two vectors, i.e.,
- \(\sum\limits_{i=1}^na_iu_i(X)=<(a_1,a_ 2,…,a_n),(u_1(x),…, u_n(x))>\)
- \(\sum\limits_{i=1}^na_iv_i(X)=<(a_1,a_ 2,…,a_n),(v_1(x),…, v_n(x))>\)
- \(\sum\limits_{i=1}^na_iw_i(X)=<(a_1,a_ 2,…,a_n),(w_1(x),…, w_n(x))>\)
- \(h(X)z(X)=<(e_0,…,e_{n-2}),(z(x),xz(x),…, x^{n-2}z(x))>\)
The prover will commit to the above product, then use inner product argument (IPA) from Bulletproof to prove the correctness.
Then use a protocol that prove the relationship of \(COM(a\cdot b), COM(a), COM(b)\)
The mass exit problem in Privacy Preserving Zk-rollup is serious
When the design of privacy preserving zk-rollup require the zk-rollup nodes to hold some secrets, the mass exit problem need to be considered seriously as, these secrets might become necessary for a user withdraw their asset from layer 2 to layer 1. And if this is the case, if zk-rollup nodes offline, or behave maliciously, the users will stuck. So one key property that privacy-preserving zk-rollup need to have is, user should be able to withdraw, without the involvement of zk-rollup nodes.