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

<p>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.</p>

<p>k is the proportionality constant implicit in the Big Theta notation.</p>

CC BY-SA 3.0
2015-06-06T05:09:27.877Z
Thanks for your answer. I'm still not getting it though. Is Ө a function or a variable?
Alex Millar
CC BY-SA 3.0
2015-06-06T19:00:32.763Z
@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
CC BY-SA 3.0
2015-06-06T19:01:45.387Z
@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
CC BY-SA 3.0
2015-06-06T21:38:00.853Z
Thanks for your help. Yeah, why does Peter say Bitcoin scales O(n^2)? Empirical evidence from the last 90 days shows an increasing number of transactions (https://www.quandl.com/data/BCHAIN/NTRAN-Bitcoin-Number-of-Transactions) and a decreasing number of nodes (https://getaddr.bitnodes.io/dashboard/?days=90), yet bitcoin lives on. Does this not add evidence that he is mistaken?
Alex Millar
CC BY-SA 3.0
2015-06-08T10:42:08.833Z
Decreasing number of nodes means bitcoin network centralization. Because in centralized systems there is Ө(n)
amaclin
CC BY-SA 3.0
2015-06-08T14:10:43.103Z
@AlexMillar: He's assuming everyone should run a node.
Meni Rosenfeld
CC BY-SA 3.0
2015-06-08T14:10:45.960Z
@amaclin: Bitcoin can have Ө(1) nodes - some large fixed number - and still be decentralized. Then the total data will scale as Ө(n).
Meni Rosenfeld
CC BY-SA 3.0
2015-06-08T14:18:59.403Z
Ө(1) nodes and Ө(n) traffic == centralization like in fiat/bank systems.
amaclin
CC BY-SA 3.0
2015-06-08T15:01:12.733Z
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
CC BY-SA 3.0
2015-06-04T18:29:06.803Z
2015-06-06T19:02:30.400Z
2015-06-06T19:02:30.400Z
Meni Rosenfeld
<p>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.</p>

<p>reference: <a href="https://youtu.be/Td6fwuI7F7U?t=4m59s" rel="nofollow">https://youtu.be/Td6fwuI7F7U?t=4m59s</a></p>

<p>I assume n represents number of transactions?
What does k represent?</p>

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

CC BY-SA 3.0
2015-06-05T01:19:18.040Z
// , 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
<block-size-increase>
Why do people say that bitcoin scales according to O(n^2)?
Alex Millar
# Why do people say that bitcoin scales according to O(n^2)?

(Asked by: username_0 on 2015-06-04)

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

**Tags:** block-size-increase

> **Comments:**
> **username_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.  

---

## 1 answers

### Answer by username_2 on 2015-06-04. Score: 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.

> **Comments:**
> **username_0**: Thanks for your answer. I'm still not getting it though. Is Ө a function or a variable?  
> **username_2**: @username_0: Ө 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.  
> **username_2**: @username_0: 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...  
> **username_0**: Thanks for your help. Yeah, why does Peter say Bitcoin scales O(n^2)? Empirical evidence from the last 90 days shows an increasing number of transactions (https://www.quandl.com/data/BCHAIN/NTRAN-Bitcoin-Number-of-Transactions) and a decreasing number of nodes (https://getaddr.bitnodes.io/dashboard/?days=90), yet bitcoin lives on. Does this not add evidence that he is mistaken?  
> **username_3**: Decreasing number of nodes means bitcoin network centralization. Because in centralized systems there is Ө(n)  
> **username_2**: @username_0: He's assuming everyone should run a node.  
> **username_2**: @username_3: Bitcoin can have Ө(1) nodes - some large fixed number - and still be decentralized. Then the total data will scale as Ө(n).  
> **username_3**: Ө(1) nodes and Ө(n) traffic == centralization like in fiat/bank systems.  
> **username_2**: 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.  

---

