Pedersen commitment

You are currently browsing articles tagged Pedersen commitment.

1. Introduction

In part 7 we introduced the MLSAG ring signature scheme. Among other things, it safeguarded the anonymity of the signer. In part 8 we discussed the notions of Pedersen Commitments and Confidential Transactions. They were used to mask transaction amounts without compromising the proper bookkeeping of balances on the network. In this part, we combine the two in a new structure known as ring Confidential Transaction or ringCT.

It turns out that combining both concepts in a single mathematical construct requires additional work. In the first section, we explain why outright combination of the aforementioned concepts fails to preserve the anonymity of the sender.

In the second section we remedy the situation by introducing the notion of a non-zero commitment. This will form the basis of Monero’s ringCT scheme.

The last section goes over the mechanics of how a Monero transaction is created and includes references to relevant parts of the code base. We introduce two variants of ringCT, namely ringCT Type Full and ringCT Type Simple. We finally conclude with a breakdown of the components of a real-life Monero transaction.

Read the rest of this entry »

Tags: , , , , , ,

Download pdf here: CT and Pedersen Commitment

1. Introduction

Pedersen Commitments are at the heart of how Monero conceals transaction amounts. The notion of a confidential transaction as enabled by Pedersen Commitments were outlined and defined by Gregory Maxwell in [1]. In what follows we first introduce the notion of a group homomorphism (of which the Pedersen Commitment map is a particular instance), we then define the Pedersen Commitment map, and finally present the mechanisms of a confidential transaction enabled by a such a map.

2. Group homomorphism

Let (M, \boxplus) and (N, \oplus) be 2 groups with respective group operations \boxplus and \oplus. A function f: M \rightarrow N is called a group homomorphism if and only if

f(u \boxplus v) = f(u) \oplus f(v),\ \forall u, v \in M

In other terms, operating on 2 elements in M and then applying f is equivalent to applying f on each element separately and then operating on the 2 outputs in N.

We now introduce a specific instance of a group homomorphism that we will invoke when concealing transaction amounts with Monero as part of the confidential transaction construct. In particular, we conduct arithmetic in the subgroup \{{G\}} of the elliptic curve group E. introduced in part 5 (refer to the post entitled Elliptic Curve Groups for an introduction to this topic)

Let (N, \oplus) \equiv (\{{G\}}, \oplus), and let (M, \boxplus) \equiv (\mathbb{F}_l \times \mathbb{F}_l, +) where + denotes element-wise addition in modulo l arithmetic over \mathbb{F}_l \times \mathbb{F}_l.

It is a known result in group theory that if a is a generator of a cyclic group \{{a\}} of order m, then there are \phi(m) elements of the group that have order m (\phi is the euler function introduced in part 1). In our case, the generator G of \{{G\}} has prime order l. Moreover \phi(l) = l-1 (since l is prime). Hence we can find l-1 other generators of \{{G\}}. Let H \neq G be another generator such that the DL (discrete logarithm) of H with respect to G is unknown. We define the Pedersen Commitment map (which we will later use to build a confidential transaction) as follows:

k: \mathbb{F}_l \times \mathbb{F}_l \rightarrow \{{G\}}

(x,a) \rightarrow k(x,a) \equiv (x \otimes G) \oplus (a \otimes H)

We claim that the map k is additively homomorphic. To see why, let (x_1,a_1),\ (x_2,a_2)\ \in \mathbb{F}_l \times \mathbb{F}_l. We then have:

k(x_1,a_1) \oplus k(x_2,a_2) = [(x_1 \otimes G) \oplus (a_1 \otimes H)] \oplus [(x_2 \otimes G) \oplus (a_2 \otimes H)]

= ((x_1 + x_2) \otimes G)) \oplus ((a_1 + a_2) \otimes H))
(where + denotes \pmod{l} over \mathbb{F}_l)

=k((x_1+x_2),(a_1+a_2))\ =\ k((x_1,a_1) + (x_2,a_2))

hence k is homomorphic.

Read the rest of this entry »

Tags: , , ,