💻 computer science

Formal Verification of Imperative First-Class Functions in Move

Dieses Papier stellt eine Erweiterung des Move Provers vor, die die formale Verifikation imperativer First-Class-Funktionen in der Move-Sprache ermöglicht, indem Verhaltensprädikate, Zustandsbezeichner und eine SMT-Kodierungsstrategie eingeführt werden, die Moves statische Speichertrennung für eine effiziente Verifikation und automatische Spezifikationsinferenz nutzt.

Ursprüngliche Autoren: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

Veröffentlicht 2026-05-14

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Die „Smart Contract"-Fabrik

Stellen Sie sich Aptos als eine hochsichere Fabrik vor, die digitale Vermögenswerte (wie Geld oder Tickets) mit einer speziellen Sprache namens Move herstellt. Um sicherzustellen, dass diese Vermögenswerte nicht gestohlen oder beschädigt werden, setzt die Fabrik einen Roboterinspektor namens Move Prover (MVP) ein. Dieser Roboter liest die Baupläne (den Code) und beweist mathematisch, dass alles korrekt funktionieren wird, bevor die Fabrik jemals läuft.

Lange Zeit war dieser Roboter hervorragend darin, einfache Anweisungen zu prüfen. Doch kürzlich fügte die Fabrik ein neues, kniffliges Feature hinzu: First-Class Functions.

Stellen Sie sich diese neuen Funktionen wie Zauberstäbe vor.

Alter Weg: Sie mussten den Zauberstab selbst halten, um einen Zauber zu wirken. Der Roboter wusste genau, welchen Zauber Sie wirken.
Neuer Weg: Sie können den Zauberstab in eine Box legen, die Box einem Freund geben, die Box in einen Tresor legen oder sie an eine Maschine übergeben, die nicht weiß, was sich darin befindet. Die Maschine weiß nur: „Ich muss einen Zauberstab schwingen", aber sie weiß nicht, welchen Zauberstab, bis zur allerletzten Sekunde.

Dies nennt man Dynamic Dispatch. Es ist mächtig, aber es bringt den Roboterinspektor durcheinander, weil er die Zukunft nicht sehen kann, um zu wissen, welcher spezifische Zauber gewirkt wird.

Das Problem: Das „Black Box"-Dilemma

Das Papier erklärt, wie die Autoren den Roboterinspektor (MVP) so weiterentwickelt haben, dass er mit diesen Zauberstäben umgehen kann, ohne in Panik zu geraten.

Früher, wenn eine Funktion eine „Black Box" war (eine Variable, die eine Funktion hält), musste der Roboter raten oder jede einzelne Möglichkeit gleichzeitig prüfen, was die Mathematik explodieren ließ und den Roboter verlangsammte.

Die Autoren stellten zwei neue Werkzeuge vor, um dies zu lösen:

1. Behavioral Predicates: Die „Garantiekarte"

Anstatt in den Zauberstab hineinzusehen, um zu sehen, wie er funktioniert, betrachtet der Roboter nun die Garantiekarte, die am Zauberstab befestigt ist.

Der alte Weg: „Ich muss genau wissen, wie dieser calculate_price-Zauberstab funktioniert, bis auf jede Codezeile, bevor ich Sie ihn benutzen lasse."
Der neue Weg: „Es ist mir egal, wie der Zauberstab innen funktioniert. Ich muss nur seine Garantiekarte lesen. Die Karte sagt: 'Wenn Sie mir 5 Münzen geben, gebe ich Ihnen 3 Münzen zurück, und ich werde niemals brechen.'"

Das Papier nennt dies Behavioral Predicates. Sie sind wie ein Vertrag, der beschreibt:

Vorbedingungen: Was muss wahr sein, bevor Sie den Zauberstab schwingen.
Nachbedingungen: Was wird wahr sein, nachdem Sie ihn geschwungen haben.
Abbruchbedingungen: Wann der Zauberstab explodieren könnte (versagen).

Dies ermöglicht es dem Roboter, das Versprechen des Zauberstabs zu prüfen, ohne die Geheimrezeptur darin zu kennen.

2. State Labels: Die „Zeitstempel-Kamera"

Manchmal ereignet sich eine Abfolge von Ereignissen. Stellen Sie sich eine Fabrikstraße vor, auf der ein Roboter ein Auto lackiert und dann ein anderer Roboter die Räder aufsetzt.

