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

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

читають: 0

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

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

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

Ми класифікуємо посилання нижче залежно від типу обговорюваного протоколу. Але спочатку перелік деяких загальних ресурсів, які дають чудовий огляд існуючих досліджень.

Загальні ресурси

Децентралізовані думки. Цей блог ведуть Іттай Абрахам і Картік Наяк, але також містить багато внесків інших провідних дослідників. Він починається прямо з основ, але ви також можете знайти прості пояснення останніх статей.

Консенсус на 50 сторінках. Нотатки Ендрю Льюїса-Пая, що висвітлюють ключові результати класичної консенсусної літератури. Версія за цим посиланням знаходиться на стадії розробки та часто оновлюється. Дивіться також семінари з криптографії a16z, засновані на цих примітках (Частина I, Частина II).

Основи розподіленого консенсусу та блокчейнів. Попередній проект підручника Елейн Ши.

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

Основи блокчейну. Конспекти лекцій Девіда Це зосереджені на протоколах proof-of-work і proof-of-stake.

Визначення консенсусу

Найбільш вивчені три проблеми консенсусу Візантійське мовлення, Візантійська угода та Реплікація кінцевого автомата (проблема, яку вирішують протоколи блокчейн). Щоб отримати пояснення зв’язку між цими проблемами, перегляньте «Консенсус на 50 сторінках» (перелічено вище) або ці блоги на Decentralized Thoughts: «Що таке консенсус?"І"Консенсус щодо реплікації кінцевого автомата».

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

Впровадження відмовостійких служб за допомогою підходу кінцевого автомата: підручник (1990) Фреда Шнайдера.
Ви також повинні поглянути на цю старішу статтю, яка розглядає проблему реплікації станкової машини (SMR) – проблему, яку вирішують протоколи блокчейну.

Наступні посилання класифікуються відповідно до типу розглянутого протоколу, починаючи з дозволено протоколи (як розглядається в більшості класичної літератури). Дозволені протоколи - це ті, в яких усі учасники відомі з моменту початку виконання протоколу. У наведених нижче посиланнях дозволені протоколи додатково класифікуються відповідно до моделі надійності повідомлень: синхронний, частково синхроннийабо асинхронний.

Пояснення цих термінів див.: "Синхронність, асинхронність і часткова синхронність” у Decentralized Thoughts. Зведення результатів, отриманих у різних моделях, див Шпаргалка «Децентралізовані думки»..

Синхронні протоколи

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

Автентифіковані алгоритми візантійської угоди (1983) Денні Долева та Х. Реймонда Стронга.
Тут є два важливих докази. Існує доказ того, що можна розв’язати Byzantine Broadcast для будь-якої кількості несправних процесорів за допомогою інфраструктури відкритого ключа (PKI). Для іншого пояснення цього див.Автентифікована трансляція Dolev-Strong” у Decentralized Thoughts. Є й тому доказ f+1 необхідні раунди для вирішення візантійської трансляції, якщо до f процесори можуть бути несправними. Простіший доказ див Простий доказ бівалентності, що t-стійкий консенсус вимагає t+1 раундів Маркос Агілера та Сем Туег.

Прості докази неможливості для задач розподіленого консенсусу (1986) Майкла Фішера, Ненсі Лінч і Майкла Мерріта.
Дивіться також останні розмови, які висвітлюють це, автор Ендрю Льюїс-Пай та Тім Роггарден.

Межі обміну інформацією для візантійської угоди (1985) Денні Долева та Рюдігера Райшука.
Немає Що багато форм доказу неможливості в консенсусній літературі. Це важливий документ, який показує, як встановити нижню межу кількості повідомлень, які потрібно надіслати для вирішення проблем консенсусу.

«Протокол Phase King» із статті Бітовий оптимальний розподілений консенсус (1992) Пьотра Бермана, Хуана Гарея та Кеннета Перрі.
Якщо ви хочете побачити протокол, який вирішує візантійську угоду в синхронному режимі без PKI, це, мабуть, найбільш інформативний. Недавню публікацію в блозі, яка чітко пояснює це, див.Phase-King через призму Gradecast: проста неавтентифікована синхронна візантійська угода” у Decentralized Thoughts.

