Tác giả: Sao Lý

Bài viết này chỉ nhằm mục đích học hỏi và trao đổi trong ngành và không mang tính chất tham khảo đầu tư. Nếu cần trích dẫn, vui lòng ghi rõ nguồn. Để in lại, vui lòng liên hệ với nhóm IOSG để được cấp phép và hướng dẫn in lại. Đặc biệt cảm ơn tác giả Star Li về nội dung!

Công nghệ chứng minh không có kiến ​​thức ngày càng được sử dụng nhiều trong chứng minh quyền riêng tư, bằng chứng tính toán, bằng chứng đồng thuận, v.v. Trong khi tìm kiếm các kịch bản ứng dụng ngày càng tốt hơn, nhiều người dần dần phát hiện ra rằng hiệu suất chứng minh không có kiến ​​thức là một điểm nghẽn. Nhóm Trapdoor Tech đã bắt đầu nghiên cứu chuyên sâu về công nghệ chứng minh không có kiến ​​thức vào năm 2019 và đang khám phá các giải pháp tăng tốc bằng chứng không có kiến ​​thức hiệu quả. GPU hay FPGA là những nền tảng tăng tốc phổ biến hiện có trên thị trường. Bài viết này bắt đầu bằng việc tính toán MSM và phân tích những ưu điểm cũng như nhược điểm của các phép tính chứng minh không có kiến ​​thức được tăng tốc bằng FPGA và GPU.

TL;DR

ZKP là một công nghệ có triển vọng rộng lớn cho tương lai. Ngày càng có nhiều ứng dụng bắt đầu áp dụng công nghệ chứng minh không có kiến ​​thức. Tuy nhiên, có nhiều thuật toán ZKP và các dự án khác nhau sử dụng các thuật toán ZKP khác nhau. Đồng thời, hiệu suất tính toán của bằng chứng ZKP tương đối kém. Bài viết này phân tích chi tiết thuật toán MSM, thuật toán cộng điểm đường cong elip, thuật toán nhân Montgomery, v.v. và so sánh sự khác biệt hiệu suất giữa GPU và FPGA trong phép cộng điểm đường cong BLS12_381. Nhìn chung, về mặt tính toán bằng chứng ZKP, những lợi thế ngắn hạn của GPU là tương đối rõ ràng, chẳng hạn như thông lượng cao, hiệu suất chi phí cao, khả năng lập trình, v.v. FPGA có những lợi thế nhất định về mức tiêu thụ điện năng. Về lâu dài, có thể có chip FPGA phù hợp cho tính toán ZKP, hoặc chip ASIC được tùy chỉnh cho ZKP.

Thuật toán ZKP phức tạp

ZKP là tên gọi chung của công nghệ chứng minh không có kiến ​​thức (Zero Knowledge Proof). Có hai loại chính: zk-SNARK và zk-STARK. Các thuật toán phổ biến hiện nay cho zk-SNARK là Groth16, PLONK, PLOOKUP, Marlin và Halo/Halo2. Việc lặp lại thuật toán zk-SNARK chủ yếu theo hai hướng: 1/có cần thiết lập đáng tin cậy hay không 2/hiệu suất của cấu trúc mạch. Ưu điểm của thuật toán zk-STARK là nó không yêu cầu thiết lập đáng tin cậy nhưng lượng tính toán xác minh là tuyến tính logarit.

Về việc áp dụng thuật toán zk-SNARK/zk-STARK, các thuật toán chứng minh không có kiến ​​thức được các dự án khác nhau sử dụng tương đối rải rác. Trong ứng dụng thuật toán zk-SNARK, vì thuật toán PLONK/Halo2 là phổ quát (không cần thiết lập đáng tin cậy) nên có thể ngày càng có nhiều ứng dụng.

PLONK chứng minh nỗ lực tính toán

Lấy thuật toán PLONK làm ví dụ để phân tích số lượng tính toán của bằng chứng PLONK.

Lượng tính toán của phần chứng minh PLONK bao gồm bốn phần:

1/ MSM - Phép nhân vô hướng. MSM thường được sử dụng để tính toán các cam kết đa thức.

2/ Tính toán NTT - Biến đổi đa thức giữa giá trị điểm và biểu diễn hệ số.

3/ Tính toán đa thức - Cộng, trừ, nhân, chia đa thức. Đánh giá đa thức (Evaluation) và vân vân.

4/ Circuit Syntheze - Tổng hợp mạch. Phần tính toán này liên quan đến kích thước/độ phức tạp của mạch.

Nói chung, lượng tính toán của phần Tổng hợp mạch mang tính phán đoán và logic vòng lặp nhiều hơn, mức độ song song tương đối thấp và phù hợp hơn cho việc tính toán CPU. Nói chung, gia tốc bằng chứng không có kiến ​​thức thường đề cập đến gia tốc tính toán của ba phần đầu tiên. Trong số đó, MSM có số lượng tính toán tương đối lớn nhất, tiếp theo là NTT.

MSM là gì

MSM (Phép nhân vô hướng) đề cập đến một chuỗi các điểm và vô hướng trên đường cong elip và tính điểm tương ứng với kết quả của việc cộng các điểm này.

Ví dụ, cho một chuỗi các điểm trên đường cong elip:

Cho một tập hợp cố định các điểm đường cong Elliptic từ một đường cong được chỉ định:

[G_1, G_2, G_3, ..., G_n]

Và hệ số ngẫu nhiên:

và các phần tử trường hữu hạn được lấy mẫu ngẫu nhiên từ trường vô hướng đã chỉ định:

[s_1, s_2, s_3, ..., s_n]

MSM là phép tính để có được điểm Q của đường cong Elliptic:

Q = \sum_{i=1}^{n}s_i*G_i

Ngành công nghiệp thường sử dụng thuật toán Pippenger để tối ưu hóa tính toán MSM. Chúng ta hãy xem xét kỹ hơn sơ đồ nguyên lý của quá trình thuật toán Pippenger:

Quá trình tính toán của thuật toán Pippenger được chia thành 2 bước:

1/ Vô hướng được chia thành Windows. Nếu Vô hướng là 256 bit và Cửa sổ là 8 bit thì tất cả Vô hướng được chia thành 256/8=32 Windows. Mỗi lớp Cửa sổ sử dụng một "Nhóm" để lưu trữ tạm thời các kết quả trung gian. GW_x là điểm của kết quả tích lũy trên một lớp. Việc tính toán GW_x cũng tương đối đơn giản. Mỗi Scalar trong một lớp lần lượt được duyệt và giá trị của lớp Scalar được sử dụng làm Chỉ mục và G_x tương ứng được thêm vào bit Buckets tương ứng. Trên thực tế, nguyên tắc tương đối đơn giản. Nếu các hệ số của phép cộng hai điểm bằng nhau thì cộng hai điểm trước rồi thực hiện phép cộng vô hướng. Không cần thực hiện hai phép cộng vô hướng cho hai điểm rồi cộng. chúng lên.

2/ Số điểm tính theo mỗi Cửa sổ được tích lũy thông qua việc cộng kép để có được kết quả cuối cùng.

Thuật toán Pippenger cũng có nhiều thuật toán tối ưu hóa biến dạng. Trong mọi trường hợp, phép tính cơ bản của thuật toán MSM là phép cộng điểm trên đường cong elip. Các thuật toán tối ưu hóa khác nhau tương ứng với các số cộng điểm khác nhau.

Thêm điểm đường cong Elliptic

Bạn có thể xem các thuật toán khác nhau để cộng điểm trên các đường cong elip có dạng "Weierstrass ngắn" từ trang web này.

http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl

Giả sử tọa độ Projective của hai điểm lần lượt là (x1, y1, z1) và (x2, y2, z2) thì kết quả cộng điểm (x3, y3, z3) có thể được tính thông qua công thức tính toán sau.

