Глубокое погружение в BitVM

Это перевод статьи Ичиро Кувахара из Cryptogarage.

Что такое BitVM?

BitVM - это "вычислительная парадигма для выражения Тьюринг-полных контрактов Биткоина", предложенная Робином Лайнусом, которая не требует софт-форка.

Скрипт Биткоина разработан как Тьюринг-неполный, что делает невозможным реализацию произвольных контрактов, подобных тем, что реализованы на основе (E)VM-цепей. Предыдущие предложения по реализации Тьюринг-полных контрактов на Биткоине требовали софт-форка для активации новых опкодов. BitVM отличается от этих предложений тем, что он не требует этого (изменений в конесенсусе).

Обратите внимание, что у BitVM все еще есть важные ограничения:

• Контракты ограничиваются только двумя сторонами
• Требуется значительное количество вычислений и взаимодействия между двумя сторонами (то есть, от сотни мегабайт и до нескольких гигабайт взаимодействия с данными; локальное хранение) Несмотря на эти ограничения, предложение вызвало активное обсуждение в сообществе.

В следующем разделе подробно описывается, как устанавливать контракты между Вычислителем (Prover), который утверждает, что знает ответ на определенную проблему, и Верификатором (Verifier), который оценивает правдивость этого утверждения. Пока обе стороны сотрудничают, они могут совместно урегулировать любой контракт (используя мультиподпись типа 2-из-2). Если Проверяющий не согласен с тем, что утверждение Утверждающего верно, инициируется схема "Вызов и Ответ" — об этом будет подробно рассказано позже — и если несоответствия утверждения будут выявлены, Верификатор имеет право изъять средства Вычислителя.

Прежде чем касаться работы BitVM, мы предоставим некоторые предварительные сведения.

Предварительные Сведения

Логические Схемы

Код, написанный на языке программирования, компилятором преобразуется в двоичный код (последовательность нулей и единиц). Процессор читает этот двоичный код и выполняет инструкции, используя логические схемы. Типичные примеры компонентов, составляющих логические схемы, включают в себя И-вентили (AND gates), ИЛИ-вентили (OR gates), НЕ-вентили (NOT gates) и И-НЕ-вентили (NAND gates). NAND-вентили называются "универсальными вентилями", потому что их можно использовать для построения всех других вентилей.

В статье NAND-вентили используются только ради аргументации, чтобы абстрагироваться от всей сложности создания эффективных скриптов биткоина. Мы называем эту схему "Двоичной Цепью". Автор считает, что На практике использование всех доступных опкодов скрипта биткоина делает транзакции в цепочке (onchain TXs) в 10-100 раз меньше, чем при использовании только NAND-вентилей.

На следующем рисунке показана Двоичная Цепь с входами A, B, C и D. Утверждающий заявляет, что он(а) знает все входы.

OP_NAND

Существующие опкоды Биткоина, OP_BOOLAND и OP_NOT, могут быть объединены для выполнения функций операции И-НЕ (NAND).

Мы называем это сочетание OP_BOOLAND и OP_NOT "OP_NAND".

Битовый коммитмент

Ниже приведен скрипт для Вычислителя, который закрепляет обязательства по входным и выходным значениям (0 или 1) каждого И-НЕ-вентиля. Если утверждающий предоставляет предобраз hash1, 1 помещается в стек. Если утверждающий предоставляет предобраз hash0, 0 помещается в стек.

Мы называем эти наборы опкодов "OP_BIT_COMMITMENT".

OP_IF
OP_HASH160
<hash1>
OP_EQUALVERIFY
<1>
OP_ELSE
OP_HASH160
<hash0>
OP_EQUALVERIFY
<0>
OP_ENDIF

Бинарный NAND коммитмент

Следующий скрипт предназначен для Вычислителя, чтобы принять на себя обязательства по Логическому Вентилю (NAND1), сочетая OP_NAND и OP_BITCOMMITMENT. Когда они предоставляют следующие три значения, три набора значений (0 или 1), а именно A, B и E, помещаются на стек.

Предобраз хэша HashA0 или HashA1
Предобраз хэша HashB0 или HashB1
Предобраз хэша HashE0 или HashE1

