Introduction

In a previous post, we discussed important VSS and DKG constructs and presented the Aggregatable DKG. Now that the reader better understands DKG, this article elaborates on a different DKG scheme called HybridDKG, as published in Distributed Key Generation in the Wild.

HybridDKG is a DKG that operates under the asynchronous communication model which is a much more realistic model than the synchronous model that most other DKG schemes rely on. Its underlying VSS, called HybridVSS, is based on AVSS, which is the component of HybridDKG that allows it to operate asynchronously. Since HybridDKG is operating under the asynchronous model, it requires both its VSS and DKG protocols to use consensus mechanisms in order for the nodes to agree on the secrets.

Assumptions

As with every cryptographic contruct, HybridDKG relies on certain assumptions in order to prove its security properties.

Communication model

HybridDKG uses the asynchronous model of communication, in which clocks of nodes may not be accurate (meaning they can be out of sync) and messages can be delayed for arbitrary period of time. In this model, it is assumed that the adversary manages the communication channels and can delay messages as it wishes. HybridDKG assumes that a real-world adversary cannot control communication channels for all the honest nodes and, thus, that the adversary (eventually) delivers all the messages between two uncrashed nodes.

A stricter assumption, named weak synchrony, is used only in order to prove the protocol's liveness. Under the weak synchrony assumption, the time difference $delay(T)delay(T)$ between the time a message was sent ($TT$) and the time it is received doesn't grow indefinitely over time. Weak synchrony is not necessary for the protocol's correctness.

It is also assumed that all communication is authenticated and the adversary is unable to spoof messages.

Faults

HybridDKG can tolerate non-byzantine node crashes, non-byzantine broken communication links and byzantine faults. It groups non-byzantine crashes and non-byzantine single broken communication links under the same fault type. The byzantine adversary is considered static, meaning that it cannot change its choice of nodes as time progresses.

The protocol can tolerate:

• Up to $tt$ byzantine nodes
• Up to $ff$ non-byzantine crashed nodes and non-byzantine failed connections at any given instant in time
• $d(\kappa )d(\backslash kappa)$ maximum number of crashes an adversary is allowed to perform during its lifetime

The number of the participants is:

$$n\ge 3t+2f+1n\; \backslash ge\; 3t+2f+1$$

Adversary

An assumption introduced by the specific polynomial commitment scheme used in this HybridVSS is that the adversary is computationally bounded on the DLP with a security parameter $\kappa \backslash kappa$.

Prerequisites

We first list some mathematical properties that will be useful later on:

• To reconstruct a univariate polynomial of degree $tt$ we need $t+1t+1$ points on that polynomial
• Having a bivariate polynomial $\varphi (x,y)\backslash phi(x,y)$ of degree $2t2t$, we can generate univariate polynomials by fixing the value of $xx$ (or $yy$): $a_{x=x^{\mathrm{\prime }}}(y)=\varphi (x^{\mathrm{\prime }},y)a\_\{x=x\text{'}\}(y)\; =\; \backslash phi(x\text{'},\; y)$
• If the bivariate polynomial is symmetric, it holds that $\varphi (x,y)=\varphi (y,x)\backslash phi(x,y)\; =\; \backslash phi(y,x)$
• From the above we can derive that for a symmetric $\varphi \backslash phi$ it holds $a_{x^{\mathrm{\prime }}}(y)=a_y(x^{\mathrm{\prime }})a\_\{x\text{'}\}(y)\; =\; a\_\{y\}(x\text{'})$

HybridVSS

In the asynchronous model, each node follows two assumptions: that enough nodes will get their shares and there will be enough nodes participating in reconstruction. In order to remove the need to make assumptions, HybridVSS takes it a step further and provides a mechanism for nodes to keep track of how many other nodes are participating and their states instead of relying on the above assumptions.

We will now define the sharing, reconstruction, and recovery phases of HybridVSS. All the messages described below are tagged with a unique session ID $(P_d,\tau )(P\_d,\; \backslash tau)$, with $P_{d}P\_d$ being the session's dealer and $\tau \backslash tau$ a unique number.

Sharing

Initialization

The dealer $P_{d}P\_d$:

