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

[Vtools]

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

[Vtools]

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

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

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

[A-Bolt]

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

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

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

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

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

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

[Vtools]

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

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

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

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

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

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

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


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

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



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

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

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

[Vtools]

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


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

[Vtools]

Объявлена награда за вклад в развитие этого алгоритма в размере 500К Тера
https://bitcointalk.org/index.php?topic=4573801.msg45381046#msg45381046

[fxpc]

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

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

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

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

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

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

[Vtools]

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

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

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

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

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

см:

Введение

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

[fxpc]

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

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

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

[Vtools]

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

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

[Vtools]

Атака

Какую бы функцию ты не применил, атакующему ничего не помешает 1 раз заполнить память своего 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К Тера за найденный вариант атаки

[Vtools]

Раз так, то нужно ввести в алгоритм сложности на смену базы. А что если используемый хеш nonce должен обладать определенными дополнительными условиями, например при применении его в формулу предыдущего хеша блока он тоже должен давать красивый хеш. Предыдущий хеш блока майнер поменять не может он уже зафиксирован другими участниками сети. Т.е. получается, что нужно действительно осуществить большой перебор HashNonce, чтобы найти подходящее значение.
В общем виде формула будет такова:
Hash = Mesh(Hблока,HNonce)
Hash2 = Mesh(Hблока-1,HNonce)
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-майнером.

[fxpc]

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

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

[Vtools]

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

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

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

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

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

Это верно, для поиска одного хеша. Если мы хотим чтобы два хеша нашлись в одном интервале - то это же умножение вероятностей.
Допустим у нас 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

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

[fxpc]

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

[Vtools]

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

[Vtools]

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

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

Code:

var MAX_NUM=0x1000000000;

function hash(Rand)
{
    return (1664525*Rand+1013904223) % MAX_NUM;
}


function MiningCPU(Hблока,CountIteration)
{
    var Hблока2=hash(Hблока);

    var HashLider1=MAX_NUM,Nonce1;
    var HashLider2=MAX_NUM,Nonce2;
    for(var nonce=0;nonce<CountIteration;nonce++)
    {
        var Test1=hash(Hблока+nonce);
        if(Test1<HashLider1)
        {
            HashLider1=Test1;
            Nonce1=nonce;
        }

        var Test2=hash(Hблока2+nonce);
        if(Test2<HashLider2)
        {
            HashLider2=Test2;
            Nonce2=nonce;
        }
    }

    
    if(HashLider1>HashLider2)
        console.log("CPU Hash1: "+HashLider1+"  nonce1:"+Nonce1)
    else
        console.log("CPU Hash2: "+HashLider2+"  nonce2:"+Nonce2)
}

function MiningGPU(Hблока,CountIteration,CountInterval)
{
    var HashLider1=MAX_NUM,Nonce1;
    var HashLider2=MAX_NUM,Nonce2;
    for(var k=0;k<CountInterval;k++)
    {
        Hблока=hash(Hблока+k);
        var Hблока2=hash(Hблока);

        var LocHashLider1=MAX_NUM,LocNonce1;
        var LocHashLider2=MAX_NUM,LocNonce2;


        for(var nonce=0;nonce<CountIteration;nonce++)
        {
            var Test1=hash(Hблока+nonce);
            if(Test1<LocHashLider1)
            {
                LocHashLider1=Test1;
                LocNonce1=nonce;
            }

            var Test2=hash(Hблока2+nonce);
            if(Test2<LocHashLider2)
            {
                LocHashLider2=Test2;
                LocNonce2=nonce;
            }
        }

        //save lider
        var Lider=Math.max(HashLider1,HashLider2);
        var LocLider=Math.max(LocHashLider1,LocHashLider2);

        if(LocLider<Lider)
        {
            HashLider1=LocHashLider1;
            Nonce1=LocNonce1;
            HashLider2=LocHashLider2;
            Nonce2=LocNonce2;
        }

    }
    
    if(HashLider1>HashLider2)
        console.log("GPU Hash1: "+HashLider1+"  nonce1:"+Nonce1)
    else
        console.log("GPU Hash2: "+HashLider2+"  nonce2:"+Nonce2)
}

var BlockHash=1234567;

MiningCPU(BlockHash,10000000);

console.log("------------------------");

MiningGPU(BlockHash,100000,10000);

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

Code:

CPU Hash2: 2384  nonce2:6491628
------------------------
GPU Hash1: 12016  nonce1:64021

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

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

[Vtools]

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

Code:

MiningCPU(BlockHash,500000);
MiningGPU(BlockHash,180000,32);

Результаты:

Code:

CPU Hash1: 28968  nonce1:3366
GPU Hash2: 44720  nonce2:59637

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

[Vtools]

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

[fxpc]

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