The Blockstream Research team wrote about a new formally-proved fast & constant-time extended GCD algorithm that's under development for libsecp256k1 which would dramatically improve transaction signing performance and verification for Bitcoin nodes.
A new fast, constant-time extended GCD algorithm is under development for libsecp256k1. This algorithm would dramatically improve transaction signing performance (which is often done on very weak hardware) and verification (which must be done tens of millions of times by Bitcoin full nodes). However, verifying the correctness of this new algorithm was an open problem.
To verify the correctness of this novel algorithm, devs created a formal proof of its correctness in the Coq proof assistant. They took advantage of Coq’s ability to perform proof by reflection to execute a convex hull computation within the proof assistant and verify that this computation is correct.
def gcd(f, g):
del = 1
while g != 0:
if del > 0 and g & 1:
del, f, g = 1 - del, g, (g - f) >> 1
del, f, g = 1 + del, f, (g + (g % 2)*f) >> 1
Those interested in verifying the proof themselves can find the Coq code in safegcd- https://github.com/sipa/safegcd-bounds/pull/7