@Dominic

Still not sure I get the hashes signed by 31. It signs 29, 26 (which covers 25 and 27) and 8 (which covers 1 - 15), so 17 - 23 are left uncovered (which is why I thought you missed 20, as that would cover exactly the missing leaves). But more importantly:

your peer (who we are assuming has the entire feed)

This is the critical part that everything boils down to. Under that assumption, everything works. But is this a reasonable assumption? It means that only certain peers can successfully provide partial replicaton, namely those who have previously requested more than just a logarithmic amount of data. This would result in partial replication being second-class.

You could only perform fully general partial replication with a peer who has the complete feed. This violates the principle that it doesn't matter whom you get your data from, with whom you replicate. In particular, full feed replication is transitive (D can get data from C who gets data from B who got it from A). Current ooo also provides transitivity, by dropping security guarantees. D could get a single ooo message from C, who got it via ooo from B, who got it via ooo from A. D might never get to see the remainder of the message's feed. But merkle-based partial replication would not be transitive. The data could travel only one "hop" from someone who has the full feed. So "D gets a subset from C, who got a (not necessarily strict) superset of that set from B, who got got a superset of that from A" does not work (if we want to be able to verify all messages), the best you can do (in full generality) is "D gets a subset from C, who got the full feed from B, who got the full feed from A".

I consider this transitivity of passing data around to be crucial, and we failed to come up with a logarithmic scheme that maintains both transitivity and verifiability.