Канон консенсуса

Переиздано Платоном

Читают: 0

Консенсусный канон PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Примечание редактора: у криптовалюты a16z была длинная серия «пистолеты” — из нашего оригинала Крипто канон нашим ДАО канон и Канон NFT к, совсем недавно, нашему Канон с нулевым разглашением. Ниже мы собрали набор ресурсов для тех, кто хочет понять, углубиться и построить с консенсус: системы соглашений, которые позволяют криптовалютам работать, определяя действительность транзакций и управление блокчейном.

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

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

Общие ресурсы

Децентрализованные мысли. Этот блог ведется Иттаем Абрахамом и Картиком Наяком, но в нем также много статей от других ведущих исследователей. Он начинается прямо с основ, но вы также можете найти простые пояснения к последним статьям.

Консенсус на 50 страницах. Заметки Эндрю Льюиса-Пая, охватывающие ключевые результаты классической литературы по консенсусу. Версия по этой ссылке находится в разработке и часто обновляется. См. также семинары по криптографии a16z, основанные на этих заметках ( Части I, Часть II).

Основы распределенного консенсуса и блокчейнов. Предварительный набросок учебника Элейн Ши.

Основы блокчейнов. Серия лекций Тима Рафгардена на YouTube.

Основы блокчейна. Конспекты лекций Дэвида Це посвящены протоколам proof-of-work и proof-of-stake.

Определение консенсуса

Наиболее изучены три проблемы консенсуса: Византийская трансляция, Византийское соглашениеи Репликация конечного автомата (проблема, которую решают протоколы блокчейна). Объяснение взаимосвязи между этими проблемами см. в «Консенсусе на 50 страницах» (перечислены выше) или в этих блогах на сайте «Децентрализованные мысли»: «Что такое консенсус?(Основной ключ) и Консенсус для репликации конечного автомата".

Проблема византийских генералов (1982) Лесли Лэмпорт, Роберт Шостак и Маршалл Пиз.
В этой статье представлена известная «проблема византийских генералов». Его все равно стоит прочитать, но лучшие версии некоторых доказательств можно найти в другом месте. Для доказательства того, что можно решить проблему для любого числа неисправных процессоров при наличии инфраструктуры открытых ключей (PKI), можно найти более простую и эффективную версию в статье Долева и Стронга (см. протоколы»). Для известного результата невозможности, заключающегося в том, что в отсутствие PKI проблема неразрешима, если менее трети процессоров не обнаруживают византийские ошибки, более понятное доказательство можно найти в статье Фишера, Линча и Мерритта (также ниже) .

Реализация отказоустойчивых сервисов с использованием подхода конечного автомата: Учебное пособие (1990) Фреда Шнайдера.
Вам также следует взглянуть на эту старую статью, в которой рассматривается проблема State-Machine-Replication (SMR) — проблема, решаемая протоколами блокчейна.

Следующие ссылки классифицируются в соответствии с рассматриваемым протоколом, начиная с Разрешенные протоколы (как это рассматривается в большей части классической литературы). Разрешенные протоколы — это протоколы, в которых все участники известны с момента начала выполнения протокола. В приведенных ниже ссылках разрешенные протоколы дополнительно классифицируются в соответствии с моделью надежности сообщений: либо синхронный, частично синхронныйили асинхронный.

Объяснение этих терминов см.: «Синхронность, асинхронность и частичная синхронность«Децентрализованные мысли». Сводку результатов, полученных в различных моделях, см. Шпаргалка по децентрализованным мыслям.

Синхронные протоколы

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

Аутентифицированные алгоритмы для византийского соглашения (1983) Дэнни Долева и Х. Рэймонда Стронга.
Здесь есть два важных доказательства. Существует доказательство того, что можно решить проблему Byzantine Broadcast для любого количества неисправных процессоров при наличии инфраструктуры открытого ключа (PKI). Другое изложение этого см.Аутентифицированная трансляция Dolev-Strong«Децентрализованные мысли». Существует также доказательство того, что е + 1 раунды необходимы для решения Byzantine Broadcast, если до f процессоры могут быть неисправны. Более простое доказательство см. Простое двухвалентное доказательство того, что t-устойчивый консенсус требует t+1 раундов Маркос Агилера и Сэм Туэг.

