Регистрация Войти
Рейтинг:1
Max avatar Crypto

Основы ZK-SNARK: зная t(x), что мешает доказывающему создать случайный h(x) для подделки L, R и O

флаг fr
Max

После прочтения ряда пояснений ZK-SNARK от здесь, здесь, и здесь, я до сих пор не понимаю несколько вещей.

В настройке алгоритма используется QAP для вычисления многочлена P(x) = L(x) * R(x) - O(x), а также многочлен целевого делителя t(x) для представления общей формы целевого вычисления. . Затем, чтобы создать доказательство, доказывающее

  • Вычисляет P(x) = L(x) * R(x) - O(x) для конкретных параметров целевого вычисления.
  • Вычисляет h(x) = P(x) / t(x).
  • Вычисляет h(s), L(s), R(s) и O(s) для отправки верификатору. Затем верификатор использует эти значения, чтобы проверить, является ли h(s) * t(s) = L(s) * R(s) - O(s) или что t делит P без остатка.

Если доказывающему известно t(x), что мешает ему выбрать случайное h(x), вычислить h(x) * t(x) и подделать L(x), R(x) и O(x) с правильный порядок? Он пройдет проверку верификатора «без остатка». Это все равно будет полином (линейная комбинация E(s^d)), поэтому он также должен удовлетворять проверкам сдвига.

Что мне не хватает?

54
1 + 0
Рейтинг:0
Vadym Fedyukovych avatar Crypto
флаг in
Vadym Fedyukovych

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

Пожалуйста, помните (1) «эффективная» (краткая) проверка является целью снарков, и (2) есть секреты (свидетели) «замешанных» многочленов $L(), R(), O(), h()$. Не хватает двух пунктов: (1) полиномы оцениваются в случайной точке $\тау$ скрыты от прувера («токсичные отходы»), и (2) эллиптические кривые и билинейная операция (спаривание).

Полиномы оцениваются в $\тау$ отправляются на проверку, как групповые элементы.Уравнение проверки эквивалентно указанному в вопросе, с точностью до незначительной ошибки достоверности (вероятности), оцениваемой с помощью леммы Шварца-Циппеля.

0 + 3
Max avatar
флаг fr
Max
Извините, это все еще не отвечает на мой вопрос. Предположим, что произошла правильная настройка, полиномы и скрытые целевые точки были разделены, токсичные отходы были удалены и т. д. В обычном процессе проверки прувер сначала вычисляет L, O, R из целевой программы с определенными входными/выходными параметрами, которые он хочет доказать, затем вычисляет h = (L*R-O)/t, оценивает его и отправляет результаты верификатору. Однако что мешает доказывающему сначала выбрать случайный полином h'(), затем вычислить L', R' и O' так, чтобы L'*R'-O'=h'*t, а затем отправить «поддельный» результат оценки в случайной точке?
0
Ответить
Vadym Fedyukovych avatar
флаг in
Vadym Fedyukovych
Нам нужно начать с R1CS, чтобы увидеть, как все переменные/провода смешиваются в полиномы $L(), R(), O()$. Было бы разумно рассматривать проблемы и их арифметизацию R1CS только так, чтобы общедоступные переменные полностью определяли экземпляр. Верификатор вводил свою копию общедоступных переменных/проводов в уравнение проверки. Что касается вашего комментария: доказывающий может выбрать только (L, R, O), которые согласуются с общедоступными переменными. Затем программа проверки не отправляет полином h(), а группирует элементы типа $h(\tau) G_1$. Могу ли я сослаться на теорему 2, стр. 18, препринт IACR 2016/260 для такого общего «что мешает»?
0
Ответить
Max avatar
флаг fr
Max
Спасибо, это полезно!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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