ZK вглубь: арифметизация, R1CS, SNARK против STARK

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

Что вообще доказывают

Начнём с точной постановки, потому что слово «доказательство» тут значит не то, что в математике на бумаге.

Есть утверждение: например, «я знаю такой x, что x³ + x + 5 = 35». Есть свидетель (witness): само значение x, которое доказывающий держит при себе. И есть публичная часть: то, что видно проверяющему, здесь это число 35 и сама формула.

От системы доказательства требуют три свойства:

• Полнота. Если утверждение верно и доказывающий честен, проверяющий примет доказательство.
• Корректность. Если утверждение ложно, обманщик почти наверняка не сможет построить принимаемое доказательство. Слово «почти» здесь честное: вероятность обмана не ноль, а величина вроде одной двухсотой степени двойки, что на практике невозможно.
• Нулевое разглашение. Проверяющий узнаёт только факт истинности утверждения и ничего сверх: сам x остаётся у доказывающего.

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

Простейший пример такой системы мы уже собирали: протокол Шнорра и приём Фиата-Шамира доказывают знание приватного ключа, не показывая его. Разница между тем протоколом и сегодняшним разговором в общности. Шнорр доказывает одно конкретное утверждение про дискретный логарифм. Сегодня нужно доказывать произвольное вычисление: любую программу, а не одну формулу.

Шаг 1: программа превращается в схему

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

Возьмём классический пример: доказать знание x, для которого x³ + x + 5 = 35. Сначала сплющиваем выражение так, чтобы в каждой строке было не больше одной операции:

sym1 = x * x
y    = sym1 * x
sym2 = y + x
out  = sym2 + 5

Четыре строки, четыре переменные плюс вход. Ничего не поменялось по смыслу, но теперь каждый шаг элементарен. Именно это и делают компиляторы ZK-языков (Circom, Cairo, Noir), только с миллионами строк и без участия человека.

Уже здесь видна главная особенность мышления в схемах. Обычная программа исполняется: часть веток не выполняется вовсе. Схема же существует целиком и всегда: если в программе был if, в схеме будут обе ветки плюс переменная-переключатель, которая обнуляет ненужную. Схема не умеет «не выполнять» код, она умеет только зануле́ние. Отсюда и цены: цикл с переменным числом итераций разворачивают на максимум, а обращение к памяти превращается в отдельную конструкцию с доказательством корректности доступа.

Шаг 2: схема превращается в систему ограничений

Теперь запишем эти четыре строки в единообразной форме, с которой уже умеет работать криптография. Форма называется R1CS.

Собираем вектор свидетеля из всех значений программы разом:

w = [1, out, x, sym1, y, sym2]

Первая единица нужна, чтобы выражать константы, вторым идёт публичный выход, дальше секретный вход и промежуточные значения. Каждое ограничение это тройка векторов коэффициентов A, B, C, а выполняется оно, когда (A·w) * (B·w) = (C·w), где точка это скалярное произведение.

Вот вся система на Rust, вместе с проверкой свидетеля и двумя попытками соврать:

/// Учебное поле: все операции по модулю простого p. Настоящие схемы берут
/// p длиной 254 бита, здесь маленькое, чтобы арифметика читалась глазами.
const P: u64 = 97;

fn add(a: u64, b: u64) -> u64 { (a + b) % P }
fn mul(a: u64, b: u64) -> u64 { (a * b) % P }

/// Одно ограничение R1CS: три вектора коэффициентов над вектором свидетеля.
struct Constraint {
    a: Vec<u64>,
    b: Vec<u64>,
    c: Vec<u64>,
}

/// Скалярное произведение строки коэффициентов на вектор свидетеля.
fn dot(row: &[u64], w: &[u64]) -> u64 {
    row.iter().zip(w).fold(0, |acc, (coeff, value)| add(acc, mul(*coeff, *value)))
}

impl Constraint {
    /// Ограничение выполнено, если (A·w) * (B·w) == (C·w).
    fn holds(&self, w: &[u64]) -> bool {
        mul(dot(&self.a, w), dot(&self.b, w)) == dot(&self.c, w)
    }
}

