RLN Fees distribution to operators with root voting

[alrevuelta]

TLDR: Proposal on how to distribute RLN membership fees to the node operators that submit the correct Merkle root
of the messages sent during a superepoch.

Problem statement

Waku has chosen Rate Limiting Nullifiers to rate-limit users, ensuring they do a fair usage of the network resources.
In order to do so, it requires users to pay for the so-called RLN membership, which entitles the holder to send a given
amount of messages per unit of time while its active.

However at the time of writting, the collected fees from RLN memberships don't have a designated purpose.
In order to ensure the sustainability of the network and reward node operators for their work, one option would be
to distribute them among node operators.

We define node operators as entities that participate in the network, running nodes and relaying traffic. They are
the ones that make the network work. A node operator is also a registered entity known by the waku protocol,
see more information below.

This issue proposes how to distribute the generated rewards by RLN memberships to node operadors. It does so by
rewarding the node operators that vote on the correct Merkle root for each superepoch. The root agreed by a 2/3
supermajority is considered the corerct one, and the nodes that voted on that get a reward.
This reward is a fraction of the fees that were generated from membership registration during that superepoch.
Since gossipsub scoring punishes lazy peers and incentivices peers to behave properly, we assume that knowing the valid
Merkle root implies having participated in relay protocol, which is the behaviour we want to incentivice.

Proposal

This proposal introduces the following concepts:

• 1. Node registration: Require node operators to register with a sybil-resistant mechanisim.
• 2. Superepoch: Defining a superepoch that matches the RLN membership renovation cycle.
• 3. Messages Merkle Tree: A Merkle tree with all messages within a superepoch.
• 4. Commit-reveal: At the end of the superepoch each operator can submit their local Merkle root of the Merkle tree containing all messages,
     using a commit-reveal mechanisim to prevent lazy nodes from copying honest ones.
• 5. Claim: The Merkle root voted by the majority becomes the accepted root for that superepoch, and every node is given /n
     the rewards from the subscription fees of that superepoch, where n is the amount of nodes that matched the majority.

Below, each point is ellaborated.

1. Node registration

Since anyone would be able to submit a vote on the Merkle root, we need some kind of pseudo-identity to sybil-protect the voting.
Otherwise the same entity knowing a valid Merkle root, defined as the one that represent a Merkle tree constructed by all messages within a superepoch
could vote multiple times, getting more rewards than it should.

A suggested mechanisim is to require a STAKE_AMOUNT for node operators, which provides an economic sybil-protection.
When an operator stakes this amount, it becomes eligible to participate in the voting and hence, eligible for rewards.
When the operator no longer wants to participate, it will be returned.
The stake can be slashed if they dont vote in SUPEREPOCHS_PENALTY consecutive superepochs.
Its yet to be defined if there would be other slashing conditions.

2. Superepoch

A superepoch is the time window used for voting. During each superepoch nodes construct a Merkle tree with all seen messages
and once finished, the Merkle root is calculated.

The superepoch matches the "billing period", see comment.
In other words, if 10 users paid an RLN membership for a given superepoch then all this generated fees are distributes
among the nodes operators that participated in this superepoch.

3. Messages Merkle Tree

For each superepoch node operators construct a Merkle tree with all the messages they have:

• Seen in the network. With the help of gossipsub scoring, we assume that a node that is able to see messages in the network is because its also relaying them.
  Otherwise its score would be penalized.
• Got from store and store sync. We acknowledge that nodes may have some downtime, so its accepted that some of these messages will come from store and not relay.
  A protection shall be added to discard "lazy nodes", meaning that they don't participate in relay but manage to get a valid Merkle root.

4. Commit-reveal

Since all onchain activity is public and anyone can see it, we propose a commit-reveal mechanisim to prevent lazy nodes
from sniffing the blockchain and copying the Merkle root of honest nodes.

Once the superepoch finishes, a window of COMMIT_WINDOW_SLOTS opens, during which all registered nodes can
submit their vote on which root they consider to be valid for that superepoch. What the node operators commits to (aka commitment)
is a secret, in this case the root. The commitment is hash(root + salt). That would be public but since getting the preimage
of that hash is not possible, an attacker won't be able to reveal in the next phase.

Once the COMMIT_WINDOW_SLOTS is due, no more votes are accepted for that superepoch and a REVEAL_WINDOW_SLOTS window is opened.
During this window node operators can reveal their secret. If the provided root during the reveal phase matches hash(root + salt), then their
vote would be accepted.

Finally, once REVEAL_WINDOW_SLOTS is due eligible node operators can claim their share of the reward. See next section.

