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?