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 elliptic, thuật toán nhân Montgomery, v.v. và so sánh sự khác biệt về hiệu suất giữa GPU và FPGA trong phép cộng điểm đường cong BLS12_381.
Được viết bởi: Star Li
Công nghệ bằng chứng không kiến thức ngày càng được sử dụng rộng rãi, chẳng hạn như bằng chứng về 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 phát hiện ra rằng bằng chứng không có kiến thức chứng minh rằng hiệu suất là một nút cổ chai. Nhóm Trapdoor Tech đã nghiên cứu sâu về công nghệ bằng chứng không có kiến thức kể từ năm 2019 và đã khám phá các giải pháp tăng tốc hiệu quả bằng chứng không có kiến thức. GPU hay FPGA là những nền tảng tăng tốc tương đối phổ biến hiện nay trên thị trường. Bài viết này bắt đầu với việc tính toán MSM, đồng thời phân tích các ưu điểm và nhược điểm của FPGA và GPU tăng tốc tính toán bằng chứng không kiến thức.
TL;DR
ZKP là một công nghệ có nhiều triển vọng trong tương lai. Ngày càng có nhiều ứng dụng áp dụng công nghệ bằng chứng không 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 về hiệu suất giữa GPU và FPGA trong phép cộng điểm đường cong BLS12_381. Nói chung, xét về tính toán bằng chứng ZKP, GPU ngắn hạn có những lợi thế rõ ràng, thông lượng cao, hiệu suất chi phí cao, khả năng lập trình, v.v. Nói một cách tương đối, 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 với 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à một thuật ngữ chung cho công nghệ Zero Knowledge Proof (Bằng chứng tri thức bằng không). Chủ yếu có hai phân loại: zk-SNARK và zk-STARK. Các thuật toán phổ biến hiện nay của 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/liệu 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à không yêu cầu thiết lập đáng tin cậy, nhưng số lượng tính toán xác minh là log-tuyến tính.
Đối với ứng dụng của 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 sử dụng bởi các dự án khác nhau tương đối phân tán. Trong ứng dụng của thuật toán zk-SNARK, vì thuật toán PLONK/Halo2 là phổ biến (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 hơn.
PLONK chứng minh lượng tính toán
Lấy thuật toán PLONK làm ví dụ, hãy phân tích lượng tính toán của chứng minh 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 đa thức - cộng, trừ, nhân, chia đa thức. Đánh giá đa thức (uation), v.v.
4/ Circuit Synthesize - tổng hợp mạch. Việc tính toán phần này liên quan đến quy mô/độ phức tạp của mạch.
Nói chung, số lượng tính toán trong phần Tổng hợp mạch là nhiều phán đoán và logic vòng lặp hơn, và mức độ song song tương đối thấp, 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 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ố đó, lượng tính toán của MSM 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 loạt các điểm và vô hướng nhất định trên đường cong elip và tính toán các điểm tương ứng với kết quả của việc thêm các điểm này.
Ví dụ: cho một loạt điểm trên đường cong elip:
Đưa ra 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à các hệ số ngẫu nhiên:
và một phần tử trường hữu hạn được lấy mẫu ngẫu nhiên từ trường vô hướng được chỉ định:
[s_1, s_2, s_3, ..., s_n]
MSM là phép tính để lấy điểm đường cong Elliptic Q:
Q = \sum_{i=1}^{n}s_i*G_i
Ngành này thường áp dụng thuật toán Pippenger để tối ưu hóa việc tính toán MSM. Hãy xem xét kỹ hơn sơ đồ quy trình của thuật toán Pippenger:
Quá trình tính toán của thuật toán Pippenger được chia thành hai bước:
1/ Chia vô hướng 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 Cửa sổ. Mỗi lớp của 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 tích lũy kết quả trên một lớp. Việc tính toán GW_x cũng tương đối đơn giản, nó lần lượt duyệt qua từng Scalar trong một lớp và sử dụng giá trị của lớp Scalar làm Chỉ mục, đồng thời thêm G_x tương ứng vào các Nhóm tương ứng. Trên thực tế, nguyên tắc tương đối đơn giản, nếu hệ số của phép cộng hai điểm giống nhau, thì cộng hai điểm trước rồi cộng vô hướng lần nữa, thay vì cộng hai điểm hai lần rồi mới cộng vô hướng.
2/ Điểm tính theo từng Cửa sổ được cộng dồn bằng cách cộng đôi để ra 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 các đ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 số lượng điểm được thêm khác nhau.
Thêm điểm vào đường cong elip (Thêm điểm)
Bạn có thể xem các thuật toán khác nhau để bổ sung điểm trên các đường cong elip với dạng "Weierstrass ngắn" từ trang web này.
Giả sử tọa độ Xạ ảnh của hai điểm lần lượt là (x1, y1, z1) và (x2, y2, z2), kết quả của phép cộng điểm (x3, y3, z3) có thể được tính theo công thức tính sau.
Sở dĩ đưa ra chi tiết quá trình tính toán là để chỉ ra rằng toàn bộ quá trình tính toán hầu hết là các phép toán số nguyên. Độ rộng bit của số nguyên phụ thuộc vào các tham số của đường cong elip. Đưa ra độ 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 chú ý 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, tập trung vào nguyên tắc và cách thực hiện phép nhân mô-đun.
模乘（Nhân mô-đun）
Cho hai giá trị trên một trường modulo: x và y. Phép tính nhân mô-đun đề cập đến 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 của phép nhân mô đun là phép nhân Montgomery (MontgomeryMulplication). Trước khi thực hiện phép nhân Montgomery, phép nhân cần được chuyển đổi thành biểu diễn Montgomery:
Công thức tính phép 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 được tích hợp thô), FIOS (Quét toán hạng được tích hợp tinh vi) và FIPS (Quét sản phẩm được tích hợp tinh vi), v.v. Bài viết này không giới thiệu chi tiết về các triển khai thuật toán khác nhau một cách sâu sắc 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 suất giữa FPGA và GPU, hãy chọn phương pháp thực hiện thuật toán cơ bản nhất:
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 của phép nhân mô-đun (Throughput) để 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. Một phép cộng điểm (cách cộng_trộn) 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 mô-đun, sử dụng cùng một thuật toán cộng điểm, Điểm cộng Troughput của Nvidia 3090 (xét 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 liên quan đến nhiều thuật toán khác nhau, một số thuật toán có thể 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 so sánh thuật toán tương tự 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 áp dụng công nghệ bằng chứng không 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. Từ kinh nghiệm kỹ thuật thực hành của chúng tôi, FPGA là một tùy chọn, nhưng GPU hiện là một tùy chọn hiệu quả về chi phí. FPGA thích điện toán xác định hơn, có lợi thế về độ trễ và 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 suất cao tương đối hoàn thiện và có chu kỳ lặp lại phát triển ngắn cũng như ưu tiên các kịch bản thông lượng.
Xem bản gốc
Nội dung chỉ mang tính chất tham khảo, không phải là lời chào mời hay đề nghị. Không cung cấp tư vấn về đầu tư, thuế hoặc pháp lý. Xem Tuyên bố miễn trừ trách nhiệm để biết thêm thông tin về rủi ro.
Một bài viết để hiểu những ưu điểm và nhược điểm của FPGA và GPU tăng tốc điện toán bằng chứng không kiến thức
Được viết bởi: Star Li
Công nghệ bằng chứng không kiến thức ngày càng được sử dụng rộng rãi, chẳng hạn như bằng chứng về 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 phát hiện ra rằng bằng chứng không có kiến thức chứng minh rằng hiệu suất là một nút cổ chai. Nhóm Trapdoor Tech đã nghiên cứu sâu về công nghệ bằng chứng không có kiến thức kể từ năm 2019 và đã khám phá các giải pháp tăng tốc hiệu quả bằng chứng không có kiến thức. GPU hay FPGA là những nền tảng tăng tốc tương đối phổ biến hiện nay trên thị trường. Bài viết này bắt đầu với việc tính toán MSM, đồng thời phân tích các ưu điểm và nhược điểm của FPGA và GPU tăng tốc tính toán bằng chứng không kiến thức.
TL;DR
ZKP là một công nghệ có nhiều triển vọng trong tương lai. Ngày càng có nhiều ứng dụng áp dụng công nghệ bằng chứng không 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 về hiệu suất giữa GPU và FPGA trong phép cộng điểm đường cong BLS12_381. Nói chung, xét về tính toán bằng chứng ZKP, GPU ngắn hạn có những lợi thế rõ ràng, thông lượng cao, hiệu suất chi phí cao, khả năng lập trình, v.v. Nói một cách tương đối, 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 với 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à một thuật ngữ chung cho công nghệ Zero Knowledge Proof (Bằng chứng tri thức bằng không). Chủ yếu có hai phân loại: zk-SNARK và zk-STARK. Các thuật toán phổ biến hiện nay của 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/liệu 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à không yêu cầu thiết lập đáng tin cậy, nhưng số lượng tính toán xác minh là log-tuyến tính.
Đối với ứng dụng của 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 sử dụng bởi các dự án khác nhau tương đối phân tán. Trong ứng dụng của thuật toán zk-SNARK, vì thuật toán PLONK/Halo2 là phổ biến (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 hơn.
PLONK chứng minh lượng tính toán
Lấy thuật toán PLONK làm ví dụ, hãy phân tích lượng tính toán của chứng minh 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 đa thức - cộng, trừ, nhân, chia đa thức. Đánh giá đa thức (uation), v.v.
4/ Circuit Synthesize - tổng hợp mạch. Việc tính toán phần này liên quan đến quy mô/độ phức tạp của mạch.
Nói chung, số lượng tính toán trong phần Tổng hợp mạch là nhiều phán đoán và logic vòng lặp hơn, và mức độ song song tương đối thấp, 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 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ố đó, lượng tính toán của MSM 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 loạt các điểm và vô hướng nhất định trên đường cong elip và tính toán các điểm tương ứng với kết quả của việc thêm các điểm này.
Ví dụ: cho một loạt điểm trên đường cong elip:
Đưa ra 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à các hệ số ngẫu nhiên:
và một phần tử trường hữu hạn được lấy mẫu ngẫu nhiên từ trường vô hướng được chỉ định:
[s_1, s_2, s_3, ..., s_n]
MSM là phép tính để lấy điểm đường cong Elliptic Q:
Q = \sum_{i=1}^{n}s_i*G_i
Ngành này thường áp dụng thuật toán Pippenger để tối ưu hóa việc tính toán MSM. Hãy xem xét kỹ hơn sơ đồ quy trình của thuật toán Pippenger:
Quá trình tính toán của thuật toán Pippenger được chia thành hai bước:
1/ Chia vô hướng 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 Cửa sổ. Mỗi lớp của 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 tích lũy kết quả trên một lớp. Việc tính toán GW_x cũng tương đối đơn giản, nó lần lượt duyệt qua từng Scalar trong một lớp và sử dụng giá trị của lớp Scalar làm Chỉ mục, đồng thời thêm G_x tương ứng vào các Nhóm tương ứng. Trên thực tế, nguyên tắc tương đối đơn giản, nếu hệ số của phép cộng hai điểm giống nhau, thì cộng hai điểm trước rồi cộng vô hướng lần nữa, thay vì cộng hai điểm hai lần rồi mới cộng vô hướng.
2/ Điểm tính theo từng Cửa sổ được cộng dồn bằng cách cộng đôi để ra 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 các đ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 số lượng điểm được thêm khác nhau.
Thêm điểm vào đường cong elip (Thêm điểm)
Bạn có thể xem các thuật toán khác nhau để bổ sung điểm trên các đường cong elip với dạng "Weierstrass ngắn" từ trang web này.
Giả sử tọa độ Xạ ảnh của hai điểm lần lượt là (x1, y1, z1) và (x2, y2, z2), kết quả của phép cộng điểm (x3, y3, z3) có thể được tính theo công thức tính sau.
Sở dĩ đưa ra chi tiết quá trình tính toán là để chỉ ra rằng toàn bộ quá trình tính toán hầu hết là các phép toán số nguyên. Độ rộng bit của số nguyên phụ thuộc vào các tham số của đường cong elip. Đưa ra độ rộng bit của một số đường cong elip phổ biến:
模乘（Nhân mô-đun）
Cho hai giá trị trên một trường modulo: x và y. Phép tính nhân mô-đun đề cập đến 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 của phép nhân mô đun là phép nhân Montgomery (MontgomeryMulplication). Trước khi thực hiện phép nhân Montgomery, phép nhân cần được chuyển đổi thành biểu diễn Montgomery:
Công thức tính phép 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 được tích hợp thô), FIOS (Quét toán hạng được tích hợp tinh vi) và FIPS (Quét sản phẩm được tích hợp tinh vi), v.v. Bài viết này không giới thiệu chi tiết về các triển khai thuật toán khác nhau một cách sâu sắc 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 suất giữa FPGA và GPU, hãy chọn phương pháp thực hiện thuật toán cơ bản nhất:
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 của phép nhân mô-đun (Throughput) để 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. Một phép cộng điểm (cách cộng_trộn) 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 mô-đun, sử dụng cùng một thuật toán cộng điểm, Điểm cộng Troughput của Nvidia 3090 (xét 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 liên quan đến nhiều thuật toán khác nhau, một số thuật toán có thể 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 so sánh thuật toán tương tự 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 áp dụng công nghệ bằng chứng không 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. Từ kinh nghiệm kỹ thuật thực hành của chúng tôi, FPGA là một tùy chọn, nhưng GPU hiện là một tùy chọn hiệu quả về chi phí. FPGA thích điện toán xác định hơn, có lợi thế về độ trễ và 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 suất cao tương đối hoàn thiện và có chu kỳ lặp lại phát triển ngắn cũng như ưu tiên các kịch bản thông lượng.