Bitcoin Forum
December 04, 2016, 02:19:54 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Random Access Block Chain  (Read 1456 times)
bytemaster
Hero Member
*****
Offline Offline

Activity: 728

BitShares


View Profile WWW
December 22, 2010, 12:01:50 AM
 #1

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?


https://steemit.com  Blogging is the new Mining
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480861194
Hero Member
*
Offline Offline

Posts: 1480861194

View Profile Personal Message (Offline)

Ignore
1480861194
Reply with quote  #2

1480861194
Report to moderator
1480861194
Hero Member
*
Offline Offline

Posts: 1480861194

View Profile Personal Message (Offline)

Ignore
1480861194
Reply with quote  #2

1480861194
Report to moderator
1480861194
Hero Member
*
Offline Offline

Posts: 1480861194

View Profile Personal Message (Offline)

Ignore
1480861194
Reply with quote  #2

1480861194
Report to moderator
jib
Member
**
Offline Offline

Activity: 84


View Profile
December 22, 2010, 12:06:47 AM
 #2

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)

Looking forward to quantum computing so we can have qubitcoins.
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
December 22, 2010, 12:11:14 AM
 #3

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.

Quote
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).

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
bytemaster
Hero Member
*****
Offline Offline

Activity: 728

BitShares


View Profile WWW
December 22, 2010, 03:41:49 AM
 #4

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'.

 

https://steemit.com  Blogging is the new Mining
MoonShadow
Legendary
*
Offline Offline

Activity: 1666



View Profile
December 22, 2010, 04:42:40 AM
 #5

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?

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
December 22, 2010, 01:10:27 PM
 #6

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
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
December 22, 2010, 02:17:45 PM
 #7

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).

How often do you get the chance to work on a potentially world-changing project?
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!