Have you heard of Stealth Addresses (SA)? Do you know what cryptography is used in their background? Have you heard of BaseSAP, Umbra, or Monero? If so, then find out here what the Curvy protocol is and how it differs from the above protocols.

There is a great need to introduce private transactions on public blockchains such as Bitcoin and Ethereum. We can achieve this with stealth addresses. The protocols mentioned are based on stealth addresses - addresses that are generated for one-time use and allow the recipient of the transaction to remain anonymous. The protocols listed (BaseSAP, Umbra and Monero) use asymmetric cryptography in the background, more precisely the calculation of the Diffie-Hellman shared secret. These protocols use scalar and elliptic curve point multiplication as well as hashing. Since explaining these protocols would take too long, we refer curious readers to Vitalik's article and those who want to understand elliptic curves in depth to the excellent book Pairings for Beginners.

However, the desired goal (anonymous one-time addresses) can also be achieved with another cryptographic method: elliptic curve pairing. 

To follow the Curvy protocol, we need to briefly define and explain the elliptic curve pairing (or at least try to 😃).

Elliptic curve pairing

Curvy uses Type 3 pairing. 

Let's explore how Curvy works!

The building blocks of the Curvy protocol rely on the spending and viewing key, but also on the view tag (which allows a quick search in the ephemeral registry by the recipient). Therefore, we will explain these components separately.

Spending key 💸 and viewing key 🔎

The recipient of the transaction in the Curvy protocol will generate two key pairs. The first key pair is the private key (spending key) k and the corresponding public key K. Although it is called the "spending key", it is not actually the private key of the new stealth address, but it is crucial for obtaining the private key of each stealth address of the recipient. The public key, which corresponds to the spending key, is obtained by multiplying ge by k, i.e. 

K=k*ge, 

where ge is the generator point of the group of the Secp256k1 elliptic curve and k is from Fp2 - the finite field associated with a Koblitz curve Secp256k1.

Viewing key as a concept appeared later. Namely, the recipient of the transaction can give this key to someone if that person needs to be able to see all his stealth transactions (e.g. to a tax inspector). An important note is that the person holding this key cannot spend money from stealth addresses, but can only see transactions. The viewing key v is a private key, i.e. a number from the final field Fp. The public key corresponding to the viewing key is V is obtained by multiplying v and g1, i.e. 

V=v*g1, 

where g1 is the generator point of the subgroup G1  of pairing-friendly elliptic curve. In the ENS registry, the recipient only adds the public keys associated with the spending and viewing keys, i.e. the points K and V.

Curvy protocol overview

A detailed overview of the Curvy protocol can be found in our paper, and the diagram of the Curvy protocol is shown below. We have to mention that besides this protocol based on pairing and uses dual keys, we have developed 3 other pairing-based protocols, but this is the only one that is Ethereum-friendly (all our protocols are described in detail in the paper).

The full workflow of a stealth address scheme can be viewed as follows:

1. The recipient generates his spending key k and viewing key v and stealth meta-address M=(K, V), where K=k*g_e and V=v*g₁.
2. The recipient adds an ENS record to register M as the stealth meta-address for recipient.eth.
3. The sender searches for the recipient's stealth meta-address M on the ENS registry, using recipient's ENS name.
4. The sender generates an ephemeral key r, which only the sender knows and uses only once (to generate this one stealth address). The sender also generates ephemeral public key R=r*g₁ and publishes it in the ephemeral public key registry.
5. The sender uses an algorithm that combines his ephemeral key r and the recipient's meta-address M to generate a stealth address. The sender calculates the public key of the stealth address as b*K, where b is the first coordinate of e(r*V,g₂), where g₂ is the generator point of the subgroup G2  of pairing-friendly elliptic curve. He can now send assets to this address. The public key of the stealth address can only be calculated by the sender and by the person who possesses the viewing key, since either the private ephemeral key r (which only the sender possesses) or the viewing key v is required (because r*V=v*R).
6. The recipient searches through all public keys that have been published in the ephemeral public key registry since his last scan until finds a public key that matches the stealth address to which the sender sent the assets (for a quick search, use the view tag).
7. The recipient's private key of the stealth address is b*k and calculates the public key of the address as private key*g_e. The private key of the stealth address can only be calculated by the recipient, as requires the private key k.

The following figure shows this protocol in detail. 

View tag

To make it easier to scan the total set of ephemeral public keys, one technique is to add a view tag to each ephemeral public key. There are different ways to implement this idea. One way to achieve this in the above mechanism is to make the view tag one (or more) byte(s) of the x-coordinate of the point r*V, or one (or more) byte (s) of the hash(r*V). Note that this hash(r*V) does not need to be in the finite field F_p.

In Curvy, the view tag consists of two bytes of the hash(r*V), so that the receiver only needs 1/65536 of the time to check the full address.

Implementation results

Since it is very important from the point of view of the users of the protocol that the transaction is executed quickly, we wanted to create a protocol that meets the needs of the users. For this reason, it was important to optimize the most sensitive part (which takes the longest), namely the search - the calculation of the new stealth address by the recipient of the transaction.

The figure below compares the search times of the ephemeral public key registry for different numbers of announcements (5000, 10000, 20000, 40000 and 80000) of Curvy Protocol (with pairing-friendly curve bn254 and optimal Ate pairing) and the implementation of DKSAP. The values of the private keys and the size of the view tag (5.5 bytes) from DKSAP were used.

Considering that Curvy uses a very expensive operation, namely elliptic curve pairing, becomes unclear how the results obtained may be almost 5 times better compared to DKSAP.

The answer lies in the use of the gnark-crypto library and the optimizations that have been made. Some of the optimizations we made (the reader can find more about this in our paper) can be used to optimize DKSAP, others cannot. The peculiarity is that the hash of the shared secret is not used to calculate the address in the Curvy protocol, but only for the view tag. Therefore, we can also use two bytes of the hash of the shared secret as the view tag, while using the same view tag would compromise the security of DKSAP. Note that in the Curvy protocol, we can also use the entire hash of the shared secret for the view tag without compromising security of the user.

Conclusion 

In this blog, we examine how Curvy works. We covered two main directions of research:

• Analysis of the Curvy protocol;
• Compare results with DKSAP.

We hope you liked our short blog about Curvy protocol .🚀 This research was carried out with the help of a grant from the ETH Foundation.