RLN Workshop

Intro

Note:
不好意思我現在不會講中文，沒有時間準備
Director of Research at Vac
Vac builds public good protocols for the decentralized web,
with a focus on communication and privacy
origin in Status app and trying to improve on underlying protocols
We build Waku, ZK tooling and other things

Agenda

  1. Intro and overview
  2. RLN (construct + code)
  3. RLNP2P (construct + code)
  4. Conclusion, next steps etc

Note:
Go over RLN core construct first, then look at in a p2p setting
For each part we'll also do a bit of a code/demo that you can play around with

Motivating problem(s)

  • How to we prevent spam in an anon p2p network?
  • Rate limiting in a privacy-preserving manner?
  • Can we build a decentralized captcha?

Note:
Existing solutions for preventing spam are usually either centralized or they don't work in practice
This is a big problem, services that require phone number, tied to identity, and country
We'll talk more about the p2p aspects later on

RLN

  • Rate Limiting Nullifier
  • Anonymous rate limiting mechanism
  • Based on zkSNARKs
  • Anonymity: can’t link message to publisher

Note:
Rate limiting can only send N messages in a period
Can be used for spam protection in p2p messaging systems
Also things like rate limiting in general, decentralized captcha

History

Note:
ETHResearch post origin by Barry Whitehat
Then a lot of work on various implementations, performance, making it work in p2p setting
First let's look at construct a bit

RLN: Flow

  • Register
  • Signal
  • Verification and slashing

Note:
We split up flow into three parts
Put some capital at risk, economic or social, if you double signal, you get slashed

RLN: Registration

  • Users register with a membership group to be able to signal
  • Can happen with central server, or to a smart contract
  • Identity commitment stored in Merkle tree
  • Merkle proof to prove membership
  • Financial (e.g. ETH) or social stake (e.g. InterRep)

Note:
Identity commitment inserted into merkle tree
Identity secret random 32 byte values, hash twice to get identity commitment
Want to make it economically or otherwise costly to register, against Sybil attacks
InterRep prove user has a reputable social media account

RLN: Signaling

  • Registered members can signal once for a given period, external nullifier/epoch
  • User can store membership tree locally or get from somewhere
  • ZKP is generated to prove membership
  • Signal hash is keccak256 hash of content
  • Mental model: voting booth, can only vote once

Note:
Signal is hash of message, external nullifier, proof and some other fields

RLN: Verification and slashing

  • Verification to ensure ZKP and other parameters are correct
  • Slashing: If user double signals, secret credentials revealed

Note:
Verification: external nullifier correct epoch, non-duplicate check, zk proof verification and then double signal check
Slashing: based on Shamir’s secret sharing, reveal secret key -> get stake

Proof generation - ZK circuit input

// private
signal input identity_secret;
signal input path_elements[n_levels][1];
signal input identity_path_index[n_levels];

// public
signal input x; // signal_hash
signal input epoch;
signal input rln_identifier;

Note:
identity_secret is is ther secret key generated locally
path_elements elements along path, siblings
identity_path_index path to leaf for merkle proof
x is the signal hash
epoch is external_identifier here
Usually a timestamp or period, can think of as voting booth,
can only signal once in that period
RLN identifier is for a specific RLN app
path_elements has a 1 here for simplicity, indicates number of neighbors at that level

Circuit output

signal output y;
signal output root;
signal output nullifier;

Note:
Calculated locally
y is share of secret equation, see soon, and internal nullifier
internal nullifier acts as unique fingerprint for a given app/user/period combination
Also root of Merkle tree
How is this output with y and the internal nullifier calculated?

Calculating output

a_0 = identity_secret
a_1 = poseidonHash([a0, external_nullifier])

y = a_0 + x * a_1

internal_nullifier = poseidonHash([a_1, rln_identifier])

Note:
This is using Shamir's secret sharing
If a given identity a0 signals twice in epoch/external nullifier, a1 is the same
For a given RLN app, internal_nullifier then stays the same
x is signal hash which is different, and y is public, so we can reconstruct identity_secret
With the identity secret revealed, this gives access to e.g. financial stake

Shamir's secret sharing

y1 = a_0 + x1 * a_1
y2 = a_0 + x2 * a_1

(RLN SSS)

Note:
Shamir's secret sharing is based on idea of splitting a secret into shares
k points is enough to determine polynomial of degree <= k-1
In this case we have two shares, and since a0 and a1 stays the same for a given user and epoch,
With x (signal hash) changing we are able to reveal a0 which is the identity secret

RLN illustration (by Tyler)

Sending output message

`
{
  signal: signal, # full signal
  proof: zk_proof,
  internal_nullifier: internal_nullifier,
  x: x, # signal hash
  y: y,
  rln_identifier: rln_identifier,
  
  // application specific
  root: merkle_proof.root,
  external_nullifier: external_nullifier
}

Note:
This is the actual message we send
We may also include root and external nullifier here

Metadata stored

  • Slashing can happen in different ways
  • Store metadata per external nullifier, example:
{
    [external_nullifier]: {
        [internal_nullifier]: {
            x_shares: [],
            y_shares: []
        }
    }
}

Note:
E.g. can happen at central server, or at each client
Metadata needs to be stored to detect double signaling and ability to reconstruct secret

Verification checks

  • external nullifier correctness
  • non-duplicate message check
  • zk proof verification
  • double signal verification

Note:
Check external nullifier / period is correct one (e.g. 20s window)
Discard duplicate messages
Verify ZKP, otherwise discard
Check if there is more than one x/y share combination per external nullifier and internal nullifier
If there is, we can reconstruct a0 and take stake
Store metadata

Briefly on various implementations

  • Initially: Circom based implementation (slow few years ago, only JS)
  • Then: Bellman-based native Rust implementation by Onur (kilic)
  • Two different implementations, not ideal from re-use, compatibility, audit etc POV
  • Current RLN spec Circom based

Note:
Now Circom one much more performant, WASM, Circom 2 etc
Current libraries we have are

Libraries

Note:
Circom are the official spec version
rlnjs is by PSE and the reference implementation
Zerokit is using Circom circuits via WASM, more soon
js-rln wrapper Zerokit WASM, primarily made to make it easier to work with Zerokit and Waku
Final one is the alt impl not using official Circom spec, Waku used this before but moved away from

Zerokit: Circom + Rust with ark-circom

  • Goal: get best of both Circom/Solidity/JS and Rust/ZK ecosystem
  • Enable people to leverage Circom-based constructs from non-JS environments
  • Use Circom circuits via ark-circom, Rust for scaffolding, expose C and WASM API

Note:
Context: Waku as p2p infra running in many environments (Nim/JS/Go/Rust)
Circuit artifacts wasm and r1cs code
Circom strength Dapp developers, tooling, verification codes, circuits etc
Rust strength systems based, easy to interface with Nim, Go, Rust, C etc
Also access to other Rust ZK ecosystem, arkworks here with ark-circom
Opens door for using other constructs, Halo etc

Demo: RLN

Note:
Show code

RLNP2P

  • RLN applied in a p2p setting
  • Each node keeps track of state and validates messages
  • Decentralized, sybil-resistant and privacy-preserving communication channel

Examples

  • Waku RLN Relay
  • Applies to libp2p GossipSub
  • Dandellion++/Tor hybrids
  • zkchat: Using RLN on application layer
  • RLN+Interrep leveraging web2 reputation

Waku RLN Relay

  • Most mature that exists today
  • Similar principles can be applied to other topologies
  • First to give background, understand p2p messaging context

What is Waku?

  • Set of modular protocols for p2p communication
  • Focus on privacy, security and running anywhere
  • Spiritual successor to Whisper

Note:
By modular we mean: pick and choose protocols and how you use them depending on constraints and trade-offs (e.g. bw vs privacy)
Resource restricted environments
With Whisper you had holy trinity back in day, Ethereum/Swarm/Whisper

Waku protocols interactions

Note:
Waku Relay protocol based libp2p GossipSub for p2p messaging
Filter for bandwidth-restricted nodes to only receive subset of messages
Lightpush for nodes with short connection windows to push messages into network
Store for nodes that want to retrieve historical messages
Subset of protocols, for more can check specs

Gossiping

graph graphname{
        g [color=Red, penwidth=3.0]
        a [color=Red, penwidth=3.0]
        h [color=Red, penwidth=3.0]
        d [color=Red, penwidth=3.0]
        b [color=Red, penwidth=3.0]
        edge [color=Blue, style=dashed]
        rankdir=LR;
        a -- c;
        e -- a;
        f -- a;
		b -- c;
        f -- e;
        e -- d;
        e -- g;
        h -- f;
        i -- b;
        i -- c;
        a -- i;
        edge [color=Red, style=solid, penwidth=3.0]
        a -- b;
        g -- a;
        a -- d;
        h -- a;
	}

a relays messages to a subset of peers

Waku network


From 30/ADAPTIVE-NODES

Note:
Open network where nodes have different capababilities
Few problems here, e.g. spam and incentivizing service node
Want to address these while keeping privacy-guarantees of base layer
Today we gonna focus specifically on spam problem
The spam problem arises on gossip layer when anyone can overwhelm the network with messages (red lines)

Dealing with network spam

  • Phone number verification centralized and not private
  • PoW in Whisper doesn't work for heterogenerous devices
  • Peer scoring open to sybil attacks
  • Idea: Use RLN for private economic spam potection using zkSNARKs
  • RLN Relay: Relay p2p protocol (GossipSub) + RLN

Note:
Traditional phone numbers not decentralized/private
Whisper PoW not good for heterogenerous nodes
Peer scoring prone to censorship and can also be circumvented
RLN Relay!

RLN Relay overview

Note:
This is how RLN is used with Relay/GossipSub protocol
Diff other ZK applications, verify each peer
Worth noting that this can be combined with peer scoring

RLN Relay: Registration

RLN Relay: Routing

Demo: RLNP2P

Extra 1: nrln

  • Can generalize Shamir's secret sharing to be N messages in M period
  • Not currently priority, but circuits exists

Note:
TODO: Link to repo rln-circuit repo, more details
Shamir example how work?

Extra 2: RLN+Interrep

Note:

Conclusion

  • Gone over problem
  • RLN construct and code
  • RLNP2P construct and code

Note:
From above two should be able to find most things
Show docs, and RLN spec, also paper etc

Q&A

Thanks! Questions?

Select a repo