Anthony Towns [ARCHIVE] on Nostr: 📅 Original date posted:2016-01-29 📝 Original message: On Fri, Jan 29, 2016 at ...
📅 Original date posted:2016-01-29
📝 Original message:
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>;
📝 Original message:
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>;