Что такое задача византийских генералов (BFT)? Примеры

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

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

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

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

Что такое одноранговые узлы и ноды?

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

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

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

Инклюзивные и эксклюзивные блокчейны

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

Частные и публичные блокчейны

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

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

К публичным инклюзивным блокчейнам относятся Биткойн, Эфириум и им подобные.

Примеры частных эксклюзивных блокчейнов – это когда вы запустите собственную версию Hyperledger или Эфириума на своём компьютере или частный блокчейн внутри компании.

Блокчейн-консорциумы

Последний тип – блокчейн-консорциумы, когда группа участников (скорее всего, транснациональные корпорации) образуют сеть (можно представить это как своего рода «интранет») и присоединиться к ней и пользоваться ею могут только они. Примеры блокчейн-консорциумов – , Hyperledger от Linux Foundation и Quorum от JP Morgan.

Источник: crypto.com

Что такое консенсус?

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

Узнайте про все виды консенсусов в блокчейне в нашей статье!

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

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

Доказательство устойчивости криптовалютных систем

Еще одно свойство биткоина было обнаружено известным американским ученым Лесли Лэмпортом. Он доказал, что согласия в штабе N генералов можно достичь лишь в случае, если количество перебежчиков не превышает N/2 минус один генерал. Это правило, работающее при генерации биткоинов, получило название «правило 51 процента». Говоря проще, если мощности предателей превышают мощности честных генералов, то последние не смогут построить корректную систему векторов по причине недостатка правильной информации. В случае с биткоинами это позволит «перебежчикам» выборочно подтверждать чужие блоки, а значит, контролировать процесс добычи криптовалюты.

Добыча новых биткоинов происходит корректно, пока в блокчейн-сообществе преобладают добросовестные участники

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

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

• 2shares
• 0
• 0
• 2

Что такое задача византийских генералов?

Система византийских генералов (BFT), может продолжать работать правильно, пока две трети сети соглашаются или достигают консенсуса. BFT — это свойство или характеристика системы, которая может противостоять до одной трети узлов, которые выходят из строя или действуют злонамеренно.

Все децентрализованные цепочки блоков работают по согласованным протоколам или правилам, которым должны следовать все узлы в цепочке блоков, чтобы участвовать. Согласованные протоколы, такие как Proof-of-Work и Proof-of-Stake, являются BFT и, таким образом, способны противостоять одной трети несогласованных узлов.

Ссылки [ править ]

1. Киррманн, Хуберт (б). «Отказоустойчивые вычисления в промышленной автоматизации» (PDF) . Швейцария: Исследовательский центр АББ. п. 94. Архивировано из оригинального (PDF) 26 марта 2014 года . Проверено 2 марта 2015 .
2. Лэмпорт, Л .; Шостак, Р .; Пиз, М. (1982). «Проблема византийских генералов» (PDF) . Транзакции ACM по языкам и системам программирования
   .
   4
   (3): 382–401. CiteSeerX 10.1.1.64.2312 . DOI : 10.1145 / 357172.357176 . Архивировано 13 июня 2022 года (PDF) .
3. ^ a b c Дрисколл, К .; Холл, Б .; Paulitsch, M .; Zumsteg, P .; Сивенкрона, Х. (2004). «Настоящие византийские генералы». 23-я Конференция по системам цифровой авионики (IEEE Cat. No. 04CH37576)
   . С. 6.D.4–61–11. DOI : 10,1109 / DASC.2004.1390734 . ISBN 978-0-7803-8539-9. S2CID 15549497 .
4. ^ a b c Дрисколл, Кевин; Холл, Брендан; Сивенкрона, Хакан; Зумстег, Фил (2003). «Византийская отказоустойчивость, от теории к реальности». Компьютерная безопасность, надежность и безопасность
   . Конспект лекций по информатике.
   2788
   . С. 235–248. DOI : 10.1007 / 978-3-540-39878-3_19 . ISBN 978-3-540-20126-7. ISSN 0302-9743 . S2CID 12690337 .
