Zilliqa шаг за шагом. Часть 1 -Шардинг

Это вольный и краткий перевод статьи: https://blog.zilliqa.com/https-blog-zilliqa

Как и было сказано во вводной статье, Zilliqa — это новая блокчейн платформа, которая способна обрабатывать тысячи транзакций в секунду. Таким образом, у Zilliqa есть потенциал для соперничества с традиционными платежными системами (такими как Visa и MasterCard). Более того, скорость обработки транзакций растет примерно пропорционально росту сети.

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

Что же такое шардинг?

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

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

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

И это все? Звучит просто!

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

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

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

3. Размер шарда. Можно ли создать крошечные шарды размером, скажем, в 10 нод? Конечно же нет, ведь чем меньше размер шарда, тем проще будет мошенникам взять его под контроль. Более того, эти же шарды используются для обработки транзакций, поэтому небольшое количество нод на шард абсолютно неприменимо в данном случае.

Как Zilliqa борется с этими проблемами?

1. Контроль за атаками Сивиллы. Существует несколько способов, чтобы предотвратить атаки Сивиллы или сделать их экономически невыгодными. Например, ноды могут внести депозит в денежном эквиваленте или в токенах в качестве залога. Или можно попросить их произвести вычисления, как в механизме PoW. Zilliqa тоже использует PoW — каждая новая нода должна произвести ряд вычислений перед тем как начать работу в сети. Ранее добавленные ноды проверяют результат вычислений и выдают авторизацию. Таким образом, PoW служит своеобразным входным билетом в сеть.

2. Автоматизированное создание шардов. Использование протокола PoW позволяет автоматически создавать шарды. Zilliqa выбирает особую группу нод. Выбор производится на основании PoW. Через определенный интервал времени, один из членов данной группы заменяется новым членом (используется принцип «первым пришел — первым ушел»). Таким образом сохраняется постоянное число участников в группе. Новым участником становится нода, которая быстрее всех произвела вычисления. Данная группа и инициирует процесс шардинга. Затем все ноды выполняют новые вычисления согласно механике PoW, и на основании этих расчётов каждая нода определяется в некий шард.

3. Выбор верного размера шарда. Данная задача является критичной для поддержания безопасности системы. Предположим, что в сети находится 1000 нод, из которых ¾ (750) являются честными, а оставшиеся 250 нод — мошеннические. Теперь давайте создадим шарды различного размера и вычислим вероятность того, что хотя бы треть нод в одном шарде мошеннические. Как видно из рисунка, вероятность этого высока при размере шарда в 100 нод. Так как для консенсуса необходимо наличие подавляющего большинства «честных» нод, то размер шарда должен быть увеличен. При размере от 600 нод, вероятность снижается до одной миллионной. Именно поэтому в Zilliqa было решено установить минимальный размер шарда в 600 нод.

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

Наконец, шардинг позволяет производить вычисления и эффективно использовать смарт-контракты. Например, одни шарды могут выполнять функции map, другие — reduce, производя распределенные вычисления.

Заключение

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

Резюме

Zilliqa — новая блокчейн платформа, которая может обрабатывать тысячи транзакций в секунду, таким образом, потенциально приближаясь к Visa и MasterCard.

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

Основные проблемы шардинга следующие: защита от атак Сивиллы, процесс создания шардов и определение размера шарда. Zilliqa борется с этими проблемами путем применения PoW для авторизации нод, автоматического создания шардов специально отобранной группой нод, установлением минимального размера шарда в 600 нод.

 исток

Zilliqa шаг за шагом. Часть 2. Протокол консенсуса

Это вольный и краткий перевод статьи: https://blog.zilliqa.com/the-zilliqa-design-

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

Важность протокола консенсуса для высокой производительности сети

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

Идеальный протокол консенсуса для Zilliqa — этот тот, который мог бы поддерживать небольшой размер шарда (примерно 600 нод) и позволял быстро достигать консенсуса.

А как же консенсус протоколы, используемые в Bitcoin/Ethereum?

Внимательный читатель мог заметить, что размер шарда, указанный ранее, намного меньше, чем в стандартных P2P блокчейн сетях, таких как Bitcoin или Ethereum, где сеть формируется десятками тысяч нод. И у него может возникнуть вопрос, почему же Zilliqa не может использовать такой же протокол в каждом из шардов? Более того, так как размер шарда намного меньше, чем в других сетях, то и консенсус между нодами в шарде должен достигаться быстрее.

