This is the first report prepared for Obol by Nethermind Research on cryptographic building blocks needed for Obol v2 . Stay tuned for more results that we will publish in the following weeks.
Report lead: @aragirtas
TL;DR
In this report, we propose a distributed key generation (DKG) method for Obol clusters, which provides public verification and has a reasonably low cost of onchain verification. More precisely, we propose operators to perform a VSS (Feldmanâ€™s VSS) using a onelayer recursive SNARK (Groth16) composition. Then, an aggregator (one of the operators) submits a succinct wrapper SNARK that attests to the validity of a fair DKG to a verifier smart contract.
Introduction
Distributed Key Generation (DKG) is a cryptographic process employed in secure multiparty computation, cryptographic threshold schemes, and cryptographic protocol design. The primary objective of DKG is to collaboratively generate a cryptographic key among a group of participants to ensure security and prevent any individual participant from having full knowledge or control of the key.
Most of the existing DKG protocols employ a Verifiable Secret Sharing (VSS) scheme to enable shareholders to verify their respective shares. Within Obolâ€™s existing architecture, the DKG algorithm is specified as the key generation algorithm of the FROST signature scheme [1], notable for its reliance on VSS as well. Nevertheless, a significant concern arises when adopting VSS, wherein shareholders are necessitated to place trust in other participants who do not raise complaints concerning the validity of their received shares. This stems from the inherent nature of VSS, where the sole means of verifying a share entails learning the share itself. A potential solution to this problem involves substituting the conventional VSS scheme with a Publicly Verifiable Secret Sharing (PVSS) scheme. Within PVSS schemes, the distinct advantage lies in their capability to enable any third party to verify the authenticity of all shares without accessing the actual shares, thereby affording heightened transparency to the system.
In this report, we propose a distributed key generation (DKG) method for Obol clusters in which operators perform VSS instances inside of a recursive composition of SNARKs. Then, one of the operators, called the aggregator, prove that the public keys of the validators and the partial public keys of the operators are computed correctly. Finally, the aggregator submits a wrapper SNARK to a smart contract to prove that all the proofs mentioned above are valid.
Background
In this section, we give preliminary information on the building blocks of our proposed construction, such as Feldmanâ€™s verifiable secret sharing (VSS) scheme, publicly verifiable secret sharing (PVSS) scheme, joinFeldman distributed key generation (JFDKG) protocol, Groth16 scheme, and BLS signature scheme.
Verifiable secret sharing (VSS)
Verifiable secret sharing schemes are employed to share secrets in a verifiable fashion, i.e., all shareholders can verify whether their received shares are consistent with the shared secret. Below, we give a highlevel description of Feldmanâ€™s VSS scheme [3], which follows Shamirâ€™s secret sharing scheme (SSS) [2] and has found widespread utilization in prominent DKG implementations.
Consider a group of n users. Let t be the threshold. Let \mathbb{G} be a cyclic group of prime order q, and let G be the generator of \mathbb{G}. The Feldmanâ€™s VSS scheme works as follows.
In the sharing phase, the dealer who wants to share a secret s
 Chooses a random secret polynomial f(X)=\alpha_{t1}X^{t1}+\ldots+\alpha_1X+\alpha_0 \in \mathbb{Z}_q[X], where \alpha_0 = s.
 Commits to the polynomial f(X), i.e., \text{PCOM}:=\{C_kC_k={\alpha_k} \cdot G for k=0, \ldots, t1\} and broadcasts it.
 Sends the share f(i) to ith user, for i=1,\ldots,n.
Each shareholder i, upon receiving f(i) and \text{PCOM}, verifies whether its share is valid by checking {f(i)}\cdot G = \sum\limits_{k=0}^{t1} {i^k}\cdot C_k.
Notice that since only the ith shareholder knows f(i), he is the only one who can verify the validity of f(i).
In the reconstruction phase, users interpolate at least t valid shares to recover the polynomial f(X), and f(0) yields the secret s.
Publicly verifiable secret sharing (PVSS)
A Publicly Verifiable Secret Sharing (PVSS) scheme, which Stadler introduced in [4], is a verifiable secret sharing (VSS) scheme with the property that any third party (not only the shareholders) can verify the validity of the shares delivered by the dealer.
Joint Feldman DKG (JFDKG)
JFDKG is the first DKG protocol proposed by Pedersen [5] in 1991. JFDKG is based on Feldmanâ€™s VSS [3]. The idea is as follows. Assume there is a group of n participants. Each participant i acting as a dealer in parallel chooses a secret u_i \in \Z_q, and shares it using Feldmanâ€™s VSS as described above.
Let t be the threshold. Let \mathbb{G} be a cyclic group of prime order q, and let G be the generator of \mathbb{G}.
The protocol goes as follows. Each participant i
 chooses a random secret polynomial f_i(X)=\alpha^i_{t1}X^{t1}+\ldots+\alpha^i_1X+\alpha^i_0 \in \mathbb{Z}_q[X], where \alpha^i_0 = u_i, i.e., the secret to be shared.
 commits to the polynomial f_i(X), i.e., \text{PCOM}_i:=\{C^i_kC^i_k={\alpha^i_k} \cdot G for k=0, \ldots, t1\} and broadcasts it.
 sends the share f_i(j) to jth user, for j=1,\ldots,n. (keeps f_i(i) for himself) The dealer can encrypt the shares before sending them to the participants.
