Tác giả: RareSkills
"Lời hứa Pedersen" cho phép chúng ta biểu diễn một vectơ lớn tùy ý bằng cách sử dụng một điểm đường cong elip, đồng thời có thể tùy ý ẩn bất kỳ thông tin nào về vectơ này. Nó cung cấp cho chúng ta một linh kiện quan trọng cho phép chúng ta chứng minh vectơ được mã hóa bởi điểm này mà không để lộ chính vectơ đó.
động lực
Khi thảo luận về kỹ thuật Bằng chứng không tri thức của Bulletproot, mọi người thường nói: "Chúng ta có hai vectơ và tích bên trong của chúng là c." Điều này có vẻ tầm thường, nhưng trên thực tế, bạn có thể sử dụng cơ chế này để chứng minh một khẳng định rất phức tạp. Chúng tôi sẽ mở rộng về điều này sau.
Nhưng để hệ thống chứng minh như vậy hoạt động, những vectơ này không thể chỉ có người chứng minh biết - nếu không người chứng minh có thể thay đổi chúng tùy ý. Chúng phải là các thực thể toán học trong thế giới thực. Nói chung, người chứng minh chắc chắn không muốn giao trực tiếp hai vectơ này cho người xác minh, nhưng nó vẫn cần "chuyển một cái gì đó" cho người xác minh, cho biết rằng nó đã chọn một cặp vectơ và không thể thay đổi chúng nữa.
Đây là lúc chúng ta cần sự cam kết của Pedersen.
kiến thức tiên quyết
Chúng tôi giả định rằng người đọc đã quen thuộc với phép cộng và nhân điểm trên đường cong elip cũng như "một điểm trên đường cong" nghĩa là gì. Nếu bạn vẫn chưa hiểu, vui lòng tham khảo bốn chương đầu tiên trong “ Sách về Bằng chứng không tri thức ” của chúng tôi.
Về ký hiệu, chúng tôi sử dụng [A] để biểu thị điểm của đường cong elip (EC), a để biểu thị một phần tử trong trường hữu hạn và a[A] để biểu thị phép nhân điểm của phần tử trường hữu hạn a này và điểm trên đường cong elip [A] . Và biểu thức [A] + [B] biểu thị phép cộng điểm của hai điểm này.
chương trình cam kết truyền thống
Khi thiết kế chức năng tiết lộ cam kết trong hợp đồng thông minh, chúng tôi thường sử dụng hình thức này:
commit = hash(value, salt)" Trong đó" là một giá trị ngẫu nhiên được sử dụng để ngăn chặn những kẻ tấn công đoán tìm kiếm bằng vũ lực. Ví dụ: nếu chúng tôi cam kết bỏ phiếu, vì các tùy chọn bỏ phiếu bị giới hạn, thì phiếu bầu của chúng tôi dành cho ai có thể được phát hiện bằng cách thử tất cả các tùy chọn và kiểm tra giá trị băm phù hợp. (Với việc bổ sung muối, việc tìm kiếm vũ phu như vậy sẽ không hiệu quả.)
Việc sử dụng muối trong tình huống này có một thuật ngữ học thuật gọi là "yếu tố gây mù ". Vì là ngẫu nhiên nên kẻ tấn công bị mù và không thể đoán được giá trị đã hứa (“giá trị” trong công thức trên) là gì.
Bởi vì kẻ tấn công không thể đoán được giá trị đằng sau nó thông qua "lời hứa", chúng ta nói rằng kế hoạch cam kết này có tác dụng che giấu .
Trong giai đoạn tiết lộ giá trị, người hứa tiết lộ giá trị và muối (trong tài liệu, chúng được gọi là " lời mở ") và bên kia (hoặc hợp đồng thông minh) có thể xác minh rằng chúng phù hợp với cam kết ban đầu. Nếu không thể đạt được cùng một lời hứa với một cặp khác (value, salt) trong cùng một sơ đồ lời hứa, chúng tôi nói rằng sơ đồ này có hiệu lực ràng buộc - một khi người hứa tiết lộ lời hứa, thì không thể thay đổi giá trị đã hứa. Tức là cả hai đều bị ràng buộc).
Tóm tắt thuật ngữ
- Một kế hoạch cam kết có hiệu ứng ẩn không cho phép đối thủ biết giá trị mà người cam kết đã chọn. Điều này thường được thực hiện bằng cách thêm một số ngẫu nhiên mà kẻ tấn công không thể đoán được.
- Yếu tố gây mù là một con số ngẫu nhiên khiến cho giá trị đã hứa không thể đạt được thông qua tìm kiếm vũ phu. Trong một số trường hợp mà chúng tôi không quan tâm đến kiến thức bằng không (mà chỉ quan tâm đến sự đơn giản), yếu tố gây mù có thể không được sử dụng.
- Cơ hội là tính toán giá trị của lời hứa (giá trị đã hứa và muối).
- Các chương trình cam kết có hiệu lực ràng buộc không cho phép người hứa tính toán cùng một lời hứa bằng các cơ hội khác nhau. Nghĩa là, họ sẽ không thể tìm thấy hai cặp
(value, salt)tính toán cùng một lời hứa (hàm băm trong trường hợp này).
Cam kết của người đi bộ
Mô hình sơ đồ cam kết của Pedersen không khác, ngoại trừ việc nó sử dụng nhóm đường cong elip thay vì hàm băm mật mã.
Theo giả định rằng "logarit rời rạc trên các đường cong elip là không thể giải được", với các điểm trên đường cong elip [U] và [G] , chúng ta không thể tính u để có thể làm cho [U] = u[G] .
Xét về mã ngôn ngữ Python, đó là:
from py_ecc.bn128 import G1, multiplyu = 569723450 # chosen randomlyU = multiply(G1, u)print(U, "cannot compute the discrete log of U") Ta nói u là logarit rời rạc của [U] . Ngay cả khi không thể tính được u , chúng ta vẫn gọi nó là logarit rời rạc của [U] vì chúng ta biết nó tồn tại. Tất cả các điểm trên đường cong elip (mật mã) đều có logarit rời rạc, ngay cả khi chúng ta không thể tính được nó.
Theo nghĩa này, phép nhân điểm trên đường cong elip giống như hàm băm. Chúng có tác dụng ràng buộc, miễn là chúng ta chỉ cho phép các cơ hội theo thứ tự đường cong.
Tuy nhiên, mặc dù nó có tác dụng ràng buộc, nhưng chúng ta không thể thu được logarit rời rạc của nó thông qua phép đảo ngược điểm. Nếu phạm vi giá trị của u rất nhỏ, chúng ta sẽ gặp phải vấn đề tương tự (như trong trường hợp biểu quyết ở trên). Kẻ thù có thể đoán x của chúng ta bằng cách lặp qua tất cả x có thể và tính x[G] .
Chúng ta có thể đạt được "che giấu kiểu Pedersen" theo cách sau:
commitment = v[G] + s[Q] Ở đây v là giá trị mà chúng ta muốn cam kết, và s là muối (hệ số mù); Q là một điểm khác trên đường cong elip mà người hứa không biết logarit rời rạc.
Chúng tôi muốn nhấn mạnh rằng mặc dù logarit rời rạc của chúng chưa được biết nhưng cả [G] và [Q] đều được công khai và được cả người xác minh và người ủy quyền biết đến.
Tại sao người hứa không thể biết logarit rời rạc của [Q]
Giả sử rằng người hứa biết logarit rời rạc đằng sau [Q] [Q] = d[G] . Điều này cho phép người hứa xác định hai cơ hội có cùng một lời hứa. Nguyên tắc như sau.
[C] = v[G] + s[Q] = 10[G] + 15[Q] = 10[G] + 15[dG] [C′] = 11[G] + (15d−1)[G] [C] = [C′] Bạn đọc có thể thay thế thủ công bất kỳ số nào cho d để xem nó hoạt động như thế nào.
Những người hứa hẹn không thể biết mối quan hệ logarit rời rạc của các điểm trên đường cong elip mà họ sử dụng.
Một cách để đảm bảo điều này là yêu cầu người xác minh cung cấp cho người xác nhận điểm đường cong elip này. Tuy nhiên, cách tiếp cận đơn giản hơn là chọn ngẫu nhiên và minh bạch một điểm trên đường cong elip, ví dụ, chọn giả ngẫu nhiên một điểm trên đường cong elip. Cho một điểm đường cong elip ngẫu nhiên, chúng ta không biết logarit rời rạc của nó.
Ví dụ: chúng ta có thể bắt đầu với một trình tạo ( [G] ), băm tọa độ x và tọa độ y của nó, sau đó cung cấp cho nó một hàm giả ngẫu nhiên nhưng xác định để tìm điểm tiếp theo.
Việc sử dụng cam kết Pedersen là gì?
Có vẻ như cam kết của Pedersen chỉ là một kế hoạch cam kết thông thường sử dụng một hàm băm khác, nó hữu ích ở đâu?
Chương trình này có nhiều lợi ích.
Có thể thêm đồng hình
Với một trình tạo [G] , chúng ta có thể thêm hai cam kết lại với nhau: a[G] + b[G] = (a + b)[G] . Ngay cả khi chúng tôi thêm quyền riêng tư mù ngẫu nhiên, chúng tôi vẫn có thể tạo ra các cơ hội hiệu quả:
$$
C_1 = a[G] + s_1[Q] \
C_2 = b[G] + s_2[Q] \
C_3 = C_1 + C_2 \
Cam kết được tiết lộ\
(a,b,s_1 + s_2) \
Kiểm tra trình xác thực\
C_3 ?= a[G] + b[G] + (s_1 + s_2)[Q]
$$
Các hàm băm mật mã thông thường (chẳng hạn như SHA256) không thể thực hiện được điều này.
(Trong Lời hứa của Pedersen) b[G] và s[Q] sẽ không "xung đột" với nhau khi được thêm vào.
Bạn có thấy đẳng thức sau đây đúng không?
(a[G]+b[H]) + (c[G]+d[H]) = (a+c)[G] + (c+d)[H] ( [G] và [H] đây là hai điểm đường cong elip có logarit rời rạc chưa biết).
Bạn có thể coi các điểm trên đường cong elip là cơ sở của sự kết hợp tuyến tính theo các chiều trực giao.
Khi có các phần tử trường hữu hạn $a_1, a_2, b_1, b_2$ và các điểm đường cong elip [G] và [H] , và [G] không bằng [H] , $a_1 \ne a_2$, $b_1 \ ne b_2$ , ngay cả khi $a_1[G] + b_1[H] = a_2[G] + b_2[H]$ thì vẫn không thể giải được $(a_1, a_2, b_1, b_2)$ bằng cách bỏ qua logarit rời rạc vấn đề.
Hơn nữa, khi thứ tự của nhóm đường cong elip của chúng ta đủ lớn thì khả năng tìm được sự trùng khớp như vậy nhờ may mắn càng khó xảy ra hơn.
Nói cách khác, giả sử hai người tính toán các cam kết tương ứng của họ [C] = a[G] + b[H] và [C'] = a'[G] + b'[H] và $a $ và $b Chừng nào chưa biết logarit rời rạc của [G] và [H] thì không chắc [C] bằng [C'] .
Pedersen hứa hẹn sẽ thân thiện với zk
Tạo ra các mạch để cộng và nhân trên các đường cong elip tương đối dễ dàng vì yêu cầu duy nhất là các phép toán số học thông thường; nhưng các hàm băm thông thường sử dụng phép dịch bit và phép toán OR loại trừ (XOR), đòi hỏi các ràng buộc mạnh .
Chúng ta có thể mã hóa bất kỳ số điểm nào thành một điểm
Ví dụ của chúng tôi sử dụng [G] và [Q] cũng có thể cho rằng là cam kết vectơ 2 chiều không có yếu tố gây mù. Nhưng chúng ta cũng có thể thêm bao nhiêu điểm trên đường cong elip $[G_1, G_2,…, G_n]$ tùy thích, cam kết với bất kỳ số lượng vô hướng nào.
Lời hứa vector Pedersen
Chúng tôi tiến thêm một bước nữa cho kế hoạch trên và cam kết thực hiện một tập hợp các giá trị, thay vì một giá trị và một đồng đô la mù quáng.
kế hoạch cam kết vector
Giả sử chúng ta có một tập hợp ngẫu nhiên các điểm trên đường cong elip ($[G_1, G_2,…, G_n]$) (chúng tôi chưa biết logarit rời rạc của chúng), thì chúng ta có thể làm điều này:
$$\underbrace{[C] = v_1[G_1] + v_2[G_2] + … + v_n[G_n]} {Giá trị cam kết} + \underbrace{r[Q]} {Hệ số mù}$$
Điều này cho phép chúng ta hứa hẹn nhiều giá trị với lời hứa [C] và ẩn chúng bằng r .
Vì những người cam kết không biết logarit rời rạc đằng sau bất kỳ trình tạo nào, nên họ sẽ không biết logarit rời rạc của [C] . Do đó, sơ đồ này có tác dụng ràng buộc: chúng chỉ có thể tạo ra Promise [C] với $[v_1, v_2,…, v_n]$, không thể tạo ra một tập vectơ khác.
Lời hứa vector có thể được tổng hợp
Chúng ta có thể thêm hai hứa hẹn vectơ Pedersen để nhận được lời hứa cho cả hai vectơ. Người hứa hẹn vẫn có thể sử dụng vectơ ban đầu để tiết lộ. Một chi tiết triển khai quan trọng ở đây là hai cam kết vectơ ban đầu phải được tạo bằng cách sử dụng hai tập hợp điểm đường cong elip khác nhau.
$$
[C_1] = v_1[G_1] + v_2[G_2] + … + v_n[G_n] + r[Q] \
[C_2] = w_1[H_1] + w_2[H_2] + … + w_n[H_n] + s[Q] \
[C_3] = [C_1] + [C_2]
$$
Ở đây, r[Q] và s[Q] là những yếu tố gây mù. Những người hứa hẹn ngay lập tức không có vectơ cam kết và toàn bộ lời hứa vẫn giống như một điểm ngẫu nhiên.
Người cam kết sau đó có thể tiết lộ các vectơ ban đầu $[v_1, v_2,…, v_n]$ và $[w_1, w_2,…, w_n]$, cũng như yếu tố gây mù r + s . Điều này cũng có tác dụng ràng buộc và không thể tạo ra lời hứa tương tự với một tập hợp vectơ và yếu tố gây mù khác.
Chúng tôi sử dụng $[G_1, G_2,…, G_n]$ cho một bộ vectơ và $[H_1, H_2,…, H_n]$ cho một bộ khác. Điều này không có nghĩa là các bộ tạo [G_i] và bộ tạo [H_i] này là nhau. nội bộ Mối quan hệ đặc biệt là gì? Tất cả những điểm này cần phải được chọn giả ngẫu nhiên. Chúng chỉ là sự trùng hợp ngẫu nhiên về mặt ký hiệu, cho phép chúng ta nói trực tiếp "các vectơ điểm đường cong elip này khớp với tập hợp các vectơ phần tử trường hữu hạn này và các vectơ điểm đường cong elip đó khớp với các vectơ phần tử trường hữu hạn đó."
Không có giới hạn trên nội tại nào về số lượng vectơ mà chúng tôi có thể cam kết.
Kiểm tra người đọc : Nếu chúng ta sử dụng cùng một bộ tạo $[G_1, G_2,..., G_n]$ cho hai cam kết, sau đó cộng chúng lại với nhau, làm thế nào người hứa tiết lộ hai bộ vectơ khác nhau cho $[C_3]$? Ví dụ: liệu điều này có thể tránh được bằng cách sử dụng một tập hợp các điểm đường cong elip khác $[H_1, H_2,…, H_n]$ không?
Đố người đọc : Điều gì sẽ xảy ra nếu người hứa đảo ngược vị trí của giá trị đã hứa khi nó được tiết lộ?
Ví dụ: anh ấy đã hứa:
$$[C_1] = v_1[G_1] + v_2[G_2] + … + v_n[G_n] + r[Q]$$
Tuy nhiên, cơ hội để tiết lộ là:
$$[v_2, v_1, v_3, v4,…,v_n]$$
Nói cách khác, người hứa hoán đổi vị trí của hai phần tử đầu tiên nhưng giữ nguyên mọi thứ khác. Giả sử các vectơ $[G_1, G_2,…, G_n]$ không giao hoán.
Tạo điểm ngẫu nhiên một cách minh bạch
Làm thế nào chúng ta có thể tạo ra các điểm đường cong elip ngẫu nhiên này? Một giải pháp rõ ràng là sử dụng cài đặt khởi động đáng tin cậy, nhưng điều này không cần thiết. Người cam kết có thể chọn ngẫu nhiên một cách minh bạch một số điểm có logarit rời rạc mà chúng ta không biết.
Trước tiên, họ có thể chọn trình tạo [G] , trộn nó với một số ngẫu nhiên được chọn công khai, sau đó băm kết quả (yêu cầu modulo field_modulus) để thu được một giá trị khác. Nếu kết quả là giá trị x rơi trên đường cong elip thì hãy sử dụng nó làm trình tạo tiếp theo và băm lại giá trị tọa độ (x, y) của nó. Ngược lại, nếu nó không có điểm tương ứng trên đường cong elip là giá trị x thì chúng ta tăng giá trị x cho đến khi nó có điểm đường cong elip tương ứng. Bởi vì những người đề xuất không tạo ra những điểm này nên họ không thể biết logarit rời rạc của những điểm này. Chi tiết triển khai của thuật toán này được để lại dưới dạng bài tập cho người đọc.
Trong mọi trường hợp, chúng ta không nên tạo một điểm bằng phép nhân vì điều này sẽ dẫn đến việc chúng ta biết logarit rời rạc của nó. Bạn cần lấy giá trị x giả ngẫu nhiên thông qua hàm băm và xem liệu nó có nằm trên đường cong elip hay không.
Cũng có thể bắt đầu từ bộ tạo [G] (có logarit rời rạc được biết là 1) và sau đó tạo các điểm khác.
Một bài tập dành cho người đọc : Giả sử chúng ta thực hiện một vectơ 2 chiều với các điểm [G1] và [G2] . Logarit rời rạc của [G1] đã biết nhưng logarit rời rạc của [G2] thì chưa biết. (Hiện tại chúng tôi bỏ qua yếu tố gây mù). Người hứa có thể sử dụng một vectơ 2 chiều khác để tiết lộ lời hứa không? Tại sao?
(qua)
