← Back to team overview

mimblewimble team mailing list archive

Treeless block and UTXO set validation


Hi all,
I think we could do without any type of Merkle tree, both in block headers and in the complete UTXO set (for sync). Please tell me if I'm wrong.
A block is composed of the following information (ignoring header):

- Outputs, with a commitment, range proof and a features bitset.
- Inputs, which are just outputs commitments.
- Kernels, with the excess value, its signature and the fee.

The UTXO set necessary to sync-up a new node, assuming it has the header chain already, is composed of outputs (all unspents) and kernels (all of them) with same information as above.
The purpose of putting some sort of Merkle tree root in a block header is to make it hard to mess with block data, as it would change the proof of work (also SPV but let's ignore that for a sec). Now lets get rid of all tree roots and just put 2 things in block headers: the sum of excess values over the whole block and the sum of excess values since genesis (summing all blocks). What can we mess with?

- Output commitments can't be changed, wouldn't match the sums (both in block and total in UTXO set).
- Output range proofs can't be changed, they would get invalidated with respect to their commitment.
- Inputs can't be changed, would match the sum.
- Kernel excess can't be changed, wouldn't match the sums (also both in block and total in UTXO set)
- Kernel sig can't be changed, wouldn't validate with the excess as pubkey.
- Kernel fee can't be changed, wouldn't validate with the sig.

Only the feature bitsets could be potentially messed with, but right now they're only used to flag coinbase kernels and outputs and messing with that would also invalidate sums.
The result would be that full nodes don't need to maintain any tree of any type, making it a lot simpler and saving a fair amount of space. Also when a new node wants to sync up, there's no tree to transfer and that process also get a fair amount simpler. If I'm right, I have to apologize to Merope for not seeing this earlier. And obviously we would lose some features, SPV would get harder and spent proofs, while still possible (I think), wouldn't be as elegant.
- Igno

Follow ups