저자: Fox Tech CTO 린옌시, Fox Tech 수석 과학자 맹현지

서론

Prover와 Verifier 간의 계산 대리 개념은 제로 지식 증명의 핵심 내용 중 하나로, 증명자와 검증자의 작업량을 복잡도 사이에서 조절하는 도구입니다. 서로 다른 제로 지식 증명 알고리즘의 본질적인 차이는 계산 대리의 정도에 따라 다릅니다; 높은 대리는 검증의 계산을 쉽게 만들지만, 증명의 복잡도를 높여 증명 소요 시간이 길어지거나 생성된 증명의 크기가 커질 수 있습니다; 반대로 낮은 정도의 대리는 검증자의 비용을 증가시킵니다.

그림 1: 제로 지식 증명의 계산 대리 정도의 영향

계산 대리란 무엇인가

이더리움의 애플리케이션과 사용자 확장에 따라, 이더리움 메인넷의 혼잡도가 계속 증가하고 있으며, zkRollup을 사용한 Layer2 확장이 매력적인 솔루션이 되고 있습니다. FOX는 FOAKS 알고리즘을 사용하여 zkRollup을 수행하는 프로젝트입니다. zkRollup의 실행 가능성은 본질적으로 사용되는 제로 지식 증명 알고리즘의 원리의 실행 가능성에 달려 있습니다. 간단히 말해, 제로 지식 증명 알고리즘이 구현하는 기능은 증명자가 검증자에게 어떤 사실을 증명하되, 그 사실에 대한 정보는 전혀 누설하지 않는 것입니다. zkRollup의 구조는 이 특성을 활용하여 Layer2의 노드가 원래 Layer1에서 수행되던 계산을 실행하고, 동시에 Layer1 노드에 계산의 정확성을 증명하는 증명을 제공합니다.

보다 넓은 관점에서 보면, 위의 과정은 검증자(Layer1 노드)의 계산 능력이 제한적이기 때문에 이 부분의 계산을 증명자(Layer2 노드)에게 대리하여 수행하도록 한 것으로 이해할 수 있습니다. 증명자는 이 작업을 완료한 후 결과를 검증자에게 반환해야 합니다. 이러한 관점에서 우리는 제로 지식 증명 알고리즘이 정확성을 보장하는 "계산 대리"를 실현하게 한다고 말할 수 있습니다. 거시적으로 이러한 계산 대리의 예는 zkRollup과 같은 형태의 응용으로 나타날 수 있으며, 제로 지식 알고리즘 내에서도 이러한 계산 대리의 개념은 다양한 응용이 있습니다.

본 문서는 FOAKS가 Orion에서 언급한 Code-Switching을 사용하여 증명자가 검증자의 검증 계산을 수행하도록 돕는 과정과 FOAKS가 이 기술을 어떻게 적용하여 재귀를 수행하는지를 소개합니다. 이를 통해 증명의 크기와 검증자의 비용을 줄일 수 있습니다.

왜 계산 대리가 필요한가

시스템의 실용성 관점에서 볼 때, 많은 경우 계산 노드의 계산 능력은 제한적이거나 계산 자원이 매우 귀중합니다. 예를 들어, Layer1 체인에서의 모든 계산(전송 및 계약 호출 포함)은 모든 노드의 합의를 거쳐야 하며, 사용자는 이를 위해 높은 수수료를 지불해야 합니다. 따라서 이러한 경우, 본래 합의 노드가 처리해야 할 계산을 "대리하여" 체인 외부 노드에게 수행하도록 하는 것은 자연스러운 생각이며, 체인 상의 자원 소모를 피할 수 있습니다. 이것이 바로 FOX가 집중하고 있는 체인 외부 계산 서비스입니다.

암호학 이론 관점에서 볼 때, GMR 모델에서는 증명자가 무한한 계산 능력을 가지고 있고, 검증자는 다항식 계산 능력을 가진 것으로 제한됩니다. 만약 검증자도 무한한 능력을 가진다면, 제로 지식 증명의 기본 성질을 만족할 수 없습니다. 따라서 자연스럽게 계산을 증명자 쪽으로 기울여 증명자가 더 많은 계산을 부담하도록 하는 것은 많은 제로 지식 증명 알고리즘 설계에서 고려하는 문제입니다.

