jamtis.md

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?
  • 1.2 Current Monero addresses
  • 1.3 Jamtis
• 2. Features
  • 2.1 Address format
    • 2.1.1 Recipient IDs
  • 2.2 Light wallet scanning
    • 2.2.1 Wallet component
    • 2.2.2 Third party services
  • 2.3 Wallet tiers for merchants
    • 2.3.1 Address generator
    • 2.3.2 Payment validator
  • 2.4 Full view-only wallets
  • 2.5 Janus attack mitigation
  • 2.6 Robust output detection
• 3. Notation
  • 3.1 Serialization functions
  • 3.2 Hash function
  • 3.3 Elliptic curves
    • 3.3.1 Curve25519
    • 3.3.2 Ed25519
  • 3.4 Block cipher
  • 3.5 Base32 encoding
• 4. Wallets
  • 4.1 Wallet parameters
  • 4.2 New wallets
    • 4.2.1 Standard wallets
    • 4.2.2 Multisignature wallets
  • 4.3 Migration of legacy wallets
    • 4.3.1 Standard wallets
    • 4.3.2 Multisignature wallets
  • 4.4 Additional keys
  • 4.5 Key hierarchy
  • 4.6 Wallet access tiers
    • 4.6.1 Address generator (AddrGen)
    • 4.6.2 Output scanning wallet (FindReceived)
    • 4.6.3 Payment validator (ViewReceived)
    • 4.6.4 View-balance wallet (ViewAll)
    • 4.6.5 Master wallet (Master)
  • 4.7 Wallet public keys
• 5. Addresses
  • 5.1 Address generation
    • 5.1.1 Address keys
    • 5.1.2 Address tag
  • 5.2 Sending to an address
  • 5.3 Receiving an output
  • 5.4 Change and self-spends
  • 5.5 Transaction size
    • 5.5.1 Transactions with 2 outputs
    • 5.5.2 Transactions with 3 or more outputs
• 6. Address encoding
  • 6.1 Address structure
  • 6.2 Address header
    • 6.2.1 Version character
    • 6.2.2 Network type
  • 6.3 Checksum
  • 6.4 Binary-to-text encoding
    • 6.4.1 QR Codes
  • 6.5 Recipient authentication
• 7. Test vectors
• References
• Appendix A: Checksum

1. Introduction

1.1 Why a new address format?

