Skip to main content

ducy_shuffle/
lib.rs

1//! A trustless ("mental poker") shuffle: the deck is encrypted and shuffled
2//! by every player and the host in turn, so no single party controls or sees
3//! the deal (allenpiscitello/ducy#134, step 2: #136).
4//!
5//! # How it works
6//!
7//! Each card is a fixed point on Ristretto255 ([`card_point`]). Every party
8//! makes a fresh [`Secret`] per hand. *Locking* a card multiplies its point by
9//! the secret, *unlocking* by the secret's inverse. Scalar multiplication
10//! commutes, so locks can be added and removed in any order:
11//!
12//! 1. **Shuffle rounds** ([`shuffle_round`]): starting from [`open_deck`], each
13//!    party in turn (players in seat order, then the host) locks every card
14//!    and applies a secret random permutation, and passes the deck on. Once
15//!    every party has gone, no one knows which position holds which card.
16//! 2. **Lock removal** ([`Layout`]): for each player's hole-card positions,
17//!    every *other* party removes its lock ([`Secret::unlock`]), leaving only
18//!    the owner's; the owner unlocks their own and [`decode`]s them. For the
19//!    board positions, every *player* removes their lock, leaving only the
20//!    host's.
21//! 3. **Streets:** the host removes its last lock from one street's
22//!    positions at a time, so the board is public only when it's dealt.
23//! 4. **Showdown:** a player publishes their secret; anyone can unlock that
24//!    player's hole positions with it and see their cards.
25//! 5. **Audit** ([`audit`]): after the hand, every party publishes its secret
26//!    and permutation, and anyone can re-check the whole deal.
27//!
28//! The host never sees anyone's hole cards. The host does see the board
29//! before it's dealt (decided on #134: the host has no seat at club tables).
30//!
31//! Every step can carry a zero-knowledge proof ([`proof`], #140), checked
32//! before the deal goes on, and [`setup`] runs a whole deck's setup that way
33//! for the host, leaving out anyone who drops out (#137).
34//!
35//! This is the cryptographic core only: no networking or table logic. It
36//! should be reviewed by someone with cryptography expertise before it's
37//! trusted with real games.
38//!
39//! ```
40//! use ducy_shuffle::{decode, open_deck, shuffle_round, Layout, Secret};
41//!
42//! // Two players and the host, Hold'em.
43//! let layout = Layout::new(2, 2, 5);
44//! let secrets: Vec<Secret> = (0..3).map(|_| Secret::random()).collect();
45//! let mut rng: rand::rngs::StdRng = rand::make_rng();
46//! let mut deck = open_deck();
47//! for s in &secrets {
48//!     deck = shuffle_round(&deck, s, &mut rng).0;
49//! }
50//! // Everyone but player 0 (the host is party 2) removes their lock from
51//! // player 0's hole cards; then player 0 opens them.
52//! let mut mine: Vec<_> = layout.hole(0).map(|p| deck[p]).collect();
53//! for party in [1, 2] {
54//!     mine = mine.iter().map(|c| secrets[party].unlock(c)).collect();
55//! }
56//! let cards: Vec<_> = mine.iter().map(|c| decode(&secrets[0].unlock(c)).unwrap()).collect();
57//! assert_eq!(cards.len(), 2);
58//! ```
59
60#![forbid(unsafe_code)]
61#![warn(missing_docs)]
62
63mod audit;
64pub mod proof;
65pub mod setup;
66
67pub use audit::{Fault, FaultKind, PartyRound, Transcript, Unlock, audit};
68pub use proof::{PublicKey, ShuffleProof, UnlockProof};
69pub use setup::{DeckSetup, Ready, Request, SetupParty, Step};
70
71use std::collections::HashMap;
72use std::ops::Range;
73use std::sync::OnceLock;
74
75use curve25519_dalek::ristretto::{CompressedRistretto, RistrettoPoint};
76use curve25519_dalek::scalar::Scalar;
77use ducy::deck::{Card, Deck};
78use rand::{Rng, RngExt, rngs::StdRng};
79use sha2::Sha512;
80
81/// Domain separation for the card points: changing it changes every card.
82const CARD_DOMAIN: &str = "ducy-shuffle/v1/card/";
83
84/// A card as the parties see it: a point on Ristretto255, plain (a card's
85/// [`card_point`]) or under any number of locks.
86#[derive(Clone, Copy, Debug, PartialEq, Eq)]
87pub struct Masked(RistrettoPoint);
88
89impl Masked {
90    /// The 32 bytes to send to other parties.
91    pub fn to_bytes(&self) -> [u8; 32] {
92        self.0.compress().to_bytes()
93    }
94
95    /// A card from another party; `None` if the bytes aren't a valid point.
96    pub fn from_bytes(bytes: &[u8; 32]) -> Option<Self> {
97        CompressedRistretto(*bytes).decompress().map(Masked)
98    }
99}
100
101/// The fixed point for `card`: a hash of its name onto the curve, so no one
102/// knows any relation between two cards' points.
103pub fn card_point(card: Card) -> Masked {
104    Masked(RistrettoPoint::hash_from_bytes::<Sha512>(
105        format!("{CARD_DOMAIN}{card}").as_bytes(),
106    ))
107}
108
109/// The 52 cards, unlocked, in ducy's order: where every shuffle starts.
110pub fn open_deck() -> Vec<Masked> {
111    all_cards().iter().map(|&c| card_point(c)).collect()
112}
113
114fn all_cards() -> &'static [Card] {
115    static CARDS: OnceLock<Vec<Card>> = OnceLock::new();
116    CARDS.get_or_init(|| Deck::all_cards().iter(false).collect())
117}
118
119/// The card an unlocked point stands for, or `None` if it isn't one (some
120/// lock is still on it, or it was tampered with).
121pub fn decode(m: &Masked) -> Option<Card> {
122    static TABLE: OnceLock<HashMap<[u8; 32], Card>> = OnceLock::new();
123    TABLE
124        .get_or_init(|| {
125            all_cards()
126                .iter()
127                .map(|&c| (card_point(c).to_bytes(), c))
128                .collect()
129        })
130        .get(&m.to_bytes())
131        .copied()
132}
133
134/// One party's key for one hand. Never reuse it: after the hand it's
135/// published for the audit.
136#[derive(Clone, Copy, Debug, PartialEq, Eq)]
137pub struct Secret(Scalar);
138
139impl Secret {
140    /// A fresh secret from the operating system's random source.
141    pub fn random() -> Self {
142        let mut rng: StdRng = rand::make_rng();
143        Self::from_rng(&mut rng)
144    }
145
146    /// A secret from `rng` (seeded RNGs are for tests).
147    pub fn from_rng<R: Rng + ?Sized>(rng: &mut R) -> Self {
148        loop {
149            let mut wide = [0u8; 64];
150            rng.fill_bytes(&mut wide);
151            let s = Scalar::from_bytes_mod_order_wide(&wide);
152            if s != Scalar::ZERO {
153                return Secret(s);
154            }
155        }
156    }
157
158    /// Adds this party's lock to a card.
159    pub fn lock(&self, m: &Masked) -> Masked {
160        Masked(m.0 * self.0)
161    }
162
163    /// Removes this party's lock from a card (it must be on it, or the
164    /// result is garbage that decodes to nothing).
165    pub fn unlock(&self, m: &Masked) -> Masked {
166        Masked(m.0 * self.0.invert())
167    }
168
169    /// The 32 bytes to publish (at showdown, or for the audit).
170    pub fn to_bytes(&self) -> [u8; 32] {
171        self.0.to_bytes()
172    }
173
174    /// A published secret; `None` if it isn't a valid, non-zero scalar.
175    pub fn from_bytes(bytes: &[u8; 32]) -> Option<Self> {
176        Option::<Scalar>::from(Scalar::from_canonical_bytes(*bytes))
177            .filter(|s| *s != Scalar::ZERO)
178            .map(Secret)
179    }
180}
181
182/// One party's turn: lock every card and shuffle. Returns the new deck and
183/// the permutation used (`out[i]` is `deck[perm[i]]`, locked), which the
184/// party keeps secret until the audit.
185pub fn shuffle_round<R: Rng + ?Sized>(
186    deck: &[Masked],
187    secret: &Secret,
188    rng: &mut R,
189) -> (Vec<Masked>, Vec<u32>) {
190    let mut perm: Vec<u32> = (0..deck.len() as u32).collect();
191    for i in 0..perm.len() {
192        let j = rng.random_range(i..perm.len());
193        perm.swap(i, j);
194    }
195    let out = apply_round(deck, secret, &perm).expect("a permutation of the deck");
196    (out, perm)
197}
198
199/// A shuffle round from its published secret and permutation: what the
200/// party should have sent. `None` if `perm` isn't a permutation of the deck.
201pub fn apply_round(deck: &[Masked], secret: &Secret, perm: &[u32]) -> Option<Vec<Masked>> {
202    if !is_permutation(perm, deck.len()) {
203        return None;
204    }
205    Some(
206        perm.iter()
207            .map(|&i| secret.lock(&deck[i as usize]))
208            .collect(),
209    )
210}
211
212fn is_permutation(perm: &[u32], n: usize) -> bool {
213    if perm.len() != n {
214        return false;
215    }
216    let mut seen = vec![false; n];
217    perm.iter().all(|&i| {
218        let i = i as usize;
219        i < n && !std::mem::replace(&mut seen[i], true)
220    })
221}
222
223/// Which deck positions are whose once the shuffle is done: each player's
224/// hole cards in seat order, then the board. Parties are numbered players
225/// `0..players`, then the host ([`Layout::host`]).
226#[derive(Clone, Copy, Debug, PartialEq, Eq)]
227pub struct Layout {
228    /// Players dealt in.
229    pub players: usize,
230    /// Hole cards each.
231    pub hole: usize,
232    /// Board cards.
233    pub board: usize,
234}
235
236impl Layout {
237    /// # Panics
238    /// If the cards don't fit in one deck.
239    pub fn new(players: usize, hole: usize, board: usize) -> Self {
240        assert!(players * hole + board <= 52, "not enough cards");
241        Layout {
242            players,
243            hole,
244            board,
245        }
246    }
247
248    /// The host's party number: after the players.
249    pub fn host(&self) -> usize {
250        self.players
251    }
252
253    /// Player `p`'s hole-card positions.
254    pub fn hole(&self, p: usize) -> Range<usize> {
255        p * self.hole..(p + 1) * self.hole
256    }
257
258    /// The board's positions, in dealing order.
259    pub fn board(&self) -> Range<usize> {
260        self.players * self.hole..self.players * self.hole + self.board
261    }
262
263    /// Who must remove their lock from position `pos` during setup: for a
264    /// hole card everyone but its owner; for a board card every player (the
265    /// host keeps its lock until the street is dealt). Other positions are
266    /// never dealt.
267    pub fn unlockers(&self, pos: usize) -> Vec<usize> {
268        if pos < self.players * self.hole {
269            let owner = pos / self.hole;
270            (0..=self.players).filter(|&q| q != owner).collect()
271        } else if self.board().contains(&pos) {
272            (0..self.players).collect()
273        } else {
274            Vec::new()
275        }
276    }
277}
278
279#[cfg(test)]
280mod tests;