Publicly Verifiable Secret Sharing (PVSS) Scheme for Randomness Generation on Tezos

Published in

METASTATE

5 min readJun 3, 2020

The purpose of this series is to share details with the Tezos community on another feature our team has been exploring: a publicly verifiable secret sharing scheme (PVSS) for randomness generation.

This article starts with a brief recap on how randomness is currently generated in the Tezos protocol via a commit-reveal scheme. This is followed by a description of PVSS in general, as well as how a PVSS scheme in the context of the Tezos protocol. Finally, we briefly describe a possible 2-step protocol integration process of such PVSS scheme.

Background

Before proceeding, we recommend taking a look at the current commit-reveal scheme used in Tezos. You can find more information about it in this documentation.

Under this model, to obtain the randomness seed for a cycle n, the seed from the previous cycle n-1 is hashed with a constant and the revealed nonces from cycle n-1. The nonces that didn’t get revealed will not contribute to the seed calculation.

When a baker bakes a block, it generates a seed nonce and commits its hash to the block. In the next cycle, the baker may reveal their unrevealed seed nonces. A revealed nonce must match the committed hash. A baker who fails to reveal the committed nonce forfeits their rewards and fees.

PVSS

A cryptography scheme known as PVSS (publicly verifiable secret sharing) allows further improving upon the current model. In general, it allows for making “shares” of some secret, whose subset can be used to collectively recover the original secret in a two-step protocol:

a dealer generates shares of the secret for each participant and each participant receives their share encrypted with their public key
participants can use their private key to decrypt and reveal their share and some subset of the revealed shares can reconstruct the original secret

Both steps of this protocol also produce zero-knowledge proofs that are publicly verifiable against the public keys, which means that anyone who knows the public keys can verify those proofs. For the encrypted shares it shows that each share encrypts the share of the committed secret, which guarantees that the reconstruction will result in the same secret. For the decrypted shares, the proof shows that it is decrypted honestly.

PVSS in the context of Tezos

Under the PVSS scheme, the randomness nonce (the secret) is encrypted to produce secret shares and a zero-knowledge proof that the nonce can be reconstructed from these shares. This proof can be verified with the bakers’ PVSS public keys. Each baker then receives their secret share and it can decrypt their share using their secret key and release it together with a proof that their released share is correct. The reconstruction of the nonce is performed by the protocol from a set of released shares, where only a fraction of the total number of shares is needed. This fraction can be adjusted to also provide a sufficient level of fault-tolerance.

Under a potential design direction to add to the current commit-reveal scheme the baker who bakes a block would act as a dealer in the PVSS scheme. The baker generates shares for each other baker and a commitment that is used to verify the shares. In the next cycle, the protocol would decrypt and release their shares and when the minimum threshold is met, the seed nonce can be reconstructed from them.

The introduction of PVSS scheme to Tezos would provide an improvement over the current commit-reveal scheme since the nonce revelation is no longer dependent on a single entity who committed to it, but rather can be reconstructed collectively by any subset of bakers that meets the threshold.

Even stronger guarantees than from use of PVSS can be achieved with VDFs (Verifiable Delay Functions), which instead of non-colluding honest majority only require an honest participant, but this approach also comes with its own challenges.

Possible Integration and Future Work

To introduce PVSS to Tezos, we propose a 2-step protocol integration process:

In the first step, bakers are enabled to set up their PVSS public keys and store these in their baking accounts. In this protocol upgrade, the PVSS public keys are stored on chain, but are not yet actively used for randomness seed generation. There also is no requirement for bakers to provide a PVSS key at this point.

In the second step, the protocol randomness seed generation is updated to take advantage of the PVSS scheme described above and bakers PVSS keys become active. At this point bakers may be required to participate in the PVSS scheme and update their infrastructure. The exact details of the second step are still being explored.

Summary

In this post we described a possible direction to hardening randomness generation in Tezos using a PVSS scheme in a 2-step protocol upgrade that gives extra time to bakers to update their operations. PVSS is not a silver-bullet solution to the problem of randomness generation, however it provides a considerable improvement over the current commit-reveal scheme.

Final Remarks & What’s Next?

Much like with other proposed changes, the first step of this feature (that is the ability for bakers to set their PVSS public key) is planned to be included in the upcoming public testnets.

Additionally, a detailed changelog and documentation describing the modifications introduced by each feature, including but not limited to the PVSS scheme, will be released in the upcoming weeks.

In the meantime, we would like to use this article as research synthesis and discussion reference, in addition to opening this topic for discussion on Tezos Agora.

More Tezos Protocol R&D Articles

More Resources

Metastate’s official website for more information on current projects and organization.
Metastate’s research blog.

For feedback or questions, please do not hesitate to contact us : team@metastate.dev