물론, 이를 실현하기 위해서는 특별한 기술이 필요합니다.

Code Switching

이 섹션에서는 Orion에서 사용된 Code Switching 기술을 소개합니다. Orion과 FOAKS는 모두 다항식 약속 계획으로 Brakedown을 사용하며, Code Switching은 Orion에서 증명자가 검증자의 검증 계산을 수행하는 과정을 지칭합니다.

《FOAKS의 다항식 약속 프로토콜 Brakedown을 이해하는 한 문서》에서 우리는 검증자의 검증 계산이 다음과 같은 과정임을 소개했습니다:

idxI,C0[idx]==\<0,C1[:,idx]>and EC(y0)==C0

idxI,C1[idx]==\<r0,C1[:,idx]>and EC(y1)==C1

이제 증명자가 이 부분의 계산을 맡게 되면, 증명자는 이러한 계산을 수행하는 것 외에도 자신의 계산이 정확하다는 것을 증명하기 위해 증명 값을 첨부해야 합니다.

방법은 위의 등식을 R1CS 회로로 동일하게 작성하는 것입니다:

Statement:

EC(y0)=C0, EC(y1)=C1

idxI,C0[idx]=\<0,C1[:,idx]>and EC(y0)=C0

idxI,C1[idx]=\<r0,C1[:,idx]>and EC(y1)=C1

y=\<r1, y1>

idxI, EC(C1[:,idx])는 ROOTidx와 일치하며, ROOTidx의 머클 트리 증명이 유효합니다.

그 후 Virgo 알고리즘을 사용하여 검증합니다.

FOAKS에서의 계산 대리

FOAKS에서도 유사한 기술을 사용하여 계산 대리를 완료합니다. 주목할 점은 FOAKS가 Fiat-Shamir 휴리스틱 기술을 사용하여 비상호작용 증명을 구현했다는 것입니다. 더 알고 싶으신 독자는 《상호작용 증명을 비상호작용으로 변환하는 방법? Fiat-Shamir 휴리스틱!》을 참조할 수 있습니다. 따라서 FOAKS의 도전 생성은 Orion에서 사용된 Code Switching 방법과 다르며, 회로에 새로운 등식을 추가해야 합니다:

0=H(C1,R, r0,r1)

I=H(C1,R, r0,r1,c1,y1,c0)

이렇게 하면 FOAKS의 증명자도 대리 검증자를 위한 검증 계산 증명을 생성하게 됩니다. 증명 검증 과정에 대해서는 FOAKS가 알고리즘 자체를 이용하여 반복적으로 수행하며, 이것이 FOAKS가 재귀를 구현하는 핵심 내용입니다. 구체적인 내용은 《어떻게 정교한 증명 재귀 계획을 설계할 수 있을까》를 참조하십시오.

일정 횟수의 반복을 통해 증명의 크기를 압축할 수 있으며, 이는 검증자의 계산 부담과 통신 복잡도를 크게 줄이는 효과를 가져옵니다. 이것이 FOAKS라는 제로 지식 증명 솔루션이 FOX의 zkRollup에 미치는 중요한 의미입니다.

결론

zkRollup에서 사용되는 제로 지식 증명 알고리즘의 계산 대리 정도는 세심하게 설계되어야 하며, 전체적으로 최적의 효율을 달성하기 위해 적절해야 합니다. FOAKS 알고리즘은 자체 반복 재귀를 통해 조절 가능한 계산 대리를 구현하여 zkRollup을 위해 특별히 설계된 제로 지식 증명 알고리즘입니다.

참고 문헌

1. Orion: Xie, Tiancheng, Yupeng Zhang, and Dawn Song. "Orion: Zero knowledge proof with linear prover time." Advances in Cryptology--CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15--18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022.