Difficulty scales very poorly

[sfan5]

The default of 4 seems to take about 1-2 seconds on my desktop machine.
While I have seen another site use a difficulty of 5 and take 20+ seconds.

Since the leading zeros are checked on the hex-string and not bit-based, increasing difficulty by one will require 4 more zero bits, which increases the computational complexity 16 times.
For more gradual scaling it should check the number of leading zero bits.

[JasonLovesDoggo]

#240 fixes this

[nicoonoclaste]

For more gradual scaling it should check the number of leading zero bits.

FWIW, that's still an intrinsically-exponential scale. The simplest linear difficulty mechanism I can think of, would be to require a response which hashes (along with the challenge) to an integer greater than difficulty threshold = f(difficulty). (See below)

Of course, human factors are a thing and this would likely need a scaling factor in place instead of telling people to set their difficulty to 1329227995784915872903807060280344576 or such, but it could even be chosen such that the current difficulty scale maps cleanly, say new ≍ 16ᵒˡᵈ.
(Technically, that's only equivalent if the challenge hash is a PRF, but that's a standard cryptographic assumption and quite reasonable here)

[Xe]

Wouldn't that still be kinda exponential?

[nicoonoclaste]

Wouldn't that still be kinda exponential?

The likelyhood of success, for a random solution, would be p = 1 - threshold/2ˡ (with l the hash length)
Assuming that successive trials are (statistically) independent, the expected number of attempts before success would be 1/p.
So it's not exponential, but you are right that it's not quite linear (I was thinking likelyhood, not expectation)

If we want the difficulty to be the (expected) number of attempts, that would be difficulty = 1/p, i.e. threshold = 2ˡ (1 - 1/difficulty). That's functionally equivalent to requiring solution hashes lesser than 2ˡ / difficulty, which is also a touch more implementation-friendly.

PS: since the success probability in the old (nibble-based) system is 16⁻ᵒˡᵈ, they match for new = 16ᵒˡᵈ.

[compilade]

I think it would be possible to use fractional bits as the difficulty, to allow for much more fine-grained steps, even if still exponential. At least it should be relatively intuitive that a difficulty of 15.5 bits is somewhere between 15 bits and 16 bits (√2 times bigger than $2^{15}$ to be exact). (and if backward-compatibility with existing configs using nibble difficulty is desired, scaling by 4 should be easy and should still keep the same possible fractional granularity)

See https://gist.github.com/compilade/9b16624b81f93fece2637347c27d0bd3 and the example output (in a comment of that gist) for a proof of concept of converting a floating-point difficulty to the corresponding max acceptable hash value (in C, but max_hash_f64 should be easy to adapt to other languages, as long as there is some way to extract the exponent and mantissa of a floating-point number (e.g. by manually unpacking the bits (see https://float.exposed/), or with frexp(3)))

Verifying whether a hash is small enough can then be done relatively simply with the equivalent of memcmp(3) between the hash buffer and the max hash from the difficulty.

Calculating the max hash with fractional difficulty every time might be slightly slower than the pure integer masking approach, but it's also possible to cache the max hash if it's used for many comparisons (e.g. when the client is searching for a valid hash, or when there are very few distinct difficulties configured), in which case it should be similar in speed.

[mwoelke]

While the bitcoin paper claims to scale difficulty by requiring a certain amount of leading zeroes (like hashcash), bitcoin actually implements a more granular (but still really simple!) mechanism:

A 4-byte target value is determined. This target value is simply $2^{32}-1$ (so the max 4 byte value) divided by the difficulty parameter. The first 4 bytes of each calculated hash is then compared with this target value. If the first 4 bytes are smaller than the target value, the hash is a valid solution.

As a result, the chance to find a solution is simply $\frac{1}{difficulty}$ , meaning it grows linear with the difficulty value!

Just to show how dead simple this is, here are the relevant parts copy-pasted from my PoW implementation:

//calculate target
const target = Math.floor((2 ** 32 - 1) / difficulty);
hash = [ ... calculate a hash ... ]
if(parseInt(hash.slice(0, 8), 16) <= target) {
   // hash is a valid solution!
}

Of course, transitioning to this mechanism would require to somehow migrate existing setups with their configured difficulty parameter. A value of 4 for example (which seems default as of now) would be way too weak, as this would mean that 1/4 of all possible hashes would be a valid solution.

Btw, I think @compilade is saying the same thing for the most part, I just wanted to share my knowledge :)

Very cool project by the way, found this because of the arch wiki!