• produces a random symmetric bivariate polynomial $\varphi (x,y)={\sum }_{i,j=0}^t{\varphi }_{ij}{x}^i{y}^j\backslash phi(x,y)\; =\; \backslash sum\_\{i,j=0\}^t\backslash phi\_\{ij\}x^iy^j$ with the secret encoded in as the constant factor $\varphi (0,0)={\varphi }_{00}\backslash phi(0,0)\; =\; \backslash phi\_\{00\}$.
• calculates a homomorphic commitment $CC$ to the polynomial which is a matrix with $C_{ij}=g^{{\varphi }_{ij}}C\_\{ij\}\; =\; g^\{\backslash phi\_\{ij\}\}$. $CC$ can be used by nodes to verify that:
• a given univariate polynomial $a_i(x)={\displaystyle \sum _{l=0}^t{a}_{i,l}{x}^l}a\_i(x)=\backslash displaystyle\backslash sum\_\{l=0\}^t\; a\_\{i,l\}x^l$ belongs to $\varphi \backslash phi$ by checking: $g^{a_{i,l}}{\displaystyle \prod _{j=0}^t(C_{jl}{)}^{i^j},\mathrm{\forall }l\in [0,t]}g^\{a\_\{i,l\}\}\; \backslash stackrel\{?\}\{=\}\; \backslash displaystyle\backslash prod\_\{j=0\}^t(C\_\{jl\})^\{i^j\},\; \backslash forall\; l\backslash in[0,t]$
• a given value $\alpha \backslash alpha$ corresponds to $\varphi (m,i)\backslash phi(m,i)$ by checking: $g^{\alpha }{\displaystyle \prod _{j,l=0}^t(C_{jl}{)}^{m^j{i}^l}}g^\backslash alpha\; \backslash stackrel\{?\}\{=\}\; \backslash displaystyle\backslash prod\_\{j,l=0\}^t(C\_\{jl\})^\{m^ji^l\}$

Dealing

$P_{d}P\_d$ then deals to each node $P_{i}P\_i$ a univariate polynomial $a_i(x)=\varphi (x,i)a\_i(x)\; =\; \backslash phi(x,i)$ by sending a message called $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$. This message also delivers $CC$. $CC$ is also sent with all other type of messages between nodes so that any two participants can verify the dealer’s commitment and prevent a malicious dealer from segregating the nodes by sharing different commitments.

Each $P_{i}P\_i$ that receives a $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$, verifies $a_i(x)a\_i(x)$ using $CC$. This polynomial provides a way for $P_{i}P\_i$ to generate a point that belongs to the polynomial $a_j(x)a\_j(x)$ of another node $P_{j}P\_j$ since $a_i(j)=a_j(i)a\_i(j)\; =\; a\_j(i)$ due to $\varphi \backslash phi$'s symmetry.

Gossip-based validation and consensus

Each $P_{i}P\_i$ that receives a valid $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$ message, sends a message called $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ to each node $P_{j}P\_j$ to inform them of the fact that the dealer got in touch. $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ carries $a_i(j)a\_i(j)$ as a proof that it was dealt a valid $a_i(x)a\_i(x)$.

After sending $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ to all nodes, $P_{i}P\_i$ enters a listening state, where it listens for two kinds of messages, $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ and $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$.

For every received $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ from a node $P_{j}P\_j$ the receiver $P_{i}P\_i$:

• verifies $a_j(i)a\_j(i)$ against $CC$ and if verified, it stores the point $(j,a_j(i))(j,\; a\_j(i))$ in a set $A_c^i\stackrel{}{\leftarrow }{(j,a_j(i))}_{j}A\_c^i\; \backslash xleftarrow\{\}\{(j,\; a\_j(i))\}\_j$
• if enough ($\lceil \frac{n+t+1}{2}\rceil \backslash lceil\backslash frac\{n+t+1\}\{2\}\backslash rceil$) valid $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ messages with the same commitment $CC$ are received to convince $P_{i}P\_i$ that enough nodes were reached by the dealer, it uses the points in $A_c^{i}A\_c^i$ to interpolate a polynomial ${\bar{a}}_i(x)\backslash bar\{a\}\_i(x)$
• sends a $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ to all other nodes carrying a point ${\bar{a}}_i(j)\backslash bar\{a\}\_i(j)$ as a proof of the fact that it received enough $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$s

For every received and verified $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$, $P_{i}P\_i$:

