How to use zkSNARK to make an on-chain Texas Poker game?

链捕手ChainCatcher · 2022-11-14T09:15:07.000Z

Author: The Mandalorian, Manta Network Protocol In the past year or so, more and more people have become aware of the power of cryptographic tools like ZK (zero-knowledge proof), and we have also seen the rise of many zero-knowledge proof applications, such as private social networking, private voting, and private DAO. etc. In fact, the application of zero-knowledge proof is very broad, and any application that requires on-chain privacy may use zero-knowledge proof. At the ETHGlobal Hackathon event during the just-concluded ETHSanFrancisco 2022, the friends of the Manta Network cryptography development team made a zkSNARK-based poker game in just 36 hours, and successfully launched it on ApeCoin, Four competition units organized by ENS, SKALE and Optimism won awards.

Author: Mandalorian, Manta Network Protocol
 
Over the past year or so, more and more people have realized the power of cryptographic tools such as ZK (zero-knowledge proof), and we have also seen the rise of many zero-knowledge proof applications, such as privacy social networking, privacy voting, privacy DAO, etc. In fact, the application of zero-knowledge proof is very broad, and any application with on-chain privacy requirements may use zero-knowledge proof.
At the ETHGlobal hackathon event during the just-concluded ETHSanFrancisco 2022, the guys from the Manta Network cryptography development team created a zkSNARK-based Texas Hold'em game in just 36 hours, and won awards in four competition units hosted by ApeCoin, ENS, SKALE, and Optimism.
Dark Forest, which is well known to many people, is a real-time strategy (incomplete information) game based on zkSNARK. Incomplete information games are games where players do not know all the states. For example, in poker, the cards in the player's hand are private information, and the process of drawing cards is also completely private. The fun of incomplete information is that it can give rise to a series of complex game strategies.
On public blockchains, it is difficult to build incomplete information games due to the openness and transparency of on-chain data. However, through zero-knowledge proof technology, players can publicly submit verifiable valid actions while maintaining privacy.
In this hackathon, Manta Network built an on-chain Texas Hold'em shuffling and dealing system based on zkSNARK. This system mainly solves two problems in the on-chain Texas Hold'em game: how to shuffle cards fairly and how to deal cards between players in a covert manner (otherwise the game may not be playable due to the MEV problem).
In essence, on-chain Texas Hold'em based on zero-knowledge proof makes the card dealer decentralized, and the dealer cannot control the game by controlling the card dealing.
When playing Texas Hold'em in a Web2 centralized client, you may encounter a situation where a card with a very low probability is dealt to you, while a card with a high probability cannot be played.
The purpose is to manipulate the game by dealing cards, so that your opponent happens to win you online even though the probability of winning offline is extremely low.
This is why we need decentralized poker.
The ZKShuffle system has three functions:
ZKShuffle.setup: Each player generates a key pair, and puts each person's corresponding public key together to generate an aggregate public key.
ZKShuffle.shuffle_encrypt: When shuffling, each player needs to call shuffle_encrypt in turn.
In order to ensure that encryption and decryption can be performed in any order, we use a homomorphic encryption scheme. For example, there are three players in this game. After one round of encryption, each card will have three encryption locks: Card{Alice, Bob, Charlie}.
ZKShuffle.decrypt: If you want to deal cards to a specific player, each player needs to call the decryption function. For example, if the logic of the game is to deal cards to Charlie, the correct order should be: Alice takes the encrypted card Card{Alice, Bob, Charlie}, decrypts it with her key, and then submits the decrypted card Card{Bob, Charlie} on the chain, and submits a zero-knowledge proof to verify the validity of the decryption.
After Bob gets the partially decrypted card Card{Bob, Charlie} submitted by Alice on the chain, he decrypts it with his own key and submits the card Card{Charlie} and the zero-knowledge proof verifying the validity of the decryption on the chain. Finally, Charlie gets Card{Charlie} and can view his cards by decrypting them with his own key.
The Manta Network cryptography development team built a Texas Hold'em demo using ZKShuffle, a decentralized application based on Solidity, React, and Ether.js. In this demo, every time a new round of the game starts, all players have to do a round of setup to ensure that the poker cards on the chain are shuffled fairly. Then, each player needs to do a round of decryption to get two cards. With these, players can play Texas Hold'em on an EVM blockchain.
Manta has currently deployed this DApp on the Optimism Goerli, Ethereum Goerli and Skale blockchains.
 
Implementation principle
 
The whole project consists of 3 parts:
ZK circuit;
Smart contracts for verifying decryption and shuffling, including ZKShuffle contract and game logic contract DApp frontend, a demo built with React and ether.js and Circomlib JS library;
Circomlib cryptographic JS库。
In the implementation of Circom, the ElGamal encryption scheme is adopted, and existing Circom libraries such as poseidon hashes are used.
The encryption circuit has 87308 R1CS constraints, and the proof generation time in the DApp is 4.5 seconds. The decryption circuit has 1522 R1CS constraints, and the proof generation time in the DApp is 0.1 seconds. SnarkJs is used to generate zero-knowledge proofs in the DApp.
The smart contract consists of two parts: the ZKShuffle framework contract and the Texas Hold'em game logic contract. The ZKShuffle contract simply encapsulates the ZKP verification logic and two circuits. The logic contract deploys a state machine to obtain the current stage of the game and the order of which player's turn it is from the RPC node.
The DApp is implemented using the React framework and Ether.js, showing the poker table and the action animations of each player. When a player needs to take an action, the player only needs to click a button in the UI and use metamask to sign the transaction.
Watch Demo
 
About Manta Network
 
Manta Network is committed to building a better Web3 world through privacy protection. Manta's product design starts from the first principles and provides end-to-end privacy protection for blockchain users through leading cryptographic architectures such as zkSNARK. While ensuring privacy, Manta combines interoperability, convenience, high performance and auditability, allowing users to transfer and trade privately between any parachain assets. Manta's vision is to provide more convenient privacy protection services for the entire blockchain world.
Manta's founding team consists of many cryptocurrency veterans, professors and scholars, whose experience includes Harvard University, MIT and Algorand. Manta's investment institutions include Polychain, ParaFi, Binance Labs, Multicoin, CoinFund, Alameda, DeFiance and Hypersphere. Manta is also a recipient of Polkadot's official Web3 Foundation grant, a member of the Substrate Builder Program, and a member of the Berkeley Blockchain Accelerator.