Обратимые вычисления

ИССЛЕДОВАНИЯ ПО ЛИНЕЙНОМУ ОБРАТИМОМУ КОДУ

На этой страничке будут размещены результаты моих исследований по линейному двоичному обратимому коду, обратимым вычислениям на не обратимом процессоре. Двоичный код это форма записи операторов в двоичном коде типа a += b, в этом коде у оператора всего два операнда. Двоичный код проще для обращения. Линейный код это код без ветвлений и циклов, он прост для программирования обратного выполнения и пригоден для задач криптологии. Обратимый же код это программный код, позволяющий как прямое, так и обратное, снизу-вверх, выполнение. Проект ориентирован на легальную добычу криптовалюты участием в пуле чешской компании.

Black Emulator

Линейный обратимый код

Для обратного выполнения хэш-функции её код надо записать на обратимом языке программирования. Полный обратимый язык программирования должен содержать все основные операторы языка высокого уровня, включая условия, циклы и операторы выбора. Эти операторы сложны для обратного выполнения, для их эмуляции нужно писать рекурсивное опровержение гипотез о следующем адресе выполнения. Хоть такой перебор и сокращён, основан на раннем выходе из рекурсии, тем не менее он занимает лишнее время. Обратное выполнение полной обратимой программы намного дольше прямого выполнения.

К счастью, для обращения хэш-функций полного языка программирования и не надо. Достаточно линейного обратимого кода, который выглядит так, как показано в тексте ниже. Из обратимого языка программирования удаляются все операторы с переходами, оставляя минимальный набор операторов из арифметических и логических действий. Добавляя операторы конструирования трассы выполнения хэш-функции в код хэш-функции, получаем автоматическое построение обратимой хэш-функции, на линейном обратимом коде. Эту хэш-функцию можно выполнять как прямо, от аргументов к результату, так и обратно, от результата к аргументу. Выполняя хэш-функцию обратно, от хэш-значения к входному тексту, восстанавливаем открытый текст или коллизию.

0)  Test:

1) a := input

2) b := input

3) a &= 12345

4) b &= a

5) y := input

6) z := input

7) y &= 12

8) z &= y

9) c := input

10) d := input

11) c |= 12345

12) c |= d

13) e := input

14) f := input

15) e |= 12

16) e |= f

17) g := input

18) h := input

19) g <<= 8

20) g <<= h

21) h <<= 2

22) h <<= g

23) i := input

24) j := input

25) i >>= 8

26) i >>= j

27) j >>= 2

28) j >>= i

29) i ^= j

30) i ^= 12

31) neg i

32) k := input

33) l := input

34) k ^= l

35) k ^= 12

36) neg k

37) m := math

38) n := math

39) m += n

40) m += 12345

41) m *= n

42) m *= 12345

43) flag <- 1

44) result <- m

Линейный обратимый код содержит основные логические операторы языка программирования - не, и, или, сильное или, сдвиги влево и вправо. Кроме того он содержит арифметические операторы плюс, минус, умножить, и операторы копирования значения и перемещения значения. Линейный обратимый код оперирует не с регистрами, а с переменными. Ниже приводится дамп обратного выполнения со всеми операторами линейного обратимого кода.

44)  result <- m                     m = 3762465317

43) flag <- 1

42) m *= 12345                      m = 2353230157

41) m *= n                          m = 277215 n = 132435

40) m += 12345                      m = 264870

39) m += n                          m = 132435 n = 132435

38) n := math                       math = 132435

37) m := math                       math = 132435

36) neg k                           k = 12 k = 12

35) k ^= 12                         k = 0

34) k ^= l                          k = 49 l = 54321

33) l := input                      input = 54321

32) k := input                      input = 49

31) neg i                           i = 13568 i = 13568

30) i ^= 12                         i = 13580

29) i ^= j                          i = 0 j = 13580

28) j >>= i                         j = 13580 i = 0

27) j >>= 2                         j = 54320

26) i >>= j                         i = 0 j = 54320

25) i >>= 8                         i = 0

24) j := input                      input = 54320

23) i := input                      input = 0

22) h <<= g                         h = 217284 g = 1644167168

21) h <<= 2                         h = 54321

20) g <<= h                         g = 12544 h = 54321

19) g <<= 8                         g = 49

18) h := input                      input = 54321

17) g := input                      input = 49

16) e |= f                          e = 61 f = 54321

15) e |= 12                         e = 61

14) f := input                      input = 54321

13) e := input                      input = 61

12) c |= d                          c = 62521 d = 54321

11) c |= 12345                      c = 62521

10) d := input                      input = 54321

9) c := input                      input = 62521

8) z &= y                          z = 255 y = 0

7) y &= 12                         y = 243

6) z := input                      input = 255

5) y := input                      input = 243

4) b &= a                          b = 4294967295 a = 4145

3) a &= 12345                      a = 4294959095

2) b := input                      input = 4294967295

