암호학에서 제로지식증명 기술은 웹3 세계에서 프라이버시 컴퓨팅, zkRollup 등 다양한 응용 분야를 가지고 있습니다. FOX의 Layer2 프로젝트에서 사용되는 FOAKS는 제로지식증명 알고리즘입니다. 위 응용 분야에서 제로지식증명 알고리즘에 대해 매우 중요한 두 가지 특성은 알고리즘의 효율성과 상호작용성입니다.
By: Frederick Kang, CEO of Fox Tech; Sputnik Meng, Chief Scientist of Fox Tech
암호학의 제로 지식 증명 기술은 웹3 세계에서 프라이버시 컴퓨팅, zkRollup 등을 포함한 다양한 응용 프로그램을 갖고 있습니다. FOX의 Layer2 프로젝트에서 사용되는 FOAKS는 제로 지식 증명 알고리즘입니다. 상기 응용 프로그램 시리즈에서 지식 제로 증명 알고리즘에 대한 두 가지 속성이 극도로 중요합니다. 즉, 알고리즘의 효율성과 상호 작용입니다.
알고리즘의 효율성의 중요성은 명백합니다. 효율적인 알고리즘은 시스템 가동 시간을 크게 줄일 수 있어 클라이언트 대기 시간을 감소시키고 사용자 경험과 효율성을 크게 향상시킬 수 있습니다. 이것이 FOAKS가 선형 증명 시간을 달성하기 위해 약속하고 있는 중요한 이유입니다.
반면에 암호학적 관점에서, 제로 지식 증명 시스템의 설계는 일반적으로 입증자와 확인자 간의 다수의 상호 작용을 필요로 합니다. 예를 들어, 다수의 인기있는 과학 기사에서 제로 지식 증명을 소개하는 "제로 지식 동굴" 이야기에서처럼 증명은 알리바바(입증자)와 기자들(확인자) 간의 다수의 정보 전달 상호 작용에 의존합니다. 그러나 실제로 많은 응용 분야에서 의존적인 상호 작용은 시스템을 사용할 수 없게 만들거나 대기 시간을 크게 증가시킬 수 있습니다. zkRollup 시스템에서처럼, FOX의 폴더인 입증자가 입증자와의 상호 작용에 의존하지 않고도 올바른 입증자 값을 로컬에서 계산할 수 있기를 기대합니다.
이 관점에서 상호 작용하는 제로 지식 증명 프로토콜을 비상호 작용으로 변환하는 방법은 매우 중요한 문제입니다. 본 문서에서는 FOX가 클래식 Fiatic-Shamir 휴리스틱을 사용하여 Brakedown에서 도전을 생성하여 비상호 작용 프로토콜을 구현하는 과정을 소개합니다.
제로 지식 증명 알고리즘은 응용 프로그램의 확산과 함께 극도로 인기를 얻었습니다. 최근 몇 년 동안 FOAKS, Orion, zk-stark 등 다양한 알고리즘이 포함되었습니다. 이러한 알고리즘의 핵심 논리 및 암호학의 초기 sigma 프로토콜은 입증자가 먼저 값을 확인자에게 보내고, 확인자가 지역 무작위 숫자를 통해 도전을 생성하고 생성된 도전 값을 입증자에게 보내는 것입니다. 입증자는 실제 지식을 갖고 있어야 하며 이에 대한 응답을 통해 입증자를 통과해야 합니다. 예를 들어, 제로 지식 동굴에서 기자가 동전을 던지고 알리바바에게 왼쪽이나 오른쪽에서 나오라고 할 때, "왼쪽과 오른쪽"은 알리바바에게 도전입니다. 그가 주문을 분명히 알고 있다면 요구되는 방향에서 나올 수 있지만 그렇지 않으면 실패할 확률이 반반이 됩니다.
여기서 도전의 생성은 중요한 단계이며, 무작위성과 증명 불가능성 두 가지 요구사항이 있습니다. 무작위성 안내서
보안을 보장합니다. 둘째, 증명자가 도전값을 예측할 수 있다면, 합의의 보안이 깨졌다는 뜻이며, 증명자는 지식 없이도 확인을 통과할 수 있습니다. 비슷한 예시를 들면, 알리바바가 리포터가 어느 쪽에서 오라고 부탁할지 예측할 수 있다면, 주문을 쓰지 않고도 미리 그 쪽에 들어갈 수 있고, 결과적으로 합의를 통과할 수 있다는 것을 보여줍니다.따라서 증명자가 로컬에서 예측할 수 없는 난수를 생성하고, 동시에 증명자에 의해 검증될 수 있는 방법이 필요하여, 비대화식 프로토콜을 구현할 수 있습니다.
해시 함수의 이름은 우리에게 친숙할 수 있습니다. 비트코인의 합의 프로토콜 POW에서 채굴 수학 문제로 사용되는 것부터 데이터 양을 압축하고, 메시지 검증 코드를 구축하는 등 다양한 방면에서 해시 함수가 사용됩니다. 이 모든 다른 프로토콜에서 실제로 해시 함수의 여러 속성을 사용합니다.
구체적으로, 안전한 해시 함수의 속성은 다음과 같습니다:
해시 함수가 충돌 저항성을 만족한다면, 단방향성도 만족해야 한다는 것에 주목해야 합니다. 즉, 출력 y가 주어졌을 때, h(x) = y를 만족하는 x를 찾는 것은 어렵습니다. 암호학에서 이론적으로 절대적으로 단방향성을 만족하는 함수를 구축할 수는 없지만, 해시 함수는 실제 응용에서 단방향 함수로 간주할 수 있습니다.
이러한 방식으로, 위의 여러 응용이 해시 함수의 다양한 속성에 해당한다는 것을 알 수 있습니다. 동시에, 해시 함수가 난수를 제공하는 데 중요한 역할을 한다고 말할 수 있습니다. 암호학 이론에서 요구되는 완벽한 난수 생성기는 현재 구축할 수 없지만, 실제 응용에서 해시 함수도 이 역할을 할 수 있습니다. 나중에 소개할 Fiat-Shamir Heuristic 기술의 기초를 제공합니다.
사실, Fiat-Shamir 휴리스틱은 이전에 생성된 스크립트를 해시하는 데 해시 함수를 사용하여 도전값으로 사용됩니다.
해시 함수 H가 무작위 함수로 간주되기 때문에, 도전값은 증명자의 공개 정보 및 약속과 독립적으로 균일하게 무작위로 선택됩니다. 보안 분석은 앨리스가 H의 출력을 예측할 수 없다고 가정하고, 그저 오라클로 취급할 수 있다고 가정합니다. 이 경우, 앨리스가 프로토콜을 따르지 않고 올바르게 응답할 확률 (특히 필요한 비밀을 모른다면)은 H의 범위의 크기에 반비례합니다.
이 섹션에서는 Fiat-Shamir 휴리스틱이 FOAKS 프로토콜에 적용되는 방법을 보여주며, 주로 Brakedown 부분을 생성하여 비대화식 FOAKS를 구현하는 도전을 합니다.
먼저, Brakedown 증명 생성 단계 중 도전해야 하는 부분은 "근사 테스트"와 Merkle Tree 증명 섹션입니다(이전 글 "FOAKS에서 다항 Commitment 프로토콜인 Brakedown"을 참조하십시오). 첫 번째로, 원래 프로세스는 증명자가 생성한 무작위 벡터입니다. 계산 과정은 다음과 같이 표시됩니다:
이제 해시 함수를 사용하여 증명자가 이 무작위 벡터를 생성하도록 합시다.
다음과 같습니다.
성립 조건자의 검증 계산에 해당하는 경우, 0을 계산하는 이 단계도 추가해야 합니다. 이 구성에 따라, 약속 생성 전에 도전 값을 사전에 예측할 수 없으므로, 증명자가 도전 값을 사전에 기반하여 "속일 수 없으므로 즉, 해당하는 거짓 약속 값을 생성할 수 없습니다. 동시에 해시 함수의 출력의 무작위성에 따라, 도전 값도 무작위성을 만족합니다.
두 번째로,
우리는 수정된 비대화식 Brakedown 다항 약속 내에서의 증명 및 검증 함수를 의사 코드로 제시하여 FOAKS 시스템에서도 사용합니다.
다양한 제로 지식 증명 알고리즘은 설계 초반에 증명자와 검증자 간의 상호작용에 의존하지만, 이 대화식 증명 프로토콜은 온 체인 데이터 개인 정보 보호 및 zkRollup과 같은 높은 효율성과 고 네트워크 통신 비용을 추구하는 응용 시나리오에 적합하지 않습니다. Fiat-Shamir 휴리스틱을 통해 프로버는 프로토콜의 보안을 해치지 않으면서 로컬에서 "도전"의 무작위 수를 생성할 수 있고, 이를 검증자가 확인할 수 있습니다. 이러한 방식으로 FOAKS도 비대화식 증명을 구현하고 시스템에 적용합니다.
1. Fiat, Amos; Shamir, Adi (1987). "How To Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.
2.https://www.cnblogs.com/zhuowangy2k/p/12246575.html
앱으로
