<div dir="ltr">
<p class="gmail-p1"><span class="gmail-s1">This kind of thing is long overdue!</span></p>
<p class="gmail-p2">I think it’s a great idea to attempt this without soft forking TXO commitments yet so we can see what works best.</p><p class="gmail-p2"><br></p>
<p class="gmail-p1"><span class="gmail-s1">- E</span></p></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Feb 22, 2017 at 5:11 PM, Peter Todd via bitcoin-dev <span dir="ltr"><<a href="mailto:bitcoin-dev@lists.linuxfoundation.org" target="_blank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Something I've recently realised is that TXO commitments do not need to be<br>
implemented as a consensus protocol change to be useful. All the benefits they<br>
provide to full nodes with regard to allowing for old UTXO data to be pruned -<br>
and thus solving the UTXO bloat problem - can be implemented even without<br>
having miners commit to the TXO commitment itself. This has a significant<br>
deployment advantage too: we can try out multiple TXO commitment schemes, in<br>
production, without the need for consensus changes.<br>
<br>
<br>
# Reasoning<br>
<br>
1) Like any other merkelized data structure, a TXO commitment allows a data set<br>
- the TXO set - to be securely provided by an untrusted third party, allowing<br>
the data itself to be discarded. So if you have a valid TXO commitment, you can<br>
discard the TXO data itself, and rely on untrusted entities to provide you that<br>
data on demand.<br>
<br>
2) The TXO set is a super-set of the UTXO set; all data in the UTXO set is also<br>
present in the TXO set. Thus a TXO commitment with spent TXO's pruned is<br>
equivalent to a UTXO set, doubly so if inner nodes in the commitment tree<br>
commit to the sum-unspent of their children.<br>
<br>
3) Where a outpoint-indexed UTXO set has a uniform access pattern, an<br>
insertion-ordered TXO set has a delibrately *non-uniform* access pattern: not<br>
only are new entries to the TXO set always appended to the end - an operation<br>
that requires a known, log2(n), sized set of merkle tips - but due to lost<br>
coins alone we can guarantee that older entries in the TXO set will be less<br>
frequently updated than newer entries.<br>
<br>
4) Thus a full node that doesn't have enough local storage to maintain the full<br>
UTXO set can instead keep track of a TXO commitment, and prune older UTXO's<br>
from it that are unlikely to be spent. In the event those UTXO's are spent,<br>
transactions and blocks spending them can trustlessly provide the necessary<br>
data to temporarily fill-in the node's local TXO set database, allowing the<br>
next commitment to be calculated.<br>
<br>
5) By *not* committing the TXO commitment in the block itself, we obsolete my<br>
concept of delayed TXO commitments: you don't need to have calculated the TXO<br>
commitment digest to validate a block anyway!<br>
<br>
<br>
# Deployment Plan<br>
<br>
1) Implement a TXO commitment scheme with the ability to efficiently store the<br>
last n versions of the commitment state for the purpose of reorgs (a<br>
reference-counted scheme naturally does this).<br>
<br>
2) Add P2P support for advertising to peers what parts of the TXO set you've<br>
pruned.<br>
<br>
3) Add P2P support to produce, consume, and update TXO unspentness proofs as<br>
part of transaction and block relaying.<br>
<br>
4) Profit.<br>
<br>
<br>
# Bootstrapping New Nodes<br>
<br>
With a TXO commitment scheme implemented, it's also possible to produce<br>
serialized UTXO snapshots for bootstrapping new nodes. Equally, it's obviously<br>
possible to distribute those snapshots, and have people you trust attest to the<br>
validity of those snapshots.<br>
<br>
I argue that a snapshot with an attestation from known individuals that you<br>
trust is a *better* security model than having miners attest to validity: the<br>
latter is trusting an unknown set of unaccountable, anonymous, miners.<br>
<br>
This security model is not unlike the recently implemented -assumevalid<br>
scheme(1), in that auditing the validity of the assumed valid TXO commitments<br>
is something anyone can do provided they have a full node. Similarly, we could<br>
ship Bitcoin nodes with an assumed-valid TXO commitment, and have those nodes<br>
fill in the UTXO data from their peers.<br>
<br>
However it is a weaker security model, in that a false TXO commitment can more<br>
easily be used to trick a node into accepting invalid transactions/blocks;<br>
assumed valid blocks requires proof-of-work to pull off this attack. A<br>
compromise may be to use assumed valid TXO commitments, extending my partial<br>
UTXO set(2) suggestion of having nodes validate the chain backwards, to<br>
eventually validate 100% of the chain.<br>
<br>
<br>
# References<br>
<br>
1) <a href="https://github.com/bitcoin/bitcoin/pull/9484" rel="noreferrer" target="_blank">https://github.com/bitcoin/<wbr>bitcoin/pull/9484</a><br>
2) [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework),<br>
Peter Todd, Jul 17th 2013, Bitcoin development mailing list,<br>
<a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-July/002917.html" rel="noreferrer" target="_blank">https://lists.linuxfoundation.<wbr>org/pipermail/bitcoin-dev/<wbr>2013-July/002917.html</a><br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
<a href="https://petertodd.org" rel="noreferrer" target="_blank">https://petertodd.org</a> 'peter'[:-1]@<a href="http://petertodd.org" rel="noreferrer" target="_blank">petertodd.org</a><br>
</font></span><br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href="mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.<wbr>linuxfoundation.org</a><br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.<wbr>org/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div><br></div>