git.nmyk.io / government

@ 27e33aecf4976d7646339e35c5fff6755a29497c

refs | commits



README.md

# GOVERNMENT

GOVERNMENT is a small Lisp whose programs are chains of X.509 certificates,
stored in `.gov` files.

The interpreter validates the chain as an X.509 certification path, then reads
its certificate policies as the program and evaluates them. If the chain does
not validate, the program does not run.

Each expression in a program is one certificate policy OID. Each pair of
parentheses is a set of policy mappings. The program's nesting depth is the
length of the chain.

## Terms

| Term         | Meaning                                                                                                       |
| ------------ | ------------------------------------------------------------------------------------------------------------- |
| GovLisp      | The Lisp source language. Source files use the extension `.gov.lisp`.                                         |
| Compile      | Turn GovLisp source into a `.gov` file.                                                                       |
| Ratify       | Validate a `.gov` file as a certification path. A program that ratifies is "lawful".                          |
| Trust anchor | The one self-signed certificate at the top of the chain.                                                      |
| Depth        | A certificate's position below the trust anchor. The anchor is depth 0.                                       |
| Node         | One expression of the program, stored as one policy OID.                                                      |
| Copy         | A node the validator creates to carry an atom down to the bottom of the tree. The interpreter ignores copies. |
| Repeal       | Revoke a program with a certificate revocation list (CRL).                                                    |

## Install

You need Go 1.24 or later.

1. Clone the repository.
2. In its root directory, run `make bin` to build the commands into `./bin`, or
   `make install` to install them.

The Go code lives in `src/`, which is the module root; the Makefile runs every
Go command there.

There are two commands:

- `government` compiles, checks, inspects, runs and repeals `.gov` files.
- `govlisp` runs GovLisp source directly, with no certificates, and has an
  interactive REPL.

## Quick start

1. Write a program, for example `square.gov.lisp`:

   ```lisp
   ; The square of a number.
   (define sq (lambda (n) (* n n)))
   (sq 12)
   ```

2. Compile it:

   ```sh
   government compile square.gov.lisp -o square.gov
   ```

3. Run it:

   ```sh
   government square.gov
   ```

   It prints `144`.

4. Inspect the certificates with any X.509 tool, for example `openssl x509
   -text`.

5. Show the program as a policy tree:

   ```sh
   government tree square.gov
   ```

6. Get the source back:

   ```sh
   government decompile square.gov
   ```

## The language

GovLisp is a strict Lisp with lexical scope. All values are immutable. There is
no I/O, no mutation and no macro system.

### Values

| Type       | Example                        | Notes                                                                          |
| ---------- | ------------------------------ | ------------------------------------------------------------------------------ |
| Integer    | `-42`                          | 64 bits. Overflow is an error.                                                 |
| Float      | `3.25`                         | 64 bits. A NaN or infinite result is an error. Floats always print with a dot. |
| String     | `"hi\n"`                       | Escapes: `\"` `\\` `\n` `\t` `\u{1F3DB}`.                                      |
| Boolean    | `T`, `F`                       |                                                                                |
| Symbol     | `foo`                          |                                                                                |
| Pair       | `(1 2 3)`, `(1 . 2)`           | A list is a chain of pairs ending in `()`.                                     |
| Empty list | `()`                           |                                                                                |
| Function   | `#<lambda sq>`, `#<builtin +>` | Builtins are ordinary values, so `(define add +)` works.                       |

Only `F` is false. Everything else is true, including `0`, `""` and `()`.

### Special forms

| Form                       | Result                                                                    |
| -------------------------- | ------------------------------------------------------------------------- |
| `(quote d)`, `'d`          | `d` itself, unevaluated.                                                  |
| `(if c a b)`               | `a` if `c` is not `F`, otherwise `b`. With no `b`, the result is `()`.    |
| `(define name expr)`       | Binds `name` and returns the symbol `name`.                               |
| `(lambda (p1 … pk) body…)` | A closure with a fixed number of parameters.                              |
| `(and x…)`                 | Stops at the first `F`; otherwise returns the last value. `(and)` is `T`. |
| `(or x…)`                  | Returns the first value that is not `F`; otherwise `F`. `(or)` is `F`.    |

### Builtin functions

| Group      | Functions                                                                                                       |
| ---------- | --------------------------------------------------------------------------------------------------------------- |
| Arithmetic | `+` `-` `*` `/`. Integers stay integers; any float makes the result a float. Integer `/` truncates toward zero. |
| Comparison | `<` `>` `<=` `>=`, each on two numbers.                                                                         |
| Equality   | `==` `!=`, each on any two values. `(== 1 1.0)` is `T`.                                                         |
| Logic      | `not`                                                                                                           |
| Lists      | `cons` `car` `cdr`                                                                                              |
| Strings    | `strlen` `strcat` `str?`                                                                                        |

