flat-tree.log

15:25 <+mafintosh> yoshuawuyts: the purpose of the method is finding the "best" signature that signs your current chunk of data
15:26 <+mafintosh> best meaning the newest one, cause then you have to verify fewer signatures overall
15:26 <+mafintosh> verifying a sig is expensive
15:27 <+mafintosh> the way it does it is by first finding the root of the tree of the chunk, https://github.com/mafintosh/hypercore/blob/master/lib/tree-index.js#L119-L127
15:27 <+mafintosh> (that you have locally)
15:27 <+mafintosh> the after finding that root you need to find a signature that includes that root
15:28 <+mafintosh> this is done by expanding down right
15:28 <+mafintosh> yoshuawuyts: fx, if you run print-flat-tree {0..10}
15:28 <+mafintosh> then notice the blue values
15:28 <+mafintosh> the blue values are the roots signed by the green one
15:28 <yoshuawuyts> mafintosh: oh what
15:29 <yoshuawuyts> mafintosh: so 3 and 8 are signed by 10
15:29 <+mafintosh> in the case of {0..10} it is 3 and 8 are signed by 10
15:29 <+mafintosh> yes exactly
15:29 <yoshuawuyts> mafintosh: ohhhhhhhhhhh
15:29 <+mafintosh> so once you have your root your goal is finding the newest node that signs that root
15:30 <+mafintosh> yoshuawuyts: that's what i do here, https://github.com/mafintosh/hypercore/blob/master/lib/tree-index.js#L129-L138
15:30 <+mafintosh> yoshuawuyts: it's a bit clever
15:30 <yoshuawuyts> mafintosh: ahaha
15:43 <+mafintosh> yoshuawuyts: no 27 always holds the hashes of 25 and 29
15:44 <+mafintosh> but as a peer you might not have 29 and 25 both when you have 27
15:44 <+mafintosh> depends on the order of chunks you download
15:45 <yoshuawuyts> right right right
15:46 <yoshuawuyts> hmmmmm
15:46 <yoshuawuyts> I'm having trouble reconcilliating these two ideas
15:46 <yoshuawuyts> on the one hand it seems we have a determined order - the tree structure is the order we think about the tree
15:46 <yoshuawuyts> left-hand side is all data
15:46 <yoshuawuyts> right hand side is hashes of hashes of hashes
15:47 <yoshuawuyts> but then you were just explaining that we store the hashes of things further left of the tree, further right in the tree
15:47 <yoshuawuyts> I understand both separately now; but not sure how they combine
15:47 <yoshuawuyts> oh damn, I'm using two definitions of "left / right" here also
15:48 <yoshuawuyts> The first one is "higher up in the tree". And the second one is "further right in the tree"
15:48 — yoshuawuyts definitely wants to document this
15:49 <+mafintosh> yoshuawuyts: the tree is always representing the same
15:49 <+mafintosh> leafs are data, everything else is hashes
15:50 <+mafintosh> a hash hashes together two children (merkle tree)
15:50 <yoshuawuyts> yes, right
15:50 <+mafintosh> every leaf has a signature that signs all the current roots at that point in time
15:51 <yoshuawuyts> OH!
15:51 <yoshuawuyts> AHHH
15:51 <yoshuawuyts> yes
15:51 <yoshuawuyts> okay
15:51 <yoshuawuyts> alright, that IS pretty clever
15:51 <yoshuawuyts> damn you :P
15:51 <+mafintosh> and for efficiency you wanna replicate as few sigs as possible
15:51 <yoshuawuyts> yes, that makes a lot of sense
15:51 <+mafintosh> :)
15:52 <yoshuawuyts> that took me a while to realize
15:52 <yoshuawuyts> but got it
15:52 <+mafintosh> but def document this in detail
15:52 <+mafintosh> ya it's dense
15:52 <yoshuawuyts> not sure...
15:52 <yoshuawuyts> I'm doing that right now :P
15:52 <yoshuawuyts> e.g. signing things correctly
15:52 <yoshuawuyts> in https://github.com/datrs/merkle-tree-stream I mean
15:54 <yoshuawuyts> but understand it enough now that I can dive back in

15:30 <+mafintosh> yoshuawuyts: basically what you can do is, given the root, pick the *next* node with the same depths left child
15:30 <yoshuawuyts> mafintosh: I like this a lot - I was picturing it wrong
15:31 <+mafintosh> that is the best case scenario of nodes to have
15:31 <+mafintosh> cause it's the next root that spans the widest area
15:31 <+mafintosh> yoshuawuyts: so in your example pic you posted above ...
15:32 <+mafintosh> if your chunk is 20 and the root you have for that is 19
15:32 <+mafintosh> the 19's next node with same depth is 27
15:32 <+mafintosh> and 27's left sibling is 25
15:32 <+mafintosh> so you check if you have 25
15:33 <+mafintosh> if so, you pick the next node after 25 with the same depth, and that's left child etc
15:33 <+mafintosh> if not! you pick 25's left child (next best one)
15:33 <+mafintosh> you keep doing this until you hit a leaf (max log(n) times, we are always walking *down* the tree)
15:34 <+mafintosh> once you hit a leaf, that's your sig :)
15:34 <yoshuawuyts> ahhh
15:35 <+mafintosh> pretty smart i know haha
15:35 <+mafintosh> :D :D :D
15:35 <yoshuawuyts> mafintosh: this is pretty cool!
15:35 <yoshuawuyts> mafintosh: also completely not how I pictured it lol
15:36 <yoshuawuyts> mafintosh: does every root hold 4 leaf nodes?
15:36 <yoshuawuyts> mafintosh: also: what do we call nodes like "21" - parent nodes?
15:37 <yoshuawuyts> wanna make sure I got all the terminology right :p
15:37 <+mafintosh> yoshuawuyts: a root, just marks the root of a given tree. (ie a root is a node with no sibling atm)
15:37 <+mafintosh> if you a node *and* it's sibling, then you can hash them together to get their parent, ie it's not a root anymore :)
15:37 <+mafintosh> *have a node
15:39 <+mafintosh> yoshuawuyts: you should document all this terminoligy for us :)
15:39 <yoshuawuyts> mafintosh: wait wait wait, but in the image above, even if you add node "16", then "19" is still blue which means "parent"
15:40 <yoshuawuyts> damn, I think I'm still a bit lost trying to picture it
15:40 <yoshuawuyts> oh no okay, got it actually
15:41 <yoshuawuyts> the moment there's a different hash that combines both - we can get that hash
15:41 <+mafintosh> yea exactly
15:41 <+mafintosh> then the current tree grows
15:42 <yoshuawuyts> mafintosh: dang, yeah - so in my brain it was that "27" holds the hashes for "25" and "29"
15:42 <yoshuawuyts> but that's not necessarily the case

♥️