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.