Частково синхронні протоколи

Приблизно, ми перебуваємо в «частково синхронному» налаштуванні, коли доставка повідомлень іноді надійна, а іноді ні. Протоколи потрібні для забезпечення «безпеки» в будь-який час, але вони повинні бути «активними» лише в проміжки часу, коли доставка повідомлень є надійною. Стандартний спосіб моделювання цього полягає в тому, щоб припустити існування невідомого «Глобального часу стабілізації» (GST), після якого повідомлення завжди будуть доставлені в межах відомого часу. Щоб отримати офіційне визначення, перегляньте посилання у полі вище.

Консенсус за наявності часткової синхронності (1988) Синтії Дворк, Ненсі Лінч і Ларрі Стокмайера.
Це класичний документ, який представляє частково синхронне налаштування та підтверджує багато ключових результатів.

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

Streamlet: Підручник Streamlined Blockchains (2020) Бенджаміна Чана та Елейн Ши.
У цьому документі описується протокол блокчейну, спеціально розроблений для легкого навчання. Ви можете знайти лекцію Елейн Ши про це тут.

Каспер — гаджет Friendly Finality (2017) Віталіка Бутеріна та Вірджила Гріффіта.
Це протокол, який є основою нинішнього підходу Ethereum до підтвердження частки. По суті, це «ланцюгова» версія Tendermint. Щоб отримати пояснення щодо «ланцюжка», перегляньте документ Hotstuff, наведений нижче.

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

Очікувана лінійна кругла синхронізація: відсутня ланка для лінійного візантійського SMR (2020) Одеда Наора та Ідіт Кейдар.
У цьому документі розглядається проблема Hotstuff, яка полягає в тому, що він не створює ефективного механізму для «синхронізації перегляду». Це блозі Далія Малхі та Одед Наор дають огляд роботи над проблемою синхронізації перегляду. Дивитися також це подальша оптимізація Ендрю Льюїс-Пай та Іттай Абрахам.

Paxos Made Simple (2001) Леслі Лемпорт.
Якщо ви не хочете відразу переходити до нещодавніх протоколів блокчейну, таких як Tendermint, альтернативою є Paxos (який не стосується візантійських помилок), а потім перейдіть до PBFT, який є наступним посиланням у нашому списку. (і яка робить).

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

Асинхронні протоколи

У «асинхронному» налаштуванні повідомлення гарантовано надходять, але можуть зайняти будь-яку обмежену кількість часу. Щоб отримати офіційне визначення, перегляньте посилання у полі вище.

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

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

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 — це протокол mempool, а Tusk — протокол SMR, що працює поверх Narwhal і покращує ефективність DAG-Rider у певних аспектах. Bullshark схожий, але оптимізований для використання хороших умов мережі, коли вони виникають у частково синхронних налаштуваннях.

Все, що вам потрібно, це DAG (2021) Ідіт Кейдар, Лефтеріс Кокоріс-Когіас, Одед Наор та Александр Шпігельман.
Це документ, який представляє протокол DAG-Rider.

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

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

Сердечні майнери: узгоджені протоколи замовлення на основі блокового кола на будь-який випадок (2022) Ідіт Кейдар, Одед Наор та Ехуд Шапіро.
Цікавий факт, що блокчейн насправді не потрібен для впровадження децентралізованої платіжної системи — остання є значно простішим завданням (див. цей папір для доказу). Перш ніж проаналізувати, як встановити загальне впорядкування транзакцій, у наведеній вище статті Cordial Miners спочатку описується детермінований (і дуже елегантний) протокол DAG, який успішно реалізує платежі в асинхронних налаштуваннях.

Протоколи без дозволу

Протоколи без дозволу — це протоколи з доступом без дозволу: будь-хто може вільно приєднатися до процесу досягнення консенсусу, і набір учасників може навіть бути невідомим у будь-який момент під час виконання протоколу.

