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!