I came up with a workaround for some of the problems discussed above, I figure I should at least sketch it out here...

Assume a signature-skip-list where each message n contains the hashes of all messages k such that the k-th digit in the binary representation of n is a one.

The problem we looked at so far was to find for each message n a logarithmic number of messages older then n, such that the combined sets of any two such messages hold enough infomation to verify that the newer one (transitively) signs the older one. In this framing, we didn't manage to find a solution. But what if we allow including messages newer than n itself in this set? We can then include the smalles set of messages that shows that x signs n, where x is the power of two greater or equal then n.

This satisfies our validation criteria: Given two messages n and m (wlog n < m), let x be the power of two greater or equal then n. If m > x, then m contains the hash of x, and we can then verify n from x. If m < x, it also works out I think (proof by intuition... my gut feeling is that the skiplist of m and the reverse-skiplist between n and x always meet at some point... nobody bothers following this anyways, right?).

For this to make sense, requesting a single message n also involves requesting some newer messages, which may not even exist yet. To guarantee fully transitive replication, implementations need to keep non-selfishly requesting those newer messages even though they may have already received and verified n. Still, I think this is a fairly reasonable assumption to make.

CC @Tim Makarios (on Manyverse) in case you come back to the scuttleverse at some point =)