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
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 3D950A81
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 14 Nov 2017 01:21:17 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ua0-f175.google.com (mail-ua0-f175.google.com
[209.85.217.175])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5C16CFD
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 14 Nov 2017 01:21:16 +0000 (UTC)
Received: by mail-ua0-f175.google.com with SMTP id p33so9159086uag.9
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 13 Nov 2017 17:21:16 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:sender:from:date:message-id:subject:to
:content-transfer-encoding;
bh=p8Ur3LLZ3rvUF+9Jahd/f/xZ6F9WUVQWdHyIkwgZOsU=;
b=ZBegJCOwc4FGf7L6O0NteLHfIyDAmA0pJ2CB4Tmxpc3QvuRvFEJ0ou8k6aWp4Cjini
UK/7tprfHySRKqnduLtMBd39RA/K+9JwV7Zhqky1yTgQo8gvEYzkRWwF6/JiytPxzeSF
nV3u0dyUrqxey0l4Du8U9RIHc20f95el3qC/7GlOypkgp+U300qM2imhuZ/LPqdJr9qY
whc7JiS1TxSVeyApK9a5WkGbAZivTiMtcfOo6hAv2xLXrk8mYX6OsLGUv2xSIFkhftJ6
yHzL7krf3sM7ClN+IG0lcffSgP3QRlLknTMoglgaABVZvuCUaXKrg7kyJTjbcil6YDZs
cALg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:sender:from:date:message-id:subject
:to:content-transfer-encoding;
bh=p8Ur3LLZ3rvUF+9Jahd/f/xZ6F9WUVQWdHyIkwgZOsU=;
b=s6jT7fQVFkyBQxssza36LnJ1aw08mm7uoeEJgUD8w89wbb0sX2kdugJCNlUj9i3ONn
sWHYveXpn5kZ138VNgc4bWZQG0t/nDeRzc3boYtRb+ZTBIR5Q1TnU9mQyN/KfXtcPii0
KYMqCGLxbQX9MesnXQZoaIEDcbRy0VPkkix/xRM0jyJDe93ARsvOHmqMEgz4X+/tisA1
JmPECCqfm0i1RsDMJEQwArzVbMzjrxRgCBXWLuNV3QaOsjiAEtfOPVa8ajlDk08bffJI
Bc3cHxbKeQcfhsp2BtzQAoLi0tYG3TBPAzhR/qhR7eZ6/Tfzt4nQq0V2TnDz5XDw6FUo
3Gdw==
X-Gm-Message-State: AJaThX7zZ8ERgm5G425o8RFmycJdyNMZHJwsoHK0znUnD68e/rI9KUNe
Q9HFvvUJYr8WRZDt/zrRVIKP2xE7pgZ9RQQbZeoy6g==
X-Google-Smtp-Source: AGs4zMaCnRQRTBWTetR5p2JgwWAHY2MGO1fBAMdIyH0kBNQX2aWRrXhy/WX39pUCV3bqoHbCxUtKxLk3gGKXiY0pTQA=
X-Received: by 10.176.7.193 with SMTP id d1mr8594841uaf.21.1510622475294; Mon,
13 Nov 2017 17:21:15 -0800 (PST)
MIME-Version: 1.0
Sender: gmaxwell@gmail.com
Received: by 10.103.85.148 with HTTP; Mon, 13 Nov 2017 17:21:14 -0800 (PST)
From: Gregory Maxwell <greg@xiph.org>
Date: Tue, 14 Nov 2017 01:21:14 +0000
X-Google-Sender-Auth: QHjf_RI8M9ICO3BSdL2YFUTCwLM
Message-ID: <CAAS2fgQ0Cb2B=Ye2TnpfQqP4=kpZCxMWRXYB0CcFa71sQJaGuw@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
FREEMAIL_FROM,RCVD_IN_DNSWL_NONE autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: [bitcoin-dev] Updates on Confidential Transactions efficiency
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: Tue, 14 Nov 2017 01:21:17 -0000
Jump to "New things here" if you're already up to speed on CT and just
want the big news.
Back in 2013 Adam Back proposed that Bitcoin and related systems could
use additive homomorphic commitments instead of explicit amounts in
place of values in transactions for improved privacy. (
https://bitcointalk.org/index.php?topic=3D305791.0 )
We've since adopted the name 'confidential transactions' for this
particular approach to transaction privacy.
This approach makes transaction amounts private--known only to the
sender, the receiver, and whichever parties they choose to share the
information with through sharing watching keys or through revealing
single transactions. While that, combined with pseudonymous addresses,
is a pretty nice privacy improvement in itself, it turns out that
these blinded commitments also perfectly complement CoinJoin (
https://bitcointalk.org/index.php?topic=3D279249.0 ) by avoiding the
issue of joins being decoded due to different amounts being used. Tim
Ruffing and Pedro Moreno-Sanchez went on to show that CJ can be
dropped into distributed private protocols for CoinJoin (
http://fc17.ifca.ai/bitcoin/papers/bitcoin17-final6.pdf ) which
achieve the property where no participant learns which output
corresponds to which other participant.
The primary advantage of this approach is that it can be constructed
without any substantial new cryptographic assumptions (e.g., only
discrete log security in our existing curve), that it can be high
performance compared to alternatives, that it has no trusted setup,
and that it doesn't involve the creation of any forever-growing
unprunable accumulators. All major alternative schemes fail multiple
of these criteria (e.g., arguably Zcash's scheme fails every one of
them).
I made an informal write-up that gives an overview of how CT works
without assuming much crypto background:
https://people.xiph.org/~greg/confidential_values.txt
The main sticking point with confidential transactions is that each
confidential output usually requires a witness which shows that the
output value is in range. Prior to our work, the smallest range
proofs without trusted setup for the 0-51 bit proofs needed for values
in Bitcoin would take up 160 bytes per bit of range proved, or 8160
bytes needed for 51 bits--something like a 60x increase in transaction
size for a typical transaction usage.
I took Adam's suggestion and invented a number of new optimizations,
and created a high performance implementation. (
https://github.com/ElementsProject/secp256k1-zkp/tree/secp256k1-zkp/src/mod=
ules/rangeproof
). With these optimizations the size is reduced to 128 bytes per two
bits plus 32 bytes; about 40% of the prior size. My approach also
allowed a public exponent and minimum value so that you could use a
smaller range (e.g., 32 bits) and have it cover a useful range of
values (though with a little privacy trade-off). The result could give
proof sizes of about 2.5KB per output under realistic usage. But this
is still a 20x increase in transaction size under typical usage--
though some in the Bitcoin space seem to believe that 20x larger
blocks would be no big deal, this isn't a view well supported by the
evidence in my view.
Subsequent work has been focused on reducing the range proof size further.
In our recent publication on confidential assets (
https://blockstream.com/bitcoin17-final41.pdf ) we reduce the size to
96*log3(2)*bits + 32, which still leaves us at ~16x size for typical
usage. (The same optimizations support proofs whose soundness doesn't
even depend on the discrete log assumption with the same size as the
original CT publication).
-- New things here --
The exciting recent update is that Benedikt B=C3=BCnz at Standford was able
to apply and optimize the inner product argument of Jonathan Bootle to
achieve an aggregate range proof for CT with size 64 * (log2(bits *
num_outputs)) + 288, which is ~736 bytes for the 64-bit 2-output case.
This cuts the bloat factor down to ~3x for today's traffic patterns.
Since the scaling of this approach is logarithmic with the number of
outputs, use of CoinJoin can make the bloat factor arbitrarily small.
E.g., combining 64 transactions still only results in a proof under
1.1KB, so in that case the space overhead from the range proof is
basically negligible.
The log scaling in the number of range-bits also means that unlike the
prior construction there is little reason to be skimpy with the number
of bits of range at the potential expense of privacy: covering the
full range of possible values takes only slightly longer proofs than
covering a short range. This scheme also has a straightforward and
efficient method for multi-party computation, which means that the
aggregates can be used in all-party-private coinjoins like the value
shuffle work mentioned above.
Unlike prior optimizations, verification in this new work requires
computation which is more than linear in the size of the proof (the
work is linear in the size of the statement being proved). So it's
likely that in spite of the small proofs the verification will be
similar in speed to the prior version, and likely that computation
will be the bottleneck. Andrew, Pieter, Jonas Nick, and I are working
on an optimized implementation based on libsecp256k1 so we'll know
more precise performance numbers soon.
This work also allows arbitrarily complex conditions to be proven in
the values, not just simple ranges, with proofs logarithmic in the
size of the arithmetic circuit representing the conditions being
proved--and still with no trusted setup. As a result it potentially
opens up many other interesting applications as well.
The pre-print on this new work is available at https://eprint.iacr.org/2017=
/1066
|
