PVSS Implementation in Cardano SL

Publicly Verifiable Secret Sharing (PVSS) Scheme used in Cardano SL is based on “SCRAPE: Scalable Randomness Attested by Public Entities”, paper by Ignacio Cascudo and Bernardo David. Further we’ll refer to this paper’s pages, for example [6] means the 6-th page.

This guide describes implementation details of pvss-haskell library used by cardano-sl library.

What is PVSS

The core idea of VSS Scheme is an ability of participants to verify their own shares, for successful reconstruction of the secret (previously distributed by a dealer among the participants). But core idea of PVSS Scheme is that not just the participants can verify their shares, but that anybody can verify that the participants received correct shares. So it’s required (for our reconstruction protocol) that participants not only release their shares but also that they provide a proof of correctness for each share released ([9]).

We use t-out-of-n reconstruction scheme ([8]), where n is a number of participants and t is a threshold number, so any subset of t+1 shares can be used to successfully recover the secret.

So, the protocol consists of four fundamental phases ([8]):

  1. setup,
  2. distribution,
  3. verification,
  4. reconstruction.

Setup

Each participant Pi must generate its private key SKi and register its public key PKi.

Distribution

First of all, we prepare a new escrowing context. To do it we need a threshold value mentioned above and a list of public keys of participants. Result of this operation is Escrow value which includes:

  1. Extra generator,
  2. Polynomial,
  3. Secret,
  4. Proof.

Extra generator is based on a Point (Elliptic Curve Point). We use prime256v1 elliptic curve, see RFC.

Polynomial is a group of coefficient starting from the smallest degree (these coefficients are Scalar values).

Secret is based on a Point as well, actually it’s the first element of polynomial mentioned above.

Proof is generated from a challenge, raw secret and DLEQ-parameters.

Challenge is based on cryptographic hash.

After that we have to finish escrow creation. List of participants’ public keys is used to create encrypted shares and commitments. Encrypted share inсludes:

  1. Share ID,
  2. Value encrypted by participant’s public key,
  3. Proof that this share is valid ([8]).

Verification

Now commitments and encrypted shares can be published among participants. Due the public nature of PVSS scheme anyone who knows public keys can verify decrypted shares via hashes matching ([8]).

Reconstruction

First of all, participant must decrypt encrypted share using keys pair with its private and public keys. To obtain DLEQ value, we use prime256v1 curve generator. As a result, we get DecryptedShare. Its structure is the same as encrypted share.

Since decrypted share contains a proof, we can be sure that decrypted share is the same as encrypted one, there’s verification function for it. To do it we use DLEQ value and proof from the decrypted share. Actual verifying is a comparison of the hash of DLEQ points.

Now, if we have t+1 decrypted shares we can recover a secret.

Recovered secret can be verified as well, so we can be sure that secret recovered is the same escrow. To do it, we need not just a proof and a secret, but commitments as well (actually, the first one.

VSS Certificate

As said earlier, one of the challenges while using a PVSS scheme is associating the public key used for signing with the public key used for VSS scheme. This is solved by introducing VSS certificate.

VSS certificate includes:

  1. Public key used for the VSS scheme (e.g. VSS key).
  2. Public key used for signing (e.g. signing key).
  3. Index of an expiry epoch (e.g. the last epoch when this certificate was valid).
  4. Signature of a pair (A,B), where A is a VSS key and B is an epoch index.

Initially, all stakeholders with enough stake to participate in randomness generation (we call them richmen) have their own certificates. When a new stakeholder having enough stake appears, or when an existing certificate expires, a new certificate should be generated and submitted to the network. Other nodes accept this certificate if it’s valid and if the node has enough stake. Certificates are stored in blocks.

Please note that VSS certificate must be stable before usage! If an epoch we retrieve certificates for is the first one (i.e. has index 0), stable certificates are genesis ones. Otherwise stable certificate are non-expired certificates for the last known slot.