Hash Functions Monolith for ZK Applications: May the Speed of SHA-3 be With You
이 내용은 https://eprint.iacr.org/2023/1025.pdf 의 요약입니다.
ZK Friendly Hash Function의 필요성
해시함수는 굉장히 많은 곳에서 사용되고 있습니다. 그런만큼 ZKP 상에서도 해시함수의 계산에 대한 증명을 하게 될 필요가 상당히 많습니다. 그런데 일반적인 해시함수는 일반적인 컴퓨팅 환경에서 빠르게 작동하는 것을 목표로 하기 때문에, 비트 연산 등을 많이 활용합니다. 이는 비트 연산을 다루는 비용이 큰 ZKP 상에서는 큰 문제로 작용합니다. 이에 따라, ZKP 상에서 비용이 적은, 즉 적은 constraint로 증명을 할 수 있는 해시함수를 만드는 것이 필요해졌습니다. 또한, ZKP 상에서 증명 비용을 줄이는 것이 기본적인 목표이지만, 실제 컴퓨팅 환경에서의 계산 역시 빠르게 하는 것도 중요합니다. 이 목표들을 가지고 ZKP를 위한 해시함수의 연구가 본격적으로 시작되었습니다.
ZK Friendly Hash Function의 일반적인 구조
많은 ZK Friendly Hash Function은 pseudo-random permutation을 기반으로 합니다.
즉, 일반적인 해시함수를 만들기 위해서
- $t = r + c, r, c$의 값을 해시함수의 안전성을 확보하기 위해 결정하고
- permutation $\mathbb{F}_p^t \rightarrow \mathbb{F}_p^t$을 잡은 뒤
Sponge 구조를 사용하여 해시함수를 구축합니다. 굳이 Sponge를 사용하지 않더라도 permutation을 기반으로 compression function을 만들어 사용할 수 있습니다. 특히, Merkle Tree를 구축하기 위해서는 일반적으로 (child를 묶어서 올리는 경우) fixed-length compression을 사용하는 경우가 많으니, 그 경우에는 이러한 compression function을 사용할 수 있습니다.
기본적인 목표는 constraint의 개수를 줄이는 것이니, ZKP에서 표현하기 쉬운 연산들을 가지고 permutation을 만듭니다. 즉, $\mathbb{F}_p$ 위에서의 곱셈을 중심으로 하여 permutation을 만들게 됩니다. PLONK가 개발되고 lookup argument가 ZKP에 추가되어, lookup argument를 사용한 연산 역시 permutation을 구축하기 위해서 사용되게 됩니다.
Poseidon, Poseidon2의 경우, 곱셈과 덧셈을 사용하여 permutation을 만듭니다. 즉,
- algebraic degree를 높이기 위한 S-box $x \rightarrow x^\alpha$
- 값을 “충분히 섞기” 위한 MDS Matrix Multiplication $s \rightarrow M \cdot s$
- round constant addition
를 사용하게 됩니다. Poseidon 계열의 구조는 external round와 internal round가 분리되고, algebraic attack과 statistical attack에 대한 방어의 분리, MDS matrix의 설계 등 복잡한 문제와 이론이 많으나, 여기서는 생략하도록 하겠습니다.
Reinforced Concrete의 경우, lookup argument를 본격적으로 사용하게 됩니다. 이는
- Bricks: $(x_1, x_2, x_3) \rightarrow (x_1^d, x_2(x_1^2 + \alpha_1 x_1 + \beta_1), x_3(x_2^2 + \alpha_2 x_2 + \beta_2))$
- Concrete: $s \rightarrow M \cdot s + c$, ($M = \text{circ}(2, 1, 1)$)
- Bars: $\text{Bars}(x_1, x_2, x_3) = (\text{Bar}(x_1), \text{Bar}(x_2), \text{Bar}(x_3))$
Bricks와 Concrete는 무난한 곱셈과 덧셈으로 이루어져 있는데, Bars는 상당히 복잡합니다.
Bar는 Comp, SBox, Decomp로 이루어져 있습니다. $s_1, \cdots, s_n$을 $\prod s_i > p$가 되도록 고정합시다.
이제 $\text{Decomp}(x) = (x_1, x_2, \cdots, x_n)$을 $(s_1, \cdots, s_n)$-진법에서의 $x$의 표현으로 둡니다. 즉,
\[x = x_1 s_2 \cdots s_n + x_2 s_3 \cdots s_n + \cdots + x_{n-1} s_n + x_n\]이며 $0 \le x_i < s_i$가 성립합니다. Comp는 Decomp의 역산입니다.
S-box의 경우, $\text{Decomp}(p - 1) = (v_1, \cdots, v_n)$으로 두고, $p’ \le \min v_i$를 잡은 뒤, $f$를 $\mathbb{Z}_{p’}$의 permutation으로 둡니다. 이때, $y_i = S(x_i)$는 $x_i < p’$인 경우 $x_i < p’$으로 두고, $x_i \ge p’$인 경우 $x_i$로 둡니다.
이제 Bar는 $\text{Comp} \circ \text{SBox} \circ \text{Decomp}$로 이루어져 있습니다. 이 Bar의 장점은 lookup argument로 효율적으로 구현할 수 있지만, algebraic degree가 매우 크다는 것입니다. 이에 따라 Poseidon, Poseidon2처럼 많은 round를 거치지 않아도 permutation을 안전하게 완성할 수 있으며, 이에 따라 ZKP 상에서 더 효율적입니다.
Monolith의 구조와 장점
Monolith는 작은 prime $p$를 사용하는 ZKP의 계열에서 (FRI 기반) 사용되기 위해 설계된 해시함수입니다. 이 계열에서 많이 보이는 소수는 Goldilocks $2^{64} - 2^{32} + 1$이나 $2^{31} - 1$입니다. 즉, $2^{2n} - 2^n + 1$이거나 $2^n - 1$ 형태입니다.
$p$의 형태가 워낙 특수하니, Decomp, SBox, Comp의 구조를 이를 기반으로 바꿔 최적화를 할 수 있는 여지가 있습니다. 이를 기반으로 Monolith가 설계되었습니다.
Bricks는 Feistel 구조로 이루어져 있습니다.
\[(x_1, \cdots, x_t) \rightarrow (x_1, x_2 + x_1^2, \cdots, x_t + x_{t-1}^2)\]Concrete는 역시 MDS Matrix의 곱으로 diffusion을 합니다.
\[(x_1, \cdots, x_t) \rightarrow M \cdot (x_1, \cdots x_t)\]여기서 $M$은 $p$가 Goldilocks prime의 경우, circulant matrix를 사용하여 matrix-vector product를 더 효율적으로 (DFT) 할 수 있습니다.
Bars의 경우, Reinforced Concrete의 그것과 비슷합니다. 단, 쪼갤 때 $s_1, s_2, \cdots , s_n$을 잡는 복잡한 접근을 취하지 않고, 비트 묶음으로 쪼갭니다. 예를 들어, Goldilocks prime을 기준으로 설명하면, Decomp는 $x$를
\[x = \sum_{i=0}^7 x_i 2^{8i}\]인 $(x_1, x_2, \cdots , x_8)$로 보내는 mapping입니다. Comp는 여전히 Decomp의 역산입니다.
여기서 재밌는 점은 S-box의 설계인데, 다음 사실을 증명할 수 있습니다.
Claim: $S$가 $\mathbb{F}_2^{8} \rightarrow \mathbb{F}_2^8$의 permutation이고 $0 \cdots 0$과 $1 \cdots 1$이 $S$의 fixed point라면, $S$를 사용한 Bars function은 $\mathbb{F}_p$의 permutation 이다.
그러므로, $S$ 자체는 lookup argument로 증명이 될테니, native 한 계산에서 $S$가 빠르게 계산되는 것을 목표로 최적화를 할 수 있습니다.
이를 위해
\[S(y) = (y \oplus (\overline{y} \lll 1) \odot (y \lll 2) \odot (y \lll 3)) \lll 1\]를 설계합니다. 이는 differential 등에서도 좋은 조건을 갖춰, Bars의 algebraic degree의 lower bound를 구하는데 도움을 줍니다. 게다가 비트 연산으로 구성되어 있으니, native 계산 속도 역시 매우 빠릅니다.
Monolith는 $r = 6$개의 round로 이루어져 있고,
- $R’ = \text{Concrete}$
- $R_i = c_i + \text{Concrete} \circ \text{Bricks} \circ \text{Bars}$
로 이루어져,
\[\text{Monolith} = R_6 \circ \cdots \circ R_1 \circ R'\]가 됩니다. 이 permutation을 기반으로 sponge construction을 사용하여 일반적인 해시함수를 만들 수도 있으며, $t$ to $n$ construction을 만들기 위해서
\[Z(x) = \text{Tr}_n ( P(x) + x)\]를 사용할 수도 있습니다.
round constant 생성 등의 문제는 Poseidon과 비슷하게 seed, $t$, $r$, $p$ 등을 input으로 하여 SHAKE-128을 사용하여 진행됩니다.
결과적으로 이러한 최적화를 통해서 native 속도가 SHA-3에 준하는 수준까지 좋아졌습니다.
여담: 최근 발견한 Poseidon2의 구현과 발생한 버그
별개로 최근 Poseidon2의 구현체 https://github.com/HorizenLabs/poseidon2 에서 두 문제점을 찾았습니다.
첫 번째 문제가 더 중요한데, Matrix multiplication 과정에서 $t = 4$인 경우에 계산이 2배 차이가 나는 문제였습니다.
두 번째 문제는 constant generation을 위해서 사용되는 seed를 구축하기 위해서 SBOX의 형태를 input으로 넣는데, 이 값이 Poseidon과 Poseidon2 사이에서 consistent 하지 않았다는 점입니다. 다만 SBOX의 형태는 이제 거의 하나만 사용되기 때문에, 그렇게 중요한 문제는 아니었습니다.