Secure and Decentralized Generation of Secret Random Numbers on the Blockchain

Pouria Fatemi, Amir Kafshdar GoharshadyBCCA 2023 · OpenReview

TL;DR

This paper introduces a novel blockchain protocol for generating secret, verifiable, and decentralized random numbers. It's particularly useful for applications like online casinos, allowing them to prove the fairness of their operations without revealing the random seed used for bets until much later.

What Problem Does This Paper Address?

Generating truly random numbers is a fundamental challenge in many systems, especially in the blockchain space where trust and verifiability are paramount. Existing blockchain-based random number generators (RNGs) often make the generated number public, which is great for auditability but fails to meet the needs of applications requiring secret randomness. For instance, an online casino might want to use a random number as a seed for its daily operations, but revealing this seed upfront would allow players to manipulate bets. The problem is to create an RNG that is decentralized, secure, tamper-proof, auditable, and crucially, keeps the generated random number secret from everyone except a designated party (like the casino) until they choose to reveal it.

Methods

The core of the proposed solution is a clever combination of two cryptographic primitives: Homomorphic Encryption (specifically, the Goldwasser-Micali Cryptosystem) and Shamir's Secret Sharing (SSS).

Here's a breakdown of the protocol's flow:

  1. Initialization: The client (e.g., a casino named CASSIE) initiates the process, setting up parameters like the reward for participants and cryptographic keys. CASSIE generates a Goldwasser-Micali (GM) public key and shares it with the network.
  2. Player Registration: Anyone can join as a "player" by depositing a stake, which acts as collateral.
  3. Encryption and Secret Sharing: Each player generates a random bit and encrypts it using CASSIE's GM public key. Crucially, instead of sharing the encrypted bit directly, they share a secret derived from it using SSS. This ensures that no single player, nor even a colluding group of players (up to a certain threshold), can deduce the individual encrypted bits.
  4. Aggregation: Players combine their shared secrets. Each player computes a polynomial based on their secret and sends a share of this polynomial to CASSIE.
  5. Obtaining 'r': CASSIE receives these shares and uses her GM private key to reconstruct the encrypted random number. The magic here is that the homomorphic property of GM allows her to combine the encrypted bits from all players into a single encrypted value representing the final random number 'r'. She then decrypts this to get 'r'.
  6. Audit: At any point, CASSIE can reveal 'r' and her GM private key. This allows anyone to verify that 'r' was indeed generated by the protocol and that she didn't tamper with it.

The novelty lies in using homomorphic encryption to allow computations on encrypted data (specifically, combining encrypted bits) and SSS to ensure that individual bits remain secret until CASSIE decrypts the aggregated result.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of Combining Cryptographic Primitives: The paper demonstrates how combining seemingly disparate cryptographic tools (homomorphic encryption and secret sharing) can solve complex problems that neither could solve alone.
  • Secrecy as a First-Class Citizen for Blockchain RNGs: Most prior work focused on public verifiability. This paper highlights the critical need for secret randomness in certain high-value applications like online gambling, and provides a practical solution.
  • Decentralization with Controlled Secrecy: The protocol achieves decentralization by allowing anyone to participate, but maintains secrecy by ensuring only the designated client can decrypt the final result.
  • Cost-Effectiveness for Casinos: By generating a single secret random seed for a whole day's operations, the protocol significantly reduces transaction costs and latency compared to generating a new random number for every single bet.
  • Auditability Without Sacrificing Secrecy: The protocol allows for post-hoc auditing by revealing the secret seed and the decryption key, proving the integrity of the process without compromising the seed's secrecy during its use.

Key Results

The paper presents a protocol that achieves:

  • Decentralization: Open participation from anyone on the blockchain.
  • Uniform Distribution: The generated random number follows a uniform distribution.
  • Secrecy: Only the designated client (CASSIE) can see the random number 'r' until she chooses to reveal it. Even colluding players cannot deduce 'r'.
  • Tamper-Resistance: The protocol is designed to prevent participants from manipulating the outcome.
  • Auditability: CASSIE can prove the origin and correctness of the generated random number.
  • Accountability: Dishonest behavior by players can be detected and traced.
  • Efficiency: The protocol is designed to be cost-effective, especially for use cases like online casinos, by minimizing on-chain operations for each bet.

Limitations and Future Work

  • Communication Complexity: The protocol has a communication complexity of O(n²) because each player needs to send shares to every other player. While these communications can be off-chain, it's still a factor. The authors note that O(n) on-chain messages are unavoidable.
  • Collusion Threshold: The security relies on the assumption that not more than t-1 players collude with CASSIE, where t is a parameter chosen during initialization. If CASSIE controls t or more players, the secrecy guarantee is broken.
  • Future Work: The authors suggest exploring ways to further optimize communication complexity and investigate other applications for secret, verifiable random number generation. They also mention that the specific penalty mechanisms for dishonest players are an orthogonal issue for developers to implement.

Summary updated

Abstract

We propose a trustless blockchain-based protocol for secure and decentralized generation of secret random numbers. In our protocol, which can be implemented as a smart contract, a client Cassie can ask for a secret random number $r$. The protocol will then allow anyone on the blockchain network to contribute to the process of generating $r$, but crucially, only Cassie would be able to see the final result. Additionally, our approach is auditable, i.e. if Cassie later wishes to announce her secret random number $r$, she can prove that the output of the process was indeed the claimed value. Finally, we ensure no one else is able to deduce $r$ before Cassiediscloses it. A primary use-case of this approach is to enable auditable online gambling and casinos with verifiable and tamper-proof randomness. If Cassie is a casino, she can ask for a secret random number $r$ at the beginning of the day, and then use it as a seed in a predefined pseudo-random number generator which is in turn used as the source of randomness for all bets during the day. At the end of the day, Cassie can prove that the seed was indeed generated by our decentralized protocol. Thus, she can prove that the casino had no control over the outcomes of the bets. Moreover, this is a cost- and time-efficient approach as it does not require us to generate a new random number for every bet.
BibTeX
@inproceedings{fatemi2023secure,
  author = {Pouria Fatemi and Amir Kafshdar Goharshady},
  title = {{Secure and Decentralized Generation of Secret Random Numbers on the Blockchain}},
  booktitle = {BCCA},
  year = {2023},
  url = {https://openreview.net/forum?id=PPHJypW6zF},
}
Figure