Говоря о распределенных системах, проблеме византийских генералов и блокчейне

база данных Архитектура сервер алгоритм блокчейн
Говоря о распределенных системах, проблеме византийских генералов и блокчейне

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

Но мы сегодня анализируем только технологии. С технической точки зрения блокчейн — это распределенная система и связанные с ней технологии. Какова связь между ее различными концепциями и распределенными системами? Эта статья воспользуется этой возможностью сегодня, чтобы вместе с вами обсудить основные вопросы и концепции распределенных систем. Наконец, мы попробуем логически связные идеи, обсудим технологию блокчейн.

Распределенные системы и вопросы согласованности

Система, поддерживаемая технологией блокчейна, такая как сеть Биткойн или Эфириум, технически представляет собой огромную распределенную систему. Итак, давайте сначала начнем с распределенных систем.

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

На самом деле, проблема согласованности (consensus problem) — основная проблема, которую должна решить распределенная система. Распределенная система обычно состоит из нескольких узлов с одинаковым статусом, и взаимодействие между каждым узлом подобно тому, как несколько человек собираются вместе для обсуждения проблем. Представим более конкретный сценарий: например, трое обсуждают, где поесть в полдень, первый сказал, что поблизости только что открылся хот-пот ресторан, и слышал, что там очень вкусно, а второй сказал, нет, ешьте горячие горшки с цветами Это было слишком долго, так что давайте просто выпьем каши, и третий человек сказал, Я только вчера был в том магазине каши, и это было очень плохо, так что я мог бы также пойти в Макдональдс. В результате все трое зашли в тупик и так и не пришли к соглашению.

Некоторые люди говорят, что это непросто решить, пожалуйста, проголосуйте. Итак, три человека проголосовали, и каждый по-прежнему настаивал на своем, а проблема так и не была решена. У кого-то другая идея, мы просто выбираем лидера и слушаем, что он говорит, чтобы всем не пришлось драться. Итак, все начали голосовать за лидера. Результат был трагичен, каждый чувствовал, что он должен быть лидером. В конце концов все трое обнаружили, что вопрос «выбора лидера» по сути такой же, как и первоначальный вопрос «где поесть», и решить его так же сложно.

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

Поэтому какие-то умные люди разработали протокол консенсуса, вроде наших обычных, таких как Paxos, Raft, Zab и им подобных. Подобно обсуждению предыдущих нескольких человек, если перевести на термины Paxos, это эквивалентно тому, что каждый узел может сделать свое собственное предложение (называемое предложением, которое содержит конкретное значение предложения), а конечной целью соглашения является что каждый узел достигает по определенным правилам.То же предложение. Но чье предложение победит? Правило, которое мы можем легко представить, может быть таким: какой бы узел ни предложил предложение первым, какой бы ни предложил, предложение, сделанное позже, недействительно. Однако в распределенной системе ситуация сложнее, чем группа людей, собирающихся вместе для обсуждения проблемы, а также существует проблема сетевой задержки, из-за которой вам сложно глобально упорядочить все происходящие события. В качестве простого примера предположим, что узлы A и B отправляют свои предложения узлам X и Y почти одновременно, но из-за разной задержки сообщений в сети окончательный результат таков: X сначала получает предложение A, а затем получает предложение B. ; но Y как раз наоборот, он сначала получил предложение B, а затем получил предложение A. Таким образом, с точки зрения X и Y соответственно, трудно прийти к соглашению о том, кто будет первым.

Кроме того, ситуация усложняется, когда рассматривается возможность простоя узла и потери сообщений. Простой узла можно рассматривать как частный случай потери сообщения, что равносильно потере всех сообщений, отправленных на этот узел. это вCAPВ теоретической структуре это эквивалентно разделению сети, что соответствует P в CAP. Почему время простоя узла и потеря сообщений могут быть связаны с сегментацией сети? Потому что эти случаи практически неразличимы. Например, есть несколько узлов, с которыми невозможно связаться, то есть для других узлов сообщения, которые они посылают этим узлам, не могут быть получены без ответа. Настоящая причина может заключаться в том, что сеть заблокирована, узлы назначения могут быть отключены или сообщение может быть задержано на неопределенный срок. Одним словом, только потому, что с некоторыми узлами в системе невозможно связаться, они больше не могут участвовать в принятии решений, но это не значит, что их нельзя снова подключить через какой-то промежуток времени.

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

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

Проблема византийских генералов