Upon receiving \text{PCOM}_j and f_j(i) from participant j, participant i
 verifies its shares by checking {f_j(i)}\cdot G = \sum\limits_{k=0}^{t1} {i^k}\cdot C^j_k for j= 1, \dots, n
 computes its partial secret key sk_i = \sum\limits_{j=1}^{n} f_j(i)
Notice that the partial secret keys sk_j â€™s are toutofn secret sharings of a value sk = \sum\limits_{j=1}^{n}u_j, which is the groupâ€™s secret. Therefore, the groupâ€™s public key can be computed as pk = sk\cdot G =\sum\limits_{j=1}^{n}u_j\cdot G=\sum\limits_{j=1}^{n}C_0^j.
Groth16 scheme
Let \mathbb{G}_1 and \mathbb{G}_2 be two cyclic additive subgroups with the same prime order. Let R be a binary relation. The Groth16 [6] scheme is a noninteractive argument of knowledge which is described with four algorithms as follows:
 \textrm{Groth16.Setup}(1^{\lambda}, R)\to (\texttt{crs},\texttt{td}): The \textrm{Groth16.Setup} algorithm takes security parameter \lambda and the relation R as inputs and outputs a common reference string \texttt{crs} and a simulation trapdoor \texttt{td}.
 \textrm{Groth16.Prover}(R, \texttt{crs}, u,w)\to \pi =(A,B,C): The \textrm{Groth16.Prover} algorithm takes the relation R, common reference string \texttt{crs}, statement u and the witness w as inputs and outputs proof \pi=(A,B,C), where A, C \in \mathbb{G}_1 and B \in \mathbb{G}_2.
 \textrm{Groth16.Verifier}(R, \texttt{vk}, u, \pi)\to 0/1: The \textrm{Groth16.Verifier} algorithm takes the relation description R, the verification key \texttt{vk} (a part of the \texttt{crs}), the statement u and the proof \pi as inputs and outputs 0/1.
 \textrm{Groth16.Sim}(\texttt{td}, u)\to \pi_{sim}: The \textrm{Groth16.Sim} algorithm takes the trapdoor and the statement u as inputs and outputs a simulated proof \pi_{sim}.
BLS signature scheme
Let \mathbb{F}_r be the finite field with prime order r, \mathbb{G}_1 and \mathbb{G}_2 be two additive cyclic groups with prime order r, and \mathbb{G}_t be a multiplicative target group with the same order. Let g_1,g_2 be generators of \mathbb{G}_1,\mathbb{G}_2, respectively. A bilinear pairing is a map e:\mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_t. Let H:\{0,1\}^* \to \mathbb{G}_2 be a hash function which maps any binary string to the group \mathbb{G}_2.
BLS signature scheme consists of three algorithms, i.e., key generation, signature generation, and verification, such that:

\textrm{BLS.KeyGen}(par) \to (sk,pk): The key generation algorithm takes the public parameters par as input and outputs the key pair as follows:
 chooses a uniformly random secret key, sk \xleftarrow{\$} \mathbb{F}_r
 computes the corresponding public key pk \gets sk \cdot g_1 (Note that pk \in \mathbb{G}_1)

\textrm{BLS.Signer}(M,sk) \to \sigma : Signature generation algorithm takes the message M and the secret key sk as inputs, and outputs the signature \sigma as follows:
 computes the hash h\in \mathbb{G}_2 of the message M, i.e. h \gets H(M)
 computes the signature \sigma\in \mathbb{G}_2 on the message M, i.e. \sigma \gets sk \cdot h

\textrm{BLS.Verifier}(\sigma,M, pk) \to 1/0: Verification algorithm takes the message M, the signature \sigma and the public key pk as inputs, and outputs ``acceptâ€ť if e(pk,h)=e(g_1,\sigma), â€śrejectâ€ť otherwise.
Note that BLS signatures and the public keys can be aggregated, and the aggregated signature can be verified with the aggregated public key (if the messages are the same) as follows. Assume that we have N signers, i.e., P_1, \dots, P_N. Let pk_1, \dots, pk_N be the public keys of the signers, respectively. Verification of N signatures \sigma_1, \dots, \sigma_N (on the same message M) that is signed by P_1, \dots, P_N is done by checking e(apk,H(M))=e(g_1,\sigma), where apk =\sum\limits_{i=1}^{N}pk_i is the aggregated public key, and \sigma =\sum\limits_{i=1}^{N}\sigma_i is the aggregated signature.
Problem statement
Propose a DKG construction that uses a smart contract to publicly verify each shareâ€™s validity. At the same time, the verification should require a reasonably low gas cost.
Challenges
 Public verifiability. Our proposed solution should be publicly verifiable, meaning that all of the partial secret keys and the validator public keys that an operator generated should be able to be verified by any verifier without learning the secret keys.
 Onchain costs. Our proposed solution should have an efficient verification method so that onchain verification costs should be substantially low regardless of the number of validators that the cluster runs.