Біткін: електронна грошова система однорангової мережі (2008) Сатоші Накамото.
Ви чули про це. Тут також a блог від Kartik Nayak, який інтуїтивно аналізує потребу в різних аспектах протоколу, таких як підтвердження роботи, і те, як мережева синхронізація відіграє роль у протоколі.

Bitcoin і криптовалюта технології (2016) Арвінда Нараянана, Джозефа Бонно, Едварда Фелтена, Ендрю Міллера та Стівена Голдфедера.
Цей підручник дає гарне знайомство з біткойнами для новачків. Також є асоційований безкоштовний курс Coursera.

На більш технічному рівні в наступних трьох статтях аналізується безпека та ефективність біткойна, використовуючи дещо інші припущення моделювання. Папір «Bitcoin Backbone» є найвідомішим. Важкі позначення ускладнюють читання, але основна ідея доказу не така складна, як здається на перший погляд. Доказ Донгнін Го та Лін Рен пояснює основні ідеї та є коротшим і простішим.

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

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

Потім у трьох наступних статтях описуються різні форми атаки на біткойн і старий доказ роботи Ethereum.

Більшості недостатньо: майнінг біткойнів вразливий (2014) Іттай Еял та Емін Гюн Сірер.
Це добре відомий папір «самолюбного майнінгу».

Атаки Eclipse на однорангову мережу Bitcoin (2015) Ітана Гейлмана, Елісон Кендлер, Авіва Зохара та Шерон Голдберг.

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

FruitChains: чесний блокчейн (2017) Рафаеля Пасса та Елейн Ши.
Наведена вище стаття є відповіддю на проблему егоїстичного майнінгу. Автори описують такий протокол, що чесна стратегія для майнерів є формою приблизної рівноваги.

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

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

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

Algorand: Масштабування візантійських угод для криптовалют (2017) Йосі Гілада, Ротема Хемо, Сільвіо Мікалі, Георгіоса Влахоса та Ніколая Зельдовича.
У цій статті показано, як реалізувати класичний протокол у стилі BFT як протокол підтвердження частки. Ось розмова про Альгоранд Сільвіо Мікалі.

Поєднання GHOST і Casper (2020) Віталіка Бутеріна, Дієго Ернандеса, Тора Камфефнера, Кіема Фама, Чжі Цяо, Денні Раяна, Джухьок Сіна, Їн Ван та Янь І Чжана.

Три атаки на Ethereum Proof-of-Stake (2022) Каспар Шварц-Шиллінг, Йоахім Ной, Барнабе Монно, Адітя Асгаонкар, Ертем Нусрет Тас і Девід Це.
Нинішня версія Ethereum потребує додаткового аналізу. У цьому документі описані деякі атаки.

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

Візантійські генерали в бездозвільній обстановці (2021) Ендрю Льюїс-Пай і Тім Рафгарден.
У цьому документі автори розробляють структуру для аналізу протоколів без дозволу, яка дозволяє робити такі речі, як доведення результатів неможливості для протоколів без дозволу та чітко окреслювати загальні можливості протоколів proof-of-work і proof-of-stake. .

***

Ендрю Льюїс-Пай є професором Лондонської школи економіки. Він працював у різних сферах, включаючи математичну логіку, мережеву науку, популяційну генетику та блокчейн. Протягом останніх чотирьох років його наукові дослідження були зосереджені на блокчейні, де його головні інтереси зосереджені на консенсусних протоколах і токеноміці. Ви можете знайти його в Twitter @AndrewLewisPye .

Подяки: багато тдякую Лін Рен, Іттай Авраам, Картік Наяк, Валерія Ніколаєнко, Олександр Шпігельман та Матьє Боде за корисні пропозиції.

***

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

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

Наведені в ньому діаграми та графіки призначені виключно для інформаційних цілей, і на них не слід покладатися під час прийняття інвестиційних рішень. Минулі результати не вказують на майбутні результати. Зміст відповідає лише вказаній даті. Будь-які прогнози, оцінки, прогнози, цілі, перспективи та/або думки, висловлені в цих матеріалах, можуть бути змінені без попередження та можуть відрізнятися або суперечити думкам, висловленим іншими. Додаткову важливу інформацію можна знайти на сторінці https://a16z.com/disclosures.