TIP-908: Committing to transactions with dense Merkle trees

[nullchinchilla]

TIP	908
Category	9xx (consensus-breaking)
Author	Eric Tung (eric@themelio.org)

Summary

Right now, State::transactions, which contains all the transactions at that given height, is a 256-bit sparse Merkle tree (implemented in novasmt) containing a mapping from the no-signature hash of a transaction, to that transaction. This is the same way other fields, like "coins", are handled. The corresponding field in the header is simply the root hash of this mapping.

This TIP proposes to replace this SMT with a traditional, dense Merkle tree similar to that of Bitcoin. Other state fields will continue to use sparse Merkle trees.

Motivation

In most cases, SMTs are quite performant. However, they do require 256 hashes to verify a proof. This is okay in the vast majority of cases, since blake3 is extremely fast --- but not when hashes are extremely expensive.

That is the case, however, for relay contracts on EVM chains like Ethereum. This is because these relay contracts must implement a "SPV client" in EVM, which involves implementing blake3 in EVM, an extremely high-gas undertaking. Calculating an extremely expensive blake3 hash 256 times is so costly that it would cost tens of thousands of dollars and be difficult to fit within a single Ethereum block.

By changing the transactions field to use a dense Merkle tree, we drastically cut down on the number of hashes required for basic SPV verifications of an existing transaction. Instead of 256 hashes, we have log_2(n) hashes, where n is merely the number of transactions in a single block. This is almost certainly <10 hashes per proof.

Proposed changes

After a certain "flag day" block height, the transactions field of the Header stops referring to the root hash of a 256-bit SMT, but instead refers to the root hash of a normal Merkle tree that:

• contains a data block for each transaction, of the form H'(tx) || H(tx), where H'(tx) is the no-signature hash of the transaction, while H(tx) is the hash of the full stdcode encoding of the transaction. This ensures committing to the entire content of the transaction, while keeping unique identifiers that ignore the malleable part of the transaction.
• datablock and node hash-functions the same as novasmt

Deployment

TBD

Alternatives

We could alternatively do one of the following:

• Switch to something other than plain SMTs for all data, for example compact SMTs. The problem is that this would require an extremely intrusive upgrade that would require us to maintain both SMT code and CSMT code for the forseeable future.
• Switch to sha256, blake2b, or keccak for the hash function. This is even more disruptive.
• Have EVM suck it up, and wait for eth2/use rollups.