So you're saying there is some ambiguity when the block is first included in the network?  Perhaps that block becomes invalid and replaced with a different block? 

But, just like tx confirmations, after a few "confimations", that block height is going to become absolutely static.  Did I miss anything?

Nodes process which ever "longest chain" they hear about first.  If two nodes on opposite sides of the world solve the next block at exactly the same time, then half the world will get word of one block and start working on it, while the other half the world gets word of the other block first and starts working on that.  Once either of those chains is extended, the solution is broadcast and all nodes will switch to it, seeing that that chain is the longest.  Sure, both halves of the world could solve the next block at exactly the same time and both will be temporarily extended again.  But statistically speaking, eventually one chain will "lose", and it's entirely up to luck which one that is.

More often than not, you would get 90% of the world that sees one block, and 10% of that gets the other block first.  Unless the 10% side gets extremely lucky, the 90% will be the one to become the real chain.  The orphaned block becomes "invalid."  I believe nodes that who were working on that branch, will see what transactions need to be re-included in the new branch, but I'm not sure how that part works exactly.

Thank you so much for these replies!  This is exactly what I wanted to know.  And now it makes more sense why clients can eventually "forget" ancient parts of the global transaction register, because once all the outputs are "used", that transaction no longer provides any value to the network.

Why would the block number change?  Since every new block has the hash of the previous block, we have a pretty unambiguous, linear chain of blocks.  Where do the timestamps come into this?

As far as I'm aware, this only happens in two cases:
1) The rare case of simultaneously transmitted blocks where 1 of those blocks will end up invalid and discarded
2) Someone pulls off a double-spending attack where they build a competing chain faster than the rest of the network, after someone has already accepted a huge payment from them in the original chain.  The attacker broadcasts the longer chain and all the miners switch to it because it's longer.

Are there other cases?

Can someone please explain why/how the blockchain would be "reorganized" ?  Are we talking about invalid blocks that were originally accepted but now have to be discarded?   

I don't fully understand, but I will probably need to at some point if I'm going to start writing client software.  Though, even though this simple task doesn't seem like a lot of work, I do see pools like BTCguild constantly struggling to handle the load of the all the connected miners.  Clearly, something is stressing them out, though I suspected it might be a network bottleneck instead.  With even CPUs able to do millions of hashes-per-second, I can't imagine this computation would be a bottleneck even with a million miners connected.

So what is it that causes unbearable loads on the pool servers?

Why doesn't the miner do a full check?  Isn't it a single hash of the block header and a direct comparison of the result to the target?  Seems like it would be an extremely fast calculation, I don't see why there'd have to be a shortcut algorithm.

Are you referencing Satoshi's original paper?  Which paper?

So it's not sufficient to say "Address X is transferring 10 BTC to Address Y."  It requires including hashes of previous transactions with TxOuts that sum up to the specified TxIn amount in this new transaction?  Why does having references to previous TxOuts matter?  A complete node is going to have to search the entire transaction history after the last TxOut to verify that the coins weren't spent in another transaction, anyway? 

In my head, it makes sense that you would only need to specify "X sends N BTC to Y" and the nodes will check to see if address X has the desired level of funds remaining to execute that transaction, based on the transaction history.  I think I'm still missing something...

Perhaps I just need to see the paper you mentioned.  I browsed Satoshi's paper a couple weeks ago, but have since forgotten everything except the higher-level concepts.  I assumed the actual BTC implementation varied from his original vision, as most ideas like this need tweaking to get from theory to implementation.

-Eto

I have been trying to figure out exactly what information exists in each transaction and each block.  I understand the merkle trees and the chain of block headers, and how everything is linked through hashes.  What I don't understand is what is actually contained in a TxIn and OutPoint object.  Does each transaction reference a previous TxOut?  Does that TxOut have to have enough BTC to cover the amount of the TxIn?  If so, doesn't it get complicated to track partial balances in all previous TxOuts that eventually have to be accumulated if the user wants to empty those accounts? 

Perhaps I'm missing something.  There are three things I really want to know:

     (1)  Are the transactions chained to one another such that you can simply follow the chain backwards to get all the information you need to know about a particular address, given the last transaction involving that address?
     (2)  Is the specification telling me that I will need to hold the blockchain if I want to construct a transaction?  What is the minimum amount of information I would need to hold on my phone, for my lite phone-client to be able to construct a valid transaction?  I was planning to keep only the block headers, balance of the account, and the private key.  I don't want to store any block information.  Will I have to keep previous transaction data?
     (3) What information is contained in a transaction that prevents it from being repeated/re-broadcast by an attacker?  Is it linked to a specific block?  If that transaction is broadcast just as the next block is solved, does it have to be re-broadcast?  I thought a transaction could be included in any future block, but then I don't know what would prevent someone you just paid from re-broadcasting and paying themselves again. 

