Proposal: Key Refresh Scheme for DV operators

đź’ˇ Obol Protocol
1

Report lead: @aragirtas

Today, we publish a second report from the Obol and Nethermind Research collaboration. This time, we cover another important topic – key refreshing. Key refreshing allows the operators in a DV cluster to update their partial secret keys, while preserving the validator’s secret and public keys. We propose to use a Groth16 proof composition method (see below). An aggregator (one of the operators) generates a succinct wrapper SNARK that attests to the validity of a fair key refresh, and submits a commitment to the proof of a fair key refresh to a smart contract. If there are no whistleblower complaints about the proof for some time, the cluster starts using the fresh keys. If a whistleblower sends a fraud proof (see below) to the smart contract regarding what the aggregator submitted, the smart contract verifies the fraud proof and approves or declines the key refresh.

Resharing is a process that involves the redistribution or reassignment of cryptographic keys, secret shares, or other sensitive cryptographic materials in a manner that maintains the security and integrity of the cryptographic system. This concept is particularly relevant in scenarios where the distribution of cryptographic secrets needs to be modified among various parties or entities.

We are interested in resharing because of two reasons. Firstly, the operators in a cluster may change over time. Hence, we need to enable the current operators to provide partial keys to the incoming operators. This allows for smooth cluster transitions and continuity in the validation process. Secondly, resharing is valuable for proactive security measures. Operators in a cluster may periodically refresh their partial keys to prevent the gradual accumulation of (potentially) leaked partial keys over time.

Problem statement

Propose a key refresh scheme that allows operators within DV clusters to update their partial keys regularly. This approach should be publicly verifiable, and it should ensure that even in cases of collusion among excluded operators, they cannot reconstruct the validators’ secret keys.

Full resharing keeping the public key (FRKP)

In the this section, we describe the full resharing keeping the public key (FRKP) method, which keeps the public key while renewing the shares of all participants by re-executing the DKG process with minor modifications. After describing the method, we will give an example of a cluster performing a DKG and then a resharing.

Starting point. What do we have?

Assume we have a DV cluster with n operators. Each operator obtains a partial secret key participating in a DKG using a (t, n) verifiable secret-sharing scheme. The partial secret keys are sk_1, \dots, sk_n, which are the (t,n) Shamir secret sharing of the secret sk.

What do we want to have?

