He'd need to list all input transactions from blocks N... N+3 as a source of funds. This will allow the network to verify the transaction without having to do a search.
Thanks, I think I'm starting to understand a little better. I was getting confused and thinking that transactions transfer an amount from one bitcoin address to another.
What transactions really seem to do is simply to name outputs from other transactions as inputs to this transaction, provide 'script' which when combined with the output script of those transactions evaluates to true, thus proving the right to 'claim' the entire set of funds declared in the output, and then set up a new set of outputs with script that would then be combined with the next transaction to set up another such sequence.
So there is no 'adding bitcoins to a bitcoin address', there is only 'rewriting a set of old outputs with a new set of outputs' with the inputs used as a mechanism to identify, and provide proof of the claim to, the old outputs.
And so to verify a transaction, a miner just needs to verify that the inputs properly claim outputs of a transactions which themselves were validated, never needing to go further back than the transactions directly referenced by a new transaction.
What I don't understand is how do they know which transaction is in which block. Do they build a mega map of all transaction-to-block relationships and look that up? This would grow like mad.
Seems like they must, doesn't it? But I guess they can also forget about individual transaction outputs once they have been claimed and then can forget the whole transaction once all of its outputs have been claimed, since no valid transaction can ever reference those outputs again.
Seems as the number of transactions grows the cost of looking up the validity would become more than the cost to compute the hash. Maybe there would be separate parts of the network responsible for each task and they would split the transaction fees.
Yeah having to keep track of every unclaimed transaction output for all perpetuity sounds very hard when there are significant numbers of unclaimed transactions.
And having to swallow the feed of transactions (both unverified, and verified within blocks) when there are hundreds of transactions per second sounds even harder.