[tahoe-dev] [tahoe-lafs] #1813: Choice of tree-hash

CodesInChaos codesinchaos at gmail.com
Thu Sep 20 07:57:01 UTC 2012


The CPU overhead of tree-hashing depends a lot on the particular hash
function, and how you use it. In particular the interaction of the
blocksize, hashsize, padding and finalization. But I estimate that
it's only about 15% compared to a flat hash, for a leaf size of 1 KiB.
So the increase in software complexity using a higher branching factor
doesn't seem worthwhile. If those 15% worry you, I'd rather double the
leaf size.

The official Skein treehash skips finalization for anything but the
root, since finalization is only required for full pseudo-randomness,
and not for pre-image/collision resistance. This halves the overhead
from 15% to 8%.



More information about the tahoe-dev mailing list