Điểm:1

zkSnarks: Đảm bảo rằng một biến có một giá trị duy nhất trong tất cả các hoạt động mà nó được sử dụng trong

lá cờ et

Tôi đang đọc phần giải thích về zkSnarks được viết bởi Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Trong phần 4.5, pdf giải thích cách biểu diễn các thao tác sau

$a$ x $b = r1$
$r1$ x $c = r2$

như $l(x)r(x) - o(x)$ ở đâu $l(x)$ là đa thức toán hạng bên trái, $r(x)$ là đa thức toán hạng bên phải & $o(x)$ là đa thức đầu ra.

Ở đây nếu bạn thấy điều đó $a$ chỉ được sử dụng một lần trong LHS của tập hoạt động đầu tiên - nó chỉ được sử dụng trong hoạt động đầu tiên (tức là $a$ x $b = r1$) - nó không có trong phần 2.

Trong 4.6, anh ấy chuyển sang cách thực hiện điều tương tự khi $a$ lặp đi lặp lại. I E.

$a$ x $b = r1$
$a$ x $c = r2$

Đây $a$ có mặt trong cả hai hoạt động

Vì vậy, anh ấy nói

Tuy nhiên, vì giao thức của chúng tôi cho phép người chứng minh đặt bất kỳ hệ số nào thành đa thức, anh ta không bị hạn chế đặt các giá trị khác nhau của $a$ cho các hoạt động khác nhau (nghĩa là được biểu thị bằng một số x)

Quyền tự do này phá vỡ tính nhất quán và cho phép người xác minh chứng minh việc thực thi một số chương trình khác không phải là điều người xác minh quan tâm. Do đó, chúng tôi phải đảm bảo rằng bất kỳ biến nào chỉ có thể có một giá trị duy nhất trong mọi hoạt động mà nó được sử dụng trong

Tiến xa hơn trong 4.6.1, anh ấy nói

Do đó, nếu người xác minh cần bắt buộc người xác minh đặt cùng một giá trị trong tất cả các hoạt động, thì người đó chỉ có thể sửa đổi tỷ lệ chứ không phải các hệ số riêng lẻ.

Tôi không thể hiểu điều này - các hệ số của $l(x)$ đến từ tất cả các hoạt động (bạn tìm thấy $l(x)$ bằng cách sử dụng một cái gì đó như Nội suy đa thức Lagrange trên cả hai hoạt động). Vậy làm thế nào người chứng minh có thể sử dụng các hệ số khác nhau cho các hoạt động khác nhau. Một số có thể giải thích với một ví dụ?

Điểm:1
lá cờ gb

Giả sử bạn muốn sử dụng $a$ trong hai ràng buộc như bạn đã viết. Bạn muốn giả định rằng $l(x_1) = a$$l(x_2) = a$, ở đâu $x_1$$x_2$ là các chỉ số của hai ràng buộc. Nhưng mà $l(x)$ được tạo ra bởi câu tục ngữ, và họ chắc chắn có thể đã chọn một $l(x)$ đánh giá thành hai khác biệt giá trị tại $x_1$$x_2$. Sau đó, về cơ bản bạn có hai biến độc lập thay vì sử dụng $a$ hai lần. Điều này được hiển thị ở đầu trang 36 trong PDF được liên kết.

Cho đến thời điểm đó, mọi ràng buộc đều được xác minh độc lập. Bằng cách này, tôi có nghĩa là $l(x_i)*r(x_i) - o(x_i) = 0$ tại mỗi chỉ số $x_i$, được kiểm tra bằng cách đảm bảo $(x-x_i)$ là nghiệm của đa thức. Bây giờ, chúng ta cần một cách để xác minh sự bằng nhau của các biến giữa hai ràng buộc khác nhau.Nói cách khác, bằng cách nào đó thiết lập những thứ như $l(x_1) = l(x_2)$ giữa các chỉ số khác nhau.

