RLN-Relay group management performance

staheri14 commented 2 years ago

Problem

This meta issue focuses on the performance of the rln-relay membership group management i.e., bandwidth, storage, and computation. The aim is to make sure there is no bottleneck for resource-limited devices to support the group-management/synchronization logic which is mostly done locally by each peer.

Atm, the most pressing and evident issue is with the storage overhead of the Merkle tree. The tree needs to be persisted locally by each peer and its size can become large hence not suitable for mobile devices. There can be other concerns regarding the time complexity of constructing the Merkle tree or keeping it updated. More tasks can be added to this issue if need be.

The following tasks are envisioned:

[x] Evaluating Merkle tree storage overhead in Killic's lib and writing a post on the Merkle tree storage overhead https://github.com/vacp2p/research/issues/109
[x] Evaluating the computation overhead (Update: the initial runtime evaluation does not prove to be any blocker, will follow up with new issues if further optimizations found necessary)

Acceptance criteria

All the tasks are addressed. The storage, computation, and BW requirements should reasonably fit resource-limited devices.

No implementation and optimization will take place in the killic lib, the whole focus is the nwaku and zero-kit repos.

Future steps

Depending on whether the storage overhead is a bottleneck or not, we may proceed with devising a new algorithm for optimizing Merkle tree storage (RFC) for which the corresponding implementation will be hosted by zero-kit.

staheri14 commented 2 years ago

cc: @oskarth @s1fr0

s1fr0 commented 2 years ago

I guess that the implementation in zerokit should come after all the other items. Unless you have a strong feeling that the optimizations will be incremental over Kilic's tree implementation, which, however, I won't qualify at the moment as the solution that has to be necessarily implemented for Incremental Merkle trees. If the implementation comes first, then the second item IMO should be done over zerokit lib and not kilic's one. The rest then follows.

oskarth commented 2 years ago

1) I'm not convinced this warrants its own milestone, especially with our current documented knowledge.

2) I'm confused by this issue and the inclusion of "Incorporating the killic MT algorithm inside zero-kit https://github.com/vacp2p/zerokit/issues/29" in general. That seems completely separate from previous discussions. That is an implementation issue to enable Zerokit to replace kilic.

3) It'd be better to achieve clarity bottom-up https://github.com/vacp2p/zerokit/issues/29#issuecomment-1206086429 first

staheri14 commented 2 years ago

@oskarth @s1fr0 Reverted this issue from milestone to a meta-issue. Following this change, I removed the integration of killic implementation into zero-kit from this meta-issue to limit the scope. The result of the initial evaluation is now ready in https://github.com/vacp2p/research/pull/132 and we can make our decision for the future steps.

vacp2p / research