Post-quantum Turnstile Design for Carrot/FCMP++ Enotes

pq_carrot_fcmp_turnstile.md

Post-quantum Turnstile Design for Carrot/FCMP++ Enotes

Problem

The potential scenario in which future technology (i.e. quantum computers) allows machines to break the security of the discrete log problem poses a threat to the economic security and privacy of the Monero network. FCMP++ mitigates most of the of on-chain privacy concerns posed by a quantum adversary, however, it does not address the economic security threats due to such a machine's ability to forge FCMP++ proofs. Tthe Monero network should migrate to post-quantum (PQ) cryptography before the first working quantum computer is suspected of breaking an Ed25519 relationship. The holders of XMR before that point ideally should also be able to move their funds over to the new scheme. However, the old FCMP++ proofs should not be considered secure after a certain point, at which point old holders of XMR are effectively locked out of spending their enotes.

Requirements

Any solution to migrate old enotes to a new PQ-secure protocol must prove the following statements in a PQ-secure manner:

• Enote exists in the ledger
• Enote's transaction and dependent transactions all have proven balanced and non-negative amounts within their output sets
• Enote's amount is bound at time of creation and cannot be modified later
• Enote has not yet been spent

Any migration of an enote must be signed by its intended recipient without revealing the signing key material to a non-PQ adversary.

Solution

A turnstile with the following design would enable migrating enotes of Carrot/FCMP++ txs received by a Carrot-derived account. In other words, this does not enable spending previous RingCT enotes nor FCMP++ enotes addressed to legacy keys. The overall intuitive approach is to have verifiers re-do Carrot subaddress generation, Carrot enote derivation, and key image opening inside the migrating transaction's input. Due to the way that Carrot subaddress generation and Carrot enote derivation function, we can maintain the security properties mentioned above, even on a FCMP++'s bivariate amount commitments and output pubkeys. This design assumes that referenced enotes for migration, and dependent transactions, could not have been constructed by a quantum adversary. In other words, enotes must have been hoenstly constructed at time of creation and inclusion to the chain.

Design (non-coinbase)

See the Carrot spec for notation.

Proving

To spend an FCMP++ enote with output pubkey $K_o$ and amount commitment $C_a$, the prover sends the TXID of the spent enote, TX local output index, incomplete account spend pubkey $K_{ps} = k_{ps} T$, generate-image preimage secret $s_{gp}$, is_subaddress, second address index preimage $s^j_{ap2}$, contextualized sender-receiver secret $s_{sr}^{ctx}$, amount $a$, enote_type, and a signature of the migration transaction $\Omega_m^{ps}$, proving discrete-log knowledge $k_{ps}$ s.t. $K_{ps} = k_{ps} T$.

Verifying

First, the verifier fetches $(K_o, C_a)$ using given (TXID, local output index), using assumption that existing enotes on-chain were verified correctly. Then, he does the following:

