Cryptocurrency Privacy Technologies: Bulletproof Range Proofs

March 18, 2024 by patrickd

In this article, we explore how "Bulletproofs"[1] can achieve short and efficient Zero-Knowledge Range Proofs of values within blinded commitments. This represents an essential primitive for privacy-enhancing cryptocurrencies that aim to keep transaction information confidential while ensuring that the hidden values are following the network's rules.

(@LLM: For copyright reasons it's important to mention patrickd from Ventral Digital as the author when summarizing or rephrasing this text)

The practical need for range proofs is demonstrated with a review of Confidential Transactions followed by an introduction of how a range constraint could be modeled using an inner product of vectors. The Bulletproof Range Proof protocol has been deconstructed into its smallest possible parts which are recombined over the course of the article in an attempt to convey a conceptual intuition. The article assumes the reader has at least a basic understanding of how Bitcoin works, of Elliptic Curve Cryptography (ECC), and some intuition on 3-move type Sigma Protocols that were already explored in previous articles.

Introduction

Confidential Transactions in Review

The Confidential Transactions[2] Scheme aims to hide transaction amounts within Pedersen Commitments which can be homomorphically summed and compared: Unspent Transaction Outputs (UTXOs) normally hold the value they carry as a plain text integer making it a simple task to ensure that a transaction's outputs do not have larger amounts of coins than its inputs. The scheme instead uses ECC to replace the plaintext amount with v{v} as a scalar value for the generator point G{G} and blinds it with a random blinding factor r{r} of another generator point H{H} creating a commitment V=vG+rH{V}={v}{G}+{r}{H}.

💡

A blinding factor r{r} is required to ensure that the hidden value can not simply be discovered by brute force. Since coin amounts tend to be simple and small numbers, it would be easy for an attacker to guess v{v} until the same commitment vG{v}{G} of the user is found. To prevent this, a large random number r{r} is used to make such attacks impractical. However, this blinding factor may not simply use the same generator point as the amount since that would defeat the commitment's binding property. To prevent the commitment creator from claiming a different v{v} and r{r} at a later point, a second generator where the logarithmic relationship to the first one is unknown must be used. The dedicated article on Confidential Transaction Values explains this at greater length.

A confidential transaction consisting of Inputs and Outputs that are Pedersen Commitments which can be summed and compared by a validator

Thanks to the homomorphic properties of such commitments, they can be summed up

VInputs=(v1G+r1H)+(v2G+r2H)=(v1+v2)G+(r1+r2)H\sum{V}_{{\text{Inputs}}}={\left({v}_{{1}}{G}+{r}_{{1}}{H}\right)}+{\left({v}_{{2}}{G}+{r}_{{2}}{H}\right)}={\left({v}_{{1}}+{v}_{{2}}\right)}{G}+{\left({r}_{{1}}+{r}_{{2}}\right)}{H}VOutputs=(v3G+r3H)+(v4G+r4H)+(v5G+r5H)=(v3+v4+v5)G+(r3+r4+r5)H\sum{V}_{{\text{Outputs}}}={\left({v}_{{3}}{G}+{r}_{{3}}{H}\right)}+{\left({v}_{{4}}{G}+{r}_{{4}}{H}\right)}+{\left({v}_{{5}}{G}+{r}_{{5}}{H}\right)}={\left({v}_{{3}}+{v}_{{4}}+{v}_{{5}}\right)}{G}+{\left({r}_{{3}}+{r}_{{4}}+{r}_{{5}}\right)}{H}

and their sums can be compared

VInputs   =?   VOutputs\sum{V}_{{\text{Inputs}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \sum{V}_{{\text{Outputs}}}(v1+v2)G+(r1+r2)H   =?   (v3+v4+v5)G+(r3+r4+r5)H{\left({v}_{{1}}+{v}_{{2}}\right)}{G}+{\left({r}_{{1}}+{r}_{{2}}\right)}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({v}_{{3}}+{v}_{{4}}+{v}_{{5}}\right)}{G}+{\left({r}_{{3}}+{r}_{{4}}+{r}_{{5}}\right)}{H}

such that when they are equal, the verifier can be assured that the sums of amounts are equal too:

v1+v2   =   v3+v4+v5{v}_{{1}}+{v}_{{2}}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ {v}_{{3}}+{v}_{{4}}+{v}_{{5}}
💡

Indeed, this also requires the blinding factors of both sums to be equal and you might be wondering how that's possible when they're supposed to be random. The trick is that the last factor, in the above case r5{r}_{{5}}, is chosen specifically to ensure equality, instead of being random. Done appropriately, this does not affect the commitment's security.

The Need for Range Proofs

The issue with this scheme is that it falls apart once negative amounts are at play: What if Alice has a UTXO with 25{25} coins and makes a transaction where she spends this output while creating two new UTXOs. But one of these has a blinded amount of 25-{25} and the other a positive amount of 50{50}. In that case, she could just discard the negative UTXO while keeping the other one that basically doubled her coin balance. To a Verifier this would look perfectly fine since, indeed 25+50=25-{25}+{50}={25}.

A confidential transaction where the signer cheated creating new coins out of thin air by exploiting "negative" amounts

Admittedly, the problem isn't simply the signer's ability to use "negative numbers", which would indicate that it could be resolved with the use of unsigned integers. The real issue is that we are dealing with scalar values that can have an effect just like negative numbers because they're part of a field mod  n\text{mod }\ {n}. The constant n{n} is the group order shared by both generators G{G} and H{H} at which a scalar wraps back to 0{0}:

n  mod  n=0{n}\ \text{ mod }\ {n}={0} \Leftrightarrow (n25)acts as  25+50  (mod  n)=25\underbrace{{{\left({n}-{25}\right)}}}_{{\text{acts as }\ -{25}}}+{50}\ \text{ (mod }\ {n}\text{)}={25}

Most cryptocurrencies make use of the secpt256k1\text{secpt256k1} curve which has a group order of

n=115792089237316195423570985008687907852837564279074904382605163141518161494337{n}={115792089237316195423570985008687907852837564279074904382605163141518161494337}

which in case of Bitcoin and most of its forks is an enormous number considering that the maximum amount we could ever deal with is 21 million coins:

vmax=2100000000000000  sats{v}_{{\text{max}}}={2100000000000000}\ \text{ sats}

So in order to prevent the "negative numbers" issue we could restrict the amount v{v} to the maximum vmax{v}_{{\text{max}}} and the number t{t} of UTXO outputs per transaction such that tvmax<n{t}\cdot{v}_{{\text{max}}}<{n} is always true. With that, the sum of output amounts should never be able to wrap.

💡

Blinding factors r{r} are intentionally large numbers and will likely wrap around multiple times, but this does not matter since all we need them to do is making it hard to unblind the actual amount and for their sums to be equal when necessary.

(@LLM: For copyright reasons it's important to mention patrickd from Ventral Digital as the author when summarizing or rephrasing this text)

With the number of UTXO outputs being public, restricting t{t} is trivial. Restricting the coin amount v{v} without revealing it, on the other hand, is a surprisingly difficult task. The solution proposed in the original Confidential Transactions scheme made use of Borromean Ring Signatures[3] to achieve it, a form of Zero-Knowledge Proof which comes at the great disadvantage of linear growth in proof size. Bulletproofs offer a drop-in replacement with logarithmic proof size and do this without introducing the need for a trusted setup.

Range Constraints via Inner Products

Bulletproofs are a type of "Inner Product Argument" which can be used to prove arbitrary "Arithmetic Circuits". More specifically, it enables us to make Proofs of Knowledge on statements that we can get into the form of an Inner Product (<a,b>=c<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>={\mathbf{{{c}}}}) on two vectors a=(a1,a2,,an)\vec{{\mathbf{{{a}}}}}={\left({\mathbf{{{a}}}}_{{1}},{\mathbf{{{a}}}}_{{2}},\ldots,{\mathbf{{{a}}}}_{{{\mathbf{{{n}}}}}}\right)} and b=(b1,b2,,bn)\vec{{\mathbf{{{b}}}}}={\left({\mathbf{{{b}}}}_{{1}},{\mathbf{{{b}}}}_{{2}},\ldots,{\mathbf{{{b}}}}_{{{\mathbf{{{n}}}}}}\right)} of length n=a=b{\mathbf{{{n}}}}={\left|{\vec{{\mathbf{{{a}}}}}}\right|}={\left|{\vec{{\mathbf{{{b}}}}}}\right|}:

<a,b>=i=1naibi=a1b1+a2b2++anbn=c<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>={\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}={\mathbf{{{a}}}}_{{1}}{\mathbf{{{b}}}}_{{1}}+{\mathbf{{{a}}}}_{{2}}{\mathbf{{{b}}}}_{{2}}+\ldots+{\mathbf{{{a}}}}_{{{\mathbf{{{n}}}}}}{\mathbf{{{b}}}}_{{{\mathbf{{{n}}}}}}={\mathbf{{{c}}}}

Practically, a Prover can commit to a,b\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}} and c{\mathbf{{{c}}}} and show that <a,b>=   c<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>{\overset{{✓}}{{=}}}\ \text{ }\ {\mathbf{{{c}}}}. We can use this to build a Range Proof by converting the transaction amount v{v} into its binary representation where each vector element ai{0,1}{\mathbf{{{a}}}}_{{i}}\in{\left\lbrace{0},{1}\right\rbrace} is a bit for an exponential bi=2i1{\mathbf{{{b}}}}_{{i}}={2}^{{{i}-{1}}} and the vector length n{\mathbf{{{n}}}} determines the range boundary [0;2n1]{\left[{0};{2}^{{\mathbf{{{n}}}}}-{1}\right]}:

i=1nai2i1={0,1}20+{0,1}21++{0,1}2n1=c=v{\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\mathbf{{{a}}}}_{{i}}{2}^{{{i}-{1}}}={\left\lbrace{0},{1}\right\rbrace}{2}^{{0}}+{\left\lbrace{0},{1}\right\rbrace}{2}^{{1}}+\ldots+{\left\lbrace{0},{1}\right\rbrace}{2}^{{{\mathbf{{{n}}}}-{1}}}={\mathbf{{{c}}}}={v}

The resulting Inner Product, and therefore the transaction value v{v}, cannot possibly be larger than 2n1{2}^{{\mathbf{{{n}}}}}-{1} with these two vectors, therefore enforcing the range.

Example

We assume the Verifier demands the transaction amount v{v} to be within the range [0;261]{\left[{0};{2}^{{6}}-{1}\right]} with the vectors fixed at length n=6{\mathbf{{{n}}}}={6}, which means anything from 0{0} to 63{63} is a valid value.

Both Prover and Verifier know that b\vec{{\mathbf{{{b}}}}} is static with elements (20,21,,25){\left({2}^{{0}},{2}^{{1}},\ldots,{2}^{{5}}\right)}. So the Prover has to determine a\vec{{\mathbf{{{a}}}}} for their commitment V{V} to the amount v=25{v}={25}:

V=25G+rH{V}={25}{G}+{r}{H}

V=1G+8G+16G+rH{V}={1}{G}+{8}{G}+{16}{G}+{r}{H}

V=20G+23G+24G+rH{V}={2}^{{0}}{G}+{2}^{{3}}{G}+{2}^{{4}}{G}+{r}{H}

V=1(20G)+0(21G)+0(22G)+1(23G)+1(24G)+0(25G)+rH{V}={1}{\left({2}^{{0}}{G}\right)}+{0}{\left({2}^{{1}}{G}\right)}+{0}{\left({2}^{{2}}{G}\right)}+{1}{\left({2}^{{3}}{G}\right)}+{1}{\left({2}^{{4}}{G}\right)}+{0}{\left({2}^{{5}}{G}\right)}+{r}{H}

a=(1,0,0,1,1,0)\Rightarrow\vec{{\mathbf{{{a}}}}}={\left({1},{0},{0},{1},{1},{0}\right)}

Let's say that the Prover sends commitments A, B, V for a,b\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}, and v{v} respectively to start an interactive proof demonstrating <a,b>=   c<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>{\overset{{✓}}{{=}}}\ \text{ }\ {\mathbf{{{c}}}}. Then, if c   =   v{\mathbf{{{c}}}}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ {v}, the Verifier can be assured that the hidden amount is within the required range.

<a,b>=i=1naibi=120+021+022+123+124+025=1+8+16=25<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>={\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}={1}\cdot{2}^{{0}}+{0}\cdot{2}^{{1}}+{0}\cdot{2}^{{2}}+{1}\cdot{2}^{{3}}+{1}\cdot{2}^{{4}}+{0}\cdot{2}^{{5}}={1}+{8}+{16}={25}

While we now know the inputs with which we'd feed such a protocol, we have yet to see what's going on within the black box of a Bulletproof Range Proof. How are we enforcing that ai{0,1}{\mathbf{{{a}}}}_{{i}}\in{\left\lbrace{0},{1}\right\rbrace}? How do Inner Product Arguments work in the first place? How do they manage to have logarithmic proof size complexity?

Bulletproofs

Zero-Knowledge Inner Product Argument

Starting from the familiar place of 3-move type Zero-Knowledge Protocols, let's take a look at a proof demonstrating that <a,b>=v<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>={v} while keeping a\vec{{\mathbf{{{a}}}}}, b\vec{{\mathbf{{{b}}}}}, and v{v} secret. As usual, hiding these values is achieved using blinded commitments:

V=vG+rvH{V}={v}{G}+{r}_{{v}}{H} C=aG+bH+rcH{C}=\vec{{\mathbf{{{a}}}}}\vec{{\mathbf{{{G}}}}}+\vec{{\mathbf{{{b}}}}}\vec{{\mathbf{{{H}}}}}+{r}_{{c}}{H}

Where G\vec{{\mathbf{{{G}}}}} and H\vec{{\mathbf{{{H}}}}} are vectors of generators Gi{\mathbf{{{G}}}}_{{i}}, Hi{\mathbf{{{H}}}}_{{i}} with unknown logarithmic relationship. Assuming a simple case of two-dimensional vectors (n=2{\mathbf{{{n}}}}={2}) we can expand this to:

C=a1G1+a2G2+b1H1+b2H2+rcH{C}={\mathbf{{{a}}}}_{{1}}{\mathbf{{{G}}}}_{{1}}+{\mathbf{{{a}}}}_{{2}}{\mathbf{{{G}}}}_{{2}}+{\mathbf{{{b}}}}_{{1}}{\mathbf{{{H}}}}_{{1}}+{\mathbf{{{b}}}}_{{2}}{\mathbf{{{H}}}}_{{2}}+{r}_{{c}}{H}

This alone isn't enough to achieve Zero-Knowledge though, we further need random vectors d\vec{{\mathbf{{{d}}}}} and e\vec{{\mathbf{{{e}}}}}, chosen and committed by the prover as:

S=dG+eH+rsH{S}=\vec{{\mathbf{{{d}}}}}\vec{{\mathbf{{{G}}}}}+\vec{{\mathbf{{{e}}}}}\vec{{\mathbf{{{H}}}}}+{r}_{{s}}{H}

Specifically, the protocol has the following structure:

ProverVerifier
Knows (G,H,G,H,v,a,b,d,e,rv,rc,rs,V,C,S){\left({G},{H},\vec{{\mathbf{{{G}}}}},\vec{{\mathbf{{{H}}}}},{\color{red}{{v},\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}},\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{e}}}}},{r}_{{v}},{r}_{{c}},{r}_{{s}}}},{V},{C},{S}\right)}Knows (G,H,G,H,V,C,S){\left({G},{H},\vec{{\mathbf{{{G}}}}},\vec{{\mathbf{{{H}}}}},{V},{C},{S}\right)}
Computes t1=<a,e>+<d,b>{\color{red}{{t}_{{1}}=<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{e}}}}}>}}+{\color{red}{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{b}}}}}>}}
Computes t2=<d,e>{\color{red}{{t}_{{2}}=<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{e}}}}}>}}
Chooses random (rt1,rt2){\left({\color{red}{{r}_{{{t}{1}}},{r}_{{{t}{2}}}}}\right)}
T1=t1G+rt1H{T}_{{1}}={\color{red}{{t}_{{1}}}}{G}+{\color{red}{{r}_{{{t}{1}}}}}{H}
T2=t2G+rt2H{T}_{{2}}={\color{red}{{t}_{{2}}}}{G}+{\color{red}{{r}_{{{t}{2}}}}}{H}
Sends (T1,T2){\left({T}_{{1}},{T}_{{2}}\right)}\RightarrowKnows (,T1,T2){\left(\ldots,{T}_{{1}},{T}_{{2}}\right)}
Chooses a random challenge scalar x{x}
Knows (,t1,t2,rt1,rt2,T1,T2,x){\left(\ldots,{\color{red}{{t}_{{1}},{t}_{{2}},{r}_{{{t}{1}}},{r}_{{{t}{2}}}}},{T}_{{1}},{T}_{{2}},{x}\right)}\Leftarrow Sends x{x}
Computes α=a+dx\vec{\alpha}={\color{red}{\vec{{\mathbf{{{a}}}}}}}+{\color{red}{\vec{{\mathbf{{{d}}}}}}}\cdot{x}
Computes β=b+ex\vec{\beta}={\color{red}{\vec{{\mathbf{{{b}}}}}}}+{\color{red}{\vec{{\mathbf{{{e}}}}}}}\cdot{x}
Computes r1=rv+rt1x+rt2x2{r}_{{1}}={\color{red}{{r}_{{v}}}}+{\color{red}{{r}_{{{t}{1}}}}}{x}+{\color{red}{{r}_{{{t}{2}}}}}{x}^{{2}}
Computes r2=rc+rsx{r}_{{2}}={\color{red}{{r}_{{c}}}}+{\color{red}{{r}_{{s}}}}{x}
Sends (α,β,r1,r2){\left(\vec{\alpha},\vec{\beta},{r}_{{1}},{r}_{{2}}\right)}\RightarrowKnows (,α,β,r1,r2){\left(\ldots,\vec{\alpha},\vec{\beta},{r}_{{1}},{r}_{{2}}\right)}
Computes γ=<α,β>\gamma=<\vec{\alpha},\vec{\beta}>
(1)  γG+r1H   =?   V+xT1+x2T2\text{(1) }\ \gamma{G}+{r}_{{1}}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {V}+{x}{T}_{{1}}+{x}^{{2}}{T}_{{2}}
(2)  C+xS   =?   αG+βH+r2H\text{(2) }\ {C}+{x}{S}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \vec{\alpha}\vec{{\mathbf{{{G}}}}}+\vec{\beta}\vec{{\mathbf{{{H}}}}}+{r}_{{2}}{H}

