libsnark August 2017 update

[Eran Tromer]

Dear users of libsnark,

Below is an announcement regarding recent changes in libsnark, now included in the “master” branch.

Transitioned to CMake

We upgraded libsnark’s build process from a shell script and Makefile for installation and compilation to a new CMake-based process (https://cmake.org/). We are making this transition to better address the growing system-level and modularity needs of libsnark.

The commands and flags for compiling libsnark have changed (see Transition-to-CMake.md in the repo).

Factored out algebraic routines into new libraries

We have factored out core algebraic components of libsnark to allow developers to use internal classes and functions that are useful in applications beyond libsnark, as well as to simplify the growing directory structure of libsnark.

The two new libraries are:

• libff -  finite fields and elliptic curves

• libfqfft - fast polynomial evaluation and interpolation in various finite domains

These libraries are now automatically fetched and installed as Git submodules, in the “depends” (formerly: “third-party”) directory.

Monolithic version of libsnark is archived and unsupported

As part of this transition, we will maintain a copy of the deprecated version under the “monolithic” branch. However, we will not support any future development work for the “monolithic” branch. Should a critical vulnerability be found in “monolithic”, we will patch it accordingly.

Added automatic builds for commits and pull requests with Travis CI

In an effort to reduce compilation and system-level issues, we have added automatic builds for commits and pull requests to libsnark. Initially, we are performing these checks for Ubuntu 14.04, but we hope to expand this to more operating systems (your help would be appreciated!).

New SNARK constructions

We have also added two new pre-processing zkSNARK implementations to libsnark, both targeting the R1CS relation. They are r1cs_gg_ppzksnark from [Groth16] and r1cs_se_ppzksnark from [GM17]. Compared to r1cs_ppzksnark, which implements a modification of the Pinocchio protocol [PGHR13/BCTV14a], the new proof systems have improved empirical and asymptotic performance (see our performance comparison) at expense of relying on stronger cryptographic assumptions. The proof system of [GM17] is simulation extractable.

Improved performance

The current zk-SNARK prover spends most of its time computing a multi-exponentiation (the second largest cost is polynomial division via FFTs; the rest are negligible). This computation was previously performed by an implementation of the Bos-Coster algorithm. We have now implemented a variant of Pippenger’s algorithm from [BDLO12], which gives an asymptotic improvement, and switched our proof systems to use this algorithm. Concretely, for R1CS instances of million constraints, the overall speed-up of the prover runtime is around 1.25x.

Mailing list

For future announcements, as well as discussion with the developers and other users, please join the new libsnark mailing list.

[David Mercer]

These are exciting developments, and I look forward to seeing some of these improvements downstream in projects that use libsnark.

Quick question regarding the new cmake build system, is there a list of platforms/compilers/toolchains that it is tested on? specifically on Windows?

Thanks!

-David Mercer

Tucson, AZ

Lead Developer

HUSH and zcash4win

 

[Veikko Eeva]

These are exciting developments, and I look forward to seeing some of these improvements downstream in projects that use libsnark.

Quick question regarding the new cmake build system, is there a list of platforms/compilers/toolchains that it is tested on? specifically on Windows?

It does not compile on Windows, a cursory glance suggests the dependencies aren't there. But this is definitely easier to get working on Windows (and other platforms) now, I think.

[Jason Ge]

One question on the multi-exponentiation issue:

 

The current zk-SNARK prover spends most of its time computing a multi-exponentiation (the second largest cost is polynomial division via FFTs; the rest are negligible). 

It looks like the exponential table construction is done during the key generation phase as I saw the output in key generation process:

 (enter) Generating G1 multiexp table      

  (leave) Generating G1 multiexp table      

  (enter) Generating G2 multiexp table      

  (leave) Generating G2 multiexp table

When you said the 'prover' spends most of the time on multi-exponentiation, do you mean this function 

template <typename ppT>

r1cs_ppzksnark_proof<ppT> r1cs_ppzksnark_prover(

    const r1cs_ppzksnark_proving_key<ppT> &pk,

    const r1cs_ppzksnark_primary_input<ppT> &primary_input,

    const r1cs_ppzksnark_auxiliary_input<ppT> &auxiliary_input)

was calling computations on the multi-exponentiations? Thank you so much for your explanation in advance!

Best,

Jason

[Madars Virza]

Hi Jason,

It looks like the exponential table construction is done during the key generation phase as I saw the output in key generation process:

 

When you said the 'prover' spends most of the time on multi-exponentiation, do you mean this function 

template <typename ppT>

r1cs_ppzksnark_proof<ppT> r1cs_ppzksnark_prover(

    const r1cs_ppzksnark_proving_key<ppT> &pk,

    const r1cs_ppzksnark_primary_input<ppT> &primary_input,

    const r1cs_ppzksnark_auxiliary_input<ppT> &auxiliary_input)

was calling computations on the multi-exponentiations?

Yes! There are two multi-exponentiation problems encountered in linear-PCP SNARKs.

First, generator needs to encode its linear PCP queries. That is, do the computations of the following kind: given a query vector (a_1, ..., a_n) output (g^a_1, ..., g^a_n, g^(\alpha a_1), ..., g^(\alpha a_n)). This fixed-base multi-exponentiation problem benefits from first precomputing powers g, g^2, g^4, ...,, so latter computations only require elliptic point additions (and no doublings).

(see https://github.com/scipr-lab/libsnark/blob/master/libsnark/zk_proof_systems/ppzksnark/r1cs_ppzksnark/r1cs_ppzksnark.tcc#L354-L402 )

Next, the prover answers an encoded query (g_1, ..., g_n) by its witness (w_1, ..., w_n) by computing the value g_1^w_1 * ... * g_n^w_n (i.e. variable-base exponentiation). As bases g_i are all different, precomputing their powers is not beneficial. However, because intermediate values g_i^w_i are not needed, one can (asymptotically) efficiently compute the final product using tailored algorithms that do not obtain those intermediates in their computation flow. In particular, libsnark implements the Bos-Coster algorithm, and a variant of Pippenger's algorithm.

(see https://github.com/scipr-lab/libsnark/blob/master/libsnark/zk_proof_systems/ppzksnark/r1cs_ppzksnark/r1cs_ppzksnark.tcc#L484-L533 )

Hope that helps!

Madars