Skip to content
C++ library for IOP-based zkSNARKs
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
depends
libiop
.gitignore Initial release of libiop Apr 9, 2019
.gitmodules
AUTHORS
CMakeLists.txt Initial release of libiop Apr 9, 2019
INSTALL.md
LICENSE Initial release of libiop Apr 9, 2019
README.md

README.md

libiop: a C++ library for IOP-based zkSNARKs

This library provides zkSNARK constructions that are transparent and post-quantum, and moreover rely only on lightweight symmetric cryptography (any cryptographic hash function).

The library provides a tool chain for transforming certain types of probabilistic proofs (see below) into zkSNARKs that have the above properties. The library includes two zkSNARK constructions that follow this paradigm:

  • The Aurora protocol from [BCRSVW], whose argument size is O(log2 N);
  • The Ligero protocol from [AHIV], whose argument size is O(N0.5).

Both of these zkSNARKs support R1CS, an NP-complete relation that generalizes arithmetic circuit satisfiability. An important component of Aurora, which is of independent interest, is the FRI proximity test. These protocols all support binary extension fields, and smooth prime fields.

WARNING: This is an academic proof-of-concept prototype, and in particular has not received careful code review.
This implementation is NOT ready for production use.

Non-interactive arguments from IOPs

Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs (PCPs). Known IOP protocols have much better (asymptotic and concrete) performance compared to PCP protocols.

A method known as the BCS transformation uses a cryptographic hash function (modeled as a random oracle) to transform any public-coin IOP into a non-interactive argument. This transformation has the benefit that the resulting non-interactive argument is:

  • transparent, because the only global parameter needed to produce/validate proof strings is the hash function; and
  • post-quantum, because no attacks are known on the BCS transformation.

Moreover, since no cryptography beyond the hash function is used, non-interactive arguments obtained via the BCS transformation are relatively lightweight (in terms of computational resources). Finally, the BCS transformation preserves zero knowledge, in the sense that if the underlying IOP is (honest verifier) zero knowledge then the resulting non-interactive argument is zero knowledge.

This library provides zkSNARKs obtained via the BCS transformation.

IOP protocols

The folder libiop/iop contains infrastructure for writing IOP protocols.

The folder libiop/protocols contains several protocols written using this infrastructure. These include:

language round
complexity
oracle length
(field elts)
query
complexity
prover time
(field ops)
verifier time
(field ops)
Ligero-IOP R1CS 2 O(N) O(N0.5) O(N logN) O(N)
Aurora-IOP R1CS O(log N) O(N) O(log N) O(N logN) O(N)

The first is an IOP from the Ligero paper,[1] and the second is an IOP from the Aurora paper.

Efficient IOP protocols such as the above are obtained by combining two components: (1) RS-encoded IOP, and a (2) proximity test for the RS code. (See this paper for more details.) The codebase in this library provides infrastructure that enables generically composing these components.

  • The folder libiop/protocols/encoded contains RS-encoded IOPs. This includes the RS-encoded IOPs that form the core of the Aurora and Ligero protocols.
  • The folder libiop/protocols/ldt contains proximity tests for the RS code. This includes a direct test (used by Ligero) and the FRI protocol (used by Aurora and other IOPs).

[1]: More precisely, the Ligero paper only describes a construction for arithmetic circuits. An appendix of the Aurora paper explains how to extend the construction to support R1CS. The latter is the implemented protocol.

BCS transformation

The folder libiop/snark/common contains the BCS transformation as a standalone component.

The folder libiop/snark contains zkSNARKs obtained by applying the BCS transformation to the IOP protocols above.

language prover time argument size verifier time
Ligero-SNARK R1CS Oκ(N logN) Oκ(N0.5) Oκ(N)
Aurora-SNARK R1CS Oκ(N logN) Oκ(log2 N) Oκ(N)
κ is used to denote the asymptotics dependence on the security parameter explicitly.

A flag make_zk can be set to indicate that the transformation should preserve zero knowledge, or not set to indicate that the IOP being transformed is not zero knowledge and so there is no need to preserve zero knowledge.

Installation

Please follow the installation instructions.

Testing

Test files are in libiop/tests.

For example, to run all of the tests for the Aurora protocol, do the following:

	$ ./test_aurora_snark
	$ ./test_aurora_protocol # Tests the RS-encoded IOP
	$ ./test_aurora_protocol_components # More granular tests
	$ ./test_aurora_multi_lincheck
	$ ./test_aurora_rowcheck
	$ ./test_aurora_sumcheck

Profiling

The folder libiop/profiling contains tooling to produce protocol execution traces with timing and argument size information. For example, we can create traces for Aurora and Ligero over a 181 bit prime field, with RS extra dimensions=3 with the following commands:

  $ ./instrument_aurora_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --optimize_localization=1
  $ ./instrument_ligero_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --RS_extra_dimensions=3

We use traces generated from the above commands to create the following plots:

argument size

prover timeverifier time

License

This library is licensed under the MIT License.

Acknowledgements

This work was supported by: a Google Faculty Award; the Israel Science Foundation; the UC Berkeley Center for Long-Term Cybersecurity; and donations from the Ethereum Foundation, the Interchain Foundation, and Qtum.

You can’t perform that action at this time.