Efficient RingCT GPU Scanning Flow with Subaddresses
Intro
This issue details how to theoretically efficiently implement bulk view-incoming scanning leveraging the GPU, while supporting subaddresses. It doesn't require sending the subaddress tables to the GPU, or for the GPU to access the tables whatsoever.
Notation
See https://github.com/jeffro256/carrot/blob/master/carrot.md#3-notation.
| Symbol |
Name |
| $k_v$ |
Private view key |
| $K_s$ |
Account spend pubkey |
| $K^j_s$ |
Subaddress spend pubkey |
| $K_o$ |
Output pubkey |
| $C_a$ |
Amount commitment |
| $a_{enc}$ |
Encrypted amount |
| $vt$ |
View tag |
| $K_e$ |
Ephemeral enote pubkey |
| $K_d$ |
Diffie-Hellman key derivation |
| $i$ |
Transaction-local output index |
| $k_o$ |
Output pubkey one-time extension |
| $a$ |
Amount |
| $k_a$ |
Amount blinding factor |
| $m_a$ |
Amount encryption mask |
This document uses $H(...)$ to refer to Keccak256, not Blake2b.
Monero Crypto Background
The RingCT addressing protocol
A Monero transaction contains one or multiple (multiple in the case of subaddresses) "ephemeral enote pubkeys" or "ephemeral transaction pubkeys" $K_e$. This pubkey is an Ed25519 (X25519 in CARROT) elliptic curve point used by the receiver to perform a Diffie-Hellman key exchange to obtain a shared secret with the sender. A Monero transaction also contains a list of enotes, each with info $(K_o, C_a, a_{enc}, vt)$ Typically, either one or two enote pubkeys are associated to each enote within a transaction. During the scan process, for each ephemeral enote pubkey associated to a specific enote, the receiver calculates performs the following:
$$\begin{matrix}
K_d = 8 k_v K_e \\\
vt' = H_1(\mathscr{"view\_tag"} \mid\mid K_d \mid\mid i) \\\
\text{if} vt' \neq vt, \text{then ABORT} \\\
k_o = H_n(K_d, i) \\\
K'^j_s = K_o - k_o G \\\
m_a = H_8(\mathscr{"amount"} \mid\mid k_o) \\\
a = a_{enc} \mathscr{XOR} m_a \\\
k_a = H_n(\mathscr{"commitment\_mask"} \mid\mid k_o) \\\
C_a' = z G + a H \\\
\text{if} C_a' \neq C_a, \text{then ABORT} \\\
\text{if} K'^j_s \text{not in subaddress table, then ABORT} \\\
\text{return} (K^j_s, a)
\end{matrix}$$
Note, this does not include payment ID decryption.
Implications of the RingCT addressing protocol
Because the main prime-order subgroup of Curve25519/Ed25519 is a cyclic group of prime order, and thus a simple group, then if $K_e$ is a member of that subgroup, then there does not exist any $k_v' \neq k_v \bmod l$ such that $K_d = 8 k_v K_e = 8 k_v' K_e = K_d'$. What this means is that $K_d$ is unique per account. And if $K_d$ is unique per account, then $k_a = H_n(\mathscr{"commitment_mask"} \mid\mid k_o) = H_n(\mathscr{"commitment_mask"} \mid\mid H_n(K_d, i))$ is unique per account, due to the collision-resistant property of cryptographic hash functions. Assuming the hardness of the discrete log problem, and the computational binding property of our Pederson commitments, given an opening $z, a$ such that $C_a = z G + a H$, it is intractable to find $a' \neq a, z' \neq z$ such that $C_a = z G + a H = z' G + a' H = C_a'$. This means that only one $k_a$ will open any $C_a$, and finally therefore only one value of $k_v$ can pass the $\text{if} C_a' \neq C_a, \text{then ABORT}$ check above.
The practical implication of this fact is whether the LWS manages 10, 100, 1000, or 100000 accounts, it will only ever need to do a subaddress table lookup a maximum of one time per enote. This means that we scan perform GPU, or otherwise parallelizable, scanning without sending all the subaddresses of all of the accounts to each compute unit.
Coinbase transactions
The above trick doesn't work for coinbase transactions, as coinbase enotes do not contain an amount commitment, since the amount is in plaintext. However, it is a rule by convention that coinbase destinations can only main addresses, not subaddress. As such, while scanning coinbase transactions, the compute unit will need to know the main address spend pubkey $K_s$, but doesn't need the subaddress table either.
Pre-RingCT transactions
The RingCT v4 fork activated on mainnet on January 5th 2017. Subaddresses were not merged into master until Oct 25th 2017. It first made it into release binaries in v0.12.0.0 on Mar 24th, 2018. This means that RingCT support officially predates subaddress support. Thus, it would be acceptable to process pre-RingCT transactions in a similar manner as coinbase transactions: reject potential subaddress pubkeys. The one possible exception to this rule is v1 "unmixable sweep transactions", which are rare, but still allowed today.
Handling other RingCT variations
RingCT transactions before v15 do not have view tags, so the view tag check will have to be skipped. RingCT transactions before v10 have a 32 byte amount field and 32 byte field for the encrypted amount blinding factor, even though it is computed deterministically the same. All reference code, and other Monero code in the wild that I know of uses rct::genCommitmentMask() to generate the amount blinding factor. So it may be acceptable to not use the actual encrypted amount blinding factor while scanning pre-v10 enotes.
Design
CPU pre-processing
For a batch of transactions containing $N$ (ephemeral enote pubkeys plus enote pairs, and for a group of accounts of size $M$, we will need to run $M * N$ instances of the scanning shader. The enote data needs to be parsed from the transaction once. Importantly, the CPU needs to check that $(K_e, K_o)$ are both in the main prime-order subgroup, otherwise, REJECT THAT PAIR. Failing to do so may allow a DoS attack on the LWS, prevent receivers from getting their funds, and/or trick the LWS into thinking funds were scannable for a certain account when they are not. We will need to push the enote data and account data once. Then the CPU can set up all $M * N$ instances to fire at once.
Shader
A non-coinbase scanning shader will take in the following information: $(k_v, K_e, K_o, C_a, a_{enc}, vt, i)$, which is $(32 + 32 + 32 + 32 + 8 + 1 + 4) = 141$ bytes. It will output 1 bit: true or false, signaling whether the scan process succeeded or not. Each $k_v$ value is reused $N$ times, and each value of $(K_e, K_o, C_a, a_{enc}, vt, i)$ is reused $M$ times. The shader can perform the following stripped down scan process:
$$\begin{matrix}
K_d = 8 k_v K_e \\\
vt' = H_1(\mathscr{"view\_tag"} \mid\mid K_d \mid\mid i) \\\
\text{if} vt' \neq vt, \text{then return false} \\\
k_o = H_n(K_d, i) \\\
m_a = H_8(\mathscr{"amount"} \mid\mid k_o) \\\
a = a_{enc} \mathscr{XOR} m_a \\\
k_a = H_n(\mathscr{"commitment\_mask"} \mid\mid k_o) \\\
C_a' = z G + a H \\\
\text{if} C_a' \neq C_a, \text{then return false} \\\
\text{return true}
\end{matrix}$$
A coinbase scanning shader will take in the following information: $(k_v, K_s, K_e, K_o, vt, i)$, which is $(32 + 32 + 32 + 32 + 1 + 4) = 133$ bytes. It will output 1 bit: true or false, signaling whether the scan process succeeded or not. Each value of $(k_v, K_S)$ is reused $N$ times, and each value of $(K_e, K_o, vt, i)$ is reused $M$ times. The shader can perform the following stripped down scan process:
$$\begin{matrix}
K_d = 8 k_v K_e \\\
vt' = H_1(\mathscr{"view\_tag"} \mid\mid K_d \mid\mid i) \\\
\text{if} vt' \neq vt, \text{then return false} \\\
k_o = H_n(K_d, i) \\\
K'^j_s = K_o - k_o G \\\
\text{if} K'^j_s \neq K_s, \text{then return false} \\\
\text{return true}
\end{matrix}$$
CPU post-processing
The CPU will collect the output from the block of shaders per enote, and if 1 of the bits are set, the CPU can followup with the full scan process, including subaddress lookup if applicable, for that specific account.
Applicability to CARROT
A very similar process can be applied to CARROT as well, with the main difference being that the key exchange algorithm uses X25519, not torsion-cleared Ed25519. CARROT also uses Blake2b instead of Keccak256 got the hash function, and binds to different values. But overall, the general technique functions the same.
Practical concerns
The shader programs will have to be very large compared to normal shader programs I've dealt with before. They will need to implement Kecckak256, field arithmetic over $q$, field reduction at the least over $l$, Ed25519 scalar-variable-point multiplication (with fast cofactor clear) , Ed25519 scalar-fixed-point multiplication, Ed25519 point addition, and Ed25519 point negation. None of these operations by themselves are very GPU-friendly. If supporting CARROT in the future, the shader will also need to implement Blake2b and X25519 scalar-variable-point multiplication.
Efficient RingCT GPU Scanning Flow with Subaddresses
Intro
This issue details how to theoretically efficiently implement bulk view-incoming scanning leveraging the GPU, while supporting subaddresses. It doesn't require sending the subaddress tables to the GPU, or for the GPU to access the tables whatsoever.
Notation
See https://github.com/jeffro256/carrot/blob/master/carrot.md#3-notation.
This document uses$H(...)$ to refer to Keccak256, not Blake2b.
Monero Crypto Background
The RingCT addressing protocol
A Monero transaction contains one or multiple (multiple in the case of subaddresses) "ephemeral enote pubkeys" or "ephemeral transaction pubkeys"$K_e$ . This pubkey is an Ed25519 (X25519 in CARROT) elliptic curve point used by the receiver to perform a Diffie-Hellman key exchange to obtain a shared secret with the sender. A Monero transaction also contains a list of enotes, each with info $(K_o, C_a, a_{enc}, vt)$ Typically, either one or two enote pubkeys are associated to each enote within a transaction. During the scan process, for each ephemeral enote pubkey associated to a specific enote, the receiver calculates performs the following:
Note, this does not include payment ID decryption.
Implications of the RingCT addressing protocol
Because the main prime-order subgroup of Curve25519/Ed25519 is a cyclic group of prime order, and thus a simple group, then if$K_e$ is a member of that subgroup, then there does not exist any $k_v' \neq k_v \bmod l$ such that $K_d = 8 k_v K_e = 8 k_v' K_e = K_d'$ . What this means is that $K_d$ is unique per account. And if $K_d$ is unique per account, then $k_a = H_n(\mathscr{"commitment_mask"} \mid\mid k_o) = H_n(\mathscr{"commitment_mask"} \mid\mid H_n(K_d, i))$ is unique per account, due to the collision-resistant property of cryptographic hash functions. Assuming the hardness of the discrete log problem, and the computational binding property of our Pederson commitments, given an opening $z, a$ such that $C_a = z G + a H$ , it is intractable to find $a' \neq a, z' \neq z$ such that $C_a = z G + a H = z' G + a' H = C_a'$ . This means that only one $k_a$ will open any $C_a$ , and finally therefore only one value of $k_v$ can pass the $\text{if} C_a' \neq C_a, \text{then ABORT}$ check above.
The practical implication of this fact is whether the LWS manages 10, 100, 1000, or 100000 accounts, it will only ever need to do a subaddress table lookup a maximum of one time per enote. This means that we scan perform GPU, or otherwise parallelizable, scanning without sending all the subaddresses of all of the accounts to each compute unit.
Coinbase transactions
The above trick doesn't work for coinbase transactions, as coinbase enotes do not contain an amount commitment, since the amount is in plaintext. However, it is a rule by convention that coinbase destinations can only main addresses, not subaddress. As such, while scanning coinbase transactions, the compute unit will need to know the main address spend pubkey$K_s$ , but doesn't need the subaddress table either.
Pre-RingCT transactions
The RingCT v4 fork activated on mainnet on January 5th 2017. Subaddresses were not merged into master until Oct 25th 2017. It first made it into release binaries in v0.12.0.0 on Mar 24th, 2018. This means that RingCT support officially predates subaddress support. Thus, it would be acceptable to process pre-RingCT transactions in a similar manner as coinbase transactions: reject potential subaddress pubkeys. The one possible exception to this rule is v1 "unmixable sweep transactions", which are rare, but still allowed today.
Handling other RingCT variations
RingCT transactions before v15 do not have view tags, so the view tag check will have to be skipped. RingCT transactions before v10 have a 32 byte amount field and 32 byte field for the encrypted amount blinding factor, even though it is computed deterministically the same. All reference code, and other Monero code in the wild that I know of uses
rct::genCommitmentMask()to generate the amount blinding factor. So it may be acceptable to not use the actual encrypted amount blinding factor while scanning pre-v10 enotes.Design
CPU pre-processing
For a batch of transactions containing$N$ (ephemeral enote pubkeys plus enote pairs, and for a group of accounts of size $M$ , we will need to run $M * N$ instances of the scanning shader. The enote data needs to be parsed from the transaction once. Importantly, the CPU needs to check that $(K_e, K_o)$ are both in the main prime-order subgroup, otherwise, REJECT THAT PAIR. Failing to do so may allow a DoS attack on the LWS, prevent receivers from getting their funds, and/or trick the LWS into thinking funds were scannable for a certain account when they are not. We will need to push the enote data and account data once. Then the CPU can set up all $M * N$ instances to fire at once.
Shader
A non-coinbase scanning shader will take in the following information:$(k_v, K_e, K_o, C_a, a_{enc}, vt, i)$ , which is $(32 + 32 + 32 + 32 + 8 + 1 + 4) = 141$ bytes. It will output 1 bit: true or false, signaling whether the scan process succeeded or not. Each $k_v$ value is reused $N$ times, and each value of $(K_e, K_o, C_a, a_{enc}, vt, i)$ is reused $M$ times. The shader can perform the following stripped down scan process:
A coinbase scanning shader will take in the following information:$(k_v, K_s, K_e, K_o, vt, i)$ , which is $(32 + 32 + 32 + 32 + 1 + 4) = 133$ bytes. It will output 1 bit: true or false, signaling whether the scan process succeeded or not. Each value of $(k_v, K_S)$ is reused $N$ times, and each value of $(K_e, K_o, vt, i)$ is reused $M$ times. The shader can perform the following stripped down scan process:
CPU post-processing
The CPU will collect the output from the block of shaders per enote, and if 1 of the bits are set, the CPU can followup with the full scan process, including subaddress lookup if applicable, for that specific account.
Applicability to CARROT
A very similar process can be applied to CARROT as well, with the main difference being that the key exchange algorithm uses X25519, not torsion-cleared Ed25519. CARROT also uses Blake2b instead of Keccak256 got the hash function, and binds to different values. But overall, the general technique functions the same.
Practical concerns
The shader programs will have to be very large compared to normal shader programs I've dealt with before. They will need to implement Kecckak256, field arithmetic over$q$ , field reduction at the least over $l$ , Ed25519 scalar-variable-point multiplication (with fast cofactor clear) , Ed25519 scalar-fixed-point multiplication, Ed25519 point addition, and Ed25519 point negation. None of these operations by themselves are very GPU-friendly. If supporting CARROT in the future, the shader will also need to implement Blake2b and X25519 scalar-variable-point multiplication.