Напомню

Первая часть — по ссылке, а мы — продолжаем…

4. КОНСЕНСУСЫ

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

4.1 Деконструированные компоненты

Достижение консенсуса предусматривает три аспекта: кто проводит консенсус, как они действуют и какова механика взаимодействия. Мы деконструируем консенсус на несколько отдельных компонентов для лучшего понимания различных систем и улавливания их общих черт. Узлы, которые могут проводить консенсус, составляют группу консенсуса, называемую комитетом. Открытость показывает, открыт ли этот комитет для каждого узла. Выбор членов определяет правила вступления в комитет. Распределение единиц, правило расширения и разрешение конфликтов определяют методы достижения соглашения. В разделе «Основные методы» выделены отличительные методы в каждой системе. Подробные аспекты обсуждения изложены следующим образом.

Открытость показывает, может ли произвольный узел запустить алгоритм консенсуса без разрешения. Включены два типа выбора, а именно: без разрешения и с разрешением. Система DAG без разрешения означает, что каждый узел может присоединиться к комитету или покинуть его без ограничений. Размер комитета является динамическим. Система DAG с разрешением означает, что новые узлы должны получить разрешение на вступление в комитет. Разрешённые условия необычно предопределены командами основателей или членами ядра. Размер комитета фиксирован.

Выбор членов определяет правила, которые используются для отбора узлов в комитет. Для системы без разрешений каждый узел может участвовать в соревновании за производство единиц. Узлы ранжируются по приоритетности в соответствии с принадлежащими им ресурсами. Ресурсы включают вычислительную работу (Proof of Work, PoW ), долю (Delegated Proof of Stake, PoS/DPoS), голос (голосование за благоприятные узлы, Elect). Узел, владеющий/получивший наибольшее количество ресурсов, имеет высокую вероятность победы в соревновании. Для разрешенной системы узлы должны доказать, что они могут соответствовать заданным правилам. Члены комитета назначаются своими командами-разработчиками (Assign).

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

Позиционирование устройства — способ определения местоположения устройства в сети. Этот шаг необходим для сортировки блоков в общем линейном порядке. В классических блокчейн-системах определение местоположения блока может ссылаться на параметр высоты (h). Однако определение местоположения блока в системах DAG затруднено. В системах, основанных на топологии 𝐷, неструктурированные блоки делают практически невозможным точное определение местоположения блока в расширяющейся сети. Только когда блоки сортируются в линейную последовательность и закапываются достаточно глубоко, получается уникальное местоположение в виде высоты (h). В отличие от этого, в системах, основанных на топологии 𝑃, цепочки с уникальными индексами (𝑖) структурируются параллельно. Единица может быть позиционирована через ортогональные параметры (𝑖, h). Аналогично, для систем, основанных на топологии 𝐶, любой блок может быть грубо расположен по ключевым блокам для первого шага на главной цепочке, а затем точно искаться внутри этих блоков по под-параметрам, таким как хэш или метка времени.

Правило расширения существует для расширения цепочек/графов и разрушения связей. Разрушение связей происходит, когда эквивалентные вилки (подграфы) конкурируют за одного победителя, что необходимо для поддержания согласованности путём удаления перекрывающихся ветвей и уменьшения перегрузки данных. Правила расширения завершают основные механизмы консенсуса. Реализуемые методы включают консенсус Накамото (𝑁 𝐶 ) по самой длинной цепи, вариант консенсуса Накамото (variant-NC) по самому тяжеловесному поддереву, асинхронное византийское соглашение (async-BA), классические протоколы PBFT (PBFT ) и его вариации (smpl-PBFT ), алгоритм выбора вершины (TSA), некоторые специальные алгоритмы, такие как жадный алгоритм (GA), рекурсивный алгоритм обхода (RTA) и алгоритм выборки. Для систем, не имеющих явных правил, мы используем естественные для (конкретного) случая обозначения.

