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
|
Return-Path: <rsomsen@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id D9D02BB3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Sep 2019 03:39:45 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f67.google.com (mail-wr1-f67.google.com
[209.85.221.67])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 111E0619
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Sep 2019 03:39:45 +0000 (UTC)
Received: by mail-wr1-f67.google.com with SMTP id i1so9684224wro.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 07 Sep 2019 20:39:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to
:content-transfer-encoding;
bh=d5czZX+1ZzZ8rLEGCz7lcCN6biNvXk2n4TkDQHRutcQ=;
b=E5O8Z9QG1m7Y9GFiTbVVR7Chi31qn+ztoNPjYPqOoaFUC/fwDk++Uzw33uZQJLdcVd
v5Otmh1W6Ku+S4sa9rsrtIJPH2xhNz4Do4DDyy71GcoUP7ZIX8sYhwFHbR8MqxcZnaIj
Sov3pIHyk0d9EXXAw4rUv78i+1UeExYEIPKbvD9I/haX4F0RKA+tm1BRIgq2HARgE0FO
xi18MfpSuDsCFYN/kzC6aLcn+UubGkW38pzevu6dwkFPFzOm0MJz+jMXj5pmqouj+Ps2
r823ghJNKF7Cte1EygzWVumxSw4fGkLQt4ImMYRukICa/EuKshMtubOqTsHFaJg0IwIV
wwNg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to
:content-transfer-encoding;
bh=d5czZX+1ZzZ8rLEGCz7lcCN6biNvXk2n4TkDQHRutcQ=;
b=HJYQNR7Pnuj5wTXo8dDoVz9zfDOApakCKKfymNJNb4leg4XmHOf6qmgpj/g2v8h+1Q
QAPU6v/L0hqtbPs5YgeYeOnUkXneG1jiDI1bi2mlGBlabw6E9hov+n3FChfz3bF+B5lZ
tiCBhXhf0n0f79nbhzTz7XhBwkOnIYntAQ46P9wliuVSBYTV3jJgxZDZ27T+chA2K9OY
4nOl5GAdzaXKTqse0bSUHilxO6SAMOyeuCo3xeXgIAKuvEACj4I3Y90USLl/O7vf+0gM
Oa6ykIQfzoWBHinxk7qy/59etDC27ObXiPeOVkMTjTuyyKqgm9kbEawHgYmISESYNK+z
IWuQ==
X-Gm-Message-State: APjAAAW1hFu9J2AAGiUY14K9gMuL+6bqOC/w/bdcX9jeFPR+mWhlQ2L6
sVgLd3oGlLBKIr1/X8dv523yUF6n3kBdycZXV6Zd+3y8oAI=
X-Google-Smtp-Source: APXvYqyzvDsxC/CiSUZBcTBSQdy7nlELyg6+gPXrnU5/roEB2CqW8CdbmV9tgz9I62PQXOVaBs0mA5CNWDU4e24pMNg=
X-Received: by 2002:a5d:4146:: with SMTP id c6mr13111681wrq.205.1567913983346;
Sat, 07 Sep 2019 20:39:43 -0700 (PDT)
MIME-Version: 1.0
From: Ruben Somsen <rsomsen@gmail.com>
Date: Sun, 8 Sep 2019 05:39:28 +0200
Message-ID: <CAPv7TjaE1wF-25R=LaOES33A78ovDAp9-waiC7n5YLJnMmNs9A@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Sun, 08 Sep 2019 04:00:24 +0000
Subject: [bitcoin-dev] PoW fraud proofs without a soft fork
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: Sun, 08 Sep 2019 03:39:46 -0000
After looking more deeply into Tadge Dryja=E2=80=99s utreexo work [0], it h=
as
become clear to me that this opens up a way to implement PoW fraud
proofs [1] without a soft fork. With utreexo, we can efficiently
verify state transitions between blocks. Verifying a block from a
valid utreexo hash requires only about a megabyte worth of merkle
proofs.
PoW fraud proofs assume that block N is valid if no miner has tried to
fork it (read my original post for details [1]). We can extend that
assumption to the utreexo hash of block N, and use that to verify fork
block N+1, and reject it if the block is invalid, with just 2-3MB of
data.
For simplicity, I=E2=80=99ll first start by explaining a version with
commitments (which would require a soft fork).
When a fork (i.e. a PoW fraud proof) occurs at height N+1, indicating
that the block might be invalid, you=E2=80=99d need to download:
1. block N+1 from the most PoW chain (~1-2MB)
2. the utreexo hash commitment inside of block N (e.g. a merkle path
to the coinbase)
3. the utreexo merkle proofs which prove that all inputs of N+1 are
part of the UTXO set (~1MB)
Of course step 2 requires a soft fork, but we can also do a
non-committed version by relying on the assumption that at least one
of your peers is honest and then evaluate disagreements.
We simply replace step 2 above with the following:
2. [Download] the utreexo hash of block N from all your peers
If it turns out that one of your peers disagrees on what the correct
hash is, you find the last utreexo hash where that peer still agreed,
let=E2=80=99s say block M, and you simply execute the same three steps to f=
ind
out which peer is wrong: download block M+1, then get the merkle
proofs to verify whether the peer correctly transitioned their utreexo
hash from M to M+1.
One might intuitively feel that the lack of a commitment is unsafe,
but there seems to be no impact on security (only bandwidth). The only
way you can be fooled is if all peers lie to you (Sybil), causing you
to follow a malicious minority chain. But even full nodes (or the
committed version of PoW fraud proofs) can be fooled in this way if
they are denied access to the valid most PoW chain. If there are
additional security concerns I overlooked, I=E2=80=99d love to hear them.
In short, utreexo can enable PoW fraud proofs without a soft fork. At
the cost of downloading a couple of MB per stale block (and per
malicious peer), an SPV client gains the ability to (eventually)
reject the most PoW chain as long as one honest block gets mined,
thereby increasing its security beyond 51% honest miners.
Finally, while I think this goes without saying, I=E2=80=99d like to reiter=
ate
that this is by no means a replacement for running a full node. You=E2=80=
=99re
depending on other full nodes to do full verification and assuming at
least some of the miners are honest. If everyone did this, Bitcoin
would not be secure.
-- Ruben Somsen
[0] Utreexo paper: https://eprint.iacr.org/2019/611.pdf
[1] Improving SPV security with PoW fraud proofs:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-April/016873.h=
tml
|
