I denne artikel vil jeg fortælle dig om DAG (Directed Acyclic Graph) og dens anvendelse i distribuerede hovedbøger, 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å problemer med blockchain-skalerbarhed. Men i dag vil vi ikke tale om skalerbarhed, men om hvad der gør kryptovalutaer anderledes end alt andet: decentralisering, mangel på mellemled og censurmodstand.
Jeg vil også vise dig, at DAG faktisk er mere censurresistent, og der er ingen mellemled til at få adgang til hovedbogen.
I de blockchains, vi kender, har brugerne ikke direkte adgang til selve hovedbogen. Når du vil tilføje en transaktion til hovedbogen, skal du "bede" blokproducenten (alias "miner") om at gøre det. Det er minearbejderne, der bestemmer, hvilken transaktion der skal tilføjes til den næste blok, og hvilken der ikke. Det er minearbejderne, der har eksklusiv adgang til blokke og retten til at bestemme, hvis transaktion vil blive accepteret til optagelse i hovedbogen.
Minearbejdere er mellemmænd, der står mellem dig og den distribuerede hovedbog.
I praksis kontrollerer normalt et lille antal minearbejderpuljer tilsammen mere end halvdelen af netværkets computerkraft. For Bitcoin er disse fire puljer, for Ethereum - to. Hvis de samarbejder, kan de blokere alle transaktioner, de ønsker.
I løbet af de sidste par år er der blevet foreslået mange variationer af blockchains, der adskiller sig i principperne for at vælge blokproducenter. Men blokproducenterne selv går ingen vegne, de står stadig "ved barrieren": hver transaktion skal gå gennem blokproducenten, og hvis han ikke accepterer det, så eksisterer transaktionen i virkeligheden ikke.
Dette er et uundgåeligt problem med blockchain. Og hvis vi vil løse det, er vi nødt til at ændre designet radikalt og helt af med blokke og blokproducenter. Og i stedet for at bygge en kæde af blokke, forbinder vi selve transaktionerne, inklusive hasherne fra flere tidligere i hver transaktion. Som et resultat får vi en struktur kendt i matematik som en rettet acyklisk graf - DAG.
Nu har alle direkte adgang til registreringsdatabasen, uden mellemled. Når du vil tilføje en transaktion til hovedbogen, tilføjer du den blot. Du vælger flere overordnede transaktioner, tilføjer dine data, underskriver og sender din transaktion til peers på netværket. Parat. Der er ingen til at forhindre dig i at gøre dette, så din transaktion er allerede på hovedbogen.
Dette er den mest decentraliserede, mest censursikre måde at tilføje transaktioner til hovedbogen uden mellemled. Fordi alle blot tilføjer deres transaktioner til registreringsdatabasen uden at spørge nogen om tilladelse.
DAG'er kan betragtes som den tredje fase i udviklingen af registre. Først var der centraliserede registre, hvor den ene part kontrollerede adgangen til dem. Så kom blockchains, som allerede havde flere controllere, som registrerede transaktioner i hovedbogen. Og endelig er der slet ingen controllere i DAG; brugere tilføjer deres transaktioner direkte.
Nu hvor vi har denne frihed, burde det ikke føre til kaos. Vi skal have enighed om registrets tilstand. Og denne aftale eller konsensus betyder normalt enighed om to ting:
- Hvad skete der?
- I hvilken rækkefølge skete dette?
Vi kan nemt svare på det første spørgsmål: Når en korrekt oprettet transaktion er blevet tilføjet til hovedbogen, er den sket. Og punktum. Information om dette kan nå alle deltagere på forskellige tidspunkter, men i sidste ende vil alle noder modtage denne transaktion og vide, at det skete.
Hvis det var en blockchain, ville minearbejdere bestemme, hvad der sker. Uanset hvad minearbejderen beslutter sig for at inkludere i en blok er det, der sker. Alt, hvad han ikke har med i blokken, sker ikke.
I blockchains løser minearbejdere også et andet konsensusproblem: orden. De har lov til at bestille transaktionerne inden for blokken, som de ønsker.
Hvordan bestemmer man rækkefølgen af transaktioner i en DAG?
Bare fordi vores graf er rettet, har vi allerede en vis orden. Hver transaktion refererer til en eller flere tidligere overordnede transaktioner. Forældre henviser til gengæld til deres forældre og så videre. Forældre optræder naturligvis før børnetransaktioner. Hvis nogen af transaktionerne kan nås ved overgange mellem overordnede og underordnede links, kender vi nøjagtig rækkefølgen mellem transaktionerne i den pågældende transaktionskæde.
Men rækkefølgen mellem transaktioner kan ikke altid bestemmes ud fra formen af grafen alene. For eksempel når to transaktioner ligger på parallelle grene af grafen.
For at løse uklarheder i sådanne tilfælde er vi afhængige af såkaldte ordreudbydere. Vi kalder dem også "vidner". Det er almindelige brugere, hvis opgave er konstant at sende transaktioner til netværket på en ordnet måde, dvs. så hver af deres tidligere transaktioner kan nås ved overgange langs forældre-barn-links. Ordreudbydere er betroede brugere, og hele netværket er afhængigt af, at de ikke overtræder denne regel. For at rationelt stole på dem, kræver vi, at hver ordreudbyder er en kendt (ikke-anonym) person eller organisation og har noget at tabe, hvis den bryder reglerne, såsom omdømme eller forretning baseret på tillid.
Ordreudbydere vælges af brugerne, og hver bruger inkluderer en liste over sine betroede udbydere i hver transaktion, den sender til netværket. Denne liste består af 12 udbydere. Dette er et lille nok tal til, at en person kan bekræfte identiteten og omdømmet for hver af dem, og nok til at sikre, at netværket fortsætter med at fungere i tilfælde af uundgåelige problemer med et mindretal af ordreudbydere.
Denne liste over udbydere varierer fra bruger til bruger, men listerne over nabotransaktioner kan variere med op til én udbyder.
Nu hvor vi har ordreudbydere, kan vi isolere deres transaktioner i en DAG og bestille alle andre transaktioner omkring den ordre, de har oprettet. Det er muligt at oprette en sådan algoritme (se. for tekniske detaljer).
Men rækkefølgen af hele netværket kan ikke bestemmes øjeblikkeligt; vi har brug for tid for ordreudbyderne til at sende et tilstrækkeligt antal af deres transaktioner til at verificere den endelige rækkefølge af tidligere transaktioner.
Og da rækkefølgen kun bestemmes af positionerne for udbydernes transaktioner i DAG, vil alle noder på netværket før eller siden modtage alle transaktionerne og komme til den samme konklusion med hensyn til rækkefølgen af transaktionerne.
Så vi er enige om, hvad vi anser for at være sket: enhver transaktion, der ender i DAG, er sket. Vi har også enighed om rækkefølgen af begivenheder: dette fremgår enten af transaktionsrelationerne eller udledes af rækkefølgen af transaktioner sendt af ordreudbydere. Så vi har en konsensus.
Vi har denne version af konsensus i Obyte. Selvom adgangen til Obyte-reskontroen er fuldstændig decentraliseret, er konsensus om rækkefølgen af transaktioner stadig centraliseret pga. 10 ud af 12 udbydere kontrolleres af skaberen (Anton Churyumov), og kun to af dem er uafhængige. Vi søger kandidater, der er villige til at blive en af de uafhængige ordreudbydere til at hjælpe os med at decentralisere bestillingen af hovedbogen.
For nylig er en tredje uafhængig kandidat dukket op villig til at installere og vedligeholde en ordreudbyderknude - University of Nicosia.
Hvordan kontrollerer vi nu dobbeltudgifter?
Ifølge reglerne, hvis to transaktioner bliver fundet, der bruger den samme mønt, vinder den transaktion, der kommer først i den endelige rækkefølge af alle transaktioner. Den anden er ugyldiggjort af konsensusalgoritmen.
Hvis det er muligt at etablere orden mellem to transaktioner, der bruger den samme mønt (gennem forældre-barn-forbindelser), så afviser alle noder straks et sådant forsøg på at fordoble forbruget.
Hvis ordren ikke er synlig fra de overordnede relationer mellem to sådanne transaktioner, accepteres de begge i hovedbogen, og vi bliver nødt til at vente på konsensus og etablering af ordren mellem dem ved hjælp af ordreudbyderne. Så vil den tidligere transaktion vinde, og den anden bliver ugyldig.
Selvom den anden transaktion bliver ugyldig, forbliver den stadig i registret, fordi den allerede har efterfølgende transaktioner, der refererer til den, som ikke overtrådte noget og ikke vidste, at denne transaktion ville blive ugyldig i fremtiden. Ellers ville vi være nødt til at fjerne forælderen til gode efterfølgende transaktioner, hvilket ville være i strid med netværkets hovedprincip - enhver korrekt transaktion accepteres i hovedbogen.
Dette er en meget vigtig regel, der gør det muligt for hele systemet at være modstandsdygtigt over for censurforsøg.
Lad os forestille os, at alle ordreudbydere samarbejder i et forsøg på at "censurere" en specifik transaktion. De kan ignorere det og aldrig vælge det som "forælder" for deres transaktioner, men det er ikke nok, transaktionen kan stadig inkluderes indirekte som forælder til en anden transaktion udstedt af enhver bruger på netværket, som ikke samarbejder. Over tid vil en sådan transaktion modtage flere og flere børn, børnebørn og oldebørn fra almindelige brugere, der vokser som en snebold, og alle aftalte ordreudbydere bliver også nødt til at ignorere disse transaktioner. Til sidst bliver de nødt til at censurere hele netværket, hvilket er ensbetydende med sabotage.
På denne måde forbliver DAG censur-resistent, selvom der er et samarbejde mellem ordreudbydere, og overgår derved den censur-resistente blockchain, hvor vi ikke kan gøre noget, hvis minearbejderne beslutter sig for ikke at inkludere nogen af transaktionerne. Og dette følger af DAG's hovedegenskab: deltagelse i registret er fuldstændig uafhængig og uden mellemled, og transaktioner er irreversible.
Kilde: www.habr.com