Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

JAMTIS

This document describes a new addressing scheme for Monero.

Chapters 1-2 are intended for general audience.

Chapters 3-7 contain technical specifications.

Table of Contents

1. Introduction

1.1 Why a new address format?

Sometime in 2023, Monero plans to adopt a new transaction protocol called Seraphis [1], which enables much larger ring sizes than the current RingCT protocol. However, due to a different key image construction, Seraphis is not compatible with CryptoNote addresses. This means that each user will need to generate a new set of addresses from their existing private keys. This provides a unique opportunity to vastly improve the addressing scheme used by Monero.

1.2 Current Monero addresses

The CryptoNote-based addressing scheme [2] currently used by Monero has several issues:

  1. Addresses are not suitable as human-readable identifiers because they are long and case-sensitive.
  2. View-only wallets need key images to be imported to detect spent outputs [3].
  3. Too much information about the wallet is leaked when scanning is delegated to a third party.
  4. Generating subaddresses requires view access to the wallet. This is why many merchants prefer integrated addresses [4].
  5. Addresses are susceptible to man-in-the-middle (MITM) attacks [5].
  6. Subaddresses that belong to the same wallet can be linked via the Janus attack [6].

1.3 Jamtis

Jamtis is a new addressing scheme that was developed specifically for Seraphis and tackles all of the shortcomings of CryptoNote addresses that were mentioned above. Additionally, Jamtis incorporates two other changes related to addresses to take advantage of this large upgrade opportunity:

  • A new 16-word mnemonic scheme called Polyseed [7] that will replace the legacy 25-word seed for new wallets.
  • The removal of integrated addresses and payment IDs [8].

2. Features

2.1 Address format

Jamtis addresses, when encoded as a string, start with the prefix xmr1 and typically consist of 181 characters. Example of an address: xmr1majob1977bw3ympyh2yxd7hjymrw8crc9kinodkm8d3wdu8jdhf3fkdpmgxfkbywbb9mdwkhkya4jtfnod5h7s49bfyji1936w19tyf396ypjo9n64runqjrxwp6k2s3phxwm6wrb5cob6c1ntrg2mugeocwdgnnr7u7bgknya9arksrj

There is no longer any "main address" - all Jamtis addresses are equivalent to a subaddress.

2.2 Recipient IDs

Jamtis introduces a short recipient identifier (RID) that can be calculated for every wallet and every address. RID consists of 25 alphanumeric characters that are separated by hyphens for better readability. The RID for the above address is regne-hwbna-u21gh-b54no-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.3 Certified addresses

To protect from MITM attacks, Jamtis addresses can be optionally signed by the owner of the wallet. The main use cases are:

2.3.1 Identity verification

When Alice and Bob meet, Bob can write his RID on a piece of paper and give it to Alice. When Bob sends Alice an address in the future, Alice will know the address belongs to Bob because it is signed with a key that matches the RID Bob gave her.

2.3.2 Undeniable payments

When proving a payment [9], Alice can convince Charlie that the address she made a payment to belongs to Bob, because the address was signed by Bob's key. If the address were not signed, Bob could claim that the address is not his, but Alice's own address.

2.3.3 Online commerce

Dave runs an online shop at https://eshop.example.com. To assure his customers, he can create a special DNS record under the domain name eshop.example.com that validates his Monero public key and he can provide certified Monero addresses to all his customers. When shopping at Dave's website, Alice can feel safe to send her Monero to the provided address, because her wallet software will confirm that the address is owned by the domain eshop.example.com.

2.4 Light wallet scanning

Jamtis introduces new wallet tiers below view-only wallet. One of the new wallet tiers called "FindReceived" is intended for wallet-scanning and only has the ability to calculate view tags [10]. It cannot generate wallet addresses or decode output amounts.

View tags can be used to eliminate 99.6% of outputs that don't belong to the wallet. If provided with a list of wallet addresses, this tier can also link outputs to those addresses. Possible use cases are:

2.4.1 Wallet component

A wallet can have a "FindReceived" 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.4.2 Third party services

If the "FindReceived" 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 at least 256. The third party will not learn which outputs actually belong to the wallet and will not see output amounts.

2.5 Wallet tiers for merchants

Jamtis introduces new wallet tiers that are useful for merchants.

2.5.1 Address generator

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

2.5.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.6 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.7 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.8 Robust output detection

The detection of outputs received to current Monero subaddresses is based on a lookup table. This can sometimes cause the wallet to miss outputs that are received to subaddresses not present in the lookup table [16].

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

3. Notation

3.1 Serialization

  1. Fixed-size integers are serialized in little endian byte order.
  2. Private keys are serialized as 256-bit integers.
  3. String constants are serialized in ASCII encoding and always include an implicit null byte at the end.
  4. Elliptic curve points are serialized as 256-bit integers, with the lower 255 bits being the y-coordinate of the point and the most significant bit being the parity of the x-coordinate.
  5. The function BytesToInt256(x) deserializes a 256-bit little-endian integer from a 32-byte input.
  6. The operator || concatenates the serialized representations of its inputs.
  7. The function Padb(x) outputs x || 0x00 || 0x00 || ... || 0x00 where the number of padding zero bytes is such that the total length of the output is a multiple of b bytes.

3.2 Hash functions

