이 기사의 저자 Dongze는 Ambi Technology Community의 작은 파트너입니다. 그는 현재 스탠포드 대학에서 공부하고 있으며 그의 연구 방향은 암호학입니다. 이 기사 시리즈는 유명한 스탠포드 과정 "CS"에 대한 저자의 연구 노트에서 가져왔습니다. 251: 암호 화폐 및 블록체인 기술". 이 과정의 강사는 암호학의 마스터인 Dan Boneh입니다.
이 기사의 저자 Dongze는 Ambi Technology Community의 작은 파트너입니다. 그는 현재 스탠포드 대학에서 공부하고 있으며 그의 연구 방향은 암호학입니다. 이 기사 시리즈는 유명한 스탠포드 과정 "CS"에 대한 저자의 연구 노트에서 가져왔습니다. 251: 암호 화폐 및 블록체인 기술". 이 과정의 강사는 암호학의 마스터인 Dan Boneh입니다.
지난 학기 Stanford에서 저는 Dan Boneh를 따라 블록체인 및 디지털 통화 관련 기술을 배웠습니다. 이전 과정과 달리 올해 과정에는 영지식 증명이라는 새로운 챕터가 추가되었습니다. 사랑스러운 Dan과 그의 석사 박사 Ben Fisch가 차례로 우리에게 수업을 제공했고, 영지식 zkSNARK의 기원, 개념 및 실현에 대한 설명을 마치는 데 2주가 걸렸습니다.
머리말
머리말
1차 초고를 작성한 후 친구들과 공유했을 때 Proofread를 보니 많은 친구들이 배경 지식이 부족하다고 보고했습니다. 그래서 시작하기 전에 이 추가 섹션을 추가하여 이 기사를 이해하는 데 필요한 배경 정보를 표시했습니다.
서문을 읽은 후 텍스트를 시작할 수 있습니다.
첫 번째 레벨 제목
비트코인의 단점
Bitcoin에 대해 잘 알고 있다면 Bitcoin 네트워크에서 모든 거래가 공개된다는 것을 알아야 합니다.
A가 B에게 일정 금액을 지불하고자 한다면 A는 확성기를 통해 전체 네트워크에 자신이 새로운 트랜잭션(Tx)을 만들고 싶다고 알릴 것이며 이 트랜잭션의 수혜자는 B의 공개 키(P2PK)이거나, 공개 키의 해시(P2PKH). B가 거래를 보는 한 자신의 개인 키를 사용하여 디지털 서명에 서명하여 자신이 실제로 공개 키의 소유자임을 증명하고 돈을 쓸 수 있습니다.
A가 B에게 지불하기 위해 트랜잭션을 제출할 때 네트워크의 방관자 M으로서 그녀는 왜곡된 주소 bbbbb의 문자열에 x 코인을 지불하기 위해 왜곡된 주소 aaaaa의 문자열만 볼 수 있습니다. 그러다가 B가 C에게 돈을 보냈을 때 bbbbb가 ccccc에게 일정 금액을 보냈다는 것만 알 수 있었습니다. Bitcoin의 트랜잭션이 강하게 연결되어 있음을 알 수 있습니다. 누가 누구에게 돈을 보냈는지는 모르지만 덩굴을 따라가면 많은 거래 체인을 찾을 수 있습니다.
모든 사용자가 순종적으로 돈을 주고 받는다면 Bitcoin은 실제로 비교적 안전합니다.
사용자가 그것을 꿰뚫어 보고 더 이상 플레이하고 싶지 않고 거래소에서 현금화를 원하면 전체 체인의 거래 정보가 노출됩니다. 거래소에는 종종 KYC(Know Your Customer) 정책이 있으며 디지털 화폐와 법정 화폐를 교환하는 각 사용자는 실명 인증을 받아야 합니다. C가 ccccc 주소에서 돈을 인출하고 도망치면 bbbbb가 C에게 돈을 보낸 사실을 거래소가 파악한 것이다. C가 돈세탁 혐의를 받고 있다면 이때 B가 현금을 인출할 때까지 조용히 기다렸다가 잡으면 된다.
미국에는 이미 Chainalysis와 같이 비트코인에 대한 트랜잭션 체인 분석을 수행하는 많은 회사가 있습니다.
첫 번째 레벨 제목
익명 대 가명
프라이버시에 대한 우리의 이해는 실제로 두 가지 유형으로 나뉩니다.
첫 번째는 익명으로 사용자가 자신과 관련된 정보를 공개할 필요가 없으며 학교의 고백 벽과 같습니다.
두 번째는 가명(Pseudonymous)으로, 티에바와 같이 사용자가 스스로 만든 가명을 통해 정보를 게시하는 것을 의미하며, 사용자를 잘 모르면 대화명에서 실명으로 연결을 설정할 수 없습니다. , 그리고 게시물을 게시한 사람을 모르는 사람입니다.
이 분석에서 비트코인은 실제로 가명 메커니즘입니다. 각 사용자는 자신의 공개 키(가명)를 무작위로 생성하고 공개 키 주소를 통해 돈을 받습니다. 이것은 A/B/C/D 4명이 각각 Xiaoming/Xiaohong/Ergou/Xiaogang으로 익명으로 온라인 거래를 하는 것과 같습니다. Xiaoming/Xiaohong/Ergou와 D의 관계는 즉시 노출됩니다.
첫 번째 레벨 제목
보조 제목
CoinJoin
A가 B에게 지불하는 것은 남들이 볼 것이고, C가 D에게 지불하는 것도 남들이 볼 것이기 때문에, 누군가는 단순히 ABCD라는 네 사람을 하나의 거래에 집어넣는 것이라고 생각했습니다. 비트코인 거래는 여러 입력과 출력을 가질 수 있기 때문에 구경꾼은 거래에서 aaaaa와 ccccc가 모두 x 코인을 넣은 다음 bbbbb와 ddddd가 돈을 받는 것을 볼 것입니다. 이처럼 거래소는 이들 주소가 ABCD 4명에 해당한다는 사실을 알더라도 누가 누구에게 돈을 받았는지 구분하기 어렵다.
두 거래 집합이 여전히 식별하기 너무 쉽다면 어떻게 됩니까? 둘은 넷에 충분하지 않고, 넷은 여덟에 충분하지 않습니다. 다양한 사람들의 거래를 통합하여 대중을 혼란시키고 추적이 불가능하게 만듭니다. 코인조인입니다.
코인조인의 단점은 무엇인가요? 사실 여러 거래를 섞어서 사람이 다른 사람에게 잡히는 것을 완벽하게 막을 수는 없고, 끝까지 잡히는 확률을 줄여준다고 할 수 밖에 없습니다. 그리고 AB와 CD 거래를 혼합하려면 거래량이 동일해야 한다는 또 다른 매우 중요한 점이 있습니다. A가 B에게 10,000코인을 지불하고 C가 D에게 1코인을 지불하는 경우 입력과 출력만 확인하면 CoinJoin 트랜잭션을 두 개의 독립적인 트랜잭션으로 즉시 분할할 수 있습니다. 따라서 거래 금액이 비슷한 거래를 혼합하여 매칭하는 것도 CoinJoin을 구현할 때 무시할 수 없는 어려움입니다.
보조 제목
비밀거래(사적거래/CT)
내가 누구인지 숨기는 것이 너무 번거롭기 때문에 사람들은 생각하기 시작합니다. 거래에 관련된 공개 키를 숨기지 않으면 거래 금액도 숨길 수 있습니다. A가 B에게 돈을 보낼 때 B가 노출되더라도 전체 네트워크는 A가 B에게 얼마를 줬는지 알 수 없습니다.
이 작업이 실현되면 Bitcoin을 사용하여 임금을 지불 할 수도 있습니다.월급이 도착하는 것만 볼 수 있지만 수입이 얼마인지는 알 수 없습니다.
이 방법을 구현하려면 먼저 특별한 암호화 알고리즘인 동형암호를 이해해야 합니다.
한 문장에서 동형암호는 암호문이 원래의 수학적 속성을 유지할 수 있도록 하는 특별한 암호화 알고리즘입니다.
암호화 방법 E가 있다고 가정할 수 있습니다. E가 추가 동형이면 E(a) + E(b) = E(a+b)입니다. 반대로 곱셈이 동형이면 E(a) x E(b) = E(axb)입니다.
이 기사는 zkp에 대한 대중적인 과학 기사이므로 구체적인 구현 방법을 자세히 이해하지는 않겠습니다. 우리는 타원 암호화 방정식과 RSA의 큰 숫자 모듈 모두 특정 동형 속성을 가지고 있다는 것을 이해하면 됩니다.
Pederson 약속
숨겨진 볼륨 주제로 이동합니다. A가 100코인의 잔액을 가지고 있고 B에게 10코인을 지불하면 트랜잭션은 다음과 같습니다.
위에서 언급한 가산 동형암호와 결합하여 가산 동형 암호화 방법 E가 있는 경우 이 트랜잭션을 다음과 같이 변환할 수 있습니다.
첫 번째 숫자가 마지막 두 숫자의 합과 같으면 구경꾼은 결국 거래량을 볼 수 없지만 그는 A가 실제로 돈의 일부를 B에게 주고 그 다음에는 일부를 B에게 주었다는 것을 인정해야 합니다. 돈은 A에게 반환되었습니다. 이 방식을 Pederson Commitment(Pederson Commitment)라고 하는데, 데이터 자체는 숨기지만 데이터 간의 관계를 증명하는 방식이다.
음수 취약점
이것을 읽은 후 일부 친구들은 큰 허점을 발견하게 될 것입니다. Pederson은 숫자 간의 관계를 증명하겠다고 약속했지만 숫자의 값 범위를 제한하지 않았습니다! 즉, A는 속임수를 쓰고 거래를 제출하고 B에게 -100 코인을 지불하고 싶다고 말한 다음 200 코인을 "찾을" 수 있습니다. 이런 식으로 방정식은 여전히 유효합니다. A는 이것을 사용하여 돈을 무한히 인쇄하여 전체 시스템을 파괴할 수 있습니다.
음수의 존재를 피하는 방법은 무엇입니까? Pederson의 약속 외에도 모든 거래의 숫자가 양수임을 증명하기 위한 또 다른 증거 세트가 필요합니다. 즉, 모든 트랜잭션의 숫자는 0에서 2^256(양의 정수의 최대값)까지의 범위(Range Proof)로 제한됩니다.
어렵지 않게 들리고 가장 쉬운 방법은 의심할 여지없이 이 모든 수치를 공개하는 것입니다. 그러나 이것은 트랜잭션 볼륨을 숨기는 전제를 무효화합니다. 그래서 우리는 다른 증명 방법을 찾아야 합니다. 즉, 원래 숫자를 드러내는 것이 아니라 그 특성을 증명하는 것입니다(값은 0에서 2^256 사이입니다). 그게 포인트처럼 들리나요? 걱정하지 마세요. 다른 질문을 살펴보겠습니다.
소유권 허점
더 진행하기 전에 이 프로토콜에는 실제로 소유권을 알 수 없는 큰 허점이 있다는 점을 빨리 지적하고 싶습니다.
비트코인에 대해 아는 친구는 비트코인 거래를 생성할 때 입력 거래의 UTXO Txid를 제공해야 B에게 지불할 A가 실제로 돈을 가지고 있는지 신속하게 확인할 수 있습니다.
그러나 지금은 이전 트랜잭션을 가리키는 것에 대해 언급하지 않았습니다. 즉, 전체 네트워크는 A가 얼마를 쓰는지 모르기 때문에 A는 단순히 입력 수를 수만, 수만으로 변경한 다음 모두 자신에게 호출하고 비밀리에 자신을 위해 코인을 주조할 수 있습니다.
이 문제를 해결하는 방법? 두 가지 옵션이 있습니다.
첫 번째 해결책은 비트코인의 트랜잭션 메커니즘을 계속 도입하고 마지막 개인 트랜잭션의 출력을 트랜잭션의 입력으로 사용하는 것입니다. 이런 생각은 약간 문제의 변형과 비슷합니다.이 거래는 이전 거래의 결과를 사용하므로 이전 거래가 괜찮다면 내 거래도 괜찮습니다.
이것은 닭이 먼저냐 달걀이 먼저냐의 문제입니다. 문제 없이 최초의 개인 트랜잭션을 생성하는 방법은 무엇입니까?
특별한 트랜잭션을 통해 일반 코인을 프라이빗 출력으로 전환할 수 있습니다. 이 트랜잭션의 입력은 기존 트랜잭션 ID(Bitcoin UTXO)이고 출력은 비공개 출력이 됩니다. 이런 식으로 우리는 가장 초기의 알을 연상시킵니다. (ZCash의 차폐 거래가 이 원칙입니다)
두 번째 체계는 A의 입력이 실제로 A에 속함을 증명하는 것입니다. Ethereum과 같은 시스템에는 World State라는 개념이 있습니다. 세계 상태는 전체 체인의 모든 사용자 및 스마트 계약의 현재 균형 및 상태입니다. 일반적으로 완전한 노드는 전체 세계 상태(크기가 큼)를 유지하는 반면, 가벼운 노드는 세계 상태의 Merkle Commit만 저장하면 됩니다.
Pederson Commitment 및 Interval Proof를 제출하는 것 외에도 트랜잭션에 입력된 숫자가 원래 World State의 A 잔고와 일치함을 증명하기 위한 추가 증명을 제공합니다. Merkle Proof를 사용하여 이 증명을 달성할 수 있습니다.
하지만 Merkle Proof를 직접 제출하면 모든 방관자가 A의 거래 입력을 볼 수 있어 개인 거래의 전제에 위배됩니다. 그래서 다시: 우리는 여전히 위에서 언급한 신비한 알고리즘을 빌릴 필요가 있습니다. 그것은 답 자체(A의 균형)를 숨길 수 있을 뿐만 아니라 이 숫자가 실제로 세계의 상태에 속한다는 것을 증명할 수 있습니다.
ZCash: 모두 익명
CT라는 개념이 제안되었을 때 많은 사람들이 현상 유지에 불만을 품고 자신의 이름을 숨길 수 있으면 좋겠다는 생각을 금할 수 없었습니다.
그래서 ZeroCoin/ZeroCash의 개념이 제안되었습니다. CT를 기반으로 하지만 트랜잭션 사용자를 익명으로 만들 수 있는 새로운 메커니즘이 추가되었습니다. 지금 참외를 먹고 있던 구경꾼 C는 인터넷에 떠도는 일그러진 글자를 보고 그것이 무엇인지 몰랐지만 사실이라고 믿어야 했습니다.
ZCash는 ZeroCoin/ZeroCash 프로토콜을 기반으로 구현된 디지털 통화로 완전히 익명으로 거래할 수 있습니다. 여기서 너무 많이 소개하지는 않겠지만 여전히 오래된 암호화 도구에 의존합니다. Pederson Promise, Interval Proofs, Merkle Proofs, 우리가 이야기해 온 Black Magic: 답 자체를 노출하지 않는 것 증명하다
첫 번째 레벨 제목
제로 지식 증명(zkSNARK)
위의 내용을 읽은 후 모든 사람이 우리가 해결하려는 문제에 대해 일반적인 이해를 했다고 생각합니다.
0 <= a <= 2^256 또는 SHA256(x) = y와 같은 숫자 간의 관계를 증명하려고 합니다. 그러나 우리는 위의 a 및 x와 같은 이러한 숫자를 노출하고 싶지 않습니다. 이를 달성하기 위해 시스템을 구축하는 방법은 무엇입니까?
이 주제에 대해 이야기하기 전에 생각을 바꾸고 이 주제를 제로 지식(zk)과 증명(SNARK)의 두 부분으로 나누고 싶습니다.
보조 제목
프루프(SNARK)
증거부터 시작하겠습니다.
SNARK의 전체 이름은 간결한 비대화형 지식 논쟁입니다. 이 명사는 세 가지 차원으로 구성됩니다.
짧음(간결): 증명 자체는 충분히 짧아야 하며 증명이 O(logN) 또는 심지어 O(1) 복잡도인지 확인하는 것이 가장 좋습니다.
비대화형: 전체 프로세스에는 상호 작용이 없습니다. 즉, 증명자는 테이블에 큰 문자열의 왜곡된 코드를 던진 다음 떠날 수 있으며 나중에 왜곡된 코드 문자열을 확인하여 그의 증명을 확인할 수 있습니다.
지식의 표현(지식의 주장): 이것은 상대적으로 모호합니다. 그러나 일반적인 의미는 증명하려는 것이 지식을 표현할 수 있어야 한다는 것입니다(Proof of Knowledge). PoK의 증명은 추출기(Extractor)라는 보다 추상적인 개념을 포함하고 있으며, 구체적인 내용은 Guo Yu 씨의 글을 참조하시기 바랍니다. 그러나 한 문장으로, 당신이 증명하는 것은 가치 있고 계산을 통해 얻은 것이지 다른 것을 가지고 장난하지 않습니다.
정의를 읽은 후 SNARK를 구현할 수 있다는 것만으로도 특히 간결함 측면에서 이미 매우 강력하다는 것을 알게 될 것입니다.
타사 조직이 자체 데이터베이스에 대량의 (PB 수준) 데이터를 저장하는 경우 애플리케이션을 즉시 생각할 수 있습니다. 정부 기관이 각 데이터 포인트에 문제가 없는지 확인하기 위해 데이터베이스를 감사하려는 경우 정상적인 상황에서 한 줄씩 읽고 데이터의 모든 PB를 읽고 시간의 끝을 확인해야 할 수 있습니다. 이때 갑자기 SNARK가 등장하는데, O(1) 또는 O(logN)의 크기와 시간은 이 거대한 데이터베이스에서 각각의 데이터가 문제가 없음을 충분히 증명했습니다. 대부분의 사람들은 이것이 완전히 불가능하다고 생각합니다. 어떻게 몇 개의 숫자로 수천만 개의 숫자의 정확성을 확인할 수 있습니까?
보조 제목
제로 지식(zk)
영지식(zero knowledge)으로 돌아가자.
사실, 영지식은 이 SNARK 증명을 기반으로 한 추가 요구 사항일 뿐입니다. 전체 증명 자체는 증명할 답변과 관련된 데이터를 공개할 수 없습니다. 영지식의 개념에 대한 공식적인 정의는 시뮬레이터(Simulator)라는 개념을 도입하여 매우 모호하다. 자세한 소개는 Guo Yu 씨의 기사를 참조할 수 있으며 여기에서 언급하겠습니다. 한 마디로 아무리 똑똑한 해커라도 영지식증명을 아무리 봐도 답 자체에 관련된 정보를 전혀 추출할 수 없다.
이 정부 감사 데이터베이스의 개념으로 돌아가서 이 데이터베이스가 회사의 납세 상황이라고 가정할 수 있습니다. 정부는 세금 데이터가 정확해야 하지만 기업의 경우 상업 비밀이 포함될 수 있기 때문에 조사관이 일상적인 비즈니스 흐름을 보는 것을 원하지 않습니다. 현재 단순한 SNARK로는 충분하지 않으며 다음을 달성하기 위해 zkSNARK가 필요합니다.
보조 제목
영지식 증명의 응용
zkSNARK로 무엇을 할 수 있습니까?
첫 번째는 위에서 언급한 프라이빗 트랜잭션(Confidential Transaction)이 실현될 수 있다는 것입니다. ZCash의 개인 거래 메커니즘은 zkSNARK를 기반으로 구현됩니다. 이러한 방식으로 디지털 통화 거래가 훨씬 더 안전해집니다.
두 번째는 이 기술을 사용하여 블록체인 효율성 문제를 더 잘 해결할 수 있다는 것입니다. 이제 의심할 여지 없이 블록체인 확장을 위한 몇 가지 방법이 있습니다. 합의 강도를 희생하여 블록 생성 속도를 높이거나, 사이드 체인을 활성화하거나, Lightning과 유사한 오프라인 지점 간 채널을 활성화합니다.
사실 롤업이라는 또 다른 아이디어가 있습니다. 롤업의 개념은 아마도 메인 체인의 부하가 너무 크기 때문에 트랜잭션을 수신하고 트랜잭션 인증을 수행한 다음 일정 기간 동안 누적된 모든 트랜잭션을 일괄 처리할 수 있는 작은 서버를 몇 개 더 엽니다. 메인 체인. 그러나 업데이트 프로세스가 여전히 많은 양의 트랜잭션 정보를 메인 체인으로 보내야 하는 경우 이 롤업의 의미는 존재하지 않으며 메인 체인의 부하를 줄이지 않습니다. 이때 SNARK가 유용합니다. SNARK(zk일 수도 있고 아닐 수도 있음)를 통해 롤업 서버는 메인 체인에 매우 짧은 증명을 제출하여 많은 수의 트랜잭션이 괜찮다는 것을 증명하고 메인 체인만 최종 결과를 따라야 합니다. 결과적으로 일부 UTXO를 더하거나 빼면 완료됩니다. ZK Rollup을 통해 메인 체인의 부하를 크게 줄이고 더 많은 검증을 다른 곳에 아웃소싱할 수 있습니다.
세 번째로, 우리는 제3자에 대한 거래를 실제로 실현할 수 있습니다.
A가 기계 학습 연구를 하고 있지만 좋은 컴퓨터가 없어서 모델 훈련 작업을 B에게 아웃소싱할 계획이라고 가정합니다. 3일 후 B는 A에게 자신이 달리기를 마쳤으며 훈련된 모델을 제공하기 전에 A에게 먼저 비용을 지불하도록 요청해야 한다고 말했습니다. A는 B가 정직한 훈련 모델이 없는 것을 걱정하고 임의로 임의의 숫자를 생성하여 패킹하므로 B가 비용을 지불하기 전에 모델을 A에게 검증하기를 원합니다. B씨는 A씨가 모델을 받고 몰래 복사한 뒤 돈을 내지 않고 직접 차단할까 봐 걱정이다.
이러한 종류의 문제에 직면한 전통적인 해결책은 제3자에게 위임하거나 체인에서 스마트 계약을 설계하여 데이터 및 통화의 검증 및 교환을 완료하는 것입니다. 이제 zkSNARK를 사용하여 B는 모델 훈련을 위해 zkSNARK를 A에게 직접 제출할 수 있으며, 그가 3일 동안 정직하게 달렸고 부정 행위를 하지 않았음을 증명합니다. A 빠른 인증을 거쳐야 안심하고 송금할 수 있습니다.
넷째, 데이터 소유권을 완전히 이전할 수 있습니다.
은행의 계좌 잔액 데이터베이스가 SQL 테이블이라고 가정하면 1억 명의 고객이 1억 행의 레코드를 갖게 됩니다. 매년 은행은 이러한 대규모 데이터 시스템을 유지하기 위해 많은 돈을 지출해야 합니다. 모든 사람이 자신의 레코드 행을 로컬로 이동하고 자신의 계정 데이터를 유지할 수 있다면 은행은 한 푼도 지출할 필요가 없습니다. 은행이 이렇게 하지 않는 이유는 사용자가 이익을 위해 자신의 데이터를 조작하여 100위안을 100만 달러로 바꿀 가능성이 매우 높기 때문입니다.
zkSNARK는 데이터 자체에 문제가 없음을 보장할 수 있습니다. 우리는 모든 사람의 예금 잔액이 각자의 컴퓨터에 저장되는 분산형 은행을 상상할 수 있습니다. A가 B에게 돈을 이체하고자 할 때, 그녀는 전체 네트워크에 zkSNARK를 제출하여 계정의 잔액이 올바르게 차감되었음을 증명해야 합니다. 그러면 A가 자신의 잔액에서 이체 금액을 정직하게 차감할 수 있습니다. B가 계정에 들어가면 잔액 증가에 해당하는 zkSNARK도 제출합니다.
계속되다
계속되다
공간상의 이유로 이번에는 여기서 멈추겠습니다. 아마도 이것을 본다면 영지식 증명이 왜 필요한지, 영지식 증명이 얼마나 강력한지 모두가 더 깊이 이해하게 될 것입니다.
다음 글의 시작 부분에서는 zkSNARK의 구체적인 구조를 중심으로 좀 더 심도 있게 글을 쓰도록 하겠습니다.
더 읽어보기
더 읽어보기
이 기사에서 언급된 내용에 대해 더 알고 싶다면 읽기 목록을 수집하여 아래에 넣었습니다. 관심있는 친구들은 그것을 읽을 수 있습니다.
영지식 증명에 관심이 있는 친구는 그룹 토론에 WeChat Xiaoan @SECBIT(id: secbit_xiaoanbi)를 추가하는 것을 환영합니다.
IOS
Android