ZigZag DRG parents topology

[schomatis]

We seem to have two conflicting sources of information to determine the topology of ZigZag graphs:

• Paper Tight Proofs of Space and Replication which contains Figure 1.1 (and explanatory text in the "PoRep from ZigZag Expander DRGs" section).

• Technical report (TR) Scaling Proof-of-Replication for Filecoin Mining which contains a pseudo-code definition of the DAG.Parents function (and also explanatory texts).

Historically we have implemented what's described in the paper but lately more attention has been drawn to the TR because of the detailed pseudo-code. Even though both sources seem to indicate that the paper should be trusted over the TR (released before the paper) we would need an explicit confirmation of which source to rely on and a more comprehensive definition of how are ZigZag parents generated (ideally the figure and the pseudo-code should eventually converge to a definition accepted by all parties).

Discrepancies

Without going into the complete details, the parents obtained from the DRG and expander graphs, depending on the layer we're at, may either have their node indexes renumbered or their edge directions reversed (for succinctness we will associate in this description the verbs renumber and reverse with nodes and edges receptively). Renumbering and reversing (except for some corner cases) do not yield the same topology.

From the paper:

1. DRG parents are renumbered in odd layers.
2. Expander parents are reversed in odd layers (but connect the same node indexes as the even layers).

From the TR:

1. DRG parents are kept the same for even/odd layers, there is no transformation.
2. Expander parents are renumbered in odd layers (this is rough a simplification, closer inspection to the b = 1 case of the pseudo-code reveals comparisons of the renumbered j index against the original i one).

[schomatis]

Spawned from the discussion in #153 which concerned particularly the Chung's construction used to generate the parents from the expander graphs, this issue also discusses the generation of the base DRG parents.

[irenegia]

@schomatis
I believe there is no conflict between the paper and the TR as regards the final result.
The conflict is in the notation!

Notice that the TR (pag.18) describes the encoding by "swaping" the vector x = (x_0, .. x_n-1) of labels in each layer. (they the pseudocode in the box at page 18).
This + the construction from TR is equivalent to "standard" encoding (with no swiping) + construction from the paper.

my question is: which approach is better for implementation?

[schomatis]

@irenegiacomelli I'm not sure I follow, the swap seems to operate at a higher abstraction level than that of DAG.Parents, e.g., if that would "fix" the expander topology to match the paper it would "break" the DRG one I think.

Anyway, to help me follow your reasoning, could you produce a simple example where the b=1 case of the pseudo-code in the TR produces the same topology as the middle (odd) layer in the figure of the paper?

[irenegia]

@schomatis
We have two things in the PoRep: the graph (with the topology) and the definition of encoding (\ie how to use the graph topology to compute the replica given the data).

My previous comments was about the fact that both these things are different in the TR compared to the paper (eg, the encoding in the TR uses the swiping, which is not used in the paper).
In particular, the difference in the encoding in the TR "corrects" the difference in the graph definition and at the end the result (ie, the replica) are the same in the two cases.

[schomatis]

I still don't quite see how that correction works, but I trust your analysis so feel free to close this issue if you think it's resolved.

[schomatis]

From Slack:

Ben says that the paper takes precedence and also specifically confirms that the edges need to be strictly reversed between layers (for expansion).

Closing this as resolved then, do reopen if new questions arise, let's continue the expansion (Chung) parents specific construction discussion in #144.