Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Kiểm tra tính hợp lệ của chuỗi khối

    Một blockchain gồm nnn khối đánh số 0,1,…,n−10, 1, \dots, n-10,1,…,n−1. Mỗi khối iii có 4 trường: prevHash, data, nonce, hash, trong đó hash được công bố (claimed) là kết quả băm của khối. Mã băm đúng của một khối được tính theo công thức:

    expectedHash=SHA256(prevHash∥data∥nonce)\text{expectedHash} = \text{SHA256}(\text{prevHash} \parallel \text{data} \parallel \text{nonce})expectedHash=SHA256(prevHash∥data∥nonce)

    (nối chuỗi trực tiếp, không dấu phân cách). Chuỗi khối được coi là hợp lệ nếu với mọi khối iii:

    1. expectedHash của khối iii trùng khớp với hash đã công bố của khối đó, và
    2. với i>0i>0i>0: trường prevHash của khối iii phải bằng đúng hash đã công bố của khối i−1i-1i−1 (khối 0 — khối Genesis — không bị kiểm tra điều kiện này).

    Hãy tìm khối đầu tiên (chỉ số nhỏ nhất, đánh số từ 0) vi phạm một trong hai điều kiện trên. Nếu toàn bộ chuỗi hợp lệ, in ra VALID.

    Ví dụ: nếu dữ liệu của khối 1 bị sửa (từ Alice->Bob:10 thành Alice->Bob:99) nhưng hash công bố vẫn giữ nguyên như cũ thì expectedHash mới sẽ không khớp, và chương trình phải in ra 1.

    • Định dạng đầu vào:
      • Dòng 1: nnn — số lượng khối (1≤n≤10001 \le n \le 10001≤n≤1000).
      • nnn dòng tiếp theo, mỗi dòng ứng với khối theo thứ tự 0,1,…,n−10,1,\dots,n-10,1,…,n−1, gồm 4 giá trị cách nhau bởi khoảng trắng: prevHash data nonce hash (giả định data không chứa khoảng trắng).
    • Định dạng đầu ra:

      Một dòng: in VALID nếu toàn bộ chuỗi hợp lệ; ngược lại in chỉ số (bắt đầu từ 0) của khối đầu tiên bị lỗi.

    Ví dụ:

    Đầu vào:

    3
0000000000000000000000000000000000000000000000000000000000000000 Genesis 0 5af80efc111ff94db09eae2d050ff8fdf85ae9eb55a624d285285d990f73c25f
5af80efc111ff94db09eae2d050ff8fdf85ae9eb55a624d285285d990f73c25f Alice->Bob:99 5 1b4b3dfc0e189263e7d769b3cac3f72737209a4dd5878d6542ca7917d008d2ed
1b4b3dfc0e189263e7d769b3cac3f72737209a4dd5878d6542ca7917d008d2ed Bob->Carol:5 7 3bd882aaff9718a6dd729fa22553697bfc9279ca5b375da02127d11752204f0c

    Đầu ra:

    1

    Đầu vào:

    3
0000000000000000000000000000000000000000000000000000000000000000 Genesis 0 5af80efc111ff94db09eae2d050ff8fdf85ae9eb55a624d285285d990f73c25f
5af80efc111ff94db09eae2d050ff8fdf85ae9eb55a624d285285d990f73c25f Alice->Bob:10 5 1b4b3dfc0e189263e7d769b3cac3f72737209a4dd5878d6542ca7917d008d2ed
1b4b3dfc0e189263e7d769b3cac3f72737209a4dd5878d6542ca7917d008d2ed Bob->Carol:5 7 3bd882aaff9718a6dd729fa22553697bfc9279ca5b375da02127d11752204f0c

    Đầu ra:

    VALID

    Đang tải editor...