💻 computer science

Formal Verification of Imperative First-Class Functions in Move

Dit artikel presenteert een uitbreiding van de Move Prover die de formele verificatie van imperatieve first-class functies in de Move-taal mogelijk maakt door het introduceren van gedragspredicaten, statelabels en een SMT-coderingsstrategie die gebruikmaakt van Moves statische geheugenscheiding voor efficiënte verificatie en geautomatiseerde specificatie-inferentie.

Oorspronkelijke auteurs: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

Gepubliceerd 2026-05-14

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: De "Slimme Contracten"-Fabriek

Stel je voor dat Aptos een fabriek met hoge beveiliging is die digitale activa (zoals geld of tickets) bouwt met een speciale taal genaamd Move. Om ervoor te zorgen dat deze activa niet worden gestolen of beschadigd, gebruikt de fabriek een robotinspecteur genaamd de Move Prover (MVP). Deze robot leest de blauwdrukken (de code) en bewijst wiskundig dat alles correct zal werken voordat de fabriek ooit start.

Lange tijd was deze robot uitstekend in het controleren van eenvoudige instructies. Maar recentelijk voegde de fabriek een nieuwe, lastige functie toe: Eerste-Klas Functies.

Denk aan deze nieuwe functies als toverstaven.

Oude manier: Je moest de toverstaf zelf vasthouden om een spreuk te gooien. De robot wist precies welke spreuk je gooide.
Nieuwe manier: Je kunt de toverstaf in een doos doen, de doos aan een vriend geven, de doos in een kluis bewaren, of hem doorgeven aan een machine die niet weet wat erin zit. De machine weet alleen: "Ik moet een toverstaf zwaaien", maar weet pas op het allerlaatste moment welke toverstaf het is.

Dit heet Dynamische Dispatch. Het is krachtig, maar het maakt de robotinspecteur stuk omdat hij niet in de toekomst kan kijken om te weten welke specifieke spreuk wordt gegooid.

Het Probleem: Het "Zwarte Doos"-Dilemma

Het artikel legt uit hoe de auteurs de robotinspecteur (MVP) hebben opgewaardeerd om met deze toverstaven om te gaan zonder in paniek te raken.

Vroeger, als een functie een "zwarte doos" was (een variabele die een functie bevatte), moest de robot gissen of elke enkele mogelijkheid tegelijkertijd controleren, waardoor de wiskunde ontplofte en de robot vertraagde.

De auteurs introduceerden twee nieuwe hulpmiddelen om dit op te lossen:

1. Gedragspredicaten: Het "Garantiebewijs"

In plaats van in de toverstaf te kijken om te zien hoe hij werkt, kijkt de robot nu naar het Garantiebewijs dat aan de toverstaf is bevestigd.

De Oude Manier: "Ik moet precies weten hoe deze calculate_price-toverstaf werkt, tot op elke regel code, voordat ik je toestaat hem te gebruiken."
De Nieuwe Manier: "Het maakt me niet uit hoe de toverstaf van binnen werkt. Ik moet alleen zijn Garantiebewijs lezen. Het kaartje zegt: 'Als je me 5 munten geeft, geef ik je 3 munten terug, en ik zal nooit breken.'"

Het artikel noemt deze Gedragspredicaten. Ze zijn als een contract dat beschrijft:

Pre-condities: Wat waar moet zijn voordat je de toverstaf zwaait.
Post-condities: Wat waar zal zijn nadat je hem hebt gezwaaid.
Abort-condities: Wanneer de toverstaf kan ontploffen (falen).

Dit stelt de robot in staat om de belofte van de toverstaf te controleren zonder de geheime receptuur erin te hoeven kennen.

2. Staatlabels: De "Tijdstempel-Camera"

Soms gebeurt een reeks gebeurtenissen. Stel je een fabriekslijn voor waar een robot een auto schildert, en daarna een andere robot de wielen erop zet.

Als je wilt bewijzen dat de auto veilig is, moet je de staat van de auto kennen na het schilderen maar voordat de wielen erop zitten.

De auteurs introduceerden Staatlabels. Denk hierbij aan Tijdstempel-Camera's die op specifieke punten in het proces zijn geplaatst.

Camera A (Start): De auto is naakt metaal.
Camera B (Midden): De auto is geschilderd.
Camera C (Einde): De wielen zitten erop.

De robot kan nu zeggen: "Ik weet dat het schilderen gebeurde tussen Camera A en Camera B, en dat de wielen werden toegevoegd tussen Camera B en Camera C." Dit helpt de robot om te redeneren over complexe reeksen gebeurtenissen zonder in de war te raken over hoe de wereld er op elk willekeurig moment uitzag.

Hoe de Robot Eigenlijk Werkt (De "Schakelbord")

Het artikel beschrijft hoe de robot deze ideeën vertaalt naar wiskunde (SMT-logica) die een computer kan oplossen.

Stel je voor dat de robot een Schakelbord heeft.