• stores the received point ${\bar{a}}_j(i)\backslash bar\{a\}\_j(i)$ in the same set $A_c^{i}A\_c^i$
• if enough ($t+1t+1$) $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages with the same commitment $CC$ are received to be able to interpolate a polynomial of degree $tt$, $P_{i}P\_i$ interpolates ${\bar{a}}_i(x)\backslash bar\{a\}\_i(x)$
• sends a $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ that carries ${\bar{a}}_i(j)\backslash bar\{a\}\_i(j)$ to each node $P_{j}P\_j$
• if enough $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages ($n-t-fn-t-f$) with the same commitment $CC$ are received for $P_{i}P\_i$ to be convinced that enough nodes know that enough nodes are participating, it calculates its share $s_i={\bar{a}}_i(0)s\_i\; =\; \backslash bar\{a\}\_i(0)$ and stops.

Additional notes

A node terminates the sharing process if it has received $(n-t-f)(n-t-f)$ $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages. Here, the node makes sure that there is a sufficient amount of honest nodes with shares. In other words, it makes sure that the participating honest nodes form a majority in the presence of up to $tt$ byzantine adversaries and up to ff crashed nodes.

If a node received a $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ from another node, it implies that the other node has sent an echo and it was never received. I.e., a $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ implies an $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$. It is possible for a node to finish the sharing phase by only receiving enough ready messages. In this case, it needs to interpolate ${\bar{a}}_i(x)\backslash bar\{a\}\_i(x)$ in order to calculate its share, since the interpolation in $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ processing didn't happen. This is the reason behind the interpolation step in processing a $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ message.

An important note is that a node will only process the first $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$, $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ and $\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\backslash mathbf\{share\}$ messages it received from a specific node $P_{i}P\_i$ during a session $(P_d,\tau )(P\_d,\; \backslash tau)$. This is to make sure that:

• nodes' $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ and $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ counters cannot be manipulated by an adversary by repeating messages
• any recovery messages in circulation will not modify the systems state (this will become clear in the recovery subsection below)

Reconstruction

Let's first explain how the shares relate to the secret. The share of $P_{i}P\_i$ is $s_i={\bar{a}}_i(0)={\bar{a}}_0(i)s\_i\; =\; \backslash bar\{a\}\_i(0)\; =\; \backslash bar\{a\}\_0(i)$, which means that given $t+1t+1$ shares we can interpolate ${\bar{a}}_0(x)=\varphi (0,x)\backslash bar\{a\}\_0(x)\; =\; \backslash phi(0,x)$. We can then evaluate this polynomial to $00$ to get the secret $s={\bar{a}}_0(0)=\varphi (0,0)s=\backslash bar\{a\}\_0(0)=\backslash phi(0,0)$.

To reconstruct the secret, each node sends its share $s_{i}s\_i$ to all other nodes using the message $\mathbf{r}\mathbf{e}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{s}\mathbf{t}\mathbf{r}\mathbf{u}\mathbf{c}{\mathbf{t}}_{\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}}\backslash mathbf\{reconstruct\_\{share\}\}$. It also listens for $\mathbf{r}\mathbf{e}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{s}\mathbf{t}\mathbf{r}\mathbf{u}\mathbf{c}{\mathbf{t}}_{\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}}\backslash mathbf\{reconstruct\_\{share\}\}$ messages. For each received $\mathbf{r}\mathbf{e}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{s}\mathbf{t}\mathbf{r}\mathbf{u}\mathbf{c}{\mathbf{t}}_{\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}}\backslash mathbf\{reconstruct\_\{share\}\}$ from a node $P_{j}P\_j$, it will first verify $a_j(0)a\_j(0)$ against the commitment $CC$: $g^{s_i}{\displaystyle \prod _{j=0}^t(C_{j0}{)}^{m^j}}g^\{s\_i\}\; \backslash stackrel\{?\}\{=\}\; \backslash displaystyle\backslash prod\_\{j=0\}^t(C\_\{j0\})^\{m^j\}$ and if the point is verified, it will store it. When the node has collected $t+1t+1$ points, it is ready to interpolate ${\bar{a}}_0(x)\backslash bar\{a\}\_0(x)$ and then obtain the secret ${\bar{a}}_0(0)\backslash bar\{a\}\_0(0)$.

Recovery

