Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Peter Todd via bitcoin-dev]

On Fri, May 20, 2016 at 11:46:32AM +0200, Johnson Lau wrote:
> How is this compared to my earlier proposal: 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-December/011952.html
>  
> 
>  ?
> 
> In my proposal, only the (pruned) UTXO set, and 32 bytes per archived block, 
> are required for mining. But it is probably more difficult for people to 
> spend an archived output. They need to know the status of other archived 
> outputs from the same block. A full re-scan of the blockchain may be needed 
> to generate the proof but this could be done by a third party archival node.

We're working along the same lines, but my proposal is much better fleshed out;
I think you'll find you missed a few details if you flesh out yours in more
detail. For instance, since your dormant UTXO list is indexed by UTXO
expiration order, it's not possible to do any kind of verification that the
contents of that commitment are correct without the global state of all UTXO
data - you have no ability to locally verify as nothing commits to the contents
of the UTXO set.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Johnson Lau via bitcoin-dev]

How is this compared to my earlier proposal: 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-December/011952.html
 

 ?

In my proposal, only the (pruned) UTXO set, and 32 bytes per archived block, 
are required for mining. But it is probably more difficult for people to spend 
an archived output. They need to know the status of other archived outputs from 
the same block. A full re-scan of the blockchain may be needed to generate the 
proof but this could be done by a third party archival node.

> 
> 
> 
> ## Implementation
> 
> Our proposed high-performance/low-latency delayed commitment full-node
> implementation needs to store the following data:
> 
> 1) UTXO set
> 
>Low-latency K:V map of txouts definitely known to be unspent. Similar to
>existing UTXO implementation, but with the key difference that old,
>unspent, outputs may be pruned from the UTXO set.
> 
> 
> 2) STXO set
> 
>Low-latency set of transaction outputs known to have been spent by
>transactions after the most recent TXO commitment, but created prior to the
>TXO commitment.
> 
> 
> 3) TXO journal
> 
>FIFO of outputs that need to be marked as spent in the TXO MMR. Appends
>must be low-latency; removals can be high-latency.
> 
> 
> 4) TXO MMR list
> 
>Prunable, ordered list of TXO MMR's, mainly the highest pending commitment,
>backed by a reference counted, cryptographically hashed object store
>indexed by digest (similar to how git repos work). High-latency ok. We'll
>cover this in more in detail later.
> 
> 



signature.asc
Description: Message signed with OpenPGP using GPGMail
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Peter Todd via bitcoin-dev]

On Thu, May 19, 2016 at 04:23:28PM -0600, Nick ODell wrote:
> What if two people create transactions from oupoints  within the same MMR
> tree tip, at the same time?
> 
> For example, I create transaction A plus an MMR proof that MMR tip X will
> become Y.
> 
> On the other side of the planet, someone else creates transaction B, plus
> an MMR proof that tip X will become Z.
> 
> Can a miner who receives A and B put both into a block, without access to
> the outputs that were pruned?

The MMR proofs provided by transactions aren't proofs of *how* the MMR should
be be changd; they're just proofs that the MMR is in a certain state right now.
You're situation is just an example of a double-spend, that miners have to
detect if they don't want to create invalid blocks. Specifically, if I
understand your example correctly, they'd be rejected by the STXO set.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Nick ODell via bitcoin-dev]

What if two people create transactions from oupoints  within the same MMR
tree tip, at the same time?

For example, I create transaction A plus an MMR proof that MMR tip X will
become Y.

On the other side of the planet, someone else creates transaction B, plus
an MMR proof that tip X will become Z.

Can a miner who receives A and B put both into a block, without access to
the outputs that were pruned?
# Motivation

UTXO growth is a serious concern for Bitcoin's long-term decentralization.
To
run a competitive mining operation potentially the entire UTXO set must be
in
RAM to achieve competitive latency; your larger, more centralized,
competitors
will have the UTXO set in RAM. Mining is a zero-sum game, so the extra
latency
of not doing so if they do directly impacts your profit margin. Secondly,
having possession of the UTXO set is one of the minimum requirements to run
a
full node; the larger the set the harder it is to run a full node.

