@Tim Makarios (on Manyverse)

For example, if B is the finite set of powers of 2 whose sum is n (that is, basically, the binary expansion of n), then for each element b of B, include in message n a backlink to the message whose sequence number is 1 less than the sum of all members of B that are greater than or equal to b.

Wow, this is beautiful.
Looks like it is indeed amortized O(1) overhead in signed data, and O(log(n)) in certificate space and validation time.

I've pondered constructing a deterministic skip list over the feed, but I didn't make the jump to use backlinks only. Your approach is skip-list-ish, but not exactly a skip-list. So my take on this theme:

For all k such that 2^k <= n: if n+1 is divisible by 2^k, include the hash of n - 2^k in the message.