0xbok / circom-bigint

Big integer arithmetic in circom

circom-bigint

Implementation of bigint arithmetic in circom.

Project overview

This repository provides proof-of-concept implementations of bigint arithmetic in circom. These implementations are for demonstration purposes only. These circuits are not audited, and this is not intended to be used as a library for production-grade applications.

Circuits can be found in circuits. scripts contains various utility scripts (most importantly, scripts for building an example zkSNARK using the bigint circuit primitive). test contains some unit tests for the circuits, mostly for witness generation.

Install dependencies

• Run yarn at the top level to install npm dependencies (snarkjs and circomlib).
• You'll also need circom version >= 2.0.2 on your system. Installation instructions here.
• To build bigint circuits, you'll need to download a Powers of Tau file with 2^8 constraints and copy it into the circuits subdirectory of the project, with the name pot08_final.ptau. We do not provide such a file in this repo due to its large size. You can download and copy Powers of Tau files from the Hermez trusted setup from this repository.

Building keys and witness generation files

Run yarn build:bigint at the top level to compile a bigint related circuit.

This will create a subdirectory inside a build directory at the top level (which will be created if it doesn't already exist). Inside this directory, the build process will create r1cs and wasm files for witness generation, as well as a zkey file (proving and verifying keys).

This process will also generate and verify a proof for a dummy input in the respective scripts/bigint subdirectory, as a smoke test.

Benchmarks

Todo.

Testing

Run yarn test at the top level to run tests. Note that these tests only test correctness of witness generation. They do not check that circuits are properly constrained, i.e. that only valid witnesses satisfy the constraints.

Circuit unit tests are written in typescript, in the test directory using chai, mocha, and circom_tester. To run a subset of the tests, use yarn test --grep [test_str] to run all tests whose description matches [test_str].

Acknowledgments

This project was built during 0xPARC's Applied ZK Learning Group #1.

We use an optimization for big integer multiplication from xJsnark.

circom-bigint's Issues

`BigModInv` can use `BigMultModP` instead of `BigMult`

BigModInv calculates multiplicative inverse of a bigint a mod bigint p. For contraint checking, it first multiplies the inverse with a through BigMult, then computes its mod p. This can all be through BigMultModP template, which improves readability.

Context: bigint.circom#L522-L533

Unnecessary carry digit computation and constraint in `BigModSubP`

BigModSubP calculates $(a-b) % p$. Internally it calls BigAdd to compute $(a-b) + p$.

component add = BigAdd(n, k);

BigAdd also returns a carry register however it isn't used for computation or for constraints downstream. We can create a new template BigAddNoCarry and call it instead to contraint-optimize the circuit.

Context: bigint.circom#L469

Add comments specifying assumptions on circuit signals

Like bit size - most of the circuits assume n-bit wide inputs which the inheriting circuits need to constrain.