Масштабовані однорангові токени на біткойнах: вирішіть проблему повернення до Genesis за допомогою рекурсивних SNARK

Ця публікація була вперше опублікована на Середній.

Це реалізація Рішення nChain¹.

Проблема повернення до книги Буття

Токени на Bitcoin зазвичай зберігаються в UTXO. Коли передбачувана транзакція маркера отримана, користувачеві потрібен спосіб ефективно та швидко перевірити її автентичність. Основна частина полягає в тому, щоб вирішити, чи пов’язано це з певною транзакцією генезису, де випускається токен.

У базовій формі проблема «Назад до генезису» (B2G) зводиться до наступного: задана транзакція, чи пов’язана вона з певною транзакцією генезису в безперервному ланцюжку транзакцій?

всі токени на Bitcoin сьогодні для вирішення проблеми доводиться покладатися на надійну третю сторону, оскільки легкому користувачеві стає складно перевірити себе, коли ланцюжок надто довгий². Наприклад, DotWallet’s Бейдж токени використовують індексатор токенів і Розумний токени використовують оракул. Ця залежність від сторонніх розробників перешкоджає прийняттю токенів на біткойн, оскільки він не такий масштабований і SPV-дружні як рідні біткойни.

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

Рекурсивні SNARK

Відкликати в рекурсивний SNARKзокрема обчислення з можливістю інкрементної верифікації (IVC), ми хочемо довести, що функція F, застосована n разів до початкового введення z₀, дає zₙ.

На кожному кроці, zᵢ є внесок громадськості та wᵢ приватний вхід (тобто свідок).

Кожен крок дає новий доказ. В кроку iалгоритм перевірки обчислює 𝛑ᵢ, що підтверджує всі кроки до i є правильними, використовуючи лише локальну інформацію з останнього та поточного кроків, як показано нижче. Важливо те, що він не відстежує все назад до кроку 0, але все ще може перевірити, що всі кроки, починаючи з кроку 0, виконано правильно.

Алгоритм перевірки: обчислюйте докази поступово

Застосування рекурсивних SNARK до B2G

IVC природно веде до елегантного вирішення проблеми B2G.

IVC в B2G

Конкретно IVC створюється таким чином:

• zᵢ: txidᵢ, ідентифікатор транзакції i-ї транзакції в ланцюжку
• wᵢ: залишок i-ї операції. Ми ділимо його на дві частини: префіксᵢ і постфіксᵢ, які представляють те, що стоїть перед і після txidᵢ.
• функція Ф: txid транзакції є подвійним SHA256 її та (i+1)-й транзакція витрачає і-й транзакція, її txid і таким чином Ф розраховується наступним чином:

txid це частина червоної коробки, префікс/постфікс це все до/після нього відповідно. || є конкатенація.

Трансакція

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

Простий протокол токенів NFT

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

Коли Аліса передає NFT Бобу, вона створює транзакцію з Бобом як одержувачем і передає її Бобу безпосередньо з мережі. Завдяки одноранговій природі біткойна вона також надсилає підтвердження SNARK разом із транзакцією. Аліса може згенерувати доказ без відстеження транзакції генезису, як ми пояснювали раніше.

Боб приймає NFT, лише якщо обидві перевірки проходять:

1. він підтверджує транзакцію за допомогою SPVсхожий на звичайний платіж у біткойнах
2. він перевіряє доказ⁴.

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

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

Час перевірки

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

Реалізація

Ми реалізували рекурсивний SNARK за допомогою snarkyjs як зазначено нижче.

Рекурсивний доказ B2G

Для початку нам потрібно скомпілювати програму, щоб отримати ключ перевірки. Зверніть увагу, що є ні надійне налаштування.

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

The генезис метод, починаючи з рядка 5, викликається для створення початкового доказу, який просто перевіряє txid0 це ідентифікатор транзакції genesis у рядку 9.

The передача метод, починаючи з рядка 13, викликається для створення нового доказу, що підтверджує:

• останній доказ дійсний у рядку 17
• поточна транзакція проводить останню транзакцію в рядках 18 і 19.

Нарешті, ми можемо перевірити доказ за допомогою ключа перевірки.

Повний код можна знайти в це репо Github.

Резюме

Ми представляємо лише простий приклад NFT із використанням рекурсивних SNARK. Його можна розширити до орієнтованого ациклічного графа (DAG), а не до ланцюга транзакцій. Його також можна поширити на взаємозамінні токени або будь-які інші випадки використання, коли користувачеві потрібно ефективно переконатися, що транзакція може бути пов’язана з деякою трансакцією предка.

Подяки

Ми дякуємо nChain за те, що поділилися оригінальною ідеєю застосування рекурсивних SNARK до проблеми B2G. Ми також дякуємо Грегору Мітша-Боде з O(1) Labs за допомогу в реалізації схеми SHA256.

***

ПРИМІТКИ:

[1] WP1590 Transaction Chain Proof, MS Kiraz і O. Vaughan, заявка на патент GB2200400.6.

[2] У більш загальному вигляді транзакції утворюють спрямований ациклічний граф (DAG), що робить розв’язання B2G ще більш інтенсивним з точки зору обчислень.

[3] Це може бути виконано в смарт-контракті або схемі SNARK, або в обох. У першому ми можемо використовувати OP_PUSH_TX техніка для обмеження кількості входів і виходів у всіх транзакціях, що походять від транзакції генезису. Наприклад, ми можемо забезпечити, щоб будь-яка транзакція NFT мала два входи та один вихід. Другий вхід покриває комісію за транзакцію.

[4] За бажанням перевірку доказу можна виконати в ланцюжку. Це вимагає лише впровадження верифікатора в система доказів Snarkyjsподібний до Верифікатор Groth16 ми реалізували.

Дивіться: презентацію BSV Global Blockchain Convention, смарт-контракти та обчислення на BSV

Не знайомі з біткойнами? Перегляньте CoinGeek Bitcoin для початківців найкращий путівник із ресурсами, щоб дізнатися більше про біткойн (як його спочатку задумував Сатоші Накамото) та блокчейн.