Space and Time работает над тем, чтобы SQL-запросы передавались на аутсорсинг проверяющей стороне и подтверждались Верификатором.

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

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

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

Сторона, выполняющая вычисления, передается субъекту, известному как Проверяющий; Проверяющий доказывает, что заявленный результат верен. Верификатор — это сторона, которая подтвердит утверждение Проверяющего. Неофициально Проверяющего и Верификатора зовут Пегги и Виктор соответственно.

С точки зрения классической теории сложности, недетерминированные проблемы полиномиального времени (NP), по-видимому, удовлетворяют этой цели. Неформально говоря, проблемы NP — это проблемы, которые трудно решить, но легко проверить. Учитывая многочлен, может быть трудно найти нули этого многочлена; это очевидно из разнообразия методов, изучаемых на курсах математики. Однако для проверки утверждения о том, что x = 5 является нулем многочлена, достаточно просто оценить многочлен при x = 5.

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

Классический пример верифицируемых вычислений включает умножение матриц. В частности, доказывающий утверждает, что C является результатом умножения матриц A и B; для простоты мы предполагаем, что A и B — матрицы размером n x n. То есть C = AB.

Самый известный алгоритм для умножения матриц — O(n².3728596). Однако, если проверяющий выберет случайный вектор x, он может проверить Cx = ABx за O(n²). Этот метод называется алгоритмом Фревальда.

Стоит отметить, что хотя проверяющий может выбрать x так, чтобы Cx = ABx, когда C не является произведением AB, это очень маловероятно, поскольку x выбирается случайно.

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

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

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

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

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

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

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

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

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

Space and Time работает над тем, чтобы SQL-запросы передавались на аутсорсинг проверяющей стороне и проверялись Верификатором.

Оригинал: https://www.spaceandtime.io/blog/verifiable-computing-and-commitments

Website | Twitter | Linkedin | Discord | Telegram | Youtube | Instagram | Reddit | CrunchBase

Space and Time работает над тем, чтобы SQL-запросы передавались на аутсорсинг проверяющей стороне и подтверждались Верификатором.

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

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

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

Сторона, выполняющая вычисления, передается субъекту, известному как Проверяющий; Проверяющий доказывает, что заявленный результат верен. Верификатор — это сторона, которая подтвердит утверждение Проверяющего. Неофициально Проверяющего и Верификатора зовут Пегги и Виктор соответственно.

С точки зрения классической теории сложности, недетерминированные проблемы полиномиального времени (NP), по-видимому, удовлетворяют этой цели. Неформально говоря, проблемы NP — это проблемы, которые трудно решить, но легко проверить. Учитывая многочлен, может быть трудно найти нули этого многочлена; это очевидно из разнообразия методов, изучаемых на курсах математики. Однако для проверки утверждения о том, что x = 5 является нулем многочлена, достаточно просто оценить многочлен при x = 5.

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

Классический пример верифицируемых вычислений включает умножение матриц. В частности, доказывающий утверждает, что C является результатом умножения матриц A и B; для простоты мы предполагаем, что A и B — матрицы размером n x n. То есть C = AB.

Самый известный алгоритм для умножения матриц — O(n².3728596). Однако, если проверяющий выберет случайный вектор x, он может проверить Cx = ABx за O(n²). Этот метод называется алгоритмом Фревальда.

Стоит отметить, что хотя проверяющий может выбрать x так, чтобы Cx = ABx, когда C не является произведением AB, это очень маловероятно, поскольку x выбирается случайно.

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

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

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

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

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

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

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

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

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

Space and Time работает над тем, чтобы SQL-запросы передавались на аутсорсинг проверяющей стороне и проверялись Верификатором.

Оригинал: https://www.spaceandtime.io/blog/verifiable-computing-and-commitments

Website | Twitter | Linkedin | Discord | Telegram | Youtube | Instagram | Reddit | CrunchBase