Коротко

Актуальность DAG-ДРС (децентрализованных и/или распределённых систем) возрастает, но считать их блокчейнами, к сожалению или счастью, нельзя: это иной род систем. В остальном — авторы оригинальной статьи проделали колоссальную работу, которую точно стоит узнать сегодня… 

Аннотация

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

Однако в этой области до сих пор не хватает систематических работ, обобщающих технику DAG. Чтобы восполнить этот пробел, данная систематизация знаний (SoK) представляет собой всеобъемлющий анализ блокчейн-систем на основе DAG. Деконструируя открытые системы и анализируя научные исследования, определили основные компоненты и характерные особенности систем, а также описали подход к созданию DAG. С учётом этого — анализируем безопасность и производительность нескольких ведущих систем, а затем обсуждаем и сравниваем их с современными технологиями (масштабирование блокчейна). Далее — определяем открытые проблемы, чтобы подчеркнуть потенциал решений на основе DAG, и указываем перспективные направления для будущих исследований.

1. ВВЕДЕНИЕ

Ограничения. Блокчейн становится развивающейся технологией для реализации распределённых бухгалтерских книг [Всё же здесь следует сразу не согласиться с авторами: блокчейн содержит распределённые системы внутри себя — ноды, скажем, но в целом это система децентрализованная (decentralised), тогда как DAG — именно распределённая (distributed): Menaskop]. Растущий интерес к блокчейну [в данной статье мы рассматриваем «блокчейн» как общий термин, охватывающий типы и модели, основанные на одной и той же технологии. Для простоты мы игнорируем разницу между «блокчейном» и «распределённой книгой». Кроме того, мы иногда используем «DAGs» для краткого обозначения «блокчейн на основе DAG». Прим. Menaskop: конечно же, такой подход — в корне НЕ верен, но оставим это на совести авторов оригинального материала] привлёк к себе широкое внимание. Благодаря своему огромному потенциалу для решения критических проблем безопасности и доверия в различных распределённых средах, технология блокчейн быстро развивается [1][2] — [все источники будут в последней части: Menaskop], а производные темы превратились в хорошо изученную область [3][4] как в промышленности [5][6], так и в научных кругах [7][8]. Однако огромное влияние блокчейна способствует притоку участников, вступающих в игру. Постоянно растущий трафик приводит к неизбежным катастрофическим перегрузкам из-за узких мест в производительности, включая медленное подтверждение, низкую пропускную способность и плохую масштабируемость. По сравнению с большинством централизованных систем, эти факторы не могут быть легко улучшены в системах блокчейн, которые требуют децентрализации в качестве приоритета.

Некоторые исследования поднимают вопрос о трилемме блокчейна [9] и компромиссе [10], утверждая, что децентрализация, безопасность и масштабируемость не могут идеально сосуществовать в системе блокчейна. Например, одним из основных препятствий для консенсуса Накамото (NC) [1] является снижение безопасности при увеличении скорости генерации блоков. Безопасность правил выигрыша по самой длинной цепи NC требует, чтобы честные узлы знали о блоках других узлов вскоре после создания блока. Если скорость создания блока превышает время распространения, то одновременные блоки увеличивают вероятность возникновения развилок. Для уменьшения узкого места в производительности было предложено множество подходов с разных точек зрения.

Потенциальные решения. Эти подходы включают методы, основанные на технике шардинга [11][12], протоколах второго уровня [13], технологии сайдчейна [14], гетерогенной структуре [15], гибридных решениях консенсуса [16] и вспомогательных методах [17], таких как изменение жёстко закодированных параметров [18] или техника кросс-чейна [19]. Шардинг разделяет ожидающие транзакции на более мелкие шарды и делает их обработку параллельной, но из-за асинхронизации трудно достичь консенсуса между шардами. Межцепочечные протоколы помогают частично решить эту проблему, устанавливая каналы между несколькими шардами (горизонтальный шардинг [19]). В качестве жертвы, эти верхнеуровневые протоколы неизбежно приводят к тяжелым и избыточным системам, ослабляя эффективность и стабильность.

