EarthBucks Transaction State Machine, Part 2: Instant Blocks Globally

Bitcoin demonstrated that electronic cash is possible, but it is not perfect. One of the biggest problems with Bitcoin is that a transaction is confirmed slowly. You have to wait for a transaction to be confirmed for several blocks to have a high probability that it won’t be reversed. It doesn’t have to be this way.

As described in the previous article, transactions can be confirmed instantly, if only you poll the known mines and ensure that a majority agree that a transaction is valid. The only thing that you have to change about Bitcoin is that every mine must have a domain name.

Bitcoin has another weird issue. Every transaction is sent once when it is created, and it is sent again when a block is found. Block propagation should be as fast as possible because it is competitive, but the requirement to send every transaction a second time slows down block propagation. However, it doesn’t have to be this way.

Because mines on EarthBucks are identifiable by a domain name, they can keep track of the latest Merkle tree from every other mine, which is the data structure that contains all transactions for a given block. As new transactions come in, the mine verifies that the transaction is valid across a majority of mines, and then builds and synchronizes its Merkle tree.

Although all mines see the same transactions, they don’t see them in the same order, as the order depends on the geographic location of the origin vs. the geographic location of the mine. For instance, a mine in New York City sees all transactions from Tokyo with a roughly 70ms delay.

By synchronizing the Merkle tree, every mine has the full contents of every block, including the order of transactions as seen by every other mine, whenever a new block is found. This means the only thing an EarthBucks mine must transmit when finding a new block is the block header, the mint transaction, and the previous Merkle root. A receiving mine can verify that the new mint transaction, which is always the last transaction in a block, is simply added to the existing known Merkle tree, and there is no need to re-transmit or re-verify all existing transactions in that block.

The full EarthBucks transaction state machine is as follows:

• Received: Someone has created a transaction, and this mine has received it. A globally unique order number (per mine) is assigned to this transaction.
• Validated: The transaction is validated by the mine. It is either valid or not.
• Voted: The transaction is voted on by the network. A majority of mining power must agree that the transaction is valid to proceed.
• Merkled: The transaction is included in the current working Merkle tree of the mine.
• Synchronized: The Merkle proof of this transaction has been synchronized to all mines.
• Block: The transaction is included in a block.

After a transaction is “voted,” another round of messages is sent to give the order number of the new transaction to all other mines. Each mine can then deterministically reproduce the Merkle tree of every other mine. That is all the data that must be sent for each transaction so that when a block is found, only the new header and mint transaction need to be sent.

Both transactions and blocks propagate “instantly” on EarthBucks because the amount of data is small, only around the size of an ordinary transaction or header, which is less than 1kb, and only two back-and-forth messages must be sent, one message to vote on a transaction and another synchronize the Merkle tree. All of this should occur in less than a second (typically only about 300ms), making EarthBucks transactions and blocks effectively instant.