W tym artykule opowiem Wam o DAG (Directed Acycle Graph) i jego zastosowaniu w rozproszonych księgach rachunkowych, a także porównamy go z blockchainem.
DAG nie jest niczym nowym w świecie kryptowalut. Być może słyszałeś o tym jako o rozwiązaniu problemów ze skalowalnością blockchainu. Ale dzisiaj nie będziemy rozmawiać o skalowalności, ale o tym, co wyróżnia kryptowaluty od wszystkiego innego: decentralizacja, brak pośredników i opór przed cenzurą.
Pokażę Ci również, że DAG jest w rzeczywistości bardziej odporny na cenzurę i nie ma pośredników mających dostęp do księgi głównej.
W znanych nam blockchainach użytkownicy nie mają bezpośredniego dostępu do samej księgi. Kiedy chcesz dodać transakcję do księgi, musisz „poprosić” o to producenta bloku (tzw. „górnika”). To górnicy decydują, którą transakcję dodać do następnego bloku, a którą nie. To górnicy mają wyłączny dostęp do bloków i prawo decydowania, czyja transakcja zostanie przyjęta do księgi głównej.
Górnicy są pośrednikami stojącymi pomiędzy Tobą a rozproszoną księgą.
W praktyce zwykle niewielka liczba koparek wspólnie kontroluje ponad połowę mocy obliczeniowej sieci. Dla Bitcoina są to cztery pule, dla Ethereum – dwie. Jeśli zmówią się, mogą zablokować dowolne transakcje.
Na przestrzeni ostatnich kilku lat zaproponowano wiele odmian blockchainów, różniących się zasadami wyboru producentów bloków. Ale sami producenci bloków nigdzie się nie wybierają, nadal „stoją przy barierze”: każda transakcja musi przejść przez producenta bloków, a jeśli on jej nie zaakceptuje, to tak naprawdę transakcji nie ma.
Jest to nieunikniony problem związany z blockchainem. A jeśli chcemy to rozwiązać, musimy radykalnie zmienić projekt i całkowicie pozbyć się bloków i producentów bloków. I zamiast budować łańcuch bloków, połączymy same transakcje, uwzględniając w każdej transakcji skróty kilku poprzednich. W efekcie otrzymujemy strukturę znaną w matematyce jako skierowany graf acykliczny – DAG.
Teraz każdy ma bezpośredni dostęp do rejestru, bez pośredników. Jeśli chcesz dodać transakcję do księgi, po prostu ją dodajesz. Wybierasz kilka transakcji nadrzędnych, dodajesz swoje dane, podpisujesz i wysyłasz transakcję do partnerów w sieci. Gotowy. Nikt nie może Cię przed tym powstrzymać, więc Twoja transakcja jest już zapisana w księdze.
Jest to najbardziej zdecentralizowany i odporny na cenzurę sposób dodawania transakcji do księgi bez pośredników. Ponieważ każdy po prostu dodaje swoje transakcje do rejestru, nie pytając nikogo o pozwolenie.
DAG można uznać za trzeci etap ewolucji rejestrów. Najpierw istniały scentralizowane rejestry, do których jedna strona kontrolowała dostęp do nich. Potem przyszedł czas na blockchainy, które miały już kilku kontrolerów, którzy rejestrowali transakcje w księdze. I wreszcie w DAG nie ma w ogóle kontrolerów, użytkownicy dodają swoje transakcje bezpośrednio.
Teraz, gdy mamy tę wolność, nie powinna ona prowadzić do chaosu. Musimy dojść do porozumienia w sprawie stanu rejestru. A to porozumienie lub konsensus zwykle oznacza zgodę w dwóch kwestiach:
- Co się stało?
- W jakiej kolejności to się stało?
Na pierwsze pytanie możemy łatwo odpowiedzieć: poprawnie utworzona transakcja została dodana do księgi i nastąpiła. I okres. Informacja o tym może dotrzeć do wszystkich uczestników w różnym czasie, ale ostatecznie wszystkie węzły otrzymają tę transakcję i będą wiedziały, że do niej doszło.
Gdyby był to blockchain, górnicy decydowaliby, co się stanie. Cokolwiek górnik zdecyduje się umieścić w bloku, tak się stanie. Nie dzieje się wszystko, czego nie uwzględni w bloku.
W blockchainach górnicy rozwiązują również drugi problem konsensusu: porządek. Mogą dowolnie porządkować transakcje w ramach bloku.
Jak ustalić kolejność transakcji w DAG?
Tylko dlatego, że nasz graf jest skierowany, mamy już pewien porządek. Każda transakcja odnosi się do jednej lub kilku poprzednich, nadrzędnych. Rodzice z kolei odnoszą się do swoich rodziców i tak dalej. Rodzice oczywiście pojawiają się przed transakcjami podrzędnymi. Jeśli do którejkolwiek transakcji można dotrzeć poprzez przejście łącza rodzic-dziecko, znamy dokładnie kolejność transakcji w tym łańcuchu transakcji.
Jednak kolejności transakcji nie zawsze można określić na podstawie samego kształtu wykresu. Na przykład, gdy dwie transakcje leżą na równoległych gałęziach wykresu.
Aby rozwiać niejasności w takich przypadkach, polegamy na tak zwanych dostawcach zamówień. Nazywamy ich także „świadkami”. Są to zwykli użytkownicy, których zadaniem jest ciągłe przesyłanie transakcji do sieci w sposób uporządkowany, tj. tak, aby każda z ich poprzednich transakcji mogła zostać osiągnięta poprzez przejścia wzdłuż łączy rodzic-dziecko. Dostawcy zamówień są zaufanymi użytkownikami i cała sieć na nich polega, aby nie łamać tej zasady. W celu racjonalnie zaufaj im, wymagamy, aby każdy zleceniodawca był znaną (nieanonimową) osobą lub organizacją i miał coś do stracenia w przypadku złamania zasad, np. reputację lub biznes oparty na zaufaniu.
Dostawcy zamówień wybierani są przez użytkowników, a każdy użytkownik dołącza listę swoich zaufanych dostawców do każdej transakcji wysyłanej do sieci. Na tej liście znajduje się 12 dostawców. Jest to na tyle mała liczba, aby osoba mogła zweryfikować tożsamość i reputację każdego z nich, a jednocześnie wystarczająca, aby zapewnić dalsze działanie sieci w przypadku nieuniknionych problemów z mniejszością dostawców zamówień.
Ta lista dostawców różni się w zależności od użytkownika, ale listy sąsiadujących transakcji mogą się różnić w przypadku maksymalnie jednego dostawcy.
Teraz, gdy mamy dostawców zamówień, możemy wyodrębnić ich transakcje w DAG i uporządkować wszystkie inne transakcje według utworzonego przez nich zamówienia. Możliwe jest stworzenie takiego algorytmu (patrz. w celu uzyskania szczegółów technicznych).
Ale kolejności całej sieci nie da się ustalić od razu, potrzebujemy czasu, aby dostawcy zleceń przesłali odpowiednią liczbę swoich transakcji, aby zweryfikować ostateczną kolejność transakcji przeszłych.
A ponieważ o kolejności decydują jedynie pozycje transakcji dostawców w DAG, wszystkie węzły w sieci prędzej czy później otrzymają wszystkie transakcje i dojdą do tego samego wniosku co do kolejności transakcji.
Zatem jesteśmy zgodni co do tego, co uważamy za mające miejsce: każda transakcja, która trafia do DAG, miała miejsce. Mamy także zgodność co do kolejności zdarzeń: wynika ona albo z powiązań transakcji, albo wynika z kolejności transakcji przesłanej przez dostawców zleceń. Mamy więc konsensus.
Tę wersję konsensusu mamy w Obyte. Mimo że dostęp do księgi Obyte jest całkowicie zdecentralizowany, konsensus co do kolejności transakcji jest nadal scentralizowany, ponieważ 10 z 12 dostawców jest kontrolowanych przez twórcę (Antona Churyumova), a tylko dwóch z nich jest niezależnych. Poszukujemy kandydatów chcących zostać jednym z niezależnych dostawców zleceń, którzy pomogliby nam zdecentralizować porządek księgi głównej.
Niedawno pojawił się trzeci niezależny kandydat chcący zainstalować i utrzymywać węzeł dostawcy zamówień – Uniwersytet w Nikozji.
Jak teraz kontrolować podwójne wydatki?
Zgodnie z zasadami, jeśli zostaną znalezione dwie transakcje wykorzystujące tę samą monetę, wygrywa transakcja, która zajmie pierwsze miejsce w ostatecznej kolejności wszystkich transakcji. Drugi jest unieważniany przez algorytm konsensusu.
Jeśli możliwe jest ustalenie kolejności pomiędzy dwiema transakcjami wydającymi tę samą monetę (poprzez połączenia rodzic-dziecko), wówczas wszystkie węzły natychmiast odrzucają taką próbę podwojenia wydatków.
W przypadku, gdy zlecenie nie jest widoczne z relacji nadrzędnych pomiędzy dwiema takimi transakcjami, obie są akceptowane w księdze i będziemy musieli poczekać na konsensus i ustalenie kolejności pomiędzy nimi za pomocą dostawców zleceń. Wtedy wcześniejsza transakcja wygra, a druga straci ważność.
Mimo że druga transakcja utraciła ważność, to nadal pozostaje w rejestrze, ponieważ odwołują się do niej już kolejne transakcje, które niczego nie naruszyły i nie wiedziały, że w przyszłości ta transakcja stanie się nieważna. W przeciwnym razie musielibyśmy usunąć rodzica dobrych kolejnych transakcji, co naruszyłoby główną zasadę sieci – każda poprawna transakcja jest akceptowana w księdze.
To bardzo ważna zasada, która pozwala uodpornić cały system na próby cenzury.
Wyobraźmy sobie, że wszyscy dostawcy zamówień współdziałają w zmowie, próbując „cenzurować” jedną konkretną transakcję. Mogą ją zignorować i nigdy nie wybrać jej jako „rodzica” dla swoich transakcji, ale to nie wystarczy, transakcja może nadal zostać pośrednio uwzględniona jako transakcja nadrzędna innej transakcji wydanej przez dowolnego użytkownika w sieci, który nie uczestniczy w zmowie. Z biegiem czasu taka transakcja będzie otrzymywać od zwykłych użytkowników coraz więcej dzieci, wnuków i prawnuków, rosnących jak kula śnieżna, a wszyscy uzgodnieni dostawcy zamówień również będą musieli ignorować te transakcje. Ostatecznie będą musieli cenzurować całą sieć, co jest równoznaczne z sabotażem.
W ten sposób DAG pozostaje odporny na cenzurę, nawet jeśli istnieje zmowa między dostawcami zamówień, przewyższając w ten sposób odporny na cenzurę blockchain, w którym nie możemy nic zrobić, jeśli górnicy zdecydują się nie uwzględniać żadnej transakcji. A to wynika z głównej właściwości DAG: udział w rejestrze jest całkowicie niezależny i bez pośredników, a transakcje są nieodwracalne.
Źródło: www.habr.com