模擬 OP_RAND

03-03

作者：olkurbatov
來源：https://delvingbitcoin.org/t/emulating-op-rand/1409

我們提出了一種方法，可通過交易對手方之間的一種免信任的交互式遊戲，在比特幣上模擬 OP_RAND 操作碼。遊戲的結果是概率性的，並且不允許任何一方欺詐，也不允許在任何一個步驟中影響自己的勝率。協議可以讓外部參與者分辨不出，也不需要比特幣協議和腳本的升級。我們將用一個簡單的 Thimbles 遊戲 來演示這套協議是怎麼工作的，並提供關於可以使用上述方法的應用的初步思考。

引言

比特幣腳本自身並不允許置入隨機性，因此也不允許基於隨機性來構造支付流。所以，在下列假設下，“Alice 和 Bob 各出 5 BTC，如果硬幣是反面， Bob 就可以拿走所有錢 ” 這樣的流程是無法實現的：

交易無法在確認的時刻從某處派生（或者說取得）隨機性
比特幣腳本不能檢查區塊，也不能讀取過去和未來的交易
雙方都可以在每一個操作碼處理完成後得到相同的堆棧狀態
無法控制 ECDSA 和 Schnorr 簽名的確定性
比特幣不支持 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$ 是可以提前知道的。

流程：

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}
$$
Bob 收到證據 $\pi_c$ 之後，取出 $C$ 並計算：
$$
\mathsf{addr}b = \mathsf{hash}{160}(P_b + C)
$$
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)}
$$
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$，然後為它們創建一個一級承諾：$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}$ 創建二級承諾 $h_i = \mathsf{hash}(A_i), i \in[1,n]$ 以及三級承諾 $H_i = h_iG, i \in[1,n]$
$\mathcal{C}$ 創建一個證據 $\pi_a$ ，證明所有三級承諾都是正確推導的，然後其中一個一級承諾會跟 $P_{\mathcal{C}}$ 相結合
$\mathcal{C}$ 給 $\mathcal{A}$ 發送這組三級承諾，並提供證據 $\pi_a$
$\mathcal{A}$ 驗證證據 $\pi_a$，然後選擇其中一個三級承諾 $H_y$ 跟自己的 $P_A$ 組裝在一起。然後，$\mathcal{A}$ 發送該值 $R_{\mathcal{A}}=P_{\mathcal{A}}+H_y$ 和哈希值 $\mathsf{hash}(R_{\mathcal{A}})$
$\mathcal{A}$ 創建一個證據 $\pi_r$，證明其中一個三級證據會跟 $P_{\mathcal{A}}$ 相結合，然後發送給 $\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}$ 就勝出。否則 Alice 輸。

Thimbles 遊戲作為一個例子

（略）