Certificate-Carrying Transformation of Event-Driven Block Programs
Yuan Si, Jialu Zhang
cs.PL
Jul 1, 2026 · v1
TL;DR
Mechanizes the cooperative-frame refinement theorem for dead-store elimination in Lean 4, with two decision procedures as verified-executable Lean functions.
Abstract
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.
Problem
Block-based end-user languages like Scratch run on cooperative, event-driven schedulers, and existing optimization tools preserve behavior only through analysis and testing without a checked guarantee. Automatically rewriting these programs requires a soundness guarantee that a rewrite preserves what the player observes.
Approach
CertiBlock separates an untrusted optimizer that proposes rewrites from a trusted, fail-closed checker that recomputes every side condition under an explicit observation lens before accepting. The central soundness argument is a cooperative-frame refinement theorem: a write overwritten before any observation within a no-yield window can be removed. This theorem is mechanized in Lean 4, and two core decision procedures are realized as compiled Lean functions proved sound. A checker for six rewrite families is implemented in Python and validated against a headless Scratch virtual machine.
Results
On 300 real Scratch projects the checker accepts a behavior-preserving rewrite on 94.3% (283 of 300), certifying under 0.1 seconds per project. A cross-family adversarial campaign of 4,278 perturbed rewrites produced zero false accepts, and an audit found eight false accepts missed by per-family suites, each now rejected.
| Family | Recomputed condition | Mech. | Oracle |
|---|
| Comment cleanup | canonical core unchanged | yes | sanity |
| Unused-asset cleanup | no index-shift observer | no | sanity |
| Dead-broadcast removal | message reaches no receiver | no | sanity |
| Variable dead-store | overwritten in no-yield window | yes | seeded |
| Visual dead-store | no observable commit in segment | yes | VM |
Per-family recomputed conditions with mechanization and oracle status
| Family | Missed observation channel | Count |
|---|
| Unused-asset cleanup | costume/backdrop index read | 4 |
| Dead-code elimination | closure reach; broadcast timing | 2 |
| Visual dead-store | relative selector; yielding sound | 2 |
False accepts found by audit per family