Bereichsbeweis (Range Proof)

Ein Range Proof (Bereichsbeweis) weist nach, dass ein per Commitment festgelegter Wert v in einem Intervall liegt, typischerweise [0, 2^n), ohne ihn offenzulegen. Es handelt sich um einen Sonderfall eines Zero-Knowledge-Beweises, der üblicherweise auf ein Commitment des Werts (etwa ein Pedersen-Commitment) angewendet wird. Der Beweisende belegt, dass die Binärdarstellung des Werts genau n Bits hat, jedes davon null oder eins, womit v nach oben durch 2^n begrenzt ist, ohne eines dieser Bits zu zeigen.

Die Referenzkonstruktion ist Bulletproofs (Bünz, Bootle, Boneh, Poelstra, Wuille und Maxwell, IEEE Symposium on Security and Privacy 2018), die das Problem als Inner-Product-Argument umformuliert und den Beweis auf eine in n logarithmische Größe komprimiert. Sie benötigt kein Trusted Setup, stützt sich allein auf die Annahme des diskreten Logarithmus, ist über Fiat-Shamir nicht-interaktiv und erlaubt die Aggregation mehrerer Beweise mit geringem Mehraufwand. Bulletproofs+ (Chung, Han, Ju, Kim und Seo) ist eine spätere Verbesserung mit noch kürzeren Beweisen.

Das ist aus zwei Gründen wichtig. Privatsphäre: Bei vertraulichen Transaktionen muss nachgewiesen werden, dass jeder verborgene Betrag nicht negativ ist, damit durch modularen Überlauf kein Wert aus negativen Beträgen entsteht. Und Solvenz: Ein Dienstleister kann nachweisen, dass seine Konten und Reserven in gültigen Bereichen liegen, ohne einzelne Salden zu veröffentlichen. Monero führte Bulletproofs im Oktober 2018 für seine Range Proofs ein und verringerte damit die Transaktionsgröße deutlich; das Liquid Network setzt sie in seinen Confidential Transactions ein.