From: Mike Koss <mike@coinlab•com>
To: Alan Reiner <etotheipi@gmail•com>
Cc: bitcoin-development@lists•sourceforge.net
Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node
Date: Thu, 21 Jun 2012 14:42:58 -0700 [thread overview]
Message-ID: <CAErK2CgH1k2oosn2a7HyvDxvasw1pHh6jPVWG0JUORMVHettOQ@mail.gmail.com> (raw)
In-Reply-To: <4FE0C538.3090001@gmail.com>
[-- Attachment #1: Type: text/plain, Size: 3922 bytes --]
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.
[-- Attachment #2: Type: text/html, Size: 6305 bytes --]
next prev parent reply other threads:[~2012-06-21 21:49 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-06-19 16:46 Andrew Miller
2012-06-19 17:33 ` Alan Reiner
2012-06-19 17:59 ` Gregory Maxwell
2012-06-19 18:12 ` Alan Reiner
2012-06-19 18:18 ` Mark Friedenbach
2012-06-19 18:30 ` Alan Reiner
2012-06-21 21:42 ` Mike Koss [this message]
2012-06-21 22:02 ` Gregory Maxwell
2012-06-19 18:29 Andrew Miller
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAErK2CgH1k2oosn2a7HyvDxvasw1pHh6jPVWG0JUORMVHettOQ@mail.gmail.com \
--to=mike@coinlab$(echo .)com \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=etotheipi@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox