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
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <adam.back@gmail.com>) id 1UcwQF-0007hA-UC
for bitcoin-development@lists.sourceforge.net;
Thu, 16 May 2013 11:32:35 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
designates 74.125.83.43 as permitted sender)
client-ip=74.125.83.43; envelope-from=adam.back@gmail.com;
helo=mail-ee0-f43.google.com;
Received: from mail-ee0-f43.google.com ([74.125.83.43])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1UcwQE-000112-R3
for bitcoin-development@lists.sourceforge.net;
Thu, 16 May 2013 11:32:35 +0000
Received: by mail-ee0-f43.google.com with SMTP id d41so1393972eek.30
for <bitcoin-development@lists.sourceforge.net>;
Thu, 16 May 2013 04:32:28 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=google.com; s=20120113;
h=x-received:date:from:to:cc:subject:message-id:references
:mime-version:content-type:content-disposition:in-reply-to
:user-agent:x-hashcash:x-hashcash:x-hashcash:x-hashcash;
bh=vhi41t6Nf4+53ywkS12lGxGShJF6TqvQcRNUnd3N/x8=;
b=Wzq56CQ4U1cUCnTlL0UzDGmCmzM47SvPC93Gi2ihG33A+6nDFO8MOUkDXLmQgjAOwM
HUcX+licmSUyjFQPp0eD3/X0dYQar9/GpejrFyhH3Z2NwkYJDo7aPtTu4G18slwiiZTm
RKvPAFzQTwoJ+lBKpjFJSYg6kHZa8lroo+r+50f2i37ah2DB2Yv7+KKV0dhRn6GcM3F3
NK3qX0yfdDmaMdecF3mjS9LSsP2L1XCuG5IgWEmIHr2q0fsk255wndtHcOHmstwlXS0+
0eIiErNGSGviW6t6rasgw6JZPVFwQdyVopqBd4qeW+BPQ/KoKgjK+bWMV5FnlKDktc+e
Nq6Q==
X-Received: by 10.15.107.77 with SMTP id ca53mr114254325eeb.40.1368703948444;
Thu, 16 May 2013 04:32:28 -0700 (PDT)
Received: from netbook (c83-90.i07-21.onvol.net. [92.251.83.90])
by mx.google.com with ESMTPSA id m48sm9653723eeh.16.2013.05.16.04.32.26
for <multiple recipients>
(version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Thu, 16 May 2013 04:32:27 -0700 (PDT)
Received: by netbook (Postfix, from userid 1000)
id 20A6A2E0652; Thu, 16 May 2013 13:32:25 +0200 (CEST)
Received: by flare (hashcash-sendmail, from uid 1000);
Thu, 16 May 2013 13:32:23 +0200
Date: Thu, 16 May 2013 13:32:22 +0200
From: Adam Back <adam@cypherspace.org>
To: Gregory Maxwell <gmaxwell@gmail.com>
Message-ID: <20130516113222.GA16384@netbook.cypherspace.org>
References: <20130515102509.GA3401@netbook.cypherspace.org>
<20130515111906.GA26020@savin>
<20130515114956.GA5863@netbook.cypherspace.org>
<5193825B.20909@lavabit.com>
<20130515162129.GB6156@netbook.cypherspace.org>
<20130515234030.GA17920@netbook.cypherspace.org>
<BF1C6C71-9EE5-4A2F-8B73-3E8F934A7CAE@gmail.com>
<CAAS2fgQP6mFb0izQxZcBwqBWdxKUiAy1sG23ScAZ+tEMvGU0WQ@mail.gmail.com>
<CANEZrP2dFi-3nZhYpaA9RfJ8N2e-GQ_YQtKMdnFfPx-9YLU6MA@mail.gmail.com>
<CAAS2fgQQk0Lhmon4FxK7NATDVkaY13DBmJgQk4riJLE1h_Ak0w@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <CAAS2fgQQk0Lhmon4FxK7NATDVkaY13DBmJgQk4riJLE1h_Ak0w@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Hashcash: 1:20:130516:gmaxwell@gmail.com::/JRrZ/1p9FFaDnn8:0000000000000000000
00000000000000000000000019vr
X-Hashcash: 1:20:130516:mike@plan99.net::XvjbNuyBcRXjkAUq:0056Mq
X-Hashcash: 1:20:130516:bitcoin-development@lists.sourceforge.net::UF15wFIEsCBjK
5AW:000000000000000000003/pz
X-Hashcash: 1:20:130516:adam@cypherspace.org::tFj/Ffsmon0ijADY:00000000000000000
0000000000000000000000002iII
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 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(adam.back[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
X-Headers-End: 1UcwQE-000112-R3
Cc: "bitcoin-development@lists.sourceforge.net"
<bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] blind symmetric commitment for stronger
byzantine voting resilience (Re: bitcoin taint & unilateral revocability)
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: Thu, 16 May 2013 11:32:36 -0000
On Wed, May 15, 2013 at 07:45:34PM -0700, Gregory Maxwell wrote:
>[committed coins] depending on how its done, at most conceals the
>transactions from people who aren't a party to them... though as time goes
>on eventually everyone becomes a party to a sufficiently old coin, and
>avoiding publication creates quadratic costs in evaluating a private
>clique's claims.... so
I believe the coin size and verification cost is linear not quadratic, but
maybe it depends on the parameter you're measuing in. The coin size is
linear with the number of committed (uncompacted) spends. You can view
reveals as committed compaction. For efficiency a recipient of a committed
coin may as well compact and spend in one transaction so no new messages are
created.
Btw I believe if one were concerned about the committed coin size, I can see
a small tweak that would keep the size of the committed coins small eg
256-bit regardless of number of spends (no longer grows), and let the block
store the encrytped & MACed commitment. Then compaction is no longer a
concern. However I think that is SPV -> SPV client unfriendly. (A full
client -> SPV client should still be workable as the full client could
alternatively send the client the MACed data and key, rather than have him
look at it from his block history.) (Crypto sketch below).
However I am not sure multi-spend committed coin size is really a concern
because to the extent people hold long commitments without revealing to the
network for the long term, that is a bandwidth saving to the network.
Overall about privacy it would be typically temporary, though the peers have
the technical means to react and defend themselves by using longer committed
chains if dishonest mining is detected on a significant scale.
>instead an implementation would make the identities public but only once
>they're burred a bit.
That was the seed idea. The more aggressive "spend lots of times in
committed form" is just a technical threat that will keep dishonest mining
in check. By definition the coin is already irrevocably spent before the
reveal (without the threat of having the dishonest miners endlessly redoing
their own deeply burried work). The only person who could be punished by
policy by >50% dishonest miner (retroactively) is the recipient, not the
spender, and the punishment is very muted: all he can do is prevent coin
compaction. If the committed coins are small, compact doesnt even hurt the
committed coin user, just network itself. Therefore a dishonest miner is
wasting his time his dishonesty cant enforce his dishonest policy.
To store the commitments in the block chain replace:
> (blind-sender, auth-tag, tx-commit)
>
> blind-sender = SHA1( SHA256( 1, pub ) )
> auth = HMAC-SHA256-128( K, tx-commit )
> tx-commit = SHA-256( tx )
> K = SHA-256( pub )
with:
(blind-sender, auth-tag, encrypted-tx-commit)
blind-sender = SHA1( SHA256( 1, pub ) )
auth = HMAC-SHA256-128( K, encrypted-tx-commit )
encrypted-tx-commit = AES( K, tx-commit ) (*)
K = SHA-256( pub )
then a reveal is just to send the recipient the public key (32 bytes)
per hop, still linear but ~3x smaller.
I suggested fixed size committed coin spends, that also you can do but with
public key crypto needed probably, and so dropping to the verification
efficiency of standard transactions. Sketch 2:
(blind-sender, auth-tag, encrypted-tx-commit)
(pub key P = xG, G = base point)
blind-sender = cP (public key EC multiplied by constant c)
sig = ECDSA( cx, encrypted-tx-commit )
encrypted-tx-commit = AES( K, tx-commit )
K = random
as K is random, knowledge of P if stored unencrypted does not allow
committed spend-to-junk. To reveal to a recipient just send them P and K at
each hop. (Same K each time, anyone on the committed coin spend chain can
already chose to reveal at any time so no loss of security.)
You dont need to verify a second signature inside the tx-commit because you
already signed the encrypted-tx which binds to it (encryption with out MAC
is malleable but you cant change it at all without invalidating the
encryption). Just need to check the input tx in the tx-commit has P as its
recipient. P does not even need to go into tx-commit as its already bound
by cP and signature security (cant create a signature with someone elses
key). So I think the commited coins of this form are the same size and
verification cost for the network. And small and fixed size to spend
offline. (32+32=64 bytes fixed).
Adam
(*) You should not as a principle re-use keys across algorithms, I omitted a
second key for simplicity. Really K1 = SHA256( 1||pub ), K2 = SHA256(
2||pub ) encrypted-tx-commit = AES( K1, tx-commit ), auth = HMAC( K2,
encrypted-tx-committ ). Or more simply a combined authenticated mode like
CCM or GCM and a single key managed by the mode.
|
