Overview

We should aim to make our macros a lot more readable and sensible. Right now, it's a bit opaque if they are useful (although we use them) and new developers can't easily identify their purpose outside of reading tests.

Instead of macros, we should have a ProverSetup struct, like so:

pub struct MixerProverSetup<
	F: PrimeField,
	H: CRHTrait,
	HG: CRHGadget<H, F>,
	LHGT: CRHGadget<P::LeafH, F>,
	HGT: CRHGadget<P::H, F>,
	P: Config,
	const K: usize,
> {
	h3_params: H::Parameters,
	h5_params: H::Parameters,
	leaf_params: <P::LeafH as CRHTrait>::Parameters,
	inner_params: <P::H as CRHTrait>::Parameters,
};

impl MixerProverSetup {
	fn setup_arbitrary_data(...);
	fn setup_leaf(...);
	fn setup_tree_and_root_set(...);
	fn setup_circuit(...) -> (
		MixerCircuit,
		Vec<F> // Public inputs
	);
	fn setup_circuit_with_random_inputs(...);
	fn setup_circuit_with_raw_inputs(...);
	fn setup_proving_and_verifying_key(...);
	fn prove(...);
	fn verify(...); // For testing
}

Inside tests should be used like so:

let params3 = setup_hash_params();
let params5 = setup_hash_params();
let prover_setup = ProverSetup::new(params3, params5, ...);

let relayer = 1;
let recipient = 2;
let fee = 300;
let refund = 200;

let (circuit, public_inputs) = prover_setup.setup_circuit_with_raw_inputs(relayer, recipient, fee, refund);

let proof = prover_setup.prove(circuit);

let res = prover_setup.verify(public_inputs, proof); // Check if proof is valid

Checklist

• #80
• #99
• #92

Every Utxo potentially comes from a different chain, and since there is a different tree on every chain, different set of leaves need to be fetched and passed into our circuit setup. For each set of leaves, we should create a Merkle tree and derive a Merkle path for proving the existance of each commitment from the Utxo. These paths should evaluate to a root that exists in the SetGadget.

https://github.com/webb-tools/arkworks-gadgets/blob/b2fc1f4a6f9a194ba5a5080df96c8783ef45f9bf/arkworks-gadgets/src/merkle_tree/mod.rs#L373

this is feeding evaluate a length-0 array, then a leading 0 is added within evaluate, but then it goes to permute with length 1 and is not padded to have length 3

https://github.com/webb-tools/arkworks-gadgets/blob/master/arkworks-circuits/src/setup/mixer.rs#L294-L295

Instead, a leaf should be created outside this function and passed in.

TBA

// INS = number of input transactions
// OUTS = number of output transactions
// N = Tree height
// M = Size of the root set

// sum of input amounts + public amount == sum of output amounts
public_amount: F,

// Input transactions
in_amounts: [F; INS],
in_blindings: [F; INS],
in_chain_id: [F; INS],
in_nullifier_hashes: [F; INS],
in_private_keys: [F; INS],
in_paths: [Path<..., N>; INS],
in_indices: [F; INS],
in_root_set: [F; M],

// Output transactions 
out_amounts: [F; OUTS],
out_blindings: [F; OUTS],
out_chain_ids: [F; OUTS],
out_public_keys: [F; OUTS],
out_commitments: [F; OUTS],

// Arbitrary data to be added to the transcript
arbitrary_data: F,

// All the hashers used in this circuit
// Used for hashing private_key -- width 2
public_key_hasher: H::Native,
// Used for hashing nodes in the tree -- width 3
tree_hasher: H::Native,
// Used for creating leaf signature and the nullifier hash -- width 4
signature_hasher: H::Native,
// Used for creating leaf -- width 5
leaf_hasher: H::Native

The VAnchor consists of 3 parts:

1. Processing input transactions
2. Processing output transactions
3. Checking the equality of input/output transaction amounts

Processing input transactions

in_amounts - amount of tokens carried in each transaction
in_blindings - random secret values
in_chain_id - Chain Ids of the destination chains (input transactions are spent on a chain thats validating the proof)
in_nullifier_hashes - Nullifier hashes
in_private_keys - Private keys from the wallets where the transaction is make on (Ethereum wallet, Polkadot wallet, etc.)
in_paths - Merkle path for for each leafs membership
in_root_set - Merkle root set

Private inputs:
in_amounts, in_blindings, in_private_keys, in_paths,
Public inputs:
in_chain_id, in_nullifier_hashes, in_root_set

Higher level description of how input transactions:

// Sum of input amounts
let sum = F::one();

