Important Terms and Definitions
Shamir Secret Sharing
Shamir’s Secret Sharing (SSS) scheme is a polynomial threshold secret sharing scheme where the secret holder divides a secret into n multiple shares and each participant is given a share by evaluating a polynomial of order . To reconstruct the secret, shares are required.
SSS is often applied in MPC cryptography and is fundamental to Embedded Wallet’s infrastructure.
Verifiable Secret Sharing
Verifiable secret sharing (VSS) refers to a class of secret-sharing schemes—often built on top of Shamir’s Secret Sharing—that ensure a well-defined secret can be reconstructed, even if the party distributing the shares behaves maliciously.
Threshold Signature Schemes
Threshold signature schemes (TSS) refer to signing schemes that allow a qualified set of parties involved in a secret sharing scheme to generate a signature on a message without reconstructing the private key. The most well-known signature scheme is GG19 (with a reference implementation available in the ZenGo-X repository). In particular, Embedded Wallets supports and utilizes GG19, GG20, its EDDSA variants, and DKLS19.
Distributed Key Generation
Distributed Key Generation (DKG) was introduced by Pedersen, who demonstrated that using n parallel runs of SSS or VSS ensures that there is no single party who knows the secret. Embedded wallets applies a varient of Async Verifiable Secret Sharing (AVSS) in our DKG.
Async Verifiable Secret Sharing
The main advantage Async Verifiable Secret Sharing (AVSS) DKG has over the other well-known DKGs like Pedersen DKG, Feldman's VSS, and its variants is that it is fully asynchronous. This means it does not require a complaint phase when we consider the allowance for a small zero-knowledge proof. This results in a simpler implementation (with constant communication rounds even during malicious scenarios), but at the expense of message size.
In brief, this scheme generates a random bivariate polynomial (a 2D surface) and creates horizontal (X) and vertical (Y) slices at the appropriate indices as shares. From these slices, nodes derive sub-shares (evaluation points) and exchange them with other nodes.
Each node reconstructs a polynomial from the sub-shares received from other nodes and verifies that it is consistent with the initial share it received from the originating node. If inconsistencies are detected, the node can interpolate the correct share using the exchanged sub-shares, which eliminates the need for a separate complaint phase.
Finally, the scheme restricts itself to the horizontal (X) domain so that the resulting shares lie on a univariate polynomial, which matches the structure used by standard DKG protocols.
At the end of the distributed key generation process, the nodes are left with a (polynomial) share to a master polynomial. This master polynomial is the sum of all the initial polynomials which were generated by each participating node. Since a threshold number of nodes contributed to this master polynomial's randomness, it is not possible for any non-threshold subset of nodes to recover its coefficients.
Proactive Secret Sharing
Proactive Secret Sharing (PSS) allows participants to “refresh” shares, so that all participants receive new shares, while the secret remains unchanged. This allows the secret sharing to be secure against mobile adversaries who may be able to compromise all participants over the lifetime of the secret (for example, an adversary hacks a random participant’s server every month).
Simply copying shares across epochs is a bad idea, since a single node operator operating in two separate epochs would get access to two shares, and it also makes it impossible to increase or decrease the number of operators in each epoch. This is why we use PSS to migrate shares across epochs.
We refer the user to a Proactive Secret Sharing Scheme that supports dynamic sets of participants, which we use for share refresh. In brief, the key idea is that we create polynomial sharing of the existing key shares and add these polynomials in a specific way such that the coefficient of the master polynomial is the Lagrange interpolation of the existing key shares. Much like how DKGs are the sum of several secret sharings, where the master secret is the sum of all of the secrets from each of the N-parallel secret sharing protocols, we can do the same thing by setting N-parallel secret sharing protocols to be run by the original set of nodes, with their "secret" as their share. The resulting shares of shares, if added appropriately (multiply them by Lagrange coefficients first), would lead to a re-sharing on the original secret.
Epochs
The underlying node network operates within chunks of time, called an epoch. Nodes within the same epoch are part of the same BFT (Byzantine Fault Tolerant) network and hold key shares that are compatible with each others' key shares. Nodes within different epochs do not. The main purpose of epochs is to ensure that node operators can be removed and added, and to minimize the impact of loss of key shares or node failures over time.