Proposal: Publicly Verifiable Secret Sharing-based Distributed Key Generation

đź’ˇ Obol Protocol
1

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 on-chain verification. More precisely, we propose operators to perform a VSS (Feldman’s VSS) using a one-layer 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 multi-party 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, join-Feldman distributed key generation (JF-DKG) 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 high-level 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_{t-1}X^{t-1}+\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_k|C_k={\alpha_k} \cdot G for k=0, \ldots, t-1\} and broadcasts it.
  • Sends the share f(i) to i-th 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}^{t-1} {i^k}\cdot C_k.

:bulb: Notice that since only the i-th 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 (JF-DKG)

JF-DKG is the first DKG protocol proposed by Pedersen [5] in 1991. JF-DKG 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_{t-1}X^{t-1}+\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_k|C^i_k={\alpha^i_k} \cdot G for k=0, \ldots, t-1\} and broadcasts it.
  • sends the share f_i(j) to j-th 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}^{t-1} {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)

:bulb: Notice that the partial secret keys sk_j ’s are t-out-of-n 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 non-interactive argument of knowledge which is described with four algorithms as follows:

  1. \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}.
  2. \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.
  3. \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.
  4. \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.

    :bulb: 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

  1. 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.
  2. On-chain costs. Our proposed solution should have an efficient verification method so that on-chain 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 non-interactive 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 one-layer 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.

Untitled
Untitled568Ă—1292 57.9 KB

:bulb: 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

  1. each operator acting as a separate dealer,
    1. to generate recursive proofs for VSS instances in parallel,
  2. an aggregator
    1. to generate a proof for proving correct computation of the validators’ public keys and operators partial public keys, and
    2. 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

  1. 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.

  2. On-chain 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 on-chain cost low.

    :bulb: 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 JF-DKG 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.

Untitled 1
Untitled 11804Ă—1478 275 KB

:warning: Note that we do not use an encryption scheme inside the circuits. We assume that the operators exchange their shares using a TLS-enabled communication channel.
Also note that for a minimized verification cost, we do not send any ciphertext or commitment to secret polynomials on-chain 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 deposit-data file, and a validator keystore. We want operators to send the deposit-data files to the principal providers to activate the validators. Suppose the proof passes the on-chain verification and the deposit-data file is valid. In that case, the principal providers submit the deposit-data 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 cluster-definition.

