<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jan 22, 2019 at 5:36 PM <<a href="mailto:jamesd@echeque.com">jamesd@echeque.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">A new transaction is proposed.  How does the validator figure out if one <br>
of the transaction outputs has already been used?<br>
<br>
The blockchain is heading towards a terabyte.  So you cannot search the <br>
entire blockchain to make sure a particular transaction output has never <br>
been used.<br>
<br>
You are going to need a big mutable list of transaction outputs sorted <br>
by index order, a great big pile of mutable state, derived from the <br>
immutable transactions on the blockchain. I suppose that each entity <br>
maintaining a copy of the blockchain generates the mutable state by <br>
going through the very long list of immutable transactions. And because <br>
it is mutable, someone could get it wrong, by malice, fraud, or hardware <br>
error.<br>
<br>
Each peer on the blockchain has to go through the immutable pile of <br>
transactions, starting from the beginning, to generate the current <br>
mutable state.<br>
<br>
How do the peers know they all have the same mutable state?  Do they <br>
have a checksum for the mutable state at block X?  Is there a global and <br>
canonical lookup mechanism for the mutable state that is a defined part <br>
of the protocol, or could each peer implement its own custom <br>
idiosyncratic magic mechanism?<br>
<br>
What you would probably like to do, though as far as I know it has not <br>
been done, is make an immutable record of all currently unused <br>
transaction outputs at certain blocks, which would make it possible to <br>
throw away earlier blocks, an immutable snapshot of the mutable data <br>
generated from the immutable transactions.<br></blockquote><div> </div>Figuring out an efficient way to store the UTXO set or check if a given TXO is unspent has been a topic of discussion for several years. A variety of ideas have been debated, from miner commitments in blocks to the latest and greatest "utreexo"<br><br>Some light reading:<br><div><br></div><div><a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-October/011638.html" target="_blank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-October/011638.html</a><br></div><div><br></div><div><a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html" target="_blank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html</a><br></div><div><br></div><div><a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/012758.html" target="_blank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/012758.html</a><br></div><div><br></div><div><a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-March/013928.html" target="_blank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-March/013928.html</a><br></div><div><br></div><div><a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html" target="_blank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html</a><br></div><div><br></div><div><a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/015967.html" target="_blank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/015967.html</a><br></div><div><br></div><div><a href="https://dci.mit.edu/research/2019/1/15/coindesks-this-scaling-tech-could-let-you-sync-bitcoin-straight-from-your-phone-using-utreexo-created-by-tadge-dryja" target="_blank">https://dci.mit.edu/research/2019/1/15/coindesks-this-scaling-tech-could-let-you-sync-bitcoin-straight-from-your-phone-using-utreexo-created-by-tadge-dryja</a> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
_______________________________________________<br>
The cryptography mailing list<br>
<a href="mailto:cryptography@metzdowd.com" target="_blank">cryptography@metzdowd.com</a><br>
<a href="http://www.metzdowd.com/mailman/listinfo/cryptography" rel="noreferrer" target="_blank">http://www.metzdowd.com/mailman/listinfo/cryptography</a></blockquote></div></div>