Searching through the blockchain When a miner includes a transaction in a block, according to the integrity rules the miner should search for a previous transaction which output the coins being used in the current transaction. Now, the previous transaction is a record stored somewhere deep inside the blockchain.

What is the time taken to search and validate the previous txn output in the blockchain data structure?
If the block is released by mining pool or miner, each peer running bitcoin wallet such as bitcoin-qt or bitcoind will verify the transactions in the block before relaying the block.

The steps are following:


Verify SHA256 block hash which is structured from version, pref_block,merkle_root,timestamp, bits, nonce and standard SHA256 padding. When the block hash is invalid or minimum difficulty level it is rejected.


The pools or miners are supposed to release blocks according to these protocol rules

One of them:


  For each input, look in the main branch and the transaction pool to find the referenced output transaction. If the output transaction is missing for any input, this will be an orphan transaction. Add to the orphan transactions, if a matching transaction is not in there already.


So there are multiple rules that must be followed for a block to get accepted and then relayed.