Перевод статьи подготовлен специально для студентов курса «Архитектор высоких нагрузок», который стартует уже в этом месяце.
Блокчейн – это децентрализованная система, состоящая из различных субъектов, которые действуют в зависимости от своих стимулов и имеющейся у них информации.
Всякий раз, когда новая транзакция транслируется по сети, узлы могут включить эту транзакцию в копию своего леджера или проигнорировать ее. Когда большинство участников сети принимают решение о принятии определенного состояния, достигается консенсус.
Фундаментальной проблемой в распределенных вычислениях и многоагентных системах является достижение общей надежности системы при наличии ряда нерабочих процессов. Зачастую для этого требуется, чтобы процессы согласовали между собой некоторое значение, которое понадобится во время вычисления.
Эти процессы описываются как консенсус.
Чтобы консенсусный протокол был безопасным, он должен быть отказоустойчивым.
Для начала мы кратко поговорим о неразрешимой задаче двух генералов. Затем рассмотрим Задачу Византийских Генералов и обсудим Византийскую отказоустойчивость в распределенных и децентрализованных системах. А в самом конце поговорим о том, как это все относится к технологии блокчейн.
Эта задача, впервые опубликованная в 1975 году и получившая свое название в 1978 году, описывает сценарий, когда два генерала атакуют общего врага. Первый генерал считается лидером, а второй – последователем. Армии каждого генерала по отдельности недостаточно, чтобы победить вражескую армию, поэтому им нужно сотрудничать и атаковать одновременно. Этот сценарий выглядит просто, но есть один нюанс:
Для того, чтобы они могли общаться и договариваться о времени, первый генерал должен отправить гонца через лагерь противника, он должен доставить послание с временем начала атаки второму генералу. Однако существует вероятность того, что гонец будет захвачен противниками, а послание – не доставлено. Это приведет к тому, что армия первого генерала пойдет в атаку, а второго останется стоять на месте.
Даже если первое послание будет доставлено, второй генерал должен подтвердить (ACK (acknowledge), обратите внимание на сходство с трехсторонним рукопожатием в TCP), что он получил сообщение, поэтому он отправляет гонца обратно, тем самым воспроизводя предыдущий сценарий, где посланник может быть захвачен. Это перетекает в бесконечные ACK, и из-за этого генералы не могут достичь согласия.
Нет никакого способа гарантировать второе условие, то есть чтобы каждый генерал был в полной уверенности, что другой согласился с планом нападения. Оба генерала всегда будут в неведении, дошел ли гонец до его товарища.
Было доказано, что задача двух генералов неразрешима.
Описанная в 1982 году Лэмпортом, Шостаком и Пизом, версия этой задачи оказалось с изюминкой. Она описывает тот же сценарий, где вместо двух генералов о времени атаки должны договориться большее количество генералов. Дополнительная сложность заключается в том, что один или несколько генералов могут быть предателями, то есть они могут солгать о своих намерениях (например, генерал говорит, что он согласен атаковать в 09:00, но не сделает этого).
Парадигма лидера-последователя, описанная в задаче двух генералов, трансформируется в установку командир-подчиненный. Для достижения консенсуса здесь командир и каждый подчиненный должны договориться об одном и том же решении (об атаке или отступлении).
В добавок ко второму пункту нужно указать на интересный факт: если командир – предатель, то консенсус все равно должен быть достигнут. В результате все лейтенанты имеют большинство голосов.
Алгоритм достижения консенсуса в этом случае основан на значении большинства решений, которые видят подчиненные.
Теорема: Для любого m, алгоритм OM(m) достигает консенсуса при более чем 3m генералов и максимум m предателях.
Это означает, что алгоритм может достичь консенсуса пока 2/3 участников честны. Если предателей больше 1/3, консенсус не достигается, армии не могут скоординировать свои атаки, и враг побеждает.
Алгоритм ОМ(0)
Алгоритм ОМ(m), m>0
При m=0 предателей нет, каждый подчиненный следует приказу. При m>0 каждый итоговый выбор подчиненного исходит из преобладающей части выборов всех подчиненных.
Будет понятнее, если вы посмотрите на ситуацию с точки зрения второго подчиненного – пускай С – Командир, а L{i} – это i-й подчиненный.
OM(1): Подчиненный 3 – предатель. Ситуация с точки зрения второго подчиненного.
Шаги:
Окончательное решение принимается из большинства голосов от L1, L2 и L3 и в результате достигается консенсус.
Важно помнить, что цель состоит в том, чтобы большинство подчиненных выбрало одно и то же решение, а не какое-то конкретное.
Давайте посмотрим на случай, когда командир – предатель.
OM(1): Командир – предатель.
Шаги:
Они все имеют одинаковую ценность, таким образом достигается консенсус. Обратите внимание, что даже если значения x, y, z – все разные, значение большинство(x, y, z) одинаково для всех трех подчиненных. В случае, если x, y, z – совершенно разные приказы, мы можем предположить, что они будут действовать по дефолтному плану – ОТСТУПИТЬ.
Чтобы посмотреть на практический подход к более сложному примеру с 7 генералами и 3 предателями я предлагаю вам прочитать эту статью.
Византийская отказоустойчивость является характеристикой, которая определяет систему, которая допускает класс отказов, который принадлежит Задаче Византийских Генералов. Византийский отказ – самый сложный класс видов отказов. Он не подразумевает никаких ограничений и не делает предположений о том, какое поведение может иметь узел (например, узел может генерировать любые произвольные данные, выдавая себя за честного участника).
Византийские ошибки устранять сложнее всего. Византийская отказоустойчивость была необходима в системах двигателей самолетов, на атомных электростанциях и практически в любой системе, действия которой зависят от результатов работы большого количества датчиков. Даже SpaceX рассматривает ее как потенциальное требование к своим системам.
Алгоритм, упомянутый в предыдущем разделе, отвечает византийской отказоустойчивости до тех пор, пока число предателей не превысит одной трети всех генералов. Существуют и другие варианты, облегчающие решение этой задачи, включая использование цифровых подписей или введения ограничений на связь между одноранговыми узлами.
Блокчейн – это децентрализованные леджеры, которые по определению не контролируются центральным органом. Из-за значений, хранящихся в них, злоумышленники имеют хороший экономический стимул, чтобы попытаться инициировать ошибку. Тем не менее, Византийская отказоустойчивость и, следовательно, решение проблемы византийских генералов для блокчейна просто необходимы.
В отсутствие Византийской Отказоустойчивости одноранговый узел может передавать и публиковать ложные транзакции, полностью сводя на нет надежность блокчейна. Что еще хуже, нет никакого центрального органа, который может взять на себя ответственность и исправить ущерб.
Когда был изобретен биткоин, большим прорывом стало использование доказательства работы вероятностного решения задачи Византийских Генералов. Оно было подробно описано Сатоши Накамото в этом электронном письме.
В этой статье мы рассмотрели некоторые основные понятия консенсуса в распределенных системах.
Блокчейн – это децентрализованная система, состоящая из различных субъектов, которые действуют в зависимости от своих стимулов и имеющейся у них информации.
Всякий раз, когда новая транзакция транслируется по сети, узлы могут включить эту транзакцию в копию своего леджера или проигнорировать ее. Когда большинство участников сети принимают решение о принятии определенного состояния, достигается консенсус.
Фундаментальной проблемой в распределенных вычислениях и многоагентных системах является достижение общей надежности системы при наличии ряда нерабочих процессов. Зачастую для этого требуется, чтобы процессы согласовали между собой некоторое значение, которое понадобится во время вычисления.
Эти процессы описываются как консенсус.
- Что происходит, когда участник решает не следовать правилам и вмешаться в состояние своего леджера?
- Что происходит, когда таких участников в сети достаточно много, но не большинство?
Чтобы консенсусный протокол был безопасным, он должен быть отказоустойчивым.
Для начала мы кратко поговорим о неразрешимой задаче двух генералов. Затем рассмотрим Задачу Византийских Генералов и обсудим Византийскую отказоустойчивость в распределенных и децентрализованных системах. А в самом конце поговорим о том, как это все относится к технологии блокчейн.
Задача двух генералов
Эта задача, впервые опубликованная в 1975 году и получившая свое название в 1978 году, описывает сценарий, когда два генерала атакуют общего врага. Первый генерал считается лидером, а второй – последователем. Армии каждого генерала по отдельности недостаточно, чтобы победить вражескую армию, поэтому им нужно сотрудничать и атаковать одновременно. Этот сценарий выглядит просто, но есть один нюанс:
Для того, чтобы они могли общаться и договариваться о времени, первый генерал должен отправить гонца через лагерь противника, он должен доставить послание с временем начала атаки второму генералу. Однако существует вероятность того, что гонец будет захвачен противниками, а послание – не доставлено. Это приведет к тому, что армия первого генерала пойдет в атаку, а второго останется стоять на месте.
Даже если первое послание будет доставлено, второй генерал должен подтвердить (ACK (acknowledge), обратите внимание на сходство с трехсторонним рукопожатием в TCP), что он получил сообщение, поэтому он отправляет гонца обратно, тем самым воспроизводя предыдущий сценарий, где посланник может быть захвачен. Это перетекает в бесконечные ACK, и из-за этого генералы не могут достичь согласия.
Нет никакого способа гарантировать второе условие, то есть чтобы каждый генерал был в полной уверенности, что другой согласился с планом нападения. Оба генерала всегда будут в неведении, дошел ли гонец до его товарища.
Было доказано, что задача двух генералов неразрешима.
Задача Византийских Генералов
Описанная в 1982 году Лэмпортом, Шостаком и Пизом, версия этой задачи оказалось с изюминкой. Она описывает тот же сценарий, где вместо двух генералов о времени атаки должны договориться большее количество генералов. Дополнительная сложность заключается в том, что один или несколько генералов могут быть предателями, то есть они могут солгать о своих намерениях (например, генерал говорит, что он согласен атаковать в 09:00, но не сделает этого).
Парадигма лидера-последователя, описанная в задаче двух генералов, трансформируется в установку командир-подчиненный. Для достижения консенсуса здесь командир и каждый подчиненный должны договориться об одном и том же решении (об атаке или отступлении).
Перевод картинки:
Задача Византийских Генералов. Командующий генерал должен отправить приказ своим n-1 подчиненным, такой что:
- Все верноподданные подчиненные генералы подчиняются одному приказу.
- Если командующий генерал верноподданный, тогда все верные ему подчиненные подчиняются его приказам.
В добавок ко второму пункту нужно указать на интересный факт: если командир – предатель, то консенсус все равно должен быть достигнут. В результате все лейтенанты имеют большинство голосов.
Алгоритм достижения консенсуса в этом случае основан на значении большинства решений, которые видят подчиненные.
Теорема: Для любого m, алгоритм OM(m) достигает консенсуса при более чем 3m генералов и максимум m предателях.
Это означает, что алгоритм может достичь консенсуса пока 2/3 участников честны. Если предателей больше 1/3, консенсус не достигается, армии не могут скоординировать свои атаки, и враг побеждает.
Алгоритм ОМ(0)
- Командир отправляет свое значение каждому из подчиненных.
- Каждый подчиненный использует значение, которое он получает от командира, или использует значение ОТСТУПИТЬ, если не получает никакого значения.
Алгоритм ОМ(m), m>0
- Командир отправляет с свое значение каждому из подчиненных.
- Для каждого i, пусть vi будет значением, которое i-й подчиненный получает от командира, либо же будет использовано значение ОТСТУПИТЬ, если подчиненный не получает никакого значения. i-й подчиненный выступает в качестве командира в Алгоритме ОМ(m-1) и отправляет значение каждому из n-2 оставшихся подчиненных.
- Для каждого i, при условии, что ji, пусть vj будет значением, которое i-й подчиненный получил от j-ого подчиненного на шаге (2) (используя Алгоритм ОМ(m-1)), или использует значение ОТСТУПИТЬ, если не получает никакого значения. i-й подчиненный использует значение большинства (v1, …, vn-1).
При m=0 предателей нет, каждый подчиненный следует приказу. При m>0 каждый итоговый выбор подчиненного исходит из преобладающей части выборов всех подчиненных.
Будет понятнее, если вы посмотрите на ситуацию с точки зрения второго подчиненного – пускай С – Командир, а L{i} – это i-й подчиненный.
OM(1): Подчиненный 3 – предатель. Ситуация с точки зрения второго подчиненного.
Шаги:
- Командир отправляет v всем подчиненным.
- L1 посылает L2 значение v или L3 отправляет L2 значение x.
- L2 ← большинство(v,v,x) == v
Окончательное решение принимается из большинства голосов от L1, L2 и L3 и в результате достигается консенсус.
Важно помнить, что цель состоит в том, чтобы большинство подчиненных выбрало одно и то же решение, а не какое-то конкретное.
Давайте посмотрим на случай, когда командир – предатель.
OM(1): Командир – предатель.
Шаги:
- Командир посылает L1, L2, L3 значения x, y, z соответственно;
- L1 посылает значение x подчиненным L2, L3 | L2 посылает L1, L3 значение y | L3 посылает L1, L2 значение z;
- L1 ← большинство(x, y, z) | L2 ← большинство(x, y, z) | L3 ← большинство(x, y, z)
Они все имеют одинаковую ценность, таким образом достигается консенсус. Обратите внимание, что даже если значения x, y, z – все разные, значение большинство(x, y, z) одинаково для всех трех подчиненных. В случае, если x, y, z – совершенно разные приказы, мы можем предположить, что они будут действовать по дефолтному плану – ОТСТУПИТЬ.
Чтобы посмотреть на практический подход к более сложному примеру с 7 генералами и 3 предателями я предлагаю вам прочитать эту статью.
Византийская отказоустойчивость
Византийская отказоустойчивость является характеристикой, которая определяет систему, которая допускает класс отказов, который принадлежит Задаче Византийских Генералов. Византийский отказ – самый сложный класс видов отказов. Он не подразумевает никаких ограничений и не делает предположений о том, какое поведение может иметь узел (например, узел может генерировать любые произвольные данные, выдавая себя за честного участника).
Византийские ошибки устранять сложнее всего. Византийская отказоустойчивость была необходима в системах двигателей самолетов, на атомных электростанциях и практически в любой системе, действия которой зависят от результатов работы большого количества датчиков. Даже SpaceX рассматривает ее как потенциальное требование к своим системам.
Алгоритм, упомянутый в предыдущем разделе, отвечает византийской отказоустойчивости до тех пор, пока число предателей не превысит одной трети всех генералов. Существуют и другие варианты, облегчающие решение этой задачи, включая использование цифровых подписей или введения ограничений на связь между одноранговыми узлами.
Как это все относится к блокчейну?
Блокчейн – это децентрализованные леджеры, которые по определению не контролируются центральным органом. Из-за значений, хранящихся в них, злоумышленники имеют хороший экономический стимул, чтобы попытаться инициировать ошибку. Тем не менее, Византийская отказоустойчивость и, следовательно, решение проблемы византийских генералов для блокчейна просто необходимы.
В отсутствие Византийской Отказоустойчивости одноранговый узел может передавать и публиковать ложные транзакции, полностью сводя на нет надежность блокчейна. Что еще хуже, нет никакого центрального органа, который может взять на себя ответственность и исправить ущерб.
Когда был изобретен биткоин, большим прорывом стало использование доказательства работы вероятностного решения задачи Византийских Генералов. Оно было подробно описано Сатоши Накамото в этом электронном письме.
Заключение
В этой статье мы рассмотрели некоторые основные понятия консенсуса в распределенных системах.
