Batch Verification

What Is Batch Verification?

Batch verification is a cryptographic technique that checks whether multiple digital signatures are all valid by combining them into a single mathematical equation. Instead of verifying each signature independently (requiring two costly elliptic curve scalar multiplications per signature), a batch verifier merges all the verification equations and solves them together using algorithms that share computation across the group.

Think of it like a teacher grading multiple-choice exams. Checking each student's answer sheet one by one takes time proportional to the number of students. But if the teacher can overlay all the answer sheets and compare them against a combined answer key in one pass, the total work drops significantly. Batch verification applies a similar principle to signature checking: the verifier combines all the individual checks into one operation, reusing intermediate results.

In Bitcoin, batch verification is specified in BIP 340 as part of the Schnorr signature standard. While individual Schnorr verification is already efficient, batch verification enables nodes to validate entire blocks of Taproot transactions significantly faster, improving initial block download times and block validation during chain reorganizations.

How It Works

To understand batch verification, start with how a single Schnorr signature is verified. Given a public key P, a signature (R, s), and a message m, the verifier checks:

s * G = R + e * P

where e = Hash(R || P || m)  (the challenge hash)
      G = the generator point on secp256k1

This requires two elliptic curve scalar multiplications: one for s * G and one for e * P. Verifying u signatures individually costs 2u scalar multiplications total.

Combining the Equations

Batch verification exploits the fact that Schnorr's verification equation is linear: it uses only point addition and scalar multiplication, with no non-linear operations like modular inverses or coordinate extraction. This means multiple equations can be added together.

For u signatures, the verifier generates random coefficients a_2, a_3, ..., a_u (with a_1 = 1) and checks a single combined equation:

(s_1 + a_2*s_2 + ... + a_u*s_u) * G
  = R_1 + a_2*R_2 + ... + a_u*R_u
  + e_1*P_1 + (a_2*e_2)*P_2 + ... + (a_u*e_u)*P_u

The left side collapses into a single scalar multiplication of the generator point G, because the scalar sum is computed first using cheap modular arithmetic. The right side contains 2u scalar-point pairs, but these are evaluated together as a single multi-scalar multiplication using algorithms like Strauss (for small batches) or Pippenger (for large batches) that share intermediate doublings across all terms.

Why Random Coefficients Are Necessary

Without random coefficients, a naive batch equation would simply sum all the individual equations directly. This opens a cancellation attack: an attacker can craft an invalid signature whose error term cancels out the error of another invalid signature in the sum, causing the batch to pass even though individual signatures are invalid.

Random coefficients prevent this by making it impossible for an attacker to predict how the errors will combine. BIP 340 specifies generating these coefficients deterministically: the verifier hashes all public keys, messages, and signatures together using SHA-256, then uses the resulting seed to drive a ChaCha20 CSPRNG that produces 256-bit random scalars. Since the coefficients depend on the entire batch, an attacker submitting signatures cannot predict the weights their errors will receive.

Performance Benchmarks

Benchmarks from the libsecp256k1 implementation show how the speedup scales with batch size:

The speedup grows logarithmically: doubling the batch size yields a diminishing but consistent improvement. For typical Bitcoin blocks containing hundreds of Schnorr signatures, the practical speedup falls in the 1.5x to 2x range.

Why Only Schnorr, Not ECDSA

Legacy Bitcoin transactions use ECDSA signatures, which cannot be batch verified in their standard form. Two structural properties of ECDSA prevent the equations from being combined:

• Modular inverse: ECDSA verification computes s^(-1) for each signature. This inverse is non-linear: (s_1 + s_2)^(-1) does not equal s_1^(-1) + s_2^(-1). Each signature's verification is scaled by a different inverse that cannot be factored out of a combined equation.
• x-coordinate extraction: ECDSA checks that the x-coordinate of a computed point matches a value in the signature. This coordinate-extraction function discards the y-coordinate and is not a group homomorphism: x(A + B) does not equal x(A) + x(B). This breaks the ability to sum verification equations.

Schnorr's design avoids both problems. Its verification equation s * G = R + e * P uses only group operations (point addition and scalar multiplication), and the challenge hash e = Hash(R || P || m) contains no elliptic curve operations. As BIP 340 states: "This supports batch verification, as there are no elliptic curve operations inside the hashes."

