# 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](https://github.com/kilic/rln)

Prototype application is under development and can be found at [github.com/kilic/rlnapp](https://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](https://eprint.iacr.org/2019/458.pdf).

#### 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. [*](https://github.com/kilic/rlnapp/blob/master/contracts/test/poseidon_3_8_55.test.js)

#### 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.

| Curve, Hasher | Set Size | Constaint Size | Prover Time | Prover Key Size |
| - | - | - | - | - |
| BN256, Poseidon (3, 8, 55) | 2^24 | 8590 | 0.672 sec | 3.24 mb |
| BN256, Poseidon (3, 8, 55) | 2^32 | 11134 | 0.762 sec | 3.89 mb |

## 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](https://github.com/vacp2p/research/milestone/2:)

## Mobile Benchmarks

Results are generated with browserstack.com

| Device | Security Level | Merkle Depth | Prover Time (seconds) |
| --- | --- | --- | --- |
| Pixel 4 | 128 | 16 | 0.541 |
| Pixel 2 | 128 |16 | 0.62 |
| Galaxy S8 | 128 |16 | 0.538 |
| Iphone 11 | 128 | 16 | 0.247 |
| Iphone 8 | 128 | 16 | 0.304 |
| Iphone SE | 128 | 16 | 0.921 |
| Iphone 6 | 128 | 16 | 1.143 |
| Pixel 4 | 128 |24 | 0.795 |
| Pixel 2 | 128 |24 | 0.986 |
| Galaxy S8 | 128 |24 | 0.775 |
| Iphone 11 | 128 | 24 | 0.364 |
| Iphone 8 | 128 | 24 | 0.458 |
| Iphone SE | 128 | 24 | 1.391 |
| Iphone 6 | 128 | 24 | 1.885 |
| Pixel 4 | 128 |32 | 0.917 |
| Pixel 2 | 128 |32 | 1.061 |
| Galaxy S8 | 128 |32 | 0.808 |
| Iphone 11 | 128 | 32 | 0.447 |
| Iphone 8 | 128 | 32 | 0.553 |
| Iphone SE | 128 | 32 | 1.584 |
| Iphone 6 | 128 | 32 | 2.554 |
| Pixel 4 | 80 |16 | 0.464 |
| Pixel 2 | 80 |16 | 0.492 |
| Galaxy S8 | 80 |16 | 0.412 |
| Iphone 11 | 80 | 16 | 0.200 |
| Iphone 8 | 80 | 16 | 0.252 |
| Iphone SE | 80 | 16 | 0.758 |
| Iphone 6 | 80 | 16 | 0.924 |
| Pixel 4 | 80 |24 | 0.542 |
| Pixel 2 | 80 |24 | 0.624 |
| Galaxy S8 | 80 |24 | 0.551 |
| Iphone 11 | 80 | 24 | 0.249 |
| Iphone 8 | 80 | 24 | 0.336 |
| Iphone SE | 80 | 24 | 0.948 |
| Iphone 6 | 80 | 24 | 1.326 |
| Pixel 4 | 80 |32 | 0.749 |
| Pixel 2 | 80 |32 | 0.842 |
| Galaxy S8 | 80 |32 | 0.677 |
| Iphone 11 | 80 | 32 | 0.354 |
| Iphone 8 | 80 | 32 | 0.465 |
| Iphone SE | 80 | 32 | 1.322 |
| Iphone 6 | 80 | 32 | 1.627 |