Proof-Carrying Coding
Last updated: 2026-11-046 min read
Sources checked 2026-11-042 sourced figures
Proof-carrying coding is an analogy for attaching task, boundaries, executed checks, results, skips, and provenance to a change. Evidence, receipts, test output, attestations, and formal proofs are not interchangeable. Without a formal property, proof object, assumptions, and checker, these are bounded review artifacts rather than proof or a correctness guarantee.
Contents
The 1997 idea: trust through checkable artifacts
In Proof-Carrying Code (POPL 1997; SIGPLAN named it the Most Influential POPL Paper of that year in 2007), George Necula solved an adversarial trust problem elegantly: a host must run a binary from an untrusted source. Instead of trusting the source or laboriously analyzing the binary, the source attaches a formal safety proof, and the host runs a small, fast proof checker. The deep insight is asymmetric effort: constructing the proof is expensive and falls on the producer; checking it is cheap and falls on the consumer. The host stays sovereign without doing the producer’s work.
The transfer to AI coding – honestly marked as analogy
AI coding recreates the trust setup almost exactly: a prolific, not-fully-trusted producer (the model) delivers work to a receiver (your team) that cannot afford to redo it. In Sonar’s 2026 survey, 96% of developers do not fully trust that AI-generated code is functionally correct, and 48% always check it before committing. Our reading, not Sonar’s: where only half of the developers always check, a large share of AI code merges on trust anyway, and the metric that counts it is the unverified-merge rate. Proof-carrying coding resolves the dilemma the 1997 way, with one honest difference that must be stated, not hidden:
| Proof-carrying code (1997) | Proof-carrying coding (2026) | |
|---|---|---|
| Untrusted producer | Code supplier (possibly adversarial) | The generating model/agent |
| Attached artifact | Formal, machine-checkable safety proof | Evidence record: task, checks, results, skips |
| Receiver's job | Run a small proof checker | Verify the evidence, judge the trade-offs |
| Property covered | Narrow safety properties, with certainty | Task conformance and validation, with confidence |
| The economics | Checking ≪ proving | Checking evidence ≪ reconstructing the run |
The bottom row is why the analogy is load-bearing rather than decorative: in both systems, the entire design exists because verification is radically cheaper than reproduction. Evidence that costs more to check than redoing the work would be worthless, which is also the quality bar for what belongs in the record.
What the principle demands in practice
- Producers attach, always. Every AI run delivers its change plus its record: the written task, the validations that ran, their results, what was skipped. No record, no review request.
- Receivers verify, not reconstruct. The review starts from the evidence: scope against boundaries, criteria against results. Judgment time goes to architecture and trade-offs, not archaeology.
- Nothing merges on trust alone. “The agent said it passed” is a claim, not evidence. Validation authored outside the generating session is what makes the record checkable.
- The record persists. Stored with the code, the records accumulate into the audit trail nobody had to write retroactively. The artifact’s structure, with a labeled sample, is on the evidence reports page.
The 2026 revival – and the honest limits
The formal end of the idea is being rebuilt for agents. A June 2026 preprint on proof-carrying agent actions admits a high-value agent action only when a certificate path exists, checked at a gate before side effects occur: Necula’s architecture, re-aimed at runtime governance, and tested on a benchmark rather than in production. The pragmatic end, described above, is deployable today. Its limits deserve the same clarity: evidence raises confidence, it does not prove correctness; a record can be complete and the architecture still wrong, which is why the human gate stays; and the quality of the whole scheme is bounded by the quality of the task: vague mandates produce unfalsifiable evidence.
What is proof-carrying coding?
What proof-carrying coding is can be stated plainly: an analogy, not a technique. It borrows the shape of proof-carrying code, in which a program ships together with a proof that a checker can verify, and applies it to AI-assisted changes: the change ships together with its task, boundaries, executed checks, results, skips and provenance, so that a reviewer can check the record rather than take the author’s word.
The original is a research result. George Necula’s 1997 paper in the ACM Digital Library and his Berkeley project page (last revised in 2002) are the primary sources for proof-carrying code itself. If you want the formal technique, read those; this page describes the transfer, and marks it as a transfer.
The difference that matters: a receipt records what ran, test output reports observations, an attestation states what an actor asserts. None of that is a proof unless a formal property, a proof object, stated assumptions and a checker are actually present. In practice they rarely are, which is why the artifacts this analogy produces are bounded review records, closer to an evidence report than to a certificate.
Where Reality Graph fits
Proof-carrying coding is Reality Graph’s operating principle stated as a concept. Reality Graph checks every run against its written task, runs the approved checks itself and records the result in an evidence report, as a byproduct of the run and on your own machine. What that record resolves into, a single outcome per run and the rule that keeps a run blocked even when every test is green, is described under how the outcome is decided. The principle stands without any specific tool; the tool exists because the principle is tedious to uphold by hand at AI volume.
This principle gives you
- Reviews that start from verified facts, not archaeology
- The verification asymmetry working for you, per change
- An audit trail accumulating as a byproduct
- A 1997 architecture that SIGPLAN named its most influential POPL paper in 2007
It does not give you
- Formal proofs: the evidence raises confidence, not certainty
- A substitute for the human merge decision
- Value from vague tasks: checkable mandates are the precondition
- Necula's guarantees: the analogy is honest about being one
If these boundaries fit how your team wants to ship:
FAQ
- What is proof-carrying coding, and how does it work in practice?
- Proof-carrying coding is an analogy for attaching a change's task, boundaries, executed checks, results, skips, and provenance. A receipt records what ran; test output reports observations; an attestation states what an actor asserts. None is a formal proof unless a formal system, property, proof object, and checker are actually present. Review and approval remain separate decisions.
- Where does the term come from?
- George Necula's POPL 1997 paper describes programs accompanied by formal, machine-checkable evidence for specified safety properties. This article borrows only the producer-attaches / receiver-checks architecture. Ordinary development evidence does not inherit the theorem, property coverage, assumptions, or guarantees of that formal system.
- Are these actual proofs, like in Necula's work?
- Usually not. Tests, lint output, task comparisons, receipts, and attestations are evidence about stated checks and environments. They can be incomplete or wrong and do not establish business correctness. Call an artifact a formal proof only when its formal property, assumptions, proof object, and checker are identified.
- Why does the asymmetry matter so much?
- Attached evidence can reduce reconstruction work when it is current, reproducible, and relevant, but this page provides no universal time or cost result. Evidence production and checking both have costs; the reviewer still evaluates coverage, provenance, assumptions, residual risk, and the final decision.
- How does this differ from an evidence report?
- The evidence report is the artifact: what gets recorded per run, in which structure, with a labeled sample. Proof-carrying coding is the principle the artifact serves: producers attach, receivers verify, nothing is accepted on trust alone. You can read them in either order; the report page shows the how, this page argues the why.
- Is anyone applying this to AI agents formally?
- A single-author arXiv preprint of 2 June 2026 proposes proof-carrying agent actions: a high-value agent action is admitted only when a certificate path exists, checked at a gate before side effects occur, and the paper names Necula's 1997 work as the origin of the idea. It reports a reference implementation on a benchmark of 96 traces, not a production deployment, and it is not evidence that ordinary evidence-attached changes are formally proven.
- Is there a proof-carrying coding tool?
- Not in the formal sense: no tool on this page produces a proof object that a checker verifies against a stated property. What exists are tools that attach the ingredients of the analogy to a change, which is to say task, boundaries, executed checks, results and provenance, and keep them reviewable. Reality Graph does that for one run at a time; it calls the result a record, not a proof, and the review decision stays with a person.
Keep reading
Sources
- George Necula – Proof-Carrying Code, POPL 1997 (formal origin; bounded properties and assumptions; DOI verified through Crossref, the ACM page refuses automated clients); checked 4 November 2026
- George Necula – Proof-Carrying Code project page, UC Berkeley (last revised 22 July 2002 and marked out of date by its author); checked 4 November 2026
- ACM SIGPLAN – Most Influential POPL Paper Award, 2007 entry for POPL 1997: George Necula, Proof-carrying Code; checked 4 November 2026
- Zexun Wang – Proof-Carrying Agent Actions (arXiv preprint, 2 June 2026): proposed runtime-governance approach with a reference implementation, not a production deployment; checked 4 November 2026
- Sonar – State of Code Developer Survey (press release, January 2026): 96% of developers do not fully trust that AI-generated code is functionally correct, 48% always check it before committing; self-reported, and not evidence that attached artifacts close a trust gap; checked 4 November 2026