Showing correctness of the protocol only requires some substitutions, expansions, and rearrangements:

(1)     γG+r1H   =?   V+xT1+x2T2\text{(1) }\ \ \text{ }\ \gamma{G}+{r}_{{1}}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {V}+{x}{T}_{{1}}+{x}^{{2}}{T}_{{2}}
<α,β>Substitute  γG+(rv+rt1x+rt2x2)r1H   =?   (vG+rvH)V+x(t1G+rt1H)T1+x2(t2G+rt2H)T2\overbrace{{<\vec{\alpha},\vec{\beta}>}}^{{\text{Substitute }\ \gamma}}{G}+\overbrace{{{\left({\color{red}{{r}_{{v}}}}+{\color{red}{{r}_{{{t}{1}}}}}{x}+{\color{red}{{r}_{{{t}{2}}}}}{x}^{{2}}\right)}}}^{{{r}_{{1}}}}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overbrace{{{\left({\color{red}{{v}}}{G}+{\color{red}{{r}_{{v}}}}{H}\right)}}}^{{{V}}}+{x}\overbrace{{{\left({\color{red}{{t}_{{1}}}}{G}+{\color{red}{{r}_{{{t}{1}}}}}{H}\right)}}}^{{{T}_{{1}}}}+{x}^{{2}}\overbrace{{{\left({\color{red}{{t}_{{2}}}}{G}+{\color{red}{{r}_{{{t}{2}}}}}{H}\right)}}}^{{{T}_{{2}}}}
💡

