Is there any way to ensure that a network merge, after a parition, never causes disagreements?

in flag

Background: A cryptocurrency, such as Bitcoin, have a global order of all transactions that is guaranteed to be agreed by all participating nodes. With Bitcoin, this is ensured by making the longest chain win, and that creating a long chain requires performing a lot of computations (so it is not trivial to arbitrarily create a longer chain).

A problem comes when there is a long-lasting network partition. Each partition will eventually use its own local order, which is different than every other partition. Later, when the networks merge, a single global order will be enforced based on the network that had the longest chain.

This new global order can be different-enough for the other smaller networks that effectively some of their transactions will disappear if they're invalid as per the global order. E.g. coins mined in a small network partition that required a low difficulty (e.g. finding hashes a small number of zeros) will be discarded as invalid according to the perspective of the larger network which requires solving more difficult problems (e.g. finding hashes with more zeros).

This is a problem, as some payments become zero. Imagine being a business owner that sold and delivered goods in a small network partition in return to some BTC, only to realise that the payment has disappeared from the global transactions order once the partitions got merged back into the main network. Effectively, we will have the equivalent effect of having goods stolen (or given for free).

Question: How to design a cryptocurrency that guarantees that such network merges will never cause any disagreement in payments? Are there any fundamental principles that, if satisfied, we ensure consist money balances even after long-term network partitioning?

fgrieu avatar
ng flag
I'm leaning towards thinking this does not pertain to cryptography, or/and is insufficiently defined. But a drawback of being a mod is that I can't cast a normal single vote towards closing the question.
caveman avatar
in flag
@fgrieu - You're likely right. It's a database transactions synchronisation problem. But I got confused as to where to post it, as I'm not sure how much of the limitations in this specific use case (cryptocurrency) is due to how basic cryptographic functions work. I'd appreciate suggestions on where to move this.
kelalaka avatar
in flag
@fgrieu Maybe CS
ug flag

This is a long studied question in distributed algorithms design. There are three network models that are traditionally studied: synchronous networks, partially synchronous networks, and asynchronous networks. You can probably find lecture notes online that describe them better than I can right now. Anyhow, Consensus/State Machine Replication protocols built in the partially-synchronous network model achieve exactly what you describe. Typically a bitcoin-like nakamoto consensus protocol breaks because we need an identity mechanism that persists through a network partition: the problem with nakamoto being that, during a partition, we no longer have the (informal) guarantee that all honest miners work on the same longest chain, and thus competing adversarial chains can grow faster. The only solutions that I've seen thus far are for permissioned settings with an honest (super)majority assumption (which can then be mauled into various solutions for PoS and a sort-of-permissionless setting).

Feasibility of consensus has different requirements in each of the three network models; moreover the MPC literature (which generalizes byzantine agreement) also cares greatly about these different network settings, so I guess it could be considered a cryptographic question (but moreso distributed algorithms).

caveman avatar
in flag
Thanks a lot. To save time, do you know of any cryptocurrency that already offers a solution to this partitioning problem? Meanwhile I'll search with the keyboards that you offered; highly appreciated!
ug flag
Noteswise I find that this (rather academic) blog is usually pretty accessible (e.g., and I also believe that most proof-of-stake designs are partially synchronous, but don't quote me on that.
ug flag
e.g. the ethereum consensus protocol post-merge should be partially synchronous (conditioned on some liveness bugs being fixed)
baro77 avatar
gd flag
@Vervious: Very interesting contact point the one via MPC! Could you elaborate a bit more? caveman Regarding blockchains without reorgs (but with dual, unavoidable stale problem): the ones with BFT-type state machine replication, check for these keywords: Tendermint, Cosmos, Tezos Really great resource to be serious about all of this:

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.