CHUNG: Understanding Chung's construction in the ZIgZag graph

[irenegia]

Standard Chung's construction:

• we have a two-layer graph, each layer with N nodes (indices form 1 to N)
• we sample a random permutations of pairs, P: [d] x [N] --> [d] x [N]
• assign edges in this way: given a node i in the lower level, its parents in the upper lever are computed as follows.

     Chung.Parents(i) {
          Parents = empty
          for k = 1 to d
                 (k',j) = P(k,i)
                 Parents = Parents U {j}
          output the list Parents
       }   
  
  

This always gives at most d parents.
My understanding is that if N is large, then this gives exactly d parent with high probability.

How to modify the previous to get the "alternate" construction we need for ZIgZag?

In ZigZag, the expander edges in layer j (j=2, 3,...) are constructed by taking the edges between layer j-1 (upper) and layer j (lower) given by Chung construction and projecting them on the lower layer following this rules:

1. if j is even, edges goes from higher-index to lower-index nodes // (1) <-- (2)
2. if j is odd, edges goes from lower-index to higher-index nodes // (1) --> (2)

This means that the Chung.Parents(i) functionality need to be changed!
This is an attempt for the new parent functionality:

   ZZ.Parents(i,j) {
         Parents = empty

           --if mod_2(j) =0 (even layer)

               for k = 1 to d
                   (k',i') = P(k,i) and i' > i 
                   Parents = Parents U {i'}    
                   ## this are the Chung parents of i with the right direction
                   
                   (k',i') = P^{-1}(k,i) and i' > i 
                   Parents = Parents U {i'}    
                    ## in Chung construction there is an edge from i to i', since i'>i we reverse this and i' becomes a parent  
              
           -- if mod_2(j) =1 (odd layer)
               
               ToDo!  QUESTION: do I reverse the node indices as well? 
                See \ pag 17 [here](https://web.stanford.edu/~bfisch/porep_short.pdf)

            output the list Parents
         }'

EDIT:
my main concern is the following:
given that we modify Chung.Parents(i), can we still use the expansion factor of Chung to analysis the security of the proof ???

[irenegia]

@porcuquine: is this "close enough" to what we do in the code? :)

Question (@nicola): in each layer we use the permutation P and its inverse, P^{-1}. Because of this, each node can have more than d parents. Right?
About what you wrote in the slack channel, are you suggesting to avoid using the inverse P^{-1}?

[schomatis]

For reference, this is the (not correctly formatted) Chung spec:

https://github.com/filecoin-project/specs/blob/master/zigzag-porep.md#chungexpander-bipartite-expander-graphs

(The Rust code on which it is based is here and here.)

[schomatis]

@porcuquine: is this "close enough" to what we do in the code? :)

We only use one permutation (direct or inverse) per layer, the rest seems close enough. (Yes, we invert nodes indexes in the reverse.)

[schomatis]

Question (@nicola): in each layer we use the permutation P and its inverse, P^{-1}. Because of this, each node can have more than d parents. Right?

Yes, that would be my intuition. Looking at the paper pseudo-code, we iterate 8 times (k) but each iteration can add two parents (direct and inverse permutation), so we can add between 0 and 16 parents per node.

[schomatis]

On a personal note, I would also like to better understand the intuition behind simultaneously using P and P^{-1} on the same node/layer, which seem to me as totally unrelated oracles (even though they're its own inverse), that is, what does it bring to the table in contrast with cases like:

1. Use only P, iterating it from 0 to 16.
2. Use a different permutation P_2 (with inverse P_2^{-1}) alongside P on one layer, iterating from 0 to 8, and P^{-1}/P_2^{-1} on the next layer.

[irenegia]

We only use one permutation (direct or inverse) per layer, the rest seems close enough. (Yes, we invert nodes indexes in the reverse.)

Thanks @schomatis !
So, it is confirmed that what is written in the spec (ie, what we implement) is different to what is described in the paper.
I need to check if this affect the security of the construction (and in case, how)!

[irenegia]

On a personal note, I would also like to better understand the intuition behind simultaneously using P and P^{-1} on the same node/layer,

@schomatis
This is the intuition:
Because of the "only-one direction" rule, the parents the node i are of two kinds (assuming even layer):

1. parents of node i according to standard Chung construction with higher indices (these are the ones we get using the permutation P and checking i' > i),
2. "sons" of node i according to standard Chung construction with higher indices (these are found by the inverse permutation P^{-1}. In other words (k,i) = P(k', i') with i' >i)

To understand the second case: recall that if the standard Chung construction creates an edge
(i) -- > (j) with j >i
then because of the "only-one direction" rule we invert this edge and get
(i) <-- (j)
(in other words "sons become parents if the are higher" :p )

[schomatis]

Thanks for the explanation! I agree with the necessity of the property that parent/child relation should be invertible, but I'm not sure I can extract from that the rationale of using the current construction, in contrast with the other two proposals I submitted as example, e.g., using only P (with doubled the iterations) would still guarantee that the parents we found will be its sons in the reverse direction (similarly with a P_2 permutation that would also have an inverse).

To put a simple example (because I sense there might be a gap in my understanding of the Chung permutation or its properties), in the even layer (b=0) if k only takes value 0 (single iteration) and I run for node i

• j <- P(i,0)
• j' <- P^{-1}(i,0)

is there any guarantee that, for example, if j > i (so the found j can't be a parent) then j' < i and then I have at least one parent from running both permutations? What is the difference with running only P with 2 values of k?

• j <- P(i,0)
• j' <- P(i,1)

In this case do I have different probabilities of having [0,2] parent for node i? Isn't the "only-one direction" rule respected just the same (any valid j/j' parent will be the son of i in the inverse layer) or is there a difference in its application?

[porcuquine]

@irenegiacomelli I think @schomatis understands both the implementation and my specific question about the implications of changing it. For that reason, I'll leave this to him. Please one of you ping me here if something new comes up, we reach a resolution, or we reach a decision point where input is valuable.

[nikkolasg]

So, it is confirmed that what is written in the spec (ie, what we implement) is different to what is described in the paper.
I need to check if this affect the security of the construction (and in case, how)!

To me it looks like on expectation, there will be half less parents in one layer, since the other half have lower indices than their parents (following @irenegiacomelli algo. notation) so these are "invalid" given the direction of the layer (again, on expectation). For example, the first 10% of the nodes (low indices) will often get valid parents since each of these parents is randomly chosen so has a 90% chance of having a higher index. On the other hand, the last 10% of the nodes (higher indices) will often get invalid parents because each parent has a 90% chance to have a lower index.

Hence imo it's the reason why we are using the inverse permutation to get another "valid half". So it seems problematic that the implementation is not doing that since then the Chung's -based analysis can't apply.

As a side note, because it appeared in Slack at some point: the "reversing of direction each other layer" goal is different though, as Ben put it in the paper p.31 without it the whole construction wouldn't be a tight proof of space.

[nikkolasg]

@schomatis

is there any guarantee that, for example, if j > i (so the found j can't be a parent) then j' < i and then I have at least one parent from running both permutations?

From what I understand of permutations, there's no guarantees at all. It's even how Ben wrote the algorithm in the filecoin / porep paper p.17: if puts a condition on the reverse permutaiton: if j' > i.
The only difference using the reverse permutation is that, if i != j (which happens with high pr.), you can't get back the j you got from the first permutation. To put it differently, it's as if you pick out a second time a ball from a jar without replacement, so you can't get the first ball again.

But if we were using a second random permutation, since there's a negl. pr. of finding that exact same j again, I am not sure how the reverse permutation really helps. I tend to agree with you that both "methods" look indistinguishable (with high pr.).

[schomatis]

The only difference using the reverse permutation is that you can't get back the j you got from the first permutation. To put it differently, it's as if you pick out a second time a ball from a jar without replacement, so you can't get the first ball again.

@nikkolasg Why? If I understand correctly you're saying that if j <- P(i,k) then P^{-1}(i,k) != j, and for me the only guarantee is that if if j <- P(i,k) then i <- P^{-1}(j,k) (let's say i!=j) but I know nothing about the inverse permutation of the original node i.

---

In any case, that discussion is just for improving my personal understanding of the model (I'm not challenging the original construction), the important part is that I agree with your assessment, the expectation of "valid" (not padding) parent nodes of our implementation is indeed d/2 (that's something that can be seen when debugging the code), and I also agree that this must violate security assumptions.

From the implementation side, I'm trying to better understand a solution (like actually implementing the paper's algorithm) that would produce the expected d parents but also have the possibility of having more than d parents per node. That is something that may impact performance and will definitely have other implications on how we handle parents at the moment (our assumption is always that we have an array with 13 = 5 base + 8 expansion parents).

Again from the side of implementation, ideally I'd stop adding parents once I reached the desired target of, say, 8, but that would put an upper bound while leaving the lower at 0 and will drop the expectancy (not as low as our current implementation but still). Is there any middle ground acceptable from the theoretical side here?

[porcuquine]

@schomatis I think limiting the parents could also leading to a violation of the assumption that all edges are shared between layers (just with direction reversed).

One thought for everyone to consider (cc: @nico): since we already intend to fully cache expansion parents, we could commit to this strategy, require precomputation, and implement some approach which requires global analysis of the graph (losing localization). This might be expensive, but if it saves us from (for example) having to double the number of expansion parents (to 16) just to guarantee an expected 8, it may be worth it.

I do not have a concrete suggestion for how to do that, but we should consider whether such a solution would be acceptable in general.

[schomatis]

If that (or something along those lines) were possible we could extend the number of Feistel rounds to increase the chances of finding parents within the acceptable [0,i) range (and (i,N] in reverse).

[nikkolasg]

@schomatis So let's call the permutation P, and its inverse P'. If you have P(i) = j , then P'(j) = i. So P'(i) = j' != j , because if it was the case, then we would have P'(i) = P'(j) which is impossible when i != j since P' is a permutation.

[schomatis]

I'm not sure we're meaning the same by permutation here, for me the bit permutation of Feistel is just "generate random int of bits length", but let's continue this on Slack later, I feel I already diverted the discussion too far from the original (important) issue you raised earlier.

[porcuquine]

@nikkolasg

I am not sure your analysis holds for all P. In particular, what if P contains 2-cycles, so thatP = P' (at least for some i, j)?

For example: P(1) = 2, P(2) = 1, P'(2) = 1, P'(1) = 2.

If i = 1, j = 2, then j = P(i) = 2 = P'(i) = j', but still i != j.

I could be seeing this wrong, but do you think this case is handled by your description? I think it's still possible to pick the same parent twice by either method. (I am not saying the probability is identical: not sure without more thought.)

[nikkolasg]

Good catch. My condition is wrong indeed and here is the correct one that catches your example I believe:

P(i) = j  means P'(j) = i
P'(i) = j' means P(j') = i
=> 
j' == j <=> P(j') = P(j) <=> i = P(j)

So the condition is P(j) != i , i.e. to not having a 2-cycle as shown by @porcuquine.
That probability (Pr[ P(j) = i ]) is the same actually than before I think: for a given permutation, it's 1/N, which is believed in our case to be negligible. With composition, even if we run k times this permutation, if k << N, then the probability still is negligible.
So using a new permutation or using the inverse seem to exhibit the same pr. that we get the same parent. So both approaches do seem indistinguishable to me as well.

[irenegia]

This is very interesting, thank you all!

Unfortunately, I am still stuck still at the very begging of this discussion.
I'll recap here my thinking and keep work on this offline (help welcome!)

1. (OK) The security analysis of the Stacked-DRGs is strongly based on two properties of the expansion factor of the standard Chung's construction for degree 8. These properties are proved in Ben's Tight PoS paper.

2. (Partially Open) Now, if we consider the ZIgZag graph (with Ben's way to project Chung edges) these properties about the expansion should be maintained (clearly not among layers, but inside the same layer).

3. (Totally Open) If we modify the projection of the Chung edges as proposed by @schomatis and the others, then we can't have any assumption on the fact that these key properties hold! We need to re-prove them (or a modified version of them) from scratch.
   A way to approach this, maybe, is the following: what would be the "best" (most efficient) way to project? Fix that and see what we can prove... What do you think?

[nico]

One thought for everyone to consider (cc: @nico): since we already intend to fully cache expansion parents, we could commit to this strategy, require precomputation, and implement some approach which requires global analysis of the graph (losing localization). This might be expensive, but if it saves us from (for example) having to double the number of expansion parents (to 16) just to guarantee an expected 8, it may be worth it.

I do not have a concrete suggestion for how to do that, but we should consider whether such a solution would be acceptable in general.

It's an interesting question! Have you considered if this would impact cache expiry at all?

[porcuquine]

Thank you, @nico — and what a wonderfully gracious way to respond to my mistake. For clarity, I had meant to mention @nicola.

To your question: the cache will remain valid for as long as the graph seed remains unchanged. Individual parts will not have different lifetimes than the graph as a whole, regardless of how they are computed.

[irenegia]

@porcuquine @schomatis

Quick update: I finally started to follow better this part of the security proof more and in my understating we should use both P and its inverse P^-1 in each layer.

The difference between odd and even layers is the re-numbering of nodes (we invert them ivy two layers) and the direction of edges.

[porcuquine]

The difference between odd and even layers is the re-numbering of nodes (we invert them ivy two layers) and the direction of edges.

I am not sure what you mean by this. Assuming you are only talking about the expansion (Chung) parents and not the DRG (bucket sample) parents, then there is no re-numbering between layers. I agree that edges are simply reversed between layers but believe this would not be the case if we were also renumbering nodes. (It's possible we are just using different terminology, in which case hopefully this discussion will clear it up.)

Also, is your comment about the need for P and inverse P in the context of the discussion above, or more general? In other words, are you specifically ruling that doubling the number of expansion parents would not be equivalent? Or are you just noting that our current implementation yields too few parents.

Either way, do you agree that making this change can theoretically lead to up to 16 parents? (An extra eight more become possible at each layer.) If we make this changes, as it seems we must, we should strongly consider implementing #142. Otherwise this will significantly increase our circuit size. Can you comment there on whether we are on the same page, and whether you believe we can safely perform that optimization?

[irenegia]

@porcuquine

I am not sure what you mean by this. Assuming you are only talking about the expansion (Chung) parents and not the DRG (bucket sample) parents, then there is no re-numbering between layers. I agree that edges are simply reversed between layers but believe this would not be the case if we were also renumbering nodes. (It's possible we are just using different terminology, in which case hopefully this discussion will clear it up.)

Yes, there is no re-numbering. I meant that node i becomes node n-i+1, bad choice of words.

[porcuquine]

That's what I thought, but I don't think this transformation affects expansion parents. I think it's only used when calculating the DRG parents (bucket sampling). We may be agreeing; I just want to make sure since if we aren't, something will have to change somewhere (implementation or ideas).

[irenegia]

Also, is your comment about the need for P and inverse P in the context of the discussion above, or more general? In other words, are you specifically ruling that doubling the number of expansion parents would not be equivalent? Or are you just noting that our current implementation yields too few parents.

Yes, for sure our current implementation of ZigZag has too few parents.
Using P and inverse P is the same layer is the correct way to construct ZigZag according to the security proof in the paper (based on Chung's construction)
Note: P and inverse P have to be computed only for the first and second layers (layer 0 and layer 1), all the others are just copies of one of these two!!
Is this still very expensing?

Substituting inverse P with another random permutation doesn't work with current analysis and parameter. It basically means that we use a different (new?) construction for the bipartite expander (instead of Chung.) So, if we need to do this, we have to carefully study this new construction.

[porcuquine]

Got it, thanks.

[irenegia]

Either way, do you agree that making this change can theoretically lead to up to 16 parents? (An extra eight more become possible at each layer.) If we make this changes, as it seems we must, we should strongly consider implementing #142. Otherwise this will significantly increase our circuit size. Can you comment there on whether we are on the same page, and whether you believe we can safely perform that optimization?

Yes... we are doubling the number of expander parents, but only for some (half?) nodes. For the others we are actually reducing it. So, you are right that if we want to not double the circuit size, we should do the bucket trick... I'll look at that.

Other solution: we can try to start form Chung's construction with degree 4!
(cc @nikkolasg)

[porcuquine]

Can we do both? That would be fantastic.

[irenegia]

That's what I thought, but I don't think this transformation affects expansion parents. I think it's only used when calculating the DRG parents (bucket sampling). We may be agreeing; I just want to make sure since if we aren't, something will have to change somewhere (implementation or ideas).

mmmh... I think this transformation is used also for the expansion parents of odd layers (the reverted ones). But let' me check this!

[porcuquine]

@irenegiacomelli

I looked a this and for a moment thought you were right, but @schomatis pointed out otherwise.

So everything I wrote below does not correspond to p.17. The paper describe using the same numbering with each layer.

That having been said. Wouldn't it be better to reverse the numbering (as you describe as I misunderstood you to be suggesting) so that each layer would have an expected 8 parents for all nodes?

My quoted text below describes implications of doing it that way. This seems far better than using a method which will cause expansion-parent count to vary between 0 and 16 parents, require special challenges and circuit changes as in #142, etc.

Is it possible that your my (accidentally) proposed 'mixed' solution or some variant is what should have been described all along?

I looked at the paper (p.17) as noted in your TODO, and I think you are right.

This also makes sense because it resolves the issue of expected number of parents varying by position. Because the inverse permutation is used, and the node is taken from the reversed graph, the probabilities of finding a parent by either method (forward or inverse with 'renumbering') are complementary.

For example, the first node will always have zero parents derived from the forward permutation, but after renumbering, this node (now the last) will always have eight parents. The same logic applies for all nodes, so each node has eight expansion parents, on expectation — which is the goal.

This all makes sense now. It also means we may not need to eliminate padding as in #142.

The one concern I have is that as far as I can tell, this does not guarantee eight parents (even though my trivial example does). It seems we might occasionally have fewer (and need padding, which seems fine) — but might also occasionally have more. If we had more we would either have to ignore (bad) or handle it in the circuit somehow, which would be expensive. In the worst case, we would need to pad everywhere else to account for the possibility.

It might be the case that this is vanishingly unlikely, though. My suggestion is that we state a constraint that there never be more than eight parents and check it at run-time (or at cache-generation time). In practice, we can analyze the entire graph (by running this check) before setting the graph seed (or the feistel keys — which should probably be made public parameters). It should be safe to only choose graphs that have this property, assuming they are common. Do you agree?

If this all seems right, I think we can begin moving this into development. Once we reach agreement, I will create an issue inrust-fil-proofs and ask you to monitor to make sure we remain on the same page.

[irenegia]

Wouldn't it be better to reverse the numbering (as you describe as I misunderstood you to be suggesting) so that each layer would have an expected 8 parents for all nodes?

I am not sure that I understand: in the way I see this, the numbering of nodes does not change the number of parents that a node has.
Numbering is just the names we give to nodes, but the construction will anyway require that the first node (starting from the left) in an odd layer is "equivalent" (ie, has the role of) the last node in an even layer (Here equivalent has different meaning depending is we are adding expander edges or DRG edges).

So, unfortunately I don't see how we can save parents....

Notice that 16 is an upper-bound, I think in practice we can have less parents (there is even intersection between expander and DRG parents).

[porcuquine]

I am not sure that I understand: in the way I see this, the numbering of nodes does not change the number of parents that a node has.

You can ignore what I wrote. I have convinced myself that this misinterpretation doesn't actually make any sense. I concur with your unfortunate assessment, though I think we can still use #142 to reduce parents.

I think in addition to adding the inverse permutations at each layer, we also have to add the renumbering (which we use for DRG parents but not expander parents, currently).

I don't actually understand why this is done, since it seems to destroy the property that expander edges are the same between layers just with directions reversed. (Do you agree, or do you think I'm confused about that, which is possible?)

However, if you are sure that we should implement what is described in the pseudocode on p. 17, then I think we need to do that also.

Let us know when you are confident in the changes required, and we can create an implementation issue.

[irenegia]

if you are sure that we should implement what is described in the pseudocode on p. 17, then I think we need to do that also.

The pseudocode on p.17 convinces me for the way expander edges are added. But I don't understand with the DRG edges/parents are added in the same way for odd and even layers. I believe that is a typo (refer to the very first line in the algorithm).

I'll check and let you know.

[irenegia]

I re-wrote the pseudocode of p.17 applying the re-numbering only to DRG parents (and not to chung parents) following what is explained in Ben's paper.
See section 2 here:
https://www.overleaf.com/3456316943pfxsqxkdghsy

@schomatis, @nikkolasg @porcuquine
What do you think about this?

[nicola]

Chung construction written up here: https://www.overleaf.com/3456316943pfxsqxkdghsy


Possible improvements on expander parents: #157

[nicola]

implementation issue being created here: filecoin-project/rust-fil-proofs#827

[nicola]

Can you ack, so that we can close this:

• @porcuquine
• @schomatis