Proposed solution
In a blog post, Gailly proposed using SNARKs to have a noninteractive and publicly verifiable VSS, i.e., a PVSS. The idea is as follows. A dealer represents the VSS as an arithmetic circuit. Then, the dealer broadcasts the commitment to the secret polynomial, the proof, and encrypted shares. Any verifier must only verify this succinct proof to check whether the computation belongs to a fair sharing.
The author constructs a onelayer recursive proof composition as described below.
Each dealer generates two proofs, i.e., one proof for proving the evaluation of a secret polynomial (share generation of a VSS) and another proof for performing the following operations:
 Computing the commitment to the secret polynomial,
 Encrypting the shares under the public keys of the shareholders,
 Verifying the first proof.
Note that the verifier should verify only the second proof.
In his blog post, Gailly proposes this method for a single dealer, i.e., a single VSS. Different from the blog post of Gailly, we need
 each operator acting as a separate dealer,
 to generate recursive proofs for VSS instances in parallel,
 an aggregator
 to generate a proof for proving correct computation of the validatorsâ€™ public keys and operators partial public keys, and
 to generate a wrapper proof to attest to the validity of all proofs.
Certifying the fairness of all operatorsâ€™ VSS runs means affirming a fair DKGâ€™s validity.
Addressing the challenges

Public verifiability.
Utilizing VSS in a SNARK approach enables public verification because any verifier having the SNARK and the corresponding public data can confirm the legitimacy of the partial secret keys of the operators and the public keys of the validators that the cluster runs.

Onchain costs. Because Obol clusters may run multiple validators simultaneously, the operators should have distinct partial secret keys for each validator they run. Each operator generates a recursive Groth16 proof, verifying an inner proof that attests to the validity of multiple honest VSSs, each corresponding to a different validator. Then, the operators exchange those recursive proofs. After generating its partial secret keys and public keys, the aggregator generates another Groth16 proof to prove that the public keys are computed correctly. Finally, the aggregator verifies all these proofs in a wrapper circuit and obtains a single Groth16 proof. The aggregator submits only one proof with a set of public data to the verifier smart contract. This keeps the onchain cost low.
An estimation: k DKGs of a cluster with 4 operators cost ~269,656 gas. (Note that the cost is independent of the parameter k.)
The construction
In this section, we present our construction, which mainly follows the JFDKG protocol as described above. Each operator computes a share and a dealing (including commitments to the secret polynomials, proofs, and some public data) using a recursive SNARK and exchanges it with other operators. After verifying the dealings, each operator computes its partial secret keys, partial public keys, and the validatorsâ€™ public keys locally. Then, an aggregator (ideally the leader of the cluster) generates another SNARK to prove that the public keys are computed correctly. The aggregator generates a wrapper proof that attests to the validity of all proofs. The resulting wrapper proof and the corresponding public data are submitted to the smart contract.
Note that we do not use an encryption scheme inside the circuits. We assume that the operators exchange their shares using a TLSenabled communication channel.
Also note that for a minimized verification cost, we do not send any ciphertext or commitment to secret polynomials onchain as they increase the calldata size linearly in the number of validators to be run.
After a successful DKG, all Charon clients will output three files, i.e., a cluster_lock
file, a depositdata
file, and a validator keystore. We want operators to send the depositdata
files to the principal providers to activate the validators. Suppose the proof passes the onchain verification and the depositdata
file is valid. In that case, the principal providers submit the depositdata
file to the Beacon chain deposit contract for activating their validators.
Assumptions and setup
Let \mathcal{C} be a cluster of n operators that run k validators.
We deploy a Key Manager Contract (KMC) on L1, which
 verifies the wrapper proofs
 keeps the status of the DKG with \text{DKGStatus} which is initially set to \text{Null} and can take two states during a DKG: \text{failed}, \text{success}.
We assume operators agree on how they create and update the clusterdefinition
.
We assume that only the operators in the clusterdefinition
have access to the KMC.
We assume that the aggregator is compensated for its extra work, i.e., generating the wrapper proof and submitting it to the KMC.
Below, we give our DKG construction. The details on dealings, proofs, commitments, and shares will be described later in this report.
DKG

Each operator O_i loads its
clusterdefinition
file into its Charon client. 
DKG starts with generating the shares and proofs. Each operator O_i computes the dealing D_{i}, which includes
 an inner Groth16 proof \pi_{\text{in}}^i for proving the correct share generation
 an outer Groth16 proof \pi_{\text{out}}^i that attests to the validity of inner Groth16 proof \pi_{\text{in}}^i and correct computation of commitments to the secret polynomials,
 the commitments to the secret polynomial of operator O_i, i.e., \text{PCOM}_i.

Each operator O_i sends the corresponding shares s_j^{i,\ell}\in \mathbb{F}_r for j=1, \dots, n z = 1, \dots, n \ell=1, \dots, k to other operators, along with its dealing D_i and a signature \sigma_i on the dealing D_i within a time window \tau_D.
\tau_D is a reasonable time bound for operators to send the shares, dealings, and signatures to each other.

If the O_i could not receive shares from operator O_j, O_i publishes a complaint to other nodes that it couldnâ€™t receive shares from O_j.
 If at least t complaints about O_j are published within a time window \tau_D,
 operators update the cluster by excluding the operator O_j and adding new operators instead,
 restart from step 1 of the DKG.
 If at least t complaints about O_j are published within a time window \tau_D,

