Skip to content

Instantly share code, notes, and snippets.

@tevador

tevador/jamtis-rct.md

Last active August 6, 2024 07:27
Show Gist options
  • Save tevador/d3656a217c0177c160b9b6219d9ebb96 to your computer and use it in GitHub Desktop.
Save tevador/d3656a217c0177c160b9b6219d9ebb96 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
jamtis-rct.md

JAMTIS-RCT

This document introduces a new addressing scheme for Monero called Jamtis. The new addresses are 244 characters long and come with several new features. The new scheme allows users to delegate blockchain scanning to a 3rd party service without revealing which specific outputs belong to the wallet or the amounts that were received. New wallet tiers are introduced for merchants that only have capabilities for generating addresses or processing incoming payments. New addresses can be created statelessly (without the need to keep track of how many addresses have been generated). View-only wallets can display the correct balance.

The transaction protocol that comes with Jamtis is backwards compatible with existing CryptoNote addresses. That means wallets can send payments to both new and old addresses and the resulting transactions will be indistinguishable in the blockchain. Additionally, the protocol provides Janus attack mitigations for both new and old addresses.

Table of Contents

1. Introduction

1.1 Why a new address format?

When Monero was created in 2014, it inherited the the CryptoNote addressing scheme [1]. Originally, each wallet only had a single public address and payments were disambiguated with payment IDs. In 2017, subaddresses were introduced, which allowed each wallet to generate a virtually unlimited number of seemingly unlinkable addresses. However, several issues with the legacy addressing scheme have been identified:

  1. Addresses are not suitable as human-readable identifiers because they are long and case-sensitive.
  2. Too much information about the wallet is leaked when scanning is delegated to a third party.
  3. Generating subaddresses requires view access to the wallet. This is why many merchants prefer integrated addresses [2].
  4. View-only wallets need key images to be imported to detect spent outputs [3].
  5. Subaddresses that belong to the same wallet can be linked via the Janus attack [4].
  6. The detection of outputs received to subaddresses is based on a lookup table, which can sometimes cause the wallet to miss outputs [5].

1.2 Jamtis

Jamtis is a next-generation addressing scheme that was developed specifically to tackle all of the shortcomings of CryptoNote addresses that were mentioned above. Jamtis comes with a new transaction protocol that is backwards compatible with existing CryptoNote addresses. That means wallets will be able to send to both new and old addresses and the resulting transactions will be indistinguishable in the blockchain.

Additionally, Jamtis comes with a new 16-word mnemonic scheme called Polyseed [6] that will replace the legacy 25-word seed for new wallets.

2. Features

2.1 Address format

Jamtis addresses, when encoded as a string, start with the prefix xmra and consist of 244 characters. Example of an address: xmra1mm95tp74ihjcu244xt4hpw1smcg5cdhdubfbmk3iyyw16ned1tu70hys0r3784af7r8515f2p9xtrx58akjtwb0cft00ari8jecrighji8aqaexwsh2475q3e1bay734kuhicey8bck5wwfbbp2yi4e4qn9h8dst5aaq8qnbyj0xrweamt1jwq5m0j1anh5srpm6fkhm6s76s3udi6xi0rm0jwf884j2exgg3t0ebxdcc3k

2.1.1 Recipient IDs

Jamtis introduces a short recipient identifier (RID) that can be calculated for every address. RID consists of 25 alphanumeric characters that are separated by underscores for better readability. The RID for the above address is regne_hwbna_u21gh_b54n0_8x36q. Instead of comparing long addresses, users can compare the much shorter RID. RIDs are also suitable to be communicated via phone calls, text messages or handwriting to confirm a recipient's address. This allows the address itself to be transferred via an insecure channel.

2.2 Light wallet scanning

Jamtis introduces new wallet tiers below view-only wallet. One of the new wallet tiers called "FilterAssist" is intended for wallet-scanning and only has the ability to calculate view tags [7].

View tags can be used to eliminate 99.6% of outputs that don't belong to the wallet. Possible use cases are:

2.2.1 Wallet component

A wallet can have a "FilterAssist" component that stays connected to the network at all times and filters out outputs in the blockchain. The full wallet can thus be synchronized at least 256x faster when it comes online (it only needs to check outputs with a matching view tag).

2.2.2 Third party services

If the "FilterAssist" private key is provided to a 3rd party, it can preprocess the blockchain and provide a list of potential outputs. This reduces the amount of data that a light wallet has to download by a factor of about 100. The third party will not learn which outputs actually belong to the wallet and will not see output amounts.

2.3 Wallet tiers for merchants

Jamtis introduces new wallet tiers that are useful for merchants.

2.3.1 Address generator

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.3.2 Payment validator

This wallet tier combines the Address generator tier with the ability to also view received payments (including amounts). It is intended for validating paid orders. It cannot see outgoing payments and received change.

2.4 Full view-only wallets

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

2.5 Janus attack mitigation

Janus attack 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.

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

2.6 Robust output detection

Jamtis addresses and outputs contain an encrypted address tag which enables a more robust output detection mechanism that does not need a lookup table and can reliably detect outputs sent to arbitrary wallet addresses.

3. Notation

3.1 Miscellaneous definitions

  1. The function BytesToInt256(x) deserializes a 256-bit little-endian integer from a 32-byte input.
  2. The function BytesToInt512(x) deserializes a 512-bit little-endian integer from a 64-byte input.
  3. The function RandBytes(x) generates a random x-byte string.
  4. Concatenation is denoted by ||.

3.2 Hash function

The function Hb(x) with parameters b, x, refers to the Blake2b hash function [8] 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) = H32(x)

3.3 Elliptic curves

Two elliptic curves are used in this specification:

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

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

3.3.1 Curve25519

