Математика и алгоритмы биткоина.

[fxpc]

Я тут на досуге поэкспериментировал с нахождением sha256 от чисел. Получил интересные результаты
Если посчитать все хэши чисел от 1 до 1 000 000, то среди них будут:

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

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

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

23 хэша у которых четыре нуля в начале, среднее число переборов = 42065, при этом в 69.6 % случаев, требуемое число переборов меньше среднего


Таким образом оказалось, что решения с заданной сложностью распределены неравномерно. Значит sha256 не дает нормального распределения? Можно ли эту особенность использовать как преимущество в майнинге?
Сейчас на слуху какой-то супер секретный алгоритм асик буст. Кто что про него знает? Я ничего толкового нагуглить не могу.

А для sha256d результат аналогичен? В каком формате были числа? Не стоит воспринимать равномерность так буквально. "Надёжный" RNG может выдать число 42 хоть 10 раз подряд, а ненадёжный покажет равномерное распределение уже на малой выборке, что говорит о его предсказуемости.

[amaclin1]

Сейчас на слуху какой-то супер секретный алгоритм асик буст. Кто что про него знает? Я ничего толкового нагуглить не могу.

Никакой он не секретный
Несколько оптимизаций, которые позволяют перебрать большее количество вариантов
sha256d от 80 байт заголовка используя меньшее количество вычислений sha256

[fxpc]

Сейчас на слуху какой-то супер секретный алгоритм асик буст. Кто что про него знает? Я ничего толкового нагуглить не могу.

Никакой он не секретный
Несколько оптимизаций, которые позволяют перебрать большее количество вариантов
sha256d от 80 байт заголовка используя меньшее количество вычислений sha256

Эти оптимизации основаны на том что хеширование двойное и HMAC не используется?

[amaclin1]

Эти оптимизации основаны на том что хеширование двойное и HMAC не используется?

Ну ты уж совсем не делай вид, что я на экзамене и тебе зачет сдаю
В общем да. Ещё связано с тем, что sha256 - блочный алгоритм. То есть на первом проходе
отдельно и по сути параллельно хэшируются первые 64 байта заголовка блока и отдельно
оставшиеся 16 (я по памяти, лень искать).

Помог бы в этом случае HMAC куда-нибудь засунутый - не знаю. Скорее всего помогло бы иное
построение заголовка блока - чтобы, например, merkle-hash и hash предыдущего блока шли
бы не друг за другом, а "расческой" - то есть байт от одного, байт от другого...

[kzv]

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 итераций.

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

[amaclin1]

Вот результаты двойного хэширования чисел от 1 до 1000 000
[...]
Если я ничего не напутал конечно...

Напутал, разумеется.
Возьми другие диапазоны, например от 1000001 до 2000000,
от 2000001 до 3000000 и так далее и попробуй повторить те же результаты.

Хотя если имеется в виду "при этом в хх.х % случаев, требуемое число переборов меньше среднего"
то опять же не значит, что хх.х - это какая-то магия. Это - матожидание. Иногда - находится за
Х переборов, иногда за Y. Чтобы найти среднее значение - надо не просто брать среднее
между Х и Y, а с учетом их встречаемости. Там гауссиана должна получиться в результате.

[kzv]

В других диапазонах все то же самое.
Я для этих целей сделал простенькую страничку
https://trade.multicoins.org/test.html

[fxpc]

Эти оптимизации основаны на том что хеширование двойное и HMAC не используется?

Ну ты уж совсем не делай вид, что я на экзамене и тебе зачет сдаю
В общем да. Ещё связано с тем, что sha256 - блочный алгоритм. То есть на первом проходе
отдельно и по сути параллельно хэшируются первые 64 байта заголовка блока и отдельно
оставшиеся 16 (я по памяти, лень искать).

Помог бы в этом случае HMAC куда-нибудь засунутый - не знаю. Скорее всего помогло бы иное
построение заголовка блока - чтобы, например, merkle-hash и hash предыдущего блока шли
бы не друг за другом, а "расческой" - то есть байт от одного, байт от другого...

И в мыслях не было, просто поделился своим предположением
Бес меня попутал с этими бустами, мог бы сам догадаться, знаю же про блочность sha256 и про то что при хешировании уникальную соль следует перед паролями ставить именно из-за этого, но подумалось что могли что-то похитрее откопать. Да, в 256-битной версии блок как раз 64 байта.

Наверно HMAC бы не помог, не туда меня понесло. Данные в 64-байтном блоке редко меняются, поэтому буст останется и после "расчёсывания". Возможно эффективнее было бы изменить порядок заголовков при расчёте хеша, чтобы в 64 байта попадал перебираемый nonce.

[amaclin1]

Возможно эффективнее было бы изменитть порядок заголовков при расчёте хеша, чтобы в 64 байта попадал перебираемый nonce.

Тогда в 16-байтовом остатке (80-64) вообще будет константное значение, которое можно будет 1 раз вычислить на пуле

[amaclin1]

