Create RLN proof without having the whole tree

[alrevuelta]

TLDR: We present a proof of concept for light clients, where they don't need to sync the whole tree to create RLN proofs to send their messages. PoC here

One of the main problems with light clients and RLN is that they require the whole Merkle tree to generate valid proofs. Meaning that they need to sync the whole tree to send a message into the network. This creates friction since syncing the whole tree takes several minutes, and the sync time increases with the number of memberships registered.

This issue proposes a proof of concept where light clients can generate RLN proofs with just a Merkle proof that their commitment belongs to the tree. This Merkle proof has a fixed size of 20 and can be fetched from:

• 1. Other waku nodes: Some nodes can opt to offer Merkle proofs to others.
• 2. The contract: Which would be the endgoal. See ongoing work and Onchain RLN tree+root: Proof Of Concept #72.

This issue explores i) and presents this proof of concept to showcase the feature. The Merkle proofs are obtained with this service deployed in the sandbox machine. Endpoint available here, just replace the number with your commitment. Note that this Proof Of Concept is fully compatible with The Waku Network. Note that i) is a step in between towards ii). Any client can use this feature, see newly exported generate_rln_proof_with_witness from zerokit.

curl http://65.21.94.244:30312/debug/v1/merkleProof/21235824865182058647676208664819393617711826061506661756580202797779091020767

Related PR:

• Expose generate proof with witness ffi vacp2p/zerokit#227
• chore: bump zerokit v0.3.5 to include proof with witness go-zerokit-rln-apple#3
• chore: bump zerokit v0.3.5 to include proof with witness go-zerokit-rln-arm#3
• chore: bump zerokit v0.3.5 to include proof with witness go-zerokit-rln-x86_64#3
• Expose get_proof as GetMerkleProof go-zerokit-rln-x86_64#2
• Expose get_proof as GetMerkleProof go-zerokit-rln-arm#2
• Expose get_proof as GetMerkleProof go-zerokit-rln-apple#4
• Add GetMerkleProof go-zerokit-rln#17
• Add GenerateRLNProofWithWitness go-zerokit-rln#19

Thanks @richard-ramos @rymnc for their help.

[rymnc]

wow, this is nice!

[chaitanyaprem]

Nice work!

One thought wrt approach:
In order to avoid generating proofs which would get invalidated(because of using older proof), the sender should always get the latest proof for their commitment from a WakuNode before sending a message.
Wouldn't this slow down or cause delay, because for every message to be sent there is an additional confirmation to be made with WakuNode (if merkle proof has changed).
Maybe this was already considered and there exists another solution, but wanted to drop my suggestions.

In order to address this

• LightClients can poll for the merkle-proof in regular intervals with fullNode. This can still lead to a race condition where-in merkle proof is updated while the lightClient sends a message in a corner-case (it is possible more than 5 updates to root happens in 5 blocks which may lead to invalid-proof). We can update the lightPush protocol where-in the lightPushServiceNode can reply to the client with an error indicating it is using a older/invalid merkle proof, which would trigger client to query and get an updated proof. Client can resend message in case it has used invalid proof. This would only add additional round-trip in case of hitting the scenario of more than 5 root updates happened, which maybe ok.

• Another approach is, can we have a light-protocol (maybe call it membershipFilter) where lightClients can subscribe to WakuNodes in order to get updates on their own merkle proofs? This would prevent complexity of updating lightPush protocol and client retrying as proof updates would be near real-time.

[alrevuelta]

We can update the lightPush protocol where-in the lightPushServiceNode can reply to the client with an error indicating it is using a older/invalid merkle proof

That's a great idea. As a rule of thumb any API endpoint or protocol such as light-push should perform as much validations as possible, and inform the user if such message is invalid (like invalid root)

Another approach is, can we have a light-protocol (maybe call it membershipFilter) where lightClients can subscribe to WakuNodes in order to get updates on their own merkle proofs?

Once merkle proofs are fetched directly from the contract (see point ii in issue), the "NewMerkleRoot" event could act as that, and we avoid having an extra protocol on waku side. In other words, you can subscribe to that NewMerkleRoot event and whenever it changes, you request a new proof.

Another idea could be to guarantee that all roots belonging to the last x blocks are valid. If we set this to 1 minute, then we could guarantee that proofs <1min will be valid. This would require to store way more merkle roots in some cases, since afaik each insertion/deletion "consumes" a slot in the window. Example, if 100 insertions are done in this last minute, we have to store 100 different merkle roots and validate each message against each one.

Related to your first point, we could have an optimistic approach, where you assume your proof is valid until light-push errors saying otherwise. At that point you fetch a new one.

[chaitanyaprem]

Once merkle proofs are fetched directly from the contract (see point ii in issue), the "NewMerkleRoot" event could act as that, and we avoid having an extra protocol on waku side. In other words, you can subscribe to that NewMerkleRoot event and whenever it changes, you request a new proof.

I missed going through this. But got it and this would require querying contract to get the new root.I am trying to think if we can avoid blockchain interaction in lightClients. :) Hence suggesting some Waku protocol for this (It could be as simple as reusing existing FilterProtocol where merkleRoots are advertised in a contentTopic named RLN-membership-updates ). This does comes with it own challenge of trusting whoever broadcasts into this topic. But since mostly lightClients would actually use some RPC provider API for this anyways, maybe avoids that.

[chaitanyaprem]

Another idea could be to guarantee that all roots belonging to the last x blocks are valid. If we set this to 1 minute, then we could guarantee that proofs <1min will be valid. This would require to store way more merkle roots in some cases, since afaik each insertion/deletion "consumes" a slot in the window. Example, if 100 insertions are done in this last minute, we have to store 100 different merkle roots and validate each message against each one.

I had thought about this, but validating a message against soo many roots maybe too costly. I think the current last 5 roots seem good enough.

[chaitanyaprem]

Related to your first point, we could have an optimistic approach, where you assume your proof is valid until light-push errors saying otherwise. At that point you fetch a new one.

Yea, thought of this as well..but polling + this felt like the sweet spot to me. That way we reduce multiple RTT's for sending a message most of the time and only in some corner cases where suddenly a lot of registrations happen in a short span.
1 more question related to this, in a block if there are multiple RLN registrations are there going to be multiple valid roots or only 1 final root after all updates that is considered valid?

[rymnc]

1 more question related to this, in a block if there are multiple RLN registrations are there going to be multiple valid roots or only 1 final root after all updates that is considered valid?

1 final root per block

[alrevuelta]

Workshop agenda 14 Marc 2024 [1h]:

• Quick intro to RLN.
• Problems for light clients and adoption.
• Possible solution. Merkle proofs instead of the whole tree.
• Source of Merkle proofs. Alternatives and tradeoffs: i) rest service, ii) libp2p protocol iii) contract.
• Demo for i) using rln-proof-witness
• Summary, next steps: nwaku/js-waku
• Questions