#ff #uint #finite-fields #framework #finite #bellman #circom

ff-uint

Library for building and interfacing with fixed-sized integers and finite fields

11 releases

0.2.4 Mar 10, 2022
0.2.2 Jan 23, 2022
0.2.0 Nov 22, 2021
0.1.7 Jul 28, 2021
0.1.1 Sep 23, 2020

#249 in Cryptography

Download history 37/week @ 2022-06-15 34/week @ 2022-06-22 12/week @ 2022-06-29 36/week @ 2022-07-06 85/week @ 2022-07-13 89/week @ 2022-07-20 66/week @ 2022-07-27 37/week @ 2022-08-03 38/week @ 2022-08-10 19/week @ 2022-08-17 59/week @ 2022-08-24 20/week @ 2022-08-31 57/week @ 2022-09-07 54/week @ 2022-09-14 27/week @ 2022-09-21 34/week @ 2022-09-28

172 downloads per month
Used in 4 crates (via fawkes-crypto)

MIT/Apache

86KB
2K SLoC

Fawkes-Crypto - zkSNARKs framework

Abstract

Fawkes-Crypto is a lightweight framework for building circuits in bellman, using groth16 proving system and BN254 curve.

The framework is targeted to use best practices for circuit building from circom and sapling-crypto.

Final fields and circuit math are wrapped and operators are implemented, so, in most cases if you want to type a+b, you can do it.

Example

Here is an example, how Merkle tree implementation is working. Also you may check the rollup here.

#[derive(Clone, Signal)]
#[Value="MerkleProof<CS::F, L>"]
pub struct CMerkleProof<'a, CS: ConstraintSystem, const L: usize> {
    pub sibling: SizedVec<CNum<'a, CS>, L>,
    pub path: SizedVec<CBool<'a, CS>, L>
}


pub fn c_poseidon_merkle_proof_root<'a, CS: ConstraintSystem, const L: usize>(
    leaf:  &CNum<'a, CS>, 
    proof: &CMerkleProof<'a, CS, L>,
    params: &PoseidonParams<CS::F>
) -> CNum<'a, CS> {
    let mut root = leaf.clone();
    for (p, s) in proof.path.iter().zip(proof.sibling.iter()) {
        let first = s.switch(p, &root); 
        let second = &root + s - &first;
        root = c_poseidon( [first, second].as_ref(), params);
    }
    root
}

Signal is a sparse linear combination of inputs, based on ordered linked list, so we perform arithmetics with Signal with U(N) complexity. With Signal bellman will allocate additional inputs only when you really need it (for example, in the case when you multiply two nonconstant Signal). If you perform multiplication with constant or zero Signal, no additional inputs will be allocated.

Benchmarks

Circuit Constraints Per bit
poseidon hash (4, 8, 54) 255 0.33
jubjub oncurve+subgroup check 19
ecmul_const 254 bits 513 2.02
ecmul 254 bits 2296 9.04
poseidon merkle proof 32 7328
poseidon eddsa 3860
rollup 1024 txs, 2^32 set 35695616

At i9-9900K rollup is proved for 628 seconds.

Source code of the rollup is available at https://github.com/snjax/fawkes-rollup.

Circuit improvements

  • We are using indeterministic subgroup checks, performing most part of computations as witness-only and perform cofactor multiplication at the circuit.
  • ecmul and ecmul_cost operations are working assuming that the base point is in the subgroup. This allows us to use Montgomery (0, 0) point as adder initial state. Then the adder never reaches zero point and subgroup point, because (0, 0) is not in subgroup and we can use cheap montgomery_add circuit safely.
  • improved compconstant circuit. The same PR into circomlib available here

See more as ethresear.ch here.

Authors

Igor Gulamov

Disclaimer

Fawkes-Crypto has not been audited and is provided as is, use at your own risk.

License

Fawkes-Crypto is available under Apache License 2.0 license or MIT as your choice.

Dependencies

~2.4–3.5MB
~59K SLoC