Curve25519 is used exclusively for the Diffie-Hellman key exchange [9].

Only a single generator point B is used:

Point Derivation Serialized (hex)
B generator of 𝔾1 0900000000000000000000000000000000000000000000000000000000000000

Private keys for Curve25519 are 32-byte integers denoted by a lowercase letter d. They are constructed using the following KeyClamp1(i) function from a uniformly distributed 32-byte integer i:

  1. i[31] &= 0x7f (clear the most significant bit)
  2. i[0] &= 0xf8 (clear the least significant 3 bits)
  3. return i

Non-deterministic keys can be generated using the KeyGen1() function:

  1. i = BytesToInt256(RandBytes(32))
  2. return KeyClamp1(i)

Deterministic keys are derived using the following KeyDerive1(x) function:

  1. i = BytesToInt256(H32(x))
  2. return KeyClamp1(i)

The KeyClamp1 function causes all Curve25519 private keys to be multiples of the cofactor 8, which ensures that all public keys are in the prime-order subgroup. The multiplicative inverse modulo ℓ is calculated as 1/d = 8*(8*d)-1 to preserve the aforementioned property.

Public keys (elements of 𝔾1) are denoted by the capital letter D and are serialized as the x-coordinate of the corresponding Curve25519 point. Scalar multiplication is denoted by a space, e.g. D = d B.

3.3.2 Ed25519

The Edwards curve is used for signatures and more complex cryptographic protocols [10]. The following generators are used:

Point Derivation Serialized (hex)
G generator of 𝔾2 5866666666666666666666666666666666666666666666666666666666666666
H Hp1(G) 8b655970153799af2aeadc9ff1add0ea6c7251d54154cfa92c173a0dd39c1f94
T Hp2("Monero generator T") d1e6c1e625757d40bee4eed4fa6ad6447c426693f29dfb1c2fbb4c41e1f6bfd3

Here Hp1 and Hp2 refer to two hash-to-point functions.

Private keys for Ed25519 are 32-byte integers denoted by a lowercase letter k. They are generated using the following function:

KeyDerive2(x) = BytesToInt512(H64(x)) mod ℓ

Public keys (elements of 𝔾2) are denoted by the capital letter K 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 Public key conversion

We define two functions that can transform public keys between the two curves:

  1. ConvertPubkey1(D) takes a Curve25519 public key D and outputs the corresponding Ed25519 public key K with an even-valued x coordinate.
  2. ConvertPubkey2(K) takes an Ed25519 public key K and outputs the corresponding Curve25519 public key D.

Additionally, we define the function NormalizeX(K) that takes an Ed25519 point K and returns K if its x corrdinate is even or -K if its x coordinate is odd.

3.4 Block cipher

The function BlockEnc(s, x) refers to the application of the Twofish [11] permutation using the secret key s on the 16-byte input x. The function BlockDec(s, x) refers to the application of the inverse permutation using the key s.

3.5 Base32 encoding

"Base32" in this specification referes to a binary-to-text encoding using the alphabet xmrbase32cdfghijknpqtuwy01456789. This alphabet was selected for the following reasons:

  1. The order of the characters has a unique prefix that distinguishes the encoding from other variants of "base32".
  2. The alphabet contains all digits 0-9, which allows numeric values to be encoded in a human readable form.
  3. Excludes the letters o, l, v and z for the same reasons as the z-base-32 encoding [12].

4. Wallets

4.1 Wallet parameters

Each Jamtis wallet consists of two main keys, a timestamp and a bit flag:

Field Type Description
kps private key prove-spend key
svb secret key view-balance secret
birthday timestamp date when the wallet was created
jamtis bit always set to 1

The prove-spend key kps is required to spend money in the wallet and the view-balance secret svb provides full view-only access.

The birthday timestamp is important when restoring a wallet and determines the blockchain height where scanning for owned outputs should begin.

Wallets with the jamtis bit set to 0 are legacy wallets using the CryptoNote address format and the legacy keys. Jamtis wallets always set the jamtis bit-flag to 1 and use the new address format.

4.2 Wallet creation

4.2.1 Standard wallets

Standard Jamtis wallets are generated as a 16-word Polyseed mnemonic [6], which provides the wallet master secret sm and also encodes the date when the wallet was created and the jamtis bit-flag. The keys kps and svb are derived from the master secret.

Field Derivation
sm from Polyseed
kps kps = KeyDerive2("jamtis_prove_spend_key" || sm)
svb svb = SecretDerive("jamtis_view_balance_secret" || sm)
birthday from Polyseed
jamtis from Polyseed

4.2.2 Multisignature wallets

Multisignature wallets are generated in a setup ceremony, where all the signers collectively generate the prove-spend key kps and the view-balance secret svb.

Field Derivation
kps setup ceremony
svb setup ceremony
birthday setup ceremony
jamtis setup ceremony

4.3 Additional keys

There are additional keys derived from svb:

Key Name Derivation Used to
kgi generate-image key kgi = KeyDerive2("jamtis_generate_image_key" || svb) generate key images
svr view-received secret svr = SecretDerive("jamtis_view_received_secret" || svb) find and decode received e-notes
dur unlock-received key dur = KeyDerive1("jamtis_unlock_received_key" || svr) derive e-note shared secrets
dir identify-received key dir = KeyDerive1("jamtis_identify_received_key" || svr) derive e-note shared secrets
dfa filter-assist key dfa = KeyDerive1("jamtis_filter_assist_key" || svr) calculate primary view tags
sga generate-address secret sga = SecretDerive("jamtis_generate_address_secret" || svr) generate addresses
sct cipher-tag secret sct = SecretDerive("jamtis_cipher_tag_secret" || sga) encrypt/decrypt address tags

The key kgi is required to generate key images.

