Cryptonote auditability. How to append the wallet balance audit.

Some time ago I read the original Cryptonote whitepaper. The scheme looks simple and proven secure up to some level. However, interestingly, it lacks an option for spending audit.

Namely, there is an option called ‘tracking key’ that allows to audit incomings. At the same time, there is no symmetric option allowing to audit outgoings as well.

A question I asked myself was: is it possible to modify the original Cryptonote protocol in some way to append the aforementioned outgoings audit or, at least, to append a simultaneous incomings plus outgoings (that is, the wallet balance) audit?

Best case, without inflating the protocol data stored in the blockchain, and, in any case, without compromising security.

I have checked if a solution already exists. It looks like the Bytecoin system has some solution already implemented, however it seems to be there is no algorithm disclosure on paper, everything in the code, haven’t looked inside yet.

Anyway, here is my answer to the question: yes, it’s possible. I have an idea, two variants, on how to construct a reliable wallet balance audit for the original Cryptonote protocol.

After playing with the Cryptonote cryptography, both variants seem not intricate, although they require to modify certain things in the protocol core. The understanding of why they don’t leak security is a bit more complex, it’s discussed afterward.

There are several extensions for the Cryptonote protocol in the contemporary cryptocurrency systems. To keep things simple, I refer to the original Cryptonote paper only. This doesn’t exclude the possibility for applying the existing extensions to the modified version of the protocol.

Note, both variants below are drafts, the idea expressed as simple as possible.

In short words,

- Bob has a wallet with private key
**(a, b)**, public key**(A=a*G, B=b*G)**and tracking key**(a, B)**. - Alice generates a random
**r**and sends a transaction to stealth address**P=Hs(r*A)*G+B**associated with Bob’s wallet. She also packs**R=r*G**into the transaction. Only Bob, knowing**(a, b)**, can compute**x=Hs(a*R)+b**, such that**P=x*G**. - Bob sends his transaction from the stealth address
**P**to Charlie’s wallet the same way as Alice did to Bob. Substantial detail here is how he hides**P**among the n-1 other user stealth addresses:

Pick n-1 other user addresses, picks a arbitrary

sand form a set , wherePs=PPick random

andCalculate:

I=x*Hp(P), wherex=Hs(a*R)+bas above

Li=qi*G, fori=s

Li=qi*G+wi*P, forall i≠s

Ri=qi*Hp(P), fori=s

Ri=qi*Hp(Pi)+wi*I, forall i≠sCalculate

c=Hs(m, L1,…,Ln, R1,…,Rn), wheremis the transaction public message containing information about the setFinally, compute:

ci=wi, forall i≠s

ci=c-sum(ci, for all i≠s), fori=s

ri=qi, forall i≠s

ri=qi−cs*x, fori=sPublish the transaction

signature=(I, c1,…,cn, r1,…,rn)

- Any public verifier can check the transaction signature the following way:

Build:

L’i=ri*G+ci*Pi, forall i

R’i=ri*Hp(Pi)+ci*I, forall iChecks if

sum(ci, for all i)?=Hs(m, L’1,…,L’n, R’1,…,R’n).

- If the equality is correct, then the verifier is convinced about that, that the sender (Bob, however the verifier doesn’t know that) knows
**x**, such that**P=x*G**and, simultaneously,**I=x*Hp(P)**for certain unknown**P**in the set - Also, the verifier checks if
**I**(called ‘key image’) is not previously used in the blockchain, thus preventing double-spends. - Carol, who knows the tracking key
**(a, B)**, can associate**P**with Bob by checking**P?=Hs(a*R)*G+B**, seeing all the Bob’s wallet incoming transactions this way.

Some years ago an attack to this protocol using ed25519 low order points was revealed and mitigated. Some additional checks were added. This doesn’t affect the auditability.

Essential is that the core protocol idea doesn’t require any specific curve. What is required: a group of large prime order and no feasible pairings for the curve.

Also, according to the whitepaper, **Hp** function is not required to be an ideal cryptographic hash function, pseudo-random only. The necessity of **Hp** is discussed in the whitepaper by an example: if **Hp(_)=G2**, where **G2** is a const point (another generator) on the curve, then Alice, after sending some transactions to Bob, is able to link some of the future Bob’s transactions with him, that she is not authorized to do.

