Aaand I think none of this actually works.

Past Aljoscha wrote:

Assume we received m6 and the associated certificate c6 described above (h7, h45, h0123, and h01234567), and now we ask for m1. The certificate c1 we get consists of h0 and h01. The server we are requesting from might not even know about any messages that were published after m1. But now we can't check whether c1 contradicts c6. c6 contains h0123, but does not tell us how h01 must relate to it. Fortunately, there's an easy fix: Each certificate must contain all the diamon-shaped nodes (h0, h01, h0123, and so on) that existed up to that point in time.

The same problem also applies to verifying message 8 and 15. And 16 and 23, and 24 and 31. And so on. So we'd need to include the spines of all merkle-subtrees with height four. But it's worse than that: For a feed of length at least 32, the same problem arises for verifying the creation order of messages 16 and 31. So we also need to include the spines of all merkle-subtrees with height five. And so on. As a result, we'd need to include all layers of the tree except the three lowest ones. And that is in O(n).

So either we

• find the error in my reasoning
• figure out how to actually get message-specific certificates with size in O(log(n))
• figure out how to work with an approach that produces logarithmic certificates specific to each pair of messages
• give up

=(