@Tim Makarios @aljoscha it's most certainly possible to verify any two messages are in the same merkle tree using only O(log(n)) data. You don't need to put the branches of the tree in the message (which would expand each record to log(n) size, making the space for the entire feed O(n*log(n))) you just need to hash the top branches together, and put that hash in the record. And if you are missing a single record, knowing it's hash is enough to validate messages following that.

However, for partial replication (of say, specific message types) this doesn't tell you whether you have all the messages of that type. I have heard that there are also merkle tree designs that can do non-membership proofs, but I don't understand how they work yet. Could be worth looking into.

Since it's likely many of the important messages are encrypted, so if you go back and ask for particular encrypted messages it will basically reveal who is talking to who, but if you get every message, that doesn't happen.

That's just an example of why you need to look at the greater impact of protocol design decisions, and think through what sort of thing might be built on top of it in the application layer.

I think this sort of thing really makes sense for something like streaming live video or audio. Or for sensors or say, a weather report where having the latest thing is useful, but having the old things is not as valuable.