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

Metastate
Metastate
Jun 3, 2020 · 5 min read

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.

Bactrian camels — by Animals Adda

Background

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 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 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

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

Final Remarks & What’s Next?

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

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

Follow us on Twitter and Medium to stay tuned! 🐫

METASTATE

Realizing Decentralized Protocols