Skip to content

Instantly share code, notes, and snippets.

@tevador
Last active May 22, 2024 21:58
Show Gist options
  • Save tevador/50160d160d24cfc6c52ae02eb3d17024 to your computer and use it in GitHub Desktop.
Save tevador/50160d160d24cfc6c52ae02eb3d17024 to your computer and use it in GitHub Desktop.

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

key hierarchy

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 2128 different addresses. Each address is constructed from a 128-bit index j. The size of the index space allows stateless generation of new addresses without collisions, for example by constructing j as a UUID [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 1012 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))
@jeffro256
Copy link

jeffro256 commented Sep 28, 2023

This brings me to an interesting privacy hiccup when distributing xk_fr to a third-party, under both the new and old schemes: depending on the size of the previous view tag / primary view tag, a third-party will see that outgoing transaction enotes are exponentially more likely to to be owned by a user the more self-send enotes there are. This affects both light wallets and people using the payment validator tier.

We can reason that the number of successful view tag checks within a transaction unrelated to you follows a binomial distribution. Each view tag check is a Bernoulli trial, so we can expect the number of successful view tag checks X for a transaction with n outputs to follow the distribution X ~ B(n, VTFP), where VTFP is the view tag false positive rate. The probability mass function for getting k view tag matches can be written as P(X = k) = (n choose k) * VTFP^k * (1 - VTFP)^(n-k). As an extreme example, someone may implement PocketChange-like feature which breaks up outputs to help users work around the 10-block lock. Let's say they create 16 self-send outputs and the false positive rate is 1/256. All 16 outputs will be matched by view tag, which should normally only have a probability of 2.939 x 10^-39 (the same chance as randomly guessing someone's AES key). This can also happen with 2-output transactions with one self-spend and one change, although not as severe: the probability should be 1/65536.

We need a way to have third-parties scan the information they need without this privacy downside. I propose that we split up the self-send types into three self-send types: SELF_SPEND, PLAIN_CHANGE, & AUXILIARY_CHANGE. When doing an outgoing transaction, enote types SELF_SPEND XOR PLAIN_CHANGE (one or the other, not both) will always be present. For these enotes, primary view tags will calculated as normal. For any additional desired self-sends, we set the primary view tag to random bits and the self send type to AUXILLIARY_CHANGE, but do everything else the same (meaning binding the self-send type to s^sr_1). When it comes time to scan, we also scan all enotes in transactions in which any of the view tags matched even if their view tag did not match (hence "auxiliary"), but only scan them for type AUXILIARY_CHANGE. Unfortunately, this change will more than double the bandwidth required for light wallet clients, but only marginally affect compute time as no extra DH ops are required, and depending on the complementary view tag size, most enotes won't have to have K_o recomputed.

@jeffro256
Copy link

jeffro256 commented Sep 28, 2023

This wouldn't have to slow down non-auxiliary enote scanning at all (besides an extra amount commitment recomputation on an already confirmed owned enote) due to the following reason: since we assume that exactly one of SELF_SPEND or PLAIN_CHANGE is present in a transaction, they can share the same s^sr_1 derivation, and only have s^sr_2 derivation differ (this avoids the problem of sharing xK_e leading to the same K_o). The s^sr_1 derivation for AUXILIARY_CHANGE would differ, which leaves us with the same number of K_o re-computations that we have to do: 1x for plain check and 2x for self-send check.

For any additional desired self-sends, we set the primary view tag to random bits...

To speed up auxiliary enote scanning, we could actually fill the primary view tag bits up with all complementary view tag bits, since we don't care about it matching anyways, but we're also going to check the complementary view tag.

@tevador
Copy link
Author

tevador commented Sep 29, 2023

Responding here to a reddit comment.

My first major issue with them is that they break one of the big improvements promised by Seraphis, that being the ability to sign a transaction, let it sit, and then broadcast it later by creating the membership proof just before being shipped off.

Dynamic view tags behave exactly like dynamic fees in this regard. When signing a tx, you already commit to the chain state by selecting a fee amount. If the dynamic fees adjust upwards before the tx is submitted, you might have to mine the tx yourself as it won't be relayed. The same applies to dynamic view tags, with the minor difference that the tag size can adjust both upwards and downwards. The dynamic tag size will adjust very infrequently in typical situations. With current chain history, the last adjustment would have been about a year ago (chart). You can mitigate the risk for pre-signed transactions by signing two versions with the 2 most likely view tag sizes.

Second is that it makes Monero even more complex.

