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: <tier.nolan@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 6EE81AC2
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 4 Jul 2015 15:35:51 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qk0-f171.google.com (mail-qk0-f171.google.com
[209.85.220.171])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A5BD4192
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 4 Jul 2015 15:35:50 +0000 (UTC)
Received: by qkei195 with SMTP id i195so90417267qke.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 04 Jul 2015 08:35:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:cc
:content-type; bh=S0EtoGxohgrKXM7oAYdn5hJVH8VUCpdgnfhdf25u8iQ=;
b=0HdF1P2/n8Ga5/RFkIj5wUhl9oHnbUGk4YWFEyOegE7+XujJNCmyjFm8Xgp+lJhvML
dIAk4tGMMrHaaCXhxUauZecVqyyRudqzU/q95nIFOJ02SEEqHa/86+LDaXbinOgRRwjR
viAV3KCFPc3E2zskhPR9ol4pQ1S6zz96yQ+RY2k8VGl103YM38YjTJ8cj9+4jT/H/zQ2
cSCwyi0eKV/53PWQY1aT/StA/dpFcKMsd4LvHC5jmhqRw8ON2INEfU2UoVIkZDhd2gkv
LlsDU6sTLvVoDOmYHp/aHLXPYOV2EmoW1bE0sR4msm1T7smVv4J+R1wpECfF0krzXZqs
P3iA==
MIME-Version: 1.0
X-Received: by 10.140.238.15 with SMTP id j15mr63289740qhc.4.1436024149893;
Sat, 04 Jul 2015 08:35:49 -0700 (PDT)
Received: by 10.140.93.162 with HTTP; Sat, 4 Jul 2015 08:35:49 -0700 (PDT)
In-Reply-To: <5597F93B.3000205@openbitcoinprivacyproject.org>
References: <COL402-EAS195B72E1CF2B75999C1AB11CD950@phx.gbl>
<20150704054453.GA348@savin.petertodd.org>
<5597F93B.3000205@openbitcoinprivacyproject.org>
Date: Sat, 4 Jul 2015 16:35:49 +0100
Message-ID: <CAE-z3OWTzgYP7CKbFLf-YFKU+G6CNKND2DmAbnr_3_NjB-Y4fw@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a1135b6f257e625051a0e6d50
X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,MISSING_HEADERS,
RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations
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: Sat, 04 Jul 2015 15:35:51 -0000
--001a1135b6f257e625051a0e6d50
Content-Type: text/plain; charset=UTF-8
On Sat, Jul 4, 2015 at 4:18 PM, Justus Ranvier <
justus@openbitcoinprivacyproject.org> wrote:
> In general, the situation can be improved if there existed proofs which
> validating full nodes could broadcast which would tell SPV nodes why the
> branch it sees with the most proof of work is actually invalid.
>
Yeah, fraud proofs have been suggested lots of times in the past.
In this case, they weren't even needed. Fully updated SPV clients should
also have rejected the invalid fork. All the information required to
reject it was in the header chain.
The problem wasn't SPV miners, it was SPV-miners where the SPV part wasn't
upgraded to handle v3 blocks.
> As far as I can tell, producing such proofs is reasonably
> straightforward for all cases except the case where a block is invalid
> because it contains a transaction which references a non-existent output.
>
Even that can be handled with UTXO set commitments. If the UTXO tree is
sorted you can prove that an entry doesn't exist.
What cannot be handled is proving that a block is invalid if the
transaction data for the block is withheld.
> If each transaction input identified the block containing the referenced
> outpoint, then the proof of non-existence is either the block in
> question, or the list of block headers (to show that the block doesn't
> exist). That's a significant improvement in proof size over the entire
> blockchain.
>
That is reasonable. Unconfirmed transactions can't include that info
though.
It could be committed in as an extra commitment.
One issue is that you need to prove of of these commitments too.
A transaction which points to the wrong block would also be provable in the
same way.
> Proving the non-existence of a particular transaction in a specific
> block could be made easier for future blocks by requiring transactions
> to be ordered in the merkle tree by their hashes. Then it would just
> require a few nodes in the tree to show that the transaction isn't in
> the place where it should be.
>
You could just have an extra merkle tree.
You would only need to include the block hashes for all transactions to
show that the two trees don't match. That is 32 bytes per transaction
rather than the full 200-500 bytes per transaction.
--001a1135b6f257e625051a0e6d50
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On S=
at, Jul 4, 2015 at 4:18 PM, Justus Ranvier <span dir=3D"ltr"><<a href=3D=
"mailto:justus@openbitcoinprivacyproject.org" target=3D"_blank">justus@open=
bitcoinprivacyproject.org</a>></span> wrote:<br><blockquote class=3D"gma=
il_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-lef=
t:1ex"><span class=3D"">
</span>In general, the situation can be improved if there existed proofs wh=
ich<br>
validating full nodes could broadcast which would tell SPV nodes why the<br=
>
branch it sees with the most proof of work is actually invalid.<br></blockq=
uote><div><br></div><div>Yeah, fraud proofs have been suggested lots of tim=
es in the past.<br><br></div><div>In this case, they weren't even neede=
d.=C2=A0 Fully updated SPV clients should also have rejected the invalid fo=
rk.=C2=A0 All the information required to reject it was in the header chain=
.<br><br></div><div>The problem wasn't SPV miners, it was SPV-miners wh=
ere the SPV part wasn't upgraded to handle v3 blocks.<br></div><div>=C2=
=A0<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;b=
order-left:1px #ccc solid;padding-left:1ex">
As far as I can tell, producing such proofs is reasonably<br>
straightforward for all cases except the case where a block is invalid<br>
because it contains a transaction which references a non-existent output.<b=
r></blockquote><div><br></div><div>Even that can be handled with UTXO set c=
ommitments.=C2=A0 If the UTXO tree is sorted you can prove that an entry do=
esn't exist.<br><br></div><div>What cannot be handled is proving that a=
block is invalid if the transaction data for the block is withheld.<br></d=
iv><div>=C2=A0<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0=
0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If each transaction input identified the block containing the referenced<br=
>
outpoint, then the proof of non-existence is either the block in<br>
question, or the list of block headers (to show that the block doesn't<=
br>
exist). That's a significant improvement in proof size over the entire<=
br>
blockchain.<br></blockquote><div><br></div><div>That is reasonable.=C2=A0 U=
nconfirmed transactions can't include that info though.<br><br></div><d=
iv>It could be committed in as an extra commitment.<br><br></div><div>One i=
ssue is that you need to prove of of these commitments too.<br><br></div><d=
iv>A transaction which points to the wrong block would also be provable in =
the same way.<br></div><div>=C2=A0<br></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Proving the non-existence of a particular transaction in a specific<br>
block could be made easier for future blocks by requiring transactions<br>
to be ordered in the merkle tree by their hashes.=C2=A0 Then it would just<=
br>
require a few nodes in the tree to show that the transaction isn't in<b=
r>
the place where it should be.<br></blockquote><div><br></div><div>You could=
just have an extra merkle tree.<br><br></div><div>You would only need to i=
nclude the block hashes for all transactions to show that the two trees don=
't match.=C2=A0 That is 32 bytes per transaction rather than the full 2=
00-500 bytes per transaction.<br></div></div></div></div>
--001a1135b6f257e625051a0e6d50--
|