Протокол консенсуса, который мы обсуждали ранее, имеет важное предварительное условие: каждому узлу можно доверять, и все они строго соблюдают один и тот же набор правил. Это условие можно считать в основном выполненным во внутренней сети компании. Но что делать, если это условие не выполняется? Предполагая, что некоторые узлы в сети являются вредоносными, они не только не следуют протоколу, но и намеренно создают проблемы (например, отправляют сообщения случайным образом), могут ли другие нормальные узлы работать без сбоев?

В теории распределенных систем эта проблема абстрагируется в хорошо известную проблему — проблему византийских генералов. Этим вопросом задавался известныйLeslie Lamportпредложил, то есть автор Paxos. В то же время Лэмпорт также является лауреатом премии Тьюринга в 2013 году.

Он начинается с истории (которую, конечно же, выдумал Лэмпорт). Несколько армий Византийской империи атаковали вне города противника, а затем разделились. Каждую армию возглавлял византийский генерал. Чтобы сформулировать единый план сражения, каждому генералу необходимо общаться с другими генералами через мессенджеры. Однако среди византийских полководцев могли быть и предатели. Цель этих генералов-отступников — сорвать план битвы, согласованный другими лояльными генералами. Они могут делать что угодно для этой цели, например, вступать в сговор, преднамеренно распространять ложные новости или вообще не распространять никаких новостей.

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

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

  • A, Все верные генералы получают одинаковый (последовательный) план сражения. Например, они все решили атаковать, или они все решили отступить, а не одни генералы, которые думали, что должны атаковать, а другие генералы решили отступить.
  • BВерные генералы не только получают один и тот же план боя, но и должны следить за тем, чтобы полученный план боя был разумным (разумным). Например, атака была более выгодным боевым планом, но из-за обструкции предателей окончательно был сформулирован план отступления вместе. Таким образом, наш алгоритм не работает.

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

Сначала давайте рассмотрим процесс, с помощью которого генералы составляют планы сражения (при условии, что предателей нет). Каждый генерал давал свой предполагаемый план боя — наступление или отступление — исходя из собственных наблюдений за обстановкой. Затем каждый генерал передал свои оперативные рекомендации каждому из других генералов через посланника. Теперь каждый генерал знает оперативные советы других генералов, а также свои собственные оперативные советы, и ему необходимо получить окончательный оперативный план на основе всей этой информации. Чтобы сделать выражение более ясным, мы нумеруем каждого генерала как 1, 2, ..., n, а боевые предложения, сделанные каждым генералом, записывают как v (1), v (2), ..., v ( n), всего n значений, некоторые из которых представляют «атаку», а некоторые — «отступление». После того, как посыльный доставляет сообщение, каждый генерал видит одинаковые боевые предложения v(1), v(2), ..., v(n), разумеется, одно из которых предлагает сам текущий генерал. Затем, пока каждый генерал использует один и тот же метод для объединения всей информации v (1), v (2), ..., v (n), может быть получен один и тот же окончательный план битвы. Например, метод, который легко придумать, — это метод голосования, то есть голосование по различным планам битвы в v(1), v(2), ..., v(n) и, наконец, выбор плана битвы. с наибольшим количеством голосов.

Конечно, итоговый план битвы не обязательно будет лучшим, но это должно быть лучшее, что мы можем сделать. Мы по-прежнему предполагаем, что среди генералов нет предателей. Мы обнаружили, что вышеупомянутые требования для целей A и B можно было бы соответствующим образом «снизить»: мы больше не сосредотачиваемся на том, смогут ли генералы достичь в конечном счете согласованного оперативного плана и является ли план «разумным»; генерал получил точно такие же оперативные рекомендации v(1), v(2), ..., v(n). Пока каждый генерал получает одни и те же оперативные рекомендации и объединяет их одинаковым образом, легко прийти к окончательному и последовательному оперативному плану. Что касается того, является ли этот окончательный план битвы лучшим, то это связано со многими «человеческими» факторами, и нас это не волнует.

Теперь считаем предателей среди генералов. Следуя предыдущему ходу мыслей, мы по-прежнему хотим, чтобы каждый генерал получал одни и те же оперативные рекомендации v(1), v(2), ..., v(n). Теперь давайте подробнее рассмотрим одно из этих значений, v(i), которое в предыдущем описании представляет собой предложение войны от i-го генерала. Если i-й генерал лоялен, то в этом определении нет ничего плохого. Однако, если i-й генерал предатель, то возникает проблема. Зачем? Поскольку предатель может делать все, что захочет, для того, чтобы сорвать постановку всего плана сражения, он вполне может давать разные боевые предложения разным генералам. При этом разные лояльные генералы могут получать разные значения v(i) от i-го генерала. Таким образом, определение v(i) неверно, и его необходимо изменить.

