Chào các nhà nghiên cứu ethe! Khi mùa đông đến, tôi quyết định chia sẻ giao thức hấp dẫn này trên diễn đàn. Đầu năm nay, chúng tôi đã viết một bài nghiên cứu về cách triển khai Secret Santa (thực sự) trên Ethereum, bảo vệ quyền riêng tư của người chơi và tính chính xác của trò chơi. Tôi tò mò muốn biết bạn nghĩ gì về giao thức ZKSS!

Đây là liên kết đến bài báo trên arXiv .

Tóm tắt

Bài báo này đề xuất một thuật toán Secret Santa ba bước với thiết lập tận dụng Zero Knowledge Proofs (ZKP) để thiết lập mối quan hệ giữa người gửi và người nhận quà, đồng thời vẫn đảm bảo tính bảo mật của người gửi. Thuật toán duy trì sự xáo trộn hoán vị và không yêu cầu một cơ quan trung ương để thực hiện thành công. Phương pháp được mô tả có thể được triển khai trong Solidity với điều kiện tích hợp với một bộ chuyển tiếp giao dịch.

1. Giới thiệu

Mọi người đều thích chơi Secret Santa khi Giáng sinh đến. Nhưng chơi trò chơi trực tuyến có một số thử thách cần vượt qua.

Thứ nhất, tính mở của blockchain Ethereum không cho phép chúng tôi thực hiện các phép tính riêng tư. Để che giấu danh tính (địa chỉ) của những người tham gia Secret Santa, một bộ chuyển tiếp giao dịch được sử dụng cùng với ZKP.

Thứ hai, vì không có nguồn ngẫu nhiên (thực sự) nào khả dụng trên chuỗi nên việc lựa chọn cặp người gửi/người nhận quà được chuyển giao cho những người tham gia chương trình Ông già Noel bí mật và được xác minh thông qua ZKP, đảm bảo rằng không ai tự mình lựa chọn.

Thứ ba, vấn đề “bỏ phiếu kép” được giải quyết bằng khái niệm “người bỏ phiếu mù”. Giao thức có thể xác minh sự tham gia của người chơi mà không làm mất tính bảo mật.

2. Mô tả giao thức

Giao thức ZK Secret Santa (ZKSS) là quy trình ba bước không tương tác ngang hàng, đòi hỏi sự tham gia của tất cả người tham gia trò chơi.

Về bản chất, thuật toán dựa trên một số nguyên hàm mật mã để đảm bảo tính chính xác khi thực thi và duy trì tính bảo mật của người dùng. Giả sử \mathbb{F}_p F p là một trường hữu hạn trên một số nguyên tố p p và

\mathsf{hash}(m) \;\rightarrow\; h \;\in\; \mathbb{F}_p h a s h ( m ) → giờ ∈ F p

biểu thị một hàm băm mật mã lấy một thông điệp m m tùy ý làm đầu vào và trả về một phần tử trường h h .

Mối quan hệ chứng minh được định nghĩa là

\mathcal{R} = \{(w, x) \in \mathcal{W} \times \mathcal{X} \;:\; \phi_1(w,x), \phi_2(w,x), \dots, \phi_m(w,x)\}, R = { ( w , x ) ∈ W × X : ϕ 1 ( w , x ) , ϕ 2 ( w , x ) , … , ϕ m ( w , x ) } ,

trong đó w w là dữ liệu chứng kiến, x x là dữ liệu công khai và \{\phi_1(w,x), \phi_2(w,x), \dots, \phi_m(w,x)\} { ϕ 1 ( w , x ) , ϕ 2 ( w , x ) , … , ϕ m ( w , x ) } là tập hợp các mối quan hệ phải được chứng minh đồng thời.

Hàm \mathsf{ecrecover} e cr r e c o v e r [1] được sử dụng để khôi phục \mathsf{address} a d r e s s của người dùng dựa trên chữ ký ECDSA \mathsf{sig} s i g và hàm băm có chữ ký h h .

Cuối cùng, hãy xem xét chứng minh Merkle p_i \in \mathbb{F}_p^{(n)} p i ∈ F ( n ) p , là danh sách các giá trị nút dẫn đến giá trị gốc. Chứng minh Merkle cho phần tử x x có thể được xác minh bằng