Currently the maximum size of the UTXO set is unbounded as there is no
consensus rule that limits growth, other than the block-size limit itself;
as
of writing the UTXO set is 1.3GB in the on-disk, compressed serialization,
which expands to significantly more in memory. UTXO growth is driven by a
number of factors, including the fact that there is little incentive to
merge
inputs, lost coins, dust outputs that can't be economically spent, and
non-btc-value-transfer "blockchain" use-cases such as anti-replay oracles
and
timestamping.

We don't have good tools to combat UTXO growth. Segregated Witness proposes
to
give witness space a 75% discount, in part of make reducing the UTXO set
size
by spending txouts cheaper. While this may change wallets to more often
spend
dust, it's hard to imagine an incentive sufficiently strong to discourage
most,
let alone all, UTXO growing behavior.

For example, timestamping applications often create unspendable outputs due
to
ease of implementation, and because doing so is an easy way to make sure
that
the data required to reconstruct the timestamp proof won't get lost - all
Bitcoin full nodes are forced to keep a copy of it. Similarly anti-replay
use-cases like using the UTXO set for key rotation piggyback on the uniquely
strong security and decentralization guarantee that Bitcoin provides; it's
very
difficult - perhaps impossible - to provide these applications with
alternatives that are equally secure. These non-btc-value-transfer use-cases
can often afford to pay far higher fees per UTXO created than competing
btc-value-transfer use-cases; many users could afford to spend $50 to
register
a new PGP key, yet would rather not spend $50 in fees to create a standard
two
output transaction. Effective techniques to resist miner censorship exist,
so
without resorting to whitelists blocking non-btc-value-transfer use-cases as
"spam" is not a long-term, incentive compatible, solution.

A hard upper limit on UTXO set size could create a more level playing field
in
the form of fixed minimum requirements to run a performant Bitcoin node, and
make the issue of UTXO "spam" less important. However, making any coins
unspendable, regardless of age or value, is a politically untenable economic
change.


# TXO Commitments

A merkle tree committing to the state of all transaction outputs, both spent
and unspent, we can provide a method of compactly proving the current state
of
an output. This lets us "archive" less frequently accessed parts of the UTXO
set, allowing full nodes to discard the associated data, still providing a
mechanism to spend those archived outputs by proving to those nodes that the
outputs are in fact unspent.

Specifically TXO commitments proposes a Merkle Mountain Range¹ (MMR), a
type of deterministic, indexable, insertion ordered merkle tree, which
allows
new items to be cheaply appended to the tree with minimal storage
requirements,
just log2(n) "mountain tips". Once an output is added to the TXO MMR it is
never removed; if an output is spent its status is updated in place. Both
the
state of a specific item in the MMR, as well the validity of changes to
items
in the MMR, can be proven with log2(n) sized proofs consisting of a merkle
path
to the tip of the tree.

At an extreme, with TXO commitments we could even have no UTXO set at all,
entirely eliminating the UTXO growth problem. Transactions would simply be
accompanied by TXO commitment proofs showing that the outputs they wanted to
spend were still unspent; nodes could update the state of the TXO MMR purely
from TXO commitment proofs. However, the log2(n) bandwidth overhead per
txin is
substantial, so a more realistic implementation is be to have a UTXO cache
for
recent transactions, with TXO commitments acting as a alternate for the
(rare)
event that an old txout needs to be spent.

Proofs can be generated and added to transactions without the involvement of
the signers, even after the fact; there's no need for the proof itself to
signed and the proof is not part of the transac

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Jorge Timón via bitcoin-dev]

On May 19, 2016 01:53, "Peter Todd"  wrote:
tip of the tree.
> >
> > How expensive it is to update a leaf from this tree from unspent to
spent?
>
> log2(n) operations.

Updating a leaf is just as expensive as adding a new one?
That's not what I expected.
Or is adding a new one O (1) ?

