Я хотел бы знать, какие криптографические примитивы можно использовать для Алисы, чтобы доказать Бобу, что она действительно выполнила программу. Цель состоит в том, чтобы сделать Proof-of-useful работой, где Алиса доказывает, что она подтвердила транзакцию, но где это доказательство привязано к открытому ключу Алисы. Создание доказательства должно быть возможно только при выполнении программы. Проверка доказательства должна быть намного быстрее с использованием открытого ключа Алисы.
Ввод (известный всем):
- Личность Алисы (включая открытый ключ и другие необходимые материалы)
- Ввод программы
- Сама программа
- Вывод программы
Вывод (созданный Алисой):
- Доказательство исполнения
Проверка (выполнена Бобом):
- Возьмите все входные данные плюс доказательство выполнения и проверьте их правильность.
Ограничения:
- Даже если Ева знает все входы и выходы, это не должно давать ей преимущества в создании собственного доказательства выполнения.
- Проверка должна быть намного быстрее, чем повторное создание доказательства
В настоящее время я изучаю проверяемые функции задержки и проверяемые случайные функции, но, похоже, это не совсем соответствует цели. Возможно, можно было бы использовать какой-то ZKP, но доказать универсальное выполнение программы кажется очень сложным.