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;