Web3 Builder Frank's Archive

🇰🇷 Korean

💡

Youtube에서 찾은 영지식 증명을 위한 좋은 동영상을 소개하고, 해당 개념이 블록체인 내에서 어떻게 적용되는지 소개해봤어요.

영지식 증명이 뭘까?

해당 동영상을 본다면, 영지식 증명에 대해서 이해할 수 있습니다!

동영상을 보기 힘드신 분들을 위해, 텍스트로 요약하자면 다음과 같습니다.

“4가지 색을 갖고, 미국의 모든 주들이 국경이 맞닿을 때, 서로 다른 색상을 갖도록 모두 색칠 하기” 라는 문제가 있습니다. Alice가 돈을 건 문제이고, Bob이 이를 해결할 정답을 들고 왔습니다. 하지만, 여기서 두 사람은 이런 고민을 하고 있습니다.

Bob은 돈을 받고 정답을 넘겨주고 싶습니다.

Alice는 정답이 정확한지 알고 돈을 주고 싶습니다.

어떻게 하면, Bob과 Alice 모두 만족하는 방향으로 문제를 해결할 수 있을까요?

영지식 증명을 활용한다면, 이 문제를 해결 가능합니다.

이를 반영하기 위해서, Bob은 다음과 같은 방식으로 Alice에게 모두 다른 색으로 지도를 색칠했는지 증명합니다.

“Alice가 고른 맡 닿은 2가지 주의 색상을 보여주기”

Alice가 만일 2가지 색상을 골랐고, Bob의 정답이 정확하다면, 두 색깔은 다를겁니다.

해당 과정이 만일 100번 정도 진행되었다면, Alice는 Bob의 정답을 확신 후 돈을 주고, Bob은 돈을 받고 정답을 넘길 수 있을 것입니다.

어떻게 ZK Rollup Chain에 영지증명을 반영할까?

이제, 간단한 영지증명의 개념에서 확장하여 ZK Rollup Chain에 활용까지 확장해보겠습니다.

먼저 위에서 간단한 비유를 통해 기본적인 메커니즘을 확인해보았다면, 영지증명에는 이론적으로 어떠한 구성요소가 있는지 살펴 보겠습니다.

Statement : 모두에게 공개된 증명 정보, “모든 주가 겹치지 않도록 4가지 색으로 색칠하기”

Verifier : Alice, 정보를 검증할 사람

Prover : Bob, 자신이 가진 정보를 공개하지 않고, 정보를 증명하고 싶은 사람

Secret : 색칠이 칠해진 지도, 모두에게 숨기지만, Prover가 증명할 정보

Challenge : 2가지 주를 선택하는 과정, Verifier가 Prover에게 Secret을 검증하는 과정

Statement is true : Verifier가 Prover가 Secret을 갖고 있음을 확인한 상태

위 개념들이, 코드와 여러가지 인프라를 통해서 zkEVM에서 반영되게 됩니다.

하지만, 블록체인 네트워크에선 Bob과 Alice처럼 상호작용하며, 영지 증명을 이루지는 않습니다. 따라서, 어떻게 블록체인에서 영지증명 개념을 반영하였는지, Polygon의 zkEVM을 살펴보며 이해해보겠습니다.

일반적으로 블록체인 내 영지증명은 Non-Interactive Zero-Knowledge Proof System입니다.

따라서, zk-SNARKs 라는 암호화 체계를 따르게 됩니다. 해당 체계의 특성은 다음과 같습니다.

SNARK의 특징

Succinct : 증명의 크기가 작고, 신속하게 확인할 수 있다.

Non-interactive : 상호작용이 필요없다.

Argument of Knowledge : Secret을 실제로 알고 있다는 사실을 증명

Polygon zkEVM에서 zk-SNARKS를 사용하는 방식

ZK Rollup 방식은 Optimistic Rollup 방식과 다르게 모든 트랜잭션을 L1 레이어로 올리지 않으면서 이점을 챙기려 합니다. 대신 L1에는 블록에 대한 ZK Proof 를 넘겨주고, Verifier가 이를 검증하면서 트랜잭션의 무결한 상태 전이를 검증합니다. 여기서, Polygon zkEVM은 zkSNARKs 방식을 채택했습니다.

그렇다면, 실제 네트워크에서 영지 증명은 어떻게 구현되었을까요? 다음과 같은 구현체들이 존재합니다.

The trusted sequencer : L2 트랜잭션을 실행하는 노드, L2 트랜잭션의 Batch를 Aggregator에게 전달한다.

The trusted aggregator : Sequencer에게 받아 새로운 State Root에 따른 zk proof를 생성하고, 이를 Verifier(Consensus Contract)에 전달한다.

The consensus contract (PolygonZkEVM.sol, deployed on L1) : L1에서 zk proof를 검증한다.

한 문장으로 요약하면,

💡

Aggregator가 Sequencer가 보낸 L2의 트랜잭션 배치를 통하여 zkProof를 생성하고, L1에 전달하여 Verifier 컨트랙트가 검증한다.

zk Proof가 Verify되는 순간, 확정되는 사실들은 뭘까요?

맨 처음에 다루었던 영지 증명 케이스는, Alice가 두 가지 주를 선택하여, 색깔이 다름을 반복적으로 확인하는 과정이었습니다. 그 결과로 입증할 수 있는 사실은, Statement가 옳고, Secret 또한 유효하다는 사실이었죠.

그렇다면, Verifier Contract가 Aggregator가 보낸 ZK Proof를 검증하게 되면 어떤 Statement와 Secret이 유효한지 알 수 있을까요?

이를 위해선, 어떠한 값들이 결국엔 Snark값으로 변환되는지 확인하면서 알 수 있습니다.

대략적으로, Prover가 L2 Transaction Batch를 Snark Proof 값으로 변환되는 과정은 다음과 같습니다.

https://docs.polygon.technology/zkEVM/concepts/circom-intro-brief/

SNARK Proof가 최종적으로 생성되는 과정에서 다음과 같은 프로세스가 진행됩니다.

STARK Recursion : 배치 트랜잭션들의 올바른 실행을 보장하는 증명을 하나의 증명으로 결합

CIRCOM : 해당 증명을 수행할 수 있고, 사이즈는 줄인 Circuit 형태로 변환 후 Witness 생성

해당 과정에서는, 다양하고 복잡한, 산술적 메커니즘이 적용되면서 트랜잭션의 올바른 상태전이가 하나의 증명으로 나타나게 됩니다. 하지만, 해당 과정부터는 매우 복잡하고 깊은 지식이 필요하니, 이번 글에서는 다루지 않겠습니다.

결론

영지증명은, 중요한 Secret을 노출하지 않고, 상대방에게 Secret을 알고있음을 증명하는 암호학 체계입니다. 단순히 지도에 색을 칠하는 정답을 안전하게 거래할 수 있을 뿐만 아니라, L2의 모든 트랜잭션을 빠르게 증명할 수 있는 방안으로도 채택되고 있다는 사실이 놀랍습니다. 따라서, 조금만 더 찾아보면 ZK를 활용한 암호화 체계는 세상 전반에 퍼져있는 걸 확인할 수 있습니다.

또한, zk-SNARKs를 살펴보며 안정성을 높이기 위해서 다양한 수학적 배경이 깔려있다는 사실을 알게되었습니다. 이 글에서 다루지 않았지만, 충분히 공부할만한 가치가 있다고 생각해서 관련 리서치를 읽어보기 시작했습니다.

제가 쓰고 있는 글들이, 정말 RAW하게 모든 공식과 수식을 이해하고 쓰는 글이 아니지만, 복잡한 지식을 읽는 사람에게 가볍게 읽어보지 않도록 추후 해당 글도 정리해보겠습니다.

💡

I'd like to introduce a great video I found on YouTube about Zero-Knowledge Proofs and explain how this concept is applied in blockchain.

What is Zero-Knowledge Proof?

Watch this video to understand Zero-Knowledge Proofs!

For those who can't watch the video, here's a text summary:

"Color all US states with 4 colors so that no adjacent states share the same color" is the problem. Alice has put money on this problem, and Bob has come with a solution. However, both parties have concerns.

Bob wants to receive payment for providing the solution.

Alice wants to verify the solution before paying.

How can we solve this problem in a way that satisfies both Bob and Alice?

This can be solved using Zero-Knowledge Proof.

To implement this, Bob proves to Alice that he colored the map correctly using the following method:

"Showing the colors of any two adjacent states that Alice chooses"

If Alice selects two states and Bob's solution is correct, the colors will be different.

If this process is repeated about 100 times, Alice can be confident in Bob's solution and pay him, and Bob can receive payment and provide the solution.

How is Zero-Knowledge Proof Applied in ZK Rollup Chain?

Now, let's expand from the basic concept of Zero-Knowledge Proof to its application in ZK Rollup Chain.

After understanding the basic mechanism through the simple analogy above, let's examine the theoretical components of Zero-Knowledge Proof.

Statement: Publicly known proof information, "Color all states with 4 colors so no adjacent states share the same color"

Verifier: Alice, the person verifying the information

Prover: Bob, who wants to prove he has the information without revealing it

Secret: The colored map, hidden from everyone but proven by the Prover

Challenge: The process of selecting two states, where the Verifier validates the Prover's Secret

Statement is true: When the Verifier confirms the Prover possesses the Secret

These concepts are implemented in zkEVM through code and various infrastructure.

However, blockchain networks don't create Zero-Knowledge Proofs through interaction like Bob and Alice. Let's understand how blockchain implements Zero-Knowledge Proof concepts by examining Polygon's zkEVM.

Generally, Zero-Knowledge Proof in blockchain is a Non-Interactive Zero-Knowledge Proof System.

Therefore, it follows the encryption system called zk-SNARKs. This system has the following characteristics:

SNARK Characteristics

Succinct: The proof size is small and can be verified quickly

Non-interactive: No interaction needed

Argument of Knowledge: Proves that the Secret is actually known

How Polygon zkEVM Uses zk-SNARKS

Unlike Optimistic Rollup, ZK Rollup doesn't send all transactions to the L1 layer while maintaining benefits. Instead, it sends ZK Proof of the block to L1, and the Verifier validates the proof to verify the transaction's valid state transition. Here, Polygon zkEVM adopted the zkSNARKs approach.

So, how is Zero-Knowledge Proof implemented in the actual network? The following components exist:

The trusted sequencer: A node that executes L2 transactions and sends L2 transaction batches to the Aggregator

The trusted aggregator: Receives from Sequencer, generates zk proof based on new State Root, and sends it to the Verifier(Consensus Contract)

The consensus contract (PolygonZkEVM.sol, deployed on L1): Verifies zk proof on L1

In one sentence:

The Aggregator generates zkProof through L2 transaction batches from the Sequencer and sends it to L1 for verification by the Verifier contract.

What Facts are Confirmed When zk Proof is Verified?

In our initial Zero-Knowledge Proof case, Alice repeatedly verified that two selected states had different colors. This proved that the Statement was correct and the Secret was valid.

Then, when the Verifier Contract verifies the ZK Proof sent by the Aggregator, what Statement and Secret are validated?

To understand this, we need to see what values are ultimately converted into Snark values.

Roughly, here's how the Prover converts L2 Transaction Batch into Snark Proof values:

The following processes occur during the final generation of SNARK Proof:

STARK Recursion: Combines proofs ensuring correct execution of batch transactions into a single proof

CIRCOM: Converts the proof into a smaller Circuit format and generates Witness

During this process, various complex arithmetic mechanisms are applied to represent the transaction's valid state transition as a single proof. However, as this process requires very complex and deep knowledge, we won't cover it in this article.

Conclusion

Zero-Knowledge Proof is a cryptographic system that proves possession of a Secret without revealing it. It's amazing that it can not only safely trade solutions like map coloring but is also adopted as a way to quickly prove all L2 transactions. If you look a bit further, you'll find that ZK-based encryption systems are widespread throughout the world.

Also, examining zk-SNARKs revealed the diverse mathematical background needed for increased security. Although not covered in this article, I've started reading related research as I believe it's worth studying.

While my articles don't RAW-ly explain all formulas and equations, I plan to organize this topic in future posts to ensure readers don't take complex knowledge lightly.

Understanding ZK Proof (with Polygon zkEVM)