The function H(x) refers to the keccak-256 hash function. The following other functions based on H are used:

  1. H1(x) = H(x)[0] is hash function with an output length of 1 byte.
  2. H8(x) = H(x)[0:8] is hash function with an output length of 8 bytes.
  3. H16(x) = H(x)[0:16] is hash function with an output length of 16 bytes.
  4. Hs(x) = BytesToInt256(H(x)) mod ℓ refers to a "hash to scalar" function, where is a prime number.
  5. Hp(x) refers to an unspecified "hash to point" function, which outputs elliptic curve points.
  6. KeyDerive(k, x) = Hs(Pad136(k) || x) is a function to derive elliptic curve private keys.
  7. SecretDerive(k, x) = H(Pad136(k) || x) is a function to derive secret keys for symmetric cryptography.

3.3 Elliptic curve

This specification assumes the use of the ed25519 elliptic curve, which includes a cyclic subgroup 𝔾 of prime order ℓ = 2252 + 27742317777372353535851937790883648493.

  1. Uppercase letters usually refer to elements of 𝔾.
  2. Lowercase letters usually refer to elements of Z (scalars).
  3. Scalar multiplication is denoted by a space between the scalar and the group element, e.g. K = k G.
  4. Scalar multiplication may be prepended with the number 8, which means that the point is also multiplied by the ed25519 cofactor to ensure the result belongs to the group 𝔾.

3.3.1 Base points

The following three base points are used:

Point Derivation Serialized (hex)
G generator of 𝔾 5866666666666666666666666666666666666666666666666666666666666666
U Hp("seraphis U") 126582dfc357b10ecb0ce0f12c26359f53c64d4900b7696c2c4b3f7dcab7f730
X Hp("seraphis X") 4017a126181c34b0774d590523a08346be4f42348eddd50eb7a441b571b2b613

3.4 Block cipher

The function BlockEnc(k, x) refers to the application of the Blowfish [11] permutation using the secret key k on the 64-bit little-endian integer x. The function BlockDec(k, x) refers to the application of the inverse permutation using the key k.

3.5 Recoverable signatures

In order to save space, certified addrfesses use a recoverable Schnorr signature scheme specified in this section as a set of two functions SignIdent and RecoverIdent.

3.5.1 SignIdent

This function accepts two parameters: a private key k and an abitrary octet string data.

  1. Select a deterministic nonce r = KeyDerive(k, data || "SignIdent nonce")
  2. Calculate R = r G
  3. Calculate e = Hs(R || data)
  4. Calculate s = (e-1*k - r) mod ℓ
  5. Return the tuple (R,s)

3.5.2 RecoverIdent

This function accepts two parameters: the signature tuple (R,s) and an abitrary octet string data.

  1. Calculate e = Hs(R || data)
  2. Calculate u = e*s mod ℓ
  3. Calculate K = u G + e R
  4. Return K

3.5.3 Security

If an adversary changes R or data, the resulting public key K will change unpredictably.

If an adversary replaces s with s' = (s + e-1*m) mod ℓ, the public key will change to K' = K + m G. For this reason, the private signing key k must never be constructed by adding an offset to an existing key.

3.6 Hash identifier

We define a HashIdent function that accepts an arbitrary octet string data and returns H16(data) encoded in base32 using the ID32 scheme [12].

4. Wallets

4.1 Wallet parameters

Each wallet consists of two main private keys and a timestamp:

Field Type Description
km private key wallet master key
kvb private key view-balance key
birthday timestamp date when the wallet was created

The master key km is required to spend money in the wallet and the view-balance key kvb 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.

4.2 New wallets

4.2.1 Standard wallets

Standard Jamtis wallets are generated as a 16-word Polyseed mnemonic [7], which contains a secret seed value used to derive the wallet master key and also encodes the date when the wallet was created. The key kvb is derived from the master key.

Field Derivation
km BytesToInt256(polyseed_key) mod ℓ
kvb kvb = KeyDerive(km, "view-balance key")
birthday from Polyseed

4.2.2 Multisignature wallets

Multisignature wallets are generated in a setup ceremony, where all the signers collectively generate the wallet master key km and the view-balance key kvb.

Field Derivation
km setup ceremony
kvb setup ceremony
birthday setup ceremony

4.3 Migration of legacy wallets

Legacy pre-Seraphis wallets define two private keys:

  • private spend key ks
  • private view-key kv

4.3.1 Standard wallets

Legacy standard wallets can be migrated to the new scheme based on the following table:

Field Derivation
km km = ks
kvb kvb = KeyDerive(km, "view-balance key")
birthday entered manually

Legacy wallets cannot be migrated to Polyseed and will keep using the legacy 25-word seed.

4.3.2 Multisignature wallets

Legacy multisignature wallets can be migrated to the new scheme based on the following table:

Field Derivation
km km = ks
kvb kvb = kv
birthday entered manually

4.4 Additional keys

There are additional keys derived from kvb:

Key Name Derivation Used to
kga generate-address key kga = SecretDerive(kvb, "generate-address key") generate addresses
kfr find-received key kfr = KeyDerive(kvb, "find-received key") scan for received outputs
kid identify-wallet key kid = KeyDerive(kga, "identify-wallet key") certify addresses
ket encrypt-tag key ket = SecretDerive(kga, "encrypt-tag key") encrypt address tags

The keys kga and kfr separate the view access into two tiers. The first one provides the ability to derive all public addresses that belong to the wallet and the latter is used to calculate the sender-receiver shared secret when scanning for received outputs.

The key kga has two additional child keys kid and ket, which are used in different cryptographic algorithms when generating an address.

4.5 Key hierarchy

The following figure shows the overall hierarchy of wallet keys. Note that the relationship between km and kvb only applies to standard (non-multisignature) wallets.

key hierarchy

4.6 Wallet access tiers

