summaryrefslogtreecommitdiff
path: root/2d/8dff4e7acf5054ad53a44473b8797f2fceac25
blob: 97492407348584803e5603ff816b449530f732a2 (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
Return-Path: <matsjj@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 3AABD267
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 27 Nov 2015 08:02:43 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f41.google.com (mail-wm0-f41.google.com [74.125.82.41])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 17865120
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 27 Nov 2015 08:02:39 +0000 (UTC)
Received: by wmww144 with SMTP id w144so47845101wmw.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 27 Nov 2015 00:02:37 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:date:message-id:subject:from:to:content-type;
	bh=GUPTuMRa5AtOD5qK9lpP5aEY5BrtANFDGf03qOiPyNE=;
	b=tHrdq109yw8CnfQPwrIZVFzquwVJw+l0uaViluClQwLFfctTIBWQWgrz3JIu7TZav2
	ounXa+Khjxeq9HuSdtdqGAEfGlKE/FwCKJr277zLwrEBXAegCA6oCPcorjhAAoeCWVU3
	xP+NMz86AnJ0sXthgv3m9KuBuWuGquEibFGqGKy5IFd/P9jG9qzwhdR4CV+5WkpOSotD
	gf+pqY4cQKOOHHMHWR2APXYl7AvC5uCA5hOsk8yQRwElR/bM45eT6BCZOPD2/MGaQXGL
	i/UavlWhxzNJ0aB/U1dbcr7/Bomk+4F31gxV5C/SxVNE1zva/azI1b5NxStJq1RfVKiF
	bFpw==
MIME-Version: 1.0
X-Received: by 10.28.232.136 with SMTP id f8mr9330914wmi.1.1448611357723; Fri,
	27 Nov 2015 00:02:37 -0800 (PST)
Received: by 10.27.88.193 with HTTP; Fri, 27 Nov 2015 00:02:37 -0800 (PST)
Date: Fri, 27 Nov 2015 09:02:37 +0100
Message-ID: <CAE8CtVmqT0L74+xyEh-fn9vDcudBuMvgSr39DBVFopXbKyvNcA@mail.gmail.com>
From: Mats Jerratsch <matsjj@gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: text/plain; charset=UTF-8
X-Spam-Status: No, score=-1.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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, 27 Nov 2015 11:13:17 +0000
Subject: [bitcoin-dev] [BIP] OP_CHECKPRIVPUBPAIR
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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, 27 Nov 2015 08:02:43 -0000

Prior discussion:
http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000309.html

Goal:
Greatly improve security for payment networks like the 'Lightning
Network' (LN) [1]

---

Introduction:
To improve privacy while using a payment network, it is possible to
use onion-routing to make a payment to someone. In this context,
onion-routing means encrypting the data about subsequent hops in a way
that each node only knows where it received a payment from and the
direct next node it should send the payment to. This way we can route
a payment over N nodes, and none of these will know

(1) at which position it is within the route (first, middle, last?)

(2) which node initially issued the payment (payer)

(3) which node consumes the payment (payee).

However, given the way payments in LN work, each payment is uniquely
identifiable by a preimage-hash pair R-H. H is included in the output
script of the commit transaction, such that the payment is enforceable
if you ever get to know the preimage R.

In a payment network each node makes a promise to pay the next node,
if they can produce R. They can pass on the payment, as they know that
they can enforce the payment from a previous node using the same
preimage R. This severely damages privacy, as it lowers the amount of
nodes an attacker has to control to gain information about payer and
payee.

---

Problem:
The problem was inherited by using RIPEMD-160 for preimage-hash
construction. For any cryptographic hash-function it is fundamentally
unfeasible to correlate preimage and hash in such a way, that

F1(R1) = R2 and
F2(H1) = H2, while
SHA(R1) = H1 and SHA(R2) = H2.

In other words, I cannot give a node H1 and H2 and ask it to receive
my payment using H1, but pass it on using H2, as the node has no way
of verifying it can produce R1 out of the R2 it will receive. If it
cannot produce R1, it is unable to enforce my part of the contract.

---

Solution:
While above functions are merely impossible to construct for a
cryptographic hash functions, they are trivial when R and H is a EC
private/public key pair. The original sender can make a payment using
H1 and pass on a random number M1, such that the node can calculate a
new public key

H2 = H1 + M1.

When he later receives the private key R2, he can construct

R1 = R2 - M1

to be able to enforce the other payment. M1 can be passed on in the
onion object, such that each node can only see M for that hop.
Furthermore, it is unfeasible to brute-force, given a sufficiently
large number M.

---

Example:

Given that E wants to receive a payment from A, payable to H. (if A
can produce R, it can be used as a prove he made the payment and E
received it)

A decides to route the payment over the nodes B, C and D. A uses four
numbers M1...M4 to calculate H1...H4. The following payments then take
place

A->B using H4
B->C using H3
C->D using H2
D->E using H1.

When E receives H1, he can use attached M1 to calculate R1 from it.
The chain will resolve itself, and A is able to calculate R using
M1...M4. It also means that all privacy is at the sole discretion of
the sender, and that not even the original pair R/H is known to any of
the nodes.

To improve privacy, E could also be a rendezvous point chosen by the
real receiver of the payment, similar constructions are similar in
that direction as well.

---

Caveats:

Currently it is difficult to enforce a payment to a private-public key
pair on the blockchain. While there exists OP_HASH160 OP_EQUAL to
enforce a payment to a hash, the same does not hold true for EC keys.
To make above possible we would therefore need some easy way to force
a private key, given a public key. This could be done by using one of
the unused OP_NOP codes, which will verify

<private key> <public key> OP_CHECKPRIVPUBPAIR

and fails if these are not correlated or NOP otherwise. Would need
OP_2DROP afterwards. This would allow deployment using a softfork.

As there are requests for all sort of general crypto operations in
script, we can also introduce a new general OP_CRYPTO and prepend one
byte for the operation, so

0x01 OP_CRYPTO = OP_CHECKPRIVPUBPAIR
0x02-0xff OP_CRYPTO = OP_NOP

to allow for extension at some later point.

---

Alternatives:

In the attached discussion there are some constructions that would
allow breaking the signature scheme, but they are either very large in
script language or expensive to calculate. Given that the blocksize is
a difficult topic already, it would not be beneficial to have a 400B+
for each open payment in case one party breaches the contract. (or
just disappears for a couple of days)

It is also possible to use a NIZKP - more specifically SNARK - to
prove to one node that it is able to recover a preimage R1 = R2 XOR
M1, given only H1, H2 and M1. However, these are expensive to
calculate and experimental in it's current state.

---

Acknowledgements:
Gregory Maxwell for pointing out addition of M1 for EC points is much
less expensive
Pieter Wuille for helping with general understanding of EC math.
Anthony Towns for bringing up the issue and explaining SNARKs

[1]
http://lightning.network/