Monero

You are currently browsing the archive for the Monero category.

Monero – Content

June 18, 2018 in Monero | No comments

The Monero Building Blocks series is the result of a personal interest in the mathematical underpinnings of Monero. My interest is primarily derived from Monero’s ability to conceal information about senders, receivers and transacted amounts, all the while maintaining proper operation of the network. It is my hope that this typescript help the reader understand the technology better. We divide the work into a series of 10 parts:

Part 1 – Prerequisites needed to construct and analyze digital signature schemes.
Part 2 – Description of a generic signature scheme introduced by Pointcheval & Stern [5] and analysis of its security: correctness, unforgeability.
Part 3 – Introduction to ring signature schemes and their security analysis.
Part 4 – Description of a generic ring signature scheme by Herranz & Saéz [1] and analysis of its security: correctness, unforgeability, anonymity.
Part 5 – Introduction to Cryptonote’s original linkable ring signature scheme [6] and analysis of its security: correctness, unforgeability, exculpability, anonymity, linkability.
Part 6 – Description of a variant of the Linkable Spontaneous Anonymous Group (LSAG) scheme by Liu, Wei, and Wong [2] and analysis of its security: correctness, unforgeability, exculpability, anonymity, linkability.
Part 7 – Description of the Multilayered Linkable Spontaneous Anonymous Group (MLSAG) signature scheme used in Monero as introduced by Shen Noether [4], and analysis of its security: correctness, unforgeability, exculpability, anonymity, linkability.
Part 8 – Introduction to Confidential Transactions (CT) and Pedersen Commitments as described by Gregory Maxwell [3].
Part 9 – Combining MLSAG and CT into a single RingCT signature scheme [4] (with 2 variants: RingCT Type Full and RingCT Type Simple) to mask the origins and the amount of funds transacted.
Part 10 – Introduction to Monero’s and Cryptonote’s Stealth Address system [6] to ensure that any 2 transactions can not be proven to be destined to the same person. This protects the recipient of funds.

I assume that the reader is familiar with basic probability theory, modulo arithmetic, as well as group theoretic concepts including the notions of cyclic groups and elliptic curve groups over finite fields. A concise introduction to group and field theory can be found in this post, and an introduction to elliptic curve groups in this one.

References

[1] J. Herranz and G. Saez. Forking lemmas in the ring signatures’ scenario. Proceedings of INDOCRYPT’03, Lecture Notes in Computer Science(2904):266-279, 2003.

[2] J. K. Liu, V. K. Wei, and D. S. Wong. Linkable spontaneous anonymous group signature for ad hoc groups. ACISP, Lecture Notes in Computer Science(3108):325-335, 2004.

[3] Greg Maxwell. Confidential transactions, 2015.

[4] S. Noether and A. Mackenzie. Ring condential transactions. Monero Research Lab, 2016.

[5] D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.

[6] N. Van Saberhagen. Cryptonote 2.0. , 2013.

Elliptic Curve Groups – Crypto Theoretical Minimum

June 18, 2018 in Bitcoin, Monero, Prerequisites | No comments

Download pdf here: Elliptic Curve Groups

1. Introduction and motivation

The sempiternel question of how to gain and maintain power has haunted the minds of humanity’s brightest and darkest since the dawn of civilization. Be it physical (e.g., military) or economical (e.g., wealth), power’s very existence relied in part on access to information. Asymmetric information that is. Numerous are history’s examples that demonstrate how entities that knew what others didn’t and that were able to act on it, benefited from an unfair advantage. The quest for sustainable power motivates the protection of one’s proprietary information and the attempt at breaching that of the others.

Although significant in its own right, the pursuit of power is not the only motivator to conceal information. Privacy, in so far as the individual’s well-being is concerned, is another. In that respect, two areas stand out. The first is concerned with the unique nature of a human persona. As a matter of observation, and at the risk of irritating adherents of monism, the attributes of a human personality are so varied. Each attribute exists on a wide spectrum, making it unlikely that any two individuals have the same profile so to speak. The privacy spectrum is no exception, and while some live their lives as an open book, others might not even be comfortable sharing their half title page. The second area is concerned with the safety of a certain subset of individuals, e.g., whistle-blowers. They may hold sensitive information destined to be shared with a specific party. Should this information fall in the wrong hands, it could jeopardize the safety of the source.

