Can you post "typical" case benchmark comparisons?

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #14400 (Add Benchmark to test input de-duplication worst case by JeremyRubin)
• #14397 (Faster duplicate input check in CheckTransaction (alternative to Faster Input Deduplication Algorithm #14387) by sipa)
• #14074 (Use std::unordered_set instead of set in blockfilter interface by jimpo)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

@JeremyRubin Impressive speedup! What is the risk-reward trade-off we're facing with this change? More specifically: what risks do you see associated with this change to consensus critical code?

Does the change in which DoS error gets reported for transactions which have both duplicates and null inputs have any consequences or impose any risks?

Anyone measured -reindex with and without this change?

My immediate reaction is that this seems very complex compared to a naive std::set comparison! This also pulls our SipHash implementation into consensus-critical code, which seems like a big price to pay for a performance win. I lean pretty strongly towards concept NACK.

@JeremyRubin - your PR description talks about what this PR does, but not why. This makes block propagation faster, but do we have an understanding of how much these milliseconds matter? Is there a way we can determine whether the increased complexity introduced is a reasonable price to pay for the performance win?

Also, +1 to @MarcoFalke's comment here: #14387 (comment) . Can reviewers please not start nitting code before there's been a concept discussion.

Goal was to minimize the performance regression caused by the CVE fix. Understand this is sensitive code for that reason. This code is also generally theoretically useful for several other contexts because it is O(N). An adapted version (different parameters) could be used to check for duplicate inputs across a large number of txns (e.g., mempool syncing context).

It's actually not thaaat complicated; it's basically just a bloom filter. The complexity is also mostly in the performance, the correctness is somewhat easy to check.

I don't know if the performance win is worth it. I'll leave that for others to determine. Just putting it out there.

@JeremyRubin It is sufficiently complicated to introduce undefined behaviour in consensus critical code without any of the reviewers noticing .-)

I'm afraid the code as it is currently formulated will trigger undefined behaviour due to shift exponents being too large.

