💻 computer science

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

Dieses Paper führt „Split Tallies“ ein, ein Verfahren zur Auditierung mit konstantem Speicherbedarf, das dynamische geordnete Mengen, die von einer nicht vertrauenswürdigen Partei verwaltet werden, durch die Verfolgung maximaler Lücken mittels eines diskreten Zertifikatskalküls verifiziert, wobei eine Sicherheit mit hoher Wahrscheinlichkeit gegen rechnerisch unbegrenzte Angreifer erreicht wird, während gleichzeitig bewiesen wird, dass eine solche Effizienz ohne verborgene Zufälligkeit oder Zeitstempel unmöglich ist.

Ursprüngliche Autoren: Faruk Alpay, Levent Sarioglu

Veröffentlicht 2026-06-12

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Faruk Alpay, Levent Sarioglu

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben einen sehr klugen, aber potenziell unehrlichen Bibliothekar (den Maintainer), der eine Bibliothek mit perfekt geordneten Büchern verwaltet. Sie (der User) stellen Fragen wie „Ist Buch X hier?“ oder „Welches Buch steht direkt vor Y?“. Der Bibliothekar antwortet sofort. Sie vertrauen jedoch nicht dem internen Gedächtnis des Bibliothekars und können nicht jedes Mal die Regale überprüfen, wenn Sie eine Frage stellen, da dies zu langsam wäre.

Sie benötigen einen Weg, um später zu verifizieren, dass jede Antwort des Bibliothekars tatsächlich korrekt war, ohne dass Sie die gesamte Bibliothek selbst im Gedächtnis behalten müssen.

Dieses Paper stellt ein System namens Split Tallies vor, um dieses Problem zu lösen. Es nutzt eine geschickte Mischung aus alter Buchhaltungshistorie und moderner Mathematik, um ein „Zertifikat“ zu erstellen, das beweist, dass der Bibliothekar die Wahrheit sagt, während es auf Ihrer Seite fast keinen Speicherplatz beansprucht.

Hier ist die Funktionsweise, unterteilt in einfache Konzepte:

1. Die antike Metapher: Der gespaltene Stock (The Split Stick)

Die Idee ist inspiriert von den 600 Jahre alten englischen „Tally Sticks“ (Kerbstöcken).

Die Geschichte: Wenn ein Kaufmann einem Bauern Geld lieh, schnitt er Kerben in einen Holzstock, um den Betrag darzustellen. Dann spaltete er den Stock der Länge nach. Der Kaufmann behielt die eine Hälfte (den Stock) und der Bauer die andere (die Foil).
Die Magie: Wenn es Zeit zur Rückzahlung war, legte man die beiden Hälften zusammen. Nur der echte Stock würde perfekt passen, da die Maserung des Holzes und die Kerben übereinstimmten. Ein gefälschter Stock würde niemals passen.
In diesem Paper:
- Der Bibliothekar hält die „Foil“ (sein internes Gedächtnis der Bibliothek).
- Der Auditor (Sie) hält den „Stock“ (eine geheime Liste von 5 Zahlen).
- Der Public Tally ist eine Liste von „Kerben“, die der Bibliothekar nach jeder einzelnen Aktion aufschreiben muss.
- Das Audit ist der Moment, in dem Sie prüfen, ob die Geschichte des Bibliothekars mit Ihrer geheimen Liste übereinstimmt.

2. Der Kern-Trick: „Lücken“ statt Bücher verfolgen

Die meisten Menschen denken bei einer Bibliothek an eine Liste von Büchern. Dieses Paper sagt: „Nein, denken Sie an die leeren Räume zwischen den Büchern.“

Stellen Sie sich vor, das Bibliotheksregal hat einen Anfang (0) und ein Ende (U).
Wenn das Regal leer ist, gibt es eine einzige riesige Lücke vom Anfang bis zum Ende.
Wenn Sie ein Buch hinzufügen, spalten Sie diese große Lücke in zwei kleinere Lücken auf.
Wenn Sie ein Buch entfernen, verschmelzen Sie zwei Lücken wieder zu einer.