Простые доказательства невозможности для задач распределенного консенсуса (1986) Майкла Фишера, Нэнси Линч и Майкла Мерритта.
См. также недавние доклады, посвященные этому, от Эндрю Льюис-Пай и Тим Рафгарден.

Границы обмена информацией для Византийского соглашения (1985) Дэнни Долева и Рюдигера Райщука.
Нет который много форм доказательства невозможности в литературе консенсуса. Это важный пример, который показывает, как установить нижнюю границу количества сообщений, которые необходимо отправить для решения проблем с консенсусом.

«Протокол Фазового Короля», из статьи Битовый оптимальный распределенный консенсус (1992) Петра Бермана, Хуана Гарая и Кеннета Перри.
Если вы хотите увидеть протокол решения Византийского соглашения в синхронных условиях без PKI, это, вероятно, наиболее информативно. Для недавнего сообщения в блоге, которое ясно объясняет это, см.Phase-King через призму Gradecast: простое синхронное византийское соглашение без аутентификации«Децентрализованные мысли».

Частично синхронные протоколы

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

Консенсус при наличии частичной синхронности (1988) Синтии Дворк, Нэнси Линч и Ларри Стокмейера.
Это классическая статья, в которой вводится частично синхронная настройка и доказываются многие ключевые результаты.

Последние слухи о консенсусе BFT (2018) Итана Бухмана, Джэ Квона и Зарко Милошевича.
При правильном представлении протокол Tendermint (описанный в этой статье) достаточно прост, чтобы его можно было использовать для изучения State-Machine-Replication в частично синхронных условиях. Очень простую презентацию можно найти в Consensus на 50 страницах (см. выше), а также есть четкие презентации в выступлениях Эндрю Льюис-Пай и Тим Рафгарден.

Streamlet: упрощенные блокчейны из учебника (2020) Бенджамина Чана и Элейн Ши.
В этой статье описывается протокол блокчейна, специально разработанный для простоты обучения. Вы можете найти лекцию Элейн Ши об этом. здесь.

Каспер Дружелюбный гаджет завершения (2017) Виталика Бутерина и Вирджила Гриффита.
Это протокол, который формирует основу нынешнего подхода Ethereum к Proof-of-Stake. По сути, это «связанная» версия Tendermint. Для объяснения «цепочки» см. документ Hotstuff, указанный ниже.

HotStuff: Консенсус BFT через призму блокчейна (2018) Маофан Инь, Далия Малхи, Майкл К. Райтер, Гай Голан Гета и Иттай Абрахам.
По сути, это был протокол, который проект Facebook Libra (переименованный в Diem) изначально намеревался реализовать. Преимущество перед Tendermint в том, что протокол оптимистично отзывчивый, что означает, что подтвержденные блоки могут производиться на «скорости сети», когда лидеры честны, то есть нет необходимости тратить предварительно определенное минимальное время на создание каждого подтвержденного блока. Вы также можете посмотреть выступление Иттая Абрахама на этом здесь.

Ожидаемая линейная синхронизация раундов: недостающее звено для линейной византийской SMR (2020) Одеда Наора и Идит Кейдар.
В этом документе рассматривается проблема с Hotstuff, заключающаяся в том, что он не устанавливает никакого эффективного механизма для «синхронизации представлений». Этот Блог Далия Малхи и Одед Наор дают обзор работы над проблемой синхронизации представлений. Смотрите также эта дальнейшая оптимизация Эндрю Льюис-Пай и Иттай Абрахам.

Паксос — это просто (2001) Лесли Лэмпорт.
Если вы не хотите сразу переходить к последним протоколам блокчейна, таким как Tendermint, можно начать с Paxos (который не работает с византийскими неудачами), а затем перейти к PBFT, который является следующей ссылкой в нашем списке. (и что делает).

Практическая византийская терпимость (1999) Мигеля Кастро и Барбары Лисков.
Это классический протокол PBFT. Отличный доклад о протоколе Барбары Лисков можно найти здесь.

Асинхронные протоколы

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