/// Схема для x^3 + x + 5 = out.
/// Свидетель: [1, out, x, sym1, y, sym2].
fn circuit() -> Vec<Constraint> {
    vec![
        // x * x = sym1
        Constraint { a: vec![0,0,1,0,0,0], b: vec![0,0,1,0,0,0], c: vec![0,0,0,1,0,0] },
        // sym1 * x = y
        Constraint { a: vec![0,0,0,1,0,0], b: vec![0,0,1,0,0,0], c: vec![0,0,0,0,1,0] },
        // (y + x) * 1 = sym2
        Constraint { a: vec![0,0,1,0,1,0], b: vec![1,0,0,0,0,0], c: vec![0,0,0,0,0,1] },
        // (sym2 + 5) * 1 = out
        Constraint { a: vec![5,0,0,0,0,1], b: vec![1,0,0,0,0,0], c: vec![0,1,0,0,0,0] },
    ]
}

/// Честный свидетель: прогоняем программу и записываем КАЖДЫЙ шаг.
fn witness(x: u64) -> Vec<u64> {
    let sym1 = mul(x, x);
    let y = mul(sym1, x);
    let sym2 = add(y, x);
    let out = add(sym2, 5);
    vec![1, out, x, sym1, y, sym2]
}

fn satisfied(w: &[u64]) -> bool {
    circuit().iter().all(|constraint| constraint.holds(w))
}

fn main() {
    let honest = witness(3);
    println!("свидетель x=3: {honest:?}");
    println!("система выполнена: {}", satisfied(&honest));

    // Попытка соврать: заявляем нужный выход, не меняя промежуточные значения.
    let mut forged = witness(4);
    forged[1] = 35;
    println!("подделка выхода: система выполнена: {}", satisfied(&forged));

    // Попытка соврать аккуратнее: подгоняем и предпоследний шаг.
    let mut forged2 = witness(4);
    forged2[1] = 35;
    forged2[5] = 30; // sym2 = out - 5
    println!("подделка двух шагов: система выполнена: {}", satisfied(&forged2));
}

Вывод программы:

свидетель x=3: [1, 35, 3, 9, 27, 30]
система выполнена: true
подделка выхода: система выполнена: false
подделка двух шагов: система выполнена: false

Здесь и лежит суть корректности. Система связывает каждый шаг вычисления через общий вектор свидетеля. Подкрутить выход не выйдет: сломается последнее ограничение. Подкрутить выход вместе с предыдущим шагом тоже не выйдет: сломается предыдущее. Чтобы система сошлась, придётся подобрать согласованный набор значений всех переменных, а это ровно и означает «честно провести вычисление».

Поиграй с этим ниже: двигай секрет, ломай промежуточное значение и смотри, какая строка перестаёт сходиться.

Обрати внимание на размер: три сложения и одно возведение в куб дали четыре ограничения. У настоящего zkEVM их десятки миллионов, и вся инженерия там про то, как ужать это число.

Шаг 3: зачем полиномы

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

Идея в двух шагах. Сначала все строки матриц A, B, C интерполируют в полиномы: значение полинома в точке i это коэффициент из i-го ограничения. Мы этот приём уже видели в схеме Шамира, где через точки восстанавливали секрет.

Дальше вся система из миллионов проверок превращается в одно полиномиальное тождество. Грубо говоря, A(z)·B(z) - C(z) обязано делиться нацело на известный полином Z(z), у которого корни ровно в точках-номерах ограничений. Выполнено тождество, значит выполнены все ограничения разом.

Почему это выгодно? Потому что работает лемма Шварца-Циппеля: два разных полинома невысокой степени совпадают лишь в исчезающе малой доле точек поля. Значит, проверяющему достаточно спросить значение в одной случайной точке. Если доказывающий не знал точку заранее, обмануть он может лишь с вероятностью порядка «степень полинома, делённая на размер поля», а поле у нас в районе 2²⁵⁴.

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