엔지니어들을 위한 영지식 증명 소개 - (Dark Forest팀 글 번역)

donghyun·2022년 6월 17일
zero-knowledgezkSNARK블록체인영지식영지식증명
1

Zero Knowledge

목록 보기
1/1

이 포스트에서, 우리는 블록체인 공간에서 중요성이 커지고 있는 영지식 증명의 특정 브랜드인 zkSNARKs에 대해 이야기 할 것입니다.

우리는 사용방법과 어디에 유용한지를 다룰 것이며, 그리고 circom이라는 SNARK 구축 언어로 된 기본 zkSNARK를 또한 살펴볼 것입니다.

전제 조건

우리는 당신이 유한체를 이전에 마주친 경험이 있고 그들의 기본 특성들을 기억하고 있다고 가정합니다. 당신이 4⋅5 ≡ 6 in Fp\mathbb{F}_p 계산할 수 있다면 넘어가도 좋습니다.

영지식 증명이란 무엇인가?

영지식 프로토콜은 사실 자체에 대한 정보를 드러내지 않고 당신이 몇몇의 특정한 수학적 사실을 알고 있다는 것을 증명하는 것을 허용해줄 수 있는 프로토콜입니다. 영지식 증명이라고 불리는 증명은 영지식 프로토콜에서 생성됩니다.

영지식 증명을 만들 수 있는 "수학적 사실"의 몇 가지 예시는 다음과 같습니다.

  • 그래프의 세가지 색에 대한 지식(즉, 나는 잘알려진 그래프의 세가지 색상을 알고 나는 색상을 보여주지 않고 그 것을 알고 있음을 증명할 것입니다.)
  • modulo pp에 대한 몇개의 나머지의 이산 로그 지식(즉, 주어진 공개 generator g, 공개 modulus p, 그리고 some residue y, 나는 gx≡yg^x≡y modulo pp에서 xx를 압니다.)
  • 공개적으로 알려진 공개 키에 해당하는 개인 키에 대한 지식

영지식 프로토콜의 아이디어는 처음보면 역설적으로 보입니다: 내가 아는 것을 보여주지 않고 내가 안다는 것을 어떻게 증명할 것인가? 그러나, 우리는 실제로 영지식 프로토콜을 항상 사용하고 있습니다! 예시로, 디지털 서명같은 친숙한 툴들은 사실 영지식 증명입니다. 메시지에 서명하면서, 나는 내가 널리 알려진 공개 키에 맞는 개인 키를 안다는 것을 증명합니다. 사실, 공개 키 암호화는 영지식 프로토콜이기 때문에 작동합니다. 만약 서명이 개인 키에 대한 정보를 드러낸다면, 악의적인 행위자가 당신의 서명을 분석하고 개인 키를 복구한다음 당신을 가장할 수 있습니다.

조금 더 공식적으로, 알려진 함수 ff 그리고 비밀 입력값 ⋅에 대해 당신이 f(⋅)=yf(⋅)=y를 계산했다고 가정하세요. 함수 ff에 대한 영지식 프로토콜은 당신이 다른 사람에게 당신이 비밀 입력값을 드러내지 않고 비밀 입력값에 대한 ff의 결과 yy를 알고 있다는 것을 증명할 수 있게 해줍니다.

더 많은 영지식 증명을 알고 싶다면, 이 포스트를 참고하세요.

SNARKs가 무엇인가?

위에서 언급했듯이, 영지식 증명은 특정한 수학적 사실에 대한 지식을 증명할 수 있게 해주는 프로토콜입니다: 이산 로그, 개인 키에 대한 지식, 세가지 색상에 대한 지식, 등등. 그러나, 초기 영지식 증명은 한번에 한 가지 수학적 사실만 증명할 수 있었습니다. 즉, 암호학자들은 이산 로그에 대한 지식을 증명할 수 있는 프로토콜, 세 가지 색상에 대한 지식을 증명하는데 사용할 수 있는 프로토콜, 디지털 서명을 위한 프로토콜을 개발했습니다. 하지만 임의의 수학 함수에 대한 영지식 증명을 생성하고 싶다면 어떻게 해야 할까요? 예를 들어 - SHA256 해시 출력의 사전 값를 알고 있음을 증명할 수 있는 영지식 프로토콜을 원한다면? 모든 사용 사례에 대해 암호학자에게 맞춤형 새 프로토콜을 만들어 달라고 요구해야 한다면 다루기 힘들 것입니다.

