Discussion for the auditable wallets Variant 1 and 2
This is a continuation for my previous post.
The Variant 1 recap
Wallet:
private key: (a, b, d)
public key: (A=a*G, B=b*G, D=d*G)
incoming tracking key: (a, B, D)
balance tracking key: (a, B, d, B2=b*B, Proof of B2).
Stealth address:
address: P=Hs(r*A)*D+B
address private key: x=Hs(a*R)*d+b
key image: I=x*P
Sender hides his stealth P among n-1 other addresses:
s <-random
{Pi | i=1,…,n}, where Ps=P
{qi | i=1,…,n} and {wi | i=1,…,n, i≠s} <-randomI=x*P, where x=Hs(a*R)*d+bLi= qi*G, for i=s
qi*G+wi*P, for all i≠sRi= qi*P, for i=s
qi*Pi+wi*I, for all i≠sc=Hs(m, L1,…,Ln, R1,…,Rn, I, P1,…,Pn)ci= wi, for all i≠s
c−sum(ci, for all i≠s), for i=sri= qi, for all i≠s
qi−cs*x, for i=ssignature=(I, c1,…,cn, r1,…,rn)
Public verifier checks the signature:
L’i=ri*G+ci*Pi, for all i
R’i=ri*Pi+ci*I, for all isum(ci, for all i)?=Hs(m, L’1,…,L’n, R’1,…,R’n, I, P1,…,Pn)
Knowing the incoming tracking key (a, B, D) for Bob's wallet (A, B, D) Carol can check if tx output P belongs to Bob:
P?=Hs(a*R)*D+B, where R is taken from the txKnowing Bob's wallet balance tracking key (a, B, d, B2, Proof of B2) an Auditor can check if tx input P belongs to Bob:
I?=k*k*G+2*k*B+B2,
where k=Hs(a*R)*d,
I is the tx key image,
R is taken from a transaction where P is the output
Wallet audit use cases
Incoming transaction audit use case
This case doesn’t differ a lot from the original Cryptonote incoming transaction audit case.
Carol, knowing Bob’s wallet incoming tracking key, sees all his wallet incoming tx outputs.
Namely, she scans the blockchain transaction outputs and checks the
P?=Hs(a*R)*D+B equality.
The only difference from the Cryptonote here is that D is substituted for G.
Balance audit use case
Bob discloses his wallet balance tracking key to Auditor. From that moment onwards, the Auditor can see Bob’s wallet balance. Namely, he sees all past and all future incomings and spendings for the Bob’s wallet.
As the wallet balance tracking key completely contains the incoming tracking key, the Auditor sees all incomings the same way as Carol does.
To see the spendings, the Auditor scans the blockchain key images and checks the
I?=k*k*G+2*k*B+B2 equality.
Informal explanation for the scheme
In general, the signature scheme used in the original Cryptonote paper is a NIZK proof for the following statement: given two public arrays of points: {Xi}, {Yi} and two public generators: U1, U2, the signer knows certain hidden number x and index s, such that the following two equalities hold:
Xs=x*U1 and Ys=(x^-1)*U2
For the original Cryptonote:
{Xi}={Pi}, {Yi}={Hp(Pi)},
U1=G, U2=I, where I=x*Hp(P) and P=Ps=x*U1For the Variant 1:
{Xi}={Pi}, {Yi}={Pi},
U1=G, U2=I, where I=x*P and P=Ps=x*U1
The key image I, in addition to making the proof non-repeatable, allows those who know the (a, d, B, B2) to link it with the corresponding stealth address by checking I?=k*k*G+2*k*B+B2.
In other words, this way the NIZK proof gets smth. like a backdoor for linking I to P, and the balance tracking key is the backdoor key.
In simpler words, there is two different routes for constructing I: as x*x*G and as k*k*G+2*k*B+B2. The first route requires to know (a, b, d), the second one requires to know (a, d, B, B2) only. Both yield the same I.
Anonymity primer
According to the Cryptonote paper, the Hp was introduced to prevent the following possibility of breaking anonymity by linking Bob’s transactions:
Suppose, I=x*G2, where G2 is another generator.Alice makes two transfers to Bob:
P1=Hs(r1*A)*G+B=x1*G
P2=Hs(r2*A)*G+B=x2*G
Now Alice knows p12=(x1-x2)=(Hs(r1*A)-Hs(r2*A))After that, when she finds two transaction key images I1 and I2 in the blockchain, such that (I1-I2)=(x1*G2-x2*G2)=p12*G2, she can conclude, that these two transactions definitely belong to Bob spending those her transfers.Hence, to make Bob's transactions unlinkable, the pseudo-random Hp(P) was substituted for G2 in I=x*G2:
(I1-I2)=(x1*G2-x2*G2) => (I1-I2)=(x1*Hp(P1)-x2*Hp(P2))≠p12*G2
With this, even knowing a key for some linear combination of Bob's stealth addresses, nobody except for Bob can link his transactions.
The Variant 1 doesn’t allow to link two key images this way. Really,
Alice makes two transfers to Bob:
P1=h1*D+B=x1*G ,where h1=Hs(r1*A)
P2=h2*D+B=x2*G ,where h2=Hs(r2*A)Suppose, she can calculate somehow the non-zero coefficients e1, e2 and a constant E, such that e1*I1+e2*I2=E for the corresponding key images.That means, that:
E=e1*x1*P1+e2*x2*P2
E=e1*(h1*h1*d*D+2*h1*d*B+b*B)+e2*(h2*h2*d*D+2*h2*d*B+b*B)
E=(e1*(h1*h1)+e2*(h2*h2))*d*D+2*(e1*h1+e2*h2)*d*B+(e1+e2)*b*BIn matrix form:
M = m11=h1*h1, m12=h2*h2
m21=h1 , m22=h2
m31=1 , m32=1
E=(M*(e1, e2).T)*(d*D, d*B, b*B).T ,where '.T' means transpositionThe V=(d*D, d*B, b*B) is a vector of fixed unknown points without any known (to Alice) linear relationship between them.
The M is a matrix of known elements.
The point E is known by supposition.
The (e1, e2) is a vector that Alice knows by supposition.It's easy to see, that for the pseudo-random h1 and h2 the only possibility for (e1, e2) to exist is:
E=0, M*(e1, e2).T=0
This implies (e1, e2) is zero, contradiction.Hence, it's not possible to link two key images.
Breaking anonymity using more key images
However, what’s about an arbitrary non-zero linear combination of key images, is it possible to turn it into a known point with some computable coefficients?
( For the anonymity investigation Alice is an adversary, as not being an Auditor she possesses maximum information about Bob’s transactions. )
Let’s perform an attack as above with the increased number of key images:
Definitions:
I=(I1, I2, ...) - a vector of key images, n is the length of I
e=(e1, e2, ...) - a vector of coefficients, length n
V=(d*D, d*B, b*B) - a basis vector V
M is a (3 x n) matrix of known elements, such that I=V*M.
E=0Equations:
0=I*e.T=(V*M)*e.T=V*(M*e.T)
0=M*e.TObviously, a non-zero e can be found for n > 3
Thus, it’s possible to link n key images with Bob’s wallet as soon as n is greater than the length of the basis V defined as a set of fixed linearly independent possibly unknown ‘basis points’, that each key image is represented in.
The linear independence is meant from the adversary’s point of view here. That is, for instance, the d*B and b*B are considered independent as Alice knows neither d nor b.
Anonymity for the Variant 1 and 2
For the Variant 1 the basis vector V=(d*D, d*B, b*B) is of length 3. Hence the Variant 1 scheme is not anonymous for the combinations of 4 and more key images.
For the Variant 2 the basis V=(d*D, d*B) is of length 2, hence the Variant 2 is not anonymous for the combinations of 3 and more key images.
Thoughts about how to make the key image schemes anonymous
Apparently, the larger the key image basis vector V the larger the lower boundary for the amount of linkable key images. So, the first option is to upgrade D to be a vector of different EC-points instead of a single point. Thus, the x*x*G will get a large number of summands and V will get larger. However, the scheme anonymity will still remain broken for the larger sets of key images.
The second option is Hp(P). As P varies for different key images, the V gets a variable point in it. As no one knows private key for Hp(P), the variable point can’t be decomposed to a linear combination of fixed points. Thus, the attack is impossible for key images in the form of some_unknown_coeff*Hp(P).
The third option is G2/x, where G2 is an independent generator, and x=b+h, where h can be known to Alice, whereas b is unknown and uniformly random. It seems to be it’s nor possible for Alice to distinguish a series of G2/(b+h1), G2/(b+h2), G2/(b+h3), … from a series of uniformly random points. Although, I haven’t thought a lot about this, just referring to the work of Y. Dodis and A. Yampolskiy “A Verifiable Random Function With Short Proofs and Keys” here.