I wish you had mentioned it before I implemented the two level hash classes :-).
I'm not sure it is necessary for us though. I can see the advantage when sending large pieces of data where each part needs to be a certain size, but that is not really the case for us. Firstly data on freenet is limited in size anyways, and secondly it is not necessary for us to support arbitrarily small parts. I think that splitting into 20 parts ought to be enough even for large documents, since somebody downloading something really big is also likely to have a faster connection. And 20*40 hex characters is not more then what we can fit in a storable field. On Sat, 29 Apr 2000, hal at finney.org wrote: > A while back I described a way of hashing stream data such that bad data > could be detected and rejected before waiting for the end of the stream. > That was a two-level hash where each block of data gets hashed, and a > table of all these hashes is sent before the data; that table is itself > hashed to form the overall hash of the document (the CHK). > > Looking through some old crypto papers I found an alternative scheme > from the Crypto 97 conference. It introduces a complication in the > stream transfer but has some advantages. > > Similar to the earlier idea, the data is broken up into blocks and each > block is hashed. However the hashes are computed from the last block > to the first, and each block's hash covers that block's data PLUS the > hash of the next block. > > So the last block is hashed to form H(n). For the next to the last > block we hash that block's data plus H(n) to get H(n-1). For the block > before that we hash the data plus H(n-1) to get H(n-2), etc. At the > end we hash the first block of data plus the hash for the next block, > and that is the hash of the whole document which is the CHK. > > Graphically, the data is calculated as follows: > > H(N) = hash( block_N ) > H(N-1) = hash( block_N-1 + H(N) ) > ... > HH(1) = hash( block_1 + H(2) ) > H(0) = hash( block_0 + H(1) ) > > CHK = H(0) > > Now what happens is that as we send the data, we send each block plus > the hash for the next block. The data gets stored in this form; the > client software would have to strip out the hashes. (It has to know > about the special format anyway because it is going to calculate and > verify the hashes.) So the data is stored and sent as block_0, H(1), > block_1, H(2), block_2, ... > > When the first block is sent, along with the hash for the next block, > this data is hashed and compared with the CHK. If it matches we continue, > storing the hash for the next block. When we receive that next block, > we hash it and compare with our stored hash. If OK we then update the > stored hash from the data in that block and proceed. > > This is similar to the two-level hash concept, except the per-block hashes > are stored with the blocks rather than at the front. That is better because > there is no need to deal with a potentially large table of hashes, rather the > data is spread out into the stream. > > By chaining the blocks together, H(0) depending on H(1) which depends on > H(2), there is no way a node can forge a partial message which matches > the CHK. So it has the same strong properties as an overall hash. > > Calculating the hash data would take some effort. It has to be calculated > back to front (which is what prevents a rogue node from substituting > data front to back). The sending client could make a copy of the data, > leaving room for the hash blocks, then go through and insert them in the > file one at a time, last to first. Alternatively it could go ahead and > make a large table of all the hashes, and interleave them into the data > stream as it goes out. Doing it this way would be more similar to the > two-level hash proposal, but it would eliminate one of the potential > advantages of this method, the avoidance of the need for a large table. > > All in all I'm not sure which way is better, but I thought I'd mention > this one as an alternative. > > Hal > > _______________________________________________ > Freenet-dev mailing list > Freenet-dev at lists.sourceforge.net > http://lists.sourceforge.net/mailman/listinfo/freenet-dev -- Oskar Sandberg md98-osa at nada.kth.se #!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj $/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1 lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/) _______________________________________________ Freenet-dev mailing list Freenet-dev at lists.sourceforge.net http://lists.sourceforge.net/mailman/listinfo/freenet-dev
