Introdução
A segurança do Bitcoin e de outros blockchains, como o Liquid, depende do uso de algoritmos de assinatura digital, como assinaturas ECDSA e Schnorr. Uma biblioteca AC chamada libsecp256k1, em homenagem à curva elíptica na qual a biblioteca funciona, é usada tanto pelo Bitcoin Core quanto pelo Liquid, para fornecer esses algoritmos de assinatura digital. Esses algoritmos usam um cálculo matemático chamado modular inversoque é a parte mais cara do cálculo.
Em “Computação rápida de gcd e transformações modulares”, Daniel J. Bernstein e Bo-Yin Yang desenvolvem um novo algoritmo para transformações modulares. Em 2021, este algoritmo, denominado “safegcd”, foi implementado em libsecp256k1 por Peter Dettman. Como parte do processo de teste deste novo algoritmo, a Blockstream Research foi a primeira a concluir a verificação formal do design do algoritmo usando o assistente de prova Coq para verificar formalmente se o algoritmo realmente termina com o resultado inverso modular correto em 256 bits. entrada.
Lacuna entre algoritmo e implementação
A tentativa de legalizá-lo em 2021 apenas mostrou que o algoritmo desenhado por Bernstein e Yang funciona corretamente. No entanto, a implementação desse algoritmo em libsecp256k1 requer o uso da definição matemática do algoritmo safegcd na linguagem de programação C. Por exemplo, a definição matemática de um algoritmo faz a multiplicação de matrizes de vetores que podem ter até 256 números inteiros com sinal, mas a linguagem de programação C fornecerá apenas números inteiros de até 64 bits (ou 128 bits com algumas extensões de linguagem).
O uso do algoritmo safegcd requer a programação da multiplicação de matrizes e outros cálculos usando números inteiros de 64 bits do C. Além disso, muitas outras configurações foram adicionadas para tornar a inicialização mais rápida. Finalmente, existem quatro implementações diferentes do algoritmo safegcd em libsecp256k1: dois algoritmos de geração de assinatura em tempo constante, um para sistemas de 32 bits e outro para sistemas de 64 bits, e dois algoritmos de tempo variável para verificação de assinatura também. um para sistemas de 32 bits e outro para sistemas de 64 bits.
Verificado C
Para garantir que o código C implemente corretamente o algoritmo safegcd, todos os detalhes de implementação devem ser verificados. Usamos Verifiable C, parte do Verified Software Toolchain para raciocinar sobre o código C usando o provador do teorema Coq.
A validação prossegue especificando pré-condições e pós-condições usando lógica de partição para cada operação executada pela validação. O conceito de fragmentação é um conceito especial para raciocínio sobre sub-rotinas, alocação de memória, paralelismo e assim por diante.
Depois que cada função recebe uma especificação, a validação continua começando pela pré-condição da função e estabelecendo uma nova constante após cada instrução no corpo da função, até que uma pós-condição seja encontrada no final do corpo da função ou no final de cada função . declaração de retorno. A maior parte do esforço de formalização é gasto “entre” as linhas de código, usando variáveis para traduzir as funções brutas de cada expressão C em declarações de alto nível sobre o que as estruturas de dados em uso representam matematicamente. Por exemplo, o que a linguagem C considera uma matriz de números inteiros de 64 bits pode, na verdade, ser uma representação de um número de 256 bits.
O resultado é uma prova formal, verificada pelo assistente de prova Coq, de que a implementação de tempo variável de 64 bits do algoritmo inverso modular safegcd da libsecp256k1 está funcionalmente correta.
Limitações de garantia
Existem algumas limitações à evidência de justiça de operação. O método de classificação usado no Verified C usa o que é conhecido como precisão parcial. Isso significa que apenas prova que o código C retorna o resultado correto se ele retorna, mas não se completa sozinho. Reduzimos essa limitação usando nossa prova anterior dos limites de Coq no algoritmo safegcd para provar que o valor do contador de loop do loop principal na verdade nunca excede 11 iterações.
Outra questão é que a linguagem C em si não possui especificações formais. Em vez disso, o projeto C verificável usa o projeto de compilação CompCert para fornecer uma especificação formal para a linguagem C. Isso garante que quando um programa C verificado for compilado com o compilador CompCert, o código assembly resultante atenderá sua especificação (sujeito ao limite acima). . No entanto, isso não garante que o código gerado pelo GCC, clang ou qualquer outro compilador realmente funcione. Por exemplo, os compiladores C podem ter diferentes ordens de avaliação de argumentos entre chamadas de função. E mesmo que a linguagem C tenha definições formais, qualquer compilador que não seja formalmente certificado não poderá compilar programas. Isso é possível através da prática.
Finalmente, Verifiable C não suporta passagem de propriedades, retorno de propriedades ou atribuição de propriedades. Enquanto em libsecp256k1 as estruturas são sempre passadas por ponteiro (permitido em Certified C), há alguns momentos em que a atribuição de estrutura é usada. Para obter uma prova de correção do módulo, houve 3 atribuições que tiveram que ser substituídas por uma chamada de função especial que faz a atribuição da propriedade campo por campo.
Resumo
A Blockstream Research confirmou oficialmente a exatidão da função reversa do libsecp256k1. Este trabalho fornece mais uma prova de que a verificação do código C é possível na prática. Usar um assistente de prova de uso geral nos permite verificar software baseado em argumentos matemáticos complexos.
Nada impede que todas as outras funções implementadas em libsecp256k1 também sejam verificadas. Portanto, é possível que o libsecp256k1 obtenha garantias de integridade de software muito altas.
Este é um post convidado de Russell O'Connor e Andrew Poelstra. As opiniões expressas são inteiramente próprias e não refletem as da BTC Inc ou da Bitcoin Magazine.