Das Paper beweist, dass, wenn man genau weiß, wie die Lücken miteinander verbunden sind, man genau weiß, wo sich jedes Buch befindet. Der Bibliothekar sagt nicht nur „Buch X ist hier“; er muss die spezifische ID der Lücke angeben, die dies beweist.

3. Die Regeln des Spiels (Die „Indenture“)

Um den Bibliothekar am Lügen zu hindern, zwingt das System ihn, strengen Regeln zu folgen, vergleichbar mit einem Stuhlkreisspiel mit striktem Timing:

Die öffentliche Uhr (The Public Clock): Jedes Mal, wenn eine neue Lücke entsteht (ein Buch hinzugefügt wird), erhält sie eine eindeutige, sequentielle ID-Nummer (wie einen Zeitstempel).
Die Zitierregel (The Citation Rule): Wenn der Bibliothekar eine Frage beantwortet, muss er die ID der Lücke angeben, die er verwendet.
- Wichtige Regel: Sie können nur eine Lücken-ID zitieren, die vor diesem Moment erstellt wurde. Sie können keine „zukünftige“ ID zitieren.
Die geheime Mathematik: Der Auditor (Sie) hält eine geheime Zahl. Jedes Mal, wenn eine Lücke geboren wird oder verwendet wird, multipliziert der Auditor seine geheimen Zahlen mit einer mathematischen Formel, die diese Lücken-ID beinhaltet.
- Wenn der Bibliothekar ehrlich ist, geht die Mathematik am Ende perfekt auf.
- Wenn der Bibliothekar lügt (z. B. behauptet, ein Buch sei vorhanden, obwohl es nicht da ist), muss er eine Lücken-ID fälschen. Da er Ihre geheime Zahl nicht kennt, wird die Mathematik am Ende mit an Sicherheit grenzender Wahrscheinlichkeit fehlschlagen.

4. Warum es so effizient ist

Das Paper behauptet, dass dieses System unglaublich leichtgewichtig ist:

Für Sie (den Auditor): Sie müssen nur 5 Zahlen und ein „Flag“ (einen Ja/Nein-Schalter) im Gedächtnis behalten. Sie müssen nicht die Bibliothek, die Bücher oder die Historie speichern. Sie beobachten lediglich den Strom der Kerben.
Für den Bibliothekar: Er benötigt nur ein wenig zusätzlichen Platz (eine zusätzliche Zahl pro Buch), um die Lücken-IDs zu speichern.
Die Kosten: Wenn der Bibliothekar versucht zu betrügen, ist die Chance, dass er damit durchkommt, astronomisch gering (weniger als 1 zu einer Billion bei einer Million Operationen).

5. Die „unmöglichen“ Teile

Die Autoren haben auch bewiesen, dass man dieses System nicht einfacher machen kann, ohne es zu zerstören:

Keine Zufälligkeit? Wenn man keine geheime Zufallszahl verwendet, kann ein cleverer Lügner Sie immer täuschen.
Keine Geheimhaltung? Wenn der Bibliothekar Ihre geheime Zahl kennt, kann er die Mathematik fälschen.
Keine Zeitlimits? Wenn der Bibliothekar erlaubt ist, „zukünftige“ IDs zu zitieren (Zeitreisen), kann er eine perfekte Fake-Bibliothek erstellen, die echt aussieht. Die „Uhr“-Regel ist essenziell, um dies zu verhindern.

6. Der „Rebalancing“-Bonus

Bibliotheken müssen manchmal die Regale neu organisieren (einen vollen Abschnitt in zwei teilen oder zwei leere Abschnitte zusammenführen). Das Paper zeigt, dass selbst diese chaotischen Reorganisationsschritte auditiert werden können. Sie haben bewiesen, dass die Gesamtzahl der „Moves“ (Bewegungen), egal wie oft der Bibliothekar die Regale neu organisiert, vorhersehbar ist. Der Auditor kann einfach die „Quittungen“ des Bibliothekars für diese Bewegungen zählen, um sicherzustellen, dass er nicht zusätzliche Arbeit verrichtet, um eine Lüge zu vertuschen.

Zusammenfassung

