Read A Simple Proof of Sybil Proof. for a complete and formal proof.
Learn about Sybils and how they damage permisionless networks.
A sybil produces the block with w/ 2nd hop routing work. A non-sybil produces the block faster with 1st hop routing work. The probability of the sybil collecting payment is lower because the probability of their blocks being added to the chain is lower.
The only way a sybil can reach parity on probability is if they burn their own money, which puts their cost higher than the non-sybil. There is simply no world in which the probability of getting paid is the same for a sybil as a non-sybil ceteris paribus.
-David Lancashire
As argued in On Bitcoin and Red Ballons [Babaioff et al., 201] the Sybil problem widely agreed to be unsolvable, since giving other block producers access to transaction fees always gives them an advantage, and allowing arbitrary claims on fees allows Sybils to earn multiple, unwarranted rewards for fake relays.
This poses a problem for blockchain networks which wish to remain open and secure against converging power at scale. If, as argued by experts in the field, Sybilling on transaction propagation is impossible to defend against, blockchain networks are doomed to fall into patterns of hoarding which reward the largest nodes in the network and introduce economic problems as they shelter transactions rather than share them - even if sharing would increase overall efficiency.
Saito proves that by reducing the work available to produce blocks with each 'hop' in a transaction's relay path, that Sybil nodes and nodes who otherwise add unnecessary 'hops' on their way to block producers are less profitable and out-compete by nodes who only add hops to reduce propagation time to block producers. The mechanism and basic mathematics of the proof are demonstrated below.
Saito Consensus rewards routing nodes based on their ability to propagate transactions towards successful block producers in as few hops as possible. A single transaction may take many paths throughout the network into the mempools of different nodes, and each hop diminishes the 'work' which is required for block production by half, starting with the base fee.
The winning routing node is selected using the hashing puzzle solution from the Golden Ticket which is required to release rewards. That number is used to select a transaction from the previous block with each transaction's chance of selection being proportional to its share of fees contributed to the block. The random number which selected the transaction is then hashed again to select a random node from the routing path of that transaction. Each node in the routing path has a chance of winning this proportional to its share of the aggregate routing work held by all members of that routing path.
The "Classic Saito" design targets a difficulty where the network can produce one golden ticket every two blocks on average and is secure at the cost of deflation from unsolved blocks.
Saito's routing reward scheme is provably Sybil Proof, as any routing node which self-clones to gain a larger share of routing-work for a given transaction also reduces by half the ability for that transaction to contribute towards the valid block production work threshold. In order to remain competitive for block production with a node at the same depth who chooses not to Sybil, the self-cloning node must produce their own transaction to supplement the reduced block work; the math works out that this strategy is less profitable.
In each block, half the total fee reward is paid to routing nodes, and the other half split between staking UTXOs and the miner who discovered the solution which selects the winning router. The reward for the winning router is thus . Note that this "playsplit" of half-and-half is not necessarily required, but is the standard parameter.
The expected value for a routing node is the value of the potential routing reward multiplied by the sum of probabilities that the node is selected in the routing path of the selected transaction; these selections are determined at random weighted by routing work.
The expected value is for any node is:
The chance that a transaction from the block is the , which is the value of the fee in that transaction proportional to the total fees paid in the block. Each router for the chosen transaction has a chance proportional to their routing work in the transaction's relay-path to win the .
The sum considers every transaction in the block. Transactions where a node has a routing work share of zero add zero expected value.
Consider a transaction pays fee, and is given to node who then propagates it to node . If Sybils, then he will increase his share of routing work in the transaction by marking it with an additional address he controls - if is honest, he will not. Note that by adding an extra signature to the routing-chain, claims more of its reward without further propagation the transaction.
The following demonstrates the expected returns of both and when is honest, then when decides to Sybil:
and 's respective shares of routing work as well as the total routing work of the transaction which holds (total) are described below.
Note that is free at any time to produce a block with the version of the transaction without including and keep , 100%, of the work, but if wants to produce a block, he only has access to it such that is in the routing path and thus must share the work.
| Fee | routing work | routing work | Total Routing Work |
|---|---|---|---|
For the block containing just the single transaction in the table above, the total fees equals , thus the probability of that transaction being chosen is , and there is only a single term for each sum of probabilities. The routing reward is .
The expected values in the honest case, , are as follows:
For node :
And for node :
If this behavior is repeated and the parameters do not change, node can expect to earn while node can expect to earn .
If node decides to Sybil the transaction sent to him by node , the respective and total shares of routing work are now described by:
| Fee | routing work | routing work | routing work | Total Routing Work |
|---|---|---|---|---|
Crucially, node has also diminished his block production ability from to . If wants to include this Sybilled transaction which pays him more, he must supplement his block with the routing work he destroyed when adding a hop () - that block looks like this:
| Fee | routing work | routing work | routing work | Total Routing Work |
|---|---|---|---|---|
| 0 | 0 |
The total block reward is now and so the routing reward is . In the Sybil case, the expected values are:
Node 's expected value must take into account 's unique cost in the form of the fee node supplemented to remain competitive with block work . 's expected value after Sybilling is now:
For the non-Sybil (honest; ) case:
When Sybils ():
If chooses to Sybil, his expected value drops almost by half. also loses marginal expected value by sending to Sybils, or equivalently, any node which adds unecessary extra hops. If sees that another node can include her transactions in successful blocks at the same rate while using less hops, is incentivized to stop sending to her peers which require more hops; the network in general sheds extractive agents offering sub-optimal routing utility.
One can see that summing the expected values of the non-Sybil case results again in the total honest routing reward: . But summing the values for the Sybilling case has a deficit: . So where does the remaining end up?
It turns out this is exactly the quantity of burn fee from the supplemental transaction the Sybilling node added with a fee of , that is, the half of each fee which pays Golden Ticket rewards.
This additional burned fee ends up as a bonus to the mining and staking rewards (as expected value for miners and stakers), which make complimentary attacks on the Golden Ticket mechanism more expensive - routing attackers' wasted value enhances re-org security.
One common objection to the the claim that Saito's router reward scheme is Sybil Proof is to notice that it cannot tell the difference between Sybils adding an extra hop to extract value and honest nodes performing sub-optimally. Saito is secure against Sybils, however, precisely because it is able to identify their behavior as a generalized form of sub-optimal routing outcomes.
This in fact makes Saito's defense against extractive behavior stronger than if it was specifically Sybil Proof, as sub-optimal outcomes which it is secure against includes Sybils.
The fact that Sybils fall under a broader category of behavior in Saito than simply self-cloning does not prevent Sybils from being punished and driven out.
This broader category of behaviors punishes sub-optimal outcomes more generally. Sybils and non-competitive nodes both extract reward without a similar provision of resources for the network.
Saito's reward scheme, more generally, is proofed against sub-optimal routing behavior in favor of efficient routing and block production. Sybils may not be distinct from non-competitive nodes, but as neither can extract undue rewards (and neither is desirable for an economically scalable and sustainable network), the network has security against both.