5. Avizienis, A .; Laprie, J.-C .; Рэнделл, Брайан ; Ландвер, К. (2004). «Основные понятия и таксономия надежных и безопасных вычислений». Транзакции IEEE о надежных и безопасных вычислениях
   .
   1
   (1): 11–33. DOI : 10.1109 / TDSC.2004.2 . hdl : 1903/6459 . ISSN 1545-5971 . S2CID 215753451 .
6. «Надежные вычисления и отказоустойчивость» . Архивировано 2 апреля 2015 года . Проверено 2 марта 2015 .
7. Generalized Communication and SecurityModelsin Byzantine Agreement, Матиас Фитци https://www.crypto.ethz.ch/publications/files/Fitzi03.pdf
8. ^ а б «SIFT: проектирование и анализ отказоустойчивого компьютера для управления самолетом». Надежность микроэлектроники
   .
   19
   (3): 190. 1979. DOI : 10,1016 / 0026-2714 (79) 90211-7 . ISSN 0026-2714 .
9. Пиз, Маршалл; Шостак, Роберт; Лэмпорт, Лесли (апрель 1980 г.). «Достижение соглашения при наличии недостатков». Журнал Ассоциации вычислительной техники
   .
   27
   (2): 228–234. CiteSeerX 10.1.1.68.4044 . DOI : 10.1145 / 322186.322188 . S2CID 6429068 .
10. Лэмпорт, Лесли (2016-12-19). «Проблема византийских генералов» . Транзакции ACM по языкам и системам программирования
    . SRI International . Проверено 18 марта 2022 .
11. ^ а б в Лэмпорт, Л .; Шостак, Р .; Пиз, М. (1982). «Проблема византийских генералов» (PDF) . Транзакции ACM по языкам и системам программирования
    .
    4
    (3): 387–389. CiteSeerX 10.1.1.64.2312 . DOI : 10.1145 / 357172.357176 . Архивировано 7 февраля 2022 года из оригинального (PDF) .
12. Дрисколл, Кевин (2012-12-11). «Реальные сбои системы» . DASHlink
    . НАСА . Архивировано 2 апреля 2015 года . Проверено 2 марта 2015 .
13. Уолтер, C .; Ellis, P .; ЛаВэлли, Б. (2005). «Надежная платформа-сервис: отказоустойчивая сервисная архитектура на основе свойств». Девятый международный симпозиум IEEE по системной инженерии с высоким уровнем надежности (HASE’05)
    . С. 34–43. DOI : 10,1109 / HASE.2005.23 . ISBN 978-0-7695-2377-4. S2CID 21468069 .
14. Feldman, P .; Микали, С. (1997). «Оптимальный вероятностный протокол для синхронного византийского соглашения» (PDF) . SIAM J. Comput
    .
    26
    (4): 873–933. DOI : 10.1137 / s0097539790187084 . Архивировано (PDF) из оригинала 5 марта 2016 года . Проверено 14 июня 2012 .
15. Paulitsch, M .; Моррис, Дж .; Холл, Б .; Driscoll, K .; Latronico, E .; Купман, П. (2005). «Покрытие и использование циклических кодов избыточности в сверхнадежных системах». 2005 Международная конференция по надежным системам и сетям (DSN’05)
    . С. 346–355. DOI : 10.1109 / DSN.2005.31 . ISBN 978-0-7695-2282-1. S2CID 14096385 .
16. Хопкинс, Альберт Л .; Lala, Jaynarayan H .; Смит, Т. Бэзил (1987). «Эволюция отказоустойчивых вычислений в лаборатории Чарльза Старка Дрейпера, 1955–85». Эволюция отказоустойчивых вычислений
    . Надежные вычисления и отказоустойчивые системы.
    1
    . С. 121–140. DOI : 10.1007 / 978-3-7091-8871-2_6 . ISBN 978-3-7091-8873-6. ISSN 0932-5581 .
