@aljoscha that is incorrect. To prove that the earlier message already existed, you just have to show that the later message signs the hash of that message, or the hash of something containing the hash, or the hash of something containing the hash of something... etc recursively.

So if I can take two messages, one with a low sequence number and one with a high sequence number, and I ask you if you can prove that one signs the other - if you can provide any set of hashes, and values they may be hashed with, such a hash in the value of the later message is produced - that is cryptographic proof that the earlier message really was earlier.

If you look at the picture I posted - the boxes are the messages/leaves (note - leaves are assigned odd numbers, and hash trees assigned even numbers). The numbers written to the right of the box are the hashes that leaf signs - so leaf 25 signs 20 and 8.

Lets say we want to prove that message 25 signs message 5. message 25 signs hash(tree[20]+tree[8]) (+ is concat) and message 5 is inside tree[8]. so we just have to show that tree[8] contains hash(message[5]) we can do that if we are provided with tree[7] and tree[2].

tree[8] == hash(
  tree[2] +
  hash(
    hash(msg[5]) + //aka, tree[5]
    tree[7])
  )
)

and we know that message 25 signs hash(tree[8]|tree[20]) so there you go, proof that messages 5 existed before message 25.