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

Автор: Міранда Кріст (аспірантка з інформатики в Колумбійському університеті/стажер із дослідження шифрування a16z), Джозеф Бонно (a16zcrypto) Джерело: a16z crypto; компілятор: Yvonne, MarsBit

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

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

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

держава без громадянства

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

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

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

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

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

Дослідження

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

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

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

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

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

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

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

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

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

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

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

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

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

(Читачі, знайомі з криптографією, можуть помітити, що ми тут замовчуємо деякі деталі; наприклад, декодування Боба не вдається з незначною ймовірністю. Наша стаття містить повне підтвердження.)

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

ВПЛИВ РЕЗУЛЬТАТІВ

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

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

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

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

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