How do payment ids work?

Question

In particular, how do the encrypted ones work cryptographically.

I'm guessing they are based on the shared secret.

Answer 1

Since StackExchange prefers content to be on the site rather than through links, I've transcribed and annotated the information from luigi1111 on PasteBin to make it more accessible for readers.

Stealth Short Payment IDs

This is a proposal for shortening both "user" and "blockchain" payment IDs from 256 bit (32 bytes) to 64 bit (8 bytes), incorporating a stealth feature to improve anonymity, and adding a new shorter v2 integrated address.

We are basically discussing three different aspects here, which aren't strictly related:

1. Stealth IDs which change every TX similar to addresses

2. Shortened IDs have less characters since the current 256 bit requirement is absurdly large and unnecessary. See examples below

Standard (95): 45BEPXEXAN6YrvHgP3owF8GCzBZ2vCZNb9sMxZG6D7iuSvjVret5ciY2GfqVMHZiPoTEEcmSmVhcyaReTjJafrSqV26ZoYE

64-bit ID integrated (106): 4TZ76dT4mbsizsTtJzy7kYBo9f8xduc8wTsWb86pCmx5Cmh43CDxNS1FRcMrE3CNQ2ZT17vzCudc5TbNYBzizwqZFah5K1Js7VpL88qPSi

Full 256-bit ID integrated (139): 4LRv6jJYxh5Ba1Z4UfCZYmTzP7g1mP5uUC32KgWcMtBi2QV6xGjHpqs5ZeEnpAwaWVNgF7b7xtumQGoL9posmQMfRvFupJBXkZyWGdcDizfMUAiEgrG7cA98yf6vcqJzZT1EPg8A69e

3. Integrated addresses to become v2 addresses and replace/deprecate v1, which isn't in use yet.

The objective is to get the payment ID scheme to a point where it is ready for years of use with no further changes. To maintain backward compatibility with the current payment ID scheme during the transition stealth payment IDs will only be generated by default through the use of integrated addresses. Thus, when recipients are ready to accept the new stealth version, they would use integrated addresses.

This new 64 bit ID will be given a new tx_extra nonce tag: 0x01 (current payment ID is 0x00).

A note on collisions

With 64 bit IDs, there is a non-negligible chance of a collision if they are randomly generated. It is up to recipients generating them to sanity check for uniqueness.

1 million IDs at 64-bit (simplified): 1,000,000^2 / (2^64 * 2) = ~1/36,893,488 so there is a 50% chance a collision happens around 5.06 billion IDs generated.

Current integrated address

At present the integrated address looks like:

netbyte (0x13 [standard Monero is 0x12]) + 32 byte public spend key + 32 byte public view key + 32 byte payment ID (8 byte proposed for v2) + 4 byte checksum of all previous data

JavaScript implementation

Note that JavaScript is only to ease expressing the method. Import cn_util.js from mymonero.com for methods.

For the stealth key, a derivation of the shared secret used for public key generation is required. The varint encoding used by output indices gives us 128 1-byte options to use as part of our key: 0x80 - 0xFF

Choosing entirely arbitrarily: charcode(I) + charcode(D) = 0x49 + 0x44 = 0x8d

Therefore

encryption key = H(sharedSecret + 0x8d)

Note that "+" means "append" above.

//---------------------------------------------------------
//proposal 1.5 (older ideas discarded as subpar and/or unscalable)
//xor payment ID with one-time key
var receiverKeys = create_address(rand_32()); //for example only
var payId = "0123456789abcdef"; //64-bit example
var txkey = random_keypair();
var der = generate_key_derivation(receiverKeys.view.pub, txkey.sec);
var stealthKey = cn_fast_hash(der + "8d").slice(0,16);
var encPayId = hexXor(stealthKey, PayId); //JS can only xor numbers, made up function to xor hex strings

//receiver would:
var der = generate_key_derivation(txkey.pub, receiverKeys.view.sec); //txkey.pub from tx_extra
var stealthKey = cn_fast_hash(der + "8d").slice(0,16);
var payId = hexXor(stealthKey, encPayId); //encPayId from tx_extra
//*compare payID with known set*
//---------------------------------------------------------