[bittorrent] Short secure file identifiers

Edward Walker walker.edward at gmail.com
Wed Jun 29 04:42:18 EDT 2005


Currently, BitTorrent requires a .torrent file containing a cryptographic
digest of every block of the file to allow the verification of blocks during
the download. Serving .torrent files for large files puts a strain on the
Web servers used. The idea is to replace the .torrent a short, secure
identifier. For example, a single digest. 
        
A related problem is the use of large block sizes. To keep the size of a
.torrent small (as to not overload the Web servers) the number of hashes for
a file is being kept small. For large files this implies that the block size
over which digests are calculated must go up (up to 2MB blocks are used).
The large block sizes affect the ability of peers to barter blocks. Only
when a block has been completely received and verified using the digest may
it be traded with other peers. This means that it may be some time before a
node starts bartering with others. 
		
There are multiple ways to solve both problems, for example, the
controversial Merkle hash trees. I propose a different solution based on
simple recursion. The solution is to distribute the .torrent via BitTorrent
as well and use one (or more) digest of the .torrent as identifier, as follows.

1. Generate a .torrent file T for the file F in the normal way (i.e., calculate
   digests for each piece and select a tracker)

2. Generate a .torrent file M of the .torrent file T, I call this the meta
   torrent file. The number of pieces into which the .torrent T is divided 
   should be kept as low as possible, ideally 1.

3. The short, secure file identifier SSFID of file F is now formed by the
   concatenation of the digests found in meta torrent M. 
   
4. Start a tracker and seeder for the original file F, as usual.

5. Start a tracker and seeder for the .torrent T, but using the first digest of
   the SSFID as "info_hash" parameter, rather than the digest of the info
   part of the meta torrent M. I call this first digest the root hash.
   
6. Publish the SSFID, by combining it with the URL of a tracker for T to form
   a URL U with e.g. the following format:
   
	btp://<tracker URL>?<version><SSFID>-<size of .torrent T>
   
   where version is a 1 byte version number in HEX, SSFID is BASE64 encoded
   and the BASE64 encoding is done after concatenation the binary digests,
   rather than concatenation the BASE64 encodings of each individual digest.
   The size of T is also in HEX.
   
7. Clients can now simply download the .torrent T by decoding the URL U, and
   ask the tracker for peers using the root hash as "info_hash" parameter.
   Having the size of the .torrent T makes it easier for a client to see
   it has the complete T, and it is used to calculate block size for T
   (see below).
   
8. Once the client has the .torrent, it can start downloading the original
   in the usual way.

The advantage of this solution is that it does not require any changes to
the BitTorrent protocol. A disadvantage is that it increases load on the
trackers somewhat.

What I like particularly is that we can use this solution to reduce
blocksize. Because the .torrent is now in BitTorrent we can make it larger,
within limits. This means we can start using smaller blocksizes, allowing
new peers to start bartering more quickly after joining. In addition, DoS
attacks by malcious peers sending bad data will be detected more quickly.

The limitation is that the number of pieces that the .torrent T is divided
into should be kept small, to ensure the SSFID remains small. Ideally, there
is just a single piece, and the SSFID consists of a single digest (i.e. the
root digest is the SSFID). This means that the peers sharing the .torrent
file T will have only a single block to barter, in other words, will have
nothing to exchange. This situation is, however, not different from that of
new peers joining who also need to get the first piece for free. 

If .torrent T is split into more blocks there will be bartering, so for
larger .torrents based on small blocksizes this disadvantage does not hold.
To keep the SSFID small, I currently suggest a maximum of 8 pieces/torrent.
This leads to a URL that is maximally around 256 characters in length
(8*20-byte SHA-1 digest encoded in BASE64 gives 224 characters + tracker URL
+ size). 

Alternatively, one can first apply recursion again and upload the meta
torrent M into BitTorrent. The SSFID will then be based on the digests in
the meta meta torrent X. The number of digest in X will be lower than in M 
as the meta torrent M is even smaller than .torrent T, resulting in the
desired small SSFID. Basically this means that a client should recursively
download files that are torrents until it gets a file with different
contents.

Blocksize of the .torrent T (single recursion) is calculated from the URL U as
follows. Blocksize is equal to the size of T divided by the number of
digests rounded upward to the first power of 2. The number of digests
is derived from the length of the BASE64-decoded SSFID and the digest
algorithm used. The version tells which digest algorithm was used, currently
SHA-1 (version 0x00).

Web servers can publish the btp:// URL in .torrenturl files that are
associated to BitTorrent clients via a MIME type e.g.
application/x-bittorrenturl.

Comments, please?

ttfn, Ed



More information about the BitTorrent mailing list