Is it possible to create a "proof-of-upload" system for BitTorrent ratio tracking? One issue that private BitTorrent trackers that track users' share ratios often run into is how to keep track of people who are screwing with their upload statistics, something known as "stat-hacking". As it is, because uploading and downloading is entirely peer-to-peer, there is no reliable way for the tracker to know purely through the BitTorrent protocol itself how much a client has uploaded or downloaded, except to trust the numbers that each client forwards. While somebody who uploads 1 petabyte in 2 days is an obvious impossibility, somebody simply augmenting their upload by 10% at a time could go unnoticed for a very long time.

Can we devise a cryptographic protocol to ensure that stats about upload and download are accurately reported to the tracker? In particular, it should be resistant to the following related attacks:


The uploader cannot claim empty upload credit - that is, to be able to report to the tracker that a piece was uploaded to a person, without having actually uploaded the piece to that person.
A downloader cannot repudiate their download - that is, the downloader cannot download a piece and then refuse to verify to the uploader that the piece was actually downloaded.
The current specification says that tracker GET requests specify the following variables:

uploaded=... (bytes)
downloaded=... (bytes)
left=... (bytes)


This is great for public trackers but is poorly designed for private trackers. The problem is that the numbers don't always add up as they should and this can be for several reasons. For example, you might notice two users uploaded variables increase by 100MB over a period of time, but the sum of downloaded reported by the swarm might only increase by 150MB over the same period. This could be because someone is cheating, or it could be that someone else has unexpectedly left the swarm without reporting their extra 50MB downloaded. Smaller accounting errors might also occur due to packet loss between peers.

The core problems:


Transfer statistics are only reported to the tracker in aggregate, so in the event of contradictions, it is difficult or impossible to tell exactly which peers were involved in some change of total uploaded or downloaded bytes. (Over time an algorithm might be used to guess cheating clients, but this is still not 100% accurate.)
Since private trackers typically reward users which keep a good upload:download ratio, this creates an incentive for a peer to:


Claim it has uploaded more data than it really has
Claim it has downloaded less data than it really has



To prevent this kind of cheating, the above two problems must be solved. First, it is necessary to introduce some form of detailed accounting. Second, it is necessary to change the way statistics are reported so that there is no longer any benefit or incentive to do the wrong thing.



NOTE: When I first provided this answer, I gave a non-cryptographic method which would only need a relatively small extension of the BitTorrent protocol. However, I then came up with a far superior method involving cryptography, which is now given here. I have moved the non-cryptographic method to another answer so as to not clutter this one.



Cryptographic solution:


The tracker and each peer should have a public/private key pair.
The torrent metadata should contain the tracker's public key, to be used to establish secure communication with the tracker. This ensures encryption and prevents MITM between the tracker and clients.
When a client connects to the tracker, it should inform the tracker of its public key fingerprint. If the tracker does not know the public key, it should request it from the client.
When the tracker responds with a (partial) list of peers, it should include the public key fingerprints for each of those peers.
The tracker should also provide the client with a signed token such as expiry:SIGNATURE(client_ip:client_port:client_public_key_fingerprint:expiry), signed with the tracker's private key. The expiry, a UTC UNIX timestamp perhaps 24 hours from then, ensures that peers can only participate in the swarm while they are welcome by the tracker (i.e. not banned).
As expiry times are important for this protocol to work, the client may need to record and use a clock offset if the time reported by the tracker is very different to its own.
When the client connects to a peer, it should first provide its public key fingerprint and signed token. After the peer verifies the token, they will exchange public keys as necessary, and use them to establish secure communication. This ensures encryption and prevents MITM between peers.
After successfully downloading a number of blocks from an uploading peer, the uploader will request a download chit from the client, to be signed with the downloader's private key. This chit is described in the next section, but to put it briefly, it is proof of bytes sent which the uploader may give to the tracker. A client which refuses to provide valid download chits will quickly be blocked by its peers.
When next connecting to the tracker, a client which has been uploading data should take each downloading peer's public key fingerprint and append the latest download chit(s) it has received from that peer since last time. The client should then sign this list of chits and send it to the tracker.
The tracker should process the chits in sequence, verifying signatures and skipping any chits with which are out-of-order or have very old timestamps (e.g. over 7 days old). The tracker can then log how much data has been downloaded and uploaded by each peer. The tracker should respond with a success code, after which the client should clear those chits from memory (but still keep track of the previously used chit timestamps for each peer).


In addition to much stronger security and full encryption, this system ensures it is impossible for an uploader to unilaterally cheat about how much data they have transferred. While not directly prevented, downloaders who try to cheat will quickly be blocked from participating in the swarm.

