## Untraceable Transactions

In this section we propose a scheme of fully anonymous transactions satisfying both untraceability and unlinkability conditions. An important feature of our solution is its autonomy: the sender is not required to cooperate with other users or a trusted third party to make his transactions; hence each participant produces a cover traffic independently.

Our scheme relies on the cryptographic primitive called a group signature. First presented by D. Chaum and E. van Heyst, it allows a user to sign his message on behalf of the group. After signing the message the user provides (for verification purposes) not his own single public

key, but the keys of all the users of his group. A verifier is convinced that the real signer is a member of the group, but cannot exclusively identify the signer.

The original protocol required a trusted third party (called the Group Manager), and he was the only one who could trace the signer. The next version called a ring signature, introduced by Rivest et al., was an autonomous scheme without Group Manager and anonymity revocation. Various modifications of this scheme appeared later: linkable ring signature allowed to determine if two signatures were produced by the same group member, traceable ring signature limited excessive anonymity by providing possibility to trace the signer of two messages with respect to the same metainformation (or “tag”).

A similar cryptographic construction is also known as a ad-hoc group signature. It emphasizes the arbitrary group formation, whereas group/ring signature schemes rather imply a fixed set of members. For the most part, our solution is based on the work “Traceable ring signature” by E. Fujisaki and K. Suzuki. In order to distinguish the original algorithm and our modification we will call the latter a one-time ring signature, stressing the user’s capability to produce only one valid signature under his private key. We weakened the traceability property and kept the linkability only to provide one-timeness: the public key may appear in many foreign verifying sets and the private key can be used for generating a unique anonymous signature. In case of a double spend attempt these two signatures will be linked together, but revealing the signer is not necessary for our purposes.

## Elliptic curve parameters

As our base signature algorithm we chose to use the fast scheme EdDSA, which is developed and implemented by D.J. Bernstein et al. Like Bitcoin’s ECDSA it is based on the elliptic curve discrete logarithm problem, so our scheme could also be applied to Bitcoin in future.

Common parameters are:

q: a prime number; q = 2255 − 19;

d: an element of Fq; d = −121665/121666;

E: an elliptic curve equation; −x2 + y2 = 1 + dx2y2;

G: a base point; G = (x, −4/5);

l: a prime order of the base point; l = 2252 + 27742317777372353535851937790883648493; Hs: a cryptographic hash function {0,1}∗ → Fq;

Hp: a deterministic hash function E(Fq) → E(Fq).

## Terminology

Enhanced privacy requires a new terminology which should not be confused with Bitcoin entities.

- private ec-key is a standard elliptic curve private key: a number a ∈ [1, l − 1];
- public ec-key is a standard elliptic curve public key: a point A = aG;
- one-time keypair is a pair of private and public ec-keys;
- private user key is a pair (a, b) of two different private ec-keys;
- tracking key is a pair (a, B) of private and public ec-key (where B = bG and a = b);
- public user key is a pair (A, B) of two public ec-keys derived from (a, b);
- standard address is a representation of a public user key given into human friendly string with error correction;
- truncated address is a representation of the second half (point B) of a public user key given into human friendly string with error correction.

The transaction structure remains similar to the structure in Bitcoin: every user can choose several independent incoming payments (transactions outputs), sign them with the corresponding private keys and send them to different destinations.

Contrary to Bitcoin’s model, where a user possesses unique private and public key, in the proposed model a sender generates a one-time public key based on the recipient’s address and some random data. In this sense, an incoming transaction for the same recipient is sent to a one-time public key (not directly to a unique address) and only the recipient can recover the corresponding private part to redeem his funds (using his unique private key). The recipient can spend the funds using a ring signature, keeping his ownership and actual spending anonymous. The details of the protocol are explained in the next subsections.

## Unlinkable payments

Classic Bitcoin addresses, once being published, become unambiguous identifier for incoming payments, linking them together and tying to the recipient’s pseudonyms. If someone wants to receive an “untied” transaction, he should convey his address to the sender by a private channel. If he wants to receive different transactions which cannot be proven to belong to the same owner he should generate all the different addresses and never publish them in his own pseudonym.

Our solution allows a user to publish a single address and receive unconditional unlinkable payments. The destination of each output (by default) is a public key, derived from recipient’s address and sender’s random data. The main advantage against Bitcoin is that every destination key is unique by default (unless the sender uses the same data for each of his transactions to the same recipient). Hence, there is no such issue as “address reuse” by design and no observer can determine if any transactions were sent to a specific address or link two addresses together.

First, the sender performs a Diffie-Hellman exchange to get a shared secret from his data and half of the recipient’s address. Then he computes a one-time destination key, using the shared secret and the second half of the address. Two different ec-keys are required from the recipient for these two steps, so a standard Dynex address is nearly twice as large as a Bitcoin wallet address. The receiver also performs a Diffie-Hellman exchange to recover the corresponding secret key.

A standard transaction sequence goes as follows:

- Alice wants to send a payment to Bob, who has published his standard address. She unpacks the address and gets Bob’s public key (A, B).
- Alice generates a random r ∈ [1,l−1] and computes a one-time public key P = Hs(rA)G+ B.
- Alice uses P as a destination key for the output and also packs value R = rG (as a part of the Diffie-Hellman exchange) somewhere into the transaction. Note that she can create other outputs with unique public keys: different recipients’ keys (Ai , Bi ) imply different Pi even with the same r.
- Alice sends the transaction.
- Bob checks every passing transaction with his private key (a,b), and computes P′ = Hs(aR)G + B. If Alice’s transaction for with Bob as the recipient was among them, thenaR=arG=rAandP′ =P.
- Bob can recover the corresponding one-time private key: x = Hs(aR) + b, so as P = xG. He can spend this output at any time by signing a transaction with x.

