# 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  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](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)  --- ## 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  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  *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  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 - 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?