Gradually, as time goes by I intend to make this blog get more and more cypherpunk and today’s tutorial is going to be a game changer in this journey. We are going to learn about Pedersen commitments (and commitments in general) and we will apply prior theory of ECC cryptography acquired from Diffie-Hellman key exchange over elliptic curve, hashing functions, eliptic curve digital signature algorithm and Schnorr signature to formalize the concept of confidential transactions.
Information ownership raises important ethical dilemmas. In todays society information became a valuable resource and is centrally acquired by powerful organizations for close to nothing. We are using online services, mobile payment applications, credit cards and others often without even realizing we are feeding this huge machine with valuable data. Since we create this data, we should be able to take profits from it. To be the one in control. For that, confidential transactions are a way of storing transaction data on the elliptic curve allowing third party to verify validity of this data without them knowing the transaction amounts.
If you are panically afraid of commitments do not worry. This section is about the cryptographic commitments! If you recall the hashing functions tutorial you probably know by now that a hashing function can be used to assign a number to anything and if that function is good it is unlikely to find two different things assigned same number. Such hashing function can be used to form a cryptographic commitment.
For an example of a cryptographic commitment let us imagine a scenario in which Alice and Bob have a bet who will win the world cup in one of games where people run and kick inflated piece of rubber. They do not want to reveal their bet to not influence each others choices, at same time they want to be sure the other party will not change their mind after the winner gets announced. They could form a commitment to a value and share those commitments. Due to irreversability of hashing function it is not going to be easy to find the matching value, at same time it is also very unlikely their choices would collide.
Just as a reminder, the commitment by
SHA256 hash function was caculated by simply feeding their committed values into the hash function. Now they simply wait for the world cup to end and winners gets announced. It turns out to be
FC Smelly Socks! Now they can both show their inputs to the hash function. Alice choice was
I bet for smelly socks football club and Bob’s
oi oi oi FC sweaty trousers will win! and looks like Alice has won! Bob double checks by feeding her choice into
SHA256 function and finds match with
cdd878c2097d1af4a1a36a399264acda21b46486c11b1ee1f6fee5019564a5bf and he does not believe she found a way to reverse this hash function so he believes she made this prediction when they both shared the commitments.
You probably noticed they decided to write some weird phrase instead of just official name of the club. Let us denote to be a weird way of writing . That was for the reasons of security as other parties could simply calculate the hash of each football club name to find a match. A way less creative way to achieve that would be to add some random number after official name and of course, note it down for later! In context of storing passwords in the database such value is referred to as
salt and in case of cryptographic commitment we may call it a
blinding factor .
| operator above is the concatenation.
Hashing functions have done the job when it comes to Alice’s and Bob’s bet. However in terms of commitments they do however have limitation of not allowing to perform any computation on committed data. Possibility of performing some operations such as addition could be useful, as we will see later. If instead of simple hashing function we use Pedersen commitments the following properties would hold
The above statement is a homomorphic property of the Pedersen commitments (Pedersen, n.d.). The homomorphic encryption is a type of encryption that allows to perform computation on the encrypted data without revealing it. In this case the computation is addition and subtraction of the commitments. The homomorphic property seems not so relevant for Alice’s and Bob’s world cup bet however for confidential transactions it is a game changer! Let us imagine a transaction represented as Pedersen commitment.
Back in 2015 Gregory Maxwell introduced the scheme of the confidential transactions based on Pedersen commitments allowing a very private way of storing transaction amounts. Here we will explain this concept in a Mimblewimble way, using Schnorr signature on the excess to prove amounts cancel out. Let us jump right into this concept and imagine that each participant forms own part of the transaction.
What is shown to the third party who keeps the records are values and and what this third party has to check is
which proves no value gets created out of thin air! Let us refer to that as a
non-inflation proof. Doing the above computation on the commitment is only possible if it has the homomorphic property. As long as the third party does not know the blinding factors and is not able to know how exactly the values of changes in account balances represented by numbers and .
Such commitment can be implemented using the elliptic curve cryptography by adding curve points corresponding to the blinding factors and amounts by using different generator points.
where generates the blinding factors indicated by and generates the values or amounts indicated by . Having vanishing difference of two commitment proving the non-inflation can be done by verifying a Schnorr signature with blinding factors as private keys. In the original formalism of confidential transactions participants would need to pick their blinding factors in such a way that makes them cancel out as well. Given the Mimblewimble approach, signature can only be valid if generated by which is true only if values cancel out. This can be verified in Python using our regular ECC code as follows
def isTransactionValid(G, inputs_data, outputs_data, p): inp, inputs_signature = inputs_data out, outputs_signature = outputs_data # calculate inputs - outputs P = inp - out # check if signature matches proving the difference is 0 inp_s, inp_R = inputs_signature out_s, out_R = outputs_signature s_comb = np.mod(inp_s - out_s, p) valid, _, _ = verify('m', s_comb, G, P, inp_R - out_R, p) return valid
G is the generator point. The other generator point is not required during the verification. To understand the notation of this function please check previous the minicurve library.
Let us consider a scenario in which we are a sort of private banking service in which we are in charge of managing people’s transactions. What is so private about our service is the fact that we manage those transactions without knowing the actual amounts being exchanged.
In this example we will use a small ECC finite field of a prime order to represent a storage space for the transactions. Our users would own outputs which are blinded using the blinding factors as described above. Our banking vault that stores the transactions can be visualized as follows.
In blue we mark elliptic curve solutions. In green we have the generator point for the blinding factors and in cyan the generator point for the amounts. In orange we mark the inputs that are owned by our clients. We can see there is some data there. There are two account balances in the field but hard to make any sense of it (and that’s the point!).
One of the inputs is marked as belonging to Alice. We can imagine Alice has revealed which input belongs to her in order to perform transaction to Bob, who is our new clients. On the right plot above we see the points after the transaction. Indeed there is a new input we attributed to Bob but we do not know how many coins have been transferred to his account. Alice’s point also changed, meaning that her balance has updated, but what amount, that we cannot really tell.
As you can see, as verifier we know nothing, we only check the signature and that proves the net difference is zero, but let us imagine we are Alice and Bob just to explain how this field was generated and how the transaction was created. Since now we are putting ourselves in the shoes of the participants of the transaction we can reveal the confidential information.
It means that Alice has coins and Bob is receiving coin. They are both participants of the transaction thus they both know those values. Alice is blinding her input with value and Bob has just chosen value to blind his newly created input. Only they know those values and they did not share them with each other. Once the transaction is done the input belonging to Alice will be spent thus she needs to also create an output for herself that contains the change of the transaction, she decided to choose the value of to blind her new balance of coins
To perform the transaction each of participants creates a Schnorr signature using their blinding factors as private keys. Then we combined all the inputs and outputs
and their corresponding signatures as well just as done in the previous tutorial on multisignatures. The corresponding Python code of the process of forming transaction can be found here. The Schnorr signature can only be valid of terms generated by form infinity point (cancel out) and that is the case if
where is transaction excess. Valid signature proves non-inflation as difference of inputs and outputs vanishes as well as ownership as only participant knowing the blinding factor can produce valid signature. In the original formalism of confidential transactions participants would need to pick blinding factors in a way to cancel out.
We explained what commitments are in general. Then we extended it to Pedersen commitments to provide the homomorphic property and motivated it by the need of confidential transactions. For the latter, we provided a small example of transaction with blinded amounts and visualized it on one of our small finite fields from previous tutorials.
Franckly, the fact that this code works and the example transaction is valid is a blind luck. Designing the finite field of prime order with two generator points providing sufficient key space is a huge challenge. I managed to find random nonces for the signature that makes it all work. Please see it as a way to illustrate how it works and not as an actual implementation. In cryptography you should never “hack” your own curve, use fields which have been designed and proven by experienced cryptographers.
One might have noticed that transaction participant could introduce negative inputs and thus increase own account balance. This hack is addressed in the Mimblewimble protocol by using bulletproofs to prove the amounts are not negative. I honestly hope to cover entire Mimblewimble at some point someday. As for this tutorial, I would like to thank @kurt2, @vegycslol and @phyro for the interesting discussion on the cryptography channel in the grincoin keybase team. In addition, special thanks again to @phyro and John Tromp for taking their time to read this article and providing comments for the revised version.
The full source code is provided in the public gist repository. As usual, if you find mistakes or have questions please do not hesitate to reach me. Feel free to tweet me and let me know.
- Pedersen, T. P. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Advances in Cryptology — CRYPTO ’91 (pp. 129–140). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-46766-1_9