Mitigating Sybil attacks

[sanity]

Problem

Every node in the Locutus network has a location, a floating-point value between 0.0 and 1.0 representing its position in the small-world network. These are arranged in a ring so positions 0.0 and 1.0 are the same. Each contract also has a location that is deterministically derived from the contract's code and parameters through a hash function.

The network's goal is to ensure that nodes close together are much more likely to be connected than distant nodes, specifically, the probability of two nodes being connected should be proportional to 1/distance.

A Sybil attack is where an attacker creates a large number of identities in a system and uses it to gain a disproportionately large influence which they then use for nefarious purposes.

In Locutus, such an attack might involve trying to control all or most peers close to a specific location. This could then be used to drop or ignore get requests or updates for contract states close to that location.

Solutions

I think there are at least three categories of solution to this:

1. Increase the cost of creating a large number of nodes close to a specific chosen identities
2. Make it more difficult to target specific contracts
3. Increase the cost of bad behavior by making other nodes in the network monitor for it and react accordingly

1. Identity Creation Cost

1.1 Gateway assignment

When a node joins through a gateway it must negotiate its location with the gateway first. This could be done by both node and gateway generating a random nonse, hashing it, and sending the hash to the other. After exchanging hashes they exchange their actual nonces which are combined to create a new nonse, and a location is derived from that. This prevents either gateway or the joiner from choosing the location.

1.1.1 Attacks

• Gateway and joiner could collude to choose the location

1.2 IP-derived location

• The location could be derived deterministically from the node's IP address, this could then be verified by any node that communicates directly with it.

1.2.1 Attacks

• Attackers could limit connections to peers they also control, which could then ignore a mismatch between their location and their IP address.

2. Location Hopping

2.1 Replication

A contract has multiple copies, each indicated by a contract parameter - the location of each copy will be pseudorandom. A user could query a random subset of the copies to ensure that they receive any updates. If any copy has an old version of the state then the user can update them by reinserting the latest version obtained from a different copy.

2.2 Date hopping

A contract contains a parameter for the current date, which will mean that the contract has a different location every day. If today's contract is found to be missing it can be reinserted using an older copy.

3. Peer Pressure

[ple1n]

• Scarce resources like IP addresses, domains, geo-location
  • Matrix requires a domain to federate, terrible idea
• Social graph analysis (WoT, or anything similar)
• Proof of Personhood (captcha, people can still be bribed)
• Randomness (drand, etc.)
• Proof of work/storage
• Economic measures based on blockchains
• Node behavior (identity age, connectivity...)

Is the gateway trusted ? It shouldn't be, or it would cause too much centralization.

A contract that stores drand randomness may be used, perhaps a few latest blocks, and the contract may truncate the beacon chain. The contract verifies drand randomness, and the value can be forwarded by anyone into this contract. Drand produces a block every 30 seconds.

ID generation with cost

• The proof of work must be easy to verify
• The PoW can't be reused. It is bound to a drand random number and peer publickey
• It should take a few hundred milliseconds to generate.

Hashcash of, drand randomness || publickey || nounce. Drand is used so a peer can't pre-calculate the hashcash. The resulting ID is the hash of hashcash-hash, so it is costly to try. It expires quickly too.

Or use a different PoW, like cuckoo.

Multiparty random number generation

• The joiner may be required to generate the ID with a gateway peer close to current drand number, so no one can choose the gateway (or the peer can wait)
• PRNG(drand number) to allow more choices ?
• To combine the above method, the joiner has to generate a hashcash of drand number || nounce. The result and the preimage are then included in the commitment

Unpredictable random hopping of contracts based on drand

Harder to attack if unpredicatable