This is one of the key reasons BIP 342 (Tapscript) replaced the legacy OP_CHECKMULTISIG opcode with OP_CHECKSIGADD: the new opcode produces independent signature checks that can be batch verified, whereas the old opcode's structure made batch verification impossible even for Schnorr signatures.

Use Cases

Faster Initial Block Download

When a new Bitcoin node joins the network, it must download and validate every block since the genesis block during initial block download (IBD). Signature verification is one of the most CPU-intensive parts of this process. Batch verification allows the node to validate all Schnorr signatures in a block together, reducing the CPU time spent on cryptographic checks.

At current Taproot adoption levels (roughly 15-20% of transactions), benchmarks project a ~3% reduction in block validation time. For blocks composed entirely of Schnorr signatures, the improvement reaches approximately 16%. As Taproot adoption grows, the real-world benefit converges toward the larger figure.

Block Validation During Reorgs

When a chain reorganization occurs, nodes must quickly validate the new chain's blocks to determine the correct tip. Faster signature verification through batching reduces the time a node spends in an uncertain state, improving network convergence after competing blocks are found.

Layer 2 Protocol Verification

Off-chain protocols that settle large numbers of Schnorr-signed transactions on-chain can benefit from batch verification. When a layer 2 protocol like Spark produces settlement transactions with multiple Taproot inputs, nodes validating those transactions can batch verify all the signatures together.

Why It Matters

Bitcoin's security model depends on every full node independently verifying every transaction. Any optimization that makes verification faster without weakening security allows the network to scale more effectively. Batch verification is particularly valuable because it is a pure node-side optimization: it requires no protocol changes, no soft fork, and no additional data on-chain. The signatures remain the same; only the verification algorithm changes.

This distinguishes batch verification from the related concept of cross-input signature aggregation (CISA), which would combine multiple signatures into a single on-chain signature to reduce transaction size and fees. CISA would require a consensus-level soft fork, while batch verification can be deployed as a node software update at any time.

For a deeper look at how Schnorr signatures enable these optimizations, see the research article on Taproot and Schnorr signatures.

Implementation Status

Although BIP 340 specifies the batch verification algorithm, Bitcoin Core does not yet use it in production. As of mid-2026, the implementation is tracked across two open pull requests:

• libsecp256k1 PR #1134: adds an experimental batch module supporting both Schnorr signature batch verification and Taproot tweak checks, using Strauss's algorithm for batches of up to ~53 signatures
• Bitcoin Core PR #29491: integrates batch verification into the block validation pipeline, passing a batch object through ConnectBlock() and CheckInputScripts()

Both PRs remain under active development and review. Early benchmarks identified architectural challenges around thread contention that need to be resolved before merging. The libsecp256k1 PR shows ~1.2x speedup with Strauss alone, with Pippenger integration expected to push this closer to ~2x.

Risks and Considerations

Probabilistic Acceptance

Batch verification is inherently probabilistic: if all signatures are valid, the batch always passes. If any signature is invalid, the batch fails with overwhelming probability (at most 2^-128 chance of a false positive with 128-bit random coefficients). This negligible error probability is considered cryptographically safe, but it means batch verification is technically not deterministic. BIP 340 notes that the outcome "may only differ from individual verification with negligible probability, even to an attacker who intentionally tries to make batch and non-batch verification differ."

Failure Identification

When a batch fails, the verifier knows at least one signature is invalid but does not know which one. Identifying the invalid signature(s) requires falling back to individual verification or using a binary search strategy: split the batch in half, test each half, and recurse into the failing half. This adds complexity to error handling, though invalid signatures are rare in practice (they typically indicate a consensus violation or a bug).

Adoption Dependency

The performance benefit of batch verification is directly tied to Taproot adoption. Since only Schnorr signatures (used by Taproot outputs) can be batched, the optimization has limited impact while most transactions still use legacy or SegWit v0 output types with ECDSA signatures. At 15-20% Taproot adoption, the block validation speedup is modest. The full potential is realized only when the majority of transactions use Taproot.

Not a Consensus Change

Batch verification is a verification optimization, not a consensus rule change. Nodes that use batch verification and nodes that verify individually will always agree on which blocks are valid (with negligible probability of disagreement). This means batch verification can be deployed incrementally as a node software update without requiring network-wide coordination or a soft fork.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.