영지식 스나크

지캐시(Zcash)

영지식 스나크(zk-SNARKs)는 'zero-knowledge Succinct Non-interactive Argument of Knowledge'의 약자로, 기존의 영지식 증명을 좀 더 간결하고(succinct) 비상호적인 환경(non-interactive)에서 적용 가능하도록 변형한 기술이다. 2012년 지캐시(Zcash)에 의해 개발되었다. 지캐시는 영지식 스나크를 기반으로 작동하고 있는 애플리케이션 중 가장 큰 규모이다.

개요

영지식 스나크는 그 특성들로 인하여 블록체인 환경에서 영지식 증명을 구현할 수 있게 되었다. 영지식 스나크를 활용한 블록체인 트랜잭션의 경우 수신자, 송신자, 전송금액 등의 정보를 노출하지 않고도 해당 트랜잭션의 유효성을 송수신 노드 외의 다른 노드들에게 알릴 수 있다. 영지식 스나크를 최초로 적용한 암호화폐는 지캐시가 있으며, 이외에 이더리움의 비잔틴 하드포크에도 관련 내용이 적용되었다.

스나크(SNARK)라는 약어 내에서 "간결한"(succinct)의 뜻은 증명의 크기가 작고 신속하게 확인할 수 있음을 나타낸다. 비상호작용(non-interactive)은 증명자와 검증자 사이의 상호작용이 거의 없거나 전혀 없다는 것을 뜻한다. 영지식 스나크가 개발되기 이전의 영지식 증명은 일반적으로 증명자와 검증자가 서로 통신을 주고받는 것을 요구하므로 간접적 영지식 프로토콜으로 간주된다. 반면에 비상호작용 구조에서는 증명자와 검증자가 하나의 증거만 주고받아도 된다. 영지식 스나크는 증명자와 검증자 사이의 신뢰할 수 있는 초기 설정에 의존한다. 즉 영지식 증명 및 개인거래를 구축하기 위하여 일련의 고객 매개 변수가 필요한 것이다. 이 매개 변수는 게임의 규칙과 거의 상응하며 프로토콜에 인코딩되어 트랜잭션이 유효하다는 것을 증명하기 위해 필요한 요소이다. 그러나 매개 변수가 매우 작은 그룹에 의하여 공식화 되는 경우가 있기 때문에 잠재적으로 중앙 집중화 문제가 존재한다.

초기 공개 설정은 지금의 영지식 스나크가 구현되기 위한 밑바탕이지만 개발자들은 프로세스에 필요한 신뢰과정을 최소화하기 위한 다른 대안을 찾기 위해 많은 노력을 기울이고 있다. 초기 설정 단계는 위조 지출을 막기 위해 매우 중요하다. 악의를 품은 누군가가 매개 변수를 생성하는 무작위성에 접근하여 검증자에게 유효할 것이라 판단되는 거짓 증명을 만들 수 있기 때문이다. 지캐시에서 초기 설정 단계는 매개 변수 생성 의식으로 알려져 있다.</ref> SNARK의 논쟁(Argument)에 대해 설명해보자면, 영지식 스나크는 계산적으로 확실한 것으로 간주된다. 따라서 증명자의 컴퓨팅 능력이 제한적이라고 가정했을 때, 정직하지 않은 증명자는 시스템을 속일 확률이 매우 낮다. 이러한 속성은 건전성으로 알려져 있지만, 이론적으로는 충분한 컴퓨팅 능력을 가지고 있는 증명자는 가짜 증명을 만들 수 있다. 이것이 많은 사람들이 양자 컴퓨터를 영지식 스나크 및 블록체인 시스템에 대한 위협 중 하나로 간주하는 이유이다. 약어의 마지막 부분인 K는 지식(Knowledge)이다. 이는 증명자가 실제로 자신의 진술을 뒷받침할 수 있는 지식이 없는 증거는 만들 수 없다는 것을 의미한다. 영지식 증명은 매우 신속한 검증이 가능하며 비트코인 트랜잭션보다 더 적은 데이터를 차지한다. 이것이 영지식 스나크 기술이 프라이버시 및 확장성에 대한 솔루션으로 사용되는 이유 중 하나이다.