It is therefore reasonable to assume that not every piece of information is meant to be common knowledge. One could certainly debate the merits of such a claim and in the process, revisit the very foundation of power, privacy and safety. The fact remains however, that information can be a source of influence, discomfort, and danger. One way of protecting specific content and limiting its access to intended parties only, is through the use of encryption and decryption algorithms.

Read the rest of this entry »

Tags: Curve25519, ed25519, Edward, elliptic curve, elliptic curve group, Montgomery, Twisted edward, Weierstrass

The Stealth Address System

May 17, 2018 in Bitcoin, Monero | No comments

Download pdf here: The Stealth Address System

1. Introduction

The previous nine parts introduced Monero’s privacy and confidentiality attributes in so far as senders’ identities and transaction amounts were concerned. This part focuses on privacy with respect to the recipients of funds. To that end, we introduce the stealth address system [8] to ensure that any two transactions remain unlinkable, i.e., can not be proven to be destined to the same entity.

We divide this part into two sections. The first is an overview of some of the anonymity limitations of Bitcoin. The second introduces Cryptonote’s stealth address system which when coupled with ringCT, ensures a highly anonymous and confidential environment.

Anonymity over the blockchain

2. On Bitcoin’s anonymity … or lack thereof

In what follows, we describe two avenues that can be used separately or jointly to conduct a deanonymization attack on Bitcoin users. The first has to do with the propagation mechanisms of Bitcoin transactions over the network, and the second with the structure of a transaction. In addition, we describe some common practices that help an attacker link a Bitcoin address to a real-world identity.

Read the rest of this entry »

Tags: anonymity, Monero, one-time private key, one-time public key, spend key, Stealth, tracking key, unlinkable, view key

RingCT and Anatomy of Monero Transactions

May 13, 2018 in Monero | No comments

Download pdf here: RingCT and Anatomy of Monero Transactions

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: confidential, MLSAG, Monero, Pedersen commitment, Privacy, ringCT, transaction

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.

Read the rest of this entry »

Tags: anonymity, confidential transaction, Monero, Pedersen commitment

MLSAG Signature Scheme

May 7, 2018 in Monero | No comments

Download pdf here: MLSAG Signature Scheme

1. Introduction

Monero stands out from other cryptocurrencies in its ability to hide the signer, conceal the transaction amount, and protect the identity of the recepient. Parts 1, 2, 3, 4, 5, and 6 helped us build the foundation to better understand and appreciate the security properties of ring signatures (albeit in the RO model). This part (introduction to MLSAG), as well as part 8 and part 9 will focus on Monero’s privacy in so far as the signer’s identity and the transaction amount are concerned. Part 10 will introduce stealth addresses as a mechanism to protect the identity of the fund’s recipient.

In order to describe how a Monero transaction hides both the signer’s identity and the amount of the transaction, we introduce 2 additional concepts:

A generalization of the LSAG signature (introduced in part 6) to allow each member of the ring to have a key-pair vector $[(pk_1,sk_1),.,(pk_n,sk_n)]$ instead of only one pair $(pk,sk).$
A particular map known as the Pedersen Commitment that will be used to hide transaction amounts while allowing the network to check that input and output amounts always balance out.

Recall that by proving that a digital signature scheme was unforgeable, one gets the assurance that only the signing algorithm ${\Sigma}$ associated with a given ring member can produce a valid signature (i.e., verified by $\mathcal{V}$ ). Any other procedure that bypasses ${\Sigma}$ will result in a failed attempt of forgery with overwhelming probability. We note the following about the verification process of $\mathcal{V}$ :

In a “non-ring” setting, the verification is done using a particular public key $pk_{\pi}$ . The validation of a given signature proves that the signer of the message (in this case user $\pi$ ) knows the secret key $sk_{\pi}$ associated with $pk_{\pi}$ . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair ( $pk_{\pi},sk_{\pi}$ ) signed the message.
In a ring setting, the verification is conducted using a public key vector $L \equiv [pk_1,...,pk_{\pi},...,pk_n]$ known as a ring. This vector is used to conceal the identity of the signer. The validation of a given signature proves that the the signer of the message (in this case user $\pi$ ) knows the secret key associated with one of the public keys in $L$ . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair ( $pk_{\pi},sk_{\pi}$ ) signed the message, for some index $1 \leq \pi \leq n$ that no one other then the actual signer knows.
The ring setting can be generalized further by allowing each ring member $i, 1 \leq i \leq n$ to have a key-pair vector of length $m$ , given by $[(pk_{i}^1, sk_{i}^1),...,(pk_{i}^m, sk_{i}^m)]$ , as opposed to a unique key pair $(pk_i, sk_i)$ . In this setting, the verification is conducted using a public key matrix

