Simple Yet Efficient Knowledge-Sound and Non-Black-Box Any-Simulation-Extractable ZK-SNARKs
Motivated by applications like verifiable computation and privacy-preserving cryptocurrencies, many efficient pairing-based SNARKs were recently proposed. However, the most efficient SNARKs like the one by Groth (EUROCRYPT 2016) have a very brittle and difficult-to-verify knowledge-soundness proof in the generic model. Due to that, it is difficult to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program). We propose a template for constructing knowledge-sound and non-black-box any-simulation-extractable (NBBASE) SNARKs for QAP. This template is designed so that the knowledge-soundness and even NBBASE proofs of the new SNARKs are quite simple. The new knowledge-sound SNARK for QAP is very similar to the mentioned SNARK of Groth, except it has fewer trapdoors. To achieve NBBASE, we add to the knowledgesound SNARK a few well-motivated extra steps, while its security proof is even simpler due to the use of a second verification equation. Moreover, we give a simple characterization of languages like SAP, SSP, and QSP in the terms of QAP and show how to modify the SNARK for QAP correspondingly. The only prior published efficient simulation-extractable SNARK was for SAP.