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

Вопреки мнению, популярному в крипто-сообществе, применение направленного ациклического графа (directed acyclic graph, DAG) как основы для распределенного реестра не влечет ни отказа от майнинга с доказательством работы (proof of work, PoW), ни от блоков, ни от комиссий за транзакции. Использование DAG-а дает лишь возможность применить его структурные свойства для решения проблемы блоков-сирот, неустранимой в блокчейне. Но способность DAG-а справиться с ней и за счет этого улучшить масштабируемость конечного решения зависит еще и от ряда дополнительных правил, обеспечивающих согласованность набора транзакций и влияющих на выбор конструктивных решений, баланс между которыми приходится искать в ходе разработки системы.

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

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

В контексте распределенных реестров blockDAG — это граф, вершинам которого соответствуют блоки, а ребрам — ссылки из блоков на блоки-предшественники. BlockDAG возник, как часть решения проблемы блоков-сирот в блокчейне.

Проблема появления блоков-сирот в блокчейне

Масштабируемости блокчейна препятствует масса вещей: скорость обработки данных, скорость дискового ввода-вывода, объем потребной оперативной памяти, пропускная способность каналов связи, проблемы синхронизации новых узлов. Ограничения такой природы уходят по мере улучшения оборудования и технологий. Но есть еще одно серьезное препятствие уже на уровне протокола: частота появления блоков-сирот. Сироты — это блоки, генерируемые вне пределов «самой длинной цепочки», и возникающие из-за неизбежных задержек распространения данных по сети.

Рост скорости создания блоков и/или увеличение размера блоков увеличивает количество блоков-сирот: к тому моменту, как новый блок распространится по сети, уже будут, возможно, созданы другие новые блоки, которые на него не ссылаются. Хорошо известно, что высокий процент блоков-сирот угрожает безопасности сети; чем больше «честных» блоков оказывается вне самой длинной цепочки из-за спонтанных ее разветвлений, тем менее надежна эта цепочка.¹

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

Парадигма blockDAG

Понятие форка — разветвления цепочки — в структуру DAG вписывается вполне органично. Взяв PoW-систему Биткойна в качестве отправной точки, достаточно внести одно изменение в протокол майнинга, чтобы получить blockDAG вместо блокчейна: «блоки могут ссылаться на несколько предшественников (родителей) вместо одного». Естественный способ развить структуру реестра в этом направлении — это потребовать, чтобы блоки ссылались на все вершины графа (локально наблюдаемые каждым из майнеров), а не только на вершину единственной, самой длинной, цепочки, как это сделано в исходном протоколе Сатоши.

В реестре blockDAG новые блоки ссылаются на все вершины графа (т.е. блоки, на которые еще нет иных ссылок), которые известны локально майнерам этих новых блоков. Как и в блокчейне, новые блоки публикуются немедленно.

Сложность при этом в том, что, в отличие от блокчейна, который по своей конструкции сохраняет согласованность транзакций (каждый блок в цепочке добавляет в реестр только транзакции, согласованные с их предшественниками), blockDAG объединяет в структуру блоки из разных «ветвей», и поэтому может содержать множество конфликтующих транзакций. Из-за этого DAG вообще — и blockDAG в частности — не может считаться «решением» или «новым протоколом» сам по себе. Вместо этого blockDAG предоставляет основу для разработки протоколов согласования, которые могут (или не могут) быть такими же безопасными и более масштабируемыми, чем протоколы на основе цепочки².

Поэтому нам нужен метод для обеспечения согласованности. Иными словами, система blockDAG требует замены правила «самой длинной цепочки» Сатоши новым правилом достижения консенсуса.

Консенсус через упорядочивание

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

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

Естественная топология DAG уже приводит к частичной упорядоченности блоков: если в DAG есть путь от блока X к блоку Y, то блок Y был доказуемо создан до блока X и, следовательно, должен предшествовать X в глобальной очередности, и наоборот. Таким образом, нам нужно только доопределить правило упорядочивания блоков, создаваемых параллельно, т. е. блоков из такого набора, что в графе нет пути, который бы соединял какие-либо два из них.

Эта парадигма началась с протоколов на основе blockDAG, разработанных в Еврейском университете (Inclusive , SPECTRE и PHANTOM); каждый из них предлагает алгоритм, который определяет порядок блоков в DAG, проходит по DAG в этом порядке и отбрасывает транзакции, конфликтующие с предыдущими принятыми (на самом деле, SPECTRE делает кое-что послабее; см. поясняющую статью соавтора).

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

