V tomto článku vám povím o DAG (Directed Acyclic Graph, orientovaný acyklický graf) a jeho aplikaci v distribuovaných registrech a porovnáme ho s blockchainem.
DAG není nic nového ve světě kryptoměn. Možná jste o něm slyšeli jako o řešení problémů s škálovatelností blockchainů. Dnes však nebudeme mluvit o škálovatelnosti, ale o tom, co dělá kryptoměny odlišnými od všeho ostatního: decentralizace, absence zprostředkovatelů a odolnost vůči cenzuře.
Také vám ukážu, že DAG je ve skutečnosti více odolný vůči cenzuře a postrádá zprostředkovatele pro přístup k registru.
V běžných blockchainech nemají uživatelé přímý přístup k samotnému registru. Když chcete přidat transakci do registru, musíte "požádat" výrobce bloků (block producer, také známého jako "miner"). Právě minři rozhodují, kterou transakci přidat do dalšího bloku a kterou nikoli. Právě minři mají exkluzivní přístup k blokům a právo rozhodnout, čí transakci přijmou pro přidání do registru.
Minři jsou zprostředkovatelé, kteří stojí mezi vámi a distribuovaným registrem.
V praxi obvykle malé množství poolů minerů kolektivně kontroluje více než polovinu výpočetních kapacit sítě. Pro Bitcoin jsou to čtyři pooly, pro Ethereum dva. V případě jejich spiknutí mohou zablokovat jakékoli transakce, jaké chtějí.
V posledních několika letech bylo navrženo mnoho variant blockchainů lišících se v principech výběru výrobců bloků. Ale výrobci bloků nikam neodcházejí, stále "stojí na závorách": každá transakce musí projít přes výrobce bloků, a pokud ji nepřijme, transakce vlastně neexistuje.
To je nevyhnutelný problém u blockchainu. A pokud chceme tento problém vyřešit, musíme radikálně změnit design a zcela se zbavit bloků a výrobců bloků. Místo toho, abychom budovali řetězec bloků, budeme propojení transakcí, přičemž do každé transakce zahrneme hash několika předchozích. V důsledku toho získáme strukturu známou v matematice jako orientovaný acyklický graf – DAG.
Nyní má každý přímý přístup do registru, bez prostředníků. Když chcete přidat transakci do registru – jednoduše ji přidáte. Vyberete několik nadřazených transakcí, přidáte své údaje, podepíšete a odešlete svou transakci přímo do sítě. Hotovo. Nikdo vám nemůže bránit to udělat, takže vaše transakce je již v registru.
Jedná se o nejvíce decentralizovaný, nejneotřesitelnější způsob, jak přidávat transakce do registru bez prostředníků. Protože kdokoliv chce, může jednoduše přidat své transakce do registru, aniž by se ptal na povolení kohokoliv.
DAG lze považovat za třetí fázi evoluce registrů. Nejprve existovaly centralizované registry, kde jedna strana kontrolovala přístup k nim. Poté přišly blockchainy, kde již bylo několik kontrolorů, kteří zapisovali transakce do registru. A nakonec, v DAG neexistují žádní kontrolory, uživatelé přidávají své transakce přímo.
Nyní, když máme takovou svobodu, by to nemělo vést k chaosu. Musíme mít shodu o stavu registru. A tato shoda, nebo konsensus, obvykle znamená shodu o dvou věcech:
- Co se stalo?
- V jakém pořadí k tomu došlo?
Na první otázku můžeme snadno odpovědět: jakmile byla správně vytvořená transakce přidána do registru, stala se. A tečka. Informace o tom mohou dospět ke všem účastníkům v různé době, ale nakonec všechny uzly obdrží tuto transakci a dozvědí se, že k tomu došlo.
Kdyby to byl blockchain, těžaři by rozhodovali, co se děje. Všechno, co se těžař rozhodne zahrnout do bloku – to se děje. Všechno, co nezahrne do bloku – to se neděje.
V blockchainu těžaři také rozhodují o druhém problému konsensu: pořadí. Mají povoleno uspořádávat transakce uvnitř bloku jakkoli chtějí.
Jak tedy určit pořadí transakcí v DAG?
Jelikož máme orientovaný graf, již máme určité uspořádání. Každá transakce odkazuje na jednu nebo více předchozích, rodičovských transakcí. Rodiče zase odkazují na své rodiče a tak dále. Rodiče se zjevně objevují před dceřinými transakcemi. Pokud jakoukoli transakci lze dosáhnout pomocí odkazů „rodič-dítě“, přesně víme pořadí mezi transakcemi v tomto řetězci transakcí.
Ale pořadí mezi transakcemi nelze vždy určit pouze z tvaru grafu. Například když leží dvě transakce na paralelních větvích grafu.
Abychom vyřešili nejednoznačnost v takových případech, spoléháme na tzv. poskytovatele pořadí. Také je nazýváme „svědky“. To jsou běžní uživatelé, jejichž úkolem je neustále odesílat transakce do sítě v souladu s pořadím, t.j. tak, aby každá jejich předchozí transakce mohla být dosažena pomocí odkazů „rodič-dítě“. Poskytovatelé pořadí – důvěryhodní uživatelé, a celá síť se spoléhá na to, že neporuší toto pravidlo. Abychom rozumně jim důvěřovali, požadujeme, aby každý poskytovatel pořadí byl známou (neanonymní) osobou nebo organizací a měl něco, co může ztratit v případě, že poruší pravidla, například reputaci nebo podnik založený na důvěře.
Poskytovatelé pořadí jsou vybíráni uživateli a každý uživatel zahrnuje seznam svých důvěryhodných poskytovatelů do každé transakce, kterou odesílá do sítě. Tento seznam se skládá z 12 poskytovatelů. To je poměrně malé číslo, aby si člověk mohl ověřit identity a reputaci každého z nich, a dostatečné k tomu, aby síť mohla pokračovat v provozu v případě nevyhnutelných problémů s menšinou poskytovatelů pořadí.
Tento seznam poskytovatelů se liší od uživatele k uživateli, ale seznamy sousedních transakcí se mohou lišit maximálně o jednoho poskytovatele.
Nyní, když máme poskytovatele pořadí, můžeme vyčlenit jejich transakce v DAG a uspořádat všechny ostatní transakce kolem pořadí, které vytvořili. Možnost vytvořit takový algoritmus existuje (viz pro technické detaily).
Ale řád v celé síti není možné určit okamžitě, potřebujeme čas, aby poskytovatelé pořádku poslali dostatečné množství svých transakcí a ujistili se o konečném pořadí minulých transakcí.
A protože pořadí je určováno pouze pozicemi transakcí poskytovatelů v DAG, všechny uzly sítě dříve či později obdrží všechny transakce a dospějí k jednomu závěru ohledně pořadí transakcí.
Takže máme shodu na tom, co považujeme za událost: jakákoli transakce, která se dostala do DAG, se stala. Také máme shodu o pořadí událostí: to buď vyplývá z rodičovských vazeb transakcí, nebo se odvozuje z pořadí transakcí zaslaných poskytovateli pořádku. To znamená, že máme konsensus.
Tento typ konsensu máme v Obyte. I když je přístup do registru Obyte zcela decentralizovaný, konsensus ohledně pořadí transakcí je stále centralizovaný, protože 10 z 12 poskytovatelů je kontrolováno zakladatelem (Anton Čurjumov) a pouze dva z nich jsou nezávislí. Hledáme kandidáty, kteří by se chtěli stát jedním z nezávislých poskytovatelů pořádku, abychom nám pomohli decentralizovat určování pořadí v registru.
Nedávno se objevil třetí nezávislý kandidát, který chce zřídit a udržovat uzel poskytovatele pořádku – Univerzita v Nikósii.
Jak ovládáme dvojité utrácení (double-spends)?
Podle pravidel, při zjištění dvou transakcí, které utrácejí stejnou minci, vyhrává ta transakce, která byla dříve v konečném pořadí všech transakcí. Druhá je zneplatněna konsenzuálním algoritmem.
Pokud je možné určit pořadí mezi dvěma transakcemi, které utrácejí jednu minci (podle vazeb rodič-dítě), všechny uzly okamžitě odmítnou takový pokus o dvojité utrácení.
Pokud však pořadí není zřejmé z rodičovských vazeb mezi dvěma takovými transakcemi, obě jsou přijaty do registru a budeme muset počkat na konsensus a určení pořadí mezi nimi prostřednictvím poskytovatelů pořádku. Poté vyhraje dřívější transakce a druhá se stane neplatnou.
I když se druhá transakce stává neplatnou, stále zůstává v registru, protože má následující transakce, které se na ni odvolávají a které nic nenarušily a nevěděly, že se v budoucnu tato transakce stane neplatnou. Jinak bychom museli odstranit rodiče od dobrých následujících transakcí, což by porušovalo hlavní princip sítě – každá správná transakce je přijímána do registru.
To je velmi důležité pravidlo, které umožňuje celému systému být odolným vůči pokusům o cenzuru.
Představme si, že všichni poskytovatelé pořadí se spolčí, aby se pokusili „cenzurovat“ jednu konkrétní transakci. Mohou ji ignorovat a nikdy ji nezvolit „rodičem“ svých transakcí, ale to nestačí, tato transakce stále může být zahrnuta nepřímo jako rodič nějaké jiné transakce vydané kterýmkoli uživatelem sítě, který se na spiknutí nepodílí. V průběhu času taková transakce získá stále více a více dětí, vnuků a pravnuků od běžných uživatelů, rozrůstající se jako sněhová koule, a všichni dohodnutí poskytovatelé pořadí budou muset ignorovat také tyto transakce. Nakonec budou muset cenzurovat celou síť, což je ekvivalentní sabotáži.
Tímto způsobem zůstává DAG odolný vůči cenzuře, i když dojde ke spiknutí poskytovatelů pořadí, čímž překonává blockchain v odolnosti vůči cenzuře, kde nemůžeme nic dělat, pokud se těžaři rozhodnou nezahrnout některou z transakcí. A to vyplývá z hlavní vlastnosti DAG: účast v registru je zcela nezávislá a bez prostředníků, a transakce jsou neodvolatelné.
Zdroj: habr.com
