Рейтинг:2

Поддающееся проверке выполнение программы

флаг si

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

Ввод (известный всем):

  • Личность Алисы (включая открытый ключ и другие необходимые материалы)
  • Ввод программы
  • Сама программа
  • Вывод программы

Вывод (созданный Алисой):

  • Доказательство исполнения

Проверка (выполнена Бобом):

  • Возьмите все входные данные плюс доказательство выполнения и проверьте их правильность.

Ограничения:

  • Даже если Ева знает все входы и выходы, это не должно давать ей преимущества в создании собственного доказательства выполнения.
  • Проверка должна быть намного быстрее, чем повторное создание доказательства

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

флаг cn
Помогут ли поддающиеся проверке вычисления, например, https://eprint.iacr.org/2013/279.pdf? Ключевая особенность VC заключается в том, что проверка вычислений должна быть намного эффективнее, чем сами вычисления. Кстати, это ZKP, потому что верификатор должен знать ввод, но, похоже, он соответствует вашим требованиям.
флаг cn
Извините, опечатка, должно быть *не ЗКП*. Не могу отредактировать почему-то.
флаг si
В статье показывают, как его можно использовать и как ЗКП. Однако, если Ева хочет доказать, что она действительно проверяла программу, ей придется снова вызывать `KeyGen`, что кажется довольно дорогим. Я немного просмотрел документы, в которых упоминается Пиноккио, но не смог найти ничего, что могло бы удалить множественные вызовы `KeyGen`.
флаг jp
По определению любая информация, которая есть у Алисы и которой нет у Боба, является результатом работы программы. Мы могли бы вывести все промежуточные результаты, чтобы доказать, что Алиса действительно знает промежуточные результаты, но тогда их знала бы и Ева.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.