30줄 코드로 구현하는 영지식 증명: 그래프 3색칠하기

A quick look at zero-knowledge proofs

영지식 증명(ZKP)은 암호화폐와 무관하게 그래프 이론만으로 구현할 수 있다. 이 글은 Goldreich, Micali, Widgerson의 논문에 기반한 3색칠 문제용 인터랙티브 프로토콜을 Python 코드로 설명한다. 프로버는 그래프의 유효한 3색칠을 공개하지 않고도 검증자에게 증명할 수 있다. 각 라운드에서 색상을 무작위로 섞고 해시로 잠근 뒤, 검증자가 선택한 간선의 색상만 공개한다. 이 과정을 반복하면 검증 실패 확률을 낮출 수 있다. 실제 네트워크 데모(서버-클라이언트)도 제공된다.