alexpdev
commented
1 year ago Have you read the documentation on it? https://www.bittorrent.org/beps/bep_0030.html
I'm kinda lost in understanding of torrent.py's
The merkle roots are not calculated in torrent.py they are calculated in hasher.py. The entire version 2 implementation is contained in the the HasherV2 class.
def merkle_root(blocks: list) -> bytes:
"""
Calculate the merkle root for a seq of sha256 hash digests.
Parameters
----------
blocks : list
a sequence of sha256 layer hashes.
Returns
-------
bytes
the sha256 root hash of the merkle tree.
"""
if blocks:
while len(blocks) > 1:
blocks = [
sha256(x + y).digest() for x, y in zip(*[iter(blocks)] * 2)
]
return blocks[0]
return blocks
class HasherV2:
"""
Calculate the root hash and piece layers for file contents.
Iterates over 16KiB blocks of data from given file, hashes the data,
then creates a hash tree from the individual block hashes until size of
hashed data equals the piece-length. Then continues the hash tree until
root hash is calculated.
Parameters
----------
path : str
Path to file.
piece_length : int
Size of layer hashes pieces.
"""
def __init__(self, path: str, piece_length: int):
"""
Calculate and store hash information for specific file.
"""
self.path = path
self.root = None
self.piece_layer = None
self.layer_hashes = []
self.piece_length = piece_length
self.num_blocks = piece_length // BLOCK_SIZE
with open(self.path, "rb") as fd:
self.process_file(fd)
def process_file(self, fd: str):
"""
Calculate hashes over 16KiB chuncks of file content.
Parameters
----------
fd : TextIOWrapper
Opened file in read mode.
"""
while True:
blocks = []
leaf = bytearray(BLOCK_SIZE)
# generate leaves of merkle tree
for _ in range(self.num_blocks):
size = fd.readinto(leaf)
if not size:
break
blocks.append(sha256(leaf[:size]).digest())
# blocks is empty mean eof
if not blocks:
break
if len(blocks) != self.num_blocks:
# when size of file doesn't fill the last block
# when the file contains multiple pieces
remaining = self.num_blocks - len(blocks)
if not self.layer_hashes:
# when the there is only one block for file
power2 = next_power_2(len(blocks))
remaining = power2 - len(blocks)
# pad the the rest with zeroes to fill remaining space.
padding = [bytes(32) for _ in range(remaining)]
blocks.extend(padding)
# calculate the root hash for the merkle tree up to piece-length
layer_hash = merkle_root(blocks)
self.layer_hashes.append(layer_hash)
self._calculate_root()
def _calculate_root(self):
"""Calculate root hash for the target file."""
self.piece_layer = b"".join(self.layer_hashes)
hashes = len(self.layer_hashes)
if hashes > 1:
pow2 = next_power_2(hashes)
remainder = pow2 - hashes
pad_piece = [bytes(HASH_SIZE) for _ in range(self.num_blocks)]
for _ in range(remainder):
self.layer_hashes.append(merkle_root(pad_piece))
self.root = merkle_root(self.layer_hashes)An oversimplified explanation is that you break the file into pieces just like you do in the version 1 protocol, but instead of using piece-length blocks of the file you instead use 16KiB blocks of the file. Then once you have the entire file broken into 16KiB blocks and their sha256 hashes, you iterate through them pairwise and hash their hashes together, which would leave you with exactly half the number of hashes. Then you apply the same process over again until you finally reach the root hash.
kovalensky
I'm kinda lost in understanding of torrent.py's merkle root hash creation, I'm trying to write a function in php to calculate root hashes of files, I can create v1 implementations but still struggling with v2, could you please provide me a simple one block python code function to generate root hash from given file so I could inspect it and learn how to write something equal in php, I know it's too much to ask, but I'm just lost in hash functions, thanks.