Random Access Block Chain

[bytemaster]

Suppose I want to query the block chain for the balance of 'some account'.  Is this a linear-time operation where you have to find all transactions that deposited money into that account before you can know the 'balance'?

The only alternative I can think of is that every transaction outputs the new 'sum' and then you can stop searching once you find the first transaction into an account.

What can of performance hit could we expect once there are 1000's of transactions per block instead of just a half dozen or so?

[1714824769]

1714824769

[1714824769]

1714824769

[1714824769]

1714824769

[1714824769]

1714824769

[1714824769]

1714824769

[jib]

Yes, it's a linear-time operation.

Why do you need to quickly find the balance of an address from the block chain, anyway?

Also, don't get the terminology confused. You can find out the balance of an address, not of an account. (An account is a way to manage multiple sets of addresses in the client; there's no information about accounts in the block chain)

[theymos]

Is this a linear-time operation where you have to find all transactions that deposited money into that account before you can know the 'balance'?

Yes. Fortunately, only the owner of the address ever needs to do this.

What can of performance hit could we expect once there are 1000's of transactions per block instead of just a half dozen or so?

It's not that hard to scan through transactions, especially if you're not actually verifying the crypto for each one (which a lightweight client doesn't need to do).

[bytemaster]

So for the client to know its 'balance' it must compare every transaction against all of its 'addresses'. 

This isn't a problem today, but suppose you were developing a light weight client that kept its own private keys, but did not have access to the block chain.   This client wishes to use a block-chain service to 'check its balance' now this block chain service needs to perform 'random', 'real time' queries on the block chain.

This isn't too big of a problem now, but if bitcoin ever started processing even 5% of the financial transactions in this country a linear search would not be practical.  I suppose a service would have to create and maintain an 'index'.

 

[MoonShadow]

So for the client to know its 'balance' it must compare every transaction against all of its 'addresses'. 

This isn't a problem today, but suppose you were developing a light weight client that kept its own private keys, but did not have access to the block chain.   This client wishes to use a block-chain service to 'check its balance' now this block chain service needs to perform 'random', 'real time' queries on the block chain.

This isn't too big of a problem now, but if bitcoin ever started processing even 5% of the financial transactions in this country a linear search would not be practical.  I suppose a service would have to create and maintain an 'index'.

A blockchain index?  Doesn't the vanilla client index the blockchain for itself already?

[Mike Hearn]

Yes, given only a set of keys and nothing else, a client needs to traverse the block chain to discover what transactions are available to it.

The concept of "balance" in bitcoin is potentially a little fuzzy as the scripting system lets you create transactions that have quite complicated conditions to redeem the outputs, but right now nearly all transactions are standard.

Indexing the block chain isn't that hard - see blockexplorer.com for an example of that, which lets you go from address to all transactions. The question is one of trust vs latency.

The way to do this that gives you the highest confidence in its correctness is to download and verify the block chain for yourself. That's what I'm working towards in my client. The downside is it takes a long time.

The way to do this that gives you lower confidence but has an easier implementation and faster response time is just query the blockexplorer site or an equivalent you run yourself. Now you know all the transactions for all of your keys and can calculate the balance.

[Gavin Andresen]

A blockchain index?  Doesn't the vanilla client index the blockchain for itself already?

Yes, that is exactly what the blkindex.dat file is.

wallet.dat contains "extended dance mix" versions of all the transactions you care about (all of "your" receives/sends).  Those are loaded into memory at startup (and then kept up-to-date as new transactions are seen), so calculating "your" balance is quick (just scan through all wallet transactions in memory and total them up).