Общий вход: граф $ G=(V,E)$.

1) Первый шаг доказывающего. Пусть $ \psi$ - $ 3$-раскраска графа $ G$. Доказывающий выбирает случайную перестановку $ \pi$ множества $ \{1,2,3\}$ и устанавливает $ \varphi(v)=\pi(\psi(v))$ для каждого $ v\in V$. Следовательно, доказывающий образовывает случайную перемаркировку $ 3$-раскраски $ \psi$. Доказывающий отправляет проверяющему последовательность из $ \vert V\vert$ закрытых и непрозрачных ящиков таких, что $ v$-ый ящик содержит значение $ \varphi(v)$.

2) Первый шаг проверяющего. Проверяющий равномерно выбирает ребро $ (u,v)\in E$ и отправляет его доказывающему.

Примечание. Проверяющий просит проверить цвета вершин $ u$ и $ v$.

3) Второй шаг доказывающего. Доказывающий отправляет проверяющему ключи от ящиков $ u$ и $ v$.

4) Второй шаг проверяющего. Проверяющий открывает ящики $ u$ и $ v$ и принимает доказательство если и только если они содержат два различных элемента из $ \{1,2,3\}$.

Общий вход: $ 3$-раскрашенный граф $ G=(V,E)$. Пусть $ n=\vert V \vert$ и $ V=\{1,2,...,n\}$.

Дополнительный вход доказывающего: $ 3$-раскраска графа $ G$, обозначаемая $ \psi$.

1) Первый шаг доказывающего. Пусть $ \psi$ - $ 3$-раскраска графа $ G$. Доказывающий выбирает случайную перестановку $ \pi$ множества $ \{1,2,3\}$ и устанавливает $ \varphi(v)=\pi(\psi(v))$ для каждого $ v\in V$. Доказывающий использует протокол привязки к биту для привязки собственно к цветам каждого из вершин. Т.е. доказывающий равномерно и независимо выбирает $ s_1,s_2,...,s_n \in \{0,1\}^n$, вычисляет $ c_i = C_{s_i}(\varphi(i))$ для каждого $ i \in V$ и отправляет $ c_1,c_2,...,c_n$ проверяющему.

2) Первый шаг проверяющего. Проверяющий равномерно выбирает ребро $ (u,v)\in E$ и отправляет его доказывающему.

3) Второй шаг доказывающего. Без потери общности мы можем предположить, что сообщение, полученное от проверяющего, это ребро, обозначеное $ (u,v)$. (В противном случае, доказываюший задает $ (u,v)$ для некоторого заранее определенного ребра графа $ G$). Доказывающий использует (канонический) этап раскрытия протокола привязки к биту для того, чтобы раскрыть цвета вершин $ u$ и $ v$ проверяющему.

4) Второй шаг проверяющего. Проверяющий проверяет правильно ли или неправильно были раскрыты значения, соответствующие $ u$ и $ v$, и являются ли они различными или нет. Т.е. после получения $ (s,\sigma)$ и $ (s',\tau)$ проверяющий проверяет выполняются ли или нет следующие условия: $ c_u=C_s(\sigma)$, $ c_v=C_{s'}(\tau)$ и $ \sigma\neq\tau$ (и $ \sigma$ и $ \tau$ принадлежат $ \{1,2,3\}$). Если все условия выполняются, то проверяющий принимает доказательство. В противном случае, отвергает.