Proposition for better difficulty PoW computation
Created by: M5oul
I propose a better way to compute Proof of Work difficulty to have numbers more explicit and which represents in a more realistic way how strong machines are working on it.
Definitions
-
H
: hexadecimal possibilities, each char can have 16 values:[0-9A-F]
. -
P
: valid possibilities -
pos
: position on the string
Current computing difficulty
Proof of Work protocol documentation on how difficulty is currently computed. Currently difficulty is calculated with a sum of difficulties of each char to appear:
Difficulty = Σ (pos = 0 ; pos += 1 ; max(len)) [H - P(pos) + 1] Difficulty = [H - P(pos(0)) + 1] + [H - P(pos(1)) + 1] + [H - P(pos(n)) + 1] + [H - P(pos(n+1)) + 1]…
For instance: to match 0000*
, difficulty = 16 × 4 = 64.
Compute difficulty proposition
Computation must be done with multiplication to fit with probabilities rules:
Difficulty = Π (pos = 0 ; pos += 1 ; max(len)) [H - P(pos) + 1] Difficulty = [H - P(pos(0)) + 1] × [H - P(pos(1)) + 1] × [H - P(pos(n)) + 1] × [H - P(pos(n+1)) + 1]…
For instance: to match 0000*
, difficulty = 16⁴ = 65.563.
Probability
With this difficulty computing, we could also compute probability to found a valid block at each test:
Probability = 1 / Difficulty
Results comparison table
Match | Σ Difficulty | Π Difficulty | Probability |
---|---|---|---|
***** = [0-9A-F]****
|
1 | 1 | 1/1 |
[0-9]**** |
7 | (16 - 10 + 1) = 7 | 1/(16 - 10 + 1) = 1/7 |
[0-1]**** |
15 | (16 - 2 + 1) = 15 | 1/(16 - 2 + 1) = 1/15 |
0**** |
16 | 16 | 1/[16 - 1 + 1] = 1/16 |
0[0-9]*** |
16 + (16 - 10 + 1) = 24 | 16 × (16 - 10 + 1) = 112 | 1/112 |
00*** |
16 × 2 = 32 | 16² = 256 | 1/16² |
0000* |
16 × 4 = 64 | 16⁴ = 65.563 | 1/16⁴ |
0000[0-5] |
16 × 4 + 6 = 70 | 16⁴ × (16 - 10) = 393.216 | 1/[16⁴ × (16 - 10)] |
As you could see 70 is very different than 393k.
Implementation
I don't know what do that means for implementation. May be, only changing calculation formula? Does it impact PoW computation?