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