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

[tahoe-lafs]

#1813: Choice of tree-hash
------------------------------+------------------------
     Reporter:  CodesInChaos  |      Owner:  davidsarah
         Type:  enhancement   |     Status:  new
     Priority:  minor         |  Milestone:  undecided
    Component:  unknown       |    Version:  n/a
   Resolution:                |   Keywords:  newcaps
Launchpad Bug:                |
------------------------------+------------------------

Comment (by davidsarah):

 There may be a slight performance benefit to non-binary trees, at the
 expense of an increase in size of the uncle chain for a given leaf block.
 Here's the expansion in size of the uncle chain relative to a binary tree,
 for arities k = 2..16:

 {{{
 >>> from math import log
 >>> for k in xrange(2, 17): print "%3d %8.3f" % (k, (k-1) * log(2.0, k))
 ...
   2    1.000
   3    1.262
   4    1.500
   5    1.723
   6    1.934
   7    2.137
   8    2.333
   9    2.524
  10    2.709
  11    2.891
  12    3.068
  13    3.243
  14    3.414
  15    3.583
  16    3.750
 }}}

 This is useful to increase the performance slightly if hashing k children
 in each intermediate hash can be done in the same time as hashing 2
 children. (That depends on which hash is used, but most hashes have an
 input block size larger than their output size.)

 I'll look up some references for papers on tree hashes.

-- 
Ticket URL: <https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1813#comment:1>
tahoe-lafs <https://tahoe-lafs.org>
secure decentralized storage