Хабрахабр

[Перевод] Разбираемся в основах Blockchain: Задача Византийских Генералов. Часть 1

Перевод статьи подготовлен специально для студентов курса «Архитектор высоких нагрузок», который стартует уже в этом месяце.

Блокчейн – это децентрализованная система, состоящая из различных субъектов, которые действуют в зависимости от своих стимулов и имеющейся у них информации.

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

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

Эти процессы описываются как консенсус.

  • Что происходит, когда участник решает не следовать правилам и вмешаться в состояние своего леджера?
  • Что происходит, когда таких участников в сети достаточно много, но не большинство?

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

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

Задача двух генералов

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

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

Это перетекает в бесконечные ACK, и из-за этого генералы не могут достичь согласия. Даже если первое послание будет доставлено, второй генерал должен подтвердить (ACK (acknowledge), обратите внимание на сходство с трехсторонним рукопожатием в TCP), что он получил сообщение, поэтому он отправляет гонца обратно, тем самым воспроизводя предыдущий сценарий, где посланник может быть захвачен.

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

Было доказано, что задача двух генералов неразрешима.

Задача Византийских Генералов

Описанная в 1982 году Лэмпортом, Шостаком и Пизом, версия этой задачи оказалось с изюминкой. Она описывает тот же сценарий, где вместо двух генералов о времени атаки должны договориться большее количество генералов. Дополнительная сложность заключается в том, что один или несколько генералов могут быть предателями, то есть они могут солгать о своих намерениях (например, генерал говорит, что он согласен атаковать в 09:00, но не сделает этого).

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

Перевод картинки:

Командующий генерал должен отправить приказ своим n-1 подчиненным, такой что: Задача Византийских Генералов.

  • Все верноподданные подчиненные генералы подчиняются одному приказу.
  • Если командующий генерал верноподданный, тогда все верные ему подчиненные подчиняются его приказам.

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

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

Теорема: Для любого m, алгоритм OM(m) достигает консенсуса при более чем 3m генералов и максимум m предателях.

Если предателей больше 1/3, консенсус не достигается, армии не могут скоординировать свои атаки, и враг побеждает. Это означает, что алгоритм может достичь консенсуса пока 2/3 участников честны.

Алгоритм ОМ(0)

  1. Командир отправляет свое значение каждому из подчиненных.
  2. Каждый подчиненный использует значение, которое он получает от командира, или использует значение ОТСТУПИТЬ, если не получает никакого значения.


Алгоритм ОМ(m), m>0

  1. Командир отправляет с свое значение каждому из подчиненных.
  2. Для каждого i, пусть vi будет значением, которое i-й подчиненный получает от командира, либо же будет использовано значение ОТСТУПИТЬ, если подчиненный не получает никакого значения. i-й подчиненный выступает в качестве командира в Алгоритме ОМ(m-1) и отправляет значение каждому из n-2 оставшихся подчиненных.
  3. Для каждого i, при условии, что ji, пусть vj будет значением, которое i-й подчиненный получил от j-ого подчиненного на шаге (2) (используя Алгоритм ОМ(m-1)), или использует значение ОТСТУПИТЬ, если не получает никакого значения. i-й подчиненный использует значение большинства (v1, …, vn-1).

При m=0 предателей нет, каждый подчиненный следует приказу. При m>0 каждый итоговый выбор подчиненного исходит из преобладающей части выборов всех подчиненных.
Будет понятнее, если вы посмотрите на ситуацию с точки зрения второго подчиненного – пускай С – Командир, а L – это i-й подчиненный.

Ситуация с точки зрения второго подчиненного. OM(1): Подчиненный 3 – предатель.

Шаги:

  1. Командир отправляет v всем подчиненным.
  2. L1 посылает L2 значение v или L3 отправляет L2 значение x.
  3. L2 ← большинство(v,v,x) == v

Окончательное решение принимается из большинства голосов от L1, L2 и L3 и в результате достигается консенсус.

Важно помнить, что цель состоит в том, чтобы большинство подчиненных выбрало одно и то же решение, а не какое-то конкретное.

Давайте посмотрим на случай, когда командир – предатель.

OM(1): Командир – предатель.

Шаги:

  1. Командир посылает L1, L2, L3 значения x, y, z соответственно;
  2. L1 посылает значение x подчиненным L2, L3 | L2 посылает L1, L3 значение y | L3 посылает L1, L2 значение z;
  3. L1 ← большинство(x, y, z) | L2 ← большинство(x, y, z) | L3 ← большинство(x, y, z)

Они все имеют одинаковую ценность, таким образом достигается консенсус. Обратите внимание, что даже если значения x, y, z – все разные, значение большинство(x, y, z) одинаково для всех трех подчиненных. В случае, если x, y, z – совершенно разные приказы, мы можем предположить, что они будут действовать по дефолтному плану – ОТСТУПИТЬ.

Чтобы посмотреть на практический подход к более сложному примеру с 7 генералами и 3 предателями я предлагаю вам прочитать эту статью.

Византийская отказоустойчивость

Византийская отказоустойчивость является характеристикой, которая определяет систему, которая допускает класс отказов, который принадлежит Задаче Византийских Генералов. Византийский отказ – самый сложный класс видов отказов. Он не подразумевает никаких ограничений и не делает предположений о том, какое поведение может иметь узел (например, узел может генерировать любые произвольные данные, выдавая себя за честного участника).

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

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

Как это все относится к блокчейну?

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

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

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

Заключение

В этой статье мы рассмотрели некоторые основные понятия консенсуса в распределенных системах.

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»