RLN

Membership

Each member has a secret key that is denoted by a_0. And identity commitment q is the hash of the secret key

q  = h(a_0)

To become a member one must,

• Deposit certain amount of eth to the membership contract.
• Place herself in a empty leaf of the membership merkle tree.

Signalling

Members are cryptoeconomically bounded to send only one signal in an epoch. Proof system enforces members to reveal their secret key a_0 when they go beyond that limit.

Membership

For a valid signal identity commitment q must be exists in identity tree. Membership is proven by providing a authenticity path auth_path.

Linear Equation & SSS

Secret key a_0 which is first coefficient of a linear polynomial.

Each member knows a linear polynomial for any epoch which is derived from secret key a_0 and the epoch. So, each epoch there is a polynomial with different a_1 equation but with same a_0.

A(x) = (a_0, a_1)
a_1 = h(a_0, epoch)

Each member has a secret line equation for an epoch

y = a_0 + x a_1

Along with a signal members should publicly provide a (x, y) share such that satisfies the line equation.

With more that one share anyone can derive a_0 the secret id key. Hash of a signal will be evaluation point x. So that a member who sends more that one signal reveails the secret key.

Note that shares used in different epoches cannot be used to derive the secret key.

Nullifiers

epoch is external nullfier.

Internal nullifier is calculated as in = hash(a_1). Note that a_1 has already a secret id key ingredient a_1 and epoch ingredient, so, each epoch a member can signal to only one nullifier.

Circuit

Constaints

To send a valid signal member should provide,

• Membership proof
• A share satisfies the line equation
• Correct nullifier.

These are constraints of RLN circuit.

Public Inputs

• share_x
• share_y
• epoch
• membership_tree_root
• nullifier

Private Inputs

• a_0
• auth_path

Slashing

Members reveail a single share of secret key for each signal in an epoch.

A share (x, y) is a valid point at the polynomial of a member.

If a member signals more than one, secret key is enforced to be exposed. It means that watchtower nodes can calculate coefficients of this line equation, so the secret key a_0.

Therefore, a member who spams goes under a risk to be slashed that is burn of the deposit. The risk remains until the end of withdrawal period.

We can also dismember the related public key from membership tree.

Implementation

RLN circuit can be found at github.com/kilic/rln

Prototype application is under development and can be found at github.com/kilic/rlnapp

Poseidon Hasher

Poseidon hasher configured with t = 3, rf = 8, rp = 55 parameters. For details about parameters see Posedion research paper.

Performance

With our circuit implementation a single hash costs 314 constaints. Note that there is still room down to ~240 constaints.

Cost per hash in EVM is 20402 gas. *

Construction

• Mds multiplication is skipped at last round.
• Initial state is (0, 0, 0).
• Constant generation is based on seeding, personalization and blake2s hasher.
• Unlike circomlib different round constants are added for each element in a round. Used single constant value per round to reduce gas cost.

Benchmarks

Circuit

Results are generated using native bellman on i5 2.7 GHz machine.

Questions

1

With this setup there is nothing prevents a member to use same share for many messages. So, we need to block members to do double-share-revealing. Therefore nullifier hash set shuold be tracked in public and a member should commit in public by paying eth fees for each message in order to prepare a valid signal. Problem with it is that this process itself is already a rate limiting

2

Since membership is proven in zero-knowledge, origin of messages cannot be linked. Because of this the fisherman should run a search program with exponential complexity to find a member that violates the limit. This complexity also becomes worse when number of allowed messages per epoch increases.

3

One cool feature would be to not reveal previous messages if you get slashed

4

Issues at vacp2p research

Mobile Benchmarks

Results are generated with browserstack.com