summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMark Friedenbach <mark@monetize.io>2014-04-26 18:43:36 -0700
committerbitcoindev <bitcoindev@gnusha.org>2014-04-27 01:43:47 +0000
commit0deda1dfb74d15ac0d4509d6bbd315901985b924 (patch)
tree9aa3174819aebc0f6c4d861c9e86a0ad5ce3a8ce
parentc860e5090b26f7655651b3db8899fd826693b625 (diff)
downloadpi-bitcoindev-0deda1dfb74d15ac0d4509d6bbd315901985b924.tar.gz
pi-bitcoindev-0deda1dfb74d15ac0d4509d6bbd315901985b924.zip
Re: [Bitcoin-development] About Compact SPV proofs via block header commitments
-rw-r--r--d4/cbc8f17c2f0e9e65fff5874c647cf4c6812652198
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
+>
+
+