> your AI agent picks dependencies from memory; give it dated facts — try starlog.dev ↗ vet your agent's deps ↗ vibe-coding is fine. vibe-importing isn’t. — try starlog.dev ↗ vibe-importing isn’t fine ↗ your agent has never seen your private packages — try starlog.dev ↗ facts for private packages ↗ a linter for the dependencies your AI agent picks — try starlog.dev ↗ a linter for agent deps ↗ whois is redacted, cdns mask the rest — get the real operator — try whoisgeni.us ↗ who really runs that domain ↗ domain attribution that shows its work — full evidence chain — try whoisgeni.us ↗ domain intel w/ evidence ↗

← Back to Articles

Fiat-Crypto: The Proof-Producing Compiler That Generates Cryptographic Code You Can Actually Trust

[ View on GitHub ]

Fiat-Crypto: The Proof-Producing Compiler That Generates Cryptographic Code You Can Actually Trust

Hook

Every major crypto library has shipped bugs in field arithmetic—the foundation of elliptic curve cryptography. Fiat-Crypto makes these bugs mathematically impossible by generating C code with machine-checked correctness proofs.

Context

Cryptographic implementations fail in spectacular ways. OpenSSL's Heartbleed, Debian's weak key generation, and countless timing attacks have one thing in common: they're implementation bugs, not algorithmic flaws. The math is sound, but translating modular arithmetic into C code that handles carries, prevents overflow, and runs in constant time is error-prone.

Field arithmetic—addition, multiplication, and reduction modulo a prime—is the bedrock of elliptic curve cryptography. A single off-by-one error in carry propagation can silently produce wrong answers. Worse, these bugs are subtle: they might only manifest for specific inputs, passing fuzzing and unit tests while lurking in production. Traditional approaches rely on careful C programming, code review, and extensive testing. But testing can only show the presence of bugs, not their absence. Fiat-Crypto takes a radically different approach: it proves correctness first, then extracts code from the proof.

Technical Insight

Verified Outputs

Proof-Carrying Pipeline

curve params, limb widths

term → AST

transform

apply tactics

optimized IR

emit

emit

emit

Field Specification

(Gallina)

Reification Engine

Typed Expression AST

(with range bounds)

Proven Rewrite Rules

Partial Evaluation

& Simplification

Code Extraction

C Code

Rust Code

Go/Bedrock2 Code

System architecture — auto-generated

Fiat-Crypto is a compiler written in Coq (recently renamed to Rocq Prover) that takes mathematical field specifications and produces C, Rust, Go, or Bedrock2 implementations with machine-checked proofs that they compute the correct answer. The architecture is a multi-stage rewriting pipeline that maintains correctness invariants through dependent types.

The pipeline starts with a high-level specification. You describe your prime field—say, the field modulo 2^255-19 used in Curve25519—and Fiat-Crypto generates optimized arithmetic. Here's what a simplified specification looks like in Gallina (Coq's programming language):

Definition p : Z := 2^255 - 19.
Definition a24 : Z := 121665.

(* Specify the representation: 10 limbs of 25.5 bits each *)
Definition limbwidth := 25.5.
Definition n : nat := 10.

(* The compiler generates functions for this field *)
Definition curve25519_ops := 
  synthesize_field_ops p limbwidth n.

This high-level specification gets lowered through intermediate representations. First, it becomes a simple imperative language that explicitly models carries and bounds. The system tracks value ranges using dependent types—if a variable holds a 26-bit limb, its type encodes that constraint. When two limbs are added, the type system proves the result fits in 27 bits (or requires a carry).

The genius is in the reification-based transformation. Coq terms are converted to an abstract syntax tree, then transformed via proven-correct rewrite rules. Each optimization—constant folding, common subexpression elimination, strength reduction—comes with a lemma proving it preserves semantics. The type system ensures these transformations never violate bounds or introduce overflow.

Here's a simplified view of what the generated C looks like for a field multiplication (actual output is more optimized):

void fe_mul(uint32_t out[10], const uint32_t in1[10], const uint32_t in2[10]) {
  uint64_t x0 = ((uint64_t)in1[0] * in2[0]);
  uint64_t x1 = (((uint64_t)in1[0] * in2[1]) + ((uint64_t)in1[1] * in2[0]));
  // ... multiplication and carry propagation ...
  uint64_t x18 = (x17 + (x16 >> 26));
  uint32_t x19 = (uint32_t)(x18 & UINT32_C(0x3ffffff));
  // ... final reduction modulo p ...
  out[0] = x19;
  out[1] = x20;
  // ...
}

The key difference from hand-written code: this function comes with a Coq proof that for any inputs in1 and in2, the output out represents (in1 * in2) mod p under the limb representation. The proof accounts for all carries, all reductions, and all intermediate overflow checks.

The system supports multiple implementation strategies parameterized over curve equations. Saturated Solinas representation packs bits tightly for pseudo-Mersenne primes like 2^255-19. Unsaturated representations leave headroom for additions without carries. Montgomery form optimizes reduction for arbitrary primes. You specify the prime and target platform (32-bit vs 64-bit), and Fiat-Crypto selects the optimal strategy.

The Bedrock2 backend is particularly interesting. Instead of extracting to C and trusting the compiler, it generates code in Bedrock2, a formally verified low-level language with semantics defined in Coq. This provides an end-to-end verified path: your field specification in math, through the compiler, to assembly-level semantics, with zero trust in external tools. The entire chain is mechanically checked.

Partial evaluation during proof generation keeps compile times manageable (though "manageable" is relative—large primes still take hours). The system proves correctness for symbolic inputs, then specializes to concrete primes. This avoids exponential blowup in proof size while maintaining full generality. When you run the extracted OCaml compiler binary, it performs this specialization on-demand.

Gotcha

Compile times are the elephant in the room. Generating code for P-521 (a 521-bit prime) can take several hours and requires increasing OCaml's stack size limit. This makes iteration painful—if you're experimenting with different limb widths or representation strategies, you're waiting a long time for feedback. CI pipelines need significant resources, and casual experimentation is impractical.

Performance is another trade-off. Generated code is readable and correct, but not competitive with hand-optimized assembly. Expect 20-40% slower than libraries like HACL* or BoringSSL. The system optimizes algebraically (eliminating redundant operations, factoring constants), but doesn't know about microarchitectural details like instruction scheduling, register allocation tricks, or SIMD. If you're building a high-throughput TLS terminator handling thousands of connections per second, this performance gap matters.

The scope is also limited: Fiat-Crypto generates field arithmetic primitives, not complete protocols. Point addition, scalar multiplication, and protocol logic live elsewhere. You'll need to compose generated code with other verified components (like Bedrock2 programs or HACL* libraries) or hand-written code, which introduces verification gaps. The constant-time guarantees rely on assumptions about C compiler behavior—the Bedrock2 path eliminates this, but has narrower platform support and less battle-testing than mature C compilers.

Verdict

Use if: you're building security-critical systems where a single arithmetic bug means catastrophic failure—HSMs, cryptocurrency wallets, aerospace/medical embedded systems, or high-assurance TLS implementations. The compilation time tax is worth paying when correctness trumps absolute performance and you need mathematical certainty, not just extensive testing. The Bedrock2 backend is particularly compelling if you're targeting a verified software stack and can tolerate limited platform support. Skip if: you need maximum performance (use HACL* or carefully audited assembly), are building general-purpose crypto libraries where developer velocity matters (use Ring or BoringSSL), or can't afford multi-hour compile times in your development workflow. For most applications, well-tested constant-time C with fuzzing and code review is sufficient—reserve Fiat-Crypto for contexts where "sufficient" isn't good enough.