Lý do đưa ra quy trình tính toán chi tiết là để cho thấy toàn bộ quá trình tính toán chủ yếu là các phép toán số nguyên. Độ rộng bit của một số nguyên phụ thuộc vào các tham số của đường cong elip. Cho độ rộng bit của một số đường cong elip phổ biến:

BN256 - 256 bit BLS12_381 - 381 bit BLS12_377 - 377 bit

Đặc biệt lưu ý rằng các phép toán số nguyên này là các phép toán trên trường modulo. Phép cộng/trừ mô-đun tương đối đơn giản. Hãy tập trung vào nguyên tắc và cách thực hiện phép nhân mô-đun.

Phép nhân mô-đun (Modular Muliplication)

Cho hai giá trị trên miền mô-đun: x và y. Các phép tính nhân mô-đun tham khảo x*y mod p. Lưu ý rằng độ rộng bit của các số nguyên này là độ rộng bit của đường cong elip. Thuật toán cổ điển cho phép nhân mô-đun là Phép nhân Montgomery. Trước khi thực hiện phép nhân Montgomery, số nhân cần được chuyển đổi sang biểu diễn Montgomery:

Công thức nhân Montgomery như sau:

Có nhiều thuật toán triển khai phép nhân Montgomery: CIOS (Quét toán hạng tích hợp thô), FIOS (Quét toán hạng tích hợp tinh tế) và FIPS (Quét sản phẩm tích hợp tinh tế), v.v. Bài viết này không đi sâu vào chi tiết thực hiện các thuật toán khác nhau và bạn đọc quan tâm có thể tự nghiên cứu.

Để so sánh sự khác biệt về hiệu năng giữa FPGA và GPU, phương pháp triển khai thuật toán cơ bản nhất được chọn:

Nói một cách đơn giản, thuật toán nhân mô-đun có thể được chia thành hai phép tính: phép nhân số lớn và phép cộng số lớn. Sau khi hiểu logic tính toán của MSM, bạn có thể chọn hiệu suất nhân mô-đun (thông lượng) để so sánh hiệu suất của FPGA và GPU.

Quan sát và suy nghĩ

Theo thiết kế FPGA như vậy, có thể ước tính rằng toàn bộ VU9P có thể cung cấp thông lượng tại các điểm đường cong elip BLS12_381. Phép cộng một điểm (phương pháp add_mix) yêu cầu khoảng 12 phép nhân mô-đun. Đồng hồ hệ thống của FPGA là 450M.

Theo cùng một thuật toán nhân/cộng modulo mô-đun, sử dụng cùng một thuật toán cộng điểm, Troughput cộng điểm của Nvidia 3090 (có tính đến các yếu tố truyền dữ liệu) vượt quá 500M/s. Tất nhiên, toàn bộ quá trình tính toán bao gồm nhiều thuật toán khác nhau. Có thể có một số thuật toán phù hợp với FPGA và một số thuật toán phù hợp với GPU. Lý do sử dụng cùng một thuật toán so sánh là để so sánh khả năng tính toán cốt lõi của FPGA và GPU.

Dựa trên các kết quả trên, hãy tóm tắt so sánh giữa GPU và FPGA về hiệu suất bằng chứng ZKP:

Tóm tắt

Ngày càng có nhiều ứng dụng bắt đầu áp dụng công nghệ chứng minh không có kiến ​​thức. Tuy nhiên, có nhiều thuật toán ZKP và các dự án khác nhau sử dụng các thuật toán ZKP khác nhau. Đánh giá từ kinh nghiệm kỹ thuật thực tế của chúng tôi, FPGA là một lựa chọn, nhưng hiện tại GPU là một lựa chọn tiết kiệm chi phí. FPGA ưu tiên tính toán xác định và có lợi thế về độ trễ cũng như mức tiêu thụ điện năng. GPU có khả năng lập trình cao, có khung tính toán hiệu năng cao tương đối hoàn thiện, có chu kỳ lặp lại phát triển ngắn và thích các kịch bản thông lượng hơn.