Repository navigation
Expand file tree
/
Copy pathstatement.tex
More file actions
831 lines (763 loc) · 64.5 KB
/
Copy pathstatement.tex
File metadata and controls
831 lines (763 loc) · 64.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
\documentclass[11pt]{article}
\usepackage[margin=2.3cm]{geometry}
\usepackage{amsmath,amssymb,booktabs}
\usepackage[hidelinks]{hyperref}
\usepackage{microtype}
\usepackage{url}
\DeclareUrlCommand\lean{\urlstyle{tt}\def\UrlBreaks{\do\.\do\_\do\/}}
% the claim lists of a statement and their byte encodings
\newcommand{\Cx}{C_{\mathrm{xmss}}}
\newcommand{\Cs}{C_{\mathrm{sphincs}}}
\newcommand{\enc}{\mathrm{enc}}
\emergencystretch=3em
\setlength{\parskip}{0.35em}
\title{What is proved about leanVM}
\author{}
\date{November 2026}
\begin{document}
\maketitle
\noindent This document states, in plain mathematics, every end statement the repository proves:
leanVM is knowledge sound and complete; its leanISA guest program, which aggregates signatures,
data-availability claims and other proofs, is sound and complete as an aggregation step; leanXMSS
and leanSPHINCS are strongly unforgeable; and LeanDA's commitments are position binding, and code
binding for arguments whose relation is evaluated over the model's permutation. Each is a Lean~4
proposition proved using only Lean's three axioms (\lean{propext}, \lean{Classical.choice},
\lean{Quot.sound}): no \lean{sorry}, no \lean{native_decide}, no added axiom. The system is
leanVM as of this document's tree.
\paragraph{Where to read it.} The statements live in one folder, \lean{Statement/}: seventeen files
of definitions and end statements, which import Mathlib,
VCVio and CompPoly and nothing of the proofs. Beside them sit the honest prover the completeness
statements name (\lean{Statement/Prover/}; it is proved to make the specification's
honest moves, so a reviewer only needs to see that it is a genuine prover), the guest program's
generated bytecode (\lean{Statement/Data/}), and proved \lean{@[csimp]} lemmas for speed only
(\lean{Statement/Fast/}). \textbf{The entry point is \lean{Statement/Theorems.lean}}: the
structure \texttt{Statement.Theorems} (its programs named, \texttt{leanVmKnowledgeExtractor := P},
\texttt{guestWitnessDecoder := D}) has one field per end statement, and
\lean{lean_vm/LeanVM.lean} proves them all at once,
\texttt{LeanVM.theorems\_hold : Statement.Theorems
(leanVmKnowledgeExtractor := LeanVM.Cost.compiledKnowledgeExtractor)
(guestWitnessDecoder := LeanVM.Cost.compiledGuestWitnessDecoder)}, its axioms pinned by the build,
$D$ the compiled decoder \lean{LeanVM.Cost.compiledGuestWitnessDecoder}.
\begin{center}\small
\begin{tabular}{lll}
\toprule
Field & End statement & Section\\\midrule
\lean{leanVmKnowledgeSoundness} & \lean{LeanVM.KnowledgeSoundness (extractorComputedBy P)} & \ref{sec:zkvm}\\
\lean{leanVmCompleteness} & \lean{LeanVM.Completeness} & \ref{sec:zkvm}\\
\lean{guestKnowledgeSoundness} & \texttt{LeanVM.Node.GuestKnowledgeSoundness D} & \ref{sec:guest}\\
\lean{statementDigestBinds} & \lean{LeanVM.Node.StatementDigestBinds} & \ref{sec:guest}\\
\lean{guestCompleteOnHonestChildren} & \lean{LeanVM.Guest.Completeness.GuestCompleteOnHonestChildren} & \ref{sec:guest}\\
\lean{honestProofRarelyRefused} & \lean{LeanVM.Guest.Completeness.HonestProofRarelyRefused} & \ref{sec:guest}\\
\lean{batchingSound} & \lean{LeanVM.Guest.Batch.BatchingSound} & \ref{sec:guest}\\
\lean{leanXmssStronglyUnforgeable} & \lean{LeanXmss.RandomPermutationModel.LeanXmssStronglyUnforgeable} & \ref{sec:schemes}\\
\lean{leanSphincsStronglyUnforgeable} & \lean{Sphincs.LeanSphincsStronglyUnforgeable} & \ref{sec:schemes}\\
\lean{leanDaComplete} & \lean{LeanDa.LeanDaPerfectlyComplete} & \ref{sec:schemes}\\
\lean{leanDaPositionBinding} & \lean{LeanDa.LeanDaPositionBinding} & \ref{sec:schemes}\\
\lean{leanDaCodeBinding} & \lean{LeanDa.LeanDaCodeBinding} & \ref{sec:schemes}\\
\bottomrule
\end{tabular}
\end{center}
The last file, \lean{Statement/Corollaries.lean}, is optional reading: it states one
consequence of the fields, \lean{AggregateSound} (Section~\ref{sec:guest}), proved from the
fields alone by
\lean{LeanVM.corollaries_of_theorems}. Theorems cited below with \lean{lean_vm} or another
project beside them are proved in the proof projects; their statements are not part of
\lean{Statement/}.
\paragraph{Reading order.} After \lean{Theorems.lean}, the files of \lean{Statement/} in the order they build on each other:
\begin{enumerate}\itemsep0pt
\item \lean{Keccak.lean}: Keccak-f[1600] and Keccak-256 over any permutation, on the one state type.
\item \lean{RandomPermutation.lean}: the model, its oracles $\pi$ and $\pi^{-1}$, query costs and logs.
\item \lean{SufCma.lean}: the single-key SUF-CMA game and \lean{StronglyUnforgeable}.
\item \lean{HashSignatures.lean}: the tweakable hash, chain, path fold and tree both schemes share.
\item \lean{LeanXmss.lean}, \lean{LeanSphincs.lean}: the two schemes and their end statements.
\item \lean{Field.lean}: $\mathbb{F} = \mathrm{GF}(2^{64})$, $\mathbb{E} = \mathrm{GF}(2^{128})$ and the Fiat-Shamir duplex sponge.
\item \lean{LeanDa.lean}: LeanDA, its argument and games, and its three end statements.
\item \lean{LeanIsa.lean}: leanISA, its runs, \lean{ValidExecution} and the bytecode encoding.
\item \lean{LeanVmVerifier.lean}: the verifier, the readable reference of \lean{crates/verifier}.
\item \lean{LeanVm.lean}: statements, the honest prover, \lean{KnowledgeSoundness} and \lean{Completeness}.
\item \lean{CostMachine.lean}: the cost machine, the extractor's encodings, size bound and budget.
\item \lean{LeanVmGuest.lean}, \lean{LeanVmGuestBatching.lean}: a node's statement, relation and digest, the guest program and its decoder, the batching program.
\item \lean{LeanVmGuestCompleteness.lean}: the deployed limits, honest children, the guest's completeness and \lean{BatchingSound}.
\item \lean{Corollaries.lean}, optional: \lean{AggregateSound}.
\end{enumerate}
\lean{Statement/Data/} needs no review beyond its provenance: it is not committed, and \lean{lean_vm/scripts/guest-export} writes it from leanVM's sources before every build, in CI and in \lean{check-all.sh}. \lean{Statement/Fast/} needs none: each \lean{@[csimp]} lemma is an equation the kernel checks.
\section{The setting}
\paragraph{Hashing.} leanVM hashes with Keccak-256, the sponge over the permutation
Keccak-f[1600] (rate $136$ bytes, capacity $512$ bits, padding \texttt{0x01}\,\dots\,\texttt{0x80},
zero initial state, the first four lanes as digest). The statement writes a state as $25$ lanes of
$64$ bits throughout and defines Keccak-256 once, over any permutation (\lean{keccak256With});
the deployed Keccak-256 is this sponge over Keccak-f[1600]. leanVM's Fiat-Shamir transcript is a
duplex that calls Keccak-f[1600] directly, overwriting the first $16$ lanes of the state.
\paragraph{The random permutation model (RPM).} Keccak-f[1600] is modelled as a uniformly random
permutation $\pi$ of $\{0,1\}^{1600}$, sampled lazily (\lean{Common.lazyRandomPermutation},
\lean{Statement/RandomPermutation.lean}). The model's oracles are $\pi$ and $\pi^{-1}$ and
nothing else (\lean{Common.RandomPermutationOracles}). No hash is an oracle or a parameter of
the statement: every algorithm (verifier, prover, scheme, argument) is written over one
permutation and computes Keccak-256 as the sponge over it (\lean{keccak256With}), and its duplex
calls it; the model gives every party $\pi$ (\lean{Common.queryPermutation}), the deployed
instance Keccak-f[1600]. Each experiment is one game run against the lazily sampled permutation
(\lean{Common.runWithRandomPermutation}), the adversary's queries recorded where an extractor reads
them (\lean{Common.loggedOracles}). \emph{The assumption is that the
deployed Keccak-f[1600], a fixed permutation, behaves like a random one}, even to programs that
compute it: the \texttt{KECCAK} instruction a proved program executes computes the deployed
Keccak-f[1600], so in the model the transcript's permutation and a program's are independent,
while deployed they are the same function. The model thus excludes, by construction, programs that
evaluate their own proof's Fiat-Shamir duplex, the setting of the known attacks on Fiat-Shamir
for GKR-based systems (Khovratovich, Rothblum and Soukhanov, 2025). The adversary is classical,
and its code is fixed before $\pi$ is sampled (no advice that depends on the permutation). Every end statement with
an adversary is in this model; \lean{Statement/} contains no random oracle. Queries are counted in
one of two ways:
\begin{itemize}
\item for leanVM and its guest program (Sections~\ref{sec:zkvm} and~\ref{sec:guest}), $Q$ bounds
the adversary's own queries to $\pi$ and $\pi^{-1}$ on every path; the verifier's calls are bounded
in the proofs and enter the constants;
\item for the signature schemes (Section~\ref{sec:schemes}), $q$ bounds the adversary's own calls
of $\pi$ and $\pi^{-1}$ on every path; key generation, the signer and the final verification are
not charged;
\item for LeanDA (Section~\ref{sec:schemes}), $Q$ bounds every permutation call of the game on
every path, the scheme's own included; a Keccak-256 evaluation of $n$ bytes costs
$\lfloor n/136\rfloor + 1$ calls.
\end{itemize}
Adversaries may flip private coins, which no budget counts; the transcript records them, but the extractor's program reads only the permutation queries (\lean{permutationQueries}).
\paragraph{How the proofs reach the RPM.} Each proof is first carried out with independent random
oracles (Keccak-256 a random function on byte strings and, for leanVM and LeanDA, Keccak-f a random
function on states), then moved to the RPM by the project \lean{common}: the sponge over $\pi$ is
indifferentiable from a random oracle, so an experiment of $q$ permutation calls changes
probability by at most $q^2/2^{509}$, or $q^2/2^{508}$ with the duplex's direct calls
(\lean{Common.keccak256_transfer}, \lean{keccak256_transfer2}). The proofs reason with Keccak-256 as a call or parameter of its own, over
the same $\pi$; with that hash Keccak-256 over the permutation these forms are the statement's
algorithms and games, with the same distribution and the same permutation calls (the
\lean{WithHashBridge} files of each project, \lean{Common.PiOnly}). These are proof steps; their
costs are included in the bounds below.
\section{The zkVM: knowledge soundness and completeness}\label{sec:zkvm}
\paragraph{What a proof claims.} A proof claims that a program $\mathit{prog}$ (leanVM bytecode) runs to completion on a public input $x$. A \emph{valid execution} of $\mathit{prog}$ on $x$ (\lean{ValidExecution}, \lean{Statement/LeanIsa.lean}) is a memory of $2^\kappa$ words, $2 \le 2^\kappa \le 2^{30}$, holding $x$ in words $0$ and $1$, together with a number of steps that run $\mathit{prog}$ on it from $(\mathit{pc}, \mathit{fp}) = (1, 1)$ to the final state $(g^{N_{\mathit{prog}}-1}, 1)$, where $N_{\mathit{prog}}$ is the bytecode's size: the last bytecode slot, in \texttt{main}'s frame. The machine halts when both registers equal the final state's, checked before each step. This is exactly the state the verifier's state bus checks for.
\paragraph{Well-formed programs only.} A program (\lean{LeanIsaProgram}) is $2^{k} \le 2^{30}$ typed instructions (\lean{LeanIsaInstruction}), and the verifier reads it as the table of words \lean{bytecodeWords}, sixteen per instruction (\lean{instructionSlots}). Such a table is well formed by construction: slots $0$ to $2$ and every slot the instruction does not use are zero, slot $3$ is one of the six opcodes, the \texttt{DEREF} flags are $(0,0)$, $(1,0)$ or $(0,1)$, never $(1,1)$ (\lean{derefFlags}), the \texttt{KECCAK} layout flags are $0$ or $1$, and its output flags are $(0,0)$, $(1,0)$ or $(1,1)$, one, two or all thirteen cells (\lean{keccakOutputFlags}); operands and immediates are any words. \textbf{The statement assumes this form}: the adversary outputs a typed program, and the Lean verifier does not check it. The Rust verifier rejects any other table (\texttt{Bytecode::new}). For a well-formed program, knowledge soundness needs no further condition.
\paragraph{The extractor.} Knowledge soundness is stated for the extractor a program of a cost
machine computes (\lean{LeanVM.extractorComputedBy}~$P$, \lean{Statement/CostMachine.lean}): the
program $P$, of size at most $25380$ (\lean{leanVmKnowledgeExtractorSizeBound}: the compiled
extractor's $25260$ and a slack of $120$, less than one leanXMSS signature's encoding), run on the encoded
statement, transcript and proof within a budget (\lean{leanVmKnowledgeExtractorBudget}: the most its
run may cost in the machine's price, so also the most steps it may execute,
$2^{\max(58,\,2\mu + 9)} + (N + 2^{30})(D + 2)^2(2^{15} + 2D)$ for a proof announcing a stack of $2^\mu$
elements (\lean{announcedStackLog}) and $N$ permutation queries, $D = \log_2(N + 2) + 1$, above the
price \lean{lean_vm} proves of the compiled extractor wherever it extracts, at every shape of that size; polylogarithmic
per query: $2^{69}$ at $\mu = 30$ up to $N = 2^{38}$, the descent at level 0 dominating, $2^{76.5}$ at $N = 2^{50}$
and $2^{157.1}$ at $N = 2^{128}$, the transcript's index dominating), its output
parsed as an execution; a run out of budget outputs nothing, which counts as a break. The budget
passes $2^{128}$ at about $N = 2^{99.7}$, where the soundness bound is still about $2^{-25}$, and its first
term, at most $2^{69}$, would pay for a search of about $2^{58}$ Keccak-f[1600] evaluations: knowledge
of a witness such a search finds
(of low entropy) is not what the statement certifies. The
statement takes $P$ as a parameter (\texttt{leanVmKnowledgeExtractor := P}) and constrains it only
by its size and budget: $P$ is a program (no classical choice), the size bound leaves the compiled
extractor no room for a useful table of witnesses, the budget is the one above, and the machine's
only runtime data is its input. The machine's prices are trusted to be honest: each step costs at
least $1$ and at least the words it writes (a \texttt{case} pays for the fields it binds, a
closure's application for its captured values); an operation on natural numbers costs the 64-bit
limbs it reads or writes, and a product, quotient, remainder or carry-less product the product of
its operands' limb counts (schoolbook), at least the limbs it writes, so one-limb operations, the
carry-less product included (PCLMULQDQ, PMULL), cost $1$, or $2$ when the result spills into a
second limb; a $\mathbb{F}_{2^{64}}$ product is compiled code (a carry-less product
and its reduction, $27$). In a program's size, a constructor's tag and a function index count one:
the machine reads them only by bounded lookups.
\texttt{lean\_vm} proves it for \lean{LeanVM.Cost.compiledKnowledgeExtractor}, the compiled form of
\lean{transcriptExtractor} (\lean{lean_vm/LeanVM/Protocol/Extraction/AS/Lite.lean}), and proves
that the program computes it within the budget. \lean{transcriptExtractor} is straight-line: it reads the proof and
the adversary's transcript and nothing else; it neither queries $\pi$, nor rewinds the adversary,
nor sees the verifier's queries. From the transcript's permutation queries (its coins left out,
\lean{permutationQueries}) it keeps each forward query's first answer, and recomputes the
Fiat-Shamir transcript through them: the verifier's transcript operations are fixed by the sizes
the proof announces (the verifier's skeleton), so it replays the sponge along that skeleton, reading
the announced sizes, every level's Merkle root, the fold rounds' messages and the final
polynomial off the proof. It inverts every level's Merkle tree through the Keccak-256 evaluations
the transcript holds to recover each committed word, and then descends from the final polynomial to
level 0's stack: in each fold round it decodes the previous round's word with at most one error on
the columns where the current tuple agrees with the word (on the first $d + 3$ of them, $d$ the
level's degree), and between levels it rebuilds the level's tuple from the next one's message and
the proof's high part. Level 0's tuple gives one stack, whose memory image it runs; it returns the
execution if the halting run is a valid one.
It is an algorithm: every definition it uses is computable and deterministic. Unlike a list
decoder it decodes uniquely, on agreement sets the transcript pins down, and the proof shows that on
an accepted proof, outside the soundness events, the stack it finds is the one the commitment's
out-of-domain answer leaves, with the same per-message errors. It runs the candidate for at most as
many steps as the announced tables have rows (\lean{stepCapLite}), which a valid execution never
exceeds (proved). Its running time, as the compiled program, is proved within the budget above
(\lean{LeanVM.Cost.Bounds.AS.extractL_cost}, \lean{LeanVM.Cost.Bounds.AS.asPrice_le}, \lean{lean_vm}):
the descent at level 0 dominates, about $2^{2\mu + 7}$ at the worst rate, with $O(\log^2 N)$
comparisons per lookup in the transcript's indexes (sorted maps). It gives straight-line knowledge
with a concrete reduction cost for the collision clauses below.
\paragraph{The proof.} A proof (\lean{Proof}, \lean{Statement/LeanVmVerifier.lean}) is the Rust
verifier's: the scalar stream and the Merkle openings, grouped in phases, one phase per opened
commitment, each opening (\lean{Opening}) the position it opens, the leaf's words and the full path
of siblings, in the order the verifier samples the queries. The verifier opens a phase
(\lean{openPhase}, \texttt{Transcript::merkle}) in the Rust's order: it rejects unless every leaf is
the commitment's width and every path its height (the shape), then unless the phase's positions are
the queries it sampled, in order (the positions), then unless each path climbs to the committed
root. A proof of work of $b$ bits (\lean{grindingBits}, round by round for a $2^{-125}$ error per
verifier message) reads a nonce from the stream, absorbs it with its own tag and permutes at once:
the third lane of that permutation must have its low $b$ bits zero, and its first two lanes are the
next challenge; nothing is absorbed while that challenge waits, and a grind of zero bits is no step
at all (\lean{run}, \texttt{Transcript::grind\_check}).
\paragraph{Knowledge soundness} (\lean{LeanVM.KnowledgeSoundness}). In the experiment
(\lean{knowledgeSoundnessExperiment}), an adversary $\mathcal{A}$ with oracle access to $\pi$ and
$\pi^{-1}$ outputs a (well-formed) program $\mathit{prog}$, a public input $x$ and a proof, and the verifier
checks it with Keccak-256 the sponge over $\pi$ and Keccak-f the permutation $\pi$. For every
adversary making at most $Q \le 2^{128}$ queries to $\pi$ and $\pi^{-1}$ on every path,
\[
\boxed{\ \Pr\left[\begin{array}{l}\text{the verifier accepts } (\mathit{prog},x,\text{proof}) \text{ and the}\\
\text{extractor outputs no valid execution of } \mathit{prog} \text{ on } x\end{array}\right]
\le (Q+2^{14})\cdot 2^{-125} + 5\,(Q+2^{14})^2\cdot 2^{-256}\ }
\]
(\lean{LeanVM.knowledgeSoundness_holds}). Each call may complete a verifier message, whose
round-by-round error after its proof of work is at most $2^{-125}$. The constant $2^{14}$ absorbs
the verifier's $13708$ Keccak-256 evaluations and duplex permutations (as calls of $\pi$ up to
$13708\cdot 2^{30}$, the IV hashing a bytecode of up to $2^{30}$ instructions) and three further terms
of at most $2^{-125}$ each: the transfer to the RPM, which pays for those calls; a fresh hash answer of
the verifier equal to a Merkle root the extractor reads (at most $2^{16}$ roots per verifier query,
$2^{-256}$ each); and a fresh permutation answer that passes the final query's proof of work
($2^{-127}$, once), which the extractor's replay of the fold challenges needs
(\lean{LeanVM.soundnessRpmAS_le_statement}).
\paragraph{Completeness} (\lean{LeanVM.Completeness}). The statement names its honest prover,
\lean{LeanVM.leanVmHonestProver}: the executable \lean{LeanVM.Prover.prove}
(\lean{Statement/Prover/}), its Keccak-256 and Keccak-f[1600] calls answered here from $\pi$; with
the deployed Keccak it is \texttt{lake exe leanvm-prove}. It runs the execution once to obtain the
witness, then plays the honest moves against the verifier's own program. Its only search is the
proof-of-work nonce search within its fuel, and it sees hash answers only as the challenges the
verifier samples. On the test corpus ($17$ programs at $4$ rates) its proofs are byte-identical to
the Rust prover's, and both verifiers reject every mutation of them.
For every program $\mathit{prog}$, public input $x$ and valid execution of $\mathit{prog}$ on $x$ of committed size at
most $2^{30}$ cells, at every inverse rate $2^\rho$ with $1 \le \rho \le 4$, trying $2^{35}$ nonces
per proof of work (the widest grind within that size is the bus's, $27$ bits),
\[
\boxed{\ \Pr[\text{the verifier rejects the honest proof}] \le 2^{-256}\ }
\]
(\lean{LeanVM.completeness_holds}, through \lean{prove_eq_honestComp} in \lean{lean_vm}: the prover is the
specification's honest prover at the execution's witness). Completeness is not perfect only
because the proof of work is bounded: for any fuel $f \le 2^{64}$ the rejection probability is at
most
\[
\delta(f) = Q_f\,(1-2^{-27})^{f} + (Q_f\cdot 2^{30})^2/2^{508}, \qquad
Q_f = 13710 + 54825\,(2^{29} + 2f + 2)
\]
(\lean{LeanVM.Rpm.completenessRpm}, \lean{lean_vm}). The \emph{committed size} (\lean{Execution.committedSize}) of an
execution is
$3\cdot 2^{\kappa} + 2^{\ell} + 13h_{\mathrm{xor}} + 13h_{\mathrm{mul}} + 7h_{\mathrm{set}} +
14h_{\mathrm{deref}} + 14h_{\mathrm{jump}} + 28k + 2^6 k$, where $2^\kappa$ is the memory size,
$2^\ell$ the bytecode size, $h_{op}$ the least power of two at least the number of executed
instructions of opcode $op$, and $k$ the same for \texttt{KECCAK}, at least $2^9$.
\paragraph{The proof on the wire.} The end statements are about the structured proof. On the wire
a proof travels as bytes, its one encoding (\lean{crates/verifier/src/wire.rs}), each phase's
paths pruned to their positions, their sizes, the distinct leaves and the siblings no other path
gives; the pruning idea and its first formalization, on leanerVM's \texttt{main} branch, are
Nicolas Schleicher's (\url{https://github.com/scaraven}). The encoding is a compression layer, outside
\lean{Statement/}: \lean{lean_vm} transcribes the encoding and the decoding
(\lean{lean_vm/LeanVM/Wire/Encoding.lean}) and proves, as theorems of its own pinned with the end
theorems, that it is lossless on honest proofs (the round trip, \lean{LeanVM.Wire.roundTrip}, with
\lean{LeanVM.Wire.proveWithHash_wireDecodable}: the honest prover's proofs decode from their
encoding) and the only encoding of its proof (bytes that decode to a proof are its encoding,
\lean{LeanVM.Wire.oneEncoding}). That the transcription is the Rust's
\texttt{from\_bytes} and \texttt{to\_bytes} is test evidence (the wire differential: honest wire
proofs, their mutations and the Rust test's vector).
\section{The signature schemes and LeanDA}\label{sec:schemes}
In the signature games $q$ counts the adversary's own calls of $\pi$ and $\pi^{-1}$; in LeanDA's games
$Q$ counts every permutation call of the game. Every bound holds for every $q$ or $Q$ (a bound above
one says nothing).
\subsection*{The signature schemes}
\paragraph{leanXMSS} (\lean{LeanXmss.RandomPermutationModel.LeanXmssStronglyUnforgeable},
\lean{Statement/LeanXmss.lean}): a single key is strongly unforgeable under chosen-message attack
(multi-key security is not stated: a guessing reduction would have to simulate the other keys' key
generation and signing as its own, charged, calls, so it does not give $k\cdot(q+\mathit{slack})\cdot2^{-127}$ for
$k$ keys; a direct multi-key bound, the public parameters acting as salts, is plausible but not proved).
The game samples the key's seed, generates the keys, and runs the adversary with $\pi$,
$\pi^{-1}$ and a signing oracle; the adversary picks each request's leaf index and wins
only if no index is requested twice (re-signing the same message at the same index, which the crate allows, is a loss too), and its forgery wins if it verifies and is not a pair the
oracle returned. For every $q$, an adversary that itself makes at most $q$ calls of $\pi$ and
$\pi^{-1}$ on every path, and at most $2^{32}$ signing requests (a hypothesis of the Lean statement that costs nothing: past $2^{32}$ requests some leaf index repeats, so the adversary that stops there wins at least as often),
forges with probability at most
\[
\boxed{\ (q + 2^{10})\cdot 2^{-127}\ }
\]
(\lean{XmssSecurity.leanXmss_rpm_security}, \lean{Common.SufCma.StronglyUnforgeable}). Key
generation, the signer's hashing, its grinding through up to $2^{32}$ randomizers per layer
included, and the final verification are not charged to $q$. The constant is the random-oracle
step's $530 = (2\cdot384 + 290 + 2)/2$ (the forgery's verification counted in each of the proof's two
lanes, the first lane's forgery probes, two seed guesses) and the transfer's one unit, rounded up.
\paragraph{leanSPHINCS} has the same game and the bound $(q + 2^{19})\cdot 2^{-127}$ for every $q$
(\lean{Sphincs.LeanSphincsStronglyUnforgeable}, \lean{Statement/LeanSphincs.lean}), for at most
$N = 1\,182\,000\,000$ signing requests (\lean{Sphincs.leanSphincsStronglyUnforgeable}, from
leanVM's own random-oracle theorem \lean{FORS.h26_layered}, $(q + 265072)/2^{127}$: key
generation's $264193$ hash calls and the verification's $879$); staying within $N$ signatures is the key holder's duty (the signer does not
count them). The scheme is SLH-DSA (FIPS 205) on Keccak-256 with WOTS$^+$C: every tree, chain and
secret hash is $\mathrm{Trunc}_{16}(H(\mathrm{PK.seed} \Vert \mathrm{ADRS} \Vert M))$ with FIPS 205's
32-byte address, FORS trees are hashed to their roots, and the digest is two counter-mode calls on
the 32-byte message unframed (only the randomizer's $\mathrm{PRF}_{\mathrm{msg}}$ hashes pure
SLH-DSA's framing $M'$), read as FIPS 205's Algorithm~19. Its secret key is the crate's, the
32-byte $\mathrm{SK.seed}$, from which $\mathrm{PK.seed}$ and $\mathrm{SK.prf}$ are hashed again at
each signature, and its signer is the
crate's, hash call for hash call (the top tree built once, for the root and the top path, each FORS
tree built once, the layers from the bottom up). In leanXMSS the secret key is the crate's too: the
key's seed $S_0$ and the public parameter $P$ key generation derived, from which the signer derives
the scheme seed $S = H(\mathit{tag} \Vert S_0)$ again at each signature. A leanSPHINCS signature
costs about $2^{19}$ permutations in expectation and about $2^{33.6}$ in the worst case ($2^{32}$
encoding counters on each of its three layers); none of it is charged to $q$, and the bound does not
grow with the number of signatures. Signed messages are 32 bytes: a longer payload needs an outer
hash, whose collisions are outside the bounds. Both schemes are stated through one game,
\lean{Common.SufCma.StronglyUnforgeable},
and share the shape of one tweakable hash (\texttt{prefixed\_hasher}, \texttt{truncate} of each
scheme crate's \texttt{lib.rs}), hash chain and path fold.
\subsection*{LeanDA}
LeanDA commits to a matrix of blobs so that clients can check random pieces of it. Its statements are
Benedikt Wagner's framework, theorems and proofs, ported and instantiated with LeanDA
(\lean{Statement/LeanDa.lean}). Everyone in the games (the adversary, the argument, the verifier)
queries $\pi$ and $\pi^{-1}$ alone and hashes with Keccak-256 over $\pi$.
\paragraph{The matrix.} The matrix has $r$ rows, $1 \le r \le$ \lean{maxRows}, one blob each. A blob is a
payload of $2^{13}$ elements of $\mathbb{E}$, Reed-Solomon encoded to $2^{14}$ on a domain in
$\mathbb{K}$ (\texttt{leanDaErasureCode r}), so each of a row's two limbs is a codeword over $\mathbb{K}$. Each encoded row is cut into $128$ \emph{cells}, so the matrix has
$128\,r$ positions.
\paragraph{The commitment.} The committer hashes each row's $128$ cells into a Merkle tree, the
row's \emph{blob root} (\lean{blobRootWith}), builds the Merkle tree over the blob roots, the rows
padded to \lean{maxRows} with zero codewords, so every path has $7 + \mbox{\lean{logMaxRows}}$
siblings, and publishes the hash of its root with the row count $r$ (\lean{commitCells},
\lean{countBytes}). To \emph{open} a position, it gives the cell and its path, in its blob's tree
and then in the tree over the blob roots; the opening verifies if they and the row count hash back
to the root (\lean{verifyCellWith}).
\paragraph{The proof that the rows are codewords.} A Merkle root alone does not show that the rows
are codewords. So the committer also gives a proof, from some \emph{argument} (\lean{OracleArgument}: a
prover and a verifier that may query the oracles), that the cells satisfy LeanDA's relation
(\lean{relationWith}):
\begin{itemize}
\item the cells hash to the root, and
\item every row passes the \emph{membership test}: from the root, the duplex derives one
challenge $z \in \mathbb{E}$, which defines a codeword $L(x) = \prod_{j<13} (1 + z^{2^j}\,\widehat{W}_j(x))$ of the
dual code (\lean{dualCodewordAt}); every row must be orthogonal to $L$. A row that is not a codeword
passes with probability at most $(2^{13}-1)/2^{128} < 2^{-115}$: its inner product with $L$ is a
nonzero polynomial in $z$ of degree below $2^{13}$.
\end{itemize}
The challenge is ground (\lean{membershipChallengeWith}): the duplex seeded with the root absorbs
the nonces $0, 1, \dots$ of $64$ bits, each into a copy of the seeded sponge, and the first whose
permutation's third lane has $10$ low zero bits gives $z$, the first two lanes of that permutation.
The nonce is not sent; anyone deriving $z$ finds it, about $2^{10}$ permutations per root. If no
$64$-bit nonce is valid, the Rust search never ends; the statement then has no challenge and the
relation asks every row to be a codeword (\lean{membershipCheckOpt}), which keeps honest matrices
in the relation for every $\pi$.
\paragraph{Completeness} (\lean{LeanDa.LeanDaPerfectlyComplete}). If the argument is perfectly
complete, every position of an honest commitment to at most \lean{maxRows} rows opens and verifies, with probability $1$, for
every permutation $\pi$ (\lean{LeanDa.leanDa_perfectlyComplete_rpm}).
\paragraph{Position binding} (\lean{LeanDa.LeanDaPositionBinding}). No adversary can open one
position to two different cells. For every argument, with $Q$ permutation calls, it succeeds with
probability at most
\[
\boxed{\ (Q+1)^2\cdot 2^{-256}\ }
\]
(\lean{LeanDa.leanDa_positionBinding_rpm}).
\paragraph{Code binding} (\lean{LeanDa.LeanDaCodeBinding}). Position binding is not enough for
sampling. A committer could commit to rows that are not codewords; each opening would still
verify, but the cells clients receive would not come from one matrix of codewords, whose blobs could then not
be reconstructed. Code binding says this cannot happen.
\emph{The game} (\lean{codeBindingGame}). The adversary outputs a root, a proof, and some opened
positions (each with a cell and an opening). It wins if
\begin{itemize}
\item the argument's verifier accepts the proof,
\item every opening verifies, and
\item no codeword agrees with all the opened cells (\lean{ErasureCode.Consistent}).
\end{itemize}
\emph{The assumption.} Code binding can only be as good as the argument, so the theorem assumes the
argument is \emph{knowledge sound}. That means there is an extractor that, reading only the proof
and the adversary's queries (\lean{StraightLineExtractor}; it does not rewind), finds cells satisfying the
relation whenever the verifier accepts. Precisely: in the game \lean{knowledgeSoundnessGame}, an adversary making
$q \le 2^{128}$ calls makes the verifier accept while the extracted cells fail the relation with
probability at most $(q + c)\cdot 2^{-k}$, for some constants $c$ and $k$.
\emph{The theorem.} Under this assumption, an adversary making $Q$ calls (any $Q$, verifications
included) wins the code-binding game with probability at most
\[
\boxed{\ (Q + c + 2^{65})\cdot 2^{-k} + (Q + 2^{10})\cdot 2^{-125} + (Q + 2^{22})^2\cdot 2^{-247}\ }
\]
(\lean{LeanDa.leanDa_codeBinding_rpm_bound}). At $Q = 2^{64}$ the last two terms are about
$2^{-61}$ and $2^{-119}$. The offset $2^{65}$ of the first term is the knowledge-soundness game's
own calls beyond the adversary's: the relation's check hashes the extracted matrix (fewer than
$2^{22}$ calls) and, on its worst path, runs the whole nonce search, $2^{64} + 2$ calls; the
assumption is read at $q = Q + 2^{65}$. Note that because \lean{QueryCostAtMost} is worst-case over
all paths, this $2^{65}$ offset imposes an additive floor of $2^{65 - k}$ on the first term even at
$Q = 0$, $c = 0$ (i.e.\ $2^{-60}$ at $k = 125$, and vacuous for $k \le 65$).
\emph{Why.} Run the extractor on the adversary; it returns cells $c^*$. One of three things holds.
\begin{enumerate}
\item $c^*$ fails the relation. Then the adversary breaks the argument's knowledge soundness:
the first term.
\item $c^*$ satisfies the relation but has a row that is not a codeword. Then it passed the
membership test by luck: the second term. The grind makes luck cost permutation calls. A call of
the adversary on one of a root's nonces gives a valid proof of work and an accepting challenge at
once with probability at most $2^{-10}\cdot(2^{13}-1)/2^{128} < 2^{-125}$, the two independent;
the verifier's own search for the root, however many nonces it tries, stops at its first valid
one, so it is a single fresh try, $(2^{13}-1)/2^{128} < 2^{10}\cdot 2^{-125}$.
\item $c^*$ is a codeword. Every opened cell hashes to the same root as $c^*$, so unless Keccak-256
has a collision, each opened cell is $c^*$'s cell, and the codeword $c^*$ agrees with all of them:
the adversary loses. Collisions and other bad hash events give the third term.
\end{enumerate}
\emph{What is open.} The assumption can be met: the argument whose proof is simply all the cells
is complete and knowledge sound, though its proof is as large as the matrix (an observation, not
formalized). The deployed argument is leanVM proving the relation inside the guest program. It cannot
meet the assumption in this model: its relation uses the real Keccak-f[1600], not $\pi$, so an
adversary computes a root with no query to $\pi$ and proves its opening honestly, and no
straight-line extractor finds a $\pi$-preimage of it. Code binding covers the arguments whose
relation is evaluated over $\pi$; for the deployed one it would need a model that ties the guest
program's Keccak to $\pi$ (Section~\ref{sec:notgive}, and the first item of the last section).
\section{The leanISA guest program (aggregation)}\label{sec:guest}
The guest program aggregates: from signatures, DA matrices and child proofs, it proves one statement
holding all their claims. This section defines what it proves and states what is proved about it.
Every definition named here is in \lean{Statement/}: what a node proves in
\lean{Statement/LeanVmGuest.lean} (with the statement and its digest), the batching program
in \lean{Statement/LeanVmGuestBatching.lean}, the completeness statements and the batching's
soundness in \lean{Statement/LeanVmGuestCompleteness.lean}, the decoder program's also in
\lean{Statement/LeanVmGuest.lean}, the composed statements in \lean{Statement/Corollaries.lean}; names
marked \lean{lean_vm} are the proofs'.
\subsection{The objects}
\paragraph{The guest program} $G$ (\lean{LeanVM.Guest.guestProgram}) is leanVM's compiled aggregation
program (\texttt{guests/lean\_ethereum.py} in this tree),
transcribed as generated data (\lean{Statement/Data/}). Its bytecode $B$ has $2^{19}$ instruction
slots of $16$ words of $\mathbb{F} = \mathrm{GF}(2^{64})$, so $2^{23}$ words
(\lean{bytecode_length}, in \lean{lean_vm}). Below, $H$ is Keccak-256 and
$\mathbb{E} = \mathbb{F}[y]/(y^2+xy+1)$, the field of $2^{128}$ elements. Its \emph{deployed seed}
\[
iv_G = \mathrm{IV}(B) = H(\mathit{TAG} \,\|\, \bar B), \qquad \mathit{TAG} = \texttt{leanvm-v1}
\]
(\lean{deployedSeed}, \lean{fiatShamirIvWith}, \texttt{crates/verifier/src/layout.rs},
\texttt{bytecode.rs}), the hash of the proof system's $9$-byte version tag and the bytecode's
words as $8$-byte little-endian strings, is the Fiat-Shamir initial value prover and verifier
derive from the bytecode; a test run by the gate (\texttt{lake exe node-vectors}) checks it against
leanVM's \texttt{fs\_seed}.
\paragraph{A statement} $s$ (\lean{NodeStatement}) consists of
\begin{itemize}
\item a list $\Cx$ of leanXMSS claims and a list $\Cs$ of leanSPHINCS claims, each a pair $(pk, m)$
meaning ``$pk$ signed $m$'';
\item a \emph{DA digest} $\mathit{da}$ (\lean{NodeClaims.daDigest}): either $H(\rho \,\|\, z)$ of one
data-availability claim (\lean{DaClaim}, \lean{daClaimDigest}), a matrix root $\rho$
(\lean{daRoot}) and a membership challenge $z \in \mathbb{E}$ (\lean{membershipChallenge}, as its
two limbs and two zero words), or $32$ zero bytes without one (\lean{zeroDigest};
\texttt{verifier::da::digest}, \texttt{crates/verifier/src/da.rs}). The claim: some matrix of
$1$ to \lean{LeanDa.maxRows} encoded blobs with root $\rho$ has every row orthogonal to the dual codeword $L$ of $z$
(\lean{Da.MatrixWitness.Opens}), which the guest program builds from $z$. The outer verifier holds
$\rho$, derives $z$ from $\rho$ (Section~\ref{sec:schemes}) and checks $\mathit{da} = H(\rho \,\|\, z)$; that
this derivation makes the rows codewords is not proved (Section~\ref{sec:notgive});
\item a \emph{deferred claim} $c = (\zeta, v)$, $\zeta \in \mathbb{E}^{23}$, $v \in \mathbb{E}$, meaning
that the multilinear extension $\widehat{B}$ of the bytecode, as a function on $\{0,1\}^{23}$,
satisfies $\widehat{B}(\zeta) = v$ (\lean{DeferredBytecodeClaim.HoldsWithShape}).
\end{itemize}
\paragraph{The statement's digest} under a seed $\sigma$ (\lean{statementDigest},
\texttt{crates/aggregation/src/statement.rs}) is
\[
\mathrm{dig}_\sigma(s) = H\big(\sigma \,\|\, H(\enc(\Cx)) \,\|\, H(\enc(\Cs)) \,\|\, \mathit{da} \,\|\, \enc(c)\big),
\]
where $\enc(\Cx)$ concatenates, per claim, the key's bytes, a leanXMSS key's root ($16$ bytes)
then its parameter ($16$), and the message ($32$); $\enc(\Cs)$ likewise, a leanSPHINCS key's bytes
being $\mathrm{PK.seed}$ then $\mathrm{PK.root}$ (\lean{claimListDigest},
\texttt{crates/aggregation/src/statement.rs}); and $\enc(c)$ is the $16$-byte encodings of
$z_1, \dots, z_{23}, v$. The lists' lengths are bound by Keccak's padding;
the deferred claim's encoding carries no length, so deferred claims are told apart only at one
shape. The guest program's public input is this $32$-byte digest.
The seed $\sigma$ is the Fiat-Shamir IV with which $G$ verifies its children's proofs, meant to be
proofs of $G$ itself (the deferring verifier reads $G$'s bytecode only through its length, so it
accepts as well a proof of any program of that length: Section~\ref{sec:notgive}). $G$ cannot contain its own IV (a hash of its own bytecode), so it reads
$\sigma$ as input, and the digest binds it; the outer verifier computes the digest with
$\sigma = iv_G$.
\paragraph{A witness} $w$ (\lean{NodeWitness}) consists of
\begin{itemize}
\item a list of \emph{children}, each a statement $s_i$, a proof $p_i$, and a \emph{fresh} claim
$f_i = (\zeta_i, v_i)$ on the bytecode, the evaluation the child's proof leaves to be checked;
\item the \emph{raw signatures}, leanXMSS and leanSPHINCS, each with the claim it signs;
\item optionally, one LeanDA matrix the node checks directly, with the DA claim it opens;
\item the \emph{batching hints}: a proof of work's nonce, the round messages of one sumcheck, and a final value.
\end{itemize}
\subsection{What one node establishes}
$\mathrm{NodeRel}(B, \sigma, s, w)$ (\lean{NodeRelation}) is the conjunction of four conditions,
the witnesses holding the claims:
\begin{enumerate}
\item Every signature claim of $s$ is held (\lean{SignatureClaimsHeld}): every raw signature verifies
under its claim's key and message (Keccak-256 as the schemes' hash, at any leaf index), and every
claim of $s$ is a raw signature's claim or occurs in the corresponding list of some child's $s_i$.
\item The DA digest is accounted for (\lean{DaDigestHeld}): with a direct matrix,
$\mathit{da} = H(\rho \,\|\, z)$ of the claim it opens; without one, $\mathit{da}$ is zero or
some child's DA digest (the guest program's \texttt{da\_pick}, \texttt{lean\_ethereum.py}).
\item Every child is proven (\lean{ChildrenProven}): its deferred claim has the bytecode's shape,
and the \emph{deferring verifier} accepts its proof: $\mathrm{verifyDeferred}(B, \sigma,
\mathrm{dig}_\sigma(s_i), f_i, p_i) = \mathsf{true}$. The deferring verifier is the zkVM verifier
except that, where the proof claims a value of $\widehat{B}$ at the point its bytecode sumcheck
reaches, it does not evaluate $\widehat{B}$ there but requires that point and value to be the claim
$f_i$ (\lean{claimedBytecodeValue}). It runs on the real Keccak-256 and Keccak-f[1600], the ones the guest program
computes.
\item The deferred claim batches the children's (\lean{DeferredClaimBatched}). With no children, its
point is all-zero (its value is left to the outer verifier); otherwise $\mathrm{batch}\big(
(\mathrm{dig}_\sigma(s_i), f_i, c_i)_i, \text{hints}\big) = c$ (\lean{nodeBatchingProgram} run by
\lean{runBatching}; \lean{batch} in \lean{lean_vm}), with $c_i$ the deferred claim of $s_i$. The
batching is a Fiat-Shamir transcript on Keccak-f[1600], seeded from the hash of the label
\texttt{leanvm/recursion-aggregation/v1}: it absorbs the number of children, then each child's
digest and two claims; checks a proof of work of $2$ bits (\lean{batchLambdaGrindBits}) and squeezes one challenge $\lambda \in \mathbb{E}$, whose powers batch the
claims (\lean{lambdaPowers}); and runs one degree-$2$ sumcheck reducing
$\sum_i (\lambda^{2i} v_i + \lambda^{2i+1} v'_i)$, with $v_i$
the value of $f_i$ and $v'_i$ that of $c_i$, to one claim on $\widehat{B}$ at a new point.
Either way $s$'s deferred claim has the bytecode's shape: its point has $23$ coordinates
(\lean{DeferredBytecodeClaim.HasBytecodeShape}), the zero point's or the sumcheck's challenges.
\end{enumerate}
\lean{NodeRelation} does \emph{not} say that a child's claims are true, only that the deferring verifier,
run on the real Keccak, accepts its proof. Whether that makes them true is the soundness of leanVM
with Keccak instantiated, which is not proved (Section~\ref{sec:notgive}).
\paragraph{The outer verifier} (\texttt{AggregateProof::verify},
\texttt{crates/aggregation/src/proof.rs}) additionally checks that the DA digest is that of its root
with the root's membership challenge, that the deferred claim holds ($\widehat{B}(\zeta) = v$), and
the lists' form (sorted, no repeats). Of these, \lean{AggregateSound} below
assumes only that the deferred claim holds (\lean{DeferredBytecodeClaim.HoldsWithShape}); no end statement
models the DA digest's derivation or the lists' form. Without the derivation, the DA condition says
nothing of the blob: \lean{MatrixWitness.Opens} accepts any challenge the digest binds, $z = 0$
included, whose dual codeword is all ones.
\subsection{Soundness}
The outer verifier accepts a proof that $G$ ran on the public input $x = \mathrm{dig}_{iv_G}(s)$.
What does that establish about $s$? The answer has three parts, each an end theorem.
\begin{enumerate}
\item \textbf{The zkVM is knowledge sound} (\lean{KnowledgeSoundness},
Section~\ref{sec:zkvm}). Except with probability
\[
\varepsilon(Q) = (Q+2^{14})\cdot 2^{-125} + 5\,(Q+2^{14})^2\cdot 2^{-256},
\]
the extractor returns a valid execution $t$ of $G$ on $x$. This is the only step with an oracle
and a probability.
\item \textbf{Every execution of $G$ proves a statement} (\lean{GuestKnowledgeSoundness}). From
every valid execution $t$ of $G$ on any public input $x$, the decoder program $D$ outputs, within
its budget, a seed $\sigma'$, a statement $s'$ and a witness $w'$ with
\[
\mathrm{dig}_{\sigma'}(s') = x \qquad\text{and}\qquad \mathrm{NodeRel}(B, \sigma', s', w').
\]
\item \textbf{The digest binds} (\lean{StatementDigestBinds}). Let $(\sigma, s)$ and $(\sigma_0, s_0)$
be seeds and statements whose deferred claims have the bytecode's shape. If
$\mathrm{dig}_\sigma(s) = \mathrm{dig}_{\sigma_0}(s_0)$, then $(\sigma, s) = (\sigma_0, s_0)$, or
Keccak-256 collides on one of three pairs of inputs (\lean{collisionCandidates}): those of the
outer hash, of $H(\enc(\Cx))$ and of $H(\enc(\Cs))$. The DA digest enters the outer input as it
is, so it needs no pair of its own.
\end{enumerate}
Steps 2 and 3 are facts about $G$'s code and the digest: no oracle, no probability, and Keccak is
the deployed function $G$ computes.
\paragraph{Chained.} Steps 1 and 2 compose: except with probability $\varepsilon(Q)$, an accepted
proof of $G$ on any $x$ yields an extracted execution on which $D$ outputs, within its budget, a
decoding $(\sigma', s', w')$ with $\mathrm{dig}_{\sigma'}(s') = x$ and
$\mathrm{NodeRel}(B, \sigma', s', w')$ (\lean{lean_vm} proves this for its
\lean{transcriptExtractor} and its memory decoder \lean{decode}: \lean{aggregate_knowledge}). Step 3
with $(\sigma_0, s_0) = (iv_G, s)$ then gives \lean{AggregateSound} (from the fields alone,
\lean{LeanVM.corollaries_of_theorems}, \lean{lean_vm}): except with probability $\varepsilon(Q)$, if
the verifier accepts a proof of $G$ on $\mathrm{dig}_{iv_G}(s)$, for any $s$ whose deferred claim
holds (\lean{DeferredBytecodeClaim.HoldsWithShape}, as the outer verifier checks), the extracted execution $t$
\emph{explains} $s$
(\lean{ExplainsStatement}):
\begin{itemize}
\item $D$ decodes $t$ to $(iv_G, s, w')$ with $\mathrm{NodeRel}(B, iv_G, s, w')$, or
\item the decoded seed and statement, with $(iv_G, s)$, give a Keccak-256 collision among the
three pairs.
\end{itemize}
For one execution and \lean{lean_vm}'s decoder \lean{decode}, steps 2 and 3 together are
\lean{decode_binds} (\lean{lean_vm}).
Two Keccaks meet here. The verifier of step 1 runs on $\pi$: Keccak-256 is the sponge over $\pi$,
Keccak-f is $\pi$, and its transcript starts from the IV computed over $\pi$, while the digest's
seed $iv_G$ is the IV over the deployed Keccak. The digest, \lean{NodeRelation} (the children's proofs, the signatures, the
batching) and the collision use the deployed Keccak, which $G$ executes. The collision is therefore
not an event of small probability: it is a concrete pair of inputs, read off $t$ and $s$, on which
the deployed Keccak-256 collides.
\paragraph{Why a decoder.} \lean{GuestKnowledgeSoundness} could have said only that some
$(\sigma', s', w')$ exists (\lean{guest_sound} in \lean{lean_vm} proves that too). It says more: the
witness is computed \emph{from} the execution, by a program within a budget. That is what makes the
extracted execution knowledge of a witness. But a decoder given as a Lean function may use classical
choice, and one that simply chose some triple satisfying the conclusion would make
\lean{GuestKnowledgeSoundness} no stronger than the existential. The statement is only as strong as
its decoder, so the decoder is a parameter of the same kind as the extractor: a cost-machine program
$D$ (\lean{Statement/LeanVmGuest.lean}) of size at most \lean{guestWitnessDecoderSizeBound} (its
literals, the guest program's per-function tables, counted in full), run within
\lean{guestWitnessDecoderBudget} on the encoded program and execution
(\lean{encodeGuestWitnessDecoderInput}), whose output must be the encoding (\lean{encodeValue}) of a
decoding that explains the input; there is no parse, and the encoding is injective
(\lean{encodeValue_decoded_injective}, \lean{lean_vm}). A program chooses nothing. The statement
accepts any program that computes the witness from the execution within the budget, not only one
that reads it off the memory, just as it asks of the extractor program only that it compute a valid
execution within its budget. A program that output another statement of the same digest would
exhibit a Keccak-256 collision; what excludes it is that none is known.
\paragraph{The decoder's budget.} The budget (\lean{guestWitnessDecoderBudget}) is
$(\mathit{steps} + 1)(2^{21} + 2^{13}\lambda) + (70\kappa + 374 + 2^{23} + 2^{14}\lambda)\cdot 2^\kappa + 2^{37}(\lambda + 16)$,
$\lambda = \log_2(\mathit{steps} + 1)$, above the closed-form price \lean{lean_vm} proves of the
compiled decoder: per step, the replay and the filing of the state in a sorted array (its share of
one sort, growing as $\log$ of the steps); per memory word, the sorted table of the memory's
addresses and the witness read at the counts a valid execution bounds, each below the memory's
size ($G$ checks every announced count to be a memory address, \lean{valid_counts}); and
$2^{37}(\lambda + 16)$ for the rest of the witness: $G$'s own asserts give at most $16$ children,
each child's cursor is at most $8192$ words, as the stream of its proof is, which the deferring
verifier accepts on a valid execution (\lean{valid_cursor}, from
\lean{stream_le_of_verifyDeferred}), and the decoder clamps the DA matrix's row count at \lean{LeanDa.maxRows}. The
budget is $2^{43.90}$ at $\kappa = 20$ and $2^{20}$ steps, $2^{47.44}$ at $\kappa = 24$ and
$2^{24}$, $2^{51.42}$ at $\kappa = 28$ and $2^{28}$, $2^{53.42}$ at $\kappa = 30$ and $2^{30}$,
$2^{70.25}$ at $\kappa = 30$ and $2^{49}$, and $2^{81.30}$ at $\kappa = 30$ and $2^{60}$ (the price
there, at counts up to the memory's size: $2^{43.19}$, $2^{47.02}$, $2^{51.02}$, $2^{53.03}$,
$2^{69.92}$, $2^{80.98}$). The budget prices the witness at the bounds above, not at the run's, so
with fewer children and claims it is several times the compiled decoder's price. There is no cap on the steps in the budget. A valid execution of $G$ (\lean{ValidExecution})
has fewer than $2^{49}$ steps: the memory is fixed and every instruction reads a cell at
$\mathit{fp}\cdot o$ for an offset $o$ fixed by $\mathit{pc}$, so at each $\mathit{pc}$ at most
$2^\kappa$ values of $\mathit{fp}$ let a step succeed; the run is determined by
$(\mathit{pc}, \mathit{fp})$, and a repeated state would loop without halting
($2^\ell\cdot 2^\kappa$ states, $\ell = 19$, $\kappa \le 30$; argued, not a Lean theorem;
\lean{lean_vm} proves fewer than $2^{128}$, \lean{steps_lt_replayFuel}).
\paragraph{The decoder's size bound.} The bound (\lean{guestWitnessDecoderSizeBound}, $568917$)
limits any program; it is the compiled decoder's size, $568507$ (proved
at most that; it measures $566531$; the guest's frame-cell table is $515352$ of it), and a slack of
$410$: room for one leanXMSS signature's encoding ($309$) beside its code but not two, so no useful
table of witnesses (hard-coded signatures that would mask a bug of $G$ on finitely many statements)
fits there. It does not bound what a program written differently could hold: the frame-cell table
(cells below $2^{20}$) packs to about a third, three cells to a limb, and a program may compute its
tables from its input.
The proofs' decoder is \lean{LeanVM.Guest.End.decode}, defined in \lean{lean_vm}; a program
computing it within its size bound and budget gives \lean{GuestKnowledgeSoundness}
(\lean{guestKnowledge_of_decode}, \lean{lean_vm}). It replays the run:
\begin{itemize}
\item the seed and the statement from \texttt{main}'s frame, read through the sorted table of the
memory's $2^\kappa$ addresses;
\item each signature, matrix, child proof and batching hint from the frame of the function that
checked it: the run is stepped from its initial state through the program's and the memory's
tables, and each call is given the frame at which the run first entered its callee, its
precondition decided there.
\end{itemize}
It runs the machine (whose \texttt{KECCAK} instruction checks Keccak-f[1600]) and no verifier,
decides no proposition classically and picks no witness. The test
\lean{LeanVMTests.Guest.DecodeNoChoice} checks this by following every definition the decoder
unfolds to.
\paragraph{The batching on its own} (\lean{BatchingSound}). The batching of \lean{NodeRelation}'s fourth
condition is also proved sound as a verifier in its own right, in the RPM: Keccak-256 is the sponge
over $\pi$, Keccak-f is $\pi$, and it accepts when the sumcheck closes and the claim it outputs
holds of $\widehat{B}$ (\lean{runBatching} of \lean{boundedBatchingProgram}). Fix a bytecode $B$ of power-of-two
length and $M \le 2^{64}-1$. An adversary making $Q_A$ queries to $\pi$ and $\pi^{-1}$ outputs a
proof. The probability that the batching accepts it while its proof stream begins with fewer than
$M$ children of the bytecode's shape, one of whose claims (fresh or carried) is false
(\lean{SomeChildClaimFalse}), is at most
\[
\boxed{\ (Q_A + Q_V + 1)\cdot \max(2M-3,\,8)\cdot 2^{-130} + 5\,(Q_A+Q_V)^2\cdot 2^{-256}\ }
\quad\text{for } Q_A \le 2^{128},\ Q_V \le 2^{96},
\]
where $Q_V$ (\lean{batchingQueryBound}) is the batching's own query bound for $M$ children (about
$2^{68}$ for $G$'s bytecode at $M = 2^{64}-1$; \lean{batch_sound_holds}, \lean{lean_vm}). The factor $\max(2M-3, 8)\cdot 2^{-130}$ bounds each query's chance at a challenge. A sumcheck round's challenge is bad at at most $2$ values, $2/|E| = 8\cdot 2^{-130}$. The single challenge $\lambda$ weighs the gaps (claimed minus true value) of the $2n$ claims of $n < M$ children by its powers: they form a polynomial in $\lambda$ of degree at most $2n-1 \le 2M-3$, nonzero when a claim is false, which vanishes at at most $2M-3$ values; and a query reaches $\lambda$ only by passing the proof of work of $2$ bits before it (\lean{batchLambdaGrindBits}), with probability $2^{-2}$. For $G$'s $16$ children, $M = 17$: $31\cdot 2^{-130} \approx 2^{-125.05}$ per query.
\subsection{What the soundness theorems do not give}\label{sec:notgive}
They speak about one node. A claim the root holds through a child carries no knowledge by itself:
the deferring verifier reads the bytecode only through its length and holds the bytecode's value
the proof claims at the child's point to the witness (the fresh claim $f_i$), which no end statement
requires true, so
a proof of any program of $G$'s length, under the node's seed, makes a child of any statement. A
child's claims mean something only once its fresh claim is true. That needs the root's deferred
claim recomputed, as the outer verifier does (\lean{AggregateSound} assumes it), and the batching
sound inside the circuit at every level, so that a true batched claim makes the children's fresh and
carried claims true; and to conclude from an accepted root that every claim held at the leaves, one
would need, at each internal node, the soundness of the children's proofs \emph{as the guest
program verifies them}: with the real Keccak-256 and Keccak-f, not with $\pi$. That is the
Fiat-Shamir heuristic for an instantiated hash, and it is not proved. Likewise \lean{BatchingSound} is
the batching outside the circuit, with Keccak-f $= \pi$; it does not compose with the in-circuit
statements, whose \texttt{KECCAK} instruction computes the deployed Keccak-f[1600], so soundness
across recursion levels does not follow from it.
\subsection{Completeness}
\paragraph{The hypotheses,} on a statement $s$ and a witness $w$ with
$\mathrm{NodeRel}(B, iv_G, s, w)$, under the deployed seed:
\begin{enumerate}
\item \lean{DeployedLimits}, the node's limits: each declared list
is a sub-multiset of the raw signatures' claims and the children's lists (a claim declared $n$ times
is held $n$ times, each raw signature or child's entry used once); and the node's fixed capacities: at most $16$ children holding at most $2^{17}$ claims in their lists in all, at most $2048$ leanXMSS and $512$ leanSPHINCS signatures held directly, and a blob matrix held directly of at most \lean{LeanDa.maxRows} rows. Every node of a tree aggregating $2^{17}$ signatures of one scheme is within them: $64$ leaves of $2048$ leanXMSS signatures (or $256$ of $512$ leanSPHINCS), nodes of $16$ leaves each, and a root over those. The guest program enforces the sub-multisets, the $16$ children and the blob matrix's rows, not the other capacities: a node past one of them is still accepted, and the prover may still prove it, but the theorems below do not cover it.
\item Every child carries an honest proof (\lean{HonestChild}): its fresh claim is true of the
bytecode (\lean{BytecodeClaim.Holds}); its proof is the one the named honest prover
\lean{LeanVM.leanVmHonestProver} makes with the deployed Keccak
($2^{35}$ nonces per proof of work) of an execution of $G$ on $\mathrm{dig}_{iv_G}(s_i)$ (the
prover makes none past $2^{30}$ committed words, and $G$ opens every stack the verifier admits of an
execution of its bytecode, of log $20$ to $30$); and the verifier that also refuses
every zero challenge (\lean{verifierRefusingZero}, through
\lean{VerifierProgram.refusingZeroChallenge}, which fails on every zero challenge the verifier
program samples) accepts it with the deployed Keccak. The guest program divides by the fold and tail
challenges and by each non-final level's batching challenge $\lambda$ at the stacked opening; refusing every zero
challenge is slightly stronger, each challenge being zero with probability $2^{-128}$. An honest
proof is refused with probability at most $2^{-100}$ in the RPM (\lean{HonestProofRarelyRefused}
below).
\end{enumerate}
What the guest program checks of a child is in \lean{lean_vm} (\lean{AcceptableChild}): the
statement's deferring-verifier conditions; a stack log of $20$ to $30$ announced (the guest program
has one opening arm per stack log, eleven in all, the rate dispatched inside it) and a proof stream of at most $8192$ field
elements; at each query step of its deferring verifier, the Merkle openings agreeing wherever they
share a node of the tree (an honest prover's openings, all from one tree, agree); and no zero
challenge in its deferring verifier. \lean{lean_vm} proves that honest children meet it
(\lean{guest_child_complete}, with \lean{freshClaim_unique}: the deferring verifier accepts a proof
with at most one true claim, so the child's fresh claim is the one its run evaluates).
\paragraph{The capacities.} \lean{lean_vm} bounds the words a run of $G$ allocates and the instructions of each opcode it executes by linear forms in the node's counts (its declared claims, coverage slots, raw signatures, blob rows and padded rows, children and their claims), counted from $G$'s code, not measured, each child at its own opening arm. At the capacities, each child charged at $G$'s largest opening arm, $\mu = 30$, a run allocates at most $2^{26}$ words and executes at most $2^{23}$ \texttt{XOR}, $2^{24}$ \texttt{MUL}, $2^{22}$ \texttt{SET}, $2^{23}$ \texttt{DEREF}, $2^{21}$ \texttt{JUMP} and $2^{21}$ \texttt{KECCAK} instructions, so its committed size (Section~\ref{sec:zkvm}) is at most $3 \cdot 2^{26} + 2^{19} + 13 \cdot 2^{23} + 13 \cdot 2^{24} + 7 \cdot 2^{22} + 14 \cdot 2^{23} + 14 \cdot 2^{21} + 92 \cdot 2^{21} \approx 2^{29.74}$, and the coverage table, at most $2048 + 512 + 2^{17}$ slots, is below $2^{23}$, below the memory the execution has.
\paragraph{The theorems.} Each concludes that $G$ has a valid execution $t$ on public input
$\mathrm{dig}_{iv_G}(s)$ with $\mathrm{size}(t) \le 2^{30}$ (committed size), so that its honest
proof is a child \lean{HonestChild} admits.
\begin{itemize}
\item \lean{GuestCompleteOnHonestChildren}: under hypotheses 1 and 2, for every node within \lean{DeployedLimits}, each child at any $\mu \in [20,30]$ and $r \in [1,4]$.
\item \lean{guest_complete_on_acceptable_children} (\lean{lean_vm}): under hypothesis 1 and \lean{AcceptableChild} for every child, at any seed.
\item \lean{aggregate_complete_of} (\lean{lean_vm}, in the RPM): the execution so obtained,
proved by the honest prover at $\rho \in [1,4]$ with $f \le 2^{64}$ nonces, is rejected with
probability at most $\delta(f)$ of Section~\ref{sec:zkvm}.
\end{itemize}
\paragraph{Honest proofs are rarely refused} (\lean{HonestProofRarelyRefused}). For the same named
prover \lean{LeanVM.leanVmHonestProver}: in the RPM, with $2^{35}$ nonces per proof of work, it
makes no proof, or the verifier that also refuses every zero challenge
(\lean{verifierRefusingZero}) rejects its proof, of any valid execution
of committed size at most $2^{30}$, at $1 \le \rho \le 4$, with probability at most $2^{-100}$. The
guest program checks a child with the deployed Keccak, so the bad events (a proof of work with no
nonce within its fuel, a zero challenge) are bounded in the
RPM for the same prover and check, and their absence at the deployed Keccak is what
\lean{HonestChild} asks. Completeness thus holds level after level as far as the deployed Keccak
behaves like $\pi$ for these events; that step is the model's assumption, not a theorem. Not stated
either: that honest batching hints exist, that batching true claims gives a deferred claim that
holds, and that the outer verifier accepts an honest root (see the last section).
\section{What is not proved}
\begin{itemize}
\item The \texttt{KECCAK} instruction a program executes computes the real Keccak-f[1600], not
$\pi$: the RPM idealizes the proof system's hash, not the guest program's computation. It thus
excludes, by construction, programs that evaluate their own proof's Fiat-Shamir duplex
(Khovratovich, Rothblum and Soukhanov, 2025); the assumption is that Keccak-f[1600] behaves as a
random permutation even to programs that compute it. Statements
about the guest program's own execution use the deployed Keccak-256, under the assumption that no
one finds a Keccak-256 collision.
\item Soundness across recursion levels (Section~\ref{sec:notgive}); completeness across levels
holds only through \lean{HonestProofRarelyRefused}.
\item That the cost machine's prices are honest (Section~\ref{sec:zkvm}): trusted, as the
statement's model of computation (a one-limb operation, the carry-less product included, at one
unit: a few instructions of a 64-bit CPU).
\item Security against quantum adversaries (a quantum random-permutation model), for the
signature schemes and for leanVM's Fiat-Shamir: every statement is about classical adversaries.
\item LeanDA's code binding for an argument whose relation uses the deployed Keccak-f[1600] rather than $\pi$ (leanVM's in-circuit DA check), and the link from the guest
program's DA check (\lean{Da.MatrixWitness.Opens}) and the outer verifier's derivation of the challenge to
LeanDA's code binding.
\item That a parent can always form its witness from honest children (the batching hints exist),
that batching true claims gives a true deferred claim, and that the deployed outer verifier
(\texttt{AggregateProof::verify}) accepts an honest root.
\item Completeness for children whose proofs are not \lean{LeanVM.leanVmHonestProver}'s with the
deployed Keccak (the Rust prover's, say), or under another seed than the deployed one:
\lean{HonestChild} names the proof.
\item Completeness for a node beyond a capacity whose run still fits $2^{30}$ (one holding more raw signatures and fewer children, say): the capacities are a box under $2^{30}$, each child charged at the largest opening arm.
\item Which programs $P$ and $D$ are: the statement takes them as parameters within their size
bounds and budgets; the end theorem holds at \lean{lean_vm}'s compiled \lean{transcriptExtractor}
and \lean{LeanVM.Guest.End.decode} (\lean{LeanVM.Cost.compiledKnowledgeExtractor},
\lean{LeanVM.Cost.compiledGuestWitnessDecoder}).
\item That the extracted execution is the one the proof commits to: \lean{KnowledgeSoundness}
asks only for some valid execution of $\mathit{prog}$ on $x$, and \lean{AggregateSound} decodes that one.
\item That a valid execution of $G$ has fewer than $2^{49}$ steps (Section~\ref{sec:guest}): argued,
not a Lean theorem (\lean{lean_vm} proves fewer than $2^{128}$, \lean{steps_lt_replayFuel}); the
decoder's budget has no cap on the steps, and it prices the witness at the bounds a valid
execution's asserts and its children's accepted proofs give ($16$ children, claims of each scheme
below the memory's size, a cursor of $8192$ words each), not at the run's.
\item That the size bounds exclude a table of witnesses for every program: literals count toward
size, and the bounds are tight only for programs written like the compiled ones (a decoder
written differently could pack the guest's frame-cell table about three times tighter, freeing
room for about $1120$ signatures' encodings, or compute it from its input, freeing room for about $1690$).
\item How $D$ computes the witness: the statement accepts any program that computes it from the
execution within its budget, not only one that reads it off the memory.
\item A tight extractor budget: it is $2^{\max(58,\,2\mu + 9)} + O(N\log^3 N)$, priced at the worst shape of each stack size.
\item Knowledge soundness for a bytecode table that encodes no program (Section~\ref{sec:zkvm}): the Rust verifier rejects one (\texttt{Bytecode::new}), the statement assumes none.
\item The Rust verifier, prover and guests. They are tested against the Lean specification: the
verifier differential fuzz; the wire differential (the Lean decoding against the Rust
\texttt{Proof::from\_bytes} on honest wire proofs and their mutations); the prover differential (the Lean prover's proofs byte-identical to the
Rust prover's, accepted by both verifiers, every mutation rejected by both), which does not yet
include an execution of the guest program; the guest-diff check on real aggregations; and the node
vectors.
\item Witness generation: the Lean prover takes the execution (memory and hints) as input, checks
it, and computes the committed columns from it, but nothing in Lean runs a program on its private
inputs; in the prover differential the executions come from leanVM's Rust interpreter.
\item The Lean prover's speed: compiled, it takes about $24$ times as long as the multithreaded
Rust prover on the test corpus ($2876$ s against $119$ s), and no complexity bound is proved.
\end{itemize}
\end{document}