The secret svr (and its child keys) provides the ability to calculate the sender-receiver shared secrets when scanning for received payments. The key dfa can recognize candidates for owned e-notes by matching the primary view tag.

The secret sga (and its child secret sct) is used to generate public addresses.

4.4 Key hierarchy

The following figure shows the overall hierarchy of wallet keys. Note that the master secret sm doesn't exist for multisignature wallets.

s_m (master secret)
 |
 |
 |
 +- k_ps (prove-spend key)
 |
 |
 |
 +- s_vb (view-balance secret)
     |
     |
     |
     +- k_gi (generate-image key)
     |
     |
     |
     +- s_vr (view-received secret)
         |
         |
         |
         +- d_ur (unlock-received key)
         |
         |
         |
         +- d_ir (identify-received key)
         |
         |
         |
         +- d_fa (filter-assist key)
         |
         |
         |
         +- s_ga (generate-address secret)
             |
             |
             |
             +- s_ct (cipher-tag secret)

4.5 Wallet public keys

There are 4 global wallet public keys. These keys are not usually published, but are needed by lower wallet tiers.

Key Name Value
Ks spend key Ks = kgi G + kps T
Dur unlock-received key Dur = dur B
Dfa filter-assist key Dfa = dfa Dur
Dir identify-received key Dir = dir Dur

4.6 Wallet access tiers

The private key hierarchy enables the following useful wallet tiers:

Tier Secret Public keys Off-chain capabilities On-chain capabilities
AddrGen sga Ks, Dur, Dir, Dfa generate public addresses none
FilterAssist dfa - recognize all public wallet addresses eliminate the majority of non-owned outputs
ViewReceived svr Ks all view received (except of internal e-notes)
ViewAll svb Ks all view all
Master sm - all all

4.6.1 Address generator (AddrGen)

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

4.6.2 Output scanning wallet (FilterAssist)

Thanks to view tags, this tier can eliminate 99.6% of outputs that don't belong to the wallet. If provided with a list of wallet addresses, it can also link outputs to those addresses (but it cannot generate addresses on its own). This tier should provide a noticeable UX improvement with a limited impact on privacy. Possible use cases are:

  1. An always-online wallet component that filters out outputs in the blockchain. A higher-tier wallet can thus be synchronized 256x faster when it comes online.
  2. Third party scanning services. The service can preprocess the blockchain and provide a list of potential outputs. This reduces the amount of data that a light wallet has to download by a factor of about 100.

4.6.3 Payment validator (ViewReceived)

This level provides the wallet with the ability to see all incoming payments, but cannot see any outgoing payments and change outputs. It can be used for payment processing or auditing purposes.

4.6.4 View-only wallet (ViewAll)

This is a full view-only wallet than can see all incoming and outgoing payments (and thus can calculate the correct wallet balance).

4.6.5 Master wallet (Master)

This tier has full control of the wallet.

5. Addresses

5.1 Address generation

Jamtis wallets can generate up to 2128 different addresses. Each address is constructed from a 128-bit index j. The size of the index space allows stateless generation of new addresses without collisions, for example by constructing j as a UUID [13].

