Концепции Zero-Knowledge

Зачем это блокчейн-разработчику?

В Module 2 мы изучали криптографические примитивы: хеш-функции, эллиптические кривые, цифровые подписи. Все они позволяют подтвердить информацию — подписать сообщение, проверить целостность данных. Но ни один из них не позволяет доказать что-то, не раскрывая секрета.

В Module 8 мы узнали, что ZK rollups используют validity proofs для мгновенной финализации. Но КАК можно доказать что-то, не раскрывая секрета? В этом модуле мы разберём математику zero-knowledge доказательств — от пещеры Али-Бабы до написания ZK-схем на Circom.

Zero-Knowledge Proofs (ZKP) — одна из самых мощных криптографических технологий. Они позволяют одной стороне (Prover) убедить другую (Verifier) в истинности утверждения, не раскрывая никакой дополнительной информации. Это не магия — это строгая математика.

Цепочка знаний:

• Phase 2 (CRYPTO-09/10): Эллиптические кривые — основа для commitment schemes и Sigma протоколов
• Phase 2 (CRYPTO-12): Schnorr подпись = Fiat-Shamir transform, применённый к Schnorr identification protocol
• Phase 8 (SCALE-06/07): ZK rollups используют validity proofs — теперь мы узнаем, как эти proofs устроены

Пещера Али-Бабы: интуиция ZK

Самая известная аналогия для Zero-Knowledge Proof — задача пещеры Али-Бабы. Она была предложена в 1990 году Жан-Жаком Кискватером, Луи Гийу и Томасом Биералем.

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

Почему это работает?

Ключевое наблюдение: после одного раунда Виктор не уверен — Пегги могла угадать (50%). Но каждый дополнительный раунд экспоненциально снижает вероятность обмана:

При 40 раундах вероятность обмана — 1 к триллиону. Виктор убеждён, но не узнал секретное слово.

Три свойства ZK-доказательства

Любой ZK-протокол должен удовлетворять трём свойствам:

Completeness (Полнота)

Если Prover действительно знает секрет, Verifier всегда примет доказательство. Это гарантирует, что честный Prover никогда не будет отвергнут.

Формально: Pr[Verify(proof) = accept | statement is true] = 1

Soundness (Надёжность)

Если Prover не знает секрет, он не сможет убедить Verifier (кроме пренебрежимо малой вероятности epsilon). Это защищает от мошенничества.

Формально: Pr[Verify(proof) = accept | statement is false] < epsilon

Zero-Knowledge (Нулевое разглашение)

Verifier не узнаёт ничего, кроме того, что утверждение истинно. Вся информация, которую Verifier получает из протокола, он мог бы сгенерировать сам (с помощью Simulator).

Формально: Существует алгоритм Simulator S, такой что выход S(statement) неотличим от реальной записи протокола.

Трёхцветная раскраска графа

Пещера Али-Бабы — интуитивная аналогия, но есть более строгий пример. Задача трёхцветной раскраски графа (3-coloring) — NP-полная задача. Prover знает раскраску, Verifier хочет убедиться в её существовании.

Протокол:

1. Prover случайно переставляет цвета (красный->синий, синий->зеленый, зеленый->красный) и скрывает все вершины (commitment).
2. Verifier выбирает случайное ребро (u, v).
3. Prover раскрывает цвета вершин u и v.
4. Verifier проверяет: цвета u и v различны.

Анализ свойств:

• Completeness: При правильной раскраске соседние вершины всегда разных цветов.
• Soundness: Если раскраска неправильная, хотя бы одно ребро одноцветное. Verifier обнаружит это с вероятностью >= 1/|E| за раунд.
• Zero-Knowledge: Перестановка цветов каждый раунд означает, что Verifier видит только “два разных цвета” — никакой информации о реальной раскраске.

Применения Zero-Knowledge

ZK-доказательства из теоретической конструкции превратились в одну из самых практичных криптографических технологий:

Реальные проекты

Interactive vs Non-Interactive

ZK-доказательства бывают двух типов:

Interactive: Prover и Verifier обмениваются сообщениями в реальном времени. Пещера Али-Бабы — интерактивный протокол. Требуется живой Verifier.

Non-Interactive: Prover генерирует доказательство один раз, любой может его проверить позже. SNARKs и STARKs — неинтерактивные. Доказательство публикуется в блокчейн, тысячи нод верифицируют независимо.

Ключевой мост между ними — Fiat-Shamir transform (ZK-03): хеш-функция “заменяет” случайный challenge от Verifier.

Три уровня понимания

Уровень 1: Интуитивный (аналогия)

ZK-доказательство — как доказать другу, что вы знаете решение судоку, не показывая решение. Вы можете:

• Дать другу выбрать любую строку — показать, что в ней все числа от 1 до 9
• Дать выбрать столбец — показать, что в нём все числа от 1 до 9
• Дать выбрать квадрат 3x3 — то же самое

После достаточного числа проверок друг убеждён, что вы решили судоку, но не видел решение целиком.

Уровень 2: Алгоритмический (псевдокод)

ZK_PROTOCOL(Prover, Verifier, statement, witness):
    for round in 1..N:
        # Move 1: Prover commits
        commitment = Prover.commit(witness, randomness)
        send(Prover -> Verifier, commitment)

        # Move 2: Verifier challenges
        challenge = Verifier.random_challenge()
        send(Verifier -> Prover, challenge)

        # Move 3: Prover responds
        response = Prover.respond(witness, randomness, challenge)
        send(Prover -> Verifier, response)

        # Verifier checks
        if not Verifier.check(statement, commitment, challenge, response):
            return REJECT

    return ACCEPT  # After N rounds, convinced

Уровень 3: Математический (формальный)

Определение (Interactive Proof System):

Пара алгоритмов (P, V) — interactive proof system для языка L, если:

1. Completeness: Для всех x принадлежащих L, существует witness w: Pr[(P(x, w), V(x)) = accept] = 1

2. Soundness: Для всех x не принадлежащих L, для всех P*: Pr[(P*(x), V(x)) = accept] < epsilon(n)

3. Zero-Knowledge: Существует PPT Simulator S, для всех x принадлежащих L: {View_V[(P(x, w), V(x))]} ~ {S(x)}

   где ~ означает вычислительную неотличимость.

Виды ZK:

• Perfect ZK: Распределения тождественны (информационно-теоретическая стойкость)
• Statistical ZK: Статистическое расстояние < epsilon
• Computational ZK: Полиномиальный наблюдатель не различит (достаточно для практики)

Итоги

Что дальше: В ZK-02 мы изучим commitment schemes — строительные блоки ZK-доказательств. Hash-based и Pedersen commitments, свойства binding и hiding, гомоморфность. Это подготовит нас к пониманию Sigma протоколов в ZK-03.