Subspace consensus builds upon Nakamoto-style Proof-of-Work (PoW) and Proof-of-Stake (PoS) consensus. Let’s understand the security statements for each of them.
- PoW Security: Given some honest mining power \Omega, an adversary must control an mining power of at least \Omega in order to break the system security. This requirement is economically infeasible due to the vast amount of computing power needed. For example, Bitcoin today has a total mining power capable of computing 10^{20} hashes per second. An adversary would need more than half of that to break the security.
- PoS Security: Given some honest stake \Omega, an always-online adversary must control a stake of at least \Omega/\phi_c in order to break the security, where \phi_c > 1 represents the growth rate of c-correlation. (The larger c is, the closer \phi_c is to 1.) As with PoW, having such a massive stake is economically infeasible for large PoS chains.
- Subspace Consensus Security (Proof-of-Archival-Storage - PoAS): Given some honest storage \Omega, an always-online adversary must control or fake a storage of at least \Omega/\phi_c in order to break the security.
Next, we will discuss three important questions related to Subspace consensus:
- What do we mean by an always-online adversary?
- How hard is it to fake storage?
- What if the initial honest storage is relatively small?
2 Likes
Before we answer the previous questions, we take a detour to parameter selection and understand its implication for security.
Given a network delay bound \Delta, our previous security statement can be extended as follows: Given some honest storage \Omega, an always-online adversary must control or fake a storage of at least \Omega/\phi_c(1 + \lambda \Delta) in order to break the security, where \lambda is the target block rate for honest farmers.
Say, if we set \lambda = 1/6 (i.e., one block every 6 seconds) and \Delta = 6 seconds, then 1 + \lambda \Delta = 2. That is, an adversary must control or fake a storage of at least \Omega/ 2 \phi_c to break security.
Next, we turn our attention to \phi_c, whose expression is given by
\phi_c = \frac{- c \theta_c^*}{\ln (- \theta_c^*) + (c-1) \ln (1 - \theta_c^*)},
where \theta_c^* is the unique negative solution to
-\ln (- \theta_c) - (c - 1) \ln (1 - \theta_c) = -1 + (c - 1) \frac{\theta_c}{1 - \theta_c}.
It is easy to check that \phi_1 = e and \phi_{c} \to 1 as c \to \infty. If we set c = 20, then an adversary needs \Omega/ 2 \phi_{20} to break security. Hassan computed the first 20 values for \phi_c which are listed below:
c = 1: \phi_c = e
c = 2: 2.22547
c = 3: 2.01030
c = 4: 1.88256
c = 5: 1.79545
c = 6: 1.73110
c = 7: 1.68103
c = 8: 1.64060
c = 9: 1.60705
c = 10: 1.57861
c = 11: 1.55409
c = 12: 1.53266
c = 13: 1.51372
c = 14: 1.49681
c = 15: 1.48160
c = 16: 1.46780
c = 17: 1.45522
c = 18: 1.44368
c = 19: 1.43305
c = 20: 1.42321
Finally, we need to understand how these parameters (namely, \lambda, \Delta, and c) are related to the difficulty of faking storage.
Here is more values for \phi_c:
c= 21: \phi_c=1.414059
c= 22: \phi_c=1.405529
c= 23: \phi_c=1.397549
c= 24: \phi_c=1.390061
c= 25: \phi_c=1.383017
c= 26: \phi_c=1.376372
c= 27: \phi_c=1.370092
c= 28: \phi_c=1.364142
c= 29: \phi_c=1.358495
c= 30: \phi_c=1.353125
c= 31: \phi_c=1.348010
c= 32: \phi_c=1.343131
c= 33: \phi_c=1.338469
c= 34: \phi_c=1.334008
c= 35: \phi_c=1.329735
c= 36: \phi_c=1.325636
c= 37: \phi_c=1.321700
c= 38: \phi_c=1.317916
c= 39: \phi_c=1.314274
c= 40: \phi_c=1.310765
c= 41: \phi_c=1.307382
c= 42: \phi_c=1.304117
c= 43: \phi_c=1.300963
c= 44: \phi_c=1.297914
c= 45: \phi_c=1.294964
c= 46: \phi_c=1.292108
c= 47: \phi_c=1.289341
c= 48: \phi_c=1.286658
c= 49: \phi_c=1.284055
c= 50: \phi_c=1.281528
2 Likes
Here’s the plot. 20 looks good.
This question has been answered very well in the POSAT paper. Basically, most PoS papers made the following assumption: “all adversary nodes are always
online starting from the genesis block and no new adversary nodes can join”. To better understand this assumption, the POSAT paper introduced the following example:
“Suppose for the 1st year of the existence of the PoS-based blockchain, only 10% of the total stake is online. Out of this, consider that all nodes are honest. Now, at the beginning of the 2nd year, all 100% of the stake is online out of which 20% is held by adversary. At any point of time, the fraction of online stake held by honest nodes is greater than 0.8.”
However, the adversary can use its 20% stake to go back in time, doing “costless simulation” and breaking the security. This is because the adversary will have a significant advantage if it goes back to Year 1. This issue applies to Proof-of-Storage blockchains as well, because an adversary can rent some storage from Year 2 and then go back in time to Year 1.
As a solution, we should prevent the adversary from going back in time. The POSAT paper proposes to use VDF. Similarly, we used the PoT to address this issue.
The beyond-Hellman paper presents an initial answer to the above question. Let L be the amount of storage we would like to fake. Then, we need to satisfy the following fundamental tradeoff: S^q \cdot T \in \Omega\left(L^q \right).
For example, we can (honestly) buy or rent L amount of storage (i.e., S = L). Then, we don’t need to do additional computation (i.e., T = 1). On the other hand, if we don’t want to buy or rent any storage, then we need to do L^q amount of computation.
In reality, we have other resources (such as memory IO) that make it hard to fake storage. This is our ongoing research at Subspace. In particular, we aim to establish some new fundamental tradeoffs taking into account memory IO. Stay tuned!
This question is essentially about bootstrapping a new blockchain. Some good answers are available in this lecture note.
I have copied the \phi_c above (from c= 15 to 50) and computed the threshold of which fraction of honest storage an adversary can control as 1/(\phi_c(1+\lambda\Delta)) with \lambda=1/6 and \Delta=6:
and with
\Delta=2
So
c=50 does look better if we are not concerned with the prediction window and risk of a faster PoT.
Thanks @dariolina! Could you please replot the second figure (with \Delta = 2) by using the security threshold, which is defined as
\frac{\Omega/\phi_c (1 + \lambda \Delta)}{\Omega/\phi_c (1 + \lambda \Delta) + \Omega} = \frac{1}{1 + \phi_c (1 + \lambda \Delta)}
Also, could you please try \Delta = 1 too? Thanks a lot!
Here’s 1/(1+\phi_c(1+\lambda\Delta)) for \Delta=2:
And for
\Delta=1 (which I’m not sure is an adequate estimate):
Generally, the bigger the \Delta the less difference there is between c=20 and 50 in terms of the above threshold
