Introduction
The security of Bitcoin, and other blockchains, such as Liquid, relies on the use of digital signature algorithms such as ECDSA and Schnorr signatures. An AC library called libsecp256k1, named after the elliptic curve on which the library works, is used by both Bitcoin Core and Liquid, to provide these digital signature algorithms. These algorithms use a mathematical calculation called a modular inversewhich is a very expensive part of the calculation.
in “Constant-time fast gcd computing and modular conversion,” Daniel J. Bernstein and Bo-Yin Yang developed a new modular inversion algorithm. In 2021, this algorithm, called “safegcd,” implemented for libsecp256k1 by Peter Dettman. As part of the research process for this new algorithm, Blockstream Research was the first to complete its formal confirmation of the algorithm design using the Coq proof helper to formally prove that the algorithm does indeed end up with the correct modular inverse product on 256-bit input.
The gap between Algorithm and Implementation
The formal attempt in 2021 only showed that the algorithm designed by Bernstein and Yang works correctly. However, using that algorithm in libsecp256k1 requires the mathematical description of the safegcd algorithm to be implemented within the C programming language. For example, the mathematical description of the algorithm performs matrix multiplication of vectors which can be as wide as 256 bit signed integers, but the C programming language natively only accepts numbers up to 64 bits (or 128 bits with some of language extension).
Implementation of the safegcd algorithm requires programming the matrix multiplication and other calculations using 64 bit C integers. In addition, many other optimizations are added so that the implementation is fast. Finally, libsecp256k1 contains four different implementations of the safegcd algorithm: two constant-time signature generation algorithms, one optimized for 32-bit systems and one optimized for 64-bit systems, and two variable time algorithms for signature verification, again. one for 32-bit systems and one for 64-bit systems.
C
To verify that the C code implements the safegcd algorithm correctly, all implementation details must be examined. We use Cpart of the Validated Software Tool for reasoning about C code using the Coq theorem prover.
Verification proceeds by specifying preconditions and post conditions using separation logic for each function under verification. The logic of separation the specialized logic for reasoning about subroutines, memory allocations, concurrency and more.
Once each function is assigned, validation proceeds by starting from the function precondition, and setting up a new variable after each statement in the function body, until the the position of the post will be established at the end of the task group or the end of each one. return statement. Most of the formal effort is spent “between” the lines of code, using the variables to translate the raw operations of each C expression into high-level statements about what the data structures being manipulated are. ' represent mathematically. For example, what the C language considers an array of 64-bit integers may be a representation of a 256-bit integer.
The result is final formal confirmationverified by the Coq validation helper, that the libsecp256k1 64-bit variable-time implementation of the safegcd modular inverse algorithm is functionally correct.
Limitation of proof
There are some limitations to the verification of an executive function. The separation logic used in Verifiable C implements what is called partial justice. That means it only checks that the C code returns the correct output if so it returns, but it does not determine its own end. We mitigate this limitation by using our previous Coq confirmation of the limits on the safegcd algorithm to verify that the loop counter value of the main loop will not actually exceed 11 iterations.
Another issue is that the C language itself has no formal specification. Instead the Verifiable C project uses the CompCert compiler project to provide a formal specification of the C language. This guarantees that when a certified C program is compiled by the CompCert compiler, the resulting compiled code will meet its specification (subject to the above restriction). But this does not guarantee that the code generated by GCC, clang, or any other compiler will work. For example, C compilers are allowed to have different evaluation orders for arguments within a function call. And even if the C language had a formal specification, any uncertified compiler could still compile programs incorrectly. This will do happen in practice.
Finally, Verifiable C does not support passing structures, returning structures or specifying structures. While in libsecp256k1, structures are always passed with a directive (which is allowed in Verifiable C), there are a few instances where a structure specification is used. For the correct modular declaration, there were 3 specifications that had to be replaced by a special function call that performs the specification of a structure field by field.
Summary
Blockstream Research has formally verified the correctness of libsecp256k1's modular inverse function. This work provides further evidence that C code verification is possible in practice. Using a general purpose verification assistant allows us to verify software based on complex mathematical arguments.
Nothing prevents the rest of the functions implemented in libsecp256k1 from being verified as well. Thus libsecp256k1 is able to achieve the highest software correctness guarantees.
This is a guest post by Russell O'Connor and Andrew Poelstra. Their views are entirely theirs and do not necessarily reflect the views of BTC Inc or Bitcoin Magazine.
Source link
