Spent and Unspent UTXO Append-Only Merkle Roots for Fuel Block Header Design

[SilentCicero]

Abstract

Fuel light clients can only prove inclusion of UTXOs and transactions. While this is useful for proving a UTXO actually existed at one point, it is not useful for proving that a UTXO was either spent or unspent by a specific block. This makes light clients less useful for determining things like a users balance, or their unspent UTXOs cryptographically from the current block header.

Chia Design

The Chia blockchain uses two append only Merkle roots for spent and unspent UTXOs in their block header. This enables light clients to have a view of the current unspent UTXOs. The append-only nature reduces the overhead of having to delete or update the trees with O(1) efficiency. Full nodes would only have to store the farthest most right side of the tree.

Append-Only Merkle Tree Resources

• https://docs.rs/merkle-log/latest/merkle_log/
• https://eprint.iacr.org/2016/683.pdf?ref=hackernoon.com
• https://crypto.stackexchange.com/questions/9198/efficient-incremental-updates-to-large-merkle-tree

Design Challenges

Parallelism loss due to serial nature of append-only calculation. While the append-only nature is favorable for an O(1) efficiency, it will still need to be done in serial per-block. This may be okay, but is not as parallizable as calculating a classical binary Merkle tree root as we do for the transaction root (which can be done in parallel). This may be an acceptable loss as you can still verify blocks in parallel and verify across blocks in a similar fashion, but a single thread will have to be used to build the final append-only structure.

Fraud Proving Benefits

These trees would also vastly simplify the fraud proving inputs required to prove a single transaction valid or invalid. Without these trees, we have to provide full transaction proofs for each transaction input in the challenge transaction. With these trees, we will only need to provide the proofs to the unspent UTXO trees, which is far simpler by design.