perhaps fn verified_by() need more comments

[ZhouHansen]

https://github.com/datrs/tree-index/blob/82e189ef4eb6b4dba4f9003e946f3601eeecb149/src/lib.rs#L236

It's hard to understand the function of fn verified_by() by reading the test code and the current comment.

[yoshuawuyts]

Ah yeah, good question! We should write a better version for this for the book, but here's some notes on how verification works with flat-tree (and in turn tree-index).

A PR for a better description based on ^ would be very welcome! -- also happy to answer any questions you might have around this, as I think I have a good grasp on it nowadays :D

[ZhouHansen]

emmm.. I don't know what verification and signature is.

[yoshuawuyts]

verification is a hash of hashes -- kind of like with a blockchain, it signs the whole history. A signature is an Ed25519 cryptographic signature. It takes data (e.g. the hash), and signs it to ensure this hash was created by the person with the private key.

Ummm, I don't know if my explanation makes much sense here! -- I always struggle explaining this stuff back -- and that's not a good sign. I need to do better here; sorry if things are not clear!

[ZhouHansen]

Thanks for telling me what things I should know first!

I've learned digital signatures and blockchain a little. Within the notes, you said verifying a sig is expensive, but verifying the signature (proof-of-work) of new block in blockchain is easy, produce is difficult. So I guess the verification here is kind of like the bitcoin transaction verification, the digital signatures. I'm not sure, because you said the newest node is the best signature, I don't understand why. This makes I feel it is like with a blockchain again, which each block's signature is generated dependent on previous one's signature.

In a word, why we need signature and verification here, Is there some examples?

And what's the difference between the return value node and top from fn verified_by()?

[yoshuawuyts]

Produced with print-flat-tree.

Before we go in, it's important to know that we have 2 trees with the exact same layout. In .dat/ they're stored as .dat/data and ./dat/signatures.

In the viz above, you can see numbers in yellow, white, blue and green.

• yellow: leaf node. (src) Holds the hash of a piece of data in the .dat/data tree. In the .dat/signatures tree this holds a signed hash of all previous nodes in the tree (see green for how this works).
• white: parent node (src). Combines the hashes of the nodes below it. This is what makes this a "merkle tree". E.g. this becomes a hash of hashes.
• blue: root node. A parent node that has a hash of all data under it -- e.g. the tree under the node is complete. This is otherwise the same as a "parent node".
• green: head (src). The last node added to the tree. It holds a combined hash of all previous root nodes. So we use the data stored in this node to verify all previous parts of the tree.

---

Hope this somewhat makes sense? So when you call .verified_by() you try and find the green node that corresponds to holding the signatures for a blue node.

All of this hasn't been reviewed btw, it's just a quick draft of my best-effort understanding of how things work. I want to write some more about it for the guide, and let some people review it to make sure it's 100% accurate. Hope this is somewhat helpful though!

[ZhouHansen]

Thanks! Very helpful.

[ZhouHansen]

it's important to know that we have 2 trees with the exact same layout. In .dat/ they're stored as .dat/data and ./dat/signatures.

But look at hypercore/feed's fn append(), It only writes the merkle-tree data to the tree storage, signatures storage and data storage are not tree:

self.storage.write_data(self.byte_length + offset, &data)?;
// ...
self.storage.put_signature(index, signature)?;

for node in self.merkle.nodes() {
  self.storage.put_node(node)?;
}

The last node added to the tree. It holds a combined hash of all previous root nodes.

Yeah! I see it:

let hash = Hash::from_roots(self.merkle.roots());
let index = self.length;
let signature = sign(&self.public_key, key, hash.as_bytes());
self.storage.put_signature(index, signature)?;

And fn proof_with_digest() and fn digest() really need more explanations, I can't figure them out.