비트코인 레이어2 확장 기술 분석: 유효성 증명과 사기 증명
작성: mutourend & lynndell, Bitlayer Labs
1 서론
어떤 알고리즘 f에 대해 서로 신뢰하지 않는 두 참여자 앨리스(Alice)와 밥(Bob)은 다음과 같은 방법으로 신뢰를 구축할 수 있다.
-
앨리스가 입력 x를 넣고 알고리즘 f를 실행하여 결과 y를 얻는다. 밥 또한 동일한 입력 x를 기반으로 알고리즘 f를 실행하고 결과 y′을 얻는다. 만약 y = y′이라면, 밥은 앨리스가 제공한 입력 x와 출력 y를 인정한다. 이는 특수한 형태의 유효성 증명 메커니즘으로, 블록체인 합의에서 자주 사용된다. 여기서 앨리스는 블록을 패키징하는 노드이며, 밥은 합의에 참여하는 노드이다.
-
앨리스가 입력 x를 넣고 알고리즘 f에 대해 zk.prove 프로그램을 실행하여 결과 y와 증명 proof를 얻는다. 밥은 f, y, proof를 기반으로 zk.verify 프로그램을 실행한다. 결과가 true이면 밥은 앨리스의 결과 y를 인정하고, false이면 인정하지 않는다. 이것이 바로 유효성 증명이다. 여기서 밥은 체인 상의 스마트 계약일 수 있다.
-
앨리스가 입력 x를 넣고 알고리즘 f를 실행하여 결과 y를 얻는다. 밥 또한 동일한 입력 x를 기반으로 알고리즘 f를 실행하고 결과 y′을 얻는다. 만약 y = y′이라면 아무 조치도 취하지 않으며, y ≠ y′일 경우 밥은 앨리스에게 도전(challenge)을 발동하고, 도전 대상 프로그램은 f가 된다. 앨리스와 밥 사이의 상호작용 횟수는 한 번 또는 여러 번일 수 있으며, 도전-응답 절차를 통해 중재를 실현한다. 이를 사기 증명(Fraud Proof)이라고 한다. 여기서 밥은 도전자로서 오프체인에서 모니터링하고 온체인에서 도전을 발동한다.
-
앨리스가 입력 x를 넣고 알고리즘 f에 대해 zk.prove 프로그램을 실행하여 결과 y와 증명 proof를 얻는다. 밥은 f, y, proof를 기반으로 zk.verify 프로그램을 실행한다. 결과가 true이면 아무 조치도 취하지 않고, false이면 밥은 앨리스에게 도전을 발동하며, 도전 대상 프로그램은 zk.verify이다. 앨리스와 밥 사이의 상호작용 횟수는 한 번 또는 여러 번일 수 있다. 도전-응답 절차를 통해 중재를 실현한다. 이것 역시 사기 증명이다. 밥은 도전자로서 오프체인에서 모니터링하고 온체인에서 도전을 발동한다.
위 2,3,4번 항목에서 x를 L2 트랜잭션과 초기 상태로, f를 L2 합의 프로그램으로, y를 트랜잭션 종료 상태로 설정하면, 이는 블록체인 L2 확장 솔루션에 해당한다. 즉:
-
유효성 증명(Validity Proof): 비관적 가정을 기반으로 하며, 유효하다는 것이 입증된 후에만 수용되며 즉시 효력이 발생한다. 유효성 증명에서는 L2 상태 전환이 올바르다는 증거를 제공해야 하며, 이는 세상에 대한 비관적인 관점을 반영한다—즉, 어떤 상태가 올바르다고 입증될 때만 그 상태를 수용한다.
-
사기 증명(Fraud Proof): 낙관적 가정을 기반으로 하며, 기본적으로 수용되며 오류가 있음을 누군가 입증할 경우에만 거부된다. 일정한 도전 창(window) 기간이 존재하며, 이 기간이 지나야만 효력이 발생한다. 사기 증명에서는 L2 상태 전환이 잘못되었다는 증거를 제공해야 하며, 이는 세상에 대한 낙관적인 관점을 반영한다—즉, 상태 전환은 기본적으로 올바르다고 간주되며, 오직 틀렸다는 것이 입증될 경우에만 거부된다.
표 1: 신뢰 구축 방식
또한 다음 사항을 유념해야 한다.
-
사기 증명과 유효성 증명을 구분하는 핵심은 SNARK/STARK 등의 ZK 증명 시스템을 사용했는지 여부가 아니다. ZK 증명 시스템은 사용된 증명 방식을 나타내는 것이며, 사기 증명인지 유효성 증명인지 여부는 증명의 내용을 의미한다. 그래서 표 1의 시나리오 1이 유효성 증명임을 설명할 수 있다.
-
유효성 증명은 실시간성이 우수하나 체인 상 검증 복잡도가 비교적 높다. 반면 사기 증명은 체인 상 검증 복잡도가 낮으나 실시간성이 다소 떨어진다.
-
표 1의 2번 및 4번 경우, ZK 재귀 및 조합 기술을 활용하여 여러 f의 계산을 압축함으로써 오프체인 계산의 온체인 검증 비용을 크게 분산·감소시킬 수 있다.
현재 솔리디티(Solidity)의 튜링 완전 스마트 계약 덕분에 사기 증명과 유효성 증명 기술은 이더리움 L2 확장에 널리 사용되고 있다. 그러나 비트코인 패러다임 하에서는 비트코인의 제한된 오퍼코드 기능, 1000개 스택 요소 등의 제약으로 인해 이러한 기술의 적용은 여전히 탐색 단계에 머물러 있다. 본고는 비트코인 L2 확장 시나리오를 중심으로 비트코인 패러다임의 제약과 돌파 기술을 정리하고, 유효성 증명과 사기 증명 기술을 연구하며, 비트코인 패러다임에서 독자적으로 발전한 스크립트 분할 기술을 정리한다.
2 비트코인 패러다임 하의 제약과 돌파
비트코인 패러다임 하에는 많은 제약이 있으나, 다양한 영리한 방법이나 기술을 통해 이를 극복할 수 있다. 예를 들어, 비트 커밋먼트(bit commitment)는 UTXO의 무상태성 제약을 극복하고, 탭루트(taproot)는 스크립트 공간 제약을 극복하며, 커넥터 아웃풋(connector output)은 UTXO 소비 방식의 제약을 극복하고, 계약(covenant)은 사전 서명(presign) 제약을 극복할 수 있다.
2.1 UTXO 모델과 스크립트 제약
비트코인은 UTXO 모델을 채택하며, 각 UTXO는 locking 스크립트에 잠겨 있고, 이 스크립트는 해당 UTXO를 소비하기 위해 충족되어야 하는 조건을 정의한다. 비트코인 스크립트는 다음과 같은 제약을 갖는다.
-
비트코인 스크립트는 무상태(stateless)이다.
-
P2TR 출력 유형의 경우, 단일 트랜잭션에 포함될 수 있는 오퍼코드 수는 최대 약 400만 개로, 전체 블록을 채울 수 있으며, 다른 출력 유형의 경우는 1만 개에 불과하다.
-
단일 UTXO의 소비 방식이 제한적이며, 조합적 소비 방식에 대한 탐색이 부족하다.
-
유연한 계약 기능을 지원하지 않는다.
-
스택 크기는 최대 1000개 요소(altstack + stack)로 제한되며, 개별 요소의 최대 크기는 520바이트이다.
-
산술 연산(덧셈, 뺄셈 등)은 4바이트 요소에만 국한된다. 20바이트 이상의 장요소로 수정할 수 없으며, 이는 암호학 연산에 필수적이다.
-
OP_MUL 및 OP_CAT 등의 오퍼코드는 모두 금지되어 있으며, 기존 오퍼코드로 시뮬레이션할 경우 비용이 매우 높다. 예를 들어 one-round BLAKE3 해시를 시뮬레이션할 경우 script size는 약 75KB에 달한다.
2.2 비트 커밋먼트: UTXO 무상태성 제약 극복
현재 비트코인 스크립트는 완전히 무상태이다. 비트코인 스크립트를 실행할 때마다 실행 환경은 각 스크립트 이후 리셋된다. 따라서 스크립트 1과 스크립트 2가 동일한 x 값을 가지도록 제약하는 것은 원천적으로 불가능하다. 그러나 이를 우회하는 방법이 있는데, 핵심 아이디어는 어떤 값을 서명하는 방식을 통해 구현하는 것이다. 값에 서명할 수 있다면 상태가 있는 비트코인 스크립트를 구현할 수 있다. 즉, 스크립트 1과 스크립트 2에서 x 값의 서명을 검증함으로써 두 스크립트에서 동일한 x 값을 사용하도록 강제할 수 있다. 동일한 변수 x에 대해 서로 다른 값 2개를 서명하는 충돌 서명이 발생할 경우 이를 처벌할 수 있다. 이러한 해결책을 비트 커밋먼트(bit commitment)라고 한다.
비트 커밋먼트의 원리는 비교적 간단하다.所谓 bit란 서명할 메시지의 각 비트에 대해 2개의 서로 다른 해시값(hash0과 hash1)을 설정하는 것이다. 서명할 비트 값이 0이면 hash0의 원상(preimage0)을 공개하고, 1이면 hash1의 원상(preimage1)을 공개한다.
단일 비트 메시지 m ∈ {0,1}을 예로 들면, 해당하는 비트 커밋먼트 해제 스크립트는 단순히 몇 개의 원상일 뿐이다. 비트 값이 0이면 해당 해제 스크립트는 preimage0—"0xfa7fa5b1dea37d71a0b841967f6a3b119dbea140"; 비트 값이 1이면 해당 해제 스크립트는 preimage1—"0x47c31e611a3bd2f3a7a42207613046703fa27496"이다. 따라서 비트 커밋먼트를 통해 UTXO의 무상태성 제약을 극복하고 상태가 있는 비트코인 스크립트를 구현함으로써 다양한 새로운 기능을 가능하게 할 수 있다.
OP_HASH160
OP_DUP
<0xf592e757267b7f307324f1e78b34472f8b6f46f3> // This is hash1
OP_EQUAL
OP_DUP
OP_ROT
<0x100b9f19ebd537fdc371fa1367d7ccc802dc2524> // This is hash0
OP_EQUAL
OP_BOOLOR
OP_VERIFY
// Now the value of the bit commitment is on the stack. Either "0" or "1".
비트 커밋먼트는 현재 두 가지 구현 방식이 있다.
-
Lamport 일회용 서명: 원리가 비교적 간단하며 해시 함수만 필요하므로 비트코인 친화적이다. 메시지의 각 비트마다 2개의 해시값을 커밋해야 하므로 서명 데이터가 상대적으로 크다. 즉, v 비트 길이의 메시지의 경우 공개키 길이는 2v 비트, 서명 길이는 v 비트이다.
-
Winternitz 일회용 서명: Lamport 서명에 비해 서명 및 공개키 길이를 크게 줄일 수 있으나, 서명 및 검증 복잡도가 증가한다. 이 방안은 다양한 hash chain 길이 d 값을 유연하게 설정할 수 있어 길이와 복잡도 사이에서 균형을 맞출 수 있다. 예를 들어 d=15로 설정하면 공개키 및 서명 길이가 약 4배 짧아지지만 검증 복잡도는 4배 증가한다. 본질적으로 비트코인 스택 공간과 script size 사이의 트레이드오프이다. Lamport 서명은 Winternitz 서명에서 d=1인 특수한 경우로 볼 수 있다.
현재 BitVM2 라이브러리에서는 Blake3 해시 함수를 기반으로 Winternitz 서명을 구현하고 있으며, 단일 비트에 해당하는 서명 길이는 약 26바이트이다. 따라서 비트 커밋먼트를 통해 상태를 도입하는 것은 비용이 많이 든다는 것을 알 수 있다. 따라서 BitVM2 엔지니어링 구현에서는 먼저 메시지를 해시하여 256비트 해시값을 얻은 후, 이 해시값에 대해 비트 커밋먼트를 수행하여 비용을 절감하며, 원래 긴 메시지의 각 비트를 직접 커밋하지 않는다.
2.3 탭루트: 스크립트 공간 제약 극복
2021년 11월 활성화된 비트코인 탭루트 소프트포크 업그레이드에는 세 개의 제안이 포함된다: Schnorr 서명(BIP 340), 탭루트(BIP 341), 탭스크립트(BIP 342). 새로운 트랜잭션 유형인 Pay-to-Taproot(P2TR) 트랜잭션이 도입되었다. P2TR 트랜잭션은 탭루트, MAST(메릴크 추상 구문 트리), Schnorr 서명의 장점을 결합하여 더 익명성 있고 유연하며 확장 가능한 트랜잭션 형식을 만들 수 있다.
P2TR은 두 가지 소비 방식을 지원한다: key path 또는 script path를 통한 소비.
탭루트(BIP 341) 규정에 따르면, script path로 소비할 경우 해당 Merkle 경로의 최대 길이는 128을 초과할 수 없다. 즉 taptree 내 tapleaf 수는 2^128개를 초과하지 않는다. 2017년 segwit 업그레이드 이후 비트코인 네트워크는 weight units로 블록 크기를 측정하며, 최대 400만 weight units(약 4MB)를 지원한다. P2TR output이 script path를 통해 소비될 경우 실제로는 단일 tapleaf 스크립트만 공개되면 되므로, 블록에 패키징되는 것은 단일 tapleaf 스크립트이다. 이는 P2TR 트랜잭션의 각 tapleaf 스크립트 크기가 최대 약 4MB라는 의미이다. 다만 비트코인의 기본 전략상 많은 노드들이 400KB 미만의 트랜잭션만 전달하며, 더 큰 트랜잭션은 채굴자와 협력해야 채굴될 수 있다.
탭루트가 가져온 스크립트 공간 프리미엄은 기존 opcode를 이용해 곱셈, 해시 등의 암호학 연산을 시뮬레이션하는 것을 더욱 가치 있게 만든다.
P2TR 기반으로 검증 가능한 컴퓨팅을 구축할 때, script size는 더 이상 4MB 제한에 묶이지 않고, 해당 계산을 여러 개의 하위 함수로 나누어 각각의 tapleaf에 분산시킴으로써 4MB 스크립트 공간 제약을 극복할 수 있다. 실제로 현재 BitVM2에서 구현된 Groth16 verifier 알고리즘의 크기는 무려 2GB에 달한다. 그러나 이를 약 1000개의 tapleaf로 분할하고 비트 커밋먼트와 결합하여 각 하위 함수의 입력-출력 간 일관성을 제약함으로써 전체 계산의 완전성과 정확성을 보장할 수 있다.
2.4 커넥터 아웃풋: UTXO 소비 방식 제약 극복
비트코인이 현재 제공하는 단일 UTXO의 원시 소비 방식은 스크립트를 통한 소비 또는 공개키를 통한 소비이다. 따라서 올바른 공개키 서명을 제공하거나 스크립트 조건을 만족하면 해당 UTXO를 소비할 수 있다. 두 개의 UTXO는 독립적으로 소비될 수 있으며, 두 UTXO에 추가적인 조건을 걸어 동시에 특정 조건을 만족해야만 소비되도록 제약할 수 없다.
그러나 Ark 프로토콜의 창시자 Burak은 SIGHASH 플래그를 영리하게 활용하여 커넥터 아웃풋(connector output)을 구현했다. 구체적으로, 앨리스는 자신의 BTC를 밥에게 보내는 서명을 생성할 수 있다. 그러나 서명은 여러 Inputs를 commit할 수 있으므로, 앨리스는 자신의 서명이 조건부로 유효하도록 설정할 수 있다: Take_tx 트랜잭션에 대해 서명이 유효하려면 반드시 두 번째 input을 소모해야 한다. 이 두 번째 input을 커넥터라 하며, UTXO A와 UTXO B를 연결한다. 즉, Take_tx 트랜잭션이 유효하려면 UTXO B가 Challenge_tx에 의해 소비되지 않아야 한다. 따라서 커넥터 아웃풋을 폐기함으로써 Take_tx 트랜잭션의 효력을 차단할 수 있다.
그림 1: 커넥터 아웃풋 개념도
BitVM2 프로토콜에서 커넥터 아웃풋은 if...else 기능을 수행한다. 한번 커넥터 아웃풋이 어떤 트랜잭션에 의해 소비되면 다른 트랜잭션에서는 소비할 수 없어 독점적 소비가 보장된다. 실제 배포 시 도전-응답 주기를 확보하기 위해 timelock이 적용된 UTXO를 추가로 도입한다. 또한 필요한 경우 해당 커넥터 아웃풋에 다른 소비 전략을 설정할 수 있다. 예를 들어 도전 트랜잭션은 누구나 소비할 수 있도록 하고, 응답 트랜잭션은 운영자(operator)만 소비하거나 일정 시간 초과 후 누구나 소비할 수 있도록 설정할 수 있다.
2.5 계약: 사전 서명 제약 극복
현재 비트코인 스크립트는 주로 해제 조건을 제한할 뿐, 해당 UTXO가 어떻게 추가로 소비되는지는 제한하지 않는다. 그 이유는 비트코인 스크립트가 트랜잭션 자체의 내용을 읽을 수 없기 때문이다. 즉, 트랜잭션 자성(transaction introspection)이 불가능하다. 비트코인 스크립트가 트랜잭션의 모든 내용(output 포함)을 검사할 수 있다면 계약 기능을 구현할 수 있다.
현재 계약 구현 방식은 두 가지로 나뉜다.
-
사전 서명(presign): 기존 비트코인 스크립트 능력을 기반으로 제한된 기능을 갖는 사전 결정된 계약을 구축한다. 즉, 모든 가능한 미래 트랜잭션을 미리 설계하고 서명하여 참여자를 특정 개인키와 수수료율에 묶어둔다. 일부 방안은 참여자가 모든 사전 서명 트랜잭션을 위한 단기 개인키를 생성하도록 요구하기까지 한다. 사전 서명이 완료되면 이러한 단기 개인키를 안전하게 삭제하여 공격자가 키를 획득해 자금을 훔쳐갈 수 없도록 한다. 그러나 매번 새로운 참여자가 추가되거나 작업을 업데이트할 때마다 위 과정을 반복해야 하므로 유지 관리 비용이 높다. 예를 들어 라이트닝 네트워크는 사전 서명을 통해 2자 계약을 구현하고 해시 타임락(HTLC) 기술을 활용해 여러 2자 계약의 라우팅 기능을 실현함으로써 신뢰 최소화 확장 전략을 달성했다. 그러나 라이트닝 네트워크는 여러 트랜잭션을 사전 서명해야 하며, 2자에 국한되어 다소 무겁다. BitVM1에서는 매 초기화 시 수백 건의 트랜잭션을 사전 서명해야 했으며, 최적화된 BitVM2에서도 매 초기화 시 수십 건의 트랜잭션을 사전 서명해야 한다. BitVM1이나 BitVM2 모두 사전 서명에 참여한 operator만 보상을 받을 수 있다. n명의 참여자가 사전 서명에 참여하고 각 참여자가 m건의 트랜잭션을 사전 서명한다면, 각 참여자의 사전 서명 복잡도는 n × m이 된다.
-
계약 오퍼코드 도입: 새로운 계약 기능 오퍼코드를 도입하면 계약 참여자 간 통신 복잡도와 유지 관리 비용을 크게 줄여 비트코인에 더 유연한 계약 구현 방식을 도입할 수 있다. 예를 들어 OP_CAT: 바이트 문자열을 연결하는 데 사용된다. 기능은 매우 간단하지만 매우 강력하여 BitVM의 복잡도를 크게 낮출 수 있다. OP_TXHASH: 계약 내 행동을 더 세밀하게 제어할 수 있다. BitVM에 사용하면 더 큰 operator 집합을 지원할 수 있어 BitVM의 보안 가정을 크게 개선하고 신뢰를 최소화할 수 있다. 또한 사전 서명 방식은 BitVM 설계상 operator가 항상 선지급 후 보상을 받는 방식을 채택할 수밖에 없어 자금 활용 효율이 낮다. 반면 새로운 계약 오퍼코드를 통해 peg-in 자금 풀에서 직접 출금 사용자에게 지불하는 것이 가능해져 자금 효율을 더욱 높일 수 있다. 따라서 유연한 계약 모델은 기존 사전 서명 제약을 효과적으로 극복할 수 있다.
3 비트코인 L2 확장: 유효성 증명과 사기 증명
유효성 증명과 사기 증명 모두 비트코인 L2 확장에 사용될 수 있으며, 두 방식의 주요 차이는 표 2에 정리되어 있다.
표 2: 유효성 증명과 사기 증명
비트 커밋먼트, 탭루트, 사전 서명, 커넥터 아웃풋을 기반으로 비트코인 기반 사기 증명을 구축할 수 있다. 탭루트와 함께 OP_CAT과 같은 계약 오퍼코드를 도입하면 비트코인 기반 유효성 증명을 구축할 수 있다. 또한 밥(Bob)이 접근 제한(access control)을 갖는지 여부에 따라 사기 증명은 허가형(permissive) 사기 증명과 무허가형(non-permissive) 사기 증명으로 나뉜다. 허가형 사기 증명에서는 특정 그룹만 밥 역할을 수행해 도전을 발동할 수 있으며, 무허가형에서는 임의의 제3자가 밥 역할을 수행해 도전을 발동할 수 있다. 무허가형의 보안성이 더 우수하며, 허가 참여자들 간 공모 위험을 줄일 수 있다.
앨리스와 밥의 도전-응답 상호작용 횟수에 따라 사기 증명은 일회성(one-round) 사기 증명과 다회성(multi-round) 사기 증명으로 나뉘며, 그림 2에 나와 있다.
그림 2: 일회성 사기 증명과 다회성 사기 증명
표 3에 나와 있듯이, 사기 증명은 일회성 상호작용 모델과 다회성 상호작용 모델을 통해 구현될 수 있다.
표 3: 일회성 상호작용과 다회성 상호작용
비트코인 L2 확장 패러다임 하에서 BitVM1은 다회성 사기 증명 메커니즘을 사용하고, BitVM2는 일회성 사기 증명 메커니즘을 사용하며, bitcoincircle stark는 유효성 증명을 사용한다. 여기서 BitVM1과 BitVM2는 비트코인 프로토콜에 어떤 수정도 하지 않고도 구현 가능하지만, bitcoin-circle stark는 새로운 오퍼코드 OP_CAT의 도입이 필요하다.
대부분의 계산 작업은 비트코인 signet, testnet, mainnet 모두 4MB 스크립트로 완전히 표현할 수 없으므로 스크립트 Split 기술—즉, 전체 계산을 표현하는 스크립트를 4MB 미만의 청크로 분할하여 각 tapleaf에 분산시키는 기술—이 필요하다.
3.1 비트코인 상의 다회성 사기 증명
표 3에 나와 있듯이, 다회성 사기 증명은 체인 상 중재 계산량을 줄이고자 하거나 문제 계산 조각을 한 번에 찾을 수 없는 시나리오에 적합하다. 다회성 사기 증명은 말 그대로 증명자와 검증자 간 다수의 상호작용을 통해 문제 계산 조각을 찾아낸 후, 그 위치를 기반으로 중재를 진행하는 것이다.
Robin Linus의 초기 BitVM 백서(일반적으로 BitVM1이라 함)는 다회성 사기 증명을 사용한다. 각 라운드의 도전 기간을 1주로 가정하고 이분 탐색법을 사용하여 문제 계산 조각을 찾는다면, Groth16 Verifier의 체인 상 도전-응답 주기는 최대 30주에 달하며 실시간성이 매우 낮다. 현재 일부 팀들은 이분법보다 더 효율적인 n-ary 탐색법을 연구하고 있지만, 일회성 사기 증명의 2주 주기에 비하면 실시간성이 여전히 훨씬 낮다.
현재 비트코인 패러다임 하의 다회성 사기 증명은 모두 허가형 도전을 사용하지만, 일회성 사기 증명은 무허가형 도전 방식을 구현하여 참여자 간 공모 위험을 줄이고 보안성을 높였다. 이를 위해 Robin Linus는 탭루트의 장점을 최대한 활용하여 BitVM1을 최적화했다. 상호작용 횟수를 1회로 줄였을 뿐 아니라 도전 방식을 무허가형으로 확장했으나, 그 대가로 체인 상 중재 계산량이 증가했다.
3.2 비트코인 상의 일회성 사기 증명
증명자와 검증자 간 단 한 번의 상호작용으로 사기 증명의 검증을 완료하는 모델이다. 이 모델에서 검증자는 단 한 번의 도전만 발동하고, 증명자는 단 한 번의 응답만 하면 된다. 이 응답에서 증명자는 자신의 계산이 올바르다고 주장하는 증거를 제공해야 한다. 검증자가 이 증거에서 불일치를 발견하면 도전 성공, 그렇지 않으면 도전 실패이다. 일회성 상호작용 사기 증명의 특징은 표 3에 나와 있다.
그림 3: 일회성 사기 증명
Robin Linus는 2024년 8월 15일 발표한 'BitVM2: Bridging Bitcoin to Second Layers' 기술 백서에서 그림 3과 유사한 방식으로 일회성 사기 증명을 사용하여 BitVM2 크로스체인 브릿지를 구현했다.
3.3 비트코인 + OP_CAT을 통한 유효성 증명 구현
OP_CAT은 비트코인 최초 출시 당시 스크립트 언어의 일부였으나, 보안 취약성 문제로 2010년에 비활성화되었다. 그러나 수년간 비트코인 커뮤니티는 이를 다시 활성화하는 것을 논의해왔다. 현재 OP_CAT은 번호 347로 할당되었으며 비트코인 signet에서 이미 활성화되었다.
OP_CAT의 주요 기능은 스택의 두 요소를 결합하여 그 결과를 다시 스택에 푸시하는 것이다. 이 기능은 비트코인 상의 계약 및 STARK Verifier 구현을 열어준다.
-
계약: Andrew Poelstra는 CAT and Schnorr Tricks I에서 OP_CAT과 Schnorr 기술을 사용해 비트코인 상에 계약을 구현하는 방법을 제안했다. 여기서 Schnorr 알고리즘은 P2TR 출력 유형의 디지털 서명이며, 다른 출력 유형의 경우 유사한 ECDSA 기술을 사용할 수 있다(Covenants with CAT and ECDSA 참조). OP_CAT 계약을 활용하면 STARK Verifier 알고리즘을 여러 트랜잭션으로 분할하고 단계적으로 전체 STARK proof를 검증할 수 있다.
-
STARK Verifier: STARK Verifier는 본질적으로 데이터를 연결하고 해시하는 것이다. 대수 연산과 달리 해시 연산은 원시 비트코인 스크립트 연산이므로 많은 비용을 절약할 수 있다. OP_SHA256을 예로 들면, 원시 방식은 단 하나의 오퍼코드지만 시뮬레이션 방식은 수십만 개의 오퍼코드가 필요하다. STARK의 주요 해시 연산은 Merkle 경로 검증과 Fiat-Shamir 변환이다. 따라서 OP_CAT은 STARK Verifier 알고리즘에 매우 적합하다.
3.4 비트코인 스크립트 Split 기술
SNARK/STARK로 증명된 후, 해당 verifier 알고리즘을 실행해 proof를 검증하는 데 필요한 계산량은 원래 계산 f를 직접 실행하는 것보다 훨씬 적다. 그러나 이를 비트코인 스크립트로 구현할 경우 필요한 스크립트 양은 여전히 막대하다. 현재 기존 비트코인 오퍼코드를 기반으로 최적화된 Groth16 verifier 스크립트 크기와 Fflonk verifier 스크립트 크기는 모두 2GB를 초과한다. 그러나 비트코인 단일 블록 크기는 4MB에 불과하여 전체 verifier 스크립트를 단일 블록 내에서 실행할 수 없다. 그러나 탭루트 업그레이드 이후 비트코인은 tapleaf 단위로 스크립트를 실행할 수 있으므로 verifier 스크립트를 여러 청크로 분할하고 각 청크를 tapleaf로 하여 taptree를 구성할 수 있다. 각 청크 간에는 bit commitment를 통해 값의 일관성을 보장한다.
OP_CAT 계약이 있는 경우, STARK Verifier를 400KB 미만의 표준 트랜잭션 여러 개로 분할하여 채굴자와 협력하지 않고도 전체 STARK 유효성 증명 검증을 완료할 수 있다.
본 절에서는 새 오퍼코드를 도입하거나 활성화하지 않은 기존 상황에서 비트코인 스크립트 관련 Split 기술에 초점을 맞춘다.
스크립트를 분할할 때 다음 차원들을 균형 있게 고려해야 한다.
-
단일 청크 스크립트 크기는 4MB를 초과하지 않아야 하며, input bit commitment 스크립트, 트랜잭션 서명 등의 공간을 포함해야 한다.
-
단일 청크 스택 크기는 최대 1000을 초과하지 않아야 한다. 따라서 각 청크의 스택에는 필요한 요소만 남기고, script size 최적화를 위한 충분한 스택 공간을 확보해야 한다. 비트코인 트랜잭션 수수료는 사용된 스택 크기에 따라 달라지지 않기 때문이다.
-
비트코인 상의 bit commitment는 비용이 많이 든다. 현재 1비트당 26바이트이므로 인접한 두 청크 간 입력-출력 비트 수를 최소화해야 한다.
-
감사를 용이하게 하기 위해 각 청크의 기능은 가능한 명확해야 한다.
현재 스크립트 분할 방식은 주로 다음 세 가지로 나뉜다.
-
자동 분할: 스택 크기와 스크립트 크기를 기반으로 스크립트 크기가 약 3MB이고 스택 크기가 최소인 분할 방식을 찾는다. 장점은 특정 verifier 알고리즘에 의존하지 않아 임의의 계산에 대한 스크립트 분할로 확장 가능하다는 것이다. 단점은 (1) 전체 로직을 별도로 표시해야 하며, OP_IF 코드 블록은 분할할 수 없고, 분할 시 스크립트 실행 결과가 잘못될 수 있다. (2) 청크 실행 결과가 스택 상의 여러 요소에 해당할 수 있으므로 실제 계산 로직에 따라 bit commitment를 적용할 스택 요소 수를 표시해야 한다. (3) 각 청크 스크립트의 로직 기능이 가독성이 나빠 감사에 불리하다. (4) 스택에 다음 청크에서 필요하지 않은 요소가 포함되어 스택 공간을 낭비할 수 있다.
-
기능적 분할: 계산 내 각 기능 하위 함수를 기반으로 분할하며, 하위 함수의 입력-출력 값이 명확하다. 스크립트 분할과 동시에 각 청크에 필요한 bit commitment 스크립트도 구현되며, 최종 청크 스크립트 총 크기가 4MB 미만이고 스택 크기가 1000 미만이면 된다. 장점은 기능이 명확하고 단일 청크 로직이 명확하여 가독성이 좋고 감사에 용이하다는 것이다. 단점은 원래 계산 로직 표현과 스크립트 수준 로직 표현이 일치하지 않아 원래 계산 하위 함수가 최적이더라도 스크립트 수준에서 최적이 아닐 수 있다는 것이다.
-
수동 분할: 스크립트 분할 지점이 기능 하위 함수가 아닌 수동으로 설정된다. 특히 단일 하위 함수 크기가 4MB를 초과하는 경우에 적합하다. 장점은 Fq12 관련 계산 하위 함수와 같이 스크립트 크기가 큰 하위 함수를 수동으로 분할할 수 있고, 단일 청크 로직이 명확하여 가독성과 감사에 유리하다는 것이다. 단점은 인간의 튜닝 능력에 제한을 받으며, 전체 스크립트를 최적화한 후 기존에 설정한 수동 분할 지점이 최적이 아닐 수 있어 재조정이 필요하다는 것이다.
예를 들어, Groth16 verifier는 다수의 최적화를 거쳐 script size가 약 7GB에서 약 1.26GB로 감소했다. 이러한 전체 계산 최적화 외에도 각 청크를 개별적으로 최적화하여 스택 공간을 충분히 활용할 수 있다. lookup table 기반의 더 나은 알고리즘을 도입하고 lookup table을 동적으로 로드 및 언로드함으로써 각 청크의 script size를 추가로 줄일 수 있다.
web2 프로그래밍 언어의 계산 비용과 실행 환경은 비트코인 스크립트의 비용과 실행 환경과 완전히 다르므로, 다양한 알고리즘을 비트코인 스크립트로 구현할 때 기존 구현을 단순히 번역하는 것은 불가능하다. 따라서 비트코인 시나리오에 맞춰 다음 최적화를 고려해야 한다.
-
메모리 지역성 최적 알고리즘을 찾는다. 계산량 일부를 희생하더라도 청크 간 입력-출력 비트 수를 줄여 BitVM2 설계에서 assertTx 트랜잭션이 약속해야 하는 데이터 양을 감소시킨다.
-
논리 연산 등의 관련 연산의 교환 법칙(x&y = y&x)을 활용하여 조회표를 거의 절반으로 줄인다.
-
현재 Fq12 연산에 해당하는 스크립트 양이 매우 크므로 Fiat-Shamir, Schwartz-Zipple 및 다항식 커밋 방안을 활용하여 Fq12 확장 체 연산의 계산 복잡도를 크게 줄일 수 있다.
4 결론
본고는 먼저 비트코인 스크립트의 제약을 소개하고, 비트 커밋먼트를 통해 UTXO의 무상태성 제약을 극복하고, 탭루트를 통해 스크립트 공간 제약을 극복하며, 커넥터 아웃풋을 통해 UTXO 소비 방식 제약을 극복하고, 계약을 통해 사전 서명 제약을 극복하는 방법을 설명하였다. 이후 사기 증명과 유효성 증명의 특징, 허가형과 무허가형 사기 증명의 특징, 일회성과 다회성 사기 증명의 특징, 비트코인 스크립트 분할 기술에 대해 포괄적으로 정리하고 요약하였다.
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
@BitlayerLabs