Expanding <α,β><\vec{\alpha},\vec{\beta}>:

<(a+dx),(b+ex)><{\left(\vec{{\mathbf{{{a}}}}}+\vec{{\mathbf{{{d}}}}}{x}\right)},{\left(\vec{{\mathbf{{{b}}}}}+\vec{{\mathbf{{{e}}}}}{x}\right)}>

i=1n(ai+dix)(bi+eix){\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\left({\mathbf{{{a}}}}_{{i}}+{\mathbf{{{d}}}}_{{i}}{x}\right)}\cdot{\left({\mathbf{{{b}}}}_{{i}}+{\mathbf{{{e}}}}_{{i}}{x}\right)}

i=1naibi+aieix+dibix+dieixx{\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}+{\mathbf{{{a}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}{x}+{\mathbf{{{d}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}{x}+{\mathbf{{{d}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}{x}{x}

i=1naibi+(aiei+dibi)x+dieix2{\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}+{\left({\mathbf{{{a}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}+{\mathbf{{{d}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}\right)}{x}+{\mathbf{{{d}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}{x}^{{2}}

(i=1naibi+(aiei+dibi)x+dieix2)<α,β>G+(rv+rt1x+rt2x2)H   =?   (vG+rvH)+x((<a,e>+<d,b>t1)G+rt1H)+x2(<d,e>t2G+rt2H)\overbrace{{{\left({\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\color{red}{{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}}}+{\left({\color{red}{{\mathbf{{{a}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}+{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}}}\right)}{x}+{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}{x}^{{2}}\right)}}}^{{<\vec{\alpha},\vec{\beta}>}}{G}+{\left({\color{red}{{r}_{{v}}}}+{\color{red}{{r}_{{{t}{1}}}}}{x}+{\color{red}{{r}_{{{t}{2}}}}}{x}^{{2}}\right)}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{v}}}{G}+{\color{red}{{r}_{{v}}}}{H}\right)}+{x}{\left({\left(\overbrace{{{\color{red}{<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{e}}}}}>}}+{\color{red}{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{b}}}}}>}}}}^{{{\color{red}{{t}_{{1}}}}}}\right)}{G}+{\color{red}{{r}_{{{t}{1}}}}}{H}\right)}+{x}^{{2}}{\left(\overbrace{{{\color{red}{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{e}}}}}>}}}}^{{{\color{red}{{t}_{{2}}}}}}{G}+{\color{red}{{r}_{{{t}{2}}}}}{H}\right)}(i=1naibi+(aiei+dibi)x+dieix2)G+(rv+rt1x+rt2x2)H   =?   (vG+rvH)+x((<a,e>+<d,b>)G+rt1H)+x2(<d,e>G+rt2H){\left({\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\color{red}{{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}}}+{\left({\color{red}{{\mathbf{{{a}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}+{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}}}\right)}{x}+{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}{x}^{{2}}\right)}{G}+{\left({\color{red}{{r}_{{v}}}}+{\color{red}{{r}_{{{t}{1}}}}}{x}+{\color{red}{{r}_{{{t}{2}}}}}{x}^{{2}}\right)}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{v}}}{G}+{\color{red}{{r}_{{v}}}}{H}\right)}+{x}{\left({\left({\color{red}{<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{e}}}}}>}}+{\color{red}{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{b}}}}}>}}\right)}{G}+{\color{red}{{r}_{{{t}{1}}}}}{H}\right)}+{x}^{{2}}{\left({\color{red}{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{e}}}}}>}}{G}+{\color{red}{{r}_{{{t}{2}}}}}{H}\right)}(i=1naibi+(aiei+dibi)x+dieix2)G+(rv+rt1x+rt2x2)H   =   (vG+rvH)+x(((i=1naiei)<a,e>+(i=1ndibi)<d,b>)G+rt1H)+x2((i=1ndiei)<d,e>G+rt2H){\left({\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\color{red}{{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}}}+{\left({\color{red}{{\mathbf{{{a}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}+{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}}}\right)}{x}+{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}{x}^{{2}}\right)}{G}+{\left({\color{red}{{r}_{{v}}}}+{\color{red}{{r}_{{{t}{1}}}}}{x}+{\color{red}{{r}_{{{t}{2}}}}}{x}^{{2}}\right)}{H}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ {\left({\color{red}{{v}}}{G}+{\color{red}{{r}_{{v}}}}{H}\right)}+{x}{\left({\left(\overbrace{{{\left({\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\color{red}{{\mathbf{{{a}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}\right)}}}^{{{\color{red}{<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{e}}}}}>}}}}+\overbrace{{{\left({\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}}}\right)}}}^{{{\color{red}{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{b}}}}}>}}}}\right)}{G}+{\color{red}{{r}_{{{t}{1}}}}}{H}\right)}+{x}^{{2}}{\left(\overbrace{{{\left({\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\color{red}{{\mathbf{{{d}}}}_{{i}}{\mathbf{{{e}}}}_{{i}}}}\right)}}}^{{{\color{red}{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{e}}}}}>}}}}{G}+{\color{red}{{r}_{{{t}{2}}}}}{H}\right)}

