Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel auditing method for dynamic ordered sets maintained by untrusted parties, utilizing a constant memory footprint while ensuring high reliability in audit outcomes. The approach leverages a discrete certificate calculus that tracks order semantics through maximal gaps and hidden field accumulators to verify the integrity of operations. Key results indicate that the proposed method achieves a probability of one for accepting honest executions, while maintaining robust security against incorrect outputs in a session involving T operations.
Auditors can now verify dynamic ordered sets with constant memory while achieving perfect reliability in honest executions, even against untrusted maintainers.
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.