그로스16 증명의 가단성에 대하여
Groth16 증명의 중요한 속성 이해하기
Move Sui 에서 사용자는 효율적이고 널리 사용되는 영지식 간결 비대화형 지식 인수(Zk-SNARK)인 Groth16을 사용하여 모든 비결정적 다항식 시간(NP) 문을 효율적으로 검증할 수 있으며, 이는 유용한 영지식 증명 시스템의 일종입니다.
영지식 증명은 블록체인에서 개인 정보 보호와 보안을 강화하기 위한 핵심 암호화 방식입니다. 영지식 증명을 사용하면 한 당사자("증명자")가 기밀 세부 정보를 공개하지 않고도 다른 당사자("검증자")에게 어떤 진술이 참임을 증명할 수 있습니다. 예를 들어, 증명자는 퍼즐의 해답을 공개하지 않고도 자신이 퍼즐의 해답을 알고 있음을 증명할 수 있습니다.
그로스16은 정확성, 건전성, 영지식이라는 고전적인 비대화형 영지식(NIZK) 속성을 만족합니다. 또한 검증 증명을 생성하는 당사자가 실제로 유효한 해법을 알고 있다는 것을 의미하는 지식 건전성이라는 더 강력한 속성도 만족합니다. 그러나 Groth16을 사용하여 더 큰 애플리케이션의 일부로 NIZK를 인스턴스화할 때, 개발자는 해당 NIZK에 필요한 속성이 원래 Groth16 시스템에서 제공되는지 확인해야 합니다. 시뮬레이션 건전성, 실제 시뮬레이션 건전성, 전복 저항성, 시뮬레이션 추출 가능성 등 애플리케이션에 필요할 수 있는 몇 가지 추가 속성이 NIZK에 있습니다. Groth16은 그 자체로는 이러한 속성 중 많은 부분을 만족시키지 못한다는 것은 문헌에 잘 기록되어 있습니다. 그러나 Groth16이 멤버십의 ZK 인수로 사용될 때 이러한 속성의 부재는 시스템의 의도된 보안 또는 개인 정보 보호 속성에 방해가 되지 않습니다.
그로스16 증명은 무작위화가 가능하기 때문에 공개적으로 새로운 증명문을 생성할 수 있습니다. 즉, 증명자가 전송한 증명이 동일한 진술에 대한 유효한 증명으로 남아 있더라도 완전히 다른 것처럼 보이도록 스크램블할 수 있습니다. 실제로 재난수성은 일부 애플리케이션에서 기능으로 사용되었습니다. 그러나 애플리케이션 개발자는 특정 시나리오에서 이중 지불 공격을 방지하기 위해 이 속성을 주의 깊게 이해해야 합니다. 특히, 애플리케이션 계층에서는 동일한 명세서에 대한 두 개의 서로 다른 증명을 동일한 지출 행동에 해당하는 것으로 간주해야 합니다.
이 속성에 대한 비유로 앨리스와 밥이 비밀 메시지를 전달하기 위해 A가 K, B가 D, C가 M인 시저 코드북이라는 이름의 코드북을 공유한다고 가정해 보겠습니다. 앨리스는 "Hello" 메시지를 암호화하여 IFOOR가 되도록 합니다. 비밀 전송을 관찰하고 있는 이브는 예를 들어 모든 문자를 5씩 이동하는 등 메시지를 더 스크램블할 수 있습니다. 새로운 메시지는 (NKTTW, 5)가 됩니다. 밥은 먼저 5씩 역변환한 다음 코드북을 역으로 적용하여 이 메시지를 해독할 수 있습니다. 여기서 중요한 점은 앨리스와 밥의 통신은 여전히 비밀로 유지되지만, 동시에 이브는 메시지를 완전히 다르게 보이도록 스크램블할 수 있다는 것입니다. 암호화 대신 증명을, 비밀 평문 대신 비밀 증인을, 복호화 대신 검증 가능성을 사용하는 Groth16 NIZK에도 동일한 비유가 적용됩니다.
많은 애플리케이션에서 Groth16은 서명에 대한 영지식 증명(ZKPoK)을 제공하는 데 사용됩니다. 이러한 애플리케이션에서 Groth16은 시뮬레이션 추출 가능성이라는 속성을 제공하지 않는다는 점을 알아두는 것이 중요합니다. 이 속성에 대한 직관적인 설명은 다음과 같습니다. SP1로 지정된 두 개의 스도쿠 퍼즐과 관련 퍼즐 SP2가 있고, 두 퍼즐 모두 해를 가지고 있다고 가정해 보겠습니다. 정직한 당사자가 자신이 SP1의 해를 알고 있다는 증명인 파이를 게시합니다. SP2에 대한 완전한 해를 모르는 공격자가 SP2를 풀었다고 주장하는 증명 pi'를 생성할 수 있을까요? 두 퍼즐 모두 해를 가지고 있기 때문에 이러한 공격자는 NIZK의 고전적인 건전성 속성을 위반하지 않을 것입니다.
이러한 대부분의 애플리케이션을 안전하게 인스턴스화하기 위해서는 약한 시뮬레이션 추출 가능성 속성을 만족하는 것으로 충분하다는 것이 밝혀졌습니다. 다행히도 Groth16은 몇 가지 기술적 개념이 충족된다면 이 약한 개념을 만족합니다. 안드리야 노바코비치와 코비 구르칸은 증명자가 이러한 모든 기술적 조건을 만족하도록 증명자를 수정하는 간단한 방법을 설명합니다. snarkjs와 arkworks 라이브러리에는 이미 이러한 수정 사항이 포함되어 있어 이러한 라이브러리를 사용하는 배포는 이러한 특정 공격으로부터 자유롭습니다.
특히 이러한 기술적 조건은 증명자만 사용하는 프로그램, 즉 이차산술 프로그램(QAP)과 1등급 제약 시스템(R1CS)의 표현에 부과됩니다. Groth16 검증기에는 이러한 입력이 필요하지 않으므로 이러한 요구 사항은 검증자보다 증명자 측에서 더 잘 처리될 가능성이 높습니다. 또한 모든 애플리케이션에 이러한 추가 속성이 필요한 것은 아닙니다. 따라서 이러한 강력한 속성의 보증을 수용하기 위해 Move 측에서 수정할 가능성은 낮으며, 대신 개발자가 애플리케이션에 적합한 안전장치를 통합하도록 권장합니다.