That's a non-argument. All new features make Monero even more complex. The question is if the complexity is worth the benefits it brings. For dynamic view tags, I think the answer is yes if we're already introducing an extra public key in every address just to support 3rd party scanning. If we don't adopt dynamic view tags, I think we should revert back to the original Jamtis design with 3 public keys as it seems like a better compromise between complexity and privacy with 3rd party scanning.

@kayabaNerve
Copy link

kayabaNerve commented Sep 29, 2023

@tevador I can't personally support dynamic view tags if dynamic view tags are part of the signed blob and requires re-signing to adjust the size of them. It's very different from creating a TX, saving a 2-byte view tag, publishing it as 1-byte, then rebroadcasting it as 2-byte if necessary, than re-signing entirely.

If they're not part of the signed blob, then they lose their integrity, as anyone can frontrun a TX with invalid view tags in the mempool.

Accordingly, I'm unable to voice support for this complexity due to the practical issues it'd cause (not just complexity which may cause practical issues).

I will also note that while I'm not up to date on JAMTIS, I leaned towards adding an extra key per @jeffro256. What I'd most like however is not to decide on whether or not to have an extra key, yet to have a complete spec document considered up-to-date (not with hundreds of errata comments) and final barring:

  1. Incredibly minor tweaks (DST choices, round counts)
  2. Major issues found. I would not call any issues in view tag tiers major unless they fundamentally invalidate the tier.

Though I'm sure this desire to be finite is well shared, meaning my statement of it may not contribute.

@tevador
Copy link
Author

tevador commented Sep 29, 2023

I want to reiterate my view that the proposed change to extend Jamtis addresses to 4 public keys to improve 3rd party scanning might be wasteful without dynamic view tags.

The static 8-bit view tag works well with a "medium" transaction volume, which is a range from mid tens of thousands to mid hundreds of thousands of enotes per day. We're presently near the bottom of this range. Within this range, the 8-bit view tag provides both good filtering and sufficient anonymity.

However, if a bear market hit and the tx volume plummeted for some reason, then there would be nearly no privacy advantage compared to the 3-key variant of Jamtis. Similarly, if Monero is successful and the tx volume goes up by 2 orders of magnitude, light wallets might be forced to switch to a less private wallet tier to reduce the bandwidth and computation costs. This would also remove any privacy advantage of the 4-key variant.

In both of these scenarios, 3rd party scanning will suffer a privacy loss and we'll be stuck with longer addresses and bloated specs.

Note that even the 3-key variant of Jamtis significantly improves 3rd party scanning. Currently, light wallet clients have to give up their private view key and leak practically all of their transaction history to the scanning server. With 3-key Jamtis, light wallet clients would only give up their "find-received" private key, which will reveal only some incoming transactions (e.g. recurring payments to the same address) without amounts to the scanning server.

A major advantage of 3-key Jamtis is that the 3rd party scanning improvements come "for free" because they are simply a byproduct of Janus attack protection provided by the 3rd public key, so even if 3rd party scanning doesn't catch on, we won't be wasting anything.

@kayabaNerve
Copy link

👍

I can't react to comments, apparently, so I'm forced to leave a new post. I hear you, that all sounds sane, and I have no further comments to contribute at this time.

@jeffro256
Copy link

jeffro256 commented Sep 29, 2023

I think what would solve all these issues is a arbitrary-size-by-concensus (with a reasonable limit, e.g. 24 bits) fixed-size-by-relay view tag. It's just as simple to implement because it does not depend on chain data. A cold signed tx won't temporally be invalidated unless you hold it so long that relay rules change (which is already an issue for fees). The view tag can be part of the signed blob without the need for multiple signings. We can adjust for really low and/or current tx volume if the anonymity set gets dangerously small. Conversely, if there is a large outcry from users that the bandwidth/computational requirements are unmanageable, we can manually increase the size (this really shouldn't happen more than a once every several years if at all, since we can assume that most user's machines / network connections will get at least slightly better year over year). Attackers cannot affect the view tag size by spamming the chain. All in all, we would reap the benefit of fixed-size view tags' linear increase in privacy with transaction volume and general robustness, but we could have a community handbrake if things got bad.

I think that we're all trying really hard to look ahead into the future and predict what tech trends will be like and what user's reactions to them will be and we could sit here all day postulating different user's different rationales for doing things, and create a decent solution for that specific use-case. Ideally, we want something that is both flexible and simple, and I think that making the view tags arbitrary size by consensus, but fixed size by relay is the best way to do that.

