Accounting for resources in Waku and beyond

tldr: accounting for resources proposal and example

Motivation

In an open p2p network, certain valuable services are provided. While some nodes might choose to be altruistic, these services are not cost-free. Owing to this fact, there’s a natural supply and demand of these services in a network. We propose to capture this resource usage with an accounting mechanism. This is prerequisite for incentivization. It is the underlying structure that forms any incentives or disincentives. Later on, this can be extended through settlement and policy changes.

Accounting in Bittorrent

One basic example of accounting in a p2p network is Bittorrent. Here is how accounting works in BT, in a nutshell:

  1. Nodes upload and download chunks of a specific, valuable, file together in a swarm.
  2. A node wants to download a specific chunk, and it values other nodes sharing it.
  3. Uploading a chunk to another node brings a cost, and no direct benefit.
  4. The ratio between providing and extracting (upload/download) is called a seed ratio.
  5. A node can choke (not upload to) another node that doesn’t upload back.
  6. Choking uses tit-for-tat, where nodes trust at first but then penalize bad nodes.
  7. This tit-for-tat game, and the knowledge for it, is only local to a specific torrent.
  8. A user running a node can leech a torrent - download it quickly and then run.
  9. To discourage many torrents, private trackers have a global seed ratio.
  10. This seed ratio is self-reported and cross-checked against other nodes’ reports.
  11. If this seed ratio is too low, or node is lying, the private tracker can punish the user.
  12. Punishment for private trackers means restricting access to valuable torrent files.

This system does two important things:

  1. Accounting: It accurately identifies and accounts for the resources involved (upload/download BW)
  2. Policy: It encourages the right behavior by rewarding good behavior and punishing bad behavior

Notice how it doesn’t involve any form of monetary settlement, that is converting resources into cash. If we wanted to we could extend this system, but there’s no requirement to do so.

Waku

Based on the above, we have a blueprint for how to do accounting for resources. However, for Waku the domain is slightly different. Here’s how we might go about it. First, we need to answer the question:

What are the types of actions a node can take?

