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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

Алгоритм следующий
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байта) + константа ) )

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

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

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

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

Плюсы тут означают не арифметическое сложение, а добавление информационного блока в конец. То есть 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

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

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


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

https://youtu.be/GyRAK5Pqv2k

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

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

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

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

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

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


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

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

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

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

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