summaryrefslogtreecommitdiff
path: root/b7/e062c2977f2ffce300d0848dd9ad973c45cbee
blob: 46bce897af6ca35d3e8089857fdb0ac70155ba90 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
Return-Path: <matthew@roberts.pm>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id B51998B0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 20 May 2016 10:57:47 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f170.google.com (mail-io0-f170.google.com
	[209.85.223.170])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1B1C919B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 20 May 2016 10:57:47 +0000 (UTC)
Received: by mail-io0-f170.google.com with SMTP id t40so49180576ioi.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 20 May 2016 03:57:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=roberts-pm.20150623.gappssmtp.com; s=20150623;
	h=mime-version:date:message-id:subject:from:to;
	bh=1mNx+CKa8L6Aopv88sLH4ZX1tzjl5Dzea4RDk4pFhnA=;
	b=0mrdCwJU8idRZpTLyYaTkLFpo6v+vvWb1ZE/+MssF4li5x4mcQXtEXF6pztYTtO+hJ
	hq+I9Qwwvpu+apTxyLc1gV6EpmzpU6y21akPhJbaCbWNl+P4GJ/uLQi7rckCnAY/GRrf
	ewifgCpmPIuVQwIoZFyNUfjIV7AwIZydZyHXOMh4tWHwUQIexYKzI0jVDgP+I18D3u1G
	/BS9KM/DFFIBIzkoC1Vos1yZXIFHbkkwQaZenLob3kzTrnN/grY6GIgpuGIsW3KW02dX
	sdp3RfqS1OeBYbns9pBTIMPGZKFbCOpu384BWKMh66y7qG74LWtyMsI4sERM3jKdh/V1
	YSpQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:date:message-id:subject:from:to;
	bh=1mNx+CKa8L6Aopv88sLH4ZX1tzjl5Dzea4RDk4pFhnA=;
	b=g5cxcYg2PiM8NaNuJAuRbHi87qFZLxWWUZaRMnXwGYLIA1NftqMU5dxnSkAVicHeuC
	ybWiAjCIh7ogg/pnXRro2vqQQkM+cwZqNKvIgya/Z9hy4GltbYSxTUW10C3Xn5dsF+7O
	uuWpLPASMzptWZjbe49H9zBiu6NAz6iKJ64fssfQPuYpq/5ZTLC3cn87SYjSk7Pm8Czu
	P8jnv/DBp/5xeD9Tlizhsawhbx5hXmeEYEvUcdI/EYkv/hyvLx4EbLkzmGXbLDthz1pp
	ZSGPOOLAWCaCJ4AfQ/qcfQvf+AhxC2LZZ4PPNpkrbgpss8tQHI2iqkPuJcEjla1CCMbB
	AbGw==
X-Gm-Message-State: AOPr4FVzcUWht6W3iSmgnPgwOjziuccZ5gGYRlDusmEyy03IO2wFWdjwXB5gFqhFWQ6EnxSOgWxeBBBhVHTO9Q==
MIME-Version: 1.0
X-Received: by 10.107.154.130 with SMTP id c124mr2537714ioe.169.1463741866321; 
	Fri, 20 May 2016 03:57:46 -0700 (PDT)
Received: by 10.107.198.10 with HTTP; Fri, 20 May 2016 03:57:46 -0700 (PDT)
X-Originating-IP: [115.70.56.56]
Date: Fri, 20 May 2016 05:57:46 -0500
Message-ID: <CAAEDBiEB_RXBjrLB8kDb52bJOwZK-arVeHA_9LyoDgAraLKHNg@mail.gmail.com>
From: Matthew Roberts <matthew@roberts.pm>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a1140f6bafc741c053343f5b8
X-Spam-Status: No, score=-1.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,HTML_MESSAGE,RCVD_IN_DNSWL_LOW,SUBJ_ALL_CAPS autolearn=no
	version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Fri, 20 May 2016 11:25:21 +0000
Subject: [bitcoin-dev] BIP: OP_PRANDOM
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 20 May 2016 10:57:47 -0000

--001a1140f6bafc741c053343f5b8
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

=3D=3D Background

OP_PRANDOM is a new op code for Bitcoin that pushes a pseudo-random number
to the top of the stack based on the next N block hashes. The source of the
pseudo-random number is defined as the XOR of the next N block hashes after
confirmation of a transaction containing the OP_PRANDOM encumbered output.
When a transaction containing the op code is redeemed, the transaction
receives a pseudo-random number based on the next N block hashes after
confirmation of the redeeming input. This means that transactions are also
effectively locked until at least N new blocks have been found.


=3D=3D Rational

Making deterministic, verifiable, and trustless pseudo-random numbers
available for use in the Script language makes it possible to support a
number of new smart contracts. OP_PRANDOM would allow for the simplistic
creation of purely decentralized lotteries without the need for complicated
multi-party computation protocols. Gambling is also another possibility as
contracts can be written based on hashed commitments, with the winner
chosen if a given commitment is closest to the pseudo-random number.
OP_PRANDOM could also be used for cryptographically secure virtual asset
management such as rewards in video games and in other applications.


=3D=3D Security

Pay-to-script-hash can be used to protect the details of contracts that use
OP_PRANDOM from the prying eyes of miners. However, since there is also a
non-zero risk that a participant in a contract may attempt to bribe a miner
the inclusion of multiple block hashes as a source of randomness is a must.
Every miner would effectively need to be bribed to ensure control over the
results of the random numbers, which is already very unlikely. The risk
approaches zero as N goes up.

There is however another issue: since the random numbers are based on a
changing blockchain, its problematic to use the next immediate block hashes
before the state is =E2=80=9Cfinal.=E2=80=9D A safe default for accepting t=
he blockchain
state as final would need to be agreed upon beforehand, otherwise you could
have multiple random outputs becoming valid simultaneously on different
forks.

A simple solution is not to reveal any commitments before the chain height
surpasses a certain point but this might not be an issue since only one
version will eventually make it into the final chain anyway -- though it is
something to think about.


=3D=3D Outro

I'm not sure how secure this is or whether its a good idea so posting it
here for feedback

Thoughts?

--001a1140f6bafc741c053343f5b8
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">


=09
=09
=09
=09


<p style=3D"margin-bottom:0in;line-height:100%">=3D=3D Background

</p><p style=3D"margin-bottom:0in;line-height:100%">OP_PRANDOM is a new
op code for Bitcoin that pushes a pseudo-random number to the top of
the stack based on the next N block hashes. The source of the
pseudo-random number is defined as the XOR of the next N block hashes
after confirmation of a transaction containing the OP_PRANDOM
encumbered output. When a transaction containing the op code is
redeemed, the transaction receives a pseudo-random number based on
the next N block hashes after confirmation of the redeeming input.
This means that transactions are also effectively locked until at
least N new blocks have been found.</p>
<p style=3D"margin-bottom:0in;line-height:100%"><br>
</p>
<p style=3D"margin-bottom:0in;line-height:100%">=3D=3D Rational</p>

<p style=3D"margin-bottom:0in;line-height:100%">Making
deterministic, verifiable, and trustless pseudo-random numbers
available for use in the Script language makes it possible to support
a number of new smart contracts. OP_PRANDOM would allow for the
simplistic creation of purely decentralized lotteries without the
need for complicated multi-party computation protocols. Gambling is
also another possibility as contracts can be written based on hashed
commitments, with the winner chosen if a given commitment is closest
to the pseudo-random number. OP_PRANDOM could also be used for
cryptographically secure virtual asset management such as rewards in
video games and in other applications.</p>
<p style=3D"margin-bottom:0in;line-height:100%"><br>
</p>
<p style=3D"margin-bottom:0in;line-height:100%">=3D=3D Security</p>

<p style=3D"margin-bottom:0in;line-height:100%">Pay-to-script-hash
can be used to protect the details of contracts that use OP_PRANDOM
from the prying eyes of miners. However, since there is also a
non-zero risk that a participant in a contract may attempt to bribe a
miner the inclusion of multiple block hashes as a source of
randomness is a must. Every miner would effectively need to be bribed
to ensure control over the results of the random numbers, which is
already very unlikely. The risk approaches zero as N goes up.</p>

<p style=3D"margin-bottom:0in;line-height:100%">There is however
another issue: since the random numbers are based on a changing
blockchain, its problematic to use the next immediate block hashes
before the state is =E2=80=9Cfinal.=E2=80=9D A safe default for accepting t=
he
blockchain state as final would need to be agreed upon beforehand, otherwis=
e you
could have multiple random outputs becoming valid simultaneously on
different forks.</p><p style=3D"margin-bottom:0in;line-height:100%">A simpl=
e solution is not to reveal any commitments before the chain height surpass=
es a certain point but this might not be an issue since only one version
will eventually make it into the final chain anyway -- though it is somethi=
ng to think about.</p>
<p style=3D"margin-bottom:0in;line-height:100%"><br>
</p>
<p style=3D"margin-bottom:0in;line-height:100%">=3D=3D Outro</p>

<p style=3D"margin-bottom:0in;line-height:100%">I&#39;m not sure how
secure this is or whether its a good idea so posting it here for
feedback</p>

<p style=3D"margin-bottom:0in;line-height:100%">Thoughts?</p>

</div>

--001a1140f6bafc741c053343f5b8--