Using Merklix tree to shard block validation

When scaling a system, there always comes a time when all of the processing cannot be done on one machine. This problem is solved by spreading the workload across several machines. This presents some challenges however, solutions are well known in the industry.

In a trustless system such as Bitcoin, peers generally do not trust each other. Currently this is solved by having all peers doing all of the validation, which obviously doesn’t scale, at all. If we are to shard the blockchain, how can a node trust that other shards are validating properly ?

Using Merklix tree

The first step to be able to shard the blockchain is to have a way to identify which node is in charge of which part of the block. By using Merklix tree as a key value store in the block, the key being the transaction id and the value the transaction itself, it is easy to shard the workload by prefix of the transaction id, in a similar way it could be done for the UTXO set.

Trusting other shards are validating as well

Now we need a way for nodes in a shard to be confident enough that nodes in other shard are validating properly. There are essentially 2 roads, passive security, where other shards provide a proof they validated properly, and the active one, where nodes publish a fraud proof when something invalid is found in their shard.

The passive approach can be achieved with SNARK. SNARK are compact cryptographic proofs that a computation has been done successfully. While this may seem like an attractive tool, it does require a very large amount of resources from the prover, which would be prohibitively expensive in this use case. There are some promising advancements such as the use of cycles of elliptic curves that could get us there in the future, but it is not realistic at this stage.

Which leaves us with the active solution. Assume the other shards are correct unless some other node provides you a proof they aren’t. This seems like it would be insecure, but the security assumption done here isn’t that big. In effect, you assume that there is at least one honest node per shard. Producing a block is very expensive for miners, so there is a strong incentive for them to make sure their blocks are valid. In addition building on top of an invalid block is also a costly mistake, so miners have a strong incentive to check each other’s work. Many businesses in the space also have a strong incentive to do so. Finally, running a node in a shard could be cheap for the enthusiast. It looks like this would be secure enough in practice.

Fraud proofs for transactions

As we discussed earlier, we need to be able to provide a cryptographic proof that something is invalid in a shard. The first thing we want to prove is that transactions are valid. Using our scheme we can prove that:

  • A transaction is in a block via a Merklix proof
  • It’s input are or aren’t in the UTXO set using Merklix proof

If a block contains an invalid transaction, a proof that this transaction is in the block can be produced. If an input is required to produce the proof, another Merklix proof can be produced. This covers all we want to do with transactions.

Fraud proofs for aggregates in the block

Now that we can validate that all transactions in the block are valid and can provide a proof in case some isn’t, we need to validate that some information across the whole block is consistent. The typical example is that the transaction fees of all the transactions are accounted for properly in the coinbase.

Because these fees are aggregated over the whole block, we have a problem. Hopefully, we can aggregate the transaction fee in the Merklix tree by modifying it slightly in order to include this aggregate in every node, just as it is done with the prefix. It is now possible to know how much fees are in some shard, and it is possible for any node in that shard to produce a proof, if fees don’t add up.

The same technique can be used for any other block wide limit, such as the sigops limit, but I would argue that it is not necessary to enforce these once quadratic hashing is solved, which it looks like it is going to be soon.

Double spend

While double spend proofs are easy to produce – we can produce the 2 transactions that spend the same input – these 2 transactions may be in different shards and not be detected. Oops !

There are essentially two ways to solve this problem. One is to add a sentinel in the UTXO set “this output has been spent by X”. It becomes impossible to create a valid UTXO with a double spend. The sentinel can be kept for one block and then thrown away. While this is a solid solution, it basically doubles the writes in the UTXO set, which seems like a fairly high cost.

Alternatively, is is possible to aggregate amounts in the UTXO set, in the same way it is done for transaction fees in the block. This way, we can prove that the money supply does not grow due to double spending. Such blocks could effectively be rejected without knowing where the double spend is, only that it happened. This solution has also the extra property of obviating the need to aggregate transaction fees in the block – but that would still be needed for other aggregate constraints.

Impact on SPV and Conclusion

If we consider SPV to be node validating 0 shard, we can understand that this model improves their security considerably. They can be made aware of any invalid thing going on in the blockchain and can’t be lied to about the UTXO set. This is a significant improvement over current security level.

Sharding the blockchain is something that can actually be done, assuming there is at least one honest node in each shard. Actors that do wish to validate the whole blockchain can still do it, but these actors would still benefit from technology that allows them to spread the workload.

Using this technology, we can make sure that the blockchain scales to meet global demand, while ensuring users will maitain a high level of security. So what are we waiting for ?

One thought on “Using Merklix tree to shard block validation

  1. Pingback: Sharding FAQ - Cyber Capital

Leave a Reply

Your email address will not be published. Required fields are marked *