If the O_i could not receive the (D_j,\sigma_j), the O_i wants other operators to send (D_j,\sigma_j) within a time window \tau_D. If nobody has the (D_j,\sigma_j),
 they update the cluster by excluding the operator O_j and adding new operators instead,
 restart from step 1 of the DKG.

Upon receiving the shares, the dealings D_j, and the signatures \sigma_j from the operators O_j, the operator O_i checks the signatures, shares, and dealings as follows.
 verifies the signature of each operator O_j
 if a signature \sigma_j is invalid, the O_i notifies the operator O_j to send a valid signature within a time window \tau_D.
 If the operator O_j does not send a valid signature within a time window \tau_D, the O_i asks other operators to send the valid signature \sigma_j of the operator O_j (if they have) in time \tau_D. If nobody has a valid signature from O_j,
 they update the cluster by excluding the operator O_j and adding new operators instead,
 restart from step 1 of the DKG.
 If the operator O_j does not send a valid signature within a time window \tau_D, the O_i asks other operators to send the valid signature \sigma_j of the operator O_j (if they have) in time \tau_D. If nobody has a valid signature from O_j,
 if a signature \sigma_j is invalid, the O_i notifies the operator O_j to send a valid signature within a time window \tau_D.
 verifies the shares that come from O_j, and the proofs in the dealing D_j
 if any share or proof is invalid, O_i publishes a complaints about the false share or dealing. The O_i publishes the proofs and the shares that comes from O_j along with its signature \sigma_j.
 If the complaint is valid
 operators update the cluster by excluding O_j and adding new operators instead,
 restart from step 1 of the DKG.
 If the complaint is invalid
 operators update the cluster by excluding O_i and adding new operators instead,
 restart from step 1 of the DKG.
 If the complaint is valid
 if any share or proof is invalid, O_i publishes a complaints about the false share or dealing. The O_i publishes the proofs and the shares that comes from O_j along with its signature \sigma_j.
 verifies the signature of each operator O_j

After receiving and verifying the dealings, each operator O_i
 computes its partial secret keys by summing the shares s_i^{z,j} \in \mathbb{F}_r for z=1, \dots, n z = 1, \dots, n j=1, \dots, k, e.g., the partial signing key of the operator O_i for the validator j is computed as sk_{i}^{j}= \sum\limits_{z=1}^{n}s_i^{z,j}
 obtains the partial public key of the operator O_s, i.e., pk_s^j\in \mathbb{G}_1^{\text{in}}, for the validator j by computing pk_s^j = \sum\limits_{z=1}^{n} \sum\limits_{\ell=0}^{t1} {s^{\ell}}\cdot A_{\ell}^{z,j} for s=1, \dots, n z = 1, \dots, n j=1, \dots, k, where A_{\ell}^{z,j} â€™s are the commitments to the coefficients of the secret polynomials.
 obtains the public key of the validator j, i.e., pk^j\in \mathbb{G}_1^{\text{in}}, by computing pk^j= \sum\limits_{i=1}^{n} A_0^{i,j}.
 outputs

cluster_lock
file 
depositdata
file 
validator keystore
We leave the creation of the above output files out of scope.
Note that the Charon nodes generate thecluster_lock
anddepositdata
files with a joint effort, as the files include the threshold BLS signatures or BLS aggregate signatures. The Charon clients jointly perform the DKG to obtain partial secret keys for validation tasks. But, before loading the partial secret keys into the validator clients, Charon clients use the partial secret keys (the first and the last time use case outside the validator clients) to generate thecluster_lock
anddepositdata
files.


The aggregator generates a SNARK, i.e., \pi_{\text{pk}}, that proves the correct computation of the validator public keys, and partial public keys of the operators.

The aggregator generates the wrapper proof \pi_{\text{w}}, the commitments Pub_{\text{w}} and Pub_{\text{pk}}, and submits them to the KMC within a time window \tau_D along with a set of public data PD.
 If the aggregator does not send the wrapper proof for \tau_D, operators update the cluster by excluding the aggregator and adding a new operator.
 Restart from step 1 of the DKG.

When the KMC receives the wrapper proof,
 KMC verifies the wrapper proof.
 If wrapper proof is not valid,
 adds the aggregator to the â€śto be excludedâ€ť list which is initially empty,
 sets \text{DKGStatus}: \text{failed}
 If the proof is valid,
 it stores the commitment to the public keys of the validators, i.e., Pub_{\text{pk}}, to be used in the future key refreshes.
 it sets \text{DKGStatus}: \text{success}

Operators check for the \text{DKGStatus} of KMC.
 If \text{DKGStatus}: \text{failed}, they update the cluster by excluding the operators in the â€śto be excludedâ€ť list (the aggregator) and adding new operators instead, and restart from step 1 of the DKG.
 If \text{DKGStatus}: \text{success}, the
depositdata
files are sent to the principal providers.

Principal providers (internal or external)
 check the
depositdata
file whether it includes correct data, such as validatorâ€™s public key, withdrawal credentials, amount and signature.  check if Pub_{\text{w}} and Pub_{\text{pk}} are the hashes of PD and PK_{validator}, respectively.
 if both checks pass, the principal providers submit the
depositdata
file to the Beacon chain deposit contract.
 check the
