Scalable Distributed Verifiable RNG

Hôm trước ngồi nói chuyện với mấy anh bạn ôn lại chuyện cũ ngày còn làm ở công ty Infinity Blockchain Labs, có cậu bạn bảo mình: "Anh viết blog nhiều như vậy mà sao anh lại không viết một bài viết về mấy cái paper của anh nhỉ?". Mình sực nhớ ra. Ờ nhỉ, mình quả thật thiếu sót! Bài báo của mình, chính xác hơn là team mình là một trong những bài báo đầu tiên viết về cách sinh số ngẫu nhiên trên blockchain, gồm có một series vài bài, nhưng về cốt lõi thì bài báo này là tâm điểm:

Scalable Distributed Random Number Generation Based on Homomorphic Encryption

Các bạn có hứng thú có thể vào link trên để tìm hiểu. Dưới đây là bản tóm tắt bài báo:

Bài viết này tóm tắt giải pháp dRNG (Distributed Random Number Generation) dựa trên sự kết hợp giữa Mã hóa đồng cấu (HE) và Hàm ngẫu nhiên có thể kiểm chứng (VRF), và một số các kỹ thuật khác liên quan đến đường cong Elliptic. Bạn có thể tham khảo thêm tại các bài viết của mình:

• Đường cong elliptic: EC trên trường số thực, EC trên trường hữu hạn, Chữ ký số trên EC

• Chứng minh không để lộ tri thức - Zero Knowlege Proof (ZKP): ZKP đơn giản

• Mã hóa đồng cấu: Đồng cấu nhóm cộng vỡi hệ mã Paillier

• Hàm ngẫu nhiên có thể kiểm chứng (VRF): VRF đơn giản

Mục tiêu

Blockchain về bản chất là một máy trạng thái xác định (deterministic), nơi mọi dữ liệu đều phải công khai và minh bạch để mọi node có thể thực hiện lại phép tính và cho ra cùng một kết quả. Do đó:

• Không có hàm random() thực sự: Nếu một node dùng hàm ngẫu nhiên của hệ điều hành, các node khác sẽ không thể đồng thuận về kết quả đó.

• Vấn đề tin tưởng: Làm sao để tin một số ngẫu nhiên được tạo ra mà không bị bên nào (kể cả thợ đào hay người yêu cầu) thao túng hoặc biết trước kết quả để trục lợi?

Mục tiêu của giao thức: Tạo ra một số ngẫu nhiên từ sự đóng góp của nhiều bên, đảm bảo: Unpredictability (Không thể dự đoán), Tamper-resistance (Kháng thao túng), Scalability (Khả năng mở rộng) và Verifiability (Có thể kiểm chứng công khai).

Sequence Diagram

Các Role và Thành phần hệ thống

Hệ thống bao gồm 3 vai trò chính phối hợp trên nền tảng Public Distributed Ledger (PDL):

1. Requester (Người yêu cầu): Bên khởi tạo phiên tạo số ngẫu nhiên. Requester giữ khóa bí mật $x$ để giải mã kết quả cuối cùng.

2. Participants/Nodes (Người tham gia): Các node trong mạng lưới phân tán. Họ sử dụng khóa cá nhân để tự chạy VRF nhằm xác định quyền đóng góp và tạo ra các mảnh ghép Beacon bí mật.

3. PDL (Sổ cái phân tán/Smart Contract): Đóng vai trò là "điểm hẹn" công khai. PDL lưu trữ các bằng chứng, thực hiện phép toán cộng đồng cấu và đảm bảo quy trình diễn ra đúng trình tự thời gian. Ở đây, chúng ta có thể hình dung PDL là một hệ Blockchain bất kỳ có smart contract.

Quy trình tổng quan

Quy trình hoạt động theo mô hình phễu lọc để tối ưu hiệu năng:

1. Giai đoạn Đăng ký: Requester gửi yêu cầu kèm một nonce công khai.

2. Giai đoạn Sàng lọc (VRF): Từ hàng ngàn node ban đầu, hệ thống dùng VRF để chọn ra một nhóm nhỏ $k$ node đủ điều kiện (Eligible Nodes).

3. Giai đoạn Đóng góp (HE): Những node trúng tuyển mã hóa mảnh ghép ngẫu nhiên của mình và gửi lên PDL.

4. Giai đoạn Tổng hợp & Giải mã: PDL cộng các bản mã lại mà không cần mở chúng ra. Cuối cùng, kết quả được giải mã để công bố Beacon.