17. Дрисколл, Кевин; Пападопулос, Грегори; Нельсон, Скотт; Хартманн, Гэри; Рамохалли, Готэм (1984), Многомикропроцессорная система управления полетом
    (технический отчет), база ВВС Райт-Паттерсон, ОН 45433, США: AFWAL / FIGL Командование систем ВВС США, AFWAL-TR-84-3076CS1 maint: location ( ссылка )
18. Кастро, М .; Лисков, Б. (2002). «Практическая византийская отказоустойчивость и упреждающее восстановление». ACM-транзакции в компьютерных системах
    . Ассоциация вычислительной техники .
    20
    (4): 398–461. CiteSeerX 10.1.1.127.6130 . DOI : 10.1145 / 571637.571640 . S2CID 18793794 .
19. ↑
    Abd-El-Malek, M .; Ganger, G .; Хорошая песня.; Reiter, M .; Уайли, Дж. (2005). «Отказоустойчивые византийские отказоустойчивые услуги».
    Обзор операционных систем ACM SIGOPS
    . Ассоциация вычислительной техники .
    39
    (5): 59. DOI : 10,1145 / 1095809,1095817 .
20. Каулинг, Джеймс; Майерс, Дэниел; Лисков, Варвара ; Родригес, Родриго; Шрира, Люба (2006). Репликация HQ: протокол гибридного кворума для византийской отказоустойчивости . Труды 7-го симпозиума USENIX по разработке и внедрению операционных систем. С. 177–190. ISBN 1-931971-47-1.
21. Котла, Рамакришна; Альвиси, Лоренцо; Далин, Майк; Клемент, Аллен; Вонг, Эдмунд (декабрь 2009 г.). «Зызыва: умозрительная византийская отказоустойчивость». ACM-транзакции в компьютерных системах
    . Ассоциация вычислительной техники .
    27
    (4): 1–39. DOI : 10.1145 / 1658357.1658358 .
22. Геррауи, Рашид; Кнежевич, Никола; Вуколич, Марко; Кема, Вивьен (2010). Следующие 700 протоколов BFT . Труды 5-й Европейской конференции по компьютерным системам. EuroSys. Архивировано 2 октября 2011 года . Проверено 4 октября 2011 .
23. Clement, A .; Wong, E .; Alvisi, L .; Далин, М .; Маркетти, М. (22–24 апреля 2009 г.). Обеспечение устойчивости византийских отказоустойчивых систем к византийским сбоям (PDF) . Симпозиум по проектированию и внедрению сетевых систем. USENIX . Архивировано (PDF) из оригинала 25 декабря 2010 года . Проверено 17 февраля 2010 .
24. Aublin, P.-L .; Бен Мохтар, С .; Quéma, V. (8–11 июля 2013 г.). RBFT: избыточная византийская отказоустойчивость . 33-я Международная конференция IEEE по распределенным вычислительным системам. Международная конференция по распределенным вычислительным системам . Архивировано из оригинального 5 -го августа 2013 года .
25. Bahsoun, JP; Guerraoui, R .; Шокер, А. (01.05.2015). «Как сделать протоколы BFT действительно адаптивными» . Симпозиум по параллельной и распределенной обработке (IPDPS), 2015 IEEE International
    : 904–913. DOI : 10.1109 / IPDPS.2015.21 . ISBN 978-1-4799-8649-1. S2CID 16310807 .
26. ↑
    Чун, Бюнг-Гон; Маниатис, Петрос; Шенкер, Скотт; Кубятович, Джон (01.01.2007). «Подтвержденная память, предназначенная только для добавления: заставляя противников придерживаться своего слова».
    Материалы двадцать первого симпозиума ACM SIGOPS по принципам операционных систем
    . СОСП ’07. Нью-Йорк, Нью-Йорк, США: ACM: 189–204. DOI : 10.1145 / 1294261.1294280 . ISBN 9781595935915. S2CID 6685352 .