Невозможность распределенного консенсуса с одним ошибочным процессом (1985) Майкла Фишера, Нэнси Линч и Майкла Патерсона.
Теорема FLP (названная в честь авторов), вероятно, является самым известным результатом невозможности в литературе по протоколам консенсуса: ни один детерминистический протокол не решает Византийское соглашение (или SMR) в асинхронных условиях, когда даже один неизвестный процессор может быть неисправен. Вы можете найти хорошую презентацию в лекции Тима Рафгардена. здесь.

«Передача Брахи», впервые появившаяся в газете Асинхронные протоколы византийского соглашения (1987) Габриэля Брачи.
Один из способов обойти теорему о невозможности FLP — ослабить требование завершения. Bracha's Broadcast — это детерминированный протокол, который работает в асинхронных условиях, решая более слабую форму Byzantine Broadcast, которая не требует завершения в случае неисправности вещателя. Хотя трансляция Брахи впервые появляется в статье выше, в ней также показано, как использовать широковещательный протокол для решения Византийского соглашения с помощью случайности. Если вы просто хотите изучить трансляцию Брахи, то понятную презентацию можно найти здесь.

FastPay: высокопроизводительный византийский отказоустойчивый расчет (2020) Матье Боде, Джорджа Данезиса и Альберто Соннино.
В этой статье описывается, как реализовать платежную систему в асинхронных условиях с использованием надежной трансляции (и без необходимости установления общего порядка).

Если вам действительно нужно решить Византийское соглашение или SMR в асинхронном режиме, то результат FLP означает, что вам придется использовать некоторую форму случайности. Помимо статьи Брахи (упомянутой выше), следующие две ссылки являются классикой литературы, описывающей, как решить Византийское соглашение с помощью случайности:

Еще одно преимущество свободного выбора: полностью асинхронные протоколы согласования (1983) Майкла Бен-Ора
Случайные оракулы в Константинополе: практическое асинхронное византийское соглашение с использованием Криптография (2005) Кристиана Качина, Клауса Курсаве и Виктора Шупа

Утвержденное асинхронное византийское соглашение с оптимальной устойчивостью и асимптотически оптимальным временем и словесным общением (2018) Иттая Абрахама, Далии Малхи и Александра Шпигельмана.
Альтернативный путь к пониманию того, как решить SMR (и Византийское соглашение) в асинхронной обстановке, — это перейти к статье выше, которая модифицирует Hotstuff. Если вы уже разбираетесь в Hotstuff, то модификация достаточно проста. Стандартный Hotstuff нельзя запускать в асинхронном режиме, потому что после выбора лидера злоумышленник может просто скрыть сообщения от этого лидера. Поскольку честные стороны не знают, является ли лидер нечестным и не отправляет сообщения, или является ли лидер честным и их сообщения задерживаются, в конечном итоге они вынуждены попытаться добиться прогресса другим путем. Чтобы решить эту проблему, нам просто нужно, чтобы все стороны одновременно выступали в роли лидеров. Как только подавляющее большинство сторон успешно завершает стандартное «представление» протокола Hotstuff, мы ретроспективно выбираем лидера случайным образом. Если они создали подтвержденный блок, мы используем его, отбрасывая остальные.

Dumbo-MVBA: пересмотр оптимального многозначного валидированного асинхронного византийского соглашения (2020) Юань Лу, Чжэньлян Лу, Цян Тан и Гуйлин Ван.
Эта статья оптимизирует предыдущую работу Абрахама, Малхи и Шпигельмана, уменьшая ожидаемую сложность коммуникации.

Медоед протоколов BFT (2016) Эндрю Миллера, Ю Ся, Кайла Кромана, Элейн Ши и Доун Сонг.

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

Протоколы DAG

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

На этом семинаре по криптографии a16z Эндрю Льюис-Пай дает обзор консенсуса на основе DAG.

В следующих четырех статьях описываются протоколы DAG, обеспечивающие эффективное упорядочение транзакций. DAG-Rider работает в асинхронном режиме и похож на Cordial Miners, но имеет более высокую задержку и меньшую ожидаемую (амортизированную) сложность связи. Narwhal — это протокол мемпула, а Tusk — это протокол SMR, работающий поверх Narwhal, который в некоторых отношениях повышает эффективность DAG-Rider. Bullshark аналогичен, но оптимизирован для использования хороших сетевых условий, когда они возникают в частично синхронных настройках.

