작성자: Fox Tech CTO 린옌시, Fox Tech 수석 과학자 멍현지

서론:

zkRollup 및 zkEVM 분야에서 직면한 거의 모든 문제의 본질은 알고리즘 문제입니다. ZKP 하드웨어 가속이 자주 언급되는 주된 이유는 현재 알고리즘이 일반적으로 느리기 때문입니다. "알고리즘이 부족하니 하드웨어로 보완하자"라는 어색한 상황에 빠지지 않기 위해, 우리는 본질적인 알고리즘에서 문제를 해결해야 합니다. 정교한 증명 생성 방안을 설계하는 것이 이 문제를 해결하는 열쇠입니다.

스마트 계약의 지속적인 발전과 함께 점점 더 많은 web3 애플리케이션이 등장하고 있으며, 이더리움과 같은 전통적인 Layer1의 거래량이 급격히 증가하고 있으며 언제든지 혼잡해질 수 있습니다. Layer1이 제공하는 보안성을 보장하면서 더 높은 효율성을 얻는 방법이 시급히 해결해야 할 문제입니다.

이더리움의 경우, zkRollup은 제로 지식 증명 알고리즘을 기본 구성 요소로 사용하여 원래 Layer1에서 실행해야 했던 고비용의 계산을 체인 외부로 옮기고 체인 상에 실행의 정확성을 증명합니다. 이 분야에는 StarkWare, zkSync, Scroll 및 Fox Tech와 같은 프로젝트가 있습니다.

사실, zkRollup의 설계에서는 효율성에 대한 요구가 매우 높습니다: 제출되는 증명 값이 충분히 작아야 Layer1의 계산량을 줄일 수 있습니다. 충분히 작은 증명 길이를 얻기 위해 각 zkRollup 프로젝트는 알고리즘 및 아키텍처 설계를 개선하고 있으며, 예를 들어 Fox는 최신 제로 지식 증명 알고리즘을 결합하여 최적의 증명 시간과 증명 길이를 얻기 위해 자신의 증명 알고리즘 FOAKS를 개발했습니다.

또한, 증명을 검증하는 단계에서 가장 일반적인 방법은 선형적으로 증명을 생성하고 차례로 검증하는 것입니다. 효율성을 높이기 위해, 사람들이 가장 먼저 생각하는 것은 여러 증명을 하나의 증명으로 패키징하는 것입니다. 이것이 일반적으로 언급되는 증명 집합(Proof Aggregation)입니다.

직관적으로 볼 때, zkEVM에서 생성된 증명을 검증하는 것은 선형적인 과정입니다. 검증자(Verifier)는 생성된 각 증명 값을 차례로 검증해야 합니다. 그러나 이러한 검증 방식은 효율성이 낮고 통신 비용이 크며, zkRollup의 경우 검증자 측의 더 높은 비용은 더 많은 Layer1의 계산을 의미하며, 이는 더 높은 가스 요금으로 이어집니다.

먼저 예를 들어 보겠습니다: 앨리스는 전 세계에 자신이 이달 1일부터 7일까지 Fox 공원에 갔다는 것을 증명하고 싶어합니다. 이를 위해 그녀는 1일부터 7일까지 매일 그날의 신문을 들고 공원에서 사진을 찍을 수 있습니다. 이 7장의 사진이 하나의 증명이 됩니다.

그림 1: 일반적인 의미의 증명 집합 방안

위의 예에서 7장의 사진을 직접 하나의 봉투에 넣는 것은 직관적인 의미의 증명 집합입니다. 이는 실제 상황에서 서로 다른 증명을 연결하고 차례로 선형적으로 검증하는 것에 해당합니다. 즉, 첫 번째 증명을 검증한 후 두 번째 증명 및 이후의 증명을 검증합니다. 문제는 이러한 방법이 증명의 크기를 변경하지도 않고 증명의 시간을 변경하지도 않으며, 하나씩 증명하고 검증하는 것과 동일한 효과를 가진다는 것입니다. 로그 수준의 공간 압축을 달성하려면 아래에서 언급하는 재귀 증명(Proof Recursion)을 사용해야 합니다.

