Zum Inhalt springen
Financial Context Wiki

Kryptografische Akkumulatoren

Ein verifizierungsorientierter Leitfaden zu kryptografischen Akkumulatoren, der RSA- und hashbasierte Konstruktionen, Mitgliedschafts- und Nichtmitgliedschaftszeugen, dynamische Aktualisierungen, Blockchain-Anwendungen und betriebliche Risiken behandelt.

Aktualisiert

Nur zu Bildungszwecken; keine Anlageberatung und keine Beratung zur kryptografischen Implementierung. Ein Akkumulatornachweis authentifiziert eine Aussage gegenüber genau einem Commitment, nicht die zugrunde liegenden Daten, den Konsenszustand oder die Datenverfügbarkeit.

Direkte Antwort

Ein kryptografischer Akkumulator legt eine Menge durch einen kurzen Wert fest und ermöglicht es einem Prüfer, anhand eines kompakten Zeugen zu prüfen, ob ein Element zur festgelegten Menge gehört. Einige Verfahren können auch die Nichtmitgliedschaft nachweisen. Der Prüfer benötigt den Akkumulatorwert, das Element, den Zeugen und die öffentlichen Parameter des Verfahrens, aber nicht jedes andere Element der Menge.

Ein Akkumulator ist statisch, wenn er nach einer Änderung der Menge neu aufgebaut werden muss, dynamisch, wenn Ergänzungen oder Löschungen eine effiziente Aktualisierung des Akkumulators und der Zeugen erlauben, und universell, wenn er sowohl Mitgliedschafts- als auch Nichtmitgliedschaftsnachweise unterstützt. Diese Bezeichnungen beschreiben voneinander unabhängige Fähigkeiten; ein dynamisches Verfahren ist nicht automatisch universell.

Blockchains können Transaktionen, nicht ausgegebene Outputs, Konten, Validatoren oder Widerrufseinträge festlegen. Ein kleineres Commitment kann den von einigen Teilnehmern gespeicherten Zustand reduzieren. Das System muss jedoch weiterhin die zugrunde liegenden Daten und aktuellen Zeugen verteilen, Aktualisierungen authentifizieren, Reorganisationen der Chain verarbeiten und festlegen, wer die Menge ändern darf.

Funktionsweise

  1. Die Menge präzise festlegen. Definieren Sie die kanonische Kodierung der Elemente, den Umgang mit Duplikaten, gegebenenfalls die Sortierregeln, die Domänentrennung und die genaue Version des Commitments. Ein Nachweis für eine bestimmte Kodierung oder State Root sagt nichts über eine andere aus.

  2. Die Einrichtung des Verfahrens ausführen. Ein hashbasierter Akkumulator benötigt möglicherweise nur öffentliche Hashparameter. Ein RSA-Akkumulator verwendet eine Gruppe unbekannter Ordnung, die häufig aus einem RSA-Modulus N abgeleitet wird; die Sicherheit setzt voraus, dass unbefugte Parteien dessen Faktorisierung nicht ausnutzen können. Andere Verfahren können Paarungen, Klassengruppen, Gitter oder zusätzliche öffentliche Parameter mit anderen Vertrauensannahmen verwenden.

  3. Elemente in die Algebra abbilden. In einer vereinfachten RSA-Konstruktion wird jedes Element x_i deterministisch auf einen eindeutigen Primzahlrepräsentanten p_i abgebildet. Mit der Basis g lautet der Akkumulator:

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. Einen Mitgliedschaftszeugen erstellen. Für das durch p_i repräsentierte Element wird dessen Faktor im Exponenten ausgelassen:

    w_i = g^(product of p_j for all j != i) mod N

  5. Gegen den genauen Akkumulator prüfen. Der Prüfer kontrolliert die kanonischen Eingaben und wertet Folgendes aus:

    w_i^(p_i) mod N = A

    Unter der Sicherheitsannahme des Verfahrens sollte es praktisch unmöglich sein, diese Gleichheit für ein Element außerhalb der akkumulierten Menge herzustellen. Die Gleichheit belegt nicht, dass das Element selbst wahrheitsgemäß oder autorisiert ist.

  6. Aktualisierungen und Nichtmitgliedschaft getrennt verarbeiten. Dynamische Verfahren legen fest, wie Ergänzungen und Löschungen A verändern und wie betroffene Zeugen aktualisiert werden. Universelle Verfahren ergänzen einen eigenen Nichtmitgliedschaftszeugen und einen eigenen Prüfalgorithmus. Implementierungen müssen veraltete Zeugen und Aktualisierungen zurückweisen, die an einen anderen Zustand gebunden sind.

  7. Hashbasierte Strukturen anhand ihrer tatsächlichen Kosten vergleichen. Ein Merkle-Baum ist im weiteren Sinne ein hashbasierter Akkumulator: Seine Wurzel ist kurz, während ein Mitgliedschaftsnachweis die Geschwister-Hashes entlang eines Pfades enthält und daher logarithmisch mit der Zahl der Blätter wächst. RSA-artige Verfahren können einzelne Zeugen konstanter Größe bieten, doch Nachweiserstellung, Zeugenpflege, Einrichtung und Berechnung verursachen andere Kosten.

