[ZK-STARK series] # 05 Appendix (Arithmetization with polynomial)
본 게시글은 ZK-STARK 에 대해 분석한 시리즈의 부록입니다. 이번 편에선 1편에서 간단히 언급만 하고 넘어간 Arithmetization 과정을 예시와 함께 설명합니다.
Author
Beomki Kim
Reviewed By Yohan Lim, Sunghwan Ha
[ZK-STARK] Series
# 05. Appendix
아래와 같은 문제의 답을 같이 생각해 볼까요?
Bob 은 Alice 에게 자신이 {1,2,3,…,10} 으로만 이루어진 10⁶길이의 배열을 가지고 있다고 주장합니다.
Alice 는 몇 번의 query 를 통해 Bob 의 주장을 틀린지 아닌지 판단할 수 있을까요?
가장 간단한 방법은 10⁶ 개를 모두 보는 것입니다. 하지만 이는 1편에서 나온 Naive Replay 방법과 다를게 없고 모든 데이터셋을 다 봐야 하므로 매우 비효율적입니다.
하지만 똑똑한 Alice 는 다항식의 성질을 이용해 이 문제의 필요한 단계를 줄이고자 합니다. 그러기 위해 Bob 에게 아래와 같은 요청을 합니다.
Alice 는 Bob에게 f(index) = value 을 만족하는 10⁶ 차 다항식(Bob 이 가지고 있는 배열의 인덱스를 함수에 넣으면 그 인덱스의 배열 값이 나오는 함수)를 만들어주도록 요청했습니다. 그리고 이 함수는 다항식의 성질에 의해 10⁶ 개의 점을 지나는 유일한 10⁶차 함수입니다. 그리고 에러 체킹을 위해 같은 함수에 대해 10⁹개까지 정의역을 확장시켜 f의 함숫값을 계산해서 제공받았습니다.
또한 이제는 새로운 함수 g에 대해, g(index) = value 을 만족하는 10⁷ — 10⁶ 차 다항식을 10⁹ 개 정의역에 대해 만들어서 계산해달라고 요청합니다. 이 다항식 g 는 차수가 10⁶ 보다 크므로 유일하지는 않습니다.
이제 Alice 는 위 2가지 요청을 이용해 단 2 번의 쿼리(임의의 숫자를 f에 한 번, g에 한 번) 으로 Bob 의 주장을 증명할 수 있게 됩니다.
아래와 같이 새로운 함수 C, D 를 정의합니다. C 는 1 부터 10을 넣으면 무조건 0을 리턴하는 10차 함수이고, D는 1부터 10⁶ 을 넣으면 무조건 0을 리턴하는 10⁶ 차 함수입니다.
Let C(X) := (X-1)*(X-2)*...*(X-10)
Let D(X) := (X-1)*(X-2)*...*(X-10^6)Alice 의 규칙 )Alice 는 {1,...,10^9} 정의역에서 랜덤한 x0 를 고른다.
첫 번째 쿼리 : f(x0)
두 번째 쿼리 : g(x0)
Alice 의 결정 : C(f(x0)) == g(x0)*D(x0) 일 때만 Bob 의 주장을 수용한다.증명 )Bob 이 거짓말을 해서 배열 중에 1~10 이 아닌 값이 있다고 해보자. (e.g. f(1) = 11)
C(f(x)) 의 값은 정의역 {1,...,10^6} 에서 0 이 아닌 지점이 적어도 하나는 있다. (f의 함숫값이 1부터 10 안에 다 들어가지 않기 때문에)
g(x)*D(x) 의 값은 정의역 {1,...,10^6} 에서 D(x) 때문에 항상 0이다.따라서 g(x)*D(x) 와 C(f(x)) 는 같은 점을 지나지 않으므로 다른 함수인 것이다. 그리고 다항식의 성질에 의해 위 두 함수는 g(x)*D(x) 의 차수인 최대 10^7 개의 점에서만 만날 수 있다. -> 만나는 경우에 Alice 가 Bob 의 주장을 수용한다.따라서 총 10^9 개의 랜덤한 선택지 중에 잘못된 판단을 하게 되는 경우는 최대
10^7 개인 것이다. --> 1% 확률(10⁹, 10⁶등의 수는 1% 확률을 예시로 들기 위해 임의로 지정한 숫자입니다.)
이렇게 다항식의 성질을 이용해 컴퓨터의 계산과정을 획기적으로 줄이는 것을 Arithmetization 이라고 합니다. 이 과정은 비단 STARK 뿐만 아니라 모든 ZK 기술에서 활용되고 있습니다.
