@ 29fbe69f4da4ce1dc5603c685ced1955b2808761 | history
# GOVERNMENT Implementation Plan
Nov 14, 2026
## How to use this plan
The plan builds GOVERNMENT in 39 small steps across 8 phases, with a running program at the end of every phase. It is ordered for learning: the Lisp core comes first with no certificates, so the language works before PKI enters; then certificates are built before they are validated.
**Each step has**
- **Build:** the code, in packages named as in DESIGN.md.
- **Learn:** the concept the step teaches, and where to read about it.
- **Done when:** a test that proves the step works. Each step should be one reviewable commit of roughly 100–300 lines, tests included.
**Review conventions**
- Every step ends with `go test ./...` green. No step depends on a later one.
- Tests come with the code: Go table tests for internals, `testdata/*.gov.lisp` files for language behavior.
- Each commit message names its step number, e.g. `step 12: tail calls via trampoline`.
- Standard library only (Go 1.24+). The one-off prototype from the design phase is not reused.
### Phases at a glance
| Phase | Steps | Milestone at the end |
| --- | --- | --- |
| 1. Lisp core | 1–13 | `testdata/*.gov.lisp` passes, run straight from source text |
| 2. AST and OIDs | 14–17 | Any program converts to a layered, padded OID tree and back |
| 3. Building certificates | 18–22 | `government compile` writes a `.gov` file that `openssl` can print |
| 4. Ratification | 23–26 | A tampered, expired or misordered `.gov` file is rejected |
| 5. Policy processing | 27–30 | `government run prog.gov` works end to end; tests switch to the full pipeline |
| 6. Tooling | 31–32 | `tree`, `decompile` and `verify` commands |
| 7. Civic features | 33–36 | Notes, authorship and repeal |
| 8. Hardening | 37–39 | Shared subexpressions, stress, golden and OpenSSL cross-check tests |
Reading list used throughout: RFC 5280 (X.509 profile and path validation), RFC 9618 (policy graph), the Go `crypto/x509` docs, and, for the language side, *Structure and Interpretation of Computer Programs* chapter 4 (the metacircular evaluator).
## Phase 1: Lisp core (steps 1–13)
Build a complete GOVERNMENT evaluator that reads ordinary Lisp text. No certificates yet: this isolates the programming-language ideas, and every later phase reuses this evaluator unchanged.
1. **Module skeleton**
- Build: `go.mod` (Go 1.24), empty packages `sexpr`, `eval`, `cmd/government`, a `Makefile` with `test` and `vet`.
- Learn: Go module layout; why `internal/` versus public packages.
- Done when: `go test ./...` and `go vet ./...` pass on the empty tree.
2. **Values and printer** (`sexpr`)
- Build: a `Value` interface with Int, Float, String, Bool, Symbol, Pair, Nil, and a placeholder Function; `Print(Value) string` covering proper lists, dotted pairs, float formatting with a guaranteed dot, string escapes.
- Learn: cons cells; how lists are just pairs ending in `()`; tagged unions in Go via interfaces and type switches.
- Done when: table tests print `(1 2 3)`, `(1 . 2)`, `(1 2 . 3)`, `1.0`, `"a\"b"`.
3. **Tokenizer** (`sexpr`)
- Build: a lexer emitting `(`, `)`, `'`, `.`, atoms, strings (with `\u{…}`), and comments, each with line and column.
- Learn: lexical analysis; why tokens carry positions (error messages now, notes in Phase 7).
- Done when: tests cover nested parens, escapes, Unicode, and an unterminated string error.
4. **Reader** (`sexpr`)
- Build: a recursive-descent parser from tokens to `Value`; `'x` becomes `(quote x)`; dotted pairs; integer vs float vs symbol classification by the design's grammars.
- Learn: recursive descent; "code is data" (homoiconicity): the reader's output is both the program and an ordinary list.
- Done when: `Print(Read(s)) == normalize(s)` for a corpus of inputs, and malformed input (`(1 . )`, `)`) gives positioned errors.
5. **Environments** (`eval`)
- Build: an immutable linked list of bindings (`Env{name, value, parent}`), `Lookup`, `Extend`.
- Learn: lexical scope as a chain of frames; why an immutable chain gives cheap closures and no aliasing bugs. Read SICP §4.1.3.
- Done when: tests show shadowing and that extending a child never affects the parent.
6. **Evaluator skeleton** (`eval`)
- Build: `Eval(expr, env)` for self-evaluating atoms, symbol lookup, `quote`, and `if` (2 or 3 operands, Scheme truthiness).
- Learn: the eval/apply loop; special forms versus function calls; why `if` cannot be a function.
- Done when: `(if 0 1 2)` is `1`, `(if F 1)` is `()`, and `(if T 1 (car '()))` never evaluates the else branch.
7. **Arithmetic** (`eval`)
- Build: `+ - * /` as builtin function values; int/float promotion; int64 overflow detection; truncating integer division; divide-by-zero and NaN/Inf errors.
- Learn: numeric towers; checked arithmetic (detecting overflow without wider integers); first-class builtins.
- Done when: `(+)` is `0`, `(- 5)` is `-5`, `(/ 7 2)` is `3`, `(/ 7.0 2)` is `3.5`, and `(* 9223372036854775807 2)` errors.
8. **Comparisons, lists and strings** (`eval`)
- Build: `< > <= >= == !=`, `not`, `cons car cdr`, `strlen strcat str?`.
- Learn: structural equality on pairs; why comparing functions is refused; strings as code points, not bytes.
- Done when: `(== '(1 2) '(1 2))` is `T`, `(== 1 1.0)` is `T`, `(strlen "héllo")` is `5`.
9. **Lambda and application** (`eval`)
- Build: closures capturing the current `Env`; fixed-arity application; argument evaluation left to right.
- Learn: closures as code plus environment; lexical vs dynamic scope.
- Done when: the design's scoping test `(g 2)` returns `1`, and arity mismatches error.
10. **Define and sequential scope** (`eval`)
- Build: `define` at top level and at the start of a lambda body; self-visible binding (a slot filled after the value is computed); rebinding in the same scope is an error.
- Learn: `let*` vs `letrec`; how self-recursion needs the name visible before the value exists, and how mutual recursion is excluded by construction.
- Done when: factorial works; `(define x (+ x 1))` errors; the design's mutual-recursion example errors as unbound.
11. **and / or** (`eval`)
- Build: short-circuit special forms returning values (Scheme style).
- Learn: why short-circuiting forces these to be special forms rather than functions.
- Done when: `(or F 7)` is `7` and `(and F (car '()))` is `F` without error.
12. **Tail calls** (`eval`)
- Build: rewrite `Eval` as a loop that continues in place for `if` branches and closure bodies (a trampoline).
- Learn: proper tail calls; why a naive recursive evaluator overflows the Go stack.
- Done when: a tail-recursive countdown from 1,000,000 completes.
13. **Errors and the source-mode test runner**
- Build: typed errors with codes (`E-UNBOUND`, `E-ARITY`, …) and an optional source location; a test runner that reads `testdata/*.gov.lisp`, parses `;=>` and `;=!` annotations, and runs each top-level form through reader + evaluator.
- Learn: designing errors as data; golden-style tests that read like documentation.
- Done when: the design doc's example test files all pass. **Milestone: the language works.**
**Extra: the `govlisp` REPL** (`cmd/govlisp`). Added between Phases 1 and 2. `govlisp` with no arguments is an interactive REPL; `govlisp prog.gov.lisp` runs a file. A form may span lines: the reader marks syntax errors caused only by input ending early as incomplete, and the REPL reads another line instead of reporting them. Errors name the failing subexpression and keep the session going.
## Phase 2: The AST and OID encoding (steps 14–17)
Define the program tree that certificates will carry, and prove it round-trips, before any certificate exists. Everything here is pure data structures, so it is fast to test.
14. **Node OIDs** (`ast`)
- Build: the `GOV` root constant; `EncodeOID(ns, id, text) x509.OID` and `DecodeOID(x509.OID) (ns, id, text, error)`; payload grammar checks per namespace.
- Learn: what an OID is (a path in a global naming tree), arcs, the `2.25` UUID arc, and how Go's `x509.OID` holds arcs too big for `uint64`.
- Done when: every row of the design's namespace table round-trips; surrogates, empty symbols and `"1."` as a float are rejected.
15. **ToTree and FromTree** (`ast`)
- Build: `ToTree(program []sexpr.Value) *Tree`, which classifies reserved names into ns 0 and numbers nodes in pre-order; `FromTree(*Tree) []sexpr.Value`, the inverse, which also keeps a map from each produced value to its node for error locations.
- Learn: an AST as a separate structure from source text; why sibling order must be explicit data once you leave a text format.
- Done when: `FromTree(ToTree(p))` equals `p` for every `testdata` program, and `'+` becomes the symbol `+`.
16. **Layering** (`ast`)
- Build: `Layer(*Tree) Layers`, which computes depth n and returns per-depth node sets plus parent→child edges. No padding: certs 2..n assert `anyPolicy`, and the validator copies each unmapped leaf down.
- Learn: why the policy tree forces every leaf to depth n (RFC 5280 §6.1.3 step d.3 pruning), and how `anyPolicy` (RFC 9618 step d.2) makes the validator do the padding.
- Done when: the design's worked example `(+ 1 (* 2 3))` produces exactly its seven nodes and the edges in its table.
17. **Unlayering** (`ast`)
- Build: `Unlayer(Layers) (*Tree, error)`, which rebuilds the tree from depth sets and edges, skips copies (a child with its parent's OID), orders children by id, and enforces decode rules 1–6. Accept a node with several parents (a DAG).
- Learn: validating untrusted structure; Phase 5's policy graph will feed this function directly.
- Done when: `Unlayer(Layer(t))` equals `t` for every `testdata` program, and each broken-structure case (a copy with a non-copy child, an atom with a real child, a list node with no elements, `.` in the wrong place) gives its own error.
## Phase 3: Building certificates (steps 18–22)
Learn X.509 by producing it: first a plain two-certificate chain, then the bytes of the two extensions Go cannot write, then the whole transpiler.
18. **Your first chain** (`lisp2gov`, experiment-style)
- Build: an anchor and one child cert with `x509.CreateCertificate`, Ed25519 keys from a fixed seed, fixed dates and serials; PEM output.
- Learn: the anatomy of a certificate: TBSCertificate, issuer and subject names, validity, subject public key, extensions and the critical flag, the signature over the TBS bytes. Also self-signed vs issued, basicConstraints, keyUsage, SKI/AKI. Read RFC 5280 §4.1 and §4.2.1.1–4.2.1.3, 4.2.1.9. Run `openssl x509 -text -noout` on your output and match every line to a field.
- Done when: two runs produce byte-identical PEM, and `child.CheckSignatureFrom(anchor)` passes.
19. **DER by hand** (`internal/der`)
- Build: a tiny TLV writer (tag, short and long length forms, SEQUENCE, OBJECT IDENTIFIER, UTF8String).
- Learn: ASN.1 as a schema language and DER as its one canonical encoding; why canonical encoding matters for signatures; base-128 OID arcs (compare your encoder with `x509.OID.MarshalBinary`).
- Done when: your encoding of small OIDs and sequences matches `encoding/asn1.Marshal` byte for byte.
20. **policyMappings extension** (`lisp2gov`)
- Build: encode `PolicyMappings ::= SEQUENCE OF SEQUENCE { issuerDomainPolicy, subjectDomainPolicy }` and attach it as a critical `ExtraExtensions` entry (OID `2.5.29.33`).
- Learn: why Go 1.24 parses this extension but does not write it; what "critical" means for a relying party. Read RFC 5280 §4.2.1.5.
- Done when: `ParseCertificate` returns your mappings in `PolicyMappings` and lists no unhandled critical extensions.
21. **certificatePolicies extension** (`lisp2gov`)
- Build: hand-encode `certificatePolicies` (OID `2.5.29.32`) as a SEQUENCE of PolicyInformation, OIDs only for now, leaving room for qualifiers in Phase 7. Cert 1 lists the top-level nodes; certs 2..n list `anyPolicy` (`2.5.29.32.0`).
- Learn: policy OIDs as assertions a CA makes about a certificate, which is the hook GOVERNMENT abuses. Read RFC 5280 §4.2.1.4.
- Done when: `ParseCertificate` returns the OIDs in `Policies`, including one with the 128-bit `GOV` arc.
22. **The transpiler** (`lisp2gov`, `cmd/government`)
- Build: `Compile(src) ([]byte, error)`: read, build the tree, layer, then one cert per depth (cert 1 with the top-level nodes, the rest with `anyPolicy`), each with the mappings for its depth's outgoing edges; per-depth keys from the seed; PEM, with the source above the first block if `-source` is given. Wire up `government compile`.
- Learn: how a certification path is a chain of issuer→subject links; how a whole program becomes n+1 signed objects.
- Done when: `government compile examples/sq.gov.lisp -o sq.gov` writes a file that `openssl x509` can print block by block, and compiling twice gives identical bytes. **Milestone: GOVERNMENT programs exist.**
## Phase 4: Ratification (steps 23–26)
Now read `.gov` files back and decide whether to trust them. This is the part of RFC 5280 §6.1 that ordinary TLS clients run on every connection.
23. **PEM loader** (`ratify`)
- Build: `Load([]byte) ([]*x509.Certificate, error)`; ignore text between blocks; reject non-`CERTIFICATE` blocks and files with fewer than two certs.
- Learn: PEM as base64-wrapped DER with labels; why the bytes inside are what gets signed, not the text.
- Done when: files from step 22 load; a file with a `PRIVATE KEY` block is rejected.
24. **Chain checks** (`ratify`)
- Build: for each cert *i*: issuer equals the subject of *i−1*, `CheckSignatureFrom` passes, parents are CA with keyCertSign, no cert is self-issued, no unknown critical extensions, and `policyConstraints` / `inhibitAnyPolicy` are absent.
- Learn: basic path processing (RFC 5280 §6.1.3 a–c, §6.1.4 k–n); why name chaining and signatures are separate checks; what a relying party must do with a critical extension it does not understand.
- Done when: a mutation table test (flip a signature byte, swap two certs, clear `IsCA`, add an unknown critical extension) gives `E-TAMPERED` or the specific chain error for each.
25. **Validity windows** (`ratify`)
- Build: check every cert's `NotBefore`/`NotAfter` against the check time; the `-at` flag; `E-NOT-IN-FORCE` and `E-LAPSED`.
- Learn: why validity is per certificate, so a chain's lifetime is the overlap; UTCTime vs GeneralizedTime (RFC 5280 §4.1.2.5 switches encodings at 2050, which is why 9999-12-31 works).
- Done when: a cert valid in 2027 passes with `-at 2027-06-01T00:00:00Z` and fails with each error on either side.
26. **Trust anchors and pinning** (`ratify`)
- Build: the anchor must be self-signed; optional `-anchor` compares SubjectPublicKeyInfo bytes with a given cert or public key PEM.
- Learn: a trust anchor is a key you already trust, not really a certificate; why pinning a key outlives pinning a cert.
- Done when: a program built from the same seed but with different dates still matches its pin, and one from another seed does not. **Milestone: tampered, expired and foreign programs are refused.**
## Phase 5: Policy processing and the full pipeline (steps 27–30)
Implement the algorithm that turns a certificate chain into a program. This is the most important code in the project; build it in two halves so each can be checked against the RFC on its own.
27. **Policy graph without mappings** (`policy`)
- Build: levels 0..n; the `anyPolicy` root expecting `{anyPolicy}`; RFC 9618 step (d): attach each policy of cert *i* to every depth-*i−1* node expecting it, else to an `anyPolicy` parent; step (d)(2): `anyPolicy` in cert *i* creates every expected policy that has no node yet; repeated pruning of childless nodes at depth *i−1* or less; step (e) (no extension means an empty graph); explicit policy, so an empty graph fails.
- Learn: what the valid policy tree/graph means in real PKI (which policies hold along the whole path) and why RFC 9618 replaced the tree with a DAG. Read RFC 5280 §6.1.2–6.1.3 and RFC 9618 §3–5.
- Done when: hand-built chains where every cert asserts the same policy keep it, a chain where one cert drops it yields failure, pruning removes a dead-end branch, and an atom at depth 1 survives to depth 3 only when certs 2 and 3 assert `anyPolicy` (the design-phase prototype's `copyonly`/`nocopy` chains).
28. **Policy mappings** (`policy`)
- Build: RFC 5280 §6.1.4 (a)–(b): reject `anyPolicy` in mappings; for each depth-*i* node that is an `issuerDomainPolicy`, set its expected set to the mapped `subjectDomainPolicy` values; skip this step for cert *n*.
- Learn: what mappings mean between real CAs ("your policy X is equivalent to my policy Y"), and why that is exactly a parent→child edge.
- Done when: the design's worked example produces its tree exactly, checked against the table, and a child mapped from two parents gets two parents.
29. **Strict check and limits** (`policy`)
- Build: after processing, every asserted policy is a node at its depth, every mapping produced an edge, and node ids are exactly 1..N (else an orphaned-policy error naming the OID); mappings in cert *n* rejected; `anyPolicy` missing from a cert 2..n, or asserted in cert 1, rejected; `-max-nodes` budget.
- Learn: how silent pruning makes RFC processing forgiving, and why a language needs it to be unforgiving; policy-processing DoS (CVE-2026-32281 in Go).
- Done when: deleting one mapping from a valid file gives an error (a gap in the node ids, or a list node left with no elements), not a shorter program, except for the subtree with the highest ids, which the test documents.
30. **The full pipeline** (`cmd/government`)
- Build: `government run`: load → ratify → policy graph → `Unlayer` → `FromTree` → evaluate; errors carry the node OID and depth; exit codes 1 and 2. Switch the test runner to compile every `testdata` file and run the resulting bytes.
- Learn: how the stages compose into a compiler-like pipeline with a trust boundary in the middle.
- Done when: every `testdata/*.gov.lisp` file passes through the full pipeline with no test changes. **Milestone: GOVERNMENT runs.**
## Phase 6: Tooling (steps 31–32)
Make programs inspectable. These commands are also the best debugging aids for Phase 7.
31. **tree and decompile** (`cmd/government`, `gov2lisp`)
- Build: `government tree` prints the policy graph with `GOV` abbreviated, payloads decoded and depth shown; `government decompile` prints Lisp from the decoded AST via the `sexpr` printer. Add the round-trip test: `decompile(compile(src))` equals the normalized source for every `testdata` file.
- Learn: decompilation as the inverse of every compile step; why a round-trip test catches bugs in both directions at once.
- Done when: `government tree` on the worked example matches the design doc's drawing, and the round-trip test passes.
32. **verify** (`cmd/government`)
- Build: `government verify` ratifies and decodes without evaluating, then prints a certificate of ratification: anchor subject, key fingerprint (SHA-256 of the SPKI), window in force (the overlap of all validity periods), depth and node count.
- Learn: fingerprints as stable identifiers for keys; separating "is it lawful?" from "what does it do?".
- Done when: `verify` exits 0 on valid files and 2 with the right error on each Phase 4 mutation.
## Phase 7: Civic features (steps 33–36)
Add the four features that use X.509 for more than structure. Effective dates already exist from step 25 (`-effective` and `-expires` only need compile flags, added in step 34), so this phase covers notes, authorship and repeal.
33. **Notes** (`sexpr`, `lisp2gov`, `policy`)
- Build: the reader keeps comments and attaches each to the form on the next line or the form it trails; the certificatePolicies encoder adds user-notice qualifiers (`1.3.6.1.5.5.7.2.2`), splitting text over 200 characters; a raw-extension decoder reads them back; `tree`, errors and `decompile` show them.
- Learn: policy qualifiers and why relying parties may ignore them (they never affect validation); working with extension bytes Go parses only partly.
- Done when: a 450-character comment survives compile → decompile intact, and an error inside a noted form prints its note.
34. **Authorship** (`lisp2gov`, `cmd/government`)
- Build: `-key` (Ed25519 PKCS#8), `-author "Name <email>"` into the anchor subject and subjectAltName, per-depth key derivation SHA-256(seed ‖ "GOVERNMENT" ‖ i), the `-effective` and `-expires` flags; `verify` reports "ratified by nobody in particular" for the default seed.
- Learn: private keys, PKCS#8, and key derivation; why the default seed being public makes every default-built program forgeable.
- Done when: two authors' builds of one source differ only in keys and names, each verifies with its own `-anchor` pin, and neither verifies with the other's.
35. **Writing repeals** (`cmd/government`)
- Build: `government repeal prog.gov -depth i`: re-derive the key of cert *i−1*, then `x509.CreateRevocationList` listing serial *i+1* with a CRLReason, `thisUpdate`, `nextUpdate` and a revocation time. Every CA cert gains `cRLSign` in its keyUsage.
- Learn: CRLs, why the issuer (not the anchor) revokes, serial numbers being unique only per issuer, reason codes. Read RFC 5280 §5.
- Done when: `openssl crl -text` prints your CRL, and its signature verifies against cert *i−1*.
36. **Checking repeals** (`ratify`)
- Build: `-crl` (repeatable); match each CRL to its issuer in the path, verify with `RevocationList.CheckSignatureFrom`, reject if the check time is past `nextUpdate` (`E-STALE-REPEALS`), and reject listed certs whose revocation time has passed (`E-REPEALED`, so future times act as scheduled repeals).
- Learn: revocation checking as a separate trust decision; fail-open vs fail-closed, and why GOVERNMENT picks fail-closed.
- Done when: a table test covers repeal of each depth, a scheduled repeal before and after its date, a stale CRL, and a CRL signed by the wrong key. **Milestone: the full design is implemented.**
## Phase 8: Hardening and interop (steps 37–39)
Finish with the tests that prove GOVERNMENT is deterministic, survives large programs, and agrees with an independent PKI implementation.
37. **Shared subexpressions** (`lisp2gov`, `eval`)
- Build: an opt-in `-share` compile flag that hash-conses identical subtrees at the same depth into one node with several parents; confirm `Unlayer` and the evaluator walk the DAG without copying.
- Learn: hash-consing; how RFC 9618's graph makes sharing cheap where RFC 5280's tree would duplicate it.
- Done when: every `testdata` file gives the same results with and without `-share`, and a program with 20 nested copies of one subexpression stays small.
38. **Stress and golden tests**
- Build: generated programs 200 deep (201 certs) and 1,000 arguments wide; `-max-nodes` tests; one checked-in golden `.gov` compared byte for byte.
- Learn: why reproducible output is a security property (anyone can rebuild and compare), and how golden files catch unintended format changes.
- Done when: stress tests finish in under a few seconds, and the golden test fails if any byte of the encoding changes.
39. **OpenSSL as an oracle** (optional, skipped when `openssl` is absent)
- Build: run `openssl verify -policy_check -explicit_policy -policy 2.5.29.32.0 -x509_strict` (and `-crl_check` with repeal CRLs) on compiled programs and on deliberately broken ones. Without `-policy 2.5.29.32.0`, OpenSSL treats the acceptable set as empty and rejects everything; its `-policy_print` shows only top-level policies, so compare accept/reject decisions, not trees.
- Learn: differential testing against an independent implementation; where implementations disagree on edge cases.
- Done when: OpenSSL accepts every valid program, prints the same set of policies at each depth, and rejects each repealed program. **Milestone: done.**