Zero-knowledge proof (ZKP) — это способ доказать, что у тебя есть решение задачи, не раскрывая его. Крис предложил автору реализовать такую схему, но не для криптовалют, а через теорию графов. Классический пример — 3-раскраска графа. Для данного графа нужно раскрасить вершины в три цвета так, чтобы соседние вершины были разного цвета. Задача решается долго, но проверить готовую раскраску легко: достаточно пройтись по всем ребрам.
Протокол из статьи Goldreich, Micali и Widgerson выглядит так. Доказывающий случайным образом переставляет цвета в своей раскраске. Потом кладет каждый цвет в «запертую коробку»: хеширует цвет вместе со случайным nonce, чтобы одинаковые цвета в разных вершинах не выглядели одинаково. Все хеши отправляются проверяющему. Тот выбирает случайное ребро и просит показать цвета его концов. Доказывающий открывает коробки, отправляя ключи — то есть исходные значения (цвет + nonce). Проверяющий сверяет хеши и убеждается, что цвета разные. Если нет — отвергает. Если все в порядке, повторяет. Один раунд мало что доказывает: доказывающий мог угадать ребро. Поэтому протокол повторяется m² раз. Тогда вероятность обмана становится исчезающе малой.
Авторы реализовали это на Python. Для устойчивости советуют ставить random.seed(0) и PYTHONHASHSEED=0, а для продакшена использовать не встроенный hash, а hashlib.sha256, а nonce генерировать через secrets.token_hex() или модуль hmac. Еще они сделали демо с сервером-доказывающим и клиентом-проверяющим, чтобы данные реально передавались по сети.
Тот же подход легко применить к судоку: переставляешь цифры, а вместо ребер проверяешь строки, столбцы и блоки. Любую NP-полную задачу можно свести к 3-раскраске, и тогда для нее тоже получится ZKP. Но на практике это непрактично: например, доказательство знания множителей для составного числа уже на двузначных числах дает граф с тысячами вершин. Лучше использовать более хитрые методы. Авторам больше всего понравились графы, теория вычислений и сетевые демо, а не криптовалюты или проверка возраста.