3 ms·

Technically, BitCoin is hardly scalable. As every participant needs to be aware of every transaction, that gives O(N^2) computational/storage cost, assuming N i

by gritzko 15y ago

Technically, BitCoin is hardly scalable. As every participant needs to be aware of every transaction, that gives O(N^2) computational/storage cost, assuming N is participants and transactions~participants. May be cured by a dedicated central server storing all the transactions, but then it is not P2P anymore.

tlrobinson 15y ago
I was wondering about this after reading a little about how BitCoin worked. It sounded like every client needed to know about every transaction ever, which clearly can't scale to a mainstream currency. Perhaps there's a way to partition/shard the historical data?
- dfox 15y ago
  there really is way to "shard" historical data. But mainly, it is expected, that most users will not use whole transaction history, but trust majority opinion of network without actually verifying it or even use services of established network nodes without actively participating in network. This can be seen even now, when there are disjoint sets of nodes that actually perform "useful" transactions (users) and nodes that timestamp them (miners).
spenvo 15y ago
This is a good point and is one of a large number of challenges BTC faces. Right now, a small transaction fee ensures that your transaction will be processed quickly. This distributes the cost of validating the transaction. Eventually, we may see the transaction fee structure become less of an option and more of a necessity. BitcoinJ (the Google 20% time project) uses a very compressed and less comprehensive block chain to make transactions but is not intended to be used to generate coins. In other words, the problem is being mitigated. The level of innovation in the BTC community is jaw dropping.
njs12345 15y ago
I don't think that's true. Clients just need the latest block (and a few blocks after) to verify that a transaction has gone through, only nodes (which are meant to be quite computationally powerful) need the whole block chain.
- eof 15y ago
  Clients need to download and verify the entire block chain; but they don't need to store the whole thing.
Tichy 15y ago
I think they count on Moore's law.
weavejester 15y ago
> Technically, BitCoin is hardly scalable. As every participant needs to be aware of every transaction, that gives O(N^2) computational/storage cost, assuming N is participants and transactions~participants. That's not true. The Bitcoin protocol defines a "simplified payment verification" method that does not require clients to store the full block chain. The Bitcoin network does need a sufficient number of full clients to ensure that an attacker cannot get access to over 50% of the processing power in the network, but the number of full clients could be much lower than the number of simple clients. If Bitcoin ever becomes a major economy, the full clients will be sitting in data centers with lots of bandwidth, and most people will use simple clients.
- gritzko 15y ago
  So, the claim of being P2P goes to the wind first :) Second. When accepting a coin, a node needs to check the coin was not spent since the last time it changed hands. If the buyer claims he got it 1 month ago (and shows a proof), then the seller needs to check a month worth of transactions, just in case it was double-spent. Note the terrible asymmetry of the attacker's and the defender's costs. Third. Today I had to reread the paper (by Nakamoto) and I am surprised (again) by the level of wishfulness and naïveté. Sec 5 (page 3) says: "the nodes that were working on the other branch will then switch to the longer one". Does he realize that in a distributed system nodes might have totally different opinions on the number and length of those branches? And that those opinions might change. It is easy to imagine nodes hopping between branches with no global agreement possible. His very way of thinking has zero intuition about distributed/asynchronous systems, sorry. Obviously, that may be cured by introducing well-provisioned central sites, as you say. But then, all that crypto-trickery becomes entirely meaningless and the system loses its raison d'être. Well-provisioned mutually-recognized sites/banks may do it exactly the way they do it these days. Sorry for the rant.
  - weavejester 15y ago
    "So, the claim of being P2P goes to the wind first" It depends on how pedantic you are about the term "P2P". I guess you could argue that any P2P network that includes supernodes is not a true P2P network, but in practise I've never heard that objection. "If the buyer claims he got it 1 month ago (and shows a proof), then the seller needs to check a month worth of transactions, just in case it was double-spent. Note the terrible asymmetry of the attacker's and the defender's costs." Not really. Finding out whether an address can spend a coin is just a hashtable lookup. It's not like we have to use linked lists! So the cost for the defender is trivial. An attacker, however, has to orphan the current block chain, which requires controlling at least 50% of the computational power in the Bitcoin network. For instance, let's say Alice gives Bob 1 BTC. Bob waits for 6 confirmations before accepting it as valid, which is the standard length the official Bitcoin client uses. This means that there is a chain of 6 blocks verifying the transaction; if Alice wants to double-spend, she needs to get rid of that chain, which she can only do if she can produce a longer alternative block chain. This means she has to produce blocks at a faster rate than everyone else on the network, which requires that she possess over 50% of the computational resources. "Does he realize that in a distributed system nodes might have totally different opinions on the number and length of those branches? And that those opinions might change. It is easy to imagine nodes hopping between branches with no global agreement possible." No, because clients always choose the longest block chain. It's possible that for a little while the block chain will branch, but that situation is inherently unstable; eventually one branch will produce a block faster than the other, and everyone will switch to the winning branch.

