Towards settlement bounds for Subspace consensus

[Chen_Feng_2023]

Recall from our previous post that the main security statement of Subspace consensus is the following:

“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 (with high probability).”

This is an asymptotic result, meaning that the adversary can break the security with high probability no matter what the confirmation depth is. In practice, we may be interested in the following, non-asymptotic, question: Given certain fraction of adversary storage (owned or faked) and confirmation depth k, what is the probability that the adversary can break the security (by conducting a double-spending attack on a target transaction)? Intuitively, such probability should decrease with k.

Saeid (our research assistant) will help us understand such probability for two special cases (c \to \infty and c = 1), since these two cases can be reduced to some known results in the literature called settlement bounds.

Correction: Only one special case (c \to \infty) is discussed in the literature. To the best of my knowledge, the settlements bounds for c = 1 is still open.

[saeid]

@Chen_Feng_2023

Saeid (our research assistant) will help us understand such probability for two special cases (c→∞c \to \inftyc→∞ and c=1c = 1c=1), since these two cases can be reduced to some known results in the literature called settlement bounds.

In the case where, c \to \infty, two research papers have proposed lower and upper bounds for Proof of Work. One such paper, titled Bitcoin’s Latency Security Analysis Made Simple, introduced two theories and the second theory offers tighter bounds. I implemented theorem two using Subspace parameters, setting \lambda = 1/6 and \Delta = [1,2] with K = 160. Below is the result:

The result from my implementation are presented in the code below:

import numpy as np
import matplotlib.pyplot as plt
from scipy.special import comb

# Parameters

lmbda = 1/6
delta = 1.1
rho = 0.9
N = 160
p = rho * np.exp(-lmbda * delta)

# Functions

def P2(j, n, q):
    return comb(n, j) * (q**j) * (1-q)**(n-j)

def P1(i, p):
    q = 1-p
    return (q/p)**(i-1) * (1-(q/p))

def F2(j, n, q):
    result = 0
    for l in range(j+1, n+1):
        result += P2(l, n, q)
    return result

def F1(i, p):
    q = 1-p
    return (q/p)**i

def T2_H_1(k,i):
  return F2(k - i, 2 * k + 1 - i, 1 - p)

def T2_H_2(i,j,k):
  return P2(j, 2 * k + 1 - i, 1 - p) * F1(2 * k + 1 - 2 * i - 2 * j, p)

def T2_L_1(k,i):
  return F2(k - i, 2 * k + 1 - i, 1 - rho)

def T2_L_2(i,j,k):
  return P2(j, 2 * k + 1 - i, 1 - rho) * F1(2 * k + 1 - 2 * i - 2 * j, rho)

# Main Code

p_safty_viol_upper_th2 = []
p_safty_viol_lower_th2 = []
k_vec = range(1, N+1)

for k in k_vec:


    # Theory 2
    upper_th2 = 0
    lower_th2 = 0
    for i in range(1, k+1):

        temp_up_2 = 0
        temp_low_2 = 0
        for j in range(k - i + 1):
            temp_up_2 += T2_H_2(i,j,k)
            temp_low_2 += T2_L_2(i,j,k)

        temp_up_2 += T2_H_1(k,i)
        temp_low_2 += T2_L_1(k,i)

        upper_th2 += P1(i, p) * temp_up_2
        lower_th2 += P1(i, rho) * temp_low_2

    p_safty_viol_upper_th2.append(upper_th2 + F1(k, p))
    p_safty_viol_lower_th2.append(lower_th2 + F1(k, rho))



# Plotting the results
plt.figure(figsize=(20, 12))
plt.semilogy(k_vec, p_safty_viol_upper_th2, 'b-o', label='Theorem 2 Upper - 90% Honest', linewidth=2, markersize=2.5)
plt.semilogy(k_vec, p_safty_viol_lower_th2, 'r-s', label='Theorem 2 Lower - 90% Honest', linewidth=2, markersize=2.5, markeredgewidth=2)




plt.grid(True)
plt.xlabel('Confirmation Depth, k')
plt.ylabel('Probability of Double Spending')
plt.title('Subspace Longest Chain')
plt.legend()
plt.show()

[Chen_Feng_2023]

Thanks Saeid! For your setup of \lambda = 1/6, \Delta = 1.1 and c \to \infty, our security statement says that the adversary must control or fake a storage of at least \Omega/(1 + 1.1/6) = 0.845\Omega in order to break the security with high probability. This translates to the case of 45.8\% malicious storage.

If the adversary controls or fakes only 10\% of the storage, then it cannot break the security with high probability. Indeed, the chance (of breaking security) is rather low for a confirmation depth of 160 blocks, as suggested by your result. What if the adversary controls or fakes 30\% of the storage?

[saeid]

When the ratio of honesty is set to 70%, the likelihood of a successful attack by a malicious node markedly increases (K = 160).

Nevertheless, enhancing the value of K can improve the situation. For instance, if we set K=300, the lower band will show significant improvement.

[saeid]

@Chen_Feng_2023

Saeid (our research assistant) will help us understand such probability for two special cases (c→∞c \to \inftyc→∞ and c=1c = 1c=1), since these two cases can be reduced to some known results in the literature called settlement bounds.

There is a recent research paper titled Practical Settlement Bounds for Longest-Chain Consensus. This paper presents lower and upper bounds for both Proof of Stake (PoS) and Proof of Work (PoW). When c \to 1, in relation to the previous parameters \lambda = 1/6, \Delta = 1.1, and K=150, I computed the lower and upper bounds of PoS at 70% and 90% honesty levels. The results are as follows:

• PoS with 90%

• PoS with 70%

In my subsequent responses, I will provide a comparison of PoW and PoS as outlined in this paper, as well as a comparison between PoW from this paper and Theorem 2 from the previous research paper.

[saeid]

The comparison of PoW and PoS for 70% honest storage based on the second research paper approach:

The comparison of Theorem 2 PoW approach vs PoW on second paper for 70% and 90% honest storage:

• PoW Theorem 2 vs PoW second paper at 70% honest storage

• PoW Theorem 2 vs PoW second paper at 90% honest storage

P.S. : You can find the code of the second paper at this GitHub repo: GitHub - renling/LCanalysis: Numeric evaluation of longest-chain PoW and PoS blockchains

[Chen_Feng_2023]

Thanks a lot, @saeid! Your last two figures suggest that the bounds provided in the second paper are much tighter than those in the first paper. For example, for PoW with 30% malicious storage and k = 100, the second upper bound is between 10^{-5} and 10^{-6}, while the first upper bound is just between 10^{-1} and 10^{-2}.

The case of PoS with 30% malicious storage and k = 100 is most relevant to our setup. The upper bound is close to 10^{-4}, which is good. This suggests that our choice of k = 100 (as archiving depth) is reasonable. In my next reply, I will suggest some additional numerical evaluations.

[Chen_Feng_2023]

There is a heuristic way to evaluate PoS performance. The “adversarial power” can be amplified by \phi_c. For example, suppose that the honest power is 90% and the adversarial power is 10%. When c = 1, the adversarial power is amplified by \phi_1 = e. That is, its new power is 0.1 e. How accurate is this heuristic method? If it is reasonably accurate, we can use it to evaluate our PoAS.