@expiredhotdog
Copy link

When signing a tx, you already commit to the chain state by selecting a fee amount

Sure, but that's not quite the same. You can always just set an aggressively high fee rate which practically guarantees that it'll work, whereas the view tag size would have a specific range enforced by consensus (I assume). Unless we take a different approach like @jeffro256 's proposal.

You can mitigate the risk for pre-signed transactions by signing two versions with the 2 most likely view tag sizes.

That seems like an incomplete solution, and isn't guaranteed to work in case of a large surge in volume, whether malicious or not.

The other option would be to have the tag itself signed normally, but its "accuracy level" bundled with the membership proof. That way you can overshoot the number of bits while constructing the transaction, but set its "claimed" accuracy immediately before broadcasting. The downside would be potentially allowing a 3rd party scanner to filter more accurately.

But it might not make much of a difference depending on how many extra bits you fill in: even 4 extras would be expected in 1/16 matches just by random chance, which isn't really that bad, considering how many matches there would already be per day. Especially since not all transactions will use this method.

Maybe this has been brought up before, and if so, then... whoops my bad.

@tevador
Copy link
Author

tevador commented Sep 29, 2023

view tag size would have a specific range enforced by consensus

No, the dynamic tag size would be a relay rule, just like fees.

isn't guaranteed to work in case of a large surge in volume

The view tag size is calculated based on the last 100 000 blocks. Even a large surge in tx volume will take weeks to affect the tag size. Note that during hard forks, we give old transactions only 24 hours to be confirmed before they are permanently invalidated (v9, v11, v14 and v16). The view tag adjustment would never permanently invalidate transactions, it would only make it harder, but not impossible, for them to be mined.

@kayabaNerve
Copy link

I'd be fine with a relay rule so long as on-change, the prior and new value are both valid for a period of 24 hours.

@expiredhotdog
Copy link

expiredhotdog commented Sep 30, 2023

No, the dynamic tag size would be a relay rule

Okay, so not a consensus rule. However it still would, effectively for most users, make it an unusable transaction.

we give old transactions only 24 hours to be confirmed

The 24 hour grace period isn't really an issue since it only happens once every few years and is known in advance, compared to (potentially) within weeks. I think this is a pretty significant tradeoff, potentially not worth the benefits.

Signing multiple different versions of the transaction does work, but it's very much a bandaid-type solution which we should try to avoid.

@tevador
Copy link
Author

tevador commented Sep 30, 2023

I'd be fine with a relay rule so long as on-change, the prior and new value are both valid for a period of 24 hours.

The current proposal has the following:

  1. 10-block delay between the calculation and the view tag size taking effect. This prevents short reorgs from reverting view tag size changes. Longer reorgs will already invalidate transactions due to decoys.
  2. 10000-block (2-week) grace period after each change when both the previous and the current tag sizes are relayed.

However it still would, effectively for most users, make it an unusable transaction.

There is a big difference between invalidated-by-consensus and invalidated-by-view-tag presigned transactions. The former one is useless as you can never hope for the old consensus rules to be restored. The latter can be mined in two situations:

  1. If tx volume changes back and the view tag size again matches the one used in the tx.
  2. The user solomines the tx themself. Due to the existence of hashpower rental services, this option is available to anyone and probably worth it if the presigned tx is valuable enough.

The 24 hour grace period isn't really an issue since it only happens once every few years and is known in advance

If a 24-hour grace period known 1-2 months in advance (e.g. the v11 fork date was finalized 25 days prior to the fork) to permanently invalidate presigned transactions is acceptable, then I think a grace period of a few weeks to temporarily invalidate presigned transactions is also fine.

@jeffro256
Copy link

jeffro256 commented Oct 31, 2023

Here's my attempt at distilling weeks of conversations into a nice table of different contentious Jamtis proposals crossed against properties, so others don't have to read all those comments.

Abbreviation Table

Abbreviation Term
XXK Extra Exchange Key
VT View tag
ATH Address Tag Hint
LW Light Wallet
LWS Light Wallet Server
BCR Bandwidth & Computation Requirements

Quick Summary Table of Contentious Diffie-Hellman-Related Jamtis Proposals

