a16z: Про неможливість «блокчейну без стану»

Оригінально написаний Мірандою Кріст і Джозефом Бонно

Компіляція оригінального тексту: Deep Tide TechFlow

Оскільки блокчейн підтримує більше користувачів і частіші транзакції, кількість інформації (або «стан»), що зберігається валідаторами для перевірки транзакцій, збільшується. Наприклад, у біткойнах стан складається з набору невитрачених вихідних даних транзакцій (UTXO). В Ethereum стан складається з балансу кожного облікового запису та коду та сховища кожного смарт-контракту.

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

Це саме мета «блокчейну без стану». Але, незважаючи на численні дослідження, вони все ще далекі від практичних. Але виявилося, що це відставання в прогресі є невід’ємним — прірва між цими збірками та практичністю ніколи не буде подолана. Наша нещодавня робота показує, що будь-яка пропозиція блокчейну без стану, якою б розумною вона не була, неможлива без додаткових заходів для керування станом. Однак, як ми показуємо в кінці цієї статті, цей неймовірний результат не повинен засмучувати.

без статусу

Сьогодні держава величезна, але керована. Наприклад, вузол Bitcoin зберігає близько 7 ГБ даних, а вузол Ethereum зберігає близько 650 ГБ даних. Однак навантаження на сховище на повних вузлах масштабується приблизно лінійно залежно від пропускної здатності ланцюга (транзакцій за секунду, або TPS), що все ще є неприйнятним сьогодні. У поточному плані стан, необхідний для справжньої підтримки повсякденних транзакцій (від десятків до сотень тисяч транзакцій на секунду), стане некерованим, вимагаючи гігабайтів або навіть петабайтів пам’яті.

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

Незважаючи на велику кількість досліджень блокчейнів без збереження стану (наприклад, Тоддом, Бутеріном, Боне та ін. та Срінівасаном та ін.), вони далекі від практичних і, наскільки нам відомо, жодного з них не було розгорнуто. Фундаментальна проблема всіх відомих блокчейнів без збереження стану полягає в тому, що вони вимагають від користувачів зберігати додаткові дані, які називаються свідками, щоб допомогти валідаторам перевірити транзакції, пов’язані з їхніми обліковими записами. Наприклад, цей свідок може бути доказом включення Merkle, який показує, що обліковий запис і баланс користувача включено до глобального державного зобов’язання. Коли користувачі здійснюють транзакції, вони передають це свідоцтво валідаторам, щоб підтвердити, що на їхніх рахунках є достатній баланс.

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

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

Передумови нашого дослідження

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

Спочатку ми будуємо дерево Merkle, де кожна пара (ідентифікатор рахунку, баланс) (a, b) включена як листовий вузол. Стан постійного розміру V, який зберігається валідаторами, є коренем цього дерева, яке діє як зобов’язання для набору пар балансу облікового запису. Кожен користувач зберігає свого свідчення як доказ включення Merkle. Доказ включення Меркла для листка (a,b) складається з партнерських вузлів (v1,...,vk) уздовж шляху від цього листка до кореня дерева. Враховуючи транзакцію за рахунком a та заявлений баланс b, верифікатор може перевірити, що b справді є балансом рахунку a, перевіряючи доказ (v1,...,vk) (a,b) з його поточним станом V. Якщо так, валідатор виконує транзакцію та має відповідно оновити баланс рахунку. Зручною властивістю дерев Меркла є те, що, маючи доказ включення Меркла для листка, легко обчислити корінь результату, коли цей листок змінюється. Іншими словами, верифікатор може легко обчислити оновлений стан V', який фіксує новий баланс рахунку a після виконання транзакції.

Ця схема дерева Меркла має два головних недоліки. По-перше, свідок користувача є відносно великим і зростає логарифмічно із загальною кількістю облікових записів у системі. В ідеалі вони повинні бути постійного розміру, і ми можемо досягти цього за допомогою таких схем, як акумулятори RSA.

Другого недоліку важче уникнути: кожного разу, коли інший користувач здійснює транзакцію, підтвердження пари балансу рахунку змінюється. Пам’ятайте, що доказ листового вузла складається з партнерських вузлів на шляху від цього листового вузла до кореня дерева. Якщо інші листові вузли зміняться, зміниться один із вузлів, що спричинить справжню проблему. Більшість користувачів блокчейну хочуть пасивно зберігати свої монети в гаманцях і виходити в Інтернет лише тоді, коли хочуть здійснювати транзакції. Однак у такому блокчейні без збереження статусу користувачі повинні постійно відстежувати транзакції інших людей, щоб підтримувати актуальну інформацію про свідків. Хоча третя сторона може проводити цей моніторинг від імені користувача, це відрізняється від стандартної моделі блокчейну без збереження стану. На практиці це непереборна проблема для блокчейнів без стану, що лягає важким тягарем на користувачів.

Наш висновок: відсутність громадянства неможлива

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

Це означає, що навіть якщо користувач Аліса не здійснює жодних транзакцій, її інформація про свідка може змінитися разом із транзакціями інших користувачів. Поки компактний стан, який зберігається валідаторами, занадто малий, щоб охопити повний стан (тобто набір усіх балансів на рахунку), збільшення розміру компактного стану мало допомагає. Ми будуємо цей зв’язок, показаний нижче, на основі нашої теореми разом із кількістю змін свідків, необхідних на день для блокчейнів із різною пропускною здатністю. Ці графіки показують, скільки разів оптимальному блокчейну без збереження стану потрібно було б змінити інформацію про свідків. Тут сукупність даних стосується загальної кількості облікових записів у моделі облікового запису або загальної кількості UTXO у моделі UTXO.