В любом случае, даже если есть предатели, мы надеемся, что каждый генерал в конечном итоге будет агрегирован на основе точно таких же боевых предложений, которые все еще записываются как v(1), v(2), ..., v(n) . Однако v(i) здесь больше не представляет боевое предложение от i-го генерала, а i-е предложение, которое каждый генерал наконец видит после обработки разработанным нами алгоритмом консенсуса. Здесь можно обсудить две ситуации. Прежде всего, в первом случае, если i-й генерал лоялен, то мы, естественно, надеемся, что это v(i) и есть боевое предложение, присланное i-м генералом. Другими словами, мы надеемся, что после алгоритма консенсуса, если i-й генерал лоялен, его предложение можно будет добросовестно передать другим генералам, не беспокоясь о поведении предателя. Это является предпосылкой того, что может быть разработан «разумный» оперативный план. Во втором случае, если i-й генерал предатель, то он может послать разные предложения разным генералам. На данный момент мы можем не просто слушать его слова, а надеяться, что после обработки алгоритмом консенсуса генералы полностью обменяются мнениями, и тогда на основе информации, переданной другими генералами, мы сможем всесторонне судить, чтобы получить av( я). Неважно, атакует ли этот v(i) или отступает, главное, чтобы каждый генерал получил один и тот же v(i) . Только так, просуммировав все v(1), v(2), ..., v(n), генералы могут получить окончательный и вполне непротиворечивый план сражения.

Из приведенного выше анализа мы находим, что в обоих случаях нам нужно только обратить внимание на то, как предложение, сделанное одним генералом (то есть i-м генералом), передается другим генералам. Дело наконец здесь! На этом этапе мы можем свести исходную проблему к подзадаче. Эта подзадачаLeslie LamportПроблема в его статье действительно называется «Проблема византийских генералов». В этой задаче мы ориентируемся только на одного генерала, отдающего приказ, называем его командующим генералом, а остальных генералов, получающих приказ, — лейтенантом. Ниже приводится точное описание «проблемы византийских генералов».

Учитель отправит заказы на N-1 Lieutenants, как можно обеспечить следующие два условия:

  • (IC1) Все лояльные лейтенанты в конечном итоге получают одни и те же приказы.
  • (IC2) Если генерал лоялен, то все лояльные лейтенанты принимают приказы генерала.

Фактически это соответствует двум ситуациям, которые мы обсуждали ранее. Если генерал лоялен, то условие IC2 гарантирует, что приказ будет доставлен добросовестно, и тогда естественно выполняется условие IC1; если генерал предатель, то условие IC2 бессмысленно, а условие IC1 гарантируется, даже если предатель Главный будет на каждого адъютанта отдавать разные приказы и каждый адъютант все равно в итоге получит согласованный приказ.

Есть два места, где может возникнуть путаница.

Во-первых, спросят некоторые, может ли Господь быть предателем? Генералы все предатели, что тут еще делать? На самом деле это так, эта «проблема византийских генералов» является лишь подзадачей исходной проблемы. Когда n генералов решают план сражения путем передачи сообщений, его можно разложить на n «проблему византийских генералов», то есть каждый генерал является главным генералом, а остальные n-1 генералов — адъютантами. Если существует алгоритм, который может решить «Проблему византийских генералов», то одновременный запуск n экземпляров алгоритма позволит каждому генералу получить точно такую ​​же последовательность боевых рекомендаций, а именно v(1), v(2) как мы упоминали ранее. , ..., v(n). Наконец, каждый генерал объединяет v(1), v(2), ..., v(n), используя один и тот же метод (например, голосование большинством), чтобы получить окончательный план битвы.

Во-вторых, когда генерал-предатель, он может отдавать разные приказы разным лейтенантам, как это возможно, что каждый лейтенант может получить один и тот же приказ? Это именно то, что алгоритм должен решить. На самом деле, это тоже легко объяснимо (об этой мысли мы также упоминали ранее), так как адъютант может посылать разные приказы разным адъютантам, адъютант не может напрямую принять приказ, посланный адъютантом, а должен также смотреть, что передали другие адъютанты .Каков приказ командира. Затем адъютант может получить более полную информацию после синтеза приказов, переданных всеми адъютантами (плюс приказы, отправленные непосредственно генералом), чтобы сделать последовательное суждение (на практике это непрерывный итеративный процесс).

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

