5 ms·

BEP 30: Merkle hash torrent extension

66 points by mariorz 12y ago

andrewchambers 12y ago
Isn't this how git works? I would have thought bit torrent did this all along.
- deleted 12y ago
  [deleted]
- JeremyBanks 12y ago
  Not exactly. Git uses per-file, per-commit, and per-directory hashes. It does make up a sort of hash tree, but the tree does not descend within a given file. You need to hash the entire file and determine its hash to know if any of the pieces you have are valid. This would be a problem for large files if many of those pieces come from untrusted sources -- you'd have to spend a lot of time/bandwidth downloading invalid data before you realized it. This isn't generally the case for Git, but it for BitTorrent. BitTorrent traditionally solves this using a hash list. All of the data in a torrent is broken up between pieces of a chosen size, and hashes are calculated for each of those pieces individually. (These are generally not aligned with file boundaries, which is why you may have noticed that even if you tell your torrent to only download a certain set of files, you may still end up with some data from adjacent files.) This entirely hash list is included in the torrent file. For torrents with a lot of data, this could be 10MB or more. If you're using a magnet link, that torrent file needs to be downloaded from peers. This brings back the original problem: you need to download this entire large file before you know that the peer isn't just sending you random data. BEP-30 proposes a solution: generate a binary hash tree whose leaves are the torrent pieces, and include only the single root hash in the torrent file to keep it small. When you're getting pieces from a peer, they send you the missing inner hashes of the tree that you need to verify the piece. The minimum data transfer in ideal circumstances is increased a bit, but the peer-to-peer system is made more robust, able to identify invalid data much faster. I think it's a great modification to the protocol. Unfortunately it isn't widely-enough supported to be practical for general use.
  - im3w1l 12y ago
    >The minimum data transfer in ideal circumstances is increased by log(N) There should be roughly as many internal nodes as there are leaves, so there is a linear space increase. As the leaves are much bigger than the internal nodes, the linear factor is small.
- beagle3 12y ago
  git's smallest unit is a file - if your repostiory has one 3GB file, that's what is going to be hashed. but bup[0] does so within a git repository to make incremental backup more efficient. [0] https://github.com/bup/bup https://github.com/bup/bup
- rakoo 12y ago
  Yes it is, but it makes much more sense for git to use it: if a single byte is changed somewhere, you only need re-hashing the file and the trees up to the root; the other blobs/trees are left unchanged. It is very useful in this setting to reuse older existing hashes. In bittorrent, OTOH, we suppose every swarm will share different content, so there was no point making sure a hash would be reused somewhere.
qqueue 12y ago
Hash trees are pretty cool. For some fancier uses, see the Peer to Peer Streaming Protocol (PPSP), which is authored by the libswift/tribler guys. https://datatracker.ietf.org/wg/ppsp/documents/ https://datatracker.ietf.org/wg/ppsp/documents/ Basically, instead of the stream source having to sign every single new chunk (so peers can verify that they're getting the right data), the source signs subtree hashes of the new data and slowly builds up a larger hash tree. Once the stream is over, the complete hash tree is instantly seedable by anybody in the original stream.
- amirouche 12y ago
  The (other?) big win of pspp is the ability to stream live feeds.
zmanian 12y ago
Very similar to IPFS's merkle DAG and seems like a critical element of getting content centric networking projects like Bitorrent, Inc's Project Malestrom up and running
whyrusleeping 12y ago
ipfs uses exactly the same strategy to distribute content via the hash of their root merkleDAG node. http://ipfs.io http://ipfs.io
edonkey 12y ago
"Large torrent files put a strain on the Web servers distributing them". Finally! bittorrent designers are acknowledging the centralized deficiency in the torrent protocol and implementing Merkle / root hash distribution model, as eDonkey / eMule used since 2000's: https://en.wikipedia.org/wiki/Ed2k_URI_scheme#eD2k_hash_algorithm https://en.wikipedia.org/wiki/Ed2k_URI_scheme#eD2k_hash_algo... 15 years later, everything old is new again.
- ikeboy 12y ago
  >Last-Modified: Fri Aug 28 18:30:47 2009 +0000 9 years.