### Definitions and scope

- `define` works at the top level and at the start of a lambda body.
- Definitions are sequential: each `define` sees the ones before it and itself,
  never the ones after it. So a function can call itself, but two functions
  cannot call each other.
- A name can be defined only once in a scope. A lambda parameter or an inner
  `define` may shadow an outer name.
- Tail calls use no extra stack, so recursive loops can run indefinitely.

### Output

Running a program evaluates its top-level forms in order and prints the value of
each one that is not a `define`, one per line.

## The `.gov` file

A `.gov` file holds PEM `CERTIFICATE` blocks: a trust anchor, then one
certificate for each depth of the program. The compiler writes the anchor first,
but the interpreter accepts the certificates in any order, because each
signature links a certificate to its parent.

- **Certificate 1** lists the top-level forms as its policies.
- **A list** is one node, with a policy mapping to each of its elements in the
  certificate at the list's depth.
- **Certificates 2 to n** list only `anyPolicy`. From that, the validator
  creates each mapped element, and copies each atom down one level so that
  nothing is pruned. The compiler writes nothing for these copies.
- **Comments** in the source become notes on their nodes, stored as RFC 5280
  user notices.
- **Keys** are Ed25519, and output is deterministic: the same source and options
  always produce the same bytes.

### OIDs

Every node OID has the form `GOV.<namespace>.<id>.<payload>`, where `GOV` is
`2.25.9665536045854453410170579537759926404`, a UUID arc.

| Namespace | Kind    | Payload                        | Example                        |
| --------- | ------- | ------------------------------ | ------------------------------ |
| 0         | Builtin | One fixed code                 | `+` is `GOV.0.7.21`            |
| 1         | Symbol  | The name's code points         | `foo` is `GOV.1.8.102.111.111` |
| 2         | Integer | The decimal text's code points | `-42`                          |
| 3         | Float   | The decimal text's code points | `3.14`                         |
| 4         | String  | The string's code points       | `"hi"`                         |

Ids are unique within a program. A certificate's policies are an unordered set,
so the ids are what record argument order.

### Shared subexpressions

RFC 9618 replaces RFC 5280's policy tree with a graph, in which one node can
have several parents. The compiler takes advantage of this: when the same list
appears under different parents at the same depth, it writes the list once and
gives it each of those parents. The file gets smaller and the program behaves
the same.

Pass `--no-share` to keep every copy instead.

## Ratification

The interpreter runs these checks before anything else. If one fails, the
program does not run and the exit code is 2.

| Error             | Cause                                                                               |
| ----------------- | ----------------------------------------------------------------------------------- |
| `E-MALFORMED`     | The file is not valid PEM, or holds a block that is not a certificate.              |
| `E-CHAIN`         | The certificates do not form one clean chain, or one has a forbidden extension.     |
| `E-TAMPERED`      | A signature does not verify.                                                        |
| `E-FOREIGN`       | The anchor's key does not match `--anchor`, or a CRL comes from another program.    |
| `E-NOT-IN-FORCE`  | The check time is before the program takes effect.                                  |
| `E-LAPSED`        | The check time is after the program expires.                                        |
| `E-REPEALED`      | A CRL revokes one of the program's certificates.                                    |
| `E-STALE-REPEALS` | A CRL is past its next update time.                                                 |
| `E-POLICY`        | The policies do not form a valid program, for example because a node is missing.    |
| `E-TOO-LARGE`     | The policy graph needs more nodes than `--max-nodes` allows (1,000,000 by default). |
| `E-DECODE`        | The policy graph is not a valid GovLisp tree.                                       |

A runtime error stops the program with exit code 1. The message gives the OID
and depth of the expression that failed, plus the nearest note if there is one.

| Runtime error      | Cause                                                               |
| ------------------ | ------------------------------------------------------------------- |
| `E-UNBOUND`        | A symbol is not bound in the current scope.                         |
| `E-SYNTAX`         | A special form is malformed.                                        |
| `E-SPECIAL-FORM`   | A special form's name is used as a value.                           |
| `E-NOT-A-FUNCTION` | The head of a call is not a function.                               |
| `E-ARITY`          | A call has the wrong number of arguments.                           |
| `E-TYPE`           | An argument has the wrong type.                                     |
| `E-ARITH`          | Overflow, division by zero, or a float result that is not a number. |
| `E-IMMUTABLE`      | A name is defined twice in the same scope.                          |

## Civic features

These features never change what a program computes. They decide when it may
run, and record who made it.

### Dates

`--not-before` and `--not-after` set when a program is in force. Each takes an
RFC 3339 time or a date, which means midnight UTC at the start of that day.

```sh
government compile law.gov.lisp -o law.gov \
    --not-before 2027-01-01 --not-after 2027-12-31
government law.gov --at 2027-06-01
```

