This is largely a summary of a series of insights and ideas around parallel validation that were discussed at the 2140 Bitcoin Consensus Code Week. This involved participants who work on Bitcoin Core, Libbitcoin, Floresta, BTCD, and various others.
It's well-known that in order to maximize your hardware resources, software generally should try to minimize ordering constraints. The more you can do in parallel, the better you can utilize your hardware without waiting on prior things to finish. This write-up maps out the areas where we can apply this to Bitcoin and what tradeoffs it entails. Most of this is not new and summarizes community knowledge, though one small novel component is how you can parallelize double spend validation with a single spend check.
First, let's describe the ordered components of validation.
Blocks are valid if all its previous blocks are valid as well as all transactions contained within.
Transactions are valid if all inputs have a pre-existing output and the combined output + input script is valid.
Input scripts generally contain signatures, which require a hash over the transaction itself, all previous outputs in the transaction, and their amounts.
Therefore, to validate an arbitrary input, you need:
- The corresponding previous output script (which must be present at a prior point in the chain - more on this later)
- The signature hash, which requires:
- The full transaction
- All remaining previous outputs in the transaction
- All amounts
In practice, this means validation of an arbitrary input cannot be completed until all components are present that allow for the full validation of the entire transaction.
Order-wise, the transaction can be validated as soon as all the blocks containing the previous outputs are in. Rather than dealing with the complexity of figuring out when the previous outputs are present, in practice it suffices to simply start validating when all previous blocks are present without meaningfully impacting validation speed1.
Having an ordered set of blocks also has a lot of practical benefits, such as scanning for payments with a gap limit that is affected by what you found in prior blocks2, or keeping a cache of recent outputs in memory3 so they don't need to be fetched from disk.
If you separate the signature check from the rest of the script check, you can also technically start the script check (sans sig check) as soon as the previous output of any arbitrary input is available, but again, the added complexity of figuring out when you have all relevant scripts adds virtually no meaningful benefit. That said, separating out the signature checks does make sense for the purposes of e.g. batch or GPU validation.
General block integrity checks can be done as soon as a block arrives, regardless of order.
- Download and check all proof-of-work headers
- Attempt to download all blocks in order, within a moving window
- Check every incoming block for integrity and add its outputs to a set
- Once a sequence of blocks is in that connects to genesis, validate all transactions in any order by fetching the previous outputs
This takes care of everything except double spends.
The main issue we run into here is that double spending has some ordering constraints. If two blocks spend the same output, the block that came first is still valid. This means that not only must we a.) detect if a double spend occurred, but we must also b.) determine the order in which it happened. To what degree can we do this without falling back to ordered validation?
One observation is that the order only matters if a double spend did indeed occur, which is exceedingly rare and costly, given that it involves proof-of-work. It can therefore be a reasonable tradeoff to optimize for the former rather than the latter. We can take advantage of this as follows.
Imagine we had a single bit for every output, indicating spentness. We ignore order, don't bother reading the bit, and just mark it as spent when we spend an output. This means the bit indicates spentness, but not whether the output was spent more than once. Interestingly, we can rule out double spends at any point by checking if the total number of flipped bits indicating spentness matches the total number of inputs we processed4. If it doesn't match, it means an output was spent more than once. The downside of this approach is that if a double spend does occur, it's harder to figure out exactly where5.
The approach we just outlined permits any operation to take place in any order and without requiring exclusive access to outputs (wait-free). While it's a very elegant approach, on conventional hardware there are perfectly reasonable ways to deal with gaining exclusive access to elements without locking the entire set6, so it's not obvious whether non-exclusive access makes a practical difference. Furthermore, if you want to prune spent outputs (better on memory constrained hardware) it gets harder to maintain the benefits.
SwiftSync achieves perfect parallelization, is elegant to implement, and requires practically no memory to function, but has two key tradeoffs:
- ~5% more data is needed ( ~2% with ~100 block cache in memory)
- A trusted source needs to attest to the validity of the extra data to prevent DoS issues
I consider these tradeoffs very mild7, but what can't be denied is that if you're bottlenecked by bandwidth, the additional data slows you down.
Footnotes
-
Validation speed: Simply put, validation will either be bottlenecked by bandwidth or hardware constraints. If you are bottlenecked by bandwidth, waiting for a set of blocks before starting validation won't have a meaningful impact, because your hardware will always catch up to the point where it's waiting on bandwidth again. And if you're not constrained by bandwidth, there will always be enough blocks available for your hardware to validate. From this we can conclude that enforcing some order on block downloads will not meaningfully impact validation speed. ↩
-
Gap limit: To clarify, the issue is that you check for incoming payments within a limited window (the gap limit) that expands whenever a payment is found. For instance, you might check for 100 addresses, but once you find a payment on the first address, you increase the limit and now start looking for 101 addresses, etc. This makes your search window dependent on what was found in prior blocks, which imposes an order of operations. ↩
-
Output caching: The obvious thing to do (which is generally not counted as caching) is to process same-block spends, which already accounts for roughly one third of all outputs. After that, we can account for another 9/31/66/83% with a 1/6/144/2016 in-memory block cache. Source: mainnet-observer. ↩
-
UTXO counting: While we described the single spend check as an input count in the context of this write-up, it can equally apply to the UTXO set by checking if the number of unflipped bits matches the total number of outputs minus the number of inputs we processed. This is relevant for any implementation wishing to remove spent elements from the set (i.e., converging on a UTXO set). ↩
-
Tracking double spends: Under the single spend check model, locating where a double spend occurs is more involved. Instead of a flipping a bit for every spend, we could write the height at which the output was spent and read it back again after writing. If it changed to some other value, you know a double spend occurred, and at which height. Alternatively, we could do the single spend check periodically during validation and do another pass to find the double spend if it occurred. ↩
-
Atomicity: While this is not my area of expertise, in general you can use atomic compare-and-swap (CAS) instructions to ensure an element you're operating on in a map is accessed exclusively without race conditions. While this results in being lock-free rather than wait-free, in practice this is generally fine. ↩
-
The SwiftSync trust tradeoff: This is sometimes mistaken for being equivalent to assumevalid - it is not. An unreliable party can merely waste your time at the cost of their reputation, so in practice this is unlikely to be an issue. They can't get you to accept an incorrect state. More generally, Bitcoin can be described as a protocol where party A tries to convince party B to accept their BTC payment. Therefore, A is incentivized to help B complete validation. Finally, the ~2% (with caching) bandwidth overhead is very minor compared to all the benefits SwiftSync brings. ↩