Anyway, thanks, I'll read this in more detail.

> > Wouldn't it be better to have both an append-only TXO and an append-only
> > STXO (with all spent outputs, not only the latest ones like in your
"STXO")?
>
> Nope. The reason why this doesn't work is apparent when you ask how will
the
> STXO be indexed?

Just the same way the TXO is (you just stop updating the txo leafs from
unspent to spent.

> If it's indexed by outpoint - that is H(txid:n) - to update the STXO you
need
> he entire thing, as the position of any new STXO that you need to add to
the
> STXO tree is random.
>
> OTOH, if you index the STXO by txout creation order, with the first txout
ever
> created having position #0, the second #1, etc. the data you may need to
update
> the STXO later has predictable locality... but now you have something
that's
> basically identical to my proposed insertion-ordered TXO commitment
anyway.

Yeah, that's what I want. Like your append only TXO but for STXO (that way
we avoid ever updating leafs in the TXO, and I suspect there are other
advantages for fraud proofs).

> Incidentally, it's interesting how if a merbinner tree is insertion-order
> indexed you end up with a datastructure that's almost identical to a MMR.

No complain with MMR. My point is having 2 of them separated: one for the
TXO (entries unmutable) and one for the STXO (again, entries unmutable).

Maybe it doesn't make sense, but I would like to understand why.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Peter Todd via bitcoin-dev]

On Wed, May 18, 2016 at 01:14:59PM +0200, Jorge Timón wrote:
> On May 17, 2016 15:23, "Peter Todd via bitcoin-dev" <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> > # TXO Commitments
> >
> 
> > Specifically TXO commitments proposes a Merkle Mountain Range¹ (MMR), a
> > type of deterministic, indexable, insertion ordered merkle tree, which
> allows
> > new items to be cheaply appended to the tree with minimal storage
> requirements,
> > just log2(n) "mountain tips". Once an output is added to the TXO MMR it is
> > never removed; if an output is spent its status is updated in place. Both
> the
> > state of a specific item in the MMR, as well the validity of changes to
> items
> > in the MMR, can be proven with log2(n) sized proofs consisting of a
> merkle path
> > to the tip of the tree.
> 
> How expensive it is to update a leaf from this tree from unspent to spent?

log2(n) operations.

I wrote a full MMR implementation with pruning support as part of my
proofchains work:

https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal/mmr.py

Documentation is a bit lacking, but I'd suggest reading the above source code
and the unit tests(1) to understand what's going on. As of writing item
retrieval by index is implemented(2), and if you follow how that works you'll
see it's log2(n) operations; changing elements in-place isn't yet
implemented(3) but would be a fun homework problem. I'll bet anyone a beer that
you'll find it can be done in k*log2(n) operations, with a reasonably small k. 
:)

Additionally, I also have a merkelized key:value prefix tree implementation
called a "merbinner tree" in the same library, again with pruning support. It
does implement changing elements in place(4) with log2(n) operations.

Incidentally, something I probably should have made more clear in my TXO
commitments post is that the original MMR scheme I developed for OpenTimestamps
(and independently reinvented for Certificate Transparency) is insufficient:
while you can easily extract a proof that an element is present in the MMR,
that inclusion proof doesn't do a good job of proving the position in the tree
very well. OpenTimestamps didn't need that kind of proof, and I don't think
Certificate Transparency needs it either. However many other MMR applications
do, including many types of TXO commitments.

My proofchains MMR scheme fixes this problem by making each inner node in the
MMR commit to the total number of elements under it(5) - basically it's a
merkle-sum-tree with the size of the tree being what's summed. There may be
more efficient ways to do this, but a committed sum-length is easy to
implement, and the space overhead is only 25% even in the least optimised
implementation possible.

