This is a continuation for the previous post.

Let’s forget for a while about the space efficiency and build a truly anonymous scheme based on the Variant 2 using Hp(P).

The stealth address will contain two parts. For the first part let’s revert to the original Cryptonote formula. For the second part the formula from the Variant 2 is used.

The scheme, Variant 3, is below:

Wallet:
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:
Address pair: (P=Hs(r*A)*G+B, T=Hs(r*D)*D)
Address private key pair: (x=Hs(a*R)+b, t=Hs(d*R)*d)
Key image pair: (I=x*Hp(P), Ï=Hs(d*R)*d*Hp(P))
Sender hides his stealth (P, T) among n-1 other address pairs:
s <-random
{(Pi, Ti) | i=1,…,n}, where (Ps, Ts)=(P, T)
{(qi, ki) | i=1,…,n}
and {wi | i=1,…,n, i≠s} <-random
I=x*Hp(P), where x=Hs(a*R)+b
Ï=t*
Hp(P)
, where t=Hs(d*R)*d
Li= qi*G , for i=s
qi*G +wi*Pi
, for all i≠s
Ri= qi*Hp(Ps)
, for i=s
qi*Hp(Pi) +wi*I
, for all i≠s
Mi= ki*G
, for i=s
ki*G +wi*Ti
, for all i≠s
Ni= ki*Hp(Ps)
, for i=s
ki*Hp(Pi) +wi*Ï
, for all i≠s
c=Hs(m, L1,…,Ln, R1,…,Rn, M1,…,Mn, N1,…,Nn, I, Ï, P1,…,Pn, T1,…,Tn)ci= wi , for all i≠s
c−sum(ci, for all i≠s)
, for i=s
ri= qi , for all i≠s
qi−cs*x
, for i=s
zi= ki
, for all i≠s
ki−cs*t
, for i=s
signature=(I, Ï, c1,…,cn, r1,…,rn, z1,…,zn)Public verifier checks the signature:
L’i= ri*G +ci*Pi , for all i
R’i= ri*Hp(Pi) +ci*I
, for all i
M’i= zi*G +ci*Ti
, for all i
N’i= zi*Hp(Pi) +ci*Ï
, for all i
c'=Hs(m, L'1,…,L'n, R'1,…,R'n, M'1,…,M'n, N'1,…,N'n, I, Ï, P1,…,Pn, T1,…,Tn)sum(ci, for all i)?=c'Knowing the incoming tracking key (a, B) for Bob's wallet (A, B, D) Carol can check if tx output (P, T) is sent to Bob:
P?=Hs(a*R)*G+B, where R is taken from the tx
Knowing Bob's wallet balance tracking key (a, B, d) an Auditor can check if another tx output is spent by Bob:
Ï?=t*Hp(P), where t=Hs(d*R)*d,
Ï is the second part of the tx key image,
(P, T) is one of the tx inputs,
R is taken from a tx that outputs (P, T)

Informal explanation for the scheme

Here we have the original Cryptonote scheme together with the additional key image Ï and the corresponding M and N series of arguments to the c hash.

The role for the original Cryptonote part is to prove that there is some index s for the ring, such that there is some x known to the sender (Bob), such that Ps=x*G and I=x*Hp(Ps). In other words, to prove that Bob knows key x for some of the inputs and he really spends that input by publishing its key image I.

The role for the additional part is to prove that for the same index s Bob knows some t, such that Ts=t*G, and to publish the Ï=t*Hp(Ps).

Wallet balance audit use case

The Auditor knows t’s constructed from d that he knows. Hence, scanning the blockchain, he selects those output (P, T)’s that he can reconstruct T private key for.

Next, he looks at the key images (I, Ï)’s and selects those that he can reconstruct Ï for. Namely, for all selected (P, T)’s he knows t’s and checks:

Ï?=t*Hp(P)

If this equality holds, then Ï is linked to (P, T). That is, the Auditor links an output sent to Bob with a signature spending that output.

