RLN ZK-Proof Generation For Light Clients

[alrevuelta]

TLDR: Using a LazyIMT + a change we contributed upstream, we can have Merkle roots and Merkle proofs onchain in the RLN contract with an assumable gas increase. This will allow light client to generate and verify RLN proofs without having to keep any state, with a very low impact in development. An end-to-end PoC is presented in Go using light push and the new RLN contract.

Previous Work

Some background of the previous work that has been done in relation to RLN in light clients:

• Everything started with https://github.com/waku-org/research/issues/45, acknowledging that light clients currently require synchronizing the RLN membership Merkle tree, which is not practical for resource-restricted clients.
• In here https://github.com/waku-org/research/issues/72 we introduced an approach using BinaryIMT that partially solved the issue by having the Merkle root onchain. This helped RLN proof verification but increasing the membership registration to from 80k to 700k. Not feasible. Moreover, it didn't address the problem of proof generation. Sync times improved but light clients still needed to keep the tree.
• Later in https://github.com/waku-org/research/issues/79, we proposed a "Merkle Proof Provider" service, that could serve Merkle Proofs to light clients. Using this service, light clients no longer needed to sync/store the tree. They could use other nodes in the network offering such service to get the Merkle proof so that they could then generate the RLN proof locally. However, this approach required to implement a new libp2p protocol and involved trust since a light client could not verify that the given Merkle proof was valid.

New Proposal

The latest proposal is showcased with a PoC that integrates and showcases the end-to-end solution:

• It only requires a minor modification in the RLN contract deployed in Polygon zkEVM testnet.
• And can be used by any light client, see go-waku-light. This PoC showcases how a light client can use it end-to-end.

Key features:

• New function in the contract: root() function that allows to get the Merkle root of the membership tree. A light client can use it to verify RLN proofs. Synchronizing the tree is no longer needed.
• New function in the contract: merkleProofElements(index) that provides the Merkle proof given an index in the tree. A light client can use it to create RLN proofs. Synchronizing the tree is no longer needed.
• New function in the contract:getCommitments(start, end) which allows to sync the tree faster. No longer needed to fetch events wasting time in ranges of blocks without any events. Syncing the tree is not really needed, but if someone wants to do it, it will be faster.
• Since these features are part of the contract, any RPC provider (eg Infura) will offer these services by default. Once fluffy is ready and Ethereum light clients are, this data can be verified. Note also that this approach doesn't require the development of a new libp2p protocol, which was the initial idea. Everything would be onchain.
• The smart contract uses a LazyIMT instead of a BinaryIMT using an upstream change that we introduced to allow Merkle proofs.
• Good news is that membership insertion cost goes from 90k see TWN to 120k see new contract. Some variations are expected but this is 7 times less than the initial approach. And note that we have some gas optimizations pending.

Conclusion and Future

• Based on the above-explained features, I would say this is the end game for RLN, allowing for frictionless proof generation and verification using nothing but the contract itself. No development needed on nwaku side, and contract already done. Peer review pending.
• This feature has been prioritized on the app level, but these proposal might want to reconsider that.
• Since this will require a breaking change in the RLN smart contract, I would suggest waiting for RLN V2 so that in the same "fork" we can include RLN v2 + Merkle Proofs/Roots onchain.
• Feel free to play around with go-waku-light

Thanks @rymnc for his help.

[rymnc]

err, maybe we want to include the subtree strategy in previous work? :)

I would say this is the end game for RLN

💯