Assume we wish to have a cluster with (t',n') structure, where operators have fresh partial secret keys sk'_1, \dots, sk'_{n'} of the same DV secret key sk. (keeping the DV’s public key the same)

:bulb: Throughout this report, we will call the operators that are still active and hold a partial secret key from the previous key refresh (or initial DKG) old operators.

How?

We employ the FRKP method, which we describe as follows. It is similar to DKG, but unlike DKG, in the FRKP method, only the old operators generates sub-shares, with a crucial difference that the shared secrets are their existing partial secret keys.

  • Each old operator O_i creates (t', n') sub-shares of its current partial key sk_i,
    • O_i randomly chooses a secret polynomial f_i(X) of degree t'-1 over \mathbb{F}_q, where f_i(0)=sk_i.
    • distributes the sub-shares s_{i,j}=f_i(j) to the corresponding operators O_j for j\in\{1,\dots,n'\}.
  • When the operator O_j receives sub-shares from at least t old operators, it obtains its fresh partial secret key sk'_j by interpolating t sub-shares it received, i.e., sk_j'=\sum_{i\in \mathcal{S}} \lambda_{i}s_{i,j}, where \lambda_i is the appropriate Lagrange coefficient with respect to the old operator O_i and \mathcal{S} is a set of at least t old operators.

Remark. Notice that the fresh partial secret keys sk'_1, \dots, sk'_{n'} are (t',n') Shamir secret sharing of the same secret sk. Also, note that the fresh partial secret keys (sk'_1, \dots, sk'_{n'}) cannot be combined with old partial secret keys (sk_1, \dots, sk_n) to reconstruct the secret key sk of the DV.

Below, we give an example to show how operators in a cluster perform a DKG, obtain their partial secret keys and how they can refresh their partial secret keys, keeping the public key the same in the case that cluster mutates.

Example.

In the following example (see the figure below), we have a cluster with structure (3,4), meaning that there are 4 operators in the cluster, and the threshold is 3. Each operator participates in a DKG protocol and obtains its partial secret key. Then, the 3-rd operator is exited (or excluded) from the cluster. The cluster decides to transition to a (4,5) structure and adds two new operators, i.e., operators 3 and 5. The old operators 1, 2, and 4 share their existing partial secret keys using a (4,5)-secret sharing scheme. Upon receiving those sub-shares, all operators compute their fresh partial secret keys using the received sub-shares.

Untitled
Untitled1950Ă—1450 306 KB

Challenges

Challenge 1. Accumulation of the shares of excluded operators

A potential threat may arise when an excluded operator or an external party collects the partial keys of operators who are not part of the cluster anymore (and have nothing at stake). Also, malicious operators in the cluster may collude with the previously exited (or excluded) operators. We need a mechanism to avoid this potential threat.

Solution to Challenge 1

:bulb: Recall that there can be at most f_i < \frac{n_i}{3} malicious operators in a cluster, and the threshold should satisfy t_i\geq\frac{2n_i}{3}, where n_i is the number of operators in the cluster state S_i.

To avoid the partial keys accumulated by a possible malicious party, we cannot allow more than t_i-f_i -1 operators from the same cluster state S_i to leave. In other words, it should not be possible for the (t_i-f_i)-th operator from S_i to leave, or for the cluster to exclude it. Instead, the cluster should initiate the withdrawal process to exit the validators that the cluster runs. Indeed, suppose we let the (t_i-f_i)-th operator exit. In that case, it may be possible for f_i malicious and active operators from S_i to collude with (t_i-f_i) excluded operators from S_i. They can reconstruct the validators’ secret key because the number of colluding operators from S_i will be t_i-f_i + f_i = t_i, which is the threshold of the cluster state S_i.

For example, assume that the initial state of a cluster consists of 4 operators (as in the figure below) with threshold 3. By assumption, there is only one malicious operator, say operator 1 (red). Suppose that the cluster state S_1 mutates by excluding operator 4 (green) and adding new operators (blue) 4, 5, and 6. Let’s assume that the threshold for S_2 is t_2=4. Suppose, after a while, the second cluster state S_2 mutates again by excluding operator 3 (green) and adding a new operator 3 (grey) instead. The number of operators and the threshold in the current state S_3 stays the same, 6 and 4 respectively.

Notice that the excluded operators 3 (green) and 4 (green) from state S_1 can collude with the active and malicious operator 1 (red), also from state S_1. These colluding operators have 3 partial secret keys from S_1 in total, and this suffices to reconstruct the validators’ secret keys because the threshold in S_1 was 3.

Untitled 1
Untitled 11708Ă—1354 255 KB

:warning: Notice that these colluding operators may seem harmless if we only check the current cluster state S_3 or the previous one because the threshold in these states is 4.

Therefore, after each key refresh, all old operators must delete their old partial secret keys. Moreover, before the operators in the cluster exclude an operator, they must guarantee that the number of excluded operators in any cluster state S_i is at most (t_i-f_i-1) for all i.

Challenge 2. DoS attacks

Given that the distributed validator clusters are relatively small, in a synchronous protocol, a malicious actor can disrupt the operators and prevent them from carrying out their validator duties through a Denial of Service (DoS) attack. We need a design to mitigate the feasibility of DoS attacks.

Solution to Challenge 2

Since the size of the clusters is not too big, a malicious party can DoS the operators and disable them to perform validation duties if we assume synchronous communication model. The asynchronous communication model solves this problem. We could use asynchronous proactive secret-sharing schemes for key refresh. However, in that case public verifiability cannot be achieved.
On the other hand, since we need a periodical key refresh, we still need a time-bound after which the fresh partial keys will be used. Therefore, we propose to set the time bounds large enough to make DoS very costly, and small enough to guarantee proactive security.

Challenge 3. Public verifiability vs on-chain costs

To ensure the transparency of resharing transactions accessible to the public, we want public verifiability of the refreshing procedure. At the same time, we should minimize the gas cost.

Solution to Challenge 3

Each operator generates a Groth16 proof composition, verifying a proof that attests to the validity of multiple honest resharing, each corresponding to a different validator and different versions of cluster_lock and validator_keystore files. Then, the operators exchange those Groth16 proof compositions.

After generating its fresh partial secret keys and fresh partial public keys, the aggregator generates another Groth16 proof to prove that the fresh partial 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 smart contract. We follow an optimistic approach in which the smart contract does not verify the wrapper proof. It only stores a commitment to the wrapper proof and the corresponding public data. The smart contract makes computations only if a whistleblower claims that the wrapper proof is invalid. This keeps the on-chain cost low. (See the gas estimation below).

Proposed solution

Computing the dealings

Each old operator generates sub-shares and resharing dealings as described in the Publicly Verifiable Secret Sharing proposal. To make the shares publicly verifiable, we follow the same idea of using SNARKs. Although the generation of the proofs is very similar, some crucial points need to be emphasized:

  1. In the key refresh, only the old operators generate sub-shares and the corresponding proofs.
  2. The constant terms of the secret polynomials of the old operators have to be their existing partial secret keys.
  3. The size of the public data that will be published is linear in the threshold t, unlike the PVSS-based DKG.

The detailed description of the curves and the proofs are given in Appendices C-F below.

Next, we introduce our construction.

The construction

In this section, we present our construction, which mainly follows our Publicly Verifiable Secret Sharing proposal. Each old operator computes the sub-shares and a resharing dealing (including commitments to the secret polynomials, proofs, and some public data) using a Groth16 proof composition and exchanges it with other operators. After verifying the resharing dealings, each operator participates in a consensus for determining the set of t resharing dealings. Then, each operator computes its fresh partial secret keys and all fresh partial public keys locally.

After generating their fresh partial secret keys, the operators jointly generate cluster_lock and validator_keystore files. (Or multiple versions of these files if the cluster agrees to do so)

Then, an aggregator (ideally the leader of the cluster) generates another SNARK to prove that the fresh partial 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 using a Blob transaction as described in the EIP-4844.

If no whistleblower raises a complaint about the validity of the wrapper proof, the operators participate in a consensus to determine when to use the fresh partial secret keys. Otherwise, if a whistleblower submits valid fraud proof (see below), the key refresh protocol is labeled as failed by the smart contract.

Untitled 2
Untitled 21472Ă—1238 127 KB

Assumptions and setup

Let S_{i} be a state of a cluster with n operators that run k validators with a threshold t. We will perform a key refresh for a transition to the new state S_{i+1} with n' operators that run k validators with a threshold t'. As a result, the operators in the new cluster state will obtain v verisons of cluster_lock and validator_keystore files.

We deploy a Key Manager Contract (KMC), which

  • keeps a “to be excluded” list, which is initially empty,
  • keeps the status of the resharing with \text{ResharingStatus} which is initially set to \text{Null} and can take two states during a key refresh: \text{failed}, \text{success},
  • keeps the \text{EndAccusation}, which is the block height that shows the end of accusation period,
  • stores Com_{\text{w}}, i.e., the versioned hash of the key refresh data that is included in the Blob transaction,
  • accepts bond from whistleblowers,
  • verifies fraud proofs provided by a whistleblower.

We assume the EIP-4844: Shard Blob Transactions.

We assume operators agree on a way that they update the cluster-definition.

We assume that operators have a withdrawal process, and we leave it out of scope.

We assume a secure and authenticated communication channel.

We denote the number of operators, the threshold, and the maximum number of malicious operators in the state S_c as n_c,t_c, and f_c, respectively. Note that there can be at most f_c < \frac{n_c}{3} malicious operators in a cluster, and the threshold should satisfy t_c\geq\frac{2n_c}{3}, where n_i is the number of operators in the cluster state S_c.

Each operator maintains the list of excluded operators, i.e., \textrm{ExcludedOperators}, and the list of the number of excluded operators that participated in each cluster state, i.e., \textrm{NumberOfExOps}, in their Charon clients locally.

Sub-procedure for checking the number of excluded operators

Each operator in a cluster state maintains a list of excluded operators for all cluster states in its Charon clients and checks the number of excluded operators before excluding an operator. More precisely, the operators maintains two lists, i.e.,

  • a list \textrm{ExcludedOperators} of tuples (j, \textrm{Start}_j, \textrm{End}_j) for the excluded operators, where j denotes the excluded operator $O_j$’s id, \textrm{Start}_j and \textrm{End}_j denote the first, and the last cluster states that the operator O_j participated in, and
  • a list \textrm{NumberOfExOps} of the values \textrm{NumEx}_i (initially zero), i.e., number of excluded operators which were active during the state S_i.

Using these list, operators count the number of operators excluded from the cluster states. The logic is as follows. Let N be the index of the current cluster state S_N. Before excluding an operator, e.g., O_j, each operator proceeds as follows.

\textrm{CheckNumExOps}(O_j):

  1. Append (j, \textrm{Start}_j, \textrm{End}_j) to the list \textrm{ExcludedOperators}.
  2. FOR i=0 TO N DO:
    1. IF \textrm{Start}_j \leq i \leq \textrm{End}_j

      1. \textrm{NumEx}_i = \textrm{NumEx}_i+1

      2. IF \textrm{NumEx}_i \geq t_i-f_i
        RETURN (i, \textrm{NumEx}_i)

      3. END IF

    2. END IF
  3. END FOR
  4. RETURN ”Safe”

When the cluster is about to decide to exclude an operator or an operator wants to exit, each operator in the current cluster state performs the above check. If the logic returns (i, \textrm{NumEx}_i) for some i\leq N, the cluster withdraws the validators it runs. Otherwise, the cluster can exclude the operator. Below, we define this sub-procedure that we are going to use in our key refresh scheme construction.

\textrm{check\_number\_of\_exited\_operators}\ (O_j)

  1. If \textrm{CheckNumExOps}(O_j) = (i, \textrm{NumEx}_i) for some i\leq N, the operators proceed with the withdrawal process.
  2. If \textrm{CheckNumExOps}(O_j) = \text{Safe}, the operators update the cluster by excluding the old operator O_j and adding new operators instead.
  3. The operators restart from step 1 of the key refresh.

Key refresh scheme

  1. Each old operator checks whether the current cluster-definition has at least n_c-(t_c-f_c-1) node operators from the state S_c for all c. If not, they proceed with the withdrawal process to exit the validators that are being run by the cluster.

  2. Key refresh protocol starts with generating the sub-shares and proofs. Each old operator O_i computes the resharing dealing RD_{i}, which includes

    1. an inner Groth16 proof \pi_{\text{in}}^i for proving the correct sub-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 the old operator O_i, i.e., \text{PCOM}_i,
      as described in Appendix D.

  3. Each old operator O_i sends sub-share s_{\ell}^{i,j,b}\in \mathbb{F}_r for $\ell=1, \dots, n’$$z = 1, \dots, n$$j=1, \dots, k$ and b=1, \dots, v, to operator O_j, along with its resharing dealing RD_i and a signature \sigma_i on the resharing dealing RD_i within a time window \tau_D.

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

  4. If an operator has not received sub-shares from the old operator O_j, it publishes a complaint among other operators in the cluster that it couldn’t receive sub-shares from O_j.

    1. If at least t complaints about O_j are published within a time window \tau_D, the operators run the sub-procedure on input O_j, i.e., \textrm{check\_number\_of\_exited\_operators}\ (O_j).

  5. If an operator has not received (RD_j,\sigma_j), it asks other operators to send (RD_j,\sigma_j) within a time window \tau_D.

    1. If nobody has the (RD_j,\sigma_j), the operators run the sub-procedure on input O_j, i.e., \textrm{check\_number\_of\_exited\_operators}\ (O_j).

  6. Upon receiving the sub-shares, the resharing dealings RD_j, and the signatures \sigma_j from the old operators O_j, the operator O_i checks the signatures, resharing dealings and sub-shares as follows.

    1. Each operator O_i verifies the signature of each old operator O_j
      1. if a signature \sigma_j is invalid, the O_i notifies the operator O_j to send a valid signature in time \tau_D.
        1. If the old operator O_j does not send a valid signature within a time window \tau_D, O_i asks other operators to send the valid signature \sigma_j of the operator O_j within a time window \tau_D (if they have it).
          1. If nobody has a valid signature from O_j, the operators run the sub-procedure on input O_j, i.e., \textrm{check\_number\_of\_exited\_operators}\ (O_j).
    2. Each operator O_i verifies the sub-shares that come from O_j, and the proofs in the resharing dealing RD_j
      1. If any sub-share or proof is invalid, O_i publishes a complaint about the invalid sub-share or dealing. O_i publishes the proofs and the sub-shares that came from O_j along with its signature \sigma_j.
        1. If the complaint is valid, the operators run the sub-procedure on input O_j, i.e., \textrm{check\_number\_of\_exited\_operators}\ (O_j).
        2. If the complaint is invalid, the operators run the sub-procedure on input O_i, i.e., \textrm{check\_number\_of\_exited\_operators}\ (O_i).

  7. Operators participate in a consensus on t valid resharing dealings, i.e., \mathcal{S}:= \{RD_{i_1}, \dots, RD_{i_t}\} that they received.

  8. After reaching consensus on the set \mathcal{S}, each operator O_i

    1. computes its fresh partial secret keys by performing Lagrange interpolation with the sub-shares that came from the owners of the resharing dealings in the set \mathcal{S}, i.e., s_i^{z,j,b} \in \mathbb{F}_r for $z \in \mathcal{S}$$z = 1, \dots, n$$j=1, \dots, k$, and b=1, \dots, v.

      The fresh partial signing key sk_{i}'^{j,b} of the operator O_i for the validator j for the cluster version b is computed as sk_{i}'^{j,b}= \sum\limits_{z\in \mathcal{S}} \lambda_z s_i^{z,j,b} for j=1, \dots, k and b=1, \dots, v.

    2. obtains the partial public key of the operator O_s, i.e., pk_s'^{j,b}\in \mathbb{G}_1^{\text{in}}, for the validator j for the cluster version b by computing pk_s'^{j,b} = \sum\limits_{z \in \mathcal{S}}^{} \lambda_z\cdot \left(\sum\limits_{\ell=0}^{t'-1} {s^{\ell}}\cdot A_{\ell}^{z,j,b}\right) for $s=1, \dots, n’$$z = 1, \dots, n$$j=1, \dots, k$, and b=1,\dots,v, where $A_{\ell}^{z,j,b}$’s are the commitments to the coefficients of the secret polynomials.

      :bulb: Note that the validators’ public keys, i.e., PK_{validator}:=\{pk^1, \dots, pk^k \in \mathbb{G}^{\text{in}}_1\} stay the same.

    3. outputs

      1. fresh cluster_lock_b for b=1, \dots, v.
      2. fresh validator_keystore_b for b=1, \dots, v.

      :bulb:We leave the creation of the above output files out of scope. They are generated as in DKG. Note that the Charon clients generate the fresh cluster_lock file with a joint effort, as the file includes the BLS aggregate signature of the operators.

  9. The aggregator generates a SNARK, i.e., \pi_{\text{pk}}, that proves the correct computation of the fresh partial secret keys, as described in Appendix E.

  10. The aggregator generates the wrapper proof and obtains \pi_{\text{w}}, the commitments Pub_{\text{w}} and Pub_{\text{pk}}, and a set of public data PD, as described in Appendix F].

  11. The aggregator submits the key refresh data, i.e., (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD), as blob data (as described in EIP-4844) to the KMC within a time window \tau_D.

  12. If the aggregator does not submit the key refresh data within a time window \tau_D, the operators run the sub-procedure on input “aggregator”, i.e., \textrm{check\_number\_of\_exited\_operators}\ (\text{aggregator}).

  13. Upon receiving the key refresh data, i.e., (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD), the KMC

    1. stores the versioned hash of (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD), i.e., Com_{\text{w}},
    2. sets \text{EndAccusation} to current\_slot + \tau_w.

    :bulb: \tau_w is the time window for a whistleblower to generate and send the fraud proof. It may be the same as the blob data duration.

  14. Any whistleblower can check whether the wrapper proof is valid.

  15. If the proof is invalid, a whistleblower submits a fraud proof to the KMC along with a small bond B within a time window \tau_w.

    :bulb:$B$ is a small bond to avoid malicious parties to send irrelevant data.

  16. Upon receiving the fraud proof, the KMC verifies it.

    1. If there is no bond B, the KMC rejects the fraud proof.
    2. If the fraud proof is valid, the KMC

      1. adds the aggregator to the “to be excluded” list, which is initially empty.

      2. sets \text{ResharingStatus}: \text{failed}.

      3. rewards the whistleblower.

        :bulb:We leave how to reward a whistleblower as a todo. It may possibly be rewarded by calling a function of another contract (using leftover rewards).

      4. pays back the bond B to the whistleblower.

    3. If the fraud proof is invalid, the KMC
      1. slashes the bond of the whistleblower,
      2. sets \text{ResharingStatus}: \text{success}

  17. If no whistleblower triggers the KMC within a time window \tau_w, any operator triggers the KMC. When triggered, the KMC sets the \text{ResharingStatus}: \text{success} if current\_slot > \text{EndAccusation}.

  18. Operators check the \text{ResharingStatus} of the KMC.

    1. If the operators see that \text{ResharingStatus}: \text{failed}, the operators run the sub-procedure on input “aggregator”, i.e., \textrm{check\_number\_of\_exited\_operators}(\text{aggregator}).
    2. If the operators see that \text{ResharingStatus}: \text{success}, they participate in a consensus protocol to decide when to use the fresh keys regarding each version of the cluster_lock and validator_keystore files. The result of the consensus is \tau_b for b=1,\dots,v.

  19. After the last duty before each \tau_b, for b=1,\dots,v, each operator

    1. deletes the cluster_lock_b-1 file from its Charon client.
    2. loads the cluster_lock_b file to its Charon client.
    3. deletes the validator_keystore_b-1 from its validator client
    4. loads the validator_keystore_b to its validator client

Remark. In the case of b>1, the operators should keep the unused versions of the validator_keystore file in a secure (physically separated) storage. The operators should delete their old keys from their validator clients and keep only those for the current period in their validator clients. Note that deleting the old partial secret keys is crucial because of a potential accumulation of the old partial secret keys from the same cluster state. Please see the “Solution to Challenge 1” above for a detailed explanation of this potential threat.

Next, we describe how a whistleblower generates a fraud proof.

Computing the fraud proof

When a whistleblower finds an invalid key refresh data, i.e., (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD), in the Blob Tx, it generates a fraud proof. The types of complaints that a whistleblower can raise are as follows.

  1. Type 1 claims that Pub_{\text{w}} \neq H_2(PD)
  2. Type 2 claims that Pub_{\text{pk}} \neq H_1(PK_{validator})
  3. Type 3 claims that \textrm{Groth16.Verifier}(R_{\text{w}}, \texttt{vk}_{\text{w}}, (Pub_{\text{w}}, Pub_{\text{pk}}), \pi_{\text{w}})=0

How does KMC verify the fraud proof?

When the KMC receives the fraud proof,

  1. If the complaint is valid return valid,
  2. If the complaint is not valid return invalid.

Notice that the complaint that will be verified by the KMC may be one of the three types above. The whistleblower calls one of the functions in the KMC, according to the type of complaint. These functions are as follows.

:bulb:Note that Com_{\text{w}} denotes the commitment to the key refresh data, i.e., (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD), that is stored in the storage of the KMC when the Blob Tx is received, and VH() denotes the versioned hash as described in EIP-4844.

  • verify_complaint_public_data: It takes (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD) as input, and outputs valid or invalid.
    • It checks
      • whether Com_{\text{w}} = VH(\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD) and
      • whether Pub_{\text{w}} =H_2(PD)
    • If this is not the case, return valid.
    • Otherwise, return invalid.
  • verify_complaint_public_keys: It takes (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD) as input, and outputs valid or invalid.
    • It checks
      • whether Com_{\text{w}} = VH(\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD) and
      • whether the received Pub_{\text{pk}} is identical to the Pub_{\text{pk}} stored in the storage of KMC during the DKG.
    • If this is not the case, return valid.
    • Otherwise, return invalid.
  • verify_complaint_wrapper_proof: It takes (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD) as input, and outputs valid or invalid.
    • It checks
      • whether Com_{\text{w}} = VH(\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD)
      • whether \textrm{Groth16.Verifier}(R_{\text{w}}, \texttt{vk}_{\text{w}}, (Pub_{\text{w}}, Pub_{\text{pk}}), \pi_{\text{w}}) = 1, where R_{\text{w}} and \texttt{vk}_{\text{w}} are the relation and verification key for the wrapper circuit.
    • If this is not the case, return valid.
    • Otherwise, return invalid.

Gas estimation

:warning: Disclaimer. We did gas cost estimation according to the known gas costs for submitting calldata. However, the key refresh data is submitted as Blob data. Submitting blob data requires blob gas, which, currently, cannot be translated into USD. Note that the blob gas cost of submitting Blob data would be less than estimated in this section.

The table below gives a rough gas estimation for submitting the key refresh data, i.e., (\pi_{\text{w}}, Pub_{\text{w}}, Pub_{\text{pk}}, PD), and storing the versioned hash of the key refresh data, i.e., Com_{\text{w}}.

Data # tuples Size (bytes) Example data size (in Bytes) (for n'=4, t=3, b=1) Example data size (in Bytes) (for n'=4, t=3, b=10)
PI n' n' 4 4
Pub_{\text{in}}^i t 32t 96 96
Pub_{\text{out}}^i t 48t 144 144
\pi_{\text{in}}^i t 192t 576 576
\pi_{\text{out}}^i t 288t 864 864
\pi_{\text{pk}} 1 288 288 288
Pub_{\text{pk}} 1 48 48 480
Pub_{\text{com}} 1 48 48 480
\text{LH} b 32b 32 320
\text{SA} b 96b 96 960
Pub_{\text{w}} 1 32 32 32
\pi_{\text{w}} 1 128 128 128
Com_{\text{w}} 1 32 32 32
TOTAL bytes n+ 560t + 128b + 576 2,388 bytes 3,540 bytes
(16 gas per byte of calldata) 16n+8,960t + 2,048b + 9,216 gas 38,208 gas 56,640 gas
Updating storage (Com_{\text{w}}) 5,000 gas 5,000 gas 5,000 gas
Tx cost 21,000 gas 21,000 gas 21,000 gas
TOTAL gas cost (calldata + storage + Tx) ~ 16n + 8,960t + 2,048b + 34,216 gas ~ 64,208 gas (\approx 2.32 USD (assuming 20 gwei per gas) ~ 82,640 gas (\approx 2.98 USD (assuming 20 gwei per gas)

:bulb: - 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}} 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 to 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)

  • Com_{\text{w}} is a 256-bit hash of a KZG commitment to the key refresh data, i.e., 32 bytes. (source)

Refreshing period

In the previous section we gave an estimation for submitting and storing the wrapper proof and the corresponding public data. Note that the cost that we computed needs to be paid every time the operators refreshes their partial keys. If a cluster decides to generate more than two versions of cluster_lock and validator_keystore files simultaneously, the refreshing period becomes less than 1 month if we fix the monthly cost as 1.5 USD per cluster.

:bulb: All computations are done by assuming 1 gas = 20 gwei and 1 ETH = 1,800.00 USD.

Number of versions vs refreshing period

Structure operators threshold versions cost of key refresh refreshing period monthly cost per cluster
(3,4) 4 3 1 2.275 1.517 1.5
(3,4) 4 3 2 2.349 0.783 1.5
(3,4) 4 3 3 2.423 0.538 1.5
(3,4) 4 3 4 2.497 0.416 1.5
(3,4) 4 3 5 2.57 0.343 1.5
(3,4) 4 3 10 2.939 0.196 1.5
(3,4) 4 3 20 3.676 0.123 1.5
(3,4) 4 3 50 5.888 0.079 1.5
(3,4) 4 3 100 9.575 0.064 1.5
(7,10) 10 7 1 3.569 2.379 1.5
(7,10) 10 7 2 3.643 1.214 1.5
(7,10) 10 7 3 3.717 0.826 1.5
(7,10) 10 7 4 3.79 0.632 1.5
(7,10) 10 7 5 3.864 0.515 1.5
(7,10) 10 7 10 4.233 0.282 1.5
(7,10) 10 7 20 4.97 0.166 1.5
(7,10) 10 7 50 7.182 0.096 1.5
(7,10) 10 7 100 10.868 0.072 1.5

Notice that the worst case occurs when a cluster generates a single version. To mitigate this, the cluster may run more than one validators.

In the below table, we fix the monthly cost as 1.5 USD per validator and we assume that cluster generates a single version of cluster_lock and validator_keystore files. The refresh period becomes less than 1 month if a cluster runs more then two validators.

Number of validators vs refreshing period

Structure operators threshold validators cost of key refresh refreshing period monthly cost per cluster
(3,4) 4 3 1 2.275 1.516666666667 1.5
(3,4) 4 3 2 2.275 0.758333333333 3
(3,4) 4 3 3 2.275 0.505555555556 4.5
(3,4) 4 3 4 2.275 0.379166666667 6
(3,4) 4 3 5 2.275 0.303333333333 7.5
(3,4) 4 3 10 2.275 0.151666666667 15
(3,4) 4 3 20 2.275 0.075833333333 30
(3,4) 4 3 50 2.275 0.030333333333 75
(3,4) 4 3 100 2.275 0.015166666667 150
(7,10) 10 7 1 3.569 2.379333333333 1.5
(7,10) 10 7 2 3.569 1.189666666667 3
(7,10) 10 7 3 3.569 0.793111111111 4.5
(7,10) 10 7 4 3.569 0.594833333333 6
(7,10) 10 7 5 3.569 0.475866666667 7.5
(7,10) 10 7 10 3.569 0.237933333333 15
(7,10) 10 7 20 3.569 0.118966666667 30
(7,10) 10 7 50 3.569 0.047586666667 75
(7,10) 10 7 100 3.569 0.023793333333 150

We gave the possible key refresh periods, which cost a monthly 1.5 USD per validator in the above tables. If we want to reduce the cost further, we should either generate multiple versions or run multiple validators.

The worst case scenario is that a cluster runs a single validator and generates a single versions of the cluster_lock and validator_keystore files.

  • For such a cluster of 4 operators, the refreshing period may be more than ~1,6 months to have a monthly cost of 1.5 USD.
  • For such a cluster of 10 operators, the refreshing period may be more than ~2,4 months to have a monthly cost of 1.5 USD.

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?
  3. How should we reward the whistleblower?

References

Appendices

A. 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 scheme is a non-interactive argument of knowledge which consists of four algorithms as follows:

  1. \textrm{Groth16.Setup}(1^{\lambda}, R)\to (\texttt{crs},\texttt{td}): The \textrm{Groth16.Setup} algorithm takes a security parameter \lambda and the relation R as inputs, and it 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 witness w as inputs, and it outputs a 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 it outputs 0/1 (“reject”/“accept”).
  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 it outputs a simulated proof \pi_{sim}.

B. BLS signature scheme

Let \mathbb{F}_r be the finite field with prime order r, and \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 linear in both entries, non-degenerate, and efficiently computable. Let H:\{0,1\}^* \to \mathbb{G}_2 be a hash function which maps any binary string to the group \mathbb{G}_2.

The BLS signature scheme consists of three algorithms: key generation, signature generation, and verification. These are as follows:

  • \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 1 (“accept”) if e(pk,h)=e(g_1,\sigma), 0 (“reject”) otherwise.

    :bulb: Note that BLS signatures and public keys can be aggregated, and the aggregated signature can be verified with the aggregated public key if the messages are the same. (BLS signatures on different messages can also be aggregated, but in this report, we are not interested in that case.) For instance, assume we have N signers P_1, \dots, P_N. Let pk_1, \dots, pk_N be their respective public keys. The verification of N signatures \sigma_1, \dots, \sigma_N on the same message M produced respectively 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.

C. The curves

For the Groth16 proof composition, we use a 2-chain of curves as described in [8] and this repo. More precisely, we use BLS12-381 as the inner curve and BW6-767 as the outer curve:

  • 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}_i^{\text{in}} is denoted by G_i^{\text{in}}.

    :bulb: Note that we will use the generator G_1^{\text{in}} of \mathbb{G}_1^{\text{in}} for committing to 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 SNARK for the validity of the public keys, we also use E_2(\mathbb{F}_p).