zkSNARKs는 이 문제를 해결합니다. zkSNARK는 모든 수학적 함수에 대한 영지식 증명을 생성하는데 사용할 수 있는 가제트이다. 기본적으로, 당신은 zkSNARK에 함수 ff에 대한 "code"를 입력하고, SNARK가 ff에 대한 영지식 증명을 만들 수 있는 프로토콜을 생성합니다.

예를 들어, 가짜 "해시" 함수 h(x)=x3−x+7h(x)=x^3-x+7를 가지고 있고 우리가 영지식 증명을 만들고 싶어한다고 생각해봅시다. 첫 째로, 우리는 zkSNARK를 사용해 hh에 대한 영지식 증명을 만들 수 있습니다. 그 다음, 우리는 만들어진 영지식 증명을 사용하여 "나는 h(⋅)=67h(⋅)=67인 ⋅의 값을 안다."(⋅를 드러내지 않으면서)라는 주장을 증명할 수 있습니다. zkSNARKs는 또한 이 과정이 "간단하고","비대화형"임을 보증합니다: 우리는 이 증명을 선형 시간에 생성할 수 있고, 다른 사람들은 우리(증명자)에게 추가 질문할 필요 없이 상수 시간에 확인할 수 있습니다. 함께, 이러한 특성들은 zkSNARK를 형성합니다: a Zero Knowledge Succinct Non-interactive ARgument of Knowledge.

사용자들이 증명 생성을 locally하게 할 수 있고, 짧은 증명을 상시 검증을 위해 짧은 증명을 시간 연산 비용이 비싼 스마트 컨트랙트에 업로드합니다. 이러한 특성들은 SNARKs를 블록체인 애플리케이션에 유용하게 만들어줍니다.

Dark Forest는 SNARKs를 어떻게 사용하나요?

Dark Forest의 핵심 메커니즘은 암호화된 "전장의 안개(fog of war)"입니다. 전장의 안개는 당신이 모든 플레이어들, 행성, 기타 관심 지점들이 유니버스의 어디에 있는지 위치를 자동적으로 알지 못하게 보장합니다; 당신은 그것을 발견하기위해 연산 자원을 소비해야합니다. 이 메커니즘은 zkSNARKs에 의해 보호됩니다.

전장의 안개가 있는 유니버스에서, 모든 플레이어들은 서로가 서로에게 프라이빗하고 숨겨져 있습니다. 이는 플레이어가 공개적으로 검사할 수 있는 이더리움 블록체인에 행성의 좌표를 업로드하지 않는다는 것을 의미합니다. 대신에, 각각의 플레이어는 그들의 좌표의 해시를 블록체인에 업로드합니다. 이 것은 플레이어들이 특정 위치에 "committed"된 상태로 있는 것을 보장하지만, 이더리움 데이터 계층에서는 위치를 결정할 수 없습니다.

zkSNARKs가 없다면, 명백한 공격 vector가 있습니다 - 플레이어가 실제 유효한 위치에 해당하지 않는 임의의 바이트 문자열을 업로드하고 게임의 무결성이 깨진 경우. 이것을 막기위해, Dark Forest는 플레이어가 실제로 알고 있는 유효한 좌표에 해당하는 해시를 제출하는지 보장하기 위해 플레이어들에게 모든 움직임에 대해 zkSNARKs를 제출하라고 요구합니다.

플레이어가 움직일 때, 그들은 또한 그들의 움직임이 "유효"한지에 대한 영지식 증명을 제출하라고 요구받습니다 - 당신은 너무 멀리 혹은 너무 빨리 움직일 수 없습니다. zkSNARKs가 없다면, 악의적인 플레이어가 이동하려는 곳이 자신의 위치 근처에 있다고 주장하며 불법적인 "텔레포트" 움직임을 만들 수 있습니다.(두 위치가 실제로 유니버스의 반대편에 있더라도). 다시 한번, 영지식 증명을 요구하는 것은 플레이어들을 정직하게 유지합니다. 체스 비유를 사용하기위해, 필요한 영지식 증명은 기본적으로 스마트 컨트랙트에 "나는 나이트를 움직입니다."라고 말합니다; 내 나이트를 어디에서 옮겼는지, 어디로 옮겼는지 말하지 않겠지만 이 증거는 합법적인 L자 모양으로 움직였다는 것을 증명합니다.

