diff options
author | Andrew Miller <amiller@cs.ucf.edu> | 2012-06-19 12:46:52 -0400 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2012-06-19 16:47:01 +0000 |
commit | 2dc9b5665b7605b8be43e91b74c5e0bf68c20049 (patch) | |
tree | 1bb101243187d8f81f73d66daefac5854f64cfff | |
parent | a5d66bb1f2bb608eb8cb6414b5eff517df83959c (diff) | |
download | pi-bitcoindev-2dc9b5665b7605b8be43e91b74c5e0bf68c20049.tar.gz pi-bitcoindev-2dc9b5665b7605b8be43e91b74c5e0bf68c20049.zip |
Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node
-rw-r--r-- | 1b/7ea6981d8474a5ed230a8ea5a72d3170151b7e | 108 |
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 + + |