summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndrew Miller <amiller@cs.ucf.edu>2012-06-19 12:46:52 -0400
committerbitcoindev <bitcoindev@gnusha.org>2012-06-19 16:47:01 +0000
commit2dc9b5665b7605b8be43e91b74c5e0bf68c20049 (patch)
tree1bb101243187d8f81f73d66daefac5854f64cfff
parenta5d66bb1f2bb608eb8cb6414b5eff517df83959c (diff)
downloadpi-bitcoindev-2dc9b5665b7605b8be43e91b74c5e0bf68c20049.tar.gz
pi-bitcoindev-2dc9b5665b7605b8be43e91b74c5e0bf68c20049.zip
Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node
-rw-r--r--1b/7ea6981d8474a5ed230a8ea5a72d3170151b7e108
1 files changed, 108 insertions, 0 deletions
diff --git a/1b/7ea6981d8474a5ed230a8ea5a72d3170151b7e b/1b/7ea6981d8474a5ed230a8ea5a72d3170151b7e
new file mode 100644
index 000000000..afb685957
--- /dev/null
+++ b/1b/7ea6981d8474a5ed230a8ea5a72d3170151b7e
@@ -0,0 +1,108 @@
+Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
+ helo=mx.sourceforge.net)
+ by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
+ (envelope-from <socrates1024@gmail.com>) id 1Sh1a1-0000Ro-JA
+ for Bitcoin-development@lists.sourceforge.net;
+ Tue, 19 Jun 2012 16:47:01 +0000
+Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
+ designates 74.125.82.175 as permitted sender)
+ client-ip=74.125.82.175; envelope-from=socrates1024@gmail.com;
+ helo=mail-we0-f175.google.com;
+Received: from mail-we0-f175.google.com ([74.125.82.175])
+ by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
+ (Exim 4.76) id 1Sh1Zy-0004Af-F9
+ for Bitcoin-development@lists.sourceforge.net;
+ Tue, 19 Jun 2012 16:47:01 +0000
+Received: by werg55 with SMTP id g55so5216936wer.34
+ for <Bitcoin-development@lists.sourceforge.net>;
+ Tue, 19 Jun 2012 09:46:52 -0700 (PDT)
+MIME-Version: 1.0
+Received: by 10.180.94.4 with SMTP id cy4mr4901249wib.2.1340124412181; Tue, 19
+ Jun 2012 09:46:52 -0700 (PDT)
+Sender: socrates1024@gmail.com
+Received: by 10.217.2.207 with HTTP; Tue, 19 Jun 2012 09:46:52 -0700 (PDT)
+Date: Tue, 19 Jun 2012 12:46:52 -0400
+X-Google-Sender-Auth: xRkqSG3FKtSodSxG-I6fV-SpS24
+Message-ID: <CAF7tpEyEWCbcB+jSpWOMyeZUBjQ=FbVEC8kLt3j2Yzv3YJOgiA@mail.gmail.com>
+From: Andrew Miller <amiller@cs.ucf.edu>
+To: Bitcoin-development@lists.sourceforge.net
+Content-Type: text/plain; charset=ISO-8859-1
+X-Spam-Score: -1.2 (-)
+X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
+ See http://spamassassin.org/tag/ for more details.
+ -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
+ sender-domain
+ 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
+ (socrates1024[at]gmail.com)
+ -0.0 SPF_PASS SPF: sender matches SPF record
+ 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in
+ digit (socrates1024[at]gmail.com)
+ 0.1 DKIM_SIGNED Message has a DKIM or DK signature,
+ not necessarily valid
+ -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
+X-Headers-End: 1Sh1Zy-0004Af-F9
+Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/
+ trust-free lite node
+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: Tue, 19 Jun 2012 16:47:01 -0000
+
+> Peter Todd wrote:
+> My solution was to simply state that vertexes that happened to cause the
+> tree to be unbalanced would be discarded, and set the depth of inbalance
+> such that this would be extremely unlikely to happen by accident. I'd
+> rather see someone come up with something better though.
+
+Here is a simpler solution. (most of this message repeats the content
+of my reply to the forum)
+
+Suppose we were talking about a binary search tree, rather than a
+Merkle tree. It's important to balance a binary search tree, so that
+the worst-case maximum length from the root to a leaf is bounded by
+O(log N). AVL trees were the original algorithm to do this, Red-Black
+trees are also popular, and there are many similar methods. All
+involve storing some form of 'balancing metadata' at each node. In a
+RedBlack tree, this is a single bit (red or black). Every operation on
+these trees, including search, inserting, deleting, and rebalancing,
+requires a worst-case effort of O(log N).
+
+Any (acyclic) recursive data structure can be Merkle-ized, simply by
+adding a hash of the child node alongside each link/pointer. This way,
+you can verify the data for each node very naturally, as you traverse
+the structure.
+
+In fact, as long as a lite-client knows the O(1) root hash, the rest
+of the storage burden can be delegated to an untrusted helper server.
+Suppose a lite-client wants to insert and rebalance its tree. This
+requires accessing at most O(log N) nodes. The client can request only
+the data relevant to these nodes, and it knows the hash for each chunk
+of data in advance of accessing it. After computing the updated root
+hash, the client can even discard the data it processed.
+
+This technique has been well discussed in the academic literature,
+e.g. [1,2], although since I am not aware of any existing
+implementation, I made my own, intended as an explanatory aid:
+https://github.com/amiller/redblackmerkle/blob/master/redblack.py
+
+
+[1] Certificate Revocation and Update
+ Naor and Nissim. 1998
+ http://static.usenix.org/publications/library/proceedings/sec98/full_papers/nissim/nissim.pdf
+
+[2] A General Model for Authenticated Data Structures
+ Martel, Nuckolls, Devanbu, Michael Gertz, Kwong, Stubblebine. 2004
+ http://truthsayer.cs.ucdavis.edu/algorithmica.pdf
+
+--
+Andrew Miller
+
+