Introduction

In the most famous blockchains protocols (e.g Bitcoin or Ethereum) addresses are partly obfuscated by the fact that addresses are pseudo anonymous: they aren't directly tied with an identity. However chain analysis can succeed in discovering the identity associated with a given address.
We've seen that for instance CoinJoin offers a solution to break the link between sender and receiver. CoinJoin still provides limited privacy because it doesn't obfuscate the transaction amounts.

Limitations of CoinJoin

While CoinJoin obfuscates the relationship between a sender and a recipient, Confidential Transactions (CTs) obfuscate the content of a transaction together with the recipient's address.
CTs "blind" the amounts: from_address pays ?? to to_address.
CT were invented by G.Maxwell (Link 1, Link 2) and further investigated by Adam Gibson.

CT: how it works

Bitcoin transactions maps inputs amounts from a sender, with outputs amounts that can be redeemed by the receiver.
On the Bitcoin blockchain, the amouts are in clear text.

As defined by the protocol, for a transaction to be valid, INPUTS needs to equal OUTPUTS:
4 + 1 == 2 + 3

Confidential transactions and bulletproofs allow to

1. hide amounts
2. check that the hidden inputs and hidden outputs add up.

A + B == C + D

Trick 1: Commitments to hide and bind values

Commitments solve the first part: hiding and binding the amounts. By relying on asymmetric cryptography they let you keep a piece of data secret but commit to it so that you cannot change it later.

               commit
data             ->   Commitment(data)
                open
Commitment(data) ->   data

A real-life simple implementation of a commitment could be a sealed enveloppe.
A and B are playing coin flipping but they are in separate rooms. Only B gets to toss the the coin. Only A gets to call. To avoid disputes (A announcing her call after B flips, or B reporting a wrong result):

1. A would commit to her call in a sealed enveloppe.
2. A doesn't communicate her call to B
3. B tosses the coin
4. B reports result (B still ignores her call)
5. A's commitment is revealed and tells who won

A simple commitment scheme can be constructed using a cryptographic hash: commitment = SHA256(data )

Trick 2: Homomorphic (Pedersen) commitments to perform operations with bound and hidden values

By committing to inputs and outputs values, we've hidden the values. To check that the sum of hidden inputs matches the sum of hidden outputs, we need commitments that are compatible with the addition (and multiplication) operations. We need our commitments to be homomorphic.

A homomorphism is a map between two algebraic structures of the same type, that preserves the operations of the structures.
f: A -> B
f is an homomorphism if for all x,y of A, f(xy) = f(x)f(y)

The natural logarithm or the exponential functions are homomorphisms.
Pedersen commitments rely on the discrete logarithm and are precisely homomorphic. So they solve the second part: checking that the sum of committed inputs matches the sum of committed outputs.

A + B == C + D <-> Com(a) + Com(b) == Com(c) + Com(d)
               <-> Com(a+b) == Com(c+d)
               <-> a + b == c + d

However, if the value of a transaction is encrypted, how do I know that someone didn't spend money they didn't have or that no money was created out of thin air?

A + B == C + D <-> Com(5) + Com(4) == Com(-100) + Com(109)
               <-> Com(4 + 5) == Com(-100 + 109)
               <-> 4 + 9 == -100 + 109
               is TRUE!! 100 created out of nowhere!!

More technically, we aren't really dealing with real negative values. We rather want to prevent overflow as we are in a finite field (e.g finite field from 1 to 9999, 1 + 9999 causes overflow to 100000 = 1).
Verifying that hidden inputs match with hidden outputs sum isn't enough. We need to be able to verify that the values remain in a given range to avoid overflow, while still keeping them secret!

Outcome

• [x] The inputs' commitments match the outputs' commitments only if the inputs match the outputs.
• [x] Values are hidden.
• [ ] Values are in a given range

Trick 3: zero knowlege range proofs as a scalar product

We want to transform the verification that a value v is in a given range (2^n) into the verification of a scalar (or 'inner' or 'dot') product that doesn't require revealing v.
We want to have a zero knowledge proof: (1) 0 <= v <= 2^n <-> (2) t = <l, r>.
"Zero knowledge" meaning that knowing that (2) is true tells that (1) is true too but without revealing v.

1. Break v in bits:

   2^n = (2⁰, 2¹, 2², ..., 2^n-1)
   a_l = vector of bits = (0, 1, 0, 1, ...., 1, 0)
   

   With (3) v = <a_l, (2⁰, 2¹, 2², ..., 2^n-1)> = <a_l, 2^n> then we can verifiy (1) if we can prove that all bits of a_l are real "bits": either 0 or 1.

2. Prove bits of v are actually bits (0 or 1)

   f: {0, 1} -> {-1, 0}
                    b   -> c = b - 1
            0   -> -1
            1   -> 0
   b is a bit <-> b.f(b) = 0
   

   With (4) a_r = a_l - 1^n, bits of v are actually bits <-> (5) <a_l, a_r> = 0^n.

So (1) 0 <= v <= 2^n <-> (3) & (4) & (5).
We transformed the verification of a range into the verification of 3 equalities!

Trick 4: combine multiple statements into 1 with a "random scalar challenge"

Random scalar protocol: combine 2 statements into 1

A Prover wants to prove A: a= 0 & B: b= 0.
The Verifier provides a "random challenge scalar x" , where x is in Z_p* = [1, 2, ...p].

P <- V: x
a + b*x = 0

Since prover cannot predict x, if the latter statement holds then the first statement holds with a probability (1 - 1/p).

Random scalar challenge to combine n statements into 1

To prove <a, b> = 0^n the verifier provide a random challenge scalar y:

<a, b> = 0^n <-> for each i in [0, n-1], a[i]*b[i] = 0
             <-> a[0]*b[0] + a[1]b[1]*y + a[2]*b[2]*y² + ... + a[n-1] * b[n-1] * y^n-1 = 0
             <-> <<a,b>, y^n> = 0
(We chose different powers of y to avoid that coefficients can cancel each other out)

So we provide 2 random challenge scalars:

1. Random challenge scalar y to transform (4) and (5) ( 2 times n equalities) into 2 equalities: (4') and (5').
2. Random challenge z to transform the (3) & (4') & (5') into 1 equation (6)

After some nice algebra we get

(6) <-> <f(a_l), g(a_l)> = h(v, z) = z²v + d(y, z)
    <-> t  = <l, r>

So the verifiation of the range 0 <= v <= 2^n has been reduced to verifying an equality where one side is defined by the random scalar provided by the Verifier, and one other defined by 2 vectors that reveals v.
We can't send l and r over to the verifier because they would discover v because they already know the random scalar z (they sent it to you over!). This would defeat the whole purpose of confidential transaction which is to hide v!
So we use the trick 2 again: with homomorphic commitments we can hide l and r!
<f(a_l), g(a_r)> = h(v) <-> (7) <f(com(a_l)), g(com(a_r))> = h(com(v))

Outcome

• [x] The inputs' commitments match the outputs' commitments only if the inputs match the outputs.
• [x] Values are hidden.
• [x] Values are in a given range

Trick 5: "compressing" with Bulletproofs for better efficiency

Verifying (7) means verifying n equations. Bulletproofs transactions are an optimization of confidential transactions to "compress" the proof. To reduce it to the verification of log_2(n) equations.
The vectors are "cut" recurringly in half to reduce the dimension of the proof till we get only 1 equality to verify. Then we proceed backwards to check the n equalities.

Summary

Confidential Transactions (CT) hide inputs and outputs.

To go further:
-Fiat-Shamir: how the challenge scalars are generated

Implementations of CTs

Liquid and Elements sidechains by Blockstream.

Video explaination of Bulletproof transactions by Cathie Yun