[Motivation]

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?