Cryptonote auditability. How to append a wallet balance audit.

6 min readNov 10, 2019

Preface

Recently I read the original Cryptonote whitepaper. The scheme looks simple and proven secure up to certain high 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 to append the aforementioned outgoings audit or, at least, to append a simultaneous incomings plus outgoings (that is, the wallet balance) audit in some way?

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

From the beginning, I had two simple ideas about how to construct the balance audit for the original Cryptonote protocol. However, having shared the ideas, thanks for reviewers, I immediately got a feedback about possible anonymity issues.

After that, I understood that more elaborated variants can be here, and maybe it would make sense to try to find them.

So, in this series of posts I will look for a solution by gradually proposing new variants, discussing correctness, involving more and more math and keeping accent on informal explanations.

Update 2020–01–27:

As this series has got longer than I expected, I put a table of content with remarks below.

If you are an experienced cryptographer, then you may skip the first posts or start reading right from the fifth one or from the conclusion.

If you are curious about the internals of the Cryptonote protocol, then probably the description of my first attempts could be of interest to you.

This post: Preface, the Cryptonote protocol recap. The first two variants: Variant 1 and 2, they are rather naive and have an issue with anonymity discussed in the second post.
Second post: The anonymity issue is discussed. A semi-formal approach for finding issues of that kind and necessity of Hp() hash are shown.
Third post: A scheme for the auditable wallets: correct, however, not memory efficient.
Fourth post: A memory efficient scheme for the auditable wallets that contains a multi-signature-like formula (batch-Schnorr) under the hood. Discussing its security and possibility of Wagner’s attack.
Fifth post: A more memory efficient scheme for the auditable wallets. A generalized scheme for key vectors with signature size O(n), where n is the decoy count.
Sixth post: About the point-to-point hash Hp.
Seventh post: Conclusion, a practical method for adding this type of audit.

Update 2021–03–21: It appears the scheme described in the Fifth post is very similar to a scheme named CLSAG, that was already invented and published a half of a year earlier by Brandon Goodell, Sarang Noether, and Arthur Blue.

Original Cryptonote protocol recap

In brief,

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, pick an arbitrary s and form a set {Pi | i=1,…,n}, where Ps=P
Pick random {qi | i=1,…,n} and {wi | i=1,…,n, i≠s}Calculate:
I=x*Hp(P), where x=Hs(a*R)+b as aboveLi=qi*G, for i=s
Li=qi*G+wi*P, for all i≠sRi=qi*Hp(P), for i=s
Ri=qi*Hp(Pi)+wi*I, for all i≠sCalculate c=Hs(m, L1,…,Ln, R1,…,Rn), where m is the transaction public message containing information about the {Pi} setFinally, compute:
ci=wi, for all i≠s
ci=c-sum(ci, for all i≠s), for i=sri=qi, for all i≠s
ri=qi−cs*x, for i=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, for all i
R’i=ri*Hp(Pi)+ci*I, for all iCheck 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 {Pi}
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.

The core protocol idea doesn’t require any specific curve. What is required: a group of large prime order and no 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 few transactions to Bob, is able to link some of the future Bob’s transactions with him, that she is not authorized to do.

That’s about the original protocol.

Next, the first trials to modify the protocol:

Variant 1, with a hidden anonymity issue

Wallet modification:

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, D) 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 it.

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*P from now

Ri=qi*P, for i=s

Ri=qi*Pi+wi*I, for all i≠s

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’s actions modification:

R’i=ri*Pi+ci*I

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

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 transaction I’s:

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

If the equality is correct for some Bob’s incoming (P, R), then the new transaction spends P and hence 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. No additional data is appended to the blockchain.

Variant 2, different, however with the same anonymity issue

Wallet modification:

Private key: (a, b, d)

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

Incomings tracking key: (a, B, D)

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 for the first variant) and T=Hs(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

Ri=qi*T, for i=s

Ri=qi*Ti+wi*I, for all i≠s

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

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

Verifier’s actions modification:

R’i=ri*Ti+ci*I

sum(ci, for all i)?=Hs(m, L’1,…,L’n, R’1,…,R’n, I, P1,…,Pn, T1,…,Tn)

Carol’s actions modification:

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

The Auditor can track Bob’s wallet auditable balance:

Namely, he tracks all Bob’s incoming transactions by acting as Carol does. Also, for each found Bob’s (P, T) he can verify:

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

If this equality doesn’t hold, then the 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 is correct, the incoming transaction is considered as 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 by checking 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(d*R)*d

What’s in the Variant 1 and 2

The wallets are auditable, Auditor can see the incoming and outgoing transactions.

In the Variant 2, the funds sent by senders to a recipient’s wallet are auditable by default. However, the senders may opt to make them spend-untraceable in the recipient’s wallet. This doesn’t violate auditability: no one can hide auditable funds provided to him.

The Variant 1 puts no additional data to the blockchain, whereas the Variant 2 puts an additional point T for each stealth output P.

No one except for Auditor and wallet owner can directly link an outgoing transaction with the wallet. This is seen from the formulas above. However, the question about if there is an indirect way for linking is still open.

Continued in the following post.