Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

Computer Science > Data Structures and Algorithms [Submitted on 11 Jun 2026] Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory Faruk Alpay, Levent Sarioglu We study retrospective auditing for dynamic ordered sets maintained by an untrusted party. A passive auditor watches insert, delete, membership, predecessor, successor, min, and max operations, stores five machine words and a flag, and receives a constant-size public tally record per operation. At audit time the maintainer discloses the claimed live vacant intervals. The method represents order semantics by maximal gaps: gaps are born, cited, consumed, and timestamped, while two hidden field accumulators test equality of the birth and consumption ledgers. Honest executions are accepted with probability one. If any answer in a T-operation session is wrong, acceptance occurs with probability at most (4T+1)/p over one secret field element, against computationally unbounded maintainers. We prove that deterministic and visible-coin auditors require linear state, and that removing the timestamp rule permits an exact replay forgery. A leaf-oriented (2,4)-tree implements the maintainer in O(log n) worst-case time per operation with one extra word per element, and its rebalancing events admit an auditable O(m) envelope over m updates. Checkpoint audits compose with additive error. Comments: 22 pages, 2 figures, 3 tables Subjects: Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR) MSC classes: 68P05, 68W20, 68W40 Cite as: arXiv:2606.13272 [cs.DS]   (or arXiv:2606.13272v1 [cs.DS] for this version)   https://doi.org/10.48550/arXiv.2606.13272 Focus to learn more Submission history From: Levent Sarioglu [view email] [v1] Thu, 11 Jun 2026 12:25:43 UTC (31 KB) Access Paper: HTML (experimental) view license Current browse context: cs.DS < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.CR References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)