Message-ID: <535CA722.1000704@monetize.io>
Date: Sat, 26 Apr 2014 23:43:46 -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>
In-Reply-To: <535C6DEC.9040505@certimix.com>
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

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.

That said, I do think that the definition I gave matches how the term is
used in the Satoshi whitepaper, and the way in which SPV clients like
BitcoinJ work. "Best chain" is typically taken to mean the most-work,
*valid* chain. 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. These SPV
nodes use block headers as proofs to determine the most-work block
connected to the genesis block or most recent checkpoint. So yes,
operationally at least this is what the community seems to mean by "SPV
proof".

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.

On 04/26/2014 07:39 PM, Sergio Lerner wrote:
> El 26/04/2014 10:43 p.m., Mark Friedenbach escribió:
>> Sergio,
>> 
>> First of all, let's define what an SPV proof is: it is a succinct 
>> sequence of bits which can be transmitted as part of a 
>> non-interactive protocol that convincingly establishes for a
>> client without access to the block chain that for some block B, B
>> has an ancestor A at some specified height and work distance back,
>> and the cost of creating a false proof is at least as much work as
>> it claims to represent.
> Ok. I was thinking with another definition SPV proof.
> 
> For me a SPV proof is a sequence of bits which can be transmitted as
>  part of a non-interactive protocol that convincingly establishes
> for a client without access to the block chain that a block B is part
> of the best-chain.
> 
> I understand that SPV nodes require SPV proofs as defined in my 
> definition, but I can't realize how to prove that SPV nodes require 
> SPV proofs under your definition. So your definition sounds to me 
> like one possible solution, but not the need.
> 
> Is your definition something well-established in the community?
> 
> 
> 
> 
> ------------------------------------------------------------------------------
>
>
> 
Start Your Social Network Today - Download eXo Platform
> Build your Enterprise Intranet with eXo Platform Software Java Based 
> Open Source Intranet - Social, Extensible, Cloud Ready Get Started 
> Now And Turn Your Intranet Into A Collaboration Platform 
> http://p.sf.net/sfu/ExoPlatform 
> _______________________________________________ Bitcoin-development 
> mailing list Bitcoin-development@lists.sourceforge.net 
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>