Next, we describe how to compute the dealings, i.e., the shares, the partial secret keys, partial signing keys, validatorsâ€™ keys, the commitments, and the proofs.
Computing the dealings
For a cluster of n operators running k validators, each operator generates a onelayer recursive Groth16 proof that consists of inner and outer SNARKs. The final (outer) SNARK attests to the validity of k fair VSSs of a single operator. Operators exchange these final proofs along with the shares. Then, they compute their partial secret keys using the shares.
The aggregator generates a Groth16 proof that proves the correct computation of the validatorâ€™s public keys and operatorsâ€™ partial public keys.
Upon receiving all proofs from the operators, the aggregator verifies these proofs in a wrapper circuit and obtains a wrapper Groth16 proof. Finally, the aggregator submits the wrapper proof and its public inputs to the verifier smart contract.
The curves
We use 2chain of curves for generating a onelayer recursive Groth16 composition as described in [8] and this repo. In particular, we use BLS12381 as the inner curve and BW6767 as the outer curve, i.e.,

the BLS12381 curve is denoted as E_1(\mathbb{F}_q) whose scalar field is denoted as \mathbb{F}_r. The subgroups are denoted as \mathbb{G}_1^{\text{in}} and \mathbb{G}_2^{\text{in}} and the generator of \mathbb{G}_1^{\text{in}} is denoted as G_1^{\text{in}}.
Note that we will use the generator of \mathbb{G}_1^{\text{in}}, i.e., G_1^{\text{in}}, for committing the secret polynomials and computing the public keys for the threshold BLS signature scheme as specified in Beacon chain spec.

the BW6767 curve is denoted as E_2(\mathbb{F}_p) whose scalar field is denoted as \mathbb{F}_q. The subgroups are denoted as \mathbb{G}_1^{\text{out}} and \mathbb{G}_2^{\text{out}}.
For the proof for public keys, we also use E_2(\mathbb{F}_p).
For the wrapper proof, we use alt_bn128 curve, which we denote as E_3(\mathbb{F}_{\ell}). The subgroups are denoted as \mathbb{G}_1^{\text{w}} and \mathbb{G}_2^{\text{w}}.
Recursive Groth16 composition
Each operator O_i, \ i = 1, \dots, n, computes a recursive Groth16 composition as follows.
Inner SNARK:
The inner circuit is over \mathbb{F}_r. The operator O_i generates a proof \pi_{\text{in}}^i=(A_{\text{in}} ^i,B_{\text{in}} ^i,C_{\text{in}} ^i), where A_{\text{in}} ^i,C_{\text{in}} ^i\in \mathbb{G}_1^{\text{in}}, B_{\text{in}} ^i \in \mathbb{G}_2^{\text{in}}. We will use the hash H_0 : \{0,1\}^* \to \mathbb{F}_{r} for committing the public data.
 Private inputs:
 coefficients of the secret polynomials, i.e., (a_0^{i,j}, \dots, a_{t_{}1}^{i,j}) \in \mathbb{F}_r^{kt} for j=1, \dots, k, which are chosen by the prover.
 shares (s_1^{i,j}, \dots, s_{n_{}}^{i,j}) \in \mathbb{F}_r^{kn} for j=1, \dots, k, which are computed by evaluations of the secret polynomials at the indices in the public inputs.
 Public inputs:
 indices of the operators PI=\{1, \dots, n\}
 Pub_{\text{in}}^i= H_0(\{a_0^{i,j}, \dots, a_{t_{}1}^{i,j}\}_{j=1}^{k})
 Relation R_{in}:
 Assert s_{\ell}^{i,j} = \sum\limits_{z=0}^{t_{}1}a_z^{i,j} \ell^z for \ell = 1, \dots, n_{} and j=1, \dots, k.
 Assert that Pub_{\text{in}}^i= H_0(\{a_0^{i,j}, \dots, a_{t_{}1}^{i,j}\}_{j=1}^{k})
Outer SNARK:
The outer circuit is over \mathbb{F}_q. The operator O_i generates a proof \pi_{\text{out}}^i=(A_{\text{out}}^i,B_{\text{out}}^i,C_{\text{out}}^i), where A_{\text{out}}^i,C_{\text{out}}^i\in \mathbb{G}_1^{\text{out}}, B_{\text{out}}^i \in \mathbb{G}_2^{\text{out}}. We will use the hash H_1 : \{0,1\}^* \to \mathbb{F}_{q} for committing the public data. We denote the relation for the inner proof as R_{\text{in}} and the verification key for the inner proof as \texttt{vk}_{\text{in}}.

Private inputs:

coefficients of the secret polynomials, i.e., (a_0^{i,j}, \dots, a_{t_{}1}^{i,j})\in \mathbb{F}_r^{kt} for j=1, \dots, k.

commitments to coefficients of the secret polynomials, i.e., \text{PCOM}_i:=\{A_0^{i,j}, \dots, A_{t_{}1}^{i,j} \in \mathbb{G}_1^{kt}\} , where A_{\ell}^{i,j} = a_{\ell}^{i,j}\cdot G_1^{\text{in}} for j=1, \dots, k.
According to the Beacon chain spec, the public key of the BLS signature scheme is specified as an element of \mathbb{G}_1^{\text{in}}. Since we will use the commitments to compute the public keys, we use the generator of \mathbb{G}_1^{\text{in}}, i.e., G_1^{\text{in}}, for committing the secret polynomials.


