В тази статия ще ви разкажа за DAG (Directed Acyclic Graph, насочена ациклична графа) и неговото приложение в разпределените регистри, а също така ще го сравним с блокчейн.
DAG не е нещо ново в света на криптовалутите. Вероятно сте чули за него като решение на проблемите с мащабируемостта на блокчейните. Но днес ще говорим не за мащабируемост, а за това, което отличава криптовалутите от всичко останало: децентрализация, отсъствие на посредници и устойчивост на цензура.
Също така ще ви покажа, че DAG всъщност е по-устойчив на цензура и в него липсват посредници за достъп до регистъра.
В познатите ни блокчейни потребителите нямат пряк достъп до самия регистър. Когато искате да добавите транзакция в регистъра, трябва да "попитате" производителите на блокове (блок-продуцента, известен още като "майнер"). Именно майнерите решават коя транзакция да бъде добавена в следващия блок и коя - не. Само майнерите имат ексклузивен достъп до блоковете и правото да решават коя транзакция да приемат за добавяне в регистъра.
Майнерите са посредниците, които стоят между вас и разпределения регистър.
На практика обаче, обикновено малък брой миниинг пулове колективно контролират повече от половината изчислителни мощности на мрежата. За биткойн това са четири пула, а за Ethereum - два. В случай на техен сговор, те могат да блокират каквито и да е транзакции, които пожелаят.
През последните няколко години бяха предложени множество вариации на блокчейни, различаващи се по принципите на избор на производители на блокове. Но самите производители на блокове не изчезват, те все още "стоят на пост": всяка транзакция трябва да премине през производителя на блокове, и ако той не я приеме, трансакцията фактически не съществува.
Това е неизбежен проблем с блокчейна. И ако искаме да го решим, трябва радикално да променим дизайна и напълно да се отървем от блоковете и производителите на блокове. Вместо да изграждаме верига от блокове, ние ще свързваме самите транзакции, включвайки в тях хешове на няколко предишни. В резултат ще получим структура, известна в математиката като насочен ацикличен граф – DAG.
Сега все имат директен достъп до регистъра, без посредници. Когато искате да добавите транзакция в регистъра – просто я добавяте. Избирате няколко родителски транзакции, добавяте данните си, подписвате и изпращате транзакцията си в мрежата. Готово. Няма никой, който да може да ви попречи да го направите, така че вашата транзакция вече е в регистъра.
Това е най-децентрализираната, най-неуязвимата пред цензура начин на добавяне на транзакции в регистъра без посредници. Защото всеки, който желае, просто добавя своите транзакции в регистъра, без да пита разрешение от никого.
DAG може да се счита за третата фаза на еволюцията на регистрите. Първо бяха централизирани регистри, където една страна контролираше достъпа до тях. След това дойдоха блокчейни, където вече имаше няколко контролора, които записваха транзакции в регистъра. И накрая, в DAG няма контролори, потребителите добавят своите транзакции директно.
Сега, когато имаме такава свобода, тя не трябва да води до хаос. Трябва да имаме съгласие относно състоянието на регистъра. И това съгласие, или консенсус, обикновено означава съгласие относно две неща:
- Какво се случи?
- В какъв ред се е случило това?
На първия въпрос можем лесно да отговорим: щом правилно създадената транзакция е добавена в регистъра, тя се е случила. И точка. Информацията за това може да достигне до всички участници в различно време, но в крайна сметка всички възли ще получат тази транзакция и ще разберат, че тя се е случила.
Ако това беше блокчейн, майнерите щяха да решават какво се случва. Всичко, което майнер решава да включи в блока – това се случва. Всичко, което не включва в блока – не се случва.
В блокчейните майнерите също решават втория проблем на консенсуса: реда. Им е разрешено да подреждат транзакциите в блока както поискат.
Как да определим реда на транзакциите в DAG?
Само по себе то, что граф у нас ориентированный, уже создает некоторый порядок. Каждая транзакция ссылается на одну или несколько предыдущих, родительских. Родители, в свою очередь, ссылаются на своих родителей, и так далее. Родители, очевидно, появляются раньше дочерних транзакций. Если какая-либо из транзакций может быть достигнута переходами по ссылкам «родитель-ребёнок», мы точно знаем порядок между транзакциями в этой цепочке транзакций.
Однако порядок между транзакциями не всегда можно определить только из формы графа. Например, когда две транзакции лежат на параллельных ветвях графа.
Чтобы разрешить неоднозначность в таких случаях, мы полагаемся на так называемых провайдеров порядка. Мы также называем их «свидетелями». Это общепринятые пользователи, чья задача заключается в постоянной отправке транзакций в сеть с соблюдением порядка, т.е. так, чтобы каждая их предыдущая транзакция могла быть достигнута переходами по ссылкам «родитель-ребёнок». Провайдеры порядка – доверенные пользователи, и вся сеть полагается на то, что они не будут нарушать данное правило. Для того чтобы обоснованно доверять им, мы требуем, чтобы каждый провайдер порядка был известным (неанонимным) лицом или организацией и имел что-то, что может потерять в случае, если нарушит правила, например, репутацию или бизнес, основанный на доверии.
Провайдеры порядка выбираются пользователями, и каждый пользователь включает список его доверенных провайдеров в каждую транзакцию, которую отправляет в сеть. Этот список состоит из 12 провайдеров. Это достаточно небольшое количество, чтобы человек мог проверить личности и репутацию каждого из них, и достаточно для того, чтобы сеть продолжала функционировать в случае неизбежных проблем с меньшинством провайдеров порядка.
Данный список провайдеров варьируется от пользователя к пользователю, но списки у соседних транзакций могут отличаться максимум на одного провайдера.
Теперь, когда у нас есть провайдеры порядка, мы можем выделить их транзакции в DAG и упорядочить все другие транзакции вокруг порядка, созданного ими. Возможность создания такого алгоритма существует (см. для технических деталей).
Но редът в цялата мрежа не може да бъде определен моментално, имаме нужда от време, за да могат доставчиците на реда да изпратят достатъчно количество свои транзакции, за да се уверим в крайния ред на предишните транзакции.
И, тъй като редът се определя само от позициите на транзакциите на доставчиците в DAG, всички възли в мрежата рано или късно ще получат всички транзакции и ще достигнат до едно и също заключение относно реда на транзакциите.
Така че, ние имаме съгласие относно това, което считаме за станало: всяка транзакция, попаднала в DAG, е станала. Освен това имаме съгласие относно реда на събитията: това може да бъде видно от родословните връзки на транзакциите или може да бъде извлечено от реда на транзакциите, изпратени от доставчиците на реда. Следователно имаме консенсус.
Този вариант на консенсуса имаме в Obyte. Въпреки че достъпът до регистъра на Obyte е напълно децентрализиран, консенсусът относно реда на транзакциите все още е централизиран, тъй като 10 от 12 доставчици се контролират от създателя (Антон Чурюмов), а само двама от тях са независими. Търсим кандидати, които искат да станат един от независимите доставчици на реда, за да ни помогнат да децентрализираме установяването на реда в регистъра.
Скоро се появи трети независим кандидат, желаещ да установи и поддържа възел на доставчик на реда – Университет Никозия.
Сега как контролираме двойните разходи (double-spends)?
Според правилата, при откритие на две транзакции, които харчат една и съща монета, транзакцията, която е била по-рано в крайния ред на всички транзакции, печели. Втората се анулира от алгоритъма на консенсуса.
В случай че е възможно да се установи ред между две транзакции, които харчат една монета (по родителски връзки), всички възли незабавно отхвърлят такава попытка за двойни разходи.
В случай обаче, че редът не е видим от родителските връзки между двете транзакции, и двете се приемат в регистъра, и ще трябва да изчакаме консенсуса и установяването на реда между тях с помощта на доставчици на реда. Тогава по-ранната транзакция ще спечели, а втората ще стане невалидна.
Въпреки че втората транзакция става невалидна, тя все пак остава в регистъра, тъй като вече има последващи транзакции, които се позовават на нея и които не нарушават нищо и не знаят, че в бъдеще тази транзакция ще стане невалидна. В противен случай щеше да е необходимо да премахнем родителя на добрите последващи транзакции, което би нарушило основния принцип на мрежата – всяка правилна транзакция се приема в регистъра.
Това е много важно правило, което позволява на цялата система да бъде устойчива на опити за цензура.
Представете си, че всички редови доставчици се съюзяват в опит да "цензурират" една конкретна транзакция. Те могат да я игнорират и никога да не я избират за "родител" на своите транзакции, но това не е достатъчно, тъй като тази транзакция все още може да бъде включена косвено като родител на някоя друга транзакция, издадена от потребител на мрежата, който не участва в съюза. С времето, такава транзакция ще получава все повече и повече деца, внуци и правнуци от обикновени потребители, разраствайки се като снежна топка, и на всички съгласили се доставчици ще им се наложи да игнорират и тези транзакции също. В крайна сметка, те ще трябва да цензурират цялата мрежа, което е равносилно на саботаж.
По този начин, DAG остава устойчива на цензура, дори ако има сговор между редовите доставчици, като по този начин надминава блокчейна по устойчивост на цензури, в който ние не можем да направим нищо, ако миньорите решат да не включват някоя от транзакциите. И това произтича от основното свойство на DAG: участието в регистъра е абсолютно независимо и без посредници, а транзакциите са необратими.
Източник: habr.com
