Что такое направленный ациклический граф (DAG) в криптовалютах?
Содержание
Введение
Что такое DAG?
Как работают DAG?
Преимущества и недостатки направленных ациклических графов
Резюме
Что такое направленный ациклический граф (DAG) в криптовалютах?
ГлавнаяСтатьи
Что такое направленный ациклический граф (DAG) в криптовалютах?

Что такое направленный ациклический граф (DAG) в криптовалютах?

Продвинутый
Published Jul 19, 2020Updated Feb 3, 2022
7m

Содержание


Введение

Когда вы думаете о криптовалюте, на ум, скорее всего, приходят термины "блокчейн" или "технология распределенного реестра". С момента появления биткоина были созданы сотни криптовалют. Большинство из них полагаются на схожую архитектуру сети. Их структуры данных позволяют передавать ценность или взаимодействовать с децентрализованными приложениями.
В блокчейне новый блок добавляется к растущей цепочке блоков через определенные промежутки времени. Каждый блок связан с предыдущим криптографической связью (а именно, хешем). В каждом из этих блоков записаны последние транзакции, совершенные пользователями.
Но часто между транзакцией и ее включением в блок существует задержка. Ее можно сравнить с ожиданием поезда на станции. Из-за размера вагонов (размера блоков) и количества других ожидающих людей (ожидающих транзакций) вы можете даже не успеть на следующий поезд. Или даже тот, что придет после. Подтверждение транзакции может занять от нескольких секунд до нескольких часов.
Для многих это приемлемый компромисс. В конце концов, блокчейн обеспечивает очень высокую степень безопасности, не полагаясь на централизованного координатора. Еще один недостаток — технология блокчейн имеет срок годности. Скептики считают, что в долгосрочной перспективе проблемы масштабируемости, с которыми сталкивается технология, будут препятствовать ее массовому внедрению.

Некоторые энтузиасты полагают, что будущее криптовалютных платежей связано с совершенно другой архитектурой — направленными ациклическими графами (DAG).


Что такое DAG?

DAG — структура данных другого типа, которую можно представить в виде базы данных, связывающей между собой различные фрагменты информации. "Направленный ациклический граф" — достаточно сложный термин, поэтому для начала разберём его.


Направленный ациклический граф


В общем виде DAG выглядит как на рисунке сверху. Он состоит из вершин (окружностей) и ребер (соединяющих линий). Они являются  направленными, поскольку имеют одно направление (изображено стрелками). Они являются ациклическим (т. е. не циклическим), поскольку вершины не переходят сами в себя — если вы начнете двигаться по графу из любой точки, то не сможете вернуться в нее же. Рассмотрим подробнее.

Такие структуры данных обычно используются для моделирования. DAG используются в научной и медицинской областях для определения взаимосвязей между переменными и их влияния друг на друга. Например, можно рассмотреть такие процессы, как питание, циклы сна и физические симптомы, чтобы установить связь между ними и влияние на пациента.

Нас больше интересует, как они способствуют достижению консенсуса в распределенной криптовалютной сети.


Как работают DAG?

В криптовалютах, основанных на DAG, каждая вершина в структуре представляет собой транзакцию. Здесь нет понятия блоков, и для расширения базы данных не требуется майнинг. Таким образом, вместо группировки транзакций в блоки, каждая транзакция записывается поверх другой. Однако когда нода подтверждает транзакцию, все еще необходима некоторая операция с консенсусом Proof-of-Work. Это необходимо для проверки предыдущих транзакций и гарантии того, что сеть не подвергается атаке спама.

Добавление новой транзакции происходит поверх старых. Предположим, Алиса совершает транзакцию. Для подтверждения эта транзакция должна ссылаться на предыдущие. Аналогия — ссылка текущего блока биткоина на предыдущий, но здесь ссылки на несколько транзакций. 

В некоторых системах алгоритм сам выбирает, на каких конечных неподтвержденных транзакциях (tips) должна строиться новая транзакция. С наибольшей вероятностью будут выбраны транзакции с большим весом: в зависимости от того, сколько подтверждений имеет путь к транзакции.

Транзакции, на основе которых Алиса будет строить свою, не подтверждены. Они подтвердятся, когда Алиса сошлется на них. Теперь неподтвержденной станет транзакция Алисы — кто-то другой должен построить новую ссылающуюся транзакцию, прежде чем будет принята предыдущая.

Чтобы система продолжала расти, пользователи с большей вероятностью будут подтверждать транзакции с "более тяжелым" весом. В противном случае, ничто не мешало бы пользователям постоянно строить на более старых транзакциях.

В блокчейнах защита от двойного расходования достаточно проста. Одни и те же средства не могут быть потрачены в блоке дважды — ноды могут легко обнаружить такую попытку и отклонить блок, содержащий конфликтующие транзакции. Поскольку генерировать блоки майнерам очень затратно, они заинтересованы в том, чтобы все соответствовало правилам.