5. Claim

After REVEAL_WINDOW_SLOTS the commit-reveal phase is done and votes are counted. An example:

• node0..4 (5) voted on root root1.
• node5..24 (20) voted on root root2.
• node25 (1) voted on root root3.
• note26..30 (4) did not vote.

As explained before, node operators are registered beforehand in the contract a priori so the total amount of votes are known.
The previous votes can be written as [num_votes, root_n] or [5, root1], [20, root2], [1, root3], [4, NaN].
With the votes, a simple 2/3 consensus of a supermajority of 66% is used to decide which root to accept.

The weights would be:

• root1 5/30 = 16%
• root2 20/30 = 66%
• root3 1/30 = 3%

This means that root2 is accepted onchain as the Merkle root of all the messages seen during the superepoch.
Nodes that voted for that root are eligible for rewards.
The amount to be distributed is calculated as the amount of memberships * price paid for each membership for each superepoch.
If 100 active memberships were active and each one paid 10 tokens/superepoch, then the amount to spit is: 100 * 10 = 1000 tokens.

Membership fees would be split among the nodes that voted the agreed root, aka root2 meaning, 1000/20 = 50 tokens for node5..24.

Note that a node operator that does not vote during SUPEREPOCHS_PENALTY can be slashed by anyone, as this information is accesible onchain
by anyone. The whistleblower will get WHISTEBLOWER_REWARD which is <=STAKE_REQUIREMENT and the node will no longer be part of the
active node operators.

In order to make it gas efficient, each node operators rewards can be claimed at any time.
For each superepoch the claimable amount keep accumulating, so that the operator can claim their rewards of multiple superepochs at once.

Consensus

An interesting side effect of this proposal is that it introduces an onchain consensus of the messages sent for each superepoch.
This would allow light clients (eg filter) to verify that a given message was indeed sent through the network, since the onchain root
can be used.

Open problems

This proposal has some open problems:

• Handle lazy nodes, defined as entities not participating in relay but somehow getting a valid Merkle root.
  They should not be eligible for rewards.
• Handle nodes registering multiple stakes. An operator running just one node could stake STAKE_AMOUNT for multiple node operators.
  This will allow it to vote multiple times but its only doing the work of one node.

[SionoiS]

Just to state the obvious, this assumes that we collect fees otherwise it can't work long term.

we need some kind of pseudo-identity to sybil-protect the voting

Do you think it would be economically viable to register 2/3 of ALL possible memberships and control the vote to get all the fees?

A protection shall be added to discard "lazy nodes", meaning that they don't participate in relay but manage to get a valid Merkle root.

Waku Sync could be used to get the correct Merkle root without using Relay at all. I'm not sure we can prevent that. 🤔

a simple 2/3 consensus of a supermajority of 66% is used to decide which root to accept.

What happen when no majority? Do fees just accumulate?

Note that a node operator that does not vote during SUPEREPOCHS_PENALTY can be slashed by anyone

To me it feels unnecessary, is the lack of reward not penalty enough? It would allow superepoch to not have votes and for rewards to accumulate. It would be good to have a mechanism that can allow skipping superepoch when the fees are not high enough but maybe it makes the system too gameable?

Maybe instead of voting, let people gamble on the correct merkle root? Stake/Vote -> Bet, Reward -> odds of wining.
No idea how to determine the truth though... 🤔 🤷

[alrevuelta]

Do you think it would be economically viable to register 2/3 of ALL possible memberships and control the vote to get all the fees?

This is one of the issues that "1. Node registration" should address. In Ethereum this was solved by requiring a minimum amount of operators to stake first. Without this minimum amount of operators MIN_GENESIS_ACTIVE_VALIDATOR_COUNT, the protocol could not launch. Since the participation was open to anyone, and the stake was considerable, the diversity was quite good, but at some point an entity controlled around 30%.

Waku Sync could be used to get the correct Merkle root without using Relay at all. I'm not sure we can prevent that. 🤔

Perhaps with a rate limit. Its okay to get some messages via waku sync (eg if you are offline for some time) but it shouldn't be possible to purely rely on waku sync. Another option (largely vague) is to mix service incentivization here. Meaning store sync will only work if you pay a small fee (see service incentivization).

What happen when no majority? Do fees just accumulate?

No majority can happen in two scenarios: i) nodes strongly disagreeing in the root or ii) a bunch of nodes not voting. For ii) we can heavily penalize that since that hinders consensus. For i) tbh to be defined.

To me it feels unnecessary, is the lack of reward not penalty enough? It would allow superepoch to not have votes and for rewards to accumulate.

