Sybil-resistant social interactions based on proof-of-bandwidth

[kozlovsky]

Yesterday I had some idea of how it may be possible to implement Sybil-resistant social interactions and discussed it shortly with @devos50. Now I'm trying to write it down in coherent form, for the purpose of brainstorming. It is possible that this idea is not something especially new and was discussed already in some form.

When nodes gossip messages about likes/dislikes and similar social stuff, it is important to protect against Sybil attacks. The protection can be achieved by proof-of-work when each message includes a result of some expensive computation. But a usual proof-of-work assumes performing some "useless" work which consumes electricity and CPU.

In Tribler, nodes are already performing useful work: transferring data packets in anonymous tunnels. It may be interesting to use this work in a proof-of-work algorithm. I think it can be implemented in the following way:

Consider a data packet that NodeA sends to NodeB. This packet can include the following additional fields unrelated to the actual data transferred:

• A public key of NodeA (KeyA);
• A public key of NodeB (KeyB);
• An unique MessageID generated by NodeA.
• A signature of (KeyA, KeyB, MessageID), generated by NodeA with its private key, let's name it SignatureA.

When NodeB receives the data packet, it sends back the signature of (KeyA, KeyB, MessageID, SignatureA). Let's name it SignatureB. After that, NodeA can use the ProofBlock (KeyA, KeyB, MessageID, SignatureA, SignatureB) as a proof that the like/dislike is not generated by a Sybil, using the technique described below.

Of course, the number of data packets transferred in anonymous tunnels is much bigger than the number of likes/dislikes that a user of NodeA can generate. To balance this, only a small percentage of ProofBlock can actually be used as proof. To achieve this restriction, valid ProofBlock should contain a specified number of leading zeros in SignatureB.

If later NodeA wants to gossip to NodeC information about some like/dislike created by the user of NodeA, it sends the following message to NodeC:

• A ProofBlock from some previous data transfer
• Unique information about like/dislike
• A signature of the entire message

Then NodeC can check whether it trusts the information about this like/dislike. NodeC trusts information about received like/dislike if it has a non-trivial amount of traffic exchange with both NodeA and NodeB. The exact amount of required traffic is not constant; NodeC can change it over time using some heuristics.

Consider the following types of attacks:

1. NodeA creates multiple Sybils Sybil1, Sybil2 and Sybil3, and generates a fake ProofBlock for fake data exchange NodeA -> Sybil1, Sybil1 -> NodeA, or Sybil1 -> Sybil2. If NodeA then gossips some fake like/dislike to NodeC using this fake ProofBlock, NodeC then will ignore the received like/dislike, as NodeC does not have a sufficiently large data exchange with the Sybil node specified in ProofBlock. So, to make this ProofBlock plausible, NodeA should allow the Sybil node to exchange with NodeC a non-trivial amount of traffic. In that case, the Sybil node is no more truly Sybil, as it behaves like a normal node and has regular exchanges with other nodes. So, if NodeA want to create a significant number of Sybils, it should split its physical traffic between many Sybils, so each Sybil has a non-trivial amount of data traffic with a considerable number of honest nodes. If traffic is a limited resource, it restricts the number of Sybils each node can run.

2. Two nodes NodeA and NodeB can initiate a fake data transfer to exchange a big number of fake data packets and mine a big number of ProofBlock to use with likes/dislikes. It is possible to do, but then it will not be possible to significantly change like/dislike statistics for a single torrent, as each node can provide at most one like/dislike for a specific torrent.

So, to affect a specific torrent, a significant number of nodes should vote for it, and honest nodes will ignore these likes, as they did not interact personally with all these Sybils and does not have a big enough traffic transferred to/from Sybil nodes.

As additional protection, when NodeC receives a like/dislike with a ProofBlock from NodeA, it checks that NodeA never sent other likes/dislikes with the same ProofBlock. If NodeC discovers this situation, it can call NodeA a liar and gossip proof of the lie (that is, a pair of NodeA likes/dislikes with the same ProofBlock) to all its peers.

It is possible to further extend the idea, for example by including an approximate Unix timestamp into a ProofBlock. It makes ProofBlock valid for a limited time, so a node cannot accumulate a big number of ProofBlocks for the future. A node can reject the received like/dislike with a suspicious timestamp value inside a ProofBlock, for example, if the timestamp is in the future or far in the past.

In the proposal above, the ProofBlock content does not actually depend on the data transferred via the anonymous tunnel, maybe it is possible to change the algorithm somehow to tie it with the real encrypted data transferred (if it somehow allows making the Sybil protection stronger).

[qstokkink]

In the past two years, this brainstorming issue has neither seen brainstorming or any type of POC implementation. Therefore, I'll close this issue.