VRF - Verifiable Random Function

ãy tưởng tượng bạn bạn thả xúc sắc rơi vào một cái hộp đen của một người khác. Bạn không thể nhìn thấy con xúc sắc có giá trị bao nhiêu mà phải nhờ người đó kiểm tra hộ để xem xúc sắc có kết quả bao nhiêu. Người đó sẽ nói cho bạn kết quả của xúc sắc và một bằng chứng rằng con xúc sắc đó không hề bị thay đổi giá trị. Đó là ý tưởng chính của Verifiable Random Function.

Bài viết này, mình giới thiệu về VRF và có một ví dụ đơn giản để các bạn không chuyên sâu dễ hình dung, trong thực tế, mọi tính toán của VRF thường được thực hiện trên đường cong Elliptic, và cặp ghép, và sẽ phức tạp hơn rất nhiều.

VRF có hai đặc tính cốt lõi:

Ngẫu nhiên (Randomness): Với cùng một đầu vào, chỉ người giữ khóa bí mật mới có thể tạo ra con số ngẫu nhiên. Người ngoài không thể đoán trước được kết quả.
Có thể kiểm chứng (Verifiability): Bất kỳ ai cũng có thể dùng khóa công khai để kiểm tra và xác nhận rằng con số ngẫu nhiên đó là hợp lệ cho đầu vào tương ứng.

Cách hoạt động

Một quy trình VRF luôn bao gồm ba bước cơ bản:

Tạo Khóa (KeyGen): Alice tạo ra một cặp khóa: một khóa bí mật (SK) mà cô ấy giữ kín và một khóa công khai (PK) mà cô ấy chia sẻ cho mọi người.
Tạo Bằng Chứng (Prove): Khi cần tạo số ngẫu nhiên cho một dữ liệu đầu vào, Alice sẽ dùng khóa bí mật (SK) của mình để tính toán ra hai thứ: một giá trị ngẫu nhiên $y$ và một bằng chứng - proof $\pi$
Kiểm Chứng (Verify): Người khác có thể lấy khóa công khai (PK) của Alice, cùng với dữ liệu đầu vào, giá trị ngẫu nhiên $y$ , và bằng chức $\pi$ đề xác thực. Nếu việc kiểm tra thành công, Bob có thể chắc chắn 100% rằng $y$ là kết quả ngẫu nhiên hợp lệ do chính Alice tạo ra.

Ví dụ

1. Tạo Khóa (KeyGen)

Alice tạo một cặp khóa cho VRF

Chọn hai số nguyên tố (bí mật): $p=5,q=11$
Tính N: $N=p \times q = 55$
Tính phi(N): $\phi(N)=(p-1) \times (q-1) = 40$
Chọn số e: $e$ là số nguyên tố cùng nhau với $\phi(N)$ . Ta chọn $e=3$
Tính số d: $d$ là nghịch đảo modular của $e$ theo $\mod \phi(N)$ . Tức là $d \times e \equiv 1 (\mod 40), d=27$

Kết quả:

Khóa bí mật (SK): $d=27$
Khóa công khai (PK): $(N=55, e=3)$

2. Chứng Minh (Prove)

Bây giờ, Alice muốn tạo ra một giá trị ngẫu nhiên có thể kiểm chứng cho một đầu vào.

Đầu vào: $\alpha = \text{"Hello World"}$
Bước 1: Hashing: Alice cần chuyển $\alpha$ thành một con số. Ta dùng hàm hash công khai (để đơn giản ở ví dụ này mình lấy tổng mã Ascii đem mod cho $N$ ) và lấy kết quả theo modulo $N$
Bước 2: Tạo bằng chứng (Proof): Alice dùng khóa bí mật $d$ của mình để tính toán bằng chứng $\pi$ . Đây chính là cốt lõi của việc "ký" bằng RSA.
- $\pi = m^d \bmod N = 7^{27}\bmod 55 = 28$
- Vậy bằng chứng là $\pi=28$
Bước 3: Tạo giá trị ngẫu nhiên (Random Output): Giá trị ngẫu nhiên $y$ được tạo ra bằng cách hashbằng chứng $\pi$
- $y=Hash(\pi) = Hash(\text{"28"})=51$
- Vậy, Giá trị ngẫu nhiên (Output) là $y=51$

Alice sẽ công bố $(\alpha, y, \pi)$ tức là: $(\text{"Hello World", 51, 28})$

3. Kiểm Chứng (Verify)

Bob nhận được bộ ba thông tin từ Alice và muốn kiểm chứng. Bob chỉ có khóa công khai $(N=55, e=3)$

Bước 1: Kiểm tra Bằng chứng: Bob dùng bằng chứng $\pi$ và khóa công khai $e$ để tính ngược lại giá trị $m$ ban đầu
- $m'=\pi^e \bmod N = 28^3 \bmod 55 = 7$
Bước 2: Băm lại đầu vào: Bob tự hash đầu vào $\alpha$ mà Alice đã cung cấp
- $m_{hash} = Hash(\text{"Hello World"}) = 7$
Bước 3: So sánh: Bob so sánh $m'$ và $m_{hash}$
- $7=7$ Chúng khớp nhau! Điều này chứng tỏ bằng chứng $\pi=28$ là hợp lệ cho đầu vào “Hello World“ và được tạo bởi người giữ khóa bí mật tương ứng với khóa công khai $(55,3)$
Bước 4: Kiểm tra giá trị ngẫu nhiên: Bob băm bằng chứng $\pi$ để xem có khớp với giá trị $y$ mà Alice đưa ra không.
- $y' = Hash(\pi)=Hash(\text{"28"})=51$
- Vậy $y=51$ khớp với $y'=51$

Kết luận: Vì tất cả các bước đều hợp lệ, Bob có thể tin rằng $y=51$ là giá trị ngẫu nhiên duy nhất và không thể đoán trước, được tạo ra một cách hợp lệ cho đầu vào “Hello World” bởi Alice.

Interactive Demo

Để đơn giản, hàm hash sẽ được định nghĩa bằng cách mình lấy tổng mã Ascii mod cho $N$

Verifiable Random Function (VRF) và một ví dụ đơn giản