FPGA 및 GPU 가속 영지식 증명 컴퓨팅의 장점과 단점을 이해하는 기사
원작자: 스타 리
원본 출처: IOSG Ventures
영지식 증명 기술은 프라이버시 증명, 계산 증명, 합의 증명 등과 같이 점점 더 널리 사용되고 있습니다. 더 많고 더 나은 애플리케이션 시나리오를 찾는 동안 많은 사람들은 영지식 증명이 성능이 병목 현상임을 증명한다는 것을 점차 발견했습니다. 트랩도어 테크팀은 2019년부터 영지식 증명 기술을 심도 있게 연구하고 효율적인 영지식 증명 가속화 솔루션을 탐색해왔습니다. GPU 또는 FPGA는 현재 시장에 나와 있는 비교적 일반적인 가속 플랫폼입니다. 이 기사는 MSM의 계산으로 시작하여 FPGA 및 GPU 가속 영지식 증명 계산의 장단점을 분석합니다.
TL;DR
ZKP는 미래에 대한 전망이 넓은 기술입니다. 점점 더 많은 애플리케이션이 영지식 증명 기술을 채택하고 있습니다. 그러나 많은 ZKP 알고리즘이 있으며 다양한 프로젝트에서 서로 다른 ZKP 알고리즘을 사용합니다. 동시에 ZKP 증명의 계산 성능은 상대적으로 좋지 않습니다. 본 논문에서는 MSM 알고리즘, 타원 곡선 점 가산 알고리즘, 몽고메리 곱셈 알고리즘 등을 상세하게 분석하고, BLS 12_381 곡선 점 가산에서 GPU와 FPGA의 성능 차이를 비교한다. 일반적으로 ZKP 증명 컴퓨팅 측면에서 단기 GPU는 높은 처리량, 높은 비용 성능, 프로그래밍 가능성 등 분명한 이점이 있습니다. 상대적으로 FPGA는 전력 소비 측면에서 특정 이점이 있습니다. 장기적으로는 ZKP 계산에 적합한 FPGA 칩이나 ZKP에 맞춤화된 ASIC 칩이 있을 수 있습니다.
ZKP 알고리즘은 복잡합니다.
ZKP는 Zero Knowledge Proof 기술(Zero Knowledge Proof)의 총칭입니다. 주로 zk-SNARK와 zk-STARK의 두 가지 분류가 있습니다. zk-SNARK의 현재 공통 알고리즘은 Groth 16, PLONK, PLOOKUP, Marlin 및 Halo/Halo 2입니다. zk-SNARK 알고리즘의 반복은 주로 두 가지 방향을 따릅니다. 1/신뢰할 수 있는 설정이 필요한지 여부 2/회로 구조의 성능. zk-STARK 알고리즘의 장점은 신뢰할 수 있는 설정이 필요하지 않지만 검증 계산량이 로그 선형적이라는 것입니다.
zk-SNARK/zk-STARK 알고리즘의 적용에 관한 한, 서로 다른 프로젝트에서 사용되는 영지식 증명 알고리즘은 상대적으로 분산되어 있습니다. zk-SNARK 알고리즘의 적용에서 PLONK/Halo 2 알고리즘은 보편적이기 때문에(신뢰할 수 있는 설정이 필요하지 않음) 점점 더 많은 적용이 있을 수 있습니다.
PLONK는 계산량을 증명합니다.
PLONK 알고리즘을 예로 들어 PLONK 증명의 계산량을 분석합니다.
PLONK 증명 부분의 계산량은 네 부분으로 구성됩니다.
1/ MSM - 다중 스칼라 곱셈. MSM은 종종 다항식 약속을 계산하는 데 사용됩니다.
2/ NTT 계산 - 포인트 값과 계수 표현 사이의 다항식 변환.
3/ 다항식 계산 - 다항식 덧셈, 뺄셈, 곱셈 및 나눗셈. 다항식 평가(Evaluation) 등.
4/ 회로 합성 - 회로 합성. 이 부분의 계산은 회로의 규모/복잡도와 관련이 있습니다.
일반적으로 Circuit Synthesize 부분의 계산량은 판단과 루프 논리가 많고 병렬도가 상대적으로 낮아 CPU 계산에 더 적합합니다. 일반적으로 제로 지식 증명 가속은 일반적으로 처음 세 부분의 계산 가속을 나타냅니다. 그 중 MSM의 계산량이 상대적으로 가장 많고 그 다음이 NTT이다.
What's MSM
MSM(Multiple Scalar Multiplication)은 타원 곡선에서 주어진 일련의 점과 스칼라를 참조하고 이러한 점을 더한 결과에 해당하는 점을 계산합니다.
예를 들어 타원 곡선에 일련의 점이 있다고 가정합니다.
Given a fixed set of Elliptic curve points from one specified curve:
[G_ 1, G_ 2, G_ 3, ..., G_n]
랜덤 계수:
and a randomly sampled finite field elements from specified scalar field:
[s_ 1, s_ 2, s_ 3, ..., s_n]
MSM is the calculation to get the Elliptic curve point Q:
Q = \sum_{i= 1 }^{n}s_i*G_i
업계에서는 일반적으로 MSM 계산을 최적화하기 위해 Pippenger 알고리즘을 채택합니다. Pippenger 알고리즘 프로세스의 개략도를 자세히 살펴보십시오.
Pippenger 알고리즘의 계산 프로세스는 두 단계로 나뉩니다.
1/ Scalar는 Windows로 분할됩니다. Scalar가 256비트이고 Window가 8비트이면 모든 Scalar는 256/8 = 32 Windows로 나뉩니다. Window의 각 레이어는 "버킷"을 사용하여 중간 결과를 임시로 저장합니다. GW_x는 한 레이어의 누적 결과 지점입니다. GW_x를 계산하는 방법도 비교적 간단하여 한 레이어의 각 Scalar를 차례로 순회하고 Scalar 레이어의 값을 Index로 하여 해당 Bucket의 비트에 해당 G_x를 더합니다. 사실 원리는 비교적 간단한데, 두 점을 더하는 계수가 같다면 스칼라를 더하기 전에 두 점을 두 번 더하는 것이 아니라 두 점을 먼저 더한 다음 다시 스칼라를 더하면 된다.
2/ 각 창에서 계산된 포인트는 이중 추가로 누적되어 최종 결과를 얻습니다.
Pippenger의 알고리즘에도 많은 변형 최적화 알고리즘이 있습니다. 어쨌든 MSM 알고리즘의 기본 계산은 타원 곡선에 점을 추가하는 것입니다. 다른 최적화 알고리즘은 추가된 포인트의 다른 수에 해당합니다.
타원 곡선 점 추가(Point Add)
이 사이트에서 "짧은 Weierstrass" 형식의 타원 곡선에 점을 추가하는 다양한 알고리즘을 볼 수 있습니다.
http://www.hyperelliptic.org/EFD/g 1 p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
두 점의 사영 좌표를 각각 (x 1, y 1, z 1), (x 2, y 2, z 2)라고 가정하면 점 가산 결과(x 3, y 3)는 다음과 같이 계산할 수 있습니다. 다음 계산식 , z 3).
계산 과정을 자세히 설명하는 이유는 전체 계산 과정이 대부분 정수 연산임을 보여주기 위함입니다. 정수의 비트 폭은 타원 곡선의 매개변수에 따라 다릅니다. 몇 가지 일반적인 타원 곡선의 비트 너비를 제공하십시오.
BN 256 - 256 bits
BLS 12 _ 381 - 381 bits
BLS 12 _ 377 - 377 bits
특히 이러한 정수 연산은 모듈로 필드에 대한 연산입니다. 모듈러 덧셈/모듈러스 뺄셈은 비교적 간단하며 모듈러 곱셈의 원리와 구현에 중점을 둡니다.
모듈러 곱셈
모듈로 필드에 x와 y라는 두 가지 값이 주어집니다. 모듈러 곱셈 계산은 x*y mod p를 참조합니다. 이러한 정수의 비트 폭은 타원 곡선의 비트 폭입니다. 모듈러 곱셈의 고전적인 알고리즘은 Montgomery Multiplication입니다. 몽고메리 곱셈을 수행하기 전에 피승수를 몽고메리 표현으로 변환해야 합니다.
몽고메리 곱셈을 계산하는 공식은 다음과 같습니다.
몽고메리 곱셈 구현 알고리즘에는 CIOS(Coarsely Integrated Operand Scanning), FIOS(Finely Integrated Operand Scanning), FIPS(Finely Integrated Product Scanning) 등이 있습니다. 이 기사에서는 다양한 알고리즘 구현에 대한 세부 정보를 자세히 소개하지 않으며 관심 있는 독자는 자체 조사를 수행할 수 있습니다.
FPGA와 GPU의 성능 차이를 비교하려면 가장 기본적인 알고리즘 구현 방법을 선택하십시오.
간단히 말해서, 모듈식 곱셈 알고리즘은 큰 수 곱셈과 큰 수 덧셈의 두 가지 계산으로 더 나눌 수 있습니다. MSM의 계산 논리를 이해한 후 모듈 곱셈의 성능(처리량)을 선택하여 FPGA와 GPU의 성능을 비교할 수 있습니다.
관찰하고 생각하다
이러한 FPGA 설계에서 전체 VU 9 P는 BLS 12 _ 381 타원 곡선 지점에서 처리량을 제공할 수 있다고 추정할 수 있습니다. 포인트 추가(add_mix 방법)에는 약 12개의 모듈식 곱셈이 필요합니다. FPGA의 시스템 클럭은 450M입니다.
동일한 모듈식 곱셈/모듈식 덧셈 알고리즘에서 동일한 포인트 추가 알고리즘을 사용하면 Nvidia 3090의 포인트 플러스 Troughput(데이터 전송 요소 고려)이 500M/s를 초과합니다. 물론 전체 계산에는 다양한 알고리즘이 포함되며 일부 알고리즘은 FPGA에 적합하고 일부 알고리즘은 GPU에 적합합니다. 동일한 알고리즘 비교를 사용하는 이유는 FPGA와 GPU의 핵심 컴퓨팅 기능을 비교하기 위해서입니다.
요약하다
요약하다
점점 더 많은 애플리케이션이 영지식 증명 기술을 채택하고 있습니다. 그러나 많은 ZKP 알고리즘이 있으며 다양한 프로젝트에서 서로 다른 ZKP 알고리즘을 사용합니다. 실제 엔지니어링 경험에서 FPGA는 옵션이지만 GPU는 현재 비용 효율적인 옵션입니다. FPGA는 대기 시간과 전력 소비의 이점이 있는 결정론적 컴퓨팅을 선호합니다. GPU는 프로그래밍 가능성이 높고 상대적으로 성숙한 고성능 컴퓨팅 프레임워크를 가지고 있으며 개발 반복 주기가 짧고 처리량 시나리오를 선호합니다.
