Re: [bitcoin-dev] Rolling UTXO set hashes

[Pieter Wuille <pieter.wuille@gmail.com>]

On Tue, May 16, 2017 at 4:01 AM, Peter Todd via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> To be clear, *none* of the previous (U)TXO commitment schemes require *miners*
> to participate in generating a commitment. While that was previously thought to
> be true by many, I've seen no counter-arguments to the argument I published I
> few months ago(1) that (U)TXO commitments did not require a soft-fork to
> deploy.
>
> 1) "[bitcoin-dev] TXO commitments do not need a soft-fork to be useful",
>    Peter Todd, Feb 23 2017,
>    https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013591.html

I'm aware, I agree, and I even referenced that mail in my original post.

However, all of those approaches still require a network wide choice
to be useful. A validating node that does not maintain a UTXO X must
get a proof of its unspentness from somewhere for at least the block
which contains a spend of X. In a world where such a model is deployed
network-wide, that proof information is generated by the wallet and
relayed wherever needed. In a partial deployment however, you need
nodes that can produce the proof for other nodes, and the ability to
produce a proof is significantly more expensive than running either an
old or a new full node.

This ability to produce proofs becomes even harder when there are
different models deployed at once. Even just having a different
criterion for which UTXOs need a proof (eg. "only outputs created more
than 1000 blocks ago") may already cause compatibility issues. Combine
that with the multitude of ideas about this (insertion-ordered TXO
trees, txid-ordered UTXO Patricia tries, AVL+ trees, append-only
bitfield, ...) with different trade-offs (in CPU, RAM for validators,
complexity for wallets/index services, ...), I don't think we're quite
ready to make that choice.

To be clear: I'm very much in favor of moving to a model where the
responsibilities of full nodes are reduced in the long term. But
before that can happen there will need to be implementations,
experiments, analysis, ...

Because of that, I think it is worthwhile to investigate solutions to
the "how can we efficiently compare UTXO sets" problem separately from
the "how do we reduce full node costs by sending proofs instead of it
maintaining the data". And rolling UTXO set hashes are a solution for
just the first - and one that has very low costs and no normative
datastructures at all.

-- 
Pieter