Storage overhead per peer

[staheri14]

Overview

rln-relay consists of the following steps: 1- A membership smart contract must be deployed on the blockchain, the contract holds the list of current registered members (as well as deleted members) and has the API for member insertion, and deletion (slashing). Root of the tree and auth path of pubkeys are not available as part of the contract.

2- Each rln-relay enabled peer must register a public key through the smart contract. Peers need to persistently store their public and secret keys. Registered peer locks a certain amount of fund in the smart contract, which gets burned in case the peer misbehaves (spams the system). 3- Each rln-relay enabled peer must construct and maintain a Merkle Tree based on the list of current members )fetched from the membership contract). This is required for the spam protection. As scuh, peers must keep listening to the contract events (member insertion or deletion) and update their local Merkle tree accordingly. Having the Merkle tree, a peer is able to

• calculate the tree root
• its authentication path (membership proof)

4- By having access to the recent root and membership proof

• Peers can anonymously publish messages with a certain rate and prove that they are not spammers (have not violated the designated rate)

• Routing peers can authenticate the non-spam messages, and otherwise drop the message and slash the spammers (delete them from the membership contract and withdraw their deposit)

  Problem

  For a group of size N, each peer has to dedicate 2N-1.H (H is the hash size (Poseidon hash function)) storage space to maintain the Merkle tree.

  • let N = 2^32
  • Hash output = 32 bytes = 2 ^ 5
  • Tree size = (2 2^32 - 1) 32 = 2 ^ 38 bytes = (almost) 2^8 Gigabyte

For a smaller size groups e.g., N = 128

• Tree size = almost 8 Kilobyte

[mratsim]

In Eth2 we are considering moving away from Merkle Trees and use KZG Polynomial Commitments / Verkle Trees to have constant size proofs. This is also necessary research for Eth1 stateless clients to cur down on witness size.

This is still in research phase but if it's finalized, there will be new libraries that will be optimized and audited to support that usage.

Some writeups:

• https://notes.ethereum.org/@ZuSZK8r2TgO7eFShwj4hVg/H1XE_w30w
• https://math.mit.edu/research/highschool/primes/materials/2019/conf/12-5-Kuszmaul.pdf
• https://vitalik.ca/files/misc_files/stateless_client_witnesses.pdf
• https://ethresear.ch/t/open-problem-ideal-vector-commitment/7421/27

[staheri14]

@mratsim It is good to know! thanks for sharing it! a constant proof size is a significant improvements, I had a quick look at the verkle tree slides, it seems this new construction has a higher complexity for proof construction which is somehow in favour of spam protection (lowers the messaging speed of the spammers). But I am not sure whether it lowers the storage complexity of the peers or not, I need to investigate further, but my guess is that the storage complexity would be still linear (though we may be able to optimize it).