DeShuffle (Randomization)

Background and Motivation

DeShuffle toolkit provide an easy way for Rust developers to create fair poker games utilizing verifiable dealayed function(VDF) and zero-knowledge proofs(zkp). The challenge of building a “mental poker” game is to ensure that no one can cheat while maintaining the communications reliable, efficient and low-cost.

DeShuffle is an efficient mental poker emphasizing the reduction of gas cost on Ethereum. zkShuffle can be applied beyond poker to many different types of card or board games where secure and fair card shuffle and deal is required without a trusted third party.

The problem can be described thus: "How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?" (Eliminating the trusted third-party avoids the problem of trying to determine whether the third party can be trusted or not, and may also reduce the resources required.)

The concept of "mental poker" refers to the implementation of playing a fair game over distance without the need for a trusted third party. The name itself comes from poker which is one of the games to which this kind of problem applies and itwas initially proposed in 1979 by Adi Shamir, Ron Rivest, and Leonard Adleman in a paper where they discussed the idea of creating a fair poker game in which players could not see each other's cards or shuffle and deal the cards themselves. .

DeShuffle is a framework for playing card/board games without physical cards or a trusted third party. For example, if you build a mental poker framework for a deck of 52 cards, you can almost write any poker game such as Texas Hold’em or Joker using only Rust or Solidity. For a comprehensive overview, we direct the reader to the series of articles published by Geometry [3, 4]. However, Geometry’s implementation [5] requires verifier to run a linear-sized multiexponentiation, which is expensive on EVM. In this work, we propose a new poker design focusing on unbiased randomness generation and shuffling cards with minimal transactions and gas cost on public blockchains.

DeShuffle Scheme Overview

At a high level, DeShuffle can shuffle a deck of cards through player's seeds generated privately and deal necessary cards to each individual player. And a player can reveal a single card (or a subset of cards) on her hand when she needs to show her hand.

Our construction utilize trapdoor verifiable delayed function(VDF) and Groth16 zero-knowledge proof.

setup

vdf_verifier

shuffle

shuffle verifier

decrypt

Intuition Behind DeShuffle and How to Use It

Shuffle the Deck

aggregated seeds contributed only from players with delayed verifiability and off-chain shuffling process with on-chain zero-knowledge proof on Ethereum. Technically this design still follows the design from Barnett and Smart (also the one Geometry uses), the difference is that we implements the new shuffle argument using Groth16 [6]. This reduces the cost of each shuffle and decrypt to constant cost of verification on chain (thus also scales to more players). Now, everyone can play Texas Hold’em and Hearth Stone on Ethereum!

Card Dealing

Where and Why is a SNARK needed