Протоколы второго уровня позволяют участникам выполнять вне-цепочечные (оффчейн) транзакции посредством приватной связи, а не широковещательной рассылки по всей сети. Вместе с такими особенностями возникает проблема: как правильно и эффективно гарантировать достоверность и согласованность между транзакциями вне цепи и в цепи?

Техника боковых цепочек (сайдчейнов) привязывает вспомогательные цепочки для вовлечения большего количества транзакций. Гетерогенная структура добавляет новые типы блоков, чтобы назначить им различные задачи. Гибридное решение консенсуса объединяет несколько фундаментальных механизмов консенсуса вместе (PoX+BFT [15][16][20]) для интеграции их преимуществ. Изменение жёстко закодированных параметров, например, прямое увеличение объема блока с 1М до 8М в BCH [18]. Однако эти методы всё ещё основаны на линейном магистральном протоколе, что ограничивает сферу их применения. Поэтому радикальная модификация — реконструкция цепей на основе базовой структуры и топологии — становится новым решением.

Подход на основе DAG. Системы блокчейн с линейной структурой хранят все транзакции/блоки в одной цепочке. Параллельные транзакции/блоки конкурируют за одну действительную позицию в каждом раунде. Такая конструкция неизбежно приводит к медленному подтверждению из-за конкурирующих майнеров, конфликтующих транзакций и напрасных вычислений. Производительность системы можно только искусственно подавить (например, отрегулировать время подтверждения), чтобы каждый блок был полностью присоединен до прихода следующего. В системе может быть задействовано очень мало блоков-сирот [имеются ввиду orphan blocks: Menaskop]. В связи с этим стремление обеспечить возможность одновременного проведения/подтверждения большего количества транзакций мотивирует появление блокчейн-систем на основе DAG [21][22][23][24]. Они структурируют транзакции/блоки в виде топологии графа, чтобы изменить фактические операции.

Системы на основе DAG могут повысить производительность, поскольку требуют меньше затрат на связь, вычисления и хранение. Однако источники существующих проектов и решений с открытым исходным кодом разрозненны и неорганизованны. Различные базовые понятия в DAG (например, значение вершины, консенсусный подход, последовательность порядков) до сих пор неясны, а потенциальные проблемы не определены. Отсутствует организованный и структурированный систематический обзор для новичков. Несколько исследований привлекают внимание к этой области, но работы либо грубы в резюме [25][26][27][28][29][30][31][32], поверхностны в анализе [17][33][34][35][36][37][38][39][40], либо неполны в оценках [41][42][43][44].  

[Наш] Вклад. В данной работе попытались обобщить основные знания о структурных изменениях в системах блокчейн и рассмотреть современные системы блокчейн на основе DAG с соответствующими механизмами и свойствами. Чтобы стимулировать будущие исследования, мы также предоставляем многогранные обсуждения и сравнения с методами масштабирования блокчейна. Кроме того, мы обобщаем нерешённые проблемы, существующие в современных системах DAG, надеясь привлечь внимание к исследовательским задачам в этой области. Мы начинаем с серии простых вопросов, чтобы дать читателям краткое руководство к действию.

• Q1. Что такое блокчейн на основе DAG? 
• Q2. Как они структурируют бухгалтерские книги?
• Q3. Как осуществляется консенсус?
• Q4. Каковы желаемые свойства?
• Q5. Насколько они безопасны?
• Q6. Каково улучшение производительности?
• Q7. Чем они отличаются от других методов? 
• Q8. Каковы проблемы исследования?

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

Обзор DAG. Во-первых, в разделе 2 мы рассмотрим достаточное количество исследований, посвященных блокчейн-системам на основе DAG, охватывая темы разработки протокола, анализа и обсуждения, оценки и моделирования, усовершенствования, применения и косвенного анализа.

Идентифицированные типы. Во-первых, мы определяем модель для математического описания систем на основе DAG в разделе 3, которая содержит два элемента в различных измерениях. Затем мы получаем шесть типов структур, объединяя каждый элемент вместе. Наконец, мы собираем и классифицируем существующие исследования по выделенным нами типам.

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