1) 
https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f36377ad6c1901de19273604e6fbc/proofmarshal/test/test_mmr.py
2) 
https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f36377ad6c1901de19273604e6fbc/proofmarshal/mmr.py#L294
3) 
https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f36377ad6c1901de19273604e6fbc/proofmarshal/mmr.py#L230
4) 
https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f36377ad6c1901de19273604e6fbc/proofmarshal/merbinnertree.py#L140
5) 
https://github.com/proofchains/python-proofmarshal/blob/3f0ba0a9d46f36377ad6c1901de19273604e6fbc/proofmarshal/mmr.py#L139

> Wouldn't it be better to have both an append-only TXO and an append-only
> STXO (with all spent outputs, not only the latest ones like in your "STXO")?

Nope. The reason why this doesn't work is apparent when you ask how will the
STXO be indexed?

If it's indexed by outpoint - that is H(txid:n) - to update the STXO you need
he entire thing, as the position of any new STXO that you need to add to the
STXO tree is random.

OTOH, if you index the STXO by txout creation order, with the first txout ever
created having position #0, the second #1, etc. the data you may need to update
the STXO later has predictable locality... but now you have something that's
basically identical to my proposed insertion-ordered TXO commitment anyway.

Incidentally, it's interesting how if a merbinner tree is insertion-order
indexed you end up with a datastructure that's almost identical to a MMR.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Jorge Timón via bitcoin-dev]

On May 17, 2016 15:23, "Peter Todd via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> # TXO Commitments
>

> Specifically TXO commitments proposes a Merkle Mountain Range¹ (MMR), a
> type of deterministic, indexable, insertion ordered merkle tree, which
allows
> new items to be cheaply appended to the tree with minimal storage
requirements,
> just log2(n) "mountain tips". Once an output is added to the TXO MMR it is
> never removed; if an output is spent its status is updated in place. Both
the
> state of a specific item in the MMR, as well the validity of changes to
items
> in the MMR, can be proven with log2(n) sized proofs consisting of a
merkle path
> to the tip of the tree.

How expensive it is to update a leaf from this tree from unspent to spent?

Wouldn't it be better to have both an append-only TXO and an append-only
STXO (with all spent outputs, not only the latest ones like in your "STXO")?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Chris Priest via bitcoin-dev]

On 5/17/16, Eric Lombrozo via bitcoin-dev
 wrote:
> Nice!
>
> We’ve been talking about doing this forever and it’s so desperately needed.
>

"So desperately needed"? How do you figure? The UTXO set is currently
1.5 GB. What kind of computer these days doesn't have 1.5 GB of
memory? Since you people insist on keeping the blocksize limit at 1MB,
the UTXO set growth is stuck growing at a tiny rate. Most consumer
hardware sold thee days has 8GB or more RAM, it'll take decades before
the UTXO set come close to not fitting into 8 GB of memory.

Maybe 30 or 40 years from not I can see this change being "so
desperately needed" when nodes are falling off because the UTXO set is
to large, but that day is not today.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Jameson Lopp via bitcoin-dev]

Great post, Peter.

4) By fixing the problem (or possibly just "fixing" the problem) are
we encouraging/legitimising blockchain use-cases other than BTC value
transfer? Should we?

I don't think it would encourage non-value-transfer usage more
because, as you noted, many such use cases are valuable enough that
people are willing to pay much higher transaction fees in order to
have their data timestamped. I think it's more an issue of the block
space / transaction fee market since the cost of making a transaction
is directly borne by users, as opposed to the cost of the UTXO set
which may not be borne by them if they don't run a full node.

I'm of the opinion that if the world decides that Bitcoin is more
valuable as a trustworthy generalized timestamping mechanism than as a
value transfer system, protocol developers shouldn't try to steer the
ship against the wind. As more people and use cases enter the
ecosystem, the most valuable ones ought to survive - I hope that this
market will be fostered by the developers.

- Jameson


