Waku-RLN-Relay: Evaluating Storage Overhead of Membership Merkle Tree

[staheri14]

Closes https://github.com/vacp2p/research/issues/109 and partially addresses https://github.com/vacp2p/research/issues/127 The PR contains the initial storage overhead evaluation of the membership Merkle tree. The "introduction" and "conclusion" sections are self-contained and will highlight the most important aspects and results of this analysis. The “storage overhead analysis” section is there to back the conclusion section and to elaborate on the intermediate results and the thought/evaluation process.

Please note that in this write-up, the FMT algorithm is considered to follow an array-based structure to represent the Merkle tree, this does not exactly map to the zero-kit implementation, but I believe the analysis holds true storage-wise.

I also did not dive in to the mechanics of OMT, but if necessary, I can elaborate on that.

[staheri14]

@oskarth Please let me know if we want to publish this as a forum/research post?

[oskarth]

To be honest, I feel like the conclusion is fairly obvious and I'm not sure how illuminating it'd be as a research post. Forum post sure!

Research post would make more sense to me when we have something that new that goes beyond what is already known (e.g. basic more efficient MT construct coded years ago, or benchmarks that PSE group did a year ago). Perhaps once we have it working in the browser, or for a more complete picture of perf? E.g. some things wrt to UX perf were discovered during testnet, and how we address this can be useful. Also interesting once we have Zerokit and same proofs in browser and nwaku/go-waku I think.

[oskarth]

E.g. there's a lot here https://ethresear.ch/search?q=merkle%20tree and also probably in geth / erigon how they've been optimizing storage trees

[staheri14]

A forum post looks fine to me, just to show that we have investigated the storage overhead both asymptotically and empirically and that we have confidence it won't be an issue.

@oskarth

To be honest, I feel like the conclusion is fairly obvious and I'm not sure how illuminating it'd be as a research post. Forum post sure!

Research post would make more sense to me when we have something that new that goes beyond what is already known (e.g. basic more efficient MT construct coded years ago, or benchmarks that PSE group did a year ago). Perhaps once we have it working in the browser, or for a more complete picture of perf? E.g. some things wrt to UX perf were discovered during testnet, and how we address this can be useful. Also interesting once we have Zerokit and same proofs in browser and nwaku/go-waku I think.