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

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

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

-Костыльно
-Предыдущий хеш не связан с текущим и поэтому не связан с 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 раз).