The second article in this series built Nexa’s validation engine out of six components, a tape, and a head, and watched it settle a payment from Alice to Bob with no software running at all. Because the tape only ever moved in the forward direction, the engine got to tick the first of the four boxes a better Bitcoin has to check: it was pipelineable.
This article ticks the rest. As Nexa Chief Scientist, Dr Peter Rizun, showed in Sydney, we can fix Satoshi’s Bitcoin and make it check all of those boxes with only three simple changes, and along the way the engine picks up two more properties, extensibility and compressibility, almost for free.
Two Pipelines
The next property to look into is parallelizability. In this design, a second validation pipeline is added in parallel to the first. There is a switch which routes transactions to whichever pipeline is not busy.
The first problem we encounter is that both heads, head one and head two, must access the same UTXO set. If pipeline one spends a coin, the coin must be spent from the perspective of pipeline two as well. But what if both pipelines attempt to spend the same coin on the same clock cycle? This is a race condition that we must prevent.
It is really easy to prevent this in hardware, though. The clock signal to pipeline two is inverted, so that it is physically impossible for the two heads to access the same coin at the same time. Either pipeline one grabs a coin on the clock’s rising edge, or pipeline two grabs a coin on the clock’s falling edge.
A Tree for Sets
The other problem we encounter is that the transactions might come out in a different order than they went in. For example, TX2 might come out and enter our block candidate before TX1. If our node solves the block, its peer might reassemble this block in a different order, calculate a different root hash and thus reject the block as invalid. Of course this can be fixed by sorting the block, but sorting is not pipelineable as the tape must move forwards and backwards. So we don’t want to sort because sorting doesn’t scale. If we interpret the whitepaper literally, Bitcoin is either parallelizable or pipelineable but it cannot be both.
Satoshi probably did not literally mean a Merkle tree; he meant a binary tree that would work for SPV proofs. The problem is that a Merkle tree is for lists. What Satoshi really wanted was a tree for sets. A tree with this property is a compact bitwise prefix tree. It still works for SPV proofs but it also produces the same root hash regardless of the order of the transactions in the block. As long as the two sets of transactions are equal, the root hashes will also be equal.
This is the first of the three changes: calculate the root hash for a block using a compact bitwise prefix tree rather than a Merkle tree, an idea that builds on Amaury Séchet’s idea to hash the block as a set rather than as a list. If we use the prefix tree, we can eliminate the need for sorting and recover the pipelineable property. With this one change our cryptocurrency becomes scalable.
So why is pipelineability and parallelizability such a big deal? With pipelineability we can guarantee that our throughput in transactions per second can be as fast as the reciprocal of the slowest step in the pipeline, which will typically be signature validation. The other shorter latencies don’t matter at all. With parallelizability our throughput can be multiplied by the number of parallel pipelines. Thus we have a system that scales arbitrarily just by increasing the pipeline depth and the number of parallel validation engines.
“Basically we can get to any scale we want just by throwing more hardware at the problem.” – Dr Peter Rizun, Australian Crypto Convention, Sydney, 2024
The Accidental Turing Machine
That one change strangely also gave us a Turing machine. To dig in deeper and see how, consider the case where Alice pays Bob and then Bob immediately pays that same coin to Carol. Remember we can’t control the order, so the payment from Bob to Carol might get checked by head one before the payment from Alice to Bob is registered. So when head one looks up Bob’s coin from the UTXO set it’s not going to find it, but nor will it find proof that the coin was already spent. So this transaction could not be marked valid, but it cannot be marked invalid either. It’s undecided.
To deal with undecided transactions we have to add a third pipeline that feeds those transactions back into the input. When this transaction reenters pipeline one, Bob’s coin is now sitting in the UTXO set because head one had to put it there, and the transaction can be validated normally and everything works out.
So it is the fact that a transaction can remain undecided that makes the feedback path necessary, and it is the feedback path that allows the machine to emulate a Turing machine, and this is really easy to see. So from the perspective of the head the tape is doing loops in front of it, but from the perspective of the tape the head is walking to the end and then starting over at the beginning. But remember the head has control over the flow control lines, so it can stop the tape at any square it wants. So what it really looks like is this: the head can move both right and left on the tape, and we already showed how the head could insert new squares into the tape, so the length of the tape is effectively unbounded. And as many of you probably know, this is all we need to show that our validation engine can emulate a Turing machine.
There is far more here than one talk can hold, but the headline is that with this architecture we can add things like quantum resistant signature schemes purely in script without even requiring a hard fork or a soft fork. So now we get to tick this box: our coin is now extensible.
Proofs Instead of Databases
The next step is to make it compressible. Currently full validating nodes use their UTXO set to determine whether a coin exists and is unspent. That’s it. But they could get that unspent status from a compact proof if such a proof existed.
We could easily make this happen, and it is the second of the three changes. The way it would work is that miners would store the UTXO set in a compact bitwise prefix tree and include the tree’s root hash in the block header, right beside where they’re including the root hash for the block. This builds on ideas from the ultimate blockchain compression thread on BitcoinTalk in 2012. Full nodes can now check that a coin is unspent with only a branch proof to the block header. There is no longer a need for full validating nodes to maintain a UTXO database.
Calculating the UTXO root hash is not hard for the miners. It is pipelineable, parallelizable and has O(log s) complexity per insertion/deletion, and so it meets our definition for scalable. So we get to tick this box, and our coin is now compressible. The third and last change, using a hash function that forces a miner to exercise the entire transaction validation pipeline, is the incentive-compatible box, and it was the whole subject of the first article in this series.
Coins, Not Accounts
All of that parallelism was only available because of one design decision, the same one people are really asking about when they ask what the difference is between Nexa and Ethereum. Both have flexible scripting systems, but the underlying architecture is very different.
Nexa uses the same UTXO model as Bitcoin and there are no accounts. There are only coins, and coins can either be spent in full or not at all. A typical transaction has the inputs being consumed, the signatures which authorize the spending of those inputs, and the new outputs being created. If the transaction succeeds, these coins are removed from the state and the new coins are added. So either the whole transaction goes through or none of it does.
So this architecture is nice because the changes to the global state are localized to the specified inputs of the transaction, and it’s this localization which allows for the high degree of parallelism at the heart of this article. We can have multiple heads checking multiple transactions and there will be no conflicts because we know ahead of time the region of state space that each transaction can modify. So the UTXO model is highly scalable because it is highly parallelizable.
Ethereum is very different because it uses an account based model. You can imagine the head is inside the global state space and has read and write access to everything. This makes Ethereum more flexible but can also lead to unexpected results. For example, Alice could write a transaction that debits her account and credits Bob’s account, but maybe, if the contracts are confusing as they often are, Eve can write a transaction that debits Alice’s account and credits Eve’s account. This is not possible in Bitcoin or Nexa because the inputs are essentially firewalled. Ethereum’s model won’t be parallelizable like the Bitcoin or Nexa model, because the region of state space that a transaction can interact with cannot be localized like it can in Bitcoin.
Nexa and Ethereum are two completely different things that serve two different purposes. In Nexa, miners compete via proof of work to confirm recent transactions in a block. Global state access is not necessary because a coin belongs to its owner. Ether is a share in a decentralized company and it is not a coin or commodity like Bitcoin or Nexa.
That is three boxes ticked. Scalable, from parallel pipelines and a tree for sets. Extensible, from the feedback loop that turned the engine into a Turing machine. Compressible, from committing the ledger to the block header so a proof can stand in for a database. The fourth box, incentive compatible, was the whole subject of the first article. On paper, the engine is now complete: a better Bitcoin, checked box by box, built from wires and gates. What remains is to build it out of real silicon you can hold in your hand, and that is where this series goes next.
Sources
-
Parallel pipelines, the inverted-clock race fix, the tree for sets, the feedback loop and Turing-machine argument, UTXO commitments, and the Nexa-versus-Ethereum comparison: Peter Rizun, “A New Chapter in Scaling: Cryptocurrency-specific integrated circuits,” Australian Crypto Convention, Sydney, 23 November 2024. Transcript: Peter R. Rizun on X: "https://t.co/AQnAQyUHa1" / X.
-
The compact bitwise prefix tree for the UTXO set builds on the “ultimate blockchain compression” thread, BitcoinTalk, 2012: Ultimate blockchain compression w/ trust-free lite nodes. Hashing a block as a set rather than a list builds on Amaury Séchet’s work.
-
The SPV proof concept: Satoshi Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System,” 2008, https://bitcoin.org/bitcoin.pdf.
-
Previous articles in this series: “Why Nexa Builds Hardware,” Why Nexa Builds Hardware, and “A Node Made of Wires,” A Node Made of Wires.