\mathsf{merkleVerify}(x, p_i, root) \;\rightarrow\; \ mathsf { bool } . m e r k l e Xác minh y ( x , p i , root ) → b o o l .

2.1. Thiết lập

Thiết lập sơ bộ yêu cầu tất cả người tham gia ZKSS phải đăng ký công khai địa chỉ của họ trong một hợp đồng thông minh. Việc thiết lập chỉ được thực hiện một lần, cho phép sử dụng lại bộ người tham gia trong nhiều trò chơi.

Vì quá trình thiết lập là một quá trình mở nên có thể chọn một người tham gia chính để đăng ký tất cả người chơi trong một giao dịch duy nhất một cách an toàn thay mặt họ.

Thuật toán 1: Thiết lập

Đầu vào:

• Công cộng:
  • địa chỉ - người tham gia ZKSS Địa chỉ Ethereum

Quá trình thiết lập:

1. Người tham gia chính gọi hàm đăng ký trên hợp đồng thông minh để cung cấp địa chỉ của tất cả những người tham gia.
2. Hợp đồng lưu trữ các địa chỉ trong Cây Merkle thưa thớt (SMT) của người tham gia theo \mathsf{index} = \mathsf{hash}(\mathsf{address}) i n d e x = h a s h ( a d r e s s ) tương ứng .

SMT [2] của những người tham gia được sử dụng trong toàn bộ ZKSS để xác minh rằng người tham gia thuộc về nhóm người tham gia ban đầu.

2.2. Cam kết chữ ký

Bước đầu tiên, được gọi là cam kết chữ ký , là cần thiết để ràng buộc người tham gia ZKSS sử dụng chữ ký ECDSA được suy ra một cách xác định. Xem phần bảo mật ecdsa-phi-xác định để biết cơ sở lý luận đằng sau bước này.

Thuật toán 2: Cam kết chữ ký

Đầu vào:

• Công cộng:
  • H H – một hàm băm của chữ ký ECDSA của người dùng ( \mathsf{address}\ ||\ \mathsf{eventId } a d r e s s | | e event Id ) , trong đó \mathsf{address} a d r e s s là địa chỉ Ethereum của người dùng, \mathsf{eventId} e event Id là ( \ mathsf {contract\ address}\ ||\ \mathsf{nonce} c o n t r a c t Địa chỉ​​​​​ | | n o n c e ), và || | | là một phép toán nối

Quy trình cam kết:

1. Người tham gia ký vào tin nhắn M M = ( \mathsf{address}\ ||\ \mathsf{eventId } a d r e s s | | e event I d ) và tính toán băm chữ ký.
2. Người tham gia gọi hàm cam kết trên hợp đồng thông minh với hàm băm làm tham số.
3. Hợp đồng lưu trữ hàm băm được cung cấp trong một chữ ký cam kết SMT theo \mathsf{index} i n d e x = H H tương ứng.

Hơn nữa, trong bước cam kết chữ ký, hợp đồng thông minh phải xác minh rằng \mathsf{msg.sender} m s g . s e nd e r thuộc về tập hợp ban đầu của những người tham gia ZKSS.

2.3. Xác định người tặng quà

Bước thứ hai, được gọi là xác định người gửi , yêu cầu mọi người tham gia ZKSS phải ẩn danh thêm tính ngẫu nhiên của họ vào một mảng người gửi quà.

Thuật toán 3: Xác định người gửi quà

Đầu vào:

• Riêng tư:

  • \mathsf{sig} s i g – chữ ký ECDSA của người dùng ( \mathsf{address}\ ||\ \mathsf{eventId } a d r e s s | | sự kiện I d )​​
  • \mathsf{address} a d r e s s – địa chỉ của người dùng
  • p_p p p – bằng chứng Merkle cho việc bao gồm địa chỉ của người dùng
  • p_c p c – bằng chứng Merkle cho việc bao gồm cam kết chữ ký của người dùng

