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

[amaclin1]

разминка для мозга и не более.

Там два вектора атаки было overt и covert - кажется так назывались.
Я щас уже не вспомню что к чему.
Из того что помню - можно при неизменных полях, в том числе и nonce менять неиспользуемые
биты в версии блока (второй чанк остается без изменений и его пересчитывать не нужно)
Можно в некоторых пределах использовать поле таймстампа блока (но это уже совсем мелочевка)

Можно подобрать два меркль-хэша, которые заканчиваются на одинаковые 4 байта (то, что
зовется "Tail" на рисунке 2 https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf ) и опять же
крутить не nonce, а version. Короче, меня не слушайте, разбирайтесь сами. Я в этом только
"по верхам" понимаю.

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

Ну ты, блин, философ. Я так на Григория Перельмана стану похожим - он тоже доказывал
для души гипотезу Пуанкаре и совсем потерял связь с реальным миром.

[fxpc]

разминка для мозга и не более.

Там два вектора атаки было overt и covert - кажется так назывались.
Я щас уже не вспомню что к чему.
Из того что помню - можно при неизменных полях, в том числе и nonce менять неиспользуемые
биты в версии блока (второй чанк остается без изменений и его пересчитывать не нужно)
Можно в некоторых пределах использовать поле таймстампа блока (но это уже совсем мелочевка)

Можно подобрать два меркль-хэша, которые заканчиваются на одинаковые 4 байта (то, что
зовется "Tail" на рисунке 2 https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf ) и опять же
крутить не nonce, а version. Короче, меня не слушайте, разбирайтесь сами. Я в этом только
"по верхам" понимаю.

В целом идея буста мне вполне ясна, а больше чем "по верхам" она интересна лишь Джиханам.

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

Ну ты, блин, философ. Я так на Григория Перельмана стану похожим - он тоже доказывал
для души гипотезу Пуанкаре и совсем потерял связь с реальным миром.

Наоборот намекаю на какую-то позитивную активность в реальном мире, но если хочется как Перельман, то конечно дело хозяйское.

https://youtu.be/GyRAK5Pqv2k

[kzv]

А я хочу разобраться с бустом. Но для начала с классическим майнингом.

Как происходит поиск хэша.

Плюсы тут означают не арифметическое сложение, а добавление информационного блока в конец. То есть 10+20=1020

1. extraNonce = 0
2. коинбейс_транзакция = константа1 + extraNonce + константа2
3. дерево_меркла = хитрый_хэш(коинбейс_транзакция+остальные_транзакции)
4. заголовок_блока = версия + хэш_предыдущего_блока + дерево_меркла + юникс_время + сложность
5. nonce = 0
6. заголовок_блока = заголовок_блока + nonce.

После этих манипуляций получается буфер с размером 80 байт. Чтобы сделать sha256, нужно иметь 128 байт. Поэтому недостающее место заполняем нулями на следующем шаге.

7. заголовок_блока = заголовок_блока + 48_нулей.

8. хэш = sha256(sha256(заголовок_блока))

Если хэш не удовлетворяет сложности, то нужно продолжать перебор. Перебираем сначала nonce (добавляем единицу и идем в п.6), а когда nonce кончатся, то добавляем 1 к extraNonce и идем в п.2

Так работает классический асик-перебор. Все правильно?

[amaclin1]

Так работает классический асик-перебор. Все правильно?

Еще раз повторяю. SHA256 - блочный алгоритм. Грубо говоря,
а) считаем сперва первые 64 байта от 80
б) потом вторые 64 байта. (16 плюс паддинг)
в) потом считаем sha256 от того что получилось (потому как у нас sha256d)
г) сравниваем, если не подошло, увеличиваем nonce на 1
д) идем не в (а), а сразу в (б)

Это то что очевидно. Есть менее очевидные оптимизации

[kzv]

Вот как я понял оптимизацию асик буст.

sha256 можно описать примерно так:
1. Разбить буфер на 64 байтныйе куски
2. С каждым куском сделать какую-то хрень
3. Хрени от кусков объединить и сделать с результатом другую хрень.