- gojomo 12y ago
  ED2K was kind of a degenerate Merkle tree: large chunks (9.5 MiB) and only one level of leaves, all under the root. Thus it didn't have some of the benefits of a full tree that this 2009 Bittorrent spec was hoping to achieve, such as verifying smaller-sized chunks without a metadata-cost that grows linearly with the size of the full resource. (AFAIK, the 1st application of multi-level Merkle trees to P2P filesharing was the TigerTree hash I wrote up with Justin Chapweske in 2002. At first glance, it looks like this proposal makes the same mistake we did in our first draft, not distinguishing between leaf and node hashes, corrected in the final TigerTree spec version of March 2003.)
  - JeremyBanks 12y ago
    Based on http://crypto.stackexchange.com/a/2108/342 http://crypto.stackexchange.com/a/2108/342: BEP-30 should be safe. On its own, that root hash may be vulnerable to length-extension collisions. However, the root hash is never provided alone. It's included with the length in the torrent's infohash, preventing length-extension.
  - adamzochowski 12y ago
    edonkey has two methods of file verification. The ED2K hash as you have mentioned. However, around 2004, edonkey world also received nicer AICH hashes. People that generate ed2k style links are encouraged to make include the To recap: ICH : inteligent corruption hash : also known as the old original ed2k method. Root hash is md4 and is generated from a series of md4 hashes generated for 9.5mb chunks. If a file is below 9.5mb then ed2k root hash is just the real md4 hash. AICH : Advanced inteligent corruption hash : is a full Merkle tree using SHA1, where chunks are 180kb (with exception of a chunk on the 9.5MiB boundary). This weird part/chunking allows to map 53 of these AICH chunks perfectly into the ed2k chunks. More on this available at : http://www.emule-project.net/home/perl/help.cgi?l=1&rm=show_topic&topic_id=589 http://www.emule-project.net/home/perl/help.cgi?l=1&rm=show_... http://en.wikipedia.org/wiki/EMule#Basic_concepts http://en.wikipedia.org/wiki/EMule#Basic_concepts http://wiki.amule.org/t/index.php?title=AICH_Hashset http://wiki.amule.org/t/index.php?title=AICH_Hashset
amluto 12y ago
I think it's sad that they're using SHA-1 for this. SHA-1 is a bit weak, and the hashes are too short. There's a reason that SHA-1 is deprecated for X.509 certificates. At the very least, this should use SHA-256. If they really did it right, though, the protocol would use a secure tree hash. The construction they're using has trivial collisions, which are only avoided because the size of the file comes from a trusted source. A good hash (e.g. the Sakura construction) doesn't have this problem. Fixing that would make the resulting torrent files or URLs a bit shorter, as the size could potentially be omitted.
- mox1 12y ago
  Are you serious? Realistically, these are bits of a video stream, not your bitcoin wallet or some other bits where security it of the upmost concern. Were talking millions of dollars of equipment to find a collision in SHA1 today.... How exactly is a 160 bit hash too short? Collisions can be had after 2^80 trys in naive scenario and 2^57.5 with an active attacker, not exactly easy...
  - amluto 12y ago
    Torrents can be, and often are, executable. Many Linux distributions are available over Bittorrent, for example. Breaking crypto, especially new crypto, should pass a much higher bar than "not exactly easy". 2^57.5 is not all that large by the standards of a big cloud provider or a government.
    - mox1 12y ago
      Again "not exactly easy" today will cost you > $1 MILLION dollars, you are greatly exaggerating the actual problem. If you have millions of dollars to spend and want to commit digital crimes, there are better methods than flipping bits in torrents......
      - wereHamster 12y ago
        $1 million today, at the cost of the average PC in a couple years. Think of the future.