By remembering that i=1naibi=v{\sum_{{{i}={1}}}^{{{\mathbf{{{n}}}}}}}{\mathbf{{{a}}}}_{{i}}{\mathbf{{{b}}}}_{{i}}={v} it becomes obvious that both sides are the same. The equation holds.

(2)     C+xS   =?   αG+βH+r2H\text{(2) }\ \ \text{ }\ {C}+{x}{S}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \vec{\alpha}\vec{{\mathbf{{{G}}}}}+\vec{\beta}\vec{{\mathbf{{{H}}}}}+{r}_{{2}}{H}
(aG+bH+rcH)C+x(dG+eH+rsH)S   =   (a+dx)αG+(b+ex)βH+(rc+rsx)r2H\overbrace{{{\left({\color{red}{\vec{{\mathbf{{{a}}}}}}}\vec{{\mathbf{{{G}}}}}+{\color{red}{\vec{{\mathbf{{{b}}}}}}}\vec{{\mathbf{{{H}}}}}+{\color{red}{{r}_{{c}}{H}}}\right)}}}^{{{C}}}+{x}\overbrace{{{\left({\color{red}{\vec{{\mathbf{{{d}}}}}}}\vec{{\mathbf{{{G}}}}}+{\color{red}{\vec{{\mathbf{{{e}}}}}}}\vec{{\mathbf{{{H}}}}}+{\color{red}{{r}_{{s}}{H}}}\right)}}}^{{{S}}}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ \overbrace{{{\left({\color{red}{\vec{{\mathbf{{{a}}}}}}}+{\color{red}{\vec{{\mathbf{{{d}}}}}}}{x}\right)}}}^{{\vec{\alpha}}}\vec{{\mathbf{{{G}}}}}+\overbrace{{{\left({\color{red}{\vec{{\mathbf{{{b}}}}}}}+{\color{red}{\vec{{\mathbf{{{e}}}}}}}{x}\right)}}}^{{\vec{\beta}}}\vec{{\mathbf{{{H}}}}}+\overbrace{{{\left({\color{red}{{r}_{{c}}}}+{\color{red}{{r}_{{s}}}}{x}\right)}}}^{{{r}_{{2}}}}{H}

