← All papers
First page of Certificate-Carrying Transformation of Event-Driven Block Programs

Certificate-Carrying Transformation of Event-Driven Block Programs

Yuan Si, Jialu Zhang

cs.PL Jul 1, 2026 · v1
Mechanizes the cooperative-frame refinement theorem for dead-store elimination in Lean 4, with two decision procedures as verified-executable Lean functions.
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.

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.

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.

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.

FamilyRecomputed conditionMech.Oracle
Comment cleanupcanonical core unchangedyessanity
Unused-asset cleanupno index-shift observernosanity
Dead-broadcast removalmessage reaches no receivernosanity
Variable dead-storeoverwritten in no-yield windowyesseeded
Visual dead-storeno observable commit in segmentyesVM
Per-family recomputed conditions with mechanization and oracle status
FamilyMissed observation channelCount
Unused-asset cleanupcostume/backdrop index read4
Dead-code eliminationclosure reach; broadcast timing2
Visual dead-storerelative selector; yielding sound2
False accepts found by audit per family