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

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


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-карты продолжали оставаться неконкурентными.