Mediating Mutual Exclusivity

The Big Picture: Mutually-exclusive events are events which are each valid independently, but cannot co-exist. I can vote for one candidate, or I can vote for another, but I can’t vote for both. I can spend this dollar at Target or at Walmart, but not at both. If the voting/spending/whatever else occurred on a blockchain (whose protocol was able to determine mutual exclusivity for the type of event in question), the acceptance of one of the events (voting for a certain candidate, spending the dollar at a certain store) would exclude all other possible conflicting events from occurring, and would guarantee that one of them is known to have happened globally, and the others are, by exclusion, impossible.

One of the primary use cases for blockchains is to determine which of several modifications, each of which is individually valid but only one of which can occur, actually get applied to the state machine a blockchain enables the synchronization of. The arbitration of mutually-exclusive events enables the creation of a system in which authenticity of an asset can be determined. Examples include preventing double-spending or unauthorized mintage of currency (make sure someone doesn’t spend a token twice, which would effectively result in the creation of an additional token in circulation), ensuring every party receives the appropriate voting power, and tracking the ownership history of unique physical goods (such as provenance of artwork, or the ownership of real estate).

The functionality of arbitration in a blockchain is performed by the block miners (whether they be proof of work, proof of stake, or something more exotic). By selecting the transactions (which are atomic operations to the underlying state machine) which are most valuable to them (generally the ‘value’ of a transaction is its transaction fee relative to its size), the miners (perhaps without even knowing alternative mutually exclusive transactions occur) establish and finalize the single truth of a particular set of previously-potential truths.

For example, two transactions A and B are created. They are mutually exclusive: perhaps they spend the same tokens, transfer the same property, or otherwise conflict in some fashion. Both transactions can be broadcast to the blockchain network (although some nodes may choose not to relay a transaction which conflicts with one they have already seen). Until one or the other is included in a block in the blockchain, nobody on the network knows which transaction will eventually be deemed valid. Whichever transaction pays a higher fee is more likely, but not guaranteed, to be the one eventually accepted. Furthermore, no node on the network knows for certain that they have seen all possible conflicting transactions (in the trivial case, a miner could create a transaction that’s mutually exclusive of another which has been previously broadcasted, and keep the transaction private unless they are able to mine it into a block). As such, accepting any transaction before it has been included in a block (and, for more security, until that block has been buried by a few more) is risky, because an alternate version of history could be the one which the blockchain eventually settles on and declares as truth.