# Chung's construction in ZigZag

## Chung Bipartite Expander

Let us work on the example from the paper but by adding the distinction between the different permutations via different colors.
Here we have $n = 5, k = 3$. I chose the permutations (i.e. assigned colors) completely arbitrarily.

digraph G {

  rankdir="LR";
  splines=false;
  //graph [nodesep=0.5, ranksep=1];

  

  subgraph cluster_level1 {
      C1 -> C2 -> C3 -> C4 -> C5 
      C1 -> C6 [ color="green", constraint=false]
      C1 -> C8 [ color="blue", constraint=false]
      C1 -> C9 [ color="red", constraint=false] 
      C2 -> C6 [ color="blue", constraint=false]
      C2 -> C7 [ color="green", constraint=false]
      C2 -> C8 [ color="red", constraint=false]
      C3 -> C7 [ color="blue", constraint=false]
      C3 -> C8 [ color="green", constraint=false]
      C3 -> C10 [ color="red", constraint=false]
      C4 -> C7 [color="red", constraint=false]
      C4 -> C9 [ color="green", constraint=false]
      C4 -> C10 [ color="blue", constraint=false]
      C5 -> C10 [ color="green", constraint=false]
  }
  

  subgraph cluster_level2 {
      C10 -> C9 -> C8 -> C7 -> C6 
      C6 -> C11 [color="green", constraint=false]
      C6 -> C13 [color="blue", constraint=false]
      C6 -> C14 [color="red", constraint=false]
      C7 -> C11 [color="blue", constraint=false]
      C7 -> C12 [color="green", constraint=false]
      C7 -> C13 [color="red", constraint=false]
      C8 -> C12 [color="blue", constraint=false]
      C8 -> C13 [color="green", constraint=false]
      C8 -> C15 [color="red", constraint=false]
      C9 -> C12 [color="red", constraint=false]
      C9 -> C14 [color="green", constraint=false]
      C9 -> C15 [color="blue", constraint=false]
      C10 -> C15 [color="green", constraint=false]
    }
  
  subgraph cluster_level3 {
      C11 -> C12 -> C13 -> C14 -> C15 
  }
  

  { rank = same;  C1; C6; C11 }
  { rank = same;  C2; C7; C12}
  { rank = same;  C3; C8; C13}
  { rank = same;  C4; C9; C14}
  { rank = same;  C5; C10; C15}
  
}

Note that we "accept" node **C5** only has one child, for sake of clarity & consistency with the paper.

The goal is to explore the different projections possible by looking at the **last layer** (C11 -> C15).
We use the following notation: $C^l_i$ is the node at index $i$ (1-based indexed) at level $l$ (0-based indexed).

## Naive projection

Let us see what happens when we simply project the edges on the lower layer, rejecting the ones that are invalid. An edge $(c^1_i,c^2_j)$ is invalid when projected at the lower layer if $i $. Note that the edges of the form $(i, i+1)$ is not relevant to the discussion (because always present).

digraph G {

  rankdir="LR";
  C11 -> C12 -> C13 -> C14 -> C15 [weight=10]
  C11 -> C13 [color="blue"]
  C11 -> C14 [color="red"] 
  C13 -> C15 [color="red"]
}

We dropped the edges
+ C7 -> C11
+ C9 -> C12
+ C8 -> C12

## Projection by reversing edge

This projections add the particularity that if an edge $(i,j)$ is invalid, then it takes the inverse edge $(j,i)$. By definition, if $(i,j)$ is invalid, then $i < j$ so the edge $(j,i)$ is valid since $i > j$.
The algorithm can be summarized as:

for each edge (i,j) with i!=j, add (min(i,j), max(i,j))

digraph G {

  rankdir="LR";
  C11 -> C12 -> C13 -> C14 -> C15 [weight=10]
  C11 -> C13 [color="blue"]
  C11 -> C14 [color="red"] 
  C13 -> C15 [color="red"]
  C12 -> C14 [color="red"]
}

We added the edges:
+ C12 -> C14

Note that this is what is shown on Figure 1.1 of the [paper](https://eprint.iacr.org/2018/702.pdf).
This method will always produce $kn$ edges in the graph. Of course, the distribution of these edges is changed.

## Projection with inverse permutation

This projection takes from option 1 but additionally use the inverse permutation. The code shown below is simplified from the [paper](https://web.stanford.edu/~bfisch/porep_short.pdf):

e = (i,j) 
if j < i, add (j,i)

e' = (j',i) # from same partition
if j' < i, add (j',i)

digraph G {
  rankdir="LR";
  C11 -> C12 -> C13 -> C14 -> C15 [weight=10]
  C11 -> C13 [color="blue"]
  C11 -> C14 [color="red"] 
  C13 -> C15 [color="red"]
  C12 -> C14 [color="red"]
}

This methods gives the same graph as the reversing edge.

**Questions**:
+ Why do we need this inverse permutation ? Why does the reversing edge is not enough ?

# ZigZag Graph Computation

In ZigZag, we have to alternate each other layer's direction. That gives rise to different ways to creating both the DRG and expander edges for the layers with inversed directions. We first explore the two ways and then potential ways to create the graph.

## Techniques for creating edge in reversed layer

Let's see two technique we can use to create the edges in a reversed layer, i.e. a graph where edges go from higher indices to lower indices.
This will be the graph we will be working on, taken from the tight pos [paper p.6 fig1.1](https://eprint.iacr.org/2018/702.pdf). Blue edges are expander edges, and red edges are DRG edges.
**Note**: I removed duplicate edges between expander and drg edges for sake of clarity (they are present in fig 1.1).

digraph G {

  rankdir="LR";
  //graph [nodesep=0.5, ranksep=1];

  subgraph cluster_level3 {
      C11 -> C12 -> C13 -> C14 -> C15 
      
  }
  
  subgraph cluster_level2 {
      C10 -> C9 -> C8 -> C7 -> C6  
      C10 -> C8  [color="red",weight=-1]
      C9 -> C6 [color="red",weight=-1]
      C8 -> C6 [color="blue",weight=-1]
      //C9 -> C6 [color="blue",weight=-1]
      C9 -> C7 [color="blue",weight=-1]
      // C10 -> C8 [color="blue",weight=-1]
    }

  { rank = same;   C6; C11 }
  { rank = same;   C7; C12}
  { rank = same;   C8; C13}
  { rank = same;   C9; C14}
  { rank = same;   C10; C15}
  
}

The goal of this section is to show two technique to map the edge of the first layer to the lower layer.

### Reversing the edge

The simplest technique consist to reverse an edge when going to a lower layer. Indeed if $(i,j)$ is a valid edge at layer $l$, then $(j,i)$ is a valid edge a layer $l+1$. This gives the following graph when applying the transformation to both DRG and expander edges.
**NOTE**: This is the current way EXPANDER edges are created at this time of writing. In the graph below, both DRG and expander edges are created using reversing.

digraph G {

  rankdir="LR";

  subgraph cluster_level3 {
      C11 -> C12 -> C13 -> C14 -> C15 
      C11 -> C14 [color="red", weight=-1]
      C13 -> C15 [color="red", weight=-1]
      C11 -> C13 [color="blue", weight=-1]
      C12 -> C14 [color="blue", weight=-1]
  }
  
  subgraph cluster_level2 {
      C10 -> C9 -> C8 -> C7 -> C6  
      C10 -> C8  [color="red",weight=-1]
      C9 -> C6 [color="red",weight=-1]
      C8 -> C6 [color="blue",weight=-1]
      C9 -> C7 [color="blue",weight=-1]
    }

  { rank = same;   C6; C11 }
  { rank = same;   C7; C12}
  { rank = same;   C8; C13}
  { rank = same;   C9; C14}
  { rank = same;   C10; C15}
  
}

### Renumbering

Renumbering apply a "mirror" effect to the graph. A valid edge $(i,j)$ at layer $l$ is mapped to a valid edge $(n - i + 1, n - j + 1)$ at layer $l+1$. This gives the following graph when applying the transformation to both DRG and expander edges.
**Note**: this is the current way DRG parents are constructed at this time of writing. In the graph below, both DRG and expander edges are created using renumbering.

digraph G {

  rankdir="LR";

  subgraph cluster_level3 {
      C11 -> C12 -> C13 -> C14 -> C15 
      C12 -> C15 [color="red", weight=-1]
      C11 -> C13 [color="red", weight=-1]
      C12 -> C14 [color="blue", weight=-1]
      C13 -> C15 [color="blue", weight=-1]
  }
  
  subgraph cluster_level2 {
      C10 -> C9 -> C8 -> C7 -> C6  
      C10 -> C8  [color="red",weight=-1]
      C9 -> C6 [color="red",weight=-1]
      C8 -> C6 [color="blue",weight=-1]
      C9 -> C7 [color="blue",weight=-1]
    }

  { rank = same; C6; C11 }
  { rank = same; C7; C12}
  { rank = same; C8; C13}
  { rank = same; C9; C14}
  { rank = same; C10; C15}
  
}

### Trade offs

The reason renumbering *can* be useful is because of the locally-navigatable property of the DRG graph. In such a graph, one can compute the parents of a node (in logarithmic time ?). When generating a DRG graph in the reversed direction, with the [bucket sampling (p.22)](https://web.stanford.edu/~bfisch/porep_short.pdf) algorithm, the renumbering is necessary to keep that property. Reversing the edge does not allow (afaik) to get that property for reversed graph. That means, if one does NOT need that property for DRG graph anymore, using **the renumbering technique does not bring any benefit**.

## Computing the graph

### With renumbering and inverse permutation

This is the algorithm proposed in the [issue's latest PDF](https://github.com/filecoin-project/research/files/3509754/zigzag.pdf). It uses the renumbering technique for the DRG edges and the reversing technique for the expander edges.

// compute the parents for the node at the given index and given 
// layer with d parents, with the given chung's permutation
def parent(n, layer, index, d, perms):
  parents = []
  // correct ordering (lower indices -> higher indices)
  if layer % 2 == 0: 
     // add the correct DRG parents
     parents += drg_parents(index)
     for p in range(0, d):
       j = perms[p].compute(index)
       j' = perms[p].reverse().compute(index)
       // natural ordering lower to higher indices
       if j < index: parents.append(j)
       if j' < index: parents.append(j')
  
  // reversed ordering (higher -> lower indices)
  if layer % 2 == 0:
      // add the "renumbered" DRG parents
      natural = drg_parents(n - index + 1)
      parents += *map(lambda x: n - x + 1, natural)
      for p in range(0,d):
        j = perms[p].compute(index)
        j' = perms[p].reverse().compute(index)
        // reverse ordering higher to lower indices
        if index < j: parents.append(j)
        if index < j': parents.append(j')
        
  return parents 

### From the previous layer

This technique strives for **simplicity**. It assumes the following:
+ we use reversing **both** for the expander and the DRG edges such that an edge at layer $l$ gets mapped to its reverse at layer $l+1$.
+ we have the whole previous layer loaded in memory

Using this has two impacts:

**Graph computation** is now very simplified and more performant (at the cost of more space); shortened to the following pseudo-algo:

// previousLayer is represented as a list of edges for simplicity
def computeNextLayer(previousLayer):
    return map(lambda edge: return (edge[1],edge[0]), previousLayer)

One only needs to call the permutation of the chung's construction and DRG.parent function **once** (for the first layer); all other layers are derived from it.

**Family Commitment** seems simplified as well but TO VERIFY.