[tahoe-dev] Recombinant Hashes

David-Sarah Hopwood david-sarah at jacaranda.org
Fri Feb 12 05:31:51 UTC 2010


Chris Dew wrote:
> I'm a bit confused by your reply.  I hope you could expand on it.
> There are 12 hashes created (numbered from 0 to confuse people).

Then first let me fix the arithmetic:

>> In the demo, 5 of 12 hashes are needed to recover the data. But the
>> maximum input size was 16 bytes, and the total size of the hashes was
>> 12*4 = 48 bytes. That's an expansion of 48/16 = 3, when an expansion
>> of 12/5 = 2.4 should be possible.

> Any number of hashes can be created, I just chose 12 as it is a nice
> number.  There could have been 1000 hashes.  I don't understand the
> term 'expansion'.

As I'm using it (and the Tahoe does use it), "expansion" is the total
output size of the shares or hashes, divided by the input size. This is the
reciprocal of the "code rate": <http://en.wikipedia.org/wiki/Code_rate>
It's defined only for a given total output size.

> Is unlimited expansion what defines a fountain code
> - or is the definition restricted to variants of the 'random linear
> fountain'?
> 
> The efficiency of my algorithm increases as you increase the number of
> hashes.  I restricted the demo to a short block of data and a limited
> number of hashes.  In fact only 4 hashes an one bit from a fifth hash
> is required to get back the data.  That was too complicated for a
> demo.

Ah, OK. So your code actually has near-optimal expansion or code rate
on this example.

According to this ticket: <http://allmydata.org/trac/tahoe/ticket/678>,
the FEC code that Tahoe uses also has the property that the content of
some initial subset of shares does not depend on the total number of
shares. If that's correct, it's not clear to me why it it's not also
classified as a fountain code, although I've never heard of Reed-Solomon
codes referred to as fountain codes.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://tahoe-lafs.org/pipermail/tahoe-dev/attachments/20100212/be896547/attachment.asc>


More information about the tahoe-dev mailing list