Evolution of Cooperation and BitTorrent Economics

This post was originally written as a speech given in Chinese at the Papers We Love meetup in Taipei. The Chinese version can be found here and the recording here.

Introduction

Last time I talked to you about about cooperation. What it is, why people choose to cooperate with each other, even when it is in their interest not to.

This talk is based on BitTorrent Economics by the creator of BitTorrent. We'll look at how the lessons we learned last time can be applied in a modern system in the form of BitTorrent, a p2p file sharing protocol, to encourage people to share with each other.

After this talk, you should have a better understanding of how we can use these insights into cooperation and game theory to design better systems.

Brief recap

First, a brief recap and summary of last time. What did we learn? We learned that:

Cooperation can evolve during repeat encounters even in among enemies in war zones.
Prisoner's dilemma is a common type of game in game theory, and in real life.
a) In prisoner's dilemma (PD) you can cooperate or defect
b) In PD the best outcome is mutual collaboration, but the dominant strategy is for both to defect
c) By playing PD many times, as a repeated game, better strategies emerge, such as tit for tat
Tit for tat is a great strategy for cooperation in repeated PD games.
a) We first cooperate, then we follow whatever the other person is doing
b) Tit-for-tat is nice, forgiving, retaliatory and clear
c) This makes it a very simple and robust strategy in many evolutionary environments

BitTorrent

Let’s look at how some of these insights are used in designing computer systems, specifically how it is used in BitTorrent.

BitTorrent is a peer to peer protocol for sharing files over the Internet. It has been around for 20 years and is very popular, accounting for a significant portion of all Internet traffic (2.5% down, 25% up), with hundreds of millions of users. BitTorrent is a protocol, just like HTTP for the web or SMTP for email. There are many different programs to use to interact with it, and the user interface is very simple: find and download a small .torrent file and open it, then simply let it do its thing in the background. Outside of being an open, permission-less protocol, what makes it unique is how it distributes load. Unlike a traditional server-client architecture, where some server is hosting a file and sharing it with clients, everyone in BitTorrent is an equal peer sharing a file with other peers.

How do you incentivize people to share with each other? There’s nothing stopping people from leeching, only downloading, and not seeding, contributing back. How do you address this? You might notice it is a form of prisoner’s dilemma, where nodes would prefer to only download and not upload back. Everyone would be better off if people uploaded to everyone else. By splitting an individual file into multiple chunks, we can turn this into an iterated prisoner’s dilemma game and use tit-for-tat to incentivize cooperation.

BitTorrent has a very interesting property. The more people want a certain piece of information, the faster it gets distributed because there are more people around to help out and upload this. It is antifragile in that sense - the system gets stronger as it is put under stress - an impressive property.

This is in contrast with a fragile system or a robust system. A normal website might be fragile under load and require complex operations to keep up and performant. If there is a lot of redundancies and good engineering, it might become robust, so that it won't go down under load. But how any systems actually get better the more load they are put under?

As an analogy, imagine you walk into the post office and there are 10 times more people there than usual. Normally you'd expect mailing a letter to be slower. What if instead of it being slower things got faster? How could this work? Instead of having official post office workers, people who happened to be in the post office would handle the entire posting pipeline in a p2p manner. For example, some people would write labels, some would scan labels, some would do packaging, etc. At the same time, each person has one or several parcel(s) they want to send through the p2p pipeline. Instead of waiting in queue, playing on their phone, people would cooperate and do their tasks faster to get their parcels shipped faster. This would obviously run into many issues, but you could perhaps imagine something similar happening when a large family is doing grocery shopping and preparing dinner. This is similar to how BitTorrent works, except it happens in the background and only uses your bandwidth.

Tit for Tat in BitTorrent

If there was only one piece to download in BitTorrent you'd be done with it in one go. Download and leave. But BitTorrent deliberately chunks up a file into many pieces, and this turns the file distribution into a form of iterated game. How does this work?

A peer tells other peers what pieces of data it has, and it selects some chunks to receive from other peers. While chunk selection is initially random, there are some heuristics that are often used here. For example we use “rarest-first”, which means you get the most rare chunk first among all the peers you are connected, as that’s what is most valuable. Initially there is only one seeder, so this way more and more peers can join in and take the load off the initial seeder.