Как видим, если внутри буфера будет 64 - байтовый кусок который не меняется при переборе, то для этого куска можно хрень из п.2 сделать один раз, а потом уже не тратить на ее вычисление время.

Для буфера в 128 байт, хэширование можно записать так:

хэш = sha256_final( sha256_step(первые64байта) + sha256_step(последние64байта))

Асик буст так и делает.

Алгоритм следующий
1. Пул раздает асикам разные nonce
2. Для асика nonce = константа, юникс_время = константа, сложность = константа. Тогда если асик сам с собой договорится, что последние 4 байта дерева меркла это тоже константа (например нули), то тогда для асика последние 64 байта заголовка блока это тоже будет константа. Вуаля, для этой константы можно сэкономить время на вычисления хэшей!

Итак имеем для асика sha256_step(последние64байта) = константа

3. extraNonce = 0
4. коинбейс_транзакция = константа1 + extraNonce + константа2
5. дерево_меркла = хитрый_хэш(коинбейс_транзакция+остальные_транзакции)
6. Если последние 4 байта у дерева меркла не нули, то увеличиваем extraNonce и идем в п.3
7. заголовок_блока = версия + хэш_предыдущего_блока + первые28байт_дерева_меркла + последние64байта.
8. хэш = sha256( sha256_final( sha256_step(первые64байта) + константа ) )

[amaclin1]

Тогда если асик сам с собой договорится, что последние 4 байта дерева меркла это тоже константа (например нули)

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

[kzv]

Тогда если асик сам с собой договорится, что последние 4 байта дерева меркла это тоже константа (например нули)

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

Да.
Асики отказались перебирать nonce. Теперь они перебирают только extraNonce. Причем хэши для блока ищут только если хэш меркла получается красивый.
То есть дальше уже оптимизировать надо хэширование меркла, а не заголовка.

[fxpc]

Либо я чего-то не понимаю, либо ты не понял принцип. ExtraNonce и дерево Меркла перебирать дорого, а в каждой итерации с бустом вертят только то что можно без предварительного хеширования легко менять пока диапазон не кончится. И лишь когда он кончится вертят extraNonce и дерево Меркла, а затем снова перебирают "мелочь" в диапазоне.

[amaclin1]

ExtraNonce и дерево Меркла перебирать дорого

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

Плюс к этому - для каждой вычисленной второй части можно прокручивать в цикле версию блока. То есть опять же экономия.

[investgroup]

А что мешает сделать тупо повтор блока?

После того, как хоть 1 хэш с заданной сложностью найден(сложность вроде раз в 2 нед пересчитывается?) - уже известно какой блок(то есть данные на входе, которые по сути сворачиваются SHA до объема внутренней памяти!) дает хешь с нужной сложностью - остается только его повторить...

Одинарная или двойная SHA значения не имеет - это просто f(x)

То есть если y = f(x1) = f(x2) в случае если x1 = x2.   (точнее они не равны, но эквивалентны для SHA)


Остается только потусовать транзакции чтобы найти такой-же экв. для SHA блок...

[amaclin1]

А что мешает сделать тупо повтор блока?

Иди, мальчик, учи уроки. Не мешай дяденькам.

[fxpc]

ExtraNonce и дерево Меркла перебирать дорого

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

Плюс к этому - для каждой вычисленной второй части можно прокручивать в цикле версию блока. То есть опять же экономия.

Точно, зря я в однопотоке рассматривал, в многопотоке намного эффективнее. Но насколько я понял, в каждой итерации мы перебираем именно последние 16 байт, а отдельные 64 байта для каждого потока вычисляем единожды за ~4 миллиарда итераций.

Что значит прокручивать версию блока в цикле? Придётся же заново пересчитывать первую часть для каждого потока.

[A-Bolt]

Что значит прокручивать версию блока в цикле? Придётся же заново пересчитывать первую часть для каждого потока.

Имеется в виду, что дешевле перебирать версию блока вместо ExtraNonce, потому как в случае перебора ExtraNonce нужно каждый раз вычислять ещё и корень дерева Меркла, а в случае перебора версии, корень дерева Меркла вычислять не требуется.

