W tym artykule opowiem ci o DAG (Directed Acyclic Graph, skierowany acykliczny graf) i jego zastosowaniu w rozproszonych rejestrach oraz porównamy go z blockchainem.
DAG nie jest niczym nowym w świecie kryptowalut. Może słyszałeś o nim jako o rozwiązaniu problemów skalowalności blockchainów. Ale dzisiaj będziemy mówić nie o skalowalności, a o tym, co sprawia, że kryptowaluty są inne niż wszystko inne: decentralizacja, brak pośredników i odporność na cenzurę.
Pokażę ci również, że DAG jest faktycznie bardziej odporny na cenzurę, a dostęp do rejestru odbywa się bez pośredników.
W tradycyjnych blockchainach użytkownicy nie mają bezpośredniego dostępu do samego rejestru. Gdy chcesz dodać transakcję do rejestru, musisz 'poprosić' producenta bloków (producenta bloków, znanego również jako 'górnik'). To właśnie górnicy decydują, którą transakcję dodać do następnego bloku, a którą pominąć. To oni mają wyłączny dostęp do bloków i prawo decydowania, którą transakcję przyjąć do dodania do rejestru.
Górnicy są pośrednikami, którzy stają między tobą a rozproszonym rejestrem.
W praktyce zwykle niewielka liczba pooli górników kolektywnie kontroluje ponad połowę mocy obliczeniowej sieci. Dla Bitcoina są to cztery pule, a dla Ethereum – dwie. W przypadku ich zmowy mogą zablokować dowolne transakcje, jakie zechcą.
W ciągu ostatnich kilku lat zaproponowano wiele wariantów blockchainów, różniących się zasadami wyboru producentów bloków. Ale sami producenci bloków wciąż pozostają, wciąż 'stoją przy bramie': każda transakcja musi przejść przez producenta bloków, a jeśli ten jej nie przyjmie, faktycznie nie istnieje.
To nieunikniony problem w przypadku blockchaina. I jeśli chcemy go rozwiązać, musimy radykalnie zmienić projekt i całkowicie pozbyć się bloków oraz producentów bloków. Zamiast budować łańcuch bloków, połączymy same transakcje, włączając w każdą transakcję hashe kilku poprzednich. W rezultacie uzyskamy strukturę znaną w matematyce jako skierowany acykliczny graf – DAG.
Teraz każdy ma bezpośredni dostęp do rejestru, bez pośredników. Kiedy chcesz dodać transakcję do rejestru – po prostu ją dodajesz. Wybierasz kilka transakcji rodzicielskich, dodajesz swoje dane, podpisujesz i wysyłasz swoją transakcję do sieci. I gotowe. Nikt nie może ci w tym przeszkodzić, więc twoja transakcja już jest w rejestrze.
To najbardziej zdecentralizowany, najbardziej odporny na cenzurę sposób dodawania transakcji do rejestru bez pośredników. Ponieważ każdy, kto chce, po prostu dodaje swoje transakcje do rejestru, nie pytając nikogo o pozwolenie.
DAG można uznać za trzeci etap ewolucji rejestrów. Najpierw były zcentralizowane rejestry, gdzie jedna strona kontrolowała dostęp do nich. Następnie pojawiły się blockchainy, w których istniało już kilku kontrolerów, którzy zapisywali transakcje w rejestrze. A ostatecznie, w DAG nie ma żadnych kontrolerów, użytkownicy dodają swoje transakcje bezpośrednio.
Teraz, gdy mamy taką wolność, nie powinna ona prowadzić do chaosu. Musimy mieć zgodę co do stanu rejestru. A ta zgoda, czy też konsensus, zazwyczaj oznacza zgodę co do dwóch rzeczy:
- Co się stało?
- W jakiej kolejności to się zdarzyło?
Na pierwsze pytanie możemy łatwo odpowiedzieć: gdy tylko poprawnie utworzona transakcja została dodana do rejestru, miała miejsce. I kropka. Informacja o tym może dotrzeć do wszystkich uczestników w różnym czasie, ale ostatecznie wszystkie węzły otrzymają tę transakcję i dowiedzą się, że miała miejsce.
Gdyby to był blockchain, górnicy decydowaliby, co się dzieje. Wszystko, co górnik postanowiłby umieścić w bloku – to się dzieje. Wszystko, czego nie uwzględnia w bloku – nie dzieje się.
W blockchainach górnicy również decydują o drugim problemie konsensusu: kolejności. Mają prawo porządkować transakcje w bloku według własnego uznania.
Jak więc zdefiniować kolejność transakcji w DAG?
Tylko dlatego, że graf jest skierowany, mamy pewien porządek. Każda transakcja odnosi się do jednej lub kilku poprzednich, rodzicielskich. Rodzice z kolei odnoszą się do swoich rodziców, i tak dalej. Rodzice, oczywiście, pojawiają się przed transakcjami potomnymi. Jeśli jakakolwiek transakcja może być osiągnięta przez przejścia po linkach „rodzic-dziecko”, dokładnie znamy porządek pomiędzy transakcjami w tym łańcuchu transakcji.
Jednak porządek pomiędzy transakcjami nie zawsze może być określony tylko na podstawie kształtu grafu. Na przykład, gdy dwie transakcje znajdują się na równoległych gałęziach grafu.
Aby rozwiązać niejednoznaczność w takich przypadkach, polegamy na tak zwanych dostawcach porządku. Nazywamy je również „świadkami”. Są to zwykli użytkownicy, których zadaniem jest nieustanne przesyłanie transakcji do sieci z zachowaniem porządku, tzn. tak, że każda ich poprzednia transakcja może być osiągnięta przez przejścia po linkach „rodzic-dziecko”. Dostawcy porządku – zaufani użytkownicy, a cała sieć polega na tym, że nie będą łamać tej zasady. Aby racjonalnie im ufać, wymagamy, aby każdy dostawca porządku był znaną (nieanonimową) osobą lub organizacją i miał coś, co może stracić w przypadku naruszenia zasad, na przykład reputację lub biznes oparty na zaufaniu.
Dostawcy porządku są wybierani przez użytkowników, a każdy użytkownik dołącza listę swoich zaufanych dostawców do każdej transakcji, którą wysyła do sieci. Lista ta składa się z 12 dostawców. To dość mała liczba, aby osoba mogła zweryfikować tożsamości i reputację każdego z nich, i wystarczająca, aby sieć funkcjonowała w przypadku nieuniknionych problemów z mniejszością dostawców porządku.
Ta lista dostawców różni się od użytkownika do użytkownika, ale listy sąsiednich transakcji mogą różnić się maksymalnie o jednego dostawcę.
Teraz, gdy mamy dostawców porządku, możemy wydzielić ich transakcje w DAG i uporządkować wszystkie inne transakcje wokół porządku, który stworzyli. Istnieje możliwość stworzenia takiego algorytmu (patrz po szczegóły techniczne).
Jednakże porządek w całej sieci nie może być ustalony natychmiast, potrzebujemy czasu, aby dostawcy porządku wysłali wystarczającą liczbę swoich transakcji, aby upewnić się co do ostatecznej kolejności poprzednich transakcji.
A ponieważ porządek określany jest wyłącznie przez pozycje transakcji dostawców w DAG, wszystkie węzły sieci prędzej czy później otrzymają wszystkie transakcje i dojdą do tej samej konkluzji odnośnie porządku transakcji.
Zatem mamy zgodność co do tego, co uważamy za zdarzenie: każda transakcja, która trafiła do DAG, miała miejsce. Mamy również zgodność co do kolejności zdarzeń: jest to widoczne na podstawie relacji rodzic-dziecko transakcji lub też wyprowadzane z porządku transakcji wysyłanych przez dostawców porządku. Oznacza to, że mamy konsensus.
Ten wariant konsensusu mamy w Obyte. Mimo że dostęp do rejestru Obyte jest całkowicie zdecentralizowany, konsensus co do porządku transakcji wciąż pozostaje scentralizowany, ponieważ 10 z 12 dostawców jest kontrolowanych przez twórcę (Anton Churyumov), a tylko dwóch z nich jest niezależnych. Szukamy kandydatów, którzy chcą zostać jednym z niezależnych dostawców porządku, aby pomóc nam w decentralizacji ustalania porządku w rejestrze.
Ostatnio pojawił się trzeci niezależny kandydat, który chce ustalić i utrzymać węzeł dostawcy porządku – Uniwersytet Nikozji.
Jak zatem kontrolujemy podwójne wydatki (double-spends)?
Według zasad, gdy wykryte zostaną dwie transakcje wydające tę samą monetę, transakcja, która pojawiła się wcześniej w ostatecznym porządku wszystkich transakcji, wygrywa. Druga zostaje unieważniona przez algorytm konsensusu.
W sytuacji, gdy istnieje możliwość ustalenia porządku między dwiema transakcjami wydającymi jedną monetę (na podstawie relacji rodzic-dziecko), wszystkie węzły odrzucają taką próbę podwójnego wydatku.
Jeśli jednak porządek nie jest widoczny z relacji rodzicielskich między dwiema takimi transakcjami, obie są akceptowane w rejestrze, a my musimy poczekać na konsensus i ustalenie porządku między nimi przez dostawców porządku. Wówczas wygrywa wcześniejsza transakcja, a druga staje się nieważna.
Chociaż druga transakcja staje się nieważna, nadal pozostaje w rejestrze, ponieważ ma już następne transakcje, które się na nią powołują, a które nie naruszały niczego i nie wiedziały, że w przyszłości ta transakcja stanie się nieważna. W przeciwnym razie musielibyśmy usunąć rodzica z dobrych następnych transakcji, co naruszyłoby główną zasadę sieci – każda prawidłowa transakcja jest akceptowana w rejestrze.
To bardzo ważna zasada, która pozwala całemu systemowi być odpornym na próby cenzury.
Załóżmy, że wszyscy dostawcy porządku wchodzą w zmowę, próbując "cenzurować" jedną konkretną transakcję. Mogą ją ignorować i nigdy nie wybierać jako "rodzca" dla swoich transakcji, ale to niedostateczne; ta transakcja wciąż może być pośrednio uwzględniona jako rodzic innej transakcji wydanej przez dowolnego użytkownika sieci, który nie bierze udziału w zmowie. Z biegiem czasu taka transakcja będzie zdobywać coraz więcej dzieci, wnuków i prawnuków od zwykłych użytkowników, rozwijając się jak kula śnieżna, i wszyscy umówieni dostawcy porządku będą musieli ignorować również 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 dochodzi do zmowy dostawców porządku, tym samym przewyższając blockchain pod względem trwałości na cenzurę, w którym nic nie możemy zrobić, jeśli górnicy zdecydują się nie uwzględniać żadnej z transakcji. Z tego wynika główna cecha DAG: udział w rejestrze jest całkowicie niezależny i bezpośredni, a transakcje są nieodwracalne.
Źródło: habr.com
