Topic: Алгоритм с защитой от GPU-майнинга (TeraHash) (Read 1015 times)

Это значительная оптимизация. Наверно, раньше код был написан некорректно.



Я так понимаю, что для снижения вероятности нахождения в одном интервале можно использовать одновременно не два, а три и более хешей. Каково оптимальное значение количества используемых хешей для получения значительной форы CPU перед GPU?

Неделю назад мы зарелизились в Тере со следующей формулой:



Функция на JS:



После оптимизации с памятью хешрейт слабого ноутбука с 4Гб оперативки стал примерно 60Mh/s (до этого был 200Kh/s)

Это то о чём я выше написал - борьба со спамом. Давай удалим оффтоп.

странно что люди рассуждая о программных кодах, не способны переварить один абзац текста. я ничего не утверждал и следовательно не притягивал. потому что сам не до конца уверен, а лишь предупредил. тера это альткоин или нет?судя по этой теме https://bitcointalksearch.org/topic/m.45381046 да. хотя я может ошибаюсь.

п.п. 15

------------------------------------------------------------------------------------------

вот здесь три больших поста разбора этого правила
https://bitcointalksearch.org/topic/m.45583710

Слышал бы, если был, а его нет.

Слышал бы тебя бог Все в этом мире костыльно

-Костыльно
-Предыдущий хеш не связан с текущим и поэтому не связан с coinbase транзакцией майнера

Вариации алгоритма улучшающие защиту от изменения базы и тем самым улучшающие вероятность полного перебора:
-Ввести более двух хешей (ухудшается вероятность поиска в одном интервале для GPU-майнера)
-Использовать предыдущий хеш (его не изменить он уже в блокчейне)

Практические примеры:
Компьютер: используя память DDR4-2133 будет иметь иметь скорость канала равную 17Гб/с и поэтому сможет сравнить порядка 500 млн хешей
GPU GTX 1060 имеет память 6Гб, скорость работы памяти 192 Гб/с. Таким образом в память видеокарты может поместиться 180 млн хешей, которую она в может вызывать 32 раза.
Подставим параметры:
CPU: 500тысяч
GPU: 180 тысяч в 32 раунда
запустим программу:

Результаты:
GPU показал даже немного худший результат.

Вот код программы сравнения стратегии  CPU-майнера и GPU-майнера:



Сравниваем 10 млн итераций на CPU и 100 тыс итераций умноженных на 10 тыс интервалов на GPU, т.е. когда GPU вычислительнее мощнее в 100 раз.
Смотрим хеши, чем меньше тем лучше:

Как видим CPU нашел более сильный хеш.

Это доказывает правильность такого подхода при создании GPU-устойчивых алгоритмов. Осталось только аккуратно подобрать параметры...

Я сейчас напишу простенькую программу для проверки гипотезы (раз ты не согласен с доказательством, значит это все еще гипотеза)...

Ты не врубаешься в рандом. Вероятность найти 2 хеша за X попыток одинаковая независимо от интервала, пусть он хоть всего из 2 HNonce состоит. Кто быстрее перебирает, у того и выше вероятность, а перебирает быстрее GPU.

Да, верно, когда писал мысль была сырая еще. В гуглдоке записал конечную версию, а тут не подправил. Должно быть так:


Это верно, для поиска одного хеша. Если мы хотим чтобы два хеша нашлись в одном интервале - то это же умножение вероятностей.
Допустим у нас 2 интервала.  Переберем все комбинации (1-первый хеш, 2- второй хеш, квадратные скобки это интервалы):
1) [1,2] [0,0]
2) [1,0] [0,2]
3) [0,2] [1,0]
4) [0,0] [1,2]

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


Пары nonce подойдут из разных интервалов, но важно чтобы они были в одном.
Поэтому формула вероятности при K>>1 будет примерно такая:

P=K*(1/2)^k

(сложение вероятностей полученной от умножения вероятностей)

Не понял откуда ты взял HNonce1 и HNonce2, видимо формула должна быть такой:
Hash = Mesh(Hблока,HNonce1)
Hash2 = Mesh(H2блока,HNonce2)
Power=min(Power(Hash),Power(Hash2))

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

Атака
GPU-майнер может найти HNonce для функции Hash2, а потом начать менять текущий блок, так чтобы его хеш подходил к этому Nonce. Например, сделет 1 млн переборов найдет nonce с силой = 20 бит, а потом изменяя хеш текущего блока сделает еще в среднем 1 млн переборов и найдет подходящий хеш.


Анализ
Что имеем:
Майнер все так же может менять базу.

Пути преодоления:
Придумать другой вариант сложности на смену базы. Например майнер должен доказать, что база не менялась. Например, он должен найти HashNonce который подходит как к текущему хешу блока так и к двойному хешу блока.

В общем виде формула будет такова:
Hash = Mesh(Hблока,HNonce)
Hash2 = Mesh(H2блока,HNonce)
Power=min(Power(Hash),Power(Hash2))

