This WIP PR addresses https://github.com/vacp2p/zerokit/issues/16 solving previous issues with proving and verifying keys import, proof generation/verification, RLN witness fields, etc. It further removes some unnecessary crates.

Problem

Create a merkle tree that allows one to insert identity commitments and make merkle proofs.

From spec (https://github.com/vacp2p/rfc/blob/670816fa01f84fbde12a44f72f30e9b9458aaf5a/content/docs/rfcs/32/README.md):

{
  root: bigint
  indices: number[]
  path_elements: bigint[][]
}

See:

• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L44
• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/src/utils.ts#L27
• https://github.com/kilic/rln/blob/7ac74183f8b69b399e3bc96c1ae8ab61c026dc43/src/merkle.rs
• https://github.com/worldcoin/semaphore-rs/blob/main/src/merkle_tree.rs

Acceptance criteria

Merkle tree struct and merkle proofs can be created

Problem

We want to be able to use RLN through Circom circuits in Nim.

Notes

Currently this issue is a bit too big, so will probably want to split this up into smaller tasks.

Some relevant links:

• https://github.com/kilic/rln
• https://github.com/status-im/nim-waku/blob/master/waku/v2/protocol/waku_rln_relay/rln.nim
• https://github.com/appliedzkp/rln
• https://github.com/appliedzkp/zk-kit/tree/main/packages/protocols/src
• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L44
• https://github.com/appliedzkp/zk-kit/blob/acaf3f43a0aab447905cdd9d6b9b24a8d99344fb/packages/protocols/src/witness_calculator.js

Acceptance criteria

RLN API is usable through nim-waku and has feature parity with existing implementation.

Problem

Currently https://github.com/vacp2p/zerokit/blob/master/rln/src/lib.rs#L51test is ignored because verification fails:

        // thread 'test::test_end_to_end' panicked at 'called `Result::unwrap()`
        // on an `Err` value: SynthesisError(MalformedVerifyingKey)',
        // rln/src/lib.rs:62:84
        //
        // Not sure why this is MalformedVerifyingKey, though the proof is
        // likely incorrect with wrong fields in protocol.rs
        //
        // Indeed:
        // if (public_inputs.len() + 1) != pvk.vk.gamma_abc_g1.len() {

This requires changing protocol.rs (https://github.com/vacp2p/zerokit/blob/master/rln/src/protocol.rs#L85) so public inputs etc are correct.

This should make tests pass, but it is also possible that the verification key from zkey file isn't correctly generated for some reason.

Note

This is using a different code path from JSON generate proof.

This is a slightly more specific version of https://github.com/vacp2p/zerokit/issues/10

Acceptance criteria

End to end tests pass and RLN proof can be verified.

Problem

Add poseidon hash with functionality according to spec. Create an identity structure with identity commitment that can be inserted into a merkle tree.

From spec (https://github.com/vacp2p/rfc/blob/670816fa01f84fbde12a44f72f30e9b9458aaf5a/content/docs/rfcs/32/README.md):

[](https://github.com/vacp2p/rfc/blob/670816fa01f84fbde12a44f72f30e9b9458aaf5a/content/docs/rfcs/32/README.md#hash-function)Hash function

Canonical [Poseidon hash implementation](https://eprint.iacr.org/2019/458.pdf) is used, as implemented in the [circomlib library](https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom), according to the Poseidon paper. This Poseidon hash version (canonical implementation) uses the following parameters:

    t: 3
    RF: 8
    RP: 57

See:

• https://github.com/iden3/circomlibjs/blob/main/src/poseidon.js
• https://github.com/kilic/rln/blob/7ac74183f8b69b399e3bc96c1ae8ab61c026dc43/src/circuit/poseidon.rs
• https://github.com/arnaucube/poseidon-rs

Acceptance criteria

Posedion hash function added and with correct parameters.

Problem

Create an identity structure with identity commitment that can be inserted into a merkle tree.

From spec (https://github.com/vacp2p/rfc/blob/670816fa01f84fbde12a44f72f30e9b9458aaf5a/content/docs/rfcs/32/README.md):

{
    identity_secret: [identity_nullifier, identity_trapdoor],
    identity_secret_hash: poseidonHash(identity_secret),
    identity_commitment: poseidonHash([identity_secret_hash])
}

See:

• https://github.com/worldcoin/semaphore-rs/blob/main/src/identity.rs
• https://github.com/appliedzkp/zk-kit/tree/main/packages/identity
• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L32-L35
• https://github.com/kilic/rln/blob/7ac74183f8b69b399e3bc96c1ae8ab61c026dc43/src/circuit/bench.rs#L93-L96

Acceptance criteria

Identity struct based on poseidon hash with secret and commitment

Problem

Create the most minimal Circom circuit example possible with prove, verification etc API.

Ensure this can be called through basic FFI interface.

Instead of checking in .wasm and .zkey files as resources, it'd be better to add as a git submodule with instructions for generating them.

https://github.com/appliedzkp/rln

Acceptance criteria

RLN submodule and instructions added

Instead of manually importing moving target

Assumes public functions etc are exposed and that code bases / priorities end up developing in same way

1. Upstream changes
2. Keep fork up to date
3. Keep option open to embed it as appropriate

This PR addresses https://github.com/vacp2p/zerokit/issues/19.

Progress

• [x] Implement byte serialization/deserialization of custom data structure (RLN Witness and Proof values);
• [x] Extend/update RLN Rust public API to support all required features;
• [ ] Extend/update RLN C public API to support all required features.

Problem

PR https://github.com/vacp2p/zerokit/pull/18 solves https://github.com/vacp2p/zerokit/issues/16 (and https://github.com/vacp2p/zerokit/issues/10), but public APIs need to be updated to reflect implemented fixes/changes.

Acceptance Criteria

• [ ] Update currently implemented public APIs to work with fixes/changes introduced by https://github.com/vacp2p/zerokit/pull/18.

Problem

As an example, it'd be useful to have something that works end to end.

Acceptance criteria

A lot of the code for Semaphore already exists. This should:

• Have basic protocol / public API that can be mimicked for other constructs
• Basic Rust tests
• FFI for important functionality
• (Outside of this repo) basic integration through e.g. nwaku

Problem

Currently FFI interface support is partial and not enough to support nwaku needs.

See https://github.com/vacp2p/zerokit/blob/master/rln/src/ffi.rs for current FFI.

Context

This issue supersedes https://github.com/vacp2p/zerokit/issues/2 and is slightly more specific.

Here's the current nwaku interface https://github.com/status-im/nim-waku/blob/master/waku/v2/protocol/waku_rln_relay/rln.nim

Current RLN library https://github.com/kilic/rln

Spec is here https://github.com/vacp2p/rfc/blob/26929735d2db9a97d9e7ca610502e0b7ad885780/content/docs/rfcs/32/README.md

Details

• [ ] Clarify differences between current Circom-based spec and Rust RLN library - this will inform what FFI interace should be supported - cc @staheri14 for issue here (TODO: add link to separate issue here)
• [ ] Ensure Rust library supports all relevant operations (TODO: add link to separate issue here)
• [ ] Update mul to RLN reference in ffi.rs
• [ ] Make sure get_root etc are on right LE form (some gotchas when it comes to conversion here)
• [ ] Add other FFI interfaces needed here

Once this gets further along, a parallel PR should be made to nwaku for integration testing.

List of current rough implementations:

• new_circuit (not with params)
• prove
• verify
• get_root

List of things not yet ported (note that the specifics here might change):

• get_secret
• new_circuit_from_params (similar to new)
• update_next_member
• delete_member
• signal to field
• keygen

Acceptance criteria

RLN FFI API is usable through nim-waku and has feature parity with existing implementation. The interface might be slightly different and should be according to RLN spec.

Problem

Generate a prof based on witness and wasm/zkey files. Witness consists of secret hash, merkle proof, epoch, signal and rln identifier.

From spec (https://github.com/vacp2p/rfc/blob/670816fa01f84fbde12a44f72f30e9b9458aaf5a/content/docs/rfcs/32/README.md):

For proof generation, the user need to submit the following fields to the circuit:

    {
      identity_secret: identity_secret_hash,
      path_elements: merkle_proof.path_elements,
      identity_path_index: merkle_proof.indices,
      x: signal_hash,
      external_nullifier: external_nullifier,
      rln_identifier: rln_identifier
    }

and

const witness = RLN.genWitness(secretHash, merkleProof, epoch, signal, rlnIdentifier)
...
const fullProof = await RLN.genProof(witness, wasmFilePath, finalZkeyPath)

This also requires setting up mocked signal, epoch and identifier.

See:

• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L94-L103
• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/src/rln.ts#L67-L83
• Related: https://github.com/worldcoin/semaphore-rs/blob/main/src/protocol.rs#L72
• <> (not best source)

Acceptance criteria

After adding user identity into merkle tree and creating required merkle proof, as well as signal, epoch etc, a proof should be generated.

Problem

When debugging circuits, it is very useful to see what constraints haven't been met and why.

Details

This should be possible with ConstraintLayer but I haven't managed to get to work properly:

In poseidon_tornado with

RUST_LOG="poseidon_tornado=TRACE,ark_relations=TRACE" cargo run

We get

Constraint trace requires enabling `ConstraintLayer`
thread 'main' panicked at 'assertion failed: {\n    use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};\n    let cs = ConstraintSystem::<E::Fr>::new_ref();\n    circom.clone().generate_constraints(cs.clone()).unwrap();\n    cs.is_satisfied().unwrap()\n}', /home/oskarth/repos/github.com/gakonst/ark-circom/src/circom/builder.rs:82:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The panic happens because constraints aren't met, which is expected. This then panics because of the debug_assert here https://github.com/gakonst/ark-circom/blob/master/src/circom/builder.rs#L82-L87

The problem is the lack of tracing, even with https://github.com/vacp2p/zerokit/commit/9b1fa85e46fc1d37f2f3e201ea6624940582925a

Tracing instrumentation based on example here https://github.com/arkworks-rs/r1cs-tutorial/blob/main/merkle-tree-example/src/constraints.rs#L109-L113

Same when trying to do tracing instrumentation in various ways directly in ark-circom etc.

Error from https://github.com/arkworks-rs/snark/blob/master/relations/src/r1cs/constraint_system.rs#L609

Probably missing something simple here but haven't been to figure out what's wrong.

Acceptance criteria

Failing constraints should produce some form of useful debugging information re which constraints are failing.