Carrot

Carrot (Cryptonote Address on Rerandomizable-RingCT-Output Transactions) is an addressing protocol for the upcoming FCMP++ upgrade to Monero which maintains backwards compatibility with existing addresses. It does this while bringing new privacy and usability features, such as outgoing view keys. Carrot is designed to be indistinguishable on-chain from another potential addressing protocol, Jamtis, which will justify some seemingly strange design choices later on in this document.

1. Background

1.1 Cryptonote Addresses, Integrated Addresses, and Subaddresses

In 2013, the Cryptonote whitepaper [1] introduced an addressing scheme which remains a crucial component of Monero's privacy model today, providing recipient unlinkability across transactions. Unlike Bitcoin, which uses transparent addresses, Monero's use of addresses ensures that all created transaction outputs cannot be attributed to any single receiver regardless of the number of times an address is reused, and without requiring interactivity.

In the beginning, since there was only one address per wallet, a method was needed for receivers to differentiate their senders. Payment IDs [2], an arbitrary 32 byte string attached to transactions, was the initial solution to this problem. The aim was that users sending funds would include a 32 byte message that gave the recipient user enough evidence to attribute that transaction to them. Integrated addresses improved the UX of these payment IDs by having the recipient's wallet generate and include them inside of addresses, which were automatically added to the transaction data by the sender's wallet. They were also shortened to 8 bytes. Wallets then started encrypting the payment IDs on-chain, and adding dummies if no payment IDs were used, which greatly improved privacy.

In 2016, Monero iterated even further by introducing subaddresses [3], an addressing scheme that existing wallets could adopt, allowing them to generate an arbitrary number of unlinkable receiving addresses without affecting scan speed.

1.2 FCMP++

In order to tackle privacy shortcomings with Monero's ring signatures, there is a consensus protocol update planned called FCMP++, an abbreviation of "Full-Chain Membership Proofs + Spend Authorization + Linkability" [4]. In contrast to ring signatures' relatively small decoy set size, FCMP++ enables all transaction outputs on the blockchain to be used as decoys for each input. FCMP++'s deterministic anonymity avoids almost all the undesirable edge cases and targeted attacks against ring signatures, as well as improving on it in the normal case. To read more about the FCMP++ upgrade, the original author wrote a blog post outlining new features, academic work, etc.

However, most relevant to Carrot, FCMP++ has a subtle, but powerful effect on how transaction outputs can be composed on-chain. This effect is dubbed "Rerandomization" and is already applied to amounts in Monero RingCT [5] to make them confidential. Rerandomization in the context of FCMP++ opens the door for long-desired features, namely forward secrecy and outgoing view keys. Both of these features are described in greater detail in later sections.

1.3 Where Carrot fits in

Carrot is an addressing protocol, designed to be a layer on top the consensus protocol FCMP++. In other words, FCMP++ dictates the rules that transactions must follow in order to be valid, whereas Carrot provides a shared framework for how to transmit funds and otherwise interact with addresses meaningfully on FCMP++ transactions. Carrot also contains a recommended wallet specification, detailing how to construct public and private keys in a way which best leverages FCMP++. A wallet with the Carrot key hierarchy can expect flexibility in how wallet functions can be compartmentalized, as well as unconditional forward secrecy for change outputs, etc.

However, an equally important design consideration of Carrot is backwards compatibility. One can participate in the Carrot addressing protocol using preexisting Cryptonote addresses, subaddresses, and integrated addresses. No wallet key migration is required. Even without a migration, using the Carrot addressing protocol provides protection against the burning bug attack, conditional forward secrecy, etc. The exact breakdown of which wallets get which features is outlined in the following section. Furthermore, addresses generated by the new Carrot wallet key hierarchy will be of the same format as old addresses. Indeed, these new addresses will be computationally indistinguishable from old addresses, maintaining off-chain privacy and easing developer loads.

2. New Features

2.1 All wallets

Carrot immediately brings these features to both newly generated wallets and existing wallets.

2.1.1 Address-conditional forward secrecy

As a result of leveraging the FCMP++ consensus protocol, Carrot has the ability to hide all transaction details (sender, receiver, amount) from third-parties with the ability to break the security of elliptic curves (e.g. quantum computers), as long as the observer does not know receiver's addresses.

2.1.2 Janus attack mitigation

A Janus attack [6] is a targeted attack that aims to determine if two addresses A, B belong to the same wallet. Janus outputs are crafted in such a way that they appear to the recipient as being received to the wallet address B, while secretly using a key from address A. If the recipient confirms the receipt of the payment, the sender learns that they own both addresses A and B.

Carrot prevents this attack by allowing the recipient to recognize a Janus output.

2.1.3 Stateless burning bug mitigation

The burning bug [7] is a undesirable result of Monero's old scan process wherein if an exploiter creates a transaction with the same ephemeral pubkey, output pubkey, and transaction output index as an existing transaction, a recipient will scan both instances of these enotes as "owned" and interpret their balance as increasing. However, since key images are linked to output pubkeys, the receiver can only spend one of these enotes, "burning" the other. If the exploiter creates an enote with amount a = 0, and the receiver happens to spend that enote first, then the receiver burns all of the funds in their original enote with only a tiny fee cost to the exploiter!

An initial patch [8] was introduced secretly to catch when such an attempted attack occurred. However, this patch did not attempt to recover gracefully and instead simply stopped the wallet process with an error message. Further iterations of handling this bug automatically discarded all instances of duplicate output pubkeys which didn't have the greatest amount. However, all instances of burning bug handling in Monero Core require a complete view of all scanning history up to the current chain tip, which makes the workarounds somewhat fragile.

The original Jamtis [9] proposal by @tevador and the Guaranteed Address [10] proposal by @kayabaNerve were some of the first examples of addressing schemes where attempting a burn in this manner is inherently computationally intractable. These schemes somehow bind the output pubkey to an "input context" value, which is unique for every transaction. Thus, the receiver will only ever correctly determine an enote with a given output pubkey to be spendable for a single transaction, avoiding the burning bug without ever having to maintain a complete scan state.

Carrot prevents this attack statelessly in the same manner.

2.1.4 Payment ID confirmation

Payment IDs are confirmed by a cryptographic hash, which gives integrated address payment processors better guarantees, provides better UX, and allows many-output batched transactions to unambiguously include an integrated address destination.

2.2 New wallets only

These features are only available to wallets generated with the newly defined account key hierarchy. Existing Monero wallets will not inherit these features, unfortunately.

2.2.1 Internal forward secrecy

Enotes that are sent "internally" to one's own wallet will have all transactions details hidden (sender, receiver, amount) from third-parties with the ability to break the security of elliptic curves (e.g. quantum computers), even if the observer has knowledge of the receiver's addresses.

2.2.2 Address generator tier

This tier is intended for merchant point-of-sale terminals. It can generate addresses on demand, but otherwise has no access to the wallet (i.e. it cannot recognize any payments in the blockchain).

2.2.3 Payment validator tier

Carrot supports view-incoming-only wallets that can verify that an external payment was received into the wallet, without the ability to see where those payment enotes were spent, or spend it themselves. But unlike old Monero view-only wallets, a Carrot payment validator wallet cannot see "internal" change enotes.

2.2.4 Full view-only tier

Carrot supports full view-only wallets that can identify spent outputs (unlike legacy view-only wallets), so they can display the correct wallet balance and list all incoming and outgoing transactions, without the ability to spend anything.

3. Notation

3.1 Miscellaneous definitions

The function BytesToInt256(x) deserializes a 256-bit little-endian integer from a 32-byte input.
The function BytesToInt512(x) deserializes a 512-bit little-endian integer from a 64-byte input.
The function IntToBytes32(x) serializes an integer into a little-endian encoded 4-byte output.
The function IntToBytes64(x) serializes an integer into a little-endian encoded 8-byte output.
The function IntToBytes256(x) serializes an integer into a little-endian encoded 32-byte output.
The function RandBytes(x) generates a random x-byte string.
Concatenation is denoted by ||.
Bit-wise XOR (exclusive-or) is denoted by ⊕.

3.2 Hash functions

The function H_b(x) with parameters b, x, refers to the Blake2b hash function [11] initialized as follows:

The output length is set to b bytes.
Hashing is done in sequential mode.
The Personalization string is set to the ASCII value "Monero", padded with zero bytes.
The input x is hashed.

The function SecretDerive is defined as:

SecretDerive(x) = H₃₂(x)

The function Keccak256(x) refers to the Keccak function [12] parameterized with r = 1088, c = 512, d = 256.

3.3 Elliptic curves

Two elliptic curves are used in this specification:

Curve25519 - a Montgomery curve. Points on this curve include a cyclic subgroup 𝔾_M.
Ed25519 - a twisted Edwards curve. Points on this curve include a cyclic subgroup 𝔾_E.

Both curves are birationally equivalent, so the subgroups 𝔾_M and 𝔾_E have the same prime order ℓ = 2²⁵² + 27742317777372353535851937790883648493. The total number of points on each curve is 8ℓ.

3.3.1 Curve25519

The Montgomery curve Curve25519 [13] is used exclusively for the Diffie-Hellman key exchange with the private incoming view key. Only a single generator point B, where x = 9, is used. We denote the group additive identity element, or "point at infinity", for Curve25519 as 𝐼_M.

Elements of 𝔾_M are denoted by D, and are serialized as their x-coordinate. As is convention for Curve25519, the y coordinate is assumed to be the even value that satisfies the Montgomery curve equation. Scalar multiplication is denoted by a space, e.g. D = d B. In this specification, we always perform a "full" scalar multiplication on Curve25519 without scalar clamping, a notable difference from typical X25519 implementations. Using a clamped scalar multiplication will break completeness of the ECDH for existing pubkeys in addresses for which the private keys can be any element of F_ℓ.

3.3.2 Ed25519

The twisted Edwards curve Ed25519 [14] is used for all other cryptographic operations on FCMP++. The following generators are used:

Point	Derivation	Serialized (hex)
`G`	generator of 𝔾_E	`5866666666666666666666666666666666666666666666666666666666666666`
`H`	`H_p¹(G)`	`8b655970153799af2aeadc9ff1add0ea6c7251d54154cfa92c173a0dd39c1f94`
`T`	`H_p²(Keccak256("Monero generator T"))`	`966fc66b82cd56cf85eaec801c42845f5f408878d1561e00d3d7ded2794d094f`

Here H_p¹ and H_p² refer to two hash-to-point functions on Ed25519.

Elements of 𝔾_E are denoted by K or C and are serialized as 256-bit integers, with the lower 255 bits being the y-coordinate of the corresponding Ed25519 point and the most significant bit being the parity of the x-coordinate. Scalar multiplication is denoted by a space, e.g. K = k G.

3.3.3 Point conversion

We define a function ConvertPointE(K) that can transform an Ed25519 curve point into a Curve25519 point, preserving group structure. The conversion is done with the equivalence x = (v + 1) / (1 - v), where v is the Ed25519 y-coordinate and x is the Curve25519 x-coordinate. Notice that the x-coordinates of Ed25519 points and the y-coordinates of Curve25519 points are not considered. Since the y coordinate is ignored during serialization of Curve25519 points, the conversion should be unambiguous, with only one result.

3.3.4 Private keys

Private keys for both curves are elements of the field F_ℓ. These keys are not "clamped" [15] like they would be in the X25519 [16] protocol. Unfortunately, this somewhat slows down implementations of Curve25519 scalar-point multiplications, but it must be this way for backwards compatibility and on-chain indistinguishability. Private keys are derived using one of the two following functions:

ScalarDerive(x) = BytesToInt512(H₆₄(x)) mod ℓ
ScalarDeriveLegacy(x) = BytesToInt256(Keccak256(x)) mod ℓ

4. Rerandomizable RingCT abstraction

Here we formally define an abstraction of the FCMP++ consensus layer called Rerandomizable RingCT which lays out the requirements that Carrot needs. All elliptic curve arithmetic occurs on Ed25519. When we use the term "list" in this section, we refer to a sequence of elements where the order of elements is encoded and preserved. Thus, the list {A, B} is distinct from the list {B, A}.

4.1 Creating a transaction output

Transaction outputs are defined as the two points (K_o, C_a). To create a valid transaction output, the sender must know z, a such that C_a = z G + a H where 0 ≤ a < 2⁶⁴. Coinbase transactions have a plaintext integer amount a instead of the amount commitment C_a, which is implied to be C_a = G + a H.

4.2 Spending a transaction output

To spend this output, the recipient must know x, y, z, a such that K_o = x G + y T and C_a = z G + a H where 0 ≤ a < 2⁶⁴. Spending an output necessarily emits a key image (AKA "linking tag" or "nullifier") L = x H_p²(K_o). All key images must be in the prime order subgroup 𝔾_E.

4.3 Transaction model

Transactions contain a list of outputs, a list of key images, and additional unstructured data. All key images must be unique within a transaction. Similarly, all output pubkeys must be unique within a transaction.

4.4 Ledger model

The ledger can be modeled as an append-only list of transactions. Transactions can only contain key images of transaction outputs of "lower" positions within the ledger list. No two key images in the ledger may ever be equal to one another. In practice, the ledger will contain additional cryptographic proofs that verify the integrity of the data within each transaction, but those can largely be ignored for this addressing protocol.

5. Wallets

5.1 Legacy key hierarchy

The following figure shows the overall hierarchy used for legacy wallet keys. Note that the private spend key k_s doesn't exist for multi-signature wallets.

k_s (spend key)
 |
 |
 |
 +- k_v (view key)

Key	Name	Derivation	Used to
`k_s`	spend key	random element of F_ℓ	calculate key images, spend enotes
`k_v`	view key	`k_v = ScalarDeriveLegacy(k_s)`	find and decode received enotes, generate addresses

5.2 New key hierarchy

The following figure shows the overall hierarchy one should use for new wallet keys. Users do not have to switch their key hierarchy in order to participate in the address protocol, but this hierarchy gives the best features and usability. Note that the master secret s_m doesn't exist for multi-signature wallets.

s_m (master secret)
 |
 |
 |
 +- k_ps (prove-spend key)
 |
 |
 |
 +- s_vb (view-balance secret)
     |
     |
     |
     +- k_gi (generate-image key)
     |
     |
     |
     +- k_v (incoming view key)
     |
     |
     |
     +- s_ga (generate-address secret)

Key	Name	Derivation	Used to
`k_ps`	prove-spend key	`k_ps = ScalarDerive("Carrot prove-spend key" \|\| s_m)`	spend enotes
`s_vb`	view-balance secret	`s_vb = SecretDerive("Carrot view-balance secret" \|\| s_m)`	find and decode received and outgoing enotes
`k_gi`	generate-image key	`k_gi = ScalarDerive("Carrot generate-image key" \|\| s_vb)`	generate key images
`k_v`	incoming view key	`k_v = ScalarDerive("Carrot incoming view key" \|\| s_vb)`	find and decode received enotes
`s_ga`	generate-address secret	`s_ga = SecretDerive("Carrot generate-address secret" \|\| s_vb)`	generate addresses

5.3 New wallet public keys

There are two global wallet public keys for the new private key hierarchy.

Key	Name	Value
`K_s`	spend key	`K_s = k_gi G + k_ps T`
`K_v`	view key	`K_v = k_v K_s`

Note: for legacy key hierarchies, K_s = k_s G.

5.4 New wallet access tiers

The new private key hierarchy enables the following useful wallet tiers:

Tier	Secret	Off-chain capabilities	On-chain capabilities
Generate-Address	`s_ga`	generate public addresses	none
View-Received	`k_v`	all	view received
View-All	`s_vb`	all	view all
Master	`s_m`	all	all

5.4.1 Generate-Address

This wallet tier can generate public addresses for the wallet. It doesn't provide any blockchain access.

5.4.2 View-Received

This tier provides the wallet with the ability to see all external payments and external change, but cannot see any internal enotes, nor where any enotes are spent.

5.4.3 View-All

This is a full view-only wallet that can see all external and internal payment and change enotes, as well as where they are spent (and thus can calculate the correct wallet balance).

5.4.4 Master wallet (Master)

This tier has full control of the wallet.

6. Addresses

6.1 Address generation

There are two cryptographically distinct address types in Monero: Cryptonote and subaddress. Note that integrated addresses are derived exactly like a Cryptonote address, but they have an additional payment ID included. There can only be a maximum of one Cryptonote address per view key, referred to as the main address, but any number of subaddresses.