향후 블로그 게시물에서 Dark Forest 건설과 SNARKs에 대해 더 자세히 알아볼 것입니다!

Circom

위에서 언급했듯이, SNARKs는 함수를 취하고 해당 함수에 대한 영지식 증명을 출력하는 가제트입니다. 그럼 SNARK를 위해 함수에 "먹이"를 어떻게 줄까요?

SNARKs 함수들은 Circom언어의 circuits으로 쓰여 있습니다. 다음은 "가짜" 해시 함수에 대한 예제 circuit입니다, h(x)=x3−x+7h(x)=x^3-x+7.

코드를 입력하세요
// file: circuit.circom

template BadHash() {
	signal private input x;
    signal x_squared;
    signal x_cubed;
    signal output out;
    
    x_squared <== x * x;
    x_cubed <== x_squared * x;
    out <== x_cubed - x + 7;
}

component main = BadHash();

우리의 zkSNARK는 이 circuit을 가져와서, 씹고 증명 키와 확인 키를 뱉어냅니다. 증명 키는 BadHash(x) = out을 연산하는 증명자가 out의 이전 상태를 실제로 알고 있다는 증거를 생성할 수 있도록 합니다. 확인 키는 누구든지 그 증명을 out과 함께 검사하고, 증명자가 알려진 비밀 입력으로 연산을 정직하게 수행했다는 결론을 내릴 수 있습니다.

구체적으로, 증명자가 BadHash(4) = 67을 연산한다고 가정합시다. 증명자는 검증자에게 out = 67과 함께 그들의 증명을 제출합니다; 비밀 입력 x = 4는 제출하지 않으면서. 해당 증명의 검증자는 BadHash circuit의 소스 코드를 알고, 또한 out = 67과 증명자의 증명을 받았습니다. 검증자는 증명자가 out에 실제로 유효한 x, x_squared, x_cubed를 연산했는지 확인하기 위해 증명을 검사할 수 있습니다. 그러나, 검증자는 증명자가 (x = 4, x_squared = 16, x_cubed = 64)를 사용했는지 구체적인 값을 알 수 없습니다 - 단지 이러한 값이 올바르게 계산되었다는 것만 알 수 있습니다.

SNARK circuits을 우리에게 익숙한 일반적인 "함수"와 다르게 만드는 두 가지 요소가 있습니다.

첫 째로, BadHash는 세가지 작업만 사용합니다: 곱셈, 덧셈, 뺄셈. 초기 단계에서, SNARK 제약 조건은 이러한 작업으로만 제한됩니다. 나눗셈과 모듈로 연산 같은 작업을 할 수 있는 방법은 있지만, 그들은 모두 궁극적으로 작업이 덧셈과 곱셈으로 나누어집니다. 우리가 이러한 작업으로 제한된다는 사실은 SNARK 프로그래밍을 어렵게 만드는 부분입니다.

두 번째 문제는 SNARK의 각 신호가 유한체 요소이고, 모든 작업이 유한체 안에서 일어난다는 것입니다. 이것의 가장 분명한 의미는 소수, 분수, 음수 또는 77자리보다 큰 숫자에 대한 기본 개념이 없습니다. 이들 중 하나를 원한다면, p보다 작은 양의 정수로 만들어야 합니다. 또 다른 의미는 연산자가 "wrap around"되는 것: 3 - 5의 결과는 p - 2이고, 이것은 77자리 숫자입니다. 소수는 충분히 커서(254) 대부분의 경우 이것이 중요하지 않습니다. 하지만 때때로 미묘한 정확성 버그를 일으킬 수 있습니다.

실제로 증명을 만들기 위해, 우리는 Jordi Baylina와 Iden3가 구축한 SnarkJS라는 라이브러리를 사용합니다. SnarkJS는 circuit을 사용하여 JavaScript 및 Solidity에서 증명 및 확인 코드를 생성하고, 뿐만 아니라 프로토콜 매개변수와 증명 및 확인 키도 생성합니다.

다음 포스트에서, 우리는 계산과 제약 조건의 차이를 포함하여 SNARKs의 실행 모델을 이야기할 것이며, 나눗셈과 모듈로 연산 같은 작업을 어떻게 수행하는지 알아볼 것입니다.


원문:
https://blog.zkga.me/intro-to-zksnarks

profile
donghyun
Blockchain

0개의 댓글