Confidential Transaction and Pedersen Commitment

May 7, 2018 in Monero | No comments

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.

We call $k(x,a)$ a commitment. $a$ denotes the amount we commit to, while $x$ is referred to as the blinding factor. Note that $\forall c \in \{{G\}},\forall a \in \mathbb{F}_l$ , there always exists a blinding factor $x \in \mathbb{F}_l$ such that $k(x,a) = c.$ Indeed, given $c$ and $a$ , an adequate $x$ must satisfy $(x \otimes G) \oplus (a \otimes H) = c$ (by definition of the map $k$ ). This is equivalent to finding $x$ such that $x \otimes G = c \ominus (a \otimes H).\ (\ominus$ denotes the additive inverse of $\oplus$ over the group $\{{G\}}).$ Since $c \ominus (a \otimes H) \in \{{G\}}$ and since $G$ is a generator of $\{{G\}}$ , we can be certain of the existence of such an $x.$

Note that this does not mean that we can find the value of $x$ since this would require finding the DL of $c \ominus (a \otimes H)$ in base $G$ . However, it means that for a given amount $a$ , one could achieve any commitment value $c \in \{{G\}}$ by appropriately choosing $x \in \mathbb{F}_l$ . A consequence of this is if we are given $a$ and we randomly choose $x \in \mathbb{F}_l$ , then $c$ would look random over $\{{G\}}.$ So given a transaction amount $a \in \mathbb{F}_l$ , one can randomly generate a blinding factor $x \in \mathbb{F}_l$ and calculate $k(x,a) \equiv (x \otimes G) \oplus (a \otimes H).$ We now introduce the notion of a confidential transaction.

3. Confidential transaction

In Bitcoin, transaction amounts are openly published to allow the network to verify that no value was created out of thin air or destroyed. The Bitcoin network checks that for each transaction, the total input amount of relevant UTXOs (denoted by $(a_{in})_i,\ i \in \{{1,...,m\}}$ ) is equal to that of the output UTXOs (denoted by $(a_{out})_j,\ j \in \{{1,...,t\}}$ ). It must be that

$\sum_{i=1}^m (a_{in})_i = \sum_{j=1}^t (a_{out})_j$

The question that a confidential transaction scheme must answer is whether the above equation can be verified without accessing the exact transaction values $(a_{in})_i$ and $(a_{out})_j$ . We now describe a method that solves the question by using the homomorphic Pedersen Commitment previously introduced. Without loss of generality:

$\forall i \in \{{1,...,m\}}$ , let $(C_{in})_i = ((x_{in})_i \otimes G) \oplus ((a_{in})_i \otimes H)$ be the Pedersen Commitment associated with amount $(a_{in})_i$ with blinding factor $(x_{in})_i$ randomly chosen in $\mathbb{F}_l.$
Let $(a_{out})_t \equiv txfee$ be the miner’s transaction fee and let $(C_{out})_t = (a_{out})_j \otimes H$ be the Pedersen Commitment associated with txfee. The blinding factor $(x_{out})_t$ is deliberatly chosen to be 0 (i.e., the identity element of $\mathbb{F}_l).$
$\forall j \in \{{1,...,t-1\}}$ , let $(C_{out})_j = ((x_{out})_j \otimes G) \oplus ((a_{out})_j \otimes H)$ be the Pedersen Commitment associated with amount $(a_{out})_j$ with blinding factor $(x_{out})_j$ randomly chosen in $\mathbb{F}_l$ . We additionaly require that $\sum_{i=1}^m (x_{in})_i = \sum_{j=1}^{t-1} (x_{out})_j \pmod{l}$ (the rationale will become clear in the next paragraph).

Suppose that:

$\sum_{i=1}^m (C_{in})_i = \sum_{j=1}^{t} (C_{out})_j$

This is equivalent to:

$\sum_{i=1}^m (C_{in})_i = \sum_{j=1}^{t-1} (C_{out})_j\ \oplus\ (txfee \otimes H)$
(by definition of txfee and $(c_{out})_t)$

$\iff\ \sum_{i=1}^m [((x_{in})_i \otimes G) \oplus ((a_{in})_i \otimes H)]$

$= \sum_{j=1}^{t-1} [((x_{out})_j \otimes G) \oplus ((a_{out})_j \otimes H)]\ \oplus\ (txfee \otimes H)$

$\iff\ \sum_{i=1}^m k((x_{in})_i, (a_{in})_i)$

$= \sum_{j=1}^{t-1} k((x_{out})_j, (a_{out})_j)\ \oplus\ (txfee \otimes H)$

$\iff\ k(\sum_{i=1}^m (x_{in})_i, \sum_{i=1}^m (a_{in})_i)$

$= k(\sum_{j=1}^{t-1} (x_{out})_j, \sum_{j=1}^{t-1} (a_{out})_j)\ \oplus\ (txfee \otimes H)$

(by invoking the additive homomorphic property of the Pedersen Commitment map)

$\iff\ [(\sum_{i=1}^m (x_{in})_i) \otimes G]\ \oplus\ [(\sum_{i=1}^m (a_{in})_i) \otimes H]$

