Scalability and transaction rate

Large transaction rates are a key future bottleneck of the current bitcoin system.

As far as I can tell, it's a completely connected network.  And it kind of has to be for the security to work - the main idea is that an attacker needs nearly 50% of the computing power of the entire network to inject false transaction information into (or delete honest transactions from) the network.  If there was a propagation system, you'd only need to to have about 50%+ of whatever the lowest rung is, and then the rung would be duped into transmitting your false information, possibly beating out the other lowest rungs to dupe the next higher up rung, and so on.

The bottleneck was my first reaction when I read about bitcoin.  For one thing, the way the blocks are currently set up, it takes linear time with respect to the total number of transactions (and I think more than that in memory) to verify one transaction.  So after 10 years of bitcoin, you need to either go through all 10 years worth of transactions, or have a snapshot of all the account balances of every user ever and work from there.  And since the blocks form a straight chain, all of those 35,000 transactions need to go into the same block (if block generation continues to average one per ten minutes).  There's currently no way to split that up and have the network work on 350 blocks with 100 transactions each simultaneously, because each block needs the hash of the previous block.  That seems particularly silly with the way bitcoin transactions are verified.  If everyone waits for one to three blocks to verify a transaction before spending their bitcoins, that means that none of the 35,000 transactions in one ten minute period can depend on each other, and most shouldn't even depend on the previous block.  And as far as I can tell, there's no way for the network to speed up block creation in response to transaction overload - if the network ever hit the point where transactions were being made faster than they were being hashed into blocks, the problem would snowball until enough people quit bitcoin out of frustration that the number of transactions dropped below block creation speed.  And if block creation were to speed up (via difficulty decrease) then the reward for hashing a new block would have to go down to maintain the planned rate of bitcoin introduction.  The nodes would have to know that during the Great Bitstorm of August 2013 blocks only netted the creator 2.5 bitcoins - and they'd have to figure it out during the Great Bitstorm of August 2013.

Also, there's a potential problem if block creation speed were to exceed the speed of information on the network.  Chains could be built faster than they would be distributed to the rest of the network, which could mean that two different network segments could work on two different chains simultaneously.

And of course it's worse than 35,000 transactions / ten minutes - we'd probably see something like 50-60k+ transactions during peak hours (depending on how geographically distributed the network is) and much less during the off hours.  There would be a need to dynamically throttle proof-of-work difficulty and coin reward hour-by-hour.  Since bitcoin is computer based, there'll probably eventually be a fair number of automated systems buying and selling bitcoins - a sudden sharp fluctuation in stock markets or currency exchange rates could set those off all at once.  (Although the verification system might help with this, since you can't do microsecond scale trading with bitcoins.)

Thank you both!

I understand that all transactions and all validated blocks need to get to every node. I was just curious about the implementation of the broadcast mechanism.

At worst case a million nodes would each have a million minus one open connections (bad). A better case would have each node broadcast to log(n) nodes who relayed to log(n) node, and to complete the broadcast in log(n) time.

Do you have any details of the thought experiment quantumplication?

You're right - I keep forgetting that the actual coins are tracked rather that just the account balance.  So yeah, you only need to go back find whoever last owned the coins in question and verify that they're the same person sending them.  Which is technically linear time in that if the first coin ever was hoarded for ten years you really would need to go through the entire ten year block chain (unless you indexed it, which would be easy as all the coins are numbered) to see who had it - but in practice it would be closer to constant time because most people won't hoard bitcoins.  (Unless they figure out that deflation is all but guaranteed...)  For some reason I keep thinking that you would need to verify the account balance of the sender, and that would require verifying the account balance of everyone who has sent the sender money, and everyone who sent them money, and so forth.

I didn't mean anything other than how does the network communicate now?

When I run the network I see 20ish connections. I'm assuming that is not every node running. How does the algorithm decide who talks to who?

There are several know distributed hash table topologies. Was wonder if it was using one of those.

Granted, it could be everyone talks to everyone at the moment, and to be optimized in the future. I'd find that a reasonable answer too.

Cheers!

Actually communicating through federated irc servers would probably work as well as anything. :-)

I used to have similar thoughts, but I decided I was wrong. It turns out that BitCoin is peer to peer in the sense that tier-1 internet providers are peer to peer. It is not P2P in the same sense that bittorrent is P2P.

Satoshi points out that he sees the NEED for at most 100,000 nodes verifying transactions and logging blocks. Others would use those nodes in a more client/service fashion. If I was guessing that number I would put it much lower (3<X<100) independent interested parties. Anyone can choose to be one of those X parties, or can choose to validate some or all of the work of those X parties, but only a small number are really REQUIRED.

Because in effect, the entire block list is mostly a distributed notary service. And though that requires rigor, it is not a particularly hard job.

So who would choose to do that job for free?

Knightmb for one. I'm have no doubt that many others like NewLibertyStandard will as well. Why Knightmb specifically? Well he has lots of coins and his business model and personal wealth relies on a well functioning honest system. Without that, his wealth and business simply evaporate. It is altruism and cooperation though self interest.

If you want a real world example consider the internet itself. At its amorphous core are about 7 tier-1 service providers. They are called tier-1 only because each has a mutually self interested "peering agreement" with the other six providers. That means these huge services providers move phenomenal amounts of date back and forth with zero accounting and zero payments among each other. They make all their money by selling their service to NON-tier-1 providers who make their money from selling it to you.

There is nothing to stop anyone from becoming a tier-1 provider. All you have to do is convince the others that it is in their self interest to peer with you. So for a example, Google is thought to pay zero in bandwidth to transmit youtube videos. There is enough traffic both ways, that it is in everyones self-interest to peer with them.

I expect that the same will happen with BitCoin. All the internal accounting and transfers will be free. (with the exclusion of transaction fees meant to avoid spam and mischief). Value will be created at the edges where people exchange bitcoins for something else of value.

I am convinced that bandwidth, disk space, and computation time necessary to distribute and "finalize" a transaction will be prohibitively expensive for micro-payments.  Consider for a second that the current banking industry is unable to provide a reasonable micropayment solution that does not involve depositing a reasonable sum and only allowing a withdraw after a reasonable sum has been accumulated. 

Besides, 10 minutes is too long to verify that payment is good.  It needs to be as fast as swiping a credit card is today.

Thus we need bit-banks that allow instant transfers among members and peer banks.   Anyone can open a bit-bank but the system would, by necessity operate on some level of trust.  Transfers in and out of the banks and peer-to-peer would still be possible but will be more costly.   Thus, a bit bank could make money by enabling transfers cheaper and faster than the swarm with the added risk of trusting the bank.  A bank has to maintain trust to make money.