Parallelle herhaling: hoe je een bewijs sterker maakt door vragen tegelijk te stellen
Stel je bent een grensbewaker die moet checken of iemand echt weet wat het wachtwoord van een geheim genootschap is, zonder dat woord zelf te horen. Je stelt een slimme vraag waarop alleen een ingewijde het juiste antwoord kan geven, maar een gokker heeft ook een kans van, zeg, vijftig procent om toevallig goed te antwoorden. Om zeker te zijn, stel je de vraag vaker. Doe je dat na elkaar, dan kan een sluwe bedrieger van de ene vraag leren voor de volgende. Stel je in plaats daarvan meteen tien vergelijkbare vragen tegelijk, zonder dat de bedrieger de antwoorden onderling kan afstemmen, dan wordt gokken ineens veel lastiger. Dat idee – dezelfde toets meerdere keren tegelijk in plaats van na elkaar afnemen – heet in de informatica parallelle herhaling (parallel repetition).
Het klinkt als een detail, maar parallelle herhaling is een van de fundamentele bouwstenen van de theoretische informatica en cryptografie. Het duikt op telkens wanneer computers elkaar (of mensen) moeten overtuigen van iets zonder alle informatie prijs te geven: bij zogeheten zero-knowledge-bewijzen, bij de wiskundige basis van blockchain-technieken die transacties compact bewijzen, en bij onderzoek naar de grenzen van wat kwantumcomputers kunnen. Intuïtief zou je verwachten dat de kans dat een bedrieger slaagt gewoon exponentieel daalt als je vaker test – maar bewijzen dat dit ook echt klopt, bleek verrassend lastig en leidde tot decennia onderzoek.
Wat is het precies?
Om parallelle herhaling te begrijpen, moet je eerst weten wat een interactief bewijssysteem is. Daarin praten twee partijen met elkaar: een bewijzer (prover), die beweert iets te weten of iets waar te kunnen maken, en een controleur (verifier), die dat wil checken zonder alles zelf te hoeven berekenen. De controleur stelt vragen; de bewijzer antwoordt. Bij een eerlijke bewijzer met een ware bewering lukt dat altijd. Bij een bedrieger die iets vals beweert, lukt het maar met een bepaalde kans te slagen — de zogeheten foutkans (soundness error).
Eén ronde vragen is vaak niet genoeg: de foutkans kan bijvoorbeeld een derde of de helft zijn, veel te hoog om op te vertrouwen. De oplossing is herhaling. Je kunt sequentieel herhalen: de vraag steeds opnieuw stellen, wachtend op elk antwoord voor je de volgende vraag stelt. Dat werkt goed, maar kost tijd: bij honderd herhalingen zijn er honderd communicatierondes nodig. In veel toepassingen – zeker als er over een netwerk gecommuniceerd wordt, of als het bewijs uiteindelijk in één klap gecontroleerd moet worden – is dat onhandig.
Parallelle herhaling lost dat op door alle vragen in één keer te stellen. De controleur stuurt in één ronde bijvoorbeeld honderd (deels onafhankelijke) vragen tegelijk; de bewijzer moet in één keer honderd antwoorden teruggeven. Omdat de bewijzer alle antwoorden tegelijk moet vastleggen, kan hij niet meer per vraag zijn strategie aanpassen op basis van eerdere reacties van de controleur, zoals bij sequentiële herhaling wel enigszins het geval kan zijn.
Het probleem is dat dit intuïtieve voordeel wiskundig lastig te bewijzen is, vooral bij protocollen met twee onafhankelijke bewijzers die niet met elkaar mogen overleggen (two-prover games). Voor gewone kansrekening zou je verwachten dat de foutkans bij k parallelle herhalingen gewoon tot de k-de macht daalt, zoals bij het k keer achter elkaar gooien van een oneerlijke munt. Begin jaren negentig lieten onderzoekers echter tegenvoorbeelden zien: er zijn spellen waarbij de foutkans bij parallelle herhaling niet netjes exponentieel daalt, en soms zelfs nauwelijks kleiner wordt dan bij één enkele ronde. Dat was een onaangename verrassing voor een aanname die iedereen als vanzelfsprekend had beschouwd.
De doorbraak kwam met het werk van de Israëlische informaticus Ran Raz, die in 1998 bewees dat voor de belangrijke klasse van "two-prover one-round games" de foutkans bij parallelle herhaling wél exponentieel daalt in het aantal herhalingen — zij het met een minder scherpe (kleinere) exponent dan de simpele intuïtie zou suggereren. Dit resultaat staat sindsdien bekend als het Parallel Repetition Theorem. Latere onderzoekers, onder wie Thomas Holenstein en Anup Rao, vereenvoudigden het bewijs en vonden scherpere grenzen voor speciale gevallen, zoals zogeheten "projectiespellen".
Wat wil men ermee bereiken?
De kern van het doel is foutkans verkleinen zonder de communicatie onhandig groot te maken. Dat klinkt technisch, maar heeft grote praktische gevolgen op minstens drie terreinen.
Ten eerste: bewijssystemen en zero-knowledge. Bij zero-knowledge-bewijzen wil een partij aantonen dat ze een geheim kent (bijvoorbeeld een wachtwoord, of dat een berekening correct is uitgevoerd) zonder het geheim zelf prijs te geven. Zulke protocollen hebben vaak een niet te verwaarlozen kans dat een bedrieger toch slaagt. Parallelle herhaling maakt het mogelijk die kans in één communicatieronde tot een verwaarloosbaar niveau te drukken, wat protocollen sneller en praktischer maakt.
Ten tweede: de PCP-stelling en hardheid van benaderen. De Probabilistically Checkable Proofs (PCP)-stelling, een van de belangrijkste resultaten uit de theoretische informatica van de jaren negentig, zegt dat je een wiskundig bewijs zo kunt herschrijven dat een controleur het met hoge zekerheid kan checken door slechts een handjevol willekeurige plekken te lezen. Om deze controle betrouwbaar genoeg te maken, is herhaling nodig – en om dat efficiënt te doen, is parallelle herhaling essentieel. Deze machinerie ligt aan de basis van bewijzen dat bepaalde optimalisatieproblemen (zoals het zo goed mogelijk oplossen van bepaalde puzzels in de logica of grafentheorie) niet alleen moeilijk exact op te lossen zijn, maar zelfs moeilijk goed te benaderen.
Ten derde: compacte cryptografische argumenten. Moderne technieken om berekeningen compact te bewijzen — gebruikt in privacytechnologie en in blockchain-schaaloplossingen — bouwen voort op interactieve bewijssystemen die via herhaling en wiskundige transformaties worden omgezet in korte, snel controleerbare bewijzen. Een lage foutkans, efficiënt bereikt, is daarbij cruciaal voor zowel veiligheid als snelheid.
Voorbeelden uit de praktijk
Ran Raz, "A Parallel Repetition Theorem" (1998). Het startpunt van het vakgebied: het bewijs dat two-prover games via parallelle herhaling exponentieel betrouwbaarder worden, gepubliceerd in SIAM Journal on Computing na eerdere presentatie op de STOC-conferentie.
Håstads inapproximability-resultaten (rond 2001). De Zweedse informaticus Johan Håstad (KTH, Stockholm) gebruikte PCP-constructies met herhaling om te bewijzen dat bepaalde optimalisatieproblemen, zoals varianten van 3-SAT (een klassiek logisch beslissingsprobleem), zelfs met de beste mogelijke algoritmen niet beter dan een bepaalde nauwkeurigheid te benaderen zijn — tenzij P gelijk is aan NP.
Vereenvoudigde en scherpere bewijzen (2007-2008). Thomas Holenstein publiceerde een korter, toegankelijker bewijs van Raz' stelling; Anup Rao vond in 2008 scherpere, optimale foutmarges voor de belangrijke deelklasse van "projectiespellen", wat de theorie praktisch bruikbaarder maakte.
Kwantumversies van het probleem. Omdat kwantumfysica correlaties tussen twee bewijzers toestaat die klassiek onmogelijk zijn (verstrengeling), moest het hele vraagstuk opnieuw bekeken worden voor kwantumbewijzers. Onderzoekers als Julia Kempe, Thomas Vidick en Richard Cleve onderzochten in het afgelopen decennium onder welke voorwaarden parallelle herhaling ook werkt wanneer de "bedriegers" van kwantumverstrengeling gebruikmaken — relevant voor de veiligheid van kwantumcryptografie en zogeheten device-independent protocollen.
Toepassing in schaalbare blockchain-bewijzen. Bedrijven die zogeheten STARK-bewijzen bouwen (Scalable Transparent Arguments of Knowledge), zoals het Israëlische StarkWare, gebruiken protocollen die voortbouwen op PCP-achtige technieken en herhaalde, willekeurige controles om met hoge betrouwbaarheid en weinig communicatie te bewijzen dat een grote berekening correct is uitgevoerd — een directe praktische afgeleide van dezelfde onderliggende ideën.
Hoe ver is de techniek?
Parallelle herhaling is in de kern wiskunde, geen apparaat dat je "af" kunt bouwen — de vooruitgang zit in scherpere bewijzen en bredere toepasbaarheid, niet in engineering-mijlpalen. Voor de klassieke, niet-kwantum situatie is de hoofdstelling sinds Raz' werk stevig bewezen; latere verbeteringen verscherpten vooral de precieze foutmarges en vereenvoudigden de bewijstechniek.
Toch is het veld niet "af". Voor algemene spellen is de optimale snelheid waarmee de foutkans daalt nog niet volledig bekend, en dit hangt nauw samen met een van de grootste open problemen in de complexiteitstheorie: de Unique Games Conjecture, een nog onbewezen vermoeden dat, als het klopt, verstrekkende gevolgen zou hebben voor precies hoe goed duizenden optimalisatieproblemen wel of niet te benaderen zijn. Ook de kwantumversie van parallelle herhaling is nog volop in ontwikkeling: voor sommige typen kwantumspellen is bewezen dat parallelle herhaling werkt, voor andere ligt dat nog open of zijn de bekende grenzen minder scherp dan in de klassieke setting.
In de praktijk gebruiken ingenieurs die zero-knowledge- of STARK-systemen bouwen vaak niet rechtstreeks de meest algemene stelling, maar afgeleide, specifiek geoptimaliseerde technieken en heuristieken (zoals de Fiat-Shamir-transformatie) die in de praktijk goed werken, ook al zijn niet alle theoretische garanties daarvan even sterk als bij het oorspronkelijke Parallel Repetition Theorem. Dat gat tussen theoretische volledigheid en praktisch gebruik blijft onderwerp van onderzoek.
Wie werken eraan?
Het onderzoek naar parallelle herhaling speelt zich vooral af binnen de theoretische informatica, aan universiteiten en onderzoeksinstituten wereldwijd. Ran Raz, de grondlegger van de stelling, werkte lange tijd aan het Weizmann Institute of Science in Israël en is tegenwoordig verbonden aan Princeton University in de Verenigde Staten. Johan Håstad is hoogleraar aan het KTH Royal Institute of Technology in Zweden. Thomas Vidick, een van de drijvende krachten achter de kwantumversie van de theorie, is verbonden aan het California Institute of Technology (Caltech) en later het Weizmann Institute.
Belangrijke centra voor dit type onderzoek zijn onder meer het Weizmann Institute of Science (Israël), het Institute for Advanced Study en Princeton University (Verenigde Staten), en het Simons Institute for the Theory of Computing aan de University of California, Berkeley, dat regelmatig workshops en programma's rond complexiteitstheorie en PCP-onderzoek organiseert. Op de toepassingskant investeren bedrijven in de blockchain- en cryptografie-industrie, zoals het al genoemde StarkWare en andere ontwikkelaars van zero-knowledge-technologie, in ingenieurs die deze theoretische inzichten vertalen naar werkende, efficiënte protocollen.