Fix expander parents generation

[nicola]

Description

See the work done in filecoin-project/research#144, the newest spec for the chung construction lives in https://www.overleaf.com/3456316943pfxsqxkdghsy%E2%80%A9

Acceptance criteria

Risks + pitfalls

Where to begin

[schomatis]

Studying new analysis in Stacked-DRGs & ZigZag Security parameters, section 2.1, the conclusion for implementation fixes until now is:

1. Increase expansion_degree from 8 to 16.
2. Generate those extra 8 parents not from the same permutation but form its inverse.

@irenegia @porcuquine Could either of you confirm point 2 please? Reading Algorithm 1 I'm having trouble following the notation and it's not clear to me that this is the case (although I've been told as such, but would rather have a clear confirmation here please before moving forward).

[porcuquine]

@schomatis Your general reading is correct, but let me make a few notes and help prioritize.

1. I think it might be better to leave expansion_degree as 8 and instead change the interpretation of that parameter. This is because making this change is a correction. The average expansion degree will now be 8. Since d = 8 is the formal concept we're trying to replicate, we should probably just define expansion_degree = d and propagate the change that way for now.

There will probably be changes to how parents are handled in the future.

2. Yes, we need to generate as many parents from the inverse as from the permutation itself. In practice, this means we will use both the inverse and the permutation on every layer.

It's not clear to me that the PDF is updated to reflect this, btw. cc: @irenegia

[porcuquine]

@schomatis Elsewhere (will try to comment there also), I think you mentioned wanting to defer this until after caching is moved to disk. I think it's important that we make the logic changes as soon as possible so that they don't block or complicate the many other changes which will be coming soon.

If we really want to avoid caches growing in the short term, you could change the parameters to be 'half-strength' (i.e. lower expansion_degree to 4) as a temporary measure.

But please prioritize this over restructuring the cache. It's very high priority that this be taken care of before we start in on new ZigZag work.

[UPDATE: after catching up, it's not clear to me that my comments above address any plan you actually had — so ignore whatever is inapplicable. That this is a high priority change that should be taken care of as early as possible remains true, though.]

[schomatis]

@porcuquine I'm sadly missing most of what you wrote in the last two messages, sorry. Let me ask one question at a time to narrow down the conversation as much as possible. Regarding point 1, the ZigZag graph degree function controls the size of the vectors allocated for its parents, so my new question would be: should that function still return 8 or 16? If the answer is still 8, should we adapt the code around it to allocate two vectors? (edit: or should it return twice the value of the expansion_degree?)

[irenegia]

It's not clear to me that the PDF is updated to reflect this, btw. cc: @irenegia

For the zigzag graph, we need to implement Algorithm 2 from the PDF (ie, Chung construction + inversion of projected edges), not Algorithm 1 (which is only the basic Chung construction)

More clear now?

[porcuquine]

@schomatis The ZigZag graph degree method returns the base graph's degree plus the ZigZag graph's expansion_degree.

Per #744 (which seems is still not yet implemented), the base graph's degree should be 1 + its base_degree.

My suggestion above is that we leave expansion_degree as 8, but adjust the value of degree.

So, with current parameters the ZigZag graph's degree should be 5 + 1 + 2*8 = 22.

This is the actual number of parents (including padding) that a node will have.

[schomatis]

Thanks for the clarification, will correct PR #860 in the coming days.

[schomatis]

Per #744 (which seems is still not yet implemented), the base graph's degree should be 1 + its base_degree.

@porcuquine Note that there is a (draft) implementation in place already linked to that issue, see #843, @dignifiedquire had some thoughts about it, I'll need you two to work them out in #744.

[schomatis]

Will be fixed in #864.