MSM 이해하기 (1)— Multi-scalar multiplication & Pippenger algorithm

1편에서는 Multi scalar multiplication problem이 무엇인지 알아보고, 대표적 알고리즘인 pippenger algorithm에 대해 알아봅니다.

2편에서는 Pippenger algorithm을 최적화하기 위한 여러 시도들에 대해서 알아봅니다.

(유한체와 군, 타원곡선에 대한 아주 기초적인 이해가 필요합니다. MSM이 애매쓰할때 읽어보세요(우하하하하하))

1. Multi Scalar Multiplication Problem?

문제 정의

어떤 group G가 있어서, 이 group의 order가 2^b라고 하자.

이 때 group의 원소들과 0~2^b-1 범위의 scalar 값들을 곱하는 연산을 수행하여 G를 얻고 싶다.

MSM Problem : G를 구할 때, group operation의 갯수를 최소화하는 문제

유한체 위의 타원곡선에서

유한체 위의 타원곡선에서는 MSM problem이 더 중요한 문제가 된다. 그 이유는 scalar multiplication이란 곧 여러 번의 addition이고, 타원곡선에서의 point addition은 비싸기 때문이다. 타원곡선에서 서로 다른 두 점의 point addition은 다음과 같이 정의된다.

위 정의를 보면 s를 구하는 과정에서 나눗셈이 필요하다는 것을 알 수 있다. 그런데 유한체에서의 나눗셈은 연산량이 많고, 특히 큰 p에 대해서 비싼 연산이다. 유한체에서의 나눗셈에는 페르마의 소정리나 확장 유클리드 알고리즘 등 역수를 구하는 특별한 알고리즘을 사용하게 되는데, 예를 들어 페르마의 소정리를 생각해 보면 역수를 구하는 데에 p-2번의 곱셈을 필요로 한다. 영지식증명에서 많이 쓰이는 타원곡선인 BLS12–381 curve에서 p는 대략 381bit로 나타내어지는 숫자인데, 이런 경우 제곱에 엄청난 시간이 소요될 것이다.

정리하자면 타원곡선에서의 MSM은 덧셈 연산의 갯수를 최소화하는 문제이며, 타원곡선에서 덧셈 연산이 비싸기 때문에(유한체의 나눗셈이 비싸기 때문) 중요한 문제가 된다. 보다 실제적인 예로, 영지식증명에서의 groth16은 proving 과 setup 과정에서 MSM을 수행하는데, 이것이 영지식증명의 bottleneck으로 알려져 있다. 아래 그림은 필자의 컴퓨터에서 groth16 알고리즘을 돌려 만든 flame graph인데, create_proof 부분을 보면 대부분의 시간을 variable based MSM을 위해 소모하고 있다는 사실을 알 수 있다. 따라서 이 부분의 MSM을 효율적으로 수행하는 것이 중요한 과제이다.

create_proof의 flame graph

generate_parameters의 flame graph

Naive Approach: Double and Add

아주 간단하게 생각해 보면 double and add 방식을 생각해 볼 수 있다. Double and add algorithm을 사용했을 때의 시간복잡도를 계산해 보자. 앞서 scalar는 0~2^b-1 범위라고 했기 때문에, b bit로 표현 가능하다. B bit scalar의 binary representation에서 0과 1이 균등하게 등장한다 가정했을 때 평균 1.5b 번의 덧셈이 scalar마다 발생한다. Scalar는 n개이므로 총 시간복잡도는 O(1.5bn)이다. ZKP에서 자주 사용되는 pairing-friendly curve 중 하나인 BLS12–381 curve가 대략 2²⁵⁵ 정도의 위수를 가지므로, 이 때는 383n 정도의 + 연산이 필요하게 되는 것이다.

2. Pippenger Algorithm

앞서 설명한 MSM problem을 위한 algorithm 중 가장 대표적인 것이 Pippenger algorithm이다. 글과 그림으로 설명하겠지만, 구현이 궁금하다면 여기에서 확인할 수 있다.

