Isabelle/STARK: A Formalization of zk-STARK in Isabelle/HOL
Dit artikel presenteert een Isabelle/HOL-formalisatie van een STARK-stijl transparant bewijsprotocol, met een uitvoerbaar prover- en verifier-model, een probabilistische state-monade met weakest-precondition-calculus, en formeel geverifieerde stellingen voor zero-failure eerlijke volledigheid en betrouwbaarheid met expliciete waarschijnlijkheidsgrenzen.
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
Stel je voor dat je probeert te bewijzen dat je een geheim wachtwoord weet van een enorme, vergrendelde kluis, maar je wilt dat zonder het wachtwoord daadwerkelijk aan iemand te vertellen, en zonder dat zij urenlang hoeven te wachten terwijl jij het intypt. Dit is de wereld van de cryptografie, de wetenschap van veilige communicatie. In deze specifieke hoek kijken we naar een type digitaal bewijs dat een STARK wordt genoemd. Beschouw een STARK als een "magisch bonnetje". Als je een complex computerprogramma uitvoert, is een STARK een klein, onvervalsbaar briefje dat zegt: "Ik heb dit programma correct uitgevoerd, en hier is het resultaat," zonder de rommelige details te onthullen van hoe het programma werkte.
Om te begrijpen hoe deze bonnetjes werken, moet je drie eenvoudige dingen weten. Ten eerste zetten computers problemen vaak om in wiskundige puzzels met behulp van polynomen (die kromme lijnen die je misschien nog wel eens zag in de algebra). Ten tweede, om te bewijzen dat de wiskunde klopt, controleer je niet elk enkel getal; je neemt een paar willekeurige monsters, zoals het proeven van een lepel soep om te zien of de hele pan zout is. Ten derde, om ervoor te zorgen dat niemand de soep verandert nadat je ervan geproefd hebt, gebruik je een Merkle-boom, wat een soort digitale vingerafdruk is voor een enorme berg gegevens. Als zelfs één korrel rijst in de berg verandert, verandert de vingerafdruk volledig.
De grote vraag in dit veld is: "Kunnen we er absoluut zeker van zijn dat deze magische bonnetjes onmogelijk te vervalsen zijn?" Lange tijd hebben mensen de regels voor STARKs opgeschreven, maar regels opschrijven is iets anders dan bewijzen dat ze werken. Dat is waar formele verificatie in beeld komt. Het is alsof je een wiskundig bewijs invoert in een superstrikte robotadvocaat die elke logische stap controleert om ervoor te zorgen dat er geen gaten zijn, geen "misschien"s en geen verborgen trucjes. Dit is precies wat het artikel "Isabelle/STARK: A Formalization of zk-STARK in Isabelle/HOL" doet.
De auteur, Diego Marmsoler, heeft een complex STARK-protocol genomen en dit vertaald naar een taal die een computer kan begrijpen en met 100% zekerheid kan verifiëren. Ze hebben niet alleen een verhaal geschreven over hoe het zou moeten werken; ze hebben een werkend model gebouwd binnen een tool genaamd Isabelle/HOL. Deze tool fungeert als een rigoureuze wiskundeleraar die een antwoord pas accepteert als elke stap is gerechtvaardigd.
Dit is wat zij ontdekten. Ten eerste bouwden ze een speelbare versie van het systeem. Ze creëerden een digitale "Prover" (degene die het bonnetje maakt) en een "Verifier" (degene die het controleert) die daadwerkelijk op een computer kunnen draaien. Ze bewezen dat als de Prover eerlijk is en de regels volgt, de Verifier het bewijs altijd zal accepteren. Er is nul kans dat de eerlijke Prover faalt. Dit is als bewijzen dat als je het recept perfect volgt, de cake altijd zal rijzen.
Ten tweede, en het belangrijkste, pakten ze het enge deel aan: Wat als iemand probeert oneerlijk te handelen? Ze creëerden een scenario waarin een sluwe "Adversary" (tegenstander) probeert de Verifier te misleiden om een vals bonnetje te accepteren. Het artikel bewijst dat de kans dat deze Adversary slaagt niet nul is, maar extreem, mathematisch minuscuul. Ze zeiden niet alleen "het is onwaarschijnlijk"; ze schreven een specifieke formule die exact berekent hoe klein die kans is. Deze formule telt alle verschillende manieren op waarop een Adversary probeert oneerlijk te handelen — zoals het raden van de juiste willekeurige getallen, het vinden van een fout in de digitale vingerafdruk, of het vervalsen van een wiskundige vergelijking — en laat zien dat de totale slaagkans begrensd wordt door een zeer klein getal.
Het artikel sluit ook enkele "makkelijke" manieren om dit te bewijzen expliciet uit. Je zou kunnen denken: "Kunnen we niet gewoon de hele berg gegevens bekijken om te zien of het nep is?" De auteur zegt nee. In de echte wereld kijt de Verifier slechts naar een paar willekeurige plekken (de "proef van smaak"). Het artikel bewijst dat je er niet vanuit kunt gaan dat de Verifier het hele plaatje ziet. In plaats daarvan moet het bewijs werken, zelfs wanneer de Verifier slechts een kleine, gedeeltelijke blik werpt. Ze verwierpen ook het idee om er simpelweg van uit te gaan dat de wiskunde werkt; ze braken het bewijs af in kleine, beheersbare lagen, waarbij ze de "vingerafdruk"-logica apart controleerden van de "willekeurige bemonstering"-logica, en vervolgens lieten zien hoe deze samenkwamen.
Een van de coolste onderdelen van dit werk is dat ze het niet alleen bewezen voor een theoretische, oneindige wereld. Ze bouwden een kleine, werkende uitvoering met een zeer kleine wiskundige wereld (een veld met slechts 5 getallen, zoals een klok die slechts tot 5 loopt). Ze draalden de eerlijke Prover en Verifier op deze kleine klok en zagen ze slagen. Dit laat zien dat de code niet alleen een theorie is; het draait daadwerkelijk.
Dus, wat is de kern van het verhaal? Het artikel beweert niet dat het een nieuw type STARK heeft uitgevonden of dat het het systeem sneller heeft gemaakt. In plaats daarvan beweert het dat het de deur op slot heeft gedaan op de wiskunde. Het biedt een door een machine gecontroleerde garantie dat het STARK-protocol solide is. Als je de regels volgt, krijg je een bonnetje. Als je probeert de regels te breken, zegt de wiskunde dat je bijna geen kans hebt om ermee weg te komen, en de computer heeft elke stap van die logica gecontroleerd om dat zeker te weten. Het verandert een complex cryptografisch belofte in een geverifieerd feit, wat ons een niveau van vertrouwen geeft dat voortkomt uit een robotadvocaat die het huiswerk controleert, in plaats van alleen maar een mens die zegt: "Ik denk dat het er goed uitziet."
Verdrinkt u in papers in uw vakgebied?
Ontvang dagelijkse digests van de nieuwste papers die bij uw onderzoekswoorden passen — met technische samenvattingen, in uw taal.