Cryptocurrency and blockchain are often mentioned together because they are closely related. Cryptocurrencies, such as Bitcoin, are distributed digital payment systems that use blockchain, a distributed ledger, underneath.
You might already know that blockchain is not only used to transfer digital assets. There are many other potential use cases like medical information sharing, voting/elections, digital art ownership (aka NFTs) and even gambling. But given that this is such a powerful technology, can it be overkill just for electronic payments? Can you build a cryptocurrency without blockchain? Yes, you can!

I’ve been doing theoretical research in distributed computing and, in particular, decentralized asset transfer systems for some time. In this post, I want to share why blockchain and consensus is not the only solution to the design of cryptocurrency protocol and what the alternatives are. First, we will recap some theory behind Bitcoin and other blockchain-based cryptocurrencies, then look into why exactly blockchain is not necessary to implement a decentralized payments system and finally overview some existing systems that allow to transfer money in a distributed system without using blockchain. We will mostly focus on the theory, but in quite a lightweight style. If there is an interest I would be happy to dive deeper in the future posts!

Bitcoin problem

Let us take a small step back and answer a fundamental question: what is a fundamental problem when one designs a protocol for a distributed payment system (cryptocurrency)?

To answer this question, let's refer to the Bitcoin white paper [1]. The author, Satoshi Nakamoto (whoever this is), claimed that financial institutions can't be trusted completely. Indeed, banks have too much power over the merchants and customers, can freeze their money and are a single point of failure: if something goes wrong with a bank, everyone (both customers and merchants) will be affected. What's more, as financial institutions serve as a mediator, this increases transaction costs. To solve this problem, Nakomoto proposed a digital asset system, Bitcoin, that would allow the movement of money between people peer-to-peer without any central authority like a bank. Instead, the payment problem is brought to a distributed setting, where each participant has theoretically equal rights.

The removal of a central authority that processes all transactions is not a feature that is unique to Bitcoin. All digital asset transfer systems aim to do the same thing one way or another.

Technical details might be different, but, as Nakomoto pointed out, no matter how one designs their cryptocurrency protocol, there is one fundamental problem that everyone will need to solve — double-spending.

Imagine if Alice has exactly 10 dollars. How do we ensure she cannot send these 10 dollars to Bob and Carol? Of course, when you have a bank, this is pretty simple since all transactions go through it: either transaction to Bob or to Carol will go first, and the other won't be permitted. But can we do it without a bank?

Blockchain: How Bitcoin (and others) solve double-spending

So, how do (most) cryptocurrencies solve this problem? Well, you most likely already know the answer — blockchain!

In the Bitcoin white paper, Nakomoto proposed that without a centralized financial institution, which verifies transactions, all system participants (known as miners) act like a bank. As a result, everybody should know about all transactions in the system and store their version of a "transactions gross book". For this, Bitcoin suggests ordering transactions globally using a variation of a commonly known abstraction in distributed systems called distributed ledger or blockchain.

A distributed ledger (blockchain) — is a distributed data structure that represents a chain of blocks of data that has two operations:

• Append(x) — write a block of data x to the end of the chain;
• Read(n) — read data from the n-th block in the chain.

One can notice that in blockchain, we build a sequence of blocks, which defines a total order on the set of blocks. From the theory of distributed computing, we know that building a total order in a distributed system is equivalent to the problem of consensus (where participants propose values and decide on exactly one of them). Thus, every blockchain uses consensus underneath.

However, Bitcoin couldn't take any already existing distributed ledger protocol. This is because Bitcoin also aims to solve the double-spending problem in a permissionless setting, where anyone can join the system as an active participant (known as miners). Systems that operate in such a setting should tolerate the notorious Sybil attacks, where an adversary can control an unbounded number of malicious (formally called Byzantine) participants. At the same time, traditional ledgers could only tolerate a small fraction of Byzantine nodes (less than one-third).

To fight this issue, Nakomoto proposed an infamous proof-of-work mechanism that artificially slows down miners by making them solve a cryptographic puzzle and make the number of adversaries irrelevant as long as they don't have a lot of computational power.

You might have already heard that the proof-of-work is known as a very energy-inefficient solution, and other mechanisms like proof-of-stake (Ethereum, Algorand), proof-of-space (SpaceMint), or proof-of-space-time (Chia) and others can obviate tremendous energy consumption of Bitcoin, while still preventing Sybil attacks.