$PK= \begin{bmatrix} pk_1^1 & ... & pk_{\pi}^1 & ... & pk_n^1 \\ ... & ... & ... & ... & ...\\ pk_1^m & ... & pk_{\pi}^m & ... & pk_n^m \\ \end{bmatrix}$

The validation of the signature proves that the signer knows the secret key associated with each one of its public keys. In other terms, there exists a column in $PK$ (say column $1 \leq \pi \leq n$ ) such that the signer knows the secret key associated with each public key appearing in that column. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair vector $[(pk_{\pi}^1,sk_{\pi}^1),...,(pk_{\pi}^m,sk_{\pi}^m)]$ signed the message, for some index $1 \leq \pi \leq n$ (that no one other then the actual signer knows).

Read the rest of this entry »

Tags: LSAG, MLSAG, Monero, multilayered, ring signature, Security

LSAG Signature Scheme

April 26, 2018 in Monero | No comments

Download pdf here: LSAG Signature Scheme

1. Introduction

For a given ring size $n$ , Cryptonote’s original scheme (as introduced in part 5), generates signatures of the form $(I, c_1,..,c_n,r_1,..,r_n)$ consisting of $(2n+1)$ arguments. It turns out that a more efficient scheme initially introduce in [3] and later adapted by Adam Back in [1] can achieve the same security properties as Cryptonote’s with $(n+2)$ arguments instead (a reduction factor that tends to 2 as $n$ tends to $\infty$ ). The scheme introduced in [3] is known as Linkable Spontaneous Anonymous Group signature or LSAG signature scheme for short. In part 7 of this series, we will see how [4] generalizes the LSAG construct to build the foundation of Monero’s current ringCT signature scheme.

2. The LSAG scheme

The LSAG signature introduced in [3] is built on a group $E$ of prime order $q$ and generator $G$ . Moreover, it uses 2 statistically independent ROs:

$\mathcal{H}_1: \{{0,1\}^*} \longrightarrow \mathbb{F}_q$
$\mathcal{H}_2: \{{0,1\}^*} \longrightarrow E$

In what follows we introduce a slightly modified LSAG scheme that will allow an easier comparison to Cryptonote’s original scheme. We carry forward all the notation used in the Cryptonote scheme to the current LSAG definition. In particular, we let $E$ be a large finite group generated by the same elliptic curve introduced in part 5 (refer to the post entitled Elliptic Curve Groups for an introduction to this topic). We also consider the same base point $G$ . Recall that the base point is chosen in such a way to ensure that it has a large prime order $l < q.$ All arithmetic is done in the subgroup $\{{G\}}$ of the elliptic curve group $E.$ As a matter of convention, we write $\{{G\}^{*}} \equiv \{{G\}} - e.$

Read the rest of this entry »

Tags: anonymity, Group, Linkable, LSAG, Monero, Privacy, ring signature

Cryptonote’s Ring Signature Scheme

April 23, 2018 in Monero | No comments

Download pdf here: Cryptonote’s Ring Signature Scheme

1. Introduction

In this part, we introduce Monero’s original signature scheme as described in van Saberhagen’s seminal Cryptonote paper [2]. The scheme is an adaptation of the Traceable Ring Signature introduced by Fujisaki and Suzuki [1]. The most recent version of Monero implements a different signature known as RingCT. It modifies the original scheme to accomodate confidential transactions. We will discuss it in detail in parts 7, 8 and 9.

