From aj at erisian.com.au Fri Jan 29 04:37:33 2016 From: aj at erisian.com.au (Anthony Towns) Date: Fri, 29 Jan 2016 14:37:33 +1000 Subject: [Lightning-dev] Laundry list of inter-peer wire protocol changes In-Reply-To: <87powlrwuw.fsf@rustcorp.com.au> References: <87d1snvhyf.fsf@rustcorp.com.au> <20160127142229.GA17540@sapphire.erisian.com.au> <87powlrwuw.fsf@rustcorp.com.au> Message-ID: <20160129043733.GA20497@sapphire.erisian.com.au> 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: -------------- next part -------------- A non-text attachment was scrubbed... Name: shachain.py Type: text/x-python Size: 798 bytes Desc: not available URL: