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

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

It's z-base32 with the character z replaced by 2. We need all digits since the address version is explicitly included in the "human readable header". It still satisfies all of the design criteria of z-base32 as their only argument against 2 was:

'2' is potentially mistaken for 'z' (especially in handwriting).

Of course you can propose a different character set if you think it's more suitable.

I already foresee many confused devs taking a glance at this set, plugging their z-base32 code and wondering why it doesn't work. Maybe it's better to rearrange it back to sorted set abc...789? The only reason they reordered it in the original proposal was to have an "easy" character at the end, and in this case it's not even at the end becase 3 wallet keys are in the middle.

The only reason they reordered it in the original proposal was to have an "easy" character at the end, and in this case it's not even at the end becase 3 wallet keys are in the middle.

It's true that the order is probably not important in our case.

Maybe it's better to rearrange it back to sorted set abc...789

This could also cause confusion as someone will see abcde... and will assume RFC 4648. It might be better to use a completely random permutation.

Maybe use xmr...789 and the rest in alphabetic order :)

We can try xmrbase32cdfghijknopqtuwy1456789

That will do

I'd personally prefer to user bech32m exactly. I see tevador wants a longer checksum. which I'm not here to dismiss entirely, but it's the easiest to integrate. Barring that, a standardized bech32 character set (bech32's or z-base32, which I'm only now hearing of) makes sense.

The HRP, as defined in bech32m, is free of the character set encoding. Accordingly, it's not an issue if it has chars not in the charset. I question if we can take the same approach here and accordingly use an already standardized base32 charset.

I'd personally prefer to user bech32m exactly.

Bech32(m) uses a polynomial optimized for short addresses. The specs even prohibit addresses longer than 90 characters [1], so it's not useful for us. The bech32 charset order was also optimized specifically for their polynomial, which has some improved bit-error detection capability [2].

If we want to match or exceed the error detection capability of the 32-bit hash used in CryptoNote addresses, we need at least 7 checksum characters, which is an awkward size for a BCH code. So a degree-8 BCH code is the best option, in my opinion.

The HRP, as defined in bech32m, is free of the character set encoding

The HRP encoding was a necessity for bech32, so that an address can have a prefix with the name of your favorite dog-meme-based cryptocurrency, while still using the same character set as bitcoin. We don't need to support other cryptocurrencies, so having a charset tailored for us removes the complexity around having to encode the HRP in order to calculate the checksum.

In short, Monero is so distinct from Bitcoin and other cryptocurrencies that we need to design our own encoding and I think we have enough manpower to do so.

[1] https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#bech32
[2] https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#cite_note-4

I think the ideas in the 4th proposition 'Account index encoded in the output public key' are pretty nice and that we should go in this direction. I have some issues though with K1 depending on G now as you propose.

K1 = Ks + (i / kacct_g + kaddr_g) G + kaddr_x X + kaddr_u U

It means that for i != 0 there will be a term depending on G for the one-time address? If so it means that the enote-image creation will have to take into account this number when generating the blinding factor tk in Ko' = tkG + kaX+ kbU. Also if you mean G to be an independent base from the ones we are using then the composition proofs wouldnt work I guess, since it is meant to be exactly for three bases and not four, right? So I would suggest letting K1 = Ks + xX where x contains the information of the addresses and accounts and we keep the structure as it is. Otherwise the linking tag would be impacted and the whole protocol would have to change I guess. Am I missing something and saying some bs?

I think a better proposition would be just letting x = kaddr^(kaddr*i) or something like that. I didn't think much about the function. What do you think?

Sorry for jumping in late. I don't see that anyone has asked this yet - why not use base64 instead of base32? That would make the anonymous addresses about 30 characters shorter. Since the addresses are already so long we don't expect people to type them in manually or read them aloud, the reduced ambiguity of eliminating mixed-case doesn't seem to me to be a valid argument for base32. And base64 would still be a prime power, still viable for BCH code. The impact on QR codes is kind of a wash, alphanumeric QR at 5.5 bits per symbol vs binary base64 at 6 bits per symbol, but fewer symbols.

QR will use 8 bits per symbol in case of base64.

Right, ok. So for 181 symbols of base32 it will use 996 bits.
For 150 symbols of base64 it will use 1200 bits. Still easily manageable for a QR code.

Is there any reason we can't just use raw 8-bit bytes for the QR code?

Should base64 be seriously considered, please stick to base64url otherwise the / and + will make it harder to generate URLs containing addresses.

It means that for i != 0 there will be a term depending on G for the one-time address? If so it means that the enote-image creation will have to take into account this number when generating the blinding factor

There will be a G-component regardless of the value of i (check the formula carefully). This is done to provide perfect forward secrecy against quantum attackers. Explained in this comment.

why not use base64 instead of base32

With base64, we'd lose the ability to double-click-select an address, which is bad for UX. As for the length, there is not much qualitative difference between 164 and 196 characters, both are way too long to type but easy to copy-paste.

It would be possible to use something like base59, which would save roughly 28 characters, but that would be highly non-standard and require more complex checksum code (mod 59 math instead of simple XOR).

Is there any reason we can't just use raw 8-bit bytes for the QR code?

There are interoperability issues with binary QR codes. Most readers expect a string formatted as an URI. For example, Android apps can define custom handlers for specific URI schemes: https://developer.android.com/training/app-links/deep-linking

Oh, thanks. It is a bit confusing looking at the specs in the main post, the seraphis pdf and the comments at the same time. Maybe we could have a place where we find the updated notations then? Or could you update the specs?

Yes, the specs here are somewhat outdated. I'm planning to update it.

With base64, we'd lose the ability to double-click-select an address,

Why is that?