Double Spending - Does each node maintain a list of unspent transaction references?

Question

My Understanding Of How Bitcoin Prevents Double Spending

Each transaction contains references to the input transactions and ever node has to verify all transactions from time immemorial to ensure that the inputs are in fact unspent. Once this is confirmed, and subject to other conditions, the transaction can be added to the block chain.

I can not fathom the practicality of what this means, lets say there have already been 50 million transactions on bit coin, for the transaction after the 50 millionth, each input transaction reference will have been looked against 50 million rows to see if it appears anywhere as an input transactions (it shouldn't) and it was in fact an output transaction then benefiting the now spender. This is done for all transactions being broadcast in an interval of time before miners can start working for that good looking cipher.

However to make this simple, each nodes maintains a list of unspent transaction references of all nodes (say U list), when is used as a starting point and updated every time a transaction is added and these updates are committed across the network after a transaction block is confirmed giving the starting point of the next block.

My Questions

Sounds too much hard work for this to be practical.

1. Does it mean that every miner will have a database of those 50 million records? Isn't that a massive and expensive requirement?

2. Every miner will compare each input transaction references to each of those 50 million before including the new transaction in a block to ensure that it has not been spent already and was in fact valid?

3. Quoting myself,

   however to make this simple, each nodes maintains a list of unspent transaction references of all nodes (say U list), when is used as a starting point and updated every time a transaction is added and these updates are committed across the network after a transaction block is confirmed giving the starting point of the next block

   Doesn't this go against the principle of not having a book showing each node's balance? In case a node has only 2, 3, 5, or 5000 unspent input transaction references. This more or less boils down to a book of balances that needs to be referred to for each transaction before block inclusion and the new block is committed over it on confirmation (i.e. when a proof of work is found). Does it not?

4. Given the above post, how close am I to understanding controls over double spending? I am a CPA trying to get my head around this.

Preliminary Doubt

Only miners need bother about assembling transactions in blocks. Shoppers and Payers may execute transactions and simply await block confirmation. All transactions shall be broadcast to them and they need not bother recording those unless they are involved or a block confirmation is broadcast.

Answer 1

Each full node must maintain a list of all unspent outputs. Currently there are 15 million unspent outputs with a total size of 525 MB. To check whether a new transaction is a double-spend, Bitcoin sees whether the outputs being spent are in this unspent transaction output (UTXO) database. If they are, the new transaction is not a double-spend, and if the transaction meets the other validity requirements, the spent outputs will be removed from the UTXO database.

Searching for a transaction in the UTXO database is extremely fast because the outputs are ordered by transaction hash, so searching can be done using binary search. That means that even though there are more than 15 million UTXOs, finding a particular UTXO given its transaction hash requires looking at only ~24 database locations in the worst case, which a computer can do very quickly.

This is complicated somewhat by the fact that transactions can rarely become invalid after initially being valid (after a reorganization), so full nodes must be able to roll back at least the last few weeks of changes to the UTXO database. Bitcoin Core implements this by keeping a log of each change to the UTXO database and reversing each change in the log in reverse order when a rollback is necessary.

Every full node does have enough information to compute the current balance of any address, though Bitcoin never actually deals in balances directly.

Answer 2

1) Does it mean that every miner will have a database of those 50 million records ???!!!

No need to keep in database all 50 millions. Node keeps in database only unspent yet outputs.

2) Every miner will compare each input transaction references to each of those 50 million before

This is very simple operation. No need to compare with all records, but search in sorted array.