By convention, subaddresses are generated from a "subaddress index", which is a tuple of two 32-bit unsigned integers (j_major, j_minor), which allows for 2⁶⁴ addresses. The reason for the distinction between j_major and j_minor is simply for UX reasons. The "major" index is used to make separate "accounts" per wallet, which is used to compartmentalize input selection, change outputs, etc. The subaddress index (0, 0) is used to designate the main address, even though the key derivation is different. For brevity's sake, we use the label j as shorthand for (j_major, j_minor) and 0 as a shorthand for (0, 0).

Each Monero address derived from index j transmits information (is_main, K_s^j, K_v^j, pid), where is_main is a boolean flag which is true for Cryptonote addresses, and false for subaddresses.

6.1.1 Main address keys

The two public keys of the main address are constructed as:

K_s⁰ = K_s
K_v⁰ = k_v G

6.1.2 Subaddress keys (Legacy Hierarchy)

Under the legacy key hierarchy, the two public keys of the subaddress at index j are constructed as:

k_{sub_ext}^j = ScalarDeriveLegacy(IntToBytes64(8) || k_v || IntToBytes32(j_major) || IntToBytes32(j_minor))
K_s^j = K_s + k_{sub_ext}^j G
K_v^j = k_v K_s^j

Notice that generating new subaddresses this way requires knowledge of k_v which necessarily ties the ability to generate subaddresses to the ability to find owned enotes.

6.1.3 Subaddress keys (New Hierarchy)

Under the new key hierarchy, the two public keys of the subaddress at index j are constructed as:

s_gen^j = SecretDerive("Carrot address index generator" || s_ga || IntToBytes32(j_major) || IntToBytes32(j_minor))
k_{sub_scal}^j = ScalarDerive("Carrot subaddress scalar" || s_gen^j || K_s || K_v || IntToBytes32(j_major) || IntToBytes32(j_minor))
K_s^j = k_{sub_scal}^j K_s
K_v^j = k_{sub_scal}^j K_v

The address index generator s_gen^j can be used to prove that the address was constructed from the index j and the public keys K_s and K_v without revealing s_ga. Notice that, unlike the legacy derivation, the new subaddress derivation method does not require the private incoming view key k_v, only the generate-address secret s_ga, which allows for private deferred address generation.

7. Addressing protocol

7.1 Transaction global fields

7.1.1 Payment ID

A single 8-byte encrypted payment ID field is included in non-coinbase transactions for backwards compatibility with integrated addresses. Because only one encrypted payment ID pid_enc is included per transaction, senders can only send to one integrated addresses per transaction. When not sending to a legacy integrated address, pid is set to nullpid, the payment ID of all zero bytes.

The payment ID pid is encrypted by exclusive or (XOR) with an encryption mask m_pid. The encryption mask is derived from the shared secrets of the payment enote.

7.1.2 Ephemeral public keys

Every 2-output transaction has one ephemeral public key D_e. Transactions with N > 2 outputs have N ephemeral public keys (one for each output). Coinbase transactions always have one key per output.

7.2 Input Context

For each transaction, we assign a value input_context, whose purpose is to be unique for every single transaction within a valid ledger. We define this value as follows:

transaction type	`input_context`
coinbase	`"C" \|\| IntToBytes256(block height)`
non-coinbase	`"R" \|\| first spent key image`

This uniqueness is guaranteed by consensus rules: there is exactly one coinbase transaction per block height, and all key images are unique. Indirectly binding output pubkeys to this value helps to mitigate burning bugs.

7.3 Enote format

Each enote represents an amount a and payment ID pid sent to an address (is_main, K_s^j, K_v^j).

An enote contains the output public key K_o, the 3-byte view tag vt, the amount commitment C_a, encrypted Janus anchor anchor_enc, and encrypted amount a_enc. For coinbase transactions, the amount commitment C_a is omitted and the amount is not encrypted.

7.3.1 The output pubkey

The output pubkey, sometimes referred to as the "one-time address", is a part of the underlying Rerandomizable RingCT transaction output. Knowledge of the opening of this point allows for spending of the enote. Partial opening knowledge allows for calculating the key image of this enote, signalling in which location it was spent.

7.3.2 Amount commitment

The amount commitment is also part of the underlying Rerandomizable RingCT transaction output. This Pederson commitment should open up to the decrypted value in a_enc and the blinding factor derived from the shared secret. Coinbase transactions have this field omitted.

7.3.3 Amount

In non-coinbase transactions, the amount a is encrypted by exclusive or (XOR) with an encryption mask m_a. In coinbase transactions, a is included as part of the enote in plaintext.

7.3.4 View tags

The view tag vt is the first 3 bytes of a hash of the ECDH exchange with the view key. This view tag is used to fail quickly in the scan process for enotes not intended for the current wallet. The bit size of 24 was chosen as the fixed size because of Jamtis requirements.

7.3.5 Janus anchor

The Janus anchor anchor is a 16-byte encrypted array that provides protection against Janus attacks in Carrot. The anchor is encrypted by exclusive or (XOR) with an encryption mask m_anchor. In the case of normal transfers, anchor is uniformly random, and used to re-derive the enote ephemeral private key d_e and check the enote ephemeral pubkey D_e is constructed properly. In special enotes, anchor is set to an HMAC of D_e, authenticated by the private view key k_v. Both of these derivation-and-check paths should only pass if either A) the sender constructed the enotes in a way which does not allow for a Janus attack or B) the sender knows the private view key, in which case they can determine that addresses belong to the same wallet without performing a Janus attack.

7.4 Enote derivations

The enote components are derived from the shared secrets s_sr and s_sr^ctx. The definitions of these secrets are described in a later section.

