# Circle STARKs {% hint style="warning" %} **목표 : STARK에서 효율적으로 발전한 Circle STARKs에 대해 알아보도록 하겠습니다.** {% endhint %} ### 1. 왜 Circle STARKs인가 – Mersenne 소수와 STARK의 충돌 고전적인 STARK는 다음과 같은 조건을 매우 강하게 요구한다. * 유한체 $$\mathbb F\_p$$​ 위에서 곱셈 부분군 $$\mathbb F\_p^\*$$​ 안에 크기가 $$2^k$$ 꼴인 **smooth한 부분군**이 있어야 한다. 즉, $$p−1=2^k⋅c$$, $$c$$ 는 홀수, $$k$$ 는 충분히 커야 한다. 이 조건이 필요한 이유는 STARK에서 사용하는 **FFT**, **FRI** 가 전부 “도메인 크기를 절반씩 줄이는” 재귀 구조를 갖기 때문이다. 도메인 크기가 계속 $$\frac{1}{2}$$​씩 줄어들어야 하므로, 처음 크기가 $$2^k$$ 꼴이어야 한다. 그런데, 성능 측면에서 보면 * 현대 CPU에서 **가장 빠르게 연산되는 소수 필드** 중 하나가 $$M\_{31} = 2^{31} - 1$$같은 **Mersenne prime**이다. * 이 필드는 모듈러 연산이 $$2^{31} \equiv 1 \pmod{2^{31}-1}$$ 같은 성질 때문에 비트 연산만으로도 빠르게 처리할 수 있다. 하지만 Mersenne prime에 대해 $$p - 1 = (2^{31} - 1) - 1 = 2^{31} - 2 = 2 \cdot (2^{30} - 1)$$ 이 되어 **2의 지수는 1밖에 없다.** \ 즉, $$p-1 = 2 \cdot \text{홀수}$$꼴이므로, 고전적인 STARK 요구사항인\ “$$2^k \mid p-1$$에서 $$k$$ 가 충분히 크다”를 만족시키지 못한다.\ 그래서: > “필드는 Mersenne prime으로 쓰고 싶은데, 곱셈 부분군이 STARK용으로는 smooth하지 않다”는 딜레마가 생긴다. **Circle STARKs** 는 바로 이 문제를 해결하기 위한 구조이다. * 필드는 여전히 **Mersenne prime**처럼 “연산 빠른 소수”를 쓰면서, * STARK/FRI에서 요구하는 “크기가 $$2^k$$ 인 smooth 도메인”은 **필드의 곱셈군이 아니라 다른 군**, 즉 **원 위의 군(circle group)** 에서 가져오는 구조이다. *** ### 2. Circle Group Circle STARK에서는 다음과 같은 집합을 사용한다. * 소수 $$p \equiv 3 \pmod 4$$인 필드 $$\mathbb F\_p$$​ 를 잡는다. * 그 위의 **단위원(unit circle)** $$C(\mathbb F\_p) = { (x, y) \in \mathbb F\_p^2 \mid x^2 + y^2 = 1 }$$ 를 생각한다. 이 점들의 집합은 다음 연산으로 군을 이룬다(복소수 곱셈과 같은 형태이다). $$(x\_0, y\_0) \cdot (x\_1, y\_1) = (x\_0 x\_1 - y\_0 y\_1,; x\_0 y\_1 + x\_1 y\_0)$$ * 항등원은 (1,0) 이다. * 역원은 $$(x, y)^{-1} = (x, -y)$$이다. 이 군을 보통 **circle group** 이라고 부른다. 흥미로운 사실은, 이 circle group의 원소 수가 항상 $$p+1$$ 이라는 점이다. 이는 대략 다음 사실에서 온다. * 원 위의 점들을 적절히 대응시키면, **사영선(projective line)** $$P^1(\mathbb F\_p)$$ 와 동형이 된다. * 사영선에는 유한한 점이 $$p$$개, “무한원점”이 하나 있어 총 $$p+1$$개의 점이 존재한다. 따라서 circle group의 위수(원소 수)도 $$|C(\mathbb F\_p)| = p + 1$$ 이 된다. 이제, 만약 $$p$$ 가 Mersenne prime $$p = 2^m - 1$$ 라면 $$|C(\mathbb F\_p)| = p + 1 = 2^m$$ 꼴이 된다. 즉, **circle group 위에는 크기가 정확히** $$2^m$$ **인 순환군이 존재한**다. * 예: $$p = 3 = 2^2 - 1$$ 이면, $$p+1 = 4 = 2^2$$이므로 원 위의 점이 4개이다. 이 덕분에, > “필드는 Mersenne prime으로 두고, STARK/FRI에서 필요한 ‘크기 $$2^k$$ 짜리 도메인’은 circle group에서 가져오는 것”이 가능해진다. 이것이 Circle STARKs의 핵심 동기이다. *** ### 3. Circle STARK에서의 다항식 표현 Circle STARK에서는 **원 위의 점에 대한 함수**를 다루어야 하므로, 자연스럽게 $$x, y$$ 두 변수의 다항식 $$f(x, y)$$ 를 사용한다. 하지만 circle 위에서는 항상 $$x^2 + y^2 = 1$$이 성립하므로, 이를 이용해 항상 $$y^2$$ 를 제거할 수 있다. 예를 들어, $$y^2 = 1 - x^2$$로 두면, 임의의 다항식 $$f(x,y)$$ 에 대해 $$y^2, y^3, y^4, \dots$$ 항들을 반복적으로 치환하여\ 다음과 같은 **표준형(canonical form)** 으로 쓸 수 있다. $$f(x,y) = f\_0(x) + y,f\_1(x)$$ 여기서 $$f\_0(x), f\_1(x)$$ 는 **모두 일변수 다항식**이다. 역원 맵 $$J(x,y) = (x, -y)$$를 사용하면, $$f(x,y)$$ 와 $$f(x,−y)$$ 를 더하고 빼서 $$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차원 다항식 두 개” 문제로 바꾸어 FFT, FRI를 적용할 수 있게 된다. *** ### 4. Circle FFT (CFFT) – Circle 위에서의 FFT이다 STARK에서 FFT는 * “트레이스를 다항식으로 표현하고” * “그 다항식을 더 큰 도메인에서 평가”하는 핵심 루틴이다. Circle STARK에서는 이 FFT의 버전이 **CFFT(Circle FFT)** 이다. #### 도메인: Twin-coset CFFT는 아무 점 집합에서나 돌아가지 않고, 특정한 형태의 도메인에서만 잘 동작한다. 먼저 circle group의 부분군 $$G\_{n-1}$$​ (크기 $$2^{n-1}$$)을 잡는다. 어떤 원소 $$Q$$ 를 골라 코셋을 만들면 $$Q \cdot G\_{n-1} = { Q \cdot g \mid g \in G\_{n-1} }$$ 여기에 역원 코셋 $$Q^{-1} \cdot G\_{n-1}$$ 를 더해 $$D = (Q \cdot G\_{n-1}) \cup (Q^{-1} \cdot G\_{n-1})$$ 를 생성한다. 이 집합이 바로 **twin-coset 도메인**이다. 이 도메인의 특징은 원소가 총 $$2^n$$ 개이며 \ 어떤 점 $$P = (x, y)$$가 도메인에 있다면 항상 그 짝인 $$J(P) = (x, -y)$$ 도 도메인에 포함된다는 점이다. 이 “짝” 구조가 앞에서 본\ $$f(x,y) = f\_0(x) + y f\_1(x)$$분해와 정확히 맞물린다. #### CFFT의 2단계 분할 정복 1. **1단계 – J-맵을 이용한 짝수/홀수 분해** * twin-coset 도메인 위에서 함수 $$f(x,y)$$ 의 값들을\ $$J(x,y) = (x,-y)$$에 따라 짝지어,\ 짝수 부분 $$f\_0(x)$$, 홀수 부분 $$f\_1(x)$$ 로 나눈다. * 이 과정에서 2차원 문제를 “x에만 의존하는 두 개의 1차원 다항식” 문제로 바꾼다. 2. **2단계 – 제곱 맵을 이용한 도메인 절반 축소이다.** * 제곱 맵(squaring map)을 $$\pi(x,y) = (x^2 - y^2,; 2xy) = (2x^2 - 1,; 2xy)$$ 로 두면, 첫 번째 좌표는 $$x$$ 만의 함수가 된다. * 이 맵은 적절한 도메인에서는 **2-to-1** 이므로,\ 도메인 크기를 절반으로 줄이면서 $$x \mapsto 2x^2 - 1$$같은 형태로 재귀적으로 FFT를 수행할 수 있다. 결국 CFFT는 > “원 위의 함수 값을 입력받아, 특별한 기저(basis)에 대한 다항식 계수들로 바꾸는 변환” 이다. 여기서 기저는 일반 모노미얼 $$1, x, x^2, \dots$$가 아니라,\ Circle STARK에 맞게 구성된 **소멸 다항식(vanishing polynomial)들**로 만든 기저이다. #### 4.3 Dimension gap 문제 Circle STARK에서는 이 과정에서 **차원 격차(dimension gap)** 라는 미묘한 문제가 생긴다. * 이론적으로 사용하는 다항식 공간 $$\mathcal L\_N(F)$$의 차원은 $$N+1$$ 이다. * 그러나 CFFT로 실제로 표현되는 공간$$\mathcal L'\_N(F)$$ 의 차원은 $$N$$ 이다. 즉, **N개의 점으로는**$$N+1$$차**원 전체를 표현할 수 없기 때문에**, 실제로는 그 중 $$N$$ 차원짜리 부분공간만 다룰 수 있다. 이 격차를 처리하기 위해 * 소멸 다항식 $$v\_n(x)$$ 를 이용하여 * $$q = \lambda \cdot v\_n + g$$같은 형태로 나누어 * $$g$$에 대해 FRI 테스트를 진행하는 등의 보정이 필요하다. *** ### 5. Circle FRI (CFRI) – Circle 위의 Low-Degree Test STARK의 핵심은 “어떤 함수가 low-degree 다항식에서 나왔는지”를 테스트하는 FRI 프로토콜입니다. Circle STARK에서는 이에 대응하는 **Circle FRI(CFRI)** 를 사용한다. 전체 흐름은 고전 FRI와 매우 비슷하지만, circle group 특성 때문에 다음과 같은 차이가 있다. #### 시작 단계 – 차원 격차 보정 앞에서 본 것처럼, Circle STARK에서는 다항식 공간에 차원 격차가 존재합니다. 이를 해결하기 위해 $$f = g + \lambda \cdot v\_n(x)$$ 형태로 분해를 먼저 수행한다. * $$v\_n(x)$$ 는 도메인 전체에서 0이 되는 소멸 다항식이다. * $$\lambda$$는 랜덤 스칼라다. * 이 분해를 통해, 실제 FRI를 적용하는 함수 $$g$$ 가 “folding을 반복해도 차원이 잘 절반씩 줄어드는 좋은 공간” 안에 있도록 만든다. #### 5.2 Folding 단계 – J-map + 제곱 맵 CFRI의 folding은 대략 다음 두 단계로 진행된다. 1. **J-map으로 짝수/홀수 나누기** * $$J(x,y) = (x,-y)$$를 이용해 $$f(x,y)$$ 를 짝수/홀수 부분으로 나누고, 이를 통해 2차원 문제를 1차원 다항식 문제로 낮춘다. 2. **제곱 맵으로 도메인 절반 축소** * 이후에는 1변수 다항식 $$h(x)$$ 에 대해 $$x \mapsto 2x^2 - 1$$형태의 folding을 반복하며, 도메인 크기를 반으로 줄인다. * 이 과정이 몇 번 반복되면, 결국 “상수 함수” 수준까지 내려가고, 여기서 FRI가 “정말 low-degree인지”를 판별한다. 이 과정 전체는 고전 FRI의 “제곱 맵으로 도메인 줄이기”와 구조가 동일하지만, * 도메인이 $$\mathbb F\_p^\*$$ 의 부분군이 아니라 circle group의 twin-coset이고, * 짝수/홀수 분해에 J-map을 사용한다는 점이 다르다. *** ### 6. Circle STARKs의 전체 그림과 장단점 #### 6.1 전체 그림 요약 Circle STARKs를 한 문단으로 요약하면 다음과 같다. > Mersenne prime 같은 “하드웨어 친화적(연산 빠른) 소수 필드”에서\ > 곱셈 부분군이 부드럽지 않다는 문제를 해결하기 위해,\ > 필드 위의 unit circle $$x^2 + y^2 = 1$$에서 얻은 **circle group**을 도메인으로 사용하고,\ > 여기에 맞춘 CFFT·CFRI를 정의하여 고전 STARK와 거의 동일한 논리 구조를 유지하면서\ > 훨씬 빠른 연산을 가능하게 하는 STARK 변형이다. **장점** * $$M\_{31}$$, $$2^{61}-1$$ 같은 **매우 빠른 Mersenne prime 필드**를 그대로 사용할 수 있다. * 작은 비트 크기(32bit, 64bit)의 필드를 쓰므로, ZK-VM 등의 trace 표현에서 **메모리·대역폭 overhead가 줄어든다.** * StarkWare의 **Stwo**, Polygon의 **Plonky3** 등 최신 STARK 계열 prover들이 Circle STARK 아이디어를 실제 제품에 적용하고 있다. **단점** * 수학적 구조가 고전 STARK보다 훨씬 복잡하다. * circle group, twin-coset, dimension gap, 특수 기저 등 이해해야 할 개념이 많이 늘어난다. * 구현도 복잡해진다. * 하지만 실제 사용자(개발자)는 Stwo, Plonky3 같은 라이브러리를 통해 대부분의 복잡도를 감춘 상태에서 사용하게 다. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-3/stark/circle-starks.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.