Articles by bassamek

You are currently browsing bassamek’s articles.

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.

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 and be 2 groups with respective group operations and . A function is called a group homomorphism if and only if

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

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 of the elliptic curve group introduced in part 5 (refer to the post entitled Elliptic Curve Groups for an introduction to this topic)

Let , and let where denotes element-wise addition in modulo arithmetic over

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

We claim that the map is additively homomorphic. To see why, let We then have:

(where denotes over )

hence is homomorphic.

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:

1. A generalization of the LSAG signature (introduced in part 6) to allow each member of the ring to have a key-pair vector instead of only one pair
2. 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 associated with a given ring member can produce a valid signature (i.e., verified by ). Any other procedure that bypasses will result in a failed attempt of forgery with overwhelming probability. We note the following about the verification process of :

• In a “non-ring” setting, the verification is done using a particular public key . The validation of a given signature proves that the signer of the message (in this case user ) knows the secret key associated with . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair () signed the message.
• In a ring setting, the verification is conducted using a public key vector 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 ) knows the secret key associated with one of the public keys in . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair () signed the message, for some index that no one other then the actual signer knows.
• The ring setting can be generalized further by allowing each ring member to have a key-pair vector of length , given by , as opposed to a unique key pair . In this setting, the verification is conducted using a public key matrix

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 (say column ) 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 signed the message, for some index (that no one other then the actual signer knows).

1. Introduction

For a given ring size , Cryptonote’s original scheme (as introduced in part 5), generates signatures of the form consisting of 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 arguments instead (a reduction factor that tends to 2 as tends to ). 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 of prime order and generator . Moreover, it uses 2 statistically independent ROs:

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 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 . Recall that the base point is chosen in such a way to ensure that it has a large prime order All arithmetic is done in the subgroup  of the elliptic curve group As a matter of convention, we write

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 (as described in part 1)
• The ring signing algorithm (as described in part 1).
• The ring verification algorithm (as described in part 1)
• The ring linkability algorithm . Its input consists of a set of tags (key-images) and a given signature . It checks if ‘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.

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 , which by design corresponds to the length in bits of the output of the random oracle . Given a message and a ring of members, the signing algorithm outputs a signature where:

• The ‘s are pairwise-different random elements chosen from a pre-defined large set. The term pairwise-different means that , .
• . That means that is the RO’s output on query .
• is fully determined by , and , for all .

By design, we require that the probability of selecting any particular be upper-bounded by . For example, consider the finite field over a large prime . The probability of choosing a particular value for in the mutiplicative cyclic group is equal to (assuming a uniform distribution over ). Clearly, this is less than or equal to .

1. Introduction

This is a brief article that introduces the concept of a ring signature. In parts 4, 5, 6, and 7 we will look at specific instances of ring signature schemes — including those used in earlier and more recent versions of the Monero project — and analyze their security properties.

In 1991, Chaum and Van Heyst introduced a new class of signature schemes known as group signatures[2]. The core of the model consisted of a trusted entity known as the group manager that clusters a subset of users together into a group. The group manager provides each member of the group with a separate private key. The ingenuity of this structure lies in the fact that any member can sign messages in an anonymous fashion. This means that anybody who can access the signature, can also verify that it was created by one of the group members without knowing who specifically. The only entity that can identify the real signer is the trusted group manager. In group signature schemes, the anonymity of signers comes at the expense of relinquishing power to the group manager. Indeed, the trusted group manager is the only entity that:

• Decides who joins the group.
• Decides which member(s) get(s) banned from the group.
• Chooses the private key allocated to each member of the group.
• Identifies the real signer whenever a message is signed.

This setting works best if the group members agreed to cooperate beforehand . The group manager can then serve as the enforcer of this cooperation, revoking the membership of anyone trying to game the system.

The anonymity of group signatures paved the way to another class of signer-ambiguous shemes known as ring signature schemes. The expression ring signature was first coined by Rivest, Shamir, and Tauman[3]. Note that schemes fitting the definition of a ring signature have been proposed way before the publication of this paper. In a ring signature, there does not exist a pre-defined group of users. As a consequence, there does not exist any omnipotent group manager. Instead, the actual signer defines a set of members of her choosing before she signs a message. This set is known as a ring. The only constraint is that the ring must include the actual signer. The signer creates a signature using her private key and all the other ring members’ public keys. The ring can be arbitrary without the need to inform selected members of their participation — (all that is needed is access to their public keys which is usually common knowledge). The reason behind adopting the ring terminology is that “rings are geometric regions with uniform periphery and no center”[3].

1. Introduction

In the next few parts of this series, we look at various signature schemes and prove their security in the RO model. This part is dedicated to the analysis of Pointcheval and Stern Generic Signature Scheme of which the Schnorr scheme is an example. The generic scheme is built around a single pair. Later parts of this series will focus on ring signature schemes. Ring signatures embed the actual signer in a ring of other possible signers to hide her identity. We will discuss them in parts 3, 4, 5, 6, and 7.

2. Pointcheval and Stern generic signature scheme

For a given message , our generic scheme creates a signature where is a random element chosen from a pre-defined set, (i.e., RO output on query ), and is fully determined by and . By design, we require that the probability of selecting any particular be upper-bounded by for a given security parameter .

Schnorr’s signature scheme is an example that fits this generic model. To see why, recall that chooses a random commitment where is a pre-defined prime number. It then assigns where denotes a chosen generator of . Afterwards, is set to . Finally, is calculated as where denotes the signer’s private key. Note that can be any element of and so the probability that it takes on a specific value is equal to . By design, we choose the security parameter . This choice of guarantees that the aforementioned probability is upper-bounded by .

1. Introduction

We divide this post into 6 sections. Section 2 is a qualitative description of digital signature schemes. Section 3 motivates the introduction of hash functions along with some of their desired properties. Section 4 describes a hypothetical ideal random function known as a Random Oracle. Section 5 briefly introduces the notion of Probabilistic Turing Machines that will be needed when studying the security of digital signature schemes. Sections 6 and 7 describe 2 pillars introduced by Poitncheval & Stern to prove the resilience of some digital signature schemes against a forgery attack in the Random Oracle model. In particular, Setion 6 describes a reduction model to facilitate the security analysis of signature schemes. Section 7 states and proves an important lemma known as the splitting lemma.

There is one caveat: I assume that the reader is familiar with basic probability theory, modulo arithmetic, as well as some group theoretic concepts including the notions of cyclic groups and finite fields. A concise introduction to group and field theory can be found in this post. For a more detailed treatment, the reader can refer to e.g., [3].