왜 ZkRollup의 실행 가능성은 제로 지식 증명의 계산 에이전트 아이디어에서 발생하는가?

Written by: Ivan Lin, CTO of Fox Tech, and Sputnik Meng, Chief scientist of Fox Tech

Prover와 Verifier 간의 계산 에이전트 아이디어는 제로-지식 증명의 핵심 콘텐츠 중 하나입니다. 이것은 Prover와 Verifier 작업 부담 사이의 복잡성 균형을 잡는 도구입니다. 서로 다른 제로-지식 증명 알고리즘의 핵심 차이점은 계산 에이전트의 수준에서 나타납니다. 높은 수준의 프록시는 검증의 계산을 쉽게 만들지만, 프로브의 복잡성을 높일 수 있으며, 결과적으로 증명 시간이 길어지거나 생성된 증명의 크기가 커질 수 있습니다. 반대로, 낮은 수준의 프록시는 검증자를 더욱 비싸게 만들 수 있습니다.

컴퓨팅 에이전트란 무엇인가

이더리움의 애플리케이션 및 사용자 규모가 확대됨에 따라 Ethernet 메인넷의 혼잡도가 계속 증가하고, Layer2 확장을 위해 zkRollup을 사용하는 것이 매우 매력적인 방안이 되었습니다. FOX는 FOAKS 알고리즘을 zkRollup에 사용하는 데 초점을 맞춘 프로젝트입니다. zkRollup의 실현 가능성은 본질적으로 사용된 제로-지식 증명 알고리즘의 원리적 실현 가능성에 달려 있습니다. 간단히 말해, 제로-지식 증명 알고리즘의 기능은 프로버가 검증자에게 어떤 정보도 공개하지 않은 채로 무언가를 증명하게 하는 것입니다. zkRollup은 이러한 특성을 이용하여 Layer2 노드가 Layer1에서 수행되는 계산을 수행하고, 동시에 Layer1 노드에게 정확성의 증명을 제공할 수 있도록 구성되었습니다.

보다 폭넓은 의미에서, 위의 과정은 검증자의 계산 능력이 제한되어 있기 때문에 이 부분의 계산을 프로버(레이어 2 노드)에게 위임하는 것으로 이해될 수 있습니다. 프로버는 작업을 완료하고 검증자에게 결과를 반환해야 합니다. 이 관점에서, 제로-지식 증명 알고리즘은 정확성을 보장하는 "컴퓨팅 에이전트"의 실현을 가능하게 합니다. 매크로적으로는 이러한 종류의 컴퓨팅 에이전트 예는 zkRollup 응용 프로그램의 형태로 나타낼 수 있으며, 특정 제로-지식 알고리즘에서는 이러한 종류의 컴퓨팅 에이전트 아이디어에 다양한 응용이 있습니다.

본 문서는 FOAKS가 오리온에서 언급한 코드 스위칭에 사용하는 유효성 계산에 초점을 맞추어, 프로버가 검증자를 도와 수행하고, FOAKS가 이 기술을 재귀에 적용하는 방법과 이를 통해 증명의 크기와 검증자의 오버헤드를 줄이는 것에 중점을 두고 있습니다.

왜 컴퓨팅 에이전트가 필요한가

시스템의 실용적인 관점에서, 컴퓨팅 노드의 컴퓨팅 파워는 많은 경우 제한되어 있거나 컴퓨팅 리소스가 매우 소중합니다. 예를 들어, 레이어 1 체인 상의 모든 계산(전송 및 계약 호출 포함)은同의 승인을 받아야 합니다.

모든 노드와 사용자는 이를 위해 높은 수수료를 지불해야합니다. 따라서 이 경우에는 일반적으로 합의 노드가 처리하는 계산을 대리할 수 있도록 체인 아래의 노드에게 위임하는 것이 자연스럽습니다. 이는 체인 상에서 자원을 소비하는 것을 피하기 위해 '오프체인 컴퓨팅'에 초점을 맞춘 FOX의 목표입니다.

암호학 이론의 관점에서 GMR 모델에서는 증명자가 무한한 컴퓨팅 능력을 가지고 있고 검증자는 다항식 컴퓨팅 능력으로 제한됩니다. 검증자도 무한한 용량을 가지고 있는 경우, 제로지식 증명의 기본 속성을 만족시킬 수 없습니다. 따라서 증명자 입장에서 계산을 더 맡도록 틸팅하는 문제는 많은 제로지식 증명 알고리즘에서 고민하는 문제입니다.

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

코드 스위칭

이 부분에서는 오라이언에서 사용되는 코드 스위칭 기술에 대해 설명합니다. 오라이언과 FOAKS는 둘 다 다항식 커밋먼스 스키마로 브레이크다운을 사용하며, 코드 스위칭은 프로버가 확인자 대신 유효성 검사 계산을 수행하는 오라이언에서 명명된 프로세스입니다.

FOAKS의 다항식 커밋먼스 프로토콜에서 확인자의 확인이 어떻게 계산되는지에 대해 설명했습니다:

이제 만약 프로버에게 이 계산의 일부를 맡기면, 프로버는 계산을 수행하고 자신의 계산이 정확함을 증명하기 위해 증명값을 첨부할 것입니다.

이는 동일한 방정식을 R1CS 회로로 작성하여 수행됩니다:

그런 다음 버고 알고리즘이 사용되어 확인됩니다.

FOAKS에서의 컴퓨팅 에이전트

FOAKS에서는 FOAKS가 비대화식 증명을 구현한다는 점을 주목할 가치가 있습니다. 이는 비아트-샤미르 휴리스틱 기술 덕분에 이루어집니다. 자세한 내용은 비아트-샤미르 휴리스틱! 대화식 증명을 비대화식 증명으로 변환하는 방법!을 참조하십시오. 따라서 FOAKS의 '챌린지 생성'은 오라이언에서 사용된 코드 스위칭 방법과 다르며 회로에 새로운 방정식이 추가됩니다.

그럼 FOAKS의 프로버 역시 프록시 확인자에 의해 검증되는 계산 증명을 생성합니다. 검증 과정에서 FOAKS는 자체 알고리즘을 반복적으로 사용하며, 이는 FOAKS 재귀의 핵심 내용이기도 합니다. 자세한 내용은 우수한 증명 재귀 구조를 설계하는 방법을 참조하십시오.

일정 수의 반복을 통해 증명의 크기를 압축하여 검증자의 계산 부담과 통신 복잡도를 크게 줄일 수 있습니다. 이것이 FOX의 zkRollup에 대한 FOAKS 제로지식 증명 체계의 의의입니다.

결론

계산 프록시의 정도

제로 지식 증명 알고리즘은 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.