7.4.1 Intermediate Values

Symbol	Name	Derivation
`k_a`	amount commitment blinding factor	`k_a = ScalarDerive("Carrot commitment mask" \|\| s_sr^ctx \|\| enote_type)`
`k_g^o`	output pubkey extension G	`k_g^o = ScalarDerive("Carrot key extension G" \|\| s_sr^ctx \|\| C_a)`
`k_t^o`	output pubkey extension T	`k_t^o = ScalarDerive("Carrot key extension T" \|\| s_sr^ctx \|\| C_a)`
`m_anchor`	encryption mask for `anchor`	`m_anchor = SecretDerive("Carrot encryption mask anchor" \|\| s_sr^ctx \|\| K_o)`
`m_a`	encryption mask for `a`	`m_a = SecretDerive("Carrot encryption mask a" \|\| s_sr^ctx \|\| K_o)`
`m_pid`	encryption mask for `pid`	`m_pid = SecretDerive("Carrot encryption mask pid" \|\| s_sr^ctx \|\| K_o)`
`anchor_norm`	janus anchor, normal	`anchor_norm = RandBytes(16)`
`anchor_sp`	janus anchor, special	`anchor_sp = SecretDerive("Carrot janus anchor special" \|\| D_e \|\| input_context \|\| K_o \|\| k_v \|\| K_s)`
`d_e`	ephemeral private key	`d_e = ScalarDerive("Carrot sending key normal" \|\| anchor_norm \|\| input_context \|\| K_s^j \|\| K_v^j \|\| pid)`

The variable enote_type is "payment" or "change" depending on the human-meaningful tag that a sender wants to express to the recipient. However, enote_type must be equal to "payment" for coinbase enotes.

7.4.2 Component Values

Symbol	Name	Derivation
`K_o`	output pubkey	`K_o = K_s^j + k_g^o G + k_t^o T`
`C_a`	amount commitment	`C_a = k_a G + a H`
`a_enc`	encrypted amount	`a_enc = a ⊕ m_a`
`vt`	view tag	`vt = SecretDerive("Carrot view tag" \|\| s_sr \|\| input_context \|\| K_o)`
`anchor_enc`	encrypted Janus anchor	`anchor_enc = (anchor_sp if special enote, else anchor_norm) ⊕ m_anchor`
`pid_enc`	encrypted payment ID	`pid_enc = pid ⊕ m_pid`

The view tag binds to input_context so that an external observer (i.e. someone without knowledge of s_sr) cannot simply copy D_e, K_o, and vt into a new transaction to force a view tag match. Binding to input_context causes the view tag of a copied enote to match with the same probability as any random, unrelated enote.

7.5 Ephemeral public key

The ephemeral pubkey D_e, a Curve25519 point, for a given enote is constructed differently based on what type of address one is sending to, how many outputs are in the transaction, and whether we are deriving on the internal or external path. Here "special" means an external self-send enote in a 2-out transaction. "Normal" refers to non-special, external enotes.

Transfer Type	`D_e` Derivation
Normal, to main address	`d_e B`
Normal, to subaddress	`d_e ConvertPointE(K_s^j)`
Internal	random element of 𝔾_M
Special	`D_e^other`

D_e^other refers to the ephemeral pubkey that would be derived on the other enote in a 2-out transaction. If both enotes in a 2-out transaction are "special", then no specific derivation of D_e is required, and D_e should be set to a random element of 𝔾_M.

7.6 Sender-receiver shared secrets

The shared secrets s_sr and s_sr^ctx are used to encrypt/extend all components of Carrot transactions. Most components (except the view tag for performance reasons) use s_sr^ctx to encrypt components.

s_sr is derived the following ways:

	Derivation
Sender, external	`8 d_e ConvertPointE(K_v^j`)
Recipient, external	`8 k_v D_e`
Internal	`s_vb`

Then, s_sr^ctx is derived as s_sr^ctx = SecretDerive("Carrot sender-receiver secret" || s_sr || D_e || input_context).

7.7 Janus outputs

In case of a Janus attack, the recipient will derive different values of the enote ephemeral pubkey D_e and Janus anchor, and thus will not recognize the output.

7.8 Self-send enotes

Self-send enotes are any enote created by the wallet that the enote is also destined to.

7.8.1 Internal enotes

Enotes which are destined for the sending wallet and use a symmetric secret instead of a ECDH exchange are called "internal enotes". The most common type are "change" enotes, but internal "payment" enotes are also possible. For typical 2-output transactions, an internal enote reuses the same value of D_e as the other enote.

As specified above, these enotes use s_vb as the value for s_sr. The existence of internal enotes means that we have to effectively perform two types of balance recovery scan processes, external s_sr and internal s_sr. Note, however, that this does not necessarily make balance recovery twice as slow since one scalar-point multiplication and multiplication by eight in Ed25519 is significantly (~100x) slower than Blake2b hashing, and we get to skip those operations for internal scanning.

7.8.2 Special enotes

Special enotes are external self-send enotes in a 2-out transaction. The sender employs different shared secret derivations and Janus anchor derivations than a regular external enote.

7.8.3 Mandatory self-send enote rule

Every transaction that spends funds from the wallet must produce at least one self-send (not necessarily internal) enote, typically a change enote. If there is no change left, an enote is added with a zero amount. This ensures that all transactions relevant to the wallet have at least one output. This allows for remote-assist "light weight" wallet servers to serve only the transactions relevant to the wallet, including any transaction that has spent key images. This rule also helps to optimize full wallet multi-threaded scanning by reducing state reuse.

7.8.4 One payment, one change rule