Данные в 64-байтном блоке редко меняются

Там меркль-хэш лежит. Но можно подобрать транзакции так, что меркль-хэш
будет заканчиваться на те же 4 байта, что и другой меркль-хэш. Таким образом,
опять же - второй блок неизменен, а крутим не нонс, а версию блока.

[fxpc]

Возможно эффективнее было бы изменить порядок заголовков при расчёте хеша, чтобы в 64 байта попадал перебираемый nonce.

Тогда в 16-байтовом остатке (80-64) вообще будет константное значение, которое можно будет 1 раз вычислить на пуле

Будет, но 16 уже не так эффективно как текущие 64 и в общем-то это гипотетически решаемо. Очень абстрактно - считаем в одном 64-байтном блоке hash предыдущего блока|nonce|..., в следующем 64-байтном блоке считаем merkle-hash|nonce|... и тд.

Данные в 64-байтном блоке редко меняются

Там меркль-хэш лежит. Но можно подобрать транзакции так, что меркль-хэш
будет заканчиваться на те же 4 байта, что и другой меркль-хэш. Таким образом,
опять же - второй блок неизменен, а крутим не нонс, а версию блока.

Видимо версию придётся запихивать во все 64-байтные блоки во избежание такого онанизма.

[amaclin1]

Будет, но 16 уже не так эффективно как текущие 64 и в общем-то это гипотетически решаемо. Очень абстрактно - считаем в одном 64-байтном блоке hash предыдущего блока|nonce|..., в следующем 64-байтном блоке считаем merkle-hash|nonce|... и тд.

асик-буст - это оптимизации в существующем биткойне.
там в том числе можно вообще не включать транзакции в блок и сэкономить
время на расчете самого меркль-хэш. мы пока не рассматриваем вопрос "как сделать
так, чтобы читерства вообще не было" - ибо опять же пока майнинг выгоден в пересчете
на фиат - способ читерства найдется. а если майнинг будет невыгоден - то никто им
заниматься не станет, а если и станет - то только до первой атаки-51

[kzv]

Будет, но 16 уже не так эффективно как текущие 64 и в общем-то это гипотетически решаемо. Очень абстрактно - считаем в одном 64-байтном блоке hash предыдущего блока|nonce|..., в следующем 64-байтном блоке считаем merkle-hash|nonce|... и тд.

асик-буст - это оптимизации в существующем биткойне.
там в том числе можно вообще не включать транзакции в блок и сэкономить
время на расчете самого меркль-хэш. мы пока не рассматриваем вопрос "как сделать
так, чтобы читерства вообще не было" - ибо опять же пока майнинг выгоден в пересчете
на фиат - способ читерства найдется. а если майнинг будет невыгоден - то никто им
заниматься не станет, а если и станет - то только до первой атаки-51

Меркла разве не пул считает? Асик тупо nonce перебирает и хэширует.
Оптимизировать внутри асика можно только алгоритм перебора соли. Или нет?

[amaclin1]

Меркла разве не пул считает? Асик тупо nonce перебирает и хэширует.
Оптимизировать внутри асика можно только алгоритм перебора соли. Или нет?

Поле nonce - всего 32 бита.
Асик на 14 TH/s перебирает этот интервал за доли секунды.
Это, как вы понимаете, бессмысленно - несколько раз в секунду лезть на пул за новыми данными.
Так что давно в протоколе стратум передается дерево меркла (может быть как-то частично подсчитанное)
Асик перебирает не только нонс в заголовке блока - он также перебирает экстранонс
в scriptSig coinbase-транзакции. Считает получившийся merkle-hash, формирует 80-байтовый
заголовок и там уже перебирает нонс.

[kzv]

А асик буст это я так понимаю новый протокол общения асика и пула? Более быстрый протокол. Раз он запатентован, то должно же быть описание патента в открытом доступе?

[amaclin1]

А асик буст это я так понимаю новый протокол общения асика и пула? Более быстрый протокол.
Раз он запатентован, то должно же быть описание патента в открытом доступе?

В гугле забанили? Не, я понимаю, зима, тоска... У меня у самого в жизни какая-то черная полоса пошла.
https://www.asicboost.com/
https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf

[fxpc]

А асик буст это я так понимаю новый протокол общения асика и пула? Более быстрый протокол.
Раз он запатентован, то должно же быть описание патента в открытом доступе?

В гугле забанили? Не, я понимаю, зима, тоска... У меня у самого в жизни какая-то черная полоса пошла.
https://www.asicboost.com/
https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf

Ты понимаешь что эти кудесники патентовать собрались? Я лично нет.
Всё та же полоса что с начала года? Печально.

[amaclin1]

Ты понимаешь что эти кудесники патентовать собрались? Я лично нет.
Всё та же полоса что с начала года? Печально.

Старею. Жизнь проходит в суете. Помыться-побриться-одеться-сходить-в-магазин
за-хлебом-почитать-новости... И так каждый день без каких-то перспектив вырваться
из этой "зоны физического (но не душевного) комфорта"

