BitVM: Smarter Bitcoin Smarter (하)

Published in

Decipher Media ｜디사이퍼 미디어

29 min read3 days ago

Disclaimer : 서울대학교 블록체인 학회 디사이퍼(Decipher)에서 BitVM을 주제로 Weekly Session에서 발표한 내용을 바탕으로 합니다. 본 아티클은 BitVM의 등장 배경과 기술적 원리에 대해 설명합니다. 이 보고서에 포함된 어떠한 내용도 투자 조언이 아니며, 투자 조언으로 해석되어서도 안 됩니다.

시리즈

BitVM: Smarter Bitcoin Smarter (상)
BitVM: Smarter Bitcoin Smarter (하)

Author

최원재(@0xwonj) of Decipher

Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)

Reviewed By 이현우, 최재우, 신성헌

1. Abstract

2. Background
2.1. Bitcoin’s Design Choice
2.2. Bitcoin Upgrades and Emerging Ecosystem
2.3. Scaling Bitcoin

3. What is BitVM
3.1. Introduction
3.2. Use Cases
3.2. Architecture

4. Verify Everything on Bitcoin
4.1. Bit Commitment
4.2. Gate Commitment
4.3. Binary Circuit Commitment

5. Challenge-Response Protocol
5.1. Wrong Computation
5.2. Equivocation
5.3. Dishonest Off-chain Interaction

6. Future of BitVM
6.1. Limitations
6.2. BitVM 2

7. Final Thoughts

1. Abstract

본 아티클은 BitVM의 탄생 배경과 기술적인 동작 원리를 자세하게 설명하는 목적으로 쓰여졌다. 이를 이해하기 위해 필요한 사전 지식들은 BitVM (상)편에 자세히 정리되어 있으니 이를 참고하기 바란다.

이 글은 먼저, 배경 부분에서 비트코인의 설계 철학과 확장성 문제, 그리고 이를 해결하기 위한 BitVM의 필요성을 설명한다. 이어서, BitVM의 개념, 사용 사례, 기술 구조를 다룬다. 그 다음, 비트코인 상에서 BitVM의 비트 커밋먼트와 논리 회로를 통한 검증 방법을 설명한다. 이후, 챌린지-리스폰스 프로토콜을 통해 증명자의 부정 행위를 처벌하는 메커니즘을 다루며, 마지막으로 BitVM의 한계와 향후 발전 방향을 논의한다.

2. Background

2.1. Bitcoin’s Design Choice

비트코인은 UTXO 모델을 채택하고, 스마트 컨트랙트의 기능을 제한한 블록체인이다. 비트코인의 이러한 특성은 보안과 탈중앙성을 가장 중요하게 생각하는 철학과 결제를 위해 만들어진 비트코인의 사용용도에 맞게 설계된 것이다. 하지만 이러한 설계는 여러 단점들 또한 포함하는 트레이드오프(Trade-off)이다.

장점

보안: UTXO와 비트코인 스크립트의 단순한 구조로 인해 다양한 보안적 위험으로부터 비교적 안전하다. (예: DoS 공격)
효율성: UTXO 모델은 다른 트랜잭션 결과나 블록체인의 상태에 의존하지 않으므로, 빠르고 병렬적으로 처리될 수 있으며, 블록체인의 크기가 작게 유지된다.

단점

월드 스테이트(World State)의 부재: UTXO 모델은 트랜잭션의 입력(input)과 출력(output)만을 참고하여 실행되므로, 상태값이 저장되고 활용되어야 하는 디앱의 구현이 불가능하다. (EVM에서의 스토리지가 없음)
튜링 불완전성(Turing Incompleteness): 컨트랙트 언어로 스택 기반의 단순한 프로그래밍 언어를 사용하여, 반복문이나 메모리, 힙 등이 없고 표현력이 부족하다. (EVM에서의 메모리가 없음)

추가적으로, 비트코인은 느린 블록 생성 시간과 블록 크기 제한과 같은 제약 사항이 있으며, 이는 보안과 효율성을 높이는 동시에 낮은 확장성과 제한된 사용 사례를 유발한다.

2.2. Bitcoin Upgrades and Emerging Ecosystem

비트코인 진영에서도 낮은 확장성과 제한된 사용사례에 대한 문제점은 중요한 해결 과제였고, 이를 개선하기 위한 여러번의 프로토콜 업그레이드가 이루어졌다. 이러한 업그레이드는 주로 기존의 기능을 해치지 않으면서 낮은 확장성을 개선하는 방향으로 진행되었다. 이들 중 가장 영향력이 컸던 업그레이드들은 세그위트(Segwit)와 탭루트(Taproot) 업그레이드이다. 특히 탭루트 업그레이드는 확장성과 컨트랙트의 낮은 표현력 문제를 일부분 해결한 가장 파격적인 업그레이드이며, 이는 본 아티클의 주제인 BitVM에서도 가장 핵심적으로 활용되는 기능이다.

