Introduction

This document provides a simplified visual explanation of the ZigZag Commitment algorithm described in Tight PoS - ZigZag.

It is intended to confer intuition about the algorithm, and to serve as a reference for implementers. The author of this document and those of the linked paper believe the two are consistent; and converging on this consistent design was a third design goal of this document’s construction.

Graph

Both renumbered (DRG) and reversed (expander) parents are generated by a pseudorandom permutation and are provided only to illustrate the nature of the zigzag commitment scheme. They accurately represent how parent-child relationships change between layers, and are accurate for expander parents. However, this is not representative of the DRG parent selection algorithm.

The following graphs illustrate how the position of challenges, DRG parents, and expander parents change between layers. Only a single DRG parent and a single expander parent are shown. The immediate predecessor parent is shown for graph topology, but it is not tracked in the tables below.

• The challenged node alternates on even and odd layers.
• The DRG parents alternate in the same way.
• The expander parents do not alternate in this way. The edges between nodes and their expander parents are reversed between layers.

In order to have a compact and concrete example, we use a graph containing only 8 nodes replicated in 6 layers.

Legend

Data Layer: \(Comm_D\) Tree

Replica Column Layers: \(Comm_C\) Tree

Final Layer: \(Comm_{R_{LAST}}\) Tree

Commitment Algorithm

Goal

We will generate two commitments \(Comm_R, Comm_D\) to be placed on chain.

\(Comm_D\) is the merkle root of the original data.

\(Comm_R = H(Comm_C || Comm_{R_{LAST}})\).

Their construction is described below.

Definitions and Notation

We will perform \(L\) layers of ZigZag replication over \(N\) labeled nodes. The algorithm described here assumes, for simplicity of explanation, that \(L\) is even. This is a safe assumption given the actual parameters used by Filecoin.

In the running example, \(L\) is 6 and \(N\) is 8.

Merkle roots (commitments) are generated with the vector-commitment function \(VC(…)\).

Hashes are produced with a hash function \(H(…)\), which is not necessarily that used by \(VC(…)\).

\(Comm = VC(l_1||…||l_N)\), where the \(l_i\) are the data (labels or hashes) to be committed.

Generated trees are retained until the proving phase, when merkle proofs of a given label’s inclusion in \(Comm\) will be created. We will designate such proofs \(l_i \rightarrow Comm\).

We use the notation \(e{_i}^{(l)}\), correlated in the table below with the \((l, i)\) notation used in the graphs above, where \(l\) indexes layers, and \(i\) indexes labels or columns. Column indexes always have the property that the label of the column’s first/odd layer has the same index as the column itself.

To avoid inlining the ‘renumbering’ calculation whenever indexing even layers, we use the notation \(\bar{i}\) to represent the renumbered index, \(\bar{i} = N - i + 1\).

Taken together, the previous two paragraphs imply that the first layer’s label in \(C_i\) is \(e_i^{(1)}\) and the second layer’s label is \(e_{\bar{i}}^{(2)}\).

NOTE: Whenever we refer to even/odd parents or nodes (e.g. ‘odd expander parents’), we mean those on even or odd layers.

…

Initial Data Layer

• Vector Commitment

  Generate Merkle root for data leaves.

  \(Comm_D = VC(D_1 || D_2 || … || D_N)\), where \(D_i = e_i^{(0)}\).

  This example: \(Comm_D = VC(e_1^{(0)}, e_2^{(0)}, e_3^{(0)}, e_4^{(0)}, e_5^{(0)}, e_6^{(0)}, e_7^{(0)}, e_8^{(0)})\).

• Opening

  To open \(D_i\), provide a merkle proof \(D_i \rightarrow Comm_D\).

ZigZag Replica Columns