27. Веронезе, GS; Correia, M .; Бессани, АН; Легкое, LC; Вериссимо, П. (1 января 2013 г.). «Эффективная византийская отказоустойчивость». Транзакции IEEE на компьютерах
    .
    62
    (1): 16–30. CiteSeerX 10.1.1.408.9972 . DOI : 10.1109 / TC.2011.221 . ISSN 0018-9340 . S2CID 8157723 .
28. Buchman, E .; Kwon, J .; Милошевич, З. (2018). «Последние слухи о консенсусе BFT». arXiv : 1807.04938 [ cs.DC ].
29. «Биткойн — деньги P2P с открытым исходным кодом» . bitcoin.org
    . Проверено 18 августа 2022 .
30. М., Паулич; Дрисколл, К. (9 января 2015 г.). «Глава 48: SAFEbus» . В Zurawski, Ричард (ред.). Справочник по технологиям промышленной связи, второе издание
    . CRC Press. С. 48–1–48–26. ISBN 978-1-4822-0733-0.
31. Томас А. Henzinger; Кристоф М. Кирш (26 сентября 2001 г.). Встроенное программное обеспечение: Первый международный семинар, EMSOFT 2001, Тахо-Сити, Калифорния, США, 8-10 октября 2001 г. Материалы (PDF) . Springer Science & Business Media. С. 307–. ISBN 978-3-540-42673-8. Архивировано (PDF) из оригинала 22 сентября 2015 года . Проверено 5 марта 2015 .
32. Е, YC (2001). «Критически важная для безопасности авионика для основной системы управления полетом 777». 20-й DASC.20-я конференция по системам цифровой авионики (№ по каталогу 01CH37219)
    .
    1
    . С. 1C2 / 1–1C2 / 11. DOI : 10,1109 / DASC.2001.963311 . ISBN 978-0-7803-7034-0. S2CID 61489128 .
33. «ELC: извлеченные уроки SpaceX [LWN.net]» . Архивировано 5 августа 2016 года . Проверено 21 июля 2016 .
34. Наня, Т .; Гусен, HA (1989). «Византийская модель аппаратной неисправности». IEEE Transactions по автоматизированному проектированию интегральных схем и систем
    .
    8
    (11): 1226–1231. DOI : 10.1109 / 43.41508 . ISSN 0278-0070 .
35. Мартинс, Роландо; Ганди, Раджив; Нарасимхан, Прия; Pertet, Soila; Казимиро, Антониу; Крейц, Диего; Вериссимо, Пауло (2013). «Опыт внедрения неисправностей в византийском отказоустойчивом протоколе». Промежуточное ПО 2013
    . Конспект лекций по информатике.
    8275
    . С. 41–61. DOI : 10.1007 / 978-3-642-45065-5_3 . ISBN 978-3-642-45064-8. ISSN 0302-9743 .
36. Патент США 7475318 , Кевин Р. Дрисколл, «Метод испытания на чувствительный входной диапазоне византийских фильтров», выданный 2009-01-06, назначен Honeywell International Inc.
37. «Репозиторий Google Code для библиотеки репликации UpRight» . Архивировано из оригинала на 2016-04-15.
38. «Репозиторий библиотеки репликации BFT-SMaRt» .
39. «Репозиторий github для проекта Archistar» . 2019-05-28. Архивировано из оригинала на 2015-02-04.
40. «Репозиторий github для проекта Archistar» . 2019-04-28. Архивировано из оригинала на 2017-06-13.
41. «Домашняя страница Аскемоса» . Архивировано из оригинала на 2016-05-03.

Проблемы BFT

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

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

суть задачи

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

Варианты решения задачи

Предположим, что один из четырех генералов оказался предателем (N = 4 , M = 1). Следовательно, трое верных военачальников пошлют верные сведения о количестве своих легионеров, а в сообщениях предателя цифры могут быть какими угодно. Допустим, первый генерал сообщил, что в составе его легиона есть 1 тысяча воинов, у второго – 2 тысячи, у четвертого – 4 тысячи. Третий генерал (перебежчик) указал остальным случайно выбранные цифры x, y, z. Из полученных данных каждый военачальник формирует свой вектор:

