Recent years have witnessed great progress in building zero knowledge proofs, among which zero knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) is the most attracting one. Beyond completeness, zero knowledge, computational soundness, zk-SNARKs also enjoys succinctness -- both the proof size and verification computation are sub-linear in the size of witness.
In this paper, we consider the scenario where the prover of zk-SNARK delegates its proving power to other parties. Recall that a prover has to use the witness w of a statement x to generate a proof \pi for verifiers. When a prover is absent from work, he/she may like to delegate the proving ability to other parties (proxies). A naive way is that the prover shares the witness w with other parties (proxies). In this way, anyone who obtains w is able to generate proofs for x. But this is too much, since abuses of proving delegation are unavoidable. This raises a question: Is it possible for the prover of zk-SNARK to delegate the proving ability without leaking the witness?
To solve the problems, a research team led by Jinrui Sha published their new research on 15 October 2024 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The team solve the above question. At the first sight, it seems there is a dilemma when trying to find a solution to the question. On the one hand, the proxy has to use the witness to delegate the proof generation. On the other hand, the proxy is not allowed to obtain the witness to avoid information leakage. In this paper, we circumvent this dilemma with multi-proxies. Each proxy only gets a piece of the witness, which alone does not leak information about the witness. But many proxies can cooperate to finish the generation of the proof. We name this new type of zk-SNARK delegable zk-SNARK.
The team define the syntax of -delegable zk-SNARK and its -completeness, -knowledge soundness and -perfect zero knowledge. We also construct a - delegable zk-SNARK for the NPC language of arithmetic circuit satisfiability, which is further characterized by the quadratic arithmetic programs relation . We take advantage of the additive and multiplicative properties of polynomial-based secret sharing schemes to achieve delegation for zk-SNARK. Our delegable zk-SNARK achieves -completeness, -knowledge soundness and -perfect zero-knowledge.
DOI: 10.1007/s11704-023-2782-9