Security analysis of ring schemes consisted primarily in proving a) correctness, b) resilience against EFACM attacks in the RO model (unforgeability), and c) anonymity (i.e., signer ambiguity according to e.g., definition # 1 or # 2 as previously described in part 3). However, none of these security metrics tells if 2 signatures were generated by the same user or not. Doing so does not necessarily break the anonymity of the signer, but rather establishes a relationship between pairs of signatures. Identifying whether 2 signatures are linked or not is essential when dealing with electronic cash for example. In this case, the network must not tolerate the double spending of the same unit of electronic currency on 2 different transactions. In an electronic cash setting, the message typically consists of an unspent transaction output (also known as UTXO) and the objective is to make sure that the owner of a UTXO does not sign it twice (i.e., double spend it). Whenever this happens, the incident must be flagged and proper measures taken.

Monero in particular, and cryptocurrencies in general are prone to the double spending problem. This motivates the need to have an additional security requirement to tell if 2 signatures were issued by the same user. This must be done without releasing the identity of the user. We refer to the new requirement as linkability. It can commonly be achieved by adding to the ring signature a new signer-specific component known as a tag or a key-image.

Formally, we define a linkable ring signature scheme as a set of 4 algorithms:

The signer’s key generation algorithm $\mathcal{G}$ (as described in part 1)
The ring signing algorithm $\Sigma$ (as described in part 1).
The ring verification algorithm $\mathcal{V}$ (as described in part 1)
The ring linkability algorithm $\mathcal{L}$ . Its input consists of a set of tags (key-images) and a given signature $\sigma$ . It checks if $\sigma$ ‘s tag is included in the tag set. If so, it outputs Linked. Otherwise, it outputs Independent and adds the new tag to the set.

Read the rest of this entry »

Tags: anonymity, Cryptonote, Monero, Privacy, ring signature

Herranz & Saèz Generic Ring Signature

April 16, 2018 in Monero | No comments

Download pdf here: Herranz & Saèz Generic Ring Signature

1. Introduction

In the next 4 parts of this series, we look at various ring signature schemes and prove their security in the RO model. This part is dedicated to the analysis of a generic class of ring signature schemes introduced in [1] and inspired by [2]. We also introduce a specific instance of the generic scheme which is itself a generalization of the non-interactive Schnorr signature.

2. Herranz & Saèz generic scheme

The scheme is built on a security parameter $k$ , which by design corresponds to the length in bits of the output of the random oracle $\mathcal{H}$ . Given a message $m$ and a ring $L \equiv \{{A_1,...,A_n \}}$ of $n$ members, the signing algorithm $\Sigma$ outputs a signature $\sigma(m,L) \equiv (r_1,...,r_n,h_1,...,h_n,\delta)$ where:

The $r_i$ ‘s are pairwise-different random elements chosen from a pre-defined large set. The term pairwise-different means that $\forall i,j \in \{{1,...,n\}}$ , $(i \neq j) \Rightarrow (r_i \neq r_j)$ .
$\forall i \in \{{1,...,n\}}, h_i = \mathcal{H}(m,r_i)$ . That means that $h_i$ is the RO’s output on query $(m,r_i)$ .
$\delta$ is fully determined by $m, r_i$ , and $h_i$ , for all $i \in \{{1,...,n\}}$ .

By design, we require that the probability of selecting any particular $r_i$ be upper-bounded by $\frac{1}{2^{k-1}}$ . For example, consider the finite field $\mathbb{Z}_{q}$ over a large prime $q \geq 2^k$ . The probability of choosing a particular value for $r_i$ in the mutiplicative cyclic group $\mathbb{Z}^{*}_q$ is equal to $\frac{1}{q-1}$ (assuming a uniform distribution over $\mathbb{Z}^{*}_q$ ). Clearly, this is less than or equal to $\frac{1}{2^k-1} < \frac{1}{2^{k-1}}$ .

Read the rest of this entry »

Tags: anonymity, Crypto, Privacy, ring signature, Schnorr

« Older entries

Delfr

Monero

Monero – Content

References

Elliptic Curve Groups – Crypto Theoretical Minimum

1. Introduction and motivation

The Stealth Address System

1. Introduction

2. On Bitcoin’s anonymity … or lack thereof

RingCT and Anatomy of Monero Transactions

1. Introduction

Confidential Transaction and Pedersen Commitment

1. Introduction

2. Group homomorphism

MLSAG Signature Scheme

1. Introduction

Cryptonote’s Ring Signature Scheme

1. Introduction

Herranz & Saèz Generic Ring Signature

1. Introduction

2. Herranz & Saèz generic scheme

Recent Posts

Categories

Meta

Monero

References

1. Introduction and motivation

1. Introduction

1. Introduction

2. On Bitcoin’s anonymity … or lack thereof

1. Introduction

1. Introduction

2. Group homomorphism

1. Introduction

1. Introduction

2. The LSAG scheme

1. Introduction

1. Introduction

2. Herranz & Saèz generic scheme

Stay in touch

Recent Posts

Categories

Meta