Аннотация
В 1985 году теория FLP была предложена в статье, написанной Фишером, Линчем и Паттерсоном. Теория FLP доказывает, что в полностью асинхронной распределенной системе ни один полностью асинхронный протокол консенсуса не может допустить даже одного необъявленного завершения процесса.
В 2002 году Линч и Гилберт выдвинули теорию CAP в своей работе. Теория CAP доказывает, что в распределенной системе невозможно одновременно достичь всех трех свойств: согласованности, доступности и допуска разделов, в то время как любые два из этих трех свойств могут быть достигнуты.
Как типичная распределенная система, FLP и CAP также применимы к блокчейну. Основываясь на теории FLP и теории CAP, в этой статье будет проанализирована логическая взаимосвязь между согласованностью, доступностью, допустимостью разбиения и невозможным треугольником цепочки блоков, чтобы объяснить, почему невозможный треугольник цепочки блоков не может быть пробит.
- Краткое изложение теории FLP
В апреле 1985 года теория FLP, продемонстрированная Фишером, Линчем и Паттерсоном, является одной из наиболее важных теорий распределенных систем. Они также получили награду Dijkstra Paper Award, самую влиятельную в области распределенных вычислений, за работу по теории FLP.
Теория FLP доказывает, что в асинхронной системе связи ни один согласованный протокол не может полностью решить проблему согласования, несмотря на один ошибочный процесс.
В синхронной системе можно достичь консенсуса. Потому что в синхронной системе, когда происходит сбой процесса или время ожидания ответа, мы можем предположить, что он потерпел крах.
Находясь в асинхронной системе, один процесс не может определить, умер другой или просто работает очень медленно. В этом случае, если есть проблема с каким-либо из процессов, не существует распределенного алгоритма, который позволил бы всем не неисправным процессам достичь консенсуса.
Из-за ограничений невозможности FLP алгоритм согласования большинства проектов блокчейнов предполагает, что большинство узлов честны и соответствуют определенной синхронизации. POW предполагает, что 51% узлов являются честными и имеют некоторую степень синхронизации. POS и PBFT также считают, что большинство узлов (66%) честны.
- Краткое изложение теории CAP
На Симпозиуме по принципам распределенных вычислений (PODC) в 2000 году ученый Эрик Брюер предложил свою гипотезу о согласованности, доступности и допустимости разбиения распределенных вычислительных систем. В 2002 году его гипотеза была подтверждена Нэнси Линч и Сетом Гилбертом, двумя профессорами в Массачусетском технологическом институте, и получила название теории CAP.
Теория CAP доказывает, что невозможно обеспечить надежные атомарные данные согласованности, когда сеть разделена, в то время как возможно достичь любых двух из трех свойств: согласованность, доступность и допуск раздела. В асинхронной системе связи, когда блокировка не используется, невозможно обеспечить согласованность данных, даже если устаревшие данные разрешено возвращать в случае потери сообщений. В синхронной системе связи существует компромисс между согласованностью и доступностью.
- 2.1. консистенция
В теории CAP согласованность ограничена атомарными объектами данных, что аналогично большинству других методов, которые формально определяют службы согласованности. Система, которая удовлетворяет согласованности, имеет общий порядок для всех операций, так что каждая операция выглядит так, как если бы она была завершена в один момент. Это требует, чтобы все запросы от распределенной системы были синхронизированы до того, как операции могут быть выполнены. Это эквивалентно требованию, чтобы запросы распределенной общей памяти работали так, как если бы они выполнялись на одном узле, отвечая на операции по одной за раз. Это самая простая модель понимания согласованности для пользователей, и она наиболее удобна для тех, кто пытается разработать клиентское приложение, использующее распределенный сервис.
- 2,2 Доступность
Для того, чтобы распределенная система была постоянно доступна, каждый запрос, полученный исправным узлом в системе, должен приводить к ответу. То есть любой алгоритм, используемый сервисом, должен в итоге завершиться.
В аргументе теории CAP доступность определяется как два типа:
- Слабая доступность: он не ограничивает продолжительность работы алгоритма до его завершения и, следовательно, допускает неограниченные вычисления.
- Надежная доступность: даже в случае серьезных сбоев в работе сети каждый запрос должен завершаться.
В условиях слабой доступности системе разрешено не гарантировать время отклика, но ответ является обязательным. Когда в системе возникает ошибка, это не гарантирует прекращение запроса. В случае сильной доступности запрос должен прерваться, даже если произойдет системная ошибка.
- 2,3. Допуск раздела
В теории CAP под разделением понимается возможность потери произвольного количества сообщений, отправляемых с одного узла на другой в сети. При разделении сети все сообщения, отправленные с узлов в одном компоненте раздела на узлы в другом компоненте, теряются.
Допуск раздела означает тот факт, что система все еще соответствует согласованности и доступности, как определено выше, когда происходит разделение. Следовательно, требование атомарности подразумевает, что каждый ответ будет атомарным, хотя произвольные сообщения, отправленные как часть алгоритма, могут не доставляться. Требование доступности подразумевает, что каждый узел, получающий запрос от клиента, должен ответить, хотя отправленные произвольные сообщения могут быть потеряны.
- Использование теории CAP, чтобы объяснить, почему невозможный треугольник блокчейна не может быть пробит
В области цепочки блоков безопасность, масштабируемость и децентрализация известны как «невозможный треугольник» цепочки блоков, что означает, что в одной и той же системе цепочки блоков невозможно достичь всех трех свойств и одновременно удовлетворить высокие требования.
Наш основной аргумент заключается в том, что теория CAP верна в распределенной системе, и блокчейн принадлежит к распределенной системе, поэтому блокчейн должен соблюдать теорию CAP. Пока мы можем доказать логическую связь между непротиворечивостью, доступностью, допустимостью разбиения в теории CAP и невозможным треугольником блокчейна, мы можем доказать, что невозможный треугольник блокчейна не может быть разорван.
- 3.1. Последовательность и безопасность
В процессе доказательства теории CAP доказано, что в модели асинхронной сети невозможно реализовать объект данных чтения / записи, который гарантирует как доступность, так и согласованность. Мы применяем этот вывод и процесс доказательства к системе блокчейна.
В сетевой среде, определенной теорией CAP, мы предполагаем, что в системе блокчейна есть два узла A и B, и оба A и B записывают баланс криптовалюты одного адреса H как X1, теперь A и B разделены.
Когда пользователь инициирует транзакцию в разделе, где расположен узел A, баланс в адресе H изменится на X2. Когда пользователь запрашивает баланс в разделе, где расположен узел B, баланс в адресе H по-прежнему равен X1. Таким образом, мы считаем, что в этой системе блокчейнов несоответствие происходит в выступе.
Когда возникает несогласованность в системе блокчейна, мы заключаем, что такая система блокчейна небезопасна. Согласно этому определению, согласованность является основной предпосылкой безопасности системы блокчейна. Другими словами, безопасность блочных систем является более строгим требованием, чем согласованность распределенных систем. Безопасность> Согласованность.
- 3.2. Доступность и Масштабируемость
Доступность в теории CAP подразделяется на слабую и сильную, но обе требуют, чтобы система отвечала на все обычные запросы. С технической точки зрения это означает реализацию нормального чтения и записи.
В системе блокчейнов масштабируемость относится к числу транзакций, которые могут быть обработаны в секунду. Технически, высокая масштабируемость заключается в достижении высокочастотных операций чтения и записи в секунду.
Логически мы видим, что доступность является более фундаментальным требованием к сети, чем масштабируемость. Система блокчейна, которая не может обеспечить доступность, не может обеспечить масштабируемость, то есть доступность является предпосылкой масштабируемости. Другими словами, масштабируемость блочных систем является более строгим требованием, чем доступность распределенных систем. Масштабируемость> Доступность.
- 3.3. Толерантность к разделам и децентрализация
В теории CAP разделение считается обязательным для распределенных систем. Действительно, в реальной распределенной среде невозможно гарантировать, что каждый узел в системе не выйдет из строя
Как основная особенность блокчейна, децентрализация означает, что система блокчейна должна быть распределена, то есть децентрализация неизбежно приведет к разделению, что также означает, что допуск раздела является предпосылкой для реализации децентрализации.
- 3.4. Баланс существующих согласованных алгоритмов на CAP
В теории CAP разделение считается неизбежным присутствием распределенных систем, поэтому нет смысла обсуждать распределенную систему без разделения. Как типичная распределенная система, различные согласованные алгоритмы блокчейна уравновешивают согласованность и доступность системы в рамках раздела.
Tendermint: Tendermint — это согласованный алгоритм POS-типа, который в основном состоит из пяти этапов: NewHeight -> Propose -> Prevote -> Precommit -> Commit. Предложить -> Prevote -> Precommit относится к фазе консенсуса и является ядром алгоритма, который называется Раунд. Для подтверждения фиксации блока может потребоваться несколько раундов в одном блоке. В нескольких раундах высота блока не увеличивается, в систему передаются только пустые блоки, и после подтверждения блока его нельзя изменить. Так что Tendermint теоретически может застрять, в результате чего высота блока никогда не увеличивается. Это означает, что Tendermint больше сосредоточен на последовательности, когда есть перегородки.
Casper FFG: Casper FFG — это консенсусный алгоритм POS-типа. В проекте Casper FFG согласованность является приоритетом, поскольку она не позволяет заполнять контрольные точки без одобрения подавляющего большинства верификаторов, поэтому блок не переходит в состояние окончательного подтверждения.
Алгоранд: Алгоранд — это алгоритм консенсуса POS-типа. По дизайну Algorand похож на Tendermint. Когда существует конфликт между согласованностью и доступностью, система имеет тенденцию создавать пустые блоки, а не блоки реального значения. Поэтому Algorand отдает приоритет последовательности.
Dfinity: Dfinity — это согласованный алгоритм POS-типа. Когда сеть разбита на разделы, она автоматически приостанавливает случайный маяк и не позволяет продолжить работу каких-либо разделов в сети. Таким образом, Dfinity отдает приоритет согласованности.
POW: когда сеть, использующая POW, разделена, все разделы могут нормально генерировать блоки. Когда сеть восстанавливается и раздел заканчивается, в соответствии с принципом самой длинной цепочки, цепочки разных разделов будут объединены и в конечном итоге станут одной цепью. Так что военнопленный расставляет приоритеты в доступности.
POC: полное название POC — Proof of Credit, который инновационно используется в NULS, глобальном проекте с открытым исходным кодом и сообществом. Когда сеть, использующая POC, разделена, все разделы могут нормально генерировать блоки. Когда сеть будет восстановлена, подобно POW, блокчейн будет объединен по принципу самой длинной цепочки. Поэтому приоритет POC, инновационно используемого NULS, — это доступность.
- Заключение
Выводя логические взаимосвязи между согласованностью и безопасностью, доступностью и масштабируемостью, устойчивостью к разделам и децентрализацией, мы можем сделать следующий вывод:
- Последовательность необходима для безопасности
- Наличие необходимо для масштабируемости
- Толерантность к разделам необходима для децентрализации
В соответствии с теоремой теории CAP о невозможности достижения всех трех свойств: согласованности, доступности и допуска разделов, мы можем сделать следующий вывод: в условиях теории CAP безопасность, масштабируемость и децентрализация не могут быть достигнуты одновременно, то есть невозможный треугольник блокчейна не может быть пробит.
Об авторе:
Кен Хуанг
Известный специалист по блокчейну, главный научный сотрудник NUChain, американский исполнительный директор DistributedApps, член Комитета экспертов по блокчейну Китайского института электроники и технический советник NULS.
Сян Венбо
Инженер-программист Java, автор крипто-технологий и член основной команды NULS. Он специализируется на исследованиях технологии блокчейна и решениях блокчейна.
Рекомендации:
Гипотеза Брюера и осуществимость согласованных, доступных, допускающих разбиение веб-сервисов Сет Гилберт, Нэнси Линч
Невозможность распределенного консенсуса с одним ошибочным процессом. Майкл Дж. Фишер, Нэнси А. Линч, Майкл С. Патерсон
Теория CAP для распределенных систем: https://www.hollischuang.com/archives/666
Сравните окончательность и жизнеспособность различных согласованных алгоритмов: https://www.odaily.com/post/5134107
Окончательность в консенсусе блокчейна: https://medium.com/mechanism-labs/finality-in-blockchain-consensus-d1f83c120a9a