• 1-й вектор — 1,2,x,4;
• 2-й вектор — 1,2,y,4;
• 3-й вектор — 1,2,3,4;
• 4-й вектор — 1,2,z,4.

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

Составление векторов при обмене информацией между участниками блокчейна

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

В итоге каждый верный генерал получает свой вектор N, в котором первый элемент равняется действительной численности войск первого легиона (в случае, если его командир не является предателем) или содержит неправдивые данные (если ее генерал работает на врага). При этом векторы всех верных генералов должны получиться идентичными.

Результат выглядит следующим образом: ( 1,2,f (x,y,z), 4 ), где f (x,y,z) – значение, встречающееся как минимум дважды среди чисел x,y,z или «неизвестное» в случае, если все 3 числа различны. Поскольку x,y,z и функция f (x,y,z) у всех верных генералов совпали, следовательно, согласие достигнуто и враг будет разбит.

Что такого особенного в этой системе?

Протокол консенсуса BFT, все еще может координировать и прийти к консенсусу, несмотря на некоторое количество разногласий между узлами.

Это жизненно важно для децентрализованных блокчейнов, таких как Ethereum или Bitcoin.

Одним из важных нововведений Сатоши Накамото, когда он / она / они создали Биткойн, было решение проблемы византийского генерала путем применения Proof-of-Work в сети Биткойн. Обладая свойством BFT, сеть Биткойн защищена до трети вредоносных узлов.

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

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

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

Примеры [ править ]

Несколько примеров византийских неудач приводятся в двух эквивалентных журнальных статьях. [3] [4] Эти и другие примеры описаны на веб-страницах NASA DASHlink. [12] Эти веб-страницы также описывают некоторые явления, которые могут вызывать византийские ошибки.

Византийские ошибки наблюдались нечасто и нерегулярно во время испытаний на выносливость недавно построенных подводных лодок класса « Вирджиния » , по крайней мере, до 2005 года (когда о проблемах сообщалось публично). [13]

Недоверие в блокчейне

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

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

Майнеры — участники блокчейна, которые занимаются созданием новых блоков и проверкой транзакций.

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

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

Соображения

• Проблема для двух византийских генералов такая же, как когда перевод денег осуществляется без надежного посредника. [ 1 ] Биткойн предложил первое практическое решение этой проблемы.
• В реальном мире линии непреднамеренно выходят из строя. Коды обнаружения ошибок могут использоваться для их обнаружения . В сценарии с устными сообщениями вышедшая из строя линия может рассматриваться как предательский узел. Если используются подписанные сообщения, то отказ линии будет неопровержимо обнаружен.
• Чтобы распознать отправителя сообщения с помощью устных сообщений, у вас должны быть фиксированные линии, а не сети связи. В подписанных сообщениях нет проблем с распознаванием отправителя.
• Отсутствие сообщений обычно определяется по таймауту (временным ограничениям).
• В реальном мире никогда не гарантируется, что случайная ошибка не может подделать подпись. Однако это имеет очень низкую вероятность при правильных методах подписи.
• Предотвращение умышленного мошенничества становится криптографической проблемой. Поэтому важно выбирать безопасные алгоритмы подписи.
• Это должно быть обнаружено, если сообщение отправлено дважды, путем проверки его подписи. Таким образом, подпись не может быть сгенерирована, если процесс уже видел ту же подпись в другое время.

Русские Блоги

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

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

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

Это знаменитая «проблема византийских генералов».

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

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

Аналогичная ситуация и в блокчейн-сетях.

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

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

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

Блокчейн — это сценарий, в котором полностью применяется «механизм консенсуса».

Что такое алгоритм консенсуса?

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

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