Wenn Sie beweisen wollen, dass das Auto sicher ist, müssen Sie den Zustand des Autos nach dem Lackieren, aber vor dem Aufsetzen der Räder kennen.

Die Autoren führten State Labels ein. Stellen Sie sich diese als Zeitstempel-Kameras vor, die an bestimmten Punkten im Prozess platziert sind.

Kamera A (Start): Das Auto ist aus blankem Metall.
Kamera B (Mitte): Das Auto ist lackiert.
Kamera C (Ende): Die Räder sind aufgesetzt.

Der Roboter kann nun sagen: „Ich weiß, dass das Lackieren zwischen Kamera A und Kamera B stattfand, und die Räder wurden zwischen Kamera B und Kamera C hinzugefügt." Dies hilft dem Roboter, komplexe Ereignisfolgen zu durchdenken, ohne verwirrt zu werden darüber, wie die Welt zu einem bestimmten Zeitpunkt aussah.

Wie der Roboter tatsächlich funktioniert (Die „Vermittlungsstelle")

Das Papier beschreibt, wie der Roboter diese Ideen in Mathematik (SMT-Logik) übersetzt, die ein Computer lösen kann.

Stellen Sie sich vor, der Roboter hat eine Vermittlungsstelle.

Szenario A (Bekannter Zauberstab): Wenn der Roboter einen spezifischen, bekannten Zauberstab sieht (z. B. die Funktion product), schaltet er auf „Direktmodus". Er ignoriert die Garantiekarte und prüft einfach den tatsächlichen Code dieses spezifischen Zauberstabs.
Szenario B (Unbekannter Zauberstab): Wenn der Roboter eine generische Box sieht (eine Variable), schaltet er auf „Abstraktmodus". Er ignoriert den Code vollständig und verlässt sich nur auf die Garantiekarte (die Behavioral Predicates), um zu beweisen, dass das System sicher ist.

Dies ist effizient, weil der Roboter nicht versuchen muss, jede mögliche Box zu öffnen. Er öffnet nur die, die er kennt, und bei den anderen vertraut er dem Vertrag.

Der „Auto-Inspektor" (Spezifikationsinferenz)

Einer der coolsten Teile des Papiers ist, dass der Roboter nun seine eigenen Garantiekarten schreiben kann.

Normalerweise müssen Menschen diese Karten manuell schreiben, was mühsam ist. Die Autoren haben den Roboter so weiterentwickelt, dass er den Code betrachten, herausfinden, was die Garantiekarte sagen sollte, und sie für Sie schreiben kann.

Eingabe: Ein unordentliches Stück Code mit einem Zauberstab.
Roboter-Aktion: „Ich sehe, dieser Code prüft, ob eine Gebühr existiert. Ich werde eine Garantiekarte schreiben, die sagt: 'Dieser Zauberstab wird explodieren, wenn die Gebühr fehlt.'"
Ergebnis: Der Roboter prüft seine eigene Arbeit. Wenn der Code zur Karte passt, besteht er den Test.

Dies wird im Papier mit einem Automated Market Maker (AMM)-Beispiel demonstriert. Dies ist ein System, das Vermögenswerte handelt. Der Roboter bewies, dass das System selbst dann, wenn die Preisregel (der Zauberstab) vom Benutzer geändert werden könnte, niemals abstürzen oder Geld verlieren würde, vorausgesetzt, der neue Zauberstab folgte den Regeln, die auf seiner Garantiekarte geschrieben standen.

Zusammenfassung der Leistung

Das Papier behauptet, ein großes Ärgernis bei der Verifizierung von Smart Contracts gelöst zu haben:

Es machte „Zauberstäbe" (Funktionen) sicher zu verwenden in einer Weise, die es erlaubt, sie zu speichern, weiterzugeben und dynamisch zu ändern.
Es schuf eine neue Sprache (Behavioral Predicates + State Labels), die es dem Roboter ermöglicht, über diese Zauberstäbe zu sprechen, ohne sie von innen sehen zu müssen.
Es machte den Roboter schneller und intelligenter durch einen „Vermittlungsstellen"-Ansatz, der zwischen dem Betrachten des Codes und dem Betrachten des Vertrags wechselt.
Es automatisierte den Papierkram, indem es dem Roboter erlaubte, die notwendigen Verträge für Sie zu generieren.

Kurz gesagt: Sie lehrten den Roboterinspektor, das Versprechen eines Fremden (den Vertrag) zu vertrauen, ohne die Geheimnisse des Fremden kennen zu müssen, was die Fabrik sicherer und flexibler macht.

Technischer Zusammenfassung: Formale Verifikation imperativer First-Class-Funktionen in Move

Problemstellung
Der Move Prover (MVP) ist ein Werkzeug zur formalen Verifikation, das für Move-Smart-Verträge entwickelt wurde und ursprünglich auf einem modularen Spezifikationsstil mit statischer Dispatch beruhte. Eine kürzliche Erweiterung der Move-Sprache führte höherstufige Funktionen ein, die es ermöglichen, Funktionen als First-Class-Werte zu behandeln, die als Argumente übergeben, in Datenstrukturen gespeichert und im globalen Speicher persistiert werden können. Diese Fähigkeit ermöglicht dynamische Dispatch, bricht jedoch die statischen Analyseannahmen, auf die MVP angewiesen war. Insbesondere können bei einem dynamischen Aufruf einer Funktion ihre Vor- und Nachbedingungen am Aufrufort nicht aufgelöst werden. Der Aufrufer muss abstrakt über das Verhalten von Funktionswert-Argumenten nachdenken, während der Verifizierer diese abstrakten Spezifikationen mit den konkreten Funktionen in Einklang bringen muss, die den Aufrufort erreichen könnten. Bestehende Lösungen in anderen Sprachen (z. B. Dafny, F*, Verus) bieten entweder keine Unterstützung für imperativen First-Class-Funktionen, die Zustand ändern, oder verlassen sich auf Trennungslogik, was zu komplexen SMT-Kodierungen führen kann. Die Herausforderung besteht darin, diese dynamischen Merkmale effizient zu unterstützen und sicherzustellen, dass die Verifikation schnell bleibt, für relevante Fälle vollständig ist und frei von SMT-Trigger-Instabilität ist.

Methodik
Die Autoren erweitern MVP und die Movespezifikationssprache, um höherstufige Funktionen durch drei primäre Mechanismen zu unterstützen:

Verhaltensprädikate: Die Spezifikationssprache wird um Prädikate erweitert, die das Verhalten von Funktionswerten ( $f$ ) auf spezifischen Argumenten ( $\bar{x}$ ) und Ergebnissen ( $\bar{y}$ ) charakterisieren. Dazu gehören:
- requires_of<f>(x): Vorbedingungen.
- aborts_of<f>(x): Abbruchbedingungen.
- ensures_of<f>(x, y): Nachbedingungen.
  Diese Prädikate verfolgen implizit Lese- und Schreib-Zustandsabhängigkeiten und ermöglichen es Spezifikationen, abstrakt auf Funktionsargumente zu verweisen, ohne deren Körper inline zu setzen.
Zustandslabels: Um sequenzielle Zustandsübergänge und intermediate Speicherzustände zu analysieren, führen die Autoren Zustandslabels (z. B. $S$ ) ein. Diese Labels benennen spezifische Punkte in der Ausführung. Prädikate können einstufig ( $S \mid \sim p$ ) oder zweistufig ( $S.. \mid \sim q$ ) sein, was die Komposition von Verhaltensprädikaten ermöglicht, um Folgen von Operationen zu beschreiben (z. B. den Postzustand einer Funktion, der zum Prezustand einer anderen wird).
SMT-Kodierung durch Variantendiskriminierung: Auf SMT-Ebene werden Funktionswerte mittels algebraischer Datentypen kodiert, die alle möglichen Quellen eines Funktionswerts darstellen (konkrete Closures, Funktionsparameter oder Strukturfelder). Wenn ein Funktionswert aufgerufen wird:
- Ist die konkrete Funktion bekannt (z. B. eine spezifische Closure), wird der Aufruf durch die Wirkung dieser konkreten Funktion ersetzt.
- Ist die Funktion unbekannt (z. B. ein Parameter oder eine aus dem Speicher geladene Closure), wird der Aufruf unter Verwendung der verhaltensprädikate modelliert, die mit dem Typ dieses Funktionswerts assoziiert sind.
- Die Kodierung verwendet „Havoc"- und „Assume"-Konstrukte, um Speichermodifikationen zu modellieren und stellt sicher, dass Rahmenbedingungen eingehalten werden, indem zwischen Speicherabbildungen des Prezustands und des Postzustands unterschieden wird.

Hauptbeiträge
Die Arbeit beschreibt die folgenden spezifischen Beiträge:

Spracherweiterungen: Die Einführung von Verhaltensprädikaten und Zustandslabels in die Movespezifikationssprache, wodurch Funktionsspezifikationen zu First-Class-Bürgern werden, die in der Lage sind, Zustandsabhängigkeiten zu verfolgen.
Implementierung in MVP: Eine auf Boogie basierende Kodierung, die an Aufrufstellen über Funktionswert-Varianten diskriminiert. Dieser Ansatz vermeidet die Notwendigkeit von Trennungslogik, indem er Moves statische Speichertrennung (Ressourcenmodell) nutzt, was zu effizienteren SMT-Kodierungen führt.
Spezifikationsinferenz: Eine Erweiterung des schwächsten-Vorbedingungs-(WP-)Analysewerkzeugs von MVP, um höherstufigen Code zu verarbeiten. Dieses Werkzeug leitet halbautomatisch verhaltensprädikatebasierte Spezifikationen aus beliebigen Move-Bytecodes ab, reduziert die manuelle Annotationslast und bietet eine Validierungspipeline für die neuen Konstrukte.
Behandlung imperativer Seiteneffekte: Im Gegensatz zu einigen bestehenden Werkzeugen (z. B. Dafny) unterstützt dieser Ansatz imperativen First-Class-Funktionen, die Zustand über Rust-artige Referenzen und globale Variablen ändern.

Ergebnisse und Validierung
Die Autoren demonstrieren den Ansatz anhand eines Beispiels für einen Automated Market Maker (AMM), bei dem eine Preisungskurve als Funktionswert gespeichert ist. Das System verifiziert erfolgreich:

Invarianzen: Eigenschaften wie „die Funktion bricht niemals ab", „Monotonie der Ausgabe" und „Erhaltung des konstanten Produkts" werden mittels Verhaltensprädikaten und Zustandslabels verifiziert.
Compliance-Prüfung: Das Spezifikationsinferenzwerkzeug leitet automatisch Abbruchbedingungen für Preisungsfunktionen ab (z. B. die Erkennung, dass eine gebührenbasierte Preisungsfunktion abbricht, wenn eine Gebührenressource fehlt), was maschinenlesbare Compliance-Prüfungen ohne manuelle Annotationen ermöglicht.
Test-Suite: Eine umfassende Test-Suite, die direkte Aufrufe, gegenseitige Rekursion, höherstufige Parameter und Dispatch gespeicherter Closures abdeckt, bestätigt, dass die Kodierung intern konsistent ist und dass abgeleitete Spezifikationen für den Verifizierer eng genug sind, um die Beweise zu führen.

Bedeutung
Die Arbeit behauptet, dass diese Forschung die routinemäßige, produktionsorientierte Verifikation von Move-Smart-Verträgen mit dynamischer Dispatch und höherstufigen Funktionen ermöglicht. Durch die Bewahrung des Kostenmodells von MVP – bei dem die Verifikation innerhalb von Sekunden pro Funktion abgeschlossen wird – erlaubt die Erweiterung Entwicklern, komplexe Muster wie callback-basierte Asset-Flüsse und erweiterbare Asset-Manager mit formalen Garantien zu nutzen. Der Ansatz unterscheidet sich von auf Trennungslogik basierenden Werkzeugen durch die Nutzung der inhärenten statischen Speichertrennung von Move, um SMT-Kodierungen zu vereinfachen. Darüber hinaus bietet die Integration der Spezifikationsinferenz einen praktischen Weg zur Verifikation der Compliance von Funktionswerten und adressiert eine erhebliche Hürde für die Einführung höherstufiger Funktionen in sicherheitskritischen Smart-Verträgen. Die Arbeit erkennt an, dass, während die verifikation auf Anwendungseite nun mit der von First-Order-Funktionen vergleichbar ist, die Compliance-Verifikation (der Nachweis, dass eine übergebene Funktion einen Vertrag erfüllt) in komplexen Fällen möglicherweise immer noch manuelle Beweis-Hinweise oder vertrauenswürdige Annahmen erfordert.