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
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <sergiolerner@certimix.com>) id 1WeOJF-0008Sf-3A
for bitcoin-development@lists.sourceforge.net;
Sun, 27 Apr 2014 12:35:53 +0000
X-ACL-Warn:
Received: from p3plsmtpa07-05.prod.phx3.secureserver.net ([173.201.192.234])
by sog-mx-2.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1WeOJD-0005ny-32 for bitcoin-development@lists.sourceforge.net;
Sun, 27 Apr 2014 12:35:53 +0000
Received: from [192.168.1.101] ([190.19.169.149])
by p3plsmtpa07-05.prod.phx3.secureserver.net with
id v0bj1n00B3DkUH2010bkbs; Sun, 27 Apr 2014 05:35:45 -0700
Message-ID: <535CF9BB.5010209@certimix.com>
Date: Sun, 27 Apr 2014 09:36:11 -0300
From: Sergio Lerner <sergiolerner@certimix.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
rv:17.0) Gecko/20130509 Thunderbird/17.0.6
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>
In-Reply-To: <535CA722.1000704@monetize.io>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=ISO-8859-1
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 [173.201.192.234 listed in list.dnswl.org]
X-Headers-End: 1WeOJD-0005ny-32
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 12:35:53 -0000
El 27/04/2014 03:43 a.m., Mark Friedenbach escribió:
> I don't think there's an official definition of "SPV proof." I wasn't
> trying to make a argument "from definition" (that would be fallacious!).
> Rather I suspected that we had different concepts in mind and wanted to
> check.
So to disambiguate I define the most general definition as a NPP
(non-interactive payment proof).
> 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.
If you do not make the assumption, you compute the "economic arguments"
wrong.
> Now regarding your use case:
>
>> For the remaining peers, the client starts asking for parents blocks
>> until all parents agree (this is the last common parent).
> This linear scan of block headers is what I would prefer to avoid. By
> using back-links you make it have log(N) space usage.
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.
|