for i in 0..INS {
    // Computing the public key, which is done, just by hashing the private key
    let calc_public_key = public_key_hasher.hash(&[in_private_keys[i]]);

    // Computing the leaf
    let calc_leaf = leaf_hasher.hash(&[in_chain_ids[i], in_amounts[i], calc_public_key, in_blindings[i]]);

    // Computing the signature
    let calc_signature = signature_hasher.hash(&[in_private_keys[i], calc_leaf, in_indices[i]]);
    
    // Computing the nullifier hash
    let calc_nullifier_hash = leaf_hasher.hash(&[calc_leaf, in_indices[i], calc_signature]);

    // Checking if the passed nullifier hash is the same as the calculated one
    assert_equal(in_nullifier_hashes[i], calc_nullifier_hash);
    
    // Calculate the root hash
    let calc_root_hash = in_path[i].calculate_root_hash(leaf);

    // Check if calculated root hash is in the set
    let is_member = set_gadget.check_membership_enabled(calc_root_hash, in_amounts[i]);
    assert_equal(is_member, one());
    
    // Finally add the amount to the sum
    sum += in_amounts[i];
}
// return the sum to be used for further constraints
return sum;

To prevent double-spending of the same transaction, we should check if there are duplicate nullifiers.

for i in 0..INS {
    for j in (i + 1)..INS {
        assert_not_equal(in_nullifier_hashes[i], in_nullifier_hashes[j])
    }
}

This is potentially unnecessary step, since this can be checked from the pallet.

Processing output transactions

out_amounts - amount of tokens carried in this transaction
out_blindings - random secret values
out_chain_ids - Chain Ids of the destination chains (Chains where the transactions will be spent)
out_public_keys - Public keys
out_commitments - Output leafs commitments that will be inserted into the tree

Private inputs:
out_amounts, out_blindings, out_chain_ids, out_public_keys, out_commitments
Public inputs:
out_commitments

Higher level description of how the output transactions are processed

// Sum of all amounts
let sum = F::one();

for i in 0..OUTS {
    // Calculate the leaf commitment
    let calc_leaf = leaf_hasher.hash(&[out_chain_ids[i], out_amounts[i], out_public_keys[i], out_blindings[i]]);
    
    // Check if calculated leaf is the same as the passed one
    assert_equal(calc_leaf, out_commitments[i]);
    
    // Each amount should not be greater than the limit constant
    assert_less_than(out_amounts[i], limit);
    
    // Add in to the sum
    sum += out_amounts[i];
}

// Return the sum to make further constraints
return sum;

The limit is a variable constrained to a constant: 452312848583266388373324160190187140051835877600158453279131187530910662656.

Checking the equality of input/output amounts

The check is performed by simply:

assert_equal(in_sum + public_amount, out_sum);

NOTE: The terms input and output transactions are used loosely. These terms should not be used to understand the flow of transactions in VAnchor.

1. Structure

We should have a workspace with the following structure:

• arkworks-benchmarks
• arkworks-circom-verifier
• arkworks-r1cs-circuits - which contains only the r1cs constraints version of our circuits + gadgets
• arkworks-setups - contains the higher level APIs for both R1CS and PLONK circuits
• arkworks-native-circuits - which contains only the native version of our gadgets
• arkworks-plonk-circuits
• arkworks-utils

2. Tools

Use cargo-workspaces for workspace publishing.

3. Dependency graph