by gritzko 15y ago

tlrobinson 15y ago

I was wondering about this after reading a little about how BitCoin worked. It sounded like every client needed to know about every transaction ever, which clearly can't scale to a mainstream currency. Perhaps there's a way to partition/shard the historical data?

dfox 15y ago
there really is way to "shard" historical data. But mainly, it is expected, that most users will not use whole transaction history, but trust majority opinion of network without actually verifying it or even use services of established network nodes without actively participating in network. This can be seen even now, when there are disjoint sets of nodes that actually perform "useful" transactions (users) and nodes that timestamp them (miners).

spenvo 15y ago

This is a good point and is one of a large number of challenges BTC faces. Right now, a small transaction fee ensures that your transaction will be processed quickly. This distributes the cost of validating the transaction. Eventually, we may see the transaction fee structure become less of an option and more of a necessity. BitcoinJ (the Google 20% time project) uses a very compressed and less comprehensive block chain to make transactions but is not intended to be used to generate coins. In other words, the problem is being mitigated. The level of innovation in the BTC community is jaw dropping.

njs12345 15y ago

I don't think that's true. Clients just need the latest block (and a few blocks after) to verify that a transaction has gone through, only nodes (which are meant to be quite computationally powerful) need the whole block chain.

eof 15y ago
Clients need to download and verify the entire block chain; but they don't need to store the whole thing.

Tichy 15y ago

I think they count on Moore's law.

weavejester 15y ago

> Technically, BitCoin is hardly scalable. As every participant needs to be aware of every transaction, that gives O(N^2) computational/storage cost, assuming N is participants and transactions~participants. That's not true. The Bitcoin protocol defines a "simplified payment verification" method that does not require clients to store the full block chain. The Bitcoin network does need a sufficient number of full clients to ensure that an attacker cannot get access to over 50% of the processing power in the network, but the number of full clients could be much lower than the number of simple clients. If Bitcoin ever becomes a major economy, the full clients will be sitting in data centers with lots of bandwidth, and most people will use simple clients.

gritzko 15y ago
So, the claim of being P2P goes to the wind first :) Second. When accepting a coin, a node needs to check the coin was not spent since the last time it changed hands. If the buyer claims he got it 1 month ago (and shows a proof), then the seller needs to check a month worth of transactions, just in case it was double-spent. Note the terrible asymmetry of the attacker's and the defender's costs. Third. Today I had to reread the paper (by Nakamoto) and I am surprised (again) by the level of wishfulness and naïveté. Sec 5 (page 3) says: "the nodes that were working on the other branch will then switch to the longer one". Does he realize that in a distributed system nodes might have totally different opinions on the number and length of those branches? And that those opinions might change. It is easy to imagine nodes hopping between branches with no global agreement possible. His very way of thinking has zero intuition about distributed/asynchronous systems, sorry. Obviously, that may be cured by introducing well-provisioned central sites, as you say. But then, all that crypto-trickery becomes entirely meaningless and the system loses its raison d'être. Well-provisioned mutually-recognized sites/banks may do it exactly the way they do it these days. Sorry for the rant.
- weavejester 15y ago
  "So, the claim of being P2P goes to the wind first" It depends on how pedantic you are about the term "P2P". I guess you could argue that any P2P network that includes supernodes is not a true P2P network, but in practise I've never heard that objection. "If the buyer claims he got it 1 month ago (and shows a proof), then the seller needs to check a month worth of transactions, just in case it was double-spent. Note the terrible asymmetry of the attacker's and the defender's costs." Not really. Finding out whether an address can spend a coin is just a hashtable lookup. It's not like we have to use linked lists! So the cost for the defender is trivial. An attacker, however, has to orphan the current block chain, which requires controlling at least 50% of the computational power in the Bitcoin network. For instance, let's say Alice gives Bob 1 BTC. Bob waits for 6 confirmations before accepting it as valid, which is the standard length the official Bitcoin client uses. This means that there is a chain of 6 blocks verifying the transaction; if Alice wants to double-spend, she needs to get rid of that chain, which she can only do if she can produce a longer alternative block chain. This means she has to produce blocks at a faster rate than everyone else on the network, which requires that she possess over 50% of the computational resources. "Does he realize that in a distributed system nodes might have totally different opinions on the number and length of those branches? And that those opinions might change. It is easy to imagine nodes hopping between branches with no global agreement possible." No, because clients always choose the longest block chain. It's possible that for a little while the block chain will branch, but that situation is inherently unstable; eventually one branch will produce a block faster than the other, and everyone will switch to the winning branch.