Onchain RLN tree+root: Proof Of Concept

[alrevuelta]

tldr: We present a change in the RLN contract to store the whole membership tree on-chain + its Merkle root. This lowers sync time from several minutes to a few seconds, but at a cost of x10 the membership insertion cost. It also makes light clients lighter since proof verification becomes stateless (Merkle root can be accessed onchain, without having to sync the tree). We also present go-waku-light, to showcase the newly introduced features and how they are meant to be used.

Thanks to @rymnc for developing the contract changes and his support with the deployments.

This issue aims to solve the problem of using RLN in resource-restricted devices (aka light clients) stated in #45 with the approach proposed in #56. We propose a proof of concept that solves it, introducing:

• Modifications in the rln-contract to store the whole membersip set onchain + Merkle root.
• A go-waku-light tool, to showcase how the new RLN contract is meant to be used.
• A deployment of the RLN contract in the Polygon zkEVM with this new approach, containing 10k members.

Note: This is a proof of concept, and it's yet to decide if we will integrate this into The Waku Network.

The pros:

• Easier to verify RLN proofs, since the Merkle root is now available in the RLN contract. This means it can be fetched in a single RPC call, and the node doesn't have to keep a local copy of the Merkle tree. A node just veryfing proofs can be stateless.
• Easier to generate RLN proofs, since the Merkle tree (the leaves) can be fetched from the contract via simple RPC calls (one or multiple depending on the size), instead of having to sync from events. Sync times goes from few minutes to few seconds.
• Backwards compatible with the current approach, meaning that the changes in the contract won't break compatibility with existing nwaku + there is no need to make any modifications. A client can opt to sync with events (current approach) or via the RPC call to get the leaves (new approach). Of course, the new approach is recomended.

The cons:

• Membership insertion in the tree becomes more expensive: 80k to 700k.

The goal:

• Make RLN in light clients easier to use, helping js-waku to become more RLN user friendly.

Gas Fees and Layer2

In this proof of concept, we use BinaryIMT (binary incremental Merkle tree) to store both leafs and Merkle root of the tree on chain. While this benefits light clients, it comes at a cost. Membership insertion (adding a new RLN member into the tree) is more expensive in terms of gas. We have deployed two contracts to see the delta.

• Old contract, what we currently have in The Waku Network. Insertion cost is 80k gas.
• New contract, containing the modifications of this proof of concept from here. Insertion cost is 700k gas.

In Ethereum mainnet, that would be (using 40Gwei as gas price and 1ETH=$2000 ref):

• 80k = $6.4
• 700k = $56

In a Layer 2 such as Polygon zkEVM that would be (using 4Gwei and 1ETH=$2000 ref):

• 80k = $0.64
• 700k = $5.6

Important notes:

• Transaction gas usage slightly varies between Ethereum mainnet and Polygon zkEVM. We took the same for simplicity.
• Gas prices can change at any time, an average of the last month was taken.
• Changes in the upcoming EIP4844, affecting Layer 2s mostly, may reduce the gas consumption.
• The contract in this proof of concept is not gas-optimized, and if done, we could save some gas.

Important takes:

• Moving to a Layer 2 such as the Polygon zkEVM significantly reduces the cost of inserting a new member into the tree. Even if we don't modify the RLN contract to store the whole tree, a /10 reduction in the cost is interesting ($6.4 to $0.64).
• If we proceed with this proof of concept, storing the whole tree onchain + root, that would imply migrating to a Layer 2. Otherwise $56 would be too much of an entry barrier.

Regarding Layer 2s:

• Layer 2s in general are not very mature to date.
• Most of them contain a single centralized sequencer, that if offline, no one can broadcast new transactions.
• Gas saving as an evident advantage.
• Security from Ethereum mainnet is inherited, since its used as the settlement layer.

Proof of Concept Playground

We have developed go-waku-light, a proof of concept of a waku light client built in go that interacts with this contract deployed in the Polygon zkEVM containing the changes explained in this issue.

The goal of this tool is to serve as a playground and show the capabilities of this proof of concept. It abstracts away all waku full node capabilities and just focuses on what a light client should know in order to send (generate rln proofs) and received (verify rln proofs) messages.

It allows to easily sync a tree, access the onchain merkle root, register a new membership, generate a proof, verify a proof and listen for changes in the membership set. See instructions inside the repo.

Future work

If we decide to integrate this in The Waku Network, we should:

• Check for some gas optimizations, trying to reduce membership insertion cost.
• Peer review the contract to find vulnerabilities.
• Integrate the ideas showcased in go-waku-light in js-waku
• As a nice to have, use the new syncing method in nwaku/go-waku. Not mandatory since backwards compatibility is kept, but more efficient.

[rymnc]

was great working w/ you on this! thanks for the detailed report 🔥

[jm-clius]

Great work, @alrevuelta @rymnc. Very good input and POC to have.
I think the core of a L2/L1 decision will come down then to the general L2 tradeoffs, that you already mention: centralisation, tying ourselves/users to a specific domain, Tokenomic considerations, etc. Would love to see RLN in the hands of developers, as this will guide us to find the appropriate set of tradeoffs.