Scenario A (Bekende Toverstaf): Als de robot een specifieke, bekende toverstaf ziet (bijvoorbeeld de product-functie), schakelt hij over naar "Directe Modus". Hij negeert het garantiebewijs en controleert gewoon de daadwerkelijke code van die specifieke toverstaf.
Scenario B (Onbekende Toverstaf): Als de robot een generieke doos ziet (een variabele), schakelt hij over naar "Abstracte Modus". Hij negeert de code volledig en vertrouwt alleen op het Garantiebewijs (de gedragspredicaten) om te bewijzen dat het systeem veilig is.

Dit is efficiënt omdat de robot niet elke mogelijke doos hoeft te proberen open te maken. Hij opent alleen diegene die hij kent, en voor de rest vertrouwt hij op het contract.

De "Auto-Inspecteur" (Specificatie-inferentie)

Een van de coolste delen van het artikel is dat de robot nu zijn eigen Garantiebewijzen kan schrijven.

Meestal moeten mensen deze kaarten handmatig schrijven, wat saai is. De auteurs hebben de robot opgewaardeerd zodat hij naar de code kan kijken, uitzoeken wat het Garantiebewijs zou moeten zeggen, en het voor je schrijft.

Input: Een rommelig stuk code met een toverstaf.
Robotactie: "Ik zie dat deze code controleert of een vergoeding bestaat. Ik zal een Garantiebewijs schrijven dat zegt: 'Deze toverstaf zal ontploffen als de vergoeding ontbreekt.'"
Resultaat: De robot controleert zijn eigen werk. Als de code overeenkomt met het kaartje, slaagt het.

Dit wordt in het artikel gedemonstreerd met een Automated Market Maker (AMM)-voorbeeld. Dit is een systeem dat activa verhandelt. De robot bewees dat, zelfs als de prijsbepalingsregel (de toverstaf) door de gebruiker kan worden gewijzigd, het systeem nooit zou crashen of geld zou verliezen, mits de nieuwe toverstaf de regels op zijn Garantiebewijs volgde.

Samenvatting van de Prestatie

Het artikel beweert een grote hoofdpijn bij het verifiëren van slimme contracten op te hebben gelost:

Het maakte "Toverstaven" (functies) veilig om te gebruiken op een manier die toestaat dat ze worden opgeslagen, rondgegeven en dynamisch gewijzigd.
Het creëerde een nieuwe taal (Gedragspredicaten + Staatlabels) die de robot in staat stelt om over deze toverstaven te praten zonder ze van binnen te hoeven zien.
Het maakte de robot sneller en slimmer door een "Schakelbord"-aanpak te gebruiken die schakelt tussen het kijken naar de code en het kijken naar het contract.
Het automatiseerde het papierwerk door de robot de benodigde contracten voor je te laten genereren.

Kortom, ze leerden de robotinspecteur om te vertrouwen op de belofte van een vreemde (het contract) zonder de geheimen van die vreemde te hoeven kennen, waardoor de fabriek veiliger en flexibeler werd.

Technische Samenvatting: Formele Verificatie van Imperatieve Eerste-Klas Functies in Move

Probleemstelling
De Move Prover (MVP) is een hulpmiddel voor formele verificatie dat is ontworpen voor Move-smartcontracts en oorspronkelijk is gebouwd op een modulaire, statische-dispatch specificatiestijl. Een recente uitbreiding van de Move-taal introduceerde hogere-orde functies, waardoor functies eerste-klas waarden kunnen zijn die als argumenten kunnen worden doorgegeven, in datastructuren kunnen worden opgeslagen en in globale opslag kunnen worden vastgelegd. Deze mogelijkheid maakt dynamische dispatch mogelijk, maar doorbreekt de statische analyse-aannames waarop MVP leunde. Specifiek kunnen bij een dynamische functieaanroep de pre- en postcondities niet bij de aanroepplaats worden opgelost. De aanroeper moet abstract redeneren over het gedrag van functie-waarde-argumenten, terwijl de verificateur deze abstracte specificaties moet verzoenen met de concrete functies die de aanroepplaats kunnen bereiken. Bestaande oplossingen in andere talen (bijv. Dafny, F*, Verus) missen ofwel ondersteuning voor imperatieve eerste-klas functies die toestand wijzigen, of vertrouwen op separatielogica, wat kan leiden tot complexe SMT-coderingen. De uitdaging is om deze dynamische functies efficiënt te ondersteunen, zodat verificatie snel blijft, compleet is voor relevante gevallen en vrij is van SMT-trigger-instabiliteit.

Methodologie
De auteurs breiden MVP en de Move-specificatietaal uit om hogere-orde functies te ondersteunen via drie primaire mechanismen:

Gedragspredicaten: De specificatietaal wordt uitgebreid met predicaten die het gedrag van functiewaarden ( $f$ ) op specifieke argumenten ( $\bar{x}$ ) en resultaten ( $\bar{y}$ ) karakteriseren. Deze omvatten:
- requires_of<f>(x): Precondities.
- aborts_of<f>(x): Afbreekcondities.
- ensures_of<f>(x, y): Postcondities.
  Deze predicaten houden impliciet lees- en lees/schrijftoestandsafhankelijkheden bij, waardoor specificaties abstract kunnen verwijzen naar functieargumenten zonder hun lichamen in te lijnen.
