public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Sergio Lerner <sergiolerner@certimix.com>
To: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] About Compact SPV proofs via block header commitments
Date: Sun, 27 Apr 2014 09:36:11 -0300	[thread overview]
Message-ID: <535CF9BB.5010209@certimix.com> (raw)
In-Reply-To: <535CA722.1000704@monetize.io>

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.

 



  reply	other threads:[~2014-04-27 12:35 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-04-27  1:08 [Bitcoin-development] About Compact SPV proofs via block header commitments Sergio Lerner
2014-04-27  1:43 ` Mark Friedenbach
2014-04-27  2:39   ` Sergio Lerner
2014-04-27  6:43     ` Mark Friedenbach
2014-04-27 12:36       ` Sergio Lerner [this message]
2014-04-27 17:05         ` Mark Friedenbach
2014-04-28 14:32           ` Sergio Lerner
2014-04-28 17:29             ` Mark Friedenbach

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=535CF9BB.5010209@certimix.com \
    --to=sergiolerner@certimix.com \
    --cc=bitcoin-development@lists.sourceforge.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox