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

### Data Layer: $Comm_D$ Tree

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

### Replica Column Layers: $Comm_C$ Tree

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

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

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

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

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

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

## 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 Parents Expander 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}}$.