서론
비트코인 스크립트 자체에는 무작위성을 도입할 수 없기 때문에, 무작위성에 기반한 지불 흐름을 구축할 수 없습니다. 따라서 다음과 같은 가정 하에서 "Alice와 Bob이 각각 5 BTC를 입금하고, 동전이 앞면이 나오면 Bob이 모든 돈을 가져갈 수 있다"와 같은 프로세스를 구현할 수 없습니다: 1. 거래에서 확인 시점에 무작위성을 파생(또는 얻을) 수 없습니다. 2. 비트코인 스크립트는 블록을 확인하거나 과거 및 미래 거래를 읽을 수 없습니다. 3. 양측 모두 각 명령어 처리 완료 후 동일한 스택 상태를 얻을 수 있습니다. 4. ECDSA 및 Schnorr 서명의 결정성을 제어할 수 없습니다. 5. 비트코인은 OP_RAND 명령어를 지원하지 않습니다. 이러한 모든 제한으로 인해 무작위성을 캡처하고 비트코인에서 사용할 수 있는 신뢰할 수 있는 방법을 찾을 수 없습니다. 우리는 두 당사자 간의 상호 작용 프로토콜을 통해 이를 구현하는 방법을 제안하고, 이러한 기능을 비트코인 기반 Thimbles 게임에 사용할 수 있음을 보여줍니다.사전 지식
$\mathbb{G}$는 소수 $p$의 순서를 가진 순환 그룹이며, $G \in \mathbb{G}$는 해당 그룹의 생성자입니다. $a \in \mathbb{F}_p$는 스칼라 값이며, $A \in \mathbb{G}$는 그룹의 요소입니다. $\mathsf{hash}_p(m) \rightarrow h\in \mathbb{F}_p$는 암호학적 해시 함수로, 임의의 메시지 $m$을 입력으로 받아 $h$라는 영역 요소를 반환합니다. $\mathsf{hash}_{160}(P) \rightarrow \mathsf{addr}\in \mathcal{A}$는 공개 키에 대해 연속적인 SHA-256 및 Ripemd160 연산을 수행하여 유효한 비트코인 주소를 출력하는 함수입니다. 우리는 다음과 같은 관계에 대한 증거 $\pi$를 정의합니다: $\mathcal{R} = {(w;x) \in \mathcal{W} \times \mathcal{X}: \phi_1(w,x), \phi_2(w,x) , \dots, \phi_m(w,x)}$, 여기서 $w$는 증인 데이터이고 $x$는 공개 데이터이며, $\phi_1(w,x), \phi_2(w,x) , \dots, \phi_m(w,x)$는 동시에 증명되어야 하는 일련의 관계입니다. 우리는 $n$개의 입력과 $m$개의 출력을 가진 비트코인 거래를 $\mathsf{TX}{(\mathsf{id, i, proof})^{(n)};(\mathsf{a BTC, cond})^{(m)}}$으로 정의합니다. 여기서 $\mathsf{id}$는 이전 거래의 해시 값, $i$는 출력 인덱스, $\mathsf{proof}$는 거래 지출에 필요한 데이터 집합입니다. $a$는 출력의 자금 금액이고 $\mathsf{cond}$는 스크립트 공개 키 조건입니다. 예를 들어, P2PKH 입력의 경우 $\mathsf{proof} \leftarrow \langle \mathsf{PK}, \sigma\rangle$이고 $\mathsf{cond}\leftarrow \langle$ OP_DUP, OP_HASH160, $\mathsf{addr}$, OP_EQUALVERIFY, OP_CHECKSIG $\rangle$입니다. P2PKH를 사용할 때 우리는 이 조건 표기를 간단히 $\mathsf{addr}$로 줄입니다.타원 곡선 포인트 제한 조항
먼저 "거래의 첫 번째 출력이 지출된 후에만 거래의 두 번째 출력을 지출할 수 있는" 거래를 두 당사자 간에 구현하는 방법을 살펴보겠습니다. 과거에는 이를 해시 타임락 계약으로 수행할 수 있다고 생각했지만, (1) 이는 식별 가능하고 (2) 최종 게임을 구현하는 데 도움이 되지 않습니다. 알고리즘 1: 다른 출력이 지출된 후에만 지출할 수 있는 조건부 출력 생성. 조건: Alice와 Bob이 각각 1 BTC를 입금합니다. Bob은 Alice가 자신의 1 BTC를 지출한 후에만 자신의 1 BTC를 지출할 수 있습니다. Bob의 공개 키 $P_b$는 사전에 알려져 있습니다. 프로세스: 1. Alice는 다음을 생성합니다: $$ sk_a \leftarrow \mathbb{F}_b \\ P_a = sk_a G \\ addr_a = \mathsf{hash}_{160}(P_a) \\ C = \mathsf{hash}_{p}(P_a)·G $$ 그리고 다음 관계에 대한 증거 $\pi_c$를 생성합니다: $$ \mathcal{R}_c = {P_a;\mathsf{addr}_a,C,G:\mathsf{hash}_{160}(P_a) \rightarrow \mathsf{addr}_a \and \mathsf{hash}_{p}(P_a)·G \rightarrow C} $$ 2. Bob은 증거 $\pi_c$를 받은 후 $C$를 추출하고 계산합니다: $$ \mathsf{addr}_b = \mathsf{hash}_{160}(P_b + C) $$ 3. Bob은 거래를 생성하고 Alice에게 보냅니다: $$ \mathsf{TX}_1{(\mathsf{prev}_A, i_A, -), (\mathsf{prev}_B, i_B, \sigma_B(\mathsf{TX}_1));(1BTC, \mathsf{addr}_a),(1BTC, \mathsf{addr}_b)} $$ 4. Alice도 이 거래에 서명하고 네트워크에 브로드캐스트합니다: $$ \mathsf{TX}_1{(\mathsf{prev}_A, i_A, \sigma_A(\mathsf{TX}_1)), (\mathsf{prev}_B, i_B, \sigma_B(\mathsf{TX}_1));(1BTC, \mathsf{addr}_a),(1BTC, \mathsf{addr}_b)} $$ Alice가 자신의 출력을 지출하려면 다음과 같은 거래를 생성하고 공개 키 $P_a$와 서명을 공개해야 합니다: $$ \mathsf{TX}_2{(\mathsf{TX}_1,1, \langle P_a, \sigma_{P_a}(\mathsf{TX}_2) \rangle);(1 BTC, \mathsf{addr}_{a'})} $$ 이 거래가 공개되면 Bob은 $P_a$를 추출하고 $\mathsf{hash}_p(P_a)$의 값을 복원할 수 있습니다. 그런 다음 두 번째 출력의 개인 키를 계산할 수 있습니다: $sk = \mathsf{hash}_p(P_a) + sk_b$(Bob만 $sk_b$를 알고 있음), 그리고 Bob은 $P_b + C$의 공개 키와 주소에 연결된 서명을 구성할 수 있습니다. $$ \mathsf{TX}_3{(\mathsf{TX}_1,2, \langle P_b + C, \sigma_{P_b + C}(\mathsf{TX}_3) \rangle);(1 BTC, \mathsf{addr}_{b'})} $$ (역자 주: 문맥을 고려할 때, Alice가 Bob에게 제공한 증거는 일종의 "영지식 증거"이며, Bob은 Alice가 이러한 값을 가지고 있다는 것을 알 수 있지만 증거에서 그 값이 무엇인지는 알 수 없습니다.) 이렇게 우리는 무작위성을 모방하고 Thimbles 게임의 첫 번째 부분을 구성했습니다. 우리가 강조하고 싶은 것은, 위의 예에서 Alice가 자신의 출력을 지출하고 $P_a$를 공개하지 않으면 Bob은 두 번째 출력의 개인 키를 복원할 수 없으므로 그것을 지출할 수 없다는 점입니다. 만약 우리가 일정 기간 후에 이러한 출력을 지출할 수 있는 기능을 제공해야 한다면(예를 들어 게임이 시작되지 않은 경우), 우리는 지불 채널 구조와 같이 자금을 다중 서명 출력에 잠그고 일정 기간 후에 지출할 수 있는 거래를 생성할 수 있습니다.OP_RAND 모방 프로토콜
우리는 거래의 두 당사자 간 상호 작용 프로토콜을 통해 OP_RAND 명령어를 모방하는 방법을 제안했습니다. 도전자 $\mathcal{C}$와 수락자 $\mathcal{A}$의 역할을 도입하고 OP_RAND 모방 프로토콜을 다음과 같이 정의할 수 있습니다:- $\mathcal{C}$ 와 $\mathcal{A}$ 각각 자신의 키 쌍 $\langle sk_{\mathcal{C}}, P_{\mathcal{C}}\rangle$ 와 $\langle sk_{\mathcal{A}}, P_{\mathcal{A}}\rangle$ 를 가지고 있습니다. 단, $P_{\mathcal{C}}$ 의 값만 공개되어 있습니다.
- $\mathcal{C}$ 는 임의의 숫자 $a_1, a_2,\dots, a_n$ 을 생성하고, 이를 이용하여 1차 약속 $A_i = a_iG, i\in[1, n]$ 을 만듭니다.
- $\mathcal{C}$ 는 그중 하나의 약속 $A_i$ 를 선택하여 자신의 공개키와 결합한 $R_{\mathcal{C}} = P_{\mathcal{C}}+A_x$ 를 만들고, 이의 해시값 $\mathsf{hash}(R_C)$ 만을 공개합니다.
- $\mathcal{C}$ 는 2차 약속 $h_i = \mathsf{hash}(A_i), i \in[1,n]$ 과 3차 약속 $H_i = h_iG, i \in[1,n]$ 을 만듭니다.
- $\mathcal{C}$ 는 모든 3차 약속이 올바르게 유도되었음을 증명하는 증거 $\pi_a$ 를 만들고, 그중 하나의 1차 약속이 $P_{\mathcal{C}}$ 와 결합됩니다.
- $\mathcal{C}$ 는 이 3차 약속들과 증거 $\pi_a$ 를 $\mathcal{A}$ 에게 보냅니다.
- $\mathcal{A}$ 는 증거 $\pi_a$ 를 검증한 후, 그중 하나의 3차 약속 $H_y$ 를 자신의 $P_A$ 와 결합한 $R_{\mathcal{A}}=P_{\mathcal{A}}+H_y$ 와 그 해시값 $\mathsf{hash}(R_{\mathcal{A}})$ 를 보냅니다.
- $\mathcal{A}$ 는 자신의 $P_{\mathcal{A}}$ 와 결합되는 3차 증거를 증명하는 증거 $\pi_r$ 을 만들어 $\mathcal{C}$ 에게 보냅니다. 이 증거는 $P_{\mathcal{A}}$ 의 이산대수에 대한 지식도 보여줍니다.
- $\mathcal{C}$ 는 증거 $\pi_r$ 을 검증하고, 유효하다면 $R_{\mathcal{C}}$ 를 공개합니다.
- $\mathcal{A}$ 는 $A_x = R_{\mathcal{C}}-P_{\mathcal{C}}$ 를 계산합니다.
- 만약 $\mathsf{hash}(A_x)\cdot G = H_y$ 라면 $\mathcal{A}$ 가 승리합니다. 그렇지 않으면 $\mathcal{A}$ 가 패배합니다.
Thimbles 게임을 하나의 예제로
（생략）
