💻 computer science

Automating Bitvector and Finite Field Equivalence Proofs in Lean

Dit artikel introduceert BitModEq, een nieuwe Lean-tactiek die equivalentiebewijzen tussen bitvectoren en eindige velden automatiseert met behulp van bereiklemma's en casusanalyse, en die superieur is aan de meest geavanceerde SMT-oplossers bij het verifiëren van coderingen van Zero-Knowledge Proof-circuits.

Oorspronkelijke auteurs: Elizaveta Pertseva, Valentin Robert, Clark Barrett, James Parker

Gepubliceerd 2026-05-15

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Elizaveta Pertseva, Valentin Robert, Clark Barrett, James Parker

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: Twee Verschillende Talen voor Wiskunde

Stel je voor dat je wilt verifiëren of een geheim recept (een Zero-Knowledge Proof) correct werkt. Het probleem is dat het recept is geschreven in twee verschillende talen die niet goed samengaan:

Eindige Velden: Denk hierbij aan een wereld van "Klok-wiskunde". Als je een klok hebt met 17 uur, dan geeft het optellen van 10 en 10 niet 20; het geeft 3 (omdat je om de hoek slaat). Zo doen veel moderne cryptografische systemen (zoals die in cryptocurrencies) hun wiskunde.
Bitvectoren: Denk hierbij aan "Computerwiskunde". Computers slaan niet om zoals klokken; ze hebben gewoon een vast aantal schakelaars (bits) die aan of uit zijn. Als je getallen optelt en de schakelaars opraken, worden de extra bits gewoon afgekapt.

Het Probleem:
Wanneer ontwikkelaars deze cryptografische systemen bouwen, moeten ze de "Klok-wiskunde" vertalen naar "Computerwiskunde" om het op echte hardware te laten draaien. Deze vertaling heet arithmetisatie.

Als de vertaling verkeerd is, is het hele beveiligingssysteem gebroken.
Controleren of de vertaling correct is, is ongelooflijk moeilijk.
Handmatig controleren is als het nalezen van een roman door elk woord met een vergrootglas te lezen: het is accuraat, maar duurt eeuwen en is vatbaar voor menselijke fouten.
Automatisch controleren (met standaard computersolvers) is als het gebruik van een spellingscontrole: het is snel, maar het raakt vaak in de war door de vreemde "Klok-wiskunde"-regels en geeft op bij complexe zinnen.

De Oplossing: De "BitModEq"-Vertaler

De auteurs bouwden een nieuw hulpmiddel genaamd BitModEq binnen een systeem dat Lean heet (wat lijkt op een super-strenge wiskundeleraar die elke stap van een bewijs controleert).

Denk aan BitModEq als een gespecialiseerde vertaler die niet alleen woorden verwisselt; het begrijpt de logica achter de woorden. Het gebruikt een drie-stappenproces om te bewijzen dat het "Klok-wiskunde"-recept exact hetzelfde is als het "Computerwiskunde"-recept:

Stap 1: Het "Uitpakken" (Vertaling)

Het hulpmiddel neemt de "Klok-wiskunde" (Eindige Velden) en probeert het te "ontpakken" naar normale getallen (Natuurlijke Getallen).

De Uitdaging: In Klok-wiskunde kan $5 - 10$ een positief getal zijn vanwege het om-slaan. In normale wiskunde is het negatief.
De Truc: Het hulpmiddel kijkt naar de getallen en vraagt: "Is het mogelijk dat dit getal om slaat?" Als de getallen klein genoeg zijn (zoals bits in een computer), weet het dat om-slaan niet zal gebeuren. Het verwijdert veilig de "Klok"-regels en behandelt ze als normale wiskunde. Als het niet zeker is, behoudt het de "Klok"-regels maar voegt het een veiligheidscontrole toe.

Stap 2: Het "Veiligheidsnet" (Bereiksanalyse)

Dit is het geheime ingrediënt van het paper. Voordat het hulpmiddel probeert de wiskunde om te zetten naar computerbits, voert het een Bereiksanalyse uit.