Решение конфликтов представляет набор параметров, которые определяют приоритет конфликтующих единиц. Параметры включают три типа: а) уверенность каждой единицы, инстанцирования формами weight (вес), confidence (доверие), fee (комиссия), score (очки), fitness (соответствие); б) случайный маяк типа Hash; и в) естественная последовательность, содержащая логические часы, внешний вид и ранг. Иногда решение принимается влиятельными авторитетами, такими как лидер и координатор. Мы обозначаем их как доверенные роли (ДР). Кроме того, решение конфликтов отличается от устранения ничьей по сфере применения. Разрушение связей происходит на уровне (главных) цепочек, тогда как разрешение конфликтов влияет на каждую отдельную единицу и в основном происходит в алгоритме сортировки с целью упорядочения единиц при линеаризации. Заметим, что в некоторых системах и разрушение связей, и разрешение конфликтов интегрированы с правилом расширения. Таким образом, механизм консенсуса достигает соглашения за один шаг.

В разделе «Особенные методы» представлены методы, которые отличаются от других систем. Мы выделяем одну главную особенность каждой системы, чтобы отличить их от аналогов.

4.2. Консенсус каждого типа

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

Консенсус в системах типа I. Системы типа I являются безблочными. Топология транзакций представляет собой естественный расширяющийся граф. К системам этого типа относятся IOTA [82], Graphchain [79] и Avalanche [130].

IOTA [22] — сеть без разрешений, где каждый узел может свободно участвовать и покидать её. В качестве структуры данных IOTA использует модель UTXO. Благодаря этой структуре IOTA создаёт систему посредством транзакций. Транзакции, осуществляемые узлами, составляют набор сайтов tangle, который является книгой учёта для актуальной истории транзакций. Все узлы в сети IOTA хранят копию tangle и достигают консенсуса по его содержанию. В частности, расширение tangle происходит по правилу 3 , согласно которому для одобрения двух транзакций-предшественников требуется один совет (пендинг/неодобренная транзакция). Таким образом, пользователи, выдающие транзакцию, вносят свой вклад в безопасность системы. Однако, поскольку советы постоянно генерируются и присоединяются к tangle, сформированные подграфы неизбежно распространяются в разных направлениях. Чтобы предотвратить раскол сети на изолированные клики, алгоритмы выбора наконечников необходимы для обеспечения стабильности. Алгоритмы помогают поддерживать однонаправленный граф, контролируя способ выбора вершин. В [22] представлены три типа механизмов: равномерный случайный, невзвешенный случайный и взвешенный случайный. Все эти механизмы основаны на статистической вероятности для моделирования реальных сценариев. Наиболее продвинутым механизмом является алгоритм взвешенного случайного шага, который представляет собой применение алгоритмов Марковской цепи Монте-Карло (MCMC). MCMC может быть преобразован в другие стратегии с помощью 𝛼, настраиваемого параметра, используемого для контроля эффективности. Когда 𝛼 сходится к 0, выбор наконечника становится равномерно случайным, а когда к 1, выбор наконечника становится детерминированным. Кроме того, мы вводим два типа модифицированного выбора наконечников в качестве улучшений:

G-IOTA [86] изменяет правило (взвешенное правило выбора случайного ходового наконечника), согласно которому «наконечник» может одобрить три транзакции предков за один раз, вместо двух. Дополнительный совет выбирает оставленный совет в tangle, который используется для повышения справедливости с точки зрения доверия к транзакциям для всех честных транзакций. Алгоритм позволяет оставленным советам вновь получить возможность быть одобренными входящими советами. G-IOTA далее рассматривает механизм стимулирования для наказания конфликтующих транзакций и вводит механизм взаимного контроля для уменьшения выгоды от спекулятивного и ленивого поведения.