Toestandlabels: Om redeneren over sequentiële toestandsovergangen en tussenliggende geheugentoestanden mogelijk te maken, introduceren de auteurs toestandlabels (bijv. $S$ ). Deze labels benoemen specifieke punten in de uitvoering. Predicaten kunnen een-toestands ( $S \mid \sim p$ ) of twee-toestands ( $S.. \mid \sim q$ ) zijn, waardoor de compositie van gedragspredicaten mogelijk is om reeksen van bewerkingen te beschrijven (bijv. de post-toestand van de ene functie die de pre-toestand van een andere wordt).
SMT-codering via Variant-discriminatie: Op het SMT-niveau worden functiewaarden gecodeerd met behulp van algebraïsche datatypen die alle mogelijke bronnen van een functiewaarde vertegenwoordigen (concrete closures, functieparameters of struct-velden). Wanneer een functiewaarde wordt aangeroepen:
- Als de concrete functie bekend is (bijv. een specifieke closure), wordt de aanroep vervangen door het effect van die concrete functie.
- Als de functie onbekend is (bijv. een parameter of een closure geladen uit opslag), wordt de aanroep gemodelleerd met behulp van de gedragspredicaten die geassocieerd zijn met het type van die functiewaarde.
- De codering gebruikt "havoc" en "assume"-constructies om geheugenwijzigingen te modelleren en zorgt ervoor dat framecondities worden gerespecteerd door onderscheid te maken tussen de pre-toestand en post-toestand geheugenkaarten.

Belangrijkste Bijdragen
Het artikel beschrijft de volgende specifieke bijdragen:

Taaluitbreidingen: De introductie van gedragspredicaten en toestandlabels in de Move-specificatietaal, waardoor functiespecificaties eerste-klas burgers worden die toestandsafhankelijkheden kunnen bijhouden.
Implementatie in MVP: Een Boogie-gebaseerde codering die bij aanroepplaatsen discrimineert over functiewaarde-varianten. Deze aanpak elimineert de noodzaak voor separatielogica door gebruik te maken van Moves statische geheugenscheiding (resource-model), wat leidt tot efficiëntere SMT-coderingen.
Specificatie-inferentie: Een uitbreiding van MVP's zwakste-preconditie (WP)-analysehulpmiddel om hogere-orde code te verwerken. Dit hulpmiddel leidt semi-automatisch gedragspredicaat-gebaseerde specificaties af van willekeurige Move-bytecode, wat de last van handmatige annotatie vermindert en een validatiepijplijn biedt voor de nieuwe constructies.
Omgaan met Imperatieve Bijwerkingen: In tegenstelling tot sommige bestaande hulpmiddelen (bijv. Dafny) ondersteunt deze aanpak imperatieve eerste-klas functies die toestand wijzigen via Rust-stijl referenties en globale variabelen.

Resultaten en Validatie
De auteurs demonstreren de aanpak aan de hand van een Automated Market Maker (AMM)-voorbeeld waarbij een prijscurve wordt opgeslagen als een functiewaarde. Het systeem verifieert met succes:

Invarianten: Eigenschappen zoals "de functie breekt nooit af", "monotonie van output" en "behoud van constant-product" worden geverifieerd met behulp van gedragspredicaten en toestandlabels.
Compliance-checking: Het specificatie-inferentie-hulpmiddel leidt automatisch afbraakcondities af voor prijsbepalende functies (bijv. detecteren dat een prijsbepalende functie met commissie afbreekt als een commissie-resource ontbreekt), wat machine-leesbare compliance-checks mogelijk maakt zonder handmatige annotaties.
Testset: Een uitgebreide testset die directe aanroepen, wederzijdse recursie, hogere-orde parameters en dispatch van opgeslagen closures bestrijkt, bevestigt dat de codering intern consistent is en dat de afgeleide specificaties strak genoeg zijn voor de verificateur om ze te ontladen.

Beteekenis
Het artikel stelt dat dit werk de routinematige, productie-gerichte verificatie van Move-smartcontracts met dynamische dispatch en hogere-orde functies mogelijk maakt. Door het kostenmodel van MVP te behouden – waarbij verificatie binnen enkele seconden per functie wordt voltooid – stelt de uitbreiding ontwikkelaars in staat complexe patronen zoals callback-gebaseerde assetstromen en uitbreidbare assetmanagers te gebruiken met formele garanties. De aanpak verschilt van op separatielogica gebaseerde hulpmiddelen door gebruik te maken van Moves inherente statische geheugenscheiding om SMT-coderingen te vereenvoudigen. Bovendien biedt de integratie van specificatie-inferentie een praktische weg voor het verifiëren van de compliance van functiewaarden, waarmee een significante barrière voor de adoptie van hogere-orde functies in veiligheidskritieke smartcontracts wordt aangepakt. Het werk erkent dat, hoewel verificatie aan de applicatiekant nu vergelijkbaar is met die van eerste-orde functies, verificatie aan de compliance-kant (het bewijzen dat een doorgegeven functie voldoet aan een contract) in complexe gevallen mogelijk nog steeds handmatige bewijshints of vertrouwde aannames vereist.