m0bi5 / bulletproofs-r1cs-gadgets

Arithmatic circuits convertible to R1CS based on Bulletproofs

Creating zero knowledge proofs using the Bulletproofs implementation from dalek-cryptography. This repo contains several examples that show how various statements can be represented as arithmetic circuits which can be converted to R1CS. A blog post was written that explains the Bulletproofs API with several examples, though the API has changed slightly.

Circuits

1. Prove a number is in certain range
2. Prove value is non-zero
3. Prove value is not equal to a given value
4. Proof of set membership, 2 implementations 1, 2
5. Proof of set non-membership
6. Proof knowledge of preimage given image of MiMC hash function
7. Poseidon permutation, a 2:1 (2 inputs, 1 output) and 4:1 (4 inputs, 1 output) hash function based on it. 2 kinds of S-boxes, cube and inverse. Described in this paper. The parameters are generated using a sage worksheet supplied by Dmitry Khovratovich and a Jupyter notebook for that worksheet is present in the repo called Poseidon_Ristretto.ipynb.
8. Proof of knowledge of leaf in a sparse merkle tree of width 2, i.e. each node has 2 children. Uses Poseidon 2:1 hash function.
9. Proof of knowledge of leaf in a sparse merkle tree of width 4, i.e. each node has 4 children. Uses Poseidon 4:1 hash function.

Building

This project uses a slightly modified implementation of Bulletproofs's develop branch. The difference is addition of the methods num_constraints and num_multipliers to Prover to return the number of constraints and multipliers respectively and addition of some new methods in constraint system and linear combinations

1. evaluate_lc: to evaluate a linear constraint
2. allocate_single: to return output variable when allocating right multiplier.
3. simplify: to simplify a linear combination, eg. simplify a linear combination like 2*x + 3*y + 4*x to 6*x + 3*y.

Use the nightly compiler to run tests like
cargo +nightly test --all-features
OR in release mode to run faster
cargo +nightly test --release --all-features