Introduction
The security of Bitcoin and other blockchains, such as Liquid, depends on the use of digital signature algorithms such as ECDSA and Schnorr signatures. The AC library called libsecp256k1, named after the elliptic curve the library operates on, is used by both Bitcoin Core and Liquid to provide these digital signature algorithms. These algorithms make use of a mathematical calculation called modular reversewhich is a relatively expensive component of the calculation.
In “Fast GCD calculation in constant time and modular inversion”, Daniel J. Bernstein and Bo-Yin Yang develop a new modular investment algorithm. In 2021, this algorithm, called “safegcd”, was implemented for libsecp256k1 from Peter Dettman. As part of the research process for this novel algorithm, Blockstream Research was the first to complete a formal verification of the algorithm design using the Coq proof wizard to formally verify that the algorithm does indeed end up with the correct modular inverse result on 256-bit inputs.
The gap between algorithm and implementation
The 2021 formalization effort only demonstrated that the algorithm designed by Bernstein and Yang works correctly. However, using that algorithm in libsecp256k1 requires implementing the mathematical description of the safegcd algorithm within the C programming language. For example, the mathematical description of the algorithm performs matrix multiplication of vectors that can be up to 256-bit signed integers wide. ; However, the C programming language will only natively provide integers up to 64 bits (or 128 bits with some language extensions).
Implementing the safegcd algorithm requires programming matrix multiplication and other calculations using 64-bit C integers. Additionally, many other optimizations They have been added to speed up implementation. In the end, there are four separate implementations of the safegcd algorithm in libsecp256k1: two constant-time algorithms for signature generation, 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.
Verifiable C
To verify that the C code correctly implements the safegcd algorithm, all implementation details must be verified. We use Verifiable Cpart of the verified software toolchain for reasoning about C code using Coq’s theorem prover.
Verification proceeds by specifying pre- and post-conditions using separation logic for each function being verified. Separation logic is a logic specialized for reasoning about subroutines, memory allocations, concurrency, and more.
Once each function is given a specification, verification continues starting from the precondition of a function and setting a new invariant after each statement in the function body, until finally setting the postcondition at the end of the body. the function or at the end of each return statement. Most of the formalization effort is spent “between” the lines of code, using invariants to translate the raw operations of each C expression into higher-level statements about what the data structures being manipulated mathematically represent. For example, what the C language considers a 64-bit array of integers may actually be a representation of a 256-bit integer.
The final result is a formal testverified by test wizard Coq, that libsecp256k1’s 64-bit variable time implementation of the safegcd modular inverse algorithm is functionally correct.
Verification Limitations
There are some limitations to functional correction testing. The separation logic used in Verifiable C implements what is known as partial correction. That means it only tests that the C code returns with the correct result. Yeah returns, but does not prove termination itself. We mitigate this limitation by using our previous Coq test of the limits of the safegcd algorithm to show that the value of the main loop counter in fact never exceeds 11 iterations.
Another problem is that the C language itself does not have a formal specification. Instead, the Verifiable C project uses the CompCert compiler project to provide a formal specification of a C language. This ensures that when a verified C program is compiled with the CompCert compiler, the resulting assembly code will comply with its specification (subject to the limitation above). However, this does not guarantee that code generated by GCC, clang, or any other compiler will necessarily 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 compiler that is not formally verified could still compile programs poorly. This does occur in practice.
Finally, Verifiable C does not support pass structures, return structures, or assignment structures. While in libsecp256k1 structures are always passed by pointer (which is allowed in Verifiable C), there are some occasions when structure assignment is used. For the modular backfix test, there were 3 assignments that had to be replaced by a specialized function call that performs the structure assignment on a field-by-field basis.
Summary
Blockstream Research has formally verified the correctness of libsecp256k1’s modular inverse function. This work provides additional evidence that verification of C code is possible in practice. Using a general-purpose testing wizard allows us to verify software based on complex mathematical arguments.
Nothing prevents the rest of the functions implemented in libsecp256k1 from also being verified. Therefore, it is possible that libsecp256k1 obtains the highest possible guarantees of software correctness.
This is a guest post by Russell O’Connor and Andrew Poelstra. The opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc or Bitcoin Magazine.
