Name Sivaram Dhakshinamoorthy
Email [email protected]
IRC nick siv2r
Blog siv2r.hashnode.dev
GitHub siv2r
LinkedIn siv2ram
Twitter **** @siv2r
Timezone Indian Standard Time (UTC+5:30)
Batch verification is a method to verify many digital signatures at once. This method is more efficient than verifying the signatures one by one. Hence, It is more appropriate for systems that are required to verify a large number of signatures, such as a Bitcoin network.
For batch verifying $n$ schnorr signatures $(X_i, m_i, (R_i, s_i))$, the verifier first generates $n$ random number $a_1, a_2, ..., a_n$ then computes $n$ challenge hash $e_i = H_{tag}(R_i || P_i || m_i)$ and checks if:
$$ (\sum_{i=1}^{n}a_is_i )\!G\! \quad ?= \enspace\sum_{i=1}^{n}a_i\!\!R_i \enspace
$$
There are an equal number of point multiplications in both single signature verification and batch verification, so it may seem there isn’t any speed gains through batching. However, several algorithms (like Strauss, Pippenger, and Bos-Coster) are known for computing $a_1P_1 + a_2P_2 + ... + a_n*P_n$ faster than summing the individual multiplications.
Batch validating Bitcoin’s ECDSA signature is less efficient than single validation (without additional witness data). The Taproot upgrade (activated Nov 2021) introduced the Schnorr signature, which supports efficient batch verification algorithms. Batch verification will speed up block validation, initial block download, and large multi-party protocols (MuSig, FROST).