Next scheduled rescrape ... never
Version 2
Last scraped
Edited on 23/05/2025, 13:09:32 UTC
I just discovered this post, so forgive my thread reanimation. I happened to be working on a selfish mining simulation for a number of different ideas, and I wanted to post my results for Proof of Entropy Minima here in case they are useful.
I hope I have understood the protocol well enough, it seems quite simple: branches are weighted by the least probability of being mined based on their hashes.
Here is the full simulation code in python:
...and the resulting plot is here:
Anyway, as you should be able to see in the graph, compared to selfish mining as described in "Majority is not Enough: Bitcoin Mining is Vulnerable" which the upper bound on break even attacker hashing power is around 40%, Proof of Entropy Minima appears to have only around3218% resistance.
I think the problem is pretty much as described by earlier thread contributors: if you get lucky mining a block with a low enough weight,In short it skews your ability to profit from selfish mininglooks like this fork selection rule is catastrophic for any consensus design.
The problem is this (blocks are letters, attackers are A, honest are H, bracketed number are block hash represented as real number between 0 and 1, so expectation = 0.5):
A0[0.001]<-A1[0.5]<-A2[0.5]<-A3[0.5] => fork weight = 0.001*0.5*0.5*0.5 = 0.000125
H0[ 0.5]<-H1[0.5]<-H2[0.5]<-H3[0.5] => honest chain weight = 0.5*0.5*0.5*0.5 = 0.0625
Both sequences of blocks are equally likely, but if the attacker gets lucky with any block hash, because the fork weight is multiplicative (and will choose the lower weight) he can withhold his fork until it's going to be selected as canon, which appears to be possible at only 18% hash rate.
I hope this hasn't been implemented into any live blockchain, because its vunerable.
Cheers, Paul.
I hope I have understood the protocol well enough, it seems quite simple: branches are weighted by the least probability of being mined based on their hashes.
Here is the full simulation code in python:
Code:
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
def simulate(alpha, num_blocks=20000100000):
honest_chainhonest_weight = 0 # cumulative sum of weight of honest chain
attacker_chainattacker_weight = 0 # cumulative sum of weight of attackers chain
attackers_blocks = 0
honest_blocks = 0
attacker_reward = 0
honest_reward = 0
for _ in range(num_blocks):
r = np.random.rand()
weight = np.log(r)
if r < alpha: # Attacker mines
attacker_chainattacker_weight += weight
attackers_blocks= attackers_blocks += 1
ifattacker_chainattacker_weight < honest_chainhonest_weight:
# attacker reveals branch when it'sgotgoing to be selected as the least probability of being mined block by blockbest branch
attacker_reward += attackers_blocks
honest_reward -= attackers_blocks
# honest miners lose their rewards
honest_reward -= honest_blocks
# start again
attackers_blocks =attacker_chainhonest_blocks = honest_chainattacker_weight = honest_weight = 0
else: # Honest miner mines
honest_chainhonest_weight += weight
honest_reward += 1
honest_blocks += 1
print(alpha, attacker_reward, honest_reward)
if honest_reward > 0:
return attacker_reward / honest_reward
else:
returnfloat("inf")num_blocks
# selfish mining as explained in "Majority is not Enough: Bitcoin Mining is Vulnerable" https://arxiv.org/pdf/1311.0243
# note that gamma is optimistic so this is aupperlower bound
def simulateBitcoin(alpha, num_blocks=20000100000, gamma=0.5):
honest_chainhonest_weight = 0 # Length of honest chain
attacker_chainattacker_weight = 0 # Length of attacker's private fork
attacker_reward = 0
honest_reward = 0
deltaPrev = 0
for _ in range(num_blocks):
deltaPrev =attacker_chainattacker_weight - honest_chainhonest_weight
if np.random.rand() < alpha: # Attacker mines
attacker_chainattacker_weight += 1
if deltaPrev == 0 andattacker_chainattacker_weight == 2:
attacker_reward +=attacker_chainattacker_weight
attacker_chainattacker_weight=honest_chainhonest_weight=0
else: # Honest miner mines
honest_chainhonest_weight += 1
if deltaPrev<=0:
honest_reward +=honest_chainhonest_weight
attacker_chainattacker_weight = honest_chainhonest_weight = 0
elif deltaPrev==1:
# miners chose at random which fork to mine on based on gamma parameter
g = np.random.rand()
if g <= gamma:
attacker_reward += 1
else:
honest_reward += 1
attacker_chainattacker_weight=honest_chainhonest_weight=0
elif deltaPrev>=2:
attacker_reward += deltaPrev+1
attacker_chainattacker_weight = honest_chainhonest_weight = 0
print(alpha, attacker_reward, honest_reward)
return attacker_reward / honest_reward
alphas = np.linspace(0.1505, 0.5, 2040) # 155% to 50% attacker hashing power
results_poem = [simulate(alpha) for alpha in alphas]
results_bitcoin = [simulateBitcoin(alpha) for alpha in alphas]
# Plot results
plt.plot(alphas, results_poem, label="PoEM")
plt.plot(alphas, results_bitcoin, label="Bitcoin")
plt.axhline(y=1, color="red", linestyle="--", label="Attack break-even cost")
plt.xlabel("Attacker Hashrate (α)")
plt.ylabel("Attacker Reward / Honest Reward")
plt.ylim([0, 1.2])
plt.legend()
plt.show()
from collections import defaultdict
import matplotlib.pyplot as plt
def simulate(alpha, num_blocks=
attackers_blocks = 0
honest_blocks = 0
attacker_reward = 0
honest_reward = 0
for _ in range(num_blocks):
r = np.random.rand()
weight = np.log(r)
if r < alpha: # Attacker mines
attackers_blocks
if
# attacker reveals branch when it's
attacker_reward += attackers_blocks
# honest miners lose their rewards
honest_reward -= honest_blocks
# start again
attackers_blocks =
else: # Honest miner mines
honest_reward += 1
print(alpha, attacker_reward, honest_reward)
if honest_reward > 0:
return attacker_reward / honest_reward
else:
return
# selfish mining as explained in "Majority is not Enough: Bitcoin Mining is Vulnerable" https://arxiv.org/pdf/1311.0243
# note that gamma is optimistic so this is a
def simulateBitcoin(alpha, num_blocks=
attacker_reward = 0
honest_reward = 0
deltaPrev = 0
for _ in range(num_blocks):
deltaPrev =
if np.random.rand() < alpha: # Attacker mines
if deltaPrev == 0 and
attacker_reward +=
else: # Honest miner mines
if deltaPrev<=0:
honest_reward +=
elif deltaPrev==1:
# miners chose at random which fork to mine on based on gamma parameter
g = np.random.rand()
if g <= gamma:
attacker_reward += 1
else:
honest_reward += 1
elif deltaPrev>=2:
attacker_reward += deltaPrev+1
print(alpha, attacker_reward, honest_reward)
return attacker_reward / honest_reward
alphas = np.linspace(0.
results_poem = [simulate(alpha) for alpha in alphas]
results_bitcoin = [simulateBitcoin(alpha) for alpha in alphas]
# Plot results
plt.plot(alphas, results_poem, label="PoEM")
plt.plot(alphas, results_bitcoin, label="Bitcoin")
plt.axhline(y=1, color="red", linestyle="--", label="Attack break-even cost")
plt.xlabel("Attacker Hashrate (α)")
plt.ylabel("Attacker Reward / Honest Reward")
plt.ylim([0, 1.2])
plt.legend()
plt.show()
...and the resulting plot is here:
Anyway, as you should be able to see in the graph, compared to selfish mining as described in "Majority is not Enough: Bitcoin Mining is Vulnerable" which the upper bound on break even attacker hashing power is around 40%, Proof of Entropy Minima appears to have only around
The problem is this (blocks are letters, attackers are A, honest are H, bracketed number are block hash represented as real number between 0 and 1, so expectation = 0.5):
A0[0.001]<-A1[0.5]<-A2[0.5]<-A3[0.5] => fork weight = 0.001*0.5*0.5*0.5 = 0.000125
H0[ 0.5]<-H1[0.5]<-H2[0.5]<-H3[0.5] => honest chain weight = 0.5*0.5*0.5*0.5 = 0.0625
Both sequences of blocks are equally likely, but if the attacker gets lucky with any block hash, because the fork weight is multiplicative (and will choose the lower weight) he can withhold his fork until it's going to be selected as canon, which appears to be possible at only 18% hash rate.
I hope this hasn't been implemented into any live blockchain, because its vunerable.
Cheers, Paul.
Version 1
Edited on 16/05/2025, 13:39:39 UTC
I just discovered this post, so forgive my thread reanimation. I happened to be working on a selfish mining simulation for a number of different ideas, and I wanted to post my results for Proof of Entropy Minima here in case they are useful.
I hope I have understood the protocol well enough, it seems quite simple: branches are weighted by the least probability of being mined based on their hashes.
Here is the full simulation code in python:
...and the resulting plot is here:
https://i.imgur.com/CpFH3fT.png
It doesn't show if I tryAnyway, as you should be able to inlinesee in the imagegraph, I get a proxy errorcompared to selfish mining as described in "Majority is not Enough: Bitcoin Mining is Vulnerable" which the upper bound on break even attacker hashing power is around 40%, Proof of Entropy Minima appears to have only around 32% resistance.
Anyway, as you should be able to see in the graph, compared to selfish mining as described in "Majority is not Enough: Bitcoin Mining is Vulnerable" which the lower bound on break even attacker hashing power is around 40%, Proof of Entropy Minima appears to have only around 32% resistance.
I think the problem is pretty much as described by earlier thread contributors: if you get lucky mining a block with a low enough weight, it skews your ability to profit from selfish mining.
Cheers, Paul.
I hope I have understood the protocol well enough, it seems quite simple: branches are weighted by the least probability of being mined based on their hashes.
Here is the full simulation code in python:
Code:
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
def simulate(alpha, num_blocks=20000):
honest_chain = 0 # cumulative sum of weight of honest chain
attacker_chain = 0 # cumulative sum of weight of attackers chain
attackers_blocks = 0
attacker_reward = 0
honest_reward = 0
for _ in range(num_blocks):
r = np.random.rand()
weight = np.log(r)
if r < alpha: # Attacker mines
attacker_chain += weight
attackers_blocks = attackers_blocks + 1
if attacker_chain < honest_chain:
# attacker reveals branch when it's got the least probability of being mined block by block
attacker_reward += attackers_blocks
honest_reward -= attackers_blocks
# start again
attackers_blocks = attacker_chain = honest_chain = 0
else: # Honest miner mines
honest_chain += weight
honest_reward += 1
if honest_reward > 0:
return attacker_reward / honest_reward
else:
return float("inf")
# selfish mining as explained in "Majority is not Enough: Bitcoin Mining is Vulnerable" https://arxiv.org/pdf/1311.0243
# note that gamma is optimistic so this is alowerupper bound
def simulateBitcoin(alpha, num_blocks=20000, gamma=0.5):
honest_chain = 0 # Length of honest chain
attacker_chain = 0 # Length of attacker's private fork
attacker_reward = 0
honest_reward = 0
deltaPrev = 0
for _ in range(num_blocks):
deltaPrev = attacker_chain - honest_chain
if np.random.rand() < alpha: # Attacker mines
attacker_chain += 1
if deltaPrev == 0 and attacker_chain == 2:
attacker_reward += attacker_chain
attacker_chain=honest_chain=0
else: # Honest miner mines
honest_chain += 1
if deltaPrev<=0:
honest_reward += honest_chain
attacker_chain = honest_chain = 0
elif deltaPrev==1:
# miners chose at random which fork to mine on based on gamma parameter
g = np.random.rand()
if g <= gamma:
attacker_reward += 1
else:
honest_reward += 1
attacker_chain=honest_chain=0
elif deltaPrev>=2:
attacker_reward += deltaPrev+1
attacker_chain = honest_chain = 0
return attacker_reward / honest_reward
alphas = np.linspace(0.15, 0.5, 20) # 15% to 50% attacker hashing power
results_poem = [simulate(alpha) for alpha in alphas]
results_bitcoin = [simulateBitcoin(alpha) for alpha in alphas]
# Plot results
plt.plot(alphas, results_poem, label="PoEM")
plt.plot(alphas, results_bitcoin, label="Bitcoin")
plt.axhline(y=1, color="red", linestyle="--", label="Attack break-even cost")
plt.xlabel("Attacker Hashrate (α)")
plt.ylabel("Attacker Reward / Honest Reward")
plt.ylim([0, 1.2])
plt.legend()
plt.show()
from collections import defaultdict
import matplotlib.pyplot as plt
def simulate(alpha, num_blocks=20000):
honest_chain = 0 # cumulative sum of weight of honest chain
attacker_chain = 0 # cumulative sum of weight of attackers chain
attackers_blocks = 0
attacker_reward = 0
honest_reward = 0
for _ in range(num_blocks):
r = np.random.rand()
weight = np.log(r)
if r < alpha: # Attacker mines
attacker_chain += weight
attackers_blocks = attackers_blocks + 1
if attacker_chain < honest_chain:
# attacker reveals branch when it's got the least probability of being mined block by block
attacker_reward += attackers_blocks
honest_reward -= attackers_blocks
# start again
attackers_blocks = attacker_chain = honest_chain = 0
else: # Honest miner mines
honest_chain += weight
honest_reward += 1
if honest_reward > 0:
return attacker_reward / honest_reward
else:
return float("inf")
# selfish mining as explained in "Majority is not Enough: Bitcoin Mining is Vulnerable" https://arxiv.org/pdf/1311.0243
# note that gamma is optimistic so this is a
def simulateBitcoin(alpha, num_blocks=20000, gamma=0.5):
honest_chain = 0 # Length of honest chain
attacker_chain = 0 # Length of attacker's private fork
attacker_reward = 0
honest_reward = 0
deltaPrev = 0
for _ in range(num_blocks):
deltaPrev = attacker_chain - honest_chain
if np.random.rand() < alpha: # Attacker mines
attacker_chain += 1
if deltaPrev == 0 and attacker_chain == 2:
attacker_reward += attacker_chain
attacker_chain=honest_chain=0
else: # Honest miner mines
honest_chain += 1
if deltaPrev<=0:
honest_reward += honest_chain
attacker_chain = honest_chain = 0
elif deltaPrev==1:
# miners chose at random which fork to mine on based on gamma parameter
g = np.random.rand()
if g <= gamma:
attacker_reward += 1
else:
honest_reward += 1
attacker_chain=honest_chain=0
elif deltaPrev>=2:
attacker_reward += deltaPrev+1
attacker_chain = honest_chain = 0
return attacker_reward / honest_reward
alphas = np.linspace(0.15, 0.5, 20) # 15% to 50% attacker hashing power
results_poem = [simulate(alpha) for alpha in alphas]
results_bitcoin = [simulateBitcoin(alpha) for alpha in alphas]
# Plot results
plt.plot(alphas, results_poem, label="PoEM")
plt.plot(alphas, results_bitcoin, label="Bitcoin")
plt.axhline(y=1, color="red", linestyle="--", label="Attack break-even cost")
plt.xlabel("Attacker Hashrate (α)")
plt.ylabel("Attacker Reward / Honest Reward")
plt.ylim([0, 1.2])
plt.legend()
plt.show()
...and the resulting plot is here:
Cheers, Paul.
Original archived Re: Improved Measurement of Proof-of-Work using entropy
Scraped on 16/05/2025, 13:09:31 UTC
I just discovered this post, so forgive my thread reanimation. I happened to be working on a selfish mining simulation for a number of different ideas, and I wanted to post my results for Proof of Entropy Minima here in case they are useful.
I hope I have understood the protocol well enough, it seems quite simple: branches are weighted by the least probability of being mined based on their hashes.
Here is the full simulation code in python:
...and the resulting plot is here:
https://i.imgur.com/CpFH3fT.png
It doesn't show if I try to inline the image, I get a proxy error.
Anyway, as you should be able to see in the graph, compared to selfish mining as described in "Majority is not Enough: Bitcoin Mining is Vulnerable" which the lower bound on break even attacker hashing power is around 40%, Proof of Entropy Minima appears to have only around 32% resistance.
I think the problem is pretty much as described by earlier thread contributors: if you get lucky mining a block with a low enough weight, it skews your ability to profit from selfish mining.
Cheers, Paul.
I hope I have understood the protocol well enough, it seems quite simple: branches are weighted by the least probability of being mined based on their hashes.
Here is the full simulation code in python:
Code:
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
def simulate(alpha, num_blocks=20000):
honest_chain = 0 # cumulative sum of weight of honest chain
attacker_chain = 0 # cumulative sum of weight of attackers chain
attackers_blocks = 0
attacker_reward = 0
honest_reward = 0
for _ in range(num_blocks):
r = np.random.rand()
weight = np.log(r)
if r < alpha: # Attacker mines
attacker_chain += weight
attackers_blocks = attackers_blocks + 1
if attacker_chain < honest_chain:
# attacker reveals branch when it's got the least probability of being mined block by block
attacker_reward += attackers_blocks
honest_reward -= attackers_blocks
# start again
attackers_blocks = attacker_chain = honest_chain = 0
else: # Honest miner mines
honest_chain += weight
honest_reward += 1
if honest_reward > 0:
return attacker_reward / honest_reward
else:
return float("inf")
# selfish mining as explained in "Majority is not Enough: Bitcoin Mining is Vulnerable" https://arxiv.org/pdf/1311.0243
# note that gamma is optimistic so this is a lower bound
def simulateBitcoin(alpha, num_blocks=20000, gamma=0.5):
honest_chain = 0 # Length of honest chain
attacker_chain = 0 # Length of attacker's private fork
attacker_reward = 0
honest_reward = 0
deltaPrev = 0
for _ in range(num_blocks):
deltaPrev = attacker_chain - honest_chain
if np.random.rand() < alpha: # Attacker mines
attacker_chain += 1
if deltaPrev == 0 and attacker_chain == 2:
attacker_reward += attacker_chain
attacker_chain=honest_chain=0
else: # Honest miner mines
honest_chain += 1
if deltaPrev<=0:
honest_reward += honest_chain
attacker_chain = honest_chain = 0
elif deltaPrev==1:
# miners chose at random which fork to mine on based on gamma parameter
g = np.random.rand()
if g <= gamma:
attacker_reward += 1
else:
honest_reward += 1
attacker_chain=honest_chain=0
elif deltaPrev>=2:
attacker_reward += deltaPrev+1
attacker_chain = honest_chain = 0
return attacker_reward / honest_reward
alphas = np.linspace(0.15, 0.5, 20) # 15% to 50% attacker hashing power
results_poem = [simulate(alpha) for alpha in alphas]
results_bitcoin = [simulateBitcoin(alpha) for alpha in alphas]
# Plot results
plt.plot(alphas, results_poem, label="PoEM")
plt.plot(alphas, results_bitcoin, label="Bitcoin")
plt.axhline(y=1, color="red", linestyle="--", label="Attack break-even cost")
plt.xlabel("Attacker Hashrate (α)")
plt.ylabel("Attacker Reward / Honest Reward")
plt.ylim([0, 1.2])
plt.legend()
plt.show()
from collections import defaultdict
import matplotlib.pyplot as plt
def simulate(alpha, num_blocks=20000):
honest_chain = 0 # cumulative sum of weight of honest chain
attacker_chain = 0 # cumulative sum of weight of attackers chain
attackers_blocks = 0
attacker_reward = 0
honest_reward = 0
for _ in range(num_blocks):
r = np.random.rand()
weight = np.log(r)
if r < alpha: # Attacker mines
attacker_chain += weight
attackers_blocks = attackers_blocks + 1
if attacker_chain < honest_chain:
# attacker reveals branch when it's got the least probability of being mined block by block
attacker_reward += attackers_blocks
honest_reward -= attackers_blocks
# start again
attackers_blocks = attacker_chain = honest_chain = 0
else: # Honest miner mines
honest_chain += weight
honest_reward += 1
if honest_reward > 0:
return attacker_reward / honest_reward
else:
return float("inf")
# selfish mining as explained in "Majority is not Enough: Bitcoin Mining is Vulnerable" https://arxiv.org/pdf/1311.0243
# note that gamma is optimistic so this is a lower bound
def simulateBitcoin(alpha, num_blocks=20000, gamma=0.5):
honest_chain = 0 # Length of honest chain
attacker_chain = 0 # Length of attacker's private fork
attacker_reward = 0
honest_reward = 0
deltaPrev = 0
for _ in range(num_blocks):
deltaPrev = attacker_chain - honest_chain
if np.random.rand() < alpha: # Attacker mines
attacker_chain += 1
if deltaPrev == 0 and attacker_chain == 2:
attacker_reward += attacker_chain
attacker_chain=honest_chain=0
else: # Honest miner mines
honest_chain += 1
if deltaPrev<=0:
honest_reward += honest_chain
attacker_chain = honest_chain = 0
elif deltaPrev==1:
# miners chose at random which fork to mine on based on gamma parameter
g = np.random.rand()
if g <= gamma:
attacker_reward += 1
else:
honest_reward += 1
attacker_chain=honest_chain=0
elif deltaPrev>=2:
attacker_reward += deltaPrev+1
attacker_chain = honest_chain = 0
return attacker_reward / honest_reward
alphas = np.linspace(0.15, 0.5, 20) # 15% to 50% attacker hashing power
results_poem = [simulate(alpha) for alpha in alphas]
results_bitcoin = [simulateBitcoin(alpha) for alpha in alphas]
# Plot results
plt.plot(alphas, results_poem, label="PoEM")
plt.plot(alphas, results_bitcoin, label="Bitcoin")
plt.axhline(y=1, color="red", linestyle="--", label="Attack break-even cost")
plt.xlabel("Attacker Hashrate (α)")
plt.ylabel("Attacker Reward / Honest Reward")
plt.ylim([0, 1.2])
plt.legend()
plt.show()
...and the resulting plot is here:
https://i.imgur.com/CpFH3fT.png
It doesn't show if I try to inline the image, I get a proxy error.
Anyway, as you should be able to see in the graph, compared to selfish mining as described in "Majority is not Enough: Bitcoin Mining is Vulnerable" which the lower bound on break even attacker hashing power is around 40%, Proof of Entropy Minima appears to have only around 32% resistance.
I think the problem is pretty much as described by earlier thread contributors: if you get lucky mining a block with a low enough weight, it skews your ability to profit from selfish mining.
Cheers, Paul.