I would say penalizing here mitigates the ii) from the previous point.

[fryorcraken]

Looks good to me. Very exciting.

Yes, there are some unknown and risks. Let's do the work so we can confirm viability (or not) of such a protocol.

One potential issue is ephemeral messages. They should probably be discarded from the Merkle tree as it is not possible to use store/store sync to double check none were missed

Few thoughts regarding gaming this by relying on store sync:

• If the superepoch is greater than the retention of most store, then it would not make it possible for someone to step in and back track enough to get the merkle root.

• Hence, one would need to use store sync on a regular basis to sync all messages (instead of using RLN Relay).
  I wonder if purely by having some sane rate limits on store, this can be prevented.

• Also, I believe store currently does not store RLN proofs. So there may be some potential issue here, when doing store sync, how can you be certain that the messages you are given are legitimate?

• Maybe getting the RLN proof with store queries could be a more expensive service, app users should not need that, but those participating in this protocol would want to be sure the message should be included.

[chaitanyaprem]

I like the overall approach as it resembles very closely of the pattern that is being used in previous project that i worked on.
I am wondering if we could leverage and integrate with that project (or reuse modules/research already done) which might help us as they are solving/have solved similar problems.

Few observations.

In other words, if 10 users paid an RLN membership for a given superepoch then all this generated fees are distributes
among the nodes operators that participated in this superepoch.

Wondering if pro-rating of rewards would be requried as node operators can join the network at any point in time.

For each superepoch node operators construct a Merkle tree with all the messages they have:

Since in relay network message ordering is not gauranteed, how would this merkle tree look like as the root would keep changing based on order of insertion. Instead of a merkle tree, could we instead use sync state datastructure which is used by RBSR (as it is resilient to ordering)

As explained before, node operators are registered beforehand in the contract a priori so the total amount of votes are known.

this essentially means total votes to be considered for counting and majority would change per superepoch right.

[SionoiS]

• Hence, one would need to use store sync on a regular basis to sync all messages (instead of using RLN Relay).
  I wonder if purely by having some sane rate limits on store, this can be prevented.

We could not use the hash of the actual message for sync and instead use a different hash that is not used by the consensus mechanism.

[alrevuelta]

@fryorcraken

One potential issue is ephemeral messages. They should probably be discarded from the Merkle tree as it is not possible to use store/store sync to double check none were missed

Good catch. Yep, they should be discarded from the Merkle tree.

@chaitanyaprem

Powerloom

Will check, interesting.

Wondering if pro-rating of rewards would be requried as node operators can join the network at any point in time.

Haven't thought much about it, but most likely yes. I'm afraid though this calculations may consume too much gas. Ideally billing periods should go together with the superepoch but if someone registers the last day before the superepoch finishes, what happens? Does the user has to pay for the full period? No. Does the user pay for just 1 day and then the next superepoch(s) will match the billing period? Maybe yes.

Since in relay network message ordering is not gauranteed, how would this merkle tree look like as the root would keep changing based on order of insertion. Instead of a merkle tree, could we instead use sync state datastructure which is used by RBSR (as it is resilient to ordering)

I was thinking about ordering the leafs according to some criteria. Eg by timestamp and by hash (alphabetically). In that case the order would be deterministic and the root as well. You may receive an out of order message that you can insert in between wherever is its place. Does the datastructure you are referring to contain some kind of representation of all the content (eg like merkle root)?

this essentially means total votes to be considered for counting and majority would change per superepoch right.

Yep. New operators can be added (+) or operators can be slashed (-) or leave (-). Slightly related, Ethereum has a queue mechanism so that even if you have lots of capital to deploy (spawn new operators) you can't do it instantly. You have to wait an entry (and exit) queue. Its a protection.

[SionoiS]

I was thinking about ordering the leafs according to some criteria. Eg by timestamp and by hash (alphabetically). In that case the order would be deterministic and the root as well. You may receive an out of order message that you can insert in between wherever is its place.

That's basically what Prolly trees are.

[chaitanyaprem]

I have been giving it more thought on fee distribution to operators and the approach we are thinking of above. Dropping some more thoughts here, not sure if we need to have solution to start with or some of these should be thought at a later stage but writing them anyway.

Waku's aim is to build a p2p network where users and operators can operate in adversarial conditions (different than other p2p networks like ETH where currently they are currently designed for ideal conditions i.e node always online, not censorship resistent etc). This means that the conditions are not ideal either for users or node operators(i.e network maybe always available but nodes may not be due to various reasons which means it may not be able to function at 100% all the time).

