<aside> 🏎️

Formula Zero 는 Nonce Open Source Lab 소속으로, Tezos Foundation 의 지원을 받아 PoS 기반 블록체인의 Light Client를 연구하는 프로젝트입니다.

</aside>

Cryptographic Accumulator

Accumulator의 사전적 정의는 '누산기'로, CPU 연산장치에서 연산의 중간 값을 저장하는 기억공간을 일컫는다. 블록체인 영역에서 Accumulator 는 암호학에 기반하여 한 그룹의 전체 요소에 바인딩된 작은 길이의 commitment를 생성하며, 특정 요소가 해당 그룹에 포함됨을 commitment 기반으로 증명하는 역할을 한다. 이 증명은 공개적으로 검증 가능하다. 가장 간단한 예로 Merkle Tree 가 있으며, 비트코인에서 한 블록에 포함된 트랜잭션들을 Merkle Root 라 불리는 하나의 commitment 로 축약하여 이를 블록 헤더에 저장한다. 추후 해당 블록에 특정 트랜잭션이 포함되어 있음을 증명하는 Merkle Root 와 해당 트랜잭션 그리고 Merkle Path(해당 트랜잭션을 Tree 의 Leaf ([Figure 1] $\mathsf{H_K}$)로 설정하고, Leaf 에서 Root([Figure 1] $\mathsf{H_{ABCDEFGHIJKLMNOP}}$)까지 연산하기 위해 필요한 값들)([Figure 1] $\mathsf{H_L, H_{IJ}, H_{MNOP}, H_{ABCDEFGH}}$) 을 가지고 검증할 수 있다.

Vector Commitment

Vector Commitment(VC)는 Accumulator 와 암호학적으로 매우 유사하다. VC는 그룹에 하나의 요소가 "특정 위치"에 속해 있음을 작은 길이의 Proof로 증명할 수 있다. Sub-Vector Commitment 는 여러 요소들 및 그 위치들에 대해 증명할 수 있는 Proof 를 말한다. 보통 VC는 아래의 6개 알고리즘으로 구성된다.

• $pp \leftarrow Gen(1^\lambda, n)$ : 시큐리티 파라미터 $\lambda$ 와 Commitment 생성 대상이될 벡터의 최대 길이 $n$
• $C \leftarrow Com_{pp}( a_0, ... , a_{n-1})$ : 벡터 $\mathbf{a}=(a_0,...,a_{n-1})$ 에 대한 commitment $C$ 생성
• $\pi_i \leftarrow Open_{pp}(i,v,\mathbf{a})$ : 벡터 $\mathbf{a}$ 내에 특정 위치 $i$ 의 값이 $v$ 임을 증명하는 Proof $\pi_i$ 생성
• $\{0,1\} \leftarrow Ver_{pp}(C, i, v, \pi_i)$ : 벡터에 대한 Commitment $C$ 와 Proof $\pi_i$ 를 가지고 특정 위치 $i$ 의 값이 $v$ 임을 검증
• $C' \leftarrow UpdateCom_{pp}(u, \delta, C)$ : 특정 위치 $u$ 의 값을 $\delta$ 로 변경하였을 때 기존의 commitment 인 $C$ 를 갱신
• $\pi_i' \leftarrow UpdateProof_{pp}(u, \delta, \pi_i)$ : 특정 위치 $u$ 의 값을 $\delta$ 로 변경하였을 때 기존의 proof 인 $\pi_i$ 를 갱신

Polynomial Commitment

벡터의 한 표현방식으로 다항식(Polynomial)을 적용할 수 있다. 즉 $i$ 번째 위치의 값 $v_i$ 에 대해 $f(i)=v_i$ 를 구성하여 라그랑주 보간법(Lagrange Interpolation) 으로 다항식을 유추할 수 있다. 즉, 주어진 $n$ 개의 pair 인 $(x_i, y_i)_{i\in [0,n)}$에 대해서 $n$ 보다 작은 차수를 갖는 다항식 $\phi(X)$ 은 $\phi(x_i)=y_i$ 를 만족한다. 라그랑주 보간범을 적용하면 해당 다항식은 $O(n \log^2 n)$ 시간내에 찾을 수 있다.

• $\phi(X)=\sum_{i\in [0,n)} \mathcal{L_i}(X)y_i$ (여기서 $\mathcal{L}i=\prod{j\in [0,n), j\neq i} \frac{X-x_j}{x_i-x_j}$)
  • 참고: $\forall i \in [0,1) \text{ and } j \neq i$ 이면, $\mathcal{L}_i(x_i)=1, \mathcal{L}_i(x_j)=0$
  • 라그랑주 보간법 : $(x_0, y_0)$과 $(x_1, y_1)$ 일 때
    • $y=\frac{x-x_1}{x_0-x_1} \cdot y_0 + \frac{x-x_0}{x_1-x_0} \cdot y_1$ 으로 구성할 수 있음

다항식으로 표현한 벡터에 대한 Commitment 를 생성하는 방식 중 최근 많이 언급되는 Kate('카테'라 읽음) Polynomial Commitment 에 알아보자. 이 Commitment 는 pairing 기반 검증 알고리즘을 가지며, 아래 두 assumption을 가진다.

• 타입 1 (symmetric)의 Pairing 기반 $e:\mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$
• Discrete Logarithm (DL) Assumption : $\mathbb{G}^* = \mathbb{G} \text{ or } \mathbb{G}T$ 에 대해 생성자 $g$ 와 $a \in_R \mathbb{Z}p^*$ 에 대해서 모든 adversary 인 $\mathcal{A}{DL}$ 은 $\mathsf{Pr}[\mathcal{A}{DL}(g, g^a)=a] = \epsilon(k)$ 임. 즉 $g, g^a$가 주어졌을 때 $a$ 를 찾을 수 없다는 가정