Dieses Paper baut einen mathematischen Lügendetektor für dynamische Listen.

Der Bibliothekar erledigt die Arbeit.
Der Auditor tut fast gar nichts (nur 5 Zahlen).
Der Tally ist ein öffentliches Protokoll von „Kerben“.
Das Ergebnis: Sie können mit nahezu 100-prozentiger Sicherheit verifizieren, dass jede Antwort korrekt war, selbst wenn der Bibliothekar ein Supercomputer ist, der versucht, Sie zu täuschen, und selbst wenn Sie fast keinen Speicherplatz haben, um die Daten zu speichern.

Es ist wie das Überprüfen eines Kontostands durch einen einzigen Beleg, der beweist, dass die Rechnung aufgeht, anstatt jede einzelne Münze im Tresor zu zählen.

Technisches Resümee: Split Tallies: Ein diskreter Zertifikats-Kalkül zur Auditierung dynamischer geordnetter Mengen in konstanter Speichergröße

Problemstellung

Die Arbeit befasst sich mit der Verifizierung von dynamischen geordneten Mengen, die von einer adversariellen Partei (dem „Maintainer“) verwaltet und von einem Konsumenten abgefragt werden. In vielen modernen Computing-Szenarien befinden sich Datenstrukturen in vertrauenswürdigen Umgebungen (z. B. Remote-Services, opake Hardware-Beschleuniger oder bezogene Bibliotheken). Der Konsument führt Operationen aus (Einfügen, Löschen, Mitgliedschaftstests, Vorgänger-/Nachfolgerabfragen und Extremum-Abfragen) und erhält die Antworten unmittelbar, wobei er ohne Verzögerung auf sie reagiert.

Die zentrale Herausforderung besteht darin, ein Korrektheitszertifikat für die gesamte Historie der Operationen bereitzustellen, ohne dass der Konsument (der „Auditor“) die Datenstruktur selbst speichern oder die Operationen erneut ausführen muss. Der Auditor muss passiv sein und lediglich eine konstante Menge an Zustand speichern (speziell fünf Maschinewörter und ein Flag), während der Maintainer für jede Operation einen kurzen „Notch“ (Datensatz) an eine öffentliche, append-only-Sequenz namens Tally anhängt. Das Ziel ist es, mit hoher Wahrscheinlichkeit zu erkennen, ob der Maintainer jemals eine falsche Antwort gegeben hat, selbst wenn der Maintainer über unbegrenzte Rechenleistung verfügt und seine Strategie basierend auf der sichtbaren Historie anpasst.

Methodik

Die vorgeschlagene Lösung, bezeichnet als Split Tallies, ist von historischen hölzernen Kerbstäben inspiriert, bei denen eine Schuld durch Kerben in einem Stab dokumentiert wurde, der anschließend der Länge nach gespalten wurde. Der Gläubiger behielt den „Stock“ (den Stamm) und der Schuldner den „Foil“ (die Folie); bei der Abrechnung wurden die Hälften ineinandergefügt, um die Authentizität zu verifizieren. In diesem digitalen Kontext bedeutet dies:

Die Tally: Ein öffentlicher Strom von Kerben, die vom Maintainer angehängt werden.
Der Stock: Der private Zustand des Auditors (fünf Wörter und ein Flag).
Die Foil: Die interne Buchführung der Struktur des Maintainers.
Das Audit: Der Prozess des „Ineinanderfügens“ (Meshing) des Stocks gegen die Foil (offengelegt am Ende einer Sitzung).

Der Gap-Kalkül (Lücken-Kalkül)

Der technische Kern der Arbeit ist ein diskreter Kalkül der Lücken (Gaps). Anstatt die Menge $S$ direkt zu auditieren, auditiert das System die Familie der maximalen leeren Intervalle (Lücken), die das Universum partitionieren.

