block verification cost

Question

When a node receives a block, is it enough to validate root of Merkel tree ? How does block size affect the validation cost? What is the difference between the cost of validation 1mg-size block and 2mg-size block? Its variations are linear or constant or quadratic? Tnx.

Answer 1

It is not enough to check the merkle tree, as this says absolutely nothing about the validity of the contents of the block, just that somebody was able to follow the protocol up until that point. If a transaction say, created money out of nowhere, this would not be caught by simply looking at the existence of a transaction in a block.

To correctly validate a block a node must do the following low-cost checks:

• format of the header is correct
• rules about timestamps and difficulty are followed
• the proof of work matches what is required

Assuming these rules pass, they must do the following high-cost checks:

• the merkle tree is correct and matches the root in the header
• no outputs are spent which do not exist (or have already been spent)
• the values in every transaction input and output don't create money
• that every script execution is successful and does not end in an error
• that every ECDSA signature is valid
• that misc rules such as size, format of script, and total block size are not exceeded

Most of these are CPU intensive, such as doing potentially hundreds of thousands of ECDSA, SHA256, and RIPME160 operations. Some are IO intensive, such as validating previous transaction entries if these are not already in the cache. None of these operations are exponential in cost with the number of transactions, but they need to be completed quickly to maintain consensus on the network.

Much of this work can be done ahead of time, an unconfirmed transaction can have many checks against it done, so when it arrives confirmed inside a block the validation is cached. However we can't assume this is always the case, as the Bitcoin network needs to be able to operate in adversarial conditions, such as a miner creating a block with a large number of otherwise unseen transactions.

We also need to consider that every block needs to be validated by nodes which are newly joining the network, and the cumulative cost should not be excessive to process. The historical chain at this point takes many hours or even days to validate on low-cost hardware, and we of course shouldn't be changing behavior in such a way that this cost grows more quickly.

That said, the Bitcoin network frequently has blocks above 1MB today, often exceeding 2.2MB.