In a 2-out transaction with two internal or two special enotes, one enote's enote_type must be "payment", and the other "change".

In 2-out transactions, the ephemeral pubkey D_e is shared between enotes. input_context is also shared between the two enotes. Thus, if the two destination addresses share the same private view key k_v in a 2-out transaction, then s_sr^ctx will be the same and the derivation paths will lead both enotes to have the same output pubkey, which is A) not allowed, B) bad for privacy, and C) would burn funds if allowed. However, note that the output pubkey extensions k_g^o and k_t^o bind to the amount commitment C_a which in turn binds to enote_type. Thus, if we want our two enotes to have unique derivations, then the enote_type needs to be unique.

7.9 Coinbase transactions

Coinbase transactions are not considered to be internal.

Miners should continue the practice of only allowing main addresses for the destinations of coinbase transactions in Carrot. This is because, unlike normal enotes, coinbase enotes do not contain an amount commitment, and thus scanning a coinbase enote commitment has no "hard target". If subaddresses can be the destinations of coinbase transactions, then the scanner must have their subaddress table loaded and populated to correctly scan coinbase enotes. If only main addresses are allowed, then the scanner does not need the table and can instead simply check whether K_s⁰ ?= K_o - k_g^o G + k_t^o T.

8. Balance recovery

8.1 Enote Scan

If this enote scan returns successfully, we will be able to recover the address spend pubkey, amount, payment ID, and enote type. Additionally, a successful return guarantees that A) the enote is uniquely addressed to our account, B) Janus attacks are mitigated, and C) burning bug attacks due to duplicate output pubkeys are mitigated. Note, however, that a successful return does NOT guarantee that the enote is spendable (i.e. that the recipient will be able to recover x, y such that K_o = x G + y T).

We perform the scan process once with s_sr = 8 k_v D_e (external), and once with s_sr = s_vb (internal) if using the new key hierarchy.

If s_sr == 𝐼_M, then ABORT
Let vt' = SecretDerive("Carrot view tag" || s_sr || input_context || K_o)
If vt' ≠ vt, then ABORT
Let s_sr^ctx = SecretDerive("Carrot sender-receiver secret" || s_sr || D_e || input_context)
Set enote_type' = "payment"
If a coinbase enote, then let a' = a and jump to step 16
Let m_a = SecretDerive("Carrot encryption mask a" || s_sr^ctx || K_o)
Let a' = a_enc ⊕ m_a
Let k_a' = ScalarDerive("Carrot commitment mask" || s_sr^ctx || enote_type')
Let C_a' = k_a' G + a' H
If C_a' == C_a, then jump to step 16
Set enote_type' = "change"
Let k_a' = ScalarDerive("Carrot commitment mask" || s_sr^ctx || enote_type')
Let C_a' = k_a' G + a' H
If C_a' ≠ C_a, then ABORT
Let k_g^o' = ScalarDerive("Carrot key extension G" || s_sr^ctx || C_a)
Let k_t^o' = ScalarDerive("Carrot key extension T" || s_sr^ctx || C_a)
Let K_s^j' = K_o - k_g^o' G - k_t^o' T
If a coinbase enote and K_s^j' ≠ K_s, then ABORT
If s_sr == s_vb (i.e. performing an internal scan), then jump to step 36
Let m_pid = SecretDerive("Carrot encryption mask pid" || s_sr^ctx || K_o)
Set pid' = pid_enc ⊕ m_pid
Let m_anchor = SecretDerive("Carrot encryption mask anchor" || s_sr^ctx || K_o)
Let anchor' = anchor_enc ⊕ m_anchor
If K_s^j' == K_s, then let K_base = G, else let K_base = K_s^j'
Let K_v^j' = k_v K_base
Let d_e' = ScalarDerive("Carrot sending key normal" || anchor' || input_context || K_s^j' || K_v^j' || pid')
Let D_e' = d_e' ConvertPointE(K_base)
If D_e' == D_e, then jump to step 36
Set pid' = nullpid
Let d_e' = ScalarDerive("Carrot sending key normal" || anchor' || input_context || K_s^j' || K_v^j' || pid')
Let D_e' = d_e' ConvertPointE(K_base)
If D_e' == D_e, then jump to step 36
Let anchor_sp = SecretDerive("Carrot janus anchor special" || D_e || input_context || K_o || k_v || K_s)
If anchor' ≠ anchor_sp, then ABORT
Return successfully!

8.2 Determining spendability and computing key images

An enote is spendable if the computed nominal address spend pubkey K_s^j' from the enote scan process is one that the recipient knows how to derive. However, the enote scan process does not inform the sender how to derive the subaddress. One method of quickly checking whether a nominal address spend pubkey is derivable, and thus spendable, is a subaddress table. A subaddress table maps precomputed address spend pubkeys to their index j. Once the subaddress index for an enote is determined, we can begin computing the key image.

8.2.1 Legacy key hierarchy key images

If j ≠ 0, then let k_{sub_ext}^j = ScalarDeriveLegacy(IntToBytes64(8) || k_v || IntToBytes32(j_major) || IntToBytes32(j_minor)), otherwise let k_{sub_ext}^j = 0.

The key image is computed as: L = (k_s + k_{sub_ext}^j + k_g^o) H_p²(K_o).

8.2.2 New key hierarchy key images

If j ≠ 0, then let k_{sub_scal}^j = ScalarDerive("Carrot subaddress scalar" || s_gen^j || K_s || K_v || IntToBytes32(j_major) || IntToBytes32(j_minor)), otherwise let k_{sub_scal}^j = 1.

