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

[jamesd at echeque.com]

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.