Fast Fourier Transforms (ZKP 이해를 위한)

• FT

• Background

• Fast Fourier Transforms

FT

zkEVM에 대해 공부하면서 FFT(Fast Fourier Transform, 빠른 푸리에 변환)가 굉장히 많이 등장했다.

학교 수업에서 얼핏 들어본 적은 있었지만 제대로 알고 있지 않아 이 참에 이해하여 정리해보고자 한다.

 

FFT에 대해 찾아보면서 수학뿐만 아니라 굉장히 많은 영역에서 쓰인다는 것을 알았다.

주로 신호처리, 음성, 통신 분야에서 사용하는 개념이고, 수학 분야에서 응용을 했다고 이해했다.

 

푸리에 변환이란 시간에 대한 신호 함수를 주파수에 대한 식으로 변환하는 것을 말한다. 노이즈가 섞인 주파수에서 특정 주파수를 추출해낼 수 있다. 

 

하지만 나는 컴퓨터과학 전공자로서, 컴퓨터 과학에서 사용하는 푸리에 변환에 초점을 맞출 것이며, 그 중에서도 zkEVM을 이해하기 위한 Background로서의 FFT를 다룰 것이다.

 

Background

앞서 다뤘듯이, 본래의 푸리에 변환은 주파수 도메인과 시간 도메인의 데이터를 전환하는 것으로 설명된다.

더 구체적으로 말하자면, 푸리에 변환을 하게 되면 서로 다른 주파수와 진폭을 가진 사인파 모음이 생성되고, 이를 다 더하면 원래 데이터에 근접한다는 것이다.

 

이게 무슨 말인가 싶을 수도 있지만, 쉽게 말해서 특정 데이터 조각을 모아서 본래 데이터를 유추할 수 있다는 의미이다.

 

우리가 다룰 푸리에 변환도 실수 또는 복소수에 대한 연속 푸리에 변환이 아닌 finite field에 대한 DFT(Discrete Fourier Transform)라는 것을 제외하면 비슷한 원리의 알고리즘이다.

 

주파수 도메인과 시간 도메인간의 전환이 아닌 multi-point polynomial evaluation 과 그것의 반대인 polynomial interpolation 간의 전환을 다룰 것이다.

 

쉽게 말해, multi-point polynomial evaluation를 통해 본래 다항식을 recovering 하고, 반대로 본래 다항식을 통해 multi-pointpolynomial evaluation 를 계산한다는 것이다.

 

예를 들어, 모듈러 5인 소수 field에서 다항식이 아래와 같다고 가정해보자.

$$y=x^2+3$$

 

x = [0,1,2] 에서 [3,4,2]로 계산된다. ( [3,4,7]이 아닌 이유는 모듈러 5 소수 field이기 때문에 7%5 = 2가 된다)

또한, [3,4,2]의 값과 [0,1,2]값을 통해 우리는 본래 다항식인 $$y=x^2+3$$ 를 recover하기 위해 사용할 수 있다.

 

Multi-point evaluation와 Interpolation은 O(N^2) 시간안에 수행할 수 있다.

Multi-point evaluation은 간단한데 각 점에서 다항식을 개별적으로 계산하면 된다. 아래는 python code이다.

 

def eval_poly_at(self, poly, x, modulus):
    y = 0
    power_of_x = 1
    for coefficient in poly:
        y += power_of_x * coefficient
        power_of_x *= x
    return y % modulus

 

해당 알고리즘은 O(N) 복잡도를 가지고 있다.

각 점에서의 다항식을 계산했기 때문에 이 계산을 N개의 다른 점에서 계산하면 O(N^2)의 시간복잡도를 가진다.

 

라그랑주 보간법을 사용하면 같은 결과물을 낼 수 있지만 좀 더 복잡하다.

푸리에 변환을 공부하면서 라그랑주 보간법을 모를 수가 없는데 이 부분은 추후에 글을 쓰도록 해보겠다.

 

핵심은 DFT, 라그랑주 보간법을 사용하면 O(N^2)의 시간 복잡도를 가지고 있다는 것이다.

FFT는 이 시간복잡도를 개선하고자 나온 알고리즘으로 O(nlogn)의 복잡도를 갖는다.

 

Fast Fourier Transforms

FFT 알고리즘을 사용하기 위해선 tradeoff가 있다.

더 빠른 알고리즘이지만, 임의의 필드와 임의의 도메인을 선택할 수 없다는 것이다.

 

라그랑주 보간을 사용하면 원하는 x 좌표와 y 좌표, 원하는 필드를 선택할 수 있고, 이를 통과하는 다항식을 얻을 수 있다.

FFT를 사용하는 경우, finite field(유한체)를 사용해야 하며 도메인은 field의 multiplicative subgroup(즉, 일부 "generator" 값의 거듭제곱의 값)이어야 한다.

multiplicative subgroup, generator가 무슨 말인가 싶을 수도 있겠지만 예를 들어 설명하면 와닿을 수 있을 것이다.

 

먼저 337 모듈러 계산을 한 정수들의 유한체를 정의해보자. 도메인은 [1, 85, 148, 111, 336, 252, 189, 226]이 된다. 

해당 값은 85를 제곱한 값으로, 예를 들면 85^3 % 337 = 111 로 된다. 226이 마지막 요소인데, 85^8 % 337 = 1으로 순환되기 때문이다.

 

[1, 85, 148, 111, 336, 252, 189, 226]이 multiplicative subgroup이 되고, 85는 generator가 된다.

 

또한, multiplicative subgroup은 항상 2^n의 요소를 가지고 있다.

 

우린 재귀(recursion)를 사용하여 O(nlogn)의 복잡도로 만들 것이다.

 

MergeSort 알고리즘을 잘 알고 있다면, FFT도 결국 원리가 비슷하다.

 

 

이제야 본론인데 생각보다 쓰는게 오려걸려서 일단 여기까지만 쓰겠습니다,,

 

 

 

출처 : https://vitalik.ca/general/2019/05/12/fft.html