Merkle tree of unspent transactions (MTUT), for serverless thin clients and self-verifiable prunned blockchain.

Hello,

I've written this proposal. C&P of the overview:

Satoshi's original paper describes a way of prunning spent transactions in the blockchain to save storage space while it remains consistent and verifiable, but it's useless for partial blockchain downloads: while you can know if a given transaction is in the blockchain, you can't know if it has been spent in a subsequent transaction. This proposal describes how to add a hash-tree based check in the blockchain that allows to verify if a transaction is unspent without downloading and checking all the blockchain. The idea is not new, but at the time of this writing there isn't any technical description of how this should be done. Aditionally, this solution is rather simple.

https://en.bitcoin.it/wiki/User:DiThi/MTUT

Cheers

On 2012-01-23 20:00:59 -0600, Alberto Torres said:

> This proposal describes how to add a hash-tree based check in the
> blockchain that allows to verify if a transaction is unspent without
> downloading and checking all the blockchain. The idea is not new, but
> at the time of this writing there isn't any technical description of
> how this should be done.

Thanks for writing this up (it's high time somebody did). I like your acronym, but shouldn't it be "MTUO" since you spend *outputs* rather than *transactions*? A transaction can have multiple outputs, some of which are spent and others which aren't.

I've added a link to your proposal on the https://en.bitcoin.it/wiki/Thin_Client_Security wiki page.

> Once 55% of blocks includes a valid MTUT hash in a 2-week timespan,
> they should reject any block with an invalid (i.e. probably malicious)
> MTUT hash block while accepting blocks without MTUT.

Just like OP_EVAL/p2sh, this creates the (small) risk of a blockchain split.

Unlike adding a new transaction type, here it's possible to eliminate this risk: give each MTUT an additional "prev" pointer (hash of some prior block) which points to the latest prior block with a correct MTUT. This produces a "chain within the chain" of blocks that have valid MTUTs. Hostile miners are free to add bogus-MTUT-blocks; those bogus blocks will simply never be included in the "inner chain", just like invalid blocks mined by hostile miners are never included in the blockchain. By downloading the last day's worth of blocks (which is not much data at all), a client can see which "inner chain" the majority of the hashpower believed during the last 24 hours. This eliminates the need for a vote in any specific block -- in effect you get a "rolling election".

This "inner chain" approach can be broadened to a K-ary tree by including K-many prior-block pointers. With one of these in every block (and sensible choices) you wind up with O(log_K(chain_length))-operation hash-secure access to arbitrary blocks in the middle of the chain. This is an important building block for ultra-high-security thin clients. Even if only a 1/K of the network's hashpower starts adding these pointers the worst-case number of operations needed to reach an arbitrary block will still converge (though much more slowly) towards this ideal.

  - e