Probabilistic Proof of Aligned Storage via Suffix-Walk Overlap

Abstract

We present a lightweight, probabilistic mechanism for certifying aligned storage between participants in decentralized systems. Participants respond to randomized suffix queries by performing forward scans over their locally stored data and returning short response sequences. A verifier observes only overlap statistics between responses. We prove that the overlap probability is bounded above by the minimum storage density among participants, ensuring that high observed overlap implies all parties store a large fraction of the underlying dataset. This bound holds regardless of adversarial strategy: a single well-provisioned participant cannot "carry" an under-provisioned partner. The protocol's "+1" advancement rule introduces pointer desynchronization that causes naïve Binomial models to overestimate tail probabilities by 2–3×. We establish rigorous security bounds through systematic simulation of Poisson-walk dynamics. For example, observing 10 or more matches out of 12 recorded elements rules out minimum density below 0.6 at the 2.4% significance level. Independent repetition amplifies confidence exponentially. The mechanism requires no cryptographic commitments per element, no global verifier, and reveals only O(m) randomly-selected elements per interaction. We analyze several natural adversarial strategies—fabrication, selective answering, collusion, Sybil attacks—and show that none can increase overlap probability beyond what storage density allows. From a mechanism-design perspective, repeated suffix-walk interactions induce a game where aligned storage is the dominant strategy, enabling emergent consensus without central coordination. The protocol serves as a foundation for proof-of-aligned-storage in distributed systems and provides consensus weight based on demonstrated storage rather than computational power or stake. Throughout this paper, "proof" refers to statistical evidence under a well-validated probabilistic model, not a cryptographic zero-knowledge proof.