Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.216.175 as permitted sender)
	client-ip=209.85.216.175; envelope-from=gmaxwell@gmail.com;
	helo=mail-qc0-f175.google.com; 
MIME-Version: 1.0
In-Reply-To: <4FE0B7EB.6000100@gmail.com>
References: <CAF7tpEyEWCbcB+jSpWOMyeZUBjQ=FbVEC8kLt3j2Yzv3YJOgiA@mail.gmail.com>
	<4FE0B7EB.6000100@gmail.com>
Date: Tue, 19 Jun 2012 13:59:04 -0400
Message-ID: <CAAS2fgRFFtdsuaS+ZoFLYcnUxLBufA8aMV=_sHca5ZOi-3viTw@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Alan Reiner <etotheipi@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/
 trust-free lite node
Precedence: list

On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner <etotheipi@gmail.com> wrote:
>=C2=A0One 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. =C2=A0Not only would that be disruptive, it would be a disaster to
> track down.

This is why good comprehensive tests and a well specified algorithim
are important. The tree update algorithm would be normative in that
scheme. Worrying that implementers might get it wrong would be like
worrying that they'd get SHA256 wrong.

> 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

Provable libJudy trees. Oh boy.