Public inputs:
 indices of the operators in the cluster, i.e. PI=\{1,\dots, n_{}\}
 Pub_{\text{in}}^i= H_0(\{a_0^{i,j}, \dots, a_{t_{}1}^{i,j}\}_{j=1}^{k})
 the inner proof \pi_{\text{in}}^i=(A_{\text{in}}^i,B_{\text{in}}^i,C_{\text{in}}^i) (using the same coefficients of the secret polynomials and secret shares as above)
 Pub_{\text{out}}^i := H_1(\text{PCOM}_i)

Relation R_{\text{out}}:
 Assert Pub_{\text{in}}^i= H_0(\{a_0^{i,j}, \dots, a_{t_{}1}^{i,j}\}_{j=1}^{k})
 Assert A_\ell^{i,j}=a_\ell^{i,j}\cdot G_1^{\text{in}} for \ell = 0, \dots, t_{}1 and j=1, \dots, k.
 Assert Pub_{\text{out}}^i := H_1(\text{PCOM}_i)
 Assert \textrm{Groth16.Verifier}(R_{\text{in}}, \texttt{vk}_{\text{in}},(PI,Pub_{\text{in}}^i), \pi_{\text{in}}^{i})=1.
Each operator O_i sends (PI,Pub_{\text{in}}^i, Pub_{\text{out}}^i, \pi_{\text{in}}^i, \pi_{\text{out}}^i) to other operators.
The SNARK for proving the validity of the public keys
Assume that the operators generated their recursive proofs \pi_{out}^i, and exchanged the proofs and other public data, including PI, \pi_{\text{in}}^i,Pub_{\text{in}}^i,Pub_{\text{out}}^i,\text{PCOM}_i and the corresponding shares with each other. Operator O_i verifies the proof \pi_{out}^j for j\neq i.
 It computes its partial secret keys by summing the shares s_i^{z,j} \in \mathbb{F}_r for z=1, \dots, n z = 1, \dots, n j=1, \dots, k, e.g., the partial signing key of the operator O_i for the validator j is computed as sk_{i}^{j}= \sum\limits_{z=1}^{n}s_i^{z,j},
 It computes the set of validator public keys PK_{validator}:=\{pk^j pk^j= \sum\limits_{i=1}^{n} A_0^{i,j}, j=1,\dots,k\} using \text{PCOM}_1, \dots, \text{PCOM}_n.
 It computes the set of partial public keys PK_{partial}:=\{pk_i^jpk_i^j = \sum\limits_{z=1}^{n} \sum\limits_{\ell=0}^{t1} {i^{\ell}}\cdot A_{\ell}^{z,j}, j=1,\dots,k, \ i=1, \dots, n\} using \text{PCOM}_1, \dots, \text{PCOM}_n.
Finally, the aggregator generates a SNARK for proving that the PK_{validator} and PK_{partial} are computed correctly, and the operators know their secret keys.
The circuit:
The circuit is over \mathbb{F}_q. The aggregator generates a proof \pi_{\text{pk}}=(A_{\text{pk}},B_{\text{pk}},C_{\text{pk}}), where A_{\text{pk}},C_{\text{pk}}\in \mathbb{G}_1^{\text{out}}, B_{\text{pk}} \in \mathbb{G}_2^{\text{out}}. We will use the hash H_1 : \{0,1\}^* \to \mathbb{F}_{q} for committing the public data.

Private inputs:
 indices of the operators in the cluster, i.e. PI=\{1,\dots, n_{}\}
 \text{PCOM}:=\{\text{PCOM}_1, \dots, PCOM_n\} where \text{PCOM}_i:=\{A_0^{i,j}, \dots, A_{t_{}1}^{i,j} 1\leq j\leq k\} for i=1, \dots, n,
 PK_{partial}:=\{pk_i^j\in \mathbb{G}^{\text{in}}_1\} is the set of partial public keys for i=1, \dots, n and j = 1, \dots, k,
 PK_{validator}:=\{pk^1, \dots, pk^k \in \mathbb{G}^{\text{in}}_1\} is the set of validatorsâ€™ public keys,

Public inputs:

a commitment to the public keys, i.e., Pub_{\text{pk}} = H_1(PK_{validator}),

a commitment to the \text{PCOM}, i.e., Pub_{\text{com}} := H_1(\text{PCOM})

the lock hash, i.e., \text{LH}, of the
cluster_lock
file 
the signature aggregate, i.e., \text{SA}, of the
cluster_lock
fileNote that any verifier should check offchain Pub_{\text{pk}} actually corresponds to the public keys. Also, note that public keys can be given to the circuit as part of the public inputs, but this approach is more expensive.


Relation R_{\text{pk}}:

Assert that Pub_{\text{pk}} = H_1(PK_{validator})

Assert that Pub_{\text{com}} := H_1(\text{PCOM})

Assert that pk^j= \sum\limits_{i=1}^{n} A_0^{i,j} for j = 1, \dots, k,