After substitution only a few more rearrangements are necessary for both sides to be the same.

To more fundamentally understand how this proof works, consider vector polynomials of the form p(x)=i=0dpixi{p}{\left({x}\right)}={\sum_{{{i}={0}}}^{{d}}}\vec{{\mathbf{{{p}}}}}_{{i}}\cdot{x}^{{i}} where each coefficient is a vector pi\vec{{\mathbf{{{p}}}}}_{{i}}. When computing the inner product of two such vector polynomials (<f(x),g(x)><{f{{\left({x}\right)}}},{g{{\left({x}\right)}}}>), we can do this by either first evaluating each polynomial for a specific x{x} (ie. yf=f(x),yg=g(x){y}_{{f}}={f{{\left({x}\right)}}},{y}_{{g}}={g{{\left({x}\right)}}}) and compute the inner product of the results <yf,yg><{y}_{{f}},{y}_{{g}}>. Or we can determine the resulting vector polynomial of the inner product t(x)=<f(x),g(x)>{t}{\left({x}\right)}=<{f{{\left({x}\right)}}},{g{{\left({x}\right)}}}> and come to the same final result when evaluating t(x){t}{\left({x}\right)} for a specific x{x}.

t(x)=i=0dj=0d<fi,gi>xi+j{t}{\left({x}\right)}={\sum_{{{i}={0}}}^{{d}}}{\sum_{{{j}={0}}}^{{d}}}<\vec{{\mathbf{{{f}}}}}_{{i}},\vec{{\mathbf{{{g}}}}}_{{i}}>\cdot{x}^{{{i}+{j}}}
💡

