search

vacp2p / research

Thinking in code
MIT License
62 stars 4 forks source link

RLN-Relay suggested next steps #72

Open oskarth opened 3 years ago

oskarth commented 3 years ago

Discussed in https://github.com/vacp2p/research/discussions/63

Originally posted by **staheri14** March 9, 2021 # Context Currently, we are in the middle of rln-relay PoC. The registration pipeline is developed which includes the following parts 1. An initial raw spec https://github.com/vacp2p/specs/blob/master/specs/waku/v2/waku-rln-relay.md 2. A membership contract with a tested interface in Nim https://github.com/status-im/nim-waku/blob/307a49bb78d5d8a55ca401774b410280128a9c5e/waku/v2/protocol/waku_rln_relay/waku_rln_relay_utils.nim#L30 3. A Contract deployment proc https://github.com/status-im/nim-waku/blob/307a49bb78d5d8a55ca401774b410280128a9c5e/tests/v2/test_waku_rln_relay.nim#L92 4. A fully functional and tested key generation and registration procs https://github.com/status-im/nim-waku/blob/307a49bb78d5d8a55ca401774b410280128a9c5e/waku/v2/protocol/waku_rln_relay/waku_rln_relay_utils.nim#L34 and https://github.com/status-im/nim-waku/blob/307a49bb78d5d8a55ca401774b410280128a9c5e/waku/v2/protocol/waku_rln_relay/waku_rln_relay_utils.nim#L88 3. The group membership is integrated with waku v2 node https://github.com/status-im/nim-waku/blob/307a49bb78d5d8a55ca401774b410280128a9c5e/waku/v2/node/wakunode2.nim#L56 that is peers in relay protocol are able to register to the membership contract https://github.com/status-im/nim-waku/blob/307a49bb78d5d8a55ca401774b410280128a9c5e/waku/v2/node/wakunode2.nim#L375 # Problems 1. Not deployed on testnet 2. Hardcoded eth accounts' private keys # Next Steps There are two other phases to get this POC done 2. Static group: In this phase, we consider a static group of users where each user knows the root of the tree and its authentication path. Therefore, the Merkle tree management will be mocked. We are going 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). In the end, the specs will be updated as well. 3. Dynamic Group: 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. This allows users to compute the tree root and the authentication path, essentially, the data needed for the ZKP to be functional. This part also requires listening to the contract events to update the tree based on the contract's state. In the end, the specs will be updated as well. # Lessons so far and what should we do next By conducting the first phase i.e., the registration component, we identified some feasibility issues which did not seem to be a concern previously and even we did not know they exist. All of the identified issues concern the solution feasibility and were not known until after we started the PoC. Given that we have resource-restricted peers, the performance issues are better to be identified early on to enable an informed decision on the feasibility of this solution for a production-grade development. It is also expected that more research/performance issues will be identified as we move forward in the PoC. As such, I suggest to further this PoC at least util the second phase i.e., the e2e integration of the zkSNARKs to make sure no further blockers exist on that path. My emphasis is on the zkSNARKs part because it is our critical path, the most complex part, the heart of our privacy guarantees, and we previously had a bunch of blockers for that part, and it makes sense to make sure no performance/research issues are overlooked. # Identified feasibility issues 1. The membership contract lacked the support for deletion operation which was an important operation for the rln-relay (deletion is needed 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. 2. 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](https://github.com/vacp2p/research/issues/57). 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. 3. 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](https://github.com/vacp2p/research/issues/56). --- Would be glad to know your comments/questions/concerns re the above approach, the next steps, etc. :)