В основі нашого доказу лежить інформаційно-теоретичний аргумент. Центральний принцип теорії інформації, формалізований Клодом Шенноном, полягає в тому, що якщо Аліса навмання вибирає об’єкт із набору розміром 2n і хоче повідомити Бобу, який об’єкт вона вибрала, вона повинна надіслати йому принаймні n бітів. Якщо існує схема блокчейну без збереження стану, де користувачі рідко оновлюють інформацію про свідків, Аліса може сказати Бобу, який об’єкт вона вибрала, менш ніж за n біт, що неможливо, як довів Шеннон. Тому такого блокчейну без стану не існує.

Для простоти ми описуємо тут доказ трохи слабшого твердження: не існує блокчейну без стану, де користувачам ніколи не потрібно оновлювати інформацію про свідків. Справа в тому, що Аліса використовує схему блокчейну без збереження стану для кодування свого повідомлення Бобу. Спочатку і Аліса, і Боб знають повний набір пар балансу рахунку для всіх n користувачів. Припустимо, що в кожному обліковому записі є принаймні одна монета. І Аліса, і Боб також знають стислий стан V блокчейну без стану та свідків wi усіх пар балансу облікового запису (ai, bi). Аліса та Боб також узгоджують зв’язок між повідомленнями та наборами облікових записів. Аліса вибере набір A облікових записів, які відповідають її повідомленню, і потім витратить монети з цих облікових записів. Вона використовуватиме блокчейн без збереження стану, щоб передати Бобу вибраний набір, з якого він зможе дізнатися про неї.

Кодування: Аліса витрачає одну монету з кожного рахунку в A. Використовуючи схему блокчейну без збереження стану, Аліса обчислює оновлений стан V' і надсилає його Бобу.

Декодування: для кожного i Боб перевіряє, чи Verify(wi, (ai, bi)) є істинним. Боб виводить набір облікових записів B таким чином, що Verify(wi, (ai, bi)) = false.

Боб успішно виводить той самий набір, який вибрала Аліса: B = A. По-перше, зауважте, що якщо Аліса витрачає монету з рахунку ai, свідоцтво її старого балансу більше не прийматиметься — інакше Аліса зможе подвоїти витрати. Отже, для кожного облікового запису ai в A Verify(wi, (ai, bi)) = false, і Боб включить цей обліковий запис у B. З іншого боку, Боб ніколи не включатиме в облікові записи B, з яких Аліса не витрачала монети, оскільки баланси цих рахунків залишаються незмінними, і (згадайте м’яке твердження, яке ми хочемо довести), їхні свідки ніколи не зміняться. Отже, В точно дорівнює А.

Нарешті, ми вирішуємо наше протиріччя, обчислюючи кількість бітів, які Аліса повинна надіслати Бобу. Існує 2^n підмножин, які вона може вибрати, тому, згідно із законом Шеннона, вона повинна надіслати Бобу принаймні n бітів. Однак вона надсилає лише стан постійного розміру V', який набагато коротший за n біт.

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

Ефект результату

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

Існують деякі інші багатообіцяючі рішення, які відрізняються від моделі блокчейну без збереження стану. Природним послабленням цієї моделі є можливість третій стороні (ані користувачам, ані валідаторам) нести відповідальність за збереження повного стану. Ця третя сторона, яка називається вузлом служби перевірки, використовує повний стан для створення останньої інформації про свідків для користувача. Потім користувачі можуть здійснювати транзакції за допомогою цих свідків, як у звичайному блокчейні без збереження стану, де валідатори все ще зберігають лише компактний стан. Механізм стимулювання цієї системи, особливо те, як користувачі компенсують вузли підтвердження обслуговування, є цікавим відкритим напрямком дослідження.

Хоча наше обговорення досі було зосереджено на блокчейні L1, наші результати також мають значення для систем L2, таких як сервери Rollup. Зведення (оптимістичний чи ZK) зазвичай зберігає зобов’язання щодо великого стану на L1 із невеликим значенням. Цей стан включає облікові записи кожного користувача на L2. Ми хочемо, щоб ці користувачі могли знімати кошти безпосередньо на L1 (без співпраці з серверами L2), публікуючи свідок поточного балансу свого рахунку. Ця установка також є прикладом оборотної системи перевірки в нашій моделі. Насправді можна стверджувати, що блокчейни без стану вже реалізовані на практиці у формі зведених пакетів L2.

Однак, на жаль, це означає, що наші результати щодо неможливості застосовуються безпосередньо. Свідок отримання зведених даних користувача повинен часто змінюватися, інакше майже весь стан L2 потрібно було б записати в L1. Як наслідок, сьогодні Rollups зазвичай передбачає існування комітету доступності даних (іноді його називають «validium»), подібного до «вузла доказової служби», який допомагає користувачам обчислювати нових свідків, коли вони готові отримати доступ. Наші результати показують, що попередження для користувачів у документації Ethereum: «Без даних про транзакції користувачі не можуть обчислити докази Merkle, щоб підтвердити право власності на кошти та здійснити зняття коштів» буде застосовуватися завжди.