owned this note
owned this note
Published
Linked with GitHub
# 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 |