## DKG ### feldman dkg feldman dkg is built on top of the idea's above to create distribution of the process among participants. Each participant $i$ is now a dealer running a version of Feldman vss, and glued together according to the following. . Firstly, each participant $i$ chooses a secret value $a_i\sim U(0, p)\in\mathbb{Z}_p$, as well as a random polynomial $q_i(x)$ of degree $t$ in $\mathbb{Z}_p[x]$: $$ q_i(x) = a_{i0} + a_{i1}x + a_{i2}x^2 + \cdots + a_{it}x^t $$ The participant then computes and broadcasts $C_{ij} = g^{a_{ij}}$ for $j\in[0, t]$ Then, everyone computes the shares of $1,\ldots,n$ of their secret polynomial $s_{ij} = q_i(j)$, and sends them secretly to participants $j=1,\ldots,n$. A participant is able to verify that a share received from $j$ is consistent by assuring: $$ g^{s_{ij}} = \prod_{k=0}^{t}C^{j^k}_{ik} $$ If this fails, then participant $i$ complains publically. If there are $t$ complaints against $j$, they're automatically kicked out. If there are less than $t$ complaints, the accused participant must broadcast the correct share (and random value if used). If this fails, they're booted (you're fired!). In this way, we can remove the assumption in Shamir's secret sharing of honesty of the participants, because we can verify when they're lying. Finally, participant $i$ determines their share as $s_i = \sum_{j\in\rm qualified} s_{ji}$, and the public key is now $y=\prod_{i\in\rm qualified}C_{i0}$, and the public verification values are $C_k = \prod_{i\in\rm qualified} C_{ik}$. The shared secret value $s$ itself is not computed by anyone since they don't know all the parts, but can be seen as $s=\sum_i a_{i0}$. ### pedersen dkg We now finally move onto secure distributed key generation that is verified to be secure enough for threshold signaturing (see [this](https://link.springer.com/content/pdf/10.1007/3-540-48910-X_21.pdf)). We now buil don topof the pedersen vss and feldman vss. #### Generating s: Each player $P_i$ performs a Pedersen-VSS of a random value $z_i$ as a dealer: 1. $P_i$ chooses two random polynomials $q_i(z), q_i^\prime(z)$ over $\mathbb{Z}_q[z]$ of degree $t$: $$q_i(z) = a_{i0} + a_{i1}z + \ldots + a_{it}z^t$$ $$q_i'(z) = b_{i0} + b_{i1}z + \ldots + b_{it}z^t$$ Let $z_i = a_{i0} = q_i(0)$. $P_i$ broadcasts $C_{ik} = g^{a_{ik}}h^{b_{ik}} \mod p$ for $k = 0,\ldots,t$. $P_i$ computes the shares $s_{ij} = q_i(j), s_{ij}^\prime = q_i^\prime(j) \mod q$ for $j = 1,\ldots,n$ and sends $s_{ij}, s_{ij}^\prime$ to player $P_j$. 3. Each player $P_j$ verifies the shares he received from the other players. For each $i = 1,\ldots,n$, $P_j$ checks if $$g^{s_{ij}}h^{s_{ij}'} = \prod_{k=0}^t (C_{ik})^{j^k} \mod p$$ If the check fails for an index $i$, $P_j$ broadcasts a complaint against $P_i$. 4. Each player $P_i$ who, as a dealer, received a complaint from player $P_j$ broadcasts the values $s_{ij}, s_{ij}'$ that satisfy the above. 5. Each player marks as disqualified any player that either - received more than $t$ complaints in Step 1b, or - answered to a complaint in Step 1c with values that falsify the relation above. Each player then builds the set of non-disqualified players QUAL. The distributed secret value $s$ is not explicitly computed by any party, but it equals $s = \sum_{i \in QUAL} z_i \mod q$. Each player $P_i$ sets his share of the secret as $s_i = \sum_{j \in QUAL} s_{ji} \mod q$ and the value $s_i' = \sum_{j \in QUAL} s_{ji}' \mod q$. #### Extracting $y = g^s \mod p$: Each player $i \in QUAL$ exposes $y_i = g^{z_i} \mod p$ via Feldman VSS: 1. Each player $P_i$, $i \in QUAL$, broadcasts $A_{ik} = g^{a_{ik}} \mod p$ for $k = 0,\ldots,t$. 2. Each player $P_j$ verifies the values broadcast by the other players in QUAL, namely, for each $i \in QUAL$, $P_j$ checks if $$g^{s_{ij}} = \prod_{k=0}^t (A_{ik})^{j^k} \mod p$$ If the check fails for an index $i$, $P_j$ complains against $P_i$ by broadcasting the values $s_{ij}, s_{ij}'$ that satisfy the relation in part 1 but do not satisfy the relation immediately above. 3. For players $P_i$ who receive at least one valid complaint, i.e. values which satisfy the equation in part 1 and not the equation above, the other players run the reconstruction phase of Pedersen-VSS to compute $z_i$, $q_i(z)$, $A_{ik}$ for $k = 0,\ldots,t$ in the clear. For all players in QUAL, set $y_i = A_{i0} = g^{z_i} \mod p$. Compute $y = \prod_{i \in QUAL} y_i \mod p$. What might this look like? I'd recommend looking at the implementation [here](https://docs.rs/secret_sharing_and_dkg/latest/src/secret_sharing_and_dkg/pedersen_dvss.rs.html#1-341) for the basics. The idea is that the reduction of single point failures via the secret generation requires a more secure protocol like pedersen dkg, which allows later steps to be less secure and more efficient, namely by using feldman instead. However, [it was shown](https://www.researchgate.net/publication/2558744_Revisiting_the_Distributed_Key_Generation_for_Discrete-Log_Based_Cryptosystems) that using Feldman vss for both stages is actually secure enough when subsequently used in a thresholding signature scheme! This is why cloudflare uses it, and saves them the pain of implementing two different VSS schemes. ## publically verifiable secret sharing and DKG The schemes above rely on internal validation of the council for maintaining honesty and rigor, but if the entire idea is to create a scheme that removes trust, this is a natural point to consider for further improvements. We move to define a publically verifiable secret sharing protocol: 1. Setup - The initial parameters contain information about base field, $(t,n)$ and the relation defining valid key pairs (pairing relation) - Generate public private key pair with SNARK proof asserting the validity of the pair - Execution of proof - verify validity 2. Distribution - This takes a secret, and outputs encrypted partial shares and a SNARK proof asserting sharing correctness 3. Distribution verification - Execution of previous proof - verify distribution of shares 4. Reconstruction - outputs a decrypted share and a proof of decryption - reconstruct the secert or return an error 5. Verify the reconstruction (namely if decryted share is valid decryption of the partial share) You'll notice that there are many SNARKs involved in this process, which adds must complications and headaches. For this reason, it's difficult to implement this protocol, so if you don't need this level of scrutiny, then it's probably better to not do this. I'd read [this](https://eprint.iacr.org/2023/1651.pdf) for a nice overview.