Assert that pk^j = \sum\limits_{i=1}^{n} {\lambda_i}\cdot pk_i^j for j = 1, \dots, k, where \lambda_i is the appropriate Lagrange coefficient with respect to the operator O_i.

Assert \textrm{BLS.Verifier}(\text{SA}, \text{LH}, apk)=1, where apk := \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{k} pk_i^j.
The above assertion (BLS verification) guarantees that each operator has correct partial secret keys for all validators.

Wrapper circuit
Below, we define the wrapper circuit. We will use a SNARKfriendly hash functions H_1 : \{0,1\}^* \to \mathbb{F}_{q} and H_2 : \{0,1\}^* \to \mathbb{F}_{\ell} for committing to the private inputs. The wrapper circuit is over \mathbb{F}_{\ell}. The aggregator generates a wrapper proof \pi_w=(A_{\text{w}},B_{\text{w}},C_{\text{w}}), where A_{\text{w}},C_{\text{w}}\in \mathbb{G}_1^{\text{w}}, B_{\text{w}} \in \mathbb{G}_2^{\text{w}}. We denote the relations and verification keys for the outer SNARKs and the SNARKs for public keys as (R_{\text{out}},\texttt{vk}_{\text{out}}) and (R_{{\text{pk}}},\texttt{vk}_{{\text{pk}}}), respectively.

Private inputs:

\text{PCOM}:=\{\text{PCOM}_1, \dots, PCOM_n\}

PK_{validator}:=\{pk^1, \dots, pk^k \in \mathbb{G}^{\text{in}}_1\}

PD that includes
 indices of the operators in the cluster, i.e., PI=\{1,\dots, n_{}\}.
 Pub_{\text{in}}^i for i=1,\dots,n.
 Pub_{\text{out}}^i for i=1,\dots,n.
 the inner proof \pi_{\text{in}}^i for i=1,\dots,n.
 the outer proof \pi_{\text{out}}^i for i=1,\dots,n.
 the proof for public keys \pi_{\text{pk}}
 a commitment to \text{PCOM}:=\{\text{PCOM}_1, \dots, PCOM_n\}, i.e., Pub_{\text{com}} := H_1(\text{PCOM})
 the \text{LH} of the
cluster_lock
file  the \text{SA} of the
cluster_lock
file


Public inputs:

a commitment to the private inputs, i.e., Pub_{\text{w}} = H_2(PD).

a commitment to the public keys, i.e., Pub_{\text{pk}} = H_1(PK_{validator}).
We make the PD public so that the verifiers can check the validity of Pub_{\text{w}} = H_2(PD). And it should also verify Pub_{\text{pk}} = H_1(PK_{validator}). For example, an external principal provider can verify Pub_{\text{pk}} = H_1(PK_{validator}) by checking the
depositdata
files of the cluster.


Relation R_{w}:

Assert that Pub_{\text{out}}^i=H_1(\text{PCOM}_i) for i=1, \dots, n.
This is already asserted in the outer circuit. But, we need to be sure that \text{PCOM}_i is a part of \text{PCOM}.

Assert that Pub_{\text{pk}} = H_1(PK_{validator})

Assert that \textrm{Groth16.Verifier}(R_{\text{out}}, \texttt{vk}_{\text{out}}, (PI, Pub_{\text{in}}^i,\pi_{\text{in}}^i, Pub_{\text{out}}^i), \pi^i_{\text{out}})=1 for i=1, \dots, n.
We assert that the recursive SNARKs of the operators are valid, i.e., the operator O_i correctly evaluated a polynomial whose commitment is \text{PCOM}_i.

Assert that \textrm{Groth16.Verifier}(R_{\text{pk}}, \texttt{vk}_{\text{pk}}, (Pub_{\text{pk}},Pub_{\text{com}},\text{LH},\text{SA}), \pi_{\text{pk}})=1.
We assert that the SNARK for public keys is valid, i.e., public keys whose hash is Pub_{\text{pk}} are computed correctly according to the commitments \text{PCOM} whose hash is Pub_{\text{com}}, and the lock hash is signed by the correct partial secret keys of all operators.

Upon obtaining the wrapper proof \pi_{\text{w}}, the aggregator submits \pi_{\text{w}}, Pub_{\text{w}} and Pub_{\text{pk}} along with the public data PD to the verifier smart contract.
To have an efficient onchain verification, for the wrapper SNARK, we use the alt_bn128 curve, which we denote as E_3(\mathbb{F}_{\ell}). The recursive proofs and the proofs for public keys consist of the elements of \mathbb{G}_1^{\text{out}} and \mathbb{G}_2^{\text{out}} whose characteristic is p, and the wrapper circuit is over a field with characteristic {\ell}, where p\neq \ell. Therefore, in the wrapper circuit, the aggregator needs to do nonnative arithmetic operations that increase the prover (offchain) complexity. However, since we use the alt_bn128 curve with a precompile, the verifierâ€™s (onchain) complexity is substantially lower.
Gas estimation
The table below gives a rough gas estimation for submitting an verifying the wrapper proof.
Data  # tuples  size (bytes)  For n=4 