Let’s define the *wallet private key *as **(a, b, d)**. The meaning for **a** and **b** is the same as for the original protocol.

Let’s define the *wallet public key* as **(A=a*G, B=b*G, D=d*G)**.

Let’s rename **(a, B)** , to be called *incomings tracking key*, as opposed to simply *tracking key* in the original protocol.

Let’s define the *wallet balance tracking key* as **(a, B, d, B2=b*B, Proof of B2)**. The **B2** is a point corresponding to the square of **b**. The **Proof of B2** is a non-interactive proof for the fact that **B2** actually equals to **b*b*G**, it’s easy to construct this proof.

- Stealth address modification:

**P=Hs(r*A)*D+B** from now

- Bob’s actions and key image modifications:

**x=Hs(a*R)*d+b** , such that **P=x*G**

**I=x*Hs(P)*P** from now

**c=Hs(m, L1,…,Ln, R1,…,Rn, I, P1,…,Pn)** from now. Note, I and all **Pi’s** are moved under the hash compared to the original paper.

**signature=(I, c1,…,cn, r1,…,rn)** remains the same

- Verifier actions modification:

**R’i=ri*Hs(Pi)*Pi+ci*I**

- Carol’s actions modification:

**P?=Hs(a*R)*D+B**

- New functionality: an Auditor, who knows the
*wallet balance tracking key*, can:

Track all Bob’s incoming transactions by acting as Carol does. For convenience, let’s suppose the Auditor writes down the pairs **(P, R)** for each found Bob’s incoming transaction.

Track all Bob’s outgoing transactions by checking the following equality for all newly appended **I**’s:

**I?=Hs(P)*(k*k*G+2*k*B+B2)**, where **k=Hs(a*R)*d**

If the equality is correct for some **(P, R)**, then the transaction spends **P** and belongs to Bob.

Thus, the Auditor can track the Bob’s wallet balance by seeing all Bob’s incoming and outgoing transactions.

Note, **Hp** is not used anymore. No additional data is appended to the blockchain.

Private key: **(a, b, d)**

Public key: **(A=a*G, B=b*G, D=d*G)**

Incomings tracking key: **(a, B)**

Wallet balance tracking key: **(a, B, d)**

- Stealth address modification:

The address is a pair **(P, T)**, where **P=Hs(r*A)*D+B**, same as in the Variant1, **T=Hs(r*A, r*D)*D**. Let’s call **T** *‘key image base’*

- Bob’s actions and key image modifications:

**x=Hs(a*R)*d+b** , such that **P=x*G**

**I=x*T**

**c=Hs(m, L1,…,Ln, R1,…,Rn, I, P1,…,Pn, T1,…,Tn)**

**signature=(I, c1,…,cn, r1,…,rn)**

- Verifier actions modification:

**R’i=ri*T+ci*I**

- Carol’s actions modification:

**P?=Hs(a*R)*D+B**

- The Auditor can track Bob’s wallet auditable balance:

Track all Bob’s incoming transactions by acting as Carol does. Also, for each found Bob’s P he can verify:

**T?=Hs(a*R, d*R)*D**.

If this equality is not correct, then this incoming transaction is still considered as valid, however spend-untraceable. That means, that later Bob can spend this **(P, T) **anonymously. Otherwise, if the equality holds, the incoming transaction is considered spend-auditable.

Let’s suppose, for convenience, that the Auditor writes down **(P, T, R)** for all found Bob’s spend-auditable transactions.

He can track all Bob’s outgoing transactions related to the incoming spend-auditable ones. He checks the following equality for all newly appended I’s. If the equality is correct for some **R**, then this is Bob’s outgoing transaction:

**I?=t*P** , where **t=Hs(a*R, d*R)*d**

In this variant the only additional data placed to the blockchain are **T**’s.

The wallets are auditable, however finally senders decide if the funds they send to receivers become auditable in the receiver wallets. This doesn’t violate auditability: no one can hide funds sent to him in transactions with correct T.

To be continued, I hope I will find time to discuss security…

Published at Sun, 10 Nov 2019 20:08:04 +0000

{flickr|100|campaign}