And on a side note, I haven't quite figured out how block "timestamping" works.  In some places it looks like timestamps are 32-bit unsigned numbers, in some cases they are block numbers between 0 and 2015.  I am uncertain how the unix-time timestamps could work when you have unsynchronized clocks across all nodes.  If I want to reference a specific block, do I only provide the header hash and the node searches the headers for it?  Or is it okay to say "Block #122,245" ?

Thanks for you patience with my questions.  I am anxious to start work on a new client, but the specification clear enough for me.
-Eto

If someone broadcasts an invalid transaction to the network (perhaps moving coins from one account with not enough funds), how far will that transaction get?  Is it shot down immediately by the first node that sees it?  Is it propagated and each node can decide whether it is valid?  I'm curious about when someone sends me coins and I see the transaction immediately, but then wait for confirmation.  Would I even see the transaction if other nodes didn't think it was valid?  Or is it simply up to the miners to check validity and include it in their blocks if it is?

In other words, how much can I trust a 0-confirmation transaction?  I know that's very "weak".  But a lot of "weaknesses" are still near impossible to exploit, and for a few hundredths of a BTC, it's probably fine to assume no one is going to the effort to do that.

I want to create an Android app that allows you to confirm receipt of your BTC, but doesn't have to hold the entire block chain.  My understanding is that if it contains the block headers, it can trust any single block + transaction-list provided by an arbitrary node, because the merkle root would have to match the block header root, the block header contains the hash of the previous block, and the block header's hash is a very compute-intensive value.  It is extremely difficult to create a fake one.

The only way any dishonest node to deceive you would be to calculate a valid block by itself and try to funnel it to you alone right before you accept the transaction.  Perhaps they want to double-spend against you.  They have to create a fake block with a tx from any arbitrary account to their input account, then your client believes their input account has the money and the transaction is ultimately valid.  But then, the attacker never releases the block to the network, and the next real block computed doesn't include the transaction.

The problem is, calculating that block by the attacker would be exceptionally difficult, the window in which they have to execute the attack would be tiny (30s-10min) since a new block from the network would invalidate it, and they could get 50 BTC by just broadcasting the valid block.  Therefore, for a transaction less than 50 BTC, it doesn't even make sense for an attacker to try to deceive you.  In all likelihood, you won't be dealing with 50+ BTC transactions on your phone, anyway.

Therefore, if all you have is the block headers, you can just download the next 1-2 full blocks after the transaction was sent, and that would be evidence enough that your account actually received the money.  If the transaction wasn't valid, it wouldn't have been included in any blocks at all.  So a lite client could confirm transactions after only a single block, as long as those transactions are less than 50 BTC.  And it would really only have to hold the block headers, and a few full-blocks at a time...?

-Eto

I thought each transaction had a list of output transactions from previous blocks as inputs.  Perhaps I don't fully understand this phenomenon.  I'll look at the specification for TxIn and TxOut a little closer.

But what I'm proposing doesn't require picking out double-spends.  Tell me otherwise, but I'm pretty sure only the nodes that are mining need to have the whole blockchain, so they can verify there is no double-spending.  The only thing I want the lite-client on my phone to do is check our balance.  And as long as the merkle tree roots of the transactions provided by other nodes are consistent with the block headers, this should be alright. 

Or am I missing something?  Perhaps the client just downloads all the blocks in batches of 1000, and only keeps the ones it needs.  If it doesn't take 3 days to download the blockchain anymore, this might be okay.

-Eto

Okay, that's good to know.  I assumed it had to do with the BTC network not being ideal for moving large amounts of data, and recognizing that there's an existing decentralized protocol for doing so.  If the new client only takes a couple hours to update the block chain, then bringing bit-torrent into the mix is not going to provide a whole lot of extra benefit.

So let me switch to the other side of this question.  Given that I want to design a lite-client, I need to know what is the minimal amount of information from the blockchain that can be used to efficiently process transactions.  It sounds like the entire array of block-headers is not only really useful, but also space-efficient.  The actual transaction lists themselves are not so nice.  My understanding is that there is not currently a protocol for getting specific blocks in the manner described below:

Message Type:  Address chain
Payload:   block hash/number + relevant address

Response:
Payload:  Up to 1000 block hashes/numbers, that represent the 1000 blocks before the supplied block, that are relevant to the supplied address.  This would require the responding node to follow the transaction chain(s) for that particular address and accumulate blocks until it reaches 1000.  Then the client can issue a new request for each dangling transaction that still has to be followed to the original coinbase transactions.  Finally, the client could use that list to collect all the blocks he needs and discard the rest. 

