Протокол консенсусу Stellar вперше описаний у Девіда Мазьєра у 2015 році. Це «федеративна система візантійської угоди», яка дозволяє децентралізованим обчислювальним мережам без лідерів ефективно досягати консенсусу щодо будь-якого рішення. Платіжна мережа Stellar використовує Stellar Consensus Protocol (SCP) для ведення узгодженої історії транзакцій, яку бачать усі учасники.
Вважається, що протоколи консенсусу складні для розуміння. SCP простіше більшості з них, але все ж таки поділяє цю репутацію — частково через помилкову ідею про те, що «федеративне голосування», якому присвячена перша половина наукової статті, є SCP. Але це не так! Це лише важливий будівельний блок, який у другій половині статті використовується для створення фактичного протоколу консенсусу Stellar.
У цій статті коротко розповімо, що таке «система угод», що може зробити її «візантійською» та навіщо робити візантійську систему «федеративною». Потім пояснимо федеративну процедуру голосування, описану у статті SCP, і, нарешті, пояснимо сам протокол SCP.
Системи угод
Система угод дозволяє групі учасників дійти консенсусу на якусь тему, наприклад, що замовити на обід.
Ми в компанії Interstellar впровадили власну систему обідньої угоди: замовляємо те, що говорить наш операційний менеджер Джон. Це проста та ефективна система угод. Ми всі довіряємо Джону і віримо, що він щодня знайде щось цікаве та поживне.
Але що, якщо Джон зловживає нашою довірою? Він може одноосібно вирішити, що ми всі маємо стати веганами. Через тиждень чи два, ймовірно, ми скинемо його і передамо повноваження Елізабет. Але раптом вона любить авокадо з анчоусами і думає, що всі мають стати такими. Влада розбещує. Тому краще знайти якийсь демократичніший метод: якийсь спосіб переконатися, що враховано різні переваги, при цьому забезпечено своєчасний і однозначний результат, щоб не вийшло так, що ніхто не замовить обід чи п'ятеро людей розмістять різні замовлення, чи обговорення затягнеться до вечора.
Здавалося б, рішення просте: провести голосування! Але це оманливе враження. Хто збиратиме бюлетені та повідомлятиме про результати? І чому решта має вірити тому, що він скаже? Можливо, ми можемо спочатку проголосувати за лідера, якому довіряємо керувати голосуванням — але хто керуватиме цим першим голосуванням? Що, якщо ми не зможемо домовитися про лідера? Чи якщо домовимось, а цей лідер застрягне на зустрічі чи піде на лікарняний?
Схожі проблеми зустрічаються у розподілених комп'ютерних мережах. Усі учасники або вузли повинні узгодити якесь рішення, наприклад, чия черга оновлювати спільний файл чи забирати завдання із черги обробки. У криптовалютній мережі вузлам неодноразово доводиться вибирати, як виглядає повна історія, із кількох можливих версій, які іноді конфліктують. Ця мережна угода дає гарантію одержувачу, що монета є (а) дійсною (не підробленою) та (б) ще не витраченою в іншому місці. Це також гарантує, що він зможе витратити монети в майбутньому, тому що новий одержувач матиме ті ж гарантії з тих же причин.
Будь-яка система узгодження в розподіленій обчислювальній мережі повинна бути стійкою до відмови: вона повинна давати послідовні результати, незважаючи на помилки, такі як повільні лінії зв'язку, що не реагують вузли і неправильний порядок повідомлень. Візантійська система угод додатково стійка до «візантійських» помилок: вузлів, які дають неправдиву інформацію, чи то через помилку, чи в навмисній спробі підірвати систему або отримати певну перевагу. «Візантійська» відмовостійкість — здатність довіряти груповому рішенню, навіть коли деякі члени групи можуть брехати або іншим чином не дотримуватись правил прийняття рішень — отримала назву за , які намагалися скоординувати атаку у Ентоні Стівенса.
Розглянемо власника криптомонети Алісу, яка має обрати між покупкою смачного морозива у Боба та оплатою боргу Керол. Можливо, Аліса хоче заплатити обом відразу, шахрайсько витративши одну й ту саму монету. Для цього вона повинна переконати комп'ютер Боба, що монету ніколи не було виплачено Керол, і переконати комп'ютер Керол, що монету ніколи не було виплачено Бобу. Візантійська система угод робить це фактично неможливим, використовуючи форму більшості, яка називається кворумом. Вузол у такій мережі відмовляється від переходу до певної версії історії, доки не побачить, що достатня кількість однорангових вузлів — кворум — погоджується на такий перехід. Як тільки це відбудеться, вони сформують досить великий виборчий блок, щоб змусити вузли мережі, що залишилися, погодитися з їх рішенням. Аліса може змусити деякі вузли брехати від її імені, але якщо мережа досить велика, її спроба буде придушена голосами чесних вузлів.
Скільки вузлів потрібно для кворуму? Як мінімум, більшість, а точніше, кваліфікована більшість для боротьби з помилками та шахрайством. Але, щоб підрахувати більшість, потрібно знати загальну кількість учасників. В офісі Interstellar або на окружних виборах ці цифри легко впізнати. Але якщо ваша група – це слабко визначена мережа, до якої вузли можуть входити та виходити за бажанням без узгодження з центром, тоді потрібна федеративна система візантійської угоди, здатна визначати кворуми не із заздалегідь визначеного списку вузлів, а динамічно, з постійно змінного і неминуче неповного знімку вузлів у певний момент часу.
Може здатися неможливим створити кворум з точки зору одного вузла у великій мережі, але це можливо. Такий кворум може навіть гарантувати результати децентралізованого голосування. Технічний документ SCP показує, як це зробити за допомогою процедури, яка називається федеративним голосуванням.
для нетерплячих
Решта статті більш детально описує федеративне голосування та протокол консенсусу Stellar. Якщо вам не цікаві подробиці, ось загальний огляд процесу.
- Вузли проводять раунди федерального голосування з «номінантів». Раунд федеративного голосування означає:
- Вузол голосує за будь-яке твердження, наприклад, «Я пропоную значення V»;
- Вузол слухає голоси бенкетів, доки знайде той, що може «прийняти»;
- Вузол шукає "кворум" для цього твердження. Кворум "підтверджує" номінанта.
- Як тільки вузол може підтвердити одного чи кількох номінантів, він намагається підготувати бюлетень через кілька раундів федеративного голосування.
- Як тільки вузол здатний перевірити готовність бюлетеня, він намагається закоммітити його ще більшою кількістю раундів федеративного голосування.
- Як тільки вузол може підтвердити коміт бюлетеня, він може «екстерналізувати» цінність цього бюлетеня, використовуючи його як результат консенсусу.
Ці кроки включають кілька раундів федеративного голосування, які разом утворюють один раунд SCP. Розберемося докладніше, що відбувається на кожному кроці.
Федеративне голосування
Федеративне голосування — це процедура визначення того, чи мережа може погодити пропозицію. У раунді голосування кожен вузол має обрати одне з потенційно багатьох можливих значень. Він не може цього зробити, доки не буде впевнений, що інші вузли в мережі не виберуть іншого результату. Щоб бути впевненими в цьому, вузли обмінюються шквалом повідомлень туди і назад, щоб кожен підтвердив, що кворум вузлів приймає одне і теж рішення. Решта цього розділу пояснює терміни у цій пропозиції і як відбувається вся процедура.
Кворуми та зрізи кворуму
Почнемо з визначення кворуму. Як ми обговорювали вище, у децентралізованій мережі з динамічним членством неможливо заздалегідь знати кількість вузлів і, отже, скільки потрібно більшості. Федеративне голосування вирішує цю проблему, представляючи нову ідею зрізу кворуму (quorum slice): невеликий набір однорангових вузлів, яким вузол довіряє передачу інформації про стан голосування у решті мережі. Кожен вузол визначає власний зріз кворуму (членом якого стає фактом).
Формування кворуму починається зі зрізу кворуму. До кожного вузла додаються вузли його зрізу. Потім додаються члени зрізів цих вузлів і так далі. У міру продовження трапляється все більше вузлів, які ви не можете додати, тому що вони вже включені у зріз. Коли немає нових вузлів для додавання, процес припиняється: ми сформували кворум шляхом «транзитивного закриття» (transitive closure) зрізу кворуму початкового вузла.
Щоб знайти кворум з цього вузла.
… додаємо членів його зрізу…
… потім додаємо членів зрізів цих вузлів.
Продовжуємо, доки не залишиться вузлів для додавання.
Вузолів для додавання не залишилося. Це кворум.
Насправді кожен вузол може входити більш ніж в один зріз. Щоб сформувати кворум, виберіть лише один із зрізів і додайте членів; потім виберіть будь-який зріз для кожного з членів та додайте членів цього зрізу і таке інше. Це означає, що кожен вузол є членом багатьох можливих кворумів.
Виберіть один зріз кворуму на кожному кроці.
Один можливий кворум. Або альтернативний варіант...
… вибираємо інші зрізи…
…(коли це можливо)…
… створює інший кворум.
Як вузол дізнається, у яких зрізах складаються інші вузли? Так само, як і іншу інформацію про інші вузли: з передач, які кожен вузол транслює до мережі, коли змінюється його стан голосування. Кожна трансляція включає відомості про зрізи відправляючого вузла. У технічному документі SCP не вказано механізму комунікації. Реалізації зазвичай використовують для гарантованої трансляції повідомлень по всій мережі.
Нагадаємо, що у нефедеративній візантійській системі угод кворум визначається як більшість усіх вузлів. Візантійська система угод розроблена з погляду питання: скільки нечесних вузлів здатна винести систему? У системі з N вузлів, спроектованої на виживання при f відмовах (обманах), вузол повинен бути в змозі досягти прогресу, отримавши відгук від Nf бенкетів, оскільки f з них, можливо, не функціонують. Але отримавши відгук від N-пірів, можна припустити, що всі f-бенкетів (від яких вузол не отримав відгук) насправді чесні. Таким чином, шкідливими є f з N-f бенкетів (від яких отримано відповідь). Щоб вузли прийшли до одного консенсусу, чесним має бути більшість інших вузлів, тобто нам потрібно, щоб N-f було більше 2f або N > 3f. Отже, система, розрахована на виживання при f збоїв, матиме в загальній складності N=3f+1 вузлів і розмір кворуму 2f+1. Щойно пропозиція переходить поріг кворуму, інші члени мережі переконані, що будь-які пропозиції, що конкурують, зазнають невдачі. Так мережа сходить до результату.
Але у федеративній візантійській системі угод не тільки не може бути більшості (бо ніхто не знає загального розміру мережі), але концепція більшості взагалі марна! Якщо членство в системі відкрите, то хтось може отримати більшість, просто провівши так звану атаку Сівіли: багаторазово приєднавшись до мережі через кілька вузлів. Так чому ж транзитивне закриття зрізу можна назвати кворумомі як він здатний придушувати конкуруючі пропозиції?
Технічно, ніяк! Уявіть мережу із шести вузлів, де дві трійки ізольовані у зрізах кворуму один одного. Перша підгрупа може ухвалити рішення, про яке друга ніколи не почує, і навпаки. Для цієї мережі немає способу досягти консенсусу (крім випадково).
Тому SCP вимагає, щоб для федеративного голосування (і для застосування важливих теорем статті) мережа повинна мати властивість, звану перетином кворумів. У мережі з цією властивістю будь-які два кворуми, які можна побудувати, завжди перекриваються принаймні в одному вузлі. Для визначення переважаючих настроїв мережі це так само добре, як мати більшість. Інтуїтивно це означає, що якщо будь-який кворум погоджується із твердженням X, ніякий інший кворум ніколи не зможе погодитися з чимось іншим, тому що він обов'язково включатиме певний вузол з першого кворуму, який уже проголосував за X.
Якщо в мережі є перетин кворумів.
… тоді будь-які два кворуми, які ви можете побудувати…
… завжди перетинатимуться.
(Звичайно, вузли, що перекриваються, можуть виявитися візантійсько-брехливими або поганими в інших відносинах. У цьому випадку перетин кворумів не допомагає мережі погодитися взагалі. З цієї причини багато результатів в технічному документі SCP ґрунтуються на явно виражених припущеннях, таких як те, що в мережі залишилося перетин кворумів навіть після видалення поганих вузлів. Для простоти залишимо ці припущення неявними у решті статті).
Може здатися нерозумним очікувати, що в мережі з незалежних вузлів можливе надійне перетинання кворумів. Але є дві причини, чому це так.
Перша причина полягає у існуванні самого інтернету. Інтернет – ідеальний приклад мережі незалежних вузлів із перетином кворумів. Більшість вузлів в Інтернеті з'єднуються лише з декількома іншими локальними вузлами, але ці невеликі множини перекриваються достатньо, щоб кожен вузол був доступний з кожного іншого вузла тим чи іншим маршрутом.
Друга причина специфічна для платіжної мережі Stellar (найпоширеніше застосування SCP). Кожен актив у мережі Stellar має емітент, а рекомендації Stellar вимагають, щоб кожен емітент призначив один або кілька вузлів у мережі для обробки запитів на погашення. У ваших інтересах прямо або опосередковано включати ці вузли в зрізи кворуму для кожного активу, що вас цікавить. Потім кворуми для всіх вузлів, зацікавлених у цьому активі, будуть перекриватися принаймні у цих вузлах погашення. Вузли, зацікавлені в кількох активах, включатимуть у свої зрізи кворуму всі вузли погашення відповідних емітентів, і вони прагнутимуть об'єднати всі активи разом. Крім того, будь-які активи, які не пов'язані таким чином з іншими в мережі, та не повинні бути пов'язані — так задумано, щоб для цієї мережі не було перетину кворумів (наприклад, банки із зони долара іноді хочуть торгувати із банками із зони євро та банками із зони песо, тому вони знаходяться в одній мережі, але нікому з них немає справи до окремої мережі дітей , які торгують бейсбольними картами).
Звичайно, очікування перетину кворумів не є гарантією. Інші візантійські системи угод своєю складністю багато в чому завдячують гарантією кворумів. Важливим нововведенням SCP є те, що він знімає відповідальність за створення кворумів із самого алгоритму консенсусу та виносить його на рівень програми. Таким чином, хоча федеративне голосування є досить загальним для голосування з будь-яких питань, насправді його надійність критично залежить від ширшого змісту цих значень. Деякі гіпотетичні види використання можуть виявитися не настільки зручними для створення добре зв'язаних мереж, як інші.
Голосування, прийняття та підтвердження
У раунді федеративного голосування вузол опціонально починає голосувати за якесь значення V. Це означає трансляцію в мережу повідомлення: "Я вузол N, мої зрізи кворумів Q, і я голосую за V". Коли вузол голосує таким чином, він обіцяє, що ніколи не голосував проти V і ніколи не буде.
У трансляціях від однорангових вузлів кожен вузол бачить як голосують інші. Як тільки вузол збере достатню кількість таких повідомлень, може відстежити зрізи кворумів і спробувати знайти кворуми. Якщо він бачить кворум бенкетів, які також голосують за V, то може перейти до прийняттю V і транслювати це нове повідомлення в мережу: "Я вузол N, мої зрізи кворуму Q, і я приймаю V". Прийняття забезпечує сильнішу гарантію, ніж просте голосування. Коли вузол голосує за V він ніколи не може голосувати за інші варіанти. Але якщо вузол приймає V, жоден вузол у Мережі ніколи не прийме інший варіант (теорема 8 у технічному документі SCP доводить це).
Звичайно, висока ймовірність, що одразу не знайдеться кворум вузлів, які погодяться з V. Інші вузли можуть голосувати за інші значення. Але для вузла є ще один спосіб перейти від простого голосування до ухвалення. N може прийняти інше значення W, навіть якщо не голосував за нього, і навіть якщо не бачить для нього кворуму. Для вирішення змінити свій голос достатньо побачити блокуюча безліч вузлів, що прийняли W. Блокуюча множина - це по одному вузлу кожного зі зрізів кворумів N. Як випливає з назви, воно здатне блокувати будь-яке інше значення. Якщо всі вузли в такій множині приймають W, то (за теоремою 8) ніколи не вдасться сформувати кворум, який приймає інше значення, і тому N також безпечно прийняти W.
Вузол N із трьома зрізами кворумів.
BDF - блокуюча множина для N: воно включає по одному вузлу кожного з зрізів N.
BE також є блокуючим безліччю для N, тому що E з'являється у двох зрізах N.
Але безліч блокуючих — це не кворум. Було б дуже легко обдурити вузол N, щоб він прийняв потрібне значення, якщо достатньо зламати лише один вузол у кожному з зрізів N. Тому прийняття значення — це ще не кінець голосування. Натомість N повинен підтвердити значення, тобто побачити кворум вузлів, що приймають його. Якщо він зайде так далеко, то, як доводить технічний документ SCP (в теоремі 11), решта мережі також зрештою підтвердить те саме значення, тому N завершить федеративне голосування з певним значенням як результат.
Федеративне голосування.
Процес голосування, прийняття та підтвердження складає один повний раунд федеративного голосування. Протокол консенсусу Stellar поєднує багато таких раундів для створення повної консенсусної системи.
Протокол консенсусу Stellar
Дві найважливіші властивості консенсусної системи безпеку и живучість. Консенсусний алгоритм безпечний, якщо ніколи не може дати різні результати різним учасникам (копія історії Боба ніколи не суперечитиме Керол). «Живість» означає, що алгоритм завжди видасть результат, тобто не застрягне.
Описана процедура федеративного голосування безпечний у тому сенсі, що якщо вузол підтверджує значення V, жоден інший вузол не підтвердить інше значення. Але "не підтвердить інше значення" - це не означає, що він обов'язково щось підтвердить. Учасники можуть голосувати за таку велику кількість різних значень, що ніщо не досягне порога прийняття. Це означає, що у федеративному голосуванні відсутня живучість.
Протокол консенсусу Stellar використовує федеративне голосування таким чином, щоб гарантувати безпеку і живучість. (Гарантії безпеки та живучості SCP мають теоретичний ліміт. Конструкція вибирає дуже сильну гарантію безпеки, жертвуючи невеликим ослабленням живучості, але з огляду на достатній термін консенсус з високою ймовірністю буде досягнутий). У двох словах, ідея полягає в тому, щоб провести кілька федеративних голосувань за декількома значеннями, поки одне з них не пройде повністю через всі фази голосування SCP, описані нижче.
Значення, за якими SCP прагне консенсусу, можуть бути історією транзакцій або замовленням на обід, або ще чимось, але важливо відзначити, що це не ті значення, які приймаються або підтверджуються. Натомість федеративне голосування відбувається за заяв про ці значення.
Перші раунди федеративного голосування відбуваються на етапі висування (nomination phase), на наборі заяв типу "Я висуваю V", можливо, для багатьох різних значень V. Мета висування - знайти одну або кілька заяв, які пройти через прийняття та підтвердження.
Після знаходження кандидатів, що підтверджуються, SCP переходить до етапу голосування, де мета полягає в тому, щоб знайти якийсь бюлетень (тобто контейнер для запропонованого значення) та кворум, який може оголосити коміт йому (commit). Якщо кворум робить коміт бюлетеня, його значення приймається як консенсус. Але перш ніж вузол зможе проголосувати за коміт бюлетеня, він має спочатку підтвердити скасування всіх бюлетенів із меншим значенням лічильника. Ці кроки — скасування бюлетенів, щоб знайти той, для якого можна підтвердити коміт, — включають кілька раундів федеративного голосування за декількома заявами про бюлетені.
У наступних розділах докладніше описуються висування та голосування.
Висунення
На початку етапу висування кожен вузол може спонтанно вибрати значення V та проголосувати за твердження «Я висуваю V». Мета цьому етапі — підтвердити висування деякого значення шляхом федеративного голосування.
Можливо, достатня кількість вузлів голосує за досить різні твердження, і жодне висування не може досягти порогу ухвалення. Тому, крім трансляції власних номінаційних голосів, вузли «відбивають» номінації своїх бенкетів. Відображення (echo) означає, що якщо вузол голосує за висування V, але бачить повідомлення від сусіда, що голосує за висування W, то тепер голосуватиме за висування і V, і W. (Не всі голоси бенкетів отримують відображення під час висування, тому що це може призвести до вибуху різних номінантів.SCP включає механізм регулювання цих голосів.Чим довше йде висування, тим нижчий поріг, тому вузол розширює набір бенкетів, чиї голоси він відображатиме.Формула пріоритету в якості одного з вхідних даних включає номер слота, тому високопріоритетний одноранговий вузол для одного слота може бути низькопріоритетним для іншого, і навпаки).
Концептуально висування паралельно і V, і W - це окремі федеративні голоси, кожен окремо здатний досягти прийняття чи підтвердження. На практиці повідомлення протоколу SCP пакують ці окремі голоси разом.
Хоча голосування за висування V — це обіцянка ніколи не голосувати проти висування V, на рівні додатку — у разі SCP — визначається, що означає «проти». SCP не бачить твердження, яке суперечить голосуванню "Я висуваю X", тобто немає повідомлення "Я проти висунення X", тому вузол може голосувати за висування будь-яких значень. Багато хто з цих номінацій ні до чого не приведе, але зрештою вузол зможе прийняти або підтвердити одне або кілька значень. Як тільки номінант підтверджено, він стає кандидатом.
Висунення SCP із використанням федеративного голосування. Можливо багато значень “B”, висунутих одноранговыми вузлами і «відбитих» вузлом.
Висунення кандидатів може призвести до появи кількох кандидатів, що підтверджуються. Тому SCP вимагає, щоб прикладний рівень надав якийсь метод об'єднання кандидатів в один композит (Composite). Метод об'єднання може бути будь-яким. Головне, що якщо цей метод детермінований, то кожен вузол об'єднає тих самих кандидатів. У системі голосування за обід «об'єднання» може означати просто відмову від одного із двох кандидатів. (Але детермінованим чином: кожен вузол повинен вибрати те саме значення для скидання. Наприклад, більш ранній вибір в алфавітному порядку). У платіжній мережі Stellar, де відбувається голосування за історію транзакцій, об'єднання двох запропонованих номінантів передбачає об'єднання транзакцій, які вони містять, та останніх з їхніх двох тимчасових міток.
Технічний опис SCP доводить (теорема 12), що до закінчення фази висування мережа зрештою сходить до одного композиту. Але є проблема: федеративне голосування – це асинхронний протокол (як і SCP). Іншими словами, вузли не координуються за часом, а лише за повідомленнями, які надсилають. З погляду вузла неясно, коли завершилася фаза висування. І хоча всі вузли зрештою прийдуть до того самого композиту, вони можуть вибрати різні маршрути на цьому шляху, створюючи дорогою різних складових кандидатів, і ніколи не можуть сказати, який з них остаточний.
Але це нормально. Висунення – лише підготовка. Головне обмежити кількість кандидатів для досягнення консенсусу, який відбувається у процесі балотування (balloting).
Балотування
Бюлетень - це пара де counter — ціле число, яке починається з 1, а value — кандидат з етапу висування. Це може бути власний кандидат вузла або кандидат сусіднього вузла, прийнятий цим вузлом. Грубо кажучи, при балотуванні робляться неодноразові спроби змусити мережу досягти консенсусу щодо якогось кандидата в якомусь бюлетені шляхом проведення потенційно багатьох федеративних голосувань за заявами про бюлетені. Лічильники в бюлетенях відстежують зроблені спроби, і бюлетені з вищими лічильниками мають пріоритет над бюлетенями з нижчими лічильниками. Якщо бюлетень застряє, починається нове голосування, тепер на бюлетені .
важливо розрізняти значення (наприклад, яким має бути замовлення на обід: піца або салати), бюлетені (пара counter-value) та заяви про бюлетені. Раунд SCP включає кілька раундів федеративного голосування, зокрема, за такими заявами:
- «Я готовий до коміту бюлетеня B» та
- "Я оголошую коміт бюлетеня B"
З точки зору даного вузла консенсус досягається, коли він знаходить бюлетень B, для якого може підтвердити заяву «Я оголошую коміт бюлетеня B» (тобто знайти кворум, який приймає). З цього моменту можна безпечно діяти за значенням, зазначеним у В, наприклад, розмістити це замовлення на обід. Це називається екстерналізацією значення. Як тільки підтверджено прийняття бюлетеня, вузол може бути впевнений, що будь-який інший вузол здійснив екстерналізацію цього значення або обов'язково здійснить її майбутньому.
Хоча концептуально багато федеративних голосувань проводяться за заявами про різні бюлетені, вони обмінюються не такою великою кількістю повідомлень, тому що кожне повідомлення інкапсулює ряд бюлетенів. Одне повідомлення, таким чином, просуває стан одразу багатьох федеративних голосувань, наприклад: «Я приймаю коміт бюлетенів у діапазоні від до ».
Що означає терміни «підготовлений» (prepared) та «комміт» (commit)?
Вузол голосує за бюлетеня, коли він переконаний, що інші вузли не зроблять бюлетенів з іншими значеннями. Переконання у цьому є метою підготовки заяви. Голосування, в якому йдеться: «Я готовий до комміту бюлетеня B», — це обіцянка ніколи не здійснювати коміт бюлетеня менше, ніж B, тобто з меншим лічильником (SCP вимагає, щоб значення в бюлетенях мали певний порядок. Таким чином, бюлетень менше якщо N1
Чому «Я готовий до коміту бюлетеня» означає «Обіцяю ніколи не допускати коміт бюлетенів менше»? Тому що SCP визначає abort як протилежність commit. Голосування з підготовки бюлетеня передбачає також голосування щодо скасування деяких інших бюлетенів, і, як ми вже обговорювали раніше, голосування за щось одне — ця обіцянка ніколи не голосувати проти нього.
Перш ніж транслювати коміт, вузол повинен спочатку знайти бюлетень, який може підтвердити як підготовлений. Іншими словами, він проводить федеративне голосування на тему «Я готовий до коміту бюлетеня B», можливо, для багатьох різних бюлетенів, допоки не знайде той, який приймає кворум.
Звідки беруться бюлетені на підготовку голосування? Спочатку вузол транслює підготовку до голосування за <1, C>, де C - кандидат-композит, проведений на етапі висування. Проте, навіть після початку підготовки до голосування висування може призвести до появи додаткових кандидатів, які стануть новими бюлетенями. Тим часом, у бенкетів можуть бути різні кандидати, і вони можуть сформувати блокуючу множину, яку приймає «Я готовий до коміту бюлетеня B2», що переконає вузол також його прийняти. Нарешті, є механізм таймууту, який генерує нові раунди федеративного голосування на нових бюлетенях із вищими лічильниками, якщо поточні бюлетені застрягли.
Як тільки вузол знаходить бюлетень В, який може підтвердити як підготовлений, транслює нове повідомлення «Комміт бюлетеня В». Це голосування говорить бенкетам, що вузол ніколи не відмовиться від В. Насправді, якщо У є бюлетень , то «Коміт бюлетеня » означає беззастережну згоду голосувати за готовність кожного бюлетеня від до <∞, з>. Це додаткове значення допомагає іншим вузлам наздогнати бенкету з коммітом, якщо вони ще знаходяться на ранніх етапах протоколу.
На цьому етапі варто ще раз наголосити, що це асинхронні протоколи. Тільки тому, що один вузол відправляє голоси за комміт, це не означає, що його однолітки теж роблять це. Деякі з них можуть голосувати за заявами для підготовки до голосування, інші, можливо, вже екстерналізували значення. SCP пояснює, як вузол повинен обробляти кожен тип однорангового повідомлення незалежно від його фази.
Якщо повідомлення «Я оголошують коміт » не може бути прийнято або підтверджено, тобто ймовірність прийняття або підтвердження повідомлення або — або, принаймні, будь-якого бюлетеня зі значенням С, а не будь-яким іншим, оскільки вузол уже обіцяв ніколи не скасовувати . На той час, коли вузол транслює голоси для комміту, це буде C чи нічого, залежно від того, наскільки далеко зайде консенсус. Однак цього поки що недостатньо вузла для екстерналізації C. Деякі візантійські бенкети (складають менше кворуму, ґрунтуючись на наших припущеннях про безпеку) можуть брехати вузлу. Прийняття, а потім підтвердження деякого бюлетеня (або діапазону бюлетенів) — ось що дає вузлу впевненість екстерналізувати C.
Балотування SCP через федеративне голосування. Не показано: у будь-який момент може спрацювати таймер, збільшивши лічильник у бюлетені (і, можливо, зробити новий композит із додаткових висунутих кандидатів).
І це все! Щойно мережа дійшла консенсусу, вона готова робити це знову і знову. У платіжній мережі Stellar це відбувається приблизно раз на 5 секунд: подвиг, який вимагає як безпеки, так і живучості, гарантованих SCP.
SCP може досягти цього, спираючись на кілька раундів федеративного голосування. Федеративне голосування стало можливим завдяки концепції зрізів кворуму: наборів однорангових вузлів, яким кожен вузол вирішив довіряти як частину свого (суб'єктивного) кворуму. Ця конфігурація означає, що можна прийти до консенсусу навіть у мережі з відкритим членством та візантійськими обманами.
подальше читання
- Оригінальний технічний документ SCP можна знайти , а проект специфікацій щодо його впровадження.
- Оригінальний автор протоколу SCP Девід Мазьєр спрощено (але все ж таки технічно) пояснює його .
- Можливо, ви були здивовані, не знайшовши у цій статті термінів «майнінг» чи «доказ роботи». SCP не використовує ці методи, але деякі інші алгоритми консенсусу використовують. Зейн Візерспун написав доступний .
- простий мережі, що досягає консенсусу під час одного повного раунду SCP.
- Для читачів, зацікавлених у реалізаціях SCP: див. , що використовується платіжною мережею Stellar, або який я написав для кращого розуміння SCP.
Джерело: habr.com