Bằng chứng Zero-Knowledge: zk-STARK là gì và hoạt động như thế nào?

1. Đó là gì?

Hệ thống Bằng chứng dự trữ (PoR) zk-STARK thúc đẩy lý thuyết STARK – một giải pháp toán học phức tạp. zk-STARK là viết tắt của: Đối số kiến thức minh bạch có thể mở rộng Zero-Knowledge, một công nghệ bằng chứng mật mã dựa trên [ý tưởng] của Vitalik (https://vitalik.eth.limo/general/2022/11/19/proof_of_solvency.html) giúp thực thi tính toàn vẹn và quyền riêng tư của các tính toán trên blockchain. Trong bài viết này, chúng tôi sẽ giới thiệu cách thức hoạt động của nó và giải thích khái niệm toán học chung. Nhưng nếu bạn muốn tìm hiểu sâu hơn, hãy bắt đầu tại đây hoặc tại đây.

Cách hoạt động?

Hình 1. Bảng dấu vết thực hiện và cây Merkle được xây dựng cho zk-STARK PoR

Bước 1: xây dựng ràng buộc

Để chứng minh trách nhiệm pháp lý của sàn giao dịch, chúng tôi đưa ra ba xác nhận:

Xác nhận 1: Chúng tôi đã tích lũy giá trị của mọi người dùng một cách chính xác, bao gồm giá trị của từng loại tiền mã hóa và giá trị ròng của từng người dùng

Xác nhận 2: Sàn giao dịch không giả mạo một người dùng ảo có giá trị ròng âm để giảm tổng trách nhiệm pháp lý trao đổi (Chỉ chấp nhận người dùng cá nhân có số dư âm nếu giá trị ròng của người đó cao hơn 0)

Xác nhận 3: Tổng giá trị mà sàn giao dịch xác nhận quyền sở hữu được tính cho mỗi người dùng, vì vậy mọi người dùng sẽ có thể xác minh việc đưa giá trị ròng vào tổng giá trị

Để kiểm tra và xác minh các xác nhận trên, chúng ta cần xây dựng các ràng buộc như:

Xác nhận 1: Ràng buộc tổng số dư (Ràng buộc tổng số dư chính xác)

uts: kích thước dấu vết người dùng, là số lượng hàng theo dõi có trong dữ liệu của mỗi người dùng.

tổng: tổng số dư của người dùng

N: số lượng người dùng

Xác nhận 2: Ràng buộc không âm (Ràng buộc vốn chủ sở hữu ròng dương)

Xác nhận 3: Ràng buộc bao gồm (Ràng buộc bao gồm tất cả số dư tài khoản của khách hàng)

Theo các ràng buộc trên, chúng tôi tạo một bảng dấu vết để cam kết và xác minh tổng số dư và trạng thái không âm thông qua kiểm tra lấy mẫu. Sau đây là cách xây dựng bảng dấu vết (ví dụ đơn giản, 3 người dùng có giá trị USD tối đa nhỏ hơn 4^6 = 4096):

1. Chúng tôi khởi tạo một bảng có 32 hàng và 5 cột, đồng thời điền các giá trị và ID của người dùng vào hàng, trong đó k % 8 = 6, và . Mỗi 8 hàng là một khối và thông tin tài sản người dùng hiện có trong  ngược của mỗi khối. Người dùng đầu tiên được cung cấp số dư ảo 0, vì vậy chúng tôi có thể công bố số dư này để chứng minh rằng việc tích lũy giá trị không bắt đầu từ giá trị âm.

2. Chúng tôi tích lũy từng giá trị tài sản của người dùng và điền kết quả vào  các hàng trong đó k % 8 = 7 và , đó là những hàng cuối cùng của mỗi khối

3. Chúng tôi giữ giá trị sàn chia cho tổng giá trị của mỗi người dùng theo 4 từng hàng từ  ngược của mỗi khối. Chúng tôi làm điều đó để giữ cho giá trị ròng của người dùng không âm bằng cách kiểm tra xem các hàng đầu tiên có bằng 0 cho mỗi khối hay không. Nếu ai đó có giá trị ròng âm, hàng đầu tiên trong khối của họ sẽ không bằng 0 vì giá trị âm (-x) sẽ trở thành (p - x) trong trường hữu hạn , đó là một giá trị dương rất lớn.

4. Chúng tôi nhập các số ngẫu nhiên cho từng người dùng và điền vào các khoảng trống trong bảng bằng 0

Bước 2: Mở rộng đa thức bậc thấp Sử dụng các ràng buộc đa thức ở trên, chúng ta có thể thu được một đa thức dấu vết tính toán có độ dài uts * N. Vì lý do bảo mật, chúng tôi thực hiện cam kết với đa thức trên miền đánh giá lớn hơn, với hệ số khuếch đại miền làm hệ số_ mở rộng.

Trong trường hợp trên, chúng ta có thể tính đa thức p(x) từ I(x). Khi sử dụng hệ số_ mở rộng 8, chúng tôi sẽ tính một điểm 32(8-1)* nữa trên p(x).

Vì hai đa thức khác nhau có bậc D sẽ chia sẻ tối đa D điểm, nên một cặp đa thức ví dụ với một đa thức hợp lệ (thỏa mãn các ràng buộc trên) và một đa thức giả có bậc D (không thỏa mãn các ràng buộc trên) sẽ chia sẻ tối đa D điểm. Điều đó có nghĩa là một đa thức giả có xác suất vượt qua một lượt kiểm tra lấy mẫu ngẫu nhiên. Nếu chúng tôi thực hiện kiểm tra lấy mẫu n lần, xác suất sẽ giảm xuống còn .

Chúng tôi triển khai hệ số_ mở rộng mặc định là 16 và thời gian mặc định kiểm tra lấy mẫu là 16, vì vậy mức độ bảo mật sẽ là 80 bit.

Bước 3: cam kết đa thức Chúng tôi tính toán giá trị băm của dấu vết tính toán và số dư người dùng tương ứng, ID người dùng và giá trị của đa thức ràng buộc tương ứng cho mỗi hàng và tạo cây Merkle. Gốc Merkle là giá trị cam kết của đa thức.

Bước 4: tạo bằng chứng lấy mẫu Sử dụng gốc Merkle làm nguồn ngẫu nhiên, chúng tôi lấy mẫu dữ liệu. Để tránh rò rỉ dữ liệu dấu vết tính toán, chúng tôi tránh dữ liệu có chỉ mục là *k ** hệ số_mở rộng trong quá trình lấy mẫu và tạo đường dẫn bằng chứng Merkle tương ứng với chỉ số lấy mẫu.

Chúng tôi thực hiện kiểm tra lấy mẫu để kiểm tra xem đa thức đã cam kết có phải là đa thức hợp lệ đáp ứng các ràng buộc được liệt kê trong Bước 1 hay không. Như đã nêu trong Bước 2, thời gian kiểm tra lấy mẫu sẽ ảnh hưởng đến xác suất giả mạo hoặc thao túng thành công.

Bước 5: tạo bằng chứng bậc thấp

Chúng tôi có thể kiểm soát xác suất giả mạo hoặc thao túng thành công thông qua kiểm tra lấy mẫu. Tuy nhiên, có một điều kiện như đã đề cập ở Bước 2 là ta cần đảm bảo bậc của đa thức đang được xác minh không lớn hơn bậc của đa thức hợp lệ. Để nâng cao hiệu quả chứng minh, chúng tôi kết hợp tuyến tính tất cả các đa thức ràng buộc thành một đa thức và tạo bằng chứng bậc thấp cho nó. Các hệ số kết hợp cũng được tạo bằng cách sử dụng gốc Merkle làm nguồn ngẫu nhiên.

Ví dụ: nếu ta muốn chứng minh rằng p0(x), p1(x) và p2(x) không lớn hơn bậc D, chúng ta có thể tạo các hệ số ngẫu nhiên 2 từ căn Merkle được tạo ở Bước 3 và tính toán đa thức tuyến tính l(x) dưới dạng:

k0 = hàm băm (gốc "0")
k1 = hàm băm (gốc "1")
l(x) = k0 * p0(x) k1 * p1(x) p2(x)

Nếu l(x) có thể được chứng minh là không lớn hơn bậc D, thì xác suất bậc của bất kỳ p0(x), p1(x) và p2(x) là hơn D sẽ gần bằng 0

Bước 6: xác minh tổng số dư Trước tiên, chúng tôi xác minh bằng chứng bậc thấp được tạo ở Bước 5.

Sau đó, xác minh mở tiếp theo được thực hiện trên dữ liệu đã lấy mẫu được tạo ở Bước 4. Đầu tiên là cần xác minh rằng dữ liệu phù hợp với cam kết đa thức và thứ hai là cần xác minh rằng dữ liệu đáp ứng các ràng buộc được xây dựng trong Bước 1. Cuối cùng, các hệ số kết hợp của đa thức kiểm tra bậc thấp được xác minh.

Bước 7: tạo bằng chứng bao gồm người dùng Để chứng minh rằng một người dùng cụ thể được đưa vào tổng số tiền mà sàn giao dịch yêu cầu, chúng tôi cung cấp dấu vết đã tính toán của người dùng, số dư người dùng, ID người dùng và một số ngẫu nhiên tương ứng với chỉ mục người dùng . Chúng tôi cũng cung cấp đường dẫn Merkle tương ứng với dữ liệu này.

Bước 8: người dùng xác minh bằng chứng bao gồm Người dùng kiểm tra số dư, ID, tính toán giá trị băm của dữ liệu tương ứng với chỉ mục và xác minh giá trị băm trên nút lá của cây Merkle bằng đường dẫn Merkle được cung cấp .

2. Cách thực hiện tự xác minh Bằng chứng dự trữ (PoR)?

2.1 Xác minh ràng buộc Bao gồm zk-STARK

Lý thuyết xác minh

Theo quy trình STARK, chúng tôi sẽ tính toán bảng theo dõi thực hiện tất cả tài sản người dùng như bên dưới và băm thông tin của từng người dùng dưới dạng bảng theo dõi trở thành lá cây Merkle, sau đó chuyển các lá này vào gốc Merkle sẽ được công bố trong mỗi vòng kiểm toán PoR.

Để xác minh xem tài sản của bạn có được đưa vào thư mục gốc hay không, chúng tôi sẽ cung cấp cho bạn đường dẫn Merkle để xác minh. Trước tiên, bạn có thể tính toán lá của mình bằng cách băm thông tin tài sản, sau đó xác minh xem lá của bạn có phải là lá hợp lệ trong cây và gốc Merkle mà chúng tôi công bố hay không.

Ví dụ, trong Hình 1, người dùng có id là id_k sẽ tính hashk = hash("20" "15" "5" "id_k" "99821"), và dữ liệu khác trong khung hình vuông màu đỏ sẽ là xác minh đường dẫn Merkle. Một công cụ mã nguồn mở được cung cấp để người dùng thực hiện việc xác minh này.

Vì các lá của cây Merkle là hàm băm nên sẽ không có thông tin cá nhân nào của bạn bị rò rỉ cho người khác.

Cách xác minh:

1. Để xác minh xem số dư tài sản trong tài khoản của bạn đã được đưa vào dưới dạng lá Merkle zk-STARK hay chưa, hãy đăng nhập vào tài khoản OKX, truy cập "Kiểm toán" để xem các lần kiểm toán gần đây, bấm vào "Chi tiết" để xem dữ liệu kiểm toán của bạn.

2. Lấy dữ liệu bạn cần để xác minh thủ công bằng cách bấm vào "Sao chép dữ liệu".

3. Sau khi bấm vào "Sao chép dữ liệu", hãy mở trình soạn thảo văn bản (ví dụ: sử dụng notebook), sau đó dán và lưu chuỗi JSON dưới dạng tệp. Tệp phải kết thúc bằng tên "_inclusion_proof.json." Chuỗi JSON chứa số dư tài khoản của bạn và ảnh chụp nhanh đường dẫn Merkle, sau đó lưu tệp vào một thư mục mới.

Văn bản JSON được hiển thị như sau:

{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
“bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43”
]
}
}

