# Formal spec of circom-rln

## Utils

utils.circom is a set of templates/gadgets that the RLN circuit uses.

These are:

• MerkleTreeInclusionProof - Merkle tree inclusion check, used like set membership check;
• RangeCheck - used for range check.

Their description is given below.

### MerkleTreeInclusionProof

MerkleTreeInclusionProof(DEPTH) template used for verification of inclusion in full binary incremental merkle tree. The implementation is a fork of https://github.com/privacy-scaling-explorations/incrementalquintree, and changed to binary tree and refactored to Circom 2.1.0.

Parameters:

• DEPTH - depth of the Merkle Tree.

Inputs:

• $$leaf$$ - $$Poseidon(elem)$$, where $$elem$$ is the element that's checked for inclusion;
• $$pathIndex[DEPTH]$$ - array of length = $$DEPTH$$, consists of $$0 | 1$$, represents Merkle proof path. Basically, it says how to calculate Poseidon hash, e.g. for two inputs $$input1$$, $$input2$$, if the $$pathIndex[i] = 0$$ it shoud be calculated as $$Poseidon(input1, input2)$$, otherwise $$Poseidon(input2, input1)$$;
• $$pathElements[DEPTH]$$ - array of length = $$DEPTH$$, represents elements of the Merkle proof.

Outputs:

• $$root$$ - Root of the merkle tree.

Templates used:

### RangeCheck

RangeCheck(LIMIT_BIT_SIZE) template used for range check.

Parameters:

• $$LIMIT\_BIT\_SIZE$$ - maximum bit size of numbers that are used in range check, f.e. for the $$LIMIT\_BIT\_SIZE = 16$$, input numbers allowed to be in the interval $$[0, 65536)$$.

Inputs:

• $$messageId$$ - denotes counter value, that'll be described further;
• $$limit$$ - maximum value.

Templates used:

Logic/Constraints: Checked that $$0 \le messageId < limit$$.

## RLN

rln.circom is a template that's used for RLN protocol.

Parameters:

• $$DEPTH$$ - depth of a Merkle Tree. Described here;
• $$LIMIT\_BIT\_SIZE$$ - maximum bit size of numbers that are used in range check. Described here.

Private inputs:

• $$identitySecret$$ - randomly generated number in $$\mathbb{F_p}$$, used as a private key;
• $$userMessageLimit$$ - message limit of the user;
• $$messageId$$ - id of the message;
• $$pathElements[DEPTH]$$ - pathElements[DEPTH], described here;
• $$identityPathIndex[DEPTH]$$ - pathIndex[DEPTH], described here.

Public inputs:

• $$x$$ - $$Hash(signal)$$, where $$signal$$ is for example message, that was sent by user;
• $$externalNullifier$$ - $$Hash(epoch, rln_identifier)$$.

Outputs:

• $$y$$ - calculated first-degree linear polynomial $$(y = kx + b)$$;
• $$root$$ - root of the Merkle Tree;
• $$nullifier$$ - internal nullifier/pseudonym of the user in anonyomus environment.

Logic/Constraints:

1. Merkle tree membership check:
• $$identityCommitment = Poseidon(identitySecret)$$ calculation;
• $$rateCommitment = Poseidon(identityCommitment, userMessageLimit)$$ calculation;
• Merkle tree inclusion check for the $$rateCommitment$$.
2. Range check:
3. Polynomial share calculation:
• $$a_1 = Poseidon(identitySecret, externalNullifier, messageId)$$;
• $$y = identitySecret + a_1 * x$$.
4. Output of calculated $$root$$, $$y = share$$ and $$nullifier = Poseidon(a_1)$$ values.

### Withdrawal

withdraw.circom is a circuit that's used for the withdrawal/slashing and is needed to prevent frontrun while withdrawing the stake from the smart-contract/registry.

Private inputs:

• $$identitySecret$$ - randomly generated number in $$\mathbb{F_p}$$, used as private key.

Public inputs:

• $$address$$ - $$\mathbb{F_p}$$ scalar field element; denotes ETH address that'll receive stake.

Outputs:

• $$identityCommitment = Poseidon(identitySecret)$$.