Ok, I think I found the way to make the blue nodes less ugly: Instead of publishing and signing these extra hashes, each message (except for those one less than a power of two) includes the previous "mountaintop" (diamond node, the "left" input to the blue node of that message) in its (signed) metadata. But then, the certificates would need to validate the right spine of each subtree, which would be more data than the scheme with the extra hashes. Still logarithmic though. And who knows, maybe the other one can be somehow circumvented... I really need to sit down and do a correctness proof (or disproof...).

A few general things that are nice to know:

• the whole scheme (placement of additioal hashes etc.) works by describing each number as a sum of different powers of two - i.e. its binary representation
• message k needs to store t certificate hashes, where t is the number of trailing ones in the binary representation of k
• to compute the sequence number of the mountaintop previous to message k (where k is not itself a mountaintop), set all non-leading ones in the decimal representation of k to zero and subtract one
• the "height" of that mountaintop is the number of of places in the decimal representation of k minus the number of leading ones