On Tue, May 17, 2016 at 9:23 AM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> # Motivation
>
> UTXO growth is a serious concern for Bitcoin's long-term decentralization.
> To
> run a competitive mining operation potentially the entire UTXO set must be
> in
> RAM to achieve competitive latency; your larger, more centralized,
> competitors
> will have the UTXO set in RAM. Mining is a zero-sum game, so the extra
> latency
> of not doing so if they do directly impacts your profit margin. Secondly,
> having possession of the UTXO set is one of the minimum requirements to
> run a
> full node; the larger the set the harder it is to run a full node.
>
> Currently the maximum size of the UTXO set is unbounded as there is no
> consensus rule that limits growth, other than the block-size limit itself;
> as
> of writing the UTXO set is 1.3GB in the on-disk, compressed serialization,
> which expands to significantly more in memory. UTXO growth is driven by a
> number of factors, including the fact that there is little incentive to
> merge
> inputs, lost coins, dust outputs that can't be economically spent, and
> non-btc-value-transfer "blockchain" use-cases such as anti-replay oracles
> and
> timestamping.
>
> We don't have good tools to combat UTXO growth. Segregated Witness
> proposes to
> give witness space a 75% discount, in part of make reducing the UTXO set
> size
> by spending txouts cheaper. While this may change wallets to more often
> spend
> dust, it's hard to imagine an incentive sufficiently strong to discourage
> most,
> let alone all, UTXO growing behavior.
>
> For example, timestamping applications often create unspendable outputs
> due to
> ease of implementation, and because doing so is an easy way to make sure
> that
> the data required to reconstruct the timestamp proof won't get lost - all
> Bitcoin full nodes are forced to keep a copy of it. Similarly anti-replay
> use-cases like using the UTXO set for key rotation piggyback on the
> uniquely
> strong security and decentralization guarantee that Bitcoin provides; it's
> very
> difficult - perhaps impossible - to provide these applications with
> alternatives that are equally secure. These non-btc-value-transfer
> use-cases
> can often afford to pay far higher fees per UTXO created than competing
> btc-value-transfer use-cases; many users could afford to spend $50 to
> register
> a new PGP key, yet would rather not spend $50 in fees to create a standard
> two
> output transaction. Effective techniques to resist miner censorship exist,
> so
> without resorting to whitelists blocking non-btc-value-transfer use-cases
> as
> "spam" is not a long-term, incentive compatible, solution.
>
> A hard upper limit on UTXO set size could create a more level playing
> field in
> the form of fixed minimum requirements to run a performant Bitcoin node,
> and
> make the issue of UTXO "spam" less important. However, making any coins
> unspendable, regardless of age or value, is a politically untenable
> economic
> change.
>
>
> # TXO Commitments
>
> A merkle tree committing to the state of all transaction outputs, both
> spent
> and unspent, we can provide a method of compactly proving the current
> state of
> an output. This lets us "archive" less frequently accessed parts of the
> UTXO
> set, allowing full nodes to discard the associated data, still providing a
> mechanism to spend those archived outputs by proving to those nodes that
> the
> outputs are in fact unspent.
>
> Specifically TXO commitments proposes a Merkle Mountain Range¹ (MMR), a
> type of deterministic, indexable, insertion ordered merkle tree, which
> allows
> new items to be cheaply appended to the tree with minimal storage
> requirements,
> just log2(n) "mountain tips". Once an output is added to the TXO MMR it is
> never removed; if an output is spent its status is updated in place. Both
> the
> state of a specific item in the MMR, as well

Re: [bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Eric Lombrozo via bitcoin-dev]

Nice!

We’ve been talking about doing this forever and it’s so desperately needed.