66 points by mariorz 12y ago

andrewchambers 12y ago

Isn't this how git works? I would have thought bit torrent did this all along.

deleted 12y ago
[deleted]
JeremyBanks 12y ago
Not exactly. Git uses per-file, per-commit, and per-directory hashes. It does make up a sort of hash tree, but the tree does not descend within a given file. You need to hash the entire file and determine its hash to know if any of the pieces you have are valid. This would be a problem for large files if many of those pieces come from untrusted sources -- you'd have to spend a lot of time/bandwidth downloading invalid data before you realized it. This isn't generally the case for Git, but it for BitTorrent. BitTorrent traditionally solves this using a hash list. All of the data in a torrent is broken up between pieces of a chosen size, and hashes are calculated for each of those pieces individually. (These are generally not aligned with file boundaries, which is why you may have noticed that even if you tell your torrent to only download a certain set of files, you may still end up with some data from adjacent files.) This entirely hash list is included in the torrent file. For torrents with a lot of data, this could be 10MB or more. If you're using a magnet link, that torrent file needs to be downloaded from peers. This brings back the original problem: you need to download this entire large file before you know that the peer isn't just sending you random data. BEP-30 proposes a solution: generate a binary hash tree whose leaves are the torrent pieces, and include only the single root hash in the torrent file to keep it small. When you're getting pieces from a peer, they send you the missing inner hashes of the tree that you need to verify the piece. The minimum data transfer in ideal circumstances is increased a bit, but the peer-to-peer system is made more robust, able to identify invalid data much faster. I think it's a great modification to the protocol. Unfortunately it isn't widely-enough supported to be practical for general use.
- im3w1l 12y ago
  >The minimum data transfer in ideal circumstances is increased by log(N) There should be roughly as many internal nodes as there are leaves, so there is a linear space increase. As the leaves are much bigger than the internal nodes, the linear factor is small.
beagle3 12y ago
git's smallest unit is a file - if your repostiory has one 3GB file, that's what is going to be hashed. but bup[0] does so within a git repository to make incremental backup more efficient. [0] https://github.com/bup/bup https://github.com/bup/bup
rakoo 12y ago
Yes it is, but it makes much more sense for git to use it: if a single byte is changed somewhere, you only need re-hashing the file and the trees up to the root; the other blobs/trees are left unchanged. It is very useful in this setting to reuse older existing hashes. In bittorrent, OTOH, we suppose every swarm will share different content, so there was no point making sure a hash would be reused somewhere.

qqueue 12y ago

Hash trees are pretty cool. For some fancier uses, see the Peer to Peer Streaming Protocol (PPSP), which is authored by the libswift/tribler guys. https://datatracker.ietf.org/wg/ppsp/documents/ https://datatracker.ietf.org/wg/ppsp/documents/ Basically, instead of the stream source having to sign every single new chunk (so peers can verify that they're getting the right data), the source signs subtree hashes of the new data and slowly builds up a larger hash tree. Once the stream is over, the complete hash tree is instantly seedable by anybody in the original stream.

amirouche 12y ago
The (other?) big win of pspp is the ability to stream live feeds.

zmanian 12y ago

Very similar to IPFS's merkle DAG and seems like a critical element of getting content centric networking projects like Bitorrent, Inc's Project Malestrom up and running

whyrusleeping 12y ago

ipfs uses exactly the same strategy to distribute content via the hash of their root merkleDAG node. http://ipfs.io http://ipfs.io

edonkey 12y ago

"Large torrent files put a strain on the Web servers distributing them". Finally! bittorrent designers are acknowledging the centralized deficiency in the torrent protocol and implementing Merkle / root hash distribution model, as eDonkey / eMule used since 2000's: https://en.wikipedia.org/wiki/Ed2k_URI_scheme#eD2k_hash_algorithm https://en.wikipedia.org/wiki/Ed2k_URI_scheme#eD2k_hash_algo... 15 years later, everything old is new again.

