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

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:

1. 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ả.

2. 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:

1. Tạo Khóa (KeyGen): Người dùng 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.

2. 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\).

3. 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ứng \(\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 một 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 \(\bmod \phi(N) \) . Tức là \(d \times e = 1 (\bmod 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: Băm đầu vào (Hashing): Alice cần chuyển \(\alpha\) thành một con số. Ta dùng một hàm băm công khai (để đơn giản, mình lấy tổng mã Ascii mod cho \(N\)) và lấy kết quả theo modulo \(N\).

  • \(m=Hash(\alpha) = 7\)

• 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 \(\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 băm bằ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ị băm \(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ự băm đầ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\).