Tier Knowledge Off-chain capabilities On-chain capabilities
AddrGen kga generate public addresses none
FindReceived kfr recognize all public wallet addresses eliminate 99.6% of non-owned outputs (up to § 5.3.5), link output to an address (except of change and self-spends)
ViewReceived kga, kfr all view all received except of change and self-spends (up to § 5.3.14)
ViewAll kvb all view all
Master km 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 (FindReceived)

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 with pre-calculated spend keys (up to § 5.2.4). This reduces the amount of data that a light wallet has to download by a factor of at least 256.

4.6.3 Payment validator (ViewReceived)

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

4.6.4 View-balance 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.

4.7 Wallet public keys

There are 3 global wallet public keys. These keys are not usually published.

Key Name Value
Ks wallet spend key Ks = kvb X + km U
Kid identify-wallet key Kid = kid G
Kfr find-received key Kfr = kfr G

The keys Ks and Kfr are required by lower wallet tiers.

For better UX when opening or restoring a wallet, the wallet is identified by HashIdent("Monero RID" || Kid).

5. Addresses

5.1 Address generation

Jamtis wallets can generate up to 256 different addresses. An address is identified by a 64-bit integer j with the most significant 8 bits set to zero.

Each Jamtis address consists of three public keys and an encrypted tag:

  • K1j = Ks + kxj X
  • K2j = kaj Kfr
  • K3j = kaj G
  • tj = BlockEnc(ket, j)

The private keys kaj and kxj are derived as follows:

Keys Name Derivation
kaj address keys kaj = KeyDerive(kga, "address key" || j)
kxj spend key extensions kxj = KeyDerive(kga, "key extension" || j)

All addresses contain 3 unique public keys and are thus unlinkable by default.

Wallet software MUST NOT generate addresses with j >= 256.

5.2 Sending to an address

When sending amount a to someone else's address (K1, K2, K3, t), the sender does the following:

  1. Generate a random nonzero scalar r from Z.
  2. Calculate the ephemeral public key Ke = r K3
  3. Calculate the derived key Kd = 8*r K2
  4. Calculate the view tag v = H1("view tag", Kd)
  5. Calculate the shared secret q = Hs("sender-receiver secret", Kd)
  6. Encrypt the address tag t~ = t XOR H8("address tag", q)
  7. Derive a one-time output public key Ko = K1 + q X
  8. Calculate the blinding factor b = Hs("blind", q, r G)
  9. Encrypt the amount a~ = a XOR H8("amount", q, r G)
  10. Calculate the amount commitment C = b G + a H
  11. Output (Ke, v, t~, Ko, a~, C)

5.3 Receiving an output

The receiver does the following to examine a potential output (Ke, v, t~, Ko, a~, C):

  1. Calculate the nominal derived key Kd' = 8*kfr Ke
  2. Calculate the nominal view tag v' = H1("view tag", Kd')
  3. If v' != v, abort.
  4. Calculate the nominal shared secret q' = Hs("sender-receiver secret", Kd')
  5. Decrypt the nominal address tag t' = t~ XOR H8("address tag", q)
  6. Decrypt the nominal address index j' = BlockDec(ket, t')
  7. If j' >= 256, abort.
  8. Derive the address spend key K1j = Ks + kxj X
  9. If K1j != Ko - q' X, abort.
  10. Derive r' G = Ke / kaj
  11. Decrypt the nominal amount a'= a~ XOR H8("amount", q, r' G)
  12. Calculate the nominal blinding factor b' = Hs("blind", q, r' G)
  13. Calculate the nominal amount commitment C' = b' G + a' H
  14. If C' != C, abort (possible Janus attack).
  15. Calculate the partial private spend key ksp = kvb + kxj + q
  16. Derive the linking tag Kt = (Ks - kvb X) / ksp
  17. Set the boolean s to the spend status of the linking tag Kt
  18. Output the private values (a, b, j, ksp, s)

5.4 Change and self-spends

Change outputs and self-spends are special because the sender is the same as the receiver. There are heuristics that can be applied by lower wallet tiers to recognize when outputs are being spent based on the presence of outputs that send funds back to the wallet [13].

To protect from such attacks, the output construction and recognition is modified for change and self-spends.

5.4.1 Self-spend detection

When a wallet software is constructing a transaction to an address (K1, K2, K3, t), the following IsSelfSpend function MUST be called to detect self-spends:

  1. Decrypt the nominal address index j' = BlockDec(ket, t)
  2. If j' >= 256, return false.
  3. Derive the address spend key K1j = Ks + kxj X
  4. Return K1j == K1.

5.4.2 Output construction

  1. The shared secret from § 5.2.4 is calculated as q = DeriveKey(kvb, "self secret" || Ke)
  2. For change outputs, the encrypted address tag from § 5.2.6 is set to t~ = j XOR H8("address tag", q)
  3. For self-spends, the encrypted address tag from § 5.2.6 is set to t~ = (j + 256) XOR H8("address tag", q)
  4. The blinding factor from § 5.2.8 is calculated as b = Hs("blind", q)
  5. The encrypted amount from § 5.2.9 is calculated as a~ = a XOR H8("amount", q)

The distinction between change outputs and self-spends is done to preserve the transaction history (self-spends should be visible in the history, change outputs not).

5.4.3 Output recognition

