diff options
author | Mark Friedenbach <mark@monetize.io> | 2014-04-26 18:43:36 -0700 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2014-04-27 01:43:47 +0000 |
commit | 0deda1dfb74d15ac0d4509d6bbd315901985b924 (patch) | |
tree | 9aa3174819aebc0f6c4d861c9e86a0ad5ce3a8ce | |
parent | c860e5090b26f7655651b3db8899fd826693b625 (diff) | |
download | pi-bitcoindev-0deda1dfb74d15ac0d4509d6bbd315901985b924.tar.gz pi-bitcoindev-0deda1dfb74d15ac0d4509d6bbd315901985b924.zip |
Re: [Bitcoin-development] About Compact SPV proofs via block header commitments
-rw-r--r-- | d4/cbc8f17c2f0e9e65fff5874c647cf4c6812652 | 198 |
1 files changed, 198 insertions, 0 deletions
diff --git a/d4/cbc8f17c2f0e9e65fff5874c647cf4c6812652 b/d4/cbc8f17c2f0e9e65fff5874c647cf4c6812652 new file mode 100644 index 000000000..138ec70c9 --- /dev/null +++ b/d4/cbc8f17c2f0e9e65fff5874c647cf4c6812652 @@ -0,0 +1,198 @@ +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 <mark@monetize.io>) 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 <bitcoin-development@lists.sourceforge.net>; + 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 <bitcoin-development@lists.sourceforge.net> + (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 <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> +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: <bitcoin-development.lists.sourceforge.net> +List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, + <mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe> +List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development> +List-Post: <mailto:bitcoin-development@lists.sourceforge.net> +List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help> +List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, + <mailto:bitcoin-development-request@lists.sourceforge.net?subject=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 +> + + |