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:
- 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.
- Player Registration: Anyone can join as a "player" by depositing a stake, which acts as collateral.
- 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.
- Aggregation: Players combine their shared secrets. Each player computes a polynomial based on their secret and sends a share of this polynomial to CASSIE.
- 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'.
- 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-1players collude with CASSIE, wheretis a parameter chosen during initialization. If CASSIE controlstor 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