What is Cuckoo Cycle?

Cuckoo Cycle is een grafentheoretisch proof-of-work-algoritme dat fundamenteel verschilt van traditionele hash-gebaseerde mining doordat het van miners vereist dat ze cycli van een bepaalde lengte vinden in een grote bipartiete graaf. Het algoritme is ontworpen door John Tromp en is gebaseerd op de moeilijkheid van het detecteren van cycli in cuckoo-hashtabellen — de datastructuur waaraan het zijn naam ontleent. Bij elke miningpoging wordt een bipartiete graaf gegenereerd uit een nonce-afhankelijke seed met behulp van een hashfunctie (meestal SipHash), die randen creëert tussen twee verzamelingen knooppunten. De miner moet vervolgens een cyclus van exact 42 randen vinden (in de standaardparametrisering) binnen deze graaf, wat uitgebreide verkenning vereist van de graafstructuur die in het geheugen is opgeslagen.

De meest onderscheidende eigenschap van Cuckoo Cycle is dat het geheugengebonden is in plaats van rekengebonden. Terwijl traditionele hash-gebaseerde algoritmen zoals SHA-256 kunnen worden versneld door snellere rekenkundige circuits te bouwen, wordt de prestatie van Cuckoo Cycle voornamelijk beperkt door geheugenbandbreedte en -capaciteit. Het algoritme vereist het opslaan en doorlopen van een grote graaf die doorgaans meerdere gigabytes RAM in beslag neemt, waardoor het inherent resistent is tegen ASIC-optimalisatie, aangezien geheugenchips niet dramatisch sneller of goedkoper gemaakt kunnen worden dan standaard-DRAM. De verificatie van een oplossing is extreem snel — simpelweg bevestigen dat 42 randen een geldige cyclus vormen — wat een sterk asymmetrisch bewijs creëert waarbij het vinden van de oplossing moeilijk is maar het controleren ervan triviaal. Deze geheugenintensieve eigenschap maakt Cuckoo Cycle een van de meest egalitaire proof-of-work-schema's, aangezien het prestatieverschil tussen gespecialiseerde hardware en consumentencomputers veel kleiner is dan bij rekengebonden algoritmen.

Cuckoo Cycle verwierf zijn meest prominente adoptie via de Grin-cryptocurrency, die in januari 2019 werd gelanceerd als implementatie van het MimbleWimble-privacyprotocol. Grin gebruikte aanvankelijk twee varianten van Cuckoo Cycle: Cuckaroo (ontworpen om ASIC-resistent te zijn en regelmatig te evolueren) en Cuckatoo (ontworpen om ASIC-vriendelijk te zijn voor langetermijnmining). Aeternity (AE) implementeerde ook een variant van Cuckoo Cycle voor het proof-of-work-component. Het algoritme werd door de cryptocurrency-gemeenschap geprezen om zijn elegante wiskundige basis en daadwerkelijke geheugenintensiviteit, in tegenstelling tot veel algoritmen die ASIC-resistentie claimden zonder dit werkelijk te bereiken. Het werk van John Tromp aan Cuckoo Cycle is uitgebreid geciteerd in academische literatuur over proof-of-work-systemen, en de grafentheoretische benadering beïnvloedde vervolgonderzoek naar alternatieve miningparadigma's die verder gaan dan eenvoudige hashberekening.