Beware of Sybils Not Bearing Proof of Work

Archne (A Sybil) 1644 1648 by Diego Velasquez

How do you protect a growing network from fraudulent activity? On the one hand, creating incentives that lead to fast growth is the holy grail of network design, but fast growth comes with the danger of a malicious actor seeking to reap rewards without doing any work. This is the inherent tradeoff between virality and fraud. A so-called Sybil attack occurs, for example, when someone creates fake accounts to cheat a referral system.

How feasible is it for someone to create multiple fake identities and successfully commandeer a network? That depends on the network and its incentives. One of the most important factors is how much verifiable work one must perform in order to be eligible for a reward. “Work” in this context is defined as something valuable for the network, which will vary from network to network.

In the DARPA red balloon challenge, for example, work is either locating a red balloon or referring someone who locates a red balloon. It’s easy to verify when someone finds a red balloon. It’s harder to verify that someone has referred the search to someone else as opposed to a fake account.

To help safeguard against Sybil attacks, some networks require “proof of work.” They require that participants submit some form of work that can be verified in order to be eligible for rewards. This makes the cost of a Sybil attack much higher. For example, we recently launched a contest to find the best logo for our company, nCent Labs. Like the red balloon challenge, we offered a recursively calculated prize for people who created a winning logo or referred people who created a winning logo. This work can’t be easily faked, since logos created by bots or algorithms stick out like a sore thumb.

A would-be Sybil attacker did not dispirit our network.

In the same vein, we recently launched a crossword puzzle contest called wordCent on our telegram channel. (It’s not too late to participate!) We’re offering rewards to participants who solve an nCent-inspired crossword puzzle. The clues are lifted from our litepaper. This contest is Sybil resistant because it’s difficult to fake an answer to a crossword puzzle. Knowing the correct word requires reading and solving clues. The closest a bot could come to replicating this would be to output every word in the litepaper that has the same number of letters as the active clue. But we only allow a finite number of answers for each person. That’s why wordCent can’t be easily Sybil’d.

An effective proof-of-work system asks for work that is moderately hard to produce but easy to verify. When an attacker can’t dodge the work necessary to earn the rewards, attacking the network becomes prohibitively costly.

Beyond a viable proof-of-work system, network designers can also increase the cost of a Sybil attack by incentivizing rewards in favor of certain networks topologies. For example, one could refuse to reward “deep graphs” which have properties more likely to be indicative of fraud. A deep graph is a chain of nodes in a network where each node in the chain has exactly one parent and exactly one child node. If deep graphs are eligible for rewards, then Sybil attackers can more easily commandeer the network by linking their fake accounts in a one-to-one chain. One solution is requiring a node to have more than one parent or more than one child in order to be eligible for a reward.

In practice, there is empirical research on what kinds of tree shapes arise organically in a social network. We can use this research to incentivize behavior that conforms to organic growth at both the individual and communal level.

Forcing a complex network shape could deter Sybil attacks

Identity is a full solution to the Sybil attack. Perhaps one day a practical and reliable decentralized identity solution will emerge, but until then we are left with more centralized identity stores. There is a tradeoff between the cost of requiring identity versus virality. One approach is to require identity verification to claim an earned but unpaid reward. By requiring, say, a parent and child to also pass an identity verification for the node to be paid the reward, the cost and variance of a Sybil attack becomes higher. Combining this with a requirement for identity to be linked to a device, such as a phone, further increases the cost to attackers.

We are actively working on problems at the intersection of behavioral economics and computer science in designing sybil resistant incentive markets on blockchains. If you are interested in learning more about our work, contact me at [email protected].

To stay in the nCent loop, hear me tweet and join our international telegram channel.