Анти ASIC/GPU/FPGA/CLOUD/MAINFRAME POW-алгоритмТеперь майнинг может быть доступен каждому…Привет всем.
Я несколько лет думал над тем - как сделать алгоритм POW, который будет устойчив не только против ASIC-устройств, но и против GPU-майнеров.
И я его разработал!
Вчера ночью я успешно провел генерацию и подтверждение первой локальной цепочки подписей для подтверждения блока (смотрите скриншот ниже). Поэтому с сегодняшнего дня я буду публиковать описание алгоритма и части кода на С++.
Основное решение.Единственная причина, которая не позволяет криптосообществу решить проблему специализированных устройств – это приспособленность современных POW-алгоритмов к параллельным расчетам.
Отсюда выходит идеальное решение – алгоритм расчетов должен быть последовательным и устойчивым к любой возможности выполнить расчеты параллельно.
Первый принцип - циклические вычисления.Мы должны отказаться от хэширования, которое сейчас является основным алгоритмом расчета для подписи блока. Предлагаю заменить его Кольцевой Битовой Функцией (КБФ), потому что она идеально выполняет все требования к POW-алгоритму.
Требования к POW-алгоритму:
1) односторонняя функция;
2) тяжело вычислить;
3) легко проверить;
4) только последовательные вычисления.
Приведу пример КБФ для 32-битного числа.
Вы видите, что через 8 раундов таких вычислений мы снова получаем начальное число. Так как вычисления идут по кольцу, мы можем их использовать для POW-алгоритма. Например, с 1-го по 7-ой раунд - это поиск результата вычислений. 7-ое число – это найденная подпись. А 8-ой раунд - это проверка верности вычислений!
При этом данная функция является односторонней, то есть обратное преобразование возможно только путем полного перебора.
Таким образом для данного вида вычислений, которые я назвал "Кольцевой Битовой Функцией", выполняются все 4 требования к POW-алгоритму.
Если мы будем говорить об обычном хэшировании, то в нем возможны параллельные вычисления, что позволяет использовать специальные устройства для ускорения вычислений.
(Thanks to IadixDev for the diagram.)Размер колец в КБФ может быть разным. Это зависит от комбинации ротаций и сдвигов, которые мы применяем. Некоторые комбинации не создают кольцевых функций, поэтому необходимо предварительно проверять – какая комбинация работает.
Приведу несколько рабочих примеров для 32-битных чисел:
239 rounds
NewNum = (num >> 1) ^ (num <<< 1)
55117 rounds
NewNum = (num >> 1) ^ (num <<< 1) ^ (num >>> 3)
131069 rounds
NewNum = (num >> 1) ^ (num <<< 1) ^ (num >>> 13)
Таких комбинаций очень много, что позволяет нам варьировать уровень сложности вычислений.
Второй принцип – олимпийские кольца.Одна кольцевая фунция может нам дать только одну подпись. Но для того, чтобы подобрать "красивую" подпись, нам нужно высчитать много кольцевых функций. Четвертый принцип POW-алгоритма требует, чтобы все кольцевые функции были связаны. Так как вычисления в кольцевой функции односторонние, то при поиске "красивой" подписи мы двигаемся по кольцу в одну сторону, а при проверке – в другую. Если мы начнем высчитывать новое кольцо от старой подписи по тому же алгоритму, то будем двигаться по тому же кольцу. Чтобы создать новое кольцо от старой подписи нужно изменить алгоритм на другой. В этом случае цепочка вычислений будет похожа на олимпийские кольца (только более длинная – она будет состоять из сотен или тысяч колец). Смена алгоритма вычислений на каждом кольце поможет нам увеличить устойчивость нашего алгоритма против ASIC-устройств.
Для доплнительного усложнения алгоритма против ASIC и FPGA устройств, мы будем использовать маски на каждом переходе от одного кольца к другому. Этот алгоритм маскировки является двухсторонним. Я назвал его Mystique.
Третий принцип – двухступенчатая подпись.Однако злоумышленник все-равно может увеличить свои шансы на получение награды за блок, так как он может делать параллельные вычисления, опираясь на разные корни Меркла, а так же разные моменты времени.
Для того, чтобы устранить такую возможность, при вычислении подписи необходимо использовать только те данные, которые невозможно высчитывать параллельно. При этом они должны постоянно меняться от блока к блоку. К таким данным относится только подпись предыдущего блока и номер блока.
Дополнительно нужно закрепить право майнера на получение награды, поэтому предлагаю добавить к подписи предыдущего блока кошелек майнера, на который будет зачисляться награда за блок. Все остальные данные могут быть изменены для одного и того же блока, поэтому они не годятся для расчета подписи.
Однако, все остальные данные так же должны быть закреплены в подписи блока.
Для решения этой проблемы я предлагаю создавать подпись блока в два этапа:
1 этап.
На основании подписи предыдущего блока, номера блока и адреса кошелька майнера выполняется хэширование (например SHA256).
Полученный хэш служит стартом для основного вычисления при поиске "красивой" подписи.
2 этап.
Найденная подпись является только pre-подписью.
Pre-подпись служит стартовым числом для хэширования, которое на вход принимает все остальные данные блока – корень Меркла, счетчик цепочки, штамп времени и т.д.
Полученный хэш мы считаем подписью блока.
Таким образом, майнер не сможет высчитать хэш блока до тех пор, пока не найдет корректную pre-подпись. Но найдя ее уже нет смысла высчитывать разные хэши от разных входных данных.
Четвертый принцип – самопрограммирование.Последний принцип позволяет максимально защитить вычисления от ASIC устройств. В его основе лежит идея, что каждое входное число одновременно является программой, по которой оно будет преобразовано. Таким образом каждый новый расчет будет выполняться по уникальной программе, что не позволит использовать ASIC-устройства для ускорения вычислений.
Для этого необходимо разбить стартовое число на группы по несколько бит, и к значению каждой группы привязать определенную последовательность преобразований. Наилучшим образом это будет показано на примере сильного одностороннего алгоритма хэширования Mystique, который я разработал специально для усиления операций хэширования при вычислении блока. В нем используются различные преобразования чисел, примеры которых Вы можете видеть на картинке ниже. Данный алгоритм будет рассмотрен отдельно, так как он является дополнительным решением.
Проблема решена.Все. Проблема защиты POW-алгоритма от ASIC/GPU/FPGA и прочих специальных устройств решена. Для большей силы алгоритма в нем будут использоваться 256 битные числа.
Что уже сделано.На данный момент весь POW-алгоритм разработан и проверен. Основной код алгоритма реализован на C++ локально.
Что с этим делать делать?Вы можете имплементировать этот алгоритм в любую криптовалюту и это будет лучший алгоритм POW, который Вы только когда-либо знали.