Перебор версии называют оvert AsicBoost, перетасовку транзакций с целью сохранения последних 4-х байт корня дерева Меркла называют соvert AsicBoost.

[fxpc]

Что значит прокручивать версию блока в цикле? Придётся же заново пересчитывать первую часть для каждого потока.

Имеется в виду, что дешевле перебирать версию блока вместо ExtraNonce, потому как в случае перебора ExtraNonce нужно каждый раз вычислять ещё и корень дерева Меркла, а в случае перебора версии, корень дерева Меркла вычислять не требуется.

Перебор версии называют оvert AsicBoost, перетасовку транзакций с целью сохранения последних 4-х байт корня дерева Меркла называют соvert AsicBoost.

Про версию я сразу не догнал. Какой примерно диапазон получим, если покрутить в ней неиспользуемые биты?

[n00by]

Раз уж мы тут обсуждаем алгоритмы биткоина, то я вот что вам принес.

Вот эти приватные ключи дают один и тот же публичный:

ffffffffffffffffffffffffffffffff5d576e7357a4503bbfd25e8cd0364141
и
00000000000000000000000000000000a2a8918ca85bb0000000000000000000

Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).

Но могу привести кое-какие количественные оценки данного действа:
В подгруппе эллиптической кривой порядка биткоина может быть сгенерировано 2^131 степени таких ключей.
Сразу оговорюсь, что клиент их не генерирует, а вот сторонний софт вполне себе.

Ну и собственно их генерирует сеть (половина нулей слева дает хороший шанс попробовать найти привкей)

[n00by]

Да и еще немного накину матана вам в мозг.

Вот здесь https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=2ahUKEwiyjIvc-tngAhVpxIsKHf2EC9EQFjABegQICBAB&url=https%3A%2F%2Fistina.msu.ru%2Fdownload%2F18836198%2F1gCJiV%3A9tP1ODSVO_-fEn5MoWaXrXJJl8E%2F&usg=AOvVaw17vEKPcPZScYZ4jWRHDgJM диссертация к.м.н по криптографии, в которой есть сравнение сложности алгоритмов "зашифровать" для эллиптических кривых.

Так вот, по первым оценкам алгоритм "захешировать" гораздо сложнее.

[amaclin1]

Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).

Навскидку, потому что это не два ключа, а две разные записи одного и того же ключа (правильная запись вторая)
Что будет если взять остаток от деления первого числа на 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 ?
(можно просто вычесть столбиком - даже без калькулятора)
Лень считать, уверен на 100% что получится 0x00000000000000000000000000000000a2a8918ca85bb0000000000000000000

[n00by]

Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).

Навскидку, потому что это не два ключа, а две разные записи одного и того же ключа (правильная запись вторая)

Оба ключа записаны в hex. Ключи разные. Числа в инт'е
115792089237316195423570985008687907853053774472357734211582463631972694901057
и
216210193282829828977300490454533406720

(подсказка: циклическая группа)

[n00by]

остаток от деления первого числа на 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141?

берется только при подписи, но не при генерации привкея

при генерации мы в группе p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

[amaclin1]

берется только при подписи, но не при генерации привкея

Генерация привкея по определению число из диапазона от 1 до
0хFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Твоё 256-битное число не удовлетворяет этому условию. То, что некоторые программы
могут гипотетически генерировать такие приватные ключи ничего ровным счетом не
добавляет и ничего не меняет, так как при вычислении и публичного ключа, и подписи
сначала все берется по модулю

берется только при подписи, но не при генерации привкея
при генерации мы в группе p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

Да генерировать мы можем хоть 100500-битное число и считать его приватным ключом!
Все равно никто не узнает что у нас на бумажке в сейфе записано!
Публичный ключ и подпись строятся при взятии приватного ключа по модулю
0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

https://en.bitcoin.it/wiki/Private_key

То есть настрогать таких пар (и троек, и пятерняшек) я могу не глядя миллион.
Берем приватный ключ и добавляем к нему число
0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141
Вуаля!