Cách này được thực hiện bằng cách hạn chế hơn nữa cách người tục ngữ có thể xây dựng các đa thức (ví dụ: $l(x)$), vì vậy họ không thể nội suy bất kỳ giá trị nào họ thích. Một cách để làm điều này là đưa ra các đa thức khác nhau cho câu tục ngữ $l_a(x)$ đánh giá thành 1 bất cứ khi nào $a$ được sử dụng và 0 ở mọi nơi khác. Ví dụ, một đa thức trong đó $l_a(x_1) = l_a(x_2) = 1$, và bằng 0 ở mọi nơi khác. Sau đó, họ có thể chỉ cần nhân số này với $a$ để thiết lập cùng một giá trị của $a$ trong tất cả các vị trí nó được sử dụng. Để buộc người tục ngữ sử dụng điều này, chúng tôi lại mã hóa nó và cung cấp $\alpha$ phiên bản chuyển đổi: $$g^{l_a(x)}, g^{\alpha l_a(x)}$$ (như đã được thực hiện nhiều lần trước đây). Người tục ngữ sau đó có thể nâng từng người trong số này lên sức mạnh của $a$ để đặt giá trị đó ở mọi nơi.

Nếu chúng ta có một cặp như vậy cho một biến khác $d$: $$g^{l_d(x)}, g^{\alpha l_d(x)}$$ Sau đó, người tục ngữ có thể đặt cả hai $a$$d$ và sau đó nhân các đa thức đã mã hóa với nhau (tương ứng với việc cộng các đa thức ở các số mũ lại với nhau).

Điều tương tự cũng được thực hiện cho $R(x)$$O(x)$.

Còn một nhược điểm nữa, được giải quyết trong phần 4.9.3, cho phép người tục ngữ thêm những thứ bổ sung vào đa thức của chúng bằng cách nhân với một đa thức khác $g^1$$g^{\alpha}$. Điều này được khắc phục bằng cách giới thiệu một sự thay đổi bí mật khác bằng cách $\gamma$.

meshcollider avatar
lá cờ gb
> "đó là trường hợp ngay cả trong trường hợp trước đó. ngay cả trong trường hợp trước đó, người tục ngữ có thể chọn bất cứ điều gì họ muốn" - vâng, và đó là lý do tại sao chúng ta cần dần dần giới hạn những gì người tục ngữ có thể chọn trong suốt PDF, do đó khi chúng tôi hoàn thành, chúng tôi tin chắc rằng họ không thể gian lận.
lá cờ et
Có ví dụ nào về cách người hoạt ngôn có thể khai thác điều gì đó trong trường hợp người hoạt ngôn không bị hạn chế không?
meshcollider avatar
lá cờ gb
Chắc chắn rồi. Giả sử bạn đang cố gắng chứng minh điều gì đó dựa trên một số ràng buộc bao gồm $b = a + 1$ và $c = a - 1$. Nếu không đảm bảo rằng giá trị của $a$ được sử dụng trong cả hai ràng buộc này là như nhau, thì $b$ và $c$ có thể được cung cấp các giá trị tùy ý một cách độc lập và kiểm tra vẫn sẽ vượt qua. Giả sử một câu tục ngữ ác ý sử dụng một giá trị $b = 8$ và $c = 0$. Rõ ràng là không tồn tại một $a$ mà cả hai điều này đều có thể đúng. Nhưng sử dụng $a = 7$ trong ràng buộc đầu tiên và $a = 1$ trong ràng buộc thứ hai, cả hai ràng buộc sẽ xác minh độc lập.
lá cờ et
Khi trình chứng minh độc hại đang hình thành $l(x)$, $o(x)$ & $r(x)$ với các giá trị khác với giá trị thực sự đúng, thì Nội suy Lagrange sẽ hoạt động như thế nào? Câu tục ngữ sẽ không bị vấp vào thời điểm đó sao?
meshcollider avatar
lá cờ gb
Nội suy Lagrange hoạt động cho bất kỳ giá trị nào bạn muốn. Ví dụ: nếu $l(x)$ được cho là bằng $a$ tại $l(x_1)$ và $l(x_2)$, thì không gì có thể ngăn người tục ngữ nội suy $l(x_1) = a$ và $ l(x_2) = b$, nhận được $l(x)$ khác với giá trị bạn sẽ nhận được nếu bạn thành thật đặt cả hai $a$ thành cùng một giá trị. Tất cả những gì bạn đang làm là tìm một đa thức đi qua các điểm $(x_1, a)$, $(x_2, b)$ thay vì $(x_1, a)$, $(x_2, a)$
lá cờ et
Tôi đã tạo một phòng trò chuyện cho việc này - https://chat.stackexchange.com/rooms/134216/temp-zksnark - Tôi đã đặt câu hỏi của mình ở đó - bạn có thể xem qua không

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.