[Research] Replace ECDH with HKDF during shared secret encryption

[AllFi]

Reasoning

Below is the profile for single-threaded synchronization of the user on the production environment.

Using it, we can determine which type of work consumes the majority of the synchronization time. It is evident that the majority of time is spent performing elliptic curve scalar multiplication within these four functions.

We already have the issue that aims to drastically reduce the amount of time spent within functions 2 and 4. In theory, this proposal has the potential to entirely eliminate the time spent within functions 3 and 4. Unfortunately, this approach can only be implemented for future transactions.

Description

Within the decrypt_in function, we attempt to identify notes that belong to us using the following method:

1. Restore point $A_i$ from the memo and check that it is in the prime subgroup (function 2)
2. Perform the last step of the ECDH (function 1): $P_i = \eta * A_i$
3. Derive symmetric key: $key_i = keccak_{256}(P_i.x)$
4. Try to decrypt note $Note_i^{enc}$ using $key_i$ and constant nonce
5. ...

In the decrypt_out function, we are trying to decrypt the account and the notes by decrypting $Keys^{enc}$ using the following method:

1. Restore point $A_p$ from the memo and check that it is in the prime subgroup (function 4)
2. Perform the last step of the ECDH (function 3): $P= \eta * A_p$
3. Derive symmetric key: $key = keccak_{256}(P.x)$
4. Try to decrypt keys $Keys^{enc}$ using $key$ and constant nonce
5. ...

In the first case, we must perform ECDH between the sender and the receiver to exchange the common key. However, in the second scenario, we actually perform ECDH between the sender and themselves. What we actually need to do is to encrypt $Keys^{enc}$ in a way that allows us to decrypt it later.

Proposal

Here is a simple proposal for encrypting and decrypting $Keys^{enc}$ without using ECDH.

Key generation

We need to derive a symmetric key $key_s$ from the spending or intermediate key. Perhaps, we can use something like $HKDF_{keccak_{256}}(\eta, keccak_{256}(\text{"ZeroPool"}))$. I am not sure about it.

Encryption:

1. Generate random $nonce$
2. Encrypt $Keys^{enc}$ with $key_s$ and $nonce$
3. Put $nonce$ in the memo instead of $A_p$

Decryption:

1. Deserialize $nonce$ from the memo
2. Try to decrypt keys $Keys^{enc}$ using $key_s$ and $nonce$

By using this scheme, we can bypass slow operations and utilize only symmetric encryption.

Since we are using a random nonce, we must ensure that the probability of collision is negligible. chacha20-poly1305 uses a 96-bit nonce, enabling us to encrypt approximately $2^{32}$ messages with a collision probability of approximately $2^{-32}$. While it is likely sufficient, it may be preferable to use xchacha20-poly1305 instead, as it employs a 192-bit nonce. By using xchacha20-poly1305, we can encrypt up to $2^{32}$ messages with a collision probability of approximately $2^{-128}$.

Implementation details

This protocol update appears relatively straightforward, with the only non-obvious aspect being the memo versioning. It seems to me that there are three potential methods for determining which decryption approach to use during synchronization:

• Since the $nonce$ size is 24 bytes while the $A_p$ size is 32 bytes, we can identify which scheme to use by examining this field within the memo. I don't like this approach.
• We can introduce the version in the memo as we do with direct deposits using free bytes in ItemsNum. The main drawback of this approach is that the memo version will be located after the number of items. I guess it is the viable compromise.
• We can introduce the version in the new field of memo. This approach may be quite costly to implement.

[maikReal]

Ready for dev, waiting for previous optimization tasks

[AllFi]

PRs:

1. Optimize shared secrets encryption scheme #15
2. Optimize shared secrets encryption scheme libzkbob-rs#63

[AllFi]

The plan for the new encryption scheme adoption:

• Review and merge PR: Support new message prefix zkbob-contracts#98
• Upgrade contracts
• Review and merge PR: Support new message prefix zeropool-relayer#212
• Update relayer
• Release a new version of the libzeropool crate that includes this PR: Optimize shared secrets encryption scheme #15
• Update libzeropool version and remove patch section in this PR: Optimize shared secrets encryption scheme libzkbob-rs#63
• Review and merge PR: Optimize shared secrets encryption scheme libzkbob-rs#63
• Release new libzkbob-rs-wasm version
• Update version of libzkbob-rs-wasm in the zkbob-client-js
• Update version of the zkbob-client-js in the console and UI