Майнер делает перебор 1 млн вариантов находит HNonce1 и HNonce2, с реднем он получит по 20 бит силы pow. Майнер дальше продолжает перебирать варианты, если он меняет базовый хеш, то ему придется заново искать HNonce1 и HNonce2. И вот почему:
Поиск это процесс случайный, события нахождения хешей независимы. В среднем за миллион переборов он найдет 20 бит. Повторяя 1000 раз он может улучшить результат для каждого хеша на 10 бит, но только если не менялась база, если меняется база, то эти события (приход хеша с 30 битами силы) высоковероятно произойдут в разных итерациях.

Если майнер разбивает поиск хеша на k+1 интервалов в которых меняет базовый хеш, то вероятность нахождения двух хешей с максимальным pow в одном интервале составляет:
P=(1/2)^k


Таким образом зависимости от того во сколько у GPU-майнера меньше памяти во столько в экспоненциальной зависимости уменьшается его мощность вычислений по сравнению с CPU-майнером.

Атака

Анализ
Что имеем:
В качестве базы используется хеш блока, а итерация выполняется по nonce в классическом случае и по HashNonce в предлагаемом алгоритме. Т.е. по формулу Hash=h(Hблока,Nonce)
В алгоритме узкое место - это возможность майнера изменить базу, т.е. хеш-блока и начать заново итерации, т.е. в итоге  обойтись меньшим количеством памяти.

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

В общем виде формула будет такова:
Hash = Mesh(Hблока,HNonce)
Hash2 = Mesh(Hблока-1,HNonce)
Power=min(Power(Hash),Power(Hash2))

где:
Power() - это число первых нулевых бит
Mesh() - простая функция перемешивания, в данном случае подойдет простой XOR

Кстати с применением нового расчета Power как min значение числа нулевых битов двух хешей, получается что:
Майнеры будут оптимизировать поиск, так чтобы Power двух значений совпадал
Число переборов вырастает квадратически, например если раньше 1 млн переборов давал 20 бит, то теперь будет давать 10 (все также нужно найти 20 бит, но по 10 в каждом хеше)

P.S.
fxpc - награда 100К Тера за найденный вариант атаки

Да, ты прав. Можно менять содержимое блока и обойтись мегабайтами. Это изъян алгоритма. Надо думать.
Извини, невнимательно прочитал....

В чём тогда заключается защита от GPU-майнинга и о каком ускорении речь, если GPU на порядок быстрее? У тебя раз в 10 000 блоков генерируется HashTemp массив и ты отталкиваешься от того что для майнинга он нужен целиком, а теория вероятности говорит о том, что массива из 1 хеша достаточно, но оптимальнее по производительности массив равный объёму памяти GPU. Причём здесь терабайты памяти и скорость расчёта SHA-3? Уйма памяти и хешрейт не нужны, нужна высокая пропускная способность памяти и по этому параметру GPU уделывает CPU, не говоря уже про несколько GPU.

Ок, за замечания по названию спс, подправлю.



Вообще скорость GPU нам не важна пусть будет быстрые расчеты и пусть имеет быструю память. Например для GTX 1060 расчет sha3 keccak = 480 Mh/s

Идея русским языком - мы ускоряем ЦПУ!

см:

Введение

Цель данного алгоритма уравнять между собой людей майнящих на CPU и на GPU. Для достижения этого мы предлагаем использовать память, но в отличие от других похожих алгоритмов (например Ethash) в нашем алгоритме память не тормозит работу  GPU, а ускоряет работу CPU. Это можно осуществить тем, что при подборе хеша использовать не целое число nonce, а определенное значение, которое трудоемкое для вычисления - например вычисленное по алгоритму sha3 и допустить применение этого значения для перебора в широком диапазоне вычисления хеша блоков. Таким образом будет выгоднее сохранять эти значения в памяти для подбора, чем вычислять заново. Такая выгода должна сохраняться даже если скорость вычислительных ресурсов увеличится в 1000 раз.

Насколько мне известно такой карты не существует. Есть GTX 1060, у которой в зависимости от модели пропускная способность памяти 160-216 GB/s.


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

Объявлена награда за вклад в развитие этого алгоритма в размере 500К Тера
https://bitcointalksearch.org/topic/m.45381046

При общении с одним товарищем выяснилось что требуется пояснение...


1. Тут как бы два нонса. Первый - это просто число Nonce,  оно нужно для создания второго нонса HashTemp (хеша) и именно второй нонс используются в финальном хеше SimpleMesh (который очень быстро должен считаться, почти как XOR)
2. В этом алгоритме мы не GPU тормозим за счет использования памяти, а мы ускоряем CPU (примерно в 1000 раз).

Привет, спасибо за ответ.


