Idea:Add the UTXO set to blocks

[bitrails]

Motivation

At the moment, anyone wanting to bootstrap any sort of cryptocurrency full node needs the full block chain. For Bitcoin as of 2018-02-26 thats ...(does a quick google search) 160GB(and maybe the segwit data too, don't know if that's included in that number).

Not too awful ($8 @0.05$/GB(Amazon EC2 bandwidth fee)), but if anyone wanted to make the block sizes bigger it would makes getting all that data initially very expensive, which makes running a full node harder. I won't get into the arguments about why that's might or might not be important just consider it.

UTXO set?
Bitcoin full nodes maintain an internal UTXO set (set of all UnspentTransactionOutput(s)). This means they don't have to dig around in all the previous blocks to figure out whether an output is present and hasn't been spent yet. What I'm proposing is a block structure that includes a hash of a canonicalized merkle tree of this UTXO set. Additionally, there would be links between this tree and the transaction merkle tree and vice versa to justify any additions and removals to the UTXO tree and justify the presence of transaction inputs.

Normal full clients won't notice any difference, (although they would now maintain the canonicalized form of the UTXO tree internally) they don't ever need to send the UTXO tree over the network though since the transactions specify how to mutate the last block's UTXO tree to get the next block's UTXO tree. The same is true for archiving of blocks, just keep a cached copy of the UTXO tree for every Nth block and the rest can be computed on the fly.

The real magic is that a client can connect to the network, get the current block and UTXO tree, and just in the same way transaction confirmations increase confidence that a transaction won't be reverted, additional blocks show miners are willing to add work to this blockchain and the UTXO tree that was sent to you.

An attacker could fork the blockchain and modify the UTXO tree then send you that block but no sane profit motivated miner will work on that fork of the chain since it isn't a valid fork. Thanks to the links between the UTXO trees and transaction trees within blocks, and with the right UTXO tree structure it's possible to create a small proof that any given link in the blockchain is invalid by supplying the conflicting merkle branches.

This would be especially great for proof of stake systems since this allows for a small proof of chain link incorrectness and therefore of miner/stakeholder misbehavior.

Generalising
This is a specific case of adding redundancy to the (block/blockchain/distributed ledger) structure. Data structures which are redundant (and therefore don't add network/storage overhead) but that help achieve protocol goals (in this case:easier bootstrapping/validation of chain links). There is a trade-off in reducing implementation flexibility and increasing validation times (since the redundant structures must be built and verified) but it's a tool that might be useful.

Vague Implementation details

• Transactions in each block generates UTXO entries.
• These would be tagged with an index into the transaction merkle tree for the output transaction and put into a per block UTXO entry merkle tree.
• The roots of the per block merkle trees are put into a larger merkle tree covering all per block UTXO trees (yes this means the root of a per block tree changes when an output generated there is spent.)
• When a UTXO is spent, the entry in the UTXO tree is tagged with second tag listing an index into the transaction tree for the spending transaction.
• The spent entry disappears in the next block.
• An output created and spent in the same block would show up in that block's UTXO tree with both tags and then disappear.

Denial of service(not really)
For (Lots of money) you can buy hash power to mine an invalid block. For a short time you can send it to nodes and they will try validating it (and fail). Nodes can immunize others by circulating short proofs of chain link invalidity to other nodes who will then ignore your block. The proofs would be deleted after a certain number of new blocks have been generated under the assumption that the invalid fork hasn't been extended.

Any thoughts?

[1714893319]

1714893319

[1714893319]

1714893319

[1714893319]

1714893319

[1714893319]

1714893319

[1714893319]

1714893319

[DannyHamilton]

It's an interesting idea, and I'd like to see an altcoin try it out.  Implementing it in Bitcoin would require a fork, and I don't see it being important enough for that to happen anytime soon.

I haven't given your idea a lot of thought yet, but it feels like the general concept ought to be possible even if the specifics that you've described have any shortcomings.

[achow101]

This is not a new idea and is something that is actively being worked on.

The UTXO set is actually extremely large and hashing all of it as you describe is actually kind of computationally expensive. Furthermore, that hash has to be recomputed with every block. However there has been work on a fast way to compute the hash of the UTXO set and to efficiently add and remove entries from the hash without having to recompute the whole thing. See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html.

[DannyHamilton]

This is not a new idea and is something that is actively being worked on.

The UTXO set is actually extremely large and hashing all of it as you describe is actually kind of computationally expensive.

Certainly. But so is processing through the entire historical blockchain.

Furthermore, that hash has to be recomputed with every block.

Perhaps.  I've got a gut feeling that might not be necessary, but I'm not sure. I'd have to think about it a bit.  Couldn't it just be computed once every 100 blocks (or 1000 blocks, or 10000 blocks, etc) as sort of a UTXO checkpoint? Then a new node could start up from that checkpoint instead of the genesis block?

I've got a feeling there will be some potential attack vectors here where an attacker can provide a false UTXO and block history, but the computational work of the "valid" chain should be a deterrent.  I haven't thought that all the way through yet.

However there has been work on a fast way to compute the hash of the UTXO set and to efficiently add and remove entries from the hash without having to recompute the whole thing. See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html.

I'll have to read up on that.

[bitrails]

If the UTXO set is put into a merkle-tree then updating any entry just requires updating a set of log2(N) nodes in the merkle tree going down to the root. for a set of 1 billion values this works out to 32 SHA2 operations. (see https://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates)

Furthermore, my proposed implementation keeps UTXOs from all blocks separated and newer UTXOs are more likely to be spent. Most block UTXO trees won't need to be updated. This is the motivation behind the multi-level UTXO cache currently used in core (that only keeps recent UTXOs in memory).

All this updating is parallelizeable so checking block validity can be easily sped up by adding more computers to your full node (if you are a miner and block validation has to be fast).

but the computational work of the "valid" chain should be a deterrent.  I haven't thought that all the way through yet.

If an attacker wants to do this, they have to keep adding blocks to an invalid chain which no main chain aware nodes will ever accept (very costly). In proof of work this costs them electricity, in proof of stake this would actually cost them stake. (or fees if they don't disclose all information needed to validate the block since they can't double sign at a given height)

It's an interesting idea, and I'd like to see an altcoin try it out.  Implementing it in Bitcoin would require a fork, and I don't see it being important enough for that to happen anytime soon.

Actually, a soft fork is definitely possible by merge mining this "alt-coin" into the Bitcoin blockchain. It provides no validity guarantees (since maliciously merge-mined blocks don't penalize miners) but it's a way to signal acceptance.

[piotr_n]

As I said about 5 years ago, this would take at least 10 years to deliver for the core dev team.
So don't expect it within the next 5 years

[achow101]

Actually, a soft fork is definitely possible by merge mining this "alt-coin" into the Bitcoin blockchain. It provides no validity guarantees (since maliciously merge-mined blocks don't penalize miners) but it's a way to signal acceptance.

It could be deployed just as a normal soft fork into Bitcoin by putting the UTXO set commitment into another OP_RETURN output just like what segwit does for the witness root commitment.