Track domain points (aka "x coordinates") mapping to validators

[cygnusv]

Some context:

dnunez — 08/08/2023 8:14 AM
@piotr I'm having troubles remembering where do we track share "x-coordinates" in Ferveo (i.e., for naive SS, if the i-th share  is y_i = f(x_i), I mean the x_i values). 
Particularly, all nodes should have consensus on the x_i values, but I'm having a hard time finding where's that happening

dnunez — 08/08/2023 10:13 AM
Is it possible that the domain is deterministic?

piotr — 08/08/2023 10:58 AM
Each DKG instance creates a "x-coordinates" vector, domain: 
https://github.com/nucypher/ferveo/blob/03b4e35afc5917d8dc2f638c85fc59fafb443650/ferveo/src/dkg.rs#L62-L62
https://github.com/nucypher/ferveo/blob/03b4e35afc5917d8dc2f638c85fc59fafb443650/ferveo/src/dkg.rs#L79C3-L79C4

piotr — 08/08/2023 10:59 AM
I'm reading ark_poly sources, and so far it looks deterministic

dnunez — 08/08/2023 10:59 AM
I'm asking this because I was wondering how is that our DKG works if nodes never agree on a given domain
this seems like a potentially brittle area

piotr — 08/08/2023 11:11 AM
Ok, it looks like it's deterministic. It's using a group generator to get the evaluation domain, which should result in the same domain every time:
https://github.com/arkworks-rs/algebra/blob/bdabff578812deba6abf32c1c99a79b9d0c58322/poly/src/domain/radix2/mod.rs#L69C13-L69C22
So what is the case when the nodes would not agree on the domain? Perhaps when they have incompatible arkworks versions? I think that could hardly happen, given that FTT evaluation domain definition is not changing anytime soon? But perhaps this dependency on using deterministic evaluation domain should be documented better, for example by moving it to MyEvaluationDomain::default? 

dnunez — 08/08/2023 11:14 AM
Do we always use a Radix2EvaluationDomain?
I thought that was the case when the DKG size was a power of 2

dnunez — 08/08/2023 11:16 AM
Yes, agreed. I'm just trying to find loose ends, but if we're sure this is deterministic, then I think we can move on

So it seems I was wrong in the end dismissing this as a non-issue: it's an issue when some of the x coordinates are produced after the DKG, e.g., during share recovery (i.e. for onboarding a new cohort participant).

I see 2 alternatives:

• We track domain points explicitly somewhere, perhaps as part of transcripts. With explicitly I mean, we track x coordinates directly, associated to validator addresses. This is simpler but potentially takes up more space.
• We continue with the deterministically-generated assumption, but we need to track generation indices that account for exclusions. For example "Validator A has the 1st domain point, B has the 2nd, C has the 5th, D has the 6th, etc", which could be the case for an initial cohort of 4 nodes where the last 2 nodes where replaced by new ones.

[piotr-roslaniec]

We enforce the ordering of participants on a contract level (must be sorted). When we onboard a new participant, we'd have to append them and re-order all participants. Similarly, when we off-board a participant.

We can take advantage of the aforementioned ordering ("global ordering vector") to implement DKG state transition in ferveo and fix the issues with domain_points ordering.

Actionable items:

• Scope changes in the Coordinator contract for refreshing and recovery
• Scope changes in the ferveo DKG implementation
• Consider the impact on the product

Based on the conversation on Discord.

[piotr-roslaniec]

Consider adapting existing sorted validator ordering:

• Store canonical validator ordering in the coordinator contract
• Upon refreshing and recovery, update the ordering in the contract
  • For recovery
    • When off-boarding a validator, mark ritual.participants[validator_index] as 0x0
    • When on-boarding a new validator, either reuse an old index ritual.participants[validator_index]
  • For refreshing
    • Replace ritual.participants with new validators - No need to do anything
• Translate validator ordering into u8 share indexes (alternatively, use a HashMap)
• Use those share indexes where ordering matters (for example as a part of transcripts)

[piotr-roslaniec]

Closed by #175 and #182