Sometime in 2024, 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. 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 [3].
4. View-only wallets need key images to be imported to detect spent outputs [4].
5. Subaddresses that belong to the same wallet can be linked via the Janus attack [5].
6. The detection of outputs received to subaddresses is based on a lookup table, which can sometimes cause the wallet to miss outputs [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 xmra and consist of 196 characters. Example of an address: xmra1mj0b1977bw3ympyh2yxd7hjymrw8crc9kin0dkm8d3wdu8jdhf3fkdpmgxfkbywbb9mdwkhkya4jtfn0d5h7s49bfyji1936w19tyf3906ypj09n64runqjrxwp6k2s3phxwm6wrb5c0b6c1ntrg2muge0cwdgnnr7u7bgknya9arksrj0re7whkckh51ik

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

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 "FindReceived" is intended for wallet-scanning and only has the ability to calculate view tags [9]. 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.2.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.2.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.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 Serialization functions

1. The function BytesToInt256(x) deserializes a 256-bit little-endian integer from a 32-byte input.
2. The function Int256ToBytes(x) serialized a 256-bit integer to a 32-byte little-endian output.

3.2 Hash function

The function Hb(k, x) with parameters b, k, refers to the Blake2b hash function [10] 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.
• If the key k is not null, the hash function is initialized using the key k (maximum 64 bytes).
• The input x is hashed.

The function SecretDerive is defined as:

SecretDerive(k, x) = H32(k, 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 [11].

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 generated using the following KeyDerive1(k, x) function:

1. d = H32(k, x)
2. d[31] &= 0x7f (clear the most significant bit)
3. d[0] &= 0xf8 (clear the least significant 3 bits)
4. return d

All Curve25519 private keys are therefore multiples of the cofactor 8, which ensures that all public keys are in the prime-order subgroup. The multiplicative inverse modulo ℓ is calculated as d-1 = 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 [12]. The following three generators are used:

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

Here Hp refers to an unspecified hash-to-point function.

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

KeyDerive2(k, x) = H64(k, 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.4 Block cipher

The function BlockEnc(s, x) refers to the application of the Twofish [13] 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 [14].

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 = KeyDerive1(km, "jamtis_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 = KeyDerive1(km, "jamtis_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
dfr	find-received key	kfr = KeyDerive1(kvb, "jamtis_find_received_key")	scan for received outputs
dua	unlock-amounts key	kid = KeyDerive1(kvb, "jamtis_unlock_amounts_key")	decrypt output amounts
sga	generate-address secret	sga = SecretDerive(kvb, "jamtis_generate_address_secret")	generate addresses
sct	cipher-tag secret	ket = SecretDerive(sga, "jamtis_cipher_tag_secret")	encrypt address tags

The key dfr provides the ability to calculate the sender-receiver shared secret when scanning for received outputs. The key dua can be used to create a secondary shared secret and is used to decrypt output amounts.

The key sga is used to generate public addresses. It has an additional child key sct, which is used to encrypt the address tag.

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.

4.6 Wallet access tiers

Tier	Knowledge	Off-chain capabilities	On-chain capabilities
AddrGen	sga	generate public addresses	none
FindReceived	dfr	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	dfr, dua, sga	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, but are needed by lower wallet tiers.

Key	Name	Value
Ks	wallet spend key	Ks = kvb X + km U
Dua	unlock-amounts key	Dua = dua B
Dfr	find-received key	Dfr = dfr Dua

5. Addresses

5.1 Address generation

Jamtis wallets can generate up to 2¹²⁸ 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 [15].

Each Jamtis address encodes the tuple (K1j, D2j, D3j, tj). The first three values are public keys, while tj is the "address tag" that contains the encrypted value of j.

5.1.1 Address keys

The three public keys are constructed as:

• K1j = Ks + kuj U + kxj X + kgj G
• D2j = daj Dfr
• D3j = daj Dua

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

Keys	Name	Derivation
kuj	spend key extensions	kuj = KeyDerive2(sga, "jamtis_spendkey_extension_u" || j)
kxj	spend key extensions	kxj = KeyDerive2(sga, "jamtis_spendkey_extension_x" || j)
kgj	spend key extensions	kgj = KeyDerive2(sga, "jamtis_spendkey_extension_g" || j)
daj	address keys	daj = KeyDerive1(sga, "jamtis_address_privkey" || j)

5.1.2 Address tag

Each address additionally includes an 18-byte tag tj = (j', hj'), which consists of the encrypted value of j:

• j' = BlockEnc(sct, j)

and a 2-byte "tag hint", which can be used to quickly recognize owned addresses:

• hj' = H2(sct, "jamtis_address_tag_hint" || j')

5.2 Sending to an address

TODO

5.3 Receiving an output

TODO

5.4 Change and self-spends

TODO

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 28 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 De.

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 50-byte tuple (De, t~) per output.

6. Address encoding

6.1 Address structure

An address has the following overall structure:

Field	Size (bits)	Description
Header	30*	human-readable address header (§ 6.2)
K1	256	address key 1
D2	255	address key 2
D3	255	address key 3
t	144	address tag
Checksum	40*	(§ 6.3)

* The header and the checksum are already in base32 format

6.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 [16], 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.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 10¹² of not being detected. The reference code how to calculate the checksum is in Appendix A.

6.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 refers to the address tuple (K1, D2, D3, t), encoded in 910 bits, and the checksum is the 8-character checksum (already in base32). The total length of the encoded address 196 characters (=6+182+8).

6.4.1 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.5 Recipient authentication

TODO

7. Test vectors

TODO

References

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

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 = (
    "xmra1mj0b1977bw3ympyh2yxd7hjymrw8crc9kin0dkm8d3"
    "wdu8jdhf3fkdpmgxfkbywbb9mdwkhkya4jtfn0d5h7s49bf"
    "yji1936w19tyf3906ypj09n64runqjrxwp6k2s3phxwm6wr"
    "b5c0b6c1ntrg2muge0cwdgnnr7u7bgknya9arksrj0re7wh")

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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)

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.

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

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.

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

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

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.

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.

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.

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

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

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.

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

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.

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

The base32 encoding uses the character set ybndrfg8ejkmcpqxot1uwis2a345h769.

What is this character set? Googling ybndrfg8ejkmcpqxot1uwis2a345h769 only brings up this very document.

I found http://philzimmermann.com/docs/human-oriented-base-32-encoding.txt but it lists a different set ybndrfg8ejkmcpqxot1uwisza345h769 (z-base32). Either we go fully compatible with z-base32 and all code written for it, or just use something entirely different and better fit for this specific use case.