[p2p-hackers] Homomorphic hashing and fountain codes - implementation question (fwd)

[Michael J. Freedman]

[Looks like Max was getting his posts rejected from the mailing list, so
I'm forwarding his response.  --mike]

---------- Forwarded message ----------
Date: Sat, 26 Feb 2005 12:53:31 -0500
From: Maxwell Krohn <krohn at mit.edu>
To: Hal Finney <hal at finney.org>
Cc: Michael J Freedman <mfreed at scs.cs.nyu.edu>, p2p-hackers at zgp.org
Subject: Re: [p2p-hackers] Homomorphic hashing and fountain codes -
     implementation question (fwd)

This is the response I sent to Nick personally about the one-bit
overflow problem. This was the simplest solution we came up with.  It
makes all encoded blocks 1/256 bigger, where 256 is the number of bits
per sub-block.

Maxwell Krohn (krohn at mit.edu) wrote:
> Hi,
>
> There might be 1 overflow bit per subblock, making 512 bits per
> block, and 16 bytes per block of overflow bits.
>
> Our implementation of the Codes is here by the way, available by
> anonymous CVS:
>
> http://cvs.pdos.lcs.mit.edu/cvs/codes1/
>
> In memory, for the encoders and decoders, we store subblocks as big
> integers, which can grow to 257 bits long.  However, for sending over
> the network (and storing on disk, perhaps) we want a denser packing.  So
> what we do is we sheer off the top bit of each subblock and pack them
> together at the beginning of every block.  In our implementation, it's
> called the "carrybitmap_t" object, which you can grep for in our code.
>
> Hope this helps,
>
> Max