For the wrapper SNARK, we use the alt_bn128 curve, which we denote as E_3(\mathbb{F}_{\ell}). The corresponding subgroups are denoted as \mathbb{G}_1^{\text{w}} and \mathbb{G}_2^{\text{w}}.

D. Groth16 proof composition

Each old operator O_i computes a Groth16 proof composition as follows.

:warning: Note that we are performing v key refreshes at the same time, to have v versions of the partial secret keys and cluster_lock files. The superscript b denotes the version number of the variables used in the following constructions. Also note that if the cluster decides to generate only a single version, it is enough to set b=1.

Inner SNARK:

The inner circuit is over \mathbb{F}_r. The old 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 to the public data.

  • Private inputs:

    • coefficients of the secret polynomials, i.e., (a_0^{i,j,b}, \dots, a_{t'_{}-1}^{i,j,b}) \in \mathbb{F}_r^{kt'v} for j=1, \dots, k and b=1,\dots, v, which are chosen by the prover, where a_0^{i,j,b} = sk_i^j for all b=1, \dots, v.

      :warning: This is the most crucial point of resharing: the constant term of the secret polynomials should be the existing partial secret key of the old operator for the corresponding validator.

    • sub-shares (s_1^{i,j,b}, \dots, s_{n'_{}}^{i,j,b}) \in \mathbb{F}_r^{kn'v} for j=1, \dots, k and b=1, \dots, v, which are computed by evaluations of the secret polynomials at the indices in the public inputs.

  • Public inputs:
    • indices of all operators (sub-share holders), i.e., PI=\{1, \dots, n'\}
    • Pub_{\text{in}}^i= H_0((a_0^{i,j,b}, \dots, a_{t'_{}-1}^{i,j,b})_{j=1,\dots,k; \ b=1,\dots,v})
  • Relation R_{\text{in}}:
    • Assert s_{\ell}^{i,j,b} = \sum\limits_{z=0}^{t'_{}-1}a_z^{i,j,b} \ell^z for \ell = 1, \dots, n'_{}, j=1, \dots, k and b=1,\dots,v.
    • Assert that Pub_{\text{in}}^i= H_0((a_0^{i,j,b}, \dots, a_{t'_{}-1}^{i,j,b})_{j=1,\dots,k; \ b=1,\dots,v})

Outer SNARK:

The outer circuit is over \mathbb{F}_q. The old 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 to 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,b}, \dots, a_{t'_{}-1}^{i,j,b})_{j=1, \dots, k; \ b=1,\dots, v} \in \mathbb{F}_r^{kt'v}.

    • commitments to coefficients of the secret polynomials, i.e., \text{PCOM}_i:=\{(A_0^{i,j,b}, \dots, A_{t'_{}-1}^{i,j,b})_{j=1, \dots, k; \ b=1,\dots, v} \in {(\mathbb{G}_1^{\text{in}})}^{kt'v}\}, where A_{\ell}^{i,j,b} = a_{\ell}^{i,j,b}\cdot G_1^{\text{in}}.

      :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 to the secret polynomials.

  • Public inputs:

    • indices of all operators (sub-share holders), i.e., PI=\{1,\dots, n'\}
    • Pub_{\text{in}}^i= H_0((a_0^{i,j,b}, \dots, a_{t'_{}-1}^{i,j,b})_{j=1,\dots,k; \ b=1,\dots,v})
    • 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,b}, \dots, a_{t'_{}-1}^{i,j,b})_{j=1,\dots,k; \ b=1,\dots,v})
    • Assert A_\ell^{i,j,b}=a_\ell^{i,j,b}\cdot G_1^{\text{in}} for \ell = 0, \dots, t'_{}-1, j=1, \dots, k and b=1, \dots, v.
    • 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 old operator O_i obtains \pi^i_{\text{out}} and (PI, Pub_{\text{in}}^i,\pi_{\text{in}}^i, Pub_{\text{out}}^i).

E. The SNARK for proving the validity of the public keys

Only the old operators generate the Groth16 proof composition, as described in Appendix D, and send 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 sub-shares to all operators in the cluster. All operators participate in a consensus protocol to agree on a set \mathcal{S} of t old operators with valid resharing dealings.

Upon agreeing on the set \mathcal{S}, each operator O_i verifies the proof \pi_{out}^z from the old operators O_z for z\in \mathcal{S}.

  • The operator O_i computes its partial secret keys by interpolating the sub-shares s_i^{z,j,b} \in \mathbb{F}_r for $z\in \mathcal{S}$$z = 1, \dots, n$$j=1, \dots, k$ and b=1, \dots, v.

    E.g., the fresh partial secret key of the operator O_i for the validator j for the version b is computed as sk_{i}'^{j,b}= \sum\limits_{z\in \mathcal{S}}^{}\lambda_z\cdot s_i^{z,j,b}, where \lambda_z is the appropriate Lagrange coefficient.

  • The operator O_i computes the set of fresh partial public keys PK'_{partial}:=\{(pk_i'^{j,b})_{i=1, \dots, n';\ j=1,\dots,k; \ b=1, \dots, v}|pk_i'^{j,b} = \sum\limits_{z \in \mathcal{S}}^{} \lambda_z\cdot \sum\limits_{\ell=0}^{t'-1} {i^{\ell}}\cdot A_{\ell}^{z,j,b}\} using \text{PCOM}_z \ (z \in \mathcal{S}).

  • The operator O_i obtains a set of cluster_lock and validator_keystore versions, i.e., cluster_lock_b and validator_keystore_b for b=1,\dots,v.

The aggregator generates a SNARK for proving that the set PK'_{partial} of fresh partial public keys of all operators is computed correctly as follows.

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 all operators (sub-share holders), i.e., PI=\{1,\dots, n'\}

    • \text{PCOM}:=\{\text{PCOM}_i| \text{PCOM}_i:=\{(A_0^{i,j,b}, \dots, A_{t'_{}-1}^{i,j,b})_{j=1,\dots,k;\ b=1,\dots, v} \in {(\mathbb{G}_1^{\text{in}})}^{kt'v}\}, i\in \mathcal{S} \}, where \mathcal{S} is the set of indices of at least t old operators.

    • PK'_{partial}:=\{(pk_i'^{j,b}\in \mathbb{G}^{\text{in}}_1)_{i=1, \dots, n'; \ j = 1, \dots, k; \ b = 1, \dots, v}\} is the set of all fresh partial public keys.

    • PK_{validator}:=\{pk^1, \dots, pk^k \in \mathbb{G}^{\text{in}}_1\} is the set of validators’ public keys,

      :warning: Notice that PK_{validator} has never been changed since the first DKG!

  • 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 hashes of the fresh cluster_lock_b, i.e., \text{LH}_b, b=1,\dots,v.

    • the signature aggregate of the fresh cluster_lock_b, i.e., \text{SA}_b, b=1,\dots,v.

      :bulb: Note that any verifier should check that the off chain Pub_{\text{pk}} actually corresponds to the public keys stored on-chain. 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 \in \mathcal{S}}^{} \lambda_i\cdot A_0^{i,j,b} for j = 1, \dots, k and b = 1, \dots, v, where \lambda_i is the appropriate Lagrange coefficient with respect to the old operator O_i for i \in\mathcal{S}.

    • Assert that pk^j = \sum\limits_{i \in \mathcal{G}}^{} {\lambda_i}\cdot pk_i'^{j,b} for j = 1, \dots, k and b = 1, \dots, v, where \lambda_i is the appropriate Lagrange coefficient with respect to the operator O_i and \mathcal{G} is the set of indices of at least t' operators (sub-share holders).

      :warning: Notice that the sets \mathcal{S} is the set of at least t old operators whereas the set \mathcal{G} is the set of at least any t' operators (sub-share holders). The corresponding Lagrange coefficients are computed according to these sets. (See the definition)

    • Assert \textrm{BLS.Verifier}(\text{SA}_b, \text{LH}_b, apk_b)=1, where apk_b is the aggregated public key with respect to the version b, i.e., apk_b := \sum\limits_{i=1}^{n'}\sum\limits_{j=1}^{k} pk_i'^{j,b}.

      :bulb: The above assertion (verification of the aggregated BLS signature on the lock hash) guarantees that each operator has correct partial secret keys for all validators.

The aggregator obtains a Groth16 proof \pi_{\text{pk}} and (Pub_{\text{pk}},Pub_{\text{com}},\text{LH}_b,\text{SA}_b).

F. The wrapper SNARK

We will use a SNARK-friendly hash functions H_1 : \{0,1\}^* \to \mathbb{F}_{q} and Keccak256 (denoted by H_2) 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 proving the validity of the 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}_z | z \in \mathcal{S}\}
    • PK_{validator}:=\{pk^1, \dots, pk^k \in \mathbb{G}^{\text{in}}_1\}
    • PD that includes
      • indices of all operators (sub-share holders), i.e., PI=\{1,\dots, n'\}.
      • Pub_{\text{in}}^i for i\in \mathcal{S}.
      • Pub_{\text{out}}^i for i\in \mathcal{S}.
      • the inner proof \pi_{\text{in}}^i for i\in \mathcal{S}.
      • the outer proof \pi_{\text{out}}^i for i\in \mathcal{S}.
      • the proof for public keys \pi_{\text{pk}}
      • a commitment to \text{PCOM}:=\{\text{PCOM}_z | z \in \mathcal{S}\}, i.e., Pub_{\text{com}} := H_1(\text{PCOM})
      • the lock hashes of the fresh cluster_lock_b, i.e., \text{LH}_b, b=1,\dots,v.
      • the signature aggregate of the fresh cluster_lock_b, i.e., \text{SA}_b, b=1,\dots,v.

  • 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}).

  • 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\in \mathcal{S}.

      :bulb: We assert that the Groth16 proof composition of the operators are valid, i.e., the old 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}_b,\text{SA}_b), \pi_{\text{pk}})=1 for b= 1, \dots, v.

      :bulb: We assert that the SNARKs for public keys are valid, i.e., the validators’ public keys whose hash is Pub_{\text{pk}} are consistent with the commitments \text{PCOM} whose hash is Pub_{\text{com}} and the lock hash is signed by fresh partial secret keys (of all operators) whose interpolation gives the validators’ public keys.

Upon obtaining the wrapper proof \pi_{\text{w}}, the aggregator submits the key refresh data, i.e. (\pi_{\text{w}},Pub_{\text{w}},Pub_{\text{pk}},PD), as blob data in an Ethereum blob transaction (using EIP-4844).

4 Likes