Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-21 Thread Gregory Maxwell
On Thu, Jun 21, 2012 at 5:42 PM, Mike Koss wrote: > Are we just talking about pruning the spent transactions from an old block? No. We're talking about commitments to the state of _unspent_ transactions which would allow ~memoryless nodes to engage in full validation without having to trust anyt

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-21 Thread Mike Koss
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

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-19 Thread Alan Reiner
On 06/19/2012 02:18 PM, Mark Friedenbach wrote: On Tue, Jun 19, 2012 at 10:33 AM, Alan Reiner > 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 ins

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-19 Thread Andrew Miller
Alan Reiner wrote: > 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 looke

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-19 Thread Mark Friedenbach
On Tue, Jun 19, 2012 at 10:33 AM, Alan Reiner 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 ent

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-19 Thread Alan Reiner
On 06/19/2012 01:59 PM, Gregory Maxwell wrote: On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner wrote: 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 th

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-19 Thread Gregory Maxwell
On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner wrote: > 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

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-19 Thread Alan Reiner
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 ord

Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

2012-06-19 Thread Andrew Miller
> Peter Todd wrote: > My solution was to simply state that vertexes that happened to cause the > tree to be unbalanced would be discarded, and set the depth of inbalance > such that this would be extremely unlikely to happen by accident. I'd > rather see someone come up with something better though