etcd-grove (branch lean) verifies etcd in Lean on top of
Perennial. Its proofs rest on axioms: Hoare triples (X.wp_proof : X.spec) of the Go functions
it does not verify (libraries such as zap, grpc, bbolt), opaque predicates those triples are written
in, and facts about package initialization. They are meant to be true of the real Go code, but are
not proved of it.
This repository proves each axiom true of some code: for every axiomatized function, a super-simple reference implementation, and a proof that it meets the function's spec. If an axiom cannot be met by any implementation, writing one here is where that shows up.
The reference implementations are Go, translated by etcd-grove's own Goose:
go/: a Go module.go/third_party/<module>/is a copy of a library at the version etcd pins (go.uber.org/zapv1.28.0), replacing it (go/go.mod), with the bodies of the functions etcd calls replaced by the simplest Go that meets their specs, each marked// refimpl:. Where the real code itself can be proved, the proof belongs in etcd-grove instead (the axioms become theorems there), ask8s.io/utils/clock's did. Every type and every other declaration is the real library's. It builds withgo build ./.... Where a body grows and would move the functions after it that etcd-grove translates with their bodies (whose docstrings give their positions), a//linedirective restores the real file's line numbers below it (apimachinery'sapi/errors/errors.go).go-k8s/: the same for the packages of etcd-grove'sk8s-apiserverGoose project (klog, component-base'stracing, apimachinery, api, apiserver), a module of its own because that project's dependencies are pinned at other versions (itsgo.modisexamples/k8s/etcd3/go.mod's, as is itsgo.sum), as etcd-grove keeps the two projects in separate Go modules.stdlib/src/: the same for standard-library packages etcd-grove translates (net/http,encoding/json,internal/bytealg): copies of the pinned toolchain's (go1.27.3) files, at theirGOROOTpaths, modified. Ago.modcannot replace the standard library, soetc/goose-refimpl.pytranslates with aGOROOTthat is the toolchain's, symlinked, with these files in place of its own.go/goose-config/(go-k8s/goose-config/): the Goose configuration of those packages: etcd-grove's (Code/**/*.toml), plus the replaced functions intranslate.etc/goose-refimpl.pyruns the pinned Goose (built from the pinned Perennial) on each module with its project's-lean-rootarguments and Go toolchain (etcd-grove'setc/goose.py), and compares the output with etcd-grove's checked-in names-only translation of each package. It must be a pure superset: every line of etcd-grove's translation unchanged (the reference implementation is a drop-in replacement of the package etcd-grove assumes). What it adds, the translated bodies and theirFuncUnfold/MethodUnfoldbindings, is written toRefimpl/Gen/<pkg>.lean: the bodies (X.impl) verbatim, and one class<pkg>.Refimplbinding the names to them. Generated: never edit;--checkexits 1 if stale.
Then one directory per Go package (Refimpl/<go package path>/):
Impl.lean: what is not code: definitions of the opaque predicates the axioms are written in (in zap,zap.loggerRaw,zapcore.zapEntry), and of the untranslated package-variable initializersX.init(data axioms of etcd-grove's translation, which a translated initializer could not replace without redeclaring them).<fn>.lean, one per axiomatized function (the name of etcd-grove's spec file,Spec/<pkg>/<fn>.lean):theorem <fn>.model_proof, the spec, read in the model, proved of the translated reference implementation, under[<pkg>.Refimpl](and the package's typeAssumptions).Init.lean: the package-initialization axioms (opaqueInitsOk,initFuncsOk), read in the model, as theorems. The untranslated initializers areinitNoop; theinit()s are Go, translated, and where the real one writes a package variable (which a{{ True }}triple does not own) or calls code etcd-grove does not translate, its body is replaced by an empty one. (Until etcd-grove1ed1c7f480, which translates and proves everyvar X = errors.New(msg), there was a third,errorsNewVarsInit, modelled by Go'serrors.New.) A package with only anopaqueInitsOkneeds no Go (its directory hasInit.leanandResults.leanalone).Results.lean:#model_checkof every model proof, and#bound_checkof the binding classes.
Refimpl/Subst.lean provides model% P with [c := t, ...]. It takes the statement P exactly as
etcd-grove states it (EtcdGrove.zap.Logger.Info.spec, or type_of% of an axiom). It unfolds
etcd-grove's definitions that mention the opaque constants c (for example zapLoggerOk, which is
defined over zap.loggerRaw), and replaces each c by the model's definition t. The statement
proved is therefore etcd-grove's own spec, with no copy that could drift, and all of a package's
specs are proved against one shared definition of its predicates.
#model_check checks that a model proof rests on no sorry and on no etcd-grove axiom that is a
claim (Prop-typed). It lists the data axioms of the translation the proof uses: axiomatized types
(axiom AtomicLevel : Type, its ZeroVal, X.underlying : go.GoType). Those have trivial values
and claim nothing.
etcd-grove's axioms are stated for every Go semantics ([sem : go.Semantics]), in which a
names-only function's code is unconstrained. The model proofs take one more hypothesis,
[<pkg>.Refimpl], saying that the function names are bound to the reference implementation's
Goose translation. #bound_check refuses such a class if it binds a name some translated package's
Assumptions already binds to a real body (that hypothesis would contradict the real binding, and a
proof under it would show nothing). Each
proof therefore shows that the axiom is satisfiable: it holds of a program in which the library is
the reference implementation. It does not show that the axiom holds of the real library, and the
real Go code is not checked here. The models are deliberately the simplest implementations that
meet the specs: a logger that discards everything, field constructors that return Field{}, and
initializers that do nothing.
| package | axioms | modelled | notes |
|---|---|---|---|
go.uber.org/zap, zap/zapcore |
26 (23 function specs, CheckedEntry.Write, opaqueInitsOk ×2, initFuncsOk) |
26 | Logger.Panic spec fixed in etcd-grove: see below |
github.com/jonboulle/clockwork |
8 (NewRealClock, the 6 laws of clockLb/stampAt, opaqueInitsOk) |
8 | stampAt's model is □ P: see below |
k8s.io/utils/clock |
8 | moved | verified in etcd-grove (3591db1da2): the real code proved over Perennial's time; the 7 method axioms are theorems there |
golang.org/x/time/rate |
5 (Every, NewLimiter, Limiter.Reserve/Wait, Reservation.Delay) |
5 | a limiter that never limits (nil receivers) |
go-grpc-middleware/providers/prometheus |
7 (5 function specs, promSrvMetrics_persistent; promSrvMetrics/promSrvMetricsOpt are the predicates) |
7 | metrics that record nothing; ServerMetrics translated in etcd-grove (2040eeb525) |
k8s.io/klog/v2 |
8 (6 function specs, opaqueInitsOk, initFuncsOk) |
8 | logging that does nothing |
k8s.io/component-base/tracing |
4 (Start, SpanFromContext, Span.AddEvent, Span.End) |
4 | spans that record nothing; Span translated in etcd-grove (2040eeb525) |
go.opentelemetry.io/otel/trace |
2 (SpanFromContext, opaqueInitsOk) |
2 | SpanFromContext returns the no-op span; WithAttributes verified in etcd-grove (4fcdd2aa9d: the real body translated, its axiom a theorem) |
go.opentelemetry.io/otel/attribute |
5 (Bool, Int, Int64, String, opaqueInitsOk) |
1 + moved | the 4 functions verified in etcd-grove (4fcdd2aa9d): the real code translated, the 4 axioms are theorems there |
go.opentelemetry.io/otel/codes |
1 (opaqueInitsOk) |
1 | |
go.opentelemetry.io/contrib/instrumentation/google.golang.org/grpc/otelgrpc |
2 (NewServerHandler, opaqueInitsOk; grpcStatsHandlerOk is the predicate) |
2 | grpcStatsHandlerOk modelled as the nil handler, which grpc's StatsHandler option ignores; unblocked by etcd-grove 9d1d50a846 (grpc stats types translated): see below |
google.golang.org/grpc/codes |
2 (opaqueInitsOk, initFuncsOk) |
2 | the init() sets no internal.CanonicalString hook |
k8s.io/utils/trace |
3 (New, Trace.LogIfLong, opaqueInitsOk; the predicate trace.fromNew) |
3 | a nil trace, logging nothing; fromNew := True. LogIfLong's spec, false of the real code, fixed in etcd-grove 4fcdd2aa9d: see below |
github.com/xiang90/probing |
3 (NewHandler, NewProber, opaqueInitsOk) |
3 | an empty 200 handler (relative to net/http's WriteHeader spec) and a nil prober |
github.com/prometheus/client_golang/prometheus |
19 (14 function specs, opaqueInitsOk, initFuncsOk; collectorName/nameFree/nameUnclaimed/vecLabels are the predicates) |
19 | a registry that registers nothing, metrics and metric vectors (nil pointers) that record nothing (vecLabels := True); NewCounterVec, NewGaugeVec, NewHistogramVec (nil vectors, keeping neither slice) and NewGaugeFunc (a nil *valueFunc, never calling the function) added by etcd-grove 1ed1c7f480 (metric vectors' initializers translated); NewGauge, NewHistogram, ExponentialBuckets (factor 2) added by etcd-grove 1df314ccbf (metric initializers translated); ExponentialBuckets computes the exact buckets on the float64 bits through uint64 views (Perennial's float arithmetic is uninterpreted), NewHistogram drops the buckets slice; HistogramVec.WithLabelValues was unsatisfiable (observerSpec), fixed in etcd-grove 4fcdd2aa9d: see below; Opts translated in etcd-grove (2040eeb525) |
google.golang.org/grpc/status (and internal/status's Status.Code) |
5 | 3 | every code Unknown; Error, FromError: no implementation meets them, see below |
google.golang.org/grpc/metadata |
6 (3 function specs, incomingOf_cancelCtx, opaqueInitsOk, initFuncsOk) |
5 | no context carries metadata; MD.Get verified in etcd-grove (4fcdd2aa9d); AppendToOutgoingContext: no implementation meets it, see below |
google.golang.org/grpc/health, health/grpc_health_v1 |
9 (4 function specs, grpcHealthSrv_persistent, opaqueInitsOk ×2, initFuncsOk ×2) |
7 | a health server that records nothing; SetServingStatus, ServingStatus.String met since etcd-grove 4fcdd2aa9d (a w32 status); NewServer blocked by an axiomatized type, RegisterHealthServer by grpc's server model: see below |
k8s.io/apimachinery/pkg/api/errors |
5 (HasStatusCause, IsTimeout, NewConflict, NewInternalError, opaqueInitsOk) |
5 | the checks read a *StatusError only; the constructors leave out the message |
k8s.io/apimachinery/pkg/labels |
2 (Everything, opaqueInitsOk) |
2 | the shared selectors without their package variables; Empty/Matches are the real code |
k8s.io/apimachinery/pkg/apis/meta/v1 |
4 (LabelSelectorAsSelector, the predicate labels.reqsValid, opaqueInitsOk, initFuncsOk) |
4 | only the empty selector is accepted (reqsValid: no pair, no requirement); the two init()s register nothing in the package's scheme |
k8s.io/api/core/v1, apps/v1 |
7 (Resource ×2, DeepCopyObject of Node, Pod, DaemonSet, opaqueInitsOk ×2) |
4 | DeepCopyObject not modelled: see below; ControllerRevision.DeepCopyObject verified in etcd-grove (4fcdd2aa9d) |
k8s.io/apiserver/pkg/storage/etcd3/metrics |
9 (NewEtcdMetricsTracker, OperationLatencyTracker.Record, 6 Record*, opaqueInitsOk) |
9 | no metrics; ErrTransactionConflict translated and proved in etcd-grove since 1ed1c7f480 (its errorsNewVarsInit gone); NewEtcdMetricsTracker met since etcd-grove 4fcdd2aa9d translates OperationLatencyTracker: see below |
k8s.io/component-base/metrics |
3 (HistogramVec.WithContext, opaqueInitsOk, initFuncsOk; vecLabels, histCtxOk are its vocabulary) |
3 | nil wrappers and observers that record nothing; the init() records no process start time |
The packages whose only modelled axioms are the initialization axioms etcd-grove's etc/gen-init.py
generates (Refimpl/<pkg>/Init.lean; packages with function models are in the table above):
opaqueInitsOk: every listed untranslated initializerX.initisinitNoop. This is sound with respect to etcd-grove's other axioms:gen-init.pyleaves out of the list every variable a spec relies on, whose initializer has an axiom of its own (X_init, giving its value: rpctypes' client errors, rafthttp'slinkHeartbeatSize, ...), which these models do not cover.initFuncsOk: the package'sinit()s are Go, translated from a copy of the package's source (go/third_party/,go-k8s/third_party/) with empty bodies (// refimpl:on thefunc init()line, the real body commented out line by line, so that every line number is the real one; an import left unused is made blank, so that the package still imports it). As the post isTrue, no other axiom can rely on what a realinit()does. etcd's own packages are ingo/third_party/etcd/: the five Go modules (api,client/pkg,client/v3,pkg,server) of the fork etcd-grove'setcdproject pins (upamanyus/etcd8c28a4296), without tests; its prophecy patches (etc/proph-patches/etcd/) touch onlyclient/v3/kubernetes, which is not translated here, and are not applied.
| package | axioms | modelled | notes |
|---|---|---|---|
bufio |
opaqueInitsOk (1 var) |
1/1 | |
crypto/tls |
opaqueInitsOk (50 vars) |
1/1 | |
encoding/base64 |
opaqueInitsOk (2 vars) |
1/1 | |
encoding/json |
opaqueInitsOk (4 vars), initFuncsOk (1 init()) |
2/2 | |
github.com/Masterminds/semver/v3 |
opaqueInitsOk (11 vars), initFuncsOk (2 init()) |
2/2 | |
github.com/dustin/go-humanize |
opaqueInitsOk (35 vars), initFuncsOk (1 init()) |
2/2 | |
github.com/go-logr/logr |
opaqueInitsOk (5 vars) |
1/1 | |
github.com/spf13/pflag |
opaqueInitsOk (3 vars) |
1/1 | |
go.etcd.io/etcd/api/v3/authpb |
opaqueInitsOk (4 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/api/v3/etcdserverpb |
opaqueInitsOk (24 vars), initFuncsOk (3 init()) |
2/2 | |
go.etcd.io/etcd/api/v3/membershippb |
opaqueInitsOk (3 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/api/v3/mvccpb |
opaqueInitsOk (6 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/api/v3/v3rpc/rpctypes |
opaqueInitsOk (96 vars) |
1/1 | |
go.etcd.io/etcd/api/v3/version |
opaqueInitsOk (11 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/client/pkg/v3/logutil |
opaqueInitsOk (3 vars) |
1/1 | |
go.etcd.io/etcd/client/pkg/v3/types |
opaqueInitsOk (2 vars) |
1/1 | |
go.etcd.io/etcd/client/v3 |
opaqueInitsOk (6 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/pkg/v3/featuregate |
opaqueInitsOk (3 vars) |
1/1 | |
go.etcd.io/etcd/server/v3/auth |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 1ed1c7f480 (its variables translated) |
go.etcd.io/etcd/server/v3/etcdserver |
opaqueInitsOk (2 vars), initFuncsOk (3 init()) |
2/2 | |
go.etcd.io/etcd/server/v3/etcdserver/api |
opaqueInitsOk (1 var), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/server/v3/etcdserver/api/membership |
initFuncsOk (1 init()) |
1/1 | its errors.New variables are translated and proved in etcd-grove (f61c5c06cc); no opaqueInitsOk since etcd-grove 1ed1c7f480 |
go.etcd.io/etcd/server/v3/etcdserver/api/rafthttp |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 101733cb0e (its variables translated), no errorsNewVarsInit since etcd-grove 1ed1c7f480 (its errors.New variables translated and proved) |
go.etcd.io/etcd/server/v3/etcdserver/api/snap |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 1ed1c7f480 (its variables translated) |
go.etcd.io/etcd/server/v3/etcdserver/api/v3rpc |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 1ed1c7f480 (its variables translated) |
go.etcd.io/etcd/server/v3/etcdserver/apply |
initFuncsOk (1 init()) |
1/1 | |
go.etcd.io/etcd/server/v3/etcdserver/txn |
opaqueInitsOk (2 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/server/v3/features |
opaqueInitsOk (1 var) |
1/1 | |
go.etcd.io/etcd/server/v3/lease |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 1ed1c7f480 (its variables translated) |
go.etcd.io/etcd/server/v3/lease/leasepb |
opaqueInitsOk (3 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/server/v3/storage |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 1ed1c7f480 (its variables translated) |
go.etcd.io/etcd/server/v3/storage/backend |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 1ed1c7f480 (its variables translated) |
go.etcd.io/etcd/server/v3/storage/mvcc |
initFuncsOk (1 init()) |
1/1 | no opaqueInitsOk since etcd-grove 1ed1c7f480 (its variables translated) |
go.etcd.io/etcd/server/v3/storage/schema |
opaqueInitsOk (4 vars), initFuncsOk (1 init()) |
2/2 | |
go.etcd.io/etcd/server/v3/storage/wal |
initFuncsOk (1 init()) |
1/1 | |
go.etcd.io/etcd/server/v3/storage/wal/walpb |
opaqueInitsOk (3 vars), initFuncsOk (1 init()) |
2/2 | |
golang.org/x/crypto/bcrypt |
opaqueInitsOk (5 vars) |
1/1 | |
golang.org/x/sys/unix |
opaqueInitsOk (11 vars) |
1/1 | |
google.golang.org/grpc |
opaqueInitsOk (38 vars), initFuncsOk (6 init()) |
2/2 | |
google.golang.org/grpc/credentials |
opaqueInitsOk (3 vars) |
1/1 | |
google.golang.org/grpc/grpclog |
opaqueInitsOk (1 var), initFuncsOk (1 init()) |
2/2 | |
google.golang.org/grpc/reflection |
opaqueInitsOk (1 var) |
1/1 | |
hash/crc32 |
opaqueInitsOk (3 vars) |
1/1 | |
internal/bytealg |
initFuncsOk (1 init()) |
1/1 | |
internal/runtime/sys |
opaqueInitsOk (3 vars) |
1/1 | |
k8s.io/apimachinery/pkg/api/meta |
opaqueInitsOk (24 vars) |
1/1 | |
k8s.io/apimachinery/pkg/api/validate/content |
opaqueInitsOk (10 vars) |
1/1 | |
k8s.io/apimachinery/pkg/apis/meta/v1/unstructured |
opaqueInitsOk (7 vars) |
1/1 | |
k8s.io/apimachinery/pkg/conversion |
opaqueInitsOk (1 var) |
1/1 | |
k8s.io/apimachinery/pkg/fields |
opaqueInitsOk (2 vars) |
1/1 | |
k8s.io/apimachinery/pkg/runtime |
opaqueInitsOk (27 vars) |
1/1 | |
k8s.io/apimachinery/pkg/runtime/schema |
opaqueInitsOk (1 var) |
1/1 | |
k8s.io/apimachinery/pkg/util/errors |
opaqueInitsOk (1 var) |
1/1 | |
k8s.io/apimachinery/pkg/util/runtime |
opaqueInitsOk (3 vars) |
1/1 | |
k8s.io/apimachinery/pkg/util/validation/field |
opaqueInitsOk (2 vars) |
1/1 | |
k8s.io/apimachinery/pkg/util/version |
opaqueInitsOk (2 vars) |
1/1 | |
k8s.io/apimachinery/pkg/util/wait |
opaqueInitsOk (8 vars) |
1/1 | |
k8s.io/apimachinery/pkg/watch |
opaqueInitsOk (6 vars) |
1/1 | |
k8s.io/apiserver/pkg/audit |
opaqueInitsOk (6 vars), initFuncsOk (2 init()) |
2/2 | |
k8s.io/apiserver/pkg/endpoints/request |
opaqueInitsOk (5 vars) |
1/1 | |
k8s.io/apiserver/pkg/features |
opaqueInitsOk (1 var) |
1/1 | |
k8s.io/apiserver/pkg/storage/feature |
opaqueInitsOk (3 vars) |
1/1 | |
k8s.io/apiserver/pkg/storage/value |
opaqueInitsOk (6 vars), initFuncsOk (1 init()) |
2/2 | |
k8s.io/apiserver/pkg/util/flowcontrol |
opaqueInitsOk (3 vars) |
1/1 | |
k8s.io/component-base/featuregate |
opaqueInitsOk (6 vars) |
1/1 | |
k8s.io/utils/clock |
opaqueInitsOk (2 vars) |
1/1 | |
math/rand |
opaqueInitsOk (9 vars) |
1/1 | |
net |
opaqueInitsOk (78 vars) |
1/1 | |
net/http |
opaqueInitsOk (116 vars), initFuncsOk (2 init()) |
2/2 | |
net/url |
opaqueInitsOk (3 vars) |
1/1 | |
path |
opaqueInitsOk (1 var) |
1/1 | |
path/filepath |
opaqueInitsOk (3 vars) |
1/1 | |
reflect |
opaqueInitsOk (7 vars) |
1/1 | |
runtime |
opaqueInitsOk (94 vars), initFuncsOk (9 init()) |
1/2 | initFuncsOk blocked: Perennial translates runtime from another Go release (Findings) |
-
runtime'sinitFuncsOkis not modelled: Perennial's translation ofruntimeis of another Go release than the toolchain etcd-grove pins. etcd-grove'sruntimeaxioms (opaqueInitsOk,initFuncsOkoverinit.«0»..init.«8») are about Perennial'sPerennial/Code/runtime, which is not in etcd-grove'sCode/, so the pure-superset comparison does not apply; and translating go1.27.3'sruntime(etcd-grove'sGO_TOOLCHAIN) with Perennial's configuration gives a different translation, not a superset: Perennial's has struct fields go1.27.3 does not (_panic.gopanicFP,memRecordCycle'salloc_bytes), which go1.26'sruntimehas. Both releases have nineinit()s on linux/amd64, so the axiom's list is right for either. A model needsetc/goose-refimpl.pyto compare against Perennial's chunked translation, from the toolchain Perennial translatedruntimewith. (runtime'sopaqueInitsOkis modelled: it needs no Go.) -
otelgrpc.NewServerHandlercould not be met in etcd-grove's translation as configured (fixed in etcd-grove9d1d50a846, 2026-11-19: grpc'sstatstypes translated, imported by otelgrpc's configuration; now modelled). Asgrpc_prometheus.NewServerMetricscould not: any Go body returns astats.Handler, and Goose allocates the result (GoAlloc stats.Handler.ty, thenConvertinto it), but etcd-grove did not translate grpc'sstatspackage at all, so the translated body namedgoogle_golang_org.grpc.stats.Handler.ty, which did not exist. The reference implementation (go/third_party/otelgrpc, v0.71.0, etcd's pin) returns a nil handler, which grpc'sStatsHandleroption ignores (server.go: "ignoring nil parameter in grpc.StatsHandler ServerOption"); the model ofgrpcStatsHandlerOk his "his the nil interface", under which grpc'sStatsHandleraxiom, the predicate's only consumer, holds of the real grpc (that axiom is grpc's, not modelled here). -
k8s.io/utils/trace'sTrace.LogIfLongspec was false of the real code (fixed in etcd-grove4fcdd2aa9d:StepandLogIfLongrequiretrace.fromNew t, whichNewgives; modelled asTrue) (satisfiable: the model met it). It holds for everyt : Locwith no premise ({{ True }} t.LogIfLong(d) {{ True }}), but the realLogIfLong(k8s.io/utilsbe93311217bd,trace/trace.go:208) starts witht.lock.Lock():var t *trace.Trace; t.LogIfLong(time.Second)panics with a nil dereference (run with Go 1.27.3), yet the axiom proves it returns. Any location that is not a live*Traceis admitted too. Fix in etcd-grove: a predicate of the tracestrace.Newreturns (persistent:Tracehas its own lock), produced byNew's spec and required byLogIfLong's; the named hypothesisTrace.Stephas the same gap. -
The k8s API types'
DeepCopyObject(core/v1Node,Pod; apps/v1DaemonSet): not modelled (ControllerRevision's is a theorem in etcd-grove4fcdd2aa9d, over deepcopy-gen's code translated with generated proofs; the other three are still axioms there). The spec gives the caller a new object owned whole (l' ↦ v'andkd.*.own v' (DFrac.own 1) d, every slice and map reached fresh) with the original's deep value, so any implementation is a complete deep copy over the 166 struct types of etcd-grove'sProof/k8s_io/api/Deep.lean: the real, generatedDeepCopyIntois already the simplest one. Its proof is mechanical and belongs in etcd-grove, generated alongsideDeep.lean(etc/gen-k8s-deep.py), with the deep copies translated with their bodies; the axioms are believed true. -
metrics.NewEtcdMetricsTrackercould not be met in etcd-grove's translation as configured (fixed in etcd-grove4fcdd2aa9d, which importsschemaand component-base'smetrics; now modelled). It returns a tracker whoseGetis a non-nil*OperationLatencyTracker; any Go code doing so allocates anOperationLatencyTracker, a type etcd-grove's translation axiomatizes (its fields nameschema.GroupResourceand component-base'smetrics.ObserverMetric/CounterMetric, and the package's configuration imports neither), so the allocation is stuck onsorryinstances, asServerMetrics's was. Fix in etcd-grove: importk8s.io/apimachinery/pkg/runtime/schemaandk8s.io/component-base/metricsinCode/k8s_io/apiserver/pkg/storage/etcd3/metrics.toml, with component-base'smetrics.tomltranslating the two interface types (it has notranslate_types). The Go reference implementation and its translation are here already. -
The apierrors specs after etcd-grove's
apierrors-fix(2026-11-17) are satisfiable. The soundness review of 2026-11-17 refutedHasStatusCause(a view built after the call,notes/hasstatuscause-later-view.md) and the constructors' preconditions (notes/axiom-review/apierrors-fix.md); the texts this repository proves are the fixed ones. The models ofHasStatusCauseandIsTimeoutrest onapiErrOkholding the details read-only: an error has one view (apiErrAt_agree,Refimpl/k8s_io/apimachinery/pkg/api/errors/View.lean), so the answer computed from the view held is every view's. -
labels.reqsValidis uninterpreted, soLabelSelectorAsSelector's spec is met by a function that rejects every non-empty selector. The model is that function. The spec says nothing of which selectors the real code accepts (SelDefs.leandocuments it in prose: the four operators, andlabels.NewRequirement's syntax checks); a caller can only learn it from an error. -
grpc_prometheus.NewServerMetricscould not be met in etcd-grove's translation as configured (fixed in etcd-grove2040eeb525, 2026-11-18; now modelled). It returns a non-nil*ServerMetrics; any Go code doing so allocates aServerMetrics, but etcd-grove's Goose configuration of the package does not import prometheus, whose types the struct's fields name, so the type is axiomatized (axiom ServerMetrics : Type) and its allocation's instances aresorry(anunsafe.Pointerconversion is stuck: not a plain type). The axiom is true of the real code; what blocks a proof is the translation. Fix in etcd-grove: import prometheus's names inCode/github_com/grpc_ecosystem/go_grpc_middleware/providers/prometheus.toml. -
prometheus.HistogramVec.WithLabelValuescould not be met by any implementation (observerSpec; fixed in etcd-grove4fcdd2aa9d,∀ f : w64; now modelled). Its post givesobserverSpec oi, which says{{ True }} methods oi.ty "Observe" oi.v f {{ RET #(); True }}for everyf : val. Takef := PanicV p, a panic outcome: GooseLang evaluates an application's argument first, and a panic in that position unwinds the application (Unwinds, theAppRCtxframe), so the call evaluates toPanicV pwhatever the method is, and the triple's postcondition (Φ #()) cannot be met for it (takeΦ v := ⌜v = #()⌝). The axiom is therefore false in every model, not only of the real code (whoseObserve(v float64)would in addition be stuck allocating afloat64from any value that is not a 64-bit word). Every caller passes a float64 (EtcdServer.Range/Txn,processInternalRaftRequestOnce, rafthttp's snapshot sender and handler), so the fix in etcd-grove is∀ f : w64(#f) inobserverSpec, asgaugeSpec'sAddandGaugeVec.With'sSetalready have. (Not checked for: whether the false axiom lets etcd-grove proveFalseoutright; it needs a vector withvecLabels, which its initializer axioms give.) -
prometheus.wp_counterOptsLit(fixed in etcd-grove2040eeb525).CounterOpts = Optswas an axiomatized type (its fieldnow func() time.Time, withtimenot imported), so the composite literal had no semantics, whatever the implementation. etcd-grove now importstimein the package's Goose configuration;counterOptsis a definition and the literal's axiom is gone. -
grpc's
status.Error,status.FromErrorandmetadata.AppendToOutgoingContextcannot be met by any implementation that returns. Each post equates an opaque Lean function of a Go value with data the caller chooses, for a value the function allocates or whose method it calls:status.Error(c, msg):errDesc err = msgfor everymsg, whereerris a*status.Error(the post fixes its type), so its value is a location: one the call does not allocate cannot have everymsgas its description, and one it allocates may be any fresh location;status.FromError(err)withok = false:errDesc err = m, wheremis the precondition's string, whicherr.Error()returns (errorMsgIs): the same error value can return"a"in one heap and"b"in another (anError()that reads a cell);metadata.AppendToOutgoingContext(ctx, [k, v]):outgoingOf c' = mdAdd (outgoingOf ctx) k v, for the contextc'it returns: a fresh*valueCtx(returningctxitself would needoutgoingOf ctx = mdAdd (outgoingOf ctx) k v, false:mdAddappendsv).
errDescandoutgoingOfare fixed Lean functions, the same in every execution, while the location an allocation returns is any fresh one (GooseLang'sAlloc/AllocBytessteps), and the contents of a cell are the initial heap's. A model proof is one proof for every location and every heap, so no definition oferrDescoroutgoingOfmakes the post provable, whatever the code (short of code that never returns). The axioms are false of grpc itself in the same way: two runs ofstatus.Error(c, "a")andstatus.Error(c, "b")from the same heap may allocate the same location, so by adequacyerrDescof one value would be both"a"and"b". etcd-grove documents the reading it intends (status.FromError.spec's docstring,incomingOf_cancelCtx's: "the equations are claims about one execution's heap"), but the Lean statements do not say it: the functions do not depend on the execution. A fix in etcd-grove would make the description and the metadata ghost state of the execution (for example a persistenterrDescIs err mpoints-to-like fact, given bystatus.Errorand read byFromError) instead of functions of the value. -
grpc health's
Server.SetServingStatusandHealthCheckResponse_ServingStatus.Stringcould not be met by any implementation (fixed in etcd-grove4fcdd2aa9d, the status aw32; now modelled). Their specs take the serving status as anyval, not aw32. Avalmay be a panic outcomePanicV p, and an application to one unwinds toPanicV pin one pure step (GooseLang'sUnwinds, Perennial'spure_unwind), whatever the function: the result is not theRET #()(RET #s) the post names.String's precondition isTrue, so its axiom, atst := PanicV p, gives a WP no execution satisfies (by adequacy,False);SetServingStatus's does the same undergrpcHealthSrv hs, whichhealth.NewServer's axiom gives. (Short of a panic, the real code is stuck too on avalthat is not anint32: Goose stores a named parameter withGoAlloc,AllocBytes 4for anint32.) Fix in etcd-grove: quantify overw32. The Go model (go/third_party/grpc) leaves the parameters unnamed, so that it meets the fixed specs. -
health.NewServercannot be met in etcd-grove's translation as configured, asgrpc_prometheus.NewServerMetricscould not: it returns a non-nil*health.Server, andServeris an axiomatized type, so&Server{}is stuck. etcd-grove2040eeb525turned ontranslate_typesforhealth(importingsyncandgrpc_health_v1), but Goose still axiomatizesServer: its fieldupdates map[string]map[healthgrpc.Health_WatchServer]chan ...namesHealth_WatchServer, an alias (of the genericgrpc.ServerStreamingServer[HealthCheckResponse]) declared in another package (GOOSE_TYPES_LOG: "alias from another package google.golang.org/grpc/health/grpc_health_v1; needs import google.golang.org/grpc"; withgoogle.golang.org/grpcimported too, still "alias from another package"). The fix is in Goose (Perennial): translate a field type that is another package's alias. -
grpc_health_v1.RegisterHealthServeris not modelled here: its post is a newgrpcSrvNew(grpc's server being built, an opaque predicate), which only grpc's ownServer.RegisterServiceaxiom gives; a model proof may not use it. grpc's body issrv.testEmbeddedByValue(); s.RegisterService(&Health_ServiceDesc, srv), provable in etcd-grove fromServer.RegisterService.speconceHealth_ServiceDesc's initializer is translated. (metadata.MD.Get,md[strings.ToLower(k)], is now proved there:4fcdd2aa9d.) -
Perennial: no
go.NotInterfaceinstance for the predeclared types. Resolving a method on a value receiver of a named non-struct type (HealthCheckResponse_ServingStatus, anint32) needsgo.NotInterfaceof its underlying type; Perennial has instances for the type constructors (go.Named,go.PointerType, ...) butgo.int32is a plaindef, which instance search does not unfold, sowp_automakes no progress. The model proof supplieshaveI : go.NotInterface go.int32 := ⟨trivial⟩; the general fix is an instance per predeclared type in Perennial (Golang/Theory/PostLifting.lean). -
metrics.RecordDecodeErrorwas not modelled (this repository, fixed with the4fcdd2aa9dpin). The row counted 7 axioms; etcd-grove has 8 (RecordDecodeErrorhad been missed). Its model records nothing, like the otherRecord*. -
model%and universe-polymorphic constants (this repository).promSrvMetricsis declared with{GF : BundledGFunctors}and nothing fixing its universe;model%now takes a polymorphic constant's model as a constant with the same universe parameters, replaced at each occurrence's levels. -
model%left a substitution undone (this repository, fixed 2026-11-18). Classifying the definitions that mention a replaced constant stopped at a definition's first such constant, so a second one (rate.reservationOk, afterrate.limiterOkinLimiter.Reserve.spec) was neither unfolded nor replaced, and the check for leftovers looked only at the statement's own constants. Both fixed (every constant classified; the check follows definitions). Earlier results were not affected: a leftover opaque predicate can only make a proof harder, and its laws are axioms#model_checkrejects; every earlier model proof still checks. -
clockwork's
stampAt(a docstring only). etcd-grove'sProof/github_com/jonboulle/clockwork/Defs.leansays the clock axioms have the trivial modelclockLb := True,stampAt P T := P. That model failsstampAt_persistent, which makes every stamp persistent, for aPthat is not. The axioms are satisfiable all the same, withstampAt P T := □ P(this repository's model); no axiom changes. -
zap.Logger.Panic(fixed in etcd-grove, 2026-11-17,notes/specs-only/ledger.md).- The panic value. The spec said
r = PanicV #msg, a panic with the bare string. No Go program raises that: Go'spanic(x)(Perennial'sgo.panic) panics with an interface value,PanicV #(interface.mkOk go.string #msg), and zap'sWriteThenPanicdoespanic(ce.Message). The model could meet the old spec only with GooseLang's rawRaise. The spec now names the interface value, and so do the mvcckeyIndexspecs that had copied the bare string; the model is Go'spanic(msg). - The premise. It was
l ≠ null, which admits loggers for which the axiom is false of real zap. A zero&zap.Logger{}panics with a nil-dereference runtime error, notmsg. A logger built with a customWithPanicHookwhose hook returns makesPanicreturn. The premise is nowzapLoggerOk l, as for the other logging methods, and the mvcc callers pass it on from their index's invariant.
- The panic value. The spec said
lakefile.toml requires etcd-grove at a pinned commit. A plain lake build clones it and builds
it from scratch (hours): don't. Build against an existing, built checkout of etcd-grove at that commit,
with Lake's artifact cache on:
export LAKE_ARTIFACT_CACHE=true LAKE_RESTORE_ARTIFACTS=true
etc/link-local.sh /path/to/etcd-grove
etc/goose-refimpl.py --check # the Go reference implementations translate to Refimpl/Gen/
lake buildetc/lean-check.py FILE (copied from etcd-grove) checks a file through a persistent Lean server,
for the edit-check loop.