owned this note changed 3 years ago
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

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.

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

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
Select a repo