Chi tiết kỹ thuật: Giao thức dRNG 8 giai đoạn

Giao thức vận hành trên đường cong Elliptic $E$ xác định trên trường hữu hạn $\mathbb{F}_p$ với phần tử sinh $\mathcal{G}$ bậc $N$. Hệ mã hóa chính được sử dụng là El-Gamal ECC nhờ tính chất đồng cấu cộng.

Giai đoạn 1: Khởi tạo (Initialization)

Requester khởi tạo một session tạo số ngẫu nhiên bằng cách gửi một yêu cầu lên PDL.

• Requester tạo cặp khóa: Khóa bí mật $x$ và khóa công khai $Y = x\mathcal{G}$.

• Gửi kèm một giá trị nonce (số dùng một lần) để đảm bảo tính duy nhất cho phiên.

Giai đoạn 2: Tính toán Ticket (Ticket Generation)

Hệ thống xác định một giá trị đầu vào chung cho hàm VRF của tất cả các node:

• Mỗi node tính toán Ticket $T = H(PK, nonce)$, trong đó $H$ là hàm băm mật mã, có thể là $SHA256$. Giá trị $T$ này đảm bảo rằng không ai có thể dự đoán được kết quả VRF trước khi phiên bắt đầu.

Giai đoạn 3: Kiểm tra quyền hợp lệ (Check Eligibility)

Mỗi node $i$ trong mạng lưới tự kiểm tra quyền tham gia đóng góp:

• Sử dụng khóa bí mật $sk_i$ để tính: $(y_i, \pi_i) = VRF\_Prove_{sk_i}(T)$.

• Node được coi là hợp lệ (Eligible) nếu $y_i < \mathcal{T}$ (với $\mathcal{T}$ là ngưỡng xác định trước).

• Nếu hợp lệ, node chuẩn bị bằng chứng PoE (Proof-of-Eligibility) bao gồm $\langle T, y_i, \pi_i \rangle$.

Giai đoạn 4: Xác minh PoE (Verify PoE)

Trước khi chấp nhận đóng góp, PDL (Sổ cái) thực hiện xác minh công khai:

• PDL sử dụng khóa công khai $pk_i$ của node để chạy hàm $VRF\_Verify(pk_i, T, y_i, \pi_i)$.

• Nếu hợp lệ, node $i$ được ghi danh vào danh sách các bên đóng góp chính thức cho session này.

Giai đoạn 5: Đóng góp bản mã (Contribution)

Mỗi node hợp lệ chọn một số ngẫu nhiên bí mật $M_i$ (đóng góp của họ) và mã hóa nó bằng khóa công khai $Y$ của Requester:

1. Chọn một số ngẫu nhiên $k_i \in \mathbb{Z}_N$.

2. Tính cặp bản mã El-Gamal:

   • $C_i = k_i \mathcal{G}$

   • $D_i = k_i Y + M_i$

3. Node gửi $(C_i, D_i)$ kèm theo chữ ký số xác thực (PoC - Proof-of-Contribution) lên PDL.

Giai đoạn 6: Xác minh PoC (Verify PoC)

PDL kiểm tra tính toàn vẹn của các bản mã nhận được:

• Xác minh chữ ký số của từng node để đảm bảo dữ liệu không bị thay đổi trên đường truyền.

• Kiểm tra xem các điểm $(C_i, D_i)$ có thực sự nằm trên đường cong $E$ hay không.

Giai đoạn 7: Tổng hợp đồng cấu (Tallying)

Sau khi kết thúc thời gian đóng góp, PDL tự động tổng hợp tất cả $n_c$ bản mã hợp lệ thành một bản mã tổng duy nhất mà không cần giải mã bất kỳ giá trị trung gian nào:

• $C = \sum_{i=1}^{n_c} C_i = (\sum_{i=1}^{n_c} k_i) \mathcal{G}$

• $D = \sum_{i=1}^{n_c} D_i = (\sum_{i=1}^{n_c} k_i) Y + \sum_{i=1}^{n_c} M_i$

Phép toán này chỉ tốn $\mathcal{O}(n)$ phép cộng điểm trên đường cong Elliptic.

Giai đoạn 8: Giải mã và Công bố (Reveal)

Requester thu thập bản mã tổng $(C, D)$ từ PDL và thực hiện bước cuối cùng để lấy số ngẫu nhiên:

1. Sử dụng khóa bí mật $x$ để tính toán: $M = D - xC$.

