0
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Oct 12, 2022 at 16:19
  • $\begingroup$ @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. $\endgroup$
    – caveman
    Oct 12, 2022 at 16:24
  • $\begingroup$ @fgrieu Maybe CS $\endgroup$
    – kelalaka
    Oct 12, 2022 at 20:04

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – caveman
    Oct 12, 2022 at 18:29
  • 1
    $\begingroup$ Noteswise I find that this (rather academic) blog is usually pretty accessible (e.g. decentralizedthoughts.github.io/2019-06-01-2019-5-31-models), and I also believe that most proof-of-stake designs are partially synchronous, but don't quote me on that. $\endgroup$
    – Vervious
    Oct 12, 2022 at 19:04
  • 1
    $\begingroup$ e.g. the ethereum consensus protocol post-merge should be partially synchronous (conditioned on some liveness bugs being fixed) $\endgroup$
    – Vervious
    Oct 12, 2022 at 19:11
  • 1
    $\begingroup$ @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: youtube.com/… $\endgroup$
    – baro77
    Oct 13, 2022 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.