De Analogie: Stel je voor dat je een koffer inpakt. Je gooit kleding niet zomaar erin; je controleert de grootte van de koffer en de grootte van de kleding.
Hoe het werkt: Het hulpmiddel kijkt naar de variabelen en vraagt: "Wat is het grootste dat dit getal mogelijk kan zijn?"
- Als het weet dat een getal tussen 0 en 1 ligt (zoals een enkele lichtschakelaar), kan het de complexe "Klok"-regels volledig negeren.
- Deze stap is cruciaal omdat het het probleem zo sterk vereenvoudigt dat de computer het gemakkelijk kan oplossen. Zonder deze "veiligheidsnet"-controle wordt de computer overweldigd door de complexiteit.

Stap 3: Het "Bit-Blasten" (Definitief Bewijs)

Zodra het hulpmiddel het probleem heeft vereenvoudigd tot pure "Computerwiskunde" (bits), gebruikt het een techniek genaamd bit-blasting.

De Analogie: Dit is als het nemen van een complex slot en elke mogelijke combinatie van sleutels proberen totdat je die vindt die het opent.
Omdat het hulpmiddel het probleem in Stap 2 heeft vereenvoudigd, is het "slot" nu klein genoeg voor de computer om elke combinatie direct te proberen en te bewijzen dat de wiskunde correct is.

Waarom Dit Belangrijk Is (De Resultaten)

De auteurs testten hun hulpmiddel op echte cryptografische systemen (specifiek Jolt en CirC).

De Wedstrijd: Ze vergeleken hun hulpmiddel met de beste bestaande automatische solvers (zoals cvc5).
Het Resultaat: De bestaande solvers bleven vaak steken of liepen op tijd uit wanneer de problemen groot werden (zoals 32-bits getallen). Ze waren als een spellingscontrole die probeerde een woordenboek te lezen.
De Overwinning van BitModEq: Het nieuwe hulpmiddel loste 19% meer problemen op dan de beste bestaande hulpmiddelen. Het kon veel grotere getallen aan (tot 32 bits) waar de anderen faalden.
Bonus: Omdat het binnen Lean draait, is het bewijs kernel-gecontroleerd. Dit betekent dat de computer niet alleen maar gokte; het volgde een strikte set logische regels die gegarandeerd correct zijn, waardoor het risico op verborgen bugs wordt verkleind.

Een Wereldwijde Ontdekking

Tijdens hun testen vond het hulpmittel daadwerkelijk een bug in de CirC-compiler. De compiler had een fout in hoe het grote getallen verwerkte (specifiek, een 32-bits rechtsverschuiving). De bug kwam alleen voor bij grote getallen, wat de reden was waarom eerdere, kleinschaligere testen het hadden gemist. De ontwikkelaars hebben de bug opgelost nadat de auteurs het hadden gemeld.

Samenvatting

Het paper presenteert een nieuwe manier om automatisch te verifiëren dat cryptografische wiskunde correct werkt. In plaats van te worstelen met het handmatig vertalen tussen "Klok-wiskunde" en "Computerwiskunde" of met onhandige hulpmiddelen, bouwden ze een slimme vertaler die:

Eerst de grootte van de getallen controleert (Bereiksanalyse).
De wiskunde vereenvoudigt door onnodige "Klok"-regels te verwijderen.
Brute-force logica gebruikt om te bewijzen dat het eindresultaat correct is.

Dit maakt het verifiëren van complexe beveiligingssystemen sneller, betrouwbaarder en in staat bugs op te sporen die andere hulpmiddelen missen.

Technische Samenvatting: Automatisering van Bitvector- en Eindige Veld-equivalentiebewijzen in Lean

Probleemstelling

De verificatie van Zero-Knowledge Proof (ZKP)-circuit-coderingen staat voor een kritieke uitdaging: het bewijzen van de correctheid van kwantorenvrije stellingen die gelijktijdig bitvector-operaties (standaard machine-aritmetica modulo $2^N$ ) en eindige veld-operaties (aritmetica modulo een groot priemgetal $P$ ) gebruiken. ZKP-systemen vereisen vaak "aritmetiseringen" die bitvector-logica coderen als polynomen in een eindig veld. Het waarborgen dat deze coderingen correct zijn, is vitaal voor de geldigheid van ZKP-systemen, maar het construeren ervan is foutgevoelig.

Bestaande verificatiewerkstromen lijden onder twee primaire beperkingen:

Handmatige Verificatie: Het inbedden van volledige ZKP-systemen in Interactieve Theorema-bewijzers (ITP's) zoals Lean biedt sterke garanties, maar vereist aanzienlijke menselijke inspanning. Naarmate ZKP-optimalisaties zich snel ontwikkelen, vereisen deze handmatige bewijzen vaak aanzienlijke herwerking.
Automatische SMT-Verificatie: Het reduceren van verificatie tot Satisfiability Modulo Theories (SMT)-queries biedt grotere automatisering, maar kampt met twee fundamentele problemen:
- Theorie-conversie: SMT-oplossers missen native ondersteuning voor conversie tussen eindige velden en bitvectors. Workarounds zoals bit-splitsing introduceren overmatige variabelen, en bereikcontroles vereisen complexe polynomen die de prestaties van de oplosser verslechteren.
- Vertrouwd Code-basis (TCB): SMT-oplossers hebben een veel grotere TCB dan ITP's, wat het risico op gemiste bugs vergroot.

Methodologie

De auteurs presenteren BitModEq, een nieuwe Lean-tactiek ontworpen om automatisch de equivalentie tussen eindige veld-coderingen en hun overeenkomstige bitvector-semantiek te bewijzen. De aanpak maakt gebruik van de rijke semantiek van ITP's om directe typeconversies uit te voeren, terwijl de automatisering van SMT-oplossing behouden blijft via een gespecialiseerde werkstroom.

Kernwerkstroom

BitModEq werkt in vier distincte fasen (geïllustreerd in Figuur 1 van het paper):

Conversie van Eindig Veld naar Natuurlijk Getal: Alle termen van het soort Eindig Veld ($FP$) worden omgezet naar Natuurlijke Getallen ( $N$ ). Dit houdt in dat conversie-operatoren (zoals toNat) naar binnen worden geduwd door arithmetische expressies heen.
Bereikanalyse: Ongelijkheden over natuurlijke getallen die tijdens de conversie worden gegenereerd, worden afgehandeld met een dedicated bereikanalyse-algoritme.
Conversie van Natuurlijk Getal naar Bitvector: Overgebleven termen van natuurlijke getallen worden omgezet naar bitvectors ( $BV_N$ ).
Bit-Blasting: De uiteindelijke gelijkheidsdoelen voor bitvectors worden afgehandeld met bv_decide, een bit-blasting-beslissingsprocedure geïmplementeerd in Lean.

Belangrijkste Technische Componenten

1. Translatiecalculus (Secties 4.2)
De tactiek maakt gebruik van een set translatieregels om tussen domeinen te bewegen:

$FP \to N$ : Regels zoals distNat verdelen toNat over optelling en vermenigvuldiging. Cruciaal maakt de tactiek onderscheid tussen gevallen waar modulaire wraparound kan worden uitgesloten (waardoor eenvoudige aftrekking mogelijk is) en gevallen waar dit niet kan (waardoor het toevoegen van de modulus $P$ gevolgd door een modulo-operatie vereist is). Regels zoals sqrBds detecteren bit-coderingen (waarbij $x^2 = x$ ) en vertalen deze naar grenswaarden ( $x \le 1$ ).
$N \to BV$ : Regels zoals distBV verdelen toBV over operaties. In tegenstelling tot de stap $FP \to N$ vereisen deze regels geen toevoeging van een modulo-operator, omdat de doelruimte van nature modulo $2^N$ is.

2. Bereikanalyse (Sectie 4.3)
Standaard Lean-tactieken (zoals omega, linarith) falen vaak bij ZKP-aritmetiseringen vanwege grote coëfficiënten en complexe variabele-afhankelijkheden. BitModEq introduceert een aangepast, syntax-gestuurd bereikanalyse-calculus:

Plaatshoudervariabelen: Het algoritme introduceert existentiële plaatshoudervariabelen om complexe ongelijkheden te decomponeren.
Decompositie & Eliminatie: Regels decomponeren ongelijkheden (bijvoorbeeld $a + b \le w$ wordt $a \le w_1, b \le w_2, w_1+w_2 \le w$ ) en elimineren plaatshouders door ze te instantiëren met grenswaarden afgeleid uit hypothesen of bekende eigenschappen (bijvoorbeeld dat elementen in een eindig veld begrensd zijn door $P-1$ ).
Afhandeling van Afhankelijkheden: Gespecialiseerde regels (ineqCases, ineqXOR) voeren gerichte casusanalyse uit op variabelen die bits simuleren (0 of 1) om afhankelijkheden op te lossen die standaard arithmetische oplossers missen.

3. Implementatie
De tactiek is geïmplementeerd in Lean 4.23.0, met gebruikmaking van mathlib voor lemma's en bv_decide voor de laatste bit-blasting-stap. Het vertrouwt op de kernel van Lean voor bewijscontrole, waardoor een minimale Trusted Computing Base wordt gewaarborgd.

Belangrijkste Bijdragen

BitModEq Tactiek: Een Lean-tactiek die eindige veld-operaties vertaalt naar bitvectors en de resulterende doelen oplost via bit-blasting, waarbij de correctheidsgaranties van ITP's behouden blijven.
Beperkte Verificatie van Real-world Coderingen: Een proof-of-concept verificatie van twee real-world ZKP-systemen (Jolt en CirC) die hogere bit-breedte-grenswaarden bereikt dan eerdere technieken.
Gespecialiseerde Bereikanalyse: Een nieuwe Lean-tactiek voor het bewijzen van doelen die voortvloeien uit de translatie, specifiek ontworpen om de variabele-afhankelijkheden en ongelijkheidsbeperkingen aan te pakken die veelvoorkomend zijn in ZKP-aritmetiseringen.

Resultaten en Evaluatie

De auteurs hebben BitModEq geëvalueerd tegen state-of-the-art SMT-oplossers (specifiek cvc5 met volledige en gesplitste Gröbner-bases) op benchmarks ontleend aan Jolt (een zkVM) en CirC (een zkVM-compiler).

Prestaties: BitModEq loste 19% meer benchmarks op dan de best presterende SMT-configuraties.
- Op Jolt-benchmarks (8-bit en 32-bit zoektabellen) loste BitModEq 3 meer 8-bit en 7 meer 32-bit instanties op dan cvc5 (zwakke codering).
- Op CirC-benchmarks loste BitModEq meer instanties op voor 13 van de 17 geteste bit-breedtes.
Schaalbaarheid: Hoewel cvc5 beter presteerde op kleinere bit-breedtes, degradeerde de prestatie aanzienlijk naarmate de bit-breedte toenam door de explosie van variabelen als gevolg van bit-splitsing. BitModEq schaalde effectief tot 32-bit invoer.
Efficiëntie: Een ablatiestudie toonde aan dat de aangepaste bereikanalyse cruciaal is; het verwijderen van casus-splitsingen verminderde het aantal opgeloste benchmarks aanzienlijk (bijvoorbeeld van 737 naar 720 op CirC, en van 24 naar 21 op Jolt). Het vervangen van de aangepaste analyse door standaard Lean-tactieken (ring_nf, linarith, etc.) resulteerde in een drastische daling van het aantal opgeloste instanties (bijvoorbeeld 434 versus 737 op CirC).
Runtime: Bereikanalyse staat voor ongeveer 52% van de totale runtime, gevolgd door translatie (23%) en bit-blasting (21%).
Bug-ontdekking: Tijdens de evaluatie van CirC identificeerden de auteurs een geldigheidsbug in de implementatie van de 32-bit arithmetische rechtsverschuiving gerelateerd aan integer-overflow, die niet werd gedetecteerd bij kleinere bit-breedtes.

Betekenis en Claims

Het paper claimt dat BitModEq de specifieke beperkingen van huidige ZKP-verificatiewerkstromen aanpakt door de geldigheid van ITP's te combineren met automatisch redeneren. Door eindige veld-beperkingen terug te vertalen naar bitvectors, vermijdt de aanpak de prestatieknelpunten van SMT-theorieconversie en de grote TCB van SMT-oplossers.

De auteurs benadrukken dat hun aanpak bijzonder effectief is voor ZKP-aritmetiseringen die bit-niveau-operaties simuleren binnen een eindig veld, een veelvoorkomend patroon in moderne ZK-systemen. Hoewel de methode niet compleet is (het kan "onbekend" teruggeven voor bepaalde complexe afhankelijkheden of veldspecifieke operaties zoals inversen), verifieert het succesvol real-world coderingen die voorheen onbereikbaar waren voor automatische tools, en levert het door de kernel gecontroleerde bewijzen voor de correctheid van deze kritieke cryptografische componenten.