Wat is een zk-STARK en hoe werkt het?

Wat is een zk-STARK?

Een zk-STARK is een cryptografische manier om te bewijzen dat een berekening correct is, zonder dat degene die de proof controleert de volledige berekening opnieuw hoeft uit te voeren. Dankzij de zero-knowledge-eigenschap kunnen bepaalde gegevens die bij de berekening worden gebruikt bovendien verborgen blijven.

De afkorting staat voor Zero-Knowledge Scalable Transparent ARgument of Knowledge. Dat klinkt technisch, maar de onderdelen zijn goed uit te leggen:

• Zero-Knowledge: je kunt bewijzen dat iets klopt zonder de onderliggende geheime informatie bekend te maken.
• Scalable: ook bij grote berekeningen kan de proof relatief efficiënt worden gecontroleerd.
• Transparent: er is geen trusted setup nodig. Er hoeft dus niet vooraf een speciale setup plaats te vinden waarbij geheime informatie ontstaat die daarna veilig moet worden vernietigd.
• Argument of Knowledge: een geldige proof laat zien dat de maker over de informatie beschikt die nodig is om de berekening correct uit te voeren. Het is daardoor extreem moeilijk om zomaar een geldige proof te vervalsen.

In crypto is dit vooral nuttig wanneer grote berekeningen buiten de blockchain worden uitgevoerd. Een systeem kan bijvoorbeeld veel transacties off-chain verwerken en daarna één proof naar de blockchain sturen. De blockchain hoeft dan niet iedere berekening opnieuw uit te voeren, maar controleert alleen of de aangeleverde proof geldig is.

Voorbeeld: Stel dat duizenden transacties buiten Ethereum worden verwerkt. In plaats van al die transacties opnieuw op Ethereum uit te voeren, kan een systeem één zk-STARK genereren die bewijst dat de hele batch volgens de regels is verwerkt. Ethereum hoeft vervolgens alleen die proof te controleren.

De basis voor STARKs werd in 2018 beschreven door Eli Ben-Sasson, Iddo Bentov, Yinon Horesh en Michael Riabzev. Het systeem is ontworpen om grote berekeningen efficiënt controleerbaar te maken zonder trusted setup.

Korte samenvatting

• Een zk-STARK bewijst dat een berekening correct is uitgevoerd zonder die volledig opnieuw te doen.
• Zero knowledge kan privé-invoer verborgen houden, maar is niet automatisch aanwezig in elke STARK-toepassing.
• STARKs hebben geen trusted setup met geheime parameters nodig.
• Bij rollups kunnen veel off-chain transacties met één validity proof op een blockchain worden gecontroleerd.
• De techniek kan zowel voor blockchain-scaling als voor verifieerbare berekeningen buiten crypto worden gebruikt.

Hoe werkt een zk-STARK?

Een zk-STARK zet een grote berekening om in een vorm die veel efficiënter te controleren is. De partij die de berekening uitvoert, de prover, maakt daarna een cryptografische proof. De verifier controleert die proof zonder de volledige oorspronkelijke berekening opnieuw uit te voeren.

Simpel gezegd: de prover doet het zware rekenwerk en de verifier controleert met een aantal cryptografische en wiskundige controles of het resultaat klopt.

In grote lijnen werkt dat zo:

1. De berekening wordt omgezet naar wiskundige regels: Eerst wordt vastgelegd aan welke regels iedere stap van de berekening moet voldoen. Bij STARKs gebeurt dit vaak via een zogenoemde Algebraic Intermediate Representation (AIR). Je kunt dit zien als een wiskundige beschrijving van wat tijdens de berekening wel en niet is toegestaan.

2. De prover legt alle rekenstappen vast: De prover voert de berekening uit en maakt daarbij een zogenoemde execution trace. Dit kun je zien als een grote tabel waarin de verschillende stappen van de berekening worden bijgehouden.

3. De gegevens worden cryptografisch vastgelegd: De prover verwerkt deze gegevens wiskundig en legt ze vast met cryptografische commitments, bijvoorbeeld met een Merkle tree. Daardoor kan de prover de gegevens achteraf niet zomaar veranderen.