1) Is this sufficient for balance/transaction verification?  Or is it "safe" to just accumulate the "latest" transactions which provide the balance information necessary?
2) Is this likely to be a ton of data, anyway?  It seems all you would need is for ANY input address along the way to have a long/active history, and you'd end up having to download 10%+ of the blocks for your own address
3) Since there can be multiple inputs for a particular transaction, there may be a bit of branching, and I'm not sure exactly which blocks the responding node would include in his list of 1000.

I'm actually planning to start work on a new BTC client, and I'm anxious to start collaborating on security and processing efficiency ideas.  I think my previous threads should identify my higher-than-average understanding of what BTC is about:

http://forum.bitcoin.org/index.php?topic=26042.msg325144#msg325144
and
http://forum.bitcoin.org/index.php?topic=24882.new

Thanks,
-Eto

Well that's a start, if your computer that is going to hold the entire block chain.  I assume sourceforge can handle the download stress, even if this was linked from the main Bitcoin website.  On the other hand, for such a huge amount of data that should be the same everywhere, the client could P2P download it in minutes from the other nodes with no stress on anyone's system.

As for the lightweight clients, is my understanding correct?

• (1) You could get by with nothing but the headers, and the set of blocks that are "relevant" to your wallet
• (2) It would not be possible to know which blocks are relevant to you, without first downloading them
• (3) A new message could be added that allows one to request a list of blocks for a specific address, and nodes could handle the requests efficiently
• (4) You would only need as many blocks as necessary to find the coinbase transactions of all inputs ever sent to your addresses

-Eto

I noticed last time I started a new client-install from scratch that it took me more than a full day to get up to the current block.  I have also observed over the last few weeks, that the daily "Bitcoins Sent" on bitcoinwatch.com is consistently >1million.  It's tough to believe that the BTC community is so active, that more than 20% of the global BTC changes hands every day.  I suspect there are some people that recognize they can add a ton of bloat to the network by self-juggling transactions between their own addresses.  My understanding is, if they make sure all transactions only have 1 input and 1 output, they won't have to pay a transaction fee.  Is this correct?  Regardless, it's pretty inconvenient to acquire the entire block-chain from the BTC network.  I want to make sure I understand this, because I want to build a client that gracefully avoids being bloated like this:

• (1) Right now, there's only about 11 MB worth of block headers (135,000 blocks x 80 bytes/block), which should take a very short amount of time to download, and mere seconds to verify hash-integrity of the entire blockchain [headers].  However, the global transaction list is considerably larger, and currently downloaded in its entirety by the official BTC client, all the time.
  
