|
amaclin1
|
 |
February 17, 2019, 01:23:22 PM |
|
разминка для мозга и не более. Там два вектора атаки было overt и covert - кажется так назывались. Я щас уже не вспомню что к чему. Из того что помню - можно при неизменных полях, в том числе и nonce менять неиспользуемые биты в версии блока (второй чанк остается без изменений и его пересчитывать не нужно) Можно в некоторых пределах использовать поле таймстампа блока (но это уже совсем мелочевка) Можно подобрать два меркль-хэша, которые заканчиваются на одинаковые 4 байта (то, что зовется "Tail" на рисунке 2 https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf ) и опять же крутить не nonce, а version. Короче, меня не слушайте, разбирайтесь сами. Я в этом только "по верхам" понимаю. Такая суета в любом возрасте когда сам себе отец. Имхо, решение только одно - как-то отвлекаться
и делать что-то для души, возможно глобальное, чтобы до могильной плиты не идти каждый день
назад в завтра такое же как вчера. Ну ты, блин, философ. Я так на Григория Перельмана стану похожим - он тоже доказывал для души гипотезу Пуанкаре и совсем потерял связь с реальным миром. |
|
|
|
|
fxpc
Sr. Member
 Offline
Activity: 1316
Merit: 420
KTO EC/\U HUKTO?
|
|
February 17, 2019, 02:19:29 PM
Last edit: February 17, 2019, 03:41:29 PM by fxpc |
|
разминка для мозга и не более. Там два вектора атаки было overt и covert - кажется так назывались. Я щас уже не вспомню что к чему. Из того что помню - можно при неизменных полях, в том числе и nonce менять неиспользуемые биты в версии блока (второй чанк остается без изменений и его пересчитывать не нужно) Можно в некоторых пределах использовать поле таймстампа блока (но это уже совсем мелочевка) Можно подобрать два меркль-хэша, которые заканчиваются на одинаковые 4 байта (то, что зовется "Tail" на рисунке 2 https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf ) и опять же крутить не nonce, а version. Короче, меня не слушайте, разбирайтесь сами. Я в этом только "по верхам" понимаю. В целом идея буста мне вполне ясна, а больше чем "по верхам" она интересна лишь Джиханам. Такая суета в любом возрасте когда сам себе отец. Имхо, решение только одно - как-то отвлекаться
и делать что-то для души, возможно глобальное, чтобы до могильной плиты не идти каждый день
назад в завтра такое же как вчера. Ну ты, блин, философ. Я так на Григория Перельмана стану похожим - он тоже доказывал для души гипотезу Пуанкаре и совсем потерял связь с реальным миром. Наоборот намекаю на какую-то позитивную активность в реальном мире, но если хочется как Перельман, то конечно дело хозяйское. https://youtu.be/GyRAK5Pqv2k |
|
|
|
kzv (OP)
Legendary
Offline
Activity: 1722
Merit: 1285
OpenTrade - Open Source Cryptocurrency Exchange
|
|
February 17, 2019, 02:47:52 PM |
|
А я хочу разобраться с бустом. Но для начала с классическим майнингом.
Как происходит поиск хэша.
Плюсы тут означают не арифметическое сложение, а добавление информационного блока в конец. То есть 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
|
|
February 17, 2019, 03:03:28 PM |
|
Так работает классический асик-перебор. Все правильно? Еще раз повторяю. SHA256 - блочный алгоритм. Грубо говоря, а) считаем сперва первые 64 байта от 80 б) потом вторые 64 байта. (16 плюс паддинг) в) потом считаем sha256 от того что получилось (потому как у нас sha256d) г) сравниваем, если не подошло, увеличиваем nonce на 1 д) идем не в (а), а сразу в (б) Это то что очевидно. Есть менее очевидные оптимизации |
|
|
|
|
kzv (OP)
Legendary
Offline
Activity: 1722
Merit: 1285
OpenTrade - Open Source Cryptocurrency Exchange
|
|
February 17, 2019, 03:29:23 PM |
|
Вот как я понял оптимизацию асик буст. 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
|
|
February 17, 2019, 03:38:17 PM |
|
Тогда если асик сам с собой договорится, что последние 4 байта дерева меркла это тоже константа (например нули) Ну тут кагбе не особо договоришься  ))))))) Надо подобрать два такие дерева меркла, хэши которых будут совпадать в последних 4 байтах. Тогда результат вычисления второго чанка будет один и тот же - мы по сути дела для одного нонса перебираем два результата, а не один. |
|
|
|
|
kzv (OP)
Legendary
Offline
Activity: 1722
Merit: 1285
OpenTrade - Open Source Cryptocurrency Exchange
|
|
February 17, 2019, 03:44:55 PM |
|
Тогда если асик сам с собой договорится, что последние 4 байта дерева меркла это тоже константа (например нули) Ну тут кагбе не особо договоришься ))))))) Надо подобрать два такие дерева меркла, хэши которых будут совпадать в последних 4 байтах. Тогда результат вычисления второго чанка будет один и тот же - мы по сути дела для одного нонса перебираем два результата, а не один. Да. Асики отказались перебирать nonce. Теперь они перебирают только extraNonce. Причем хэши для блока ищут только если хэш меркла получается красивый. То есть дальше уже оптимизировать надо хэширование меркла, а не заголовка. |
|
|
|
fxpc
Sr. Member
Offline
Activity: 1316
Merit: 420
KTO EC/\U HUKTO?
|
|
February 17, 2019, 04:17:59 PM |
|
Либо я чего-то не понимаю, либо ты не понял принцип. ExtraNonce и дерево Меркла перебирать дорого, а в каждой итерации с бустом вертят только то что можно без предварительного хеширования легко менять пока диапазон не кончится. И лишь когда он кончится вертят extraNonce и дерево Меркла, а затем снова перебирают "мелочь" в диапазоне.
|
|
|
|
|
amaclin1
|
|
February 17, 2019, 04:26:07 PM |
|
ExtraNonce и дерево Меркла перебирать дорого Дорого. Но оно того стоит, похоже. Давай с простого начнем. Находим (используем парадокс дней рождения) два меркл-дерева, хэши которых совпадают в 4 последних байтах. Что это нам дает? То что мы можем сэкономить 4 миллиарда вычислений второго блока, если параллельно будем перебирать nonce - последние 16 байт блока будут одинаковыми в двух параллельных процессах. Плюс к этому - для каждой вычисленной второй части можно прокручивать в цикле версию блока. То есть опять же экономия. |
|
|
|
|
|
investgroup
|
|
February 17, 2019, 05:22:34 PM |
|
А что мешает сделать тупо повтор блока?
После того, как хоть 1 хэш с заданной сложностью найден(сложность вроде раз в 2 нед пересчитывается?) - уже известно какой блок(то есть данные на входе, которые по сути сворачиваются SHA до объема внутренней памяти!) дает хешь с нужной сложностью - остается только его повторить...
Одинарная или двойная SHA значения не имеет - это просто f(x)
То есть если y = f(x1) = f(x2) в случае если x1 = x2. (точнее они не равны, но эквивалентны для SHA)
Остается только потусовать транзакции чтобы найти такой-же экв. для SHA блок...
|
|
|
|
|
|
amaclin1
|
|
February 17, 2019, 05:32:35 PM |
|
А что мешает сделать тупо повтор блока? Иди, мальчик, учи уроки. Не мешай дяденькам. |
|
|
|
|
fxpc
Sr. Member
Offline
Activity: 1316
Merit: 420
KTO EC/\U HUKTO?
|
|
February 17, 2019, 07:30:41 PM
Last edit: February 18, 2019, 06:10:09 AM by fxpc |
|
ExtraNonce и дерево Меркла перебирать дорого Дорого. Но оно того стоит, похоже. Давай с простого начнем. Находим (используем парадокс дней рождения) два меркл-дерева, хэши которых совпадают в 4 последних байтах. Что это нам дает? То что мы можем сэкономить 4 миллиарда вычислений второго блока, если параллельно будем перебирать nonce - последние 16 байт блока будут одинаковыми в двух параллельных процессах. Плюс к этому - для каждой вычисленной второй части можно прокручивать в цикле версию блока. То есть опять же экономия. Точно, зря я в однопотоке рассматривал, в многопотоке намного эффективнее. Но насколько я понял, в каждой итерации мы перебираем именно последние 16 байт, а отдельные 64 байта для каждого потока вычисляем единожды за ~4 миллиарда итераций. Что значит прокручивать версию блока в цикле? Придётся же заново пересчитывать первую часть для каждого потока. |
|
|
|
|
|
fxpc
Sr. Member
Offline
Activity: 1316
Merit: 420
KTO EC/\U HUKTO?
|
|
February 18, 2019, 07:58:57 AM
Last edit: February 18, 2019, 09:05:54 AM by fxpc |
|
Про версию я сразу не догнал. Какой примерно диапазон получим, если покрутить в ней неиспользуемые биты? |
|
|
|
n00by
Member
Offline
Activity: 172
Merit: 11
|
|
February 26, 2019, 05:36:01 PM |
|
Раз уж мы тут обсуждаем алгоритмы биткоина, то я вот что вам принес.
Вот эти приватные ключи дают один и тот же публичный:
ffffffffffffffffffffffffffffffff5d576e7357a4503bbfd25e8cd0364141
и
00000000000000000000000000000000a2a8918ca85bb0000000000000000000
Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).
Но могу привести кое-какие количественные оценки данного действа:
В подгруппе эллиптической кривой порядка биткоина может быть сгенерировано 2^131 степени таких ключей.
Сразу оговорюсь, что клиент их не генерирует, а вот сторонний софт вполне себе.
Ну и собственно их генерирует сеть (половина нулей слева дает хороший шанс попробовать найти привкей)
|
|
|
|
|
n00by
Member
Offline
Activity: 172
Merit: 11
|
|
February 26, 2019, 05:52:03 PM |
|
|
|
|
|
|
|
amaclin1
|
|
February 26, 2019, 05:56:24 PM |
|
Почему так происходит оставлю вам в качестве домашнего задания (secp256k1). Навскидку, потому что это не два ключа, а две разные записи одного и того же ключа (правильная запись вторая) Что будет если взять остаток от деления первого числа на 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 ? (можно просто вычесть столбиком - даже без калькулятора) Лень считать, уверен на 100% что получится 0x00000000000000000000000000000000a2a8918ca85bb0000000000000000000 |
|
|
|
|
n00by
Member
Offline
Activity: 172
Merit: 11
|
|
February 26, 2019, 06:00:04 PM |
|
Почему так происходит оставлю вам в качестве домашнего задания (secp256k1). Навскидку, потому что это не два ключа, а две разные записи одного и того же ключа (правильная запись вторая) Оба ключа записаны в hex. Ключи разные. Числа в инт'е 115792089237316195423570985008687907853053774472357734211582463631972694901057 и 216210193282829828977300490454533406720 (подсказка: циклическая группа) |
|
|
|
|
n00by
Member
Offline
Activity: 172
Merit: 11
|
|
February 26, 2019, 06:01:24 PM |
|
остаток от деления первого числа на 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141?
берется только при подписи, но не при генерации привкея при генерации мы в группе p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f |
|
|
|
|
|
amaclin1
|
|
February 26, 2019, 06:05:58 PM |
|
берется только при подписи, но не при генерации привкея Генерация привкея по определению число из диапазона от 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 Вуаля! |
|
|
|
|
|