PI  n  n  4 
Pub_{\text{in}}^i  n  32n  128 
Pub_{\text{out}}^i  n  48n  192 
\pi_{\text{in}}^i  n  192n  768 
\pi_{\text{out}}^i  n  288n  1,152 
\pi_{\text{pk}}  1  288  288 
Pub_{\text{pk}}  1  48  48 
Pub_{\text{com}}  1  48  48 
\text{LH}  1  32  32 
\text{SA}  1  96  96 
Pub_{\text{w}}  1  32  32 
\pi_{\text{w}}  1  128  128 
TOTAL bytes  561 n + 672  2,916 bytes  
(16 gas per byte of calldata)  8,976 n + 10,752 gas  46,656 gas  
Storage (Pub_{\text{pk}})  40,000 gas  40,000 gas  
Tx cost  21,000 gas  21,000 gas  
Verification cost (3 pairings + 2 exponentiation)  162,000 gas  162,000 gas  
TOTAL gas cost (Calldata + Tx + Verification)  ~ 8,976 n + 233,752 gas  ~ 269,656 gas (\approx 9.7 USD) (assuming 20 gwei per gas) 
 PI has the indices, and we assumed each index can be represented by 1 byte,
 Pub_{\text{in}}^i is an \mathbb{F}_r element, i.e., 255 bits = 32 bytes, (Note that r is 255bit prime, source)
 Pub_{\text{out}}^i is an \mathbb{F}_q element, i.e., 381 bits = 48 bytes, (Note that q is 381bit prime, source)
 \pi_{\text{in}}^i includes 2 elements from \mathbb{G}_1^{\text{in}} and 1 element from \mathbb{G}_2^{\text{in}}, i.e. 48+48+96 = 192 bytes, (Note that q is 381bit prime, source)
 \pi_{\text{out}}^i includes 2 elements from \mathbb{G}_1^{\text{out}} and 1 element from \mathbb{G}_2^{\text{out}}, i.e. 96+96+96 = 288 bytes, (Note that p is 767bit prime, source)
 \pi_{\text{pk}}^i includes 2 elements from \mathbb{G}_1^{\text{out}} and 1 element from \mathbb{G}_2^{\text{out}}, i.e. 96+96+96 = 288 bytes, (Note that p is 767bit prime, source)
 Pub_{\text{pk}} and Pub_{\text{com}} are \mathbb{F}_q elements, i.e. 381 bits = 48 bytes, (Note that q is 381bit prime, source)
 Pub_{\text{w}} is an \mathbb{F}_{\ell} element, i.e. 255 bits = 32 bytes, (Note that \ell is 255bit prime, source)
 \text{LH} is the hash of the
cluster_lock
file which is 32 bytes.  \text{SA} is an aggregate BLS signature which is 96 bytes according the Beacon chain spec.
 \pi_{\text{w}} includes 2 elements from \mathbb{G}_1^{\text{w}} and 1 element from \mathbb{G}_2^{w}, i.e. 32+32+64 = 128 bytes, (Note that p is 255bit prime, source)
Todoâ€™s and open questions
 How do we compensate the aggregator for its extra work?
 How do we compensate the aggregatorâ€™s effort if the principal provider does not activate the validator?
References
 Komlo, C., Goldberg, I. (2021). In: Dunkelman, O., Jacobson, Jr., M.J., Oâ€™Flynn, C. (eds) Selected Areas in Cryptography. SAC 2020. Lecture Notes in Computer Science(), vol 12804. Springer, Cham. https://doi.org/10.1007/9783030816520_2
 Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612â€“613. https://doi.org/10.1145/359168.359176
 P. Feldman, â€śA practical scheme for noninteractive verifiable secret sharing,â€ť 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA, 1987, pp. 427438, doi: 10.1109/SFCS.1987.4.
 Stadler, M. : Publicly Verifiable Secret Sharing, Proc. of Eurocryptâ€™96, LNCS 1070, Springer, pp.190199 (1996) https://link.springer.com/content/pdf/10.1007/3540683399_17.pdf
 Pedersen, T.P. (1991). A Threshold Cryptosystem without a Trusted Party. In: Davies, D.W. (eds) Advances in Cryptology â€” EUROCRYPT â€™91. EUROCRYPT 1991. Lecture Notes in Computer Science, vol 547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3540464166_47
 Groth, J. (2016). On the Size of PairingBased Noninteractive Arguments. In: Fischlin, M., Coron, JS. (eds) Advances in Cryptology â€“ EUROCRYPT 2016. EUROCRYPT 2016. Lecture Notes in Computer Science(), vol 9666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/9783662498965_11
 Nicolas Gailly (Cryptonet), A deep dive into DKG, chain of SNARKs, and arkworks, 2022. (Protocol Labs Research)
 El Housni, Y., Guillevic, A. (2022). Families of SNARKFriendly 2Chains of Elliptic Curves. In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology â€“ EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13276. Springer, Cham. https://doi.org/10.1007/9783031070853_13
 https://github.com/nikkolasg/arkdkg
 https://ethresear.ch/t/bw6overbls12381/10321
 https://ethereum.org/en/developers/docs/evm/opcodes/
 https://eips.ethereum.org/EIPS/eip196
 https://eips.ethereum.org/EIPS/eip197
 https://eips.ethereum.org/EIPS/eip1108
 https://hackmd.io/@benjaminion/bls12381
 https://hackmd.io/@gnark/bw6_bls12381
 https://github.com/yelhousni/gnarkcrypto