Все, что вам нужно, это ДАГ (2021) Идит Кейдар, Лефтерис Кокорис-Когиас, Одед Наор и Александр Шпигельман.
Это документ, в котором представлен протокол DAG-Rider.

Нарвал и Туск: Мемпул на основе DAG и эффективный консенсус BFT (2022) Джорджа Данезиса, Лефтерис Кокорис-Когиас, Альберто Соннино и Александра Шпигельмана.

Bullshark: протоколы DAG BFT реализованы на практике (2022) Александра Шпигельмана, Нила Гиридхарана, Альберто Соннино и Лефтерис Кокорис-Когиас.

Cordial Miners: консенсусные протоколы заказа на основе блокчейна на все случаи жизни (2022) Идит Кейдар, Одед Наор и Эхуд Шапиро.
Забавно, что для реализации децентрализованной платежной системы блокчейн на самом деле не нужен — последнее является более простой задачей (см. эта бумага для доказательства). Прежде чем анализировать, как установить общий порядок транзакций, в приведенной выше статье Cordial Miners сначала описывается детерминированный (и очень элегантный) протокол DAG, который успешно реализует платежи в асинхронных условиях.

Протоколы без прав доступа

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

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

Bitcoin и криптовалюта технологии (2016) Арвинда Нараянана, Джозефа Бонно, Эдварда Фельтена, Эндрю Миллера и Стивена Голдфедера.
Этот учебник дает хорошее введение в биткойн для новичков в этой области. Существует также связанный бесплатный курс на Курсере.

На более техническом уровне следующие три статьи анализируют безопасность и живучесть Биткойна, используя немного разные допущения при моделировании. Бумага «Bitcoin Backbone» является самой известной. Тяжелые обозначения затрудняют чтение, но основная идея доказательства не так сложна, как кажется на первый взгляд. Доказательство Дуннин Го и Лин Рен объясняет основные идеи, оно короче и проще.

Магистральный протокол Биткойн: анализ и применение (2015) Хуана Гарая, Ангелоса Киайяса и Никоса Леонардоса.
Анализ протокола блокчейн в асинхронных сетях (2017) Рафаэля Пасса, Лиора Симана и Абхи Шелата.
Анализ безопасности и задержки Биткойна стал проще (2022) Дуннин Го и Лин Рен.

Все есть гонка, и Накамото всегда побеждает (2020) Амира Дембо, Шрирама Каннана, Эртема Нусрета Таса, Дэвида Це, Прамода Вишваната, Сюэчао Вана и Офера Зейтуни.
В этой статье авторы проводят элегантный анализ безопасности Биткойна, который работает, показывая, что самая очевидная атака, состоящая в том, чтобы построить более длинную цепочку, является наиболее эффективной. Анализ также распространяется на Уроборос, Белоснежку и Чиа (все перечисленные ниже).

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

Большинства недостаточно: майнинг биткойнов уязвим (2014) Иттая Эяля и Эмина Гюна Сирера.
Это хорошо известная статья о «эгоистичном майнинге».

Eclipse атакует одноранговую сеть Биткойн (2015) Итана Хейлмана, Элисон Кендлер, Авива Зохара и Шэрон Голдберг.

Атаки Eclipse с низким уровнем ресурсов на одноранговую сеть Ethereum (2018) Ювала Маркуса, Итана Хейлмана и Шэрон Голдберг.

FruitChains: честный блокчейн (2017) Рафаэля Пасса и Элейн Ши.
Приведенная выше статья является ответом на проблему эгоистичного майнинга. Авторы описывают протокол таким образом, что честная стратегия для майнеров является формой приблизительного равновесия.

Prism: деконструкция блокчейна для приближения к физическим ограничениям (2019) Вивека Багария, Шрирама Каннана, Дэвида Це, Джулии Фанти и Прамода Вишваната.
В Биткойне блоки играют несколько ролей в том смысле, что они используются для перечисления транзакций, а также для достижения консенсуса в порядке блоков. В приведенной выше статье авторы разбирают блокчейн Накамото на его основные функции и показывают, как создать протокол проверки работоспособности с высокой пропускной способностью и низкой задержкой.

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

Уроборос: надежно защищенный протокол блокчейна Proof-of-Stake (2017) Ангелоса Киайяса, Александра Рассела, Бернардо Давида и Романа Олийникова.
Белоснежка: надежно реконфигурируемый консенсус и приложения для доказуемой защиты Proof of Stake (2019) Фила Даяна, Рафаэля Пасса и Элейн Ши.

Algorand: масштабирование византийских соглашений для криптовалют (2017) Йоси Гилада, Ротема Хемо, Сильвио Микали, Георгиоса Влахоса и Николая Зельдовича.
В этой статье показано, как реализовать классический протокол в стиле BFT в качестве протокола Proof-of-Stake. Вот разговор об Algorand Сильвио Микали.

Объединение GHOST и Casper (2020) Виталика Бутерина, Диего Эрнандеса, Тора Кампфефнера, Кием Фама, Чжи Цяо, Дэнни Райана, Джухёк Сина, Ин Вана и Ян Х Чжана.

Три атаки на Proof-of-Stake Ethereum (2022) Каспар Шварц-Шиллинг, Иоахим Ной, Барнабе Монно, Адитья Асгаонкар, Эртем Нусрет Тас и Дэвид Це.
Нынешняя версия Ethereum нуждается в дополнительном анализе. В этой статье описаны некоторые атаки.

Блокчейн сети Chia (2019) Брэма Коэна и Кшиштофа Петржака.
В этой статье показано, как построить протокол с самой длинной цепочкой, используя доказательство пространства и времени.

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

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

Благодарности: многиеспасибо Лин Рену, Иттай Авраам, Картик Наяк, Валерия Николаенко, Александр Шпигельмани Матье Боде за полезные предложения.

Мнения, выраженные здесь, принадлежат отдельным цитируемым сотрудникам AH Capital Management, LLC («a16z») и не являются мнением a16z или ее аффилированных лиц. Определенная информация, содержащаяся здесь, была получена из сторонних источников, в том числе от портфельных компаний фондов, управляемых a16z. Хотя информация взята из источников, считающихся надежными, a16z не проводила независимую проверку такой информации и не делает никаких заявлений о неизменной точности информации или ее уместности в данной ситуации. Кроме того, этот контент может включать стороннюю рекламу; a16z не просматривал такие рекламные объявления и не поддерживает какой-либо рекламный контент, содержащийся в них.

Этот контент предоставляется только в информационных целях и не может рассматриваться как юридическая, деловая, инвестиционная или налоговая консультация. Вы должны проконсультироваться со своими советниками по этим вопросам. Ссылки на любые ценные бумаги или цифровые активы предназначены только для иллюстративных целей и не представляют собой инвестиционную рекомендацию или предложение предоставить консультационные услуги по инвестициям. Кроме того, этот контент не предназначен и не предназначен для использования какими-либо инвесторами или потенциальными инвесторами, и ни при каких обстоятельствах на него нельзя полагаться при принятии решения об инвестировании в какой-либо фонд, управляемый a16z. (Предложение инвестировать в фонд a16z будет сделано только в меморандуме о частном размещении, договоре о подписке и другой соответствующей документации любого такого фонда, и их следует читать полностью.) Любые инвестиции или портфельные компании, упомянутые, упомянутые или описанные не являются репрезентативными для всех инвестиций в транспортные средства, управляемые a16z, и нет никаких гарантий, что инвестиции будут прибыльными или что другие инвестиции, сделанные в будущем, будут иметь аналогичные характеристики или результаты. Список инвестиций, сделанных фондами, управляемыми Andreessen Horowitz (за исключением инвестиций, в отношении которых эмитент не предоставил разрешение на публичное раскрытие информации a16z, а также необъявленных инвестиций в публично торгуемые цифровые активы), доступен по адресу https://a16z.com/investments. /.

Диаграммы и графики, представленные в нем, предназначены исключительно для информационных целей, и на них не следует полагаться при принятии каких-либо инвестиционных решений. Прошлые показатели не свидетельствуют о будущих результатах. Содержание говорит только по состоянию на указанную дату. Любые прогнозы, оценки, прогнозы, цели, перспективы и/или мнения, выраженные в этих материалах, могут быть изменены без предварительного уведомления и могут отличаться или противоречить мнениям, выраженным другими. Пожалуйста, посетите https://a16z.com/disclosures для получения дополнительной важной информации.