E-IOTA [87] предлагает параметризованный алгоритм для обеспечения случайности при выборе чаевых. Алгоритм устанавливает два определённых параметра 𝑝1, 𝑝2, где 0 < 𝑝1 < 𝑝2 < 1. При добавлении в сеть наконечник генерирует случайное число 𝑟, где 𝑟 ∈ (0, 1], чтобы решить, какие типы механизмов следует провести: 𝑟 ∈ (0, 𝑝1) — равномерно случайный отбор; 𝑟 ∈ [𝑝1, 𝑝2) — низкий 𝛼 взвешенный отбор; или 𝑟 ∈ [𝑝2, 1) — высокий 𝛼 взвешенный отбор. Таким образом, E-IOTA контролирует распределение различных типов механизмов, изменяя параметры 𝑝1,𝑝2. Это помогает создать самонастраивающийся tangle. Алгоритм подходит как для IOTA, так и для G-IOTA. 

Graphchain [79] — сеть без права доступа, которая имеет схожий с IOTA дизайн. Graphchain формируется путём задания каждой транзакции подтвердить своих предков. В частности, транзакция должна подтвердить семь (по крайней мере, две) транзакции-предшественницы, и каждая транзакция несёт PoW различной сложности. PoW суммарно и транзитивно аффицирует предыдущую достоверную историю. Graphchain отличается от IOTA своим механизмом стимулирования. IOTA удаляет стимулы из узлов, где все транзакции являются бесчувственными. Система развивается в соответствии с правилами выбора верхушки и свободна от влияния стимулов. Graphchain, вместо этого, вводит механизм стимулирования для поддержания графа. Транзакции обязаны размещать плату за транзакции в качестве предложения для сбора. Это означает, что при проверке достоверности каждая транзакция должна ссылаться на группу транзакций-предков для внесения своего депозита (платы). При этом транзакции-предки должны иметь достаточно сборов для инкассации. Сборы исчерпываются поступающими транзакциями от самых старых предков, чтобы достичь установленной общей суммы. Транзакции с высокой комиссией привлекают мощных майнеров, работающих параллельно, для быстрого подтверждения, в то время как транзакции с низкой комиссией в конечном итоге будут собраны небольшим майнером. Основываясь на этой конструкции, Graphchain позволяет текущим транзакциям быстро закрепиться в родословной всех будущих транзакций.

Avalanche [130][182] — система без права доступа, основанная на новом типе подхода к достижению консенсуса. Отклоняясь от BFT-стиля и механизмов Накамото, Avalanche строит свой базовый протокол под названием Slush, CFT-устойчивый механизм, используя концепции т.н. алгоритма сплетен и эпидемических сетей. Более конкретно, Avalanche случайным образом выбирает небольшую группу узлов, чтобы получить их смещение в бивалентное состояние. Независимо от размера сети, размер выбранной группы варьируется в небольшом интервале (например, от 10 до 20), чтобы облегчить время выполнения при достижении раунда. Затем система аргументирует Slush в пользу расширенных алгоритмов с рядом параметров (как единичный счётчик в Snowflake и доверие в Snowball) для окончательности и безопасности. Эти параметры помогают получить пороговый результат для их исторических цветов через счётчик количества запросов (как голоса в протоколах BFT). Наконец, дополненный алгоритм применяется ко всей сети, которая естественным образом формируется в топологическую DAG. Таким образом, конечное состояние, представленное синим (b) или красным (r) цветом, достигается путём повторной выборки сети и настроенных ориентиров смещения. Avalanche также предоставляет демо-версию для визуализации процесса [164].Консенсус по типу II. Системы типа II основаны на блоках. Блоки имеют структуру естественного расширяющегося графа. К этой части относятся системы Spectre [24], Phantom [80] и Meshcash [81].

