Important Terms and Definitions
Shamir Secret Sharing (SSS)
Shamir’s secret sharing scheme is a polynomial threshold secret sharing scheme where a dealer 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 a base fundemental in a lot of MPC cryptography and in Web3Auth’s infrastucture. More can be read here.
Verifiable Secret Sharing (VSS)
Verifiable secret sharing refers to Shamir secret sharing schemes where even in the presence of malicious dealers, there is a well-defined secret that the participants can later reconstruct.
Threshold Signature Schemes (TSS)
Threshold signature schemes 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 and an implementation can be found here. In particular Web3Auth supports and utilizes GG19, GG20, its EDDSA variants, and DKLS19.
Distributed Key Generation (DKG)
Distributed key generation was introduced by Pedersen, and the key idea involves using n parallel runs of SSS or VSS to ensure that there is no dealer who knows the secret. We generally use a varient of Async Verifiable Secret Sharing in our DKG.
Async Verifiable Secret Sharing
The main advantage Async Verifiable Secret Sharing DKG has over the other well-known DKGs like Pedersen DKG, Feldman's VSS and its variants is that it is fully asynchronous and thus 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 (i.e. 2D surface) and creates horizontal (X) and vertical (Y) slices at the appropriate indices as sharings. We then get sub-sharings (points) on these horizontal and vertical sharings at the appropriate indices and echo them to other nodes. As a node, the polynomial reconstructed from the sub-sharings received from other nodes should match up with the initial sharing that the node received from the dealer, and even if they do not, the node can always interpolate the correct sharing via these echoed sub-sharings. This eliminates the dealer complaint phase. We then we restrict ourselves to just the horizontal (X) domain such that our final sharings are still on that of a univariate polynomial, which is what a typical DKG does.
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 (PSS)
Proactive secret sharing allows participants to “refresh” shares, so that all participants receive new shares, but 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 (eg. 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 not possible to increase or decrease the number of operators in each epoch. Hence, 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 sharings 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
Torus nodes operate within a certain time period, called an epoch. Nodes within the same epoch are part of the same BFT (Byzantine Fault Tolerance) 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.