@practicalswift i think I fixed that -- can you confirm? (and also a copy-paste error on which bit was being set :( )

@practicalswift No, I'm afraid the undefined behaviour is still present.

Check this code:

https://github.com/bitcoin/bitcoin/blob/4ec7597add35cfc458680fcba2b8fb64931711ef/src/consensus/tx_verify.cpp#L281-L288

I feel like this is too much review work vs the gain.

@gmaxwell @sipa please re-review the updated version (should you have time). @practicalswift I think I have eliminated the UB, if not please let me know.

In this version I have kept complexity limited in scope to validation.cpp.

Performance wise this version is actually a bit better in the worst case compared to using the filter per-transaction (DuplicateInputs) and better in an average case (DeserializeAndCheckBlockTest) compared to master.

The simpler put all in vector then sort then find duplicate algorithm could be used here too.

The major benefit of this approach (as amended) is that we not only detect duplicate inputs per transaction, but across the entire block at the same time. This guarantees we won't see an in-block double spend in ConnectBlock and CheckTxInputs. This might enable us to parallelize checking that inputs exist (against a cache that tracks at what index an output created in that block was created).

The major benefit of this approach (as amended) is that we not only detect duplicate inputs per transaction, but across the entire block at the sam

One can't do that without losing the ability to cache the check as part of the wtxid validity caching, as the simpler check could be.

I am failing to see the argument for a gain here that even justifies reviewing the change at all.

@gmaxwell That's not accurate -- by fixing the salt for the hash (which should be safe -- I will consider this more closely), you could store three uint64_t's per input in the wtxid validity cache and then re-insert those on the forward pass of the algorithm. To be clear, this just saves sip-hashing at the expense of memory, but you can just keep a table of precomputed sip-hashes for the inputs in the top of the mempool if it's actually an issue. Once you have the hashes, the check itself is very inexpensive... At the very least, such a cache could be configurable.

By checking (without inserting) that all of the outputs (not txids) created in a transaction are not already in the table as we scan we ensure that none of the inputs spent are created later in the block. This can also be done with an additional backwards pass with a new table only tracking TXIDs for no hashing (for tx in txs.reverse(): insert_table(txid); for input in tx.inputs(): check_table(input.coutpoint.hash)). The overall expected more work on either of these approaches is around 2x, and with current parameters this is reasonable. With this check completed, it would be possible to apply all the transactions in a block out of order. Without removing any checks or adding parallelization, this should make less fragile much of the code after CheckBlock (e.g., ConnectBlock) because we never reach it for a block which has out-of-longchain-order transactions (and cause us to have to abort partially applied transactions).

I wanted to get just the duplicates checking reviewed and accepted first, then, in the future work on these other projects.

@instagibbs with this current version, it seems to minorly worse (1.5% median to median) on DeserializeAndCheckBlockTest. I'm unaware if this is a representative sample of blocks or if this tell you anything about the larger performance of a block being validated with respect to things like number of transactions, caches, etc so I'm reticent to give too much weight to this one in any case. If you have ideas for how we can write a better benchmark to test this for future work, let's chat about it.

DeserializeAndCheckBlockTest, 5, 160, 12.2812, 0.0153002, 0.0154073, 0.0153456
DeserializeAndCheckBlockTest, 5, 160, 12.5319, 0.0153902, 0.0159464, 0.0155924

Much thanks to all the reviewers who have spent their time reviewing this PR so-far, I appreciate that you took the time to review this contribution to Bitcoin.

@jnewbery nothing in this PR is in the block propagation typical case anymore (not since we finally implemented the full BIP152 HB mode forwarding), so the belief that this speeds up block propagation is largely mistaken.

"Goal was to minimize the performance regression caused by the CVE fix." -- there wasn't one, or at least not an interesting one. The speedup to duplicate checking was later superseded by changes to allow blocks to be propagated without validating anything more than hash consistency.

@gmaxwell see #14837 which supersedes this PR.

In my opinion, you are incorrect that CheckBlock is not latency sensitive. Certainly there are a large class of users for whom CheckBlock performance is critical (e.g., miners performing full validation before mining a new block, and miners calling testblockvalidity to get a new template).

This also has a non negligible impact on benchmarks like DeserializeAndCheckBlockTest, which suggests to me that speeding up these checks is important for reindexing, bootstrap, and other activities.

Closing in favour of #14837.

In my opinion, you are incorrect that CheckBlock is not latency sensitive. Certainly there are a large class of users for whom CheckBlock performance is critical (e.g., miners performing full validation before mining a new block, and miners calling testblockvalidity to get a new template).

When it was on the critical path of propagation the small delays involved were cumulative across the whole network. As a result even though one was not particularly interesting, the sum total could be. Without that effect, you only get the single one shot delay. The effect of a one shot half millisecond delay on mining is negligible, and efforts spend considering that optimization could be better spent on things like getting testblockvalidity out of the critical path-- which would be an order of magnitude larger speedup, likely simpler to review and verify, and would also further moot the new proposed benefit.

This also has a non negligible impact on benchmarks like DeserializeAndCheckBlockTest, which suggests to me that speeding up these checks is important for reindexing, bootstrap, and other activities.

That logic is spurious. Microbenchmarks are microbenchmarks. If it had an impact on reindexing/bootstrap it could be measured. If it did make a big impact there that would be an argument in favor of it, but unless prior profiling was erroneous, that isn't possible.

@JeremyRand Regarding my comment regarding UB above. The problem was the following:

uint64_t bit1 = 1<<((std::get<0>(h)) & 63);

... is problematic due to ...

$ cling
[cling]$ #include <cstdint>
[cling]$ 1 << 63
warning: shift count >= width of type [-Wshift-count-overflow]
 1 << 63
   ^  ~~
(int) 0

... which can be contrasted to ...

$ cling
[cling]$ #include <cstdint>
[cling]$ static_cast<uint64_t>(1) << 63
(unsigned long) 9223372036854775808