Spam-resistant relay protocol solution

[staheri14]

Problem

To investigate and research on how to integrate the components of the RLN system (as specified in https://github.com/vacp2p/specs/issues/241) inside the relay protocol system model (as specified in #239) and achieve a realization of the IDEAL world pictured in #240.

This issue is part of #189

Acceptance criteria

The end result shall be a documented solution for the spam-resistant relay protocol. The design shall meet all the security/performance constraints and requirements specified in #239 and #240. Moreover, the components of the RLNapp that are needed for the spam protection must be determined at this phase.

[staheri14]

The following is the draft of a solution to incorporate RLN into the relay protocol to prevent spamming.
The security objective is to control the number of messages that each peer can generate per epoch, regardless of the topic.

Design parameters: epoch

Additional fields for the PubSub messages
The following fields shall be added to the PubSub messages:

1. epoch indicating the intended epoch of the message
2. share_x which is the hash of data
3. share_y (see Rate limiting Nullifier: System model extraction research#49)
4. internal_nullifier (see Rate limiting Nullifier: System model extraction research#49)

SetUp
There should be a smart contract with a known address (as in RLN vacp2p/research#49).
The state of the smart contract will be identical to the RLN except that the nullifier_map stores share_x, share_y in addition to the internal_nullifier.
Also, the set of submitted signals (i.e., the data field of PubSub messages in the current scenario) do not have to be kept by the contract.

Registration:
Peers willing to publish in the network shall follow the registration phase of RLN.
The a_0 and auth_path resultant from the RLN registration phase (step 2 of vacp2p/research#49) must be permanently and locally stored by the peer.

Publishing:
Peer:
The publisher decides on the data and calculates the epoch (the two fields in the PubSub message).
It proceeds based on the signaling per epoch (step 3 of vacp2p/research#49) of RLN with the following inputs (signal=data, a_0, auth_path, epoch).
It is recommended (and necessary for the anonymity) that the publisher updates her auth_path based on the latest version of the MT.root and attempts the proof using her updated auth_path.

Contract:
As a result of this part, the state of the smart contract gets updated and the internal_nullifier, share_x, share_y gets inserted into the nullifier_map.

Peer:
builds its PubSub message by setting the data field and the following fields

1. epoch
2. share_x
3. share_y
4. internal_nullifier

Routing:
If the epoch attached to the message has a non-reasonable gap (to be defined) with the routing node's current epoch then the message must be dropped (this is to prevent a newly registered node spamming the system by messaging for all the past epochs)
For each incoming message, the routing peer contacts the smart contract, and checks whether internal_nullifier belongs to the nullifier_map:

1. if not, then drop the message
2. if yes, compare the share_x and share_y of the PubSub message with the ones in the smart contract
   2.1 if different, slash the owner of the message
   2.2 if the same, route the message

---

Update on the solution

The lack of proof in the PubSub messages will yield faulty result, as there is no way to make sure that share_x and share_y are valid points of the A_epoch(x) i.e., correctly bound to the publisher's secret a_0. As such, if the routing peer attempts to slash, the extracted secret might be invalid. Thus, the proof (also MT.root) MUST be included in the PubSub messages.
Following this update, step 2.1 of the Routing process will change as follows:
step 2.1 if different, verify the proof and then slash the owner

---

Advantages

1. Proof verification for each message only takes place ONCE at the smart contract level
2. Related to item 1, The routing peers do not have to verify the proof (time-efficient)
3. Routing peers do not have to consume local storage to keep track of the proofs in each PubSub message

Disadvantages

1. Routing peers need to communicate with the smart contract per coming message, this increases communication overhead
2. Smart contract is somewhat a single point of failure
3. The publishing nodes have to wait for the state of the smart contract to get updated before sending their message through the Relay protocol (it can also count as an advantage where it slows down the spammers)
4. Peers have to take care of two additional pieces of secret data i.e., a_0 and auth_path (not exactly a disadvantage, but some new requirement)

---

Security Concerns
See the security concerns enumerated in vacp2p/research#49

---

Some thoughts

The proof of each message does not have to be verified by all the routing peers (as is the case in the current solution as well), as long as

1. the proof is validated once by the smart contract,
2. the validation is reflected in the contract's state (as part of nullifier_map)
3. and given that the integrity of the state of the contract is guaranteed
4. and everyone has access to the smart contract

---

Potential Enhancements

1. Local Nullifier Map: The nullifier_map can be removed from the contract and can be treated as a container for the registration Merkle tree. Routing peers maintain the nullifier_map and the root of the registration tree i.e., MT.root locally. This would allow them to verify proof of each routing query locally without interacting with the smart contract. The interaction may be needed just to update their local tree root. This alternative solution reduces the communication overhead and increases the computation overhead of the routing peers.
2. Certificate-based: One potential enhancement (which I am not sure about its implementation details) is that the publisher can obtain a signature from the smart contract (after proving her correct behaviour and not being a spammer) over the hash of her data, epoch and attaches that signature to the PubSub message. Subsequently, the routing peers do not have to contact the smart contract, instead, they only verify the signature and drop / route the message accordingly.

[oskarth]

Overall looks good! I think this can be turned into a raw spec already probably. Will need to think about some stuff in moree detail. Some initial questions and comments:

Additional fields for the PubSub messages. The following fields shall be added to the PubSub messages: [...]

1. Where exactly? Can we do this in the WakuMessage payload? If we want to build on GossipSub, there are some issues with adding additionally fields "on the outside" in Pubsub. See Waku v2 spec - split protocol ids up into three pieces #169 and Waku v2: PubSub Publish Message not data + Modify Message fields waku-org/nwaku#92 (comment)

2. Can these type of constructs be used for validation/dropping of messages? https://github.com/libp2p/specs/tree/master/pubsub#topic-validation and https://github.com/libp2p/specs/blob/master/pubsub/gossipsub/gossipsub-v1.1.md#extended-validators

For each incoming message, the routing peer contacts the smart contract, and checks whether internal_nullifier belongs to the nullifier_map:

3. Can this be cached? What are the consequences? What should happen if the node doesn't have access to the blockchain for some reason, and what would be a reasonable default?

[staheri14]

Additional fields for the PubSub messages. The following fields shall be added to the PubSub messages: [...]

1. Where exactly? Can we do this in the WakuMessage payload? If we want to build on GossipSub, there are some issues with adding additionally fields "on the outside" in Pubsub. See Waku v2 spec - split protocol ids up into three pieces #169 and status-im/nim-waku#92 (comment)

@oskarth I see your point, you are right, then we need to add these fields to the payload. Then, the routing peers (talking the Relay protocol) need to parse the payload as well to extract the proof metadata and identify spam messages.

[staheri14]

For each incoming message, the routing peer contacts the smart contract, and checks whether internal_nullifier belongs to the nullifier_map:

1. Can this be cached? What are the consequences? What should happen if the node doesn't have access to the blockchain for some reason, and what would be a reasonable default?

@oskarth Indeed! it can be cached, this is also mentioned under the first item of the Potential Enhancements of the current issue. From the security perspective, the lack of access to the blockchain does not make any harm, indeed any routing peer with a local nullifier_map and the updated MT.root is able to catch spammers (i.e., double messaging for the same epoch). To be more specific, the routing peer would never route two messages with the same internal_nullifier and hence can prevent spamming.

[staheri14]

2. Can these type of constructs be used for validation/dropping of messages? https://github.com/libp2p/specs/tree/master/pubsub#topic-validation and https://github.com/libp2p/specs/blob/master/pubsub/gossipsub/gossipsub-v1.1.md#extended-validators

@oskarth My initial guess is yes, we would probably be able to use these constructs, but I need to spend more time on this, I will get back to you with an informed answer.

[staheri14]

2. Can these type of constructs be used for validation/dropping of messages? https://github.com/libp2p/specs/tree/master/pubsub#topic-validation and https://github.com/libp2p/specs/blob/master/pubsub/gossipsub/gossipsub-v1.1.md#extended-validators

@oskarth Following your question about the usage of topic validators for RLN relay, I created an issue #255 for more concrete investigation.