We denote $d(\kappa )d(\backslash kappa)$ ($\kappa \backslash kappa$ is the system's security parameter) the maximum number of crashes an adversary is allowed to perform during its lifetime.

During recovery, the previously crashed node will ask the help of other nodes in replaying its previous communication. Each node keeps a record of all outgoing messages along with their intended recipients in a set $BB$, and $B_{l}B\_l$ indicates the subset of $BB$ intended for the node $P_{l}P\_l$. Additionally, each node maintains two counters $cntcnt$ and $cn{t}_{l}cnt\_l$. The former tracks the number of overall (system-wide) help requests and the latter the number of help requests sent by each node $P_{l}P\_l$.

A crashed node that just recovered will first send a $\mathbf{h}\mathbf{e}\mathbf{l}\mathbf{p}\backslash mathbf\{help\}$ message to all nodes. It will also replay messages in $BB$. When a node receives the $\mathbf{h}\mathbf{e}\mathbf{l}\mathbf{p}\backslash mathbf\{help\}$ message it will first make sure that the help limits are not exceeded: $cnt\le (t+1)d(\kappa )cnt\; \backslash le\; (t+1)d(\backslash kappa)$ and $cn{t}_l\le d(\kappa )cnt\_l\; \backslash le\; d(\backslash kappa)$ and if these checks pass, it will replay all messages in $B_{l}B\_l$, thus helping to replay the message history that is relevant to the recovered node.

With the above in mind we can see that, if recovery messages were to be processed, many, if not all, packet counters would count a recovered node twice.

HybridDKG

As with other DKG constructions, HybridDKG makes all nodes HybridVSS dealers. Each node generates a collection of shares from several HybridVSS instances and its final share will be the sum of those shares. Unlike DKGs operating in the synchronous setting, the asynchronous model introduces the requirement of agreement on at least $(t+1)(t+1)$ successful HybridVSS instances for a set of honest nodes. An additional complexity of the asynchronous setting is the the need to differentiate between crashed and slow nodes.

HybridDKG introduces a role called leader ($\mathcal{L}\backslash mathcal\{L\}$), which is responsible for making a proposal of a set of finished HybridVSS instances to be used. Since the leader might be malicious or crash, a leader-change mechanism is introduced. Nodes use timeouts to decide if a leader should be considered crashed.

HybridVSS is extended with a message, $\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{d}\backslash mathbf\{shared\}$ which is sent by every node that finishes the HybridVSS sharing phase. It carries all the $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages for the session $(P_d,\tau )(P\_d,\backslash tau)$ and signatures over them, which helps the leader to provide a validity proof of its proposal.

HybridDKG uses two phases, the optimistic and the pessimistic phase: the former is responsible for the key generation and is where crash recoveries take place; the latter is responsible for executing potential leader-change operations.

Optimistic phase

HybridVSS execution

The optimistic phase starts by each node $P_{d}P\_d$ becoming a dealer of a HybridVSS session for a secret $s_{d}s\_d$. At the end of a HybridVSS session, each node $P_{i}P\_i$ broadcasts a $(P_d,\tau ,\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{d},C_d,s_{i,d},R_d)(P\_d,\; \backslash tau,\; \backslash mathbf\{shared\},\; C\_d,\; s\_\{i,d\},\; R\_d)$ message. The set $R_{d}R\_d$ includes $n-t-fn-t-f$ signed $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages for session $(P_d,\tau )(P\_d,\backslash tau)$, $s_{i,d}s\_\{i,d\}$ is the share of node $P_{i}P\_i$ and $C_{d}C\_d$ is its commitment. All nodes collect $P_{d}P\_d$ and $R_{d}R\_d$ of received $\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{d}\backslash mathbf\{shared\}$ messages: $\widehat{Q}\stackrel{}{\leftarrow }\widehat{Q}\cup P_d\backslash hat\{Q\}\; \backslash xleftarrow\{\}\; \backslash hat\{Q\}\backslash cup\{P\_d\}$ $\widehat{R}\stackrel{}{\leftarrow }\widehat{R}\cup R_d\backslash hat\{R\}\; \backslash xleftarrow\{\}\; \backslash hat\{R\}\backslash cup\{R\_d\}$

VSS proposal

Once $\mathcal{L}\backslash mathcal\{L\}$ has processed $t+1t+1$ $\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{d}\backslash mathbf\{shared\}$ messages, it will broadcast a $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$ message, proposing the set of VSS instances that these $\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{d}\backslash mathbf\{shared\}$ messages correspond to. This message is HybridDKG specific and not to be confused with the $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$ message of HybridVSS. $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$ carries $\widehat{Q}\backslash hat\{Q\}$ which constitutes $\mathcal{L}\backslash mathcal\{L\}$'s proposal on the set of HybridVSS instances to use. It also carries $\widehat{R}\backslash hat\{R\}$ as a proof that the sessions referred by $\widehat{Q}\backslash hat\{Q\}$ are valid.

Leader-change condition

Any node, apart from $\mathcal{L}\backslash mathcal\{L\}$, that processed $t+1t+1$ $\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{d}\backslash mathbf\{shared\}$ messages will start a local timer that stops after $delay(T)delay(T)$. If a node's timer stops before the node has reached the end of the protocol, the node assumes that the leader has either crashed or is malicious and requests a leader change. A leader-change request is performed by broadcasting a $\mathbf{l}\mathbf{e}\mathbf{a}{\mathbf{d}}_{\mathbf{c}\mathbf{h}}\backslash mathbf\{lead\_\{ch\}\}$ message. We defer explaining the leader-change logic until we finish the optimistic phase.

Gossip-based validation and consensus

All nodes, apart from $\mathcal{L}\backslash mathcal\{L\}$, will start listening for $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$, $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ and $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages. Again, these messages are HybridDKG specific and not to be confused with their synonymous HybridVSS. Conceptually though, these messages serve the same purposes as in HybridVSS.

An $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ message is send upon receipt of a valid $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$. The purpose of $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ is to inform the receiver that the sender was reached by $\mathcal{L}\backslash mathcal\{L\}$ with a valid proposal. $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ carries the proposed set $\mathcal{Q}\backslash mathcal\{Q\}$.

A $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ message is send by nodes that have received enough ($\lceil \frac{n+t+1}{2}\rceil \backslash lceil\backslash frac\{n+t+1\}\{2\}\backslash rceil$) $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ messages for the same set $QQ$ or enough ($t+1t+1$) $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages for the same set $QQ$. At this point, the node knows that the protocol can finish successfully, since it knows enough participating nodes and the $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ message informs the receivers of that fact. The node will also update its $\widehat{Q}\backslash hat\{Q\}$ set to $QQ$, since at this point the set is agreed, and keep the relevant signed $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ or $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages as a proof. This update of the set serves as a note upon which VSS instances were agreed and is used during a leader change (more on that at the section explaining the pessimistic phase).

Shares construction

Finally, when a node receives enough ($n-t-fn-t-f$) $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$ messages, it can finish the sharing protocol by calculating its share: $s_i={\displaystyle \sum _{P_d\in Q}{s}_{i,d}}s\_i\; =\; \backslash displaystyle\backslash sum\_\{P\_d\; \backslash in\; Q\}s\_\{i,d\}$ and its commitment matrix, generated by the commitment matrices of each HybridVSS instance: $C=C_{p,q}={\prod }_{P_d\in Q}(C_d{)}_{p,q}C\; =\; C\_\{p,q\}\; =\; \backslash prod\_\{P\_d\; \backslash in\; Q\}(C\_d)\_\{p,q\}$

Pessimistic phase

A node enters this phase when it becomes unsatisfied with the current leader. The reasons for this dissatisfaction can be due to a time out or the receipt of an invalid message from the leader.

A predefined cyclic permutation of nodes is assumed to be agreed upfront. For simplicity, we will assume that leaders are sorted in a simple ascending order.

When entering this phase, the node will broadcast a message, called $\mathbf{l}\mathbf{e}\mathbf{a}{\mathbf{d}}_{\mathbf{c}\mathbf{h}}\backslash mathbf\{lead\_\{ch\}\}$, informing other nodes that it proposes a leader change. The messages carries the proposed leader $\bar{\mathcal{L}}\backslash mathcal\{\backslash bar\{L\}\}$ to which the nodes want to change. A dissatisfied node proposes the node that is next (in the ordering) of its current leader.

Two things need to be agreed between nodes: if the leader change is happening and, if so, which node will be the new leader.

A node that receives $t+f+1t+f+1$ $\mathbf{l}\mathbf{e}\mathbf{a}{\mathbf{d}}_{\mathbf{c}\mathbf{h}}\backslash mathbf\{lead\_\{ch\}\}$ messages will be convinced that a leader change is happening and will broadcast a $\mathbf{l}\mathbf{e}\mathbf{a}{\mathbf{d}}_{\mathbf{c}\mathbf{h}}\backslash mathbf\{lead\_\{ch\}\}$ proposing the smallest proposed leader it received. If the node receives $t+f+1t+f+1$ $\mathbf{l}\mathbf{e}\mathbf{a}{\mathbf{d}}_{\mathbf{c}\mathbf{h}}\backslash mathbf\{lead\_\{ch\}\}$ messages proposing the same leader, it will accept that leader since consensus on the leader is reached. Then, if the node is not the next leader, it will restart its counter and enter the optimistic mode.

In the case the node is the next leader, it will use the previously stored $\widehat{Q}\backslash hat\{Q\}$ set as the VSS set to use. It will broadcast a $\mathbf{s}\mathbf{e}\mathbf{n}\mathbf{d}\backslash mathbf\{send\}$ message with this set and the accompanying signed packets ($\mathbf{s}\mathbf{h}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{d}\backslash mathbf\{shared\}$, $\mathbf{e}\mathbf{c}\mathbf{h}\mathbf{o}\backslash mathbf\{echo\}$ or $\mathbf{r}\mathbf{e}\mathbf{a}\mathbf{d}\mathbf{y}\backslash mathbf\{ready\}$) as a proof and then enter the optimistic mode.

Crash recovery

For recovery of a crashed node, the exact same approach with HybridVSS is used.

Reconstruction

Reconstruction of a HybridDKG secret is performed the same way as in HybridVSS. Each node broadcasts its share and collects shares from other nodes. When a node has collected enough shares, it will interpolate the corresponding polynomial and evaluate it at $00$ to calculate the secret.

Performance

HybridVSS

Assuming no crashes and thus no recovery messages: The size of HybridVSS messages is dominated by the size of the commitment $CC$ which has $\frac{t(t+1)}{2}\backslash frac\{t(t+1)\}\{2\}$ group elements and thus the protocol's bit complexity is $\mathcal{O}(\kappa n^4)\backslash mathcal\{O\}(\backslash kappa\; n^4)$. An improvement exists that reduces the bit complexity down to $\mathcal{O}(\kappa n^3)\backslash mathcal\{O\}(\backslash kappa\; n^3)$ by using a collision-resistant hash function (AVSS, Sec. 3.4). In the following calculations, we assume that this improvement is used. The message complexity is $\mathcal{O}(n^2)\backslash mathcal\{O\}(n^2)$.

Taking into account the recovery messages, the message complexity becomes $\mathcal{O}(td{n}^2)\backslash mathcal\{O\}(tdn^2)$ and the the bit complexity $\mathcal{O}(\kappa td{n}^3)\backslash mathcal\{O\}(\kappa tdn^3)$ were $d=d(\kappa )d\; =\; d(\backslash kappa)$.

HybridDKG

With up to $nn$ VSS instances being able to complete and with no pessimistic phases taking place we have $\mathcal{O}(td{n}^3)\backslash mathcal\{O\}(tdn^3)$ message complexity and $\mathcal{O}(\kappa td{n}^4)\backslash mathcal\{O\}(\kappa tdn^4)$ bit complexity.

Counting in pessimistic phases, we have at most $\mathcal{O}(d)\backslash mathcal\{O\}(d)$ leader changing operations. Each leader change operation has $\mathcal{O}(td{n}^2)\backslash mathcal\{O\}(tdn^2)$ message and $\mathcal{O}(\kappa td{n}^3)\backslash mathcal\{O\}(\kappa tdn^3)$ bit complexity. Thus the overall overhead of the pessimistic phase is $\mathcal{O}(t{d}^2{n}^2)\backslash mathcal\{O\}(td^2n^2)$ message and $\mathcal{O}(\kappa t{d}^2{n}^3)\backslash mathcal\{O\}(\kappa td^2n^3)$ bit complexity.

Adding the pessimistic overhead to HybridDKG complexities, we end up with $\mathcal{O}(td{n}^2(n+d))\backslash mathcal\{O\}(tdn^2(n\; +\; d))$ message and $\mathcal{O}(\kappa td{n}^3(n+d))\backslash mathcal\{O\}(\kappa tdn^3(n\; +\; d))$ bit complexities.

Written by George Gkitsas, previously a zero-knowledge cryptography researcher & protocol developer at Heliax, the team building the Anoma Protocol.

If you're interested in zero-knowledge cryptography and cutting-edge cryptographic protocols engineering positions in Rust, check out the open positions at Heliax.