В реальности же один лишь размер шарда не приводит к ускорению механизма консенсуса.

Давайте более внимательно рассмотрим алгоритм консенсуса, применяемый в Bitcoin и Ethereum. Эти блокчейн платформы используют так называемый консенсус Накамото. Согласно этому механизму консенсуса, сеть «выбирает» лидера через определенные промежутки времени, и этот лидер предлагает блок. Затем, он передает этот блок и ноды либо принимают, либо отклоняют его.

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

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

Практическая византийская парадигма отказоустойчивости (PBFT) спешит на помощь

В Zilliqa используется протокол PBFT (практическая византийская парадигма отказоустойчивости) для достижения консенсуса в каждом шарде. Этот протокол был предложен Кастро и Лисков в 1999. При работе данного протокола считается, что до трети нод в каждом шарде могут быть нечестными (мошенническими).

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

В протоколе PBFT все ноды в группе (в шарде в нашем случае) имеют последовательность. Одна нода имеет статус главной (лидера), а остальные — вспомогательные. Процесс консенсуса проходит в три этапа:

1. Предварительная подготовка. На этом этапе лидер заявляет о новом блоке информации путем рассылки «предварительного сообщения».

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

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

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

Другие достоинства PBFT

1. Завершенность транзакций. В протоколе PBFT транзакции считаются завершенными после достижения консенсуса. Подтверждение транзакций не требуется. При консенсусе Накамото требуется верификация транзакций для защиты от атаки двойного расходования.

2. Низкое энергопотребление. Так как протокол PBFT не основан на вычислительных процессах, то он не требует значительных затрат энергии. Zilliqa использует PoW только для защиты от атак сивиллы и для идентификации нод, но не для достижения консенсуса. После идентификации начинается работа по протоколу PBFT, и повторная идентификация проводится, скажем, через каждые 100 блоков. При консенсусе Накамото PoW требуется для каждого блока.

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

Проблемы протокола PBFT

Протокол PBFT, безусловно, является подающим надежду способом достижения консенсуса в Zilliqa. Но у него есть один существенный недостаток: он работает эффективно только когда группа, достигающая консенсуса, мала (например, менее 50). Однако в Zilliqa используется размер шарда от 600 нод по причинам безопасности. В таком случае процесс коммуникации между нодами быстро становится узким местом, ведь каждая нода должна обмениваться сообщениями со всеми нодами в шарде.

Резюме

Один лишь механизм шардинга не достаточен для быстрой работы системы, поэтому требуется эффективный алгоритм консенсуса. Применяемый в Bitcoin/Ethereum алгоритм PoW не станет работать более эффективно при небольшом размере шарда, как в Zilliqa, так как зависит от общей вычислительной мощности сети.

В Zilliqa было принято решение использовать протокол PBFT (практическая византийская парадигма отказоустойчивости) для достижения консенсуса, так как он оптимален для небольшой сети. Кроме этого, PBFT обладает такими преимуществами как завершенность транзакций, низкое энергопотребление и меньшее различие между вознаграждениями майнеров.

При этом у PBFT есть один существенный недостаток: он работает эффективно только когда группа, достигающая консенсуса, мала (например, менее 50), в а в Zilliqa используется размер шарда от 600 нод по причинам безопасности.

Zilliqa шаг за шагом. Часть 3. Cоздание эффективного алгоритма консенсуса

Это вольный и краткий перевод статьи: https://blog.zilliqa.com/the-zilliqa-design-story-

В предыдущей статье мы уже упоминали о том, почему Zilliqa требуется другой протокол для консенсуса и почему классический консенсус Накамото (также известный как PoW) не идеален.

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

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

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

Стоимость обмена данными в pBFT протоколе

Данный протокол обязывает все честные ноды договариваться о состоянии системы. Таким образом, ноды находятся в постоянной связи друг с другом. В классической версии протокола, каждая нода взаимодействует со всеми остальными нодами для обмена сообщениями. Если каждая нода отсылает количество сообщений n, то общий требуемый объем обмена информацией будет примерно равен n².

Стоимость сообщений аутентификации

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

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

Имитовставка (МАС) является простым методом криптографии, который может генерировать такой тег. Одним из возможных способов создания МАС является применение кода аутентификации, использующего хеш-функцию.

Ниже приведен способ применения МАС отправителем и получателем. Отправитель генерирует тег, используя сообщение и секретный ключ, и отправляет его получателю вместе с самим сообщением. Получатель также генерирует тег и сравнивает его с присланным в сообщении. Если оба тега совпадают, то сообщение не было модифицировано в пути.