These are directly reflecting the capabilites a node has (see https://github.com/vacp2p/specs/issues/87):

  • sending messages
  • receiving messages
  • relaying messages
  • bootstrap nodes
  • store historical messages and return them on request

A natural follow up question to this is:

Of the actions a node can take, which actions are contributions or costs for the network?

  • Sending a message is a cost to the network, because it is extra work nodes have to do that they don’t directly value. It is valuable to the node sending a message. (It is also, sometimes, valuable to the receiver).

  • Receiving a message is a neutral action as it is a passive result of being relayed messages one is interested in.

  • Relaying a message is a small cost to the node doing it. It is somewhat valuable to the node requesting to be relayed such messages, though usually in an indirect way (see example below). It is indirectly valuable to the end sender and receiver, but in many topologies - including the existing one for Waku - these aren’t directly known.

  • Bootstrapping other nodes is a valuable contribution to the node that is being served with other nodes. It is fairly low cost though and not generally a bottleneck, so we’ll ignore this one for now.

  • Storing historical messages for other nodes and returning them on request is a valuable contribution to the node requesting them. (It is also, sometimes, valuable to the sender).

We might notice that these contributions and costs aren’t equal. For example, storing a message depends on its size and duration of storage. Based on this, we can assign these actions some weight. In an ideal system, these prices would be discovered and set by the market in a Hayekian fashion.

Waku - Worked example

Let’s make the above more concrete with an example. Let’s start by assigning weights and who might be credited / debited for each action. Then we’ll look at an example of how things might work in a specific scenario.

Weights

  • send: -10
  • receive: -1
  • relay: +1
  • bootstrap: 0
  • store: +10 (leaving out variablity for now)

Now, for this to be a proper accounting scheme we need these to balance out, like credit and debit. In some cases this is easy - a node storing historical messages should obviously be rewarded for its services. In the case of a node sending a message, shouldn’t everyone involved in delivering the message be rewarded? More on this later.

Concrete scenario

We have two light nodes two full nodes. A light node can only send and receive messages. A full node can do everything. They are connected in the following topology:

L1 <> F1 <> F2 <> L2

Let’s say L1 wants to send a message to L2. Let’s further assume L2 is initially offline. What does the accounting look like? Like Bittorrent, we want nodes to act on local knowledge and to keep an internal, pairwise, accounting balance. For brevity, we assume nodes all report the same numbers. We simplify this with a “global view” of the current account balances.

  1. L1 and L2 discover F1 and F2, respectively. F1 and F2 are already connected (-)
  2. L1 sends a message through F1 (L1 -10, F1 +10) [1]
  3. L1 relays a message to F1 based on F1’s interest (L1 +1, F1 -1) [2]
  4. F1 relays a message to F2 based on F2’s interest (F1 +1, F2 -1)
  5. L2 comes online and requests a historic message from F2 (L2 -10, F2 +10)

Net account balance:

L1: -10/+1 = -9
F1: +10/-1 = +9
F2: +10/-1 = +9
L2: +10/ = -10

In sum, we have two light nodes that are leeching of the network, and two nodes that help the network. In general, even though the forwarding costs F1 and F2, we can assume a form of steady state, where the inflow and outflow of relaying roughly adds up.

It is important to note that a node only has local information, and keeps track of their own accounting with the nodes they do business with.

What problems are we solving?

Accounting is just the first step. It allows us to rigorously identify good and bad (or costly) behaviour. Let’s look at a few behaviours we might observe:

  1. If a node is spamming several new messages, this is costly.
  2. Nodes that relay messages and store historical messages are rewarded.
  3. The more messages a node receives the more it costs.
  4. If node A knows another node B will likely ask for historical messages in the future, it can do arbitrage by asking a node C for more recent messages (assuming variability w.r.t. age).
  5. If two full nodes “in the middle”, like in example above, relay messages then this flow should even out in a form of a steady state (relayed in ~= relayed out).
  6. If we have two self-reports, this can inform other decision making (arbitrarion etc).
  7. Even simpler, self-reports allows local nodes to decide on their own policy 100% voluntarily, e.g. disconnect leeching or uncooperative nodes.

It doesn’t address:

  1. Proving end to end delivery or rewarding every hop in a send action. This likely isn’t doable at this layer with this gossip like topology, but different topologies might enable this enhancement. See [1].
  2. How a new message is identified. Self reporting among sender and receiver is the natural first step here. Conflicting information can inform policy and decision heuristics for settlement. It can also be extended with a proof later on.
  3. Settlement or policy based on accounting. More on this in a different post.

Next steps

  • Further discussion and input
  • Basic spec (the existing one in Waku is too simplistic)
  • PoC with relevant metrics for self-reporting in clients
  • Extend simulation with this
  • Further research into accounting mechanisms
  • Sketch of basic policy and settlement design
  • Further validation/interplay with digital double (e.g. Block.science etc)

Misc references

Notes

[1]. Why do we reward F1? For simplicity. This is the only local information L1 has, and F1 is helping it get its message out into the world. Under different topologies with different assumptions this might look different. Another simple alternative here is to burn a token of some kind. Also see [3] and [4] for postal system and stamps.

[2]. This could be optional. Depending on how much we want to - or are able to - distinguish relaying of messages from sending, this may or may not be optional. It might seem weird that F1 would pay, but it has expressed interest in these types of messages, so L1 is doing F1 a “favor” in that regard. On net, F1 comes out ahead if it also gets a piece of L1’s “sending” pie.

[3]. Even for regular mail there’s rarely any end to end guarantees. Instead, you know that a certain type of service is reliable, and if it isn’t you switch. This is similar to peer rating. Additional guarantees instead happens on top, in terms of insurance or fines for postal service if letter arrives too late, etc.

[4]. In fact, this is exactly how the postal system for international mail works. For international mail, your stamp money goes to the sender country. Settlement between intermediate destinations was only added after more than a hundred years of service (the current system is from 1969), and even the it is primarily based on quarterly settlement of imbalance (aka accounting).

It sounds reasonable that we should measure resource consumption, but seems like we are not addressing/explaining how we are solving the problem, but we are making an assumption that resource accounting is going to play a role in it: “This is prerequisite for incentivization”.

In fact, this is not true in one of the few successful network incetivization system out there (DASH), where nodes are not rewarded based on resource consumption. Also we worked on this before and the model proposed did not use resource consumption as a basis, we also have(had) a working POC merged in the app https://discuss.status.im/t/network-incentivisation-log/1173 . Which has some advantages (better abstraction from the services provided, simpler), and some disadvantages (imbalances in resources, possibly higher entry bar).

By all means we should/could track this metrics if we wanted to, as it does not hurt, but before we should have a clear strategy on how to solve the bigger problem, then we can think of possible solutions.

To put in feature terms, maybe is easier to communicate what I mean :slight_smile: , this looks like a subtask in the user story:

“As a x I want to be rewarded for my services So I can earn money/resources by participanting in the network”

  1. Track consumption

But the rest of the card is basically empty, I think we should fill up the card first with a coherent and sound strategy, and then derive an implementation, rather then let the implementation drive the solution, if you get what I mean.

What does a litenode relay?

1 Like

Apologies in advance for the long reply.

Let’s get some definitions cleared up first.

Definitions

What is accounting?

Accounting or accountancy is the measurement, processing, and communication of financial and non financial information about economic entities[1][2] such as businesses and corporations.

What do we measure? How do we process it? How do we communicate it?

What is policy?

A policy is a deliberate system of principles to guide decisions and achieve rational outcomes.

What is settlement?

Settlement of securities is a business process whereby securities or interests in securities are delivered, usually against (in simultaneous exchange for) payment of money, to fulfill contractual obligations, such as those arising under securities trades.

Slightly misleading definition because it is finance-oriented. Key is that getting e.g. payment of money in exchange of fulfilling a contract. A contract is, roughly speaking, an enforceable promise in exchange of some service involving some agents).

