3 ms·

Can someone explain how the Merkle-tree concept is useful? I didn't quite catch that part. On the one hand it is says: > all you need is the root hash of the t

Can someone explain how the Merkle-tree concept is useful? I didn't quite catch that part. On the one hand it is says: > all you need is the root hash of the tree. but on the other hand: > the .torrent file must still contain these piece hashes So what are we saving here? If a piece hash doesn't match the downloaded data, we re-download the piece.

chasil 5y ago
The main use of a Merkle tree that I know of is the filesystem "scrub" operation in ZFS and BtrFS. https://en.wikipedia.org/wiki/Merkle_tree https://en.wikipedia.org/wiki/Merkle_tree
cyphar 5y ago
The .torrent file is separate to the torrent metadata which you need to fetch for magnet links. This is mentioned a bit later in that section: > The .torrent file size is not smaller for a v2 torrent, since it still contains the piece hashes, but the info-dictionary is, which is the part needed for magnet links to start downloading. Also it seems that it'll be easier to detect peers which are sending bad data and correct it. I guess this is because previously you could fetch a piece from more than one peer but because the hashing was done at the piece level you didn't know which part of the block was wrong (meaning you'd have to redownload the whole thing). But now you can -- with a bit of tracking -- tell which block of a piece was sent from which peer and then redownload it from another (likely blocking the original peer), because you know which block hash failed to validate. (EDIT: This is correct -- [1] explains the issue and how torrent clients have worked around this problem in v1 torrents.) Merkle trees have some other benefits (you can cache parts of the tree in such a way that repeatedly checksumming data where lots of leaves are unchanged is cheaper, and you can efficiently prove that a given leaf was part of the hash), but I don't know if that's going to be useful for BitTorrent. [1]: https://blog.libtorrent.org/2011/11/smart-ban/ https://blog.libtorrent.org/2011/11/smart-ban/

chasil 5y ago

The main use of a Merkle tree that I know of is the filesystem "scrub" operation in ZFS and BtrFS. https://en.wikipedia.org/wiki/Merkle_tree https://en.wikipedia.org/wiki/Merkle_tree

cyphar 5y ago

The .torrent file is separate to the torrent metadata which you need to fetch for magnet links. This is mentioned a bit later in that section: > The .torrent file size is not smaller for a v2 torrent, since it still contains the piece hashes, but the info-dictionary is, which is the part needed for magnet links to start downloading. Also it seems that it'll be easier to detect peers which are sending bad data and correct it. I guess this is because previously you could fetch a piece from more than one peer but because the hashing was done at the piece level you didn't know which part of the block was wrong (meaning you'd have to redownload the whole thing). But now you can -- with a bit of tracking -- tell which block of a piece was sent from which peer and then redownload it from another (likely blocking the original peer), because you know which block hash failed to validate. (EDIT: This is correct -- [1] explains the issue and how torrent clients have worked around this problem in v1 torrents.) Merkle trees have some other benefits (you can cache parts of the tree in such a way that repeatedly checksumming data where lots of leaves are unchanged is cheaper, and you can efficiently prove that a given leaf was part of the hash), but I don't know if that's going to be useful for BitTorrent. [1]: https://blog.libtorrent.org/2011/11/smart-ban/ https://blog.libtorrent.org/2011/11/smart-ban/