RLN-Relay POC: summary and future steps

This issue explains all the steps and sub-steps that are taken and must be taken to conclude the rln-relay POC.

What have been done: The registration pipeline is completed i.e., as the result we have a membership contract with an appropriate interface in Nim, via which rln-relay peers are able to register to the membership group. The required methods for the key generation are also implemented and incorporated into this flow. At a high level, the following sub-tasks are done:

[X] The membership contract code is implemented both in solidity and its interface in Nim
[X] The membership contract interface is tested in Nim
[X] The connection to the contract is done through nim-web3 and all the unknowns are resolved, including
- [X] passing inputs to the contract constructor
- [X] signing transactions
[X] The Nim bindings for the key generation and circuit parameter generation methods (originally implemented in Rust by the rln team) are implemented and unit tested.
[X] The key generation process is further streamlined and unit tested
[X] The registration process is implemented in which the user generates keys, sends the public key to the membership contract through a signed transaction
[X] The registration is integrated into rln-relay, as such peers can register to the rln-relay member group
[X] The dependencies are appropriately addressed, that includes
- [X] Automating the installation and lunch of ganache-cli in the test flow through Makefile
- [X] Importing and building the rln key generation library in the build process through Makefile

Major unknowns identified so far:

[X] The membership contract lacked the support for deletion operation which was an important operation for the rln-relay (deletion is needed in order to slash spammer). In specific, the contract only stored a partial view of the Merkle tree (with log(N) storage complexity) but not the entire tree. This structure while could efficiently support the insertion operation, was unable to handle the deletion (not enough information was available to construct the root of the tree on-chain). This resulted in a change in the architecture where the storage and maintenance of the tree got delegated to the peers. As such the root of the tree shall be reconstructed by each peer individually.
[X] Following the item above, we got concerned about the storage complexity of peers, i.e., the storage complexity is linear in the size of group O(N). The calculations proved to us that the storage gets so high for large group sizes and would not be affordable by the resource-restrictive peers. This opened up a research question on how to store and update a Merkle tree by the minimum storage requirement. The proposal for such a method was made and available in this issue. The gist of this idea is that peers can maintain the tree, calculate its root as well as their authentication paths (authentication path is another piece of data that relies on the tree and is essential for the zero-knowledge proof operations) with only O(log(N)) storage complexity. N is the size of the group. This is a significant improvement over a linear storage complexity. However, to avoid any further unknown on this path, this idea is not pursued further and will be considered once the POC gets finalized. In the PoC, we consider that peers will store the entire tree; we also assume small size groups hence the Merkle tree size would be small and the storage requirement would be reasonable.
[X] Another issue that got identified was the cost associated with membership. Not necessarily a blocker, but something that has to be revisited to make it more cost-effective. Details can be seen in this issue.

Remaining phases and steps: There are two other phases to get this POC done, namely, 1- the ZKP part which includes proof generation and proof verification and 2- the Merkle Tree management. The Merkle Tree component enables access to the tree root and the authentication path, essentially, the data needed for the ZKP to be functional.

[x] The ZKP: this phase is to implement, test, and integrate the ZKP to rln-relay. At the end of this phase, peers must be able to generate a proof, attach it to their published messages and the routing peers must be able to verify the proof and decide on routing / not routing. The goal for this phase is primarily feasibility checking and discovering possible unknown technical or research open problems (as we did for the registration part). https://github.com/status-im/nim-waku/issues/298
[x] The Merkle Tree storage: this phase would be to add the Merkle Tree management to the rln-relay. As the result, peers must be able to create the Merkle tree, keep it updated by synchronizing with the contract's state, and use the updated calculated tree root and authentication path for their ZKP module. https://github.com/status-im/nim-waku/issues/395

The subtasks for each phase are listed in their respective issues.

waku-org / nwaku

RLN-Relay POC: summary and future steps #394