What is a resource?

a stock or supply of money, materials, staff, and other assets that can be drawn on by a person or organization in order to function effectively.

What is a service?

the action of helping or doing work for someone.

I used “accounting” and “service” interchangeably somewhat sloppily. The key that service is what you do and want, and some form of resources (regardless of granularity) is how you go about it. I would’ve hoped this was apparent from reading the examples and engaging in a charitable interpretation, but it could’ve been stated more clearly.

Accounting

You say that accounting for resources/services isn’t used in DASH. You also seem to see DASH as one of the few successful network incentivization systems out there.

Both of these statements are either wrong or misleading. While it is true that DASH doesn’t directly measure something narrow as “bandwidth usage” or “CPU time” (actually, it is still a PoW chain isn’t it?), it does do accounting as per the definition above.

As for it being a success and something that has stood the test of time, I guess that’s debatable. In any case - in the computer network p2p world - Bitcoin and Bittorrent are clearly more successful. They are both networks, and they both have incentives and disincentives. Even further, all markets in the physical world can be seen as networks (agents interacting with each other in some fashion), and they definitely have incentives and disincentives (hello money and policy). In terms of the domain - messaging - being more similar, an excellent example is the postal network, which has existed in the modern world for hundreds of years. It’d be wise to learn from it, since it has stood the test of time, and shares many similar attributes, challenges and incentive structures as a largely decentralized service network.

In OP we saw Bitorrrent as a an example, and then we looked at an example for how it could look like for Waku. Let’s look at Bitcoin and DASH as further examples.

