Topic: Математика и алгоритмы биткоина. - page 4. (Read 17569 times)

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

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


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

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

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

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

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

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

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

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

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

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

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

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

Равномерно они будут распределены на значительно больших выборках, чем 1м
То, что у тебя получилось не 256, а 259 - это в порядке вещей, потому что выборка была маленькая
Флуктации рандома, так сказать

это на одинарной или двойной SHA?

В майнинге двойная(то есть SHA(SHA(x)) ) - если не трудно, то проверьте то-же самое на двойной?..

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

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

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

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

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


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

Ребят, человеку с уровнем знаний математики на уровне 8 класса сколько лет осталось изучать сей предмет, чтобы понимать все, что вы тут пишите? При условии, что в день есть только 1 час на это дело

Ребят, человеку с уровнем знаний математики на уровне 8 класса сколько лет осталось изучать сей предмет, чтобы понимать все, что вы тут пишите? При условии, что в день есть только 1 час на это дело

Да, сорри. Пьяный был)

Было бы интересно узнать какой прирост производительности подписывания при увеличении потребления памяти и времени старта, но к сожалению, не осилю. Как думаешь, оптимизирован ли вообще алгоритм подписывания в либе битка? Bottleneck в скорости верификации и могли остановиться на её оптимизации, вроде ни у кого нет необходимости в подписывании 100500 транзакций в секунду.


Вероятность есть, там ещё те рукожопы. Возможно атакующему нужен был публичный ключ жертвы для вычисления из него и неслучайного значения R приватного ключа. Онлайн кошельки регулярно факапятся с RNG. Имхо, помогло бы даже подмешивание к кривому RNG каких-то пользовательских хешей от хешей, но это не точно. Удивляет что рукожопы не додумались даже до этого, полностью положившись на RNG.
https://www.coindesk.com/hacker-returns-225-btc-taken-blockchain-wallets
https://99bitcoins.com/blockchain-info-wallet-users-get-stolen-service-patched-the-bug-and-assures-it-will-refund-everyone/