4. De verifier controleert een selectie van de gegevens: Vervolgens worden op onvoorspelbare plekken controles uitgevoerd. De verifier controleert daarbij onder meer of de gegevens overeenkomen met de eerder vastgelegde commitments en of de wiskundige regels van de berekening zijn gevolgd. STARKs gebruiken hiervoor onder andere een techniek die FRI heet. Daarmee kan efficiënt worden gecontroleerd of de gebruikte wiskundige functies de juiste vorm hebben, zonder alle gegevens afzonderlijk te controleren.

5. De proof wordt geverifieerd: Als alle controles slagen, heeft de verifier sterke cryptografische zekerheid dat de berekening correct is uitgevoerd. De volledige berekening hoeft daarvoor niet opnieuw te worden uitgevoerd. Bij gebruik op een blockchain kan de prover de uiteindelijke proof naar een smart contract sturen. Dat contract controleert de proof en accepteert het nieuwe resultaat alleen wanneer deze geldig is. StarkWare gebruikt bijvoorbeeld on-chain verifiers op Ethereum om STARK-proofs te controleren.

Voorbeeld: Stel dat een rollup 1.000 transacties buiten Ethereum verwerkt. De rollup voert alle berekeningen uit en maakt daarna één proof die aantoont dat de transacties volgens de regels zijn verwerkt. Ethereum hoeft die 1.000 transacties vervolgens niet allemaal opnieuw uit te voeren. In plaats daarvan controleert een smart contract de proof. Is deze geldig, dan kan de nieuwe toestand van de rollup worden geaccepteerd.

Dit maakt zk-STARKs vooral interessant voor schaalbaarheid: veel rekenwerk kan buiten de blockchain plaatsvinden, terwijl de blockchain toch cryptografisch kan controleren of het resultaat correct is.

Wat zijn zero-knowledge proofs?

Een zero-knowledge proof maakt het mogelijk om te bewijzen dat een bewering klopt zonder de geheime informatie achter die bewering prijs te geven.

Simpel gezegd: de prover laat aan de verifier zien dat iets correct is, zonder alle onderliggende gegevens te hoeven delen.

Een zero-knowledge proof heeft drie belangrijke eigenschappen:

• Completeness: als de bewering klopt en de prover alles correct uitvoert, kan de verifier de proof accepteren.
• Soundness: iemand die probeert een onjuiste bewering te bewijzen, heeft slechts een verwaarloosbaar kleine kans om daarmee weg te komen.
• Zero knowledge: de verifier leert geen extra geheime informatie, behalve dat de bewering klopt.

Voorbeeld: Een systeem kan bewijzen dat een batch transacties volgens alle regels is verwerkt, zonder bepaalde privégegevens uit die transacties openbaar te maken.

Bij een rollup kan de publieke bewering bijvoorbeeld zijn dat een nieuwe state root voortkomt uit een geldige reeks transacties. Welke gegevens daarbij verborgen blijven, hangt af van hoe het proof-systeem en de toepassing zijn ontworpen.

Belangrijk om te weten: een validity proof biedt niet automatisch privacy. Een systeem kan cryptografisch bewijzen dat transacties correct zijn verwerkt terwijl de transactiedata zelf nog steeds openbaar is. Voor privacy moet de zero-knowledge-eigenschap bewust in het systeem zijn ingebouwd.

Wat is de rol van STARKs?

STARKs zijn het proof-systeem waarmee grote berekeningen efficiënt kunnen worden bewezen en gecontroleerd zonder trusted setup.

De zero-knowledge-eigenschap bepaalt daarbij welke informatie verborgen kan blijven. De STARK-techniek zorgt ervoor dat de verifier efficiënt kan controleren of de berekening volgens de regels is uitgevoerd.

Een belangrijk kenmerk van STARKs is dat ze transparent zijn. Er is geen trusted setup nodig waarbij vooraf geheime cryptografische parameters worden aangemaakt die daarna veilig moeten worden vernietigd. In plaats daarvan steunt het systeem onder meer op publieke willekeur en cryptografische hashfuncties.

STARKs gebruiken daarnaast technieken zoals FRI, waarmee efficiënt kan worden gecontroleerd of de wiskundige structuur achter de proof klopt.

De term Argument of Knowledge betekent dat een prover niet zomaar een geldige proof kan maken. Onder de beveiligingsaannames van het systeem moet de prover beschikken over de informatie die nodig is om de berekening correct uit te voeren.

