Succinctly verifiable computation

Mir supports arbitrary computations, but there are no gas costs. Instead, each transaction comes with a cryptographic proof showing that it is valid. These small proofs can be verified in constant time, regardless of the space or time consumed by the underlying computation.

The transactions in a block are then arranged as leaves in a binary tree, and for each non-leaf vertex, the network generates a proof which recursively verifies the proofs of its two subtrees. This effectively compresses two proofs into one. At the end of the process, we're left with a single proof (corresponding to the root of the tree) which verifies the entire block of transactions.

By downloading this root proof, a client can verify that an entire block is valid without having to download the underlying transaction data. This approach allows light clients, such as mobile wallets, to get the same security guarantees that full nodes enjoy.

Sharding without compromising security

In most other sharded blockchain designs, a block is presumed to be valid if it was signed by 2/3 of the validators in a shard. In such systems, there are two ways in which an attacker can spend the same coins multiple times:

  1. If they control 1/3 of the validators in a single shard, they can create two blocks, each containing one side of a double spend. They would then broadcast both blocks at the same time, causing half of honest validators to sign one, and half to sign the other. The attacker would then sign both blocks, giving both of them 2/3 signatures.
  2. If they control 2/3 of the validators in a single shard, they can create a single block containing transactions which spend the same coins many times over. They would then and sign the block with the 2/3 validators they control, and not require any signatures from honest validators.

Note that controlling 2/3 of the validators in a single shard requires much less than 2/3 stake. Vitalik has suggested 111 validators per shard as a reasonable minimum, in which case an attacker with only 1/3 stake could eventually get 2/3 representation on one shard (after an expected 240 chances). This is assuming that validators are assigned to shards randomly, with an unbiasable source of entropy.

It is possible to make the first attack unprofitable by punishing validators who sign conflicting blocks. This is ineffective against the second attack, however, since the upside is essentially unlimited.

Thankfully, the cryptographic proofs in our design eliminate these attack vectors entirely. Getting the network to accept an invalid transaction would require falsifying a proof, which is intractable under widely accepted cryptographic assumptions.

A more efficient, lightweight sharding scheme

Other sharded blockchains tend to support a relatively small numbers of shards, with each shard having hundreds of validators. This is for two reasons:

  1. Shards need to involve hundreds of validators, otherwise an attacker with relatively low stake would eventually “get lucky” and find themselves with 2/3 stake on a particular shard. As an extreme example, if each shard only had 7 validators, an attacker with only 10% stake would have a ~0.018% chance of corrupting any particular shard. (This follows from the binomial CDF.) For a patient attacker, it would just be a matter of time before the opportunity arose.
  2. Validators on the main chain must verify that every shard's block was signed by a quorum of validators, which would become a bottleneck if the number of shards was large.

Since we don't rely on honest majorities for validation, the first limitation doesn't apply to our scheme. We also avoid the second limitation by organizing shards into a binary tree, so that each shard only needs to interact with three others shards (its parent and its two children).

Typical shard layout

Mir's shard layout

In our scheme, the only harm that a corrupt shard can cause is temporarily stalling progress until validators are reshuffled. Moreover, it only takes a single honest validator per shard to make progress. This allows us to use extremely small shards, on the order of 10 validators or even less.

A faster BFT consensus algorithm

For cryptocurrencies to achieve real world adoption, latency is paramount. BFT algorithms like Tendermint represent a huge speed improvement over longest-chain systems like Bitcoin, but they still leave plenty of room for improvement.

Tendermint, and similar algorithms like Algorand, operate in cycles consisting of three communication steps: a block proposal followed by two voting steps. Under good conditions, they will terminate after three steps. But when something goes wrong, the current cycle will make no progress, and an additional cycle is needed before the algorithm has a chance at termination.

For instance, suppose that the first leader's proposal is delayed slightly, perhaps due to network congestion in their area. Suppose that half of all nodes receive the proposal before voting commences, while half do not. The proposal then cannot be confirmed in the first cycle, since it will only receive 1/2 approval, which falls short of the 2/3 quorum threshold. The same proposal might still be confirmed in the second cycle, but that entails a termination time of at least six steps.

Our algorithm also terminates in three rounds under good conditions, but it handles quorum failures differently. When a split vote occurs, it is normally resolved with a single extra voting step, increasing the termination time to just four steps.

Our algorithm is based on a partially synchronous network model, but under normal conditions, it is able to progress with the speed of the network rather than waiting for fixed timeouts. It is also safe under asynchrony.

For more details, see our paper which describes the algorithm, proves its correctness, and thoroughly compares it against Tendermint and Algorand.