2. Chứng minh toán học: $M = (\sum k_i Y + \sum M_i) - x(\sum k_i \mathcal{G})$

   Vì $Y = x\mathcal{G}$, nên $x(\sum k_i \mathcal{G}) = \sum k_i (x\mathcal{G}) = \sum k_i Y$.

   Do đó: $M = \sum M_i \pmod p$.

3. Requester công bố $M$ kèm theo bằng chứng giải mã đúng (thường là một Zero-Knowledge Proof). $M$ chính là Beacon cuối cùng được mọi người công nhận.

Từ điểm $M$ đến Random Seed

Sau khi đã tính toán được điểm $M$

Chúng ta sẽ tính random seed bằng cách sử dụng hàm Hash:

Từ random seed này chúng ta bắt đầu có thể khởi tạo chuỗi giá trị random theo một hàm random tùy ý.

Demo

Dưới đây là một demo đơn giản để minh họa, mình đã cố gắng thực hiện mọi thao tác sao cho sát với thuật toán nhất, và cố tình đơn giản hóa các chi tiết để cho các bạn dễ theo dõi như:

• Chọn đường cong đơn giản $y^2 = x^3 + x + 7 \pmod 83$

• Thay hàm hash bằng một hàm đơn giản hơn bằng phép modulo

• Xây dựng VRF đơn giản dạng Schnorr dựa vào hàm hash đơn giản ở trên (xem phụ lục phía dưới)

Một chút phụ lục về VRF Schnorr style được sử dụng

1. Thiết lập

Bước 1: Giá trị ngẫu nhiên $y_i$ được tính bằng

Đây là giá trị mà các bước sau sẽ bảo vệ và chứng minh tính hợp lệ.

Bước 2: Cam kết (Commitment)

Để bắt đầu bằng chứng, Prover chọn một số ngẫu nhiên tạm thời $r$ (blinding factor) và tạo ra hai "cam kết":

• $B_0 = r \cdot \mathcal{G}$ (trên đường cong Elliptic).

• $t = nonce^r \pmod N$ (trong trường số nguyên).

  Việc chọn $r$ ngẫu nhiên đảm bảo rằng không ai có thể suy ngược ra $sk_i$ từ bằng chứng sau này.

Bước 3: Thử thách (Challenge)

Hàm simpleHash đóng vai trò là một "Fiat-Shamir Heuristic". Thay vì cần một người xác minh gửi thử thách, chúng ta tự tạo ra thử thách $c$ bằng cách băm tất cả các thông tin công khai lại với nhau:

Bước 4: Phản hồi (Response)

Cuối cùng, Prover tính toán giá trị $z$:

Bằng chứng cuối cùng gửi đi là bộ ba $\pi_i = \{c, z, t\}$.

2. Quy trình xác thực vrfVerify:

Người xác minh (Verifier) nhận được bằng chứng $\pi_i$ và kết quả $y_i$. Họ thực hiện kiểm tra hai điều kiện mà không bao giờ cần biết $sk_i$:

Kiểm tra tính đúng đắn của khóa (Public Key consistency)

Verifier tính lại điểm $B_0'$ từ $z$ và $c$ nhận được:

Nếu đúng, $z\mathcal{G} - c(sk_i\mathcal{G}) = (r + c \cdot sk_i)\mathcal{G} - c \cdot sk_i\mathcal{G} = r\mathcal{G} = B_0 \checkmark$ $$

Kiểm tra tính đúng đắn của kết quả (Computation consistency)

Verifier kiểm tra xem $y_i$ có thực sự bắt nguồn từ $nonce$ hay không:

Nếu ta thay $z = r + c \cdot sk_i$ và $y_i = nonce^{sk_i}$ vào vế phải:

Nếu cả hai giá trị tính toán lại khớp với mã băm thử thách $c$, ta có thể khẳng định 100% rằng $y_i$ là kết quả hợp lệ duy nhất.

Phần kết luận

Phần tiếp theo của bài báo tập trung phân tích về khía cạnh bảo mật (security) và độ phức tạp tính toán. Mọi người có thể tìm hiểu chi tiết hơn trực tiếp từ bài báo gốc.

Bài báo này là thành quả của cả đội ngũ nghiên cứu – những thành viên đầy nhiệt huyết và đam mê trong nhóm chúng mình, đồng thời cũng là niềm tự hào rất lớn của cá nhân mình. Mình viết bài viết này như một lời tri ân chân thành gửi đến tất cả mọi người đã đồng hành, và cũng xem đây là một kỷ niệm đẹp dành cho team GINAR.