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, speed is paramount. That's why we developed a new BFT consensus algorithm which can terminate after just two steps of communication. Similar algorithms, such as DLS, Tendermint and Algorand, typically work in phases consisting of three steps: a leader proposal followed by a two-phase commit. Our algorithm is able to guarantee convergence without leaders, so the proposal step simply isn't needed.

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.