Направленные ациклические графы также имеют механизм предотвращения двойного расходования. Он похож на описанный выше, но без участия майнеров. Когда нода подтверждает более старые транзакции, она проходит весь путь до самой первой транзакции DAG, чтобы убедиться, что отправитель имеет достаточный баланс. До начальной транзакции могут существовать несколько путей, но проверить нужно только один.



Если пользователи строят по недопустимому пути, велик риск того, что их собственная транзакция будет проигнорирована. Их путь может быть корректным, но поскольку предыдущий таким не был, никто не захочет продолжать именно этот путь.

Сначала это кажется не интуитивным — разве не может быть ситуаций, когда существует несколько ветвей, которые не знают друг о друге? И не могут ли люди тратить одни и те же средства в разных ветвях?



Это действительно возможно, но это решается с помощью алгоритма выбора, который отдает предпочтение конечным транзакциям с большим накопленным весом. Это означает, что со временем образуется ветвь, которая будет намного длиннее остальных. Более слабые будут отброшены, и сеть продолжит строить самый длинный путь. 

Как и в случае с блокчейнами, этот выбор не окончателен — вы никогда не можете быть на 100% уверены, что транзакция не будет отменена. Звучит невозможно, но в теории вы можете "отменить" блок биткоина или Ethereum, отменив все транзакции до него. Чем больше блоков добавлено после того, в котором находится ваша транзакция, тем больше вы можете быть в ней уверены. Вот почему рекомендуется дождаться шести подтверждений, прежде чем тратить средства.
В таком DAG, как tangle криптовалюты IOTA, существует механизм подтверждения достоверности. Алгоритм отбора запускается 100 раз, и вы подсчитываете, сколько раз ваша транзакция была прямо или косвенно одобрена в выбранных конечных транзакциях. Чем выше процент, тем больше уверенности в том, что ваша транзакция останется "подтвержденной".

Может показаться, что это не совсем удобно для пользователя. Но это не так. Если Алиса отправляет Бобу 10 токенов MagicDAG, ей не нужно беспокоиться о выборе правильных вершин графа. В действительности, ее кошелек делает следующее:

  • Выбирает "тяжелые" транзакции (с наибольшим числом подтверждений).
  • Переходит назад по предыдущим транзакциям, чтобы убедиться, что на кошельках, задействованных в неподтвержденных транзакциях, достаточно средств.
  • Когда это требование удовлетворено, кошелек добавляет свою транзакцию в DAG, подтверждая транзакции, на которых основана текущая.
Для Алисы это будет выглядеть как обычный рабочий процесс криптовалюты. Она вводит адрес Боба, сумму, которую хочет потратить, и нажимает "перевести". Приведенный выше перечень действий представляет собой доказательство работы, которое каждый участник осуществляет при создании транзакции.



Преимущества и недостатки направленных ациклических графов

Преимущества DAG

Скорость

Независимость от времени блока — любой участник может производить и обрабатывать свои транзакции в любое время. Нет ограничений на количество транзакций, совершаемых пользователями, при условии, что они подтверждают более старые транзакции.


Отсутствие майнинга

DAG не используют привычный нам алгоритм консенсуса PoW. Таким образом, их углеродный след намного меньше, чем у криптовалют, которые для защиты своей сети блокчейна используют майнинг.


Нет комиссий за транзакции

Поскольку майнеров нет, пользователям не нужно платить комиссию за запись своих операций. Однако иногда требуется небольшая комиссия за использование специальных типов нод. Низкие комиссии (а еще лучше — их отсутствие) выгодны для микроплатежей, так как в других случаях они становятся бессмысленными из-за больших сетевых комиссий.


Отсутствие проблем с масштабируемостью

Не имея ограничений в виде времени блока, DAG могут обрабатывать намного больше транзакций в секунду, чем традиционные блокчейны. Многие сторонники считают, что это сделает их ценными при использовании в Интернете вещей (IoT), где все виды устройств смогли бы взаимодействовать друг с другом.


Недостатки DAG

Неполная децентрализованность

Протоколы, основанные на DAG, имеют различные элементы централизации. Есть мнение, что это предположительно краткосрочное решение для начальной загрузки сети, но неизвестно, смогут ли DAG существовать без вмешательства третьих сторон. Если нет, они становятся доступными для векторов атак, которые в конечном счете могут разрушить сети.


Недостаточные исследования масштабируемости 

Несмотря на то, что криптовалюты на основе DAG существуют уже несколько лет, им предстоит пройти долгий путь, прежде чем они получат широкое распространение. Таким образом, трудно предсказать, что может стимулировать пользователей применять эти системы в будущем.


Резюме

Направленные ациклические графы, безусловно, интересная технология для построения сетей криптовалют. Пока существует относительно немного проектов, использующих эту структуру данных, и им еще предстоит проявить себя в полной мере. 
Тем не менее, если они смогут раскрыть свой потенциал, они смогут обеспечить масштабируемую экосистему. Технология DAG имеет множество вариантов использования в областях, требующих высокой пропускной способности и отсутствия комиссий, таких как Интернет вещей (IoT) и микроплатежи.