How does a miner verify that a UTXO is not spent somewhere else, wouldn't he have to search the entire blockchain from that UTXO and onwards to see if this was the case? Assuming any real scale this would effectively take ages, or am I misunderstanding something?
A miner does so by checking if the
UTXOs that new transactions are trying to spend are in the
UTXO set is the collection of
UTXOs that are non-spent, and therefore, can be redeemed by new transactions.
To do so, a miner (as well as any other node) checks the LevelDB database found in
.bitcoin/chainstate by default in unix systems.
UTXOs are identified by its
txid (Little Endian representation) leaded by a
In the answer for this question you can find an extensive explanation of the format in which the UTXOs are stored, with some examples.
All full nodes process the complete blockchain. While processing, they keep a record of all Unspent Transaction Outputs in the
UTXO set. For each transaction of each block the relevant changes to the
UTXO set are applied: all
UTXOs that get spent are removed and all transaction outputs are added as new
Thus, when a node has synchronized completely to the current blockchain tip, to verify whether the inputs of a transaction are spendable, they just check if for each input there is a corresponding
UTXO is in their
UTXO set. If there isn't, the
UTXO was either spent already, or never existed.
UTXOs are unique and only can be spent once and in full. They are identified by the (unique)
txid of the transaction that created the
UTXO and the
v_out, i.e. the position of the output in the transaction's output list.