By designing a reward system for operators who validate and relay all the messages that pass through the network, we are expecting all operators to be available 100% of the time relaying messages.
If we take this approach, will we be end up hurting the operators who run the nodes from home where stability is not as guaranteed as nodes running in cloud service provider. Will we be forcing operators away from decentralization as this would push operators to run node on cloud providers only?

Should we consider an approach where operators are rewarded based on percentage of messages they were able to relay? I am not saying we should reward even if someone relays only 1% of messages, but rather than expecting 100% relaying should we look at some approach where incentives are given in other manner. Again this goes against my point above, because by incentivizing in this model we may be pushing operators towards utilizing a more centralized infra.

Alternatively how about a mechanism which randomly verifies if an operator is validating and relaying messages? Maybe similar to a mechanism which filecoin network uses for Proof-of-SpaceTime. In Proof-of-SpaceTime, random checks are done for parts of data that are expected to be stored at frequent intervals which prove that data is still being stored rather than checking for all the data that is stored all the time.
Can we think of a mechanism on similar lines that can just verify that a node is validating and relaying messages by being able to do that with some sort of a part verification rather than verifying if the node has relayed/validated all messages in the network?

[jm-clius]

Thanks for the issue write-up!

I think your "open problems" summarise what our next research focus should be. In particular, a potential no-go would be if we can't find an elegant solution for:

Handle lazy nodes, defined as entities not participating in relay but somehow getting a valid Merkle root.

A node wouldn't even need to use Sync to be able to track the Merkle root without actually contributing - you could simply run as a relay "sink" (with a few in connections and no out) without actually relaying messages or providing other services. I like the direction that @chaitanyaprem suggests - random checks to verify that a node is actually contributing to the network. It may help here to consider Sync as an integral part of the routing fabric of the network. In other words, we may expect operators participating in the fee rewards to run the trifecta of RLN + Relay + Sync - at the very least they would have to respond to Sync requests (as it may be difficult to "prove" that a node is actually relaying and not just storing messages).

Should we consider an approach where operators are rewarded based on percentage of messages they were able to relay?

Presumably, if we consider Sync an essential element here, we could expect of nodes to know about all messages. Perhaps a random check to show that expected messages are stored combined with a Merkle proof?

[alrevuelta]

@chaitanyaprem

different than other p2p networks like ETH where currently they are currently designed for ideal conditions i.e node always online, not censorship resistent etc

Note that eth is designed for very adversarial environments and nodes are not expected to be online. The incentives make them stay online, but the network can handle eg 50% nodes offline. Some non-finality period will start and penalties will kick out nodes that are not attesting.

By designing a reward system for operators who validate and relay all the messages that pass through the network, we are expecting all operators to be available 100% of the time relaying messages.

Good point. I would say its not 100% whats required, since you can be 90% up and get what you are missing via store sync (eg restart for an update). But I get the point.

Should we consider an approach where operators are rewarded based on percentage of messages they were able to relay?

I'm open for this, but not sure how it can be technically done. How can you prove that you have relayed "some" messages? I think hopr has something related to this, proof of relay.

Alternatively how about a mechanism which randomly verifies if an operator is validating and relaying messages? Maybe similar to a mechanism which filecoin network uses for Proof-of-SpaceTime

The random checks idea is interesting, will explore.

@jm-clius

A node wouldn't even need to use Sync to be able to track the Merkle root without actually contributing - you could simply run as a relay "sink" (with a few in connections and no out) without actually relaying messages or providing other services

Aren't we protected with gossipsub scoring from this?

I like the direction that @chaitanyaprem suggests - random checks to verify that a node is actually contributing to the network

Sounds interesting. Any idea on which challenge to randomly run? imho the hard thing here is that if the challenge implies "being right on something" that's tricky, since we don't have consensus, hence its not possible to verify it correct.

[chaitanyaprem]

Note that eth is designed for very adversarial environments and nodes are not expected to be online. The incentives make them stay online, but the network can handle eg 50% nodes offline. Some non-finality period will start and penalties will kick out nodes that are not attesting.

right, doesn't that mean validators are expected to be always online i.e 100%?

I'm open for this, but not sure how it can be technically done. How can you prove that you have relayed "some" messages? I think hopr has something related to this, proof of relay.

proof of relay was interesting read, Thanks!

Instead, since gossipsub already has very detailed scoring mechanism that penalizes nodes for non-effective participation when they are online, i was wondering if we can somehow leverage that. Will think more on this problem though, this is just an initial thought.
What if each node somehow indicates based on gossipsub score that a peer was available and relaying messages effectively. And if such indications are received from some n number of nodes for m times in a week/superepoch or some other duration we can think of, can we consider that node was able to do its job of relaying(maybe not 100%, but at some degree - was thinking some sort of thresholds to scores can be used in determining this)?
This also acts as an indirect random check for the node.

