summaryrefslogtreecommitdiff
path: root/3c
diff options
context:
space:
mode:
authorAlan Reiner <etotheipi@gmail.com>2012-06-19 14:30:16 -0400
committerbitcoindev <bitcoindev@gnusha.org>2012-06-19 18:30:45 +0000
commitbf805c7c1a4ff7beee494b4c5bcafca0fa6fd543 (patch)
tree6cf1325c60e3555bec7edbd3368853ad7c12e1ac /3c
parent7c1600af9a906589a58e84799faa19dacda59566 (diff)
downloadpi-bitcoindev-bf805c7c1a4ff7beee494b4c5bcafca0fa6fd543.tar.gz
pi-bitcoindev-bf805c7c1a4ff7beee494b4c5bcafca0fa6fd543.zip
Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node
Diffstat (limited to '3c')
-rw-r--r--3c/8c5887b9883ef3682f8b7c4b10d94cd60cf7f3216
1 files changed, 216 insertions, 0 deletions
diff --git a/3c/8c5887b9883ef3682f8b7c4b10d94cd60cf7f3 b/3c/8c5887b9883ef3682f8b7c4b10d94cd60cf7f3
new file mode 100644
index 000000000..cacf09722
--- /dev/null
+++ b/3c/8c5887b9883ef3682f8b7c4b10d94cd60cf7f3
@@ -0,0 +1,216 @@
+Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
+ helo=mx.sourceforge.net)
+ by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
+ (envelope-from <etotheipi@gmail.com>) id 1Sh3CP-0005Z6-F5
+ for bitcoin-development@lists.sourceforge.net;
+ Tue, 19 Jun 2012 18:30:45 +0000
+Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
+ designates 209.85.213.47 as permitted sender)
+ client-ip=209.85.213.47; envelope-from=etotheipi@gmail.com;
+ helo=mail-yw0-f47.google.com;
+Received: from mail-yw0-f47.google.com ([209.85.213.47])
+ by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-MD5:128)
+ (Exim 4.76) id 1Sh3CO-0008UN-Ng
+ for bitcoin-development@lists.sourceforge.net;
+ Tue, 19 Jun 2012 18:30:45 +0000
+Received: by yhjj56 with SMTP id j56so5258909yhj.34
+ for <bitcoin-development@lists.sourceforge.net>;
+ Tue, 19 Jun 2012 11:30:39 -0700 (PDT)
+Received: by 10.236.74.133 with SMTP id x5mr23653316yhd.126.1340130639286;
+ Tue, 19 Jun 2012 11:30:39 -0700 (PDT)
+Received: from [192.168.1.85] (c-76-111-96-126.hsd1.md.comcast.net.
+ [76.111.96.126])
+ by mx.google.com with ESMTPS id g4sm82399900yhf.12.2012.06.19.11.30.38
+ (version=SSLv3 cipher=OTHER); Tue, 19 Jun 2012 11:30:38 -0700 (PDT)
+Message-ID: <4FE0C538.3090001@gmail.com>
+Date: Tue, 19 Jun 2012 14:30:16 -0400
+From: Alan Reiner <etotheipi@gmail.com>
+User-Agent: Mozilla/5.0 (X11; Linux i686 on x86_64;
+ rv:12.0) Gecko/20120428 Thunderbird/12.0.1
+MIME-Version: 1.0
+To: Mark Friedenbach <mark@monetize.io>
+References: <CAF7tpEyEWCbcB+jSpWOMyeZUBjQ=FbVEC8kLt3j2Yzv3YJOgiA@mail.gmail.com>
+ <4FE0B7EB.6000100@gmail.com>
+ <CACh7GpEehHFEJGRTtijgM7UAa2jeEWRKrQo5dym8F_YgXAEhFA@mail.gmail.com>
+In-Reply-To: <CACh7GpEehHFEJGRTtijgM7UAa2jeEWRKrQo5dym8F_YgXAEhFA@mail.gmail.com>
+Content-Type: multipart/alternative;
+ boundary="------------040508030500040107050704"
+X-Spam-Score: -0.8 (/)
+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
+ (etotheipi[at]gmail.com)
+ -0.0 SPF_PASS SPF: sender matches SPF record
+ 1.0 HTML_MESSAGE BODY: HTML included in message
+ -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
+ author's domain
+ 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
+ -0.2 AWL AWL: From: address is in the auto white-list
+X-Headers-End: 1Sh3CO-0008UN-Ng
+Cc: bitcoin-development@lists.sourceforge.net
+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 18:30:45 -0000
+
+This is a multi-part message in MIME format.
+--------------040508030500040107050704
+Content-Type: text/plain; charset=UTF-8; format=flowed
+Content-Transfer-Encoding: 7bit
+
+On 06/19/2012 02:18 PM, Mark Friedenbach wrote:
+> On Tue, Jun 19, 2012 at 10:33 AM, Alan Reiner <etotheipi@gmail.com
+> <mailto:etotheipi@gmail.com>> wrote:
+>
+> If we were to use a raw trie structure, then we'd have all the above
+> issues solved: a trie has the same configuration no matter how
+> elements
+> are inserted or deleted, and accesses to elements in the tree are
+> constant time -- O(1). There is no such thing as an unbalanced trie.
+> But overall space-efficiency is an issue.
+>
+> A PATRICIA tree/trie would be ideal, in my mind, as it also has a
+> completely deterministic structure, and is an order-of-magnitude more
+> space-efficient. Insert, delete and query times are still O(1).
+> However, it is not a trivial implementation. I have occasionally
+> looked
+> for implementations, but not found any that were satisfactory.
+>
+>
+> No, a trie of any sort is dependent upon distribution of input data
+> for balancing. As Peter Todd points out, a malicious actor could
+> construct transaction or address hashes in such a way as to grow some
+> segment of the trie in an unbalanced fashion. It's not much of an
+> attack, but in principle exploitable under particular timing-sensitive
+> circumstances.
+>
+> Self-balancing search trees (KVL, RB, 2-3-4, whatever) don't suffer
+> from this problem.
+>
+> Mark
+
+I was using "unbalanced" to refer to "query time" (and also
+insert/delete time). If your trie nodes branch based on the next byte
+of your key hash, then the max depth of your trie is 32. Period. No
+one can do anything to ever make you do more than 32 hops to
+find/insert/delete your data. And if you're using a raw trie, you'll
+always use /exactly/ 32 hops regardless of the distribution of the
+underlying data. Hence, the trie structure is deterministic
+(history-independent) and cannot become unbalanced in terms of access time.
+
+My first concern was that a malicious actor could linearize parts of the
+tree and cause access requests to take much longer than log(N) time.
+With the trie, that's not only impossible, you're actually accessing in
+O(1) time.
+
+However, you are right that disk space can be affected by a malicious
+actor. The more branching he can induce, the more branch nodes that are
+created to support branches with only one leaf.
+
+
+
+--------------040508030500040107050704
+Content-Type: text/html; charset=UTF-8
+Content-Transfer-Encoding: 8bit
+
+<html>
+ <head>
+ <meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
+ </head>
+ <body text="#000000" bgcolor="#FFFFFF">
+ On 06/19/2012 02:18 PM, Mark Friedenbach wrote:
+ <blockquote
+cite="mid:CACh7GpEehHFEJGRTtijgM7UAa2jeEWRKrQo5dym8F_YgXAEhFA@mail.gmail.com"
+ type="cite">
+ <div class="gmail_quote">On Tue, Jun 19, 2012 at 10:33 AM, Alan
+ Reiner <span dir="ltr">&lt;<a moz-do-not-send="true"
+ href="mailto:etotheipi@gmail.com" target="_blank">etotheipi@gmail.com</a>&gt;</span>
+ wrote:<br>
+ <br>
+ <blockquote class="gmail_quote" style="margin:0 0 0
+ .8ex;border-left:1px #ccc solid;padding-left:1ex">
+ If we were to use a raw trie structure, then we'd have all the
+ above<br>
+ issues solved:  a trie has the same configuration no matter
+ how elements<br>
+ are inserted or deleted, and accesses to elements in the tree
+ are<br>
+ constant time -- O(1).  There is no such thing as an
+ unbalanced trie.<br>
+ But overall space-efficiency is an issue.<br>
+ <br>
+ A PATRICIA tree/trie would be ideal, in my mind, as it also
+ has a<br>
+ completely deterministic structure, and is an
+ order-of-magnitude more<br>
+ space-efficient.  Insert, delete and query times are still
+ O(1).<br>
+ However, it is not a trivial implementation.  I have
+ occasionally looked<br>
+ for implementations, but not found any that were satisfactory.<br>
+ </blockquote>
+ <div><br>
+ </div>
+ <div>No, a trie of any sort is dependent upon distribution of
+ input data for balancing. As <span class="Apple-style-span"
+style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px">Peter
+ Todd points out, a malicious actor could construct
+ transaction or address hashes in such a way as to grow some
+ segment of the trie in an unbalanced fashion. It's not much
+ of an attack, but in principle exploitable under particular
+ timing-sensitive circumstances.</span></div>
+ <div><span class="Apple-style-span"
+style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px"><br>
+ </span></div>
+ <div><span class="Apple-style-span"
+style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px">Self-balancing
+ search trees (KVL, RB, 2-3-4, whatever) don't suffer from
+ this problem.</span></div>
+ <div><span class="Apple-style-span"
+style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px"><br>
+ </span></div>
+ <div><span class="Apple-style-span"
+style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px">Mark</span></div>
+ </div>
+ </blockquote>
+ <br>
+ I was using "unbalanced" to refer to "query time" (and also
+ insert/delete time).  If your trie nodes branch based on the next
+ byte of your key hash, then the max depth of your trie is 32. 
+ Period.  No one can do anything to ever make you do more than 32
+ hops to find/insert/delete your data.   And if you're using a raw
+ trie, you'll always use <i>exactly</i> 32 hops regardless of the
+ distribution of the underlying data.  Hence, the trie structure is
+ deterministic (history-independent) and cannot become unbalanced in
+ terms of access time.<br>
+ <br>
+ My first concern was that a malicious actor could linearize parts of
+ the tree and cause access requests to take much longer than log(N)
+ time.  With the trie, that's not only impossible, you're actually
+ accessing in O(1) time.<br>
+ <br>
+ However, you are right that disk space can be affected by a
+ malicious actor.  The more branching he can induce, the more branch
+ nodes that are created to support branches with only one leaf.  <br>
+ <br>
+ <br>
+ </body>
+</html>
+
+--------------040508030500040107050704--
+
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-26 13:36:05 +0000