From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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.