Да, действительно продали, во время конференции Financial Crypto 2016. Это был доклад о снарках, с открытым исходным кодом и экзотической транзакцией. И подробным разоблачением черной магии, Bowe-Maxwell на bitcoincore.
Это не перевод известного материала. Здесь альтернативный C++ код и R1CS circuit для проверки правильности решения судоку. Приватной проверки: проверяющий получает только снарк-доказательство и исходную позицию, но не решение. Позвольте повторить: оригинал был в 2016.
Реализованная проверка проще оригинала: секретное решение должно соответствовать правилам судоку и исходной позиции, всё. Оригинал еще проверяет что шифротекст получен из решения, и может быть расшифрован хэшем из транзакции покупки. Мне было интересно проследить (отреверсить) код, и применить полиномиальное представление множеств в моем варианте.
Если Вы проходите или читаете курс по современной криптографии, может быть интересно русскоязычное сочинение:
doc/sudoku19ru.pdf
Тем кто только начинает - поможет введение с буквально секретной таблицей умножения, это может быть доступно первокласснику. В тексте много ссылок. Было на IEEE ATIT 2019. Полиномиальное представление графов привело к альтернативной интерактивной системе доказательства (zero-knowledge протоколу) для распознавания раскраски графов, MFCS 2012.
Сегодня мы начинаем с приватности транзакций Zcash.
Дети начинают информатику с мобильного телефона, и преподаватели могут просить их сделать что-нибудь самостоятельно, на своем телефоне.
Телефон при этом остается дорогим и очень сложным устройством.
В примере с таблицей умножения есть единственная секретная тройка, и еще C++ код размером в только одну страницу.
Построена R1CS система уравнений, получены два публичных ключа, получено снарк-доказательство существования подходящего секрета, выполнена проверка.
Если Вам понятен этот код - дальше сами разберетесь как реализована проверка правильности решения судоку и транзакции Zcash.
В этом тексте реализована “детская” проверка решения Судоку с игровыми картам, в фотографиях на сайте Наора (url в тексте). Это объяснять бессмысленно, нужно посмотреть.
Если для кого-нибудь R1CS кажется малопонятным - есть пример с “таблицей умножения на секретную тройку” в разделе 7, это уровень первого класса.
Новым (по сравнению с оригинальной работой Bowe-Maxwell) является полиномиальное представление множеств игральных карт. Уровень сложности - раскрыть скобки с иксами и упростить, седьмой класс.