Tuesday, February 14, 2023

Sybil Defense

Calling a system "decentralized" because its architecture looks decentralized causes two serious problems:
  • It ignores the fact that decentralization isn't binary, it is a spectrum. Systems claiming decentralization can be characterized by their "Nakamoto coefficient":
    The number of entities sufficient to disrupt a blockchain is relatively low: four for Bitcoin, two for Ethereum, and less than a dozen for most PoS networks.
    This number varies through time, but for both is almost always between two and five, which is not very "decentralized". Given that the "entities" in question are known to coordinate their behavior off-chain, this number doesn't tell you anything useful about the system.
  • What calling a system "decentralized" even though it actually isn't does usefully do is to inhibit regulation. It creates the false impression that responsibility for the state and actions of the system is so diffuse that regulators lack a viable traget.
Because a system's Nakamoto coefficient is variable, somewhat difficult to measure and likely to be an over-estimate, the claim that a system is "decentralized" is always subjective.

There is a much more useful, completely objective criterion. Participation in a system either is, or is not subject to permission from some authority, and this can be confirmed by the experiment of trying to participate without asking permission.

Permissionless systems can claim some advantages, but they suffer from some serious disadvantages. Chief among them is the need to defend against "Sybil attacks". Below the fold I discuss Sybil attacks, the defense against them, and the implications for the systems that adopt this defense.

Sybil Attack

The nodes in a distributed or decentralized system have to achieve consensus on the system's state by a process that can be thought of as voting on each transition from one state to the next. The assumption is that each voter acts independently, although in cryptocurrencies these are typically not "one voter one vote" systems; some voters votes may count for more than others.

The essence of a permissionless system is that there is no control over the electorate for these votes. That is, voters can join or leave the electorate at will.

This inherent feature of permissionless systems enables a Sybil attack, in which the attacker creates a large enough number of ostensibly independent voters (Sybils), which are actually under his control, to win any desired vote.

In a permissioned system, voters must register with a central authority before joining or leaving the electorate. Thus a Sybil attack is not possible.

Sybil Defense

In a permissionless system it isn't possible to prevent the attacker creating an arbitrary number of voters. It is therefore necessary to provide some disincentive against doing so, by attaching a "ticket cost" to each vote sufficient to ensure that the reward for a successful Sybil attack is less than the cost of mounting it.

In Proof-of-Work systems such as Bitcoin, the ticket cost is the cost of the hardware, power, etc. to compete in the race to mine the next block. In Proof-of-Stake systems it is the stake, which is forfeit in an attack, and its foregone liquidity.


The necessity for permissionless systems of implementing a ticket cost has many implications.