Halo2 및 STARK에서 사용하는 증명 재귀 방안

재귀 증명이 무엇인지 더 잘 설명하기 위해, 우리는 위의 예로 돌아갑니다.

앨리스의 7장의 사진은 실제로 7개의 증명입니다. 이제 이들을 합치기로 고려해 보겠습니다. 앨리스는 1일에 사진을 찍고, 2일에는 이 사진과 2일의 신문을 들고 사진을 찍고, 3일에는 2일에 찍은 사진과 3일의 신문을 들고 사진을 찍습니다. 이렇게 계속 진행하여 앨리스는 7일에 6일의 사진과 7일의 신문을 들고 마지막 사진을 찍습니다. 다른 친구들은 7일의 마지막 사진을 보고 앨리스가 1일부터 7일까지 공원에 갔다는 것을 검증할 수 있습니다. 이전의 7장의 증명 사진이 하나로 압축된 것을 볼 수 있습니다. 이 과정에서의 핵심 기술은 "사진이 포함된 사진"으로, 이전의 사진을 재귀적으로 이후의 사진에 중첩시킨 것입니다. 이는 많은 사진을 함께 놓고 다시 사진을 찍는 것과는 다릅니다.

zkRollup의 재귀 증명 기술은 증명 크기를 대폭 압축할 수 있습니다. 구체적으로, 각 거래는 하나의 증명을 생성하며, 원래의 거래 계산 회로를 C0, C0의 정확성 증명을 P0, P0를 검증하는 계산 과정을 V0라고 합시다. 증명자(Prover)는 V0를 해당 회로로 변환하여 C0'로 기록합니다. 이때, 다른 거래의 증명 계산 과정 C1은 C0'와 C1의 회로를 결합할 수 있습니다. 이렇게 되면 결합된 회로의 정확성 증명 P1을 검증하면, 위의 두 거래의 정확성을 동시에 검증한 것이 됩니다. 즉, 압축을 실현한 것입니다.

위의 과정을 되돌아보면, 사실 압축의 원리는 검증 증명의 과정을 다시 회로로 변환한 후 "증명에 대한 증명"을 생성하는 것입니다. 따라서 이 관점에서 볼 때, 이는 계속해서 아래로 재귀할 수 있는 작업이므로 재귀 증명이라고도 불립니다.

그림 2: Halo2와 Stark에서 사용하는 재귀 증명 방안

Halo2와 STARK에서 채택한 증명 재귀 방안은 증명을 병렬로 생성하고 여러 증명을 결합하여 하나의 증명 값을 검증하는 동시에 여러 거래 실행의 정확성을 검증할 수 있게 하여 계산 비용을 압축하고 시스템의 효율성을 크게 향상시킬 수 있습니다.

그러나 이러한 최적화는 여전히 구체적인 제로 지식 증명 알고리즘 위에 머물러 있습니다. 효율성을 더욱 높이기 위해, 우리는 더 낮은 수준의 최적화와 혁신이 필요하며, Fox가 설계한 FOAKS 알고리즘은 재귀의 개념을 증명의 내부에 적용하여 이를 실현했습니다.

FOAKS에서 사용하는 증명 재귀 방안

Fox Tech는 zkEVM 기반의 zkRollup 프로젝트입니다. 그 증명 시스템에서도 재귀 증명의 기술을 사용하지만, 그 내포는 위의 재귀 방식과 다릅니다. 주요 차이점은 Fox가 하나의 증명 내부에서 재귀(Recursion)의 개념을 사용했다는 것입니다. Fox가 사용하는 재귀 증명의 핵심 사상인 증명해야 할 문제를 계속해서 약화시켜, 약화된 문제가 충분히 간단해질 때까지의 과정을 설명하기 위해 또 다른 예를 들어 보겠습니다.

