Waku-RLN-Relay: Merkle tree storage evaluation

[staheri14]

The storage of the full Merkle tree by peers in waku-rln-relay may become a bottleneck, especially for resource-restricted devices. While this may intuitively make sense, we need some benchmarking and concrete performance evaluation to assess the correctness of this premise. This issue is to capture the necessary steps for this matter:

• ~Add performance metrics to the nwaku code and collect the results~ this item is no longer needed, the storage overhead can be evaluated independently and by direct inspection of the underlying rln lib
• ~Evaluate the collected data points and potentially write a research post on this subject~ no longer needed
• [ ] Compute the storage complexity of the Merkle tree based on the algorithm used in the killic lib
• [ ] Compute the concrete storage overhead by experimenting with the killic lib

• [ ] Report the result in a post with a discussion on the potential trade-offs, and how that affects resource-limited devices.

  Context: The Merkle tree implementation in waku-rln-relay is based on the killic implementation https://github.com/kilic/rln/blob/master/src/merkle.rs, and all the storage overhead evaluation refers to that specific implementation.

Next

If the storage overhead is proven to be a bottleneck, then a proper storage optimization algorithm/protocol should follow. That optimized algorithm will not be implemented in the killic lib rather in the zero-kit lib which is the replacement of killic lib for the waku-rln-relay.

[staheri14]

fyi: @oskarth

[oskarth]

Can we please clarity this in terms of order of operations? To me this seems orthogonal to dynamic testnet. The way I see it is:

1) Critical path for dynamic testnet 2) Change over to Zerokit 3) Performance etc work

Of course if there are different people involved these can be parallelized (i.e. Keshav working on contracts), but from a global POV and to have it reflected in milestones as discussed.

[staheri14]

@s1fr0 I see you have concerns about the running time of MT, can you please elaborate on that so that I can look into that aspect of the killic MT implementation?

[staheri14]

@oskarth I did some updates on the issue description to make it more clear. I will also soon publish a meta issue about the rln critical path to shed light on the envisioned milestones, order of operations, and dependencies.

[oskarth]

Thanks.

soon publish a meta issue about the rln critical path to shed light on the envisioned milestones, order of operations, and dependencies.

The most important here is having one (or several) single clear milestone issue with a tight scope.

[oskarth]

Compute the storage complexity of the Merkle tree based on the algorithm used in the killic lib Compute the concrete storage overhead by experimenting with the killic lib

How exactly are we doing this and what are the parameters? I think it'd be good to keep this work tight in scope before running large simulations or varying parameters too much.

E.g. something like back of the napkin storage complexity math (similar to what Daniel did for Discovery v5 post in forum), and maybe only testing for a few orders of magnitude for inserts or so.

Might be good also to collect more clearly what we know and don't know when it comes to perf, e.g. your presentation already quite a lot of good numbers here.