Анализ. Далее — в разделе 5 мы анализируем свойства, в разделе 6 — конкурентоспособность, а в разделе 7 — производительность. Эти разделы позволяют глубоко понять принципы проектирования, особенности систем и уникальные свойства. Читатели могут получить полное представление о собранных системах благодаря этому многомерному анализу.

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

Резюме. В качестве резюме можно сказать, что наша система анализа подробно рассмотрела перечисленные вопросы. Обсуждение элементов модели DAG даёт нам простую, но полную классификацию существующих систем на основе DAG, отвечая на вопросы Q1 и Q2. Деконструкция механизмов консенсуса показывает нам, как современные системы на основе DAG работают со своими уникальными знаками, отвечая на вопросы Q3. Анализ свойств, ценных бумаг и производительности позволяет нам понять Q4, Q5 и Q6. Обсуждения, сравнения и проблемы отвечают на вопросы Q7 и Q8. Подробные сведения о возникновении, ходе работы и применении приведены в разделах 8, 9.

Выводы. Наша работа обеспечивает дорожную карту для изучения прикладных DAG-систем. На основе нашего тщательного анализа предлагаем несколько выводов в этой части: a) Блокчейн на основе DAG всё ещё далёк от коммерческого применения из-за их несовместимого дизайна, отсутствия стандартов, ненадёжной (модели) безопасности, различной производительности и незаконченных реализаций. b) Структура DAG имеет потенциал для улучшения масштабируемости и производительности, но неизбежно жертвует некоторыми свойствами, такими как согласованность или окончательность. c) Системы на основе DAG отличаются друг от друга. Единая формализованная модель вряд ли может охватить все ключевые моменты. Наоборот, свободная и неформальная модель приносит большую пользу для лучшего понимания. г) Хотя применение структуры DAG к классическим распределённым системам и системам блокчейн является довольно сложной задачей, многие исследования с предложенными ими системами значительно продвинулись и улучшились. Мы считаем, что в скором времени появятся новые интересные схемы/протоколы/решения. 

2. ОБЗОР БЛОКЧЕЙНОВ НА ОСНОВЕ DAG

В этом разделе представлен краткий обзор существующих исследований систем DAG. Ниже приведены три аспекта.

Возникновение и эволюция. Направленный ациклический граф (DAG) представляет собой конечный направленный граф без направленных циклов в математической и компьютерной областях. Благодаря уникальной топологии, он часто используется в качестве базовой структуры данных и применяется в различных алгоритмах, таких как поиск кратчайшего пути в навигации и сжатие данных в хранении. Впервые концепция была введена в основные блокчейны Сомполинским и др. в работе GHOST [21][45], направленной на решение проблемы параллелизма путём разрешения транзакций, структурированных в деревья. Улучшенная версия [46] была применена в Ethereum [2] в качестве основного механизма консенсуса. Протокол GHOST и его варианты позволяют всем блокам цитировать более одного родительского блока, а все типы ссылок могут быть преобразованы в вознаграждения в качестве стимулов. Таким образом, необратимость цепочек может быть усилена и за счёт блоков, находящихся вне цепочки. После этого Лернер и др. в DAGCoin [47] отметили смещение гранулярности с уровня блоков на уровень транзакций. Транзакции берут на себя задачи блоков, непосредственно подтверждая ожидающие транзакции и поддерживая порядок последовательности. Следовательно, эффективность была скачкообразной из-за отказа от упаковки и конкурирующих шагов. IOTA [22] и ByteBall [23], унаследовавшие концепцию без-блочности, были предложены с полной реализацией с открытым исходным кодом и лидируют на рынках до сих пор. В последующие времена в DAG было добавлено несколько модификаций и обновлений. Spectre [24] нацелен на создание системы, позволяющей одновременное создание блоков. Hashgraph [48] предложил блокчейн на основе пермиссионного графа с консенсусом, вдохновленным протоколами в стиле BFT [49]. Nano [50] предложил так называемую блок-решетчатую структуру для реализации немедленной и асинхронной обработки данных, позволяя пользователям вести свои собственные легкие учетные записи. Conflux [51] вернул блоки в систему с целью полной линейной последовательности. Другие примеры будут рассмотрены в последующих разделах.