While the choice of the mechanism (proof-of-work/stake/space/etc.) might vary from one digital asset system to another, as well as other technical details, their core remains the same. They resort to consensus protocols to agree on a total order of transactions that are usually split into discrete blocks and applied to some initial state (the genesis block) and form a blockchain. This approach is illustrated in the picture above.

Consensus is hard, Cryptocurrency is easy

Implementations of Byzantine-prone consensus algorithms are notoriously hard and complicated. Usually, they are communication expensive (i.e., require a lot of messages to be sent in the system) and rely on synchronous networks, randomization, non-trivial cryptography, failure detectors or trusted setup systems. Finally, they are relatively hard to understand. So, is the problem that engineers haven’t figured out a way to solve in a simple and robust manner? Not really — it is not just a practical issue. Consensus is theoretically a "hard" problem, but what does it mean?

Most of the computing problems we face daily (not all of them) are either in P, which can be solved in polynomial time or in NP — most likely cannot be solved polynomially. People in computer science sometimes refer to these classes as "easy" and "hard". In distributed computing, there is a similar concept, and roughly speaking, the world can be divided into two classes: whether you can solve a problem asynchronously, without any timing assumptions, or whether it can only be solved synchronously (i.e., you need timing assumptions). If you want to go into a bit more details, I think this answer on Quora is quite good to start from. Asynchronous problems are "easy", while the ones that might only be tackled synchronously are "hard". And consensus, according to a fundamental distributed computing result, the FLP theorem, is a hard problem.

FLP Theorem

In an asynchronous message-passing system, there is no deterministic consensus algorithm that is guaranteed to terminate, if at least one node may crash.

However, this is different for the double-spending problem. A relatively recent paper [2] showed that the consensus number of a cryptocurrency with a k-shared account is k. In simple words, if an account is permitted or assumed to be controlled by at most k different users (clients), then only k users need to reach a consensus to solve the double-spending problem. Given that it is commonly assumed that an account is controlled by 1 person only, the distributed payment system has a consensus number 1. And it just makes sense: if you want to order transactions on an account correctly, only the owner of this account needs to come to an agreement with itself!

This means that the fundamental double-spending problem can be solved asynchronously and thus is provably "easy".

Thus, to solve double-spending, we don’t need to solve the consensus problem! But it is important to say that the fact in the paper was initially proved only for permissioned systems: the systems where all active participants (replicas that store transaction data) are known, and we can assume that there are less than n / 3 Byzantine users. For example, these are distributed systems with static membership or trusted setup mechanisms. Anyway, we will return to the permissionless systems later on.

As for now, let's remember one thing:

In order to solve double-spending in a decentralised system, consensus, in general, is not necessary.

To calm down some of the readers, let me note that the above fact doesn’t mean that consensus (and thus blockchain) is useless in the DeFi world. It is still required in order to build general purpose smart-contracts, however for the sake of just a distributed payment system it is unnecessary.

Cryptocurrency implementations without blockchain

But since you can implement cryptocurrency without consensus, have such systems been proposed? Yes! Let us overview some of the proposed solutions for different settings. They are all theoretically proven to be correct, and, even more, most of them, show good performance in practice).

Some of the presented systems/papers are co-authored by the author of this post.

Permissioned consensus-free cryptocurrency

The first consensusless system we will cover is Astro [3]. It is a permissioned distributed asset transfer system that, instead of consensus, uses other primitives. As a result, Astro not only outperforms Bitcoin but can also reach the same (and even higher) throughput than the VISA payment system.

The system consists of clients, nodes that submit transactions, and replicas that confirm and store transaction history. The protocol proceeds as follows:

1. The client chooses a replica (representative) and sends a transaction tx to it;
2. The representative broadcasts transaction tx to all replicas;
3. Correct replicas approve transaction tx locally, and (optionally) a representative sends an approval to the sender and recipient clients.

Here, the main magic happens in the second stage, when the representative broadcasts the transaction tx to others. It does so using a primitive called Byzantine Reliable Broadcast (BRB). This primitive is weaker than consensus and can be implemented fully asynchronously. Given that every transaction has a sequence number (each client uses its own sequence), this abstraction ensures that if a replica broadcasts a transaction tx with a sequence number n, all correct replicas deliver the same transaction tx for a sequence number n. This way, the protocol ensures consistency, i.e., no two correct replicas deliver two different transactions for the same sequence number. However, note that if two conflicting transactions are broadcasted, none of them might be delivered. Thus, double-spending in the system is impossible and brings many risks: you can lose money, or your account might be frozen.