(Simplified) Bitcoin accounting model.

  1. A node values sending money and it broadcast a transaction to the network with a fee attached to it

  2. The transaction fee acts as an encouragement for miners to include it in the next block

  3. Miners compete using proof of work to create block with some set of (valid) transactions

  4. Since space is limited, transactions with the highest fee get included in the block

  5. The miner which has spent the most CPU power on block will probabilistically win

  6. If a miner’s block gets chosen, they get a fixed block reward and transaction fees

  7. This acts as a schelling point and ensures there’s a single longest chain

  8. A single, valid and secured (with pow) chain is valuable to nodes with UXTOs/assets in it

  • Accounting: it accurately identifies and accounts for the resources/services involved - nodes want the chain to be secure and transactions to go through, miners computes pow for compensation. Transaction fees are used for transactions (variable depending on supply and demand); computing pow (variable) to secure the network. (Additionally, miners also want the chain to be secure since settlement happens in-band)
  • Policy: It encourages and discourages the (by system design) right behaviors - high txfees more likely to go through; highest pow more likely to win; even with 0 txs the network gets secured; double spending is prevented by miners validating blocks and having a single chain
    low tx fee txs less likely to go through; lower pow (less secure) less likely go win
  • Settlement: at block reward for the longest chain time for (node -txfee, miner +block +txfee). Note that just sending a transaction (stuck in mempool) or finding a correct block isn’t enough, it has to actually be chosen.