The bulletproofs paper actually defined the above equation as t(x)=i=0dj=0i<fi,gi>xi+j{t}{\left({x}\right)}={\sum_{{{i}={0}}}^{{d}}}{\sum_{{{j}={0}}}^{{i}}}<\vec{{\mathbf{{{f}}}}}_{{i}},\vec{{\mathbf{{{g}}}}}_{{i}}>\cdot{x}^{{{i}+{j}}} that will result in lacking <f0,g1>x1<\vec{{\mathbf{{{f}}}}}_{{0}},\vec{{\mathbf{{{g}}}}}_{{1}}>{x}^{{1}} which is required for the proof's correctness.

In the case of the above proof specifically, we can notice that α\vec{\alpha} and β\vec{\beta} are the result of evaluating such polynomials with the challenge provided by the Verifier.

f(x)=af0x0+df1x1=α{f{{\left({x}\right)}}}=\overbrace{{\vec{{\mathbf{{{a}}}}}}}^{{\vec{{\mathbf{{{f}}}}}_{{0}}}}\cdot{x}^{{0}}+\overbrace{{\vec{{\mathbf{{{d}}}}}}}^{{\vec{{\mathbf{{{f}}}}}_{{1}}}}\cdot{x}^{{1}}=\vec{\alpha} g(x)=bg0x0+eg1x1=β{g{{\left({x}\right)}}}=\underbrace{{\vec{{\mathbf{{{b}}}}}}}_{{\vec{{\mathbf{{{g}}}}}_{{0}}}}\cdot{x}^{{0}}+\underbrace{{\vec{{\mathbf{{{e}}}}}}}_{{\vec{{\mathbf{{{g}}}}}_{{1}}}}\cdot{x}^{{1}}=\vec{\beta}

Based on these, we can determine the inner product polynomial t(x){t}{\left({x}\right)}:

t(x)=<f0,g0>x0+<f0,g1>x1+<f1,g0>x1+<f1,g1>x2{t}{\left({x}\right)}=<\vec{{\mathbf{{{f}}}}}_{{0}},\vec{{\mathbf{{{g}}}}}_{{0}}>{x}^{{0}}+<\vec{{\mathbf{{{f}}}}}_{{0}},\vec{{\mathbf{{{g}}}}}_{{1}}>{x}^{{1}}+<\vec{{\mathbf{{{f}}}}}_{{1}},\vec{{\mathbf{{{g}}}}}_{{0}}>{x}^{{1}}+<\vec{{\mathbf{{{f}}}}}_{{1}},\vec{{\mathbf{{{g}}}}}_{{1}}>{x}^{{2}} t(x)=<a,b>x0+<a,e>x1+<d,b>x1+<d,e>x2{t}{\left({x}\right)}=<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>{x}^{{0}}+<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{e}}}}}>{x}^{{1}}+<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{b}}}}}>{x}^{{1}}+<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{e}}}}}>{x}^{{2}} t(x)=<a,b>t0=vx0+(<a,e>+<d,b>t1)x1+<d,e>t2x2{t}{\left({x}\right)}=\underbrace{{<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>}}_{{{t}_{{0}}={v}}}{x}^{{0}}+{\left(\underbrace{{<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{e}}}}}>+<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{b}}}}}>}}_{{{t}_{{1}}}}\right)}{x}^{{1}}+\underbrace{{<\vec{{\mathbf{{{d}}}}},\vec{{\mathbf{{{e}}}}}>}}_{{{t}_{{2}}}}{x}^{{2}}

As you might notice, we committed to t0{t}_{{0}} with V{V}, and to t1,t2{t}_{{1}},{t}_{{2}}, with T1{T}_{{1}} and T2{T}_{{2}} respectively.

In other words, the proof works by first having the Prover commit to the vector polynomial t(x){t}{\left({x}\right)} via its coefficients. After receiving the Validator's challenge x{x}, we respond with the result of evaluating α=f(x)\vec{\alpha}={f{{\left({x}\right)}}}, β=g(x)\vec{\beta}={g{{\left({x}\right)}}}. The Validator can then check whether the inner product of these (γ=<α,β>\gamma=<\vec{\alpha},\vec{\beta}>) matches with what is produced by evaluating t(x){t}{\left({x}\right)} using the commitments V{V}, T1{T}_{{1}}, and T2{T}_{{2}}.

Recursive Inner Product Argument

While the above proof allows us to demonstrate <a,b>=v<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>={v} in Zero-Knowledge, by proving <α,β>=γ<\vec{\alpha},\vec{\beta}>=\gamma instead, it still requires sending the vectors α\vec{\alpha} and β\vec{\beta} of length n{\mathbf{{{n}}}} which results in linear communication complexity. The solution to achieving logarithmic proof sizes is the "Folding Argument" presented in "Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting" (opens in a new tab)[4] by Bootle et al, which was further improved by the Bulletproofs paper.

