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-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1WeE8B-0003wI-0C for bitcoin-development@lists.sourceforge.net; Sun, 27 Apr 2014 01:43:47 +0000 Received: from mail-pa0-f42.google.com ([209.85.220.42]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1WeE89-00087E-LL for bitcoin-development@lists.sourceforge.net; Sun, 27 Apr 2014 01:43:46 +0000 Received: by mail-pa0-f42.google.com with SMTP id bj1so1217834pad.15 for ; Sat, 26 Apr 2014 18:43:39 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:organization:user-agent :mime-version:to:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=FgBv776a8Z4XwXGMhFzWSd+CIUUgZwZVz/LPW81PGjg=; b=kF10qvT8pa2W4cq8z6uQo4bx8MR2tfoCVzfpCIxtQUvMjuS9S8W2YaLR8S8O8+kbLx J0eVjd40qDi2/N3+LrKF3Vr0Yy+/xI4IUnKNn83E7ykMiWpKGsTPg0MPk7Kzdnq6WQLk avvLQYK6cZOtxYD6CJskZbKl9L3mf365j3Fxvws75vrYkqtRqUtpH8QTvhgBwRBaZynp NEy2rHMvpVE/J1dHdAYSvkvylRTN7nYuEE1foAgh482RNPpSGPefryE0swfCs843U5Nb XYRCeiXbKOKwBS3AnG1QXo+JxX0t4kaMtrxkw8JzN0jme7bJQ6UildJSrUud8rulh8KU eECw== X-Gm-Message-State: ALoCoQk/5GlEoX19WEVSlWo2E63yz8jK3Lkhfjw8gGaiUx0uYO3BYwoYBwQM+QZucEZ6Mkbqn3Vt X-Received: by 10.68.240.68 with SMTP id vy4mr744133pbc.127.1398563019633; Sat, 26 Apr 2014 18:43:39 -0700 (PDT) Received: from [192.168.127.239] (50-0-36-93.dsl.dynamic.sonic.net. [50.0.36.93]) by mx.google.com with ESMTPSA id su8sm25336842pbc.72.2014.04.26.18.43.38 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sat, 26 Apr 2014 18:43:38 -0700 (PDT) Message-ID: <535C60C8.5030605@monetize.io> Date: Sat, 26 Apr 2014 18:43:36 -0700 From: Mark Friedenbach 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> In-Reply-To: <535C587F.90005@certimix.com> X-Enigmail-Version: 1.6 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. X-Headers-End: 1WeE89-00087E-LL 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 01:43:47 -0000 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. The previous email you quote demonstrates how with additional backlink commitments this can be done in logarithmic space: using an average of log(N) headers to construct an SPV proof from block A to block B where N is the height differential. It can be verified without access to the block chain or other peers. Note that with back links the cost of creating a fraudulent SPV proof is the same as 51% attacking bitcoin itself. The protocol you outlined does not have this property. Other than that, honestly I'm not really sure what you are trying to accomplish. An interactive proof is does not meet the above requirements and is not usable for the driving application of two-way pegs. Maybe you had some other application in mind? I've looked at your SmartSPV proposal, but fail to see how it doesn't reduce to simply blind trust in your view of the network from your peers. SPV proofs on the other hand put an economic cost to fraud. On 04/26/2014 06:08 PM, Sergio Lerner wrote: > I read the post in this threads about Compact SPV proofs via block > header commitments (archived e-mail in > https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg04318.html). > I was working on the same problem almost at the same time, which is > something that's becoming very common nowadays.. > > The proposal starts with the following claim: > > "In simple payment verification (SPV) proofs it is currently necessary > that every intervening block header be provided between two blocks in > order to establish both connectivity and proof of work." > > I think this is false. Let's first assume that at the time of an attack > we're connected only to the attacker (no honest nodes). An > non-interactive SPV proof needs to prove that a transaction belongs to > the best chain because creating a counterfeit proof cost more than the > amount of money involved in the proof. Suppose that the proof consist at > least of a block header and a merkle branch to the claimed transaction. > > Do the proof need connectivity with the last checkpoint known by the > verifier? (here checkpoint is any block known for sure to be in the best > chain) > > Not much, because connectivity only proves that the proof was not > pre-computed before the checkpoint. Only if the checkpoint is very near > (say 10 blocks back) it brings some practical evidence that the attacker > did not have much time to prepare an attack. > > Do the proof need to know the interleaving proof-of-work? > > Not much. If the distance between blocks is less than 2016 blocks, then > the difficulty may have change only by a factor of 4. Currently > difficult adjustments are much lower (I suppose that about 1.1 or so). > Then one can assume that the proof block target difficulty is almost the > same as the last known difficulty if the block distance is less than > 2016. If the distance is more, we just load all the interleaving > re-target blocks to detect the actual difficulty. > > Do the proof need to have a certain number of confirmations? > > Yes and no, because this is the only evidence that the prover has either > spend money in creating the fake block or took a genuine block. > The cost of creating a fake block can be approximated as the minimum of: > - The current reward of the block (since currently fees are much lower > than the reward) > - The average block fees (when the reward goes to zero) > - The minimum electricity cost of mining the block. > > As time passes one could assume that the electricity cost of mining will > approach the other two. > > But there is the problem of parallel synchronized attacks: if an > attacker can reuse the same fake SPV proof to attack several victims, > then the reward for cheating increases proportionally but the cost stays > the same. > For instance, if 6 confirmations are required, and each block can hold > 2000 transactions, the attacker can find 2000 victims and re-use the > same 6 block chain to "prove" payments to 2000 victims. Also the cost of > mining 6 blocks can be amortized by mining 7, and attacking in the first > two 4000 victims, etc... > > Any scheme than relies on non-interactive SPV proofs will fail if > Bitcoin will scale up-to a point where victims can be easily found and > synchronized. > So I think one should assume that at least one peer is honest... > > But if we assume than during the attack least one peer is honest, then > we could directly ask every peer to give us the blocks of their > best-chains at the same heights of the presented proof. No back-links > are necessary. If any peer shows a different block, then we should > carefully detect which of the two nodes is the one attacking us and ban > it, by downloading the best-chain headers from the last checkpoint to > the block of the proof. This would be rare so I don't see when the > back-links can help. > > The use case should be: > > ==Use cases== > > For SPV client that has just come online asks peers what is the last block height/time. > If a peer replies with an old block, then that peer is still downloading the block-chain and it's ignored. > For the remaining peers, the client starts asking for parents blocks until all parents agree (this is the last common parent). > If (U)TxO hash-tree commitments are available, then the wallet is updated using this data from the common parent block. > > At the same time the client retrieves compact non-interactive proofs-of-inclusion (possibly orphan) for its transactions > without having to download every intervening block header. > > Is there something wrong with this? > > Best regards, > Sergio. > > ------------------------------------------------------------------------------ > 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 >