Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.
Sign up to join this community
to validate a TX, the miner or full node should first find the UTXO. How long does it take to find a specific UTXO in a list of UTXOs set?
Right now, there are around 100 million of UTXOs. Then, how long does it take to find a specific UTXO among 100 million UTXOs? I need to know the accurate time.
It is impossible to answer this accurately without knowing details such as the hardware the miner is using, their utxo storage method, and their validation process.
However, in general, the utxo set can be stored as a list keyed by the utxo identifier (txid:vout). This provides O(1), or constant, look up complexity for a single utxo.
However, the utxo set may not fit entirely in memory on many systems, and the actual retrieval time may be longer than you'd expect in an ideal scenario after accounting for disk access time, and other implementation specific details.
In a miner's case, they validate incoming transactions and prepare a block template by feerate asynchronously from the actual mining operation - this allows them to have a reasonably good chance of maximising their earnings per block without having the mining process blocked by tx and block validation systems.
