암호화폐가 아닌 그래프 이론으로 zero-knowledge proof를 이해하고 3-coloring 검증 프로토콜을 구현한 개발 실험기

이 아티클은 zero-knowledge proof(ZKP)를 암호화폐 맥락이 아니라 그래프 이론의 3-coloring 문제로 설명합니다. 증명자와 검증자가 해답 자체를 공개하지 않고도 해답의 존재를 확인하는 interactive proof 구조를 Goldreich, Micali, Wigderson 논문의 프로토콜과 간단한 구현을 통해 풀어냅니다.

ZKP를 블록체인 기술로만 보는 인식을 벗기고, NP-complete 문제와 검증 프로토콜의 관계를 직관적으로 보여준다는 점에서 교육적 가치가 큽니다. 특히 작은 코드와 고전 논문을 연결하는 접근은 privacy-preserving verification이 암호화폐 밖에서도 폭넓게 응용될 수 있음을 시사합니다.