이러한 비트코인의 방향과 더불어, 비트코인 위에서는 다양한 생태계가 생겨났다. Ordinals, BRC-20, 탭루트 자산(Taproot Assets) 등의 새로운 자산들, 또는 스택스(Stacks)와 같은 비트코인 레이어 등이 그러한 대표적인 사례이다. 이러한 시도들은 비트코인이 단순히 수동적인 자산이 아니라 다른 블록체인과 같이 그 위에 다양한 생태계가 조성될 수 있음을 보여주었다.

2.3. Scaling Bitcoin

비트코인의 확장성을 해결하는 업그레이드들이 수차례 진행되었지만, 근본적으로 비트코인의 컨트랙트는 디파이(DeFi)와 같은 디앱(DApp)을 만들 수 없기 때문에 이더리움과 같이 블록체인 위의 다양한 생태계가 생겨날 수 없었다. 단지 비트코인 위에 다양한 자산들이 생겨났을 뿐이다. 이를 해결하기 위해 비트코인 확장성 솔루션들이 많이 탄생하였고, 가장 대표적인 예시는 스택스(Stacks)이다. 하지만 스택스는 사이드체인이라는 한계를 가지고 있다. 사이드체인은 확장성을 개선하기 위해 메인 블록체인과 연결된 독립된 블록체인으로, 메인넷의 보안을 상속받지 못한다는 단점이 있다. 그렇기 때문에 이더리움에서는 사이드체인보다는 레이어 1의 보안을 상속받는 롤업(Rollup) 방식의 레이어 2 솔루션들이 주로 사용되고 있다.

그렇다면 비트코인에서는 왜 롤업 방식의 레이어 2 솔루션이 사용되지 못했던 것일까? 그 이유는 비트코인 스크립트의 튜링 불완전성에 있다. 롤업 방식에서는 레이어 2 블록체인에서 일어난 트랜잭션들이 레이어 1에서 검증되는 정산(Settlement)의 과정이 필수적이다. 이 과정을 통해 레이어 2의 트랜잭션들이 레이어 1의 합의(Consensus)에 의해 검증된다. 다른 말로 레이어 1의 보안을 상속받는다. 이더리움에서는 이 과정이 이더리움 메인넷의 스마트 컨트랙트로 처리된다. 하지만 비트코인 스크립트로는 레이어 2의 트랜잭션을 검증하는 스마트 컨트랙트를 구현하는 것이 불가능하기 때문에, 롤업 방식의 레이어 2 솔루션이 존재하지 않았던 것이다.

이러한 이유로 비트코인에서는 확장성 솔루션들이 이더리움에 비해 규모가 크지 않고 잘 사용되지 않았다. 하지만 만약 레이어 2의 트랜잭션이 검증될 수 있도록 하는 스마트 컨트랙트를 비트코인에서 구현할 수 있다면 어떨까? 기존에 불가능하다고 여겨졌던 이 방법을 가능하게 한 것이 바로 BitVM이다. 즉, BitVM을 이용한다면 레이어 2의 트랜잭션들이 비트코인에서 검증받을 수 있게 되어 비트코인 위에 진정한 레이어 2가 구현될 수 있다는 것이다.

3. What is BitVM

3.1. Introduction

BitVM은 2023년 8월에 ZeroSync의 공동창업자이자 비트코인 개발자인 Robin Linus가 백서를 공개하면서 세상에 처음 알려졌다. 오픈소스 프로젝트로, Spiral, StarkWare, OpenSats 등의 비트코인과 ZK 관련 재단에 의해 후원되고 있다.

BitVM은 비트코인 상에서 튜링 완전한 컨트랙트를 표현하기 위한 계산 패러다임이다. 비트코인의 프로토콜의 변경 없이 구현 되어 비트코인의 보안에 어떠한 영향도 미치지 않는다. BitVM은 비트코인에서 직접 계산을 실행하는 대신, 오프체인(Off-chain)에서 계산하고 이를 온체인(On-chain) 상에서 사기 증명(Fraud Proof)를 통해 검증하는 방식으로 동작한다. 옵티미스틱 롤업(Optimistic Rollup)의 방식과 비슷하다고 할 수 있다.

이 시스템은 증명자(Prover)와 검증자(Verifier)라는 두 주체로 구성된 설정을 가정한다. 증명자는 특정 계산이 올바르다는 것을 비트코인 상에서 증명하고자 하며, 이는 함수, 입력, 입력에 대한 출력, 이 세 가지 요소가 올바른 계산을 이루는 것을 증명하는 것이 목표다. 검증자는 그 주장이 거짓임을 밝혀내면 사기 증명을 수행하고 증명자를 처벌할 수 있다. 이 메커니즘을 통해 어떠한 계산 가능한 함수도 비트코인 상에서 검증할 수 있다.

3.2. Use Cases

