Введение

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

Ключевая идея шардинга заключается в том, что вместо того, чтобы каждая транзакция в сети была выполнена каждым участником, только подмножество участников выполняют каждую транзакцию. Для достижения этой цели все состояние цепи (аккаунты, контракты, данные) разбиваются на несколько непересекающихся интервалов, которые называются “шардами”; каждый участник сети назначается на один или больше шардов, и скачивает и выполняет только транзакции, относящиеся к своим шардам.

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

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

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

Предлагаемое простое решение

Наивное решение проблемы валидности данных выглядит так: допустим, мы предполагаем, что в системе порядка тысячи валидаторов, из которых злонамеренных — не более 20%. Если рассмотреть случайную выборку из ~200 валидаторов, можно посчитать, что вероятность того, что более ? из них злонамеренные, очень близка к нулю. 

Треть — это важный порог. Существует семейство протоколов, которые позволяют группе участников достичь консенсус, если меньше, чем треть из них оффлайн или целенаправленно пытаются помешать достижению консенсуса (такие алгоритмы называются Byzantine Fault Tolerant consensus algorithms).

Следующий шаг наивного решения – это назначить небольшой процент от общего числа валидаторов на каждый шард. Используя идею из прошлого абзаца, мы полагаем, что в каждом шарде не более ? валидаторов злонамеренные, и используем Byzantine Fault Tolerant консенсус для подтверждения каждого блока.

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

Валидаторы некоторой эпохи, когда их эпоха началась, получили каноническую цепь от набора валидаторов из предыдущей эпохи, которые, основываясь на предположении что не более ? из них были плохими, следовали протоколу, и создавали свои блоки честно, правильно применяя транзакции, поверх блока, который завершал каноническую цепочку в позапрошлой эпохе. Таким образом, методом индукции, получается, что цепь, заканчивающаяся на некоторый блок, подписанный набором валидаторов текущей эпохи, валидна, и поскольку ни один набор валидаторов, следуя Byzantine Fault Tolerant консенсусу, не мог создать форк, наивное решение также диктует считать, что текущая цепь — единственная в шарде и является канонической. 

Это простое решение не работает, если мы предполагаем, что валидаторы могут быть скомпрометированы уже после того, как назначены в шарды (здесь и далее мы будем это называть «скомпрометированы адаптивно»), — и это предположение небезосновательно (подробнее об адаптивном компрометировании на английском еще можно почитать здесь). Адаптивно скомпрометировать один шард в системе из тысячи шардов после назначения валидаторов значительно дешевле, чем скомпрометировать всю систему до назначения. Поэтому безопасность протокола снижается линейно с увеличением количества шардов. Чтобы быть уверенными в валидности блока, мы должны знать, что в любой момент времени ни в одном шарде в системе нет сговора большинства валидаторов. В случае если мы верим что участники могут быть скомпрометированы адаптивно мы не можем быть в этом уверены.

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

Проблему вредоносных форков можно решить, имея одну выделенную цепь с более высокой надежностью (такую как Beacon Chain в Ethereum 2.0) и сохраняя хеши новых блоков каждого шарда на такой цепи. Если затем в каждом шарде принимать за каноническую только цепь, которая содержит в себе все блоки, известные на beacon chain, легко показать, что чтобы создать форк в шарде, необходимо создать форк на Beacom Chain, что значительно дороже.

Создание невалидных блоков — гораздо более насущная проблема. 

Валидность данных

Рассмотрим рисунок ниже, на котором первый шард скомпрометирован и злоумышленники создают невалидный блок B. Предположим, что в этом блоке B была ниоткуда создана 1000 токенов и направлена на счет Алисы. Затем злоумышленники генерируют валидный блок C поверх B (т.е. транзакции в блоке C все применены корректно), «скрывая» невалидный блок B, и инициирует кросс-шардовую транзакцию на второй шард, которая переводит эти 1000 токенов на счет Боба. С этого момента созданные обманом токены находятся на полностью валидном блокчейне во втором шарде.

Так как первый шард скомпрометирован, блоки B и C имеют все необходимые подписи. Валидаторы во втором шарде не могут проверять всю историю первого шарда. Как валидаторы второго шарда могут понять, что в цепи, с которой происходит кросс-шардовая транзакция, есть невалидные блоки? Рассмотрим несколько идей:

1. Валидаторы второго шарда могут проверить валидность блока, в котором была инициирована транзакция. Это не сработает даже в вышеприведенном примере, т.к. блок C выглядит полностью валидным.

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