Maybe this somehow can also be added to the node's reputation apart from service protocol specific reputation? wdyt @s-tikhomirov

[s-tikhomirov]

I think hopr has something related to this, proof of relay.

From what I understand, HOPR is similar to Lightning in that it uses onion routing and hashlocks to make payment conditional on delivery of data. AFAIU, this scheme is suitable for a point-to-point communication, where first a path is established, and then the message is onion-encrypted using public keys of nodes along the path. Our use case, in contrast, has a broadcast communication pattern, therefore I'm not sure proof-of-relay is well-suited here. I'd be happy to be proven wrong of course.

I've also been preparing a more detailed reply to this discussion, will post it as a separate message.

[jm-clius]

if the challenge implies "being right on something" that's tricky, since we don't have consensus

No design in my head, but if we can reach some consensus on the message hash root for a superepoch (using your proposal), I guess a node could potentially be challenged to prove that they're storing random messages in this superepoch with a Merkle proof to the (consensus) root.

Aren't we protected with gossipsub scoring from this?

True. I misstated a problem we had with Relay "leeches" earlier - nodes that are not publicly reachable and only make a few outgoing Relay connections (the number of which they control). They observe gossipsub rules on these connections, but essentially provide nothing to the network since they only consume connections. In other words, they don't enrich overall connectivity by being discoverable and allowing incoming connections. Hence my entertaining the idea of combining this with at least some verification that the nodes provide a public service that contributes to the routing infrastructure (i.e. Sync in this case).

This ties into another difficulty: the overall aim of a resilient relay infrastructure is to disperse the infrastructure as much as possible and increase the number of node operators. Everyone participating in a reward sharing scheme, however, is in essence incentivised to keep the topology as constrained as possible (fewer nodes = more reward). It is possible, as explained above, to be a perfectly good gossipsub node, but artificially limit the connectivity in the network to keep new operators from joining.

[alrevuelta]

No design in my head, but if we can reach some consensus on the message hash root for a superepoch (using your proposal), I guess a node could potentially be challenged to prove that they're storing random messages in this superepoch with a Merkle proof to the (consensus) root.

I see. This addendum can fix the "lazy operator" issue, and moreover it prevents people from relying and not storing the messages. But this overlaps relay and store protocols. I mean, this proposal aimed to incentivize relay, not store. So not sure if we are mixing things? Or well, maybe relay and store can go together?

As a side note, another problem is how to act upon the challenge. NodeA challenges NodeB. Is the challenge result stored onchain? (probably not since that will consume to much resources). Or this information affects gossipsub scoring?

[mart1n-xyz]

This ties into another difficulty: the overall aim of a resilient relay infrastructure is to disperse the infrastructure as much as possible and increase the number of node operators. Everyone participating in a reward sharing scheme, however, is in essence incentivised to keep the topology as constrained as possible (fewer nodes = more reward). It is possible, as explained above, to be a perfectly good gossipsub node, but artificially limit the connectivity in the network to keep new operators from joining.

I think there is more nuance here. As a node, I prefer to have a larger node set as that increases the size of the pie of rewards. However, I want these nodes to be poorly connected, not to be able to vote for the "correct" merkle root and claim rewards.

Some ideas and comments:

• I assume the proposal gives equal voting power to all nodes. One could also play with this in a way where new nodes initially get lower voting power and it grows towards some limit over time - to promote network resilience. This does not solve the "joins later" issue. However, coupled e.g. with a lower slashing rate that again increases over time (say 75% -> 100%) could limit the financial risk for the new node of getting the initial superepoch proof wrong.
• One idea of solving the "joins later" issue that comes to my mind is to actually have two merkle roots to vote on. The first being the one described above. The second being constructed as follows:
  • Messages are split into blocks of desirable granularity within a superepoch
  • For each block, a block merkle root is constructed as described above
  • These roots are inputs to yet another merkle tree whose proof is part of the tuple that is voted on.
  • In this scenario, new nodes are allowed not to vote and submit only a single (or multiple) block merkle root that would be verified against the second merkle root and they would be rewarded for the appropriate portion. There's a bunch of caveats here but that's the gist of it.
• I think we should also bring identity into this discussion. By voting and claiming onchain, a node de facto becomes associated with an address (plus registration can involve registering a public key) and I am wondering if this can leveraged somehow for the "proof of relay" alternative or random checks.