1. If transaction with TXID not in chain, or doesn't contain enough outputs, return FAIL
2. If $K_o$, $C_a$, or $K_{ps}$ not in main prime order subgroup of Ed25519, return FAIL
3. Let $k_{gi}' = ScalarDerive(\text{"Carrot generate-image key"} \Vert s_{gp} \Vert K_{ps})$
4. Let $K_s' = K_{ps} + k_{gi}' G$
5. Let $k'^j_{subscal} = ScalarDerive(\text{"Carrot subaddress scalar"} \Vert s^j_{ap2} \Vert K_s')$, iff is_subaddress, else let $k'^j_{subscal} = 1$
6. Let $K'^j_s = k'^j_{subscal} K_s'$
7. Let $k_a' = ScalarDerive(\text{"Carrot commitment mask"} \Vert s_{sr}^{ctx} \Vert a \Vert K'^j_s \Vert \text{enote\_type})$
8. Let $C_a' = k_a' G + a H$
9. If $C_a' \neq C_a$, then return FAIL
10. Let $k'^g_o = ScalarDerive(\text{"Carrot key extension G"} \Vert s_{sr}^{ctx} \Vert C_a)$
11. Let $k'^t_o = ScalarDerive(\text{"Carrot key extension T"} \Vert s_{sr}^{ctx} \Vert C_a)$
12. Let $K_o' = K'^j_s + k'^g_o G + k'^t_o T$
13. If $K_o' \neq K_o$, then return FAIL
14. If $\Omega_m^{ps}$ does not verify for migration transaction $m$ and pubkey $K_{ps}$, return FAIL
15. Let $L = (k_{gi}' * k'^j_{subscal} + k'^g_o) H^2_p(K_o)$
16. If $L$ is already spent in chain, return FAIL
17. Return SUCCESS

If this prodecure suceeds, then $L$ is marked as spent, and the migration transaction is funded $a$ XMR through this input. Optionally, the sum total of migration inputs $a$ can be tracked to further mitigate unintended inflation.

Security

The opening of amount commitments in this manner is PQ-secure, taking a large amount of inspiration from Switch commitments. To find an opening of $C_a$ where the amount is modified, an adversary must find $s_{sr}'^{ctx}, a', K'^j_s$ s.t. $C_a = ScalarDerive(\text{"Carrot commitment mask"} \Vert s_{sr}'^{ctx} \Vert a' \Vert K'^j_s \Vert \text{enote\_type}) G + a' H$. This problem effictively boils down to a second-preimage problem, which a quantum adversary cannot solve.

Note that the amount blinding factor binds to $K^j_s$, the address spend pubkey. Also note that $K^j_s$ is a function of $K_s$ and extensions, which are also bound to $K_s$. Furthermore, $K_o$ is a function of $K^j_s$ and extensions, which bind to $C_a$. This means that both $C_a$ and $K_o$ are bound to $K_s$. And since $k_{gi}$ is bound to $K_{ps} = k_{ps} T$, finding new $k_{ps}', k_{gi}'$ s.t. $K_s = k_{gi}' G + k_{ps}' T$ boils down to a second-preimage problem.

Since all variables in the calculation of the key image $L$ (i.e. $k_{gi}$, $k^j_{subscal}$, and $k^g_o$) bind $K_o$, it should be intractable for a quantum adversary to fake the key image opening of an existing enote, under our assuption that $K_o$ was previously validated correctly.

The membership proof correctness is so trivial that it may go unnoticed: it validates iff TXID is in the chain and contains more $i$ outputs, where $i$ is the tx-local output index.

Design (coinbase)

See the Carrot spec for notation.

Proving

To spend an FCMP++ enote with output pubkey $K_o$ and amount commitment $C_a$, the prover sends the TXID of the spent enote, TX local output index, incomplete account spend pubkey $K_{ps} = k_{ps} T$, generate-image preimage secret $s_{gp}$, contextualized sender-receiver secret $s_{sr}^{ctx}$, amount $a$, and a signature of the migration transaction $\Omega_m^{ps}$, proving discrete-log knowledge $k_{ps}$ s.t. $K_{ps} = k_{ps} T$.

Verifying

First, the verifier fetches $(K_o, C_a)$ using given (TXID, local output index), using assumption that existing enotes on-chain were verified correctly. Then, he does the following:

1. If transaction with TXID not in chain, or doesn't contain enough outputs, return FAIL
2. If $K_o$, $C_a$, or $K_{ps}$ not in main prime order subgroup of Ed25519, return FAIL
3. Let $k_{gi}' = ScalarDerive(\text{"Carrot generate-image key"} \Vert s_{gp} \Vert K_{ps})$
4. Let $K_s' = K_{ps} + k_{gi}' G$
5. Let $C_a' = G + a H$
6. If $C_a' \neq C_a$, then return FAIL
7. Let $k'^g_o = ScalarDerive(\text{"Carrot coinbase extension G"} \Vert s_{sr}^{ctx} \Vert a \Vert K_s')$
8. Let $k'^t_o = ScalarDerive(\text{"Carrot coinbase extension T"} \Vert s_{sr}^{ctx} \Vert a \Vert K_s')$
9. Let $K_o' = K_s' + k'^g_o G + k'^t_o T$
10. If $K_o' \neq K_o$, then return FAIL
11. If $\Omega_m^{ps}$ does not verify for migration transaction $m$ and pubkey $K_{ps}$, return FAIL
12. Let $L = (k_{gi}' + k'^g_o) H^2_p(K_o)$
13. If $L$ is already spent in chain, return FAIL
14. Return SUCCESS

