Điểm:2

zkSnark: Hạn chế đa thức

lá cờ et

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

Tôi đã hiểu mọi thứ trong 15 trang đầu tiên.

Trong 3.4 Giới hạn một đa thức (Trang 16)

Chúng tôi đã hạn chế một trình chứng minh trong việc lựa chọn các quyền hạn được mã hóa của s, nhưng hạn chế đó không được thực thi, ví dụ: người ta có thể sử dụng bất kỳ phương tiện có thể để tìm một số giá trị tùy ý $z_p$$z_h$ thỏa mãn phương trình $z_p = (z_h)^{t(s)}$ và cung cấp chúng cho người xác minh thay vì $g^p$$g^h$. Ví dụ, đối với một số r ngẫu nhiên $z_h = g^r$$z_p = (g^{t(s)})^{r}$, ở đâu $g^{t(s)}$ có thể được tính toán từ quyền hạn được mã hóa được cung cấp của $s$. Đó là lý do tại sao người xác minh cần bằng chứng chỉ cung cấp mã hóa quyền hạn của $s$ đã được sử dụng để tính toán $g^p$$g^h$ và không có gì khác.

Tôi không thể hiểu làm thế nào một người tục ngữ có thể tìm thấy một số giá trị tùy ý của $z_p$$z_h$ thỏa mãn $z_p = (z_h)^{t(s)}$? Ví dụ, đối với một số r ngẫu nhiên $z_h = g^r$$z_p = (g^{t(s)})^{r}$

Người tục ngữ không biết $s$ & anh ấy cũng không biết $g$, vậy anh ấy sẽ làm điều này như thế nào?

Nói tóm lại, tôi không thể tìm ra cuộc tấn công (để bảo vệ chống lại) để "hạn chế đa thức" là gì.

Điểm:3
lá cờ ru

Mỗi trang 15 của bài báo, người tục ngữ được cung cấp $E(s^0)=E(1)=g$ (Tôi sẽ gọi đây là $E_0$). Tương tự như vậy, họ được cung cấp $$E_1:=E(s), E_1:=E(s^2),\cdots, E_d:=E(s^d).$$ Để cho $t(s)=\sum_{0\le i\le d}c_is^i$ (với $c_i$ được biết đến với câu tục ngữ) sau đó $g^{t(s)}=E(t(s))=\prod_{0\le i\le d}E_i^{c_i}$.

Vì vậy, người tục ngữ biết cả hai $g$$g^{t(s)}$ và như trong bài báo, họ có thể chọn ngẫu nhiên $r$ để xây dựng $z_h$$z_p$ bằng cách nâng các giá trị này lên lũy thừa $r$.

Điểm của cuộc tấn công là các phép tính trên không yêu cầu kiến ​​thức về $p(x)$ đó là những gì tục ngữ được cho là đang chứng minh kiến ​​​​thức về. Người xác minh đủ ngu ngốc để tin rằng giá trị ngẫu nhiên $z_h$ không bằng $g^{h(s)}$ và đó $z_p$ không bằng $g^{p(s)}$ sẽ không có gì mâu thuẫn với niềm tin của họ.

lá cờ et
Tôi biết tôi đã chấp nhận câu trả lời. Tuy nhiên, tôi đã thử một ví dụ và nó không hoạt động.
lá cờ et
E(c) = g^c mod 23. Trình xác minh lấy mẫu tại s = 14 & cung cấp $E(s^0) = 5$, $E(s^1) = 13$, $E(s^2) = 12 $, $E(s^3) = 3$ 2 nghiệm đã biết là 3 & 4 tức là $t(s) = (x-3)(x-4)$. Nhà cung cấp chọn ngẫu nhiên r = 6. t(6) = 3 * 2 = 6. Nhà cung cấp tính toán $z_h = 5^6 \pmod {23} = 8$ & $z_p = (5^6)^6 \pmod {23 } = 13$ Gửi $z_p$ và $z_h$ cho người xác minh Người xác minh tính toán t(14) = 11 * 10 = 110. Người xác minh tính toán $E(h)^t = 8^{110} \pmod {23} = 1$. Vậy $E(p) \ne E(h)^t$ Tôi đang làm gì sai? Tôi đã hiểu nhầm câu trả lời của bạn?
Daniel S avatar
lá cờ ru
Câu tục ngữ không tính toán $t(r)$ rồi $g^{t(r)}$. Thay vào đó, họ tính toán $g^{t(s)}=g^{s^2â7s+12}=12Ã13^{â7}Ã5^{12}$ và nâng giá trị này lên thành sức mạnh $r$. Kích hoạt sagemath, chúng tôi thấy rằng $g^{t(s)}\equiv 1\pmod{23}$, vì vậy bộ tục ngữ đặt $z_p=1^r\equiv 1\pmod{23}$ và $z_h=8$ . Sau đó, họ tính toán $z_h^{110}=8^{110}\equiv 1\pmod{23}$ có cùng giá trị.
lá cờ et
Ok, kiểm tra ra!!
lá cờ et
Tôi đã tìm thấy một vấn đề khác với giao thức được mô tả trong 3.3 Đặt căn bậc 3 thực sự bằng 0, tức là đa thức thực sự là (x)(x-3)(x-4). Ngay cả khi người tục ngữ không biết đa thức thực & căn thực & anh ta cho rằng căn bậc 3 thay vì 2 thay vì 0 & rằng đa thức là (x-2)(x-3)(x-4) & làm tất cả các bước - các bước vẫn kiểm tra và người xác minh sẽ không biết rằng người xác minh không biết đa thức đúng. Tôi tự hỏi liệu đây có phải là một lỗi riêng biệt với giao thức được giải thích trong 3.3 hay nó là một biến thể của giao thức được đề cập trong 3.4. Tôi nghĩ đó là một lỗi khác
Daniel S avatar
lá cờ ru
Có, vấn đề là giá trị mẫu được chọn, $s=14$ là gốc của $t(x)$ modulo 22 là thứ tự của nhóm mod 23. Điều này dẫn đến $z_p=1$ gây ra sự suy biến như bạn đã tìm thấy. Người xác minh nên kiểm tra trước khi gửi $t(s)\not\equiv 1\pmod{q}$ đó cho số nguyên tố lớn $q$ chia $p-1$. Điều này rất có thể xảy ra nếu chúng ta sử dụng một số nguyên tố lớn, mạnh.
lá cờ et
Có phải bạn đang nói cả hai vấn đề (một vấn đề được mô tả trong 3.4 & vấn đề tôi đã chỉ ra trong nhận xét cuối cùng của mình) là do $s=14$ là gốc của $t(x) \pmod {22}$ hay chỉ là một trong số đó vì điều này?
lá cờ et
Vì vậy, tôi đã thử cả hai vấn đề với s = 16 không phải là root . Và cả hai vấn đề vẫn còn. Vì vậy, việc có s làm gốc của t(s) mod (p-1) khiến E(p) luôn là 1, nhưng nếu không thì làm thế nào nó gây ra bất kỳ vấn đề nào với giao thức?
Daniel S avatar
lá cờ ru
Tôi không gặp vấn đề gì với $s=16$. Đối với đa thức $t(x)=x(x-3)(x-4)$, $t(s)=2496$. Đối với đa thức $(x-2)(x-3)(x-4)=x^3-9x^2+26x-24$ người chứng minh sẽ tính $E(s^3)E(s^2)^ {-9}E(s)^{26}E(1)^{-24}=8$. Chọn ngẫu nhiên $r=6$ chứng minh gửi $z_h=8$ và $z_p=13$. Sau đó, Trình xác minh có $z_h^{2496}=3$ không giống với $z_p$.
lá cờ et
p(x) = x(x-3)(x-4), t(x) = (x-3)(x-4) - vậy t(16) = 156 chứ không phải 2496. $13^{156} \ pmod {23} \equiv 8$ - do đó khớp

Đă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.