> On May 17, 2016, at 3:23 PM, Peter Todd via bitcoin-dev 
>  wrote:
> 
> # Motivation
> 
> UTXO growth is a serious concern for Bitcoin's long-term decentralization. To
> run a competitive mining operation potentially the entire UTXO set must be in
> RAM to achieve competitive latency; your larger, more centralized, competitors
> will have the UTXO set in RAM. Mining is a zero-sum game, so the extra latency
> of not doing so if they do directly impacts your profit margin. Secondly,
> having possession of the UTXO set is one of the minimum requirements to run a
> full node; the larger the set the harder it is to run a full node.
> 
> Currently the maximum size of the UTXO set is unbounded as there is no
> consensus rule that limits growth, other than the block-size limit itself; as
> of writing the UTXO set is 1.3GB in the on-disk, compressed serialization,
> which expands to significantly more in memory. UTXO growth is driven by a
> number of factors, including the fact that there is little incentive to merge
> inputs, lost coins, dust outputs that can't be economically spent, and
> non-btc-value-transfer "blockchain" use-cases such as anti-replay oracles and
> timestamping.
> 
> We don't have good tools to combat UTXO growth. Segregated Witness proposes to
> give witness space a 75% discount, in part of make reducing the UTXO set size
> by spending txouts cheaper. While this may change wallets to more often spend
> dust, it's hard to imagine an incentive sufficiently strong to discourage 
> most,
> let alone all, UTXO growing behavior.
> 
> For example, timestamping applications often create unspendable outputs due to
> ease of implementation, and because doing so is an easy way to make sure that
> the data required to reconstruct the timestamp proof won't get lost - all
> Bitcoin full nodes are forced to keep a copy of it. Similarly anti-replay
> use-cases like using the UTXO set for key rotation piggyback on the uniquely
> strong security and decentralization guarantee that Bitcoin provides; it's 
> very
> difficult - perhaps impossible - to provide these applications with
> alternatives that are equally secure. These non-btc-value-transfer use-cases
> can often afford to pay far higher fees per UTXO created than competing
> btc-value-transfer use-cases; many users could afford to spend $50 to register
> a new PGP key, yet would rather not spend $50 in fees to create a standard two
> output transaction. Effective techniques to resist miner censorship exist, so
> without resorting to whitelists blocking non-btc-value-transfer use-cases as
> "spam" is not a long-term, incentive compatible, solution.
> 
> A hard upper limit on UTXO set size could create a more level playing field in
> the form of fixed minimum requirements to run a performant Bitcoin node, and
> make the issue of UTXO "spam" less important. However, making any coins
> unspendable, regardless of age or value, is a politically untenable economic
> change.
> 
> 
> # TXO Commitments
> 
> A merkle tree committing to the state of all transaction outputs, both spent
> and unspent, we can provide a method of compactly proving the current state of
> an output. This lets us "archive" less frequently accessed parts of the UTXO
> set, allowing full nodes to discard the associated data, still providing a
> mechanism to spend those archived outputs by proving to those nodes that the
> outputs are in fact unspent.
> 
> Specifically TXO commitments proposes a Merkle Mountain Range¹ (MMR), a
> type of deterministic, indexable, insertion ordered merkle tree, which allows
> new items to be cheaply appended to the tree with minimal storage 
> requirements,
> just log2(n) "mountain tips". Once an output is added to the TXO MMR it is
> never removed; if an output is spent its status is updated in place. Both the
> state of a specific item in the MMR, as well the validity of changes to items
> in the MMR, can be proven with log2(n) sized proofs consisting of a merkle 
> path
> to the tip of the tree.
> 
> At an extreme, with TXO commitments we could even have no UTXO set at all,
> entirely eliminating the UTXO growth problem. Transactions would simply be
> accompanied by TXO commitment proofs showing that the outputs they wanted to
> spend were still unspent; nodes could update the state of the TXO MMR purely
> from TXO commitment proofs. However, the log2(n) bandwidth overhead per txin 
> is
> substantial, so a more realistic implementation is be to have a UTXO cache for
> recent transactions, with TXO commitments acting as a alternate for the (rare)
> event that an old txout needs to be spent.
> 
> Proofs can be generated and added to transactions without the involvement of
> the signers, even after the fact; there's no need for the proof itself to
> signed and the proof is not part of the transaction hash. Anyone with access 
> to
> TXO MMR data can (re)generate missing proof

[bitcoin-dev] Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

[Peter Todd via bitcoin-dev]

# Motivation

UTXO growth is a serious concern for Bitcoin's long-term decentralization. To
run a competitive mining operation potentially the entire UTXO set must be in
RAM to achieve competitive latency; your larger, more centralized, competitors
will have the UTXO set in RAM. Mining is a zero-sum game, so the extra latency
of not doing so if they do directly impacts your profit margin. Secondly,
having possession of the UTXO set is one of the minimum requirements to run a
full node; the larger the set the harder it is to run a full node.

