multilayered Archives

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).