Обязательства, разделение секрета и ZK

У нас есть весь базовый арсенал: хеши, шифры, кривые, подписи. Последний урок блока про конструкции, которые из этого арсенала строят почти магию: доказать, что знаешь секрет, не показав его; разрезать ключ так, чтобы кусок не давал ничего; считать на зашифрованных данных, не расшифровывая. Это мост от примитивов к приватности и масштабированию Web3. Обзорный, но с кодом там, где руки полезнее слов.

Схемы обязательств

Начнём с маленького, но всюду используемого кирпича. Схема обязательства (commitment) это криптографический запечатанный конверт. Ты фиксируешь значение сейчас, а раскрываешь потом, и от схемы хотят двух свойств: hiding (по конверту значение не прочитать) и binding (подменить значение после фиксации нельзя).

Простейшее обязательство строится на хеше из первого урока: commit = H(value || nonce). Случайный nonce нужен для hiding, иначе короткое значение вроде «ставка 5» подберут перебором. Раскрытие это пара (value, nonce), проверяющий пересчитывает хеш и сверяет.

use sha2::{Digest, Sha256};

fn commit(value: &[u8], nonce: &[u8; 32]) -> [u8; 32] {
    let mut h = Sha256::new();
    h.update(value);
    h.update(nonce); // случайный, иначе hiding ломается перебором
    h.finalize().into()
}

fn open(value: &[u8], nonce: &[u8; 32], commitment: &[u8; 32]) -> bool {
    &commit(value, nonce) == commitment
}

Зачем это в блокчейне: честный аукцион (все фиксируют ставки, потом раскрывают, подменить нельзя), схема «commit-reveal» против фронтраннинга, генерация случайности без доверия.

Хеш-обязательство решает задачу, но у него нет структуры: сложить два запечатанных конверта и получить конверт с суммой нельзя, хеш всё перемешивает. А именно это нужно блокчейну, который прячет суммы переводов. Тут берут обязательство Педерсена C = vG + rH. Здесь G и H две точки эллиптической кривой из урока про кривые, v это прятуемое значение, r случайная соль. Hiding держится на r: точка rH равномерно размазывает vG по всей кривой, по C про v не узнать ничего. Binding держится на том, что связь между G и H (дискретный логарифм) никто не знает, иначе нашлась бы вторая пара (v', r') с тем же C.

Отсюда вопрос, который легко проглядеть: откуда взять такую H? Выбрать точку самому нельзя. Кто выбирал, тот мог тихо взять H = kG с известным себе k, и для него binding не работает: зная k, он пересчитает обязательство в другую пару (v', r') и перепишет зафиксированное значение задним числом, а снаружи никто не отличит. Поэтому H строят публично проверяемым способом: берут что-нибудь общеизвестное (например, сериализацию самой G), хешируют и отображают результат в точку кривой (приём hash-to-curve). Такой рецепт называют nothing-up-my-sleeve: параметры выведены открытой формулой из открытых данных, спрятать в них лазейку негде, и дискретный логарифм H относительно G не знает никто, включая автора схемы.

Главная польза Педерсена в том, что он складывается: C₁ + C₂ = (v₁ + v₂)G + (r₁ + r₂)H, то есть сумма обязательств это обязательство к сумме значений. Так работают конфиденциальные транзакции Monero (протокол RingCT): сумма каждого входа и выхода заменена обязательством Педерсена, и узел проверяет баланс, складывая точки и сверяя, что вход равен выходу плюс комиссия. Суммы он при этом не видит. Остаётся одна дыра: значение под обязательством может быть «отрицательным» по модулю поля, и из воздуха создастся монета. Её закрывают доказательством диапазона (Monero с 2018 года использует Bulletproofs), которое подтверждает, что спрятанное число лежит в допустимых границах, не раскрывая его. Доказательство диапазона это уже частный случай темы из следующего раздела.

Разделение секрета по Шамиру

Следующая конструкция отвечает на вопрос: как хранить ключ так, чтобы он не лежал целиком ни у кого, но t доверенных лиц вместе могли его восстановить? Ответ Ади Шамира (того самого, S в RSA) элегантен и стоит на школьной геометрии.