При применении данной технологии, каждая пара нод должна иметь свой секретный ключ. Таким образом, если в сети находится n количество нод, то необходимое количество ключей будет следующим: n(n-1)/2.

Давайте немного глубже проанализируем стоимость обмена данными при использовании МАС. Представим, что в сети работают 4 ноды: А, В, С и D. Нода А должна разослать сообщение всей сети, то есть, В, С и D. Таким образом, А должна сгенерировать 3 разных тега с индивидуальными ключами для В, С и D. Теперь представим что нода А хочет использовать В в качестве посредника для передачи тегов от Ак нодам С и D. В свою очередь, В использует ноду С в качестве посредника. Так как В уже получила индивидуальный тег, то она просто ретранслирует 2 оставшихся тега С и так далее. Общее количество переданных сообщений при такой «эстафете» составит: 3+2+1+=6.

Три разных тега, генерируемых А, обозначены разными цветами. Аотправляет 3 тега ноде В, которая отправляет оставшиеся 2 ноде С. Наконец, С перенаправляет последний тег, предназначенный для D.

В сети с количеством нод n, общее количество сообщений (в форме тегов) будет следующее: n + (n-1) + … + 1 = n (n+1)/2.

Криптография открытого ключа как средство повышения эффективности

Технологию МАС можно заменить цифровой подписью, которая и будет использоваться для верификации отправителя. Кастро и Лисков не применили цифровую подпись в своей работе лишь потому, что в то время вычисление МАС было намного дешевле, чем создание цифровой подписи. Сегодня же стоимость цифровой подписи невелика.

Более того, у криптографии открытого ключа есть свои преимущества. Давайте вернемся к рассмотренному ранее примеру с 4 нодами. Теперь представим, что у А, В, С и D есть цифровые подписи. Нода Аотправляет сообщение и добавляет к нему свою подпись. Сообщение доставляется ближайшей ноде, В. Обратите внимание, что А не нужно создавать 3 подписи в таком случае, одной подписи достаточно.

В получает сообщение и перенаправляет его вместе с подписью А к ноде С, и так далее. Общее количество сообщений в таком случае будет 1+1+1=3.

В сети с количеством нод n, общее количество сообщений будет следующее: 1 + 1 + 1 … (n-1) раз = n-1.

Идея замены МАС цифровой подписью уже выдвигалась ранее. Сокращение количества отправляемых сообщений действительно велико. Скажем, при n равном 600, количество отсылаемых сообщений снижается с 180300 до 599.

Уменьшение размера каждого сообщения путем использования мультиподписи.

Предположим, мы заменим МАС цифровой подписью в классическом протоколе pBFT. Теперь вопрос следующий: а есть ли что-то лучше цифровых подписей? Ответ «да», даже в этом случае есть место для улучшения, и давайте разберемся поподробнее, что именно мы можем усовершенствовать.

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

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

Упрощенная схема работы мультиподписи

При таком принципе работы у сети должны быть n количество элементов с правом подписи (публичные и приватные ключи); контролер, который верифицирует подпись; и агрегатор, который выполняет роль координатора и «собирает» подписи, отправленные каждым элементом n. Для простоты примера, будем считать, что каждая нода является честной и будет использоваться в подписи сообщения.

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

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

Например, единый публичный ключ = публичный ключ_1 + публичный ключ­_2 + … + публичный ключ_n.

На втором этапе агрегатор инициирует интерактивный протокол с каждой из нод. У этого протокола имеются три основные фазы работы:

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

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

3. Фаза отклика. Каждая нода отсылает ответ на поставленную задачу, который включает в себя использование приватного ключа.

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

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

Нода, закрашенная синим, агрегатор. Н — криптографическая хеш-функция, используемая для генерации задачи с сообщением m. Пара R и S является совокупной подписью. R имеет тот же размер что и R_i, а S имеет тот же размер что и S_i. Генерация отклика возможна при знании приватного ключа.

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

Заключение

Zilliqa использует несколько современных техник, которые повышают эффективность классического протокола pBFT.

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

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

Кроме этого, возможны ли атаки при использовании упрощенной версии протокола мультиподписи?

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

Резюме

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

Zilliqa использует практическую византийскую парадигму отказоустойчивости, или pBFT. Данный протокол быстр и не требует больших затрат энергии, но у его классической версии есть узкое место — достижение консенсуса при большом количестве нод в сети (требования Zilliqa включают наличие от 600 нод).

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