The BRB protocol relies on quorums — sets of replicas such that (i) there exists at least one quorum where all replicas are correct, (ii) any two quorums intersect by at least one correct replica. Informally, if every step in the distributed protocol requires confirmation by a quorum of replicas, we guarantee that we can come to decisions that are correct and don’t contradict each other (the latter follows from the second property).

The system based on quorums would work only if we can assume that the number of Byzantine replicas is less than n / 3. Astro is a permissioned system, and we can control replicas that enter the system, such an assumption is fair.

The above might have alerted you: since every step should be confirmed by a quorum, how difficult is it to increase the number of replicas in the algorithm? Will it perform worse? This is a valid concern. However, the authors propose a way to handle it — sharding. One can break the system into smaller subsystems, called shards, and then run an instance of the protocol in each shard separately. This way, if Alice sends money to Bob and their representative replicas are in the same shard — nothing in the protocol changes. However, if Alice’s representative is in shard A and Bob’s in shard B, then the Astro protocol is executed in shard A. Then Alice’s representative replica forms a certificate given a quorum of approvals and sends it to shard B, where information is reshared, and Bob learns about the money he received.

There is another interesting approach based on probabilistic broadcast and instead of quorums uses samples — replicas that represent the system with a high enough probability. This can benefit the system and bring communication costs to the logarithmic size of the network. But let us leave it for some other time.

Many other consensus-free cryptocurrencies are similar to Astro, for example, AT2 (EPFL), FastPay (Facebook Novi) and Zef (Zefchain Labs) and in fact show very good practical results.

Permissionless and consensus-free proof-of-stake cryptocurrency

The system we described before is interesting, but it is permissioned and supposes a static system membership or a trusted setup mechanism. This is usually enough to assume that Sybil attacks are impossible. However, what if we want to implement a payment system where anyone can join the system without any verification? Can we even solve double-spending without consensus in a permissionless system? Yes, we can.

In a recent paper [4] that I co-authored, Pastro, a permissionless and asynchronous asset-transfer system, was proposed. It is based on so-called weighted quorums. More precisely, the system relies on the certificates signed by participants holding a sufficient amount of assets, or stake, instead of traditional quorums and accounting for the number of required approvals. On top of this, we build an abstraction, called Transaction Validation. It is similar to BRB and makes sure no two conflicting transactions are ever confirmed.

But how can we define stake in an asynchronous system? Since the system doesn't use a consensus mechanism, we can't really all agree on how much money every participant/account actually holds. Indeed, we don't have a total order, and the distribution of assets depends on it.

So, to introduce the notion of the stake, we use a concept of a configuration. Traditionally, in distributed computing, configurations define a set of replicas that maintain the system at a given moment in time. Instead, in Pastro, a configuration is used to determine the distribution of the system's stake among participants. Formally, a configuration is just a set of transactions that have occurred in the system since the beginning. Let us note two important things here:

1. Given such a set of transactions, one can easily determine active system participants and the distribution of the stake among them;
2. If all such sets are related by inclusion (i.e., one is contained in another), then they can represent dynamically changing stake distribution in the system throughout time.

But how does it help? The idea is that participants do not agree on the "current configuration". However, all configurations they personally decide on can be ordered by containment.

Thus, we always have "the largest" configuration with strictly more transactions (by inclusion) than in any other, denoted as active configuration and according to which stake distribution should be calculated. If you have studied mathematics and algebra for quite some time, you might have noticed that it is very close to an algebraic abstraction of the lattice (lattice order).

The system employs a variation of Byzantine Lattice Agreement protocol that, parameterised with a (semi-)lattice (in our case, a set of transactions), produces elements of the lattice that are comparable (set of transactions related by containment — precisely what we need). This abstraction collects all submitted transactions in a set, or configuration, then updates the current stake distribution given produced configurations. More importantly, lattice agreement is a powerful object that can be implemented fully asynchronously, unlike consensus.

Using these ideas, the Pastro protocol can solve the problem of double-spending in the presence of Sybil attacks and a so-called dynamic adversary that can choose which participants to compromise during the execution, taking their current stake into account. Though a variation of a common assumption is in place: the adversary can corrupt participants that, in the active configuration, own less than one-third of the total system stake. This makes Pastro the first ever fully permissionless and consensus-free cryptocurrency.

We even propose ways to incorporate stake delegation, fees and inflation mechanisms in Pastro. First, though, it is important to mention that some practical engineering challenges must be solved first (storage & communication optimisation) before fully implementing the system.

