[ad_1]
introduction
La sécurité du Bitcoin et d’autres blockchains, comme Liquid, dépend de l’utilisation d’algorithmes de signature numérique tels que les signatures ECDSA et Schnorr. Une bibliothèque AC appelée libsecp256k1, du nom de la courbe elliptique sur laquelle la bibliothèque s’exécute, est utilisée à la fois par Bitcoin Core et Liquid pour fournir ces algorithmes de signature numérique. Ces algorithmes utilisent un calcul mathématique appelé Modulaire inverséce qui est un élément relativement coûteux du calcul.
sur »Calcul rapide du pgcd en temps constant et inversion modulaire« , Daniel J. Bernstein et Bo-Yin Yang développent un nouvel algorithme d’inversion modulaire. En 2021, cet algorithme, baptisé « safegcd », a été appliqué pour libsecp256k1 par Peter Dettman. Dans le cadre du processus de test de cet algorithme innovant, Blockstream Research a été le premier à réaliser une Vérification formelle de la conception de l’algorithme en utilisant l’assistance à la preuve Coq pour vérifier formellement que l’algorithme se termine avec le résultat inverse modulaire correct sur les entrées de 256 bits.
L’écart entre l’algorithme et l’application
L’effort de formalisation de 2021 a seulement montré que l’algorithme conçu par Bernstein et Yang fonctionne correctement. Cependant, l’utilisation de cet algorithme dans libsecp256k1 nécessite l’implémentation de la description mathématique de l’algorithme safegcd dans le langage de programmation C. Par exemple, la description mathématique de l’algorithme effectue une multiplication matricielle de vecteurs qui peuvent être aussi larges que des entiers signés de 256 bits, mais le Le langage de programmation C ne fournira que des entiers jusqu’à 64 bits (ou 128 bits avec les extensions certaines langues).
La mise en œuvre de l’algorithme safegcd nécessite la programmation d’une multiplication matricielle et d’autres calculs utilisant des entiers C 64 bits. De nombreuses autres optimisations Ajouté pour rendre l’application rapide. En fin de compte, il existe quatre implémentations distinctes de l’algorithme safegcd dans libsecp256k1 : deux algorithmes à temps fixe pour générer des signatures, un optimisé pour les systèmes 32 bits et un optimisé pour les systèmes 64 bits, et deux algorithmes à temps variable pour la vérification des signatures, encore une fois. un pour les systèmes 32 bits et un pour les systèmes 64 bits.
C vérifiable
Afin de vérifier que le code C implémente correctement l’algorithme safegcd, tous les détails d’implémentation doivent être vérifiés. nous utilisons C vérifiableFait partie de la chaîne d’outils logiciels vérifiés pour raisonner sur le code C à l’aide du prouveur du théorème Coq.
La validation se déroule en spécifiant des préconditions et des postconditions à l’aide d’une logique de séparation pour chaque fonction en cours de validation. logique de séparation est une logique spécialisée dans la logique relative aux sous-programmes, aux allocations de mémoire, à la concurrence, etc.
Une fois que chaque fonction reçoit une spécification, la vérification continue en commençant par la précondition d’une fonction, et en établissant un nouvel invariant après chaque instruction dans le corps de la fonction, jusqu’à établir finalement la postcondition à la fin du corps de la fonction ou à la fin de chaque fonction. Déclaration de retour. La plupart des efforts de formalisation sont consacrés « entre » les lignes de code, en utilisant des invariants pour traduire les opérations brutes de chaque expression C en instructions de niveau supérieur sur ce que représentent mathématiquement les structures de données traitées. Par exemple, ce que le langage C considère comme un tableau d’entiers de 64 bits peut en réalité être une représentation d’un entier de 256 bits.
Le résultat final est Preuve officielleVérifié par l’assistant de preuve de Coq que l’implémentation à temps variable 64 bits de libsecp256k1 de l’algorithme inverse modulaire safegcd est fonctionnellement correcte.
Limites de validation
Il existe certaines limites à la preuve de l’exactitude fonctionnelle. La logique de séparation utilisée dans Verifiable C implémente ce qu’on appelle Partiellement correct. Cela signifie que cela prouve simplement que le code C renvoie le résultat correct si Cela se répète, mais cela ne prouve pas la fin elle-même. Nous réduisons cette limitation en utilisant Notre précédente preuve de Coq des limites de l’algorithme safecd pour prouver que la valeur du compteur de boucle de la boucle principale ne dépasse jamais 11 itérations.
Un autre problème est que le langage C lui-même n’a aucune spécification officielle. Au lieu de cela, le projet Verifiable C utilise Projet de compilateur CompCert pour fournir une spécification officielle du langage C. Cela garantit que lorsqu’un programme C vérifié est compilé avec le compilateur CompCert, le code assembleur résultant sera conforme à sa spécification (sous réserve de la limitation ci-dessus). Cependant, cela ne garantit pas que le code généré par GCC, clang ou tout autre compilateur fonctionnera nécessairement. Par exemple, les compilateurs C peuvent accepter différents ordres d’évaluation pour les arguments au sein d’un appel de fonction. Et même si le langage C avait une spécification officielle, tout compilateur qui n’est pas lui-même officiellement certifié peut toujours compiler des programmes de manière incorrecte. C’est se produire en fait.
Enfin, Verifiable C ne prend pas en charge le passage de structures, le retour de structures ou l’attribution de structures. Alors que dans libsecp256k1, les structures sont toujours transmises par pointeur (ce qui est autorisé dans Verifiable C), il existe quelques cas où l’affectation de structure est utilisée. Pour prouver l’exactitude inverse modulaire, il y avait 3 affectations qui ont dû être remplacées par un appel à une fonction spéciale qui effectue l’affectation de la structure champ par champ.
résumé
Blockstream Research a officiellement vérifié l’exactitude de la fonction inverse modulaire de libsecp256k1. Ce travail fournit une preuve supplémentaire que la vérification du code C est possible en pratique. L’utilisation d’un assistant de preuve général nous permet de vérifier des logiciels construits sur des arguments mathématiques complexes.
Rien n’empêche les autres fonctions implémentées dans libsecp256k1 de se valider également. Ainsi, libsecp256k1 peut avoir les garanties d’intégrité logicielle les plus élevées possibles.
Il s’agit d’un article invité de Russell O’Connor et Andrew Polstra. Les opinions exprimées sont entièrement les leurs et ne reflètent pas nécessairement celles de BTC Inc ou de Bitcoin Magazine.
[ad_2]
Source link