Протоколы blockDAG, такие как SPECTRE и PHANTOM, позволяют избежать проблем, связанных с высокой частотой появления блоков-сирот. Это дает массу преимуществ:

Позволяет добиться времени подтверждения транзакций порядка секунд — по крайней мере, при наличии видимых двойных трат и конфликтов.
Обеспечивает большую пропускную способность по транзакциям, ограниченную только скоростью магистрального канала сети и конечных точек; а это влечет за собой низкий уровень комиссий за транзакции.
Способствует децентрализации майнинга, позволяя добывать порядка 100 000 блоков в день, что снижает стимулы к майнингу на пуле вместо майнинга соло.
Позволяет избежать риска отбрасывания вновь найденного блока, что дает множество дополнительных преимуществ (например, совместимость с L2).
Устраняет «эгоистичный» майнинг, за счет вознаграждения всех блоков, без различия между блоками «в цепочке» и «вне ее».

BlockDAG против безблоковых DAG

Почти каждая имеющаяся на рынке криптовалюта на основе DAG (IOTA, Byteball, Nano и т. д.) отклонилась от парадигмы блокчейна Сатоши не только потому, что использует DAG, но и из-за дизайна экономики проекта: некоторые ограничили своим пользователям майнинг, другие вообще устранили майнинг с доказательством работы, многие не имеют комиссий за транзакции — и практически все не имеют блоков, объединяющих отдельные транзакции. Эти проектные решения могут работать в связке с DAG, но они не зависят от DAG. На самом деле использование DAG в этих проектах является, пожалуй, их наименее определяющей характеристикой.

Растущая популярность этих DAG-систем сильно повлияла на восприятие DAG сообществом. С одной стороны, есть ярые сторонники, которые рекламируют технологию DAG как «блокчейн 3.0», а с другой — скептики, которые отвергают ее как нежизнеспособную. Однако почти все хвалят или критикуют экономические аспекты дизайна существующих протоколов DAG, которые, однако, никак не относятся к собственно DAG.

Например, в своих недавних вопросах и ответах (https://www.youtube.com/watch?v=lfgMnbb5JeM) известный эксперт по блокчейну Андреас Антонопулос описывает DAG как «альтернативный механизм консенсуса», противопоставляемый доказательству работы. По его словам, «если у вас нет децентрализованного майнинга с доказательством работы, блоки вам на самом деле не нужны. Вы можете просто сцеплять транзакции вместе, что есть основа направленных ациклических графов».

Но, как объяснялось выше, DAG — это не про замену доказательства работы или блоков. DAG — это просто математическая структура, которая используется несколькими проектами, которые отклоняются от PoW-системы Сатоши. А вот blockDAG — это применение DAG в системе на основе концепции Накамото (в частности, с доказательством работы), только c перепроектированными структурой данных и слоем консенсуса.

Брэм Коэн из BitTorrent и Chia в своем язвительном твите попал точнее:

https://twitter.com/bramcohen/status/958535459969249280 «Направленный ациклический граф — это структура данных, а не тип доказательства работы. Она используется в Git-е, уже с 2005-го года, а появилась еще задолго до этого. Она не новая, не примечательная, и не захватывающая».

Действительно, DAG есть чисто структурная альтернатива цепочке — и цепочка тоже не что-то новое, примечательное или захватывающее. Что сделало систему Сатоши новой — так это ее общая конструкция: майнинг с доказательством работы, блоки, транзакции и протокол, который достигает консенсуса в инклюзивной (permissionless, см. http://chainmedia.ru/newcomers/permissioned-vs-permissionless-blockchains/ — прим. пер.) системе и стимулирует участие в ней. Системы BlockDAG, такие как SPECTRE и PHANTOM, обобщают инновационную конструкцию Сатоши, а новизны достигают благодаря своим уникальным протоколам консенсуса для необратимого упорядочения DAG, и позволяют избежать компромиссов между безопасностью и масштабируемостью, неизбежно возникающих в блокчейнах из-за блоков-сирот.

Примечания:

¹ Доказательства этого утверждения см. в работах [ a ][ b ][ c ]

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

Введение в парадигму blockDAG