So are we done now? Nope. Our c6 certificate assumed that m7 was available, but what if it didn't exist yet (or the certificate creator didn't know about it yet)? This is depicted in the following graphic:

Here we don't have a single merkle tree, but a merkle forest with three roots: h0123, h45 and h6. This feed as a length that is one less than a power of two, these feeds are the worst-case scenario as they result in the largest number of disjoint trees. The naive certificate attempt consisting of only these roots doesn't work, since the three hashes are completely independent. I could first create m6, and once someone requested it, I could then invent messages m0 to m5, compute h0123 and h45, and then use these hashes in the certificate. To prevent this, we add Hh45h6 (the hash of the concatenation of h45 and h6), and analogously Hh0123h45. Hh45h6 must be published (and signed) together with m6, Hh0123h45 must be published (and signed) together with m5. This gives us a valid certificate h0123, h45, Hh0123h45, h6, Hh45h6, h01, h0 for m6. (credit for this goes to the dat whitepaper's merkle tree and replication sections)

The following graphic depicts the graph where all of these additional hashes are present, marked in blue.

As a consequence, there are two possible certificates for all non-power-of-two'th messages: The one described above that bridges across different merkle trees, and a more compact one that can only be computed once the feed length has advanced to the next power of two. A simple solution is to always use the one that can immediately be computed. But these two don't conflict, so the actual implementation can use the more efficient one whenever possible. Servers just need to be aware that even if they know that the efficient one can be computed, their peer's view of the feed might be outdated, forcing the peer to send the inefficient certificate instead.

Before I move on to the actual implementations, a quick note on correctness. I won't do a full prove here, that would need a bunch of definitions first. But a basic proof sketch is based around three properties of certificates:

1. A certificate must somehow depend on all previously published messages. In the graph, that means that there must be a directed path from each message to one of the nodes in the certificate
2. A certificate must be self-consistent (unlike the naive attempt in the length-7 feed above). In the graph, that means that there must be a directed path from the certified message to each node in the certificate.
3. It must be possible to check that any two certificates do not contradict each other. In the graph, that means that after taking the union of the two certificates, each vertex from the certificate for the earlier message must be reachable from a vertex from the other certificate.

You can then go on and show that the scheme I presented fulfills these criteria. My intuition tells me that there's also a proof of optimality somewhere in there. But the more difficult part is actually showing that these criteria are exactly what we need to give ssb's security guarantees. Formal proofs in that domain are outside my current knowledge level though.

Implementation in SSB

This is a very direct translation of the above tree construction scheme into ssb. It omits some obvious optimizations, these are discussed later.

To the regular metadata of the message msg_s with sequence number s, append the following (in order, before signing)

• hash(msg_s) as field "hash0"
• hash(msg_(s - 1).hash0 | msg_s.hash0) (called "hash1") iff s == (l * 2^1) - 1 for some l
• hash(msg_(s - 2).hash1 | msg_s.hash1) (called "hash2") iff s == (l * 2^2) - 1 for some l
• ...
• hash(msg_(s - 2^(k - 1)).hash<k - 1> | msg_s.hash<k - 1>) (called "hash<k>") iff s == (l * 2^k) - 1 for some l
• If s is one less then a power of two, we are done. Else we need to add the additional hash that allows bridging between disparate merkle trees:
  • add hash(msg_(s - 2^(k - 1)).hash<k> | msg_s.hash<k - 1>) (called "bridge")

This may look intimidating, but it does nothing more than constructing the trees described above. Also a note on addressing: I used these names "hash42" to indicate the level of the tree, which is nice for humans. But for machines, there are relatively simple numbering schemes that provide bijections between natural numbers and those inner tree nodes (stealing from the dat whitepaper again). So addressing those is actually very efficient, both in terms of in-memory access time, and address size when sending stuff over the network.