BUIP033: Parallel Validation
Proposer: Peter Tschipper
Submitted: 2016-10-22
Status: passed

’'Summary:*

Essentially Parallel Validation is a simple concept. Rather than
validating each block within the main processing thread, we instead
create a separate thread to do the block validation. If more than one
block arrives to be processed then we create yet another thread. There
are currently up to 4 parallel block processing threads available making
a big block DDOS attack impossible. Furthermore, if any attacker were
somehow able to jam all 4 processing threads and another block arrived,
then the processing for the largest block would be interrupted allowing
the smaller block to proceed, unless the larger block or blocks have
most proof of work. So only the most proof of work and smallest blocks
will be allowed to finish in such
as case.

If there are multiple blocks processing at the same time, when one of
the blocks wins the race to complete, then the other threads of
processing are interrupted and the winner will be able to update the
UTXO and advance the chain tip. Although the other blocks that were
interrupted will still be stored on disk in the event of a re-org.

Design:

The following describes the internal mechanisms used to achieve parallel
validation.

2a) Script Check Queues: A total of four script check queues are created
with their own thread group which are used to validated signatures. Each
new block that arrives will be assigned one of those queues during the
validation process.

2b) Semaphores: There are two semaphores for managing block validations
which are sized at 4, for new blocks, and 32 for IBD. Although there are
only 4 script queues available we still allow 32 IBD threads to run
concurrently since that gives the main processing thread a chance to
retrieve other blocks while the current ones complete their
validation.

2c) Locking: The parallel processing is made possible by first having
separate threads for validation, but then largely by managing the
internal locks of `cs_main` in the `ConnectBlock()` function which
is found in the `src/main.cpp` source file. During the process of
`CheckInputs()` we do not have to maintain the lock on `cs_main`
which allows other competing threads to continue their own validation;
the reason for this is that each thread of validation uses it’s own view
of the UTXO and the scriptcheckqueue’s have their own internal locking
mechanism. Furthermore when it comes time to wait for the script threads
to finish we also do not need to maintain the `cs_main` locks during
the `control.Wait()`.

Although this unlocking and locking of `cs_main` causes some overhead
it is not invoked during the mining process but only when we receive a
new block from an external source which needs validation. It is designed
primarily to prevent the big block DDOS attack from jamming the main
processing thread.

2d) Interrupts: If multiple blocks are competing to win the validation
race or if all 4 script queues are in use and another new block arrives
there are several ways we use to stop one or all of the other competing
threads. We do this by first sending a message to quit the script
threads which prevents them from completing their verification, followed
by issuing a standard thread interrupt. Also, if one block has finished
and has advanced the tip, the other concurrent threads will see that the
tip has advanced and will exit their validation threads.

2e) Temp view cache: Each processing thread has it’s own temporary view
of the UTXO which it can used to pre-validate the inputs and ensure that
the block is valid (as each input is checked the UTXO must be updated
before the next input can be checked because many times the current
input depends on some previous input in the same block). When and If a
processing thread wins the validation race it will flush it’s
temporary and now updated view of the UTXO to the base view which then
updates the UTXO on disk. This is key to having several threads of
validation running concurrently, since we can not have multiple threads
all updating the same UTXO base view at the same time.

2f) nSequenceId: In order to have the correct `pindexMostWork` we must
update the `nSequenceId` an additional time after the winning block
updates the `UTXO` and advances the chain tip. We can not only rely
only on the `pindexMostWork` returned from the
`CBlockIndexWorkComparator()` as was previously the case. That is
because pindexMostWork returned from the comparator may not necessarily
point to the winning block. So what we have to do is swap the
`nSequenceId` between the winning and losing blocks such that the
winning block has the lowest nSequenceId and the losing blocks
nSequenceId’s are bumped up one while at the same time keeping their
relative ordering.

*IBD and new blocks:’’

Parallel Validation is only in effect when new blocks arrive. In other
words, the `fIsChainNearlySyncd` flag must be true indicating that IBD
has been completed.

Although parallel validation is not in operation during IBD, the blocks
arriving that need validating will get processed in a separate thread.
This helps to free up the main processing thread and allows requests for
more blocks to be made while the other threads continue to be
processed.

How is mining affected:

Mining is not affected by Parallel Validation. When new blocks are
created locally they bypass parallel validation. In other words, the
`cs_main` locks are not unlocked and then locked repeatedly, allowing
the validation process to be completed as quickly as possible. Whether
parallel validation is invoked or not depends on the boolean
`fParallel`. When set to `true` then parallel validation is in
effect, and when `false` , as in the case of generating a new block,
then it is turned off.

NOTE: Miners will still use parallel validation if a block arrives from
an external source. It is only turned off when validating a block they
mine themselves.