Зачем блокчейну алгоритм консенсуса?

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

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

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

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

Как Биткойн решает эту проблему? Он использует алгоритм консенсуса PoW (Proof of Work). Этот алгоритм может не только гарантировать, что количество предложений (запросов на учет), которые появляются в сети в течение определенного периода времени, ограничено, но также отказаться от требования строгой согласованности и перейти к требованию окончательной согласованности (то есть разрешить в одно и то же время в цепочке Есть несколько юридических блоков, и ссылка разветвляется, но в конце концов, ссылка с наибольшей рабочей нагрузкой, то есть самая длинная цепочка, будет последней юридической цепочкой)

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

Каковы алгоритмы консенсуса?

Существует множество консенсусных алгоритмов, включая PBFT (Practical Byzantine Fault Tolerance), PoW (Proof of Work), PoS (Proof of Stake) и DPoS (Delegate Proof of Stake).), Ripple и алгоритмы распределенного консенсуса (Pasox, Raft ) и т. д. У каждого алгоритма свой игровой процесс.

Вот несколько наиболее часто используемых блокчейнов:

1. PoW (Proof of Work, доказательство работы)

И Биткойн, и Эфириум реализованы на основе этого алгоритма. Проще говоря, PoW — это доказательство того, что определенный объем работы был проделан с рабочей стороны. Основной особенностью системы PoW является асимметрия вычислений.Конец работы должен выполнять определенную степень сложности, чтобы получить результат, но верификатор может легко проверить, выполнил ли конец работы соответствующую работу через результат, ха-ха , это Как говорится, работу выполнить сложно, а осмотр — легко.

В системе Биткойн раунд соревнования за вычислительную мощность начинается примерно каждые 10 минут. Каждый выполняет операции SHA256 с определенной строкой + случайным числом nonce и ожидает получить значение, которое соответствует ожиданиям системы. Если вычисленный результат не соответствует выполнено Ожидаемое, значение nonce постоянно корректируется и пересчитывается до тех пор, пока не будет достигнуто ожидаемое значение. Таким образом, трудно найти ожидаемое значение, и нет никакого ярлыка. Вы должны постоянно пробовать значение nonce, что требует огромных вычислений ., Это так называемый майнинг (здесь для удобства понимания принцип работы представлен примерно, и я представлю его в другой статье о хеш-алгоритме блокчейна).

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

Характеристики PoW:

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

Таким образом, преимущества и недостатки PoW вполне очевидны, особенно проблема потребления вычислительной мощности часто критикуется в биткойнах.Поэтому целью планирования Ethereum является переход на алгоритм PoS.

1. PoS (Proof of Stake, доказательство справедливости)

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

Согласно модели PoS, право бухгалтерского учета больше не имеет более высокой вероятности учета того, кто обладает большей вычислительной мощностью, как PoW, но тот, у кого больше токенов, с большей вероятностью получит права бухгалтерского учета. Как вы понимаете, PoW похож на больше работы, а PoS похож на богатых людей.

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

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

Следовательно, алгоритм POS также претерпел различные изменения и обновления, такие как алгоритм DPos.

1. DPoS (подтверждение доли делегата)

Алгоритм DPos называется доказательством доверенного капитала или доказательством доверенного капитала. По сравнению с PoW и PoS, он еще больше повышает эффективность блокчейна.

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

Но как определяется эта небольшая группа узлов? Фактически, за него голосуют все. В системе DPoS каждый токен является голосом, который в полной мере использует голосование акционеров для достижения консенсуса справедливым образом. Каждый выбирает N свидетелей (то есть N свидетелей). Mining pool) эти N свидетелей имеют равную мощность, и только свидетели могут создавать блоки и управлять ими. Кроме того, акционеры могут проголосовать за замену этих свидетелей в любое время.

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

Рекомендуемая литература

Использование базовых типов Redis5 в java

LinkedHashMap базовый анализ

Интерпретация плагина Mybatis на уровне исходного кода