• (2) The block headers give no information about what transactions were included in the block, only the Merkle Tree root (a hash) of the transaction list for that block.  Then, if the client wants to know and verify a BTC address balance (without anyone elses' help), he has to download the transaction list for every block, at least back to the original coinbase transactions of all the coins contained in the address.
  
• (3) You don't need the entire block chain to send/receive BTC, you only need the block headers.  A client can create transaction messages and sign them without transaction lists.  It couldn't verify whether the transaction was valid, but the transaction will be rejected by the network anyway, if it's not valid. 
• (4) Only miners would need the entire block chain, so that they can successfully, and quickly, verify the transactions they are trying to include in their blocks.
• (5) A client that receives only the headers (assuming it's the right chain), doesn't have to trust the other nodes around him so much when requesting data.  For instance, if he requests and receives the transaction list for only block X, he can quickly construct and verify the merkle tree against the block X header.  He can't verify the entire history, but presumably, if he has the longest/correct blockchain, those transactions must've been valid to be included in a block.
  

Are (1)-(4) correct assumptions?  Perhaps the transaction validity assumption in (5) is weak, since he could've been fed fake tx lists and headers by a dishonest node trying to trick him, knowing he won't follow the transaction history.  Though, any dishonest node would have to have a ton of power to even produce a single bogus block, and surely, the client would get word of the longer/correct blockchain within seconds or minutes. 

So first of all, is it possible to package up the transaction lists into something like bit-torrent file and distribute them as one giant chunk of compressed data?  The first 134,000 blocks aren't going to change, so why require the BTC nodes/network to fill all the block-data requests?  Bit-torrent is designed to handle this.  And if I'm not mistaken, someone acquiring 1 GB of block data should be able to download that in like 10 minutes, and verify the entire set in less than 10 minutes on a modern computer.  This would require bit-torrent protocol to be included in the BTC client, but seems it would be worth it.  Package up every 5000 blocks into a new btc_Blk0_to_Blk1.torrent file and let the block-chain be distributed that way.  The BTC network would only have to handle requests for the most-recent blocks.

Second, would it be possible to implement a new kind of message on the BTC network that allows lightweight-clients to leverage heavyweight clients to provide only the relevant transaction history, if they don't want the whole block chain?  The lightweight client knows that address X is mine, and wants to verify the balance and integrity of the address.  So he sends out this special request for address X, and a client on the network that has the full chain can send the a list of block numbers/hashes that are relevant to that address.  Then, the lightweight client only needs to request that list of full-blocks from the network.  Again, since he has the "correct" blockchain headers, there should be no problem trusting arbitrary nodes to give him the right block listing.  The client can continue to download every new block as it is broadcast, but will discard it if it's not relevant to himself.

I want to extend this discussion, but this message is long enough already!  Maybe I'll stop there until I know my assumptions are correct.
-Eto

So why aren't there competing clients?  I was under the impression that there's only one client option on both Windows and Linux because it's either really bad or really difficult. 

If I study the specification at https://en.bitcoin.it/wiki/Protocol_specification do you think I'll have enough knowledge to actually implement a client with all the networking/sockets to operate nicely with the rest of the network?  I suppose, the main client is open source, so perhaps I can use that source code to clear up gaps in my understanding.

-Eto

By the way, something else I've been wondering (and an excuse to get to 5 posts):  what is the incentive for a node to include any transaction in their block for free?  If you have a lot of transactions, isn't it going to take longer to hash?  If I was selfish, why wouldn't I calculate a block and only include my own coinbase transaction and nothing else?

Similarly, as the network picks up popularity aren't we running the risk that we'll have to start including millions of transactions in every block?  Even if the difficulty adjusts to accommodate the slower hashing, won't the blockchain get untolerably large (in terms of storage space)?

So you are saying that the client will not recognize a transaction with a non-standard script, unless someone knows about that transaction and spends the coins in compliance with its script?  Therefore, if a script were somehow included in a transaction, the new owner is still bound to the "terms and conditions" of the script, but if they're using the standard client, they won't see it to begin with.  Therefore, a vendor would not see the transaction in their history, and they would claim that you never paid them...?  By the way, who/what is Eligius?

There is really only one client right now, Bitcoin-0.3.23.  Is there anything wrong/unethical/prohibitive to create a new client?  I was considering trying to create a client that has built-in encryption and possibly even an option to automatically do business through Tor.  But it would have to compete with the "official" 0.3.23 client.  Is this a bad idea for the network?  If so, what's stopping someone who doesn't like Bitcoin from doing this?  From the outset, people would want it because it has useful features.    Even if it is "okay", someone could eventually sneak malicious code into the client.  What's stopping that from happening now?  Is the official bitcoin client codebase protected against this?  Could an attack of this sort cripple the network?

I have spent quite a bit of time studying how the Bitcoin network actually works, but I'm not sure I'm 100%, so these questions will hopefully clarify some of the gaps in my understanding.  Given the decentralized nature of the network, there is no single authority that decides which is the "current" block.  Nodes assume the longest chain is the "correct" one.  So:

(1)  If two blocks are computed simultaneously by nodes on opposite sides of the world,  both nodes will broadcast valid blocks with the target hashes at the same time.  Then the nodes closest to the "winners" will each start extending that chain.  Even when they get word of the other chain, they will continue to work on the first one they received.  But as soon as one of the chains gets extended, all nodes will switch to that chain, and the other chain will be orphaned. 
   -- Is this correct?
   -- If Deepbit reports a block as "Invalid," is this why?

(2)  Let's assume that a government has a massive banks of FPGAs which are not on the network right now, but actually would be more than 50% of the network speed if they were (not really feasible, but governments have a lot of money...).  Now, instead of joining the network, they start building an alternative blockchain branch, starting from some arbitrary block.  Because they have more computing power than the rest of the network, they can start building the blockchain faster than the "current" blockchain everyone is working on.  Could they build this alternate blockchain branch for 2 months, and then broadcast it to the network all at once?  If all blocks in the new chain are valid, and it's longer than the current, then won't all nodes switch to it?  Then all the transactions of the last two months will basically be reversed because they "never existed" in the new blockchain?   This would seriously disrupt the Bitcoin network...

(3) Are transaction scripts currently disabled in the main Bitcoin client software?  If not, then is anything stopping people for using scripts in their transactions?  If so, then what is stopping someone from including a script in all their transactions that says no private key is required to transfer the coins onward?  Once the main Bitcoin client software starts using the scripts, then that old transaction no longer requires a private key signature and the they can send the coins back to themself if they were never transfered out out of that account.

-Eto