Ethereum has a similar model right now, except it extends the transaction fees into a generalized gas concept for computation. How is gas cost calculated? Through gas price (variable) and accounting for computation done (fixed by operation, see fee schedule etc in https://ethereum.github.io/yellowpaper/paper.pdf).

Dash example

What does DASH do? It extends this under the premise that: Bitcoin full nodes have been decreasing, and block propagation times have been increased (https://github.com/dashpay/dash/wiki/Whitepaper#2-masternode-network). As an aside, I couldn’t find any soldi historical data on block propagation time (especially one that takes block size into account), but here are the number of full Bitcoin nodes over time:


(https://www.researchgate.net/figure/Evolution-of-basic-statistics-for-the-four-Bitcoin-network-representations-A-number-of_fig1_334316616)

I might be missing something, but I curiously don’t see the decrease. Anyway, For Ethereum this is a problem, especially when it comes to allowing light nodes to connect (no incentive to serve data). In any case, DASH wants to solve it. What does it do?

(Very simplified) Dash masternode accounting model. I haven’t studied it in detail, so some things might be wrong:

  1. Similar to Bitcoin, in general (fork). It is a two-tier model which attempts to account for things the Bitcoin network doesn’t do already (private transations, instant transaction and “governance”).

  2. Masternodes provide a level of service and are required to stake to participate

  3. Services include private send / instant send and governance services, fees are listed here
    https://docs.dash.org/en/stable/introduction/features.html#fees

  4. In return they get 45% cut of the block reward

  5. There is a notion of Proof-Of-Service to guarantee that masternodes provide some service. It checks if the nodes are online, active and have the right blockheight.

Similar to Bitcoin it its first tier (with miners etc), with some differences.

  1. Accounting: it (somewhat? maybe?) accurately identifies and accounts for the resources/services involved - Masternodes ping each other to make sure only good nodes are active and use that information for a consensus model. Users pay some fee for certain services it values. Masternodes get to participate in government decision (voting on x) and get compensated for being of use, where being active is defined roughly as being online and having some blockheight. (It isn’t clear to me how it encourages masternodes to behave (other than be online), but perhaps this is specified somewhere).
  2. Policy: Bad masternodes gets removed from list off active nodes (and slashed?) in a self-policing global (?) fashion. Low fees don’t get included. Masternodes get to participate in government decisions.
  3. Settlement: Per block reward, active masternodes gets 45% of block reward, split up over list of active bootnodes [which is determined in some fashion].

Strategy

Strategy on how to solve the bigger problem

Aside from what is mentioned in the motivation, I would’ve expect more back “yes, and” responses where we build on this framework together. The worked example is just that - an example. Further, analyzing the accounting choices through various lenses (napkin examples, game theory, simulation, agents with various profiles) and being more critical about assumptions (problem? solution: proof-of-x!) we need, can do without, would help us, etc.

We have already started doing this in an ad hoc way, where we are rate limiting peers (accounting+policy). There are also other ways of making this contribution more explicit, a la Tribler’s trust graph, etc.

As for the network incentivization log, I’m aware of it and I looked at it as recently as this week.

Cards

Here are some, in case it isn’t obvious what problems we are trying to solve, and more importantly enable solving.

As a Vac contributor I want to make accounting for resources and services be explicit, so that I can observe the health of the network and how nodes contribute and detract from it

As a Vac contributor I want to have a clear and explicit framework for service usage so that I can quickly and rigorously analyze it, compare it with other solutions, change it and play around with it, for example in simulations, formal analysis and game theoretical explorations

As a Vac contributor I want to lay the empirical groundwork and framework for any further policy and settlement protocol changes

As a Vac contributor I want to enable policy and settlement in the network, so that we can build a sustainable, open, user-operated, resiliant and decentralized network

As a user I want to be rewarded for running a node so I can earn money/resources by participating in the network

As a user I want the network to keep running even if e.g. Status Gmbh and its clusters shut down so that I can keep using it

As a leeching user I want a way to support the network so that it keeps running

As a Status contributor I want the network to be scalable and user operated without centralized costs such as cluster operation, so that the network can handle load and not cost too much money

As a Status contributor I want to see clear description and rationale for how accounting is done, so that I know the design accounts for factors that I think are relevant, so the ultimate implemementation is sound and general and unlikely to change materially

As a Vac contributor I want to ensure accounting is done properly first, before jumping to policy and settlement, so we don’t waste time on implementations that don’t work

As a user I want the network to account for users spamming the network, and ultimately ensure this doesn’t happen, so that I can enjoy the network

As a mailserver node operator I want to an incentive compatible way to store and fetch historical data so that I can profit from replicating data so that my users can get their service expected

As a Vac contributor I want an accounting method that is local and doesn’t rely on centralized consensus models unless strictly necessary (double spending), so that it the model is robust (not fragile to random events) and be used in as many network environments possible (including offline ones)

I could probably go on, but that’s a start. I hope you get the gist.

Thanks for the question. It is indeed ambiguous and somewhat inconsistent, see footnote 2. I don’t know to what extent we want to call light nodes “relaying” vs just “sending” (can we distinguish? do we want to?). For simplicity and consistency, that event can be removed. The key thing I wanted to capture there is F1 having already declared interest in being “relayed” messages of a certain topic (in our case), and that this is a general notion. Open to ideas on how to best frame that. Also see the ongoing discussion here: https://github.com/vacp2p/specs/issues/87

First of all, apologies if the reply sounded harsh and not propositive, wasn’t my intention to come that way.

What I wanted to communicate is that I feel we should adopt a model where we track coarser metrics (for example being online, as probably a pre-requisiite for most services, to start with and use it as our bedrock to build a Proof of Service network.

On top of that we could track Quality of Service metrics for accounting not just by neighbours but by any active participants in the network, chosen randomly at periodic intervals, and derive policies and settlements from there. This is what we basically discussed previously in the network incentivisation initiative.

Basically I would have metrics such as:

relay/end2end delivery (as you mentioned this is not straightforward given the current network topology, but we probably can come up with some approximation)
completeness of storage (currently historical nodes are useful if they store all or most messages, having gaps is problematic, so store only might not be necessary enough for being rewarded)
Online time

Eventually we would like also to have ethereum blockchain information so that we can query those nodes and avoid hitting infura and truly be independent from third party services other than the ethereum network. At which point we can add the relative accounting metrics & derive the related policies.