Rust library for R1CS gadgets

Research
1

This is a new Rust library for building R1CS gadgets, with an emphasis on usability and type safety: https://crates.io/crates/r1cs

Here’s a contrived example to illustrate the API. Say we’re given a field element x as input, and we want to compute x^0, \dots, x^{n - 1}. We then want to sort those elements, and pass them through a MiMC-based hash. We could do that like so:

fn hash_sorted_powers<F: Field>(
    builder: &mut GadgetBuilder<F>,
    x: Expression<F>,
    n: usize
) -> Expression<F> {
    let powers = (0..n).map(|p| builder.exp(&x, p)).collect_vec();
    let sorted_powers = builder.sort_ascending(&powers);
    builder.mimc_hash(&sorted_powers)
}

In our nomenclature, the code above is just a helper function, not a “gadget”. If we wanted to create one, execute it (i.e. generate a complete witness), and print the output, we could do that like so:

let mut builder = GadgetBuilder::<Bn128>::new();
let x_wire = builder.wire();
let x_expression = Expression::from(x_wire);
let n = 10;
let hash = hash_sorted_powers(&mut builder, x_expression, n);

let gadget = builder.build();
let mut witness = values!(x_wire => 42u8.into());
gadget.execute(&mut witness);
println!("{}", hash.evaluate(&witness))

Features implemented so far:

  • Basic operations on field elements, booleans, and binary numbers
  • Comparisons
  • Verifying permutations with AS-Waksman networks
  • Sorting
  • Random access
  • MiMC, Poseidon
  • Merkle-Damgard, Davies-Meyer, Sponges
  • Merkle proofs

Coming soon:

  • Embedded curve types and operations
  • bellman and libsnark backends

Thanks to @akosba – several of the ideas came from him or from jsnark/xjsnark.

Any feedback would be appreciated!

3 Likes
2

After a quick review I have to say that I find your work fascinating! You’ve created this package quickly and solved problems that others (myself included) haven’t. And, if I’m not mistaken and could confirm with more time, this looks to be compatible with WebAssembly which could have astounding implications. (e.g. Browser-based SNARK proofs.)

Do you have a forum or IRC channel for discussions on advancing the project and potential collaboration?

3

Thanks Sean, that means a lot! Yeah, I think it would be possible to compile to wasm and execute gadgets in a browser, although I don’t have experience with that toolchain.

We don’t have a channel or forum yet, but it would great to get one started and get your thoughts there. I haven’t used IRC for a few years, but would Telegram or Discord work ok for you? I’m dlubarov on both.

4

Hey @dlubarov this is very interesting! I definitely believe that using gadgets is the best way to have a more generic scripting language, instead of implementing something like TinyRAM.

In terms of using WASM, we have actually published a tool for interoperability of ZK systems (between frontends to write the constraints and backends to generate the proofs based on the constraints) and it supports direct compilation to WASM.

Here is the tool, called zkInterface - https://github.com/qed-it/zkinterface
And you can see a DEMO here that compiles ZoKrates code into Bulletproofs prover / verifier - https://qed-it.github.io/zkinterface-wasm-demo/

In order for this to work with your Gadgets library, one would need to implement the encoding of the calling convention to your rust library (we also have one for Bellman). If this interests you, definitely let me know.

2 Likes
5

Thanks Daniel, that sounds very promising. Makes sense to have a common format instead of n-to-n conversion tools! I’ll try implementing it when I have a chance, probably later this week, and let you know if I have questions.

1 Like
6

Update: I added a small separate crate for exporting to zkinterface, larely based on the code in QED-it’s ZoKrates fork.

2 Likes
7

Awesome @dlubarov, great work! We will check it out this week and give feedback :slight_smile:

9

@dlubarov I just visited crate.io and clicked the R1CS library , unexpectedly to know that work was done by you . Can we work together to get the remaining done ?

1 Like