Skip to content

bootstrap.md

Latest commit

 

History

History
183 lines (135 loc) · 6.7 KB

bootstrap.md

File metadata and controls

183 lines (135 loc) · 6.7 KB
Raw

tnC Bootstrap Chain — Trust From Zero

The Problem

Every major compiler today has an opaque trust chain:

??? → Some 1970s PDP-11 assembler → early C compiler → modern C compiler → everything

Ken Thompson's famous 1984 talk "Reflections on Trusting Trust" showed that a compiler can be trojaned in a way that perpetuates itself invisibly. If you can't audit every step from bare metal to your compiler, you can't fully trust it.

Our Solution: Fully Auditable Bootstrap

tnC's bootstrap chain is designed so that one person can read and verify every byte from raw hex to a self-hosting compiler:

Step 0a: hex0 (313 bytes of hand-written hex → binary converter)
         The only thing you need to audit. A single afternoon's work.
    ↓
Step 0b: hex1 (hex0 + label support, built by hex0)
         Enables writing code without computing jump offsets by hand.
    ↓
Step 0c: tnc_asm (full x86-64 assembler, built by hex1)
         Two-pass, label resolution, ELF binary output.
    ↓
Step 1:  tnc_boot (minimal tnC compiler, written in assembly, built by tnc_asm)
         Understands a subset of tnC sufficient for Step 2.
    ↓
Step 2:  tnc (full self-hosting compiler, written in tnC, built by tnc_boot)
         All language features. Can compile itself.

No C compiler is used at any point. The only external tools are POSIX shell utilities (sed, printf) to perform the initial hex→binary transcription of hex0 — a trivial text transformation that any tool could do.

Stage 0a: hex0 — The Trust Anchor

File: bootstrap/stage0/hex0_x86-64.hex (313 bytes)

hex0 is a minimal program that reads hexadecimal character pairs from stdin and outputs the corresponding raw bytes to stdout. It handles:

  • Hex digits: 0-9, A-F, a-f
  • Comments: ## to end of line
  • Whitespace: spaces, tabs, newlines (ignored between hex pairs)

hex0 is the trust root. It is written as annotated hexadecimal — every byte of the ELF header, every opcode, every jump offset is documented in the source file. You can verify it by:

  1. Reading the annotated hex alongside Intel's x86-64 ISA manual
  2. Disassembling the binary with any independent tool (ndisasm, objdump)
  3. Tracing execution in a debugger or emulator (strace, gdb, qemu)
  4. Self-rebuild test: hex0 < hex0_x86-64.hex > hex0_copy && diff hex0 hex0_copy — the output must be byte-identical to the input binary

hex0 internal structure

Offset  Size  Content
0x00    64    ELF header (ELFCLASS64, x86-64, entry=0x400078)
0x40    56    Program header (PT_LOAD, RWX, vaddr=0x400000)
0x78    193   Code: read stdin → parse hex → nybble pair → write stdout
              Uses r12 for nybble accumulator (-1=empty, 0-15=pending)
              Stack buffer for single-byte read/write
              Handles ## comments, all whitespace
Total:  313 bytes

Stage 0b: hex1 — Hex With Labels

File: bootstrap/stage0/hex1_x86-64.hex

hex1 extends hex0 with two features:

  • :name — Define a label at the current byte position
  • %name — Emit a 32-bit little-endian relative offset to that label (computed from the byte after the 4-byte field, suitable for x86 jmp/call)

This is a two-pass design:

  • Pass 1: Scan input, record label positions, count output bytes
  • Pass 2: Emit bytes, resolve %name references

hex1 is written in hex0 format and built by hex0 itself.

Stage 0c: tnc_asm — The Assembler

File: bootstrap/stage0/tnc_asm.asm (reference), built from hex1-format source

A full x86-64 assembler supporting:

  • All registers (rax-r15, 8/16/32/64-bit forms)
  • Common instructions (mov, add, sub, cmp, jmp, jcc, call, ret, push, pop, syscall, etc.)
  • Labels and forward references
  • Directives (.text, .data, .byte, .word, .dword, .qword, .ascii, .asciz, .equ, .global)
  • Two-pass assembly with fixup resolution
  • ELF binary output

Stage 1: tnc_boot — Bootstrap Compiler

File: bootstrap/stage1/tnc_boot.asm

A minimal tnC compiler written in x86-64 assembly. It compiles a subset of tnC sufficient to compile the Stage 2 self-hosting compiler:

Supported: Integer types, functions, if/else/while/for/loop, pointers, arrays, structs (no methods), enums (C-style), string literals, basic operators, inline assembly, module system.

Deferred to Stage 2: Generics, traits, pattern matching, closures, defer, operator overloading, error propagation (?).

Pipeline: Lexer → Parser → Codegen → ELF output (no IR, no optimizer).

Stage 2: tnc — Self-Hosting Compiler

Directory: compiler/

The full tnC compiler written in tnC itself. Seven-phase pipeline:

  1. Lexer (lexer/lexer.tnc) — 80+ token types, nested comments, all literals
  2. Parser (parser/parser.tnc) — Recursive descent, full AST, precedence climbing
  3. Sema (sema/sema.tnc) — Type checking, symbol resolution, scope analysis
  4. IR (ir/ir.tnc) — 30+ opcodes, SSA-style intermediate representation
  5. Optimize — Constant folding, dead code elimination
  6. Codegen (codegen/codegen.tnc) — x86-64, register allocation, instruction selection
  7. Linker (linker/linker.tnc) — Full ELF output with sections and relocations

Verification

Self-rebuild test (hex0)

./build.sh hex0
./build/stage0/hex0 < bootstrap/stage0/hex0_x86-64.hex > /tmp/hex0_copy
diff build/stage0/hex0 /tmp/hex0_copy  # must be identical

Reproducible build

./build.sh seed
cp build/stage0/hex0 /tmp/hex0_1
./build.sh clean
./build.sh seed
diff /tmp/hex0_1 build/stage0/hex0  # must be identical

Diverse double compilation

# Build compiler C1 with tnc_boot
./build/stage1/tnc_boot compiler/main.tnc -o /tmp/tnc_c1
# Build compiler C2 with C1
/tmp/tnc_c1 compiler/main.tnc -o /tmp/tnc_c2
# Build compiler C3 with C2
/tmp/tnc_c2 compiler/main.tnc -o /tmp/tnc_c3
# C2 and C3 must be byte-identical
diff /tmp/tnc_c2 /tmp/tnc_c3  # must be identical

This proves that the compiler's output is a fixed point — it produces the same binary regardless of which correct compiler compiled it.

What About the Shell?

The POSIX shell (sh/bash/dash) and utilities (sed, printf) used for the initial hex0 transcription are not part of the trust chain for any compiler or code generator. They perform two trivial text operations:

  1. Strip comments from a text file
  2. Convert hex character pairs to bytes

These operations are semantically transparent — they don't interpret, compile, or transform any program logic. You could perform them by hand with a hex editor, or with a hardware ROM programmer. The hex0 binary IS the trust anchor; the shell merely transcribes it from human-readable form.

Once hex0 exists, the shell is never used again in the compilation chain.