Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of coinlab.com
	designates 209.85.212.47 as permitted sender)
	client-ip=209.85.212.47; envelope-from=mike@coinlab.com;
	helo=mail-vb0-f47.google.com; 
MIME-Version: 1.0
In-Reply-To: <4FE0C538.3090001@gmail.com>
References: <CAF7tpEyEWCbcB+jSpWOMyeZUBjQ=FbVEC8kLt3j2Yzv3YJOgiA@mail.gmail.com>
	<4FE0B7EB.6000100@gmail.com>
	<CACh7GpEehHFEJGRTtijgM7UAa2jeEWRKrQo5dym8F_YgXAEhFA@mail.gmail.com>
	<4FE0C538.3090001@gmail.com>
Date: Thu, 21 Jun 2012 14:42:58 -0700
Message-ID: <CAErK2CgH1k2oosn2a7HyvDxvasw1pHh6jPVWG0JUORMVHettOQ@mail.gmail.com>
From: Mike Koss <mike@coinlab.com>
To: Alan Reiner <etotheipi@gmail.com>
Content-Type: multipart/alternative; boundary=20cf3079bcb62f00e504c30266ee
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/
 trust-free lite node
Precedence: list

--20cf3079bcb62f00e504c30266ee
Content-Type: text/plain; charset=ISO-8859-1

Are we just talking about pruning the spent transactions from an old block?
 We already have a data structure that allows us to replace any un-needed
transaction by just it's hash - and possibly a whole sub-tree if we get
lucky in that the un-needed transaction all fall within a common node of
the merkle tree.

If a lite client only cares to retain a single transaction in a block (the
most common case) - it will only need O(log2(T)) merkle hashes plus the
transaction it cares about.

Does it really make sense to adopt a more complex data-structure than the
merkle tree for inclusing in the bticoin protocol?  And we're not talking
about blocks with millions of transactions in them - I don't understand the
relevance of Order statistics for random access to a transaction given its
block.

On Tue, Jun 19, 2012 at 11:30 AM, Alan Reiner <etotheipi@gmail.com> wrote:

>  On 06/19/2012 02:18 PM, Mark Friedenbach wrote:
>
> On Tue, Jun 19, 2012 at 10:33 AM, Alan Reiner <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.
>
>
>
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>


-- 
Mike Koss
CTO, CoinLab
(425) 246-7701 (m)

A Bitcoin Primer <http://coinlab.com/a-bitcoin-primer.pdf> - What you need
to know about Bitcoins.

--20cf3079bcb62f00e504c30266ee
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Are we just talking about pruning the spent transactions from an old block?=
 =A0We already have a data structure that allows us to replace any un-neede=
d transaction by just it&#39;s hash - and possibly a whole sub-tree if we g=
et lucky in that the un-needed transaction all fall within a common node of=
 the merkle tree.<div>
<br></div><div>If a lite client only cares to retain a single transaction i=
n a block (the most common case) - it will only need O(log2(T)) merkle hash=
es plus the transaction it cares about.</div><div><br></div><div>Does it re=
ally make sense to adopt a more complex data-structure than the merkle tree=
 for inclusing in the bticoin protocol? =A0And we&#39;re not talking about =
blocks with millions of transactions in them - I don&#39;t understand the r=
elevance of Order statistics for random access to a transaction given its b=
lock.</div>
<div><div><br></div><div><div class=3D"gmail_quote">On Tue, Jun 19, 2012 at=
 11:30 AM, Alan Reiner <span dir=3D"ltr">&lt;<a href=3D"mailto:etotheipi@gm=
ail.com" target=3D"_blank">etotheipi@gmail.com</a>&gt;</span> wrote:<br><bl=
ockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #=
ccc solid;padding-left:1ex">

 =20
   =20
 =20
  <div text=3D"#000000" bgcolor=3D"#FFFFFF"><div class=3D"im">
    On 06/19/2012 02:18 PM, Mark Friedenbach wrote:
    </div><blockquote type=3D"cite">
      <div class=3D"gmail_quote"><div class=3D"im">On Tue, Jun 19, 2012 at =
10:33 AM, Alan
        Reiner <span dir=3D"ltr">&lt;<a href=3D"mailto:etotheipi@gmail.com"=
 target=3D"_blank">etotheipi@gmail.com</a>&gt;</span>
        wrote:<br>
        <br>
        </div><div class=3D"im"><blockquote class=3D"gmail_quote" style=3D"=
margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
          If we were to use a raw trie structure, then we&#39;d have all th=
e
          above<br>
          issues solved: =A0a 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). =A0There 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. =A0Insert, delete and query times are still
          O(1).<br>
          However, it is not a trivial implementation. =A0I 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=A0<span style=3D"border-collapse:col=
lapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px">Pete=
r
            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&#39;s not much
            of an attack, but in principle exploitable under particular
            timing-sensitive circumstances.</span></div>
        <div><span style=3D"border-collapse:collapse;color:rgb(34,34,34);fo=
nt-family:arial,sans-serif;font-size:13px"><br>
          </span></div>
        <div><span style=3D"border-collapse:collapse;color:rgb(34,34,34);fo=
nt-family:arial,sans-serif;font-size:13px">Self-balancing
            search trees (KVL, RB, 2-3-4, whatever) don&#39;t suffer from
            this problem.</span></div>
        <div><span style=3D"border-collapse:collapse;color:rgb(34,34,34);fo=
nt-family:arial,sans-serif;font-size:13px"><br>
          </span></div>
        <div><span style=3D"border-collapse:collapse;color:rgb(34,34,34);fo=
nt-family:arial,sans-serif;font-size:13px">Mark</span></div>
      </div></div>
    </blockquote>
    <br>
    I was using &quot;unbalanced&quot; to refer to &quot;query time&quot; (=
and also
    insert/delete time).=A0 If your trie nodes branch based on the next
    byte of your key hash, then the max depth of your trie is 32.=A0
    Period.=A0 No one can do anything to ever make you do more than 32
    hops to find/insert/delete your data. =A0 And if you&#39;re using a raw
    trie, you&#39;ll always use <i>exactly</i> 32 hops regardless of the
    distribution of the underlying data.=A0 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.=A0 With the trie, that&#39;s not only impossible, you&#39;re actu=
ally
    accessing in O(1) time.<br>
    <br>
    However, you are right that disk space can be affected by a
    malicious actor.=A0 The more branching he can induce, the more branch
    nodes that are created to support branches with only one leaf.=A0 <br>
    <br>
    <br>
  </div>

<br>-----------------------------------------------------------------------=
-------<br>
Live Security Virtual Conference<br>
Exclusive live event will cover all the ways today&#39;s security and<br>
threat landscape has changed and how IT managers can respond. Discussions<b=
r>
will include endpoint security, mobile security and the latest in malware<b=
r>
threats. <a href=3D"http://www.accelacomm.com/jaw/sfrnl04242012/114/5012226=
3/" target=3D"_blank">http://www.accelacomm.com/jaw/sfrnl04242012/114/50122=
263/</a><br>_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
<br></blockquote></div><br><br clear=3D"all"><div><br></div>-- <br>Mike Kos=
s<div>CTO, CoinLab</div><div>(425) 246-7701 (m)</div><div><br></div><div><a=
 href=3D"http://coinlab.com/a-bitcoin-primer.pdf" target=3D"_blank">A Bitco=
in Primer</a>=A0- What you need to know about Bitcoins.</div>
<br>
</div></div>

--20cf3079bcb62f00e504c30266ee--