solution

Trong các hệ thống blockchain kiểu Bitcoin, thợ đào phải giải một bài toán bằng chứng công việc (Proof of Work): tìm một giá trị nonce sao cho giá trị băm SHA-256 của (thông điệp nối với nonce) có ít nhất $k$ bit 0 liên tiếp ở đầu (tính từ bit có trọng số cao nhất — MSB — của toàn bộ chuỗi 256 bit).

Cho thông điệp message (chuỗi) và độ khó $k$ ($0 \le k \le 16$). Bắt đầu thử nonce = 0, 1, 2, \ldots, với mỗi giá trị tính: $H(\text{nonce}) = \text{SHA256}\big(message \,\Vert\, \text{str}(\text{nonce})\big)$ (trong đó str(nonce) là biểu diễn thập phân thông thường của nonce, ví dụ nonce = 7 → chuỗi "7"; nối chuỗi trực tiếp, không thêm ký tự phân cách).

Tìm nonce nhỏ nhất sao cho $H(\text{nonce})$, khi biểu diễn dưới dạng 256 bit nhị phân (byte đầu tiên là các bit có trọng số cao nhất), có ít nhất $k$ bit 0 liên tiếp kể từ vị trí đầu tiên.

Ví dụ: message = "hello", $k = 0$ → mọi giá trị hash đều thỏa (có ít nhất 0 bit 0 ở đầu), do đó nonce nhỏ nhất là $0$.