[Cryptography] How does bitcoin find if a transaction output has already been used.

[Jameson Lopp]

On Tue, Jan 22, 2019 at 5:36 PM <jamesd at echeque.com> wrote:

> A new transaction is proposed.  How does the validator figure out if one
> of the transaction outputs has already been used?
>
> The blockchain is heading towards a terabyte.  So you cannot search the
> entire blockchain to make sure a particular transaction output has never
> been used.
>
> You are going to need a big mutable list of transaction outputs sorted
> by index order, a great big pile of mutable state, derived from the
> immutable transactions on the blockchain. I suppose that each entity
> maintaining a copy of the blockchain generates the mutable state by
> going through the very long list of immutable transactions. And because
> it is mutable, someone could get it wrong, by malice, fraud, or hardware
> error.
>
> Each peer on the blockchain has to go through the immutable pile of
> transactions, starting from the beginning, to generate the current
> mutable state.
>
> How do the peers know they all have the same mutable state?  Do they
> have a checksum for the mutable state at block X?  Is there a global and
> canonical lookup mechanism for the mutable state that is a defined part
> of the protocol, or could each peer implement its own custom
> idiosyncratic magic mechanism?
>
> What you would probably like to do, though as far as I know it has not
> been done, is make an immutable record of all currently unused
> transaction outputs at certain blocks, which would make it possible to
> throw away earlier blocks, an immutable snapshot of the mutable data
> generated from the immutable transactions.
>

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"

Some light reading:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-October/011638.html

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/012758.html

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-March/013928.html

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/015967.html

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


>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190124/77a2c613/attachment.html>