Public key recovery for EC leaves in P2MR (BIP-360)

BIP342 introduces an accounting model that factors in both the serialized witness size and a fixed budget, with an additional charge for each recovery operation. The model specifies a 50-unit budget and imposes a 50-unit fee per recovery. Ordinary Schnorr signature verification within libsecp256k1 utilizes the Strauss–Shamir joint multiplication optimization, which enhances efficiency. To ensure a fair performance comparison, this optimization was also applied to recovery operations during benchmarking.

The preliminary benchmarks indicate parity in speed between regular Schnorr verification and recovery when leveraging this optimization. Despite concerns that shorter witnesses could result in denser distribution of signature operations compared to a standard elliptic curve (EC) leaf, testing reveals a significant difference in CPU cost per weight. Specifically, EC recovery demonstrates a much lower CPU cost per weight than the repeated-signature-check construction used in Bitcoin Core’s sigops-ratio tests.

This analysis supports the conclusion that the proposed accounting model is viable and should function effectively in practice, ensuring that resource usage remains within acceptable bounds while maintaining system performance.