As a result Bob gets incoming payments, associated with one-time public keys which are unlinkable for a spectator. Some additional notes:

- When Bob “recognizes” his transactions (see step 5) he practically uses only half of his private information: (a,B). This pair, also known as the tracking key, can be passed to a third party (Carol). Bob can delegate her the processing of new transactions. Bob doesn’t need to explicitly trust Carol, because she can’t recover the one-time secret key p without Bob’s full private key (a, b). This approach is useful when Bob lacks bandwidth or computation power (smartphones, hardware wallets etc.).
- In case Alice wants to prove she sent a transaction to Bob’s address she can either disclose r or use any kind of zero-knowledge protocol to prove she knows r (for example by signing the transaction with r).
- If Bob wants to have an audit compatible address where all incoming transaction are linkable, he can either publish his tracking key or use a truncated address. That address represent only one public ec-key B, and the remaining part required by the protocol is derived from it as follows: a = Hs(B) and A = Hs(B)G. In both cases every person is able to “recognize” all of Bob’s incoming transaction, but, of course, none can spend the funds enclosed within them without the secret key b.

## One-time ring signatures

A protocol based on one-time ring signatures allows users to achieve unconditional unlinkability. Unfortunately, ordinary types of cryptographic signatures permit to trace transactions to their respective senders and receivers. Our solution to this deficiency lies in using a different signature type than those currently used in electronic cash systems.

We will first provide a general description of our algorithm with no explicit reference to electronic cash.

A one-time ring signature contains four algorithms: (GEN, SIG, VER, LNK):

GEN: takes public parameters and outputs an ec-pair (P,x) and a public key I.

SIG: takes a message m, a set S′ of public keys {Pi}i=s, a pair (Ps, xs) and outputs a signature σ and a set S = S′ ∪ {Ps}.

VER: takes a message m, a set S, a signature σ and outputs “true” or “false”. LNK: takes a set I = {Ii}, a signature σ and outputs “linked” or “indep”.

The idea behind the protocol is fairly simple: a user produces a signature which can be checked by a set of public keys rather than a unique public key. The identity of the signer is indistinguishable from the other users whose public keys are in the set until the owner produces a second signature using the same keypair.

GEN: The signer picks a random secret key x ∈ [1, l − 1] and computes the corresponding public key P = xG. Additionally he computes another public key I = xHp(P) which we will call the “key image”.

SIG: The signer generates a one-time ring signature with a non-interactive zero-knowledge proof using the techniques from [21]. He selects a random subset S′ of n from the other users’ public keys Pi, his own keypair (x,P) and key image I. Let 0 ≤ s ≤ n be signer’s secret index in S (so that his public key is Ps).

He picks a random {qi | i = 0…n} and {wi | i = 0…n,i = s} from (1…l) and applies transformations.

VER: The verifier checks the signature by applying the inverse transformations. If this equality is correct, the verifier runs the algorithm LNK. Otherwise the verifier rejects the signature.

LNK: The verifier checks if I has been used in past signatures (these values are stored in the set I). Multiple uses imply that two signatures were produced under the same secret key. The meaning of the protocol: by applying L-transformations the signer proves that he knows such x that at least one Pi = xG. To make this proof non-repeatable we introduce the key image as I = xHp(P). The signer uses the same coefficients (ri,ci) to prove almost the same statement:

he knows such x that at least one Hp(Pi) = I · x−1. If the mapping x → I is an injection:

1. Nobody can recover the public key from the key image and identify the signer;

2. The signer cannot make two signatures with different I’s and the same x.

## A Standard Dynex transaction

By combining both methods (unlinkable public keys and untraceable ring signature) Bob achieves new level of privacy in comparison with the original Bitcoin scheme. It requires him to store only one private key (a, b) and publish (A, B) to start receiving and sending anonymous transactions. While validating each transaction Bob additionally performs only two elliptic curve multi- plications and one addition per output to check if a transaction belongs to him. For his every output Bob recovers a one-time keypair (pi,Pi) and stores it in his wallet. Any inputs can be circumstantially proved to have the same owner only if they appear in a single transaction. In fact this relationship is much harder to establish due to the one-time ring signature. With a ring signature Bob can effectively hide every input among somebody else’s; all possible spenders will be equiprobable, even the previous owner (Alice) has no more information than any observer. When signing his transaction Bob specifies n foreign outputs with the same amount as his output, mixing all of them without the participation of other users. Bob himself (as well as anybody else) does not know if any of these payments have been spent: an output can be used in thousands of signatures as an ambiguity factor and never as a target of hiding. The double spend check occurs in the LNK phase when checking against the used key images set. Bob can choose the ambiguity degree on his own: n = 1 means that the probability he has spent the output is 50% probability, n = 99 gives 1%. The size of the resulting signature increases linearly as O(n + 1), so the improved anonymity costs to Bob extra transaction fees. He also can set n = 0 and make his ring signature to consist of only one element, however this will instantly reveal him as a spender.

Reference: “Crypto Note v 2.0”; unknown author under the pseudonym Nicolas van Saberhagen; 2013