Currently the maximum size of the UTXO set is unbounded as there is no
consensus rule that limits growth, other than the block-size limit itself; as
of writing the UTXO set is 1.3GB in the on-disk, compressed serialization,
which expands to significantly more in memory. UTXO growth is driven by a
number of factors, including the fact that there is little incentive to merge
inputs, lost coins, dust outputs that can't be economically spent, and
non-btc-value-transfer "blockchain" use-cases such as anti-replay oracles and
timestamping.

We don't have good tools to combat UTXO growth. Segregated Witness proposes to
give witness space a 75% discount, in part of make reducing the UTXO set size
by spending txouts cheaper. While this may change wallets to more often spend
dust, it's hard to imagine an incentive sufficiently strong to discourage most,
let alone all, UTXO growing behavior.

For example, timestamping applications often create unspendable outputs due to
ease of implementation, and because doing so is an easy way to make sure that
the data required to reconstruct the timestamp proof won't get lost - all
Bitcoin full nodes are forced to keep a copy of it. Similarly anti-replay
use-cases like using the UTXO set for key rotation piggyback on the uniquely
strong security and decentralization guarantee that Bitcoin provides; it's very
difficult - perhaps impossible - to provide these applications with
alternatives that are equally secure. These non-btc-value-transfer use-cases
can often afford to pay far higher fees per UTXO created than competing
btc-value-transfer use-cases; many users could afford to spend $50 to register
a new PGP key, yet would rather not spend $50 in fees to create a standard two
output transaction. Effective techniques to resist miner censorship exist, so
without resorting to whitelists blocking non-btc-value-transfer use-cases as
"spam" is not a long-term, incentive compatible, solution.

A hard upper limit on UTXO set size could create a more level playing field in
the form of fixed minimum requirements to run a performant Bitcoin node, and
make the issue of UTXO "spam" less important. However, making any coins
unspendable, regardless of age or value, is a politically untenable economic
change.


# TXO Commitments

A merkle tree committing to the state of all transaction outputs, both spent
and unspent, we can provide a method of compactly proving the current state of
an output. This lets us "archive" less frequently accessed parts of the UTXO
set, allowing full nodes to discard the associated data, still providing a
mechanism to spend those archived outputs by proving to those nodes that the
outputs are in fact unspent.

Specifically TXO commitments proposes a Merkle Mountain Range¹ (MMR), a
type of deterministic, indexable, insertion ordered merkle tree, which allows
new items to be cheaply appended to the tree with minimal storage requirements,
just log2(n) "mountain tips". Once an output is added to the TXO MMR it is
never removed; if an output is spent its status is updated in place. Both the
state of a specific item in the MMR, as well the validity of changes to items
in the MMR, can be proven with log2(n) sized proofs consisting of a merkle path
to the tip of the tree.

At an extreme, with TXO commitments we could even have no UTXO set at all,
entirely eliminating the UTXO growth problem. Transactions would simply be
accompanied by TXO commitment proofs showing that the outputs they wanted to
spend were still unspent; nodes could update the state of the TXO MMR purely
from TXO commitment proofs. However, the log2(n) bandwidth overhead per txin is
substantial, so a more realistic implementation is be to have a UTXO cache for
recent transactions, with TXO commitments acting as a alternate for the (rare)
event that an old txout needs to be spent.

Proofs can be generated and added to transactions without the involvement of
the signers, even after the fact; there's no need for the proof itself to
signed and the proof is not part of the transaction hash. Anyone with access to
TXO MMR data can (re)generate missing proofs, so minimal, if any, changes are
required to wallet software to make use of TXO commitments.


## Delayed Commitments

TXO commitments aren't a new idea - the author proposed them years ago in
response to UTXO commitments. However it's critical for small miners' orphan
rates that block validation be fast, and so far it has pro