위의 예에서 앨리스는 사진을 찍어 특정 날에 Fox 공원에 갔음을 증명합니다. 그러자 밥은 다른 제안을 합니다. 그는 앨리스가 공원에 갔다는 증명을 앨리스의 휴대폰이 이 공원에 갔다는 증명으로 약화시킬 수 있다고 생각합니다. 그리고 이 증명은 앨리스의 휴대폰 위치가 공원의 범위 내에 있다는 증명으로 다시 약화될 수 있습니다. 따라서 앨리스가 이 공원에 갔음을 증명하기 위해서는 공원에 있을 때 휴대폰으로 위치 정보를 전송하기만 하면 됩니다.

이렇게 되면 증명의 크기는 원래의 사진(고차원 데이터)에서 3차원 데이터(위도, 경도 및 시간)로 줄어들어 비용을 효과적으로 절감할 수 있습니다. 이 예는 완벽하게 적절하지 않을 수 있습니다. 왜냐하면 누군가는 앨리스의 휴대폰이 Fox 공원에 갔다는 것이 앨리스 본인이 갔다는 것을 의미하지 않는다고 의문을 제기할 수 있기 때문입니다. 그러나 실제 상황에서는 이 약화 과정이 수학적으로 엄격합니다.

구체적으로, Fox의 재귀 증명의 사용법은 회로 수준의 재귀입니다. 제로 지식 증명을 수행할 때, 우리는 증명해야 할 문제를 회로로 작성하고, 그 다음 회로를 통해 충족해야 할 몇 가지 등식을 계산합니다. 이러한 등식이 충족된다는 것을 보여주는 대신, 우리는 다시 이 등식을 회로로 작성합니다. 이렇게 반복하여 마지막에 증명해야 할 등식이 충분히 간단해지면, 우리는 쉽게 직접 증명할 수 있습니다.

이 과정에서 우리는 이렇게 하는 것이 "재귀"의 의미에 더 가깝다는 것을 알 수 있습니다. 모든 알고리즘이 이 재귀 기술을 사용할 수 있는 것은 아닙니다. 만약 매번 재귀가 O(n) 복잡도의 증명을 O(f(n))의 증명으로 변환하고, 이 재귀 과정 자체의 계산 복잡도가 O(g(n))이라면, 재귀를 한 번 수행한 후 총 계산 복잡도는 O1(n)=O(f(n))+O(g(n))이 되고, 두 번 수행하면 O2(n)=O(f(f(n)))+O(g(n))+O(g(f(n)))이 되며, 세 번 수행하면 O3(n)=O(f(f(f(n))))+O(g(n))+O(g(f(n)))+O(g(f(f(n))))가 됩니다. … 이렇게 계속 진행됩니다. 따라서 f와 g 두 함수가 특정 k에 대해 Ok(n)<O(n)일 때만 이러한 재귀 기술이 효과적으로 작용할 수 있습니다. Fox에서는 이 재귀 기술을 효과적으로 사용하여 증명 복잡도를 압축했습니다.

그림 3: ZK-FOAKS에서 사용하는 재귀 증명 방안

결론

증명의 복잡도는 제로 지식 증명 응용에서 가장 중요한 핵심 중 하나입니다. 증명 복잡도라는 특성은 증명해야 할 일이 점점 더 복잡해짐에 따라 점점 더 중요해지며, 특히 zkEVM과 같은 대형 ZK 응용 시나리오에서는 증명의 복잡도가 제품의 성능과 사용자 경험에 결정적인 영향을 미칩니다. 최종 증명의 복잡도를 낮추기 위한 여러 방법 중에서 핵심 알고리즘의 최적화가 가장 중요하며, Fox는 최전선 알고리즘을 바탕으로 정교한 재귀 증명 방안을 설계하고 이 기술을 활용하여 zkEVM에 가장 적합한 ZK-FOAKS 알고리즘을 개발하여 zkRollup 분야의 성능 주역이 될 것으로 기대됩니다.

참고 문헌

1. https://blog.csdn.net/weixin_44383880/article/details/126338813
2. https://blog.csdn.net/freedomhero/article/details/126727033