Current XXK XXK + 2 fixed-size VTs - ATH XXK + "dynamic" VT - ATH XXK + "flexible" VT - ATH
Public Address Size 196 247 244 244 244
Fixes Nominal Address Tag Privacy Issues?
Can do Delegated Public Address Generation?
Transaction Size Change None None None +1 byte/tx +1 byte/tx
Doesn't Need Recent Chaindata for VT constr.?
Balances LW BCR Automatically?
Community can change LW BCR w/o fork?
LW Anon Set (Against LWS) Increases w/ Volume?
Scan Speed Change (w/ 8-bit primary VT) 0% -0.4% -0.4% -0.4% -0.4%
Post-Primary VT CPU Time Required For Scanning 1x 100x 100x 100x 100x

What the Rows Mean

  • Public Address Size - The character count for the human-readable Jamtis address you give to sender
  • Fixes Nominal Address Tag Privacy Issues? - Under this scheme are you protected against:
    • A light wallet server identifying incoming enotes with 100% accuracy if they know your public address
    • A light wallet server identifying incoming enotes with 100% accuracy if the public address is sent to more than once
  • Can do Delegated Public Address Generation? - Can a third-party generate addresses on your behalf without any additional loss of privacy?
  • Transaction Size Change - self-explanatory
  • Doesn't Need Recent Chaindata for VT constr.? - Are transaction constructors free from needing up-to-date chain info specifically for constructing view tags?
  • Balances LW BCR Automatically - Does the amount of enotes matched by a LWS stay relatively constant over long time periods so LW BCRs don't increase over time?
  • Community can change LW BCR w/o fork? - Can the community manually change the view tag match rate to meet current user demands?
  • LW Anon Set (Against LWS) Increases w/ Volume? - Does the set of transactions per time period that the LWS knows your wallet is limited to increase with transaction volume?
  • Post-Primary VT CPU Time Required For Scanning - Compared to current Jamtis, the CPU time required to scan for incoming enotes after performing the primary view tag check is 100 times more. This is because each Twofish decipher op is replaced by a x25519 scalar multiplication op. This means that light wallet clients will do ~100 times more CPU work than before, but the bandwidth needed remains the same.

Summary of "Auxiliary" Enotes

Refer to this comment for the auxiliary enote proposal. This change can apply to any of the above proposals, including current Jamtis. Basically, when a transaction has too many self-send enotes, that fingerprints that tx as owned by a LWS. The proposal would allow LW users to churn and to create pocket change without any additional loss of privacy. The downsides is that if any enote matches a primary view tag, all other enotes in the transaction must be attempted to be scanned against the AUXILIARY_CHANGE enote type. For full wallets, this only entails a 1+ extra hash operation slowdown every time an enote matches a primary view tag, but for light wallets, these extra enotes must ALSO be sent "over the wire", also increasing bandwidth requirements.

Difference between "Dynamic" and "Flexible" View Tags

On-chain, both will be serialized as a fixed size buffer of 3 (optionally 2?) bytes per enote. Additionally, there is one integer per transaction, called npbits, constrained to range 0-24 (16 if view tag buffer only 2 bytes wide), which encodes the number of bits from the front of the buffer used to match the primary view tag. Likewise, ncbits is the number of bits from the back of the buffer used to match the complementary view tag, and it is calculated as ncbits = 24 - npbits. The difference between "dynamic" and "flexible" is how the value npbits is enforced. Under the "flexible" scheme, the value npbits is set to a constant value, enforced by relay rule. Under the "dynamic" scheme, the value npbits is enforced to be a function of the on-chain transaction volume. See this comment for the exact proposed formula. Neither of these schemes cause uniformity issues because at transaction construction time, there is only one correct value to choose for npbits. What's nice about the flexible vs dynamic debate is that, as long as npbits is enforced only by relay rule, the community can switch back and forth between the two proposals as it sees fit without forking.

"Less-Contentious" Shared XXK Tweaks

Here's some extra details about tweaks accumulated through discussion that are shared for all XXK proposals and aren't hotly debated, but might be still worth a mention:

  • Suggested by @tevador
    • Get rid of unlock-amounts key in order to help thwart identify-involved fake tier
    • Make one DH privkey depend upon other in secrets derivation tree for same reason
  • Suggested by @jeffro256
    • Bind second/complementary view tag to "residue" of primary DHE in order to help thwart identify-involved fake tier
    • Bind the amount baked key to the first Diffie-Helman exchange to prevent probabilistic Janus attack

@tevador anything I'm missing?

@Gingeropolous
Copy link

so does column XXK still have a -0.4% scan speed change, even though the column name doesn't include VT?

@jeffro256
Copy link

jeffro256 commented Nov 1, 2023 via email

@Gingeropolous
Copy link