`--at` sets the time to check against. It defaults to now.

### Authorship

1. Make an Ed25519 key:

   ```sh
   openssl genpkey -algorithm ed25519 -out ada.pem
   ```

2. Compile with the key and your name:

   ```sh
   government compile law.gov.lisp -o law.gov \
       --key ada.pem --author "Ada Lovelace <ada@example.org>"
   ```

3. Print the certificate of ratification:

   ```sh
   government verify law.gov
   ```

4. To run only programs by this author, pass `--anchor` with one of their
   programs, a certificate, or their public key:

   ```sh
   government law.gov --anchor ada.gov
   ```

> **Warning:** without `--key`, the compiler uses a public default key, so
> anyone can amend or repeal the program. `government verify` names the ratifier
> as `Public (Default Key)`.

### Repeal

1. Write a CRL that repeals the program, signed with the key that compiled it:

   ```sh
   government repeal law.gov --key ada.pem --reason superseded -o repeal.crl
   ```

2. Pass the CRL to the interpreter:

   ```sh
   government law.gov --crl repeal.crl
   ```

   The program is refused with `E-REPEALED`.

`repeal` also takes:

- `--at`: when the repeal takes effect. A future time schedules it.
- `--next-update`: when the CRL goes stale. The default is 9999-12-31, which
  makes the repeal permanent.
- `--last-update`: the CRL's issue time. Set it to rebuild an identical CRL.

### Notes

Comments in the source become notes in the certificates. `government tree` shows
them, and `government decompile` turns them back into comments.

`--no-comments` drops all comments, so `decompile` cannot restore them. It
cannot be combined with `--source`.

## Commands

| Command                                        | Does                                                                                         |
| ---------------------------------------------- | -------------------------------------------------------------------------------------------- |
| `government prog.gov`                          | Ratify, decode and run the program. `government run prog.gov` is the long form.              |
| `government verify prog.gov`                   | Ratify and decode the program without running it, and print its certificate of ratification. |
| `government tree prog.gov`                     | Print the policy tree, with notes.                                                           |
| `government decompile prog.gov`                | Print the GovLisp source, with notes as comments.                                            |
| `government compile prog.gov.lisp -o prog.gov` | Compile a program.                                                                           |
| `government repeal prog.gov -o repeal.crl`     | Write a CRL that repeals a program.                                                          |
| `govlisp`                                      | Start the REPL.                                                                              |
| `govlisp prog.gov.lisp`                        | Run GovLisp source, with no certificates.                                                    |

Every command that reads a `.gov` file also takes `--at`, `--anchor`, `--crl`
and `--max-nodes`. Long flags take two dashes. Run `government <command> --help`
for the full list.

### The REPL

On a terminal, the `govlisp` REPL has line editing and history, saved in
`~/.govlisp_history`.

- **Tab** completes a name. With nothing to complete, it indents by two spaces.
- **Ctrl-C** discards the form you are typing.
- **Ctrl-D** exits.

A form can span several lines, and an error does not end the session.

## Tests

| Command                                | Does                                                                               |
| -------------------------------------- | ---------------------------------------------------------------------------------- |
| `make check`                           | Runs `gofmt`, `go vet` and every test.                                             |
| `cd src && go test -short ./...`       | Runs every test except the largest shared-subexpression one.                       |
| `cd src && go test ./lisp2gov -update` | Rewrites the golden files. Use it only for a deliberate change to the file format. |
| `make oracle`                          | Builds an OpenSSL without its policy tree limit, and checks GOVERNMENT against it. |

Each program in `src/internal/lisptest/testdata/` is a GovLisp file: a `;=>`
comment gives a form's expected value, and `;=!` its expected error. The tests
compile each file and run it through the whole interpreter.

The OpenSSL tests use the `openssl` command. On macOS that is often LibreSSL,
and the tests skip. Set `GOVERNMENT_OPENSSL` to the path of an OpenSSL binary to
run them.

## Limits

- A program needs at least one top-level form.
- Lambdas take a fixed number of parameters.
- Functions cannot be mutually recursive.
- Stock OpenSSL refuses policy trees over 1,000 nodes, so it can only check
  small GOVERNMENT programs. `make oracle` builds one without that limit.
- OpenSSL refuses scheduled repeals, and CRLs issued after the check time.
  GOVERNMENT accepts both: a revocation time says when a repeal applies, and a
  newer CRL can still answer for an earlier date.

> **Warning:** the OpenSSL that `make oracle` builds is open to CVE-2023-0464.
> Use it only on programs you compiled yourself.

## References

- [RFC 5280](https://www.rfc-editor.org/rfc/rfc5280.html): X.509 certification
  path validation.
- [RFC 9618](https://www.rfc-editor.org/rfc/rfc9618.html): the policy graph that
  replaces RFC 5280's policy tree.