The Three Properties of Zero-Knowledge Proofs (Completeness, Soundness, Zero-Knowledge) TODO
Concept
An interactive proof system is a procedure by which a prover convinces a verifier that some statement is true, and a zero-knowledge proof requires three properties on top of that. Completeness means that if the statement is true and both parties honestly follow the protocol, the verifier accepts with overwhelming probability. Soundness means that if the statement is false, no prover can convince the verifier except with negligible probability; when this guarantee holds against every prover it's called a proof, and when it holds only against provers with bounded computational power it's called an argument. The zero-knowledge property means the verifier learns nothing beyond the fact that the statement is true, formalized as the existence of a simulator — one that doesn't know the witness — able to produce something indistinguishable from a real transcript. Depending on the strength of that indistinguishability, zero-knowledge is classified as perfect, statistical, or computational, and applications often require knowledge soundness — a guarantee that the prover actually knows the witness — rather than plain soundness.
In practice, what breaks is usually not the three properties themselves but the assumptions they rest on — the integrity of a trusted setup, or the assumptions made when converting an interactive protocol into a non-interactive one.
Code & Formula
# 영지식 증명의 3성질(완전성·건전성·영지식) — 그래프 3색칠 문제의 대화형 ZK 프로토콜을
# 여러 라운드 시뮬레이션해, "거짓 증명이 계속 통과할 확률이 지수적으로 줄어드는 것"을 본다.
import random
# 삼각형 하나(간선 3개) — 진짜 3색칠 가능한 그래프
edges = [(0, 1), (1, 2), (2, 0)]
coloring = {0: "R", 1: "G", 2: "B"} # 증명자만 아는 비밀
def prover_commit(coloring, perm):
# 색을 무작위로 재배치(퍼뮤테이션)해서 커밋 — 매 라운드 다른 색 배정처럼 보이게.
return {v: perm[c] for v, c in coloring.items()}
def round_trip(coloring, edges, cheat=False):
perm = {"R": "G", "G": "B", "B": "R"} # 색 재배치(진짜 증명자는 이런 순열을 매번 새로 고름)
committed = prover_commit(coloring, perm) if not cheat else {0: "R", 1: "R", 2: "B"} # 부정직: 두 정점 같은 색
u, v = random.choice(edges) # 검증자가 무작위로 간선 하나 선택
return committed[u] != committed[v] # 그 간선의 두 끝점 색이 다른지만 공개
N = 20
honest_ok = sum(round_trip(coloring, edges) for _ in range(N))
cheat_ok = sum(round_trip(coloring, edges, cheat=True) for _ in range(N))
print(f"정직한 증명자: {honest_ok}/{N} 라운드 통과 (완전성 — 항상 통과해야 함)")
print(f"부정직한 증명자: {cheat_ok}/{N} 라운드 통과 (매 라운드 들킬 확률 >= 1/|E| — 반복할수록 사기 확률이 지수적으로 감소)")
print("영지식성: 검증자는 매 라운드 '두 끝점 색이 다르다'만 보고, 실제 색은 절대 못 봄")
Exercise
Pick a classic sigma protocol, such as graph three-coloring or proof of knowledge of a discrete log, write out completeness, soundness, and the simulator construction by hand, and reproduce the interactive process in simple code.
Practical Connection
When reviewing a rollup's validity proof or a privacy feature, the starting point for accurately assessing its trust assumptions is distinguishing whether the system is a proof or an argument, whether it has knowledge soundness, and what setup assumptions it relies on.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.