Если утверждение A NAND B == E является верным, этот скрипт может быть разблокирован.

// Раскрыть прообраз hashE0 или hashE1
<hashE0/1>
OP_BITCOMMITMENT
OP_TOALTSTACK
// Сейчас битовое значение "E" в стеке
// Раскрыть прообраз hashB0 or hashB1
<hashB0/1>
OP_BITCOMMITMENT
OP_TOALTSTACK
// Сейчас битовое значение "B" в стеке
// Раскрыть прообраз hashA0 или hashA1
<hashA0/1>
OP_BITCOMMITMENT
OP_TOALTSTACK
// Сейчас битовое значение "A" в стеке
//
// Верифицировать "A NAND B == E"
//
// Прочитать "B" из альтернативного стека
OP_FROMALTSTACK
# Вычислить A NAND B
OP_NAND
# Прочитать "E" из альтернативного стека
OP_FROMALTSTACK
# Проверить A NAND B == E
OP_EQUALVERIFY

Вызов и Ответ

Протокол "Вызова и Ответа" (challenge-response) инициируется, когда Верификатор не согласен с тем, что утверждение Вычислителя верно. Если будут выявлены несоответствия утверждения, Верификатор имеет право изъять средства Вычислителя.

Верификатор выбирает один вентиль из схемы, и Вычислитель раскрывает входные и выходные данные (мы называем это открытием Вентиля). Обе стороны повторяют этот процесс несколько раз, пока не будет обнаружено несоответствие, или Верификатор исчерпает пространство возможных вызовов. Если Вычислитель утверждает, что D=1, когда один вентиль открыт, но позже утверждает, что D=0, когда открыт другой вентиль, то он высказывается двусмысленно, и Верификатор может изъять средства Вычислителя.

Обратите внимание, что Верификатор не обязан открывать каждый Вентиль. В примере ниже Проверяющий просит Утверждающего открыть NAND7, NAND1, NAND3, NAND6 и NAND5 по порядку.

Изначально, когда запрашивается открыть NAND6, Вычислитель заявляет "I=1". Однако затем, когда запрашивается открыть NAND1, NAND3, NAND6 и затем NAND5, Вычислитель вынужден дать противоречивый ответ "I=0". Когда запрашивается открыть NAND6, если Вычислитель понимает, что он даст противоречивый ответ о значении I и не открывает его, Верификатор может изъять средства Вычислителя после определенного периода времени - таймлока.

Дерево Вызова Taptree и Дерево Ответа Taptree

Дерево Taptree используется обеими сторонами для коммитментов "Вызов и Ответ". Taptree - это Мерклево дерево, состоящее из скриптов в качестве листьев и корня (Taproot), который может быть использован для модификации секретного ключа, позволяя использовать либо ключ (путь ключа), либо скрипт внутри Taptree (путь скрипта) для разблокировки выхода. В следующем примере Верификатор выбирает Вентиль7, раскрывая условие разблокировки Дерева Вызова Taptree, и Вычислитель открывает Вентиль7, раскрывая условие разблокировки Дерева Ответа Taptree.

Если Вычислитель раскрывает разное значение для одной и той же переменной (например, E=0 && E=1), утверждение Вычислителя ложно, и Верификатор может получить все средства. Эта модель реализуется с помощью следующего Дерева Equivocations Taptree.

До сих пор мы узнали, что Вычислитель и Верификатор создают обязательства (коммитменты) по логическим вентилям, используя комбинацию скриптов Биткоина, и что Taptree используются для коммитов доказательств, основанных на схеме протокола "Вызов-Ответ". В следующих разделах мы объясним детали протокола BitVM.

Детали протокола BitVM

Ниже приводится последовательность действий контракта с использованием BitVM между Вычислителем, который утверждает, что знает значение, удовлетворяющее некоторому произвольному уравнению, и Верификатором.

1. Построение Цепи

Контракт реализуется на языке программирования и компилируется в большую Двоичную Цепь; Вычислитель утверждает, что определенный набор Входных данных, поданных на схему, приводит к определенному Выходному значению.

2. Построение и Предварительное Подписание Транзакции