• Công cộng:

  • r r – tính ngẫu nhiên duy nhất của người dùng
  • \mathsf{eventId} e event I d – một id duy nhất của trò chơi ZKSS
  • \mathsf{root_p} r o o t p – người tham gia SMT root
  • \mathsf{root_c} r o o t c – cam kết chữ ký gốc SMT
  • \mathsf{null_s} n u l l s – bộ hủy của người dùng để ngăn chặn việc đăng ký ngẫu nhiên hai lần

Chứng minh:

Tạo bằng chứng \pi_e π e cho mối quan hệ:

\mathcal{R}_{e} = \{\mathsf{sig}, \mathsf{địa chỉ}, p_p, p_c, r, \mathsf{eventId}, \mathsf{root_p}, \mathsf{root_c}, \mathsf{null_s}: \\\mathsf{null_s} \leftarrow \mathsf{hash}(\mathsf{sig.s}), \\\mathsf{địa chỉ} \leftarrow \mathsf{ecrecover}(\mathsf{sig}, (\mathsf{địa chỉ}\ ||\ \mathsf{eventId})), \\\mathsf{merkleVerify}(\mathsf{địa chỉ}, p_p, \mathsf{root_p}) \rightarrow \mathsf{true}, \\\mathsf{merkleVerify}(\mathsf{hash}(\mathsf{sig}), p_c, \mathsf{root_c}) \rightarrow \mathsf{true}, \\r = r * r\ } R e = { s i g , a d r e s s , p p , p c , r , e v e n t I d , r o o t p , r o o t c , n u l l s : n u l l s ← h a s h ( s i g . s ) , a d d r e s s ← e cr r e c o v e r ( s i g , ( a d d r e s s | | sự kiện I d ) ) ,​​​ me e r k l e V e r i f y ( a d r e s s , p p , ro o t p ) → đúng , ​​​​​me e r k l e V e r i fy y ( h a s h ( s i g ) , p c , r o o t c ) → đúng ,​​​r = r ∗ r }

Chứng minh \pi_e π e được xác minh bằng hợp đồng. Nếu chứng minh này đúng và \mathsf{null_s} n u l l s không được bao gồm trong danh sách các số vô hiệu đã sử dụng, người dùng sẽ đưa tính ngẫu nhiên của chúng vào mảng thông qua một bộ chuyển tiếp. Tính ngẫu nhiên và số vô hiệu phải được truy cập theo từng cặp.

Hoạt động cuối cùng r = r * r r = r ∗ r trong quan hệ \mathcal{R}_{e} R e tạo ra các ràng buộc bổ sung để "neo" giá trị r r nhằm đảm bảo tính hợp lý của giao thức.

R r phải được tạo ra duy nhất bởi mỗi người tham gia và được công khai . Tuy nhiên , mối quan hệ giữa r r và \mathsf{người tham gia} được ẩn trong ZKP với một bên chuyển tiếp gửi giao dịch.

Người chơi được khuyên nên sử dụng khóa công khai RSA 2048 bit cho tính ngẫu nhiên r r . Nghĩa là, người tham gia ZKSS tạo ra duy nhất các khóa riêng RSA (mà họ phải nhớ) và công bố các khóa công khai tương ứng với \mathsf{exp} e x p = 65537.

Khóa công khai RSA đã công bố sau đó được sử dụng trong bước thứ ba của thuật toán để mã hóa địa chỉ giao hàng của người nhận quà để chỉ những người gửi quà tương ứng mới có thể đọc được chúng.

2.4. Tiết lộ người nhận quà tặng

Bước thứ ba, được gọi là tiết lộ người nhận , là bước cuối cùng trong thuật toán ZKSS. Sau đó, việc phân phối Ông già Noel bí mật sẽ hoàn tất và người gửi quà có thể bắt đầu gửi quà cho người nhận.

Bước tiết lộ người nhận có thể được thực hiện mà không cần bộ chuyển tiếp, vì danh tính người nhận ( \mathsf{msg.sender} m s g . s e n d e r ) vẫn được tiết lộ bất kể thế nào.

Thuật toán 4: Tiết lộ người nhận quà

Đầu vào:

• Riêng tư:

  • \mathsf{sig} s i g – chữ ký ECDSA của người dùng ( \mathsf{address}\ ||\ \mathsf{eventId } a d r e s s | | sự kiện I d )​​

• Công cộng:

  • \mathsf{address} a d r e s s – địa chỉ của người dùng
  • \mathsf{eventId} e event Id – một id duy nhất của trò chơi ZKSS (địa chỉ hợp đồng || | | nonce)
  • \mathsf{null_s} n u l l s – bộ hủy của người gửi

Chứng minh:

Tạo bằng chứng \pi_c π c cho mối quan hệ:

\mathcal{R}_{c} = \{\mathsf{sig}, \mathsf{address}, \mathsf{eventId}, \mathsf{null_s}: \\\mathsf{null_r} \leftarrow \mathsf{hash}(\mathsf{sig.s}), \\\mathsf{address} \leftarrow \mathsf{ecrecover}(\mathsf{sig}, (\mathsf{address}\ ||\ \mathsf{eventId})), \\\mathsf{null_r} \neq \mathsf{null_s}\ } R c = { s i g , a d r e s s , e v e n t I d , n u l l s : n u l l r ← h a s h ( s i g . s ) , a d d r e s s ← e cr r e c o v e r ( s i g , ( a d d r e s s | | sự kiện I d ) ) ,​​​ n u l l r ≠ n u l l s }

Chứng minh \pi_c π c được xác minh bằng hợp đồng. Nếu xác minh thành công và \mathsf{null_r} n u l l r không bằng \mathsf{null_s} n u l l s đã chọn, \mathsf{address} a d res e s s của người nhận sẽ được gán cho tính ngẫu nhiên của người gửi tương ứng (khóa công khai RSA).

Bất đẳng thức của người vô hiệu phải được xác minh riêng tư để không tiết lộ vị trí của người nhận từ bước trước.

Để thực thi tính duy nhất của việc tiết lộ người nhận, một hợp đồng thông minh (công khai) phải duy trì danh sách \mathsf{msg.senders} m s g . s e n d e r s duy nhất và xác minh rằng chúng thuộc về tập hợp ban đầu của những người tham gia ZKSS.

Trong trường hợp xảy ra xung đột khi nhiều người nhận cùng lúc chọn cùng một người gửi, một trong các giao dịch phải hoàn nguyên và người nhận bị loại bỏ phải cố gắng tiết lộ lại thông tin của mình.

Cùng với ZKP, người nhận quà có thể cung cấp địa chỉ được mã hóa (thực tế) của họ nơi họ muốn nhận quà. Việc mã hóa được thực hiện bằng khóa công khai RSA của người gửi đã được cung cấp trước đó.

Việc triển khai giao thức ZKSS có thể bổ sung các kiểm tra tính chính xác của mã hóa RSA vào lược đồ xác minh ZKP.

3. Bảo mật

3.1. Tính không xác định của ECDSA

Nếu không có bước cam kết chữ ký, giao thức ZKSS có thể bị tấn công và DoS trò chơi. Người tham gia không trung thực có thể tạo ra chữ ký ECDSA không xác định và vượt qua cơ chế bảo vệ của trình hủy, chiếm hết tất cả các khe của người gửi.

Tuy nhiên, một phiên bản thay thế của giao thức ZKSS có thể được đề xuất bằng cách sử dụng chữ ký EdDSA. Tính chất xác định của chúng cho phép bỏ qua bước cam kết chữ ký, loại bỏ các cam kết chữ ký SMT và các hàm hủy được xây dựng trực tiếp dưới dạng \mathsf{hash}(\mathsf{sig}) h a s h ( s i g ) , chứ không phải \mathsf{hash}(\mathsf{sig.s}) h a s h ( s i g . s ) .

3.2. Người nhận chạy trước

Có khả năng xảy ra một cuộc tấn công tiên phong nhỏ trong bước tiết lộ người nhận của giao thức.

Người gửi quà không trung thực có thể theo dõi mempool giao dịch để chạy trước người nhận (bằng cách chọn cùng một người gửi) nhằm tăng khả năng người nhận đó chọn người gửi không trung thực trong lần tiết lộ tiếp theo.