...Не сердитесь, Зося, Примите во внимание атмосферный столб. Мне кажется даже, что он давит на
меня значительно сильнее, чем на других граждан. [...] А что я сделал до сих пор? Учения я не
создал, учеников разбазарил, мертвого Паниковского не воскресил...

Про патенты я не особо в курсе как и что там патентуют. Подозреваю, что там все основано
на том, насколько обтекаемыми формами будет все описано. Кто-то же патентовал двойной
(или тройной?) клик мышкой? Так почему бы не запатентовать "более технологичный способ
добычи биткойнов"? Мы же можем запатентовать "более технологичный способ добычи железа
из руды в расчете на джоуль потраченной энергии"?

[amaclin1]

Видимо версию придётся запихивать во все 64-байтные блоки во избежание такого онанизма.

Версию чего? Блока? Ну так от того, что мы дополним данные еще одним фиксированным числом -
хэш этих данных все равно останется фиксированным при пересчете других данных. Опять же - один
раз посчитали, 4 миллиарда раз используем.

Тут можно было бы так сделать: мы хэшируем не 80 байт заголовка блока байт-за-байтом, а сперва проводим
некоторое "усечение длины" - допустим, ксорим (делаем битовую операцию XOR) меркль-хэша и
хэша предыдущего блока. Тем самым у нас не два 64-байтных блока, а один получается (и даже еще
куча места для увеличения размера nonce остается). И вот над этим 64-байтным значением уже
изгаляемся. Это хард-форк, разумеется. Но, я вообще-то, не настоящий сварщик: меня усовершенствования
биткойна и других крипт, анти-асик механизны интересуют чисто гипотетически.

[fxpc]

Ты понимаешь что эти кудесники патентовать собрались? Я лично нет.
Всё та же полоса что с начала года? Печально.

Старею. Жизнь проходит в суете. Помыться-побриться-одеться-сходить-в-магазин
за-хлебом-почитать-новости... И так каждый день без каких-то перспектив вырваться
из этой "зоны физического (но не душевного) комфорта"

...Не сердитесь, Зося, Примите во внимание атмосферный столб. Мне кажется даже, что он давит на
меня значительно сильнее, чем на других граждан. [...] А что я сделал до сих пор? Учения я не
создал, учеников разбазарил, мертвого Паниковского не воскресил...

Такая суета в любом возрасте когда сам себе отец. Имхо, решение только одно - как-то отвлекаться и делать что-то для души, возможно глобальное, чтобы до могильной плиты не идти каждый день назад в завтра такое же как вчера. Я никуда не разбазарился, если приведённая тобой цитата Остапа про учеников не слишком иносказательна относительно данной ситуации.

Про патенты я не особо в курсе как и что там патентуют. Подозреваю, что там все основано
на том, насколько обтекаемыми формами будет все описано. Кто-то же патентовал двойной
(или тройной?) клик мышкой? Так почему бы не запатентовать "более технологичный способ
добычи биткойнов"? Мы же можем запатентовать "более технологичный способ добычи железа
из руды в расчете на джоуль потраченной энергии"?

Пардон, я совершенно некорректно выразился. В штатах конечно можно патентовать даже технику почёса левой пятки, на этот счёт вопросов нет, мне просто с попокорном интересно как они этот патент собираются защищать хотя бы в других юрисдикциях, а в интернетах совсем тяжко будет. Выложит какой-нибудь анонимус на форуме или в даркнете код с этим бустом и потрачено - все майнят, автор сосёт писос обмазавшись своим патентом. Давай обходиться без аналогий с рудой, адептов и так хлебом не корми дай попиздеть что биток это цифровое золото.

Видимо версию придётся запихивать во все 64-байтные блоки во избежание такого онанизма.

Версию чего? Блока? Ну так от того, что мы дополним данные еще одним фиксированным числом -
хэш этих данных все равно останется фиксированным при пересчете других данных. Опять же - один
раз посчитали, 4 миллиарда раз используем.

Тут можно было бы так сделать: мы хэшируем не 80 байт заголовка блока байт-за-байтом, а сперва проводим
некоторое "усечение длины" - допустим, ксорим (делаем битовую операцию XOR) меркль-хэша и
хэша предыдущего блока. Тем самым у нас не два 64-байтных блока, а один получается (и даже еще
куча места для увеличения размера nonce остается). И вот над этим 64-байтным значением уже
изгаляемся. Это хард-форк, разумеется. Но, я вообще-то, не настоящий сварщик: меня усовершенствования
биткойна и других крипт, анти-асик механизны интересуют чисто гипотетически.

Не, ты не понял. Сейчас все заголовки блока подаются на вход единоразово по порядку. А можно повторно в каждый 64-байтный чанк на вход подавать версию, nonce и прочее, чтобы нельзя было перебирать версию или nonce в отдельном чанке без пересчёта остальных. Да мне в общем-то тоже монопенисуально на проблемы битка и прочих лохчейнов, не более чем разминка для мозга.