Simulating OP_RAND

Author: olkurbatov

Source: https://delvingbitcoin.org/t/emulating-op-rand/1409

We have proposed a method to emulate the OP_RAND opcode on Bitcoin through a non-interactive game between counterparties. The outcome of the game is probabilistic, and it does not allow any party to cheat or influence their own probability of winning at any step. The protocol can be distinguished by external participants, and it does not require any upgrades to the Bitcoin protocol and script.

Introduction

Bitcoin script itself does not allow for the introduction of randomness, and therefore does not allow for the construction of payment flows based on randomness. So, under the following assumptions, the flow "Alice and Bob each put in 5 BTC, and if the coin is tails, Bob can take all the money" cannot be implemented:

1. Transactions cannot derive (or obtain) randomness at the time of confirmation
2. Bitcoin script cannot inspect blocks or read past and future transactions
3. Both parties can obtain the same stack state after each opcode is processed
4. The determinism of ECDSA and Schnorr signatures cannot be controlled
5. Bitcoin does not support the OP_RAND opcode

All of the above limitations prevent us from finding a trustless method to capture randomness and use it to operate on Bitcoin. We propose a solution through a two-party interactive protocol, and demonstrate how these features can be used in a Bitcoin-based thimbles game.

Preliminaries

$\mathbb{G}$ is a cyclic group of prime order $p$, and $G \in \mathbb{G}$ is a generator of the group.

$a \in \mathbb{F}_p$ is a scalar value, and $A \in \mathbb{G}$ is an element of the group.

$\mathsf{hash}_p(m) \rightarrow h\in \mathbb{F}_p$ is a cryptographic hash function that takes any message $m$ as input and returns an element $h$ of the field.

$\mathsf{hash}_{160}(P) \rightarrow \mathsf{addr}\in \mathcal{A}$ is a function that performs consecutive SHA-256 and Ripemd160 operations on a public key, outputting a valid Bitcoin address.

We define a proof $\pi$ for the following relation $\mathcal{R} = {(w;x) \in \mathcal{W} \times \mathcal{X}: \phi_1(w,x), \phi_2(w,x) , \dots, \phi_m(w,x)}$, where $w$ is a witness data and $x$ is a public data, and $\phi_1(w,x), \phi_2(w,x) , \dots, \phi_m(w,x)$ are a set of relations that must be proven simultaneously.

We define a Bitcoin transaction with $n$ inputs and $m$ outputs as $\mathsf{TX}{(\mathsf{id, i, proof})^{(n)};(\mathsf{a BTC, cond})^{(m)}}$, where $\mathsf{id}$ is the hash of the previous transaction, $i$ is the index of the output, $\mathsf{proof}$ is a set of data required to spend the transaction; $a$ is the amount of funds in the output, $\mathsf{cond}$ is the script public key condition. For example, a P2PKH input requires $\mathsf{proof} \leftarrow \langle \mathsf{PK}, \sigma\rangle$ and $\mathsf{cond}\leftarrow \langle$ OP_DUP, OP_HASH160, $\mathsf{addr}$, OP_EQUALVERIFY, OP_CHECKSIG $\rangle$. When using P2PKH, we will simplify the notation of the condition to just $\mathsf{addr}$.

Elliptic Curve Point Locking Clause

First, let's look at how to implement a transaction with the following condition: "The second output of the transaction can only be spent after the first output has been spent." In the past, people thought this could be done with a hash time-lock contract, but (1) it is recognizable; (2) it does not help us achieve our ultimate game.

Algorithm 1: Creating a conditional output that can only be spent after another output has been spent.

Conditions: Alice and Bob each deposit 1 BTC. Bob can only spend his 1 BTC after Alice has spent her 1 BTC. Bob's public key $P_b$ is known in advance.

Procedure:

1. Alice generates:

   $$
   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
   $$

   And generates a proof $\pi_c$ for the following relation:
   $$
   \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 receives the proof $\pi_c$, extracts $C$, and computes:
   $$
   \mathsf{addr}b = \mathsf{hash}{160}(P_b + C)
   $$

3. Bob creates a transaction and sends it to 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 also signs the transaction and broadcasts it to the network:
   $$
   \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)}
   $$

If Alice wants to spend her output, she needs to create a transaction like this and publish the public key $P_a$ and its signature:
$$
\mathsf{TX}_2{(\mathsf{TX}1,1, \langle P_a, \sigma{P_a}(\mathsf{TX}2) \rangle);(1 BTC, \mathsf{addr}{a'})}
$$
When this transaction is published, Bob can extract $P_a$ and reconstruct the value of $\mathsf{hash}_p(P_a)$. Then the private key for the second output can be computed: $sk = \mathsf{hash}_p(P_a) + sk_b$ (only Bob knows $sk_b$), and Bob can construct a signature associated with the public key $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'})}
$$
(Note: In the context here, the evidence Alice gives to Bob is a "zero-knowledge proof", where Bob only knows that Alice has such a value, but cannot know what the value is from the evidence.)

This completes the first part of constructing our simulation of randomness and our thimbles game. We want to point out that in the above example, if Alice does not spend her output and does not publish $P_a$, Bob cannot reconstruct the private key for the second output and therefore cannot spend it. If we need to provide the ability to spend these outputs after a period of time (e.g., if the game never starts), we can do so in a way similar to payment channel construction - locking the funds in a multi-signature output and then creating a transaction that can spend it after a certain time.

OP_RAND Emulation Protocol

We propose a method to emulate the OP_RAND opcode through an interactive protocol between the two parties of a transaction. By introducing the roles of a Challenger $\mathcal{C}$ and an Acceptor $\mathcal{A}$, we can define the protocol to emulate OP_RAND as follows:

1. $\mathcal{C}$ and $\mathcal{A}$ each have their own key pairs $\langle sk_{\mathcal{C}}, P_{\mathcal{C}}\rangle$ and $\langle sk_{\mathcal{A}}, P_{\mathcal{A}}\rangle$. Only the value of $P_{\mathcal{C}}$ is public.
2. $\mathcal{C}$ generates a set of random values $a_1, a_2,\dots, a_n$, and then creates a first-level commitment: $A_i = a_iG, i\in[1, n]$
3. $\mathcal{C}$ selects one of the commitments $A_i$, combines it with their public key: $R_{\mathcal{C}} = P_{\mathcal{C}}+A_x$, and then publishes only the hash value: $\mathsf{hash}(R_C)$
4. $\mathcal{C}$ creates second-level commitments $h_i = \mathsf{hash}(A_i), i \in[1,n]$ and third-level commitments $H_i = h_iG, i \in[1,n]$
5. $\mathcal{C}$ creates a proof $\pi_a$, proving that all third-level commitments are correctly derived, and one of the first-level commitments will be combined with $P_{\mathcal{C}}$
6. $\mathcal{C}$ sends this set of third-level commitments to $\mathcal{A}$ and provides the proof $\pi_a$
7. $\mathcal{A}$ verifies the proof $\pi_a$, then selects one of the third-level commitments $H_y$ and combines it with their $P_A$. Then, $\mathcal{A}$ sends the value $R_{\mathcal{A}}=P_{\mathcal{A}}+H_y$ and the hash value $\mathsf{hash}(R_{\mathcal{A}})$
8. $\mathcal{A}$ creates a proof $\pi_r$, proving that one of the third-level commitments will be combined with $P_{\mathcal{A}}$, and also demonstrates knowledge of the discrete logarithm of $P_{\mathcal{A}}$, then sends it to $\mathcal{C}$.
9. $\mathcal{C}$ verifies the proof $\pi_r$, and if it is valid, publishes $R_{\mathcal{C}}$
10. $\mathcal{A}$ computes $A_x = R_{\mathcal{C}}-P_{\mathcal{C}}$
11. If $\mathsf{hash}(A_x)\cdot G = H_y$, $\mathcal{A}$ wins. Otherwise, Alice loses.

Thimbles game as an example

(略)