1) a := input                      input = 4294959095

0) Test:

ТУПИКОВЫЕ СОСТОЯНИЯ

Основной решаемой сейчас проблемой есть тупиковые состояния на случайных путях обратного выполнения. В инструкциях And, Or, ShiftLeft и ShiftRight при обратном выполнении имеются неоднозначные значения восстанавливаемых битов. И при 0 и при 1 предыдущее состояние программы переходит в текущее и нет простого метода определить нужное значение бита. В зависимости от выбранного значения 0 или 1 обратное выполнение продолжится по разным путям на дереве обратного выполнения. Некоторые пути оказываются тупиковыми. В тупиковой точке может не быть решения для предыдущего состояния, переходящего в текущее. В таком случае обратное выполнение должно было развиваться по другому пути. Так как дерево обратного выполнения имеет большую глубину и большой коэффициент ветвления, то нужен хороший алгоритм поиска пути на графе или на дереве. Алгоритм поиска пути на дереве обратного выполнения, например - алгоритм Дейкстры, быстро находящий пути на гигантских графах, как то карты городов и мегаполисов в программах поиска маршрутов проезда автомобилей. Или алгоритм поиска А*.

ПРИЛОЖЕНИЯ В КРИПТОВАЛЮТАХ

После записи хэш-функции на обратимом языке программирования и выполнения её снизу-вверх, обратно, от результатов к аргументам, можно восстанавливать аргументы по результатам. Например, по результату проверки сложности блока биткоина можно восстанавливать магическое число nonce блока биткоина, добывая тем самым новый биткоин. Разрабатываемая сейчас такая программа, Back Miner, изображена ниже. Она связывается с Чешским пулом добытчиков биткоинов, по протоколу stratum, получает задачу на поиск корректного хэша, и решает задачу поиска числа nonce обратным выполнением, а не полным перебором. Это демонстрирует одно из применений обратимым вычислениям.

ОБРАТИМАЯ СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ

Идея обратимой минимизации функций состоит в том, чтобы перебирать значение, а не аргументы функции. Так как мощность множества значений меньше мощности множества аргументов, то минимизация происходит быстрее. При этом значения аргументов получаются по значению функции обратным выполнением функции, от результата к аргументам. Например, если минимизируется функция десяти аргументов, то проводя поиск в интервале возможных значений, в одномерном интервале, вместо десяти мерного пространства аргументов, ускоряем оптимизацию в десять миллиардов раз. А если минимизируется функция тысячи аргументов, по поиск происходит в одномерном диапазоне вместо тысяча мерного пространства. Задача упрощается в десять в тысячной степени раз! Примером такой задачи может быть автоматический поиск музыкальной композиции с тысячей нот, оптимизирующей модель удовольствия от прослушивания.

Для обратимой оптимизации подходят любые дискретные функции, без ограничения на вид функции в том смысле, что если код функции не сбоит при обратном выполнении, то функцию можно минимизировать. Методом обратимой стохастической оптимизации.

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

Алгоритм обратимой стохастической оптимизации состоит в следующем. Для начального приближения функция выполняется прямо и значение становится текущим минимумом. После этого в диапазоне плюс-минус 100 проверяются все точки около минимума: значение устанавливается на выходе, обратным выполнением считается вход, прямым выполнением считается выход. Получившийся выход будет левее или правее установленного выхода. Если левее и меньше текущего минимума, он становится текущим минимумом.

После того как диапазон исчерпан, выбирается новая случайная середина перебираемого диапазона, в интервале от 0 до 20 * minimum. И перебор диапазона плюс-минус 100 повторяется заново. И так до тех пор, пока не достигнуто значение минимума меньше требуемого или оптимизация не прервана. Диапазон простреливаемых значений суживается, так как ограничен справа текущим минимумом, умноженным на 20.

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

ПРИМЕР

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

Для обратного выполнения целевая функция должна быть записана на обратимом языке программирования. В данном примере она записана на языке линейного обратимого кода. Линейный код - это код без ветвлений и циклов, а обратимый код позволяет выполнять программу как прямо, так и обратно, снизу - вверх. Далее идёт пример программы с обратимой функцией дискретного полинома десятой степени.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using BinaryCode;

