I denne artikel vil jeg fortælle dig om DAG (Directed Acyclic Graph, rettet acyklisk graf) og dets anvendelse i distribuerede registre, og vi vil sammenligne det med blockchain.
DAG er ikke noget nyt i kryptovalutaernes verden. Du har måske hørt om det som en løsning på blockchainers skalerbarhedsproblemer. Men i dag vil vi ikke tale om skalerbarhed, men om hvad der gør kryptovalutaer særlige: decentralisering, fraværet af mellemmænd og modstandsdygtigheden over for censur.
Jeg vil også vise dig, at DAG faktisk er mere modstandsdygtig over for censur, og at der ikke er nogen mellemmænd for at få adgang til registret.
I de velkendte blockchains har brugerne ikke direkte adgang til selve registret. Når du ønsker at tilføje en transaktion til registret, er du nødt til at "anmode" blokproducenten (block producer, også kaldet "miner") om at gøre det. Det er minerne, der beslutter, hvilken transaktion der skal tilføjes til den næste blok, og hvilken der skal ignoreres. Det er minerne, der har eksklusiv adgang til blokkene og retten til at beslutte, hvis transaktion der skal accepteres for at blive tilføjet til registret.
Minerne er de mellemmænd, der står mellem dig og det distribuerede register.
I praksis kontrollerer et lille antal minedrift-pools kollektivt mere end halvdelen af netværkets regnekraft. For Bitcoin er det fire pools, og for Ethereum er det to. I tilfælde af sammensværgelse kan de blokere for enhver transaktion, de ønsker.
I de seneste år er der blevet foreslået mange varianter af blockchains, der adskiller sig i principperne for valg af blokproducenter. Men blokproducenterne forsvinder ikke, de "står stadig ved bommen": hver transaktion skal gå gennem blokproducenten, og hvis han ikke accepterer den, eksisterer transaktionen faktisk ikke.
Dette er et uundgåeligt problem med blockchain. Og hvis vi ønsker at løse det, må vi radikalt ændre designet og helt fjerne blokke og blokproducenter. I stedet for at opbygge en kæde af blokke, vil vi forbinde selve transaktionerne ved at inkludere hash-ene af flere tidligere transaktioner i hver transaktion. Resultatet vil være en struktur, der i matematik kaldes en rettet acyklisk graf – DAG.
Nu har alle direkte adgang til registret uden mellemled. Når du ønsker at tilføje en transaktion til registret, tilføjer du bare den. Vælg flere forældrepræstationer, tilføj dine oplysninger, underskriv, og send din transaktion ud i netværket. Klar. Der er ingen, der kan forhindre dig i at gøre dette, så din transaktion er allerede i registret.
Dette er den mest decentrale, mest modstandsdygtige metode til at tilføje transaktioner til registret uden mellemled. For hver enkelt kan tilføje sine transaktioner til registret uden at spørge om tilladelse fra nogen.
DAG kan betragtes som den tredje fase i udviklingen af registre. Først var der centraliserede registre, hvor én part kontrollerede adgangen til dem. Så kom blockchain, hvor der var flere controllere, der skrev transaktioner ind i registret. Og endelig, i DAG, findes der slet ingen controllere, brugerne tilføjer deres transaktioner direkte.
Nu hvor vi har sådan en frihed, bør det ikke føre til kaos. Vi skal have enighed om tilstanden af registret. Og denne enighed eller konsensus betyder normalt enighed om to ting:
- Hvad skete der?
- I hvilken rækkefølge fandt det sted?
På det første spørgsmål kan vi nemt svare: så snart en korrekt lavet transaktion er blevet tilføjet til registret, fandt den sted. Og punktum. Oplysninger om dette kan nå frem til alle deltagere på forskellige tidspunkter, men til sidst vil alle noder modtage denne transaktion og finde ud af, at den har fundet sted.
Hvis det havde været en blockchain, ville minerne have bestemte, hvad der skete. Alt, hvad en miner beslutter at inkludere i blokken, bliver til virkelighed. Alt, hvad han ikke inkluderer i blokken, sker ikke.
I blockchain beslutter minerne også den anden konsensusproblematik: rækkefølgen. De har tilladelse til at rækkefølge transaktioner inden for blokken, som de vil.
Hvordan bestemmer man rækkefølgen af transaktioner i DAG?
Kun grafen er rettet, har vi allerede en vis orden. Hver transaktion refererer til en eller flere tidligere, parent-transaktioner. Forældre henviser igen til deres forældre, og så videre. Forældre optræder åbenlyst før deres dattertransaktioner. Hvis en transaktion kan nås gennem "parent-child"-links, så kender vi præcist rækkefølgen mellem transaktionerne i denne kæde.
Men rækkefølgen mellem transaktionerne kan ikke altid bestemmes kun ud fra grafens struktur. For eksempel, når to transaktioner ligger på parallelle grene af grafen.
For at opklare tvetydighed i sådanne tilfælde, stoler vi på såkaldte rækkefølgeudbydere. Vi kalder dem også "vidner". Det er almindelige brugere, hvis opgave er konstant at sende transaktioner til nettet i den rigtige rækkefølge, så hver af deres tidligere transaktioner kan nås gennem "parent-child"-links. Rækkefølgeudbydere – betroede brugere, og hele netværket stoler på, at de ikke vil overtræde denne regel. For at have en rationel tillid til dem, kræver vi, at hver rækkefølgeudbyder er en kendt (ikke-anonym) person eller organisation, der har noget at tabe, hvis de overtræder reglerne, såsom omdømme eller en forretning baseret på tillid.
Rækkefølgeudbydere vælges af brugerne, og hver bruger inkluderer en liste over sine betroede udbydere i hver transaktion, de sender til netværket. Denne liste består af 12 udbydere. Det er et forholdsvis lille antal, så en person kan verificere identiteten og omdømmet for hver af dem, og tilstrækkeligt til, at netværket kan fortsætte med at fungere i tilfælde af uundgåelige problemer med et mindretal af rækkefølgeudbyderne.
Denne liste over udbydere varierer fra bruger til bruger, men listerne for tilstødende transaktioner kan maksimalt afvige med én udbyder.
Nu hvor vi har rækkefølgeudbydere, kan vi isolere deres transaktioner i DAG og ordne alle andre transaktioner omkring den rækkefølge, de skaber. Der er mulighed for at skabe en sådan algoritme (se for for tekniske detaljer).
Men orden i hele netværket kan ikke bestemmes øjeblikkeligt; vi har brug for tid til, at ordensudbyderne sender et tilstrækkeligt antal af deres transaktioner for at bekræfte den endelige rækkefølge af de tidligere transaktioner.
Og eftersom rækkefølgen kun bestemmes af ordensudbydernes positioner i DAG, vil alle noder i netværket før eller siden modtage alle transaktioner og nå frem til den samme konklusion vedrørende rækkefølgen af transaktioner.
Så vi har enighed om, hvad der er sket: enhver transaktion, der kommer ind i DAG, er sket. Vi har også enighed om rækkefølgen af hændelserne: dette er enten synligt fra de relationelle forbindelser mellem transaktionerne eller kan udledes fra rækkefølgen af transaktioner sendt af ordensudbyderne. Det betyder, at vi har konsensus.
Denne form for konsensus har vi i Obyte. På trods af at adgangen til Obyte-registret er fuldstændig decentraliseret, er konsensus vedrørende rækkefølgen af transaktioner stadig centraliseret, da 10 ud af 12 udbydere kontrolleres af skaberen (Anton Churyumov), og kun to af dem er uafhængige. Vi søger kandidater, der ønsker at blive en af de uafhængige ordensudbydere for at hjælpe os med at decentralisere fastsættelsen af rækkefølgen i registret.
For nylig er der dukket op en tredje uafhængig kandidat, der ønsker at etablere og opretholde en ordensudbydernode – Universitetet i Nikosia.
Hvordan kontrollerer vi dobbeltudgifter (double-spends)?
Ifølge reglerne, når to transaktioner, der bruger den samme mønt, opdages, vinder den transaktion, der kom først i den endelige rækkefølge af alle transaktioner. Den anden bliver ugyldiggjort af konsensusalgoritmen.
Hvis det er muligt at fastslå rækkefølgen mellem to transaktioner, der bruger samme mønt (via forælder-barn relationer), vil alle noder straks afvise et sådant forsøg på dobbeltudgift.
I tilfælde af at rækkefølgen ikke er synlig fra forældrenes forbindelser mellem de to transaktioner, accepteres begge i registret, og vi bliver nødt til at vente på konsensus og fastlæggelse af rækkefølgen mellem dem ved hjælp af ordensudbyderne. Da vinder den tidligere transaktion, og den anden bliver ikke-valid.
Selvom den anden transaktion bliver ugyldig, forbliver den stadig i registret, fordi den allerede har efterfølgende transaktioner, der refererer til den, som ikke har overtrådt noget og ikke vidste, at denne transaktion en dag ville blive ugyldig. Ellers skulle vi fjerne forælderen fra de gode efterfølgende transaktioner, hvilket ville bryde det grundlæggende princip i netværket - enhver gyldig transaktion accepteres i registret.
Dette er en meget vigtig regel, der gør hele systemet modstandsdygtigt over for forsøg på censur.
Lad os forestille os, at alle ordreudbydere indgår en sammensværgelse i et forsøg på at 'censurere' en bestemt transaktion. De kan ignorere den og aldrig vælge den som 'forælder' til deres transaktioner, men det er ikke nok; denne transaktion kan stadig blive inkluderet indirekte som forælder til en anden transaktion sendt af en hvilken som helst bruger i netværket, som ikke deltager i sammensværgelsen. Over tid vil en sådan transaktion få flere og flere børn, børnebørn og oldebørn fra almindelige brugere, der vokser som en snebold, og alle de aftalte ordreudbydere vil også være nødt til at ignorere disse transaktioner. Til sidst vil de være nødt til at censurere hele netværket, hvilket svarer til sabotage.
Dermed forbliver DAG modstandsdygtig over for censur, selvom der er en sammensværgelse blandt ordreudbydere, hvilket gør det mere modstandsdygtigt over for censur end blockchain, hvor vi intet kan gøre, hvis minepersoner beslutter ikke at inkludere nogen af transaktionerne. Og dette følger af den primære egenskab ved DAG: deltagelse i registret er helt uafhængig og uden mellemmænd, og transaktioner er irreversible.
Kilde: habr.com
