DAG-based консенсус: Avalanche, Narwhal

Bitcoin обрабатывает 7 транзакций в секунду. Visa - 65,000. Можно ли догнать Visa, не жертвуя децентрализацией? Инженеры десятилетиями бились над этим, пока не задали правильный вопрос: а зачем вообще выстраивать блоки в одну линию? Что если позволить блокам ссылаться на несколько предыдущих - превратить цепочку в паутину? Результат - протоколы с пропускной способностью 130,000 транзакций в секунду, которые сегодня работают в Avalanche, Sui и Aptos.

• **Avalanche** обрабатывает ~4,500 TPS с sub-second finality для 1,800+ валидаторов - Snowball-консенсус позволяет каждой ноде опрашивать только 20 случайных соседей вместо всех
• **Sui** (построен на вариации Narwhal) подтверждает простые переводы за ~400ms без консенсуса - object-centric модель автоматически определяет, какие транзакции независимы и могут выполняться параллельно
• **IOTA Tangle** - DAG для IoT-устройств: каждая транзакция подтверждает две предыдущие, и пропускная способность растёт с числом участников вместо того, чтобы падать

Предварительные знания

• The Consensus Problem: Why and How

DAG вместо цепочки блоков

Blockchain в классическом понимании - это **линейная цепочка**: каждый блок ссылается ровно на один предыдущий. Это создаёт строгий порядок, но и узкое место: пока весь мир ждёт один следующий блок, пропускная способность ограничена физически.

**DAG (Directed Acyclic Graph)** - это граф, в котором каждая вершина (блок или транзакция) может ссылаться на **несколько предыдущих**. Рёбра направлены (от нового к старому), циклы запрещены. В результате вместо одной «нитки» получается «паутина» - несколько транзакций могут добавляться **одновременно**, не дожидаясь друг друга.

Ключевые свойства DAG-структуры: - **Directed** - рёбра имеют направление: новая вершина ссылается на старые, а не наоборот - **Acyclic** - если идти по рёбрам, нельзя вернуться в исходную точку (иначе нарушилась бы причинность: блок не может зависеть от самого себя) - **Multi-parent** - вершина ссылается на несколько «родителей», кодируя параллелизм

**IOTA Tangle** - один из первых проектов, использующих DAG. Каждая транзакция подтверждает две предыдущие (two-parent DAG). Идея: чем больше участников, тем больше транзакций подтверждается параллельно - пропускная способность **растёт** с числом пользователей, а не падает.

**BlockDAG** - термин, объединяющий подходы, где блоки образуют DAG: PHANTOM, SPECTRE (от Hebrew University), Kaspa. В отличие от IOTA (DAG транзакций), здесь DAG из **блоков** - каждый блок содержит набор транзакций и ссылается на несколько предшествующих блоков.

Семейство Avalanche: от Slush до Snowball

В 2018 году анонимная группа «Team Rocket» опубликовала статью, предложившую радикально новый подход к консенсусу. Вместо того чтобы собирать подписи от всех валидаторов (как в PBFT), или майнить блоки (как в PoW), они предложили **повторяющийся случайный опрос** - repeated random sub-sampling.

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

Почему это работает? Метастабильность. Представьте 100 людей в комнате: каждый случайно спрашивает 10 соседей и присоединяется к большинству. Даже при начальном соотношении 51/49 система быстро сходится к единому мнению - как снежный ком (отсюда название Snowball).

**O(1) communication per node** - каждая нода в каждом раунде опрашивает фиксированное число k соседей (обычно k=20). Это не зависит от общего числа нод n. Для сравнения: в PBFT каждая нода обменивается сообщениями со **всеми** остальными - O(n) на ноду, O(n^2) суммарно.

Narwhal + Tusk: разделяй данные и порядок

Avalanche показал, что DAG ускоряет консенсус. Но исследователи из Meta (бывш. Facebook) пошли дальше: а что если **полностью разделить** две задачи - распространение данных (data dissemination) и определение порядка (ordering)? Результат - **Narwhal** (DAG mempool) и **Tusk** (zero-message consensus).

В классическом blockchain обе задачи переплетены: лидер собирает транзакции, упаковывает их в блок, рассылает блок, ноды голосуют за блок. Если лидер медленный или злонамеренный - всё стоит. Narwhal/Tusk разрезает этот узел: - **Narwhal** - каждый валидатор непрерывно распространяет свои транзакции в виде DAG-вершин, не дожидаясь лидера - **Tusk** - определяет порядок уже распространённых вершин, используя структуру DAG

**Как работает Narwhal (DAG mempool):** 1. Время делится на **раунды** (rounds) 2. В каждом раунде каждый валидатор создаёт **batch** (набор транзакций) и рассылает его 3. Batch нового раунда содержит **ссылки** (хеши) на batch-и предыдущего раунда от других валидаторов 4. Прежде чем принять batch, валидатор проверяет наличие **certificate of availability** - подтверждения, что данные доступны у 2f+1 нод 5. Результат: DAG из batch-ей, где каждый batch подтверждён и доступен

**Как работает Tusk (consensus):** Tusk не отправляет **ни одного дополнительного сообщения** - он использует структуру DAG, уже построенного Narwhal, как «голосование». В чётных раундах выбирается **anchor** (якорная вершина) предопределённым образом. Если anchor получил достаточно «голосов» (ссылок от batch-ей следующего раунда), он **коммитится** вместе со всеми своими предками.