Change outputs and self-spends can only be detected by wallet tiers ViewAll and Master because it requires the private key kvb. Whenever an output with a matching view tag is discovered in a transaction that spends a previous wallet output:

  1. Derive the nominal shared secret as q' = DeriveKey(kvb, "self secret" || Ke)
  2. Decrypt the nominal address index j' = t~ XOR H8("address tag", q')
  3. If j' >= 257, abort.
  4. If j >= 256, this may be a self-spend. Set j = j - 256. Otherwise this may be a change output.
  5. Derive the address spend key K1j = Ks + kxj X
  6. If K1j != Ko - q' X, abort.
  7. Decrypt the nominal amount a'= a~ XOR H8("amount", q)
  8. Calculate the nominal blinding factor b' = Hs("blind", q)
  9. Continue from § 5.3.13

5.5 Transaction size

Jamtis has a small impact on transaction size.

5.5.1 Transactions with 2 outputs

The size of 2-output transactions is increased by 8 bytes. The encrypted payment ID is removed, but the transaction needs two encrypted address tags t~ (one for the recipient and one for the change). Both outputs can use the same value of Ke.

5.5.2 Transactions with 3 or more outputs

Since there are no "main" addresses anymore, the TX_EXTRA_TAG_PUBKEY field can be removed from transactions with 3 or more outputs.

Instead, all transactions with 3 or more outputs will require one 40-byte tuple (Ke, t~) per output.

6. Address encoding

6.1 Address structure

An address has the following overall structure:

Field Size (bytes) Description
Header 6* human-readable address header (§ 6.2)
K1 32 address key 1
K2 32 address key 2
K3 32 address key 3
t 8 address tag
Signature 64 for certified addresses (§ 6.3)
Checksum 8* (§ 6.4)

* The header and the checksum are already encoded in base32

6.2 Address header

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

"xmr" <version char> <network type char> <address 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 3 bytes are not 0x78 0x6d 0x72 ("xmr").

The "xmr" 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.

6.2.1 Version character

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

6.2.2 Network type

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

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

6.2.3 Address type

type char address type
"a" anonymous
"c" certified

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

6.3 Signature

All Jamtis addresses are by default unlinkable to the wallet that created them. However, the owner of the wallet may optionally attach a signature that links the address to the wallet identity key Kid. The signature is present if the address type character in the address header is "c".

The signature field is encoded as:

(R,s) = SignIdent(kid, "Monero address signature" || Header || K1 || K2 || K3 || t)

When parsing a certified address, the wallet software can calculate the receiver's identity key as:

Kid = RecoverIdent((R,s), "Monero address signature" || Header || K1 || K2 || K3 || t)

6.4 Checksum

The purpose of the checksum is to detect accidental corruption of the address. The checksum consists of 8 characters and is calculated using a BCH code [15] with a degree-8 polynomial. The checksum can detect all errors affecting 4 or fewer characters and will fail to detect more errors with a chance of less than 1 in 1012. [TODO: Specify the BCH polynomial.]

6.5 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 refers to the 3 address public keys, the address tag and the optional signature. The checksum is the 8-character checksum (already in base32). The base32 encoding uses the character set ybndrfg8ejkmcpqxot1uwis2a345h769.

6.5.1 Address length

Address type length
anonymous 181
certified 283

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

6.6 Recipient authentication

6.6.1 Recipient identifiers

Because addresses are bulky and opaque, Jamtis defines a concise, more human-friendly identifier for each address, called the Recipient identifier (RID). RIDs are calculated depednding on the address type:

Address type RID
anonymous HashIdent("Monero RID" || Header || K1 || K2 || K3 || t)
certified HashIdent("Monero RID" || Kid)

6.6.2 Validating an RID

There are 4 ways how an RID may be validated when sending to an address:

  1. It may be already present in the sender's address book.
  2. It may be entered manually by the user. In this case, it's best to obtain the RID from the receiver using a different communication channel than the one used to transfer the address.
  3. The user may enter a domain name (e.g. example.com) and the RID is validated by performing a TXT DNS lookup of a subdomain equal to the RID (e.g. regne-hwbna-u21gh-b54no-8x36q.example.com). [TODO: Specify the contents of the TXT field.]
  4. The user may enter an onion address and the public key is decoded from the onion address (v3 onion addresses encode an ed25519 public key that's also usable in Monero) and compared to the address public key.

6.6.3 Authentication workflow

When sending to an address, wallet software should follow this authentication workflow:

  1. The address is parsed and verified that it's well-formed.
  2. The RID is calculated.
  3. If the RID is present in the local address book, the recipient's name is loaded and displayed with a green check mark. Skip to step 8.
  4. The user is presented with a "recipient validation dialog", where they are asked to enter an RID or a domain name.
  5. If the address RID matches the one that was entered or obtained via DNS or the onion domain, the RID is displayed as validated with a yellow check mark. Skip to step 7.
  6. If the RID doesn't match the address, no DNS record was found or the user dismisses the dialog, the RID is displayed with a red cross mark as "unverified".
  7. The user is asked to enter the remaining payment parameters.

7. Test vectors

TODO

References

  1. https://github.com/UkoeHB/Seraphis
  2. https://bytecoin.org/old/whitepaper.pdf
  3. https://www.getmonero.org/resources/user-guides/view_only.html
  4. monero-project/meta#299 (comment)
  5. https://www.reddit.com/r/Monero/comments/mcvuxc/beware_crypto_stealing_malware/
  6. https://web.getmonero.org/2019/10/18/subaddress-janus.html
  7. https://github.com/tevador/polyseed
  8. monero-project/monero#7889
  9. https://www.getmonero.org/resources/user-guides/prove-payment.html
  10. monero-project/research-lab#73
  11. https://en.wikipedia.org/wiki/Blowfish_(cipher)
  12. https://github.com/tevador/id32
  13. https://gist.github.com/tevador/50160d160d24cfc6c52ae02eb3d17024#gistcomment-4006358
  14. https://github.com/monero-project/monero/blob/319b831e65437f1c8e5ff4b4cb9be03f091f6fc6/src/common/base58.cpp#L157
  15. https://en.wikipedia.org/wiki/BCH_code
  16. monero-project/monero#8138
@UkoeHB
Copy link

UkoeHB commented Nov 28, 2022

I think we should discourage custom implementations from embedding data into the address index. It's supposed to be a randomly generated unstructured identifier to achieve the best collision resistance.

The index is not 'supposed to be a randomly generated unstructured identifier' - it's supposed to be a generic tool that enables randomly generating addresses. Making indices cleartext would have long-term privacy costs for people who actually want structured indices (i.e. want them more than the privacy cost).

The more I think about it, the more I dislike the idea of baking account indices into the protocol (whether seraphis itself, or jamtis). It excessively elevates the influence of core wallet design decisions on protocol design. There will always be lobbyists who want more bytes to paste in whatever feature they want. Let's not set a precedent here.

@j-berman
Copy link

j-berman commented Nov 28, 2022

It's a feature that appears to be used and very much so appreciated as is. Its optimal implementation would function smoothly across user-facing wallets, even on restore. I think the route that has the highest likelihood of getting there is one where the spec defines an implementation.

I personally like option 4. The primary downside seems like added internal complexity, and it seems it would have no practical impact on UX. The gain is that anyone who wants accounts as they are today, a feature which we know has seen solid usage and appreciation at 4 bytes, would get a smooth UX by default.

Are we aware of any custom subaddress index implementations in the wild today? It seems unlikely there would even be a custom implementation provided accounts are offered out the gate with the same number of bytes people use and expect today.

@UkoeHB
Copy link

UkoeHB commented Nov 28, 2022

The primary downside seems like added internal complexity, and it seems it would have no practical impact on UX.

Just because you can do something, doesn't mean you should. Stuff like this just looks like bloat/cruft to me.

Are we aware of any custom subaddress index implementations in the wild today? It seems unlikely there would even be a custom implementation provided accounts are offered out the gate with the same number of bytes people use and expect today.

No, because subaddresses currently require a look-ahead. However we do have integrated addresses with custom-defined payment IDs. The substitute for payment IDs in jamtis is... custom address indexing.

@tevador
Copy link
Author

tevador commented Nov 28, 2022

The support for accounts with option 4 can be specified as an extension and implemented in the CLI wallet. It has no negative effect on interoperability with 3rd party wallets that choose not to implement it.

it's supposed to be a generic tool that enables randomly generating addresses

It seems that we lost track of the original purpose of embedding the index into the address. The only reason the index is there is to efficiently recognize owned addresses without the need for a potentially unbounded look-up table.

The original proposal specified a 64-bit sequential index, which clearly leaks information (the number of addresses in use), which prompted the use of the block cipher based encryption scheme.

If we change the index to 128 bits for random generation, encryption is no longer needed and it would only bloat the protocol.

If someone wants to abuse the index to store custom data:

  1. This will only hurt their own privacy, not the privacy of others because the address index is always encrypted in the blockchain.
  2. They are capable of implementing a custom encryption scheme themselves, if they desire to do so.

I don't see a reason to complicate the protocol to accomodate use cases that the index is not designed for. In your own words:

Just because you can do something, doesn't mean you should.

@UkoeHB
Copy link

UkoeHB commented Nov 28, 2022

The support for accounts with option 4 can be specified as an extension and implemented in the CLI wallet. It has no negative effect on interoperability with 3rd party wallets that choose not to implement it.

Third party wallets that want to load other wallets need to implement it, there is no interop by default as there is with a single index.

If we change the index to 128 bits for random generation, encryption is no longer needed and it would only bloat the protocol.

This doesn't make sense. Increasing to 128 bits was to enable random generation, not to create an expectation of random generation. The original goal of subaddresses was to let users efficiently recover and manage funds sent to apparently unrelated addresses. Avoiding duplication (enabling random generation) and hiding the indexing scheme (ciphering the index) both support that goal.

Fiddling with account indices is just a UX thing that should be kept at the UX layer - as a wallet implementation detail.

@tevador
Copy link
Author

tevador commented Nov 28, 2022

The original goal of subaddresses was to let users efficiently recover and manage funds sent to apparently unrelated addresses.

Exactly. Encryption is not needed for this, so the specs should not be bloated by specifying the external format of the encrypted tag. A lean specification is the following:

  1. j = generate_index_however_you_want(16)
  2. mac = H2(sga || Tmac || j)
  3. (derive private keys based on j)
  4. return the tuple (K1, K2, K3, j, mac)

The default implementation of generate_index_however_you_want is to return random bytes. If wallets want to embed data, they can specify their own encryption method. This is fully interoperable regardless of how the index was originally generated.

@tevador
Copy link
Author

tevador commented Nov 28, 2022

Third party wallets that want to load other wallets need to implement it, there is no interop by default as there is with a single index.

Yes, with option 4, wallets not implementing the feature will not recognize outputs with i != 0. So option 4 would need to be a mandatory part of the specification.

If an interoperable solution is desired while minimizing the specs, then we should modify the MAC calculation to mac = H2(sga || Tmac || j) and let wallets generate j arbitrarily.

The CLI could then use a 4+12 split with a 32-bit account index and a 96-bit randomly generated "address index", together encrypted with Twofish (1 block) to form j. A 96-bit index is good for about 13 billion addresses per account until the collision probability exceeds 1 in a billion.

Custom merchant wallets could just choose j at random and get the full collision resistance.

@UkoeHB
Copy link

UkoeHB commented Nov 29, 2022

If an interoperable solution is desired while minimizing the specs, then we should modify the MAC calculation to mac = H2(sga || Tmac || j) and let wallets generate j arbitrarily.

Proposals to reduce user privacy are dead on arrival. If you are trying to make a point, it's not landing.

Minimizing the spec is one goal among many. You need to show an unambiguous benefit for privacy, security, scalability, or protocol longevity for a discussion to even be worthwhile. At most account indices are related to longevity by supporting a relatively common feature. But even then, it's questionable if any of the proposed solutions are superior in terms of implementation and interoperability effort in the long run. If that's the case, 'minimizing the spec' wins out.

@tevador
Copy link
Author

tevador commented Nov 29, 2022

Proposals to reduce user privacy are dead on arrival.

Nothing I proposed has any negative impact on user privacy. j would be either unstructured (randomly generated) or structured and encrypted (with whatever block cipher the wallet wants to use). A protocol with equal privacy and scalability and simpler specs is clearly superior.

@UkoeHB
Copy link

UkoeHB commented Nov 29, 2022

Nothing I proposed has any negative impact on user privacy. j would be either unstructured (randomly generated) or structured and encrypted (with whatever block cipher the wallet wants to use). A protocol with equal privacy and scalability and simpler specs is clearly superior.

This would just result in wallets having to support both encrypted and unencrypted address indices, with an awkward manual UX to select which one you are using, which is a clear regression. At the very least all core wallets would have to support both. Setting aside UX, Monero has an opt-out privacy design philosophy, not opt-in (switching from opt-out to opt-in is a privacy regression). It's hard to take this proposal seriously.

Going back to account ids, there is a deeper problem that hasn't been highlighted yet. In practice, user wallets like the CLI can only support around 6 bits worth of account ids (64) before the UX degrades seriously. This means 2 or 4 byte account ids implicitly have two modes: user mode (~6 bits of usable ids with special handling for ids outside that range and a setting to disable accounts entirely), automated mode (use the entire id space via an automated process e.g. with RPC). This problem reinforces what I have been saying about address indices - that there is no generic solution and index interpretation must be implementation defined.

I suggest @j-berman take a deeper look at A) what address index schemes the core software wants to vend (probably a 6-8 bit account space for users and a 2-4 byte category space for default RPC-level category management, with built-in option to disable segregation entirely for when you need to import a wallet that uses/used an unknown/unsupported index segregation strategy), B) how to architect the wallet tools to separate index segregation strategies and index generation from enote segregation handling so that both the core wallet features and custom strategies can be supported.

