Рейтинг:1

zkSNARKS: Что мешает доказывающему выбрать полином, отличный от того, который он должен знать?

флаг et

Я читаю это объяснение zkSnark, написанное Максимом Петкусом - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Здесь доказывающий знает многочлен степени 3, 2 решения многочлена равны 3 и 4. Он должен доказать проверяющему, что он знает такой многочлен, не раскрывая проверяющему третье решение.

Это полином, который они используют в качестве примера - $P(x) = x^3 - 7x^2 + 12x$ Это можно рассматривать как $х(х-3)(х-4)$, поэтому 3-е решение $х = 0$

$Т(х) = (х-3)(х-4)$

$Н(х) = х$ (это знает только доказывающий)

$P(x) = H(x) . Т(х)$

$E(c) = g^c \pmod p$.

Короче говоря, это протокол, используемый

  1. Верификатор выбирает случайный $s$, вычисляет $E(s^0), E(s^1), E(s^2), E(s^3)$ Отправляет эти 4 значения пруверу, не раскрывая s.

  2. Доказательство вычисляет $ Е (р (с)) $ используя различные $E(s^n)$с. Он также вычисляет $ Е (Н (с)) $ так же не зная $s$. Он передает оба проверяющему

  3. Верификатор вычисляет $Т(с)$ а затем повышает $E(H(s))^ {T(s)}$. Если $E(P(s))$ посланный прувером совпадает с $E(H(s))^ {T(s)}$, то протокол проходит успешную проверку.

Я понял протокол в целом. Есть проблемы с этим, которые они решают позже, но одна проблема, которая приходит мне на ум (которую они не решают), заключается в следующем.

Если доказывающая сторона не знает фактического многочлена (т. $х^3 - 7х^2 + 12х$), но просто выбирает случайное третье решение, т.е. $х = 2$ И он продолжает выполнять описанные выше шаги протокола, как описано, он все равно будет проверять с помощью верификатора.

В таком случае я не могу понять, чего именно пытается достичь протокол?

Рейтинг:1
флаг gb

Я не могу найти этот конкретный пример $x^3 – 7x^2 + 12x$ в связанном документе. Но я думаю, что вы несколько ответили на свой вопрос здесь:

Здесь доказывающий знает многочлен степени 3, 2 решения многочлена равны 3 и 4. Он должен доказать проверяющему, что он знает такой многочлен, не раскрывая проверяющему третье решение.

Это именно то, что он пытается доказать здесь - что он знает многочлен степени 3, который имеет решения 3 и 4. Доказательство знания такого многочлена не относится к одному единственному многочлену - таких многочленов степени 3 с корнями несколько. 3 и 4. Все доказательство доказывает знание один из них.

Если доказывающая сторона не знает фактического многочлена (т. $x^3 – 7x^2 + 12x$), но просто выбирает какое-то случайное третье решение, т.е. $х = 2$ И он продолжает выполнять описанные выше шаги протокола, как описано, он все равно будет проверять с помощью верификатора.

Это связано с тем, что знание полинома такое же, как знание его корней - единственный полином степени 3 с корнями 3, 4 и 2 - это $(х-2)(х-3)(х-4)$. Таким образом, доказывающий все еще доказывает, что он знает многочлен степени 3 с корнями 3 и 4, даже если это не так. $x^3 – 7x^2 + 12x$. В этом случае они «знают» многочлен $(х-2)(х-3)(х-4)$ вместо.

Следует подчеркнуть, что этот документ постепенно расширяется до более интересных приложений. Этот протокол доказательства знания полинома — всего лишь строительный блок, и сам по себе он может показаться немного бесполезным. Но позже в документе объясняется, как можно использовать это «Знание полинома», например, в разделе 4.4 и далее. Обычно это происходит потому, что нас на самом деле заботит только то, что многочлен имеет определенный набор корней (что соответствует определенным условиям, в которых доказывается вещь при нулевом знании).

флаг et
Спасибо. Я вернусь к этому после того, как закончу раздел 4.

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

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