Асикостойкий алгоритм PoW

Vtools (OP)

Full Member

Offline

Activity: 411
Merit: 135

Асикостойкий алгоритм PoW

December 30, 2017, 11:29:23 AM
Last edit: September 12, 2018, 08:12:00 PM by Vtools

Merited by chimk (5), klarki (2), noname71rus (2)

#1

UPD 12.09.2018
Тема уже неактуальна в связи с созданием более сильного алгоритма с защитой от GPU-майнинга "TeraHash"
https://bitcointalk.org/index.php?topic=5023773.0

Старое:
Друзья, продолжаю более детальную проработку темы идеального блокчейна: https://bitcointalk.org/index.php?topic=2574634.0;all
А конкретно, пункт: "12. Асикостойкий алгоритм PoW"

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

Давайте подумаем над природой проблемы, что такое CPU (процессор), GPU (графический процессор) и ASIC (микросхема для вычисления хэшей):
CPU - универсальный процессор, способный выполнять любую Тьюринг полную программу
GPU - векторный процессор с массовым параллелизмом для обработки графики (и не только)
ASIC - микросхема которая умеет вычислять только хэши (на несколько порядков быстрее CPU/GPU)

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

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

Отдельным вопросом стоит GPU - можно ли на нем написать интерпретатор?

UPD:

Давайте подумаем как реализовать интерпретатор, можно например так:
1. Берем хеш предыдущего блока, его длина 32 байта
2. Считаем его программой из 32 строк
3. Каждый байт - это отдельная команда
4. Выполняем программу, ограниченное количество тактов (например 1000)

Состав АЛУ (регистры 2 байтовые):
Регистры:
00-Аккумулятор
01-03 - общего назначения

Память: 32 байта (собственно это входящий хеш, который нужно перемешать). Вся память разбита на 16 ячеек по 2 байта.
Все значения - это целые положительные числа длиной 16 бит.

Примеры команд (цифры в 16-м коде):
RM - загрузить в регистр R двухбайтовое число из ячейки M (memory)
4R - сложить значение из аккумулятора со значением из регистра R (registr) и поместить результат в аккумулятор
5R - аналогично вычитание
6R - аналогично умножение
7R - аналогично деление
8R - аналогично побитовое OR
9R - аналогично побитовое AND
AR - аналогично побитовое XOR
BR - аналогично SIN (!)
CL,DL - переход на строку L (label) если значение в аккумуляторе меньше 2^15 (C-переход на строки: 0-15, D-переход 16-31)
EL,FL - переход на строку L (label) если значение в аккумуляторе больше 2^15 (E-переход на строки: 0-15, F-переход 16-31)
Все остальные значения (4R-AR где значения R>3) приводят к перемешиванию памяти кратно значению в аккумуляторе.
где:
R-номер регистра 0-3
M-номер ячейки памяти (0-15)
L-номер строки программы (0-15)

Итого:
¼ всех случайных команд приводит к условному переходу
примерно ⅓ команд - к случайному наполнению аккумулятора
примерно ⅓ команд - к перемешиванию хеша

Можно убрать все арифметические операции (команды 4R-AR), а ввести только сложные тригонометрические функции, как например команда BR, чтобы затруднить работу на GPU

UPD2:
Функция перемешивания на JS:

Code:

function meshhash(hash)
{
    var regs=[hash[3],hash[2],hash[1],hash[0]];
    var mem=[];
    for(var i=0;i<16;i++)
    {
        mem[i]=hash[i*2]+(hash[i*2+1]<<8);
    }

    var WasGoto=0;
    var L=0;
    for(var i=0;i<64;i++)
    {
        var c=hash[L&31];
        L++;
        var a=(c>>4)&0xF;
        var b=c&0xF;
        var r=c&0x3;


        switch (a)
        {
            case 0:
                regs[0]=regs[0] + regs[r];
                break;
            case 1:
                regs[0]=regs[0] * regs[r];
                break;
            case 2:
                regs[0]=regs[0] | regs[r];
                break;
            case 3:
                regs[0]=regs[0] & regs[r];
                break;
            case 4:
            case 5:
            case 6:
            case 7:
                regs[0]=regs[0] + regs[1] + regs[2] + regs[3];
                break;
            case 8:
                if((regs[0]&0xFFFF)<32768 && !WasGoto)
                {
                    L=32+L-b;
                    WasGoto=1;
                }
                break;
            case 9:
                if((regs[0]&0xFFFF)>32768 && !WasGoto)
                {
                    L+=b;
                    WasGoto=1;
                }
                break;

            default:
                regs[a%4]=mem[b];

        }


        var index1=regs[0]&0xF;
        var index2=(regs[0]>>8)&0xF;
        if(index1!==index2)
        {
            var temp=mem[index1];
            mem[index1]=mem[index2];
            mem[index2]=temp;
        }
    }

    var ret=[];
    for(var i=0;i<16;i++)
    {
        ret[i*2]=mem[i]&0xFF;
        ret[i*2+1]=mem[i]>>8;
    }

    return ret;
}

UPD3

Алгоритм реализован в блокчейне TERA
https://bitcointalk.org/index.php?topic=4573801
Consensus: PoW
Algorithm: sha3 + meshhash (ASIC resistent hashing)
Max emission: 1 bln (TER)
Reward for block: 1-20 coins, depends on network power (one billionth of the remainder of undistributed amount of coins and multiplied by the hundredth part of the square of the logarithm of the network power)
Block size 120 KB
Premine: 5%
Development fund: 1% of the mining amount
Block generation time: 1 second
Block confirmation time: 8 seconds
Speed: from 1000 transactions per second
Commission: free of charge

• Restart of the TERA project in 2022 •

• Web ܀ ANN ܀ Discord ܀ Telegram ܀ Twitter •

rorrim

Jr. Member

Offline

Activity: 53
Merit: 1