💻 computer science

Formal Verification of Imperative First-Class Functions in Move

This paper presents an extension to the Move Prover that enables the formal verification of imperative first-class functions in the Move language by introducing behavioral predicates, state labels, and an SMT encoding strategy that leverages Move's static memory separation for efficient verification and automated specification inference.

Original authors: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

Published 2026-05-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Smart Contract" Factory

Imagine Aptos is a high-security factory that builds digital assets (like money or tickets) using a special language called Move. To make sure these assets don't get stolen or broken, the factory uses a robot inspector called the Move Prover (MVP). This robot reads the blueprints (the code) and mathematically proves that everything will work correctly before the factory ever runs.

For a long time, this robot was great at checking simple instructions. But recently, the factory added a new, tricky feature: First-Class Functions.

Think of these new functions like magic wands.

Old way: You had to hold the wand yourself to cast a spell. The robot knew exactly which spell you were casting.
New way: You can put the wand in a box, hand the box to a friend, store the box in a vault, or pass it to a machine that doesn't know what's inside. The machine just knows, "I need to wave a wand," but it doesn't know which wand until the very last second.

This is called Dynamic Dispatch. It's powerful, but it breaks the robot inspector because it can't see the future to know which specific spell is being cast.

The Problem: The "Black Box" Dilemma

The paper explains how the authors upgraded the robot inspector (MVP) to handle these magic wands without panicking.

Previously, if a function was a "black box" (a variable holding a function), the robot had to guess or check every single possibility at once, which made the math explode and the robot slow down.

The authors introduced two new tools to solve this:

1. Behavioral Predicates: The "Warranty Card"

Instead of looking inside the magic wand to see how it works, the robot now looks at the Warranty Card attached to the wand.

The Old Way: "I need to know exactly how this calculate_price wand works, down to every line of code, before I let you use it."
The New Way: "I don't care how the wand works inside. I just need to read its Warranty Card. The card says: 'If you give me 5 coins, I will give you 3 coins back, and I will never break.'"

The paper calls these Behavioral Predicates. They are like a contract that describes:

Pre-conditions: What must be true before you wave the wand.
Post-conditions: What will be true after you wave it.
Abort conditions: When the wand might explode (fail).

This allows the robot to check the promise of the wand without needing to know the secret recipe inside it.

2. State Labels: The "Time-Stamping Camera"

Sometimes, a sequence of events happens. Imagine a factory line where a robot paints a car, and then another robot puts the wheels on.

If you want to prove the car is safe, you need to know the state of the car after painting but before the wheels are on.

The authors introduced State Labels. Think of these as Time-Stamping Cameras placed at specific points in the process.

Camera A (Start): The car is bare metal.
Camera B (Middle): The car is painted.
Camera C (End): The wheels are on.

The robot can now say: "I know the painting happened between Camera A and Camera B, and the wheels were added between Camera B and Camera C." This helps the robot reason about complex sequences of events without getting confused about what the world looked like at any given moment.

How the Robot Actually Works (The "Switchboard")

The paper describes how the robot translates these ideas into math (SMT logic) that a computer can solve.

Imagine the robot has a Switchboard.

Scenario A (Known Wand): If the robot sees a specific, known wand (e.g., product function), it flips the switch to "Direct Mode." It ignores the warranty card and just checks the actual code of that specific wand.
Scenario B (Unknown Wand): If the robot sees a generic box (a variable), it flips the switch to "Abstract Mode." It ignores the code entirely and relies only on the Warranty Card (the behavioral predicates) to prove the system is safe.

This is efficient because the robot doesn't have to try to open every possible box. It only opens the ones it knows, and for the rest, it trusts the contract.

The "Auto-Inspector" (Specification Inference)

One of the coolest parts of the paper is that the robot can now write its own Warranty Cards.

Usually, humans have to write these cards manually, which is tedious. The authors upgraded the robot so it can look at the code, figure out what the Warranty Card should say, and write it for you.

Input: A messy piece of code with a magic wand.
Robot Action: "I see this code checks if a fee exists. I will write a Warranty Card that says: 'This wand will explode if the fee is missing.'"
Result: The robot checks its own work. If the code matches the card, it passes.

This is demonstrated in the paper with an Automated Market Maker (AMM) example. This is a system that trades assets. The robot proved that even though the pricing rule (the magic wand) could be changed by the user, the system would never crash or lose money, provided the new wand followed the rules written on its Warranty Card.

Summary of the Achievement

The paper claims to have solved a major headache in verifying smart contracts:

It made "Magic Wands" (functions) safe to use in a way that allows them to be stored, passed around, and changed dynamically.
It created a new language (Behavioral Predicates + State Labels) that lets the robot talk about these wands without needing to see inside them.
It made the robot faster and smarter by using a "Switchboard" approach that switches between looking at the code and looking at the contract.
It automated the paperwork by letting the robot generate the necessary contracts for you.

