On Feb 28, 2017 15:10, "Bram Cohen via bitcoin-dev" <bitcoin-dev@lists.linuxfoundation.org> wrote:

On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <g.andrew.stone@gmail.com> wrote:

But since transactions' prevouts are not specified by [block height, tx index, output index] or by TXO index, I don't understand how an insertion ordered TXO tree can result in efficient lookups. Can you help me understand this?

You have to have a lookup table going from prevouts to txo index. Lookups on that are relatively fast because looking up things in a hashtable is a single cache miss, while looking up things in a tree is logarithmic cache misses.

I'm wondering if there is some confusion here.

Yes, someone needs to have a lookup table from prevouts to TXO tree positions. But because an insertion-ordered TXO tree does not rebalance, that table can be maintained by wallets or service providers for just their own coins, instead of by every full node and miner individually for everyone's coins.

In the simplest committed TXO model, full nodes simply maintain the TXO root hash, and every transaction/block comes with a proof that its inputs are in the TXO tree, and the necessary information to update the root after spending the inputs and adding the outputs.

Pieter