Всем привет, я один из разработчиков Near Protocol, который помимо всего прочего реализует шардинг, и в этой статье я хочу подробно рассказать, что такое шардинг в блокчейне, как он работает, и затронуть ряд проблем.
которые возникают при попытке его построить.
Хорошо известно, что Ethereum, самая популярная платформа dApps, обрабатывает менее 20 транзакций в секунду.
Из-за этого ограничения цена транзакций и время их подтверждения очень высоки: несмотря на то, что блок в Ethereum публикуется раз в 10-12 секунд, по данным АЗС ЭТХ Время между отправкой транзакции и моментом ее фактического попадания в блок составляет в среднем 1,2 минуты.
Низкая пропускная способность, высокие цены и долгое подтверждение транзакций не позволяют запускать на Ethereum какие-либо высокопроизводительные сервисы.
Основная причина, по которой Ethereum не может обрабатывать более 20 транзакций в секунду, заключается в том, что каждый узел Ethereum должен проверять каждую транзакцию.
За пять лет с момента выпуска Ethereum было предложено множество идей по решению этой проблемы.
Эти решения можно грубо разделить на две группы: те, которые предлагают делегировать выполнение транзакций небольшой группе узлов с очень хорошим оборудованием, и те, которые предлагают, чтобы каждый узел обрабатывал только подмножество всех транзакций.
Примером первого подхода является Гром , в котором блоки создаются всего одним узлом, что позволяет, по словам разработчиков, получать 1200 транзакций в секунду, что в 100 раз больше, чем у Ethereum. Другими примерами из первой категории являются Альгоранд , СпейсМэш , Солана .
Все эти протоколы улучшают различные аспекты протокола и позволяют выполнять больше транзакций, чем в Ethereum, но все они ограничены скоростью одной (хотя и очень мощной) машины.
Второй подход, при котором каждый узел обрабатывает только подмножество транзакций, называется шардингом.
Именно так Ethereum Foundation планирует увеличить пропускную способность Ethereum. В этом посте я расскажу вам, как работает шардинг в блокчейне на примере нескольких протоколов, которые сейчас находятся в разработке.
Терминология Поскольку терминология не стандартизирована, в статье я буду использовать следующие русские термины: Блокчейн — это либо технология в целом, либо структура данных, содержащая все блоки, включая форки.
Цепь — это одна конкретная цепочка в блокчейне, то есть все блоки, доступные, начиная с определенного блока, через ссылки на предыдущий блок.
Каноническая цепочка — это одна цепочка в блокчейне, которую участник, наблюдающий за блокчейном, считает текущей цепочкой.
Например, в блокчейне Proof of Work это будет цепочка с наибольшей сложностью.
Сеть представляет собой набор участников, создающих и использующих блокчейн.
Но да — это сервер, который поддерживает или использует сеть.
Самый простой шардинг
В самой простой реализации вместо поддержки одного блокчейна мы будем поддерживать несколько и называть каждый такой блокчейн «осколком».Каждый шард поддерживается независимым набором узлов, которые проверяют транзакции и создают блоки.
В дальнейшем я буду называть такие узлы валидаторами.
Каждый шард отвечает за подмножество контрактов и учетных записей.
Давайте пока предположим, что транзакции всегда работают только с контрактами и счетами внутри одного шарда.
Этого упрощенного дизайна достаточно, чтобы показать некоторые интересные проблемы и особенности шардинга.
Назначение валидатора и центральный блокчейн
Первая проблема, связанная с тем, что каждый шард имеет свои собственные валидаторы, заключается в том, что если у нас есть 10 шардов, то каждый шард теперь в 10 раз менее надежен, чем был бы один блокчейн.Таким образом, если блокчейн с X валидаторами решит провести хардфорк в шардированную систему с 10 шардами и разделит X валидаторов между 10 шардами, в каждом шарде теперь будет только X/10 валидаторов, а для получения контроля над шардом потребуется получить контроль в размере 5,1%.
(51 %/10) валидаторов.
Отсюда возникает первый интересный вопрос: кто назначает валидаторов шардам? Контроль над 5,1% валидаторов является проблемой только в том случае, если все 5,1% валидаторов находятся в одном шарде.
Если валидаторы не могут выбирать, к какому шарду им быть назначены, получение контроля над 5,1% валидаторов до того, как они будут назначены на шарды, не позволит им получить контроль над какими-либо шардами.
Почти все существующие предлагаемые схемы шардинга используют некоторый источник случайных чисел для назначения валидаторов шардам.
Получение случайных чисел в распределенной системе, в которой участники не доверяют друг другу, само по себе на сегодняшний день является не до конца решенной проблемой, которую мы не будем касаться в этой статье, а просто предположим, что у нас есть такой источник случайных чисел.
И генерация случайных чисел, и назначение валидаторов — это общесистемные вычисления, не специфичные для какого-либо конкретного сегмента.
Для таких вычислений в современных конструкциях сегментированных блокчейнов существует дополнительный выделенный блокчейн, который существует исключительно для выполнения общесистемных вычислений.
Помимо случайных чисел и назначения валидаторов, такие вычисления могут включать в себя получение хэшей последних блоков из шардов и их хранение; обработка обеспечения в системах Proof-of-Stake и изучение доказательств неправомерного поведения с сопутствующим подбором такого обеспечения; ребалансировка шардов, если такая функция предусмотрена.
Такой блокчейн называется цепочкой Beacon в Ethereum 2.0 и Near Protocol, цепочкой Relay в PolkaDot и Cosmos Hub в Cosmos. В этом посте мы будем называть такой блокчейн «центральным блокчейном».
Существование центрального блокчейна подводит нас к следующей интересной теме — квадратичному шардингу.
Квадратичный шардинг
Шардинг часто представляют как решение, которое бесконечно масштабируется по мере увеличения количества узлов.Вероятно, реально создать систему с таким свойством, но системы с центральным блокчейном имеют верхний предел количества шардов и, как следствие, не обладают бесконечной масштабируемостью.
Легко понять, почему: центральный блокчейн выполняет некоторые вычисления, такие как назначение валидаторов и сохранение последних состояний шардов, сложность которых пропорциональна количеству шардов.
Поскольку сам центральный блокчейн не сегментирован, а его пропускная способность ограничена пропускной способностью каждого узла, количество шардов, которые он может поддерживать, ограничено.
Посмотрим, как изменится пропускная способность всей системы, если мощность поддерживающих ее узлов увеличится в k раз.
Каждый шард сможет обрабатывать в k раз больше транзакций, а центральный блокчейн сможет поддерживать в k раз больше шардов.
Таким образом, пропускная способность всей системы увеличится в k^2 раза.
Отсюда и название «квадратичный шардинг».
Трудно предсказать, сколько шардов сможет поддерживать центральный блокчейн сегодня, но, скорее всего, мы не приблизимся к лимиту транзакций для сегментированного блокчейна с квадратичным шардингом в ближайшем будущем.
Скорее всего, мы скорее достигнем предела того, сколько узлов необходимо для поддержки такого количества шардов.
Государственное шардинг
Состояние — это вся информация обо всех счетах и договорах.До сих пор мы говорили о шардинге в целом, не уточняя, что именно шардируется.
Узлы в блокчейне выполняют следующие три задачи: 1) выполняют транзакции, 2) пересылают транзакции и блоки другим узлам и 3) хранят состояние и историю блокчейна.
Каждая из этих трёх задач связана с некоторой постоянно растущей нагрузкой на узлы:
- Необходимость выполнения транзакций требует большей вычислительной мощности по мере увеличения количества транзакций;
- Необходимость пересылки транзакций требует увеличения пропускной способности сети по мере роста транзакций;
- Необходимость хранения состояния и истории требует большего дискового пространства по мере увеличения размера состояния и/или истории.
Важно отметить, что, в отличие от первых двух пунктов, объем требуемого дискового пространства увеличивается, даже если количество транзакций в единицу времени не меняется.
Сегодня состояние Ethereum занимает около 100 ГБ, которые легко можно хранить на любой современной машине, но количество транзакций, которые может обрабатывать Ethereum, ограничено несколькими десятками в секунду и ограничено вычислительными мощностями и сетью.
Zilliqa — самый известный проект, который осколочные вычисления и сеть но не состояние.
Сегментирование вычислений проще, чем сегментирование состояния, поскольку все узлы имеют все состояние и по-прежнему могут легко выполнять контракты, вызывающие другие контракты, или влиять на учетные записи в разных сегментах.
В этих аспектах дизайн Zilliqa слишком упрощен; критику дизайна на английском можно прочитать Здесь .
Хотя было предложено сегментирование состояния без сегментирования вычислений, я не знаю ни одного проекта, который действительно это делает, поэтому мы предполагаем, что сегментирование состояния подразумевает сегментирование вычислений.
На практике тот факт, что состояние сегментировано, в некоторой степени изолирует сегменты, позволяя им быть независимыми блокчейнами, как мы определили их выше.
Валидаторы в шардах хранят только состояние, специфичное для их шарда, и выполняют и пересылают только те транзакции, которые влияют на это состояние.
Это снижает нагрузку на ЦП, диск и сеть линейно в зависимости от количества сегментов, но создает новые проблемы, такие как транзакции между сегментами.
Межшардовые транзакции
До сих пор мы рассматривали шарды как независимые блокчейны с точки зрения того, как они выполняют транзакции.При такой конструкции, например, невозможно выполнить транзакцию перевода денег между двумя счетами на двух разных шардах или позвонить контакту на одном шарде из контракта на другом.
Я хотел бы поддержать оба сценария.
Для простоты мы будем рассматривать только транзакции по переводу денег и будем считать, что у каждого участника есть аккаунт ровно на одном шарде.
Если участник какого-то шарда хочет перевести деньги участнику того же шарда, валидаторы этого шарда могут обработать эту транзакцию и применить ее к состоянию.
Но если, например, у Алисы есть аккаунт на шарде №1 и она хочет отправить деньги Бобу со счетом на шарде №2, ни валидаторы шарда №1 (которые смогут добавить деньги Бобу), ни валидаторы шарда №2 (которые не смогут забрать деньги Алисы) не могут завершить всю транзакцию и обновить состояние.
Существуют две большие группы подходов к решению этой проблемы:
- синхронный : для любой транзакции, которая включает в себя несколько сегментов, блоки в сегментах, содержащие обновление состояния для этой транзакции, создаются одновременно, и валидаторы в этих сегментах работают вместе для создания таких блоков.
Самая проработанная известная мне конструкция этого подхода — Merge Blocks, описанная (на английском языке) Здесь .
- Асинхронный : транзакция между шардами выполняется в шардах, на которые она влияет, асинхронно: часть транзакции, которая добавляет деньги Бобу, выполняется в шарде № 2, когда валидаторы в шарде имеют некоторые доказательства того, что часть транзакции, которая вычитает деньги из Алиса была казнена в осколке №1. Этот подход более популярен в разрабатываемых сегодня системах из-за того, что он не требует дополнительной синхронизации между шардами для создания блоков.
Такие системы сейчас предлагаются в Cosmos, Ethereum Serenity, Near Protocol, Kadena и других.
Проблема с этим подходом заключается в том, что если блоки создаются независимо, существует вероятность того, что один из блоков, содержащий обновление состояния транзакции, окажется не в канонической цепочке в своем шарде, и, таким образом, транзакция будет завершена лишь частично.
.
Например, рассмотрим рисунок ниже.
На нем показаны два раздвоенных сегмента и транзакция между сегментами, обновление состояния которых отражается в блоках A и X' соответственно.
Если цепочки A-B и V’-X’-Y’-Z’ окажутся каноническими в своих шардах, то транзакция полностью завершена.
Если цепочки A'-B'-C'-D' и V-X окажутся каноническими, то транзакция полностью отменяется, что допустимо.
Но если, например, A-B и V-X станут каноническими, то одна часть транзакции финализируется, а другая отменяется, и транзакция оказывается частично завершенной.
Описанный выше сценарий — одна из больших проблем шардинга, для которой все предложенные решения не оптимальны.
Мы коснемся этого чуть ниже.
Плохое поведение
Теперь, когда мы разобрались с тем, как работают сегментированные блокчейны, а также с концепциями центрального блокчейна, назначениями валидаторов и межшардовыми транзакциями, мы закончим эту статью рассмотрением еще одной интересной темы: что может актер, пытающийся атакуют систему, если им удалось получить контроль над достаточно большим количеством валидаторов в одном шарде.
Целевые вилки
Если участник имеет достаточный контроль над шардом, он может целенаправленно создавать форки.Для создания форков не имеет значения, какой консенсус используется в шардах, в частности не имеет значения, BFT это или нет, если под контролем злоумышленника находится достаточное количество валидаторов, он может создать форк.
.
Например, целью форка может быть откат транзакции, которая оплачивала что-то за пределами блокчейна.
Утверждается, что легче получить контроль над 50% шарда, чем над 50% всей сети (например, потому, что участник может попытаться взломать или подкупить валидаторов после того, как они были закреплены за шардом).
По определению, транзакции между сегментами меняют состояние нескольких сегментов.
Такие изменения попадут в некоторые блоки в блокчейнах соответствующих шардов.
Необходимо, чтобы либо все такие блоки были финализированы (то есть принадлежали каноническим цепочкам в соответствующих шардах), либо все не были финализированы (то есть не принадлежали каноническим цепочкам в своих шардах).
Поскольку мы предполагаем, что некоторые участники с плохими намерениями в принципе могли получить контроль над шардом, мы не можем предполагать, что форки не произойдут, даже если был достигнут византийский консенсус или поверх блока транзакции было построено большое количество блоков.
Существует множество решений этой проблемы, самым простым из которых иногда является сохранение хеша последнего блока в шарде в центральном блокчейне.
Затем алгоритм выбора канонической цепочки в шардах меняется так, что ни одна цель, не содержащая последний блок, хранящийся в центральном блокчейне, не может быть канонической.
Тогда, чтобы полностью избежать ситуаций, когда транзакция завершается частично из-за того, что часть блоков, содержащих обновление ее состояния, оказалась вне канонических цепочек, можно изменить алгоритм выполнения межшардовых транзакций, чтобы шард А не принимать подтверждение транзакции в шарде B до тех пор, пока блок, содержащий обновление состояния транзакции в шарде B, не будет сохранен в центральном блокчейне.
Создание недействительных блоков
Если участник смог получить контроль над достаточно большим количеством валидаторов в шарде, он мог попытаться создать полностью невалидный блок.Например, пусть состояние перед блоком такое, что у Алисы было 10 токенов, а у Боба 0, блок содержит только одну транзакцию, которая отправляет 10 токенов со счета Алисы на счет Боба, но в новом состоянии отражает 0 токенов для Алисы, и 1000 у Боба.
В классическом, не шардированном блокчейне создание такого блока невозможно, поскольку все участники, как те, кто создает блоки, так и те, кто просто использует блокчейн, проверяют все блоки и немедленно отбрасывают любой блок, содержащий такие ошибки.
Даже если валидаторы, контролируемые злоумышленниками, смогут построить цепочку быстрее, это не позволит им выдать более длинную цепочку, содержащую недействительный блок, за каноническую, поскольку все участники сети немедленно отбросят недействительный блок и любой блок, который был построен поверх него.
.
Честные валидаторы будут продолжать строить поверх последнего валидного блока, и все участники сети будут считать свою цепочку канонической.
На рисунке выше пять валидаторов, три из которых находятся под контролем злоумышленника.
Они создали недействительный блок А', а затем продолжили строить цепочку сверху.
Два частных валидатора немедленно отбросили блок A' как недействительный и продолжили построение поверх последнего известного им валидатора, тем самым создав форк.
Поскольку в честной цепочке меньше валидаторов, чем в нечестной, их цепочка короче.
Однако в классическом несегментированном блокчейне все участники системы проверяют все блоки, которые они видят. Таким образом, любой участник, использующий блокчейн, увидит, что A' недействителен, отбросит его и, следовательно, отбросит B', C' и D' как построенные поверх недействительного блока, и, таким образом, все участники увидят AB как каноническую цепочку.
.
В сегментированном дизайне ни один участник не может проверить все блоки во всех блокчейнах.
Следовательно, необходим некий механизм, который позволит валидаторам в конкретном шарде быть уверенными в том, что ни разу в прошлом недействительный блок не был создан в другом шарде, из которого они получили межшардовую транзакцию.
В отличие от целевых форков, отправка хеша блоков в центральный блокчейн не помогает, поскольку у центрального блокчейна также нет ресурсов для проверки всех блоков во всех шардах.
Центральный блокчейн может только подтвердить, что достаточное количество валидаторов, назначенных шарду, подписали блок (и, как следствие, объявили блок правильным).
Я знаю два решения проблемы, ни одно из которых не кажется удовлетворительным:
- Иметь какой-то механизм, который позволит системе быстро замечать появление вилок и невалидных блоков.
Если используется византийский консенсус, для создания невалидного блока более 2/3 валидаторов должны принадлежать злоумышленнику или быть скомпрометированы им.
Если система построена с предположением, что такое может случиться, но всегда есть хотя бы один честный валидатор, то необходим протокол, который позволит такому честному валидатору обнаружить, что создан невалидный блок, и уведомить систему.
Поскольку такому честному валидатору нужно время, чтобы заметить появление блока, проверить его и подготовить транзакцию с доказательством недействительности, такой протокол требует, чтобы другие шарды и центральный блокчейн ждали некоторое достаточно долгое время после получения блока, прежде чем выполнить его.
любое действие, которое от этого зависит. Это заметно замедляет любые транзакции, включающие несколько шардов.
- Используйте какой-то криптографический механизм, который доказывает, что вся цепочка блоков, включая блок, содержащий транзакцию, и саму транзакцию действительна.
Есть такой механизм, он называется zk-СНАРК (хотя часть о zk, или нулевом разглашении, на самом деле не нужна, сегодня почти нет исследований по SNARK, не относящимся к zk).
К сожалению, сегодня zk-SNARK ужасно медленны, а существующие практические реализации работают только для подмножества возможных вычислений.
Почему это не так – тема отдельной статьи.
Я много пишу о блокчейне и шардинге на английском языке.
Мы также периодически берем интервью у авторов других протоколов, таких как Cosmos и Solana, углубляясь в технические детали.
Если вам интересна тема, вы можете следить за новыми публикациями и видео, подписавшись на мой Твиттер.
Теги: #Криптовалюты #Высокая производительность #Распределенные системы #шардинг #блокчейн #Ethereum
-
Монолит Ci/Cd Авито: От Коммита До Моржа
19 Oct, 24 -
Выручка Avito Выросла На 47%
19 Oct, 24
