Stacked DRG Commitments

This section summarizes the Stacked DRG (SDR) Column Commitments algorithm described in Tight PoS - ZigZag.

Graph

(emit-legend nil)

In the following graphs, DRG and expander parents are both generated by a pseudorandom permutation and are provided only to illustrate the nature of the SDR commitment scheme. They accurately represent how parent-child relationships function between layers, and are accurate for expander parents. However, this is not representative of the DRG parent selection algorithm.

The following graphs illustrate the positions of challenges, DRG parents, and expander parents 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.

In order to have a compact and concrete example, we use a graph containing only

*layers*} {{{results(=4=)}}
layers.

Legend

legend.png

Data Layer: $Comm_D$ Tree

(emit-comm-d-layer-graph *comm-d-graph*)

data-layer.png

Replica Column Layers: $Comm_C$ Tree

(emit-layer-graph (nth 0 (sdr-graph-layer-graphs *sdr-graph*)))

layer-1.png

(emit-layer-graph (nth 1 (sdr-graph-layer-graphs *sdr-graph*)))

layer-2.png

(emit-layer-graph (nth 2 (sdr-graph-layer-graphs *sdr-graph*)))

layer-3.png

(emit-layer-graph (nth 3 (sdr-graph-layer-graphs *sdr-graph*)))

layer-4.png

Final Layer: $Comm_{R_{LAST}}$ Tree

(emit-replica-layer-graph *replica-graph*)

replica-layer.png

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 SDR key generation over $N$ labeled nodes.

In the running example, $L$ is

*nodes*} {{{results(=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.

Graph$(1, 1)$$(1, 2)$$(1, 3)$$(1, 4)$$(1, 5)$$(1, 6)$$(1, 7)$$(1, 8)$
Notation$e_1^{(1)}$$e_2^{(1)}$$e_3^{(1)}$$e_4^{(1)}$$e_5^{(1)}$$e_6^{(1)}$$e_7^{(1)}$$e_8^{(1)}$
Graph$(2, 1)$$(2, 2)$$(2, 3)$$(2, 4)$$(2, 5)$$(2, 6)$$(2, 7)$$(2, 8)$
Notation$e_1^{(2)}$$e_2^{(2)}$$e_3^{(2)}$$e_4^{(2)}$$e_5^{(2)}$$e_6^{(2)}$$e_7^{(2)}$$e_8^{(2)}$

Graph$(4, 1)$$(4, 2)$$(4, 3)$$(4, 4)$$(4, 5)$$(4, 6)$$(4, 7)$$(4, 8)$
Notation$e_1^{(4)}$$e_2^{(4)}$$e_3^{(4)}$$e_4^{(4)}$$e_5^{(4)}$$e_6^{(4)}$$e_7^{(4)}$$e_8^{(4)}$

Initial Data Layer

~~~~~~~~~~~~Challenge~~~~~~~~~~~~~~~~
$(0, 1)$$(0, 2)$$(0, 3)$$(0, 4)$$(0, 5)$$(0, 6)$$(0, 7)$$(0, 8)$

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$.

SDR Replica Columns

Columns

DRG ParentsExpander Parents~~~~Challenges~~~~~~~~~~~~~~~~
$(1, 1)$$(1, 2)^{*}$$(1, 3)$$(1, 4)$$(1, 5)$$(1, 6)$$(1, 7)$$(1, 8)$
$(2, 1)$$(2, 2)$$(2, 3)$$(2, 4)$$(2, 5)$$(2, 6)$$(2, 7)$$(2, 8)$
$(3, 1)$$(3, 2)$$(3, 3)$$(3, 4)$$(3, 5)$$(3, 6)$$(3, 7)$$(3, 8)$
$(4, 1)$$(4, 2)$$(4, 3)$$(4, 4)$$(4, 5)$$(4, 6)$$(4, 7)$$(4, 8)$

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

Concatenate and hash rows of column $i$ to construct $O_i$.

Column hash $C_i = H(e_i^{(1)} || e_i^{(2)} || … || e_i^{(L)})$.

Vector Commitment

Generate Merkle tree for column leaves, $C_i$:

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

Opening

To open labels for column $i$:
  • Reveal all labels and prove they hash to $C_i$ as above. ($L$ hash proofs).

  • Provide a merkle proof $C_i \rightarrow Comm_C$.

Then once, reusable for all columns,
  • Reveal $Comm_{R_{LAST}}$ and prove that $H(Comm_C || Comm_{R_{LAST}}) = Comm_R$.

Final Replica Layer

~~~~~~~~~~~~Challenge~~~~~~~~~~~~~~~~
$(5, 1)$$(5, 2)$$(5, 3)$$(5, 4)$$(5, 5)$$(5, 6)$$(5, 7)$$(5, 8)$

Vector Commitment

Generate Merkle tree for replica leaves.

$R_{LAST_i} = e_i^{(L+1)}$.

$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}}$.

Then once (shared with Replica Columns — see above):
  • Reveal $Comm_C$ and prove that $H(Comm_C || Comm_{R_{LAST}}) = Comm_pR$.

Replica Commitment

Commitment

  • Produce $Comm_R$ from its constituents.

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

Opening (performed once per PoRep)

  • Reveal $Comm_C$ and $Comm_{R_{LAST}}$ and prove that $H(Comm_C || Comm_{R_{LAST}}) = Comm_R$.

Challenge Selection

For each challenge $\chi$, we challenge each node $e_{\chi}^{(l)}$ for $l = 1, 2, .. L$.

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$:

  • Initial data layer openings

    • Open label for challenged data node $e_\chi^{(0)} — using Comm_D$.

  • SDR 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 columns containing challenged label's DRG parents — using $Comm_C$.

    • Open all labels in the columns containing challenged label's expander parents — using $Comm_C$.

  • Final replica layer openings

    • Open all challenged labels ($e_{\chi}^{(L+1)}$) using $Comm_{R_{LAST}}$.

  • Prove labeling for all challenged labels $e{_\chi}^{(l))} for $l = 1, 2, .. L$.

  • Prove encoding for all challenged nodes $e{_\chi}^{(L+1))}$.

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}}$.