Mitigating Sybil attacks in Freenet

[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

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
4. Use statistical anomaly detection to identify and thwart suspicious behavior

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 nonce, hashing it, and sending the hash to the other. After exchanging hashes they exchange their actual nonces which are combined to create a new nonce, 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.

[Destroyinator69420]

You might want to look into hashcash to make it difficult to create large amounts of nodes near to a location. The more crowded that location is, the harder the hashcash is to crack. This will prevent locations in the network from being too crowded. You might want to upgrade from SHA1, which is known to be vulnerable, to SHA3, which should be futureproof for a long time. You may want to consider allowing smart contracts to specify a proof of work needed to join a smart contract. This will help prevent sybil attacks from targeting specific smart contracts. It would be smart to use this system in regards to voting in a smart contract. I agree with you that it should cost something to create an identity. A proof of work would be helpful in achieving this. Ideally, each proof of work should take no longer than a minute on a raspberry pi 400, which is a good representative of the lower average of personal computers. If this hashcash is too short, then it is meaningless, but if it is too long, it will prevent participation in the network. The difficulty to crack the hash should be proportional to the propensity of the given contract or feature to be abused, and its importance to the network.

[sanity]

I hope to avoid relying on hashcash / proof-of-work for Locutus because it's wasteful and heavily biased towards those with cheap energy and ample hardware, particularly ASIC miners.

Are we currently using SHA1 anywhere? I think we're using Blake2b512, we definitely shouldn't be using SHA-1.

[Destroyinator69420]

I hope to avoid relying on hashcash / proof-of-work for Locutus because it's wasteful and heavily biased towards those with cheap energy and ample hardware, particularly ASIC miners.

Are we currently using SHA1 anywhere? I think we're using Blake2b512, we definitely shouldn't be using SHA-1.

It may be possible to use webassembly instead of a hash algorithm for proof of work. To join in a crowded area of the network, each peer would send you a custom program compiled to webassembly, you would then send them back the result. The program would be encrypted and obfuscated to prevent you from de compiling the program to get the answer without working for it. The program should be no more than 32 MiB in size and take no longer than a minute to execute, if we use the Raspberry PI 400 running 64 bit raspberry as a benchmark. This is similar to how randomX works in Monero.

[sanity]

I should have been clear, the problem isn't using hashing for proof-of-work, the problem is proof-of-work itself.

[dirvine]

I concur that POW is not great here. My fear is disadvantaging folk who wish to run nodes. I would vote for low power devices being first class citizens as much as possible. (clients may be different wrt to POW proofs, to prevent spam as hashcash was originally targetted at)

[dirvine]

An Idea from BLS land

• Allow BLS keys as identities
• A node creates a BLS pub key (X) and finds nodes closest to that (say 4)
• Take the 4 node identities and xor them together (like hash but unordered or order and hash them) (Y)
• Derive new BLS pub key (Z) from X using Y as the derivation index
• Node joins network at the new address Z

The nodes close to Z then check

1. The new key Z is signed by the old key X.
2. Given Z and Y -> derive Z (any node can do this step as BLS allows this arithmetic)
3. Confirm the 4 identities that make up Y are in fact closest to X

What this does is allow a cryptographically provable derived key that is not known beforehand. The nodes that make up Y may churn, and this operation fails, but no worry, as the node can go again quite quickly. Therefore, a node can try to join, but not in an easily targetted manner.

Given a reasonably sized network then targetting a group of nodes covering an address space becomes difficult. The difficulty is quite high, but I have not measured it yet.

This certainly prevents attackers creating billions of offline keys to wait and target a group. This offline key generation attack is, I belive the most likely approach to sybil atack, even large networks. Removing that capability is similar to the advances in secure kad via timestamp type identity creation and rotation. I belive the BLS approach to be significantly more secure than s/kad

It would be great to hear your thoughts on this one. I am very keen on simplicity here and I understand this sounds a little contrived. So any simplification should be investigated.

(p.s. BLS Allows much more, such as threshold groups for signing and encryption, also some protection against quantum attacks if we look at the proposals from the Ethereum folks with hash based derivations.)

[dirvine]

sorry for noise, but

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.

Is worth diving into more. With recent advances in spoofing prevention and with QUIK adding more protection this could be better than we think. I am not sure bad nodes only speaking to their pals is helped or hindered by this as it would not matter which protection was in place in that case? (happy to be proven wrong on this point though)

[Julian-Dumitrascu]

I thought of you while reading the FreeNet manual. And here you are!
I'd like to talk with you and somebody on the FreeNet team about what benefits people can enjoy by using the Safe network and the Free Net.
I'd like to understand this from the point of view of any Internet user, e.g. for myself.
I may have known about both projects since 2014, but we are yet to build a dialogue. Not for my lack of trying.
When we do, one of my teams can make them more popular.
When I understand the benefits and costs of developing software using your services, we can build useful software.
I've got the impression that these projects have advanced rather slowly, which can mean that many potential users are missing out. We can help them progress faster when you say you'd like this.