5

In regards to bitcoin, Peter Todd says: "Fundamentally the tech itself does not scale. The whole idea of everyone knowing everything about every transaction, which is inherent to the trust model of bitcoin right now... that's simple: O(n^2) scaling. You just can't get away from that. No matter how much you push and pull that constant k value, you'll never get away from the fact that fundamentally it's O(n^2) scaling.

reference: https://youtu.be/Td6fwuI7F7U?t=4m59s

I assume n represents number of transactions? What does k represent?

Also, is Peter referring to "Load" scalability? (wikipedia: The ability for a distributed system to easily expand and contract its resource pool to accommodate heavier or lighter loads or number of inputs. Alternatively, the ease with which a system or component can be modified, added, or removed, to accommodate changing load.)

  • 1
    // , This is a damn good question! Still, would it be possible to add more of the reddit text to this? It can be disconcerting to follow too many links to build a context for your question, and I wouldn't want it to become obscure. – Nathan Basanese Jun 5 '15 at 1:19
2

n is the number of users. It is assumed that the number of transactions is Ө(n), and that the number of full nodes who must know all transactions is also Ө(n), so the total information (that needs to be propagated, verified and stored) is n*Ө(n) = Ө(n^2).

The assumption about the nodes requires clarification according to context, because there is no actual need for the number of nodes to scale with n.

k is the proportionality constant implicit in the Big Theta notation.

  • Thanks for your answer. I'm still not getting it though. Is Ө a function or a variable? – Alex Millar Jun 6 '15 at 5:09
  • @AlexMillar: Ө is a notation. It's similar to the O you've used in the question, but more accurate in this context. Saying that something is Ө(n) means that it is asymptotically proportional to n. Basically this means - if there are twice as many users, then there are x2 transactions and x2 nodes. So there are x2 copies of the data, and the data is x2 as big, so the total amount of information stored is x4. If there are x3 as many users the total data is x9 as big (3 squared). And so on. – Meni Rosenfeld Jun 6 '15 at 19:00
  • @AlexMillar: I have to ask, though. Are you really asking why does Peter say Bitcoin is O(n^2)? Or are you asking what does O(n^2) mean? Because that is a different question, with better answers... – Meni Rosenfeld Jun 6 '15 at 19:01
  • 1
    @amaclin: Bitcoin can have Ө(1) nodes - some large fixed number - and still be decentralized. Then the total data will scale as Ө(n). – Meni Rosenfeld Jun 8 '15 at 14:10
  • 1
    No. Centralization is when there is a small number of nodes, or some built-in inequality. A system with a constant number of ~1000 nodes, and low barrier of entry for new nodes, is decentralized - whether there are 1000 users or 1,000,000,000. – Meni Rosenfeld Jun 8 '15 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.