Spectre [24][128] — сеть без разрешений. Ключевая технология Spectre — рекурсивный алгоритм взвешенного голосования, основанный на старшинстве блоков в базовой топологической сортировке. Процедура голосования выполняется блоками, а не майнерами. Вновь присоединившиеся блоки должны подать голоса за каждую пару блоков, обозначаемую как (𝑥,𝑦), в соответствии с их расположением. Голосование, (-1, 0, 1), за такую пару блоков, по своей сути является упорядочиванием предпочтений выбранных блоков, таким образом, что 𝑥 приходит раньше 𝑦 (обозначается как 𝑥 < 𝑦) и наоборот (𝑦 < 𝑥). Следовательно, окончательное решение о попарном упорядочении измеряется в абсолютных значениях суммарных голосов (они же веса). Последовательный набор операций извлекается в соответствии с большинством собранных голосов. Упорядочение не обязательно линеаризуемо. Эта конструкция ослабляет предположение об упорядочении, при котором любые две транзакции должны быть согласованы всеми не коррумпированными узлами. Вместо этого SPECTRE принимает решение об упорядочении только честными узлами. Более того, скорость обновления блоков в Spectre должна замедлиться, чтобы убедиться, что процедура голосования была завершена честными узлами.Phantom [80] — протокол на основе PoW для сети без разрешений. Каждый блок в Phantom содержит несколько хэш-ссылок на предшественников и ссылается на нескольких преёмников. Протокол, во-первых, определяет набор хорошо связанных блоков, чтобы исключить блоки (с высокой вероятностью), созданные нечестными узлами. Затем Phantom использует рекурсивный 𝑘-кластерный алгоритм (в равной степени, жадный алгоритм аппроксимации) для достижения частичного упорядочения идентифицированного набора блоков (кластера) до полного топологического порядка. Жадный алгоритм поощряет выбранные блоки внутри кластера и наказывает внешние блоки через итерационные раунды. Параметр 𝑘 используется для определения уровня допустимости одновременных блоков. После сортировки блоков транзакции в блоках упорядочиваются в соответствии с порядком их появления. Последовательные транзакции будут приняты и подтверждены как окончательное состояние. Итерация транзакций позволяет добиться полного упорядочивания сети. Подобно Spectre, Phantom также полагается на честные узлы, чтобы договориться об этом надёжном упорядочивании блоков и транзакций. Но Phantom отличается от Spectre тем, что он обеспечивает строгое линейное упорядочивание блоков и транзакций в сети.

Meshcash [81] — многоуровневая система DAG, которая позволяет блокам сосуществовать одновременно. Во-первых, для создания блока стратегия майнинга следует классическим вычислениям NC-PoW, но с изменениями, где каждый блок: a) указывает на каждый блок в предыдущем слое (определённое поле, как в других системах); b) указывает на каждый блок с 0 внутренней степенью; и c) увеличивает счётчик слоя 𝑖, когда видит больше пороговых блоков в предыдущем слое. Для достижения консенсуса используются два типа протоколов: медленный протокол черепахи (tortoise) на основе PoW для обеспечения долгосрочного консенсуса и необратимости блоков и сменный быстрый протокол зайца для получения быстрого консенсуса. Принадлежность блока к тому или иному типу протоколов зависит от его появления в сети, измеряемого его уровнем. Для блоков в старых слоях (более ранних, чем 𝑖 — 𝑠 ) система следует правилам протокола черепахи. Этот протокол по сути является консенсусом BFT без лидера, который принимает решение о согласованности (вхождении в каноническую историю) блока в соответствии со взвешенными голосами его последующих блоков. Этот протокол гарантирует полное упорядочивание блоков. Если одна и та же транзакция содержится в нескольких блоках, предпочтение отдается транзакции, появившейся в более раннем блоке. Для блоков в последних слоях (от 𝑖 — 𝑠 до последних обновлений) Meshcash переходит на протокол зайца. Этот протокол представляет собой взаимозаменяемый протокол, целью которого является быстрое урегулирование блоков. Meshcash обеспечивает как простой, но ограниченный метод безопасности, так и сложный, но устойчивый к атакам, используя вне-цепочечный асинхронный протокол византийского соглашения (ABA). Он увеличивает разрыв между честными и плохими блоками и гарантирует, что честные стороны будут голосовать в одном направлении после завершения протокола.

Консенсус в системах типа III. Системы типа III представляют собой безблочную структуру данных. Транзакции обслуживаются отдельными узлами и в итоге образуют несколько параллельных цепочек. К этой части относятся системы Nano [50], Hashgraph [48][183], DLattice [170], Jointgraph [171], Chain- web [147], Aleph [167], Vite [139], Caper [179] и протоколы класса Lachesis [122][123][124][125][126].