• Unpartitioned Columns

  Even Expander Parents	~~~~	DRG Parents	Odd Expander Parents	~~~~	~~~~	Challenges	~~~~
  \((1, 1)^{*}\)	\((1, 2)\)	\((1, 3)\)	\((1, 4)^{*}\)	\((1, 5)\)	\((1, 6)\)	\((1, 7)\)	\((1, 8)\)
  \((2, 8)\)	\((2, 7)\)	\((2, 6)\)	\((2, 5)^{*}\)	\((2, 4)\)	\((2, 3)\)	\((2, 2)\)	\((2, 1)\)
  \((3, 1)^{*}\)	\((3, 2)\)	\((3, 3)\)	\((3, 4)\)	\((3, 5)\)	\((3, 6)\)	\((3, 7)\)	\((3, 8)\)
  \((4, 8)\)	\((4, 7)\)	\((4, 6)\)	\((4, 5)^{*}\)	\((4, 4)\)	\((4, 3)\)	\((4, 2)\)	\((4, 1)\)
  \((5, 1)^{*}\)	\((5, 2)\)	\((5, 3)\)	\((5, 4)\)	\((5, 5)\)	\((5, 6)\)	\((5, 7)\)	\((5, 8)\)

  \(^{*}\) Indicates labels which must be hashed for column commitments but need not be opened for label checks.

  Define \(C_{p_{even}}\) to be the column containing the even expander parents.

  Define \(C_{p_{odd}}\) to be the column containing the odd expander parents.

• Odd Partition

  Even Expander Parents	~~~~	DRG Parents	Odd Expander Parents	~~~~	~~~~	Challenges	~~~~
  \((1, 1)^{*}\)	\((1, 2)\)	\((1, 3)\)	\((1, 4)^{*}\)	\((1, 5)\)	\((1, 6)\)	\((1, 7)\)	\((1, 8)\)
  \((3, 1)^{*}\)	\((3, 2)\)	\((3, 3)\)	\((3, 4)\)	\((3, 5)\)	\((3, 6)\)	\((3, 7)\)	\((3, 8)\)
  \((5, 1)^{*}\)	\((5, 2)\)	\((5, 3)\)	\((5, 4)\)	\((5, 5)\)	\((5, 6)\)	\((5, 7)\)	\((5, 8)\)

  Concatenate and hash rows of column \(i\) to construct \(O_i\).

  Odd column hash \(O_i = H(e_i^{(1)} || e_i^{(3)} || … || e_i^{(L-1)})\).

  Define \(O_{p_{odd}}\) to be the odd column hash containing the odd expander parents.

  Define \(O_{p_{even}}\) to be the odd column hash containing the even expander parents.

• Even Partition

  Even Expander Parents	~~~~	DRG Parents	Odd Expander Parents	~~~~	~~~~	Challenges	~~~~
  \((2, 8)\)	\((2, 7)\)	\((2, 6)\)	\((2, 5)^{*}\)	\((2, 4)\)	\((2, 3)\)	\((2, 2)\)	\((2, 1)\)
  \((4, 8)\)	\((4, 7)\)	\((4, 6)\)	\((4, 5)^{*}\)	\((4, 4)\)	\((4, 3)\)	\((4, 2)\)	\((4, 1)\)

  Concatenate and hash rows of column \(i\) to construct \(E_i\).

  Remember that column with index \(i\) contains even-layered labels of index \(\bar{i} = N - i + 1\).

  Even column hash \(E_i = H(e_{\bar{i}}^{(2)} || e_{\bar{i}}^{(4)} || … || e_{\bar{i}}^{(L-2)})\).

  Define \(E_{p_{odd}}\) to be the even column hash containing the odd expander parents.

  Define \(E_{p_{even}}\) to be the even column hash containing the even expander parents.

• Vector Commitment

  Produce the column leaves: \(C_i = H(O_i || E_i)\).

  Generate Merkle tree for column leaves:

  \(Comm_C = VC(C_1 || C_2 || … || C_N)\).

• Opening

  • To open only odd-layer labels

    Reveal all odd-layer labels and prove they hash to \(O_i\): \(L / 2 - 1\) hash proofs. Reveal the \(E_i\) (\(0\) hash proofs).

    Note: odd-layer labels of \(C_i\) have index \(i\).

  • To open only even layer labels

    Reveal all even layer labels and prove they hash to \(E_i\): \(L / 2 - 2\) hash proofs. Reveal the \(O_i\) (\(0\) hash proofs).

    Note: even-layer labels of \(C_i\) have index \(N-i+1\).

  • To open all labels

    Reveal all labels and prove they hash to \(E_i\) and \(O_i\) as above. (\(L\) hash proofs).

  • Then, in every case

    • Prove \(H(O_i || E_i) \rightarrow Comm_C\).
    • Reveal \(Comm_{R_{LAST}}\) and prove that \(H(Comm_C || Comm_{R_{LAST}}) = Comm_R\).

Final Replica Layer

• Vector Commitment

  Generate Merkle tree for replica leaves.

  \(R_{LAST_i} = e_i^{(L)}\).

  \(Comm_{R_{LAST}} = VC(R_{LAST_1} || R_{LAST_2} || … || R_{LAST_N})\).

• Opening

  To open \(R_{LAST_i}\),

  • Provide a merkle proof \(R_{LAST_i} \rightarrow Comm_{R_{LAST}}\).
  • Reveal \(Comm_C\) and prove that \(H(Comm_C || Comm_{R_{LAST}}) = Comm_R\).

Replica Commitment

Produce \(Comm_R\) from its constituents.

\(Comm_R = H(Comm_C || Comm_{R_{LAST}})\).

Challenge Selection

In order to minimize openings, we alternate challenged labels per layer.

By convention, if the challenge is \(\chi\), we challenge \(e_{\chi}^{(l_{odd})}\) and \(e_{\bar{\chi}}^{(l_{even})}\), where \(l_{odd}\) are the odd layers and \(l_{even}\) are the even layers.

Opening Commitments for Offline Proof

For use in all challenge proofs, reveal \(Comm_C\) and \(Comm_{R_{LAST}}\) and prove that \(H(Comm_C || Comm_{R_{LAST}}) = Comm_R\).

To prove encoding for a challenged label \(\chi\) on odd layers \(l_{odd}\) and \(\bar{\chi}\) on even layers \(l_{even}\).

• Remember that \(\bar{\chi} = (N-\chi)+1\).
• Initial data layer openings
  • Open label for challenged data node \(e_\chi^{(0)} — using Comm_D\).
• ZigZag replica column openings
  • Open all labels in \(C_\chi\) containing challenged label’s ‘replica node’, (\(C_\chi\)) — using \(Comm_C\).
  • Open all labels in the ‘renumbered’ column (\(C_{\bar{\chi}}\)) — using \(Comm_C\). These are the challenged label’s ‘data nodes’ (from the preceding layer).
  • Open all labels in the columns containing challenged label’s DRG parents — using \(Comm_C\).
  • Open only even-layer labels in the columns containing challenged label’s even expander parents — using \(Comm_C\) and \(O_{p_{even}}\).
  • Open only odd-layer labels in the columns containing challenged label’s odd-layer expander parents — using \(Comm_C\) and \(E_{p_{odd}}\).
• Final replica layer openings
  • Open all challenged labels (\(e_{\bar{\chi}}^{(L)}\)) and even challenged parents (any kind) — using \(Comm_{R_{LAST}}\).
• Prove encoding as usual for all odd-layer \(e{_\chi}^{(l_{odd})}\) and even-layer \(e{_{\bar{\chi}}}^{(l_{even})}\).

Opening Commitments for Online Proof

To prove encoding for a challenged label \(C\) in the replica:

• Reveal \(Comm_C\) (which must have been stored along with the replica).
• Open \(Comm_{R_{LAST}}\) from provided \(Comm_R\) by proving that \(H(Comm_C || Comm_{R_{LAST}}) = Comm_R\).
• Provide a merkle proof \(e_C^{(L)} \rightarrow Comm_{R_{LAST}}\).