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>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Subject: Re: [Bitcoin-development] About Compact SPV proofs via block header
 commitments
Precedence: list

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.