Source-linked AI summary
Scratchy: Visual-Scratchpad Multimodal Reasoning for Cryptographic Proof Generation in EasyCrypt
Yupeng Ren, Zhaoxuan Li, Rui Zhang
TL;DR
Scratchy addresses the difficulty of generating machine-checked cryptographic proofs when probabilistic, relational, and reduction dependencies are distributed across formal context. It compiles that context into a typed proof-relation graph and formula-rich visual scratchpad, then guides multimodal EasyCrypt generation. Evaluations report that structured visual proof states improve generation, with relation fidelity contributing beyond image presence alone.
Problem
Cryptographic security proofs coordinate probabilistic programs, games, invariants, assumptions, and bounds, while existing linear interfaces leave dependencies distributed and implicit.
Method
Scratchy normalizes formal proof objects into a typed proof-relation graph and structure-preservingly compiles it into a formula-rich visual state for multimodal EasyCrypt proof generation.
Results
Structured visual proof states improve EasyCrypt security-proof generation, and relation fidelity matters beyond image presence alone.
Takeaways & Limitations
Explicit proof structure can support multimodal proof-state representation for computer-aided cryptography.
Abstract
from arXiv · showhide
Large language models (LLMs) have recently made substantial progress in formal proof generation, yet presenting distinctive challenges in cryptographic area. Computational security arguments posit that a valid proof must coordinate probability, adversarial games, invariants, assumptions and bounds, which can be provided by a machine-checked framework named EasyCrypt. Although all objects may appear in available context, LLMs still struggle because proof-theoretic dependencies are typically implicit in a linear representation and distributed across multiple programs. So, this paper presents Scratchy, a visual-scratchpad approach that exposes these dependencies for multimodal generation. Given the natural-language security description, with formal context and target propositions, the proof objects can be normalized into a typed proof-relation graph. Then a structure-preserving visual compiler transforms the graph into the formula-rich visual proof state that guides a multimodal model in generating the EasyCrypt proof. Also, the Scratchy-eval, a 114-task dataset derived from reliable official EasyCrypt files, has been introduced. It contains 64 security-form proof generations and 50 multiple-choice knowledge tests. After a series of evaluations, covering semantic grounding, relational invariants, and game reductions, classical LLMs like GPT-5.6-Sol and Claude-Opus-5 have gained a clear advantage from Scratchy's structured visual proof states. This contrast suggests that explicit proof structure can make the improvement and multimodal proof-state representation as a promising direction for computer-aided cryptography.
1 Introduction
Scratchy addresses the difficulty of generating machine-checked cryptographic proofs when security dependencies are distributed across programs and obscured by linear representations. It compiles formal proof context into structured visual states and evaluates this approach with Scratchy-eval.
- Motivation: Prior formal-proof interfaces primarily serialize theorem statements, proof code, premises, and diagnostics, leaving cryptographic proof relations implicit across distributed formal context.The paper identifies this interface as a bottleneck for machine-checkable cryptographic security proofs.
- Motivation: Cryptographic security proofs must coordinate probabilistic programs, games, adversarial capabilities, invariants, assumptions, and concrete bounds.EasyCrypt provides a machine-checkable framework for these program transformations, relational judgments, and security bounds.
- Scratchy: Scratchy normalizes proof objects into a typed proof-relation graph whose directed edges encode constraints, transformations, and discharge relations.Its nodes distinguish threat models, program facts, proof obligations, rules, and security goals.
- Scratchy: A structure-preserving visual compiler renders the graph as a formula-rich visual scratchpad that guides multimodal generation of an EasyCrypt proof fragment.The fragment is parsed, type-checked, discharged, and checked for target closure in an EasyCrypt verification loop.
- Evaluation: Scratchy-eval contains 114 tasks: 64 free-form proof generations and 50 multiple-choice semantic-recognition tasks, evaluated under six paired representation conditions.Compilation under EasyCrypt is the primary generation criterion.
- Findings: The paper reports empirical evidence that structured visual proof states improve EasyCrypt security-proof generation and that relation fidelity matters beyond image presence alone.The motivating observation found structured diagrams stronger than generic or structurally corrupted diagrams.
2 Related work
Related work establishes formal cryptographic verification, language-model proof generation, and visual intermediate reasoning as separate lines of research. Scratchy combines these directions by studying structured visual proof relations for machine-checkable EasyCrypt generation.
- Formal cryptography: CertiCrypt, EasyCrypt, and related workflows support machine-checked cryptographic proofs involving program transformations, relational judgments, and probabilistic bounds.These systems have also been applied to cryptographic standards and post-quantum constructions.
- Formal proof generation: CrypFormBench evaluates several tasks across cryptographic formal-verifier languages, while ShannonProver targets EasyCrypt proof scripts from security models and lemma-level decompositions.Scratchy studies the complementary bottleneck of compiling distributed formal context into a structured visual state.
- Formal proof generation: Recent theorem-proving systems improve proof search through synthetic corpora, self-play, reinforcement learning, tree search, interleaved reasoning, and self-correction.These approaches largely concern mathematical theorem proving rather than visual cryptographic proof-state construction.
- Visual reasoning: Multimodal reasoning systems use images as intermediate computational states, with graph-oriented work showing that visual encodings can preserve connectivity and layout can affect reasoning.Examples include Visualization-of-Thought, Visual Sketchpad, GraphVis, and related systems.
- Research gap: Existing visual formalization work includes diagram-dependent Euclidean geometry, but it does not target machine-checked cryptographic security proofs.The paper frames relation fidelity as the central variable for this unexplored setting.
3 Observation
The Observation tests whether representing proof relations changes EasyCrypt generation across paired representation conditions. The professional graph produces the strongest aggregate compile rate, while layerwise diagnostics show structured changes in model expert usage.
- Observation design: The Observation examines whether proof-relation representation affects EasyCrypt generation using ten paired obligations and six representation conditions.Conditions include text controls, a generic diagram, a shuffled-edge graph, and the complete professional graph.
- Observation design: Generated fragments count as successful only when they compile under the pinned EasyCrypt environment.The evaluation therefore requires parsing, type checking, obligation discharge, and target closure.
- Results: 62.5% (25/40) of professional-graph fragments compiled, compared with 50.0% (20/40) for the strongest visual control and 27.5% (11/40) for the strongest text condition.The professional graph was consistently above the text condition, while its margin over the best visual control varied by model.
- Results: The local-model diagnostic records a reference-versus-comparison layerwise difference that remains close and positive across all 30 language layers.Its trajectory changes across depth rather than appearing as a single constant offset.
- Implication: The Observation motivates Scratchy as a systematic mechanism for constructing visual proof states rather than relying on manually selected diagrams.Scratchy organizes security assumptions, program states, proof obligations, and reduction goals into a structured visual interface.
- Scratchy pipeline: The pipeline deterministically compiles structured proof context and an SNPS into a typed graph and formula-rich scratchpad before multimodal proof synthesis and EasyCrypt checking.The output is reconstructed and checked for acceptance or an open outcome.
4 Methodology
Scratchy converts a structured natural-language proof sketch into a typed proof-relation graph, then uses that graph to guide deterministic reconstruction and EasyCrypt verification. The pipeline preserves proof-object roles and dependencies without inferring relations absent from the sketch.
- Input and pipeline: Scratchy takes a Structured Natural-Language Proof Sketch with fixed fields and directed relations as input to deterministic visual composition.The LLM generates the EasyCrypt fragment only after the visual proof state has been constructed.
- Input and pipeline: The SNPS records threat model, program facts, proof obligations, proof rules, security goal, and relations using identifiers and formulas copied from the formal context.The first five fields declare proof objects, while RELATIONS specifies sources, targets, and dependency meanings.
- SNPS-to-graph compilation: The compiler parses SNPS fields, creates typed and labeled graph nodes, adds directed relation edges, and orders dependency paths toward the target obligation.It performs parsing, matching, and normalization without inferring relations absent from the SNPS.
- Proof reconstruction and verification: The resulting graph provides a traceable route from the SNPS to verification, while proof fragments follow prescribed operations such as proc, inline, wp, while, and auto.The PIR example pins the relational declaration and official source location for reconstruction.
- SNPS-to-graph compilation: Threat-model, program-fact, proof-obligation, proof-rule, and security-goal nodes distinguish security consequences, evidence, intermediate claims, transformations, and final goals.These roles organize the proof route from available facts through permitted transformations to the machine-checkable target.
4.3 Graph-to-Visual Compilation
Scratchy’s visual compiler transforms the typed graph into a readable proof state that preserves roles, formulas, edge directions, and dependency paths. The multimodal generator uses this image with textual context, after which EasyCrypt validates the reconstructed fragment.
- 4.3 Graph-to-Visual Compilation: The visual compiler preserves node roles, semantic labels, edge directions, and the path to the target obligation in the generated proof state.Colors and icons encode node types, while formula and code cards display the associated labels and formulas.
- Relational and game-based layouts: Relational proofs place left and right games in parallel and connect corresponding program points, variables, and relational invariants.The invariant is positioned beside the state correspondence it constrains.
- Relational and game-based layouts: Game-based proofs order games along the security reduction and place each game beside its relevant hop.This layout makes the reduction sequence directly readable in the visual state.
- Multimodal generation: The graph route organizes generation into program unfolding, state alignment, rule application, and goal discharge while text preserves exact EasyCrypt syntax.The image preserves the relation structure needed to produce the proof fragment.
- Verification: EasyCrypt parses and typechecks the reconstructed source, discharges its obligations, and either closes the target or returns the open proof state for reconstruction.The LLM is used only for the transition from the visual proof state to the EasyCrypt fragment; Algorithms 1 and 2 remain deterministic.
5 Experiments
Scratchy-eval evaluates EasyCrypt proof generation and semantic recognition across provenance-preserving tasks and six representation conditions. The results show that Scratchy’s professional graph is the strongest generation condition, with gains concentrated in cryptography and reduction-oriented tasks, while compilation exposes remaining syntax and proof-route bottlenecks.
- Experimental Setup: Scratchy-eval contains 114 tasks from 26 sources and 37 official EasyCrypt files, including 64 proof-generation and 50 multiple-choice tasks.Each generation fixture preserves official imports and dependency prefixes while replacing the proof.
- Experimental Setup: The study evaluates four models under six paired representation conditions while keeping task, response contract, and output budget fixed within comparisons.Conditions vary source details, proof paths, identifiers, and edge structure; compilation is the primary generation criterion.
- Main Results: 21.1% of fragments compile with PG, compared with 9.4% under SG and 4.3% under CR, making PG the strongest generation condition for all four models.The complete representation reaches 2.25× the SG rate and 4.91× the CR rate.
- Main Results: Multiple-choice accuracy remains 97.0–99.5%, so free-form generation provides the principal discrimination in the benchmark.Among 54 compiling PG outputs, only 10 exactly match the official fragment, while 44 are distinct proofs accepted by EasyCrypt.
- Protocol and Proof-Structure Analysis: PG reaches 33.3% on complex cryptography and 21.4% on reduction paths, while SG leads foundations and program analysis and the graph conditions tie on program logics.At the source level, PG also compiles 9/20 two-server PIR pairs and 7/16 UC Diffie–Hellman encryption pairs.
- Failure and Efficiency Analysis: Parse errors, inapplicable rewrites, incomplete proofs, and unclosed by-blocks account for 90 unsuccessful PG units, leaving exact EasyCrypt syntax and local proof-route instantiation as recurring bottlenecks.The four groups comprise 30 parse errors, 30 inapplicable rewrites, 19 incomplete proofs, and 11 unclosed by-blocks.
6 Discussion
Task 064 shows that machine checking distinguishes a valid alternative proof from a rejected proof with an underspecified loop step. Across the aggregate pattern, the professional graph makes preserved state and loop rules visible, while remaining failures concentrate on exact syntax and residual obligations.
- Machine-checked proof contrast: All three outputs share the proc, inline, and wp route, but the rejected output invokes auto without stating what must remain synchronized across iterations.The decisive difference occurs at the loop.
- Machine-checked proof contrast: The official fragment and professional-graph output compile, whereas the coarse-relation output omits the loop invariant and leaves an open goal.The contrast is reported for the PIR target in Listing 2.
- Machine-checked proof contrast: The professional-graph output supplies an equivalent conjunction and explicit loop-body proof, which machine checking accepts despite textual difference from the official proof.This shows why verifier acceptance is not limited to exact textual reproduction.
- Aggregate interpretation: The professional graph is strongest for all four models, with clearest gains on protocol-specific reductions and relational judgments.For Task 064, the graph exposes the preserved state and loop rule where a linear hint remains underspecified.
- Remaining limitations: Many remaining failures arise when a plausible proof route must become exact syntax, especially around rewrites, side goals, and program-logic tactics.The paper points to more precise decoding and verifier-guided revision as the next boundary for improvement.
7 Conclusion
Scratchy compiles structured proof sketches into typed relational graphs and formula-rich visual states before multimodal generation. Across Scratchy-eval, the professional graph improves generation over textual and visual-control conditions, especially for relational and reduction-oriented proofs.
- Framework: Scratchy deterministically compiles a Structured Natural-Language Proof Sketch into a typed proof-relation graph and formula-rich visual state.The resulting state guides multimodal generation of an EasyCrypt fragment.
- Framework: The formal verifier decides the correctness of the EasyCrypt fragment produced from Scratchy's visual state.This makes proof acceptance machine-checkable rather than dependent on textual similarity.
- Evaluation: Across Scratchy-eval, the professional graph consistently improves generation over textual and visual-control conditions, particularly for relational and reduction-oriented proofs.The conclusion reports this as the central evaluation pattern.
- Future work: Future work will extend Scratchy-eval to additional protocols and proof systems and refine verifier-guided repair of syntax and residual obligations.The paper also proposes adapting visual relations to different proof families.
A Scratchy-eval Data Card
Scratchy-eval compares alternative proof-relation representations under fixed model, task-pair, response-contract, and verifier conditions. Its 114 tasks combine proof generation with static-validity and semantic-recognition diagnostics across 26 protocol or formal-program groups.
- Purpose: Scratchy-eval compares alternative representations of proof relations for machine-checkable EasyCrypt generation.The intended comparison holds the model, task pair, response contract, and verifier fixed.
- Contents: 114 tasks include 64 free-form proof-generation targets and 50 multiple-choice diagnostics.The diagnostics cover static validity and semantic recognition.
- Coverage: The source material spans 26 protocol or formal-program groups.Task-level source pointers are retained in accompanying metadata.
A.1 Representative datum
Task 003 preserves an official EasyCrypt file's imports, declarations, program, target, and dependency context while replacing one proof body with a proof hole. The generation contract asks the model to reconstruct that missing body, with any verifier-accepted equivalent considered correct.
- Source fixture: Task 003 comes from the official while-sampling example in the foundations family and reproduces its complete pinned source context.The context includes imports, declarations, probabilistic program, target, and accepted proof.
- Task construction: Only the body of Sample_lossless is replaced by a proof hole while the surrounding compilation context is preserved.The selected declaration retains required imports, definitions, and dependency prefix.
- Generation contract: The generation contract requests the missing proof body rather than the surrounding declaration.The canonical output reconstructs the official source, but a textually different fragment is correct if it closes the same target under EasyCrypt.
- Program and assumptions: The fixture includes a probabilistic sampling loop that repeatedly draws r from sample while test r holds, then returns r.The displayed source also declares losslessness and probability assumptions used by the proof.
- Diagnostic tasks: Multiple-choice tasks test whether local EasyCrypt forms are valid or which formal role a construct serves, with answers checked against pinned source or compiler behavior.This frames the example within the benchmark's semantic and static-validity diagnostics.
A.2 Representations and scoring
Scratchy-eval compares textual and graph-based proof representations across generation and diagnostic tasks, using EasyCrypt acceptance and answer accuracy as distinct measures. The benchmark preserves provenance and verification artifacts while remaining focused on included EasyCrypt material.
- Representations: Each task compares three textual conditions with three graph conditions, including a professional graph of typed proof objects, formulas, dependencies, and a target route.Other conditions remove relation detail or alter the visual structure.
- Scoring: Generation is scored by EasyCrypt acceptance after source reconstruction, whereas diagnostic tasks use answer accuracy.This separates executable proof completion from formal-knowledge recognition.
- Benchmark scope: The release record retains source provenance, task type, target information, graph metadata, supported conditions, and verification artifacts.Scratchy-eval is intended for controlled representation studies over the included EasyCrypt material rather than as a census of cryptographic formalization.
- Benchmark coverage: 64 generation tasks span seven families, accompanied by static-validity and semantic-recognition diagnostics.The category-level coverage summarizes representative material without enumerating task IDs or hidden fragments.
- Verification artifacts: Task 003 includes a complete accepted EasyCrypt output taken from the official answer record and required at the proof hole.The listing provides a canonical accepted fragment rather than merely illustrative pseudocode.