For non-basel-attendants: this is about a hypothetical world in which instead of ordered logs peers would merely insert items into ever-growing sets. These sets would be replicated via dark magic the mechanism the first question pertains to and which I will explain on here soon, probably in video form.

@adz

What sort of hash function would one use to guarantee ordered items in the binary search tree?

The hash function has nothing to do with the ordering, the trees I drew were simplified. Just sort stuff by its natural order in the tree, and compute the corresponding fingerprints (hashes in the leaves, sums (or XORs) of hashes in the inner nodes). This btw is again simplified, usually BSTs also store data in inner nodes - you'd then store value, hash of the value, and XOR of left-subtree-hash, own-value-hash and right-subtree-hash.

If one still needs partial-order for some messages (like username changes) how does one guarantee that there is no fork again?

You probably meant total order rather than partial orders. The best approach is to not require a total order for the application layer in the first place. Otherwise, mutual exclusion for writes becomes necessary - enforcing that would be an application concern. Crucially, if application-layer total order is violated, the raw data can still be replicated. Different apps using the same set would be unaffected.