Technical Summary: Probabilistic Atomic Swaps for Bitcoin and Friends

1. Problem Statement

Atomic swaps are a fundamental cryptographic primitive enabling trustless, cross-chain exchange of digital assets with an "all-or-nothing" guarantee: either both parties receive their agreed assets, or neither does. While powerful, this deterministic nature precludes exchanges where the intended outcome is probabilistic. Existing solutions for probabilistic exchanges (e.g., lotteries, wagers, or randomized allocation) on blockchains face significant limitations:

• Complexity and Cost: They often require complex smart contracts or intricate script-level mechanisms, leading to larger transaction sizes, higher fees, and reduced portability to chains with limited scripting support (like Bitcoin).
• Privacy and Fungibility: Complex scripts make on-chain behavior distinguishable, weakening privacy and fungibility.
• Participation Constraints: Many existing lottery protocols require a fixed, known set of participants, making them unsuitable for open, permissionless environments.
• Bias Vulnerability: Prior approaches often fail to prevent a party from predicting the outcome and selectively aborting if the result is unfavorable, thereby biasing the effective probability.

The core challenge is to extend atomic swaps to a probabilistic setting—where one party pays for a fixed, publicly specified chance of receiving a larger reward—without modifying the minimal on-chain footprint of existing atomic swap protocols or introducing trusted intermediaries.

2. Methodology and Protocol Design

The authors introduce probabilistic atomic swaps, a new cryptographic primitive that realizes fair exchange with a prescribed outcome distribution. The protocol involves two parties: a Dealer (D) and a Party (P). P transfers a fixed amount (e.g., 1 coin) in exchange for a probability $p$ of receiving a larger reward ($\nu$ coins) from D. If the probabilistic event does not occur, P receives nothing, and D retains the payment.

Core Cryptographic Building Blocks

The construction relies on three main components, all compatible with standard Bitcoin-like scripts (digital signatures and timelocks):

1. Adaptor Signatures: Used to ensure atomicity. They allow a pre-signature to be adapted into a full signature only if a specific witness (secret) is known. This binds the revelation of secrets to the completion of on-chain transactions.
2. Oblivious Pseudorandom Functions (OPRFs): Used to encode the probabilistic outcome. The Dealer acts as an OPRF server holding a secret key $sk_D$. The Party holds an input (a "guess" $y_{gss}$). The OPRF allows the Party to obtain the evaluation $OPRF(sk_D, y_{gss})$ without the Dealer learning the guess, and without the Party learning the key.
3. Zero-Knowledge Proofs (NIZKs): Used to prove the well-formedness of the protocol statements, ensuring the Dealer cannot manipulate the probability distribution.

Protocol Flow

The protocol is divided into four phases:

1. Setup & Funding:

   • The Dealer samples a target value $y_{tgt}$ from a domain of size $m$ (where $p = 1/m$).
   • The Dealer computes a "winning witness" $y_{win} = OPRF.Eval(sk_D, y_{tgt})$ and constructs a statement $Y_{win} = g^{y_{win}}$.
   • The Dealer provides $Y_{win}$ and a NIZK proof of well-formedness to the Party.
   • Both parties lock their funds into timelocked scripts controlled by a temporary key pair (generated via a 2-party DKG protocol).

2. Claim Dealer (OPRF Evaluation as a Service):

   • The Party selects a guess $y_{gss}$ and sends a blinded OPRF request to the Dealer.
   • The Dealer evaluates the OPRF, encrypts the result under an ephemeral key $Z$, and provides the ciphertext along with a NIZK proof of correctness.
   • Crucially, the Dealer also pre-signs the Party's payment transaction using $Z$ as the adaptor statement.
   • The Dealer adapts this pre-signature using the decryption key $z$ (the witness for $Z$) and broadcasts the transaction to claim the Party's payment.
   • Atomicity: The Party can only extract $z$ from the on-chain signature after the Dealer has been paid. $z$ is required to decrypt the OPRF response.

3. Claim Party:

   • The Party extracts $z$, decrypts the OPRF response, and computes the candidate witness $y'_{win}$.
   • If $y'_{win}$ matches the winning witness (i.e., $y_{gss} = y_{tgt}$), the Party adapts the Dealer's pre-signature to claim the reward.
   • If the guess is incorrect, the Party learns nothing useful for adaptation.

4. Timeout/Refund:

   • If the Dealer fails to claim payment within a timeout, the Party refunds their locked funds.
   • If the Party fails to claim the reward within a timeout, the Dealer refunds their locked funds.

Well-Formedness Proofs

A critical technical contribution is proving that $Y_{win}$ corresponds to a valid OPRF evaluation on a value within the correct domain, without revealing the target. The authors propose two instantiations:

• Bulletproofs: Uses R1CS constraints to prove the structure of the 2HashDH OPRF. It offers constant proof size and verification time but requires instantiating random oracles.
• Cut-and-Choose: A technique where the Dealer provides multiple instances, and the Party verifies a random subset. The authors modify the OPRF to allow opening instances without revealing the target value, ensuring the winning probability remains exactly $1/m$ even if the Dealer cheats. This approach is more efficient for high winning probabilities ($p \ge 1/2^{12}$).

3. Key Contributions

• New Primitive: Introduction of probabilistic atomic swaps, formally defined via an ideal functionality that generalizes deterministic atomic swaps to probabilistic outcomes.
• Minimal On-Chain Footprint: The protocol requires only standard Bitcoin scripts (signatures and timelocks). It does not require complex smart contracts or new opcodes, making it immediately deployable on Bitcoin, Litecoin, and other chains supporting atomic swaps.
• OPRF Evaluation for Payments: The authors develop a novel mechanism for the atomic exchange of OPRF evaluations tied to payments. This ensures the Dealer is paid before the Party learns the outcome, preventing bias. This tool is noted as having independent interest for applications like payment-driven rate limiting.
• Formal Security: The protocol is proven secure in the simulation-based model against static corruptions, satisfying the properties of probabilistic atomicity (fairness, no bias, and atomicity).
• Practical Implementation: A complete implementation in Rust, tested on Bitcoin and Litecoin testnets, and a variant for the Lightning Network (using HTLCs and off-chain link proofs).

4. Results and Benchmarks

• Testnet Deployment: The authors successfully executed cross-chain probabilistic swaps between Bitcoin and Litecoin testnets. A complete winning swap involved exactly four standard Taproot transactions.
• Transaction Size: Each transaction was approximately 575 Weight Units (WU).
• Performance:
  • Bulletproofs: Proving time $\approx 5.6$s, verification $\approx 0.35$s, proof size $\approx 2.8$KB (constant regardless of probability).
  • Cut-and-Choose: Proving time is faster for small $\ell$ (e.g., $0.27$s for $\ell=10$) but scales exponentially with the domain size. For $\ell=16$, proving takes $\approx 16$s with a 16MB proof.
  • Lightning Prototype: An HTLC-based variant was implemented, with a total online execution time of roughly 1.30s for three rounds (including precomputation).
• Cost: Fees were comparable to standard atomic swaps (e.g., 1550 sat for a 616WU funding transaction on Bitcoin testnet).

5. Significance and Claims

The paper claims that probabilistic atomic swaps solve a fundamental limitation of classical atomic swaps by enabling trustless, decentralized exchanges with randomized outcomes. The significance lies in:

• Enabling New Use Cases: Realizing the vision of "OP_RAND" on Bitcoin, allowing for wagers, lotteries, and probabilistic cross-chain trades without trusted houses.
• Preserving Privacy and Fungibility: By avoiding complex scripts, the protocol's on-chain footprint is indistinguishable from ordinary atomic swaps, preserving the privacy and fungibility of the assets.
• Accessibility: The reliance on minimal script support makes the protocol deployable on a wide range of existing blockchains and Layer-2 networks (like the Lightning Network, once PTLCs are active or via HTLC variants).
• Security: The protocol provides rigorous cryptographic guarantees that the outcome is unbiased and follows the advertised probability, even in the presence of malicious actors, without requiring a trusted third party.

The authors explicitly note that while their protocol supports asymmetric probabilistic swaps (one party pays for a chance), two-sided probabilistic swaps (where both parties have probabilistic outcomes) are likely impossible on minimal blockchains due to inherent asymmetries in sequential decision-making, a limitation they discuss but do not attempt to overcome.