From: Mark Friedenbach <mark@monetize•io>
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: Tue, 19 Jun 2012 11:18:07 -0700 [thread overview]
Message-ID: <CACh7GpEehHFEJGRTtijgM7UAa2jeEWRKrQo5dym8F_YgXAEhFA@mail.gmail.com> (raw)
In-Reply-To: <4FE0B7EB.6000100@gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2456 bytes --]
On Tue, Jun 19, 2012 at 10:33 AM, Alan Reiner <etotheipi@gmail•com> wrote:
> I hope that someone else here would chime in on the issue raised in the
> thread, about using a tree-structure that has multiple valid
> configurations for the same set of unspent-TxOuts. If you use any
> binary tree, you must replay the entire history of insertions and
> deletions in the correct order to get the tree structure and correct
> root. Along those lines, using something like a red-black tree, while
> theoretically well-known, could be subject to implementation errors.
> One implementation of a red-black tree may do the rebalancing
> differently, and still work for it's intended purpose in the majority of
> applications where it doesn't matter. One app developer updates their
> RB tree code which updated the RB-tree optimizations/rebalancing, and
> now a significant portion of the network can't agree on the correct
> root. Not only would that be disruptive, it would be a disaster to
> track down.
>
Then use a 2-3-4 tree (aka self-balancing B-tree of order 4), which is a
generalization of RB-trees that doesn't allow for implementation choices in
balancing (assuming ordered insertion and deletion).
As gmaxwell points out, this is an trivially fixable 'problem'. Choose a
standard, mandate it, and write test cases.
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
[-- Attachment #2: Type: text/html, Size: 3755 bytes --]
next prev parent reply other threads:[~2012-06-19 18:18 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 [this message]
2012-06-19 18:30 ` Alan Reiner
2012-06-21 21:42 ` Mike Koss
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=CACh7GpEehHFEJGRTtijgM7UAa2jeEWRKrQo5dym8F_YgXAEhFA@mail.gmail.com \
--to=mark@monetize$(echo .)io \
--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