Through this thread I have @mentioned everyone whose replies I can see. If I didn't mention you, then your ssb messages don't reach me.

@nanomonkey

What if each message type had their own log-chain and sequence number. So that I can say, I don't care about your chess and gathering messages, but I'd love to have and replicate your about and post messages. This seems ideal to me. You could start a client out replicating about messages, and then add on other feeds as interest requires.

Ack, that's something to consider. It is fairly orthogonal to the merkle-tree discussion though, so I won't go into this approach right now if that's ok for you. I'll definitely pick this up when the time for the metadata redesign comes. If you (or perhaps अभिनाश) want to flesh this out further, I'd appreciate if you could fork the thread to keep things somewhat structured.

@keks

One note though: please try to make your posts shorter. Specs can be walls of text (to avoid ambiguity), but starting a discussion like that doesn't scale.

Duly noted. I will try to clearly separate these background-knowledge-transfer-posts from protocol-discussion-posts. But the background-knowledge-transfer-posts definitely won't go away, I want to keep this reasonably accessible to the wider, technially-interested scuttleverse (so no worries @jeswin).

First question: In the graphs, what's the difference between the diamond, hexagon and rectangle nodes, and why does the path to m0 consist of diamonds and the others are rectangles? I suppose hex nodes are basically incomplete subtrees?

• diamond: Root of a complete binary merkle tree that contains the first 2^k messages of the feed for some k. The second half of a path to m0 always runs along these (with the first half going downwards from some m_i until a diamond node is reached).
• hexagon: roots of complete binary merkle trees that do not span messages from the beginning of the feed and are not inner nodes of one of the diamond trees
  • once the feed grows enough, a new diamond node gets created and the hexagons covered by it become regular rectangles in this visualization
    • this is only visual, the actual data structure does not need to tag node types at all
• non-blue rectangle: a node that is not a root of one o the relevant (i.e. diamond- or hexagon-rooted) complete binary merkle tree

Second question: I assume some of these hashes are signed by the feed author. I guess it's all but the blue ones? Otherwise I don't see a benefit over the current system, because if I ask you for an individual message, you could just make up some hashes.

All of them need to be signed, even the blue ones. Else a malicious peer could substitute a different blue hash, resulting in conflicting certificates for an otherwise valid feed. Only the feed owner is allowed/able to publish data that results in conflicting certificates (just as currently only he feed owner is allowed/able to fork the feed).

I think each hash needs a separate signature (I got this wrong in the "implementation" section), because otherwise certificate size would blow up to log(n) * log(n) (maybe?) *waves hands and hopes nobody cares about a precise complexity analysis*.

Bonus question: How does all of this relate to Merkle Mountain Ranges?

Another name for the same thing. This whole process would have been easier had I alredy known what to search for. But at least I had to think through everything myself. For example neither dat nor the mountain-range stuff I found mention the problem that certificates need the full path back to m0 so that all conflicts can be detected immediately. Maybe someone more knowledgeable about #dat could check whether hypercore does indeed not give that guarantee, and whether that conflicts with what dat wants to guarantee.