Упомянем здесь только выводы алгоритма, приведенные в статье.

Используя разные модели сообщений, «Проблема византийских генералов» имеет разные решения.

  • Если между генералами используются устные сообщения, т. е. сообщения могут быть подделаны при их передаче, то для борьбы с m предателями требуется не менее 3m+1 генералов (из которых требуется не менее 2m+1 генералов).
  • Если между генералами используются подписанные сообщения, то есть сообщение не может быть подделано после его отправки, и оно будет обнаружено до тех пор, пока оно подделывается, то для борьбы с m предателями потребуется только не менее m+2 генералов. Нужны, а это означает как минимум 2 лояльных генерала (если есть только 1 лояльный генерал, очевидно, вопрос не имеет смысла). Эта ситуация фактически сводится к неограниченному количеству лояльных генералов.

Отказоустойчивость

Как мы упоминали ранее, протокол распределенного консенсуса, представленный Paxos, работает в доверенной среде. В «Проблеме византийских генералов» в сети есть вредоносные узлы. Поэтому нам легко составить представление: является ли Паксос частным случаем решения «проблемы византийских генералов», когда число предателей равно нулю?

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

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

Это «византийская неисправная толерантность» и отношения между такими распределенными пассуссуссосом Paxos Consensus должны быть как его лечить? Наш анализ может произойти от прочности степени отказоустойчивости.

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

  • Византийская вина. Такие ошибки могут непоследовательно казаться разным наблюдателям.
  • Невизантийская вина. Буквально это относится к другим ошибкам, не относящимся к первой категории.

Значение этих двух типов ошибок не так хорошо понятно на первый взгляд.

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