So then what is the point of viewtags? With the whole auxiliary enotes thing, it seems that viewtags have a critical flaw that is being hacked around by auxiliary enotes, which seems like added complexity for no gain if the XXK column has the same -0.4% scan speed change without VT.

@j-berman
Copy link

j-berman commented Nov 8, 2023

View tags

I think a flexible view tag is a reasonable option.

  • Relayers start by enforcing a 1 byte view tag.
  • Consensus allows dynamic view tags.
  • If volume starts to increase significantly and sustainably AND light wallets are widely used AND the UX for light wallets starts to degrade AND the use case of submitting presigned txs many weeks in advance ends up an edge case that is outweighed by the light wallet use case, then relayers start enforcing a dynamic view tag.

A major advantage of 3-key Jamtis is that the 3rd party scanning improvements come "for free" because they are simply a byproduct of Janus attack protection provided by the 3rd public key, so even if 3rd party scanning doesn't catch on, we won't be wasting anything.

I think adding a 4th key to the address is still worth it, even if a dynamic view tag is never implemented, because I would rather users be in a situation where an extra key ends up wasted as opposed to a situation where their privacy is worse than it could otherwise be.

On auxiliary enotes

I think the benefits of this are worth it especially with full chain membership proofs. Pocket change is a use case people seem to clearly want (even despite its privacy issues today), to the point where I can see it being a reasonable default wallet behavior with full chain membership proofs.

So then what is the point of viewtags?

@gingeropouls in the current Jamtis spec (and in this matrix of proposals), its primary value-add is offloading the bulk of scanning to a server while preventing the server from being able to know all enotes the user received and spent with cryptographic certainty. It also speeds up full wallet scanning basically the same as view tags do today (i.e. when you don't give up a key to the server).

As currently proposed, if you send yourself e.g. 9 enotes in a tx (e.g. if you were to use a pocket change-like feature), and you give your "find-received" key to a server that can only identify view tag matches of txs which may belong to you, then the server could see "hey, this user had 9 view tag matches in this tx which is statistically very unlikely, therefore the user almost certainly received all 9 enotes." The auxiliary enote proposal above is strictly to ensure even pocket change-like txs would only have a single view tag match among all 9 enotes, so the server would still identify the tx as one that the user needs to scan all enotes for.

@jeffro256
Copy link

Two points about Janus attacks under the new proposed scheme:

  1. It is possible to do a Janus attack on any address when the attacker knows any one address private key. Let's say the attacker knows address private key kja and the Jamtis address corresponding to that address private key. This address private key may be revealed, for example, during an address index proof. The attacker generates ephemeral pubkey Ke = r Kibase (i is index of a new dest to be attacked). The attacker uses the ephemeral key based on an address index i, but actually encrypts the addr_tagj from the old Jamtis address j. We then do the rest of enote building from the address j. When it comes to make the amount baked key, the receiver will calculate kja * Ke. The attacker will know what this value is supposed to be since he knows kja. He can then calculate the "correct" amount baked key, by doing kja * Ke instead of r * G, and therefore, calculate the "correct" ssr2. We can fix this by including a factor of our account secrets in our base key (e.g. the view-received key). This is the reason this attack doesn't work on Jamtis currently: Kj3 contains a factor of kua, which the attacker wouldn't know.
  2. Including Kdaf in the hash of the amount baked key doesn't actually do anything to prevent Janus attacks, since the attacker knows what it should be. Also it isn't needed as long as we can prove that the ephemeral key is "bound" to a certain address index j, since otherwise, we won't reach the same shared secret.

@jeffro256
Copy link

This might seem like a trivial change, but I suggest that we remove the 'a' character from the address header. Two reasons: 1) we make addresses one character shorter (duh), but second is more important: 2) this prefix scheme falls in line with Bech32, litecoin, etc where you have characters in the ticker followed by a version number. I can see confusion possibly arising when people generate an address with the letter 'a' inside the prefix: "Huh? What is XMRA? I don't want XMRA, I want XMR!" initiate frustration

@rbrunner7
Copy link

I suggest that we remove the 'a' character from the address header.

After some searching I found out what that "a" stands for in the first place, see this comment: The letter there has two possible values, "a" for "anonymous address" and "c" for "certified address". There was quite some discussion here over many comments whether such certified addresses are a good idea, ok but overkill, or even a bad idea; I did not go through it all. But I am sure the decision to remove that "a" amounts to deciding whether we support this address distinction in the proposed form, or at least will in the future, with more extensive tooling.

If I was to decide alone I would probably let that stand without much further ado and research ...

@kayabaNerve
Copy link

I don't believe it'd be an issue to have xmr1 vs xmrcert1 and prefer xmr alone.

I also don't believe we should have multiple distinct address in general (though I'd have to double check the certified address discussion). If there's no active plans to support certified addresses now, I'd remove "a".

@tevador
Copy link
Author

tevador commented Apr 3, 2024

The Jamtis invoice encoding starts with the prefix xmri. The Jamtis Wallet keys encoding starts with the prefix xmrw. Other encodings are possible in the future.

The address prefix xmra clearly distinguishes addresses from the other encodings. It might be possible to have just xmr if we avoid using i and w as the version character (which would be beyond version 10, so unlikely to be needed anyways).

no active plans to support certified addresses

Certified addresses have been superseded by certified invoices.

@jeffro256
Copy link

jeffro256 commented May 22, 2024

Discussing post-quantum secrecy for incoming enotes spends on Jamtis-RCT here got me thinking about the same issue with Jamtis on Seraphis. For a few days, I was convinced that Jamtis-Seraphis didn't have this problem because of the different linking tag format, and the fact that the y/x in the linking tag makes it so that there are 2 "unknowns" if a DLP solver knows l = dlog(L, J) = y/x (this is opposed to 1 unknown in Jamtis-RCT L = x Hp(O). However, with just one public address, its address index extensions, and a public linking tag for an enote spending from that address (plain, non-selfsend), a DLP solver can solve for the view-balance key. Here's how it works:

How a DLP Solver Can Find the View-balance key with Address Index Extensions and a Linking Tag

Notation

  • Fixed generators G, X, U, J
  • kvb: view-balance key
  • km: master spend key
  • dvr: view-received key
  • Sj: public address spendkey
  • S: base account spendkey
  • O: Enote onetime address
  • C: Enote amount commitment
  • L: Linking tag for enote
  • kg/x/uaddr: address index extensions keys for Sj
  • kg/x/uo: onetime extensions keys for enote
  • kg/x/uview: enote view extension keys for enote
  • s1sr: sender-receiver secret 1 for enote
  • dlog(P, G): a discrete log oracle/algorithm that returns p in P = p * G

Initial Knowledge

The DLP solver must know the address index extensions kg/x/uaddr for a public address with spendkey Sj beforehand. This is not normally public information, but may be exposed to a verifier during an address index proof or to a generate-address tiered wallet. By virtue of being a DLP solver, they will also be able to calculate dvr from a public address. This means that for any incoming (plain, non-selfsend) enote to that public address, they can calculate the onetime extensions kg/x/uo = H(S, s1sr, C). This means that they know the "enote view" extensions keys kg/x/uview = kg/x/uaddr + kg/x/uo. The other piece of public information that a DLP solver must know is the linking tag L that spends an incoming plain enote to that public address. So in total, the attacker must know (Sj, kgaddr, kxaddr, kuaddr, L) beforehand.

Masker Key Equation 1

Since we know the public address spendkey Sj and the address index extension keys kg/x/uaddr, we can find the base account spendkey S = Sj - kgaddr G - kxaddr X - kuaddr U. We now know the account base spendkey. We know that the account holder would calculate the account base spendkey as S = kvb X + km U. As a DLP solver, we would be able to find u = dlog(U, X), and thus know that S = (kvb + km * u) X. Again as a DLP solver, we would be able to find s = dlog(S, X) = kvb + km * u. Solving for km, we get our first equation in terms of km:

km = (s - kvb) / u

Master Key Equation 2

Onetime addresses are constructed O = (kvb + kxview) X + (km + kuview) U + kgview G, which means that linking tags are constructed as L = (km + kuview) / (kvb + kxview) * J. Given a linking tag L, a DLP solver can calculate l = dlog(L, J) = (km + kuview) / (kvb + kxview). Solving again for km, we can re-arrange this as:

km = (kvb + kxview) * l - kuview

Solving

We now have two equations with two unknowns: km and kvb. We know all the other values in the equations: s, u, l, kxview, kuview. Using basic algebra, we substitute km:

(s - kvb) / u = (kvb + kxview) * l - kuview

and solve for kvb:

kvb = (kuview + s/u - kxview * l) / (1/u + 1/l)

@UkoeHB
Copy link

UkoeHB commented May 22, 2024

@jeffro256 that looks right to me, good analysis. I'll note, however, that section 8.7 of the implementing Seraphis paper already acknowledges this result.

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