sha256d это то же самое, что sha256 от sha256.
Вот результаты двойного хэширования чисел от 1 до 1000 000

62404 хэшей у которых один или больше нулей в начале, среднее число переборов = 16, при этом в 64.3% случаев, требуемое число переборов меньше среднего

3895 хэшей у которых два или больше нулей в начале, среднее число переборов = 257, при этом в 63.0 % случаев, требуемое число переборов меньше среднего

259 хэшей у которых три или больше нулей в начале, среднее число переборов = 3845, при этом в 61.0 % случаев, требуемое число переборов меньше среднего

16 хэшей у которых четыре нуля в начале, среднее число переборов = 60312, при этом в 68.8 % случаев, требуемое число переборов меньше среднего

То есть результаты практически идентичны одиночному хэшированию.

Рассмотрим несколько способов поиска хэша с заданной сложностью
1. Последовательный перебор nonce от нуля
2. Последовательный перебор не от нуля, а от рэндомной точки
3. Рэндомный перебор nonce.

Теперь каждый из способов отдельно. Для наглядности пусть nonce может изменяться от 0 до 1 000 000 и пусть мы ищем хэш с тремя нулями

Последовательный перебор nonce от нуля.
В этом случае майнер найдет хэш в среднем за 3845 итераций, но с вероятностью 61% итераций будет меньше. То есть Из 100 найденных хэшей, 61 хэш будет найден быстрее чем за 3845 итераций.

Последовательный перебор не от нуля, а от рэндомной точки
В этом случае майнер найдет хэш в среднем за 3845 / 2  = 1923 итераций, при этом с вероятностью 39.4 % итераций будет меньше (это я дополнительно посчитал). То есть из 100 хэшей, 40 будут найдены быстрей чем за 1923 итераций.
 
В два раза быстрее чем в первом случае! Это потому что рэндомное начало, при нормальном распределении, будет падать в среднем на центр отрезка для перебора.
Так же в этом способе с вероятностью 259/1000000 хэш будет найден сразу.

Рэндомный перебор nonce.
В этом случае можно вообще никогда не найти нужный хэш, но с вероятностью 259/1000000 хэш будет найден с первой попытки. Если рэндом распределен нормально, то вероятности должны складываться и значит после 1923 итераций вероятность найти хэш будет уже 50%. То есть из 100 хэшей, 50 будут найдены быстрей чем за 1923 итераций.

В итоге получается, что первый алгоритм самый медленный. Третий алгоритм самый быстрый. Если я ничего не напутал конечно...