4. Tải xuống công cụ xác minh mã nguồn mở OKX zk-STARKValidator

5. Lưu công cụ xác minh mã nguồn mở OKX zk-STARKValidatorvà tệp chuỗi JSON cùng nhau trong thư mục mới từ bước 3. Trong ví dụ này: chúng tôi lưu công cụ cũng như tệp dữ liệu trong thư mục “Tải xuống”, đặt tên là proof-of-reserves (bằng chứng dự trữ), được hiển thị như sau:

6. Mở zk-STARKValidator, nó sẽ tự động chạy tệp chuỗi JSON mà bạn đã lưu trong thư mục.

7. Kiểm tra kết quả

• Nếu xác minh thành công, kết quả "Xác thực đưa vào thành công" sẽ hiển thị:

  

• Nếu xác minh không thành công, kết quả "Xác thực đưa vào không thành công" sẽ hiển thị:

  

2.2 Xác minh Tổng số dư zk-STARK và Ràng buộc không âm

Cách xác minh:

Để xác minh và chứng minh rằng tài sản mà chúng tôi tuyên bố nắm giữ là đúng và không có người dùng nào nắm giữ vốn chủ sở hữu ròng âm, hãy truy cập "[Tệp kiểm toán] của chúng tôi(https://www.okx.com/proof-of-reserves/download?tab=liabilities)" và tải xuống các tệp "zk-STARK" trong Báo cáo trách nhiệm pháp lý, sau đó lưu tệp đó vào một thư mục mới.

Giải nén tệp đã tải xuống và sẽ có một thư mục "sum proof data", bao gồm hàng nghìn thư mục nhánh và một thư mục thân cây. Mỗi thư mục chứa hai tệp JSON có tên "sum_proof.json" và “sum_value.json”.

Tải xuống công cụ xác minh mã nguồn mở OKX zk-STARKValidator

Lưu công cụ xác minh mã nguồn mở OKX zk-STARKValidator và thư mục "sum proof data" trong thư mục vừa tạo ở bước 1. Trong ví dụ này: chúng tôi lưu công cụ và tệp dữ liệu trong thư mục “Tải xuống”, đặt tên là proof-of-reserves (bằng chứng dự trữ), được hiển thị như sau:

Mở zk-STARKValidator, nó sẽ tự động chạy "sum proof data" mà bạn đã lưu trong thư mục.

Kiểm tra kết quả

Nếu xác minh thành công, kết quả "Xác thực tổng và ràng buộc không âm thành công" sẽ hiển thị:

Nếu xác minh không thành công, kết quả "Xác thực tổng và ràng buộc không âm không thành công" sẽ hiển thị: