Circle STARKs
Differences Circle STARKs and STARKs
Circle STARKs
이번 아티클에서는 STARK에서 효율적으로 발전한 Circle STARKs에 대해 설명드리겠습니다.
Background
기존 STARK에서는 FFT 연산, FRI 프로토콜은 특정 대수적 구조에 영향을 받습니다.
\[\mathbb F_p\]의 곱셈 부분군의 위수가 2의 거듭제곱(\[2^k\])의 형태로 이루워져 있어야 합니다.
이런 형태를 FFT-friendly, smooth 하다고 표현합니다.
이것의 이유는 대부분 FFT(Cooley-Tukey FFT)와 FRI에서 분할정복 구조를 사용하기 때문입니다.
이러한 구조때문에 STARK에서 p를 고를 때 (\[2^k|p-1\])을 만족해야 합니다. 하지만 일부 수학적 계산이 빠른 소수를 사용하지 못하는 문제점을 갖게 됩니다.
현대 32bit or 64bit의 컴퓨터에서 수학적 계산이 빠른 소수 중 하나인 Mersenne prime(M31) \[2^{31} - 1\]이 존재하는데 이것의 부분군의 위수(p-1)이 2의 거듭제곱을 만족하지 않기 때문에 STARK 구조에 사용하기 힘듭니다.
이러한 STARK 구조에서 원하는 소수와 수학적 계산이 빠른 소수를 모두 만족하기 위해 Circle Group에서 STARK 연산을 하는 Circle STARK를 발전했습니다.
Circle Group
Circle STARK에서는 계산이 빠른 소수와 STARK의 계산 조건을 만족하기 위해 Cricle Curve Field에서 연산을 진행합니다.
M31처럼 \[p \equiv 3 (mod 4)\] 조건을 만족하는 소수 필드에서, 이 위에 존재하는 점은 \[p + 1\]개가 해당됩니다.
예를 들어 p = 3 (2^2 - 1)일 경우 점 (0,1), (1,0), (0,2), (2,0) 총 4개의 점이 나옵니다. 이로써 Circle Curve에서도 2의 거듭제곱인 Subgroup을 만들 수 있습니다.
이러한 이유는 projective line(사영선)과 isomorphic 하기 때문에 위수가 p+1이 됩니다. 일반적인 직선에서는 p개의 점이 있다면, 사영선은 직선의 양쪽 끝에서 만나는 무한대의 점을 하나 추가하여 p+1개의 점이 됩니다.
Circle STARK는 연산의 기반이 되는 도메인을 2차원 유한체 \[\mathbb F_p^2\] 위의 단위 원(unit circle), 즉 \[x^2 + y^2 = 1\] 점 \[(x, y)\]들의 집합 (\[C(\mathbb F_p)\])으로 전환합니다.
원 위의 점을 입체 사영을 통해 사영선 위의 점과 짝지어집니다. 따라서 사영선 위의 점이 p+1이기 때문에 원 위의 점도 p+1이 되어 group의 위수도 p+1이 됩니다.
M31 같은 소수일 경우 p+1이 \[2^{31}\]로 되어 2의 거듭제곱 꼴이기 때문에 FFT 연산과 FRI 연산도 잘 진행할 수 있습니다.
Group operations
이 군의 집합은 복소수 곱셈처럼 순환군(Cyclic Group)을 형성합니다.
\[(x_0, y_0) \cdot (x_1, y_1) = (x_0x_1 - y_0y_1, x_0y_1 + y_0x_1)\]의 연산을 진행합니다.
그룹의 역(inverse) 맵 \[J(x,y) = (x, -y)\]는 Circle FFT의 ‘짝수-홀수’ 분해에 사용됩니다.
원 곡선 위에 정의된 하나의 함수 \[f(x,y)\]를 두 개의 단순한 함수로 분해하는 것입니다.
짝수 부분을 \[f_0(x)\] x축 대칭에 변하지 않은 부분으로 하고, 홀수 부분을 \[f_1(x)\]로 하여 x축 대칭에 대해 부호가 바뀌는 부분으로 합니다.
\[f_0(x) = \frac{f(x,y)+f(x, -y)}{2}\]
\[f_1(x) = \frac{f(x,y)-f(x, -y)}{2y}\]로 나누면 \[f(x,y) = f_0(x) + y*f_1(x)\]로 바꿀 수 있습니다.
이러한 분해를 통해 2차원의 문제를 1차원의 문제로 바꾸어 x값에 의해 의존하도록 만듭니다.
그룹의 제곱 맵(squaring map) \[\pi(x,y) = (x^2-y^2, 2xy)\]는 이차 다항식이며 2-to-1 맵핑을 제공합니다.
여기서 \[y^2 = 1 - x^2\]이기 때문에 \[\pi(x,y) = (2x^2 - 1, 2xy)\]로 사용하기도 합니다.
이 제곱 맵을 통해 1차원으로 축소된 문제를 folding 하여 크기를 줄일 수 있습니다.
연산 결과 후 점은 항상 연산 전의 서로 다른 두 점이 대응 되기 때문입니다.
따라서 16개의 점으로 된 domain을 제곱 연산을 통해 8개의 점의 새로운 domain으로 만들 수 있습니다.
이러한 연산은 FFT나 FRI에서 사용됩니다.
CFFT
CFFT는 twin-coset이라는 도메인에서 진행됩니다. Coset은 그룹 이론의 기본 개념으로, 어떤 부분 그룹(subgroup) 전체를 특정 원소를 사용해 통째로 이동(shift)시킨 집합을 의미합니다.
계산 영역(Domain) 생성: STARK 프로토콜은 증명의 기반이 되는 작은 트레이스 도메인(trace domain)과, 보안성을 높이기 위한 더 큰 평가 도메인(evaluation domain)을 필요로 합니다.
분리와 확장: Coset은 작은 부분 그룹(트레이스 도메인)을 이동시켜, 원래 영역과 겹치지 않으면서도 수학적 구조를 유지하는 더 큰 영역(평가 도메인)을 만드는 데 사용됩니다.
이처럼 계산 영역을 분리하고 확장하는 것이 코셋의 핵심 역할입니다.
1. 계산 무대 설정: 트윈-코셋 (Twin-Coset) 도메인
CFFT 알고리즘은 아무 계산 영역(domain)에서나 작동하지 않습니다. 알고리즘의 재귀적 구조가 완벽하게 들어맞는 특별한 무대가 필요한데, 그것이 바로 트윈-코셋(twin-coset)입니다.
정의: 트윈-코셋은 하나의 코셋(\[Q⋅G_{n−1}\])과 그것의 역원 코셋(\[Q^{-1}\cdot G_{n−1}\] )을 합쳐 만든, 총 2n개의 점으로 이루어진 집합입니다.
\[ D=(Q\cdot G_{n−1}) ∪ (Q_{-1}\cdot G_{n−1})\]
핵심 특징 (대칭성): 이 구조의 가장 중요한 특징은 모든 점 P(x,y)가 그 짝꿍인 J(P) = (x,-y)를 집합 안에 항상 포함한다는 것입니다. 즉, x축 기준으로 완벽한 대칭을 이룹니다.
필요성: CFFT 알고리즘의 첫 단계는 함수를 ‘짝수’ 부분과 ‘홀수’ 부분으로 분해하는 것입니다. 트윈-코셋의 완벽한 대칭 구조는 이 분해 작업을 가능하게 하는 필수 조건입니다.
2. 핵심 문제: 차원 격차 (The Dimension Gap)
CFFT를 이해할 때 가장 중요한 미묘한 차이점입니다.
두 개의 다른 공간: Circle STARK에는 두 종류의 다항식 공간이 있습니다.
전체 다항식 공간 (\[\mathcal{L}_N(F)\]): STARK의 제약 조건 등을 다루는 이론적인 공간입니다. 여기서 다항식들의 총 차수는 \[N/2\]이하이며 이 공간의 차원은 \[N + 1\]입니다.
하지만 실제로 CFFT를 통해 만들어지는 다항식은 \[\mathcal{L’}_N(F)\] 이며 이 공간의 차원은 \[N\]이기 때문에 1차원만큼 작은 공간의 결과물이 만들어집니다.
N개의 점으로 N+1 차원의 공간을 특정할 수 없어 여기서 문제가 생깁니다.
그래서 몫 다항식 계산, FRI 과정에서 별도의 처리를 진행합니다.
3. CFFT 알고리즘의 과정: 2단계 분할 정복
CFFT는 트윈-코셋 위의 N개의 함수 값을 입력받아 N개의 계수를 출력하는 효율적인 변환 과정입니다.
1단계 (y축 기준 분해): 트윈-코셋의 대칭성을 이용하여, N개의 함수 값을 짝수 부분과 홀수 부분으로 분해합니다.
이 과정은 \[J(x,y)=(x,-y)\]를 기준으로 하며, 2차원 원 위의 문제를 1차원 x축 위의 두 문제로 변환하는 역할을 합니다.
2단계 (x축 기준 반복 분해): 1차원으로 변환된 두 개의 문제를 각각 재귀적으로 계속 분해합니다.
이 과정은 제곱 맵 π(x) = 2x²-1를 기준으로 하며, 일반적인 FFT의 ‘분할 정복’ 방식과 동일하게 작동합니다. 문제가 더 이상 쪼갤 수 없는 크기(상수)가 될 때까지 이 과정을 반복합니다.
4. CFFT의 결과: 특별한 기저의 계수들
알고리즘을 통해 최종적으로 나온 N개의 숫자는 무엇을 의미할까요?
결과: 이 숫자들은 일반적인 다항식의 계수( \[c_0, c_1, c_2 \ldots \])가 아니라 CFFT만의 **특별한 ‘기저(basis)’ 다항식 집합(\[\mathcal{B}_n\])에 대한 계수입니다.
FFT-basis (\[\mathcal{B}_n\]): 이 기저 다항식들은 소멸 다항식들을 곱하여 만들어진 독특한 형태를 가집니다. $b_j^n = y^{j_0} \cdot v_1(x)^{j_1} \cdot ….$
CFFT를 통해 trace polynomial과 Constraints polynomial을 만들는 후 아까의 차원 격차를 해소해야 합니다.
$q = \lambda \cdot v_n + g$ 를 진행 합니다.
\[v_n\]은 소멸 다항식이기 때문에 g에 대해 테스트를 진행합니다.
이러한 방법으로 차원 격차를 해소합니다. (somethign strange…)
CFRI
Circle STARKs도 마찬가지로 만들어진 다항식이 low-degree인지 테스트를 진행해야합니다.
마차간지로 Folding을 진행하기 전에 \[f = g + \lambda \cdot v_n\]으로 차원 격차를 해소합니다.
그 다음으로 J-map으로 짝수, 홀수 항을 나누어 차수를 절반으로 나눈 후, \pi -map으로 fold를 진행하여 크기를 줄여나갑니다.
다음은 기존 FRI처럼 진행을 합닌다.