---
# System prepended metadata

title: RLN Workshop

---

# RLN Workshop

---

## Intro

- [@oskarth](twitter.com/oskarth) / [oskarth.com](oskarth.com)
- [vac.dev](vac.dev) - Privacy & Communication

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

![](https://i.imgur.com/88fmC1d.png)

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

![](https://i.imgur.com/usrH2zC.png =600x400)

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

([RLN SSS](https://rate-limiting-nullifier.github.io/rln-docs/sss.html))


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)

![](https://i.imgur.com/lHqljZ4.png =800x600)

---

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

- [rlnjs (JS)](https://github.com/Rate-Limiting-Nullifier/rlnjs/)
- [Zerokit (Rust)](https://github.com/vacp2p/zerokit/)
- ([js-rln (JS wrapper around Zerokit)](https://github.com/waku-org/js-rln))
- (No longer used: [kilic/rln (Rust)](https://github.com/kilic/rln/))

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

- [rlnjs tests](https://github.com/Rate-Limiting-Nullifier/rlnjs/blob/main/tests/rln.test.ts)
- [Zerokit (Rust)](https://github.com/vacp2p/zerokit/tree/master/rln)
- [rln circuits](https://github.com/Rate-Limiting-Nullifier/rln_circuits)

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

![](https://i.imgur.com/zNdMZDK.png)

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


```graphviz
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

![](https://i.imgur.com/jWLPdeY.png)
*From [30/ADAPTIVE-NODES](https://rfc.vac.dev/spec/30/)*

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

![](https://i.imgur.com/WvESRiT.png)

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

![](https://i.imgur.com/VDVgur2.png =400x400)

---

## RLN Relay: Routing

![](https://i.imgur.com/YNQPFmF.png =400x600)

---

## Demo: RLNP2P

- Shows messages sent through RLN Relay
- [rln-js Waku ex](https://github.com/waku-org/js-waku-examples/blob/master/rln-js/index.html)
- [js/go/nim p2p chat](https://github.com/waku-org/nwaku/blob/master/docs/tutorial/rln-chat-cross-client.md)
- [RLN contract](https://github.com/vacp2p/rln-contract/blob/main/contracts/Rln.sol)

---

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

- Use social stake instead of financial stake
- Leverage web2 reputation to get sybil-resistance
- Allow for zero-cost entry, people w/o crypto assets
- https://github.com/vacp2p/research/issues/147

Note:

---

## Conclusion

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

---

## Links

- [RLN docs](https://rate-limiting-nullifier.github.io/rln-docs/)
- [RLNP2P](https://rlnp2p.vac.dev/)

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

---

## Q&A

Thanks! Questions?