Nano (RaiBlocks) [50] — сеть без разрешений, в которой участвуют два типа субъектов, а именно владелец аккаунта и представитель (сокращённо — Rpst). Владельцы аккаунтов могут выбрать представителя, который будет голосовать от их имени в случае выхода из сети. Избранные представители служат для разрешения конфликтных транзакций. Транзакции в Nano являются атомарными, и аккаунт записывает всю историю транзакций, связанных с ним самим. Полный перевод в Nano состоит из двух частей — транзакции отправки и транзакции получения. Сначала отправитель создаёт транзакцию отправки, обращаясь к последнему блоку на своём счёте. В это время с его счета были списаны соответствующие суммы. Затем получатель создаёт транзакцию получения, также ссылаясь на транзакцию отправки и последний блок на своём счёте. Когда возникают форки, представитель создаёт голосование, ссылаясь на конфликтующую транзакцию. Затем он начинает наблюдать за поступающими голосами от других представителей. Этот процесс длится в течение четырёх периодов голосования и в общей сложности занимает одну минуту. Наконец, он подтверждает победившую транзакцию с наибольшим суммарным количеством голосов (весом, 𝑤 ). Hashgraph [48][183] — сеть с разрешением. Каждый узел-участник поддерживает отдельную цепочку, а узлы взаимно взаимодействуют через протокол сплетен. Узел локально создаёт событие для записи истории полученной информации. Событие в основном содержит три поля, включая временную метку для синхронизации, транзакцию для торговли и хэш для перекрестных ссылок. Параллельные цепочки взаимодействуют друг с другом на основе дизайна перекрёстных ссылок. Эти ссылки указывают на последнее событие в собственной цепочке, а также на события из синхронизированных соседних цепочек. События, несущие полную историю просмотров бухгалтерских книг, передаются через протокол сплетен, и узлы в конечном итоге получают полную историю. Хешграф достигает консенсуса с помощью византийского консенсуса. Одно событие, чтобы быть окончательно признанным достоверным, должно пройти через трёхэтапную процедуру, а именно: увидеть, сильно увидеть и решить. Каждая процедура должна набрать голосов больше порогового значения — 2/3 известных свидетелей, которые являются инициаторами, избираемыми членами комитета в каждом раунде. Эта конструкция имитирует обычный консенсус BFT и объединяет концепции в параллельные цепочки. События, таким образом, могут быть структурированы в глобальном тотальном порядке. При этом они способны достигать законченности, когда консенсус завершен в текущих раундах.

DLattice [170] повторяет структуру Nano и Hashgraph, где параллельные цепочки, поддерживаемые отдельными узлами, составляют систему DAG. Система состоит из Genesis Header и множества узлов. Genesis Header организует задействованные узлы в виде Merkle Patricia Tree [Прим. Menaskop: чуть подробней и на русском: https://habr.com/ru/post/446558/ ] (MPT), в то время как узлы в основном выполняют задачи, такие как передача токенов. Аналогично Nano, действие передачи токена разделяется на транзакцию отправки и транзакцию получения между отправителем и получателем. Если узел замечает какие-либо развилки транзакций, запускается программа консенсуса для разрешения конфликтов. DLattice использует так называемый протокол DPoS-BA-DAG (PANDA) для достижения консенсуса между пользователями. DPoS обеспечивает способ формирования комитета, а BA показывает, как достичь консенсуса в их DAG. В частности, узлы, которые удовлетворяют настроенному условию PoS, могут локально и тайно генерировать свои идентификаторы на основе силы голоса с помощью техники Verifiable Random Function (VRF) [184]. После рассылки сообщений другие узлы могут проверить, выбрана ли личность в качестве консенсусной личности. Консенсус делится на две фазы Vote и Commit. Члены комитета выбирают транзакцию для голосования на этапе Vote и начинают фиксацию в соответствии с набранными голосами на этапе Commit. Если количество голосов за фиксацию превышает пороговое значение, консенсус достигается по этому соглашению.

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