In short, they taught the robot inspector how to trust a stranger's promise (the contract) without needing to know the stranger's secrets, making the factory safer and more flexible.

Technical Summary: Formal Verification of Imperative First-Class Functions in Move

Problem Statement
The Move Prover (MVP) is a formal verification tool designed for Move smart contracts, originally built on a modular, static-dispatch specification style. A recent extension to the Move language introduced higher-order functions, allowing functions to be first-class values that can be passed as arguments, stored in data structures, and persisted in global storage. This capability enables dynamic dispatch but breaks the static analysis assumptions MVP relied upon. Specifically, when a function is called dynamically, its pre- and post-conditions cannot be resolved at the call site. The caller must reason abstractly about the behavior of function-value arguments, while the verifier must reconcile these abstract specifications with the concrete functions that may reach the call site. Existing solutions in other languages (e.g., Dafny, F*, Verus) either lack support for imperative first-class functions that modify state or rely on separation logic, which can lead to complex SMT encodings. The challenge is to support these dynamic features efficiently, ensuring verification remains fast, complete for relevant cases, and free from SMT trigger instability.

Methodology
The authors extend MVP and the Move specification language to support higher-order functions through three primary mechanisms:

Behavioral Predicates: The specification language is extended with predicates that characterize the behavior of function values ( $f$ ) on specific arguments ( $\bar{x}$ ) and results ( $\bar{y}$ ). These include:
- requires_of<f>(x): Pre-conditions.
- aborts_of<f>(x): Abort conditions.
- ensures_of<f>(x, y): Post-conditions.
  These predicates implicitly track read and read/write state dependencies, allowing specifications to refer abstractly to function arguments without inlining their bodies.
State Labels: To reason about sequential state transitions and intermediate memory states, the authors introduce state labels (e.g., $S$ ). These labels name specific points in execution. Predicates can be single-state ( $S \mid \sim p$ ) or two-state ( $S.. \mid \sim q$ ), enabling the composition of behavioral predicates to describe sequences of operations (e.g., the post-state of one function becoming the pre-state of another).
SMT Encoding via Variant Discrimination: At the SMT level, function values are encoded using algebraic datatypes that represent all possible sources of a function value (concrete closures, function parameters, or struct fields). When a function value is invoked:
- If the concrete function is known (e.g., a specific closure), the invocation is replaced by the effect of that concrete function.
- If the function is unknown (e.g., a parameter or a closure loaded from storage), the invocation is modeled using the behavioral predicates associated with that function value's type.
- The encoding uses "havoc" and "assume" constructs to model memory modifications and ensures frame conditions are respected by distinguishing between the pre-state and post-state memory maps.

Key Contributions
The paper details the following specific contributions:

Language Extensions: The introduction of behavioral predicates and state labels to the Move specification language, making function specifications first-class citizens capable of tracking state dependencies.
Implementation in MVP: A Boogie-based encoding that discriminates over function-value variants at call sites. This approach avoids the need for separation logic by leveraging Move's static memory separation (resource model), leading to more efficient SMT encodings.
Specification Inference: An extension of MVP's weakest-precondition (WP) analysis tool to handle higher-order code. This tool semi-automatically derives behavioral-predicate-based specifications from arbitrary Move bytecode, reducing the manual annotation burden and providing a validation pipeline for the new constructs.
Handling Imperative Side Effects: Unlike some existing tools (e.g., Dafny), this approach supports imperative first-class functions that modify state via Rust-style references and global variables.

Results and Validation
The authors demonstrate the approach using an Automated Market Maker (AMM) example where a pricing curve is stored as a function value. The system successfully verifies:

Invariants: Properties such as "the function never aborts," "output monotonicity," and "constant-product preservation" are verified using behavioral predicates and state labels.
Compliance Checking: The specification inference tool automatically derives abort conditions for pricing functions (e.g., detecting that a fee-based pricing function aborts if a fee resource is missing), allowing for machine-readable compliance checks without manual annotations.
Test Suite: A comprehensive test suite covering direct calls, mutual recursion, higher-order parameters, and stored-closure dispatch confirms that the encoding is internally consistent and that inferred specifications are tight enough for the verifier to discharge.

Significance
The paper claims that this work enables the routine, production-oriented verification of Move smart contracts featuring dynamic dispatch and higher-order functions. By preserving MVP's cost model—where verification completes within seconds per function—the extension allows developers to use complex patterns like callback-based asset flows and extensible asset managers with formal guarantees. The approach is distinct from separation logic-based tools by utilizing Move's inherent static memory separation to simplify SMT encodings. Furthermore, the integration of specification inference provides a practical pathway for verifying compliance of function values, addressing a significant barrier to the adoption of higher-order functions in safety-critical smart contracts. The work acknowledges that while application-side verification is now comparable to first-order functions, compliance-side verification (proving that a passed function satisfies a contract) may still require manual proof hints or trusted assumptions in complex cases.