Анализ и оценки. В открытых и опубликованных работах представлены основные шаблоны проектирования. Сопутствующие исследования, основанные на них, имеют различные точки зрения. Несколько работ предоставляют анализ по компонентам, включая темы о свойствах базиса [52][53][54], разработке консенсуса [29][55], выборе вершины [56], выборе “свидетелей” [28], криптографическом хэш-алгоритме [57], метках времени [58], схеме подписи [59], модели памяти [60], вероятности ожидания [61], разработке компонентов [62], оплате [63] и т. д. В то время как некоторые исследования основаны на свойствах, охватывающих справедливость [26], согласованность [64], анонимность [65][66][67], производительность [44][35][44], реализуемость [41], устойчивость [42], стабильность [52], тонкий клиент [68], безопасность [43][69][70][71][72][73][74][75], стимулы и вознаграждения [76] и т.д. Обсуждения [25][27][77][36][38] и сравнения [39][37] отдельных систем (например, IOTA, Byteball, Hashgraph, Nano) выявили ряд особенностей и проблем, но они оказались технически или теоретически недостаточными. В углубленном анализе используются различные методы и инструменты, такие как создание структуры анализа [26] и преобразование сложной среды в симуляцию [34][33][53][78]. Между тем, также было предложено несколько типов формального анализа, включая краткие модели с качественными аргументами [79][45][45], анализ формальной модели [80][81][82] и формальную модель с математической индукцией [83]. Кроме того, для дальнейшего использования предложено несколько модифицированных протоколов [84][85] и улучшенных протоколов [86][87][88].

Применения. Системы, основанные на DAG, в основном используют распределённые приложения (DAPP) [Прим. Menaskop: опять же — это верно, но под dApp — обычно понимают децентрализованное приложение] с высокой производительностью и низкой стоимостью. Существующие решения можно условно классифицировать по уровням их комбинирования. Прямая интеграция строительных блоков с базовой сетью [89][90][91] помогает получить почти такие же свойства и преимущества DAG, но требует специальных навыков разработки и дорогостоящих устройств (на уровне “железа”). Создание приложений через официальные компоненты (например, Qubic [92], MAM [93] в IOTA) является альтернативным выбором для разработчиков [90][94][95]. Это упрощает процессы развёртывания и сопровождения, но в определённой степени снижает гибкость и кастомизацию. Кроме того, рассматриваются различные конкретные сценарии, которые включают области Интернета вещей [96][97], управления данными [98], автомобильных приложений [99][100][101], планирования зарядки [102], M2M коммуникаций [103][104], производства [105], инфраструктуры умного дома [91], точного сельского хозяйства [90] [Прим. Menaskop: в русском языке также используют термин “высокоточное земледелие” и аналоги], P2P торговли энергией [106], интеллектуальные транспортные системы [89], система мониторинга качества воздуха [107], интеллектуальные транспортные услуги [90][108], система сенсорных узлов [109], управление качеством данных [110], электронное здравоохранение [94][95][111][112], интеллектуальная сеть [113], система управления с обратной связью [114], платформа баз данных [115], система голосования [116][117][118], сеть именованных данных [119], умный город [120] и др. Следует отметить, что предложенные схемы не могут просто выполнить многогранные требования. Они должны использовать дополнительные технологии, такие как файловая система IPFS [121] для хранения данных, Доказательство с нулевым разглашением для обеспечения конфиденциальности, контроль доступа для аутентификации [98] и т.д. Наконец, важным фактом, основанным на вышеупомянутых решениях, является то, что все комбинации, направленные на реализацию DAPP, всё ещё остаются на стадии Proof of Concept (PoC), далекой от практической реализации и коммерческих приложений. 

Рекомендации. Для обзора обобщаем соответствующие работы, чтобы дать полное представление о DAG. Среди ссылок, приведённых в данной работе, часто изучаемые темы включают три аспекта: модели протоколов (включая как проекты в промышленности, так и схемы в академической среде); анализ, сравнение и оценки; потенциальное применение к реальным сценариям. Несколько исследований предлагают улучшенные предложения или схемы, а несколько работ посвящены технике или анализу (косвенно), связанному с DAG. Подробные распределения приведены в таблице №1. 

