Zilliqa шаг за шагом. Часть 3. Cоздание эффективного алгоритма консенсуса
Это вольный и краткий перевод статьи: https://blog.zilliqa.com/the-zilliqa-design-story-piece-by-piece-part-3-making-consensus-efficient-7a9c569a8f0e
Перевод подготовлен Mia, специально для канала @miacoins
Все мои новые публикации вы можете читать теперь на busy.org
В предыдущей статье мы уже упоминали о том, почему 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 нод).
Данной проблемы можно избежать путем применения имитовставки (МАС), однако, данный метод устарел, и цифровая подпись более актуальна. Вместе с тем, метод мультиподписи является наиболее современным на сегодняшний день, так как он позволяет эффективно сократить количество отсылаемых сообщений. Этот метод требует доработки, так как под вопросом остается работа протокола в ситуации, когда не все ноды подписывают сообщение.
***
Это вольный и краткий перевод статьи: https://blog.zilliqa.com/the-zilliqa-design-story-piece-by-piece-part-3-making-consensus-efficient-7a9c569a8f0e
Перевод подготовлен Mia, специально для канала @miacoins
Все мои новые публикации вы можете читать теперь на busy.org
