Вы здесь

Авторитетное руководство по блокчейн-шардингу. Часть 1

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

Авторитетное руководство по блокчейн-шардингу. Часть 1

Общеизвестно, что Эфириум, наиболее широко используемый блокчейн общего назначения на момент написания этого поста, может обрабатывать менее 20 транзакций в секунду в основной цепи. Это ограничение в сочетании с ростом популярности сети приводит к высоким ценам на газ (затратам на совершение операций в сети) и длительному времени подтверждения операций; несмотря на то, что на момент написания этой статьи каждый новый блок создается примерно каждые 10-20 секунд, среднее время, согласно ETH Gas Station, фактически затрачиваемое на добавление операции в блокчейн, составляет 1,2 минуты. Низкая пропускная способность, высокие цены и длительное время ожидания делают Эфириум непригодным для услуг, для массового внедрения которых требуется хорошая масштабируемость сети.

Какова основная причина низкой пропускной способности Эфириума? Причина в том, что все узлы в сети должны обрабатывать каждую новую транзакцию. Разработчики предложили множество вариантов решения проблемы пропускной способности на уровне протоколов. Эти решения могут быть в основном разделены на те, которые делегируют все вычислительные задачи небольшой группе высокомощных узлов, и те, в которых узлы выполняют только часть от общего объема работы. Примером реализации первого варианта является Thunder, в котором для достижения 1200 транзакций в секунду (что в 100 раз быстрее, чем Эфириум) обработкой всех операций и заявлений занимается один единственный узел. Я, однако, не подтверждаю действительность этого утверждения. Algorand, SpaceMesh, Solana – все они подходят для первой категории, реализуя различные улучшения в консенсусных моделях и структуре самого блокчейна для обработки большего количества транзакций, однако они по-прежнему ограничены в своих возможностях.

Второй подход, в котором работа разделена между всеми участвующими узлами, называется шардинг (или сегментирование). Именно так Ethereum Foundation в настоящее время планирует масштабировать Эфириум. На момент написания этой статьи полная Спецификация до сих пор не была опубликована. Я написал подробный обзор о шардинге в сети Эфириума и дал сравнение консенсусной модели Beacon с Near.

Протокол Near также строит шардинг. Команда Near включает в себя трех бывших MemSQL инженеров, ответственных за шардинг, кросс-шардовые транзакции и распределяемые объединения (JOIN), а также пять бывших сотрудников Google, и имеет большой опыт в создании распределенных систем.

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

Самый простой шардинг – Beanstalk

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

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

Схема Beanstalk хоть и простая, однако ее достаточно, чтобы выявить основные проблемы шардинга.

Разделение валидаторов и сеть Beacon

Первая проблема заключается в том, когда у каждого шарда свои собственные валидаторы, он в 10 раз менее безопасен, чем вся цепь. Таким образом, если не разбитая на шарды цепь с X валидаторами принимает решение о переходе путем хард-форка в шардированную цепь и разбивает x валидаторов на 10 шардов, каждый шард получает только x/10 валидаторов, а для коррумпирования одного шарда требуется только коррумпирование 5,1% (51% / 10) от общего числа валидаторов.

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

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

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

Помимо генерации случайных чисел и назначения валидаторов шардам, эти операции часто включают в себя получение обновлений из шардов и создание их снимков, обработку долей и слэшинг в консенсусных системах PoS (доказательства доли владения), а также восстановление баланса в шардах, если эта функция поддерживается. Такая цепь называется цепью Beacon в Ethereum и Near, цепью Relay в PolkaDot и Cosmos Hub в Cosmos.

В этом посте мы будем называть такие цепи цепью Beacon. Существование цепи Beacon подводит нас к следующей интересной теме – квадратичному шардингу.

Квадратичный шардинг

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

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

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

Если узлы, управляющие сетью, включая узлы в цепи Beacon, станут в четыре раза быстрее, то каждый шард сможет обрабатывать в четыре раза больше транзакций, а цепь Beacon сможет обслуживать в 4 раза больше шардов. Пропускная способность всей системы будет увеличиваться на коэффициент 4 х 4 = 16 — тем самым оправдывая свое название «квадратичный шардинг».

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

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

Известно, что Влад Замфир работает над конструктивным решением шардинга, которое не включает в себя цепь Beacon; я работал с ним над одним из прототипов, детальный обзор которого приведен здесь.

Шардинг состояний

До сих пор мы толком и не определили, что именно разделяется и не разделяется при разделении сети на шарды.

В частности, узлы в блокчейне выполняют три важные задачи: они не только 1) обрабатывают транзакции, они также 2) передают данные о проверенных транзакциях и завершенных блоках другим узлам и 3) хранят данные о состоянии и историю всего сетевого реестра. Каждая из этих трех задач предъявляет растущее требование к узлам, управляющим сетью:

  1. Необходимость обработки транзакций требует большей вычислительной мощности с увеличением количества обрабатываемых транзакций.
  2. Необходимость ретрансляции транзакций и блоков требует большей пропускной способности сети с увеличением количества ретранслируемых транзакций.
  3. Необходимость хранения данных требует большего объема памяти по мере роста состояний. Важно отметить, что в отличие от вычислительной мощности и сети, требование к хранению повышается, даже если скорость транзакций (количество транзакций, обрабатываемых в секунду) остается постоянной.

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

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

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

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

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

Кросс-шардинг транзакций

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

Давайте пока рассмотрим только простые платежные операции, где у каждого участника есть счет ровно в одном шарде. Если вы хотите перевести деньги с одного счета на другой в пределах одного шарда, транзакция может быть полностью обработана валидаторами в этом шарде. Если, однако, Алиса, которая находится в шарде #1, хочет отправить деньги Бобу, который находится в шарде #2, ни валидаторы в шарде #1 (они не смогут кредитовать счет Боба), ни валидаторы в шарде #2 (они не смогут дебетовать счет Алисы) не могут обработать всю транзакцию.

Существует одна типа подходов к кросс-шардовым операциям:

  • Синхронный: всякий раз, когда необходимо выполнить кросс-шардовую операцию, блоки из нескольких шардов, которые хранят данные о переходе состояний, связанных с транзакцией, генерируются в одно и то же время, и валидаторы из нескольких шардов сотрудничают при выполнении таких операций. Наиболее подробное предложение, известное мне, - это Merge Blocks, описанное здесь
  • Асинхронный: Кросс-шардовая операция, которая затрагивает несколько шардов, выполняется в таких шардах асинхронно, т.е. «кредитный» шард выполняет свою часть работы после того, как у него достаточно доказательств того, что «дебетовый» шард выполнил свою часть. Этот подход, как правило, имеет более широкое распространение из-за своей простоты и несложной координации. Эта система сегодня предложена в Cosmos, Ethereum Serenity, Near, Kadena и других платформах.

    Проблема этого подхода заключается в том, что если блоки производятся независимо, есть ненулевая вероятность того, что один из нескольких блоков будет потерян, что делает транзакцию только частично выполнимой. Рассмотрим рисунок ниже, на котором изображены два шарда, оба из которых столкнулись с форком, и кросс-шардовая транзакция, которая была записана в блоках A и X’ соответственно.

    Если цепочки A-B и V’-X’-Y’-Z’ окажутся каноническими в соответствующих шардах, транзакция будет полностью завершена. Если "-B "-C "-D " и V-X становятся каноническими, то транзакция полностью прекращается, что приемлемо. Но если, например, A-B и V-X становятся каноническими, то одна часть транзакции завершается, а другая прекращается, создавая сбой атомарности.

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

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

Построение системы, в которой набор цепей имеет разные свойства, но использует достаточно схожую консенсусную и блочную структуру и имеет общую цепь Beacon, может позволить создать экосистему гетерогенных блокчейнов с работающей подсистемой взаимодействия. Такая система вряд ли будет характеризоваться ротацией валидаторов, поэтому для обеспечения безопасности необходимо принять дополнительные меры. Как Cosmos, так и PolkaDot являются такими эффективными системами. В этой рецензии, которую написал Заки Маниан из Cosmos, предоставлен подробный обзор и сравнение ключевых аспектов двух проектов.

Вредоносное поведение

Теперь у вас имеется достаточное представление о том, как осуществляется шардинг, включая идею применения цепи Beacon, ротацию валидаторов и кросс-шардовые транзакции.

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

Злонамеренные форки

Группа злонамеренных валидаторов может попытаться осуществить форк. Обратите внимание, что не важно, является ли основным консенсусом BFT или нет, коррумпирование достаточного количества валидаторов всегда позволит провести форк.

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

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

Согласование недействительных блоков

Группа валидаторов может попытаться создать блок, который неправильно применяет функцию перехода состояния. Например, начиная с состояния, при котором Алиса имеет 10 токенов, а Боб - 0, блок может содержать транзакцию, которая отправляет 10 токенов от Алисы Бобу, но в конечном итоге имеет состояние, в котором Алиса имеет 0 токенов, а Боб имеет 1000 токенов.

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

На рисунке выше показано пять валидаторов, три из которых являются злоумышленниками. Они создали недопустимый блок A’, а затем продолжили строить новые блоки поверх него. Два честных валидатора отклонили блок A’ как недопустимый и начали создавать блоки поверх последнего действительного блока, известного им, создавая ответвление. Поскольку в честном ответвлении меньше валидаторов, их цепь короче. Однако в классическом нешардированном блокчейне каждый участник, использующий блокчейн для какой бы то ни было цели, отвечает за проверку всех получаемых им блоков и перерасчет состояния. Таким образом, любой человек, который связан каким-либо интересом с блокчейном, увидит, что блок A’ является недействительным, и, таким образом, также немедленно отклонит блоки B’, C' и D’, по сути принимая цепочку A-B как текущую самую длинную действительную цепь.

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

Обратите внимание, что в отличие от форков, перекрестная связь с цепью Beacon не является достаточным решением, так как цепь Beacon не имеет возможности проверить блоки. Она только может проверить, что достаточное количество валидаторов в этом шарде подписало блок (и таким образом засвидетельствовало его правильность).

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

  1. Иметь какой-то разумный механизм, который будет предупреждать систему, если будет предпринята попытка неправильно применить переход состояния. Если предположить, что каждый шард работает согласно протоколу консенсуса типа BFT, то пока количество нечестных валидаторов в конкретном шарде меньше ⅔, как минимум один честный валидатор должен будет подтвердить блок и проверить, что функция перехода состояния применяется правильно. Если более ⅔ узлов являются нечестными, они могут завершить блок без участия одного честного узла. Если предположить, что хотя бы один узел в шарде не является нечестным, необходим какой-то механизм, который позволит таким узлам отслеживать, какие блоки создаются, и иметь достаточно времени, чтобы оспорить узлы с недопустимым переходом состояния.
  2. Иметь в блоках некоторую информацию, которой будет достаточно, чтобы доказать, что переход состояния применяется правильно, но значительно дешевле для проведения проверки, чем фактическое применение функции перехода состояния. Наиболее близким механизмом для достижения этих целей является zk-SNARKs (хотя мы не нуждаемся в zk, или доказательствах нулевого знания; не использующей zk части будет достаточно), но механизмы доказательства zk-SNARKs слишком медленные, чтобы проводить вычисления на этом этапе.

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

Заключение

Благодаря приведенной выше информации вы теперь знаете о большинстве важных аспектов шардинга, а именно: концепции цепи beacon, зависимости вычислений от шардинга состояний, а также кросс-шардовых транзакциях. Подписывайтесь на нас, чтобы узнать о шардинге 201, который будет более основательно заточен под защиту от атак.

Категория: 
Криптовалюты
Технология: 
5
Ваша оценка: Нет Средняя: 5 (2 оценок)
28316 / 1
Аватар пользователя Daritas
Публикацию добавил: Daritas
Дата публикации: вт, 01/15/2019 - 13:33

Что еще почитать:

Комментарии:

Собака Шредингера

Спасибо за перевод. Жду вторую часть )

вт, 01/15/2019 - 16:39

Лефорт

Поддерживаю! Тоже жду продолжения статьи про шардинг.

вс, 01/27/2019 - 13:26

Так что кроме ethereum кто-то ещё работает над внедрением шардинга?

ср, 01/16/2019 - 13:52

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

ср, 01/16/2019 - 16:43

Просто на слуху внедрение шардинга планирует только ethereum, о других криптовалютах я не слышал такого. Или все ждут, когда шардинг применят в эфире и потом уже по результатам и другие криптовалюты подтянутся?

пт, 01/18/2019 - 09:29