The key image is computed as: L = (k_gi * k_{sub_scal}^j + k_g^o) H_p²(K_o).

8.3 Handling key images and calculating balance

If a scanner successfully scans any enote within a transaction, they should save all those key images indefinitely as "potentially spent". The rest of the ledger's key images can be discarded. Then, the key images for each enote should be calculated. The "unspent" enotes are determined as those whose key images is not within the set of potentially spent key images. The sum total of the amounts of these enotes is the current balance of the wallet, and the unspent enotes can be used in future input proofs.

9. Security properties

Below are listed some security properties which are to hold for Carrot. Unless otherwise specified, it is assumed that no participant can efficiently solve the decisional Diffie-Hellman problem in Curve25519 and Ed25519 (i.e. the decisional Diffie-Hellman assumption [17] holds).

9.1 Balance recovery security

The term "honest receiver" below means an entity with certain private key material correctly executing the balance recovery instructions of the addressing protocol as described above. A receiver who correctly follows balance recovery instructions but lies to the sender whether they received funds is still considered "honest". Likewise, an "honest sender" is an entity who follows the sending instructions of the addressing protocol as described above.

9.1.1 Completeness

An honest sender who sends amount a and payment ID pid to address (is_main, K_s^j, K_v^j), internally or externally, can be guaranteed that the honest receiver who derived that address will:

Recover the same a, pid, K_s^j, K_v^j
Recover x, y, z such that C_a = z G + a H and K_o = x G + y T

This is to be achieved without any other interactivity.

9.1.2 Spend Binding

If an honest receiver recovers x and y for an enote such that K_o = x G + y T, then it is guaranteed within a security factor that no other entity without knowledge of k_ps (or k_s for legacy key hierarchies) will also be able to find x and y.

9.1.3 Enote Scan Binding

No two honest receivers using different values of k_v for external scans or s_vb for internal scans will both successfully return from the enote scan process given the same enote, even if that enote was constructed dishonestly.

9.1.4 Burning Bug Resistance

For any K_o, it is computationally intractable to find two unique values of input_context such that an honest receiver will determine both enotes to be spendable. Recall that spendability is determined as whether K_s^j' = K_o - k_g^o G - k_t^o T is an address spend pubkey that the recipient knows how to derive from their account secrets.

9.1.5 Janus Attack Resistance

There is no algorithm that, without knowledge of the recipient's private view key k_v, allows a sender to construct an enote using two or more honestly-derived non-integrated addresses which successfully passes the enote scan process when the two addresses where derived from the same account, but fails when the addresses are unrelated.

More concretely, it is computationally intractable, without knowledge of the recipient's private view key k_v, to construct an external enote which successfully passes the enote scan process such that the recipient's computed nominal address spend pubkey K_s^j' = K_o - k_g^o G - k_t^o T does not match the shared secret s_sr = 8 r ConvertPointE(K_v^j') for some sender-chosen r. This narrowed statement makes the informal assumption that using the address view spend pubkey for the Diffie-Hellman exchange and nominally recomputing its correct address spend pubkey leaves no room for a Janus attack.

9.2 Unlinkability

9.2.1 Computational Address-Address Unlinkability

A third party cannot determine if two non-integrated addresses share the same k_v with any better probability than random guessing.

9.2.2 Computational Address-Enote Unlinkability

A third party cannot determine if an address is the destination of an enote with any better probability than random guessing, even if they know the destination address.

9.2.3 Computational Enote-Enote Unlinkability

A third party cannot determine if two enotes have the same destination address with any better probability than random guessing, even if they know the destination address.

9.2.4 Computational Enote-Key Image Unlinkability

A third party cannot determine if any key image is the key image for any enote with any better probability than random guessing, even if they know the destination address.

9.3 Forward Secrecy

Forward secrecy refers to the preservation of privacy properties of past transactions against a future adversary capable of solving the elliptic curve discrete logarithm problem (ECDLP), for example a quantum computer. We refer to an entity with this capability as a SDLP (Solver of the Discrete Log Problem). We assume that the properties of secure hash functions still apply to SDLPs (i.e. collision-resistance, preimage-resistance, one-way).

9.3.1 Address-Conditional Forward Secrecy

A SDLP can learn no receiver or amount information about a transaction output, nor where it is spent, without knowing a receiver's public address.

9.3.2 Internal Forward Secrecy

Even with knowledge of s_ga, k_ps, k_gi, k_v, a SDLP without explicit knowledge of s_vb will not be able to discern where internal enotes are received, where/if they are spent, nor the amounts with any better probability than random guessing.

9.4 Indistinguishability

We define multiple processes by which public value representations are created as "indistinguishable" if a SDLP, without knowledge of public addresses or private account keys, cannot determine by which process the public values were created with any better probability than random guessing. The processes in question are described below.

9.4.1 Transaction output random indistinguishability

Carrot transaction outputs are indistinguishable from random transaction outputs. The Carrot transaction output process is described earlier in this document. The random transaction output process is modeled as follows:

Sample r₁ and r₂ independently from uniform integer distribution [0, ℓ).
Set K_o = r₁ G
Set C_a = r₂ G

9.4.2 Ephemeral pubkey random indistinguishability

Carrot ephemeral pubkeys are indistinguishable from random Curve25519 pubkeys. The Carrot ephemeral pubkey process is described earlier in this document. The random ephemeral pubkey process is modeled as follows:

Sample r from uniform integer distribution [0, ℓ).
Set D_e = r B

Note that in Carrot ephemeral pubkey construction, the ephemeral private key d_e, unlike most X25519 private keys, is derived without key clamping. Multiplying by this unclamped key makes it so the resultant pubkey is indistinguishable from a random pubkey (needs better formalizing).

9.4.3 Other enote component random indistinguishability

The remaining Carrot enote components are indistinguishable from random byte strings. The Carrot enote process is described earlier in this document. The random enote byte string process is modeled as follows:

Sample a_enc = RandBytes(8)
Sample anchor_enc = RandBytes(16)
Sample vt = RandBytes(3)
Sample pid_enc = RandBytes(8)

10. Credits

Special thanks to everyone who commented and provided feedback on the original Jamtis gist. Many of the ideas were incorporated in this document.

A very special thanks to @tevador, who wrote up the Jamtis and Jamtis-RCT specifications, which were the foundation of this document, containing most of the transaction protocol math.

11. Glossary

Amount Commitment - An elliptic curve point, in the form of a Pederson Commitment [18], which is used to represent hidden amounts in transaction outputs in RingCT and FCMP++
Burning Bug Attack - An attack where an exploiter duplicates an output pubkey and tricks the recipient into accepting both, even though only one can be spent
Coinbase Transaction - A transaction which has no key images, and plaintext integer amounts instead of amount commitments in its outputs
Cryptonote - A cryptocurrency consensus protocol and addressing scheme which was the foundation for Monero's ledger interactions initially
Cryptonote Address - An address in the form described in the Cryptonote v2 whitepaper
Enote - A transaction output and its associated data unique to that transaction output
Ephemeral Public Key - An elliptic curve point associated to transaction outputs in order to hide enote details through a Diffie-Hellman key exchange
External Enote - An enote which was constructed by performing an asymmetric Elliptic Curve Diffie-Hellman key exchange against an address, main or subaddress
FCMP++ - A proposed cryptocurrency consensus protocol to upgrade Monero's RingCT consensus protocol
Forward Secrecy - The property of a cryptographic construction that information is hidden from an observer that can efficiently solve the Discrete Logarithm Problem
Indistinguishability - The property of multiple cryptographic constructions that the public values posted cannot be determined to the result of any single construction
Input Content - A unique value associated to each transaction used in the Carrot address protocol derivations to mitigate burning bug attacks
Integrated Address - A main address which additionally contains a payment ID
Internal Enote - An enote which was constructed using a symmetric shared secret, typically the view-balance secret
Janus Anchor - An enote component whose purpose is two fold in mitigating Janus attacks: act as an entropy source for deriving the ephemeral private key or act as an HMAC validating the ephemeral pubkey
Janus Attack - An attack where an exploiter constructs an enote partially using two different addresses they suspect to belong to the same user such that the confirmation of that payment confirms the addresses are actually related
Key Image - An elliptic curve point emitted during a Rerandomizable RingCT spend proof, used during balance recovery to determine whether an enote has been spent yet
Ledger - An immutable, append-only list of transactions which is the shared medium of data exchange for different participants of the network
Main Address - same as Cryptonote Address
Monero - A payment network, along with a cryptocurrency XMR, that historically utilizes a collection of consensus protocols on its ledger, namely: Cryptonote, RingCT, and FCMP++
Payment ID - An 8 byte array included with transaction data used to differentiate senders
Rerandomizable RingCT - An abstraction of FCMP++ defined in this document that allows the formalization of different security properties without knowledge of the underlying proving system
RingCT - A cryptocurrency consensus protocol that iterated on Cryptonote by introducing hidden amounts by way of amount commitments
Self-send Enote - An enote constructed by wallet intended to be received by the same wallet, either internal or external
Special Enote - An external self-send enote within a 2-output transaction
Subaddress - An address form introduced by Monero contributors which allows for a single wallet to generate an arbitrary number of unlinkable addresses without affecting scanning speed
Transaction - An atomic modification to the ledger containing key images, transaction outputs, and other unstructured data
Transaction Output - A distinct tuple of an elliptic curve point and amount commitment or plaintext amount which is contained in a list in a transaction
View Tag - A small enote component, calculated as a partial hash of the sender-receiver shared key, which is checked early in the balance recovery process to optimize scanning performance
Wallet - A collection of private key data, cached ledger state, and other information which is used to interact with the shared ledger

12. References

https://github.com/monero-project/research-lab/blob/master/whitepaper/whitepaper.pdf
https://www.getmonero.org/resources/moneropedia/paymentid.html
monero-project/research-lab#7
https://gist.github.com/kayabaNerve/0e1f7719e5797c826b87249f21ab6f86
https://www.getmonero.org/resources/moneropedia/ringCT.html
https://web.getmonero.org/2019/10/18/subaddress-janus.html
https://www.getmonero.org/2018/09/25/a-post-mortum-of-the-burning-bug.html
https://github.com/monero-project/monero/pull/4438/files#diff-04cf14f64d2023c7f9cd7bd8e51dcb32ed400443c6a67535cb0105cfa2b62c3c
https://gist.github.com/tevador/50160d160d24cfc6c52ae02eb3d17024
https://gist.github.com/kayabaNerve/8066c13f1fe1573286ba7a2fd79f6100
https://eprint.iacr.org/2013/322.pdf
https://keccak.team/keccak.html
https://cr.yp.to/ecdh/curve25519-20060209.pdf
https://ed25519.cr.yp.to/ed25519-20110926.pdf
https://neilmadden.blog/2020/05/28/whats-the-curve25519-clamping-all-about/
https://cr.yp.to/ecdh.html
https://crypto.stanford.edu/~dabo/pubs/papers/DDH.pdf
https://www.getmonero.org/resources/moneropedia/pedersen-commitment.html

Files

carrot.md

Latest commit

History