Base DAG should have a unique topological ordering

[schomatis]

Add edges (i, i+1) for all i < N-1 for the parents of the base Graph. Discount that from the base degree, so we'll now have only 4 parents from bucket sampling.

Not very clear in Algorithm 1 of the original paper but we do know it has to be so since its code is based on Argon2i.

(edit: once resolved we'll also need to update the spec which at this time is just a copy of the code here)

---

PR: #843.

[schomatis]

From https://web.stanford.edu/~bfisch/porep_short.pdf:

Using the underlying DRG construction BucketSample[n] the corresponding metagraph
construction BucketSample[n, m] actually has degree at most m+ 1 because one of the two edges
is to the immediate predecessor.

Meaning that when the paper talks about a degree (m) of, say, 5 it's actually referring to the degree from the bucket sampling part, and it's not counting the one from the immediate predecessor, so following that spirit adding this "extra" edge per node here should not impact our current m of 5, @porcuquine does that sound fair to you?

[porcuquine]

Hmmmm. So if I understand, that means that we would now (considering our current graph and numbers) have 6 DRG parents in addition to the 8 expansion parents. I think you are proposing leaving everything as it is and just adding an extra parent in addition to the 5 already generated (while leaving the value of base_degree as 5).

I would need to look more closely, but I think this might require explicitly allocating a larger parent for the caller. Is that right?

Another question is how this impacts KDF generation. In the ZigZag case, we could (maybe?) not increase the total number of parents expected — since we are (almost?) always adding some amount of padding. But this doesn't apply to a plan DrgPoRep. So we would then need to handle bookkeeping for the extra parent in the KDF, etc.

Because of all that, it seems like maybe it would be better to just say that for us base_degree should include the immediate predecessor. This might mean we have to increase our total parents to 14 (which would not be nice) — but I think we are (or perhaps should be) thinking about how to avoid actually adding so much padding everywhere.

@nicola Your thoughts would be useful.

@schomatis Please ask more specific questions if I didn't address your original or wasn't clear. I haven't had time to think this through completely but wanted to give an initial response while I have time.

[schomatis]

Good point, didn't think about all those implications, we should handle this as explicitly as possible (maybe only in the CLI we can hide this detail). My original intention was to match the paper expectations, but this will need more clarification.

[nicola]

My understanding is that the degree 5 includes the predecessor and 4 nodes via BucketSample. So BASE_DEGREE is still 5, but the parents to generate is BASE_DEGREE-1

By looking at the PoRep Short paper the numbers we run were for 1 and 5. This implies that the direct predecessor is not being accounted for (otherwise the one with 1 would have degree one - not great). Hence I believe that we might have to add one more parent.

We should ping @ben-a-fisch on this one.

[porcuquine]

My previous reading was that in order to have base_degree=5, we would add the immediate predecessor while still retaining 5 bucket-sample parents.

Since we now have a growing team of ZigZag theory experts, can we get a reading on this from one of @lucaniz @irenegiacomelli @nikkolasg ?

[porcuquine]

I think this has been resolved. A historical note on naming may help make most sense of the situation. It's clear what needs to happen, and we can now make new naming decisions corresponding to that.

The paper has a parameter, m, which is exactly our base_degree. In fact, we used to call this m and this name may persist in some of the benchmarking examples. We previously believed that the immediate predecessor was included by the bucket sample algorithm, and that m was indeed the in-degree of the DRG graph. We now know that this is not the case and that we need to increase the total number of parents by one — the immediate predecessor.

Generally, we have three options.

1. Leave base_degree as it is, with no change of value.

• Add the immediate predecessor to parents().
• Change the calculation of degree() to add a + 1 term.

2. Increase the planned value of base_degree from 5 to 6.

• Add the immediate predecessor to parents().
• Change the calculation of DrgGraph::parents() to only generate base_degree - 1 bucket-sampled parents.

3. Rename base_degree back to m or to some other name TBD.

• Add the immediate predecessor to parents().
• Change DrgGraph::degree() to be 1 + <the new name for base_degree>.

Of these options, 1 seems preferable, since it will minimize the number of changes to planned/published values and to defaults when calling benchmarks, etc. As part of the changeset implementing this work, we should also make sure naming in benchmark examples is consistent with whatever we end up with. (The renaming portion of that work may already have been done.)

[schomatis]

Ok, going with number 1 (modulo the benchmark modifications that should be handled later).

[porcuquine]

@schomatis Is this blocked? If not, can you implement soon? We have a lot of big changes coming down up, so it would be good to take care of known fixes like this first so we don't have to bundle them with the new.

[schomatis]

Unblocked, will implement soon.

[dignifiedquire]

This is fixed as far as I know