특징

• 확장성

영지식 스나크를 이용하여 블록체인의 확장성을 해결하고자 하는 움직임이 많이 늘어나고 있다. 실제로 블록체인 참여자가 블록의 내용을 알지 못하더라도 전체 노드 중 증명 및 보고의 역할을 수행하는 노드가 블록의 내용이 위변조 되지 않았음을 빠르게 검증할 수 있다. 이는 참여자들의 블록 싱크(block sync) 속도를 급격하게 높여주어 새로운 참여자들이 빠르게 네트워크에 참여할 수 있게 해준다.

블록체인의 추가 전용(append-only)의 속성으로 블록체인의 용량은 시간이 지날수록 계속해서 커진다. 특히 이더리움에서는 trie 형태의 여러 글로벌 자료 구조(Global Data Structure : state trie, transaction trie, receipt trie 등)가 쌓여가고 있다는 문제점이 있다. 이 trie 구조에는 각종 스마트 계약 코드와 저장소 등 수많은 데이터들이 자리를 차지하고 있는데, 영지식 스나크를 통해 실제 데이터를 가지치기(pruning)하고 오직 데이터에 대한 증명만 남기는 방식으로 데이터를 압축시켜 계약이 차지하는 공간을 절약할 수 있다. 스마트 계약의 코드와 저장소를 체인 위에 공개하지 않고도 state change를 증명하는 것이 가능하기 때문이다.

• 타원곡선 암호화

영지식 스나크는 주어진 문제를 변형하고 간결함을 더했지만 아직 정보를 숨기는 것, 즉 Zero-Knowledge를 구현해내지 못했다. 이를 위해 영지식 스나크는 타원곡선암호 알고리즘(Elliptic Curve Algorithm)을 이용했다. 이는 큰 의미에서 ‘일반적인 계산을 타원 곡선 세계 위로 가져온다’라고 할 수 있다. 타원곡선의 세상에는 정보는 숨기고 등식만 증명하는 것이 가능하기 때문이다. 즉, 증명하고자 하는 A(t_0) * B(t_0) — C(t_0) = H(t_0) * Z(t_0) 등식을 타원 곡선 위에서 증명하는 것이다.

과정

기존의 비상호작용 구조에서는 증명자가 항상 온라인 상태일 필요가 없다는 장점이 있지만 증명을 완료하는데 까지 상당한 시간이 걸린다는 치명적인 약점이 있다. 암호학에서 사용되는 숫자의 크기는 상상할 수 없을 만큼 크기 때문에, 보기에 매우 간단한 연산도 상당히 많은 횟수의 명령(instruction)을 수행한 후에야 결과를 도출할 수 있다.

간결함은 영지식 스나크의 핵심 키워드이다. 상호작용 증명 시스템(interactive proof system)은 검증자가 한정된 계산 자원을 가지고 있음을 전제로 한다. 증명자가 특정한 지식을 알고 있다는 증거로 제출한 증명이 상당히 많은 양의 데이터를 포함하고 있다면, 이 증명은 굉장히 비효율적이다. 따라서 영지식 스나크에서는 비상호작용 영지식 증명의 크기를 줄이고 빠른 시간 내에 검증을 수행할 수 있도록 하여 비상호작용 영지식 증명의 실용성을 극대화하였다. 영지식 스나크는 다음과 같은 세 과정으로 이루어지며 이를 통해서 검증자는 증명자의 지식를 직접 확인하지 않고도 빠른 시간 내에 이를 검증 할 수 있게 된다.

• Keygen : key generator G를 이용해 key pair (pk, vk)를 생성하는 과정

증명자가 알고 있다고 주장하는 값인 witness(w)가 있다. 이때 이를 매개변수로 받는 특정 프로그램 C가 있다고 하자. 프로그램 C는 다음과 같다고 가정한다.

function C(x, w) {
return ( hash(w) == x) ;
}

