Zero knowledge protocol demo with 3-colorable graph

2022 project @ NCTU Cryptography Engineering lecture
Implemented with d3.v7.js

Information

• graph_coloring.py graph coloring algorithm
• graph_puzzle.py puzzle info
• solution_gen.py generate correct data structure as input to d3.js
• zkp_d3.js dynamic network graph with d3
• zkp_puzzle.js puzzle info in d3 format
• zkp.html main page

Introduction

Zero knowledge protocol

Zero-knowledge proof

• Have the additional property of yielding nothing beyond the validity of the interactive proof protocol.
• Interactive/ Non-interactive

Zero knowledge protocol

• Interactive method for prover to prove to verifier that a statement is true, without revealing anything other than the veracity.

3-colorable graph

A graph G is 3-colorable if the vertices of a given graph can be colored with only three colors, such that no two vertices of the same color are connected by an edge.

Implementation

Backtracking algorithm

Concept

Assign colors one by one to different nodes, starting from the first node. For each assignment

1. check for safety by considering already assigned colors to the adjacent nodes.
2. If there is any safe assignment, mark the color assignment as part of the solution.
3. If no safe assignment exists then backtrack and return false.

Verifying Iteration

Two scenarios

• Prover is honest (graph_0), in each reveal event
  • Color the graph with one correct solution
  • Permute the color assignment
• Prover is lying (graph_1), in each reveal event
  • Color with randomly choose from several wrong solutions
  • Permute the color assignment

Demonstration

demo.mp4

Reference

1. Interactive zero knowledge 3-colorability demonstration
2. Zero knowledge proof
3. ZK Definition Proof
4. 3-colorable graph algorithms
5. D3.js