Gerichte acyclische graaf: de wiskunde achter blockchain-alternatieven en AI-pijplijnen
Stel je een stamboom voor. Iedereen heeft ouders, grootouders en overgrootouders, en de pijlen van afstamming wijzen altijd één kant op: van ouder naar kind. Je kunt in een stamboom nooit bij jezelf uitkomen door de pijlen te volgen — je kunt niet je eigen overgrootvader zijn. Dat is in essentie wat wiskundigen en informatici een gerichte acyclische graaf noemen, vaak afgekort als DAG (van het Engelse directed acyclic graph).
Een DAG is een netwerk van punten die met pijlen aan elkaar zijn verbonden, waarbij die pijlen altijd één richting hebben en er nooit een lus ontstaat die je terugbrengt naar je startpunt. Dat klinkt abstract, maar het is een van de meest gebruikte structuren in de digitale wereld: van de manier waarop Git de geschiedenis van software bijhoudt tot nieuwe soorten cryptovaluta die zonder mijnwerkers werken, en van planningssystemen bij grote techbedrijven tot de rekenschema's achter kunstmatige intelligentie.
Wat is het precies?
In de wiskundige tak van de grafentheorie bestaat een graaf uit knooppunten (ook wel nodes) en verbindingen daartussen, edges genoemd. Bij een gewone graaf kunnen die verbindingen alle kanten op lopen, zonder richting. Een gerichte graaf voegt daar een pijlpunt aan toe: de verbinding loopt van A naar B, en niet automatisch ook van B naar A.
Het woord acyclisch betekent "zonder cyclus" of "zonder kringloop". In een acyclische graaf kun je, door de pijlen te volgen, nooit terugkomen bij een knooppunt waar je al was. Dat lijkt een detail, maar het heeft een belangrijk gevolg: elke DAG kan in een volgorde worden gezet waarin elk knooppunt pas verschijnt nadat alle knooppunten waarvan het afhankelijk is, al aan de beurt zijn geweest. Informatici noemen dit een topologische ordening.
Dat is precies waarom DAG's zo bruikbaar zijn: ze leggen afhankelijkheden vast. Een taak B die pas kan beginnen nadat taak A is afgerond, wordt weergegeven als een pijl van A naar B. Omdat er geen kringlopen zijn, kan een computer altijd een geldige uitvoeringsvolgorde berekenen — en kan hij bovendien zien welke taken géén onderlinge afhankelijkheid hebben en dus tegelijk (parallel) mogen draaien.
Wat wil men ermee bereiken?
De kernbelofte van een DAG is orde scheppen in complexiteit. Grote softwaresystemen, dataverwerkingsprocessen en zelfs financiële transacties bestaan uit talloze stappen die van elkaar afhangen. Een DAG maakt die afhankelijkheden expliciet en controleerbaar, zodat een computer automatisch kan bepalen wat wanneer moet gebeuren, wat veilig tegelijk kan, en wat fout gaat als een stap ontbreekt of dubbel wordt uitgevoerd.
In de wereld van digitale valuta en gedistribueerde grootboeken (technologie waarbij meerdere computers gezamenlijk een gedeelde administratie bijhouden zonder centrale beheerder) wordt de DAG-structuur om een andere reden aantrekkelijk gevonden: als alternatief voor de blockchain. Een traditionele blockchain is in feite een DAG met een heel strikte, lineaire vorm — één lange ketting van blokken. Onderzoekers en bedrijven vroegen zich af of een lossere, vertakte DAG-structuur sneller en goedkoper kan werken, omdat transacties niet allemaal in precies dezelfde volgorde in blokken hoeven te worden geperst. Het doel is dan vooral: meer transacties per seconde verwerken, transactiekosten verlagen of zelfs helemaal wegnemen, en systemen beter laten opschalen naarmate meer gebruikers meedoen.
In kunstmatige intelligentie en dataverwerking dient de DAG weer een ander doel: reproduceerbaarheid en overzicht. Een rekenproces of dataverwerkingspijplijn die als DAG is vastgelegd, kan exact worden herhaald, gecontroleerd en opnieuw uitgevoerd vanaf het punt waar iets misging, zonder de hele keten opnieuw te hoeven doorlopen.
Voorbeelden uit de praktijk
Git — Het versiebeheersysteem dat Linus Torvalds in 2005 schreef voor de ontwikkeling van de Linux-kernel, legt elke wijziging in broncode vast als een "commit" die verwijst naar zijn voorganger(s). Die hele geschiedenis vormt wiskundig gezien een DAG: vertakkingen (branches) en samenvoegingen (merges) zijn mogelijk, maar je kunt nooit in een lus terechtkomen.
IOTA — Deze cryptovaluta, opgericht rond 2015 door onder anderen David Sønstebø en Dominik Schiener, gebruikt een DAG-structuur die de "Tangle" wordt genoemd, in plaats van een klassieke blockchain. Het idee: elke nieuwe transactie moet twee eerdere transacties bevestigen, waardoor er in theorie geen aparte mijnwerkers nodig zijn en transacties gratis kunnen zijn. In de praktijk leunde het netwerk jarenlang op een centraal controlepunt, de "Coordinator", om fraude te voorkomen — precies het soort centralisatie dat gedistribueerde systemen juist willen vermijden. Het project "Coordicide" moet dat controlepunt overbodig maken; de overgang naar een volledig decentrale versie (aangeduid als IOTA 2.0) is een meerjarig traject dat rond het midden van de jaren twintig nog altijd in ontwikkeling was.
Hedera Hashgraph — Sinds de mainnet-lancering in 2019 biedt dit platform, gebaseerd op onderzoek van informaticus Leemon Baird, een DAG-achtige structuur van "gebeurtenissen" (events) die via een roddel-achtig verspreidingsmechanisme ("gossip about gossip") tot consensus komen. Het netwerk wordt bestuurd door een raad van grote, uiteenlopende organisaties, waaronder techbedrijven en universiteiten, in plaats van door mijnwerkers.
Apache Airflow — Dit open source-hulpmiddel, oorspronkelijk gebouwd bij Airbnb en sinds 2015 publiek beschikbaar, laat dataverwerkers hun pijplijnen letterlijk als DAG's definiëren: taak B start pas als taak A klaar is, en de software bewaakt automatisch die volgorde. Het groeide uit tot een veelgebruikt onderdeel van de Apache Software Foundation en wordt wereldwijd ingezet om data-analyseprocessen te plannen.
Rekengrafieken in machine learning — Softwarebibliotheken zoals Google's TensorFlow (uitgebracht in 2015) leggen de opeenvolgende wiskundige bewerkingen van een neuraal netwerk vast als een DAG: elke laag van het netwerk hangt af van de uitkomst van de vorige. Dat maakt het mogelijk om berekeningen efficiënt te verdelen over meerdere rekenchips.
Hoe ver is de techniek?
Het is belangrijk twee dingen uit elkaar te houden. Als wiskundig concept is de gerichte acyclische graaf allesbehalve nieuw of experimenteel: grafentheorie bestaat al meer dan een eeuw, en toepassingen zoals Git en planningssoftware zijn volwassen, stabiele technologie die dagelijks door miljoenen mensen wordt gebruikt.
Anders ligt het bij DAG's als vervanging voor de blockchain in cryptovaluta en gedistribueerde grootboeken. Dat onderzoeksveld is jonger, minder uitgekristalliseerd en heeft nog geen consensus opgeleverd over de beste aanpak. Projecten als IOTA hebben laten zien dat volledige decentralisatie van een DAG-gebaseerd netwerk technisch lastig is: het weglaten van een centrale coördinator zonder de veiligheid tegen fraude te verliezen, kostte veel meer jaren onderzoek dan aanvankelijk voorzien. Hedera Hashgraph koos bewust voor een andere aanpak, met een vaste groep bestuurders in plaats van volledige openheid, wat door sommigen als compromis en door anderen als beperking van decentralisatie wordt gezien.
Op het gebied van dataverwerking en kunstmatige intelligentie is de DAG-aanpak inmiddels ingeburgerd en weinig omstreden; de belangrijkste ontwikkelingen daar gaan over schaal en gebruiksgemak, niet over de onderliggende structuur zelf. Kortom: de wiskunde staat als een huis, de toepassing in decentrale financiële systemen is nog volop in beweging.
Wie werken eraan?
De IOTA Foundation, een in Duitsland gevestigde non-profitorganisatie, ontwikkelt de Tangle-technologie verder. Hedera Hashgraph LLC, met hoofdkantoor in de Verenigde Staten, beheert het Hedera-netwerk samen met de Hedera Governing Council, waarin uiteenlopende internationale bedrijven en instellingen zitten. De Apache Software Foundation begeleidt open source-projecten zoals Airflow, met bijdragen van ontwikkelaars wereldwijd. Grote technologiebedrijven als Google (met TensorFlow) en Microsoft investeren in DAG-gebaseerde rekengrafieken voor kunstmatige intelligentie. Daarnaast houden universitaire onderzoeksgroepen in onder meer de Verenigde Staten en Europa zich bezig met de theoretische grondslagen van gedistribueerde consensus op basis van DAG-structuren, een vakgebied dat raakt aan cryptografie en verdeelde systemen.