3. Моделирование

В этом разделе даётся определение неформальной модели DAG и сетевой модели. Затем мы классифицируем существующие системы на шесть типов соответственно.

3.1 От классического блокчейна к DAG

Блокчейн записывает действия в виде транзакций. Транзакции организуются в иерархическую структуру в виде блока, а блоки располагаются в необратимо упорядоченной последовательности. Новые блоки могут быть присоединены только к основной цепочке, которая строго упорядочена предшественниками и преёмниками. Хотя механизмы консенсуса варьируются от системы к системе, классические блокчейны основаны на одной и той же линейной структуре цепи. Транзакции не могут быть подделаны или скомпрометированы благодаря глобальному мониторингу, разделяемому всеми участниками, следовательно, обеспечивается целостность и прослеживаемость. Существующие модификации блокчейна можно найти в [45][46][177][178].

Узкое место в производительности линейной структуры в основном связано с механизмами консенсуса. В частности, группа узлов конкурирует за право упаковки блоков с помощью таких методов, как выборы лидера (BFT-стиль), решение головоломок (PoW), проведение ставок (PoX) и т.д. Только победители могут определять действительность и подтверждение транзакций, в то время как оставленные транзакции откладываются в пул или отбрасываются из цепи. Одновременное добавление блоков вызывает больше конфликтов. В отличие от этого, структура на основе DAG направлена на обеспечение возможности подтверждения нескольких транзакций за один раунд. Каждый блок (транзакции/блоки/события) бухгалтерской книги может ссылаться на более чем один родительский блок, а также на множество последующих блоков. Такая структурная схема поддерживает одновременные операции. Несколько узлов могут одновременно добавлять данные в бухгалтерскую книгу, тем самым значительно повышая пропускную способность.

3.2 Модель на основе DAG

Направленный ациклический граф G состоит из множества точек V и множества рёбер E. Во-первых, каждый элемент в множестве точек соответствует единице. Единица может быть инстанцирована как транзакция Tx ∈ T, блок B ∈ B или событие E ∈ E в протоколах, где T, B, E представляют собой наборы элементов. Во-вторых, элемент в краевом множестве — кортеж (𝑢, 𝑣), который представляет собой отношения частичного порядка между двумя точками 𝑢 и 𝑣. Отношения, в большинстве случаев, указывают на то, что одна из единиц прямо/непосредственно ссылается на другую единицу. Например, обозначение 𝑢 ← 𝑣 означает, что 𝑣 подтверждает/проверяет/свидетельствует/видит 𝑢, где {𝑢,𝑣} ∈ V. Мы определяем модель на основе DAG с двумя свойствами следующим образом:

Определение №1 (модель на основе DAG). Модель блокчейна на основе DAG определяется следующим образом:

G = (E, V)†‡, где

V = {𝑢 |𝑢 ∈ T ∪ B ∪ E},

E = {(𝑢,𝑣) |𝑢 ← 𝑣 ∧ {𝑢,𝑣} ∈ V}.

† : ∀𝑢 ← 𝑣 ⇏ 𝑣 ← 𝑢;

‡:Предположим, что𝑢𝑖 ={𝑢1,𝑢2,…,𝑢𝑙}⊆V,

∀𝑖,𝑗,…,𝑘∈[1,𝑙-1],𝑘>=…>=𝑗>=𝑖, если

𝑢𝑖 ← 𝑢𝑗, 𝑢𝑗 ← 𝑢𝑘, …, то,𝑢𝑖 ← 𝑢𝑘 не существует.

Здесь операция «𝑎|𝑏» означает, что 𝑎 удовлетворяет условию 𝑏. Обозначение «←» представляет действие 2 , которое происходит в сети. Свойство означает (i) однонаправленность †: ссылки указывают в одном направлении; (ii) ацикличность ‡: в графе не существует петель. Эти свойства позволяют единицам в сети быть прикреплёнными и упорядоченными.