Tuy nhiên, cuộc tấn công này chỉ có hiệu quả một lần (người nhận chỉ có thể chọn người gửi một lần) và không thể thực hiện được khi đã chọn người gửi không trung thực.

4. Tính đúng đắn

Yếu tố thiết yếu của ZKSS là tách biệt bước thứ hai và bước thứ ba. Vì bộ chuyển tiếp giao dịch được sử dụng trong bước thứ hai, những người tham gia ở bước thứ ba không thể xác định tính ngẫu nhiên nào thuộc về người tham gia nào. Hơn nữa, người tham gia chỉ có thể sử dụng tính ngẫu nhiên của mình một lần, điều này được thực thi bởi logic nullifer. Hơn nữa, bằng cách sử dụng ZKP, chúng tôi đảm bảo rằng không người tham gia nào có thể thao túng giao thức để tự gửi quà tặng cho mình hoặc chọn một người gửi cụ thể.

Để minh họa những khái niệm này, hãy xem xét phép so sánh với Ông già Noel bí mật sau đây. Hãy tưởng tượng có n n người tham gia tụ tập lại với nhau (xem thuật toán 1).

Mỗi người tham gia đặt một tờ giấy ghi thông tin ngẫu nhiên của mình vào một chiếc mũ một cách an toàn. Mọi người đều bí mật thêm ghi chú của mình vào, và không ai có thể quan sát được ghi chú nào thuộc về ai, ngoại trừ cơ chế "vận chuyển", tương ứng với người chuyển tiếp trong giao thức của chúng tôi (xem thuật toán 3). Nhiều công nghệ, VPN, v.v., có thể được sử dụng để đảm bảo tính ẩn danh liên quan đến người chuyển tiếp, nhưng chúng vượt ra ngoài phạm vi tờ giấy này.

Cuối cùng, mỗi người tham gia rút đúng một tờ tiền từ chiếc mũ, và — nhờ “phép thuật” (được đảm bảo bởi ZKP) — họ không thể lấy lại tờ tiền của mình (xem thuật toán 4). Sau khi các tờ tiền có số ngẫu nhiên được tiết lộ, người tham gia tương ứng với một số nhất định sẽ gửi một món quà cho người đã rút tờ tiền ra.

Hơn nữa, nếu độ ngẫu nhiên được chọn là khóa công khai RSA, người nhận có thể truyền địa chỉ giao hàng một cách an toàn đến ông già Noel của họ thông qua mã hóa RSA.

Tóm lại, các giả định chính liên quan đến tính đúng đắn của giao thức như sau:

• Mỗi người gửi quà sẽ không tiết lộ thông tin về bản thân và tính ngẫu nhiên được sử dụng trong bước thứ hai của giao thức.
• Chữ ký ECDSA phải được xây dựng theo RFC 6979 [3]. Chỉ chấp nhận chữ ký từ nửa dưới của đường cong.
• Mã sự kiện \ mathsf { eventId } là duy nhất cho mọi trò chơi ZKSS.
• Tính vững chắc của giao thức bắt nguồn từ tính vững chắc của hệ thống chứng minh ZK cơ bản.
• Nếu người tham gia cung cấp dữ liệu được mã hóa, họ có trách nhiệm đảm bảo tính chính xác của dữ liệu được mã hóa.

Tài liệu tham khảo

1. [Woo24] Gavin Wood. Ethereum: Sổ cái giao dịch tổng quát phi tập trung an toàn. https://
2. ethereum.github.io/yellowpaper/paper.pdf . Phiên bản f3553dd. Truy cập: 2025-01-08. 2024.
   [ide24] iden3. Cây Merkle thưa thớt. https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf .
   Truy cập: 2025-01-08. 2024.
3. [Por13] Thomas Pornin. Sử dụng thuật toán chữ ký số (DSA) và Elliptic một cách xác định
   Thuật toán chữ ký số Curve (ECDSA). RFC 6979. Tháng 8 năm 2013. doi: 10.17487/RFC6979.
   url: Thông tin về RFC 6979 » Trình soạn thảo RFC .