Введение

Системы, основанные на блокчейне, входят во многие сферы нашей жизни, в такие отрасли, как DeFi или игры. Однако многим современным блокчейнам не хватает конфиденциальности и масштабируемости, что ограничивает диапазон вариантов использования. Доказательства с нулевым разглашением и цепочки блоков, поддерживаемые доказательствами с нулевым разглашением, такими как Aleo, обещают обеспечить лучшую масштабируемость и гарантии конфиденциальности, а также включить новые приложения для блокчейнов. Это включает в себя новые приложения DeFi, более сложные игры web3 или даже программы на основе искусственного интеллекта. Многие из этих приложений требуют представления широкого диапазона чисел, включая дробные числа. Aleo поставляется с языком программирования Leo, который значительно упрощает программирование программ, основанных на нулевых знаниях. Однако он поддерживает только числа на основе целых чисел. В этой статье мы анализируем структуру чисел с фиксированной запятой в zkSNARKs с использованием Leo, что позволяет нам также вычислять с использованием дробей для широкого спектра приложений.

Простая реализация чисел с фиксированной запятой

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

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

пусть i: u32 = 155;

Теперь мы можем выполнять математические вычисления с этой переменной. Например, чтобы добавить 0,45, мы добавляем 45 (.45 * 100) в программный код, что приводит к значению переменной 200. При интерпретации выходных данных программы нам нужно разделить значение на коэффициент масштабирования 100, чтобы получить желаемую десятичную систему счисления - результат сложения равен 2 в десятичной системе счисления.

Аналогично, мы также можем выполнять умножения. При умножении на 2,50 в десятичной системе счисления мы умножаем на 250 в системе счисления с фиксированной запятой, а затем делим результат на коэффициент масштабирования 100. Например, 2*2,5=5 в десятичной системе счисления относится к 200*250/100=500 в системе счисления с фиксированной запятой. Опять же, при интерпретации результата вне системы счисления с фиксированной запятой нам нужно разделить число с фиксированной запятой 500 на коэффициент масштабирования 100, чтобы получить ожидаемый результат 5.

Для деления мы действуем аналогично умножению, но вместо деления умножаем на коэффициент масштабирования.

Например, 4,5/0,5 = 9 в десятичной системе счисления относится к 100*450/50 = 900 в системе счисления с фиксированной запятой. Деленный на коэффициент масштабирования, мы получаем ожидаемый результат 9.

Обобщение и вещи, которые следует учитывать

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

В приведенном выше примере использования u32 общий диапазон составляет от 0 до 232-1=4 294 967 295. Из-за бинарной природы типов общим понятием является использование масштабных коэффициентов S степеней двойки. Например, при использовании коэффициента масштабирования 2⁵=32 для дробной части используется 5 бит, а для целочисленной части остается только 27 бит. Таким образом, максимальное число для целой части равно 22⁷-1=134 217 727, а разрешение дробной части равно 1/2⁵= 1/32. Дробная часть может добавить 31/32 к максимальному целому числу, поэтому максимальное представимое значение лежит между 0 и 22⁷-1 + 31/32 = 134 217 727,969.

В то же время максимальная ошибка представления вычисляется как (1 / С) / 2, поэтому в этом примере она равна (1/2⁵) / 2 = 1/64 = 0,015625. Таким образом, больший коэффициент масштабирования позволяет нам иметь более точные представления дробных чисел, но уменьшает размер целой части и, следовательно, диапазон представимых значений.

Как мы видим, существует компромисс между диапазоном значений, которые мы можем хранить, и точностью чисел, которые мы представляем.

Особенно при умножении или делении мы можем столкнуться с переполнением. Например, предположим, что у нас есть коэффициент масштабирования 2⁵ = 32, и мы хотим умножить 21⁶ = 65536 на 2⁶ = 64. Приведенный ниже код пытается это сделать.

функция main() -> u32 {

пусть s: u32 = 32;

пусть a: u32 = 65536 * с;

пусть b: u32 = 64 * с;

пусть результат: u32 = a * b / s;

возвращает результат;

}

Для обозначения с фиксированной точкой мы должны умножить оба числа на коэффициент масштабирования и фактически умножить 221 на 211, прежде чем делить с коэффициентом масштабирования 2⁵. Просто взглянув на инструкции, мы, таким образом, ожидаем, что код на выходе составит 22⁷.

Однако, когда мы смотрим на результат, мы получаем:

[регистры]

r0: u32 = 0;

Временный результат c * d равен 232, что просто выходит за пределы диапазона типа u32. Таким образом, мы фактически получили переполнение числа и получили неверный результат.

Итак, что мы можем с этим поделать? Мы могли бы использовать тип u64 вместо типа u32 для всех типов (переменные и выходные данные), которые могут хранить числа до 2⁶⁴-1. Таким образом, мы получаем ожидаемый результат 22⁷:

[регистры]

r0: u64 = 134217728;

Помните, что нам нужно снова разделить на коэффициент масштабирования, чтобы интерпретировать результат числа с фиксированной запятой в обычных терминах: 22⁷ / 2⁵ = 222, что является результатом вышеупомянутого вычисления 21⁶, умноженного на 2⁶.

Однако при использовании u64 размер схемы увеличился с 96 до 192 ограничений, фактически удвоившись в размере. Это может привести к увеличению затрат на проверку, особенно в сложных приложениях. Таким образом, альтернативой было бы уменьшить коэффициент масштабирования и тем самым потенциально снизить точность представления чисел.

При использовании 2⁴ в качестве коэффициента масштабирования вместо 2⁵ только для типов u32 мы получаем следующий результат:

[регистры]

r0: u32 = 67108864;

Этот результат равен 22⁶. Опять же, разделите его на коэффициент масштабирования 2⁴, и мы получим ожидаемый и правильный результат 222.

Код обычно также работает для отрицательных чисел. Однако нам нужно использовать целочисленные типы со знаком. Примите во внимание, что знаку нужен дополнительный бит, поэтому для i32 диапазон целочисленной части вычисляется как +- 231-1, что переводится в диапазон от -2147483648 до 2147483647.

Пример кода

Сложение двух чисел a и b в формате с фиксированной запятой:

функция add(a: u32, b: u32) -> u32 {

пусть результат: u32 = a + b;

возвращает результат;

}

Умножение двух чисел a и b в формате с фиксированной запятой:

функция умножения(a: u32, b: u32, s: u32) -> u32 {

пусть результат: u32 = a * b / s;

возвращает результат;

}

Деление двух чисел a и b в формате с фиксированной запятой:

функция divide(a: u32, b: u32, s: u32) -> u32 {

пусть результат: u32 = s * a / b;

возвращает результат;

}