Многообещающее решение проблемы — организовывать шарды в неориентированный граф, в котором каждый шард связан с несколькими другими шардами, и позволять кросс-шардовые транзакции только между соседними шардами (например, так работает шардинг Влада Замфира, и похожая идея используется в Chainweb проекта Kadena). Если нужно осуществить кросс-шардовую транзакцию между несоседними шардами, она будет маршрутизироваться через множество шардов. При таком устройстве валидатор в каждом шарде должен подтверждать все блоки и в своем, и во всех соседних шардах. Рассмотрим рисунок ниже, где изображены 10 шардов, у каждого из которых по 4 соседа, и никакие 2 шарда не требуют более двух «прыжков» для кросс-шардовой коммуникации:

Шард 2 подтверждает не только собственную цепочку, но и цепочки всех соседей, включая шард 1. Если злоумышленник в шарде 1 попытается создать невалидный блок B, затем построить поверх него блок C и инициировать кросс-шардовую транзакцию, такая транзакция не пройдет, потому что шард 2 подтвердил всю историю шарда 1 и распознает невалидный блок B.

Таким образом, компрометирование одного шарда становится нежизнеспособной атакой, но компрометирование нескольких шардов остается проблемой. На следующем рисунке злоумышленник, скомпрометировавший шарды 1 и 2, успешно выполняет кросс-шардовую транзакцию на шард 3, переводя средства из невалидного блока B:

Шард 3 подтверждает все блоки в шарде 2, но не в шарде 1, и поэтому не может распознать вредоносный блок. 

Существует два основных пути для корректного решения проблемы валидности данных: Fisherman и криптографические доказательства выполнения вычислений. 

Fisherman

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

При таком подходе система в безопасности, пока в шарде есть хотя бы один честный валидатор. 

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

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

2. Существование протокола оспаривания создает еще один вектор для атаки, когда скомпрометированные ноды спамят сеть невалидными опровержениями. Очевидное решение проблемы — заставлять оспаривающих вносить какое-то количество токенов в качестве депозита и возвращать их, если опровержение валидно. Но это только частичное решение, поскольку для противника может в любом случае оказаться выгодно спамить систему невалидными опровержениями (и сжигать депозиты) — например, чтобы предотвратить принятие валидного опровержения от честного валидатора. Такие атаки называются grieving attacks. 

Ни одна из двух проблем Fisherman не имеет (на момент написания оригинальной статьи в 2018 году) удовлетворительного решения, но использование Fisherman все равно строго лучше, чем возможность финализации невалидного блока.

Сжатые неинтерактивные доказательства знания

Второе решение проблемы компрометации нескольких шардов — использование криптографических конструкций, которые позволяют доказывать, что определенное вычисление (например, вычисление состояния из набора транзакций) было произведено правильно. Такие конструкции существуют: например, zk-SNARKs, zk-STARKs и др., и некоторые из них сегодня активно используются в блокчейн-протоколах для приватных платежей. Наиболее заметный пример — ZCash. Главная проблема таких примитивов в том, что они очень медленно вычисляются. Например, команда Coda Protocol, которая использует zk-SNARKs как раз для доказательства того, что все блоки в цепочке валидны, рассказывала в одном из интервью, что создание доказательства может занимать до 30 секунд на транзакцию (сейчас этот показатель может быть уже ниже).

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

Проблемы zk-SNARKs, помимо производительности:

• Зависимость от менее исследованных и менее проверенных временем криптографических примитивов;

• «Токсичные отходы»: большинство конструкций zk-SNARKs требует для использования выполнения некоторого вычисления группой людей, и необходимо, чтобы промежуточные значения вычислений были уничтожены. Если все участники сговорятся и сохранят промежуточные значения, они смогут создать ложные доказательства; Если хотя бы один сжег промежуточные вычисления, протокол в безопасности.

• Усложнение системы;

• Доказательства zk-SNARKs применимы только для части возможных вычислений: к примеру, протокол со смарт-контрактами, написанными на полном по Тьюрингу языке, не сможет использовать SNARKs для подтверждения валидности цепи (с 2018 года в этом направлении тоже есть большой прогресс). 

Доступность данных

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

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

Есть три блока: предшествующий — A — сгенерирован честными валидаторами; текущий — B — сговорившимися валидаторами; следующий — C — должен быть сгенерирован снова честными валидаторами (блокчейн изображен в правом нижнем углу).

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

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

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

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

Эта проблема называется проблемой доступности данных.

Рассмотрим два взаимодополняющих подхода к решению этой проблемы. 

Доказательство хранения (Proof of Custody)

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

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

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

Избыточные коды

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

Чтобы избежать этого, можно использовать конструкцию под названием Erasure Codes — избыточные коды — которая позволяет восстановить полный блок, даже если доступна только его часть:

На этой идее построены Polkadot и Ethereum Serenity — это позволяет легким нодам быть достаточно уверенными в доступности блоков. Подход Ethereum Serenity подробно описан в этом исследовании. 

Долгосрочная доступность

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

В этом контексте стоит упомянуть white paper Polyshard, в котором рассматривается данный вопрос. Там избыточные коды делают блоки доступными среди шардов, даже если несколько шардов потеряли все свои данные. К сожалению, конкретно этот подход требует, чтобы все шарды загружали блоки из всех других шардов, что невероятно дорого. 

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

Вперед в 2020

Большая часть текста выше была написана в 2018 году. Два года прогресс не стоял на месте, и в 2020 году запустилось по меньшей мере два протокола, которые реализуют шардинг, и пытаются решить описанные выше проблемы: Polkadot и NEAR. Они подходят к решению доступности и валидности данных очень похожими способами.

В Polkadot есть одна общая цепь (в их терминологии relay chain), и много шардов (в их терминологии “парачейнов”). В relay chain есть некоторое множество валидаторов, общие для всей системы, и безопасность системы построена на предположении, что в этом множестве меньше ? являются злонамеренными участниками. В каждый парачейн в каждой эпохе назначается небольшое количество валидаторов с relay chain, достаточно маленькое, чтобы нельзя было делать никаких утверждений об их честности. Действительно, если мы верим, что валидаторов в парачейне можно скомпрометировать адаптивно, и имеем разумную защиту от этого, нет никакого смысла пытаться минимизировать количество изначально злонамеренных участников в каждом парачейне.

Когда создается блок в парачейне, для него считаются избыточные коды так, чтобы общее количество частей было равно количеству валидаторов на relay chain, а количество частей, достаточное для восстановления блока – ? от этого числа. Каждая часть назначается и отправляется одному из валидаторов на relay chain. Хеш блока Pi, созданного для конкретного парачейна, включается в блок R на relay chain, но валидаторы на relay chain не принимают блок R, если для каждого блока Pi на каждом парачейне, хеш которого включен в R, у них нет их части избыточного кода. Таким образом, если блок R имеет подписи ? валидаторов на relay chain, и если мы полагаем, что не больше чем ? валидаторов на relay chain отходят от протокола, как минимум ? валидаторов на relay chain имеют части избыточного кода для каждого Pi, и следовательно любой Pi может быть восстановлен.

NEAR работает похожим образом, но реализует шардинг проще. В NEAR существует только одна цепь (в нашей терминологии main chain), на которой каждый блок логически содержит все транзакции со всех шардов, но физически содержит только хеш так называемых “чанков”, которые в свою очередь содержат транзакции. Участники цепи скачивают каждый блок, а затем только чанки для шадров, которые им назначены. Каждый блок для каждого шарда может содержать 0 или 1 чанк. Такой дизайн позволяет иметь такую же пропускную способность как и шардинг, описанный по ходу статьи выше, но делает дизайн системы значительно проще, поскольку есть только один консенсус, и только одна цепь. Простота дизайна – очень важный фактор при разработке отказоустойчивых систем.

Для решения проблемы доступности данных NEAR использует такой же подход как и Polkadot: когда участник цепи создает чанк, он создает избыточный код с количеством частей равным количеству валидаторов на цепи, так что ? этих частей достаточна для восстановления чанка, и отправляет одну часть каждому валидатору. Когда чанк включен в некоторый блок, валидаторы подписывают блок, только если для каждого чанка в блоке у них есть соответствующая часть избыточного кода. Соответственно, для любого блока, подписанного ? валидаторов, все чанки доступны, покуда не более чем ? валидаторов отходит от протокола.

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

Описанный выше подход позволяет убедиться в доступности данных, благодаря чему и NEAR и Polkadot могут реализовать Fisherman для решения валидности данных. Как я писал выше, одна из проблем Fisherman заключается в том, что если его реализовать наивно, любая кросс-шардовая транзакция должна ждать достаточно долго времени, чтобы Fishermen могли прислать доказательство невалидности, прежде чем выполняться на каждом шарде после первого.

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

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

Заключение

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

Быстрые и доступные протоколы блокчейна – важный компонент в инфраструктуре открытого интернета. Почитать про то, что такое открытый интернет, можно здесь и здесь.

Код NEAR открыт, наша реализация написана на Rust, её можно найти тут.

Посмотреть как выглядит разработка под NEAR, и поэкспериментировать в онлайн-IDE можно здесь.

Следить за всеми новостями на русском можно в группе в телеграме, а на английском в официальном твиттере.

До скорых встреч!