이와 같이 내가 w를 알고 있음을 증명할 수 있는 프로그램 C와 무작위표본추출 시드(random sampling seed)인 람다(lambda)를 제네레이터에 매개변수로 집어넣음으로써 키 쌍를 생성할 수 있다. 여기서 람다는 증명자 및 외부에 노출되어서는 안 된다. 왜냐하면 이 값을 알고 있는 증명자가 거짓 증명를 생성할 수 있기 때문이다. 그렇기 때문에 키 생성은 검증자가 수행하게 된다.

* G(C, lambda) = (pk, vk)

* pk = proving key

* vk = verifying key

C의 program size bound를 1, input(x) size의 bound를 n, execution time bound를 T라고 할 때, 키 생성의 시간 복잡도는 아래와 같다. 즉, 프로그램이 길고, 투입 사이즈가 크고, 실행 시간이 길수록 키 생성에 소요되는 시간이 길다.

O (1 + n + T) · log(1 + n + T)

• Prove : prover가 proof(prf)를 생성하는 과정

증명 알고리즘을 P, 증명하고자 하는 증인인 w, w의 해시를 x라고 할 때, 증명을 구하는 방법은 다음과 같다. 증명자는 prf를 계산한 후, 검증자에게 prf만을 전달한다. prf을 계산하는 데 걸리는 시간은 입력값 x와 w의 크기에 비례하여 길어진다. prf가 계산된 이후에는 당연히 prf로부터 w값을 유추할 수 없으며, prf의 길이는 매우 짧다. 이는 기존의 영지식 증명이 가지고 있지 않은 간결함의 특성을 갖게 해주는 요소이다.

prf = P(pk, w, x)

• Verify : verifier가 prf를 verifying하는 과정

검증자는 증명자로부터 prf를 전달받은 후, 검증 알고리즘 V(verifying algorithm V)를 수행하여 prf의 진위 여부를 판단한다. 검증에 걸리는 시간은 매우 짧은데, 이 역시 영지식 스나크가 간결함의 특성을 가지는 요소 중 하나이다. 아래 값이 TRUE이면 증명자는 w값을 정말 알고 있다고 할 수 있고, FALSE이면 증명자는 w값을 속였다고 판단할 수 있다.

boolean : v(vk, x, prf)

활용

지캐시

지캐시(Zcash)는 영지식 스나크를 개발하였으며, 영지식 스나크를 기반으로 작동하고 있는 애플리케이션 중 가장 큰 규모이다. 지캐시는 영지식 증명을 바탕으로 완전한 익명성이 보장된 트랜잭션의 전송을 가능하게 한다. 기본적인 작동방식은 비트코인과 상당히 유사하나, 지캐시는 두 가지 종류의 주소를 가지고 있다는 것이 비트코인과 지캐시의 차이이다.

사용자들은 Shielded address와 Transparent address의 두 주소를 사용하여 지캐시의 화폐인 ZEC 거래를 공개적으로 할지, 사적으로 할지 선택하게 된다. Shielded address에서 Transparent address로 송금을 하면 거래된 ZEC는 공개가 되며 반대의 경우는 숨겨진다. 지캐시는 두 주소 체계의 공존을 통해 자금의 흐름을 추적하는 것을 거의 불가능하게 만들었다. 이는 지캐시가 익명 코인이라고 불리는 대표적인 이유 중 하나이다. 지캐시에 대해 자세히 보기

이더리움

이더리움(Ethereum)의 플라즈마 사이드체인과 관련된 연구 중에서도 영지식 스나크를 활용한 사례가 등장하고 있다. 그동안 일반 상태 플라즈마 체인의 가장 큰 문제점은 사이드체인의 정합성을 온체인에서 간결하게 증명하는 데 큰 어려움이 따른다는 것이었다. 영지식 스나크는 이를 해결하기 위한 힌트를 제공해준 셈이다. 비탈릭 부테린이 제안한 이더리움의 온체인 스케일링 솔루션 중 하나인 롤업(roll up) 또한 영지식 스나크를 활용하여 이론적으로 하드포크 없이 이더리움의 TPS를 10~30배까지 확장하는 기술이다. 그는 영지식 스나크를 통해 네트워크가 개별보다 무리로 더 많은 트랜잭션을 처리하여 속도를 증가시킬 수 있게 하여 가까운 미래에 이더리움이 500TPS를 발생할 수 있을 것이라 예측했다.

또한 영지식 스나크를 이용하여 이더리움에서 ETH를 송금하는 트랜잭션을 발생시킬 때, 샌더(sender)와 리시버(receiver)에게 트랜잭션을 보낸 사실만을 공개하고, 그들의 잔고(balance)와 송금액(transfer amount)에 대한 상세 내용을 숨기는 전송 방식이 가능하다. 이더리움에 대해 자세히 보기

코다

코다(Corda)는 영지식 스나크를 블록체인의 확장성에 활용한 예시이다. 코다 프로토콜은 영지식 스나크를 기반으로 한 레이어2의 확장과 개인 정보 보호의 도입을 알린 바 있다. 영지식 스나크에서 검증자는 간결한 증명만으로 원본을 검증할 수 있게 되어 원본을 직접 검증할 필요가 없다. 코다는 일반적인 블록체인과는 달리 채굴자들이 트랜잭션의 원본 데이터 대신 자신들이 올바른 블록을 생성했다는 증명만을 블록에 담아 확장성 문제를 해결하고자 한다. 코다에 대해 자세히 보기

문제점

• 초기 신뢰 설정 : 영지식 스나크의 가장 큰 문제점은 신뢰기관(trusted party)의 존재이다. 프로토콜 내에서 신뢰기관의 역할은 매우 크며, 증명을 생성하는 데 있어서도 큰 비중을 차지하고 있다. 신뢰기관은 노출되면 안 되는 정보를 통해 거짓 증명(fake proof)를 생성할 수 있으며, 외부의 다른 집단과 공모할 가능성 또한 있다.

• 확장성 : 영지식 증명은 당사자 간의 거래를 위한 통신, 영지식 증명의 검증 등의 복잡성에 따라 더 높은 연산처리능력이 요구된다. 영지식 스나크의 경우, 복잡성이 증가할수록 점점 더 높은 연산처리능력이 필요하다. 또한 증명 데이터와 검증 과정이 획기적으로 간결해졌지만 증명자가 증명을 생성하는 시간이 매우 느리다는 문제점이 있다.

• 양자컴퓨터 공격 : 영지식 스나크는 ECDSA와 같은 키페어 알고리즘에 기반하지 않기 때문에 이론적으로 양자 컴퓨터 공격에 매우 취약하다고 알려져 있다. 소인수분해를 빠르게 처리할 수 있는 양자 알고리즘인 쇼어 알고리즘(Shor’s Algorithm)의 방식을 통해 공개키로부터 비밀키를 추출해 낼 수 있기 때문이다. 또한 타원곡선암호 기법으로 암호화를 하기 때문에 연산능력이 뛰어난 양자컴퓨터로 그 암호를 빠르게 해독하여 무기력할 가능성이 있다.

참고자료

• Jungwoo Pyo, 〈Zero-Knowledge proof :: chapter 1. Introduction to Zero-Knowledge Proof & zk-SNARKs〉, 《미디엄》, 2018-07-26
• Seonghwa Yun, 〈블록체인에서의 개인정보보호 기술, zk-SNARK (1)〉, 《미디엄》, 2018-10-08
• 〈zk-SNARKs 와 zk-STARKs 설명〉, 《바이낸스 아카데미》, 2019-02-26
• Jihyeok Choy, 〈Zero-Knowledge proof :: chapter 2. Deep Dive into zk-SNARKs〉, 《미디엄》, 2019-03-18
• Rachel Rose O'Leary, 〈비탈릭 부테린 “영지식 스나크로 이더리움 초당 거래 500회 처리 가능”〉, 《코인데스크코리아》, 2018-09-25

같이 보기

• 영지식 증명
• 영지식 스타크
• 지캐시

이 영지식 스나크 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반