This report presents a detailed design for a privacy-preserving version of the "Best-Possible Unpredictable Proof-of-Stake" (PoS) protocol introduced in [Euro S&P 2025, ePrint 2021/660], leveraging the Commit-and-Prove paradigm as established in privacy-preserving PoS systems like Ouroboros Crypsinous [S&P 2019, ePrint 2018/1132]. The objective is to combine the best-possible unpredictability guarantee of the new PoS protocol with strong privacy for block producers and stakers, using modern zero-knowledge techniques.

1. Background: Best-Possible Unpredictable PoS

1.1 Motivation and Security Properties

Traditional PoS protocols (e.g., Ouroboros Praos, Snow White) suffer from varying degrees of predictability, which adversaries can exploit for attacks such as selfish mining and bribery. The protocol in [ePrint 2021/660] introduces a formal notion of "best-possible unpredictability," where a player only learns their eligibility to produce the next block at the moment it becomes relevant, and nothing about future rounds.

1.2 Impossibility for Single-Extension and the Multi-Extension Solution

The paper proves that no single-extension PoS protocol can achieve both best-possible unpredictability and the common prefix property unless the honest stake is at least 73%. To overcome this, the authors propose a multi-extension framework, where honest players may attempt to extend multiple chains in each round, specifically those within a certain "distance" D of the best chain.

1.3 The D-Distance-Greedy Strategy

Let D be a fixed positive integer. In each round, an honest player identifies the current longest chain and then considers all chains whose last D blocks share a prefix with this chain (i.e., are within distance D). The honest player attempts to extend all such chains. This approach maintains consistency among honest extensions and provably thwarts balance attacks, enabling the protocol to achieve best-possible unpredictability and security with as little as 57% honest stake, depending on D.

Formalization

• Distance Between Chains: For chains C1 and C2, the distance is the minimum ℓ such that removing the last ℓ blocks from C1 yields a prefix matching C2.
• D-Distance-Greedy Set: For the longest chain C, define S = {C' | distance(C, C') ≤ D}.
• Extension Rule: Honest players attempt to extend every chain in S each round.

Protocol Steps (Flat Model):

1. On receiving a new valid chain, append it to the local set.
2. Compute S = {C' | distance from longest chain C to C' ≤ D}.
3. For each C' in S:
   • Compute η = hash(C'[-1]).
   • Compute σ = uSign(SK, <η, r>).
   • If H(η, r, PK, σ) < T, create and broadcast new block B = (η, r, PK, σ) extending C'.

2. Privacy-Preserving Proof-of-Stake: Commit-and-Prove Paradigm

2.1 Commit-and-Prove Overview

The Commit-and-Prove paradigm is a foundational tool for privacy in cryptocurrencies and PoS protocols. It combines non-interactive commitments with non-interactive zero-knowledge (NIZK) proofs, enabling participants to prove statements (e.g., stake ownership, eligibility) without revealing sensitive information; see Improving Cryptarchia #1: Privacy Preserving Hybrid Consensus.

• Commitment: The participant cryptographically commits to their secret data (e.g., stake, key).