Range Proofs und Bulletproofs+

Beweisen, dass eine verborgene Zahl zwischen 0 und 2⁶⁴ liegt, ohne sie preiszugeben

Die Idee: die Zahl in Bits zerlegen

Eine Zahl in [0, 2⁶⁴) besteht aus 64 Bits: v = b₀·1 + b₁·2 + b₂·4 + … + b₆₃·2⁶³, wobei jedes bᵢ ∈ {0, 1}. Beweist du, dass (1) jedes bᵢ wirklich 0 oder 1 ist und (2) die gewichtete Summe der Bits gleich v ist, dann liegt v sicher im Bereich.

Die Bedingung „ist ein Bit“ ist algebraisch: bᵢ·(bᵢ − 1) = 0. Die Aufgabe wird also: beweisen, dass eine Menge verborgener Zahlen eine Menge von Gleichungen erfüllt, ohne die Zahlen preiszugeben.

Entwicklung in Monero

Der Umstieg auf Bulletproofs 2018 machte Transaktionen etwa 10× kleiner und senkte die Gebühren im selben Maß. Eines der spürbarsten Upgrades in der Geschichte von Monero.

Wie Bulletproofs funktioniert (Intuition)

1. Der Beweisende legt sich mit einem einzigen Vektor-Pedersen-Commitment auf den Bitvektor a_L und den Vektor a_R = a_L − 1 fest.
2. Der Prüfer schickt (über einen Hash, Fiat–Shamir) zufällige Challenges y, z. Alle 64 „ist ein Bit“-Bedingungen und die „Summen“-Bedingung werden zu einer einzigen Gleichung mit innerem Produkt ⟨l, r⟩ = t zusammengeklebt. Die zufälligen Challenges sorgen dafür, dass man die zusammengeklebte Gleichung nicht fälschen kann, ohne alle ursprünglichen zu erfüllen.
3. Ein inneres Produkt von Vektoren der Länge n wird rekursiv bewiesen: In jedem Schritt werden die Vektoren mit einer neuen Challenge „in der Mitte gefaltet“, und nach log₂ n Schritten bleibt je eine Zahl übrig. Jeder Schritt sendet 2 Punkte – daher die logarithmische Größe.

Aggregation: Für m Outputs haben die Vektoren die Länge 64·m, und die Größe wächst nur um 2·log₂ m Punkte. Deshalb begrenzt Monero die Outputs pro Transaktion auf 16 und füllt auf eine Zweierpotenz auf.

Vor- und Nachteile