Earendil: an uncensorable decentralized network (2/3)

In an earlier blogpost, I introduced Earendil, a work-in-progress Mel-secured communication network that's both decentralized and very difficult for powerful network adversaries (like China's Great Firewall) to detect or take down.

In this blogpost, I'll talk more about the incentives behind Earendil — how people contributing to Earendil infrastructure get paid. As a side effect, the incentive system we design also makes Earendil an efficient off-chain money transfer network rather than merely a data transfer network.

A free market in resources

The basic principle behind Earendil incentives is to build a node-to-node resource market: when Alice uses up resources owned by Bob (say by sending traffic through him), Alice pays Bob his asking price. If Alice finds Bob's price too high, she can try to find cheaper nodes to route traffic through; basic market forces then drive resource prices towards marginal costs.

Importantly, users pay and receive payments from other users, not "the protocol".

This can be contrasted with a tax-and-subsidy model, where a logically centralized incentive protocol (e.g. a smart contract) pays out subsidies to nodes contributing to the network, funded by some sort of user tax (e.g. token inflation). Nym's incentive model is a typical example of a tax-and-subsidy model, where Nym mixnet nodes submit "proofs of mixing" to a blockchain in exchange for NYM-denominated rewards.

Using a market instead of a tax-and-subsidy model avoids the usual inefficiencies of central planning, like the knowledge and calculation problems. A Nym-like tax-and-subsidy model will likely require a lot of parameter-tweaking governance — which is hard to decentralize — to keep demand and supply balanced, while a free market in resources self-governs in an inherently stable and decentralized way.

What to pay for?

Recall that Earendil uses source routing: when a node wants to send a message to another node, it first plots a path through the network to its destination, and sends an onion-encrypted message to the first hop, which then gets "peeled" and forwarded at every step.

Here's an example of A sending a message to J, through nodes D and I, in a hypothetical Earendil network:

The most important resource that nodes must pay for is the routing cost of packets: A in the above example burdens D, I, and J's bandwidth and computation (decryption) resources by sending the packet.

How would this routing cost be paid? One possible way is for A to directly recompense D, I, and J, but this runs into several issues:

• A must know the prices of every single link it may want to use to transmit data, and these prices may change over time. Gossiping this information is unlikely to scale.
• A has no direct link with D, I or J, so it's unclear how A can actually communicate to pay these nodes. Out-of-band communication would need some sort of external ban-resistant channel, which may not exist!
• Clients who prioritize cost-effectiveness over privacy will likely pick the cheapest-advertised route – but that allows attacks where the attacker advertises a low or zero price to attract a lot of traffic, then drops it all. Detecting and mitigating these attacks does not seem easy.

Instead, the sender only pays the first hop, who is then responsible for paying the next hop. In the example above, A would only pay D, at a price negotiated between A and D. D then pays I to forward the packet, and finally I pays J. This sort of indirect payment is reminiscent of typical payment structures on the Internet: a user only pays their local ISP, who is then responsible for paying upstream ISPs, etc to ultimately route the user's traffic to its destination.

Paying only the first hop has several important advantages:

• Prices can be negotiated bilaterally, without some global price advertisement algorithm.
• Payment is only between parties that already have a ban-resistant channel between them – neighboring nodes.
• Advertising low prices can only affect route selection of immediately neighboring nodes sending packets, and even there, only which first hop to pick. This greatly reduces the risk of attacks.

We use a similar neighbor-to-neighbor scheme to pay for resource consumption other than packet routing, such as gossiping the adjacency graph.

Credit lines and settlement

Sending an individual payment per packet will not work; even with the world's most efficient electronic money scheme, a payment is likely to be more expensive to send than a single data packet.

Instead, we keep a running credit line between every two neighboring nodes: both nodes keep track of how much money, on net, does the other node owe them.

For example, if

• Alice and Bob are neighbors
• Alice charges 100 nMEL to route a packet
• Bob charges 50 nMEL to route a packet

then after

• Alice sends 21 packets through Bob (thus owing Bob 1050 nMEL)
• Bob sends 10 packets through Alice (thus owing Alice 1000 nMEL)

then both Alice and Bob will know that Alice owes Bob 50 μMEL.

Debt on a credit line is kept under a mutually agreed credit limit; if this limit is exceeded then the neighbors will stop routing each others' packets. By reducing the credit limit to an arbitrarily small amount, we can limit the amount of damage peers that "leech" resources without paying can do.

Of course, debt on this credit line must eventually be paid; otherwise a node-to-node link with a "maxed out" credit line will become useless. This is done through a settlement protocol, which involves paying off the debt through any mutually acceptable method. Theoretically, this could be anything ranging from an on-chain MEL transfer, to sending a fiat payment, to buying one's peer dinner!

Micropayment settlement protocols

To allow for very low credit limits – important for incentive-compatiblity – Earendil does have two micropayment settlement protocols that are mandatory to implement by all nodes:

1. Astrape-based payment channel: debts can always be settled by paying MEL through an off-chain payment channel network (PCN), somewhat similar to Lightning Network but using the privacy-protecting Astrape construction. The details of this payment channel network have yet been fully worked out, but an interesting fact is that it will be an overlay network run over Earendil itself.
   
   This means that payments for Earendil resources cannot be processed without transmitting data over Earendil, which is a problem since transmitting data itself requires payments! This is solved by a second, bootstrapping protocol
2. Proof-of-sequential work bootstrapping: alternatively, a debt of x MEL can be settled by wasting 100x MEL worth of sequential work, through a proof-of-sequential-work protocol analogous to that used for the Melmint mechanism. (Note that we know how much work is "1 MEL worth", since MEL is defined in terms of a day of sequential computation).
   
   This method does not actually allow anyone to get paid, but acts as a heavily rationed "free tier" that is resistant to abuse. Any rational user who can actually pay would choose to pay x MEL rather than waste 100x MEL. Even irrational griefers who spam the network without paying anyone "just to see the world burn" would face at least a 100-fold "griefing factor": they must pay at least 100 times the cost they impose on the network.
   
   But a free tier allows payment signaling to go through without any payments, so it's important for bootstrapping.

The very interesting thing here is that since the PCN is overlaid on Earendil, yet Earendil's incentives depend on the PCN, the two systems are inseparably coupled. This PCN is also useful for applications other than paying Earendil fees, in particular any sort of applications needing low-cost micropayments.

Thus, Earendil must also be considered a general-purpose micropayment network, on top of being a packet-based data transfer network. The implications of a globally-connected, ban-resistant channel for both communications and financial transactions are huge, and will be discussed in the next blogpost in the series.