Ключевые параметры. Мы используем несколько качественных показателей в качестве основных терминов для описания систем. В отличие от этого, мы опускаем количественные параметры (такие как время подтверждения, плата за транзакцию, время распространения, например). Эти параметры трудно оценить из-за отсутствия реализаций.

Степень вхождения/выхождения, обозначаемые как (|𝐼𝑛|,|𝑂𝑢𝑡|), описывают количество связей каждой единицы. Степень вхождения |𝐼𝑛| представляет собой число преёмников определенной единицы, а степень выхода |𝑂𝑢𝑡 | показывает число предков единицы. Модель транзакции описывает, как завершить транзакцию. Было выделено три типа моделей. UTXO [1] обозначает неизрасходованные выходы. Транзакция в модели UTXO является атомарной и неразделяемой. Каждая операция должна быть завершена через эти транзакции. Модель счёта [2] поддерживает поле баланса в своей структуре данных. Транзакции завершаются через изменения в балансе пользователя. Пользователь изменяет свои данные в локальном представлении, а затем синхронизирует их с сетью. Полная передача токенов в парной модели [50] состоит из двух связанных транзакций: транзакция «отправить», подписанная отправителем, и транзакция «получить», подписанная получателем. Эти две транзакции должны происходить в течение пренебрежимо малого промежутка времени.

Доверие — кумулятивное число, которое используется для того, чтобы показать уверенность в том, что единица будет проверена последующими единицами как напрямую, так и косвенно. Оно также отражает вероятность того, что единица будет выбрана в следующем раунде. Параметр может быть представлен в различных формах в системах, таких как кумулятивный вес в IOTA [22], свидетель в Hashgraph [48], счёт в Phantom [127].

Идентификаторы используются для определения единицы в сети. Каждая система имеет свои индивидуальные параметры. К таким параметрам относятся: высота (h) — длина пути, где путь начинается от генезисной транзакции до определённой транзакции; глубина (𝑑) — самый длинный путь обратной направленности, начинающийся от вершины транзакции до определённой транзакции; индекс цепи (𝑖) идентифицирует цепь с индексным номером, когда в сети сосуществуют несколько цепей; логические часы (𝑡) играют роль фиксации хронологических и причинно-следственных связей. 

3.3. Идентифицированные типы

Абстрактная модель описывает протоколы в теоретической и математической форме. Сначала мы определяем точные представления единиц V и рёбер E в модели. Эти элементы определяют структуру и топологию системы на основе DAG. Отсюда мы начинаем нашу схему анализа.

Представление единиц. Оно косвенно показывает базовую структуру системы, либо транзакции, либо события, либо блоки. У нас есть два типа вариантов: 1𝑜𝑑 и 2𝑜𝑑. Первый представляет собой запрос, который обрабатывается немедленно, как только он получен, без необходимости ждать новых запросов от коллег. К формам этого типа относятся транзакции и триггерные события. Второй представляет собой запрос, который требует дальнейшей обработки. В большинстве случаев запросы этого типа предварительно вычисляются или упаковываются мощными сторонами (например, майнером или валидатором), а затем распространяются. Формы этого типа содержат блоки и события.

Топология сети. Одного ребра может быть недостаточно для отображения всех отношений в системе на основе DAG. Система обычно цепляется набором рёбер. В соответствии с тенденциями (сформированными графами) выделяют три типа типологии графов, а именно 𝐷ivergence, 𝑃arallel и 𝐶onvergence, сокращенно D, P, C, соответственно. Более подробно, 𝐷ivergence означает, что единицы разбросаны в непредсказуемых направлениях без заранее определенного порядка. 𝑃arallel означает, что узлы поддерживаются в виде нескольких цепей группой узлов. 𝐶onvergence означает, что узлы организованы в определенной последовательности или имеют тенденцию к сближению в определенной последовательности.

