- PVSM.RU - https://www.pvsm.ru -
Перевод статьи подготовлен специально для студентов курса «Архитектор высоких нагрузок» [1], который стартует уже в этом месяце.
Всякий раз, когда новая транзакция транслируется по сети, узлы могут включить эту транзакцию в копию своего леджера или проигнорировать ее. Когда большинство участников сети принимают решение о принятии определенного состояния, достигается консенсус.
Фундаментальной проблемой в распределенных вычислениях [2] и многоагентных системах [3] является достижение общей надежности системы при наличии ряда нерабочих процессов. Зачастую для этого требуется, чтобы процессы согласовали между собой некоторое значение, которое понадобится во время вычисления. [4]
Эти процессы описываются как консенсус.
Чтобы консенсусный протокол был безопасным, он должен быть отказоустойчивым.
Для начала мы кратко поговорим о неразрешимой задаче двух генералов. Затем рассмотрим Задачу Византийских Генералов и обсудим Византийскую отказоустойчивость в распределенных и децентрализованных системах. А в самом конце поговорим о том, как это все относится к технологии блокчейн.
Эта задача, впервые опубликованная [5] в 1975 году и получившая свое название в 1978 году, описывает сценарий, когда два генерала атакуют общего врага. Первый генерал считается лидером, а второй – последователем. Армии каждого генерала по отдельности недостаточно, чтобы победить вражескую армию, поэтому им нужно сотрудничать и атаковать одновременно. Этот сценарий выглядит просто, но есть один нюанс:
Для того, чтобы они могли общаться и договариваться о времени, первый генерал должен отправить гонца через лагерь противника, он должен доставить послание с временем начала атаки второму генералу. Однако существует вероятность того, что гонец будет захвачен противниками, а послание – не доставлено. Это приведет к тому, что армия первого генерала пойдет в атаку, а второго останется стоять на месте.
Даже если первое послание будет доставлено, второй генерал должен подтвердить (ACK (acknowledge), обратите внимание на сходство с трехсторонним рукопожатием в TCP [6]), что он получил сообщение, поэтому он отправляет гонца обратно, тем самым воспроизводя предыдущий сценарий, где посланник может быть захвачен. Это перетекает в бесконечные ACK, и из-за этого генералы не могут достичь согласия.
Нет никакого способа гарантировать второе условие, то есть чтобы каждый генерал был в полной уверенности, что другой согласился с планом нападения. Оба генерала всегда будут в неведении, дошел ли гонец до его товарища.
Было доказано [7], что задача двух генералов неразрешима.
Описанная в 1982 году Лэмпортом, Шостаком и Пизом, версия этой задачи оказалось с изюминкой. Она описывает тот же сценарий, где вместо двух генералов о времени атаки должны договориться большее количество генералов. Дополнительная сложность заключается в том, что один или несколько генералов могут быть предателями, то есть они могут солгать о своих намерениях (например, генерал говорит, что он согласен атаковать в 09:00, но не сделает этого).
Парадигма лидера-последователя, описанная в задаче двух генералов, трансформируется в установку командир-подчиненный. Для достижения консенсуса здесь командир и каждый подчиненный должны договориться об одном и том же решении (об атаке или отступлении).
Перевод картинки:
Задача Византийских Генералов. Командующий генерал должен отправить приказ своим n-1 подчиненным, такой что:
- Все верноподданные подчиненные генералы подчиняются одному приказу.
- Если командующий генерал верноподданный, тогда все верные ему подчиненные подчиняются его приказам.
В добавок ко второму пункту нужно указать на интересный факт: если командир – предатель, то консенсус все равно должен быть достигнут. В результате все лейтенанты имеют большинство голосов.
Алгоритм достижения консенсуса в этом случае основан на значении большинства решений, которые видят подчиненные.
Теорема: Для любого 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 предателями я предлагаю вам прочитать эту статью [8].
Византийская отказоустойчивость является характеристикой, которая определяет систему, которая допускает класс отказов, который принадлежит Задаче Византийских Генералов. Византийский отказ – самый сложный класс видов отказов [9]. Он не подразумевает никаких ограничений и не делает предположений о том, какое поведение может иметь узел (например, узел может генерировать любые произвольные данные, выдавая себя за честного участника).
Византийские ошибки устранять сложнее всего. Византийская отказоустойчивость была необходима в системах двигателей самолетов, на атомных электростанциях и практически в любой системе, действия которой зависят от результатов работы большого количества датчиков. Даже SpaceX рассматривает ее как потенциальное требование [10] к своим системам.
Алгоритм, упомянутый в предыдущем разделе, отвечает византийской отказоустойчивости до тех пор, пока число предателей не превысит одной трети всех генералов. Существуют и другие варианты, облегчающие решение этой задачи, включая использование цифровых подписей или введения ограничений на связь между одноранговыми узлами.
Блокчейн – это децентрализованные леджеры, которые по определению не контролируются центральным органом. Из-за значений, хранящихся в них, злоумышленники имеют хороший экономический стимул, чтобы попытаться инициировать ошибку. Тем не менее, Византийская отказоустойчивость и, следовательно, решение проблемы византийских генералов для блокчейна просто необходимы.
В отсутствие Византийской Отказоустойчивости одноранговый узел может передавать и публиковать ложные транзакции, полностью сводя на нет надежность блокчейна. Что еще хуже, нет никакого центрального органа, который может взять на себя ответственность и исправить ущерб.
Когда был изобретен биткоин [11], большим прорывом стало использование доказательства работы [12] вероятностного решения задачи Византийских Генералов. Оно было подробно описано Сатоши Накамото в этом электронном письме [13].
В этой статье мы рассмотрели некоторые основные понятия консенсуса в распределенных системах.
Автор: MaxRokatansky
Источник [14]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/329741
Ссылки в тексте:
[1] «Архитектор высоких нагрузок»: https://otus.pw/y81W/
[2] распределенных вычислениях: https://en.wikipedia.org/wiki/Distributed_computing
[3] многоагентных системах: https://en.wikipedia.org/wiki/Multi-agent_system
[4] ачастую для этого требуется, чтобы процессы согласовали между собой некоторое значение, которое понадобится во время вычисления.: https://en.wikipedia.org/wiki/Consensus_(computer_science)
[5] задача, впервые опубликованная: http://hydra.infosys.tuwien.ac.at/teaching/courses/AdvancedDistributedSystems/download/1975_Akkoyunlu,%20Ekanadham,%20Huber_Some%20constraints%20and%20tradeoffs%20in%20the%20design%20of%20network%20communications.pdf
[6] TCP: https://en.wikipedia.org/wiki/Transmission_Control_Protocol
[7] Было доказано: https://en.wikipedia.org/wiki/Two_Generals%27_Problem#Proof
[8] статью: http://marknelson.us/2007/07/23/byzantine/
[9] видов отказов: https://en.wikipedia.org/wiki/Failure_cause
[10] потенциальное требование: https://lwn.net/Articles/540368/
[11] биткоин: https://bitcoin.org/bitcoin.pdf
[12] работы: https://en.bitcoin.it/wiki/Proof_of_work
[13] электронном письме: https://www.mail-archive.com/cryptography@metzdowd.com/msg09997.html
[14] Источник: https://habr.com/ru/post/467053/?utm_campaign=467053&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.