@tevador
Copy link
Author

tevador commented Nov 29, 2022

This would just result in wallets having to support both encrypted and unencrypted address indices, with an awkward manual UX to select which one you are using, which is a clear regression.

No, there is just one case, not two. The derivation function always uses the "encrypted" (externally visible) address index. See this comment.

As for accounts, If we want them to be part of the specification (i.e. mandatory), then option 4 seems to offer the best tradeoffs while being completely orthogonal to address indices:

  1. No extra calculation for users who don't use accounts.
  2. Tiny look-up table for "user mode" (max. ~100 accounts).
  3. Fast discrete log for "automated mode" (max 2^32 accounts).

I we want to avoid mandating how accounts are handled, then a hidden split index results in the cleanest specification.

@UkoeHB
Copy link

UkoeHB commented Nov 29, 2022

The derivation function always uses the "encrypted" (externally visible) address index. See this comment.

I see, I misunderstood this. The system would return an unencrypted payload (address index used to make the address) on balance recovery, which may be post-processed to decrypt it if the payload was originally encrypted. It's still an opt-in approach and therefore strictly worse than ciphering the payload by default.

  1. No extra calculation for users who don't use accounts. 2. Tiny look-up table for "user mode" (max. ~100 accounts). 3. Fast discrete log for "automated mode" (max 2^32 accounts).

Like I keep saying, this is not a material improvement over just interpreting raw index bytes according to different segregation strategies and therefore does not improve protocol longevity. It also has no impact on privacy, security, or scalability. I'm hoping to see arguments that promote core Monero design goals.

@tevador
Copy link
Author

tevador commented Nov 30, 2022

It's still an opt-in approach and therefore strictly worse than ciphering the payload by default.

It's not a privacy feature, so being opt-in does not make it strictly worse. Encryption is only needed if there is a plaintext to begin with. Not mandating a specific encryption method is better for protocol longevitiy (a future break of Twofish wouldn't break the protocol). The more cryptographic algorithms the protocol relies on, the more fragile it is.

With this approach, wallets that don't support accounts will still show the correct total balance when restoring a wallet that has historically used accounts.

Like I keep saying, this is not a material improvement over just interpreting raw index bytes according to different segregation strategies

I agree. I think the hidden split index (for wallets that want to support accounts) is the best solution.

@UkoeHB
Copy link

UkoeHB commented Nov 30, 2022

It's not a privacy feature, so being opt-in does not make it strictly worse.

It is a privacy feature because 'customizing index generation' and 'hiding the customization' are two different things. Making both the responsibility of the implementer reduces the privacy profile of the protocol and weakens protocol longevity because A) implementers who don't know how to encrypt things properly will lose privacy (and possibly weaken their own security by leaking secrets), B) some implementers will just say 'screw it' and not encrypt at all, C) the overall cognitive burden of using the protocol is increased (more things to think about and figure out in order to use it).

@tevador
Copy link
Author

tevador commented Nov 30, 2022