Waarvoor worden zk-STARKs gebruikt?

zk-STARKs worden vooral gebruikt om grote berekeningen buiten een blockchain uit te voeren en daarna met één cryptografische proof te bewijzen dat het resultaat klopt. Een belangrijke toepassing daarvan zijn validity rollups.

Bij zo'n rollup worden veel transacties buiten de basislaag verwerkt. Daarna wordt een proof naar de blockchain gestuurd die aantoont dat de nieuwe toestand volgens de regels uit de oude toestand is ontstaan.

Dat is handig omdat de basislaag niet alle berekeningen opnieuw hoeft uit te voeren. De kosten van één proof kunnen zo over een grote groep transacties worden verdeeld.

Een bekend voorbeeld is StarkEx. Dit systeem gebruikt STARK-proofs om grote hoeveelheden transacties te verwerken voor toepassingen zoals handel, betalingen, gaming en NFT's. De transacties worden gebundeld, waarna een proof wordt gemaakt en door een smart contract op Ethereum wordt gecontroleerd.

STARK-technologie kan ook buiten crypto worden gebruikt. In principe is de techniek geschikt voor situaties waarin je wilt bewijzen dat een grote berekening correct is uitgevoerd zonder dat de controleur alle berekeningen opnieuw hoeft te doen. Met zero knowledge kunnen daarbij ook bepaalde onderliggende gegevens verborgen blijven.

Een proof lost alleen niet alles op. Bij rollups blijft bijvoorbeeld belangrijk waar de gegevens van transacties beschikbaar zijn. Een geldige proof bewijst dat de berekening volgens de vastgelegde regels klopt, maar zorgt niet automatisch voor de beschikbaarheid van alle data.

Welke blockchains gebruiken STARKs?

Het bekendste voorbeeld van een blockchainnetwerk dat STARK-proofs gebruikt is Starknet. Starknet is een Layer 2 bovenop Ethereum die veel transacties buiten Ethereum verwerkt en daarna een STARK-proof naar Ethereum stuurt.

Ethereum controleert deze proof om te bevestigen dat de nieuwe toestand van Starknet correct is berekend. Daardoor hoeft Ethereum niet alle transacties die op Starknet plaatsvinden afzonderlijk opnieuw uit te voeren.

Ook StarkEx gebruikt STARK-proofs, maar StarkEx is geen zelfstandige blockchain. Het is een scaling-oplossing waarmee verschillende crypto-applicaties grote hoeveelheden transacties buiten Ethereum kunnen verwerken en daarna cryptografisch kunnen bewijzen dat de berekeningen correct zijn uitgevoerd.

Ethereum zelf gebruikt STARKs dus niet als eigen consensus- of transactiemechanisme. Het netwerk kan wel STARK-proofs controleren die door toepassingen en Layer 2-netwerken zoals Starknet worden aangeleverd.

Belangrijk om te weten: het gebruik van STARK-proofs betekent niet automatisch dat transacties privé zijn. Starknet gebruikt STARK validity proofs om te bewijzen dat berekeningen correct zijn uitgevoerd, terwijl zero-knowledge privacy een aparte eigenschap is.

Wat zijn de voordelen van zk-STARKs?

zk-STARKs maken het mogelijk om grote berekeningen veel efficiënter te controleren dan wanneer iedere deelnemer alle berekeningen opnieuw zou moeten uitvoeren.

De belangrijkste voordelen zijn:

• Geen trusted setup: STARKs hebben geen voorafgaande ceremonie nodig waarbij geheime cryptografische informatie wordt aangemaakt en daarna veilig moet worden vernietigd.
• Efficiënte verificatie: de verifier kan een grote berekening controleren zonder iedere afzonderlijke stap opnieuw uit te voeren.
• Geschikt voor schaalbaarheid: één proof kan de correcte uitvoering van een grote batch transacties aantonen, waardoor blockchains meer transacties buiten de basislaag kunnen verwerken.
• Mogelijkheid tot privacy: wanneer zero knowledge in het systeem is ingebouwd, kunnen bepaalde privégegevens verborgen blijven terwijl de berekening toch controleerbaar is.
• Hash-gebaseerde beveiliging: STARKs steunen voor hun proving layer op cryptografische hashfuncties in plaats van op elliptische-curve-pairings die in veel klassieke SNARK-systemen worden gebruikt.

