Vérification par lot

Un vérificateur regroupe u signatures, pondère toutes sauf la première par un scalaire aléatoire, et résout le groupe en une seule équation au lieu de u. Le BIP-340 a été conçu pour cela, fixant les signatures à 64 octets, tandis que l'ECDSA standardisé ne peut pas être traité par lot du tout, sauf si des données témoins supplémentaires sont ajoutées. Le traitement par lot relève du choix de chaque vérificateur : il change la vitesse à laquelle un nœud contrôle l'historique et rien du tout pour vos bitcoins.

Comment cela fonctionne

La vérification par lot est spécifiée dans le BIP-340 sous le nom BatchVerify : elle prend u clés publiques de 32 octets, u messages et u signatures de 64 octets et répond une seule fois pour l'ensemble.

Les pondérations viennent d'abord. Le vérificateur génère u-1 entiers dans l'intervalle allant de 1 à n-1, où n est l'ordre de la courbe, de façon déterministe à partir d'un générateur amorcé par un hachage de chaque entrée du lot : clés, messages et signatures. Le BIP-340 qualifie SHA256 de hachage d'amorçage sûr et ChaCha20 de moyen sûr de l'étendre en entiers de 256 bits, en écartant ceux qui tombent hors de l'intervalle.

Le lot se réduit alors à un seul test : la somme pondérée des valeurs s, multipliée par le point générateur, doit être égale à la même pondération appliquée aux points R et, pour chaque signature, à son défi multiplié par sa propre clé publique. Ces u vérifications séparées deviennent une seule comparaison, à laquelle le BIP-340 attribue des gains de vitesse significatifs.

Un coût par signature paie cette économie. BatchVerify replace chaque valeur r sur la courbe, ce que la vérification individuelle ne fait jamais : Verify recalcule R à partir de s et du défi, puis vérifie seulement que sa coordonnée x est égale à r.

La garantie est délibérément asymétrique. Si toutes les signatures du lot sont valides, BatchVerify réussit toujours ; si une seule est invalide, il réussit avec une probabilité au plus négligeable. Ce qu'il ne fera pas, c'est désigner la fautive : un vérificateur qui a besoin de savoir quelle signature a échoué les contrôle une à une.

Où le voir

La vérification par lot vit entièrement du côté vérificateur du réseau, ce qui explique qu'elle n'apparaisse jamais dans une interface de portefeuille ni sur une estimation de frais.

Là où elle est utile, c'est pour un nœud qui traite d'un coup des années de dépenses Taproot, pas pour un portefeuille qui envoie un paiement. Le BIP-340 n'impose le traitement par lot nulle part : la vérification d'une signature unique est la définition, et un lot est ce qu'un vérificateur peut choisir. Le BIP exige un algorithme spécifié au niveau de l'octet, l'exactitude qui manquait à l'analyse DER jusqu'au BIP-66, afin que personne ne puisse construire une signature valide pour certains vérificateurs et pas pour d'autres. Comme chaque vérificateur choisit ses propres lots, c'est cette propriété qui garantit que la vérification par lot et la vérification individuelle ne diffèrent qu'avec une probabilité négligeable, même face à un attaquant qui cherche à les faire diverger.

Le traitement par lot explique aussi des choix du BIP-340 qui semblent arbitraires isolément. Les signatures auraient pu prendre une forme plus courte, où un hachage de 16 octets suffit pour l'objectif de sécurité de 128 bits, et le BIP l'a refusée : les hachages courts sont fragiles quand des signataires méfiants travaillent ensemble, et la forme plus longue qui porte R est celle qui prend en charge le traitement par lot. Les clés publiques font 32 octets plutôt que l'encodage compressé habituel de 33 octets du bitcoin, choisi pour la compacité, et la coordonnée y ainsi omise est fixée à la valeur paire plutôt que laissée ambiguë, car une vérification efficace et le traitement par lot ont tous deux besoin qu'elle soit sans ambiguïté.

L'ECDSA n'en bénéficie pas du tout. Le BIP-340 donne cela comme l'une des raisons de changer de schéma de signature : la formulation standardisée ne peut pas être vérifiée plus efficacement en lot qu'individuellement, sauf si des données témoins supplémentaires sont ajoutées.

Vérification par lot vs MuSig2

La vérification par lot et MuSig2 rendent tous deux moins coûteuses une pile de signatures, mais seul MuSig2 change ce qui est diffusé.

MuSig2 agrège plusieurs signataires en une seule clé et une seule signature ordinaire de 64 octets avant que la transaction atteigne le réseau : son économie porte donc sur la confidentialité et l'espace de bloc, et elle est n-sur-n : chaque signataire doit participer. La vérification par lot laisse chaque signature où elle était et ne réorganise que l'arithmétique qu'effectue un validateur, sans la coopération ni même la connaissance de quiconque : un nœud peut traiter par lot des signatures faites par des inconnus à des années d'écart, dans des transactions sans rapport.