implementers who don't know how to encrypt things properly will lose privacy (and possibly weaken their own security by leaking secrets), B) some implementers will just say 'screw it' and not encrypt at all, C) the overall cognitive burden of using the protocol is increased (more things to think about and figure out in order to use it).

  1. The specification can include non-binding hints for implementors, which is common with RFCs. Mandating a specific algorithm where it's not needed is a clear sign of an overspecified protocol.
  2. You cannot prevent people from violating their own privacy with bad code. Broken implementations can easily leak private keys and other sensitive data.
  3. You cannot prevent people from leaking data if they want to. Even your encryption algorithm doesn't prevent this, e.g. I can publish an address with the "encrypted" tag badc0de11111111111111111111111112710, which decrypts to 84b94e2016d7eccf81604a4c0e277f0c0000, perfectly matching your specs with a valid MAC.

If the consensus ends up favoring the mandated tag encryption, then I at least strongly recommend to separate the MAC and get rid of the non-standard overlapping encryption routine. A much more cryptographically sound solution would be something like:

  1. j' = TwoFish(key1, j)
  2. mac = H("mac" || key2 || j')
  3. return (j', mac)

@UkoeHB
Copy link

UkoeHB commented Nov 30, 2022

The specification can include non-binding hints for implementors

You can do this, but as I said it increases the burden for implementers.

You cannot prevent people from violating their own privacy with bad code.

You can reduce the opportunities for people to violate their own privacy.

You cannot prevent people from leaking data if they want to.

Sure, but you can change the equation from 'lazy information leak' to 'intentional information leak'. In other words, opt-out privacy is better than opt-in.

If the consensus ends up favoring the mandated tag encryption, then I at least strongly recommend to separate the MAC and get rid of the non-standard overlapping encryption routine. A much more cryptographically sound solution would be something like:

I would be fine with this if blake2b wasn't 3.5x slower than twofish in this scenario (using a keyed hash; the unkeyed hash is 1.8x slower). I don't feel like rehashing the siphash argument again, unless you want to do it.

@tevador
Copy link
Author

tevador commented Nov 30, 2022

  1. Security takes precedence over speed.
  2. 700 vs 200 CPU cycles is a meaningless difference in this case. Both are so fast that the bottlenecks will be elsewhere (I/O with remote scanning, Diffie-Hellman with local scanning).

@UkoeHB
Copy link

UkoeHB commented Nov 30, 2022

Security takes precedence over speed.

You keep saying this is a matter of security. How is the current scheme insecure? Calling cipher on a block of bytes is always secure if your cipher key has enough entropy. Ciphering doesn't work if you have a bad IV because you can get duplicate ciphered blocks between messages. In our case, the index is an IV so the first cipher pass always produces a unique sequence of bytes, which means the second cipher pass (that is equivalent to ciphertext stealing, not something I invented) always produces a unique sequence of bytes.

@tevador
Copy link
Author

tevador commented Dec 1, 2022

"Encrypt-then-MAC" is a standard construction that has a formal security proof.

The use of ciphertext stealing (which is a form of encryption) to provide a MAC in combination with custom padding is non-standard. In general, block ciphers cannot replace hashes. I guess it would have a higher chance of passing review if you could provide a formal security proof, but it's still problematic for conservative security because it's using a non-standard algorithm for performance reasons, while the performance gain is not really needed.

@UkoeHB
Copy link

UkoeHB commented Dec 1, 2022

Looks like there is something called CBC-MAC. Although that construction is a bit different from what we are doing, it still sets a precedence for building a MAC with a cipher.

The only security requirements our scheme needs are: A) bits of the cipher-tag secret can't be leaked, B) all bits of the address tag are pseudo-randomly dependent on all bits of the address index and all bits of the cipher-tag secret (there is no need for an explicit dependency on constants like the MAC). (A) is trivially met by using an established block cipher and a 32-byte cipher-tag secret. (B) is trivially met by the current scheme's construction. Other requirements of a standard MAC don't apply because we are just using the MAC as a hint, so false positives are acceptable/expected unlike in a standard setting (i.e. a MAC-pass that produces an invalid address index). False negatives are acceptable as well because our system assumes any party can mangle data freely (although 'false negative' is kind of a misnomer when dealing with a mangled address or badly constructed enote).

@tevador
Copy link
Author

tevador commented Dec 1, 2022

Your MAC is constructed by leaking 16 bits of the "plaintext", which is very different from CBC-MAC. This seems to be closer to "Encrypt-and-MAC", where the MAC is calculated from the plaintext, but in your case the MAC is the plaintext at the same time.

Even if the MAC construction was provably secure, your solution is not Pareto-optimal because you can get the same security and up to 10x higher speed by using AES instead of Twofish. Blake2 is the conservative choice, AES is the fast choice. Twofish is less conservative than Blake2 and less performant than AES. I would still choose Blake2.

@UkoeHB
Copy link

UkoeHB commented Dec 1, 2022

Your MAC is constructed by leaking 16 bits of the "plaintext", which is very different from CBC-MAC.

I said it sets a precedent, that's all. We should stop calling it a MAC anyway, because it's just a 'hint' not a MAC. In fact, I will update the code today to change this so we can avoid future misunderstandings about the security properties of the address tag.

Even if the MAC construction was provably secure, your solution is not Pareto-optimal because you can get the same security and up to 10x higher speed by using AES instead of Twofish.

This seems like a disingenuous argument considering your own claim that twofish is more than fast enough. A fast C-only twofish implementation is superior to all the C-only AES implementations I tested, which means it will perform well regardless of hardware. Saying twofish is not 'Pareto-optimal' for our use-case is a textbook example of bikeshedding.

@tevador
Copy link
Author

tevador commented Dec 1, 2022

I would be fine with this if blake2b wasn't 3.5x slower than twofish

Your agument against using Blake2b implies that performance is your primary concern. I'm simply pointing out that if performance was the primary goal, AES would be a better choice than Twofish. I still think Blake2 is fast enough for the use case. Can you point out a scenario when a Blake2-based MAC would be a bottleneck?

Also using Twofish adds more cryptographic code that will need to be reviewed. Is that not a valid concern? Both Blake2b and AES are already part of the Monero codebase.

blake2b ... 3.5x slower than twofish ... using a keyed hash; the unkeyed hash is 1.8x slower

I think your keyed hash benchmark is wrong. There should be no performance difference between keyed and unkeyed Blake2b unless the key changes for every hash. If the key doesn't change, you can reuse the hash state after the first compression function call. So the real performance difference would be 1.8x in this case.

@UkoeHB
Copy link

UkoeHB commented Dec 1, 2022

Your agument against using Blake2b implies that performance is your primary concern.

It's not quite this simple. We need a cipher algorithm (in my opinion) for encrypting the address index. If we are already using a cipher algorithm, then it is not crazy to extend its use to cover the address tag hint as well as the address index. If it so happens that doing so is faster than pulling in a hash function for encrypting the hint, that's a win in my book.

Both Blake2b and AES are already part of the Monero codebase.

There is not a fast AES implementation in the Monero codebase. OAES sucks.

I think your keyed hash benchmark is wrong.

Possibly, but reusing the hash state doesn't seem to be helping more than ~7% for small hash data sizes. You can check the tests here and run the test cases with ./build/Linux/seraphis_lib/release/tests/performance_tests/performance_tests --filter=\*blake2b\* --stats

@tevador
Copy link
Author

tevador commented Dec 1, 2022

It seems that blake2b_init_key doesn't actually call the compression function. You can force that by prepending a zero byte. This should result in a ~2x speed-up.

diff --git a/tests/performance_tests/blake2b.h b/tests/performance_tests/blake2b.h
index 3057dbc..bdc11ea 100644
--- a/tests/performance_tests/blake2b.h
+++ b/tests/performance_tests/blake2b.h
@@ -93,6 +93,10 @@ public:

       if (blake2b_init_key(&m_hash_state, hash_length, derivation_key.data, 32) < 0)
         return false;
+
+      char c = 0;
+      if (blake2b_update(&m_hash_state, &c, sizeof(c)) < 0)
+        return false;
     }
     else
     {

(Note that it is possible to achieve the same without prepending the zero. This is just to overcome the lazy invocation in the current implementation.)

@UkoeHB
Copy link

UkoeHB commented Dec 1, 2022

It seems that blake2b_init_key doesn't actually call the compression function. You can force that by prepending a zero byte. This should result in a ~2x speed-up.

Ok that worked. In practice it would probably be fine to just paste the cipher secret into the transcript to avoid workarounds like this. Looks like the only practical difference is the key_length parameter gets set in keyed mode (the key bytes are consumed in a different order but that's less relevant).

I think you could avoid the lazy invocation by changing this S->buflen + inlen > BLAKE2B_BLOCKBYTES to S->buflen + inlen >= BLAKE2B_BLOCKBYTES in blake2b_update(). Not sure we want to be hacking on blake2b though.

@tevador
Copy link
Author

tevador commented Dec 2, 2022

I think you could avoid the lazy invocation by changing this S->buflen + inlen > BLAKE2B_BLOCKBYTES to S->buflen + inlen >= BLAKE2B_BLOCKBYTES in blake2b_update(). Not sure we want to be hacking on blake2b though.

That would also require changes in blake2b_final to avoid calling the compression function twice when hashing a multiple of the block size. Using the key directly in the transcript should also be secure (Blake2 is not vulnerable to length-extension attacks).

In any case, since the performance difference between Blake2 and Twofish is relatively small, I think we should use Blake2 for the MAC.

  1. It's a standard construction, easier to reason about and more likely to be accepted by reviewers.
  2. The encryption would simplify to a single block in ECB mode, which is also provably secure.
  3. It's a similar construction as the view-tag. The address tag MAC is basically a "level 2 view tag".

@UkoeHB
Copy link

UkoeHB commented Dec 5, 2022

In any case, since the performance difference between Blake2 and Twofish is relatively small, I think we should use Blake2 for the MAC.

Ok in the interest of resolving this conversation, I updated the library to use blake2b for the address tag hint. The cost in the current implementation seems to be a 2x increase in time to compute the hint (there may be minor perf improvements on the table). @tevador it would be helpful if you could review the updated implementation here.

@j-berman
Copy link

j-berman commented Dec 5, 2022

Last comment on using less than 16 bytes for the address index...

Re-using an address is a privacy degradation, one that's even worse for light wallet users as it reveals received enotes to the light wallet server. Even though 12-14 bytes would offer a very comfortable margin for random address generation, it would be below the standard threshold for guaranteed unique random numbers. This is why I'm still most comfortable with an option that leaves 16 bytes for random address generation for all users (even for the user that use accounts), though yes, one can argue I'm being irrationally paranoid given the way we expect users to use addresses. I don't have more to say on this front. I'm fine moving on from this line of reasoning, but figured it's worth expressing the view.

@tevador
Copy link
Author

tevador commented Dec 5, 2022

@tevador it would be helpful if you could review the updated implementation here.

Thanks. Looks good to me. I find the code more elegant and easier to understand than the previous version.

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