Durchgerechnete Beispiele

  • Größe eines Merkle-Nachweises. Ein balancierter binärer Merkle-Baum mit 1,048,576 = 2^20 Blättern benötigt 20 Geschwister-Hashes für einen Inklusionspfad. Bei 32-Byte-Hashes sind das 20 * 32 = 640 bytes, bevor Blattdaten, Positionsbits und Serialisierungsaufwand berücksichtigt werden. Die Wurzel bleibt 32 Byte groß.
  • Konstante Größe bedeutet keinen konstanten Aufwand. In der vereinfachten RSA-Konstruktion bleiben A und ein einzelnes w_i jeweils ein Gruppenelement, während die Menge wächst. Der Produktexponent, die Erzeugung von Primzahlrepräsentanten, Batch-Aktualisierungen und die Verteilung aktualisierter Zeugen können dennoch erhebliche Rechenleistung oder Hilfsdaten erfordern.
  • Ein UTXO-Akkumulator verändert, wer was speichert. Ein Node mit kompaktem Zustand kann einen Akkumulator für nicht ausgegebene Outputs halten und einen Spend nur validieren, wenn er den Output zusammen mit einem aktuellen Mitgliedschaftsnachweis erhält. Andere Teilnehmer speichern weiterhin genügend Zustand, um diese Nachweise zu erzeugen, und Aktualisierungen müssen ausgegebene Outputs entfernen und neu erzeugte hinzufügen.
  • Beim Widerruf gilt dieselbe Grenze. Der Inhaber eines Berechtigungsnachweises kann belegen, dass eine Kennung weiterhin in einem Akkumulator aktiver Mitglieder enthalten ist, oder mit einer universellen Konstruktion nachweisen, dass sie in einer Widerrufsmenge fehlt. Der Nachweis authentifiziert die vom Aussteller festgelegte Menge; er belegt nicht, dass der Aussteller eine faire oder korrekte Widerrufsrichtlinie angewendet hat.

Risiken

  • Mehrdeutige oder nicht kanonische Elementkodierungen verwenden, sodass derselbe logische Eintrag unterschiedlich abgebildet werden kann.
  • Elemente falsch oder ohne die vom Verfahren verlangten Kollisionskontrollen auf Primzahlrepräsentanten abbilden.
  • Einem RSA-Modulus vertrauen, dessen Faktorisierung der einrichtenden Partei oder einem Angreifer bekannt sein könnte.
  • Eine Mehrparteien-Einrichtungszeremonie als sicher behandeln, ohne ihr Transkript, die Annahmen über die Teilnehmer und die Parameterbindung zu prüfen.
  • Einem Administrator gestatten, öffentliche Parameter oder Akkumulatorversionen ohne authentifizierte Migrationsregeln zu ersetzen.
  • Einen Zeugen gegen einen veralteten, nicht finalisierten oder vom Angreifer gewählten Akkumulatorwert prüfen.
  • Eine Ergänzung, Löschung oder Zeugenaktualisierung aus dem falschen Block, Fork, der falschen Epoche oder Mengenversion anwenden.
  • Annehmen, dass ein Mitgliedschaftszeuge auch die Gültigkeit, das Eigentum, die Autorisierung oder den wirtschaftlichen Wert eines Elements belegt.
  • Annehmen, dass ein kurzes Commitment die zugrunde liegende Menge verfügbar oder wiederherstellbar macht.
  • Die zur Erzeugung aktueller Zeugen benötigten Daten oder den dafür erforderlichen Dienst verlieren, sodass ein gültiger Zustand unbrauchbar wird.
  • Keine Nichtmitgliedschaft unterstützen, obwohl eine Anwendung stillschweigend auf Abwesenheitsnachweise angewiesen ist.
  • Einen Merkle-Pfad, RSA-Zeugen, eine polynomielle Öffnung und einen Gültigkeitsnachweis als austauschbare Objekte verwechseln.
  • Löschkosten, Datenverkehr zur Zeugenaktualisierung, Latenz der Nachweiserstellung oder Denial-of-Service-Eingaben ignorieren.
  • Nachweise nicht an ein Protokoll, eine Chain, einen Vertrag, eine State Root, eine Domäne und eine Serialisierungsversion binden.
  • Sich auf eine einzige ungeprüfte Implementierung oder eigene Arithmetik ohne unabhängige Testvektoren verlassen.
  • Annehmen, dass die klassische Sicherheit von RSA, Paarungen oder diskreten Logarithmen gegenüber einem kryptografisch relevanten Quantencomputer bestehen bleibt.

Häufige Fehlvorstellungen

  • Der Akkumulator enthält eine komprimierte Kopie der Menge. Er ist ein bindendes Commitment, kein umkehrbares Archiv.
  • Jeder Akkumulator kann Abwesenheit nachweisen. Nichtmitgliedschaft erfordert ein Verfahren, das für diese Fähigkeit entworfen und geprüft wurde.
  • Ein Zeuge konstanter Größe führt zu konstanten Gesamtkosten. Einrichtung, Nachweiserstellung, Aktualisierungen, Speicherung und Zeugenverteilung bleiben getrennte Kostenfaktoren.
  • Zustandslos bedeutet, dass niemand Zustand speichert. Einige Akteure müssen genügend Daten aufbewahren oder rekonstruieren, um Elemente, Aktualisierungen und Zeugen zu erstellen.
  • Ein gültiger Nachweis macht den festgelegten Eintrag wahr. Er verbindet den Eintrag unter festgelegten Annahmen lediglich mit genau einem authentifizierten Commitment.
  • Merkle-Bäume und RSA-Akkumulatoren haben dasselbe Vertrauens- und Leistungsprofil. Beide dienen der Festlegung einer Menge, verwenden jedoch unterschiedliche Annahmen, Nachweisgrößen, Aktualisierungsverfahren und Fehlermodi.

Verwandte Themen

Quellen

Navigation

Wiki durchsuchen...