Range proof batch verification failure uses linear search
Closed this issue · 3 comments
When verifying a batch of range proofs, failure results in a subsequent linear search to identify an offending proof, where the verifier proceeds to verify each proof in the batch on its own until it identifies a failure.
There are two issues that arise. First, an attacker who can influence batch ordering can place an invalid proof at the end of the batch to maximize the number of verifications that must be performed, which serves as a denial of service. Second, even under non-adversarial conditions with a single invalid proof in the batch, the verifier will have to check half the proofs on average to find this proof.
One approach that is straightforward is to use a binary search instead of a linear search. Even under adversarial conditions, the computational effort required to identify an offending proof becomes logarithmic.
Work is ongoing to add both a complete linear search (which identifies all invalid proofs) and logarithmic binary search (which identifies a single invalid proof) to either tari-crypto or the range proof library.
After speaking with @CjS77 about this, a few thoughts and ideas came up.
This problem depends heavily on the situation. For block production where proofs come from the mempool, some are likely to be invalid: a small number for a malfunctioning honest user, but possibly a large number in an attack scenario. For block verification where proofs come from the chain, none should be invalid.
The problem also depends on how the caller needs to handle a failure. If a block producer identifies a failure in batch verification, it likely wishes to identify all invalid proofs so it can remove them in one fell swoop. If a block verifier identifies a failure, it merely needs to discard the block, perhaps identifying a single invalid proof for debugging or informational purposes.
This suggests an initial strategy. During block production, use a complete linear search on batch failure. During block verification, use a binary search on batch failure.
However, @CjS77 brought up the idea of a heuristic that attempts to identify when the mempool may be under attack. The block producer could initially use a binary search to quickly identify individual invalid proofs, but switch to a complete linear search on too many failures. The optimal number would depend on the batch size and other factors. Initial shuffling of batch data could be another step that, depending on complexity, could help thwart an attacker who attempts to influence batch ordering to "optimize" its denial-of-service attack.
Why not just error and not determine the offending output? For blocks, it's only for debugging to determine the offending output, for block construction the outputs should be determined before hitting the mempool.
It's certainly possible to do this, but was suggested during discussion that being able to report at least some failure information during block verification could be useful if it's unlikely to occur often and doesn't incur significant overhead.
For block construction, isn't it inherent that you need to identify all failed proofs in order to discard them? In this case, you either need a complete linear search or the heuristic approach.