namespace TestMath

    class Program : Emulator

        public override void Code()

            SetInput("x1", 1000);

            SetInput("x2", 2000);

            SetInput("x3", 3000);

            SetInput("x4", 4000);

            SetInput("x5", 5000);

            SetInput("x6", 6000);

            SetInput("x7", 7000);

            SetInput("x8", 8000);

            SetInput("x9", 9000);

            SetInput("x10", 10000);

            Name("Polynom10");

            Mul("x2", "x2");

            Sub("x1", "x2");

            Copy("tmp3", "x3");

            Mul("tmp3", "x3");

            Mul("tmp3", "x3");

            Add("x1", "tmp3");

            Copy("tmp4", "x4");

            Mul("tmp4", "x4");

            Mul("tmp4", "x4");

            Mul("tmp4", "x4");

            Sub("x1", "tmp4");

            Copy("tmp5", "x5");

            Mul("tmp5", "x5");

            Mul("tmp5", "x5");

            Mul("tmp5", "x5");

            Mul("tmp5", "x5");

            Add("x1", "tmp5");

            Copy("tmp6", "x6");

            Mul("tmp6", "x6");

            Mul("tmp6", "x6");

            Mul("tmp6", "x6");

            Mul("tmp6", "x6");

            Mul("tmp6", "x6");

            Sub("x1", "x6");

            Copy("tmp7", "x7");

            Mul("tmp7", "x7");

            Mul("tmp7", "x7");

            Mul("tmp7", "x7");

            Mul("tmp7", "x7");

            Mul("tmp7", "x7");

            Mul("tmp7", "x7");

            Add("x1", "tmp7");

            Copy("tmp8", "x8");

            Mul("tmp8", "x8");

            Mul("tmp8", "x8");

            Mul("tmp8", "x8");

            Mul("tmp8", "x8");

            Mul("tmp8", "x8");

            Mul("tmp8", "x8");

            Mul("tmp8", "x8");

            Sub("x1", "tmp8");

            Copy("tmp9", "x9");

            Mul("tmp9", "x9");

            Mul("tmp9", "x9");

            Mul("tmp9", "x9");

            Mul("tmp9", "x9");

            Mul("tmp9", "x9");

            Mul("tmp9", "x9");

            Mul("tmp9", "x9");

            Mul("tmp9", "x9");

            Add("x1", "tmp9");

            Copy("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Mul("tmp10", "x10");

            Sub("x1", "tmp10");

            Move("result", "x1");

        static void Main(string[] args)

            Program p = new Program();

            p.debug = false;

            p.Code();

            Console.WriteLine(p.Text);

            if (p.Minimize("result", 534287, 100)) Console.WriteLine(p.Variables);

После автоматического построения линейного обратимого кода программой на C# обратимый код выглядит следующим образом.

CODE:

0)  Polynom10:

1) x2 *= x2

2) x1 -= x2

3) tmp3 := x3

4) tmp3 *= x3

5) tmp3 *= x3

6) x1 += tmp3

7) tmp4 := x4

8) tmp4 *= x4

9) tmp4 *= x4

10) tmp4 *= x4

11) x1 -= tmp4

12) tmp5 := x5

13) tmp5 *= x5

14) tmp5 *= x5

15) tmp5 *= x5

16) tmp5 *= x5

17) x1 += tmp5

18) tmp6 := x6

19) tmp6 *= x6

20) tmp6 *= x6

21) tmp6 *= x6

22) tmp6 *= x6

23) tmp6 *= x6

24) x1 -= x6

25) tmp7 := x7

26) tmp7 *= x7

27) tmp7 *= x7

28) tmp7 *= x7

29) tmp7 *= x7

30) tmp7 *= x7

31) tmp7 *= x7

32) x1 += tmp7

33) tmp8 := x8

34) tmp8 *= x8

35) tmp8 *= x8

36) tmp8 *= x8

37) tmp8 *= x8

38) tmp8 *= x8

39) tmp8 *= x8

40) tmp8 *= x8

41) x1 -= tmp8

42) tmp9 := x9

43) tmp9 *= x9

44) tmp9 *= x9

45) tmp9 *= x9

46) tmp9 *= x9

47) tmp9 *= x9

48) tmp9 *= x9

49) tmp9 *= x9

50) tmp9 *= x9

51) x1 += tmp9

52) tmp10 := x10

53) tmp10 *= x10

54) tmp10 *= x10

55) tmp10 *= x10

56) tmp10 *= x10

57) tmp10 *= x10

58) tmp10 *= x10

59) tmp10 *= x10

60) tmp10 *= x10

61) tmp10 *= x10

62) x1 -= tmp10

63) result <- x1

Оптимизация заняла в данному случае около десяти секунд, из-за удачно подобранных констант алгоритма. Найдено относительно маленькое значение 235349 с 44% нулевых битов в начале хэш-значения. Такие показатели должны быть достаточны для хэш-функций при майнинге криптовалюты. Ниже приводится протокол минимизации. Очевидно, смысл в логически-обратимых вычислениях на необратимых процессорах есть.

Iteration 0: Point = 58634516   result = 25410071

Iteration 1632: Point = 55231296   result = 22006851

Iteration 5100: Point = 42849235   result = 9624788

Iteration 5404: Point = 5407564   result = 9624788

Iteration 5508: Point = 35690679   result = 2466234

Iteration 6324: Point = 33459794   result = 235349

VARIABLES:

 x1 = 4269793478

 x2 = 1

 x3 = 3000

 x4 = 21499808

 x5 = 166728584

 x6 = 37230448

 x7 = 202513240

 x8 = 0

 x9 = 468154408

 x10 = 0