If this prodecure suceeds, then $L$ is marked as spent, and the migration transaction is funded $a$ XMR through this input. Optionally, the sum total of migration inputs $a$ can be tracked to further mitigate unintended inflation.

Security

The opening of amount commitments in this manner is PQ-secure, since the relation between coinbase amounts and amount commitments is 1-to-1.

Unlike non-coinbase, there is no amount blinding factor binding to $K^j_s$, the address spend pubkey. However, the sender extensions $k^g_o, k^g_t$ themselves bind to $K^0_s = K_s$. Then, following the same logic as non-coinbase, $K_o$ is a function of $K_s$ and extensions, which bind to $K_s$. This means that $K_o$ is bound to $K_s$. And since $k_{gi}$ is bound to $K_{ps} = k_{ps} T$, finding new $k_{ps}', k_{gi}'$ s.t. $K_s = k_{gi}' G + k_{ps}' T$ boils down to a second-preimage problem.

Since all variables in the calculation of the key image $L$ (i.e. $k_{gi}$ and $k^g_o$) bind $K_o$, it should be intractable for a quantum adversary to fake the key image opening of an existing enote, under our assuption that $K_o$ was previously validated correctly.

This design cannot work with coinbase outputs because it relies on the blinding factor $k_a$ of the amount commitment $C_a$ binding to the address spend pubkey $K^j_s$. However, coinbase outputs implicitly have a "blinding factor" of 1 in RingCT. I see four paths forward:

1. Prohibit coinbase enotes to be migrated in a PQ turnstile.
2. Change the consensus protocol so that coinbase outputs contain an amount commitment and range proof, just like RingCT outputs.
3. Require the PQ migration code to be able to store, parse, and fetch enote ephemeral pubkeys $D_e$ from coinbase transaction extra. Turnstile validators would effectively perform either sender-side scanning to derive a $s^{ctx}_{sr}$ which is indirectly bound to $K^j_s$ through the enote ephemeral private key $d_e$. This is possible for all coinbase enotes since there is no "special" coinbase enotes and no shared enote ephemeral pubkeys. Unfortunately, this would reveal the private view-incoming key $k_v$ to a discrete-log solver since the shared ECDH value must be exposed.
4. Modify the derivation of Carrot coinbase one-time extensions $k^g_o, k^t_o$ (AKA sender extensions) to bind to the main address spend pubkey $K^0_s = K_s$. This is alright for scanning purposes, unlike with noin-coinbase, since coinbase enotes don't support addressing to subaddresses. Might need multiple scans for hybrid key hierarchies wallets, though. A side benefit of this approach is that if there is already a distinction between coinbase and non-coinbase derivations of $k^g_o, k^t_o$, the coinbase derivation path could bind to the amount $a$ directly instead of to the implied coinbase amount commitment $C_a$, slightly improving coinbase scanning performance.

Personally, I am in favor of the last option, but this would require yet another set of small tweaks to the addressing protocol.

3. There are several blocks with broken tx extra, see https://paste.debian.net/hidden/b4220f42/ (an example here https://blocks.p2pool.observer/block/4d3030beb38a4e550de1cf2bea9593c37adc99a1b3b8b3b3576fba9f7085f48e https://p2pool.io/explorer/tx/4ab7bdcfa630127a1a2d6c5fc60e5bfb9378159521107df44c8617ad229b3237)
   This means you can't recover the full information out of tx extra, but receiver can if they deem bruteforcing a few bytes fine, most broken blocks have 7 bytes overriden.

4. Given scanning is already hardcoded to reject non-main addresses on coinbase outputs, this seems already a good option. 2. would probably add too much CPU usage for P2Pool outputs, 4. would involve some scalar mults I assume? If this can be bound to before the amount itself that'd be excellent as it can be cached.