Единичное представление указывает на структуру систем. Оно также определяет модель исполнения бухгалтерской книги, указывая, как транзакция завершается в DAG. Мы приводим более подробную информацию о моделях транзакций. Как правило, выделяют два типа: модель на основе UTXO и модель на основе счета (acct). Первая означает, что все операции должны быть реализованы через атомарные транзакции. Пользователи могут рассчитать баланс, проследив историю предыдущих транзакций. Во втором случае каждый пользователь имеет счет, а транзакция конфигурируется как одно из полей в его структуре. Пользователи рассчитывают баланс непосредственно на своих счетах. Это важная особенность для понимания глубинной структуры систем, связанных с DAG.

Топология в основном фокусируется на возможном направлении этих единиц в сети из-за неопределенности подтверждения единиц в системах DAG. Блоки, которые первоначально распространяются в нескольких направлениях, но в конечном итоге сходятся к основной цепи, все еще могут быть классифицированы как кон- вергенция. Например, блоки в GHOST [45] присоединяются к своим родителям беспорядочно, но в конечном итоге они структурируются в основную цепь. Эта метрика косвенно показывает законченность и согласованность системы.

Затем мы выделяем шесть типов, основываясь на комбинациях параметров в каждой метрике. Мы собрали 30+ систем блокчейн на основе DAG (с 2011 года по настоящее время) и классифицировали эти системы по вышеупомянутым типам. Подробная классификация приведена в таблице №2: 

(𝐷, 1𝑜𝑑 ). Для лучшего понимания описываем ситуации терминами, часто используемыми в блокчейне. Этот тип означает, что структура данных не содержит блоков, а топология представляет собой естественный граф. Транзакции осуществляются в равных и справедливых сущностях. В качестве примера можно привести системы IOTA [22], Graphchain [79] и Avalanche [130]. Мы обозначаем этот тип как тип I.

(𝐷, 2𝑜𝑑 ). Транзакции должны быть организованы в блоки для упаковки, а топология представляет собой естественный граф. В качестве примеров можно привести системы Spectre [24], Phantom [80] и Meshcash [81]. Этот тип обозначается как тип II.

(𝑃, 1𝑜𝑑 ). Структура данных является безблочной, а транзакции обслуживаются отдельными узлами, которые образуют несколько параллельных цепочек. В качестве примера можно привести системы Nano [50], Hashgraph [48], DLattice [170], Jointgraph [171], Chainweb [147], Aleph [167], Vite [139], Caper [179] и протоколы класса Lachesis [122][123] [124][125][126]. Этот тип обозначается как Тип III.

(𝑃, 2𝑜𝑑 ). Транзакции структурируются в блоки для формирования параллельных цепочек. К таким системам относятся Prism [131], OHIE [145], Blockmania [132], Blockclique [180], Eunomia [146], Dexon [134] и PARSEC [149]. Мы обозначаем этот тип как Тип IV.

(𝐶, 1𝑜𝑑 ). Структура данных безблочная, а транзакции объединяются в главную цепочку. Примерами являются Byteball [23], Haootia [82] и JHdag [29]. Этот тип обозначается как тип V.

(𝐶, 2𝑜𝑑 ). Транзакции структурированы в блоки с основной цепочкой. К таким системам относятся GHOST [45], Inclusive [46], CDAG [148], Conflux [51][140][141] и StreamNet [136]. Мы де обозначаем этот тип как Тип VI.

Сравнение с предыдущей классификацией. Предыдущие классификации являются крупнозернистыми, что заставляет новичков и исследователей сбиваться с толку, например, (такие понятия, как:) блок-решётка, упомянутая в [134], blockDAG в [180], GHOSTDAG в [80], Lattice-based DAG в [15] и т. д. Мы полагаем, что эти пробелы связаны с отсутствием классификационных метрик или измерений. Вместо этого классифицируем существующие системы в тонких формах по двум измерениям (топология, создаваемая рёбрами, и единицы, обозначающие структуры). В результате мы обнаружили, что так называемые TxDAG/blockDAG названы по их представлениям единиц, а термины GHOSTDAG/TreeDAG основаны на их типологии. Наш метод классификации, естественно, приводит к тому, что каждый термин в предыдущих классификациях отображает более одного типа в нашей. Например, структура на основе решётки, или в равной степени параллельные цепочки, охватывает как тип III, так и тип IV, определённые в нашем методе… 

[Продолжение следует…]