Download chit specification:


The chit should contain the following fields:

bytes_downloaded
utc_unix_timestamp
SIGNATURE(bytes_downloaded:utc_unix_timestamp:uploader_public_key:torrent_hash)

How often an uploader requests a download chit may depend on the time since the last chit was requested, when it next intends to contact the tracker, the size of the torrent, and the degree to which the uploader trusts the downloader.
The uploader may either request a chit with the same timestamp as the last chit sent to this uploader for this torrent, or a chit with a new (current) timestamp.
If the downloader has lost the timestamp it last used for that peer on that torrent, or if it never received data from that uploader on that torrent, it should just provide a new chit.
The byte value of the chit should be the number of bytes successfully downloaded from that uploader on that torrent since a chit with an earlier timestamp. If no chit with earlier timestamp is known, this should just be all the bytes successfully downloaded during that session.
Essentially, a chit with the same timestamp can be used to replace a previous chit of lower value, or in case the previous chit was lost during transfer. Since the tracker will only accept one chit with a given timestamp, the uploading peer should always keep the one with the highest byte value. Here's an example session from the perspective of an uploader:

 --&gt; sends 2MB
 --&gt; requests new download chit
&lt;--  receives 2097152:1396945746:3653e8fa74765d18903b77435b87174be1271315
 --&gt; sends 3MB
 --&gt; requests same download chit
&lt;--  receives 5242880:1396945746:81ffed9eca4325b277ba258e2e0 CORRUPTED
 --&gt; requests same download chit
&lt;--  receives 5242880:1396945746:81ffed9eca4325b277ba258e2e01ee20ad462a7b
 --&gt; continues to send another 3MB to peer
 ==&gt; meanwhile, sends download chit to tracker (with associated info)
&lt;==  tracker says OK
 --&gt; requests new download chit from peer
&lt;--  receives 3145728:1396946262:b8b1a71da192440158adc307cab5befaafb2229e
     ...

Of course, a client may be both downloading and uploading from the same peer, so there may be download chits being transferred in both directions.
It is the responsibility of the uploader to request download chits.
It is the responsibility of the downloader to provide valid chits for past data transfers, going back up to at least one hour (or some standard amount of time). That is, a downloader should not be expected to provide download chits for data received more than that time ago, though well-behaved clients should honestly provide chits for older data if they are able.
The uploader should adjust its trust of a downloader's IP and public key based on the reception of valid download chits. If the level of trust drops too low, the uploader should refuse to upload to that peer for some amount of time (perhaps permanently). Note that it is possible for a non-cheating downloader to lose some block data during transfer or have a client crash or system failure and lose knowledge of bytes transferred, which is why some leniency is needed.


Mitigating tracker connection problems:

As a further benefit, this infrastructure could, with some small additions, allow partial decentralisation of the tracker's role. That is, the swarm could still function effectively and record most data transfers even if only some of the seeders could connect to the tracker some of the time:


If you are unable to connect to the tracker currently, but still have an unexpired token from that tracker, you could attempt to use a DHT to find another peer. Once you authenticate to that peer, they can send you a list of other peers they know (PEX). Usually PEX and DHT are disabled for private torrents, but in this case only the clients authorised by the tracker will be able to both know how to look up the DHT and successfully authenticate to a peer in the swarm. There are two options which could be used for the DHT:


A private tracker-specific DHT. Clients would need to keep records of possible bootstrap nodes specific to the tracker, and all communication would need to be authenticated with tracker-signed tokens.
The standard global BitTorrent DHT, but with a special process to find the right hash. The hash would be found by encrypting the regular torrent hash with a special key given by the tracker when you last connected. The key would be shared by all torrents on the tracker, but would be regularly updated (e.g. twice a day). To achieve this, when the client receives its authentication token from the tracker, the tracker should also send the client a list of the keys the client should use at which times during the token's lifetime. Peers found with this method should be encrypted with the same key, and all further communication would be done with tracker-signed tokens.

If the client cannot connect to the tracker to send a list of download chits, it could instead sign them and send them to another peer with token expiry indicating more recent tracker communication. To make this system more fair for the clients doing the work, there could be a standard fee for this, to be paid as a download chit. For example, if the list of accumulated download chits is 2 KB in length (including uploader public key fingerprint), then the client might need to append a chit worth 20 KB or 30 KB for the forwarding peer before signing. In order to cash in their chit, the forwarding peer would need to send the whole signed list to the tracker at any point in the future (or in turn forward the chits again to a third peer). (The formula for the fee would need to be considered carefully.)