Customs Check for Code: Guaranteeing Error-Free Optimization of Kids' Programs ✛
Context
Consider a children's game written in the Scratch system: a character appears in the center of the screen, then instantly jumps to a corner. No one saw the first move — it vanished between frames. Removing it would break nothing for the player, but how can we guarantee that automatically? Today's optimization tools for such visual languages rely on analysis and testing, without formal guarantees. Meanwhile, the Scratch repository holds tens of millions of projects written by kids and hobbyists — an audience unable to notice or fix an error introduced by an automated improver. Trust becomes paramount here: an optimizer that silently changes a child's game is worse than none at all. The classic approach from the world of verified compilers — prove the correctness of transformations once and for all — runs into the cooperative multithreading, event model, and rendering inherent to Scratch. A gap emerges: formal methods know how to handle sequential C, but the lively, breathing code of a school animation demands new foundations.
Methods
The CertiBlock developers split the system into two uneven parts: an untrusted optimizer and a trusted checker. The optimizer scans the project, builds a dependency graph, and proposes a deletion — say, of a dead command or an unused costume. Along with the proposal comes a “certificate” — a manifest stating the type of edit, the checksum of the original and modified programs, and the observation lens. The lens is a parameterized concept defining what the player sees: frames, sounds, on‑screen variable values, not internal comments. The checker, like a meticulous customs inspector, re‑parses both program versions, verifies the checksums, and recomputes every condition on which the change’s safety depends. It trusts no claim from the optimizer, even if the optimizer honestly stated its calculations. The central mechanism is a cooperative frame theorem, mechanized in the Lean proof assistant. It states: a write to a resource that is overwritten in the same thread without yielding to the scheduler and without external observation can be removed. The theorem is parameterized by the resource type and the observation boundary; a single proof covers both the removal of dead variables and the removal of invisible sprite movements. The Python checker implements two key decision algorithms, whose reference versions were verified in Lean and compiled into executable code. An extra safety net is the differential oracle: after accepting an edit, it runs both versions on the actual Scratch virtual machine under identical deterministic conditions and compares the player‑visible trace.
Results
An experiment on 300 randomly selected projects from the public repository showed that the checker accepted at least one behavior‑preserving edit in 94.3% of cases (283 out of 300). These were mostly cleanups of unused resources and comments, but deeper semantic optimizations — removal of visually dead writes — succeeded on 17 projects. The average checking time per project was tens of milliseconds, and the amount of saved data reached hundreds of kilobytes. The key result concerns safety: an independent audit of the integrated system uncovered eight false acceptances that were missed by per‑family tests. All stemmed from overlooked observation channels — for instance, the costume index was read by another sprite, and removal shifted it. The errors were fixed, and each is now covered by a regression test. A cross‑family adversarial campaign of 4278 perturbed edits — with extra changes added — produced zero false acceptances. An ablation where the semantic conditions were discarded would have led to the acceptance of dozens of unsafe replacements, but the full checker rejected them all. The differential oracle on the virtual machine recorded no behavioral divergence among the accepted edits.
Implications
The result means that for a concurrent event‑driven language, a rewriting system has been built for the first time in which every change carries a certificate verifiable by a compact trusted core. This brings the discipline of verified compilers into the end‑user space, where the cost of an error is especially high. The customs metaphor works in practice: the checker need not understand how the optimizer found a candidate for removal; it merely compares the “cargo” with the “declaration,” and the cargo is the program itself. Parametrization by the observation lens allows uniform handling of edits that are safe for the player but not for the editor. The mechanized cooperative frame theorem relies on only two model‑machine correspondence hypotheses and does not depend on a specific edit family, making it both rigorous and extensible. The trusted base amounts to around ten thousand lines of Python and about six thousand lines of Lean — a size auditable by a small team.
Future development
The framework will likely transfer to other event‑driven languages with cooperative multithreading, since the cooperative theorem only requires a scheduler that explicitly records observations. The immediate goal is to close the gap between the verified Lean reference and the deployed Python checker via automated code extraction, and to extend the approach to preemptive multithreading. Integration into a real Scratch editor would enable real‑time display of safe simplifications to the author, without breaking the game’s intent. Looking ahead: hybrid systems where a large language model proposes changes and the checker impartially reviews them, just as it now reviews machine optimizations.
Impact
The methodology touches on the development of educational programming environments, refactoring tools, and verified compilers. It also offers a blueprint for building trusted AI coding assistants: an untrusted generator outputs a candidate, and a compact formal checker accepts or rejects it.
Next steps
The next step is to complete the verification bridge between the proven Lean model and the industrial Python checker, and to expand the coverage of edit families — for example, to script merging. In parallel, the system’s behavior should be studied on extra‑large projects with thousands of sprites.
Key open problems
The work directly connects to the problem of trustworthy automatic processing of programs written by non‑experts — a longstanding challenge at the intersection of formal methods and human–computer interaction. It also illustrates how parameterized proofs can reduce the verification cost for a whole class of optimizations, appealing to fundamental questions of information completeness of correctness conditions.
The knowledge machine's view
This section is addressed to the author of the paper and their colleagues. Neighbouring works were found by meaning-based search across our archive, not by word overlap. We do not review: we show the field around the work.
What the work does
The paper presents CertiBlock, a system for safely optimizing Scratch projects: an untrusted optimizer proposes dead-code removal, while a trusted verifier checks each edit against a mechanized frame theorem in Lean. Experiments on 300 random projects showed that the verifier accepted at least one behavior-preserving edit in 94.3% of cases.
Where its strength is
The key strength is the formal guarantee that observed behavior is preserved during optimization, tailored to Scratch's cooperative multithreading and event-driven model, bridging the gap between classical compiler verification and real visual languages.
Where it could go next
- Consider adaptive learning methods to tune observation lens parameters: for instance, automatically determining which behavioral aspects matter for a given project based on user feedback.based on: Quantum Error Correction Learns on the Fly arXiv:2607.10707
- It would be interesting to study how noise and uncertainty in Scratch's virtual machine behavior could enhance verification reliability—for example, by introducing controlled random perturbations during equivalence testing.based on: The Noise That Helps Fix Errors arXiv:2608.09583v1
- One might explore real-time fault-correction approaches so the verifier not only rejects unsafe edits but also suggests fixes that preserve the author's intent.based on: A Quantum Translator That Learns from Its Mistakes arXiv:2604.27648
Worth trying
- Investigate whether reinforcement learning can automatically generate lenses that maximize the acceptance rate of safe edits.
- Explore applying quantum error correction techniques to detect subtle discrepancies in execution traces.
- Experiment with adding noise to the virtual machine to uncover hidden dependencies on nondeterministic factors.
Nearby works in our archive
- Handwriting Without an Alphabet: How the Brain Draws Letters It Has Never Seensimilarity 0.57
- Quantum Error Correction Learns on the Flysimilarity 0.57
- Magic States: How Distillation Makes Quantum Computers Reliablesimilarity 0.56
- The Noise That Helps Fix Errorssimilarity 0.56
- Quantum Magic: Nonlocal and Everlastingsimilarity 0.56
- A Quantum Translator That Learns from Its Mistakessimilarity 0.56
The archive is sparse around this work: the closest review is only 0.57, against a usual 0.64. It looks like few have drilled nearby.
Original abstract
as written by the authors arXiv:2607.00563
Block-based end-user languages such as Scratch run tens of millions of programs. Existing tools establish behavior preservation through program analysis and testing without a checked guarantee. We turn optimization into certificate-carrying source-to-source rewriting. An untrusted optimizer proposes a rewrite; a trusted, fail-closed checker accepts it only after recomputing every side condition that the rewrite's behavior preservation depends on under an explicit observation lens. The checker is the sole authority: given a correct checker and a small, explicitly stated set of model-to-VM assumptions, an optimizer bug cannot mint an unsound acceptance. The observation lens is a parameter, and the central soundness argument is a cooperative-frame refinement theorem: a write overwritten before any thread observes it, within a window in which no thread yields, can be removed. We mechanize this theorem in Lean and show that one parametric statement covers two concrete rewrite families instantiated to variable state and renderer state. We build a checker for six rewrite families and evaluate it on 300 real Scratch projects. The checker accepts a behavior-preserving rewrite on 94.3% of projects (283 of 300); certification costs under one tenth of a second per project; and a cross-family adversarial campaign of 4,278 perturbed rewrites produces zero false accepts. An audit found eight false accepts the per-family test suites missed; each is now rejected. An ablation that strips the semantic side conditions, leaving analysis and testing alone, ships rewrites the virtual machine confirms change behavior; the full checker rejects every one. The result shows how to provide behavior-preservation guarantees for a concurrent, event-driven, end-user language. The checker recomputes every required condition instead of trusting optimizer claims, keeping the trusted base small.
An independent audit of the system uncovered eight false acceptances that traditional per‑family tests missed. All were due to one sprite peeking at another through unexpected channels — for example, reading a costume number that shifted when an unused resource was removed. After fixing, the errors are now permanently guarded by regression tests.
Key numbers
- projects with successful optimization: 94.3% (283 out of 300)
- zero false acceptances in attack: 0 out of 4278 perturbed edits
- lines of trusted code (Python): 9 921
- lines of mechanized proof (Lean): 5 909
- average project checking time: tens of milliseconds