ikeboy 12y ago
>Last-Modified: Fri Aug 28 18:30:47 2009 +0000 9 years.
gojomo 12y ago
ED2K was kind of a degenerate Merkle tree: large chunks (9.5 MiB) and only one level of leaves, all under the root. Thus it didn't have some of the benefits of a full tree that this 2009 Bittorrent spec was hoping to achieve, such as verifying smaller-sized chunks without a metadata-cost that grows linearly with the size of the full resource. (AFAIK, the 1st application of multi-level Merkle trees to P2P filesharing was the TigerTree hash I wrote up with Justin Chapweske in 2002. At first glance, it looks like this proposal makes the same mistake we did in our first draft, not distinguishing between leaf and node hashes, corrected in the final TigerTree spec version of March 2003.)
- JeremyBanks 12y ago
  Based on http://crypto.stackexchange.com/a/2108/342 http://crypto.stackexchange.com/a/2108/342: BEP-30 should be safe. On its own, that root hash may be vulnerable to length-extension collisions. However, the root hash is never provided alone. It's included with the length in the torrent's infohash, preventing length-extension.
- adamzochowski 12y ago
  edonkey has two methods of file verification. The ED2K hash as you have mentioned. However, around 2004, edonkey world also received nicer AICH hashes. People that generate ed2k style links are encouraged to make include the To recap: ICH : inteligent corruption hash : also known as the old original ed2k method. Root hash is md4 and is generated from a series of md4 hashes generated for 9.5mb chunks. If a file is below 9.5mb then ed2k root hash is just the real md4 hash. AICH : Advanced inteligent corruption hash : is a full Merkle tree using SHA1, where chunks are 180kb (with exception of a chunk on the 9.5MiB boundary). This weird part/chunking allows to map 53 of these AICH chunks perfectly into the ed2k chunks. More on this available at : http://www.emule-project.net/home/perl/help.cgi?l=1&rm=show_topic&topic_id=589 http://www.emule-project.net/home/perl/help.cgi?l=1&rm=show_... http://en.wikipedia.org/wiki/EMule#Basic_concepts http://en.wikipedia.org/wiki/EMule#Basic_concepts http://wiki.amule.org/t/index.php?title=AICH_Hashset http://wiki.amule.org/t/index.php?title=AICH_Hashset

amluto 12y ago

I think it's sad that they're using SHA-1 for this. SHA-1 is a bit weak, and the hashes are too short. There's a reason that SHA-1 is deprecated for X.509 certificates. At the very least, this should use SHA-256. If they really did it right, though, the protocol would use a secure tree hash. The construction they're using has trivial collisions, which are only avoided because the size of the file comes from a trusted source. A good hash (e.g. the Sakura construction) doesn't have this problem. Fixing that would make the resulting torrent files or URLs a bit shorter, as the size could potentially be omitted.

mox1 12y ago
Are you serious? Realistically, these are bits of a video stream, not your bitcoin wallet or some other bits where security it of the upmost concern. Were talking millions of dollars of equipment to find a collision in SHA1 today.... How exactly is a 160 bit hash too short? Collisions can be had after 2^80 trys in naive scenario and 2^57.5 with an active attacker, not exactly easy...
- amluto 12y ago
  Torrents can be, and often are, executable. Many Linux distributions are available over Bittorrent, for example. Breaking crypto, especially new crypto, should pass a much higher bar than "not exactly easy". 2^57.5 is not all that large by the standards of a big cloud provider or a government.
  - mox1 12y ago
    Again "not exactly easy" today will cost you > $1 MILLION dollars, you are greatly exaggerating the actual problem. If you have millions of dollars to spend and want to commit digital crimes, there are better methods than flipping bits in torrents......
    - wereHamster 12y ago
      $1 million today, at the cost of the average PC in a couple years. Think of the future.