We assume that only the operators in the cluster-definition 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

  1. Each operator O_i loads its cluster-definition file into its Charon client.

  2. DKG starts with generating the shares and proofs. Each operator O_i computes the dealing D_{i}, which includes

    1. an inner Groth16 proof \pi_{\text{in}}^i for proving the correct share generation
    2. 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,
    3. the commitments to the secret polynomial of operator O_i, i.e., \text{PCOM}_i.

  3. 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.

    :bulb: \tau_D is a reasonable time bound for operators to send the shares, dealings, and signatures to each other.

  4. 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.

    1. If at least t complaints about O_j are published within a time window \tau_D,
      1. operators update the cluster by excluding the operator O_j and adding new operators instead,
      2. restart from step 1 of the DKG.

  5. 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),

    1. they update the cluster by excluding the operator O_j and adding new operators instead,
    2. restart from step 1 of the DKG.

  6. 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.

    1. verifies the signature of each operator O_j
      1. 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.
        1. 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,
          1. they update the cluster by excluding the operator O_j and adding new operators instead,
          2. restart from step 1 of the DKG.
    2. verifies the shares that come from O_j, and the proofs in the dealing D_j
      1. 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.
        1. If the complaint is valid
          1. operators update the cluster by excluding O_j and adding new operators instead,
          2. restart from step 1 of the DKG.
        2. If the complaint is invalid
          1. operators update the cluster by excluding O_i and adding new operators instead,
          2. restart from step 1 of the DKG.

  7. After receiving and verifying the dealings, each operator O_i

    1. 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}
    2. 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}^{t-1} {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.
    3. 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}.
    4. outputs

      1. cluster_lock file

      2. deposit-data file

      3. validator keystore

        :warning: We leave the creation of the above output files out of scope.
        Note that the Charon nodes generate the cluster_lock and deposit-data 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 the cluster_lock and deposit-data files.

  8. 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.

  9. 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.

    1. 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.
    2. Restart from step 1 of the DKG.

  10. When the KMC receives the wrapper proof,

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

  11. Operators check for the \text{DKGStatus} of KMC.

    1. 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.
    2. If \text{DKGStatus}: \text{success}, the deposit-data files are sent to the principal providers.

  12. Principal providers (internal or external)

    1. check the deposit-data file whether it includes correct data, such as validator’s public key, withdrawal credentials, amount and signature.
    2. check if Pub_{\text{w}} and Pub_{\text{pk}} are the hashes of PD and PK_{validator}, respectively.
    3. if both checks pass, the principal providers submit the deposit-data file to the Beacon chain deposit contract.

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 one-layer 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 2-chain of curves for generating a one-layer recursive Groth16 composition as described in [8] and this repo. In particular, we use BLS12-381 as the inner curve and BW6-767 as the outer curve, i.e.,

  • the BLS12-381 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}}.

    :bulb: 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 BW6-767 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.

      :bulb: 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^j|pk_i^j = \sum\limits_{z=1}^{n} \sum\limits_{\ell=0}^{t-1} {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 file

      :bulb: Note 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.

      :bulb: 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 SNARK-friendly 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}).

      :bulb: 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 deposit-data files of the cluster.

  • Relation R_{w}:

    • Assert that Pub_{\text{out}}^i=H_1(\text{PCOM}_i) for i=1, \dots, n.

      :bulb: 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.

      :bulb: 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.

      :bulb: 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 on-chain 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 non-native arithmetic operations that increase the prover (off-chain) complexity. However, since we use the alt_bn128 curve with a precompile, the verifier’s (on-chain) 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 255-bit prime, source)
  • Pub_{\text{out}}^i is an \mathbb{F}_q element, i.e., 381 bits = 48 bytes, (Note that q is 381-bit 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 381-bit 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 767-bit 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 767-bit prime, source)
  • Pub_{\text{pk}} and Pub_{\text{com}} are \mathbb{F}_q elements, i.e. 381 bits = 48 bytes, (Note that q is 381-bit prime, source)
  • Pub_{\text{w}} is an \mathbb{F}_{\ell} element, i.e. 255 bits = 32 bytes, (Note that \ell is 255-bit 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 255-bit prime, source)

To-do’s and open questions

  1. How do we compensate the aggregator for its extra work?
  2. How do we compensate the aggregator’s effort if the principal provider does not activate the validator?

References

  1. 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/978-3-030-81652-0_2
  2. Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612–613. https://doi.org/10.1145/359168.359176
  3. P. Feldman, “A practical scheme for non-interactive verifiable secret sharing,” 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA, 1987, pp. 427-438, doi: 10.1109/SFCS.1987.4.
  4. Stadler, M. : Publicly Verifiable Secret Sharing, Proc. of Eurocrypt’96, LNCS 1070, Springer, pp.190-199 (1996) https://link.springer.com/content/pdf/10.1007/3-540-68339-9_17.pdf
  5. 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/3-540-46416-6_47
  6. Groth, J. (2016). On the Size of Pairing-Based Non-interactive 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/978-3-662-49896-5_11
  7. Nicolas Gailly (Cryptonet), A deep dive into DKG, chain of SNARKs, and arkworks, 2022. (Protocol Labs Research)
  8. El Housni, Y., Guillevic, A. (2022). Families of SNARK-Friendly 2-Chains 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/978-3-031-07085-3_13
  9. https://github.com/nikkolasg/ark-dkg
  10. https://ethresear.ch/t/bw6-over-bls12-381/10321
  11. https://ethereum.org/en/developers/docs/evm/opcodes/
  12. https://eips.ethereum.org/EIPS/eip-196
  13. https://eips.ethereum.org/EIPS/eip-197
  14. https://eips.ethereum.org/EIPS/eip-1108
  15. https://hackmd.io/@benjaminion/bls12-381
  16. https://hackmd.io/@gnark/bw6_bls12381
  17. https://github.com/yelhousni/gnark-crypto
4 Likes