Trustchain network experiments. Double spend detection

[grimadas]

I was looking on how Tribler uses Trustchain to get insight on the scalability with some security guarantees. Here are some of my observations:

Network crawling

After running aggressively the crawler with introduction requests I managed to reconstruct the overlay network. The network overlay is densely formed with some peers having at least 500-1000 stable connections(these are mostly exit nodes). The network diameter is 3-4. That means that gossip with ttl=3 should be sufficient to reach anyone in the network.
This is the overlay network for TrustchainCommunity, with around ~1500 peers.

Trustchain and Overlay correlation

For the case of Tribler Trustchain bandwidth blocks are formed with overlay buddies(peers that are directly connected through an overlay network). Usually these are payments for relaying, and relay nodes are chosen from the verified peers list. That means over a time and repeating blocks one can deanonymize all neighbors of a peer. That might be sufficient for a number of attacks, e.g. Eclipse attack.

Double spend detection experiments

To combat double spend/ block hiding attacks we currently broadcast block to 25 random peers(which I call later witnesses) chosen from verified peers list.
I modeled an adversary that tries to hide the block/double spend. I randomly choose a peer p1 from the network and adversary a who is connected to p1. Adversary tries to double spend a block with same hash with another peer p2, that is randomly chosen from the a's neighbors.

I tried two different strategies for block dissemination:

• Broadcast to k=25 random peers
• 'Gossip' to k=4 peers with ttl=3

I measured the number of peers that get both blocks, meaning that double spend is successfully detected. The experiment was repeated 6000 times. Here are histograms for the experiments:

Broadcast strategy:

Gossip strategy:

Clearly we see that just broadcast is not performing well against attacks giving a probability of double spend detection ~0.80, while gossip based dissemination gives probability ~0.996. For higher k values (5-6) the probability is 1.0.

Network and Byzantine failures

Assuming that adversary cannot learn reliably about the network topology(all neighbors of a specific peer), the best adversary can do is to attack random peers corrupting them. We can frame it also a bit differently, saying that we can tolerate up to f failures of random peers.
Corrupted/Failed peer will not broadcast block further and will try to hide it.

Gossip based approach is not surprisingly more resilient to the network failures. With half of node hiding blocks we can detect double spend with probability 0.999.

[ichorid]

Basically, this means our exit nodes produce the small-world effect, which we can exploit to reliably detect double spends by switching from block broadcasting to TTL-based propagation, right?

[grimadas]

@ichorid correct. I'm thinking how to improve further the dissemination. Since you receive Trustchain blocks for your neighbours and about their neighbours you can use this for block dissemination too. Having a block(a recent one) is a reliable indicator of an overlay connection and peer can use that for deciding where to broadcast.

[qstokkink]

Trustchain has been removed and this issue is no longer relevant.