The choking and unchoking algorithm is where the game theory comes into play. There's no central coordination deciding who gets what, but this is decided on a per peer basis. A peer wants to maximize its download rate. It downloads from some other peer, and it decided who to upload to using tit-for-tat. Usually, the number of peers that can be uploaded to at a given time is limited, and less than the number of peers that wants to download that chunk. Cooperation means sharing, and defecting means you "choke" a peer, i.e. you don't upload to that peer. There's also a concept called "optimistic unchoking", where a node randomly decides to upload to other peers. This corresponds quite nicely with "cooperate first" in tit for tat, and allows nodes to find mutually beneficial connections.

As we’ve seen before, in an iterated prisoner’s dilemma game tit-for-tat is a very good strategy. Since BitTorrent is a protocol, and each app using BitTorrent is free to use whatever policy they want, the reason pretty much all implementations use this strategy is is because it leads to the best results acting out of self-interest, with random peers as strangers. There’s no coercion or top-down control here, but a bottom-up, organic discovery of who to share a certain file with.

There are more subtleties and technical details to how it works in BitTorrent. If you are interested I suggest checking out the paper for more details.

What is the duration of a game?

The BitTorrent file sharing game is limited in its duration. Each file essentially acts as a a game on its own. This means that when a file is downloaded or close to downloaded, there’s little reason to keep uploading. What has ended up happening with BitTorrent is that a lot of traffic, particularly of the pirate file sharing variety, has ended up in private communities. These are essentially private sites, where you need to be invited, and then maintain a good seed ratio to stay in. A seed ratio captures how much you contribute vs leech, and often you have to keep this above, say, 1. This means you upload more than you download, including initial seeding of new material.

This has nothing to do with the BitTorrent protocol per se. Instead, these are centralized communities which use BitTorrent as a file sharing mechanism. This makes these communities prone to attacks as a single point of failure. For famous examples, see the closure of OiNK pink palace in 2007 and What.cd in 2016, at the time two of the largest repositories of music anywhere in the world. OiNK was called “the world’s greatest record store” by Trent Reznor, musician at Nine Inch Nails.

Some open problems

It is an open question if we can generalize the game using a bottom-up, decentralized mechanisms, so the cooperative nature continues beyond a specific file. This goes beyond the scope of this presentation.

The game in BitTorrent is also fairly well defined. There’s a file and a static set of chunks that are desirable. What happens when there’s a stream of information that keeps changing, and it isn’t clear how valuable each chunk is? What about when material is rare, and most people aren’t interested in it? BitTorrent tends to incentivize more popular content.

Another aspect is in terms of what resources are being traded. In the case of BitTorrent, using bandwidth makes a lot of sense. But it is a fairly poor abstraction compared with the real world, where cooperation can happen using many forms of actions. Most commonly using money for goods and services, but many other social forms of cooperation are just as commonplace and taken for granted.

One thing BitTorrent did that is great is that it gave people the option to contribute, and a system where this was rewarded. Whereas traditional client-server side architectures makes a clear distinction between “provider” and “user”, in BitTorrent, as in the real word, the borders are more fuzzy and fluid. This gives a form of agency, and this agency leads to richer and better behavior. You can see a similar phenomena happening in the sharing economy, where people build up a reputation on sites like Airbnb and Uber and the best participants play repeated games (many reviews, say). How can we use these insights to create other systems like this that encourages cooperation and lead to better outcomes for its participants?

Conclusion

In this and the last talk talk we have seen how cooperation can develop in the most dire of circumstances, such as in a war zone. We've learned a bit about prisoner's dilemma and its structure. We've seen how playing the same game many times leads to certain strategies evolving, especially tit-for-tat. We've seen how tit-for-tat is successful because it is nice, forgiving, retaliatory and clear. Finally, we've seen how we can apply this line of thinking in designing modern systems, specifically through the BitTorrent p2p file sharing protocol to incentive mutual sharing, as well as some open problems related to this.

I hope this gives you some tools for thinking about problems, and perhaps some ideas for how to design systems which use these insights.

Acknowledgements

Thanks to Sanaz for comments on this post, and my Chinese teacher Jenny for comments and much help with the Chinese version.