It is necessary to reward the voters for bearing the ticket cost. A permissionless system cannot have a centralized nexus charging the users fiat currency and distributing it to the voters in proportion to their efforts. The rewards have to be generated internally by the system itself, so they must take the form of coins in a cryptcuurrency (See You Can't Have One Without The Other).


To have the necessary deterrent effect, the ticket cost must be in some form corresponding to real resources, and thus so must the rewards in the form of cryptocurrency. In order that the diligent voter might pay their power bill or buy the Lamborghini, there must be a way to convert the system's coins into fiat currency. Thus the need for exchanges, where the coins can be sold for fiat, or at least for metastablecoins that can be redeemed or used in trade.


Someone must be on the other side of the trades by the voters converting the coins they earned into fiat currency. The only reason for doing so is a belief that these coins are destined to proceed moon-wards, or at least that they can be manipulated into doing so (See Making Sure "Number Go Up").


Technologies generally have very strong economies of scale. Thus it is very likely that the more voters an organization creates, the lower the cost per voter. The lower the cost per voter, the greater the difference between the reward and the cost of obtaining it, i.e. the profit. This leads, as we see with Bitcoin and Ethereum, to the system centralizing around a small number of large pools.

I put forward a weak form of this argument in 2014's Economies of Scale in Peer-to-Peer Networks, pointing out that economies of scale meant that a notionally constant cost per voter would actually be a decreasing cost per voter which would drive centralization.

In 2019's Impossibility of Full Decentralization in Permissionless Blockchains, Yujin Kwon et al set out a much stronger form of the argument:
the blockchain system should be able to assign a positive Sybil cost, where the Sybil cost is defined as the difference between the cost for one participant running multiple nodes and the total cost for multiple participants each running one node.
Considering the current gap between the rich and poor, this result implies that it is almost impossible for a system without Sybil costs to achieve good decentralization. In addition, because it is yet unknown how to assign a Sybil cost without relying on a TTP [Trusted Third Party] in blockchains, it also represents that currently, a contradiction between achieving good decentralization in the consensus protocol and not relying on a TTP exists.
Thus there is a paradox; the necessary technique to implement decentralization, a permissionless network, ensures that a successful network will be centralized.


Kwon et al's definition of the Sybil cost is:
the difference between the cost for one participant running multiple nodes and the total cost for multiple participants each running one node.
The problem is identifying a "participant". In permissionless systems "participants" must create their own identities; they cannot depend on a central service to generate them. They are normally pseudonyms in the form of public/private key pairs. It is cheap to create a new key pair, and initially there is no way to connect one public key with another created by the same "participant". Eventually it may be possible to connect them by observing the transactions in which they take part, but that would be too late to impose a Sybil cost on their votes. A Sybil attacker would take care to avoid linking their Sybil identities until after the attack succeeded, when it would be too late.

Another way of looking at the paradox is that the need for user-generated pseudonyms in a permissionless system renders a positive Sybil cost impossible, and thus makes eventual centralization inevitable.

Note that even with participant's identities known 51% attacks are still possible because the participants can conspire off-chain. See, for example, Justin Sun's takeover of the Steem blockchain.

Note further that in On-Chain Vote Buying and the Rise of Dark DAOs Philip Daian and co-authors show that "smart contracts" provide for untraceable on-chain collusion in which the parties are mutually pseudonymous.

Economic Limits

In The Economic Limits Of Bitcoin And The Blockchain, Eric Budish analyzes two different kinds of 51% attacks on Proof-of-Work blockchains and shows that:
the equilibrium per-block payment to miners for running the blockchain must be large relative to the one-off benefits of attacking it. Equation (3) places potentially serious economic constraints on the applicability of the Nakamoto (2008) blockchain innovation.
In other words, the total value of the transactions in a block must be less than the block reward plus transaction fees. The block reward is currently 6.25BTC, and the average block contains about 0.14BTC in fees. The BTC infrastructure is therefore funded almost entirely by inflating the currency. (See Cryptocurrencies Have Limits).

This is necessary, because much academic work (see Taleb On Cryptocurrency Economics) shows that were the network funded largely by fees, it would be insecure. The hand-wavy explanation is that the fees in a block would have to be more than the value of the transactions, which is economically implausible. Related arguments apply to Proof-of-Stake blockchains.

The Bitcoin network currently transacts about 100K BTC/day, or an average of nearly 700 BTC/block, so the network exceeds Budish's safety criterion by more than two orders of magnitude. The safety of the network depends on the fact that the big players are making so much money that none want to kill the goose laying the golden eggs.


Networks intending to be "decentralized" must be permissionless, and thus must employ the "ticket cost" defense against Sybil attacks. But doing so inevitably results in centralization.

1 comment:

David. said...

Blake Reid on Mastodon:

"PSA: anyone who was until very recently touting the extreme importance of decentralization in the context of cryptocurrency and Web3 but is now extremely bullish on the disruptive potential of extremely centralized generative AI models might not know what they are talking about"

Believers in decentralization should check out the current top two posts on Molly White's Web3 is Going Just Great. First was Per a court order, Oasis rewrites the rules for Jump Crypto to recover stolen assets:

"Ultimately, Jump was able to recover around $140 million via their "counter-exploit". While many celebrated the recovery, some were concerned about the precedent of a so-called defi platform changing a smart contract to remove funds from a wallet at the direction of a court. Some described the upgradability as a "backdoor". "If they'd do it for Jump, what does that say about possible coercion via state actors?" wrote one trader on Twitter."

Soon after was Solana tries turning it off and on again (twice):

"It's just like mid-2022 again! As transactions slowed to a crawl, developers embarked on a "coordinated restart" — a euphemism for the rather centralized way this supposedly decentralized network has to routinely go about fixing itself.

One "coordinated restart" apparently wasn't enough, because a second one followed later that day."