Door die hash-gebaseerde aanpak worden STARKs ook vaak gezien als beter voorbereid op een toekomst met krachtige quantumcomputers. Bekende quantumalgoritmes vormen namelijk een groter probleem voor veel elliptische-curveconstructies dan voor goed gekozen cryptografische hashfuncties.

Dat betekent niet dat iedere toepassing met STARKs automatisch volledig quantumveilig is. Ook de gebruikte hashfuncties, parameters, implementatie en andere cryptografische onderdelen van het systeem blijven belangrijk.

Wat zijn de beperkingen van zk-STARKs?

zk-STARKs hebben ook nadelen. Vooral het maken van een proof kan veel rekenkracht en geheugen vragen. Het zware werk verdwijnt dus niet, maar wordt vooral verplaatst naar de prover.

Daarnaast zijn STARK-proofs doorgaans groter dan proofs van veel klassieke zk-SNARK-systemen. Dat kan betekenen dat er meer data moet worden verwerkt wanneer een proof op een blockchain wordt geverifieerd.

Andere beperkingen zijn:

• Technische complexiteit: ontwikkelaars moeten berekeningen correct omzetten naar een vorm die door het proof-systeem kan worden gecontroleerd.
• Kosten van proof-generatie: het maken van proofs kan veel rekenkracht vragen en daarmee kosten met zich meebrengen.
• De proof controleert alleen de vastgelegde regels: als de applicatielogica zelf een fout bevat, bewijst een geldige proof alleen dat die foutieve regels correct zijn gevolgd.
• Privacy is niet automatisch aanwezig: een STARK-gebaseerd systeem kan validity proofs gebruiken zonder transactiedata geheim te houden.

Kort gezegd: een STARK-proof kan heel sterk bewijzen dat een bepaalde berekening volgens de vastgelegde regels is uitgevoerd, maar kan niet bepalen of die regels zelf goed zijn ontworpen.

Wat is het verschil tussen zk-STARKs en zk-SNARKs?

zk-STARKs en zk-SNARKs hebben hetzelfde algemene doel: efficiënt bewijzen dat een berekening correct is uitgevoerd zonder dat de verifier de volledige berekening opnieuw hoeft uit te voeren.

Het belangrijkste verschil zit in de cryptografische techniek die daarvoor wordt gebruikt.

Een belangrijk voordeel van zk-SNARKs is dat proofs bij veel systemen zeer klein kunnen zijn. Daardoor zijn ze aantrekkelijk wanneer de hoeveelheid data die on-chain moet worden geverifieerd zo klein mogelijk moet blijven.

zk-STARKs hebben meestal grotere proofs, maar hebben geen trusted setup nodig en gebruiken andere cryptografische aannames. Daardoor zijn ze vooral aantrekkelijk voor grote berekeningen en toepassingen waar transparantie van de setup belangrijk is.

Het is wel belangrijk om niet alle zk-SNARKs over één kam te scheren. zk-SNARK is een verzamelnaam voor meerdere proof-systemen. Niet iedere SNARK gebruikt dezelfde cryptografie en niet iedere variant vereist dezelfde soort trusted setup.

Ook bij beide technieken geldt dat een validity proof niet automatisch privacy betekent. Zero knowledge moet onderdeel zijn van het specifieke proof-systeem en de toepassing.

Conclusie

Een zk-STARK is een cryptografische techniek waarmee je kunt bewijzen dat een grote berekening correct is uitgevoerd zonder dat de verifier die volledige berekening opnieuw hoeft uit te voeren.

Dat maakt zk-STARKs vooral interessant voor blockchain-schaalbaarheid. Rollups kunnen grote hoeveelheden transacties buiten de basislaag verwerken en daarna met één proof aantonen dat het resultaat klopt.

Belangrijke voordelen zijn de transparante opzet zonder trusted setup en de efficiënte verificatie van grote berekeningen. Daar staan grotere proofs, veel rekenwerk voor de prover en technische complexiteit tegenover.

zk-STARKs zijn dus vooral een manier om grote berekeningen efficiënt en cryptografisch controleerbaar te maken. Privacy kan daar onderdeel van zijn, maar is niet automatisch aanwezig.