BitVM을 사용하면 어떤 계산 가능한 함수도 비트코인 상에서 검증할 수 있게 된다. 하지만 이를 이용해 이더리움과 같이 유니스왑(Uniswap) 같은 디파이 디앱 등을 만드는 것은 UTXO 모델의 상태관리 문제로 인해 힘들다. 대신, 두 가지 핵심적인 사용 사례가 있다.

첫 번째는 영지식 증명 검증기(Zero-Knowledge Proof Verifier)의 구현이다. 영지식 증명 검증이 비트코인 상에서 가능해지면, 이는 레이어 2 블록체인의 정산(Settlement)을 가능하게 한다. 이를 통해 복잡한 계산과 데이터 프라이버시를 보장하는 다양한 애플리케이션을 비트코인 네트워크에서 직접 지원할 수 있다.

두 번째는 무허가 브릿지(Permissionless Bridge)의 구현이다. 현재 비트코인 브릿지는 대부분 중앙화된 다중서명 지갑(Multi-sig Wallet)을 활용한 방식을 사용하고 있다. 이러한 방식은 보안과 중앙화 문제를 가지고 있다. 그러나 BitVM을 사용하면 무허가 브릿지를 구현할 수 있으며, 이는 비트코인과 다른 블록체인 간의 안전하고 탈중앙화된 자산 전송을 가능하게 한다. 이는 레이어 2 솔루션에서도 필수적인 요소이다.

이 두 가지 기능을 구현함으로써 BitVM은 비트코인 위에서 레이어 2 솔루션을 개발하는 데 핵심적인 역할을 할 수 있다.

3.3. Architecture

BitVM은 튜링 완전성과 오프체인 계산 및 사기 증명을 구현하기 위해 비트코인의 해시락(Hashlock), 타임락(Timelock), 그리고 탭루트를 사용한다.

BitVM의 과정을 단계 별로 간략하게 보면 다음과 같다:

증명자가 비트코인에서 증명하고 싶은 프로그램을 정의한다. 이 프로그램은 입력과 출력이 존재하는 어떤 계산 가능한 함수도 될 수 있다. 또한 이를 검증하고자 하는 검증자가 있어야 한다.
예시: 덧셈 프로그램 f(a, b) = a + b
증명자는 이 프로그램(계산 가능한 함수)를 논리 회로 단위로 컴파일하여 이를 비트코인 스크립트로 탭루트에 커밋한다. 이 커밋된 스크립트들은 이 프로그램을 검증할 수 있도록 한다.
예시: f → 논리 회로 → 비트코인 스크립트들 → 탭루트
증명자와 검증자는 나중에 분쟁을 해결할 수 있도록 미리 일련의 챌린지-리스폰스(Challenge-Response) 트랜잭션들을 공동으로 사전서명(Pre-sign)한다. 이 트랜잭션들은 HTLC 방식의 스크립트를 사용하고, 각자의 개인키로 서명하여 상대방에게 준다.
증명자는 예치금(Deposit) 비트코인을 특정 탭루트 주소에 입금한다. 이 예치금은 계산이 올바르지 않았을 경우나 증명자가 부정 행위를 한 경우 검증자가 이 예치금을 가져감으로써 증명자를 처벌하기 위함이다. 옵티미스틱 롤업의 슬래싱을 위한 보증금과 같은 역할이다.

여기까지 설정(Setup)의 과정이 끝나면 BitVM 컨트랙트가 활성화 되었다. 이제 증명자는 예치금을 걸고 프로그램이 올바르다고 주장하는 검증자는 증명자의 틀린 주장과 부정 행위에 대해 온체인 상에서 처벌할 수 있는 모든 권리를 가진다. 이는 3번의 사전서명 트랜잭션을 통해 가능하다.

5. 프로그램을 검증하기 위해 오프체인에서 데이터를 교환하는 방식으로 증명자는 프로그램에 대한 입력과 출력 값을 검증자에게 제공한다.
예시: 입력 = 2, 5 / 출력 = 7

6. 검증자는 프로그램, 입력, 출력 값을 이용해 오프체인에서 직접 실행하며 이를 검증한다.
예시: 2 + 5 = 7 → O

7-a. 계산이 올바르게 검증된 경우, 검증자는 챌린지를 걸지 않는다. 챌린지 기간이 지나면 증명자는 예치금을 가져갈 수 있고, 해당 계산은 비트코인에 의해 검증이 완료되었다.

7-b. 계산이 올바르지 않은 경우, 검증자는 사전서명 트랜잭션을 이용해 챌린지를 걸고 챌린지-리스폰스 프로토콜을 시작한다. 이 과정을 통해 검증자는 증명자를 처벌하여 증명자의 예치금을 가져갈 수 있게 된다.

다음 섹션에서는 이러한 과정이 실제로 어떻게 이루어지는지 두 부분으로 나누어 설명한다. 첫 번째는 비트코인 상에서 계산이 검증되는 방식을 다루고, 두 번째는 비트코인 상에서 사기 증명이 구현되는 챌린지-리스폰스 프로토콜의 동작 방식을 설명한다.

4. Verify Everything on Bitcoin

4.1. Bit Commitment

비트코인 스크립트가 표현력이 부족한 주요 원인 중 하나는 상태가 없기(Stateless) 때문이다. 이는 UTXO(Unspent Transaction Output) 모델의 검증 방식으로 인해 발생하는데, UTXO 모델에서는 입력과 출력만을 보고 트랜잭션을 검증한다. 따라서 다른 트랜잭션과 어떤 값을 공유하는 것이 불가능하다.

간단한 예를 들어보자. 어떤 변수 x를 선언하여 여러 트랜잭션에서 이 값을 공유하고 싶다고 하자. 만약 이더리움의 EVM(Ethereum Virtual Machine)이라면, 어떤 컨트랙트의 스토리지에 x를 선언함으로써 여러 트랜잭션들이 이 값을 사용할 수 있다. 하지만 비트코인에서는 이와 같은 방식이 불가능하다.

이 문제를 해결하기 위해 BitVM에서는 비트 커밋먼트(Bit Commitment)라는 새로운 방법론을 제시한다. 비트 커밋먼트는 증명자가 어떤 변수의 값을 설정할 수 있도록 하는 방법이다. 구체적으로는, 서로 다른 스크립트들 사이에 어떤 변수의 값을 0 또는 1로 강제한다. 이를 통해 실행 환경이 단일 스크립트에 제한되지 않고, 여러 스크립트에서 실행되어 상태 값을 공유할 수 있기 때문에 튜링 완전한 계산을 구현할 수 있다.

이를 구현하는 원리는 램포트 서명(Lamport Signature)과 유사하다. 어떤 변수에 0 또는 1의 값을 할당하는 방법은 다음과 같이 이루어진다:

증명자는 암호학적으로 안전한 난수 생성기를 이용해 무작위 문자열 두 개를 생성한다. 이를 preimage0와 preimage1라 하자. (해시 함수의 출력 값에 대응하는 입력 값을 프리이미지(preimage)라 한다.)
preimage0와 preimage1을 각각 해시하여 두 해시 값을 구한다. 이 값을 hash0와 hash1라 하자.
증명자는 프리이미지들은 공개하지 않고, 해시 값들만 공개한다.
만약 증명자가 변수의 값을 0이라고 주장하고 싶다면, preimage0의 값을 공개(Reveal)한다.

5-a. 만약 증명자가 변수의 값을 0과 1로 동시에 주장한다면, 검증자에 의해 예치금을 빼앗기게 된다. 이 상황을 Equivocation이라 한다.

5-b. 증명자가 아무 값도 공개하지 않는 경우에도 검증자가 증명자의 예치금을 빼앗을 수 있다.

즉, 증명자가 커밋한 두 해시 값에 대해 무조건 하나의 해시 값만 공개하도록 강제하여, 공개한 해시 값에 따라 변수가 0 또는 1로 강제되는 원리이다. 그렇다면 실제로 비트코인 스크립트로는 어떻게 동작하는지 아래에서 보도록 하자.

전제

스택은 후입선출(LIFO)의 자료구조이다.
push: 주어진 요소를 스택의 맨 위에 추가한다.
pop: 스택 맨 위의 요소를 삭제하고 반환한다.
트랜잭션의 인풋을 통해 스크립트의 스택 초기 값을 설정할 수 있다.
HASH160(preimage0) = hash0, HASH160(preimage1) = hash1
증명자가 변수의 값을 0이라고 설정하기 위해 preimage0을 공개했다.

실행 과정

preimage0과 0을 순서대로 스택에 넣은 상태로 위의 스크립트를 실행한다.
OP_IF는 스택에서 pop하여 값이 0이면 ELSE, 그 외의 값이면 IF 블록을 실행한다. 여기서는 0이므로 ELSE 블록인 7번 줄로 점프한다.
OP_HASH160는 스택에서 pop하고 이 값을 해시하여 스택에 push한다.

4. <hash0>는 이 값을 그대로 스택에 push한다.

5. OP_EQUALVERIFY는 두번 pop하여 스택의 최상단 두 값이 같으면 계속 진행하고, 다르다면 스크립트가 바로 실패한다. 여기서는 두 값이 같으므로 진행한다.

6. <0>는 이 값을 그대로 스택에 push한다.

결과적으로, 공개한 프리이미지에 따라 스크립트의 실행 결과가 0 또는 1로 설정된다는 것을 알 수 있다. 증명자가 공개한 프리이미지는 preimage0이기 때문에, 해당 스크립트는 항상 0을 결과로 갖게 된다.

여기까지 비트 커밋먼트를 통해 변수에 값을 할당하는 방법을 알아보았다. 다음 파트에서는 이를 확장하여 어떻게 계산을 검증할 수 있는지 살펴보겠다.

4.2. Logic Gate Commitment

모든 계산 가능한 함수는 논리 회로로 나타낼 수 있으며, 논리 회로는 논리 게이트들의 집합으로 이루어진다. 그중에서도 특히 NAND 게이트는 단 하나만으로도 모든 논리 게이트를 구성할 수 있기 때문에 범용 게이트(Universal Gate)라 불린다. 이는 NAND 게이트 하나만으로도 모든 계산 가능한 함수를 표현할 수 있다는 의미이다.

Source: https://www.gsnetwork.com/nand-gate/

비트코인 스크립트에서는 NAND 연산을 OP_BOOLAND와 OP_NOT이라는 명령어(opcodes)의 조합으로 쉽게 구현할 수 있다. 이를 편의상 OP_NAND라고 부르겠다. 그리고 앞에서 설명한 비트 커밋먼트를 조합하여 NAND 게이트를 만들어낼 수 있다.

이를 통해 비트코인 스크립트에서 복잡한 계산을 어떻게 수행할 수 있는지 아래에서 자세히 살펴보자.

스크립트 설명

A NAND B = C 를 구현하는 스크립트
입력: A, B, C에 대한 변수 값들과 대응하는 프리이미지 값들.
A NAND B = C 가 올바르면 실행, 올바르지 않으면 실패.

<예시>

전제

입력: A = 0, B = 1, C = 1
결과: 0 NAND 1 = 1 이므로 올바르게 실행된다.
A = 0에 대한 프리이미지와 해시값: preimageA0, hashA0
OP_BITCOMMITMENT(X)는 X에 대한 비트 커밋먼트 스크립트를 줄여쓴 것. (실제 opcode 아님)
비트코인 스크립트에는 기본 스택 말고도 복잡한 연산을 위한 알트(Alternative) 스택이라는 추가적인 스택 구조가 존재.

실행 과정

스택의 초기 값은 순서대로 preimageA0, 0, preimageB1, 1, preimageC1, 1
OP_BITCOMMITMENT(C)를 실행
OP_TOALTSTACK을 실행하면 스택에서 pop하여 알트 스택에 push한다.

4. 마찬가지로 4, 5번 줄을 실행하면 B의 값도 알트 스택에 저장된다.

5. OP_BITCOMMITMENT(A)

6. OP_FROMALTSTACK을 실행하면 알트 스택에서 pop해서 스택에 push한다.

7. OP_BOOLAND를 하면 1과 0을 AND 연산하여 0이 되고, OP_NOT을 하면 다시 0이 1이 된다.

8. OP_FROMALTSTACK

9. 마지막으로 OP_EQUALVERIFY를 통해 스택의 두 값이 같음을 검증한다. 만약 다르다면 스크립트는 곧바로 실패하게 된다.

여기까지 비트 커밋먼트를 통해 NAND 게이트의 입력과 출력을 설정하고, 이를 비트코인 스크립트로 올바른 계산인지 검증하는 방법을 살펴보았다. NAND 게이트를 조합하면 어떠한 계산 가능한 함수도 구현이 가능하므로, 비트코인에서 모든 계산 가능한 함수를 검증할 수 있게 되었다.

비트코인 스크립트를 사용하여 NAND 게이트를 구성하는 방법을 이해했으니, 이제 NAND 게이트들이 어떻게 조합되어 더 복잡한 논리 회로와 계산을 구현할 수 있는지 살펴보자. 다음 파트에서는 이러한 NAND 게이트들의 조합 과정을 구체적으로 다루어, 비트코인 스크립트에서 복잡한 함수들을 검증하는 방법을 자세히 알아보겠다.

4.3. Binary Circuit Commitment

모든 계산 가능한 함수는 논리 회로로 나타낼 수 있다. 논리 회로는 논리 게이트들의 집합으로 구성되며, NAND 게이트는 모든 논리 게이트를 구현할 수 있는 범용 게이트(Universal Gate)이다. 따라서 모든 계산 가능한 함수는 NAND 게이트의 조합으로 나타낼 수 있다. 아래 그림은 NAND 게이트들을 조합하여 모든 계산 가능한 함수를 구현하는 예를 보여준다.

논리 회로는 비트코인 상에서 하나의 탭루트로 표현된다. 논리 회로를 구성하는 모든 NAND 게이트는 각각 하나의 리프 스크립트가 되어, 전체 탭루트가 하나의 거대한 논리 회로가 된다.

결과적으로, 하나의 탭루트는 검증하려는 하나의 함수를 나타낸다. 탭루트는 온체인 상에 담기는 데이터 양이 매우 적기 때문에, 수십억 개의 NAND 게이트를 합쳐서 복잡한 함수를 나타낼 수 있다.

탭루트는 증명자가 검증받으려는 함수를 나타내며, 증명자가 검증자에게 제공하는 프리이미지들이 함수의 입력과 출력이 된다. 따라서 증명자는 함수를 먼저 탭루트에 커밋하고, 입력과 출력은 셋업 과정 이후에 설정할 수 있다. 다만, 한 번 사용한 탭루트는 재사용할 수 없다. 이는 변수들에 대해 이미 프리이미지를 한 개씩 공개했기 때문이다. 프리이미지를 공개하는 순간 변수의 값은 해당 프리이미지에 대응하는 값으로 고정되므로, 변수의 값을 새롭게 설정할 수 없다. 따라서 동일한 함수라도 입력과 출력을 다르게 하려면, 새로운 해시값들을 생성하여 새로운 탭루트에 커밋해야 한다.

여기까지 비트코인 상에서 계산이 검증되는 방식을 살펴보았다. 다음 파트에서는 증명자가 주장하는 계산이 틀리거나 부정 행위를 했을 경우, 검증자가 이를 처벌하는 메커니즘인 챌린지-리스폰스 프로토콜에 대해 알아보겠다.

5. Challenge-Response Protocol

앞에서 만든 탭루트의 스크립트들을 전부 실행하면 비트코인 상에서 계산을 완벽히 검증할 수 있다. 하지만 복잡한 프로그램에는 수억 개의 NAND 게이트가 포함될 수 있으므로, 이를 온체인에서 실제로 실행하는 것은 비현실적이다. 이러한 문제를 해결하기 위해 BitVM은 오프체인에서 계산을 수행하고, 올바르지 않은 부분만 온체인에서 검증하여 처벌하는 메커니즘을 구현한다.

오프체인 계산은 다음과 같은 두 단계를 반복하며 진행된다:

증명자는 검증자에게 비트 커밋먼트에 대한 프리이미지들을 공개한다.
검증자는 오프체인에서 증명자가 주장하는 계산을 직접 검증한다.

만약 모든 계산이 정확하다면, 검증자는 아무런 행동도 하지 않는다. 그러나, 아래와 같은 분쟁 상황이 발생할 수 있다:

증명자가 올바르지 않은 계산을 주장하는 경우
증명자가 동일한 비트에 대해 0과 1을 동시에 주장하는 경우(Equivocation)
증명자가 오프체인에서 비트 커밋먼트에 대한 프리이미지를 공개하지 않는 경우

이러한 경우, 검증자는 온체인에서 챌린지-리스폰스 프로토콜을 시작하여 증명자의 예치금을 빼앗을 수 있다. 이를 위해 증명자와 검증자는 사전에 서명된 트랜잭션들을 미리 교환한다. 이 사전 서명된 트랜잭션들은 비트코인 네트워크에 즉시 제출되지 않고, 분쟁 상황이 발생했을 때 제출되어 챌린지-리스폰스 프로토콜을 시작하는 데 사용된다.

이 트랜잭션들은 HTLC 방식으로 구성되어 있으며, 타임락 스크립트를 포함하고 상대방의 개인키로 서명되어 있다. 따라서 제출된 후 상대방이 일정 시간 내에 이 스크립트를 해제하지 않으면 예치금을 잃게 된다. 이러한 방식으로 상대의 행동을 강제하거나 처벌할 수 있다. 더 자세한 작동 방식은 5.1에서 설명하도록 하겠다.

검증자는 한 명이 아니라 여러 명이 될 수 있다. 검증자의 수가 늘어날수록 사전 준비 비용은 증가하지만, 사기 증명 특성상 검증자 중 한 명만 정직해도 보안이 유지되는 1-of-n 보안 가정(Honesty Assumption)이 적용되므로, 검증자의 수가 많을수록 보안은 강화된다.

이제 각 상황 별로 어떻게 분쟁이 해결될 수 있는지 살펴보도록 하겠다.

5.1. Wrong Computation

증명자가 잘못된 계산을 주장한 경우이다.

위와 같이 증명자가 NAND7에 대해 잘못된 주장을 한 경우, 검증자는 해당 NAND 게이트에 대한 챌린지를 시작한다.

검증자는 증명자의 예치금이 포함된 사전 서명된 트랜잭션을 이용하여 챌린지 탭루트의 특정 해시락을 해제한다. 그러면 이에 대응되는 리스폰스 탭스크립트가 활성화된다. 이 HTLC 스크립트의 해제 조건은 NAND 게이트 커밋먼트의 해제 또는 타임락 해제이다. 타임락은 일정 시간이 지난 후 검증자가 증명자의 예치금을 가져갈 수 있도록 한다. 따라서 증명자는 자신의 예치금을 검증자에게 빼앗기지 않기 위해 NAND 게이트를 해제해야 한다. 하지만 틀린 계산이었다면 증명자는 NAND 게이트를 해제할 수 없으며, 시간이 지나 타임락 조건이 만족되면 검증자가 증명자의 예치금을 가져가게 된다.

예를 들어, 위의 그림과 같이, J AND A = L이라는 NAND 게이트에서 증명자가 J = 0, A = 1, L = 1이라고 주장한 상황을 보자. 0 NAND 1 = 0이므로 NAND 게이트 스크립트에 J = 0, A = 1, L = 1에 대한 프리이미지 값들을 넣어도 스크립트가 해제되지 않는다. 그러면 시간이 지나 타임락 조건이 만족되면 검증자가 이 예치금을 가져가게 되어 증명자의 틀린 계산에 대한 처벌이 완료된다.

여기까지 잘못된 계산에 대한 분쟁 해결 과정을 살펴보았다. 다음으로는 동일한 비트에 대해 두가지 상반된 주장을 하는 경우인 Equivocation의 상황에 대해 알아보도록 하겠다.

5.2. Equivocation

증명자는 사실 앞서 설명한 틀린 계산의 상황에서 스크립트를 해제할 수 있다. 증명자는 모든 변수에 대한 프리이미지 값들을 알고 있으므로, 이전에 주장한 L = 1을 번복하여 L = 0에 대한 프리이미지를 입력하면 NAND 게이트가 해제되고 예치금을 회수할 수 있다. 이 경우는 증명자의 사기 행위인 Equivocation이라고 부르며, 이를 처벌하기 위한 방법도 마련되어 있다.

이 상황에서도 검증자는 증명자의 개인키로 사전 서명된 트랜잭션을 통해 증명자의 비트코인을 포함한 트랜잭션을 생성할 수 있다. 이 트랜잭션의 잠금 스크립트는 HTLC 스크립트로, 아래의 해시락 스크립트(equivocation.bs)와 타임락 스크립트가 결합되어 있다. 이 타임락은 일정 시간이 지나면 증명자가 자금을 회수할 수 있도록 하여, Equivocation이 아닌 상황에서 증명자가 자금을 회수할 수 있게 한다.

이 스크립트는 A에 대한 Equivocation을 처벌할 수 있는 스크립트이다. 이 스크립트는 한 변수에 대한 두 프리이미지를 입력으로 제공하면 잠금 해제된다. 앞서 증명자가 A = 0과 A = 1이라고 주장하는 과정에서 A에 대한 두 프리이미지를 모두 공개했으므로, 검증자는 이를 통해 자연스럽게 스크립트를 해제할 수 있다. 이 스크립트를 해제하면, 검증자는 증명자의 예치금을 가져가게 되므로, 증명자의 Equivocation을 처벌하게 된다.

5.3. Dishonest Off-chain Interaction

증명자는 특정 변수에 대한 프리이미지를 공개하지 않거나 올바르지 않은 값을 제공할 수 있다. 이러한 경우, 증명자가 온체인에서 올바른 값을 공개하도록 강제할 필요가 있다. 이를 위해 타임락 스크립트와 해시락 스크립트를 결합한 HTLC 스크립트를 사용할 수 있다. 이 HTLC 스크립트는 증명자가 올바른 프리이미지를 제공하지 않으면 일정 시간이 지난 후 검증자가 타임락을 해제하여 예치금을 가져갈 수 있도록 한다. 따라서 증명자는 해시락을 해제하여 올바른 값을 공개하도록 강제된다.

이 스크립트는 앞서 설명한 HTLC 스크립트의 해시락을 구현한 것이다. 이 스크립트를 해제하기 위해서는 변수 A에 대한 프리이미지 중 하나를 제공해야 한다. 즉, 이 스크립트를 통해 검증자가 증명자에게 온체인에서 A에 대한 값을 설정하도록 강제할 수 있게 되었다.

6. Future of BitVM

6.1. Limitations

앞에서 설명한 BitVM에는 세 가지 큰 문제점이 있다.

첫 번째는 제한된 검증자이다. 이 모델에서는 미리 트랜잭션에 사전 서명한 증명자와 검증자만이 참여할 수 있는 두 주체 상호작용(Two Party Interaction)으로 제한되어 있다. BitVM의 보안은 검증자가 얼마나 잘 사기증명을 할 수 있는가가 가장 중요하기 때문에, 누구나 검증자로 참여할 수 있는 무허가 검증 시스템이 필요하다.

두 번째는 챌린지-리스폰스 프로토콜이 매우 오래 걸린다는 것이다. 증명자가 계산의 오류를 알아차리고 오프체인 상호작용을 중단한 경우, 검증자가 챌린지를 걸어 오류를 찾아내야 한다. 증명자가 최대한 천천히 챌린지에 응답하는 경우, 이는 매우 긴 시간과 여러 번의 온체인 상호작용을 필요로 한다. 이진 탐색(Binary Search)을 통해 이를 찾아내는 경우, 전체 NAND 게이트의 개수를 n이라 한다면 대부분의 경우 시간 복잡도(Amortized Time Complexity)는 log(n)이 될 것이다. 만약 게이트가 100만 개라면 약 20번, 게이트가 10억 개라면 약 30번 정도의 온체인 상호작용이 필요하다. 이는 비트코인에서 순차적으로 실행되어야 하므로 최소 3~5시간, 응답 사이의 지연 시간에 따라 실제로는 그보다 훨씬 오래 걸릴 수 있음을 의미한다.

마지막으로 매우 비효율적이라는 점이다. BitVM의 초기 디자인은 효율성을 고려하지 않은 PoC(Proof of Concept) 디자인이다. 복잡한 계산을 전부 NAND 게이트로 변환하는 것은 매우 비효율적이며, 계산의 무결성을 검증하는 방법에는 영지식 증명을 사용하는 SNARK나 STARK의 방식과 같이 효율적인 방식이 존재한다.

6.2. BitVM 2

Robin Linus는 2024년 3월에 BitVM의 업그레이드 버전인 BitVM 2의 설계를 공개하여 위의 두 문제를 해결하였다. 현재 BitVM 2는 기존의 BitVM을 대체하여 정식 디자인으로 채택되어 개발되고 있다. BitVM 2는 다음과 같은 방법으로 언급된 문제점들을 해결한다.

첫 번째로, 한 번의 1-of-n 보안 가정의 셋업 과정만 거치면, 이 과정에 참여하지 않았더라도 누구나 검증자로 역할을 할 수 있다. 이는 프로토콜의 탈중앙성과 보안을 크게 향상시킨다.

두 번째로, NAND 게이트로 이루어진 회로로 계산을 나타내는 대신 범용적인 SNARK 영지식 증명 검증기를 구현한다. 이는 어떤 계산을 직접 수행하는 대신 영지식 증명을 검증하는 방식이다. 이를 통해 복잡한 계산을 효율적으로 처리할 수 있으며, 탭루트의 각 리프 스크립트는 NAND 게이트 대신 ZKP 검증기의 하위 함수들로 대체되어 더 효율적이고 확장 가능한 방식을 제공한다.

세 번째로, 챌린지-리스폰스 과정도 최대 두 라운드로 줄어들어 매우 간소화된다. 이는 사용자 경험을 개선하며, 전체 시스템의 효율성을 높인다.

7. Final Thoughts

비트코인은 1조 달러가 넘는 시가총액을 자랑하지만, UTXO 모델과 비트코인 스크립트의 한계로 인해 생태계는 매우 제한적이며, 대부분의 비트코인은 수동적으로 존재한다. BitVM은 이러한 한계를 극복하고 비트코인 위에 진정한 레이어 2 솔루션을 구현할 수 있는 혁신적인 기술로 주목받고 있다.

BitVM을 통해 비트코인 생태계는 레이어 2 솔루션을 기반으로 디파이(DeFi), 무허가 브릿지(Permissionless Bridge) 등 다양한 활용 사례를 통해 더욱 확장될 수 있다. 이는 비트코인의 기능을 크게 향상시키고, 더 많은 사용자와 개발자가 비트코인 플랫폼에 참여하게 만들 것이다.

또한, 비트코인 스크립트의 한계를 확장시키는 또 다른 가능성인 OP_CAT에도 주목할 필요가 있다. OP_CAT은 초기 비트코인 명령어 중 하나였으나, DoS 공격에 악용될 수 있다는 우려로 제거되었다. 현재는 최대 스택 요소 크기에 제한을 두어 이러한 위험이 줄었고, 비트코인 스크립트의 표현력을 크게 향상시킬 수 있다는 점에서 BIP-420이라는 제안으로 재도입이 논의되고 있다. OP_CAT은 스택의 두 문자열을 합치는 간단한 명령어이지만, BitVM과 마찬가지로 비트코인의 컨트랙트 기능을 크게 확장할 잠재력을 가지고 있다.

특히 StarkWare가 최근 OP_CAT을 활용하여 스타크넷을 비트코인 레이어 2로 활용하겠다고 발표하며 큰 관심을 끌고 있다. OP_CAT을 사용하면 STARK 영지식 검증기를 매우 효율적으로 구현할 수 있고, 무신뢰 브릿지도 만들 수 있어 레이어 2를 효율적이고 안전하게 만들 수 있다. 더 자세한 내용은 이 링크를 참고하기 바란다.

현재 OP_CAT의 도입이 활발히 논의되고 있지만, 도입되지 않을 가능성도 충분히 존재한다. 그럴 경우 비트코인에서 레이어 2 솔루션을 구현할 유일한 방법은 BitVM일 것이다. BitVM은 비트코인에서 엄청난 패러다임의 변화를 일으킬 수 있는 기술이며, 앞으로의 발전과 쓰임새가 기대된다. BitVM을 통해 비트코인이 가진 잠재력이 최대한 발휘될 수 있기를 바란다.