Each Jamtis address encodes the tuple (j', K1j, D2j, D3j, D4j), where j' is the encrypted value of j and the other four values are public keys.

5.1.1 Address keys

The four public keys are constructed as:

  • K1j = Ks + kgj G + ktj T
  • D2j = (1 / daj) Dur
  • D3j = (1 / daj) Dfa
  • D4j = (1 / daj) Dir

The private keys kgj, ktj and daj are derived as follows:

Keys Name Derivation
sgenj address index generators sgenj = SecretDerive("jamtis_address_index_generator" || sga || j)
kgj spend key extensions kgj = KeyDerive2("jamtis_spendkey_extension_g" || sgenj || Ks || j)
ktj spend key extensions ktj = KeyDerive2("jamtis_spendkey_extension_t" || sgenj || Ks || j)
daj address keys daj = KeyDerive1("jamtis_address_privkey" || sgenj || Dur || Dfa || Dir || j)

The address index generator sgenj can be used to prove that the address was constructed from the index j and the public keys Ks, Dur, Dfa, Dir.

5.1.2 Address tag

Each address additionally includes a 16-byte tag j' = BlockEnc(sct, j).

5.2 Address encoding

5.2.1 Address structure

An address has the following overall structure:

Field Size (bits) Description
Header 30* human-readable address header (§ 5.2.2)
K1 256 address key 1
j' 128 address tag
padding 1 a zero bit
D2 255 address key 2
D3 255 address key 3
D4 255 address key 4
Checksum 40* (§ 5.2.3)

* The header and the checksum are already in base32 format

5.2.2 Address header

The address starts with a human-readable header, which has the following format consisting of 6 alphanumeric characters:

"xmra" <version char> <network type char>

Unlike the rest of the address, the header is never encoded and is the same for both the binary and textual representations. The string is not null terminated.

The software decoding an address shall abort if the first 4 bytes are not 0x78 0x6d 0x72 0x61 ("xmra").

The "xmra" prefix serves as a disambiguation from legacy addresses that start with "4" or "8". Additionally, base58 strings that start with the character x are invalid due to overflow [14], so legacy Monero software can never accidentally decode a Jamtis address.

The version character is "1". The software decoding an address shall abort if a different character is encountered.

The following 3 network types are defined:

network char network type
"t" testnet
"s" stagenet
"m" mainnet

The software decoding an address shall abort if an invalid network character is encountered.

5.2.3 Checksum

The purpose of the checksum is to detect accidental corruption of the address. The checksum consists of 8 characters and is calculated with a cyclic code over GF(32) using the polynomial:

x8 + 3x7 + 11x6 + 18x5 + 5x4 + 25x3 + 21x2 + 12x + 1

The checksum can detect all errors affecting 5 or fewer characters. Arbitrary corruption of the address has a chance of less than 1 in 1012 of not being detected. The reference code how to calculate the checksum is in Appendix A.

5.2.4 Binary-to-text encoding

An address can be encoded into a string as follows:

address_string = header + base32(data) + checksum

where header is the 6-character human-readable header string (already in base32), data is the binary payload and the checksum is the 8-character checksum (already in base32).

The binary payload encodes the address tuple (K1, j', D2, D3, D4), with a single padding bit inserted between j' and D2 to align all public keys to a character boundary. The total size of data is 1150 bits.

The total length of the encoded address is 244 characters (=6+230+8).

5.2.5 QR Codes

While the canonical form of an address is lower case, when encoding an address into a QR code, the address should be converted to upper case to take advantage of the more efficient alphanumeric encoding mode.

5.2.6 Recipient authentication

TODO

6. Transaction protocol

6.1 Transaction global fields

6.1.1 Unlock time

The unlock_time field is removed [15].

6.1.2 Payment ID

A single 8-byte encrypted payment ID field is retained for 2-output non-coinbase transactions for backwards compability with legacy integrated addresses. When not sending to a legacy integrated address, pid is set to zero.

The payment ID pid is encrypted by exclusive or (XOR) with an encryption mask mpid. The encryption mask is derived from the shared secrets of the payment e-note.

6.1.3 View tag size specifier

A new 1-byte field tag_size is added to specify the primary view tag size in bits. The permitted range of values is 1-16 (validated by a consensus rule), but a value of 8 is enforced by a relay rule.

6.1.4 Ephemeral public keys

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

6.2 E-note format

Each e-note represents an amount a sent to a Jamtis address (j', K1, D2, D3, D4) or a legacy address (K1, K2).

An e-note contains the output public key Ko, the 2-byte combined view tag vt, the amount commitment Ca and the encrypted values of j' and a. For coinbase transactions, the amount commitment Ca is omitted and the amount is not encrypted.

6.2.1 The output key

The output key is constructed as Ko = K1 + kgo G + kto T, where kgo and kto are key extensions of the address spend key K1.

6.2.2 View tags

The 16-bit combined view tag consists of the primary view tag vt1 and the secondary view tag vt2. The primary view tag size can be in the range of 1-16 bits and is equal to the value of the transaction field tag_size. The remaining 16-tag_size bits form the secondary view tag. Each view tag is derived from a different shared secret.

In the case of hidden e-notes (§ 6.6.2), all 16 bits are used for vt2. The same applies to e-notes sent to legacy (CryptoNote) addresses.

6.2.3 Amount commitment

The amount commitment is constructed as Ca = ka G + a H, where ka is the commitment mask and a is the amount. Coinbase transactions have implicitly Ca = a H.

6.2.4 Address tag

The address tag j' is encrypted by exclusive or (XOR) with an encryption mask mj'.

6.2.5 Amount

The amount a is encrypted by exclusive or (XOR) with an encryption mask ma.

6.3 E-note types

There are 2 e-notes types: payment and change.

6.3.1 Payment e-notes

These e-notes represent a received payment and show up in the wallet transaction history as a positive amount. These e-notes can be received both from the outside or from the wallet itself (internal payments).

6.3.2 Change e-notes

These e-notes represent change returned back to the wallet after a payment is made. The UX difference is that the wallet will not display change e-notes in the transaction history as a positive amount, but rather will use the change to reduce the amount that was spent. Change e-notes always come from the wallet itself. If a change e-note has a zero amount, it's called a dummy e-note.

6.4 E-note derivations

The e-note components are derived from 3 shared secret keys X1, X2 and X4. The definitions of these keys are described below.

Component Name Derivation
vt1 primary view tag vt1 = SecretDerive("jamtis_primary_view_tag" || X1 || Ko)
vt2 secondary view tag vt2 = SecretDerive("jamtis_secondary_view_tag" || X2 || Ko)
mj' encryption mask for j' mj' = SecretDerive("jamtis_encryption_mask_j'" || X1 || X2 || Ko)
ma encryption mask for a ma = SecretDerive("jamtis_encryption_mask_a" || X4 || Ko)
mpid encryption mask for pid mpid = SecretDerive("jamtis_encryption_mask_pid" || X4 || Ko)
ka amount commitment mask ka = KeyDerive1("jamtis_commitment_mask" || X4 || enote_type)
kgo output key extension G kgo = KeyDerive1("jamtis_key_extension_g" || X4 || Ca)
kto output key extension T kto = KeyDerive1("jamtis_key_extension_t" || X4 || Ca)

The variable enote_type is "payment" or "change" depending on the e-note type.

6.5 Sender-receiver shared secrets

When sending to a Jamtis address (j', K1, D2, D3, D4), the sender first generates the sending private key de = KeyGen1() and includes De = de D2 in the transaction data.

The sender and the recipient can then both derive the following three shared keys:

Shared key Sender Recipient
X1 de D3 dfa De
X2 de D4 dir De
X3 de B (daj / dur) De

The fourth shared key is derived as follows:

Shared key Derivation
X4 X4 = SecretDerive("jamtis_shared_key" || X1 || X2 || X3 || De || input_context)

Here input_context is defined as:

transaction type input_context
coinbase block height
non-coinbase sorted list of spent key images

The purpose of input_context is to make X4 unique for every transaction.

6.5.1 Janus outputs

In case of a Janus attack, the recipient will derive different values of the shared keys X3 and X4 and will not recognize the output. The attacker will not be able to derive the recipient's value of X3 even if they know the value of daj for one of the involved addresses.

6.6 Internal e-notes

E-notes which go to an address that belongs to the sending wallet are called "internal e-notes". The most common type are change e-notes, but internal payments are also possible.

For internal e-notes, a different construction of the first three shared keys is used:

Shared key Value
X1 dfa De
X2 svb
X3 svb

This ensures that:

  1. Wallet tiers below ViewAll cannot recognize internal e-notes.
  2. For typical 2-output transactions, the change e-note can reuse the same value of De as the payment e-note.

Coinbase transactions are not considered to be internal.

6.6.1 Mandatory change

Every transaction that spends funds from the wallet must produce at least one internal e-note, typically a change e-note. If there is no change left, a dummy e-note is added (change with a zero amount). This ensures that all transactions relevant to the wallet have a matching primary view tag on at least one output.

6.6.2 Hidden e-notes

If a transaction produces more than one internal e-note (e.g. a payment e-note and a change e-note or two change e-notes), only one of them gets a primary view tag. For the remaining internal e-notes, all 16 bits are filled with the secondary view tag. This prevents the FilterAssist wallet tier from linking transactions to the wallet based on the number of primary view tag matches within a transaction.

The consequence of this rule is that a wallet scanning for incoming transactions has to scan all e-notes of transactions with at least one matching primary view tag. However, most of them will only have to be tested for a secondary view tag match (false positive rate of 1/65536).

6.7 Legacy addresses

When sending the amount a to a legacy address (K1, K2, pid), the sender will first generate a sending secret n = RandBytes(16) and derive de = KeyDerive1("jamtis_legacy_sending_key" || n || a || K1 || K2 || pid). The payment ID pid is considered to be zero for main addresses and subaddresses.

The e-note public key is defined as De = de ConvertPubKey2(K1) when sending to a subaddress and De = de B when sending to a main address or an integrated address.

The three shared keys X1, X2 and X3 are all equal and calculated as follows:

Shared key Sender Recipient
X1,2,3 ConvertPubKey1(de ConvertPubKey2(8 K2)) NormalizeX(8 kv ConvertPubKey1(De))

The e-note will only include the secondary view tag vt2 with a size of 16 bits. The value of j' to encrypt is set to the sending secret n.

6.7.1 Janus outputs

The protocol provides Janus mitigation for all legacy addresses. When receiving a payment, the recipient can decrypt n, rederive de and check if the e-note public key De was constructed correctly.

6.7.2 Scanning performance

When scanning for received e-notes, legacy wallets need to calculate NormalizeX(8 kv ConvertPubKey1(De)). The operation ConvertPubKey1(De) can be done during point decompression for free. The NormalizeX() function simply drops the x coordinate. The scanning performance for legacy wallets is therefore the same as in the old protocol.

Note: Legacy wallets use scalar multiplication in 𝔾2 because the legacy view key kv might be larger than 2252, which is not supported in the Montgomery ladder.

7. Test vectors

TODO

Credits

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

References

  1. https://github.com/monero-project/research-lab/blob/master/whitepaper/whitepaper.pdf
  2. monero-project/meta#299 (comment)
  3. https://www.getmonero.org/resources/user-guides/view_only.html
  4. https://web.getmonero.org/2019/10/18/subaddress-janus.html
  5. monero-project/monero#8138
  6. https://github.com/tevador/polyseed
  7. monero-project/research-lab#73
  8. https://eprint.iacr.org/2013/322.pdf
  9. https://cr.yp.to/ecdh/curve25519-20060209.pdf
  10. https://ed25519.cr.yp.to/ed25519-20110926.pdf
  11. https://www.schneier.com/wp-content/uploads/2016/02/paper-twofish-paper.pdf
  12. http://philzimmermann.com/docs/human-oriented-base-32-encoding.txt
  13. https://en.wikipedia.org/wiki/Universally_unique_identifier
  14. https://github.com/monero-project/monero/blob/319b831e65437f1c8e5ff4b4cb9be03f091f6fc6/src/common/base58.cpp#L157
  15. monero-project/research-lab#78

Appendix A: Checksum

# Jamtis address checksum algorithm

# cyclic code based on the generator 3BI5PLC1
# can detect 5 errors up to the length of 994 characters
GEN=[0x1ae45cd581, 0x359aad8f02, 0x61754f9b24, 0xc2ba1bb368, 0xcd2623e3f0]

M = 0xffffffffff

def jamtis_polymod(data):
    c = 1
    for v in data:
        b = (c >> 35)
        c = ((c & 0x07ffffffff) << 5) ^ v
        for i in range(5):
            c ^= GEN[i] if ((b >> i) & 1) else 0
    return c

def jamtis_verify_checksum(data):
    return jamtis_polymod(data) == M

def jamtis_create_checksum(data):
    polymod = jamtis_polymod(data + [0,0,0,0,0,0,0,0]) ^ M
    return [(polymod >> 5 * (7 - i)) & 31 for i in range(8)]

# test/example

CHARSET = "xmrbase32cdfghijknpqtuwy01456789"

addr_test = (
    "xmra1mm95tp74ihjcu244xt4hpw1smcg5cdhdubfbmk3iyyw16ned1tu70h"
    "ys0r3784af7r8515f2p9xtrx58akjtwb0cft00ari8jecrighji8aqaexws"
    "h2475q3e1bay734kuhicey8bck5wwfbbp2yi4e4qn9h8dst5aaq8qnbyj0x"
    "rweamt1jwq5m0j1anh5srpm6fkhm6s76s3udi6xi0rm0jwf884j2exgg3t0")

addr_data = [CHARSET.find(x) for x in addr_test]
addr_enc = addr_data + jamtis_create_checksum(addr_data)
addr = "".join([CHARSET[x] for x in addr_enc])

print(addr)
print("len =", len(addr))
print("valid =", jamtis_verify_checksum(addr_enc))

Appendix B: 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.

B.1 Legacy wallets

All e-notes sent to legacy addresses under this protocol are forward-secret unless an address that belongs to the legacy wallet is publicly known.

If an address is known to the ECDLP solver, all privacy is lost because the private view key kv can be extracted from the address to recognize all incoming e-notes. Once incoming e-notes are identified, the ECDLP solver will be able to learn the associated key images by extracting kga = DLog(K1, G) and calculating KI = (kga + kgo) Hp(Ko).

B.2 Jamtis wallets

Jamtis wallets offer better forward secrecy than legacy wallets.

All e-notes are forward secret unless an address that belongs to the Jamtis wallet is publicly known.

If a wallet address is known, the ECDLP solver will be able to extract the private keys dfa, dir and daj / dur.

  1. The knowledge of dfa will allow the adversary to slightly reduce the privacy of internal e-notes, similarly to using a Filter Assist 3rd party service.

  2. The knowledge of dfa and dir will allow the adversary to calculate view tags and nominal address tags for all external payments received to the wallet. There will be a certain number of false-positive matches, but incoming payments to any address that was used at least twice can be detected by finding repeated address tags.

  3. The knowledge of daj / dur will allow the adversary to derive the shared secret key X4, which will reveal all external payments to that specific address, including the amounts. If at least two such e-notes are spent, the adversary will also be able to detect outgoing payments from the address. This would require the calculation of the discrete logarithm of all key images with respect to the key image bases of the received payments. The adversary will be able to see repeated values of kgi + kgj, recognizing the spends.

B.3 Summary

ECDLP solver knows Legacy wallet Jamtis wallet
just blockchain data private1 private
one public address complete privacy loss privacy loss for external e-notes to that address
medium privacy reduction for other external e-notes
small privacy reduction for internal e-notes
all public addresses2 - privacy loss for all external e-notes
small privacy reduction for internal e-notes
  1. Except of e-notes received under the old transaction protocol
  2. Access to the GenAddr wallet tier
@jeffro256
Copy link

jeffro256 commented May 1, 2024 •
edited
Loading

The private address key daj should bind to the public spend key Ks, the address index j, as well as an 'address index generator' secret sgenj. This is because this allows index generator proofs to expose sgenj instead of sga. See Appendix A.2 of Implementing Seraphis.

@jeffro256
Copy link

For Jamtis address public keys Dxj, we multiplied by daj instead of 1 / (daj) in the implementation so that we could use the crypto::x25519_invmul_key function on the balance recovery side to multiply those two scalars at once. Small detail though, won't kill performance either way.

@jeffro256
Copy link

In Section 6.1.4, why do coinbase transactions all have one ephemeral pubkey per output?

@jeffro256
Copy link

Section 6.4: s/descrived/described

@jeffro256
Copy link

In section 6.6.2 "Hidden Enotes":

This prevents the FilterReceived wallet tier from probabilistically linking transactions to the wallet.

This is not totally true, the filter-assist (FilterReceived) tier can still probabilistically link transactions to the wallet if they have data from more than one transaction. The hidden enotes feature only prevents probabilistically determining owned enotes for a single transaction in isolation.

For the remaining e-notes, all 16 bits are filled with the secondary view tag.

This is problematic as the PaymentValidator tier can hone into which enotes are your self-sends with a greater degree of accuracy than it should [probability 2^(-16) versus 2^(-tag_size)]. In Implementing Seraphis, there's a completely different derivation for "auxiliary" enotes (I think I like the term "hidden" better actually), which is bound to the view-balance key, so completely opaque to the filter-assist or view-received key. This fixes that problem, but does add a little bit of complexity. Additionally, if we do this view-balance key based derivation, we can expand the size of the complementary view tag (if benchmarks and testing deemed it beneficial for scanning perf) without exacerbating this privacy issue.

@tevador
Copy link
Author

tevador commented May 1, 2024

Thank you for the review.

"filter-assist" instead of "filter-received"

OK, filter-assist sounds better.

The private address key daj should bind to the public spend key Ks, the address index j, as well as an 'address index generator' secret sgenj. This is because this allows index generator proofs to expose sgenj instead of sga. See Appendix A.2 of Implementing Seraphis.

All good ideas. Will add.

For Jamtis address public keys Dxj, we multiplied by daj instead of 1 / (daj) in the implementation so that we could use the crypto::x25519_invmul_key function on the balance recovery side to multiply those two scalars at once. Small detail though, won't kill performance either way.

I figured using 1 / d in the address is more efficient because you don't need to invert the scalar everytime you receive a payment. You only need to invert once when generating the address.

In Section 6.1.4, why do coinbase transactions all have one ephemeral pubkey per output?

Applying the general rule "one common pubkey for 2-output transactions" is not possible for coinbase transactions because it might be a 3rd party generating the transaction (e.g. p2pool) and they would be unable to generate the shared secrets for both outputs with just one common value of De. The rule for 2-output transactions only works if one of those e-notes is change.

This is not totally true,

OK, I will reword that to be more precise.

This is problematic as the PaymentValidator tier can hone into which enotes are your self-sends with a greater degree of accuracy than it should

The secondary view tag for self-spends (hidden e-notes are always self-spends) is:

vt2 = SecretDerive("jamtis_secondary_view_tag" || kvb || Ko)

(see tables in 6.4 and 6.6)

PaymentValidator tier doesn't know kvb, so it cannot derive the secondary tag for hidden e-notes. They will look like any unrelated e-note to them.

@jeffro256
Copy link

he secondary view tag for self-spends (hidden e-notes are always self-spends) is:

vt2 = SecretDerive("jamtis_secondary_view_tag" || kvb || Ko)

Okay sorry I must have skipped over that, that's a good path.

@UkoeHB
Copy link

UkoeHB commented May 2, 2024 •
edited
Loading

How do you sign/prove a Cryptonote key image using the Jamtis-RCT spend key?

@tevador
Copy link
Author

tevador commented May 2, 2024

The spend authorization proof is described here in chapter 3.2: https://github.com/kayabaNerve/fcmp-ringct/blob/develop/fcmp%2B%2B.pdf

@UkoeHB
Copy link

UkoeHB commented May 2, 2024

Thank you

re-define output keys as O = x · G + y · T (where y = 0 for all existing outputs), and preserve the linking tag definition of x · HashToPoint(O).

If KI = k_vb Hp(K), then any view-balance wallet can burn enotes owned by the master wallet. See https://raw.githubusercontent.com/UkoeHB/Seraphis/master/implementing_seraphis/Impl-Seraphis-0-0-3.pdf Section 8.4.4 footnote 24 for a related issue.

@kayabaNerve
Copy link

kayabaNerve commented May 2, 2024 via email

@UkoeHB
Copy link

UkoeHB commented May 2, 2024

Ah right, interesting dynamic. I will think some more about it to be confident.

@jeffro256
Copy link

Optional Jamtis Feature Proposal:

Single Signer Self Sends Are Always Hidden, But it Requires a Onetime Scan with full Keys to Initiate (SSSSAAH-BROSKI)

Summary

This optional feature would be enabled by setting a flag in Polyseed, defaulting to false. This means that the user would have to commit to this feature being enabled/disabled for the lifetime of their wallet. Your self send enotes would change just as described: every one would be set to hidden (all view tag bits taken up by vt2). This would mean that your light wallet server learns absolutely no on-chain information about your self send enotes/transactions, not even probabilistic information (timing analysis still possible depending on the implementation). Your light wallet server will not send you scanning information about your self-send transactions, and as such, you are expected to keep track of these through other channels. Your light wallet server would only really be there to help you filter incoming received enotes from other parties. I believe this method of hiding all self-send enotes tackles the two biggest remaining on-chain data privacy attacks against LW users.

Pros

  • Defense against "LW2LW relationship" privacy attack (described below)
  • Defense against "Chosen LW sender transactions" privacy attack (also described below)
  • LWSs have less information about client's self sends in general
  • If you tell your LWS that you are a SSSSAAH-BROSKI wallet, you can reduce the number of enotes you need to download/scan against by about 2x since you don't need to download potential hidden enotes, only those enotes with matching primary view tags.
  • Indistinguishable on-chain from normal Jamtis/Legacy

Cons

  • In the case of a missing or corrupted wallet cache, the LW user must perform a full wallet scan up to the present chainstate before switching back to remote filter-assist scanning
  • Using a LW in a multisig setup becomes much trickier because you must know the txids of all signed self-send transactions, whether or not you signed them
  • This scheme is not friendly to using multiple separate LW wallet caches at once under certain implementations.
  • If you want to learn contextual information about your self sends txs from your LWS, without giving away which ones are those, your LWS needs to send you a list of all txids that are entering the chain in which block.
  • Telling your LWS that you are using a wallet with SSSSAAH-BROSKI enabled gives away persistent info.

Privacy attacks

LW2LW Relationship

If a LWS has the filter-assist keys of two users who send XMR between themselves (doesn't have to be two-way), then they can see that these two users are both involved in an overlapping set of transactions where the primary view matches are complementary. This is because one primary view tag will match for the recipient, and one for the sender. The more transactions there are between them, the exponentially more likely it is that these two users are sending funds between each other from the PoV of the LWS. The LWS can extend this tracking technique to multiple users to build up a probabilistic social graph.

SSSSAAH-BROSKI thwarts this attack by severing the link on the sender side, so that only the receiver gets their primary view tag matched. From the PoV of the LWS, even if they have both filter-assist keys, they get no information about the sender's view tags, and thus cannot probabilistically find overlapping transactions sets and thus cannot infer transaction relationships from on-chain data.

Chosen LW Sender Transactions

This attack involves the attacker having a preselected set of N transactions, and then searching for a sender of some of those (or all) transactions. This attacker may obtain this list of transactions from, say, raiding your favorite Kinder egg distributor. They can then corroborate or compromise your LWS (or be the same entity), and send them the set of N transactions. The expected number of transactions that should contain a primary view tag match for any random filter-assist key is roughly N/(2^(tag_size)), not factoring in the number of outputs per transaction (the point is that it's a small fraction). And more importantly, its exponentially less likely that a random user will have a matching primary view tag for a increasing long sequence of non-associated transactions. So the attacker/LWS could search for a user with an abnormally high number of matching transactions from that set and link that user to those transactions with a high degree of certainty.

Again, SSSSAAH-BROSKI thwarts this attack by severing the link on the sender side. This does not do anything to mitigate this attack on the receiving side, but it does basically eliminate it on the sender side.

@tevador
Copy link
Author

tevador commented May 2, 2024

If KI = k_vb Hp(K), then any view-balance wallet can burn enotes owned by the master wallet.

Spending an output with the key K = x G + y T requires the knowledge of both x and y (otherwise you can't make a valid composition proof that's part of the SA+L proof). If you use a different value of K, the key image will be different. So AFAICS, no, the view-only wallet cannot burn the e-note. The only thing it can do is calculate the key image to detect when the e-note is spent.

@jeffro256
Copy link

@UkoeHB I made that same mistake too since I was in the Seraphis thinking mode where we can malleate the onetime-address and still get the same key image generator.

@tevador
Copy link
Author

tevador commented May 2, 2024

This optional feature would be enabled by setting a flag in Polyseed, defaulting to false.

I haven't fully analyzed the proposal, but I personally don't think this feature is important enough to spend a Polyseed bit on (there are only 2 unallocated bits left). The attacks you describe only apply to users who give up their filter-assist key, which is an explicit opt-out of the strongest privacy guarantees of the protocol.

@jeffro256
Copy link

The NormalizeX() function simply drops the x coordinate.

Shouldn't it be "drops the y coordinate"?

@tevador
Copy link
Author

tevador commented May 3, 2024

Ed25519 points are serialized as the y-coordinate and the parity of the x-coordinate. NormalizeX() normalizes the parity of x to be even (by conditionally negating the point). This has technically the same effect as y-only serialization, i.e. dropping the x-coordinate. So there is no actual computation involved.

@jeffro256
Copy link

This allows the address itself to be transferred via an insecure channel.

It may be worth nothing that the 125 bit output may be enough to prevent preimage attacks with standard strength, but not collision attacks. We should also maybe specify that whichever hashing algorithm we use to calculate the RIDs, it needs to be slow in order to make finding preimages harder.

@tevador
Copy link
Author

tevador commented May 6, 2024

but not collision attacks

Collision attacks on RIDs are not an issue. In order to find a collision, the attacker would need to generate both addresses that collide (this is how collision attacks work). So they can only replace between a pair of addresses they both own, which is not useful for any practical attack.

If the attacker wanted to swap a 3rd party address for their own with the same RID, that's not a collision attack anymore, but a preimage attack, which is infeasible at 120 bits.

The original implementation of RIDs is in this repository, although dashes have been since replaced with underscores to enable double-click selection and also we use a different base32 variant now.

@jeffro256
Copy link

It could be an issue if a service misused RIDs as unique identifiers. For example, let's say there was a service that let's you withdraw XMR and it provides you a receipt that contains an RID. An attacker could switch out the address for another one with the same RID and claim that the receipt wasn't valid since they can't produce a valid payment proof for that address.

That's why I think we should note its lack of collision resistance and that they should NOT be used as identifiers. You should really only rely on RIDs from trusted sources (AKA from people who won't perform collision attacks). As such, the term "RID" might be inappropriate for what this human-readable preimage resistant string is.

@jeffro256
Copy link

@kayabaNerve and I discussed Janus mitigations for main addresses yesterday and came to the conclusion that we'd like to see space specifically dedicated to the payment ID, so that main addresses can be guaranteed Janus protections (by the same method of encoding randomness then recomputing D_e). We disagree on whether or not to make it per-output or per-tx, but I'd like to be able to guarantee to the users that their main addresses are Janus protected unconditionally.

I say that we provide the payment ID space per-tx since that's how its currently done and takes less space. We could then phase it out in X months now that we have a replacement with Jamtis. @kayabaNerve proposes to make the payment ID space per-output so that we can send to multiple integrated addresses within one transaction.

@tevador
Copy link
Author

tevador commented May 7, 2024

An attacker could switch out the address for another one with the same RID and claim that the receipt wasn't valid since they can't produce a valid payment proof for that address.

The sender can provide the original address with the payment proof and show that it has the same RID. This proves that the attacker is to blame.

we should note its lack of collision resistance

I'm planning to mention this in section 5.2.6.

As such, the term "RID" might be inappropriate for what this human-readable preimage resistant string is.

On the contrary, I think the term exactly describes what it is. It identifies the recipient, who generated the (one or more) addresses that match this RID. Basically, if you get an address that matches an RID, you can be pretty sure it comes from the person who created the RID.

You should really only rely on RIDs from trusted sources (AKA from people who won't perform collision attacks)

I'm not aware of any useful attacks that can be done with collided RIDs. The sender can always prove that they are the victim of a collision attack, which only the recipient could have performed.

Actually, bitcoin addresses are 160-bit hashes, so they are also susceptible to collision attacks (with a work factor of 280), but as with RIDs, I'm not aware of any useful attacks.

To be on the safe side, we could increase RIDs to 160 bits to match bitcoin. This would need 32 characters if we lose the checksum.

@jeffro256
Copy link

To be on the safe side, we could increase RIDs to 160 bits to match bitcoin. This would need 32 characters if we lose the checksum.

I think we should leave them the size that they are since preimage resistance is definitely more important than collision resistance, and making them longer might hinder the main use case. Just as long as we communicate that RIDs from untrusted sources shouldn't be used to uniquely identify addresses from that same untrusted source then we should be fine.

@tevador
Copy link
Author

tevador commented May 7, 2024

we'd like to see space specifically dedicated to the payment ID, so that main addresses can be guaranteed Janus protections

I'm not opposed to this. The current solution is the best you can do for legacy addresses without increasing the tx size beyond what the Jamtis protocol needs.

I say that we provide the payment ID space per-tx since that's how its currently done and takes less space. We could then phase it out in X months now that we have a replacement with Jamtis.

I prefer this solution.

@kayabaNerve
Copy link

kayabaNerve commented May 7, 2024 via email

@tevador
Copy link
Author

tevador commented May 7, 2024

We can keep the single legacy PID for the time being. Merchants who want to batch payments to integrated addresses should migrate to Jamtis instead, which provides basically the same function (even expanding the PID from 8 to 16 bytes).

@kayabaNerve
Copy link

kayabaNerve commented May 7, 2024 via email

@jeffro256
Copy link

I remember why we used 2 different shared secret derivations for selfsend enotes: we need a way to derive different enote components in the case of a 2-output tx where both are selfsends since they use 1 ephemeral pubkey. This proposal in its current form does not have it and thus cannot have 2 output selfsends without burning funds.

@jeffro256
Copy link

Or we could go back to the somewhat ugly method of binding shared secrets to the output's index within the transaction.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment