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

Improve this question
1
  • 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
    Commented Jun 5, 2015 at 1:19

1 Answer 1

Reset to default
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.

Improve this answer
9
  • Thanks for your answer. I'm still not getting it though. Is Ө a function or a variable?
    – Alex Millar
    Commented Jun 6, 2015 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
    Commented Jun 6, 2015 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
    Commented Jun 6, 2015 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
    Commented Jun 8, 2015 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
    Commented Jun 8, 2015 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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