**130,000 TPS** - результат тестов Narwhal/Tusk в статье 2022 года (Danezis et al., 2022). Для сравнения: Bitcoin ~7 TPS, Ethereum ~30 TPS, Solana ~4,000 TPS в реальных условиях. Ключ к такой производительности - полная утилизация bandwidth: данные распространяются непрерывно, не ожидая консенсуса.

**Sui** (от Mysten Labs, бывшие инженеры Meta/Diem) использует **Narwhal + Bullshark** (улучшенный Tusk) как основу своего консенсуса. **Aptos** (тоже наследник Diem) использует **Quorum Store** - свою вариацию идей Narwhal для разделения data dissemination и ordering. Оба проекта подтверждают: разделение данных и порядка - архитектурный паттерн, повторённый по итогам Diem.

Параллельная обработка транзакций в DAG

DAG-структура снимает ограничение на порядок добавления блоков. Но есть вторая сторона медали: как **выполнять** транзакции параллельно? В линейном blockchain порядок прост - транзакция 5 выполняется после транзакции 4. В DAG две ветки могут развиваться одновременно, и если обе тратят одни и те же средства - возникает **конфликт**.

Решение: разделить транзакции на **конфликтующие** и **неконфликтующие**: - **Неконфликтующие** (independent): Алиса переводит Бобу, Чарли переводит Дейву - разные счета, можно выполнять параллельно - **Конфликтующие** (conflicting): Алиса переводит Бобу 10 ETH и одновременно Чарли 10 ETH, а на балансе 15 ETH - нужно выбрать одну В хорошо спроектированной системе **>90% транзакций независимы** - параллелизм даёт огромный выигрыш.

**Sui** реализует этот принцип через **object-centric model**: каждый объект (монета, NFT, smart contract) имеет владельца. Транзакции, работающие с **разными объектами**, обрабатываются параллельно без консенсуса (fast path, ~400ms). Транзакции, затрагивающие **общие объекты** (shared objects), проходят через полный Narwhal/Bullshark консенсус.

**Цифры TPS из benchmarks требуют контекста.** 130K TPS у Narwhal/Tusk - это контролируемые условия (geo-distributed WAN, 50 нод). Реальный throughput зависит от: доли конфликтующих транзакций, сложности smart contracts, сетевых задержек, числа валидаторов. Solana заявляет 65K TPS, но в реальности показывает ~4,000 TPS. DAG даёт кратный выигрыш, но не магический.

**Kaspa** (BlockDAG на базе PHANTOM/GhostDAG) - один из первых проектов, применивших DAG к PoW: блоки майнятся параллельно со скоростью ~1 блок/сек (vs 1 блок/10 мин у Bitcoin), DAG-структура позволяет включать все параллельные блоки вместо отбрасывания fork-ов.

Итоги

• **DAG (Directed Acyclic Graph)** заменяет линейную цепочку «паутиной»: каждая вершина ссылается на несколько предыдущих, что позволяет добавлять транзакции **параллельно** вместо последовательного ожидания следующего блока
• **Avalanche (Snowball)** - leaderless консенсус через repeated random sub-sampling: каждая нода опрашивает k случайных соседей, система сходится через **метастабильность** с O(k log n) коммуникацией вместо O(n^2) в классическом BFT
• **Narwhal/Tusk** разделяет **data dissemination** и **ordering** - все валидаторы непрерывно распространяют данные (Narwhal), а порядок определяется по структуре DAG без дополнительных сообщений (Tusk), достигая 130K TPS в тестах
• **Параллельная обработка** работает для независимых транзакций (разные аккаунты/объекты), но **конфликтующие** транзакции всё равно требуют упорядочивания - DAG ускоряет data layer, но не устраняет потребность в линеаризации конфликтов
• Помните вопрос из начала урока: можно ли догнать Visa, не жертвуя децентрализацией? DAG-консенсус показывает, что bottleneck был не в самом консенсусе, а в **линейной структуре данных** - замена цепочки на паутину даёт 10-100x ускорение при сохранении BFT-гарантий

Связанные темы

DAG-консенсус развивает идеи классического BFT и связан с современными протоколами:

• Проблема консенсуса: зачем и как — DAG-протоколы решают ту же задачу византийских генералов, но через random sub-sampling (Avalanche) или DAG-структуру (Narwhal) вместо классического голосования
• BFT-протоколы — Классический BFT (PBFT) - O(n^2) коммуникации, что ограничивает масштабируемость. DAG-подходы снижают это до O(k log n), сохраняя BFT-гарантии
• HotStuff и линейный BFT — HotStuff оптимизирует BFT до O(n) с pipelining; Narwhal/Tusk идёт дальше, разделяя data dissemination и ordering
• Solana — Solana использует свой подход к параллельной обработке (Sealevel) и PoH для упорядочивания - альтернатива DAG-подходу

Вопросы для размышления

• Narwhal/Tusk показывает 130K TPS в тестах, но реальные DAG-сети (Sui, Avalanche) работают на порядок медленнее. Какие факторы, по вашему мнению, создают разрыв между benchmark и production - и можно ли его сократить?
• Avalanche использует probabilistic finality через random sampling, а Tendermint - deterministic finality через кворум 2/3. Для какого типа приложений вы бы предпочли каждый подход - и есть ли сценарии, где probabilistic finality с вероятностью ошибки 10^-9 практически эквивалентна deterministic?
• Sui разделяет транзакции на «owned objects» (без консенсуса, ~400ms) и «shared objects» (полный консенсус). Как бы вы спроектировали DeFi-приложение (например, DEX), чтобы максимизировать долю транзакций, проходящих по fast path?

Связанные уроки

• alg-13-dfs