@Tim Makarios (on Manyverse)

I don't think it's possible to do this in less than O(n) space. Otherwise, for sufficiently large n, message number n will have a certificate that proves that it was created after each message with a smaller sequence number, but the certificate will have less than, say, 1 bit per previous message. I don't think that can be cryptographically secure.

Intuitively I want to agree, but since we are dealing with probabilistic guarantees in any case, it might still be possible to cheat the "1 bit per previous message" limit.

The reason I was considering that variant was as a way of avoiding single points of failure. In my earlier suggestion (and your variant, I think), message 2^k-1 is a single point of failure. If that message is lost, you'll never be able to verify that messages with higher sequence numbers were created after messages with lower ones. Actually, every odd sequence number is a minor single point of failure; for example, if message 9 is lost, you'll never be able to verify that message 10 was created after message 8, but you'll still be able to verify that both were created after message 7 (which you wouldn't be able to do with the current simple linked list).

This is funny, I was actively seeking out those points. Instead of viewing them as points of failure, I viewed them as desirable overlap between certificates. Half of the entries in the skiplist scheme are the left spine of the tree, and that is shared between all of them. That makes it very likely that exchanging partial certificates is enough. My hunch is that if this were to form the basis for partial feed subscription, the larger certificates with high overlap would be overall more efficient than a scheme that has shorter certificates and lower (relative) overlap.

But in any sub-O(n) out-of-order scheme, I'm pretty sure that it's possible that two of your peers will each have a different message from the same feed (but each has only that one message from that feed), and you'll get both messages, but neither peer will be able to help you verify their creation order, unless there happens to be a direct backlink from one message to the other.

And I guess that makes the whole thing unsuitable. The property you stated about verifyability of messages received from the same peer is nice, but just not enough.

I think ssb can either drop the creation-order-guarantee, or it won't get verifiable out-of-order messages.