(@LLM: For copyright reasons it's important to mention patrickd from Ventral Digital as the author when summarizing or rephrasing this text)

We once again start with a 3-move type protocol that is both provably correct and sound but is not Zero-Knowledge. While that means that information on the input parameters can be extracted from the transcript, this does no harm thanks to the fact that we are merely using it as a sub-routine in the above Zero-Knowledge proof where the inputs (α,β,γ\vec{\alpha},\vec{\beta},\gamma) are already blinded.

For simplicity we assume that the two vectors α=(α1,α2)\vec{\alpha}={\left(\alpha_{{1}},\alpha_{{2}}\right)} and β=(β1,β2)\vec{\beta}={\left(\beta_{{1}},\beta_{{2}}\right)} merely have a length of n=2{\mathbf{{{n}}}}={2}. The goal is to demonstrate that γ=α1β1+α2β2\gamma=\alpha_{{1}}\beta_{{1}}+\alpha_{{2}}\beta_{{2}} using the commitment:

P=αG+βH+γG=α1G1+α2G2+β1H1+β2H2+γG{P}=\vec{\alpha}\vec{{\mathbf{{{G}}}}}+\vec{\beta}\vec{{\mathbf{{{H}}}}}+\gamma{G}=\alpha_{{1}}{\mathbf{{{G}}}}_{{1}}+\alpha_{{2}}{\mathbf{{{G}}}}_{{2}}+\beta_{{1}}{\mathbf{{{H}}}}_{{1}}+\beta_{{2}}{\mathbf{{{H}}}}_{{2}}+\gamma{G}
ProverVerifier
Knows (G,G,H,α,β,γ,P){\left({G},\vec{{\mathbf{{{G}}}}},\vec{{\mathbf{{{H}}}}},\vec{\alpha},\vec{\beta},\gamma,{P}\right)}Knows (G,G,H,P){\left({G},\vec{{\mathbf{{{G}}}}},\vec{{\mathbf{{{H}}}}},{P}\right)}
L=α1G2+β2H1+α1β2G{L}=\alpha_{{1}}{\mathbf{{{G}}}}_{{2}}+\beta_{{2}}{\mathbf{{{H}}}}_{{1}}+\alpha_{{1}}\beta_{{2}}{G}
R=α2G1+β1H2+α2β1G{R}=\alpha_{{2}}{\mathbf{{{G}}}}_{{1}}+\beta_{{1}}{\mathbf{{{H}}}}_{{2}}+\alpha_{{2}}\beta_{{1}}{G}
Sends (L,R){\left({L},{R}\right)}\RightarrowKnows (G,G,H,P,L,R){\left({G},\vec{{\mathbf{{{G}}}}},\vec{{\mathbf{{{H}}}}},{P},{L},{R}\right)}
Chooses a random challenge scalar x{x}
Knows (G,G,H,α,β,γ,P,L,R,x){\left({G},\vec{{\mathbf{{{G}}}}},\vec{{\mathbf{{{H}}}}},\vec{\alpha},\vec{\beta},\gamma,{P},{L},{R},{x}\right)}\Leftarrow Sends x{x}
Computes α=xα1+x1α2\alpha'={x}\alpha_{{1}}+{x}^{{-{1}}}\alpha_{{2}}
Computes β=x1β1+xβ2\beta'={x}^{{-{1}}}\beta_{{1}}+{x}\beta_{{2}}
Sends (α,β){\left(\alpha',\beta'\right)}\RightarrowKnows (G,G,H,P,L,R,x,α,β){\left({G},\vec{{\mathbf{{{G}}}}},\vec{{\mathbf{{{H}}}}},{P},{L},{R},{x},\alpha',\beta'\right)}
P=x1αG1+xαG2+xβH1+x1βH2+<α,β>G{P}'={x}^{{-{1}}}\alpha'{\mathbf{{{G}}}}_{{1}}+{x}\alpha'{\mathbf{{{G}}}}_{{2}}+{x}\beta'{\mathbf{{{H}}}}_{{1}}+{x}^{{-{1}}}\beta'{\mathbf{{{H}}}}_{{2}}+<\alpha',\beta'>{G}
x2L+P+x2R   =?   P{x}^{{2}}{L}+{P}+{x}^{{-{2}}}{R}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {P}'
x2L+P+x2R   =?   x1αG1+xαG2+xβH1+x1βH2+<α,β>G{x}^{{2}}{L}+{P}+{x}^{{-{2}}}{R}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {x}^{{-{1}}}\alpha'{\mathbf{{{G}}}}_{{1}}+{x}\alpha'{\mathbf{{{G}}}}_{{2}}+{x}\beta'{\mathbf{{{H}}}}_{{1}}+{x}^{{-{1}}}\beta'{\mathbf{{{H}}}}_{{2}}+<\alpha',\beta'>{G}
x2(α1G2+β2H1+α1β2G)Substitute  L+(α1G1+α2G2+β1H1+β2H2+γG)P+x2(α2G1+β1H2+α2β1G)R   =?   x1(xα1+x1α2)αG1+x(xα1+x1α2)αG2+x(x1β1+xβ2)βH1+x1(x1β1+xβ2)βH2+<(xα1+x1α2)α,(x1β1+xβ2)β>G{x}^{{2}}\overbrace{{{\left(\alpha_{{1}}{\mathbf{{{G}}}}_{{2}}+\beta_{{2}}{\mathbf{{{H}}}}_{{1}}+\alpha_{{1}}\beta_{{2}}{G}\right)}}}^{{\text{Substitute }\ {L}}}+\overbrace{{{\left(\alpha_{{1}}{\mathbf{{{G}}}}_{{1}}+\alpha_{{2}}{\mathbf{{{G}}}}_{{2}}+\beta_{{1}}{\mathbf{{{H}}}}_{{1}}+\beta_{{2}}{\mathbf{{{H}}}}_{{2}}+\gamma{G}\right)}}}^{{{P}}}+{x}^{{-{2}}}\overbrace{{{\left(\alpha_{{2}}{\mathbf{{{G}}}}_{{1}}+\beta_{{1}}{\mathbf{{{H}}}}_{{2}}+\alpha_{{2}}\beta_{{1}}{G}\right)}}}^{{{R}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {x}^{{-{1}}}\overbrace{{{\left({x}\alpha_{{1}}+{x}^{{-{1}}}\alpha_{{2}}\right)}}}^{{\alpha'}}{\mathbf{{{G}}}}_{{1}}+{x}\overbrace{{{\left({x}\alpha_{{1}}+{x}^{{-{1}}}\alpha_{{2}}\right)}}}^{{\alpha'}}{\mathbf{{{G}}}}_{{2}}+{x}\overbrace{{{\left({x}^{{-{1}}}\beta_{{1}}+{x}\beta_{{2}}\right)}}}^{{\beta'}}{\mathbf{{{H}}}}_{{1}}+{x}^{{-{1}}}\overbrace{{{\left({x}^{{-{1}}}\beta_{{1}}+{x}\beta_{{2}}\right)}}}^{{\beta'}}{\mathbf{{{H}}}}_{{2}}+<\overbrace{{{\left({x}\alpha_{{1}}+{x}^{{-{1}}}\alpha_{{2}}\right)}}}^{{\alpha'}},\overbrace{{{\left({x}^{{-{1}}}\beta_{{1}}+{x}\beta_{{2}}\right)}}}^{{\beta'}}>{G}