Almost consensus-free cryptocurrency with shared accounts

Both permissioned and permissionless asynchronous asset transfer systems described in the two previous sections can be generalized. At a high level, such systems maintain an unordered set of committed (or accepted) transactions. In order to be added to the set, a new transaction must pass a special Conflict Detector object (in Astro, it is a Byzantine Reliable Broadcast). The object maintains the invariant of non-negative balances by imposing a notion of pairwise conflicts on the transactions and preventing multiple conflicting transactions from being accepted. Intuitively, two transactions are considered conflicting when moving the same assets. I illustrated this below.

However, all existing consensus-free implementations share a certain limitation: they assume that each account is controlled by a single user that never issues multiple transactions in parallel. This assumption precludes sharing an account by multiple users, e.g., by family members or safely accessing it from various devices. If an honest user does accidentally issue several concurrent transactions, the existing implementations may block the account forever without the possibility of recovering.

Remember that, as we learnt, consensus is required for cryptocurrencies where accounts can be shared, so it is impossible to implement such a system in an asynchronous setting without consensus.

A permissioned system called CryptoConcurrency [5] that we recently proposed solves this issue. This is a hybrid protocol combines the benefits of both consensus and consensus-free approaches. It allows accounts to be shared by multiple users and avoids using consensus in most cases.

Informally, if concurrently issued transactions on the same account can all be accepted without exhausting the account's balance, they are processed simultaneously and purely asynchronously. In this case, they go through a so-called Recoverable Overspending Detector, an advanced version of the Conflict Detector, which tries to detect balance overdraft and not just pairwise conflict. At the same time, CryptoConcurrency dynamically detects the cases when consensus should be used, i.e., when the total value of concurrently issued transactions exceeds the account's balance. In these cases, the protocol accesses per-account consensus instances to choose a maximal possible subset of transactions that don't conflict and accept them while rejecting the others. The consensus output is then used to restore the Recoverable Overspending Detector (this is why it is called Recoverable), and the system proceeds as before.

From the implementation perspective, Recoverable Overspending Detector is a sort of combination of Byzantine Lattice Agreement (that we already touched on in the previous section) and the famous Paxos consensus algorithm.

The algorithm we proposed in CryptoConcurrency is, in some sense, optimal: the account needs to solve consensus only when there are not enough funds to cover all transactions being processed.

In my opinion, a cool feature here is that each account can plug in its own consensus implementation, as when overspending is detected on the account, then only owners of this account should come to an agreement on which transactions to revert and which to accept. So, theoretically, you can either use something as AWS or a smart contract deployed to your favourite blockchain.

I believe that an interesting challenge would be combining the ideas proposed by CryptoConcurrency and Pastro: it would be an interesting theoretical and engineering problem to build a permissionless distributed payment system that would permit shared account usage without using global consensus but only to local instances when only necessary.

Final remarks

In this post we looked into why blockchain is not the only possible way to build a cryptocurrency and overviewed some of the proposed systems for different settings. I hope you enjoyed the material and learnt something new! Also, don't hesitate to leave your questions in the comments section. If there is interest, I might post more about new protocols and concepts that researchers come up with in distributed computing.

References

[1] Bitcoin: A Peer-to-Peer Electronic Cash System. S. Nakomoto — pdf version

[2] The Consensus Number of a Cryptocurrency. R. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovic, D-A. Seredinschi — arXiv link

[3] Online Payments by Merely Broadcasting Messages. D. Collins, R. Guerraoui, J. Komatovic, M. Monti, A. Xygkis, M. Pavlovic, P. Kuznetsov, Y-A. Pignolet, D-A. Seredinschi, A. Tonkikh — arXiv link

[4] Permissionless and Asynchronous Asset Transfer. P. Kuznetsov, Y-A. Pignolet, P. Ponomarev, A. Tonkikh — arXiv link

[5] CryptoConcurrency: (Almost) Consensusless Asset Transfer with Shared Accounts. P. Kuznetsov, Y-A. Pignolet, P. Ponomarev, A. Tonkikh — arXiv link

Resources

If you want to dive deeper into the topic, I think these are good resources to start from:

• Bitcoin (ft. Rachid Guerraoui & Jad Hamza) — YouTube video
• Circumventing the Impossibility of Consensus (ft. Rachid Guerraoui) — YouTube video
• AT2: Consensusless Decentralized Cryptocurrency — YouTube video playlist