search

zkBob / libzeropool-zkbob

Apache License 2.0
0 stars 2 forks source link

[Research] Replace ECDH with HKDF during shared secret encryption #14

Open AllFi opened 1 year ago

AllFi commented 1 year ago

Reasoning

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

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

Image 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: $keyi = 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 $keys$ 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:

maikReal commented 1 year ago

Ready for dev, waiting for previous optimization tasks

AllFi commented 1 year ago

PRs:

  1. https://github.com/zkBob/libzeropool-zkbob/pull/15
  2. https://github.com/zkBob/libzkbob-rs/pull/63
AllFi commented 10 months ago

The plan for the new encryption scheme adoption: