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
207
208
209
210
211
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <pete@petertodd.org>) id 1Vu3Ld-0008VW-JQ
for bitcoin-development@lists.sourceforge.net;
Fri, 20 Dec 2013 16:54:49 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of petertodd.org
designates 62.13.149.56 as permitted sender)
client-ip=62.13.149.56; envelope-from=pete@petertodd.org;
helo=outmail149056.authsmtp.com;
Received: from outmail149056.authsmtp.com ([62.13.149.56])
by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1Vu3Lc-0003Lh-02 for bitcoin-development@lists.sourceforge.net;
Fri, 20 Dec 2013 16:54:49 +0000
Received: from mail-c237.authsmtp.com (mail-c237.authsmtp.com [62.13.128.237])
by punt17.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rBKGsgUb048437
for <bitcoin-development@lists.sourceforge.net>;
Fri, 20 Dec 2013 16:54:42 GMT
Received: from petertodd.org (petertodd.org [174.129.28.249])
(authenticated bits=128)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rBKGsYhG079089
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO)
for <bitcoin-development@lists.sourceforge.net>;
Fri, 20 Dec 2013 16:54:37 GMT
Date: Fri, 20 Dec 2013 11:54:34 -0500
From: Peter Todd <pete@petertodd.org>
To: bitcoin-development@lists.sourceforge.net
Message-ID: <20131220165434.GA23932@petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="XsQoSWH+UP9D9v3l"
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: 69410a28-6997-11e3-94fa-002590a135d3
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd
P1hXKl1LNVAaWXld WiVPGEoXDxgzCjYj NEgGOBsDNw4AXQV1
JB0aXVBSFQZ4ABoL AxoUUR48dgJCZn9y bFhgVm5ZWE1lcE56
XU8aVx99EiQJMBcf V0lYfwoacQBKdhcL bFl7VXNcY20aYHNp
QEpqZj1qeGQDJi0Q GllXcANKSB9QQzJn UTsPGy4oB1YFRj12
NRE9K0UAFUAaPw0s MFJpRVMdPhsVAQ4W FFtcGDNeb1cGXWIm
CAlXUUITHHVWRiFH DxszPwQqSidDQTZV AVAt
X-Authentic-SMTP: 61633532353630.1024:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 174.129.28.249/587
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Score: -1.5 (-)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
-0.0 SPF_PASS SPF: sender matches SPF record
0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked.
See
http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block
for more information. [URIs: petertodd.org]
X-Headers-End: 1Vu3Lc-0003Lh-02
Subject: [Bitcoin-development] Censorship-resistance via timelock crypto for
embedded consensus systems
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Fri, 20 Dec 2013 16:54:49 -0000
--XsQoSWH+UP9D9v3l
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
Embedded consensus systems such as Mastercoin face the risk that the
data they need to embed in the host consensus system will be subject to
censorship. This censorship can take two forms: whitelists and
blacklists. The former we can't do anything about, however the latter
requires someone to identify the data-carrying transactions that are to
be blacklisted.
Embedding data steganographically in transactions is known to be
possible in ways that can-not be detected. Even if P2SH^2 (1) is
implemented data can be hidden in pubkeys in P2SH scriptSigs, either by
using unused pubkeys in CHECKMULTISIG transactions with a simple
transform(2) to turn arbitrary data into valid-looking pubkeys, or with
some ECC math even usable pubkeys can have data hidden in them.(3)
However these methods are unsuitable if the data needs to be provably
made public; without the encryption key the data is securely hidden.
Almost all consensus systems rely on proof-of-publication(4) and even if
the encryption keys are later made public - perhaps by broadcasting them
on a P2P network - we've only shifted the problem to proving that the
keys were released. Of course, if we then publish them via our host
consensus system, *that* act of publishing can itself be censored!
Timelock cryptography offers a solution to this problem. Let S(n, k) be
a sequential-hard strengthening function that takes key k and number of
rounds n, outputting k'. A suitable S() might be the scrypt function.
Let E(d, k) be a symmetric encryption algorithm. Finally let H(m) be a
cryptographic hash function.
To hide data D in a transaction we set k to some random and publicly
known value in the transaction and compute k'=3DS(n, k) and D'=3DE(D, k')
Then D' is hidden in the transaction, perhaps in an unused pubkey of a
CHECKMULTISIG scriptPubKey.
Our intended audience can also calculate k' from the public data, and
thus recover D in time ~t, thus we know that after time ~t has elapsed
all participants in the system can reliably come to consensus.
However miners and other parties who may wish to censor D face a
dilemma: If they repeat the calculation for every transaction that may
be hiding data they delay all transactions for all users. In addition
miners have a financial incentive to defect and mine transactions
without checking for hidden data.
Practical Considerations
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
Efforts should be made to limit the scope of possible transactions as
much as possible to reduce the computation required, e.g. by restricting
the search space to only transactions with scriptPubKeys starting with
some short prefix. This is a balance between computation and censorship
resistance.
Consideration needs to be made as to how the data will be validated as
part of the embedded consensus system, for instance via a checksum or
cryptographic signature.
Participates in the embedded consensus system should share k' keys among
each other to reduce overall effort. This ties back to validation: it
must not be possible to distribute a fake k' undetectably.
Picking n, and thus the time taken, is a balance. Also there should be
some mechanism to update n as technological improvements warrant. Along
those lines this method works best when t can be large and immediate
consensus is not required. A suitable use-case could be a key-value
consensus system for name information where mappings are infrequently
changed.
The source of k should be such that k' can be computed in advance,
however only by the sender. For instance simply using the first txin
hash allows the attacker to compute k' in advance themselves. A better
choice would be the first (real) pubkey in a scriptPubKey, a value we
can both compute in advance, yet is not known publicly.
Censorship resistant voting
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
With due care the scheme can be used to allow for censorship-resistant
voting. While previously it was believed that miners would inevitably be
able to censor any voting scheme - with the exception of certain special
cases(5) - provided that the financial incentive to collect fees
outweighs the incentive to not count votes we have strong censorship
resistance with strong consensus in a fixed amount of time.
1) Gregory Maxwell, [Bitcoin-development] To prevent arbitrary data
storage in txouts =E2=80=94 The Ultimate Solution,
https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/m=
sg01987.html
2) Peter Todd, Re: MasterCoin: New Protocol Layer Starting From =E2=80=9CThe
Exodus Address=E2=80=9D,
https://bitcointalk.org/index.php?topic=3D265488.msg3377058#msg3377058
3) ByteCoin, Untraceable transactions which can contain a secure message
are inevitable, https://bitcointalk.org/index.php?topic=3D5965.0
4) Peter Todd, [Bitcoin-development] Disentangling Crypto-Coin Mining:
Timestamping, Proof-of-Publication, and Validation,
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/ms=
g03307.html
5) John Dillon, Proposal: We should vote on the blocksize limit with proof-=
of-stake
voting, https://bitcointalk.org/index.php?topic=3D230864.0
--=20
'peter'[:-1]@petertodd.org
0000000000000001cdaabe80320d14ab5907997ec6ad12eaaa304941c34fc8bd
--XsQoSWH+UP9D9v3l
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
iQEcBAEBCAAGBQJStHZKAAoJEBmcgzuo5/CFkhcIAMAfGk6DoYKg6wT67pTNF8y2
je8dpJnarQNpWxW+bsFlpGnhnZ4Go5j2oijkmUFvovgGrx1jmwPHwSalR4FIyeat
v5KcGayTHXRraxXqPseXA99/7ac8FFRUKtdIWOHXQ7m2QvTNhcyFObYHGarr3FMW
gVXW12eqgVoHWRst/V4fughp3Ch2XaNhjnoMA9pUwivwFQskSTvrlOJ9fD0lHzbV
1HEnc4XJyDr+yt3oxzgrSKum6TS8vKAXkOISx+csOf1P/NNmb0MYlp/3OUYWDy6D
rYu3Bw90brzNpsZbJo/h+kt8WJMXW15yz5jmVPdA8tQLIHP1uoKqnjgUpTdL/2Y=
=Dsf+
-----END PGP SIGNATURE-----
--XsQoSWH+UP9D9v3l--
|