1. Перебор Nonce допускается гораздо больше, например 2⁶⁴ что овердофига и поэтому переход на предыдущие блоки уже не требуется (ну т.е. суть не в этом).
2. Сами вычисления sha3 медленные, поэтому выгоднее их сохранять в памяти. Для того чтобы подставлять в формулу на шаге 2.
3. Алгоритмом допускается использовать старые значения но не более например 10000 блоков.

Давайте прикинем:
GPU: GTS 1060 за 1 секунду создаст и сравнит порядка 0.5 млрд хешей.
Компьютер: используя память DDR4-2133 будет иметь иметь скорость канала равную 17Гб/с и поэтому сможет сравнить тоже порядка 0.5 млрд хешей
Что очень хорошо.



Кстати шаг 2 основного алгоритма надо изменить, я нашел слабое место:

Атака:
Если для заданного блока нет подходящего (т.е. с высоким уровнем pow) значения во временной таблице, можно изменять содержимое блока, так чтобы хеш  изменился. Времени много - целая секунда. В итоге будут левые транзакции в блоке, блоки станут уникальными и будут долго распространяться в сети.

Защита:
Вместо операции XOR применять лучше перемешиваемую функцию, но обязательно быструю (не обязательно криптографическую) - главное защита от упорядоченного хранения расчетов и невозможности быстрого поиска - ибо он для нас вреден.

Нелегко мне вас понять, но я попробую.

В вашем алгоритме осуществляется перебор по двум параметрам: Nonce и PrevHashN.
То есть, берётся хеш последнего блока и производится перебор Nonce.
Если перебор Nonce не дал нужный Hash, значит
берётся хеш следующего блока (высота_блока = высота_блока - 1) и снова перебирается Nonce.
и т. д.

Получается, что у вас на одно вычисление PrevHashN приходится 2³² итераций Nonce. То есть, у вас преобладают вычислительные операции, не требующие больших объёмов памяти.

А PrevHashN можно вычислять на лету, это тяжёлая операция, требующая обращения к БД блоков, но она выполняется очень редко. CPU вычисляет PrevHashN и CurrentDataHash, даёт их GPU, а GPU итерирует Nonce (от 0 до 2³²) и проверяет хеш на соответствие сложности, что не требует больших объёмов памяти.   

Небольшие расчеты:

Современный, но доступный всем компьютер рассчитывает хеш sha3 со скоростью порядка 1Mh/s, размер хеша 32 байта, т.е. 32Мбайта данных в секунду. Если использовать MaxN = 1000, то размер таблицы составит максимум 32Гбайта.

Сейчас максимальный размер памяти видеокарт в свободной продаже 16Гбайт и 24Гб не в свободной продаже, но теоретически доступные.
Скорость заполнения примерно в 1000 раз быстрее, т.е. 32Гбайта в секунду. Таким образом скорость поиска хеша будет практически равная. Но видеокарты выгодно использовать для ускорения заполнения памяти и заполнять не 32Гб, а например 1Терабайт.. Для частичной защиты от этого можно для построения предрассчитанных HashTemp  применить более быстрый вариант sha3 - с меньшим числом раундов перемешивания (например уменьшить в 2 раза). В итоге для данного примера скорость будет отличаться не более чем в 16 раз.

Алгоритм с защитой от GPU-майнинга TeraHash

Назовем его именем TeraHash

Версия 0.1.1

На вход подается 32-байтный хеш данных текущего блока CurrentDataHash, нужно найти такой Nonce (целое число), чтобы в результате получился подходящий для нас хеш (с максимальным значением начальных нулей).
Ограничение:
1. Поиск должен быть оптимизирован на использование памяти - для защиты от GPU-майнинга
2. Проверка должна осуществлять при минимальном количестве памяти и выполняться быстро - примерно со скоростью вычисления sha3


Порядок расчета:
1. Вычисляется HashTemp = sha3(PrevHashXXX , Nonce)
2. Получаем Hash = HashTemp XOR CurrentDataHash

PrevHashXXX - 32-байтный хеш предыдущего блока, отстающий на N блоков от текущего (максимальная глубина ограничена определенным числом, например 10000 блоков)
Nonce - число для перебора значений от 0 до макс целого числа

Таким образом в блокчейн записывается:
CurrentDataHash,Nonce, N  - по которым быстро восстанавливается хеш блока

Т.е. здесь основная идея один раз рассчитать различные значения HashTemp с разными Nonce, а потом 10000 блоков просто подставлять значения через операцию XOR для лучшего подходящего хеша.

Особенность: из-за операции XOR можно так упорядочено расположить предрассчитанные значения HashTemp в памяти, что вообще не будет перебора Nonce - поиск будет вестись за логарифм времени. Соответственно при поиске CPU нагружаться не будет. Большое значение в алгоритме будет иметь размер памяти. Компьютеры с Терабайтом памяти будут 100 раз быстрее чем 10Гбайт. Но если ограничить максимальный размер N, то можно уменьшить эту разницу. Но это делать нужно осторожно, чтобы GPU-карты продолжали оставаться неконкурентными.