Bulletproofs uitgelegd: zo worden verborgen bedragen gecontroleerd

Bulletproofs zijn de korte zero-knowledge range proofs waarmee een cryptovaluta elk transactiebedrag kan verbergen terwijl elke node toch controleert dat er geen munten zijn bijgemaakt. Deze gids legt Pedersen-commitments uit, waarom verborgen bedragen range proofs nodig hebben, hoe Bulletproofs die bewijzen klein houden en hoe Blocknet ze op elke output gebruikt.

Wat zijn Bulletproofs?

Het artikel, Bulletproofs: Short Proofs for Confidential Transactions and More, verscheen in 2018 op het IEEE Symposium on Security and Privacy. De auteurs ontwierpen ze voor vertrouwelijke transacties, waarbij bedragen op een blockchain worden vervangen door commitments. Om te zien waarom zo’n bewijs überhaupt nodig is, begin je bij de commitment.

Wat is een Pedersen-commitment?

Een commitment is de cryptografische versie van een verzegelde envelop. Je stopt er een getal in, laat iedereen de envelop zien en kunt later bewijzen wat erin zat. Niemand kan het getal uit de envelop aflezen, en je kunt er achteraf geen ander getal in stoppen.

Een Pedersen-commitment, in 1991 beschreven door Torben Pedersen, doet dit met punten op een elliptische curve. Om zich vast te leggen op een bedrag v, kiest een wallet een willekeurig geheim r, de blinding factor, en berekent:

C = v·G + r·H

G en H zijn twee vaste openbare punten op de curve, zo gekozen dat niemand weet hoe het ene als veelvoud van het andere te schrijven is. Het resultaat C is één punt van 32 bytes. Het heeft twee eigenschappen:

• Verbergend. Omdat r willekeurig is, ziet C eruit als een willekeurig punt. Hetzelfde bedrag twee keer vastleggen geeft twee losse commitments, en de commitment alleen vertelt een waarnemer niets over v.
• Bindend. Zodra C is gepubliceerd, kan de wallet hem niet openen naar een ander bedrag. Daarvoor zou het discrete-logaritmeprobleem op de curve moeten worden opgelost.

Hoe kunnen nodes een transactie controleren die ze niet kunnen lezen?

Twee commitments optellen geeft (v1 + v2)·G + (r1 + r2)·H, wat zelf een commitment op v1 + v2 is. De verzender kiest de blinding factors zo dat de totale blinding van de inputs gelijk is aan die van de outputs. Kloppen de bedragen ook, dan is het verschil tussen de som van de inputs en de som van de outputs precies nul, en elke node kan dat controleren.

De netwerkfee is het enige openbare getal in een transactie. Nodes maken er een commitment van met een blinding factor van nul en tellen die op bij de kant van de outputs, dus de controle luidt: inputs = outputs + fee.

Waarom hebben verborgen bedragen range proofs nodig?

Rekenen met commitments gebeurt modulo een heel groot getal, de orde van de curvegroep, die ongeveer 2^252 is. In die rekenkunde is een “negatief” bedrag gewoon een enorm positief bedrag. Iemand zou een input van 10 munten kunnen uitgeven en twee outputs kunnen maken, een van 11 en een van “min 1”. De commitments zouden perfect kloppen, en er zou 1 munt uit het niets verschijnen, verborgen voor elke waarnemer.

Een range proof dicht dat gat. Het bewijst dat het bedrag in een commitment tussen 0 en 2^64 ligt, zonder te zeggen wat het is. Als elke output zo begrensd is, kunnen een handvol outputs nooit optellen tot een getal dat groot genoeg is om rond de groepsorde te lopen, dus kloppende commitments betekenen kloppende bedragen.

Eerdere ontwerpen voor vertrouwelijke transacties gebruikten range proofs die lineair groeiden met het aantal bits. Bulletproofs groeien alleen met de logaritme, waardoor een bewijs van 64 bits terugvalt naar een paar honderd bytes.

Hoe werken Bulletproofs?

Een Bulletproof bewijst een bereik in drie stappen.

1. Splits het bedrag in bits. Een bedrag van 64 bits wordt een vector van 64 bits. De bewijzer legt zich vast op die vector en laat er twee feiten over zien: elk element is 0 of 1, en de bits, gewogen met machten van twee, tellen op tot het vastgelegde bedrag.
2. Maak van die feiten één inproduct. Met willekeurige challenges vouwt de bewijzer al die voorwaarden samen tot één bewering over het inproduct van twee vectoren. Omdat de challenges willekeurig zijn, komt een onjuiste bewering er alleen met een verwaarloosbare kans door.
3. Bewijs het inproduct door te halveren. Elke ronde stuurt de bewijzer twee curvepunten, L en R, en beide vectoren worden tot de helft van hun lengte gevouwen. Na log2(64) = 6 rondes blijft er één paar getallen over.