Repräsentation: Eine Menge $S$ über einem Universum $\{1, \dots, U\}$ wird eindeutig durch eine ineinandergreifende Kette von Lücken $\langle a, b \rangle$ repräsentiert, die die Sentinels $0$ und $U+1$ verbinden.
Normalform: Die Arbeit beweist, dass diese Lückenfamilie der eindeutigen unitären Pfad von $0$ nach $U+1$ in einem intervall-azyklischen Graphen entspricht.
Rewrites (Umschreibungen): Operationen werden als lokale Umschreibungen dieses Pfades modelliert:
- Einfügen (Insertion): Spaltet eine Lücke $\langle a, b \rangle$ in zwei Lücken $\langle a, x \rangle, \langle x, b \rangle$ auf.
- Löschen (Deletion): Verschmilzt zwei benachbarte Lücken $\langle a, x \rangle, \langle x, b \rangle$ zu einer $\langle a, b \rangle$ .
- Abfragen (Queries): Werden dadurch beantwortet, dass eine spezifische Lücke (z. B. die Lücke, die $x$ enthält, für die Mitgliedschaft, oder die Lücke, die bei $x$ beginnt, für den Vorgänger) ausgewiesen wird.

Die Indenture-Disziplin

Um diese Umschreibungen zu auditieren, ohne den Zustand zu speichern, verwendet der Auditor einen Fingerprinting-Mechanismus basierend auf dem Identitätstest von Polynomen über einem endlichen Körper $\mathbb{F}_p$ :

Codes und Zeitstempel: Jede Geburtsstunde einer Lücke wird mittels eines öffentlichen Zählers $\kappa$ einem eindeutigen Code (Zeitstempel) zugewiesen.
Zitate (Citations): Jede Operation muss die Codes der Lücken zitieren, die sie konsumiert (umschreibt).
Akkumulatoren: Der Auditor unterhält zwei Akkumulatoren, $A$ $A$ (für Geburten) und $R$ $R$ (für Konsumtionen). Für eine Lücke mit Code $c$ $c$ und Endpunkten $a, b$ $a, b$ wird der Wert $\nu(a, b, c)$ $ν (a, b, c)$ in den Körper abgebildet.
- Bei Geburt: $A \leftarrow A \cdot (z - \nu(a, b, c))$
- Bei Konsumtion: $R \leftarrow R \cdot (z - \nu(a, b, c))$
- Hierbei ist $z$ ein geheimes Element des Körpers, das der Auditor vor der Sitzung wählt.
Verifizierung: Beim Audit offenbart der Maintainer die aktuelle Menge der Lücken mit ihren Codes. Der Auditor prüft, ob die offengelegten Lücken ineinandergreifen (eine gültige Kette bilden) und verifiziert, ob $A = R$ gilt.

Schlüsselmechanismen

Temporale Regel: Ein zitierter Code muss strikt kleiner als der Zählerstand zu Beginn des Ereignisses sein. Dies verhindert, dass der Maintainer „zukünftige“ Codes leiht, um ein balanciertes Ledger vorzutäuschen.
Forcing (Erzwingung): Aufgrund der Eindeutigkeit des Lückenpfades ist die korrekte Antwort auf jede Abfrage eine erzwungene Funktion der zitierten Lücke. Wenn der Maintainer eine Lücke zitiert, die nicht existiert oder nicht aktiv ist, wird die Antwort inkonsistent mit den Eigenschaften der Lücke sein oder das Ledger wird unbalanciert.

Zentrale Beiträge und Ergebnisse

1. Das Audit-Theorem (Korrektheit und Sicherheit)

Die Arbeit etabliert, dass das Schema perfekt vollständig (ehrliche Maintainer werden immer akzeptiert) und $\epsilon$ -sicher ist.

Fehlerrate (Soundness Error): Wenn ein Maintainer auch nur eine einzige falsche Antwort unter $T$ Operationen gibt, beträgt die Wahrscheinlichkeit der Akzeptanz höchstens $(4T + 1)/p$ .
Parameter: Mit einem 61-Bit-Primzahl $p$ (z. B. $2^{61}-1$ ) liegt die Fehlerrate bei Sitzungen von bis zu einer Million Operationen unter $2^{-38}$ .
Annahmen: Es sind keine rechnerischen Härteannahmen erforderlich; die Sicherheit ist informationstheoretisch gegenüber einem unbeschränkten Adversariellen.