$= [(\sum_{j=1}^{t-1} (x_{out})_j) \otimes G]\ \oplus\ [\sum_{j=1}^{t-1} (a_{out})_j) \otimes H]\ \oplus\ [txfee \otimes H]$

$\iff\ [\sum_{i=1}^m (x_{in})_i\ -\ \sum_{j=1}^{t-1} (x_{out})_j] \otimes G$

$=[txfee\ +\ \sum_{j=1}^{t-1} (a_{out})_j)\ -\ \sum_{i=1}^m (a_{in})_i)] \otimes H$

where $+$ and $-$ are addition and subtraction in modulo $l$ arithmetic over $\mathbb{F}_l.$ By design, the left hand side is 0 (because $\sum_{i=1}^m (x_{in})_i = \sum_{j=1}^{t-1} (x_{out})_j \pmod{l}$ ). We can thus conclude that if $\sum_{i=1}^m (x_{in})_i = \sum_{j=1}^{t-1} (x_{out})_j \pmod{l}$ , then:

$\sum_{i=1}^m (C_{in})_i = \sum_{j=1}^{t} (C_{out})_j$

$\iff \sum_{i=1}^m (a_{in})_i = \sum_{j=1}^{t} (a_{out})_j \pmod{l}$

By ensuring that

$\sum_{i=1}^m (x_{in})_i = \sum_{j=1}^{t-1} (x_{out})_j \pmod{l}$ , and
$\forall i \in \{{1,...,m\}},\ \forall j \in \{{1,...t\}}$ the amounts $(a_{in})_i$ and $(a_{out})_j$ remain confined to a pre-defined range $[0, 2^r] \subset \mathbb{F}_l.$ $r$ is chosen in such a way that $2^r$ is significantly smaller than $l$ . More specifically, suppose $m_{max}$ and $t_{max}$ respectively denote the maximum number of inputs and outputs that can be used in any given transaction. By letting $r < min(log_2(\frac{l}{m_{max}}), log_2(\frac{l}{t_{max}})),$ we are guaranteed that:
$\sum_{i=1}^m (a_{in})_i \leq m_{max} \times max_{i=1}^m (a_{in})_i \leq m_{max} \times 2^r < l$

$\sum_{j=1}^t (a_{out})_j \leq t_{max} \times max_{j=1}^t (a_{out})_j \leq t_{max} \times 2^r < l$

we get the following equivalence:

$\sum_{i=1}^m (C_{in})_i\ \ominus\ \sum_{j=1}^{t} (C_{out})_j = 0$

$\iff \sum_{i=1}^m (a_{in})_i - \sum_{j=1}^{t} (a_{out})_j = 0$

It is important to note that the amounts balance out in actuality and not in the more relaxed $\pmod{l}$ sense. This is because of the constraint we imposed on all transaction amounts to be confined to the $[0,2^r]$ range. If this constraint was no imposed, one would be able to create or destroy Monero currency while still maintaining a balanced equation. To see this, suppose transaction amounts can take on any value in $\mathbb{F}_l$ instead of being restricted to $[0,2^r].$ Let $m=3$ with $(a_{in})_1 = l-4,\ (a_{in})_2 = 3,\ and (a_{in})_3 = 5.$ Also let $t=2$ with $(a_{out})_1 = 3,\ and (a_{out})_2 = 1.$

Clearly, $\sum_{i=1}^m (a_{in})_i - \sum_{j=1}^{t} (a_{out})_j = l \neq 0.$

However, $\sum_{i=1}^m (a_{in})_i - \sum_{j=1}^{t} (a_{out})_j = 0 \pmod{l}.$

If this transaction gets approved by the network, we would have effectively destroyed $l$ units of currency. Conversely, exchanging the input and output values would allow the creation of $l$ units of currency out of thin air. This example demonstrates the importance of having a balanced equation independent of modulo $p$ arithmetic. By confining all transaction amounts to the $[0,2^r]$ range, we ensure that this is the case. To prove that a transaction amount lies in a certain range, Monero makes use of the Borromean signature construct. We are not covering its mechanics in this work but the interested reader can consult [2].

The result above allows one to safely replace the transaction amounts by their respective Pedersen Commitments (i.e., hide the transaction amounts) while still ensuring proper accounting.

References

[1] Greg Maxwell. Confidential transactions, 2015.

[2] G. Maxwell and A. Poelstra. Borromean ring signatures. 2015.

Tags: anonymity, confidential transaction, Monero, Pedersen commitment

No comments

Comments feed for this article

Trackback link: https://delfr.com/confidential-transaction-moneros-part-8/trackback/

Delfr

Confidential Transaction and Pedersen Commitment

1. Introduction

2. Group homomorphism

3. Confidential transaction

References

No comments

Reply Cancel reply

Recent Posts

Categories

Delfr

Confidential Transaction and Pedersen Commitment

1. Introduction

2. Group homomorphism

3. Confidential transaction

References

No comments

Reply Cancel reply

Stay in touch

Recent Posts

Categories