[Lightning-dev] Laundry list of inter-peer wire protocol changes

[Anthony Towns]

On Fri, Jan 29, 2016 at 12:05:35PM +1030, Rusty Russell wrote:
> > Probably doesn't really matter, but I think it leads me to prefer Rusty's
> > construction. Might be good to have an explanation with it diagrammed
> > as an n-way tree structure though, in a similar way to how you visualise
> > the elkrem tree...
> Definitely; a 64-deep binary tree is a 64-dimensional 1x1...x1
> hypercube, but the former is less brainhurty.

Nono, you don't need hypercubes to describe shachain, just a tree.
Voila:

[attached]

(Okay, so technically it's a spanning tree for a hypercube, fine,
whatever. I guess you can kind-of see the outline of the 4d hypercube
in the picture if you look hard enough...)

In the notation I'm using, H(p||x) means "flip the xth bit from the
parent hash/seed then hash" [0]. So to get to the hash for 10 you do:

   SHA256( SHA256( seed with bit 3 flipped ) with bit 1 flipped )

The subtrees are all very self-similar, and extending past 2**n just means
adding a new branch off from 0. Because it's so self-similar adding the
branch is just literally copying the existing tree, adding 2**n to all the
node values, and then adding a H(p||n) step from 0 to keep it connected.

Python code for generating the graph also attached, for whatever that's
worth. Layout gets a bit painful when you add an additional dimension to
get up to 32 nodes.

Cheers,
aj

[0] Or, alternatively and IMO preferably, append the number "x" and
    hash.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: shachain.png
Type: image/png
Size: 48127 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20160129/2463d873/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: shachain.py
Type: text/x-python
Size: 798 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20160129/2463d873/attachment-0001.py>