Разделение секрета по Шамиру прячет секрет в свободный член многочлена. Через две точки проходит ровно одна прямая, через три ровно одна парабола, через t точек ровно один многочлен степени t−1. Берём многочлен f(x) = secret + a₁x + ... + a_{t−1}x^{t−1} со случайными коэффициентами над конечным полем, раздаём доли как точки (i, f(i)). Любые t долей восстанавливают f и читают f(0) = secret. А t−1 долей оставляют бесконечно много одинаково правдоподобных многочленов: о секрете не известно ничего, не «почти ничего», а буквально ничего (это доказуемо).

const P: i128 = 2_147_483_647; // простое поле (M31), секрет должен быть меньше P

fn modp(x: i128) -> i128 {
    ((x % P) + P) % P
}

/// Обратный по модулю через расширенный алгоритм Евклида.
fn inv(a: i128) -> i128 {
    let (mut old_r, mut r) = (modp(a), P);
    let (mut old_s, mut s) = (1i128, 0i128);
    while r != 0 {
        let q = old_r / r;
        (old_r, r) = (r, old_r - q * r);
        (old_s, s) = (s, old_s - q * s);
    }
    modp(old_s)
}

/// Режем секрет на n долей с порогом t. coeffs это t-1 случайных коэффициентов.
fn split(secret: i128, n: usize, coeffs: &[i128]) -> Vec<(i128, i128)> {
    (1..=n as i128)
        .map(|x| {
            let mut y = modp(secret);
            let mut power = 1i128;
            for &a in coeffs {
                power = modp(power * x); // x, x^2, ...
                y = modp(y + a * power);
            }
            (x, y)
        })
        .collect()
}

/// Восстанавливаем f(0) интерполяцией Лагранжа по t долям.
fn reconstruct(shares: &[(i128, i128)]) -> i128 {
    let mut secret = 0i128;
    for (i, &(xi, yi)) in shares.iter().enumerate() {
        let (mut num, mut den) = (1i128, 1i128);
        for (j, &(xj, _)) in shares.iter().enumerate() {
            if i != j {
                num = modp(num * modp(-xj)); // числитель: произведение (0 - xj)
                den = modp(den * modp(xi - xj)); // знаменатель: произведение (xi - xj)
            }
        }
        secret = modp(secret + yi * modp(num * inv(den)));
    }
    secret
}

fn main() {
    let secret = 1_234_567i128;
    // порог t = 3 (значит t-1 = 2 коэффициента), всего n = 5 долей.
    // В бою коэффициенты тянут из CSPRNG: предсказуемый коэффициент рушит
    // всю схему. Здесь они зафиксированы, чтобы вывод воспроизводился.
    let shares = split(secret, 5, &[42, 999]);

    // любые 3 доли восстанавливают секрет
    let any_three = vec![shares[0], shares[2], shares[4]];
    assert_eq!(reconstruct(&any_three), secret);

    // двух долей не хватает: они задают многочлен неоднозначно
    println!("секрет восстановлен по 3 из 5 долей");
}

Покрути это руками. Ниже секрет это высота кривой над нулём, доли это точки на кривой при x = 1, 2, .... Раскрывай доли по одной и смотри, в какой момент кривая перестаёт гулять. Пока долей меньше порога, через раскрытые точки проходит сразу несколько кривых, и каждая упирается в свой секрет (оранжевые пунктиры): доли не выдают о нём ничего. Как только долей ровно t, кривая фиксируется одна, и Лагранж читает её высоту в нуле.

секрет f(0): 20порог t: 3всего долей n: 5раскрыто долей: 2форма кривой (seed): 5

Долей мало: 2 из нужных 3. Через эти точки проходит бесконечно много кривых, и каждая упирается в свой f(0). Три из них нарисованы: секрет может оказаться любым числом, доли не выдают ничего. Это и есть нулевое знание ниже порога.

Порог t = 3 даёт многочлен степени 2: при t = 2 это прямая, при t = 3 парабола. Доли это точки на ней, секрет это её высота на оси x = 0.

Так устроены резервные копии ключей (Shamir backup в кошельках), хранение ключей мостами и кастодианами, а пороговые подписи из прошлого урока это та же идея, но восстановление секрета не выполняется явно, доли участвуют в подписи прямо в расщеплённом виде.