Dat halveren verklaart de grootte. De samenvatting van het artikel noemt voor een range proof over een bereik van n bits 2·log2(n) + 9 groeps- en veldelementen. Voor 64 bits zijn dat 12 punten uit de zes rondes plus nog 9, in totaal 21 elementen, of 672 bytes als elk element 32 bytes is.

Het bewijs is niet-interactief. In plaats van een live verifier die challenges stuurt, leiden beide kanten ze af door het transcript van het bewijs te hashen, een standaardtechniek die bekendstaat als de Fiat-Shamir-heuristiek. Bulletproofs hebben ook geen trusted setup nodig: de generatoren zijn openbaar en open afgeleid, en de veiligheid rust alleen op de discrete-logaritmeaanname. Meerdere bewijzen kunnen worden samengevoegd, wat maar een logaritmisch aantal elementen toevoegt, en verificatie kan in batches gebeuren.

Wie gebruikt Bulletproofs?

Monero zette Bulletproofs aan bij zijn netwerkupgrade van 18 oktober 2018 (de release v0.13.0) om transacties kleiner te maken. De Rust-bibliotheek bulletproofs van het project dalek-cryptography implementeert ze over de Ristretto-groep van Curve25519, en de cryptografiebibliotheek van Blocknet is daarop gebouwd.

Hoe verbergt Blocknet elk bedrag?

Bij Blocknet bevat elke output van elke transactie een Pedersen-commitment in plaats van een bedrag, en elke output heeft een eigen Bulletproof van 64 bits. Privacy maakt deel uit van het transactieformaat, zonder transparante modus, dus er is geen manier om een betaling met een zichtbaar bedrag te versturen.

Dit controleert een node voordat hij een transactie accepteert:

• Elke range proof. De Bulletproof van elke output moet kloppen met zijn commitment, wat bewijst dat het bedrag tussen 0 en 2^64 ligt. De bewijzen gebruiken een transcript met het label “Blocknet Range Proof”, dat elk bewijs aan Blocknet koppelt.
• De balans. Elke input heeft een pseudo-output-commitment, en de ringhandtekening bewijst dat die zich vastlegt op hetzelfde bedrag als de echte munt die wordt uitgegeven, zonder te onthullen welk ringlid dat is. De node controleert daarna of de pseudo-outputs optellen tot de outputs plus de fee.
• Nieuwe munten. De beloning van een blok volgt een openbaar schema, dus voor de geminede output bouwt de node de commitment na die hij voor die hoogte verwacht en controleert hij of die overeenkomt.

Je kunt dit zien op de Blocknet-explorer. Een transactiepagina toont de bedragen als “hidden · Pedersen commitments”, en elke output toont zijn commitment, een versleutelde memo en een range proof van “672 bytes · Bulletproof”, de grootte die de berekening hierboven voorspelt.

De ontvanger ziet nog steeds het echte bedrag. Elke output bevat het bedrag, versleuteld met het geheim dat de wallets van verzender en ontvanger delen, en de wallet van de ontvanger ontsleutelt het met de privé view key. Het bedrag is zichtbaar voor de twee mensen in de betaling en voor niemand anders.

Verborgen bedragen werken samen met de andere lagen van Blocknet: ringhandtekeningen over 16 outputs verbergen de verzender, eenmalige stealth-adressen verbergen de ontvanger, en Dandelion++ verbergt waar een transactie het netwerk binnenkwam. De gids over de privacyfuncties van Blocknet loopt ze allemaal door.

Verdien zelf wat privé BNT

Een eenvoudige manier om munten met verborgen bedragen te krijgen, is ze te minen. Blocknet gebruikt een geheugenintensieve Argon2id-proof-of-work die je op een gewone computer kunt minen, en seine minet hem op je CPU, met eventuele NVIDIA-GPU’s ernaast, en stemt zichzelf af zonder enige configuratie. Elke uitbetaling die bntpool.com je stuurt, komt binnen als privé output met een commitment en een Bulletproof. De mininghandleiding brengt je binnen een paar minuten van download naar geaccepteerde shares.