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
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <mark@monetize.io>) id 1WeSWY-0007Pn-UU
for bitcoin-development@lists.sourceforge.net;
Sun, 27 Apr 2014 17:05:54 +0000
Received: from mail-pd0-f174.google.com ([209.85.192.174])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1WeSWX-0004gR-Pa
for bitcoin-development@lists.sourceforge.net;
Sun, 27 Apr 2014 17:05:54 +0000
Received: by mail-pd0-f174.google.com with SMTP id z10so4088004pdj.33
for <bitcoin-development@lists.sourceforge.net>;
Sun, 27 Apr 2014 10:05:47 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:message-id:date:from:organization:user-agent
:mime-version:to:subject:references:in-reply-to:content-type
:content-transfer-encoding;
bh=454oF8tZ+Gmo6VHckHDDRhgYlG7ze3f4BX/YX5wQtvA=;
b=Pspq730k5y0n4M9ZEpssOz8Ip1UZcrzBeTrwInMHfbFq1kt+clhLAqk0P8Gded3ISL
DmiRNHEzcc8xLZUHnG8EKn5ovtJU6ETJX4/Q1mdEGbIty3J6h5dXKRt4pFDUWjs2gCb5
hhnH++hhhjPYp2C/WATHRVAu2sxD9m/VS2m5Zi+Svof2jAQVIA2hJixKfZJZVKjRlru3
wuAwe7b2VxPxFKNpBRsn6RdKz04uoO+mB8oG3LYGHlxoR5uHz94JuJrqI9DTO0eBwiBG
uirRlxjadURVhWDPBMooQUknYlCrlqY9M3nJIFmdtfyPnw7mHdQmlvSowMcEz4sICzOz
xrNQ==
X-Gm-Message-State: ALoCoQmEtiW9EmM95ZSZCCewV+xRjPLAOnE+9jLfAIr1eek/QYRy7jLQjCLMauekwcC+mmUcZqrO
X-Received: by 10.68.103.165 with SMTP id fx5mr24078921pbb.118.1398618347798;
Sun, 27 Apr 2014 10:05:47 -0700 (PDT)
Received: from [192.168.127.194] (50-0-36-93.dsl.dynamic.sonic.net.
[50.0.36.93]) by mx.google.com with ESMTPSA id
xk3sm29405308pbb.65.2014.04.27.10.05.46
for <bitcoin-development@lists.sourceforge.net>
(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Sun, 27 Apr 2014 10:05:47 -0700 (PDT)
Message-ID: <535D38E9.60209@monetize.io>
Date: Sun, 27 Apr 2014 10:05:45 -0700
From: Mark Friedenbach <mark@monetize.io>
Organization: Monetize.io Inc.
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:24.0) Gecko/20100101 Thunderbird/24.4.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <535C587F.90005@certimix.com>
<535C60C8.5030605@monetize.io> <535C6DEC.9040505@certimix.com>
<535CA722.1000704@monetize.io> <535CF9BB.5010209@certimix.com>
In-Reply-To: <535CF9BB.5010209@certimix.com>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 8bit
X-Spam-Score: 0.0 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/,
no trust [209.85.192.174 listed in list.dnswl.org]
X-Headers-End: 1WeSWX-0004gR-Pa
Subject: Re: [Bitcoin-development] About Compact SPV proofs via block header
commitments
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sun, 27 Apr 2014 17:05:55 -0000
On 04/27/2014 05:36 AM, Sergio Lerner wrote:
>> Without invoking moon math or assumptions of honest peers and
>> jamming-free networks, the only way to know a chain is valid is to
>> witness the each and every block. SPV nodes on the other hand,
>> simply trust that the most-work chain is a valid chain, based on
>> economic arguments about the opportunity cost of mining invalid
>> blocks.
> I argue that you cannot talk about "the most-work chain" without
> actually making an assumption about honest peers.
I should have said "without invoking moon math or interactive protocols
requiring honest peers over jamming-free networks." The interactive
protocol was more the point than the honest peers and jamming-free
network. Yes, without an honest peer and an un-jammed network, you might
never learn about the most-work chain in the first place. But having the
security of the proof not depend on query access to an honest full node
is absolutely necessary for some applications and certainly desirable in
others.
Although strictly speaking what I said may not be 100% true. The single
alternative solution I've seen involves some sort of Fiat–Shamir
transform that could give you a probabilistic proof by including random
additional paths through the block chain chosen based on the combined
hash of the headers. However this is disadvantageous as it massively
increases the proof size and verification time, and you have to include
a lot of data to achieve assurance that more work was required to
generate the fraud than an honest chain.
> If you do not make the assumption, you compute the "economic
> arguments" wrong.
Not necessarily. By requiring connectivity you know that what you are
receiving is built off of the main chain, for example, and you can still
make assumptions about resulting opportunity costs.
> First this is a method that uses NPPs, not SPV proofs. Since the
> method chooses all peers that are synchronized (have the latest
> current block) then going back means only skipping a potential short
> fork (which I suppose has never been more than 3 blocks during normal
> network conditions). You're looking for a common ancestor, not the
> checkpoint. So the linear scan is actually O(1). The exact value can
> be approximated by the sum of the convergent infinite geometrical
> sequence of forking probabilities, which it's about 1.03 without
> considering selfish-mining, and probably less than 2.03 considering
> it.
Unless you're connected to attacker nodes which are wildly divergent
from each other. It's relatively easy to create a massive fake history
of difficulty-1 blocks.
If you assume honest peers things get very easy. But that's not a safe
assumption to be making. With back-link block-history commitments, on
the other hand, an interactive protocol allows you to do a binary search
to find common ancestors, and have trust that the intermediate links
actually exist.
|