Посмотрите еще раз на невизантийские ошибки. Лэмпорт также использует термин «невизантийский» в одной из своих статей о Паксосе (см.Paxos Made Simple"). Но название слова делает людей немного трудными для понимания. В распределенной системе, если узел выйдет из строя или сеть выйдет из строя, некоторые узлы не будут работать. На самом деле, другие узлы не могут различить эти две ситуации, а только обнаруживают, что узел временно недоступен (то есть время приема сообщения истекло). Что касается того, связано ли это с проблемой самого узла, или сеть заблокирована, или сообщение имеет серьезную задержку, то это неразличимо. Также через некоторое время узел может восстановиться (либо сам по себе, либо при вмешательстве человека). Другими словами, для узла с этой ошибкой мы получаем не только его сообщение, но и не сообщение об ошибке от него. Вместо этого само сообщение является «верным», пока получено сообщение от него.

Видно, что византийские ошибки являются более сильным классом ошибок. В «Проблеме византийских генералов» византийской ошибкой является отправка предателем непоследовательных боевых советов; невизантийская ошибка — не отправлять никаких сообщений. Следовательно, алгоритм решения «Задачи византийских генералов» может обрабатывать как византийские, так и невизантийские ошибки. Звучит немного странно, но это просто проблема с названием.

В заключение, решение «Проблемы византийского генерала» должно быть самым сильным классом алгоритмов распределенного консенсуса, которые теоретически могут обрабатывать любую ошибку. А Paxos может обрабатывать только невизантийские ошибки. Эта отказоустойчивость, которая может обрабатывать византийские ошибки, часто упоминается как "Byzantine fault tolerance», именуемый БФТ.

Таким образом, алгоритм BFT должен быть в состоянии решить проблему распределенной согласованности при любой ошибке, включая проблему, решаемую Paxos. Так почему бы не использовать алгоритм BFT единообразно для решения всех проблем распределенной непротиворечивости? Зачем разрабатывать некоторые алгоритмы, такие как Paxos? Мы не обсуждали подробно алгоритм решения «Задачи византийских генералов» ранее, поэтому не будем проводить здесь тщательный анализ. Но легко представить, что за столь высокую устойчивость к ошибкам BFT приходится платить высокую цену. Например, необходимость массовой доставки сообщений. Paxos не нужно обеспечивать такую ​​высокую отказоустойчивость, поэтому он может работать более эффективно. Кроме того, специфичный для алгоритма, приведенного в статье Лэмпорта для решения «задачи византийских генералов», он также предъявляет более строгие требования к временным предположениям системы. Это также легко понять: поскольку отказоустойчивость алгоритма настолько высока, предположения об операционной среде также могут быть выше. Поскольку этот вопрос является очень важным в распределенных системах, мы обсудим его здесь отдельно. В статье Лэмпорта алгоритм делает следующие предположения о системе:

  • The absence of a message can be detected.

Это предположение требует, чтобы если генерал-предатель не отправлял никаких сообщений (или, конечно, сообщения могли быть потеряны), то это событие можно было обнаружить. Очевидно, что это может зависеть только от определенного механизма тайм-аута (тайм-аута) и полагаться на часы между узлами для достижения определенной степени синхронизации, то есть смещение часов не может превышать максимальное значение. На самом деле это синхронная модель. Системное предположение Paxos на данный момент не столь сильно, оно основано на асинхронной модели и не предъявляет особых требований к системным часам. В моей предыдущей статье "Безопасна ли распределенная блокировка на основе Redis?Эта проблема также упоминается в статье. Иногда это может быть источником разногласий для распределенных алгоритмов.

В частности, согласно документу Paxos, дизайн Paxos основан на асинхронной, невизантийской модели системы, а именно:

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

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

Второй пункт выше, сообщение повреждено, является византийской ошибкой. Таким образом, Paxos не требует повреждения сообщений. Это можно считать способным удовлетворить требования в случае использования протокола TCP для передачи сообщений.

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

блокчейн

На самом деле существует очень мало систем, которым действительно необходимо достичь отказоустойчивости BFT, за исключением некоторых систем с очень высокими требованиями к отказоустойчивости, таких как система управления на самолете Boeing или система, такая как космический корабль SpaceX Dragon (см.Woohoo.мы используем сертификат coin-graduate coin.com/bit…).

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

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

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

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

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

Github.com/tere eu m / i ...

Давайте начнем обсуждать связь между технологией блокчейн и «проблемой византийских генералов».

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

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

Согласно предыдущим сообщениям, информация, которую мы используем в блоке цепи должна принадлежать подписанное сообщению. Воплощенный в: блок каждой сделки будет подписан, чтобы гарантировать, что не может быть подделана, но и гарантировать, что сообщение может быть отправлено только от первоначального автора. Ну, эта часть упомянутых выше втором случае говорит, что количество сетевых узлов блоков цепи не требует лояльности? Ясно, что не так. Так, например, в битовой валютной сети, вредоносные узлы могут не понять оператору необходимую силу, более чем на 50%. Почему это представляется несовместимым между ними? Это происходит потому, что «Византийские полководцы проблема» просто сосредоточиться на одной подзадачи, он обеспокоен тем, что один из генералов (так называемый Господь) для всех других генералов (называемых вспомогательных духов) при передаче команд. Заключительное резюме всей команды требует от всех лояльных генералов, чтобы достичь консенсуса. Если не число генералов лояльно, независимо от того, что план сражения завершен, или потерпит неудачу, потому что предатель не может выполнить этот план сражения. Это похоже на сеть Bitcoin в случае, в котором процесс выбора самой длинной цепи, что эквивалентен действующие генералы были объединены для всех команд (большинство голосов).

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

В рамках «Проблемы византийских генералов», как просмотреть доказательство работы? На самом деле это эквивалентно увеличению стоимости предательства, что значительно снижает вероятность предательства более чем наполовину. Здесь можно провести сравнение: если предположить, что в истории существует реальная византийская генеральная проблема, то можно предположить, что цена проникновения вражеских шпионов в группу византийских полководцев должна быть очень высока. Поэтому можно считать, что предателей среди генералов не так уж и много. Но в соответствии с компьютерной сетью, если нет механизма, подобного доказательству работы, то цена стать майнером-предателем очень низка. Скорее всего, предателей станет больше, чем лояльных горняков.

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

В дополнение к механизму доказательства работы (Proof of Work) существует механизм, который называется Proof of Stake. Хотя некоторые люди ставят под сомнение недостатки этого механизма (например,nothing at stake), но с точки зрения «проблемы византийских генералов» это также эквивалентно увеличению цены предательства. Это похоже на шпиона, который хочет смешаться с советом директоров, стоимость должна быть относительно высокой, потому что ему нужно сначала удержать большое количество акций.

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

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

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

Перевернет ли технология блокчейн будущее? Все, что мы можем сказать сейчас: это возможно.

(Заканчивать)

Другие избранные статьи:

Категории