ZK 회로가 sqrt 연산을 직접 계산하지 않고 검증만으로 floor(sqrt(tokens))를 확인하는 원리

Context

ZK 영지식 증명 회로에서 sqrt 연산은 유한 필드 산술에서 직접 계산 시 매우 비용이 큽니다. 기존 솔리디티 방식으로는 제곱근 함수를 회로 내에 구현해야 하지만 이는 Lookup 테이블이나 반복 알고리즘으로 인해 회로 크기를 급격히 증가시킵니다.

Technical Solution

• 수학적 정의 w = floor(sqrt(tokens))를 직접 검증하는 방식으로 회로 설계
• w² ≤ tokens 그리고 tokens - w² < 2w + 1 조건을 두 개의 assert 문으로 확인
• 오프체인 타입스크립트에서 w와 w_sq를 사전 계산하여 회로에 witness로 전달
• 회로 내부는 subtraction과 comparison만 수행하여 cheap한 연산만 사용
• Part 1의 witness 패턴을 제곱근 검증 문제에 적용하여 구조 재사용

Impact

회로 내에서 expensive한 sqrt 연산 완전 제거, 오직 cheap한 부등식 검증만 수행

Key Takeaway

고비용 연산은 오프체인에서 계산하고 회로는 검증 전용으로 사용하여 회로 크기와 비용을 최소화하는 것이 ZK 설계의 핵심 원칙입니다.