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
|
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 171DCB19
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 4 Jul 2015 17:58:48 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qk0-f174.google.com (mail-qk0-f174.google.com
[209.85.220.174])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7FE3C1AC
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 4 Jul 2015 17:58:47 +0000 (UTC)
Received: by qkhu186 with SMTP id u186so91695618qkh.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 04 Jul 2015 10:58:46 -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=/JbfM8Ev3Pj9V5RmmNUP3N7h4gTZM3eIXCou1UN/R+8=;
b=0BsnLts8Lmfs2nz09irbArFomrecNYFXdAup4lxQu3PC6XZTTHyV4gyjLtgeVPavyr
kDs1TCqyWBOs2J9DD8rhGyfY7dLhTCuz3XaNY535oY+OJ8kuCf026V31mc3w3tPLG+T/
6jmAK8tzcFff5uukK5Lst2CmB7U038b6Z61cAJduLg9FljQoIHTBBci1P5jFGrClLf0l
2Vp3HdoETwH2Yb/qokUchf342CGj01u7B8hcHh0MCzQ8ZRwjV9rdN0zNb77ZMikX+1Bs
qSiXGtc516BLO5+LPTQG7mgSsZzJiNturCgVa1xsGJmEFiFY4Uccp9N1D7TkNvKKNxsB
wt0Q==
MIME-Version: 1.0
X-Received: by 10.55.33.213 with SMTP id f82mr81393985qki.107.1436032726756;
Sat, 04 Jul 2015 10:58:46 -0700 (PDT)
Received: by 10.140.93.162 with HTTP; Sat, 4 Jul 2015 10:58:46 -0700 (PDT)
In-Reply-To: <55980361.9040707@openbitcoinprivacyproject.org>
References: <COL402-EAS195B72E1CF2B75999C1AB11CD950@phx.gbl>
<20150704054453.GA348@savin.petertodd.org>
<5597F93B.3000205@openbitcoinprivacyproject.org>
<CAE-z3OWTzgYP7CKbFLf-YFKU+G6CNKND2DmAbnr_3_NjB-Y4fw@mail.gmail.com>
<55980361.9040707@openbitcoinprivacyproject.org>
Date: Sat, 4 Jul 2015 18:58:46 +0100
Message-ID: <CAE-z3OXZDh=ww33Qr6yGxzm3rzquiP0LNo6yQzL1si+-dr3a_g@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a1140021690706f051a106c32
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 17:58:48 -0000
--001a1140021690706f051a106c32
Content-Type: text/plain; charset=UTF-8
On Sat, Jul 4, 2015 at 5:01 PM, Justus Ranvier <
justus@openbitcoinprivacyproject.org> wrote:
> How do we know if a committed UTXO set is valid? If a majority of the
> hashing power is willing to extend an invalid branch, it's reasonable to
> assume they'd be willing to commit an invalid UTXO set as well.
>
You can prove that it wasn't updated correctly.
For each transaction, the UTXO tree root before and after is committed.
You show the root before, and the root after and show that the after root
is wrong. You also need to include some merkle paths to prove the
transform.
> If items in the the proof tree are required to be sorted, then it's easy
> to proof that an item is missing.
>
Yes, you can mostly get short proofs for each step, but you have to make
sure your proofs are also provable.
It means going through everything that needs to be proved for a block to be
valid.
--001a1140021690706f051a106c32
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Sat, Jul 4, 2015 at 5:01 PM, Justus Ranvier <span dir=3D"ltr"><<a=
href=3D"mailto:justus@openbitcoinprivacyproject.org" target=3D"_blank">jus=
tus@openbitcoinprivacyproject.org</a>></span> wrote:<br><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex"><span class=3D"">
</span>How do we know if a committed UTXO set is valid? If a majority of th=
e<br>
hashing power is willing to extend an invalid branch, it's reasonable t=
o<br>
assume they'd be willing to commit an invalid UTXO set as well.<br></bl=
ockquote><div><br></div><div>You can prove that it wasn't updated corre=
ctly.<br><br></div><div>For each transaction, the UTXO tree root before and=
after is committed.<br><br></div><div>You show the root before, and the ro=
ot after and show that the after root is wrong.=C2=A0 You also need to incl=
ude some merkle paths to prove the transform.<br></div><div>=C2=A0<br></div=
><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1=
px #ccc solid;padding-left:1ex"><span class=3D"">
</span>If items in the the proof tree are required to be sorted, then it=
9;s easy<br>
to proof that an item is missing.<br></blockquote><div><br></div><div>Yes, =
you can mostly get short proofs for each step, but you have to make sure yo=
ur proofs are also provable.<br><br></div><div>It means going through every=
thing that needs to be proved for a block to be valid.<br></div></div></div=
></div>
--001a1140021690706f051a106c32--
|