Pippenger algorithm의 아이디어는 간단하다. Scalar를 쪼개고, 각 부분에 대해 MSM을 수행한 다음, 합치는 것이다. 당연히 이것만으로는 성능향상이 발생하지 않는다. 핵심은 각 부분의 MSM을 아주 효율적으로 수행하는 것이다.

Step 1. B bit MSM을 c bit MSM로 쪼갠다.

출처: 자체 제작

어떤 c를 선택하여 scalar의 binary representation, 즉 b bit를 쪼갠다고 해 보자. b=18, c=3일 때, s1이 234567이라고 하면 다음과 같이 쪼개질 것이다.

위와 같이 n개의 scalar를 모두 쪼갠 다음, 각 부분에 대해 Step 2를 수행한다.

Step 2. C bit MSM을 수행한다. (ceil(b/c)회)

출처: 자체 제작

Scalar 값들을 모두 쪼개고 나면 위와 같은 그림이 된다. 보다시피, 세로로 보면 c bit의 작은 MSM이 생겼다는 사실을 알 수 있다. n을 12라고 가정하면, 아래와 같은 MSM이 b/c개 생긴 것이다.

이제 각 MSM을 계산하기 위해, bucket method를 이용하자. 예를 들기 위해 T1이 다음과 같은 모양이라고 가정하자.

1. 모든 항에 대해 scalar값으로 bucket을 결정한다. 예를 들어, g1과 g9는 scalar가 7이기 때문에 bucket 7번으로 가야 한다.

출처: 이것을 바탕으로 재구성

2. Bucket 각각을 합하여 S1 ~ S7을 구한다. 예를 들어, S3 = g2 + g7이다.

출처: 이것을 바탕으로 재구성

3. S1~S7에 bucket number를 곱한 뒤 합하여 T1을 구한다. 이 때, 다음과 같이 계산하면 덧셈 연산을 줄일 수 있다. 이전에 더한 값에 이번에 새로 더해진 값을 더해 더하면 되기 때문이다.

출처: 이것을 바탕으로 재구성

Step 3. C-bit MSM을 합쳐서 b-bit MSM에 대한 답으로 만든다.

출처: 자체제작

Step2의 결과, b/c개의 MSM 결과가 도출되었다. 이제 이것을 모두 합해서 G로 만들면 된다. 이 때, a(i, 1)은 MSB, a(i, 6)은 LSB이므로, Ti를 더하기 전 c회 doubling 작업을 해 주어야 한다.

Pippenger Algorithm의 시간복잡도

Pippenger algorithm의 시간복잡도를 계산해 보자. 우선 가장 inner loop에 해당하는 Step2의 c bit MSM에는 대략 (n+2^c-2) 정도의 덧셈 연산이 필요하다. 우선 Step2–1과 2–3을 생각해 보면, 전체 버킷에 들어오는 원소의 수는 n개인데, 그 중 각 버킷에 맨 처음 들어오는 2^c-1개 원소는 덧셈이 아닌 할당을 수행하므로 총 필요한 연산의 수는 O(n-(2^c-1))이다. 다음으로 Step2–3를 생각해 보면, O(2(2^c-2) +1) 회의 덧셈 연산이 필요하다. 따라서 하나의 c bit MSM을 계산하는 데에 필요한 덧셈 연산의 횟수는 대략 O(n+2^c)이고, b/c개의 c bit MSM을 계산하므로 총 O((n+2^c)*b/c)의 시간이 소모된다.

시간복잡도는 c의 값에 따라 달라지므로, c 값을 잘 선택하는 것도 중요하다. 이론적으로는 log(n)이 최적이지만, arkworks의 groth16 구현에서는 ln(n) + 2 를 사용하고 있다. 명확한 설명은 찾을 수 없었고, 값이 애매하다는 점에서 아마 실험적으로 최적값을 찾아낸 것으로 보인다. 실제로 알고리즘의 이론적 최적값은 무한한 리소스를 가정하고 계산된 것이고, 실제 환경에서의 최적값과는 다를 수 있다. 캐시, 공간복잡도 등 다양한 요인이 개입할 수 있기 때문이다.