Транзакция создается и предварительно подписывается между Вычислителем и Верификатором, чтобы принять на себя обязательства по доказательству значения входных данных Двоичной цепи и схеме проверки.

3. Выполнение Контракта

Обе стороны подписывают и транслируют Tx1 на рисунке ниже, чтобы заблокировать свои средства. После подтверждения транзакции контракт выполняется.

Tx1 находится в цепочке, в то время как Tx2~Tx4 еще не были транслированы. Tx2 и Tx4 находятся у Проверяющего, а Tx3 у Утверждающего.

Обратите внимание, что диаграмма выше отличается от первоначального предложения. На рисунке выше выход первой транзакции делится на две части, и SIGHASH_ALL используется для предварительного подписания. Если выход не разделен, все tapleafs, которые могут быть использованы, должны быть предварительно подписаны. Подробности см. здесь.

Если Верификатор принимает утверждение Вычислителя как верное, они пропускают шаг "4. Вызов и Ответ" и переходят к шагу "5. Урегулирование". Если Верификатор считает утверждение Вычислителя неверным, они переходят к следующему шагу.

4. Вызов и Ответ

Верификатор выбирает вентиль по своему выбору, раскрывая условия разблокировки Дерева Вызова Taptree, а Вычислитель открывает вентиль, раскрывая условия разблокировки Дерева Ответа Taptree. В идеале это взаимодействие осуществляется вне цепочки. (Хотя оно также может быть выполнено в цепочке) Обе стороны повторяют этот процесс несколько раз, пока не будет обнаружено несоответствие или Вычислитель исчерпает пространство возможных вызовов.

Следующий пример показывает, как Вычислитель и Верификатор дважды повторяют процесс "Вызов и Ответ" вне цепочки, и обнаруживается несоответствие.

В первом Вызове Верификатор выбирает вентиль NAND1, и Вычислитель раскрывает его входные и выходные данные (A=1, B=1, E=0). Во втором Вызове Верификатор выбирает вентиль NAND4, и Вычислитель раскрывает его входные и выходные данные (E=1, F=1, H=0). Обратите внимание, что Верификатор дает несогласованный ответ: E=0 в первый раз и E=1 во второй раз. Поскольку Вычислитель сделал двусмысленное заявление, Верификатор переходит к шагу "5. Урегулирование", чтобы изъять средства Вычислителя.

5. Урегулирование

Если Верификатор принимает утверждение Вычислителя как верное на шаге "3. Выполнение Контракта", они пропускают шаг "4. Вызов и Ответ". Пока обе стороны сотрудничают, они могут совместно урегулировать любой контракт с подписью 2 из 2.

Если Вычислитель дает несогласованный ответ на шаге "4. Вызов и Ответ", например E=0 в первый раз и E=1 во второй раз, Верификато получает предобраз (E=0) и предобраз (E=1), что являются условиями, при которых адрес конфликта (Equivocations Taproot) может быть разблокирован. Верификатор получает средства Вычислителя, транслируя Tx6, как показано ниже.

Дальнейшее Развитие

Более высокоуровневые опкоды для эффективности

Робин Лайнус утверждает, что NAND-вентили используются только ради аргументации, чтобы абстрагироваться от всей сложности создания эффективных скриптов биткоина. Он считает, что на практике использование всех доступных опкодов скрипта биткоина делает транзакции в цепочке (onchain TXs) в 10-100 раз меньше, чем при использовании только NAND-вентилей. Вот почему были созданы более высокоуровневые опкоды для таких операций, как сложение u32, исключающее ИЛИ u32, побитовый сдвиг u32.

Более общие контракты

Предложенная модель ограничена двумя сторонами. Необходимо больше исследований для развития этой модели до N:N.

BitVM "Бесскриптовые Скрипты"

ZmnSCPxj предложил “Scriptless Script BitVM”, заменяя хеши и предобразы точками и скалярами. Используя этот трюк, мы можем уменьшить размер транзакции и их количество на цепочке цепочке.

Заключение

BitVM - это проект, который позволяет реализовать Тьюринг-полные контракты Биткоина без софт-форков. Если вы хотите внести свой вклад, вот Репозиторий. Также вы можете обсудить эту тему в группе Телеграм.

/send 100 [email protected]