---
# System prepended metadata

title: Class Group và Ứng Dụng Trong Verifiable Delay Functions (VDF)
tags: [VDF]

---

## Mở đầu

Trong mật mã học hiện đại, **Verifiable Delay Function (VDF)** là hàm tính toán *chậm bắt buộc* nhưng *xác minh nhanh*.  
Một ứng cử viên mạnh để xây dựng VDF là **class group** – khái niệm cốt lõi của lý thuyết số đại số từ thời Gauss.

---

## 1. Từ phân tích thừa số duy nhất đến class group
Trong $\mathbb{Z}$, mọi số đều phân tích duy nhất thành tích số nguyên tố. Ví dụ:

$$
30 = 2 \cdot 3 \cdot 5.
$$

Nhưng trong các vành số khác, tính duy nhất có thể thất bại.  
Ví dụ trong $\mathbb{Z}[\sqrt{-5}]$:

$$
6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}).
$$

Ở đây $2,3,1\pm\sqrt{-5}$ đều là “nguyên tố” trong vành đó ⇒ 6 có **hai phân tích khác nhau**.

---

## 2. Ideal và class group
Để khắc phục sự không duy nhất, ta xét **ideal** (tập con ổn định dưới cộng/nhân).  
- Phân tích ideal là duy nhất.  
- Các ideal “tương đương” gom vào một **class**.  
- Tập các class tạo thành **ideal class group** $\mathrm{Cl}(\mathcal{O}_K)$.  

**Class number** $h_K$ là bậc của class group:
$$
h_K = \bigl|\mathrm{Cl}(\mathcal{O}_K)\bigr|.
$$

- Nếu $h_K=1$ ⇒ mọi ideal đều principal ⇒ có phân tích duy nhất.  
- Nếu $h_K>1$ ⇒ tồn tại ideal không principal ⇒ phân tích không duy nhất.  

Ví dụ: $\mathbb{Z}[\sqrt{-5}]$ có $h=2$.

---

## 3. Unknown-order group – điểm then chốt cho VDF
VDF cần:  
- **Tính toán chậm bắt buộc**: tính $g^{2^T}$ chỉ có cách làm tuần tự.  
- **Xác minh nhanh**: dễ check kết quả.  

Nếu biết bậc nhóm $|G|$, ta có thể rút gọn mũ (theo modulo $|G|$) ⇒ mất tính “chậm bắt buộc”.  
Do đó, cần một **unknown-order group** (không ai biết chính xác bậc nhóm).  

- **RSA group** $\mathbb{Z}_N^*$: công chúng không biết $\varphi(N)$, nhưng người tạo (biết $p,q$) thì biết ⇒ có trapdoor.  
- **Class group**: với discriminant lớn, **không ai**, kể cả người tạo, biết chính xác $h_K$ ⇒ unknown-order tự nhiên, không trapdoor.  

---

## 4. Minh hoạ
Trong $\mathbb{Z}[\sqrt{-5}]$, xét ideal $I=(2,1+\sqrt{-5})$. Có thể chứng minh $I$ không principal ⇒ tồn tại ít nhất 2 class ⇒ $h=2$.  

Ở quy mô thực tế (discriminant $|D|$ vài nghìn bit), $h_K$ cực lớn và **không thể tính chính xác** bằng thuật toán hiện nay.

---

## 5. So sánh: RSA group vs Class group trong VDF

| Tiêu chí | RSA group $\mathbb{Z}_N^*$ | Class group (quadratic) |
|----------|-----------------------------|--------------------------|
| Unknown-order với công chúng | Có | Có |
| Người tạo biết bậc nhóm | Có (biết $p,q$) | Không |
| Cần trusted setup | Có | Không |
| Dễ triển khai | Rất dễ | Khó hơn |
| Ưu điểm | Hiệu năng tốt | Công bằng tuyệt đối, không trapdoor |

---

## 6. Checklist chọn class group cho VDF
1. Chọn **discriminant $D<0$** rất lớn (nhiều nghìn bit).  
2. Biểu diễn ideal/class bằng dạng chuẩn (cặp số nguyên nhỏ).  
3. Sinh phần tử $g$ từ ideal nhỏ.  
4. Cài phép toán composition (nhân class) hiệu quả.  
5. Tích hợp proof để xác minh nhanh $g^{2^T}$.  
6. Đảm bảo $h_K$ cực lớn, không ai tính được.  

---

## 7. Kết luận 
Class group là cầu nối đẹp giữa toán cổ điển và công nghệ hiện đại: tạo ra một **unknown-order group** tự nhiên, cực phù hợp cho VDF.  

- **RSA-VDF**: thực dụng, nhưng cần trusted setup.  
- **Class-group VDF**: tinh khiết, công bằng tuyệt đối, không trapdoor.  

---

## Tham khảo
- Gauss, *Disquisitiones Arithmeticae*.  
- Dan Boneh et al., *Verifiable Delay Functions*.  
- Ethereum 2.0 research, Chia Network research về class group VDF.
