[Research] zk-Shuffle SDK: Gas Optimization for Efficient On-chain Card Games
Experience fully on-chain card games on our upcoming ZERO GAS alpha net.
TL;DR
This research explains how we achieve efficient, fully on-chain shuffling with optimized cryptographic (PlonK) implementations, including:
“Mental Poker” & zk-shuffle for guaranteed in-game fairness
Zypher’s shuffle SDK as a core component of its Secret Game Engine
optimized “Reveal” process using SNARK
optimized “Shuffle” process using “partial” storage
Zypher’s upcoming ZERO GAS Alpha Net, supporting Shuffling as Pre-compiled contracts.
What is Zypher Secret Engine?
As the name suggests, Zypher’s Secret Engine preserves "on-chain secrets."
The inherent transparency of the blockchain has historically rendered fully on-chain strategy games impractical, due to predictable game mechanics.
The Secret Engine provides a suite of SDKs that enable the secure execution of encrypted computations, ensuring strategic elements remain "sealed" on-chain. Mechanics like social deception, fog of war, shuffling, randomness, and secret placing, etc., can now be integrated into on-chain games with provability.
Currently, the Engine offers two core components:
zk-Shuffle SDK
zk-Matchmaking SDK
Mental Poker / On-chain Shuffling for Card Games
In 1979, Rivest, Shamir, and Adleman posed a challenge: how to ensure a fair poker game on the internet without physical playing cards, without a trusted third party, and where all participants are assumed to be dishonest? This problem is also known as "Mental Poker".
Ensuring fairness is crucial in mental poker games, with zk-shuffle being a key step. However, the shuffling time significantly affects the user experience. The remark operation involves elliptic curve cryptography operations, leading to a large circuit for shuffling 52 cards. To reduce the size of the circuit, we redesigned the PlonK circuit gates, embedding the zk-shuffle algorithm at the base level (constraint system).
In practice, besides zk-shuffle, we also face the issue of high gas fees for on-chain verification. This paper will primarily discuss our optimization insights to reduce gas costs.
Optimized “Reveal” Process
zk-shuffle includes two actions:
1) permuting the cards,
2) remarking the cards.
Assume the masked card be:
randomly number:
the remark operation on masked card C is:
where G: the group element, i.e., Baby Jubjub, H is the aggregate public key.
After completing the above remark operation, we obtain a new masked card:
actually obtaining a masking factor of the masked card:
Hence to reveal the card, each player needs to provide their masking factor. Additionally, there's another method that doesn't require providing the masking factor, which is the reveal method discussed in this section.
Assume the player's public-private key pair be:
, when revealing a card, the player only needs to calculate:
Although revealing a card is just a simple point multiplication operation, it's important to note that we cannot ensure the player is honest, we can't ensure the player actually performed the reveal operation. Therefore, we need the player to provide a proof while revealing the card to prove their reveal action.
In the Mental Poker protocol implemented by Geometry Research, they constructed a reveal proof based on the Chaum Pedersen protocol. However, this proof is extremely expensive to verify on-chain, mainly because the entire Chaum Pedersen protocol is based on the Baby Jubjub curve, which EVM currently does not support as a precompiled contract. Therefore, we had to natively implement point addition and point multiplication operations in the contract, as detailed on GitHub, leading to very high gas costs for verifying the reveal proof. Although verifying the reveal proof only involves a few point multiplication and addition operations, testing results showed that the gas cost for native verification reaches up to 7,629,888, which is clearly unacceptable.
Considering Baby Jubjub is an embedded curve of BN254, we can use SNARK for the reveal proof. According to Groth16 Verification Gas cost, using Groth16 for the reveal proof's on-chain verification only costs about 200,000, which is almost 30 times less than the native verification method. Compared to the native verification method, this seems to be a very good option. The reveal circuit is as follows:
public input:
generator: g => Gmasked card: C = (C_a, C_b), we only use C_areveal card: outpublic key: pk
witness:
sk
circuit such that:
pk = sk * gout = sk * C_a
Optimized “Shuffle” Process
Let’s use a Texas Hold’em poker game as an example. In the game, we need to store the result of the “shuffled deck” on-chain. This not only serves as the current shuffle result but also as the public input for subsequent 'shuffles', as demonstrated in the set deck operation. Initially, the set deck defaults to storing the initialized deck of cards. However, as we all know, on-chain storage is costly, especially for large data volumes. A deck of 52 cards consists of a total of 208 uint256 type data, making storage costs a significant consideration.
Our solution is to only store part of the data on-chain after shuffling, specifically, we only need to store 2n+5 cards, where n is the number of players. Given our game supports a maximum of 6 players, only up to 17 cards are used. This means we ultimately only need to store these 17 cards on-chain.
Although we eventually only need to store 17 cards on-chain, another purpose of on-chain storage mentioned earlier is that these cards will also serve as public input for subsequent shuffles. Therefore, if only 17 cards are stored, it's impossible to verify the correctness of the shuffle.
To address this issue, our zk-shuffle circuit will additionally output the complete deck of cards' hash value as public input, also stored on-chain. When verifying zk-shuffle, users will upload the pre-shuffle deck of cards as public input, and the circuit will calculate the hash value of the user-uploaded cards and compare it with the hash value stored on-chain.
Finally, since only partial data is saved on-chain, users may need to obtain the complete set of 52 cards. For this, we can use contract events. An event is an extremely low-cost way of communication, allowing users to obtain complete game data by listening to events.
In summary, this optimization not only effectively reduces storage costs but also ensures the fairness and integrity of the game. All relevant code can be found in the uzkge repository (a earlier release of the Secret Engine open-sourced under GPLv3).
Zypher Alpha Net: Revolutionizing On-chain Card Games
As highlighted in the Risc Zero partnership announcement, zAce, a fully on-chain Texas Hold’em Game powered by Zypher’s zk-Shuffle SDK for fair on-chain shuffling and Risc Zero zkVM for provable game logic is currently under playtest phase on the opBNB testnet, demonstrating promising latency and gas costs.
To further deliver a Web 2.0 experience, we’re soon launching an Alpha Net powered by Zytron Kit (Zytron One Pager), our game-dedicated Sovereign Rollup Stack, featuring ZERO Gas, 0.2s Blocktime, enhanced cryptographic precompiles, Zypher Game Engines as pre-compiled contracts, and more. The Alpha Net will launch with a few pioneer Fully On-chain Games, including Crypto Rumble, z2048, zAce, etc. supporting zero-gas gameplay. Stay tuned!
About Zypher Games
Zypher Games is building the next-generation infrastructure for Autonomous Worlds, featuring a suite of ZKP-powered game engines from Sovereign Layer 3 Rollups to ZK-as-a-service SDKs. Our technology provides decentralized games with the required composability, programmability, scalability, and cryptographic primitives. It empowers game developers to craft rich, interactive worlds, emphasizing scalability, fairness, and the intricacies of game strategy.