1. arkworks-gadgets should not have dependency of arkworks-utils, except for testing.
2. Move PoseidonParameters, Sbox, PoseidonError (https://github.com/webb-tools/arkworks-gadgets/blob/master/arkworks-utils/src/poseidon/mod.rs) into the arkworks-native-circuits/poseidon directory.
   • Types related to the native version goes to arkworks-native-circuits.
   • r1cs constraints version for sbox goes to arkworks-r1cs-circuits, etc.
3. Modify utility functions for Poseidon to not return PoseidonParameters struct, but instead return tuple:

(Vec<F>, Vec<Vec<F>>, u8, u8, u8, PoseidonSbox)

4. Move setup_params...(https://github.com/webb-tools/arkworks-gadgets/blob/master/arkworks-utils/src/utils/common.rs#L23) functions inside the native version of poseidon.

5. Elliptic curves should only be imported for testing, for all crates.

Mixer circuit should have inputs:

secret: F,
nullifier: F,
nullifier_hash: F,
path: Path<..>,
root: F,
arbitrary_data: F,
// In mixer case, these two are the same, so we should just pass one hasher
tree_hasher: H::Native,
leaf_hasher: H::Native

The secret is a random number that will be kept secret and will not be revealed. The nullifier is also generated randomly, but it is revealed during the verification to prevent double spending.

To prevent front-run attacks (https://ethresear.ch/t/anonymous-reputation-risking-and-burning/3926 <-- see comments), hash of the nullifier is introduced. nullifier_hash is also an (public) input to the circuit, and we will check if nullifier_hash == hash(nullifier). After the proof is verified, nullifier_hash is stored inside chain storage.

path is the merkle path. It's a private input, which means all the nodes are hidden. We will use it to calculate root, and then check if it's equal to the passed root (path.calculate_root() == root) which is a public input. This root is a public input, and it will be fetched from on-chain storage, and passed into the circuit.

Arbitrary data - arbitrary constrains that will be included in the proof. // To be discussed

Out of these, private inputs are:
secret, nullifier, path
Public inputs are:
nullifier_hash, root, arbitrary_data

Higher-level description of how the Mixer circuit works:

// Making the leaf from secret and nullifier
let leaf = leaf_hasher_gadget.hash_two(secret, nullifier);
// Making the nullifier hash from nullifier
let calc_nullifier_hash = leaf_hasher_gadget.hash_two(nullifier, nullifier); // or leaf_hasher.hash(&[nullifier]) needs to be discussed

// Making sure that passed nullifier hash is the same as calculated one
composer.assert_equal(nullifier_hash, calc_nullifier_hash);

// Calculating the root using the provided path
let calc_root = path_gadget.calculate_root(leaf, &tree_hasher_gadget);

// Making sure that calculated root matches the passed one
composer.assert_equal(root, calc_root);

// Constraining arbitrary data
let _ = arbitrary_data * arbitrary_data; // to be discussed

NOTE: tree_hasher and leaf_hasher are the same in case of a mixer circuit, so we should pass one hasher

Checklist:

• Implement PLONK version of mixer circuit
• Add tests for PLONK Mixer circuit

VAnchor is using the old SetMembershipGadget that requires computing the diffs outside the circuit and passing them in. This means that you need to know the root beforehand, which is not an ideal way of making proofs. The root will be calculated inside the circuit, based on provided leaf pre-image and Merkle path, so the diffs will also be calculated inside the circuit.

Overview

Implement a ProverSetup modeled from: https://github.com/webb-tools/protocol-substrate/blob/filip/vanchor-pallet/pallets/vanchor/src/test_utils.rs.

Mockup:

pub struct VAnchorProverSetup<
	F: PrimeField,
	H: CRHTrait,
	HG: CRHGadget<H, F>,
	LHGT: CRHGadget<P::LeafH, F>,
	HGT: CRHGadget<P::H, F>,
	P: Config,
	const K: usize,
	const M: usize,
	const INS: usize,
	const OUTS: usize
> {
	h2_params: H::Parameters,
	h3_params: H::Parameters,
	h5_params: H::Parameters,
	leaf_params: <P::LeafH as CRHTrait>::Parameters,
	inner_params: <P::H as CRHTrait>::Parameters,
};

impl VAnchorProverSetup {
	fn setup_arbitrary_data(...);
	fn setup_leaves(...) -> (
		Vec<F>, // leaves
		Vec<F>, // nullifiers
		Vec<LeafPrivateInput<F>>, // leaf private inputs
		Vec<LeafPublicInput<F>>, // leaf public inputs
	);
	fn setup_tree_and_root_set(...) -> (
		Vec<Path<SparseMerkleTree<F>, TREE_DEPTH>>, // path
		Vec<F>, // indices
		[F; M], // root set
		Vec<SetPrivateInputs<F, M>>, // root set private inputs
	);
	fn setup_circuit(...) -> (
		VAnchorCircuit,
		Vec<F> // Public inputs
	);
	fn setup_circuit_with_random_inputs(...);
	fn setup_circuit_with_raw_inputs(...);
	fn setup_proving_and_verifying_key(...);
	fn prove(...);
	fn verify(...); // For testing
}

Checklist

• Setup arbitrary data
• Setup leaves function
• Setup circuit functions
• Setup Tree and root set
• Setup circuit with random inputs
• Setup circuit with raw inputs
• Setup proving and verifying key
• Prove function
• Verify function
• Update tests to use new prover setup
  • should_create_circuit_and_prove_groth16_2_input_2_output
  • should_fail_with_invalid_root
  • should_fail_with_invalid_set
  • should_fail_with_invalid_nullifier
  • should_fail_with_same_nullifier
  • should_fail_with_inconsistent_input_output_values
  • should_fail_with_big_amount
  • should_fail_with_invalid_public_input
  • should_create_circuit_and_prove_groth16_2_input_2_output
  • should_create_circuit_and_prove_groth16_16_input_2_output

Issues

Linked tasks

In our get_index method (here) for computing the index of a leaf in a Merkle tree we have some redundancy.  The method starts with by calling check_membership to generate a proof that the leaf does indeed belong to a tree with the given root_hash.  The way check_membership works is to start at the leaf-level of a path and work its way up to the root, computing the hash of the siblings at each level and checking that this matches one of the siblings at the level above.  It adds all these computations to the constraint system.

All this work is then repeated by get_index as it hashes up the path to properly determine the index of leaf.  So a lot of this hashing is proven twice.  

One way to eliminate it would be to simply eliminate the membership check at the beginning and then add a few lines at the end to confirm that the siblings at the final level of this path do indeed hash to root_hash.  In fact these siblings are already being hashed together in the final step of the for-loop (further redundancy, since the result previous_hash is never used after exiting the for loop), so all we need to do is add 

let isonpath = previous_hash.is_eq(root);
isonpath.unwrap().enforce_equal(&Boolean::TRUE)?;

after the for loop, prior to return.

All this applies as well for the plonk version with appropriate modifications.

Add proper scripts for compiling without standard library.

Crates to include: arkworks-circuits, arkworks-gadgets, arkworks-utils, arkworks-plonk-circuits

Overview

A trusted setup ceremony is a multi-party computation conducted in order to generate initial randomized parameters for generating circuit-specific (in our case) proving and verifying keys.

The trusted setup consists of two phases:

Phase 1 (Powers of Tau)

1. A coordinator generates an accumulator
2. Participant downloads the latest accumulator
3. Participant contributes their randomness to the accumulator (randomness is permanently deleted after this step)
4. Participant uploads the accumulator back to the coordinator
5. The coordinator verifies the accumulator was transformed correctly and produces a new challenge

The notable part about this procedure is that it _never_has to end. This is what allows SNARKs utilizing KZG10 to have a "continuous" setup. If a participant does not trust the setup, they themselves can contribute to the Powers of Tau, and instantiate KZG10 with the new parameters.

Phase 2 (Specialization specific to Groth16)

1. Coordinator "prepares" the parameters from Phase 1 and converts them to Lagrange Coefficients
2. Participant downloads the latest state of the parameters
3. Participant contributes their randomness to the parameters (randomness is permanently deleted after this step)
4. Participant uploads the parameters back to the coordinator
5. The coordinator verifies the accumulator was transformed correctly
6. Loop from 2 for all participants

This produces parameters that can then be used for constructing Groth16 SNARKs for that circuit. The setup is sound as long as 1 party was honest and destroyed their "toxic waste" in step 3.

Tornado.cash info

Phase 1 can be done once and reused for different types of circuits. Tornado.cash used this one for their ceremony: https://github.com/weijiekoh/perpetualpowersoftau/tree/master/0071_edward_response

Tornado.cash used this repo for phase2: https://github.com/kobigurk/phase2-bn254

Phase1 reusability:

Ideally, we want to reuse phase1 values from https://celo.org/plumo or take them from snarkjs repo: https://github.com/iden3/snarkjs#7-prepare-phase-2

Phase2 resources:

Use https://github.com/iden3/snarkjs, it should support both Bn254 and Bls12-381

In case of snarkjs not working for us we will use https://github.com/celo-org/snark-setup and update underlying dependencies to use the arkworks backend.

Use scripts to generate phase2 params: https://github.com/celo-org/snark-setup/tree/master/phase2-cli/scripts

Global tasks

• Identify open-source tools for running the multi-party ceremory
  • Find coordinator software
  • Find way of contributing in browser (is it possible with Arkworks?)
• Create a repo for running the ceremony:
• Add scripts for creating a random value
• Create guidelines for participating in the ceremony (it can be done through PRs, with specific template - contributions should be done synchronously)
• Publish powers of tau values to be used for phase 2 for bn254 from snarkjs

Arkworks:

• Clone https://github.com/AleoHQ/aleo-setup/[https://github.com/celo-org/snark-setup](https://github.com/celo-org/snark-setup) and port it to arkworks
• Update scripts for making random values

Circom Ceremony Checklist

• Contribute a random value using snarkjs and make a PR
• After contributions are submitted, it is verified by at least x people before the merge
• After everyone has submitted their contribution, apply random beacon with snarkjs to finalize phase 2, open a PR
• Verify the final key, by at least x people, before the merge
• Execute this internally first. Integrate publicly second.

Arkworks Ceremony Checklist

• Identify how to run a coordinator server.
• Contribute a random value using arkworks-setup and make a PR
  • Get our circuits working using https://github.com/AleoHQ/aleo-setup
• After contributions are submitted, it is verified by at least x people before the merge
• After everyone has submitted their contribution, apply random beacon with arkworks-setup to finalize phase 2, open a PR
• Verify the final key, by at least x people, before the merge
• Execute this internally first. Integrate publicly second.

Tools

• https://github.com/appliedzkp/multisetups
• https://github.com/tornadocash/trusted-setup-server
• https://setup.aleo.org/outer-setup

Links that Wei suggested to check out:

https://github.com/pantherprotocol/preZKPceremony

https://medium.com/privacy-scaling-explorations/zkopru-trusted-setup-ceremony-f2824bfebb0f

• https://github.com/appliedzkp/zkey-manager
• Browser based clients: https://github.com/glamperd/setup-mpc-ui

We can use snarkjs or zkey-manager to produce the initial zkey file. Then we can use https://github.com/appliedzkp/multisetups for CLI implementation. It uses IPFS for file sharing. The coordinator needs to manage the order of the contributors and providing the IPFS address of the latest zkey file to the current contributor.

The repo https://github.com/glamperd/setup-mpc-ui contains a browser-based solution. It uses Firebase databases to manage the contributed files. We first need to make an account on Firebase and set up a database. Participants authenticate via GitHub OAuth. Once authenticated, a participant gains access to the Firestore database,

Right now we have macros in mixer_circuit tests, in bench.rs and we have a separate file for common mixer setup. Merge these into one and use It

Path:

// Path
#[derive(Clone)]
pub struct Path<F: PrimeField, H: FieldHasher, const N: usize> {
    pub(crate) path: [F; N],
}

impl<F: PrimeField, H: FieldHasher, const N: usize> Path<F, H, N> {
    pub fn check_membership(
      &self,
      root_hash: &F,
      leaf: &F,
      hasher: &H,
    ) -> Result<bool, Error>;
    
    pub fn calculate_root(&self, leaf: &F, hasher: &H) -> Result<F, Error>;
}

Merkle tree:

/// Merkle sparse tree
pub struct SparseMerkleTree<F: PrimeField, H: FieldHasher, const D: [u8; 32], const N: usize> {
    /// data of the tree
    pub tree: BTreeMap<u64, F>,
    empty_hashes: [F: N],
}

impl<F: PrimeField, H: FieldHasher> SparseMerkleTree<F, H> {

    pub fn insert_batch(
        &mut self,
        leaves: &BTreeMap<u32, F>,
        hasher: &H,
    ) -> Result<(), Error>;
    
    pub fn new(
        leaves: &BTreeMap<u32, F>,
        hasher: &H,
    ) -> Result<Self, Error>;
    
    pub fn new_sequential(
        leaves: &[F],
        hasher: &H,
    ) -> Result<Self, Error>;
    
    pub fn root(&self) -> F;
    
    pub fn generate_membership_proof(&self, index: u64) -> Path<F, H, N>;
}

Calculating empty hash:

pub fn gen_empty_hashes<F: PrimeField, H: FieldHasher, const N: usize>(
    hasher: &H
    empty_bytes: [u8; 32]
) -> Result<[F; N], Error> {
    let mut empty_hashes = [F::zero(); N];

    let mut empty_hash = F::from_le_mod_order(&empty_bytes);
    empty_hashes.push(empty_hash.clone());

    for i in 1..=N {
        empty_hash = hasher.hash_two(&empty_hash, &empty_hash)?;
        empty_hashes[i] = empty_hash.clone();
    }
    
    Ok(empty_hashes)
}

Overview

Due to the overwhelming complexity of traits defined in arkworks-gadgets, I'm proposing to massively simplify traits for the Merkle tree and hash function, in the following way:

CRH:

struct Poseidon<F: PrimeField> {
   params: PoseidonParameters<F>,
}

impl Poseidon<F: PrimeField> {
    fn new(params: PoseidonParameters<F>) -> Self;
}

trait FieldHasher<F: PrimeField> {
	fn hash(&self, inputs: &Vec<F>) -> F;
        fn hash_two(&self, left: &F, right: &F) -> F;
}

Path:

// Path
#[derive(Clone)]
pub struct Path<F: PrimeField, H: FieldHasher> {
	pub(crate) path: Vec<F>,
}

impl<F: PrimeField, H: FieldHasher> Path<F, H> {
	pub fn check_membership(
		&self,
		root_hash: &F,
		leaf: &F,
		hasher: &H,
	) -> Result<bool, Error>;

	pub fn calculate_root(&self, leaf: &F, hasher: &H) -> Result<F, Error>;
}

Merkle tree:

/// Merkle sparse tree
pub struct SparseMerkleTree<F: PrimeField, H: FieldHasher> {
	/// data of the tree
	pub tree: BTreeMap<u64, F>,
	empty_hashes: Vec<F>,
	height: u8,
  _hasher: PhantomData<H>
}

impl<F: PrimeField, H: FieldHasher> SparseMerkleTree<F, H> {

	pub fn insert_batch(
		&mut self,
		leaves: &BTreeMap<u32, F>,
		hasher: &H,
	) -> Result<(), Error>;

	pub fn new(
		leaves: &BTreeMap<u32, F>,
		hasher: &H,
	) -> Result<Self, Error>;

	pub fn new_sequential(
		leaves: &[F],
		hasher: &H,
	) -> Result<Self, Error>;

	pub fn root(&self) -> F;

	pub fn generate_membership_proof(&self, index: u64) -> Path<F>;
}

Checklist

• #106
• #75
• #91
• #93

Issues

Linked tasks

Previously we had a set membership set up in such a way that diffs are calculated outside the circuit and then passed in. To calculate the diffs, you would have to pass a target root that you are checking against. This root has to be calculated inside the circuit from the provided path.

New design proposal:

struct SetGadget<F: PrimeField, const M: usize> {
    roots: [FpVar<F>; M]
}

impl<F: PrimeField, const M: usize> SetGadget<F, M> {
    pub fn check_membership(
        target: &FpVar<F>,
    ) -> Result<Boolean<F>, SynthesisError> {
        // Calculating the diffs inside the circuit
        let mut diffs = Vec::new();
        for root in self.roots {
            diffs.push(root - target);
        }

        // Checking the membership
        let mut product = target.clone();
        for (diff, real) in diffs.iter().zip(self.roots.iter()) {
            real.enforce_equal(&(diff + &target))?;
            product *= diff;
        }
        
        product.is_eq(&FpVar::<F>::zero())
    }
}

Instead of creating a circuit for each test case for our PLONK gadgets, we should use the following function: https://github.com/ZK-Garage/plonk/blob/master/plonk-core/src/constraint_system/composer.rs#L541

The benefits:

• We could debug in more detail which gate is not satisfying the constraints
• More performant tests -- we dont need to go trough prove/verify process
• Smaller code footprint

NOTE: This should only be done for out gadgets: PoseidonGadget, PathGadget, SetGadget

The way that Poseidon hash parameters are currently added to a hash gadget using add_input, which treats them as secret inputs rather than public constants.  Thus a verifier cannot be certain that the prover used the correct constants to compute their hash.  This qualifies as a bug b/c a prover could choose trivial parameters (like MDS matrix = identity, all round constants = 0) and more easily find hash preimages.

I believe the best way to fix this is to use add_witness_to_circuit_description because this method of creating variables makes the variable's underlying value visible to the verifier.  Thus the verifier can be certain that the correct poseidon parameters were used in generating the hash proof.  I would like confirmation from plonk experts at ZK garage before fixing this.

Right now the PLONK Set gadget is implemented as a circuit. In order to make it composable, we should aim to turn it into as gadget, meaning it can accept parameters other than StandardComposer, and it should return values that can be constrained further.

#[derive(Debug, Default)]
struct SetGadget<F: PrimeField> {
    pub set: Vec<F>,
}

impl<F: PrimeField, P: TEModelParameters<BaseField = F>> SetGadget {
    fn new(set: Vec<F>) -> Self {
        Self { set }
    }
    fn check_membership(&self, composer: &mut StandardComposer<F, P>, target: &Variable) -> Result<Variable, Error> {
        let mut diffs = Vec::new();
        for x in self.set {
            let diff = x - target;
            diffs.push(diff);
        }
        
        let sum = composer.add_input(F::one());
        for diff in diffs {
            sum *= diff;
        }
        
        let is_zero = composer.is_eq_with_output(sum, composer.zero_var());
        
        Ok(is_zero)
    }
}

Overview

We want to extend our suite of protococl implementations to one using PLONK as the zkSNARK backend. This requires rewriting our gadgets in the language of PLONK gates, using the external library developed against arkworks:

• https://github.com/rust-zkp/ark-plonk

We will continue to build out our toolchain in our repo below in a plonk folder.

• https://github.com/webb-tools/arkworks-gadgets

General Protocol sketches

For each of these circuits, we apply roughly the same set of constraints. We have an object called notes or UTXOs that we use to represent private transaction data. We require a prover to prove that they possess a note or a UTXO in order to satisfy the circuit. The proof of knowledge of the note or the UTXO amounts to proving knowledge of the preimage of the hash of the note or UTXO.

Then, we must prove that this note or UTXO commitment is inside a set of merkle tree roots. This is done by providing a merkle tree proof path, constructing a root, and then providing a set of difference values (needed for the next step) in order to prove that an element, the root, is inside a set of roots.

We have all these gadgets and components implemented in a few places, so there should be enough resources to begin to understand this further.

VAnchor Circuit

The VAnchor circuit is a UTXO based zk-circuit. It verifies that a public input, a set of UTXOs, and a set of output UTXO commitments are properly formatted and ensures the values of inputs match the values of outputs. We then verify that each input is in one of many merkle trees.

The reference implementations for these circuits currently can be found here:

• https://github.com/webb-tools/protocol-solidity/blob/main/circuits/vanchor/transaction.circom
• https://github.com/webb-tools/arkworks-gadgets/blob/master/src/circuit/vanchor.rs

Anchor Circuit

The Anchor circuit is a fixed sized transaction system, meaning it only supports a specific fixed value deposit. This means that notes on this system don't contain asset values. This circuit only verifies that a deposit is formatted correctly and that it exists in one of many merkle trees.

The reference implementations for these circuits currently can be found here:

• https://github.com/webb-tools/protocol-solidity/blob/main/circuits/anchor/withdraw.circom
• https://github.com/webb-tools/arkworks-gadgets/blob/master/src/circuit/bridge.rs

Notes

• Start specific before generalising.
• Poseidon circuit: https://github.com/webb-tools/arkworks-gadgets/blob/master/src/circuit/poseidon.rs
  • map generate_constraints to gadget
• Implement a Poseidon gadget

Checklist

• #93
• #75
• #120
• #76
• #121
• #86
• #85
• #87
• #171
• #172
• #173
• #90

Auxiliary resources

Poseidon implementations

• https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom
• https://github.com/webb-tools/arkworks-gadgets/blob/master/src/poseidon/circom/constraints.rs
• https://github.com/webb-tools/arkworks-gadgets/blob/master/src/poseidon/circom/mod.rs

Questions / Issues

Though, I have updated the chain identifier structure in resource IDs to consist of 6 bytes of data so we may want to consider adopting a more complex scheme here for the future. Namely, we currently are reserving 4 bytes for the chain ID (u32) and 2 bytes for the chain type (u16).

For example, since the chain ID is taken to be a public input. We could hash the (chain_id_type, chain_id) % u32::max() or FIELD_SIZE and use this as the value meant to be committed to inside deposit notes.

The goal with the chain ID type is to add separation between different chains with the same IDs such as parachains with ID 7 and EVM with ID 7 and Cosmos with ID 7.

pub struct PoseidonParametersVar {
    /// The round key constants
    pub round_keys: Vec<Variable>,
    /// The MDS matrix to apply in the mix layer.
    pub mds_matrix: Vec<Vec<Variable>>,
    /// Number of full SBox rounds
    pub full_rounds: u8,
    /// Number of partial rounds
    pub partial_rounds: u8,
    /// The size of the permutation, in field elements.
    pub width: u8,
    /// The S-box to apply in the sub words layer.
    pub sbox: PoseidonSbox,
}

#[derive(Debug, Default)]
struct PoseidonGadget {
    pub params: PoseidonParametersVar,
}

trait FieldHasherGadget<E: PairingEngine, P: TEModelParameters<BaseField = E::Fr>> {
    type Native: Debug + Clone;
    // For easy conversion from native version
    fn from_native(composer: &mut StandardComposer<E, P>, native: Self::Native) -> Self;
    fn hash(&self, composer: &mut StandardComposer<E, P>, inputs: &[Variable]) -> Result<Variable, Error>;
    fn hash_two(&self, composer: &mut StandardComposer<E, P>, left: &Variable, right: &Variable) -> Result<Variable, Error>;
}

impl<E: PairingEngine, P: TEModelParameters<BaseField = E::Fr>> FieldHasherGadget<E, P> for PoseidonGadget {
    type Native: Poseidon<E::Fr>;
    ...
}

Usage inside circuit:

struct SomeCircuit<E: PairingEngine, P: TEModelParameters<BaseField = E::Fr>, HG: FieldHasherGadget<E, P>> {
  hasher: HG::Native,
}

impl<E: PairingEngine, P: TEModelParameters<BaseField = E::Fr>, HG: FieldHasherGadget<E, P>> Circuit<E, P>
	for SomeCircuit<E, P, HG>
{
    const CIRCUIT_ID: [u8; 32] = [0xff; 32];

    fn gadget(&self, composer: &mut StandardComposer<E, P>) -> Result<(), Error> {
        let hasher_gadget = HG::from_native(composer, self.hasher);
        ....
    }
}

The basic equation goes like this:

let b = 1 - x * x_inverse;
assert(b * x, 0);

Where:
x is the number we want to check.
x_inverse is the inverse of x (meaning x * x_inverse == 1).
b is the boolean value indicating if x is 0.

Here is the gadget example:

#[derive(Debug, Default)]
struct IsZero<E: PairingEngine> {
	pub x: E::Fr,
	pub x_inv: E::Fr,
}

impl<E: PairingEngine, P: TEModelParameters<BaseField = E::Fr>> Circuit<E, P> for IsZero<E> {
	const CIRCUIT_ID: [u8; 32] = [0xff; 32];

	fn gadget(&mut self, composer: &mut StandardComposer<E, P>) -> Result<(), Error> {
		let x_var = composer.add_input(self.x);
		let x_inv_var = composer.add_input(self.x_inv);
		let one = composer.add_input(E::Fr::one());

		// x * x_inverse
		// -- should be 1 if x != 0
		// -- should be 0 if x == 0
		let res =
			composer.arithmetic_gate(|gate| gate.witness(x_var, x_inv_var, None).mul(E::Fr::one()));

		// b = 1 - x * x_inverse
		// will be 0 if x != 0
		// will be 1 if x == 0
		let b = composer.arithmetic_gate(|gate| {
			gate.witness(one, res, None)
				.add(E::Fr::one(), -E::Fr::one())
		});

		// ensures that x_inv is actually the inverse of x
		let b_check =
			composer.arithmetic_gate(|gate| gate.witness(x_var, b, None).mul(E::Fr::one()));
		composer.assert_equal(b_check, composer.zero_var());

		// If x is 0, b should be 1
		// If x is 1, b should be zero
		composer.assert_equal(b, one);

		Ok(())
	}

	fn padded_circuit_size(&self) -> usize {
		1 << 11
	}
}

The full code can be found here: https://github.com/webb-tools/arkworks-gadgets/blob/filip/iz-zero-gadget/arkworks-plonk-circuits/src/utils.rs

Instead of macros, we should have a ProverSetup struct, like so:

pub struct MixerProverSetup<
	F: PrimeField,
	H: CRHTrait,
	HG: CRHGadget<H, F>,
	LHGT: CRHGadget<P::LeafH, F>,
	HGT: CRHGadget<P::H, F>,
	P: Config,
	const K: usize,
> {
	h3_params: H::Parameters,
	h5_params: H::Parameters,
	leaf_params: <P::LeafH as CRHTrait>::Parameters,
	inner_params: <P::H as CRHTrait>::Parameters,
};

impl MixerProverSetup {
	fn setup_arbitrary_data(...);
	fn setup_leaf(...);
	fn setup_tree_and_root_set(...);
	fn setup_circuit(...) -> (
		MixerCircuit,
		Vec<F> // Public inputs
	);
	fn setup_circuit_with_random_inputs(...);
	fn setup_circuit_with_raw_inputs(...);
	fn setup_proving_and_verifying_key(...);
	fn prove(...);
	fn verify(...); // For testing
}

Inside tests should be used like so:

let params3 = setup_hash_params();
let params5 = setup_hash_params();
let prover_setup = ProverSetup::new(params3, params5, ...);

let relayer = 1;
let recipient = 2;
let fee = 300;
let refund = 200;

let (circuit, public_inputs) = prover_setup.setup_circuit_with_raw_inputs(relayer, recipient, fee, refund);

let proof = prover_setup.prove(circuit);

let res = prover_setup.verify(public_inputs, proof); // Check if proof is valid

Add a constructor to Utxo:

Utxo::new(chain_id, amount, private_key, blinding);

Add leaf creation functions:

setup_vanchor_leaf_x5_5(Curve, chain_id, amount, rng);
setup_vanchor_leaf_with_privates_x5_5(Curve, chain_id, amount, blinding, rng);

Add proof creation function:

setup_proof_x5_5(
    public_amount,
    recipient,
    relayer,
    ext_amount,
    fee,
    leaves,
    in_indices,
    in_utxos,
    out_utxos
)

• Fix broken links
• Update description about our setup
• Update examples

Task from the discussion in: #28

Things done so far:

• Merkle Tree + Gadget
• Poseidon + Gadget
• Leaf + Gadget
  • Mixer
  • Anchor
  • VAnchor
• Set Gadget
• Arbitrary Data gadget
  • Mixer
  • Anchor
  • VAnchor
• Circuits
  • Mixer
  • Anchor
• API
  • Mixer
  • Anchor

Things left to do:

arkworks-gadgets

• Circuits
  • #138
• API
  • #119
  • #139
  • #160
  • #171
  • #172
  • #173
• #146

webb.js

• #145
• [TASK] Design the UTXO structure for VAnchor transactions in wasm-utils.
• [TASK] Expose VAnchor generate proof on API (proof/vanchor.rs).
• [TASK] Expose VAnchor UTXO generation on API (note/vanchor.rs).
• [TASK] Test parsing & generating VAnchor notes.
• [TASK] Test generating & verifying VAnchor proofs.

protocol-substrate

• [TASK] Introduce code coverage tool and add to CI.
• [TASK] Use updated VAnchor inside the pallets.
• [TASK] Ensure code coverage of tests cover all pallet errors.
• [TASK] Integrate the VAnchor + XAnchor and write a cross-chain success test.

relayer

• [SPEC] VAnchor relay transaction API.
• [TASK] Integrate relaying for VAnchor.
• [TASK] Test the Anchor proof generation in Typescript.
• [TASK] Test the VAnchor proof generation in Typescript.

Mixer leaf should use parameters of width 3
Anchor leaf should use parameters of width 4
VAnchor leaf should use parameters of width 5

Anchor circuit should have inputs:

secret: F,
nullifier: F,
chain_id: F,
nullifier_hash: F,
path: Path<..>,
roots: S::Native,
arbitrary_data: F,
tree_hasher: H::Native,
leaf_hasher: H::Native

The secret and the nullifier serve the same function as in Mixer circuit (see #121 ).

path is the Merkle path. It's a private input, which means all the nodes are hidden. We will use it to calculate root, and then check if it exists inside the root set (roots) that was passed as a public input.

Arbitrary data - arbitrary constrains that will be included in the proof.

Out of these, private inputs are:
secret, nullifier, path
Public inputs are:
nullifier_hash, chain_id, roots, arbitrary_data

Higher-level description of how the Anchor circuit works:

// Making the leaf from secret and nullifier and chain_id
let leaf = leaf_hasher_gadget.hash(&[secret, nullifier, chain_id]);
// Making the nullifier hash from nullifier
let calc_nullifier_hash = leaf_hasher_gadget.hash_two(nullifier, nullifier);

// Making sure that passed nullifier hash is the same as calculated one
composer.assert_equal(nullifier_hash, calc_nullifier_hash);

// Calculating the root using the provided path
let calc_root = path_gadget.calculate_root(leaf, &tree_hasher_gadget);

// Making sure that calculated root is inside the set
let is_member = set_gadget.check_membership(&calc_root);

let one_var = composer.add_constant(F::one());
composer.assert_equal(is_member, one_var);

// Constraining arbitrary data
let _ = arbitrary_data * arbitrary_data; // to be discussed

Overview

We ought to add encryption of UTXOs to make it possible to store these encrypted UTXOs on-chain.

Tools

Using

• https://github.com/RustCrypto/nacl-compat

Referencing:

• https://github.com/webb-tools/arkworks-gadgets/blob/master/arkworks-circuits/src/setup/vanchor.rs#L193 (need to encrypt on setup)
• https://github.com/MetaMask/eth-sig-util/blob/main/src/encryption.ts
• https://github.com/tornadocash/tornado-nova/blob/master/src/utxo.js#L60

Usage

In order to improve the UX and enable users to not need to custody UTXO notes locally across all of their devices, we can store the encrypted UTXO data on-chain and emit this in an indexable event. This way, when a user wants to spend a note, as long as they possess the master key they'll be able to query the latest events containing their encrypted UTXOs. Decrypting these UTXOs exposes all the secret data necessary for generating proofs.

Hash empty of merkle tree defaults to zero element. In the Solidity side, the default empty element is not zero, but rather than keccak256("tornado") or something similar. We should allow this element to be configurable in Rust as well.

https://github.com/webb-tools/arkworks-gadgets/blob/master/arkworks-gadgets/src/merkle_tree/mod.rs#L373