Uniform-Sound zkSNARKs in the Plain Model

[adammoneill]

The open problem is to construct zero-knowledge succinct arguments of knowledge (zkSNARKs) that do not use a common reference string (CRS), i.e., are in the so-called ``plain model.'' A CRS is problematic because it inherently requires trust and often elaborate ceremonies to generate. Removing the CRS is impossible under the standard formulation of zkSNARKs. To bypass this impossibility, we propose to use uniform-soundness. This means the adversary is modeled as a Turing machine rather than a circuit family; intuitively, the adversary's code must be efficiently computed. I believe this is a reasonable assumption in practice. Similarly, the non-interactive zero-knowledge (NIZK) property is impossible without a CRS. To bypass this impossibility, we allow quasi-polynomial-time (QPT) simulators. Again, I believe provides a reasonable guarantee in practice.

This problem is heavily related to:

1. Barak et al. (CRYPTO 2003), which shows that pseudorandom generators used for derandomizing non-cryptographic algorithms can be used for cryptographic algorithms. In particular, they get non-interactive ``witness indistinguishable'' (WI) proof systems in the plain model.
2. Barak and Pass (TCC 2004), which constructs (non-succinct) non-interactive zero-knowledge proofs (NIZKs) in the plain model with uniform-soundness.
3. Bitansky et al. (TCC 2016-B), which constructs an (interactive) three-message ZK argument system with uniform-soundness.

Currently PL's Filecoin uses a zkSNARK due to Groth (EUROCRYPT 20016) whose setup requires a ``powers of tau'' ceremony due to its algebraic structure. An ideal outcome of the proposed project would be to remove the latter by considering uniform-soundness and QPT ZK. This would simplify PL's zkSNARK. It would also increase its efficiency, as the size of the (fixed) CRS would no longer depend on the circuit size.

Currently, the only approach to achieving zkSNARKs in the plain model is to use cryptographic hashing and appeal to the random oracle (RO) model (Bellare and Rogaway, CCS 1993). Unfortunately, this puts trust in the hash function designer.
Also, such an approach does not work for zkSNARKs based on algebraic groups such as Groth's zkSNARKs, since they require the base zkSNARK to have a uniformly random CRS.

The solution definition is: a construction of a CRS-free, RO-free zkSNARK satisfying uniform-soundness and QPT ZK. There are a two soft constraints at play here. The first is concrete efficiency. It may be a feasibility result, as is the case for Barak and Pass, that is not practical (e.g., in terms of the prover's or verifier's running-time). The ultimate goal, of course, is a practical such zkSNARK that modifies an existing one as little as possible to simplify implementation. In particular, I would like a version of Groth's zkSNARK in the plain model. The other soft constraint is the notion of ZK. It is not clear that QPT is the ``right'' notion, and a valid solution may satisfy a different one.