Thus, the Auditor sees all Bob’s spend-auditable incomings and outgoings.

Spend-auditable coins

The ‘spend-auditable’ means here that Alice is free to put anything to T when she sends an output to Bob. By default she puts T=Hs(r*D)*D, that means the coin is spend-auditable.

However, she may put anything, e.g. T=Hs(r*D’)*D’ where D’=d’*G, such that d’ is known to Bob and is not known to the Auditor. This way Bob is still able to spend this coin, however the Auditor won’t see that.

Anyway, this doesn’t break the auditability in general, as only sender (Alice) has this option. Once Alice decided the coin to be spend-auditable, Bob can’t change that.

In other words, this option, that Alice has, is nothing. The same manner she is able to send the coin to another Bob’s wallet, that is not under the audit.

Anonymity

The anonymity is proven the same way the original Cryptonote anonymity is, the both (P, I) and (T, Ï) parts of the scheme are obfuscated by Hp(P).

Can the intersection of the parts leak anonymity? That is, is Alice able to link Bob’s outgoing transactions with Bob by looking at the signatures containing (I, Ï)? This would be possible if she know a private key for linear combination of P and T that she composed when she sent a transaction to Bob. However, she doesn’t.

Is it possible to cheat with Ps, Ty?

Everything works when Bob knows private keys for (Ps, Ts) in the ring.

Suppose, Bob also knows private keys for another pair (Py, Ty) in the ring. Is he able to cheat by providing the second part of key image calculated for that, second, pair? E.g., like on the following sketch:

I=xs*Hp(Ps)
Ï=ty*Hp(Py)
Li= qi*G , for i=s, i=y
qi*G +wi*Pi
, for all i≠s, i≠y
Ri= qi*Hp(Pi)
, for i=s, i=y
qi*Hp(Pi) +wi*I
, for all i≠s, i≠y
Mi= ki*G
, for i=s, i=y
ki*G +wi*Ti
, for all i≠s, i≠y
Ni= ki*Hp(Pi)
, for i=s, i=y
ki*Hp(Pi) +wi*Ï
, for all i≠s, i≠y
c=Hs(m, L1,…,Ln, R1,…,Rn, M1,…,Mn, N1,…,Nn, I, Ï, P1,…,Pn, T1,…,Tn)ci= wi , for all i≠s, i≠y
(c−sum(ci, for all i≠s))/3 ,
for i=s
(c−sum(ci, for all i≠s))*2/3 ,
for i=y
ri= qi , for all i≠s, i≠y
qi−cs*xs
, for i=s
qi−cy*xs
, for i=y
zi= ki , for all i≠s, i≠y
ki−cs*ty
, for i=s
ki−cy*ty
, for i=y

Here we have two variable coefficients dependent of the c (hash for the left-side): cs and cy.

However, using the common formulas the verifier won’t get the same Ry and Ns due to Hp(Ps)!=Hp(Py) :

L’i= ri*G      +ci*Pi  , for all i
R’i= ri*Hp(Pi) +ci*I
, for all i
--- R'y=qy*Hp(Py)-cy*xs*Hp(Py)+cy*xs*Hp(Ps) != Ry=qy*Hp(Py)

M’i= zi*G +ci*Ti
, for all i
N’i= zi*Hp(Pi) +ci*Ï
, for all i
--- N's=ks*Hp(Ps)-cs*ty*Hp(Ps)+cs*ty*Hp(Py) != Ns=ks*Hp(Ps)

Thus, no, it’s not possible to cheat this way.

Summary for the Variant 3

The wallets are auditable at the cost of

  • P(P, T), plus one point for each output
  • I(I, Ï), plus one point for each key image
  • (I, c1,…,cn, r1,…,rn)→(I, Ï, c1,…,cn, r1,…,rn, z1,…,zn), plus one point and plus n integers for each transaction signature, where n is the decoy count.

Continued in the next post.

Mathematician, Software Engineer.