Re: Back to Merkle Hash Trees...

----- Original Message ----- 
From: "Elliott Mitchell" <[email protected]>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...


>>From: Joseph Ashwood <[email protected]>
> If there is only one way to construct the tree, the above is implicit in
> the structure of the tree. If it is tampered with the hashes won't
> verify.

Not quite, there are cryptographic attacks that you're not considering. In 
particular the preimage reorder attack, where carefully chosen input blocks 
are reordered without changing the upper hash, see the latest SHA/MD5 attack 
for examples of doing this as well as the reordered preimage attacks 
proposed as a result that apply to all hashes, and can be addressed at the 
protocol level.

> Given hashes for a pair of siblings, you can compute the parent hash. So,
> if you have the hashes for all direct children of the root you can verify
> them as a group. Once these are verified you can confirm all of the next
> level. This continues down to the leaves.
> If the leaves are marked similar to how THEX suggests, then you cannot
> pass off a leaf as an internal node nor can you pass an internal node off
> as a leaf without breaking the hash.

Under the preimage reorder there's no need to pass off external/internal as 
internal/external in order to break the hash.

> This is not the only possible handling of Merkle though. If blocks of
> tree nodes are handled similarly to any other data blocks, you only
> transfer the tree nodes once and only verify them once. At which point
> the work and data overhead becomes O(n), where n is the size of the file.
> The overhead will be slightly higher if you only do a partial transfer.

Most of this is good, but you're forgetting that there are nlogn hashes to 
be verified, and that the hashes have significant overhead at termination, 
so the time taken is actually O(n+fixed) for small n (e.g. internal nodes 
with few children) the fixed comes to dominate, and the fixed time actually 
has a major impact on the overall hash speed for a few kilobytes. 16K chunks 
should be enough to dominate this as long as there is a reasonable branching 
order to the Merkle tree (part of the reason I prefer my proposal is that by 
setting the #children to a 32-bit number the branching order can be 4 
billion enough to quickly dominate the fixed cost).

> Verification on receipt implies verification before sending on. There
> must be something I'm missing here.

This should happen, and almost always does happen, but seemingly in any 
large download there are always a few bad blocks received, and so by 
relation a few bad blocks have been sent by someone else. This bad block 
sending by someone else means that the other end did not verify the block 
before sending it. This assumes a stable transfer medium, but TCP is 
designed to supply exactly that.


>> RootHash = hash(data, hash( for all Level1 hash))
>> Level1 hash [i]= hash(datasegment[i], hash(for all Level2 hash))
>> LevelM hash[i] = hash(datasegment[i], hash(for all LevelM+1 hash))
>> LevelK hash[i] = hash(datasegment[i], 0000...0000)
>> (for known K) where for each level the datasegment length is decreased by 
>> a
>> given factor. This creates an O(1) lookup for each datasegment hash of 
>> any
>> of the established sizes. At the cost that the initial hash must be
>> performed K times resulting in a creation time of O(Kn), as opposed to 
>> the
>> Merkle trees O(nlogn).
>>
>> The other downside is that it still maintains the size of a Merkle tree,
>> something which is simply unnecessary for BitTorrent's uses.
>
> Interesting construction. I must suggest that this is very nearly
> equivalent to a Merkle tree in every way. I note that it looks to be much
> more expensive to compute though. I also not see it being easier to verify
> either incrementally nor as a whole.

I didn't design it to necessarily be easier to compute, I designed it to be 
easier to verify, and I will admit that I foolishly left out the critical 
serialization information (see my other statements on preimage reorder 
attacks).

> To verify a block, you appear to need the block, then you need the hashes
> of all sibling blocks and the parent block for the next level up. You
> then appear to need the same for all higher levels. You're likely to
> transfer those and they appear much larger than Merkle's.

The cost of initial verification of a block (should be good enough to send 
on) is reduced to O(blockSize), because the lookup takes O(1) and the 
verification O(blocksize). Once the a sufficient number of blocks have been 
received to verify a hash in the next level it can be moved up. Eventually 
moving the entire file up to the top level. Assuming a sufficient branching 
order, there will only be the necessity for a 2 or 3 levels (assuming 
branching order of >2^16). Like I said before it was not aimed at being 
computationally cheap, and I actually pointed out initially that it is 
computationally more expensive being O(Kn) versus Merkles O(nlogn), and 
taking up the same space. It does however directly address the first 
preimage problems by creating direct propogation of data instead of hash 
propogation. This means a tighter security model, one where the attacker 
cannot depend on the postimage data to rectify any problems because a 
substantial portion of the postimage data will change. That is not to say 
that it is entirely secure, it does in fact suffer under the attacks 
proposed against SHA-0 and MD5, that is unless the branching is continued 
down to block of sizeof(hash(x)) in which case the unicity distance proofs 
apply as long as it is a strong hash under other (easier) constraints. This 
same argument cannot necessarily be applied to hash trees because the 
pre/postimage relationship is blinded by a hash function.

I would not suggest using my iterated hash construction though because the 
proofs of the approx same strength can be derived for the Merkle 
construction I posted elsewhere, without the extra computational overhead.
                Joe 



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/