government / PLAN.md

@ 60772087cdbbe3e7543eaf73a6f0ffc9a26570c7 | 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/*.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/*.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/*.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.**

## 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. **Lowering and raising** (`ast`)
    - Build: `Lower(program []sexpr.Value) *Tree`, which classifies reserved names into ns 0 and numbers nodes in pre-order; `Raise(*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: `Raise(Lower(p))` equals `p` for every `testdata` program, and `'+` raises to the symbol `+`.
16. **Layering** (`ast`)
    - Build: `Layer(*Tree) Layers`, which computes depth n, inserts red-tape chains under shallow atoms and empty lists, and returns per-depth node sets plus parent→child edges.
    - Learn: why the policy tree forces every leaf to depth n (RFC 5280 §6.1.3 step d.3 pruning), and how padding answers that.
    - Done when: the design's worked example `(+ 1 (* 2 3))` produces exactly its nine nodes and the edges in its table.
17. **Unlayering** (`ast`)
    - Build: `Unlayer(Layers) (*Tree, error)`, which rebuilds the tree from depth sets and edges, strips red tape, 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 (red tape with two children, an atom with a real child, `.` 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.
    - 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, lower, layer, then one cert per depth with that depth's policies and the mappings for its outgoing edges; per-depth keys from the seed; PEM with the source as a header comment. 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.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; 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, and pruning removes a dead-end branch.
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 and every mapping produced an edge (else an orphaned-policy error naming the OID); mappings in cert *n* rejected; `anyPolicy` asserted anywhere 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 a strict-check error, not a shorter program.
30. **The full pipeline** (`cmd/government`)
    - Build: `government run`: load → ratify → policy graph → `Unlayer` → `Raise` → 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/*.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 lowering 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_print -x509_strict` (and `-crl_check` with repeal CRLs) on compiled programs; parse its printed policy tree and compare with ours.
    - 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.**