2. Unmöglichkeit und Notwendigkeitsergebnisse

Die Arbeit beweist, dass die spezifischen Designentscheidungen unentbehrlich sind:

Deterministischer Boden: Jeder deterministische Auditor mit End-of-Session-Sicherheit muss mindestens $2n - \log_2(2n+1)$ Bits an Zustand für eine Menge der Größe $n$ speichern. Dies beweist, dass Zufälligkeit eine Voraussetzung ist und keine bloße Bequemlichkeit.
Geheime Zufälligkeit: Wenn die Zufallszahlen des Auditors für den Maintainer sichtbar sind, wird die Fehlerrate 1 (der Maintainer kann jederzeit ein gefälschtes Protokoll erstellen). Die Geheimhaltung des Auswertungspunktes $z$ ist notwendig.
Notwendigkeit der Temporalen Regel: Ohständen der Regel, die das Zitieren zukünftiger Codes verhindert, existiert eine explizite Drei-Operationen-Fälschung, die ein exaktes Gleichgewicht erreicht und mit einer Wahrscheinlichkeit von 1 akzeptiert wird.

3. Implementierung des Maintainers

Die Arbeit liefert eine konkrete Implementierung unter Verwendung eines blattorientierten (2, 4)-Baums:

Komplexität: Operationen laufen in $O(\log n)$ Worst-Case-Zeit.
Overhead: Die Struktur benötigt nur ein zusätzliches Wort pro Element (um den Lückencode zu speichern).
Auditierte Rebalancing-Prozesse: Die Arbeit führt einen Attestations-Umschlag (Attestation Envelope) ein, der beweist, dass die Anzahl der strukturellen Ereignisse (Splits, Fusions, Shares) über $m$ Updates hinweg höchstens $2m$ beträgt. Diese Grenze wird durch den Auditor zertifiziert, der die vom Maintainer angehängten One-Word-Attestationen zählt, wodurch amortisierte Analyse in eine öffentlich verifizierbare Behauptung umgewandelt wird.

4. Checkpoints und Epochen

Das Protokoll unterstützt beliebige Checkpoints. Audits können jederzeit durchgeführt werden, und akzeptierte Epochen können mit additiven Fehlerschranken verkettet werden. Dies ermöglicht es, die Latenz der Erkennung zu steuern (z. B. Auditierung nach jeder Operation für hohe Sicherheit oder seltener für Effizienz).

Bedeutung und Umfang

Die Arbeit beansprucht, eine geschlossene Bilanz für das Constant-Memory-Auditing dynamischer geordneter Mengen zu liefern. Ihre Bedeutung liegt in:

Paradigmenwechsel: Der Übergung von „Isolations-Tests“ hin zu „Zertifizierung, die mit der Ausführung mitreist“.
Informationstheoretische Garantien: Erreichung der Verifizierung ohne kryptographische Annahmen (wie Merkle-Trees oder digitale Signaturen), stattdessen unter Nutzung algebraischer Eigenschaften von Polynomen und der kombinatorischen Struktur geordneter Mengen.
Explizite Konstanten: Alle Parameter (Primzahlgrößen, Wortanzahlen, Fehlerraten) sind explizit und für die praktische Anwendung kalibriert (z. B. Einpassen in 64-Bit-Wörter).

Der Umfang beschränkt sich strikt auf die Sieben-Operationen-Schnittstelle (Insert, Delete, Member, Pred, Succ, Min, Max). Die Arbeit stellt explizit fest, dass der Lücken-Kalkül die Anordnung (Adjazenz, Klammerung, Extremität) zertifiziert, aber nicht auf aggregierte Eigenschaften wie den Rang erweitert werden kann, da diese nicht lokal zu einer einzelnen Lücke sind. Die Erkennung ist retrospektiv; die Arbeit räumt ein, dass die Online-Erkennung (sofortige Ablehnung einer Antwort) in diesem informationstheoretischen Setting eine anerkannte Grenze darstellt, die mit der Existenz von Einwegfunktionen verknüpft ist, und somit die vorgeschlagene Lösung innerhalb ihres definierten retrospektiven Modells optimal ist.