Batch-Schnorr signature with LSAG. One more memory efficient approach to auditable wallets.

Update 2020–01–24: I renamed the ‘multi-signature formula’ to be ‘batch-Schnorr signature’ everywhere in this post. In essence, nothing has been changed except for the naming, the formula that I use resembles both the BN’s multi-signature and Gennaro’s et al. batch-Schnorr signature. As a single prover who proves knowledge of multiple private keys ‘in a batch’ is assumed below, the ‘batch-Schnorr’ looks more appropriate.

Update 2021–03–21: It appears the scheme I describe herein 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.

An approach that allows to anonymously prove knowledge of two private keys by adding one EC point to the Cryptonote signature was described in my previous post.

Now the signature size will be reduced using a method taken from J.K. Liu et al.’s paper “Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups” (LSAG). Update 2020–01–14: Better to say, a method invented in Abe, Ohkubo, Suzuki paper “1-out-of-n Signatures from a Variety of Keys” (AOS).

I will propose a scheme for auditable wallets with the reduced signature size together with a generalized scheme for arbitrary key vectors below.

After that, I will compare the generalized scheme with the MLSAG scheme described in the Monero Research Lab’s ‘Ring Confidential Transactions’ paper, Ch. 2.

LSAG idea recap (in fact, this is the AOS idea)

Reformulating a bit compared to the original LSAG paper: suppose, we have an initial ring that proves knowledge of x*G=P:

-------Prover:
Picks n-1 other public keys, picks an arbitrary s and composes a set {Pi | i=1,…,n}, where Ps=P
Picks random {qi | i=1,…,n} and {ci | i=1,…,n, i≠s}
Calculates:
Li=qi*G, for i=s
Li=qi*G+ci*P, for all i≠s
c=Hs(L1,…,Ln, P1,…,Pn)
Defines coefficient cs for i=s as:
cs=c-sum(ci, for all i≠s)
Defines:
ri=qi, for all i≠s
ri=qi−cs*x, for i=s
Publishes:
signature=(c1,…,cn, r1,…,rn)

--------Verifier: 
Builds:
L'i=ri*G+ci*P, for all i
c'=Hs(L'1,…,L'n, P1,…,Pn)
And checks:
c'?=sum(ci, for all i)

Then we can apply the LSAG (AOS) method to get rid of all ci coefficients except for one:

---------Prover:
Picks n-1 other public keys, picks an arbitrary s and composes a set {Pi | i=1,…,n}, where Ps=P
Picks random {qi | i=1,…,n}
Calculates initial value for variable L:
L=qs*G        (, for i=s)
Calculates in a loop:
for i=(s+1),…,n,1,…,s:
    ci=Hs(L, P1,…,Pn)
    L=qi*G+ci*Pi
Forgets about L and about all ci's except for c1 and cs.
Defines:
ri=qi        , for all i≠s
rs=qs−cs*x  (, for i=s)
Publishes:
signature=(c1, r1,…,rn)

--------Verifier: 
Calculates, keeping temporal results in variables L and c:
c=c1
L=None
for i=1,…,n:
    L=ri*G+c*P
    c=Hs(L, P1,…,Pn)
Forgets about L and keeps c from the last round of the cycle.
Checks:
c1?=c

As can be seen from the above, in the LSAG (AOS) method the prover iteratively generates random values for all ci’s by hashing the data from previous iterations. This allows him to skip transmitting ci’s to the verifier.

The only transmitted c1 together with ri’s and Pi’s determines the entire sequence of ci’s.

The same way and with the same coefficients the prover can anonymously prove statements like ‘I know x, such that x*G=P and simultaneously x*Hp(P)=I’.

A scheme for auditable wallets with reduced signature size

Combining two ideas, the batch-Schnorr and the LSAG (AOS), now I propose the following auditable scheme:

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:
Public address key pair: (P=Hs(r*A)*G+B, T=Hs(r*D)*D)
Private address 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 | i=1,…,n} <-random
I=x*Hp(P), where x=Hs(a*R)+b
Ï=t*Hp(P), where t=Hs(r*D)*d
Calculates initial values for the variables L and R:
L=qs*G            (, for i=s)
R=qs*Hp(P)        (, for i=s)
Calculates in a loop:
for i=(s+1),…,n,1,…,s:
    ci =Hs(L, R, I, Ï, P1,…,Pn, T1,…,Tn)
    ui =Hs(Pi, Ti, I, Ï, ci)
    L  =qi*G       +ci*Pi  +ui*Ti
    R  =qi*Hp(Pi)  +ci*I   +ui*Ï
Forgets about L, R, ui's and ci's except for c1, cs and us.
Defines:
ri=qi                , for all i≠s
rs=qs−cs*x−us*t     (, for i=s)
Publishes:
signature=(I, Ï, c1, r1,…,rn)

-------Public verifier:
Calculates, keeping temporal results in variables L, R, c and u:
c=c1
u=None
L=None
R=None
for i=1,…,n:
    u =Hs(Pi, Ti, I, Ï, c)
    L =ri*G       +c*Pi  +u*Ti
    R =ri*Hp(Pi)  +c*I   +u*Ï
    c =Hs(L, R, I, Ï, P1,…,Pn, T1,…,Tn)
Forgets about L, R. 
Keeps c from the last round of the cycle.
Checks:
c1?=c
If the equality above holds, then the verifier is convinced that the sender knows private key pair for one of (P, T)'s in the ring and simultaneously (I, Ï) is the key image pair for that (P, T).

------Incomings audit:
Knowing the incomings 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

------Auditor (balance audit):
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)

Thus, the set of n ci’s is reduced to one c1 in the signature. All the other features of the protocol are kept.

The scheme supports the wallet balance audit use case described in one of my earlier posts.

Summary for the auditable wallet scheme

The wallets are auditable, and the signature size compared to the original Cryptonote is reduced for the case if there are more than two decoys in the ring:

• 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, r1,…,rn), plus one point and minus n-1 integers for each signature, where n is the decoy count.

A generalized scheme for anonymous key vector NIZK proof

Suppose, we want to prove knowledge of key vector vec_x=(x1, …, xm), such that:

vec_P1=vec_x*G1, where vec_P1=(P11,…, P1m) is a vector of EC points 
                
Note: the ‘*’ operation propagates as: vec_x*G1=(x1*G1, …, xm*G1),
      for all i=1,…,m we can access P1i from vec_P1 as vec_P1[i]=P1i

In addition to that, suppose, we want to prove that vec_x is a key vector for the following k equalities:

vec_P1=vec_x*G1
vec_P2=vec_x*G2
   ...
vec_Pk=vec_x*Gk  , where each vec_Pi is a point vector of length m 
                   and each Gi is a point

And, suppose, we want to make the proof anonymous by hiding the pair of sets {vec_Pi} and {Gi} between n-1 other decoy pairs.

Let’s rewrite the sets {vec_Pi} and {Gi} as:

mx_P=(vec_P1, 
           …, 
      vec_Pk)
vec_G=(G1, …, Gk)
Note: for all i=1,…,k we can access 
  * row vec_Pi from the matrix mx_P as mx_P.rows[i]=vec_Pi 
  * and Gi from vec_G as vec_G[i]=Gi.
  Also, for all j=1,…,m we can access 
  * column as mx_P.columns[j], 
  j-th column contains all matrix entries whose private key is xj.

Now the k equalities above can be written in one line as:

mx_P=vec_G.T*vec_x 
Note: the mx_P is a matrix of shape kxm representing
  outer product of vec_G and vec_x.
  '.T' means transposition and '*' means matrix product,
  the vectors are taken as matrices with shapes kx1 and 1xm here.

Then we can use the following scheme, where the LSAG is combined with a batch-Schnorr style signature:

------Prover: 
Hides his tuple (mx_P, vec_G) among n-1 decoy tuples in a list M:
s <-random
M={(mx_Pi, vec_Gi) | i=1,…,n}, where (mx_Ps, vec_Gs)=(mx_P, vec_G)
Note: it's assumed that the list M is a public information, 
      so both Prover and Verifier know it ) 
{qi | i=1,…,n} <-random
Prover calculates initial values for the vector vec_L of length k:
vec_L=qs*vec_Gs            (, for i=s)
Initializes vec_C of length m:
vec_C={None | i=1,…,m}
The Prover calculates in a loop:
for i=(s+1),…,n,1,…,s:
    ci    =Hs(vec_L, M)
    for j=1,…,m:
        vec_C[j] =Hs(mx_Pi, vec_Gi, mx_Pi.columns[j], ci)
    for j=1,…,k:
        vec_L[j] =qi*vec_Gi[j] +dot(vec_C, mx_Pi.rows[j])
Note: dot(x, y) is vector dot product here.
Next, the Prover forgets about vec_L and about all ci's except for
c1 and keeps vec_C from the last round above (where i=s).
Defines:
ri=qi                          , for all i≠s
rs=qs−dot(vec_C, vec_x)       (, for i=s)
Publishes:
signature=(c1, r1,…,rn)

-------Verifier:
Calculates, keeping temporal results in variables vec_L, vec_C, c:
c=c1
vec_L={None | i=1,…,k}
vec_C={None | i=1,…,m}
for i=1,…,n:
    for j=1,…,m:
        vec_C[j] =Hs(mx_Pi, vec_Gi, mx_Pi.columns[j], c)
    for j=1,…,k:
        vec_L[j] =ri*vec_Gi[j] +dot(vec_C, mx_Pi.rows[j])
    c=Hs(vec_L, M)
Next, the Verifier forgets about vec_C, vec_L and 
keeps c from the last round of the cycle.
Checks:
c1?=c
If the equality holds, then the Verifier is convinced that the Prover knows vec_x, such that mx_P=vec_G.T*vec_x for some unknown tuple (mx_P, vec_G) in M.

Explanation for the generalized scheme

The scheme allows to prove compound (built of AND and OR series) statements like:

I know a private key vector (x1, ..., xm), such that for the publicly known tensors P and G of EC points with shapes respectively
nxkxm and nxk holds:
(((x1*G11=P111) AND (x2*G11=P112) AND ... AND (xm*G11=P11m))  AND 
 ((x1*G12=P121) AND (x2*G12=P122) AND ... AND (xm*G12=P12m))  AND
                                      ...                     AND
 ((x1*G1k=P1k1) AND (x2*G1k=P1k2) AND ... AND (xm*G1k=P1km))) 
OR
(((x1*G21=P211) AND (x2*G21=P212) AND ... AND (xm*G21=P21m))  AND 
 ((x1*G22=P221) AND (x2*G22=P222) AND ... AND (xm*G22=P22m))  AND
                                      ...                     AND
 ((x1*G2k=P2k1) AND (x2*G2k=P2k2) AND ... AND (xm*G2k=P2km)))
OR
...
OR
(((x1*Gn1=Pn11) AND (x2*Gn1=Pn12) AND ... AND (xm*Gn1=Pn1m))  AND 
 ((x1*Gn2=Pn21) AND (x2*Gn2=Pn22) AND ... AND (xm*Gn2=Pn2m))  AND
                                      ...                     AND
 ((x1*Gnk=Pnk1) AND (x2*Gnk=Pnk2) AND ... AND (xm*Gnk=Pnkm)))
==TRUE

Technically, the statement is encoded as a list of tuples (matrix Pi, vector Gi) in the scheme, so that the tuples in the list correspond to ‘OR’ blocks of the statement.

The key point is that the scheme propagates the batch-Schnorr style signature to connect all ‘AND’ rows within an ‘OR’ block and uses the LSAG method to connect all ‘OR’ blocks together.

As a result, the signature size is sizeof(int)*(n+1), where n is the number of ‘OR’ blocks in the statement. The signature size doesn’t depend on k and m.

However, this signature size is reached only for the case if the publicly known tensors P and G are composed beforehand.

The usual case is when the tensors P and G are populated on the fly with the publicly known points built from transaction outputs or taken from signatures.

For instance, if a statement to be proven is:

I know a private key vector (x1, x2, ..., xm), such that 
the corresponding public key vector is one of:
(X11, X12, ..., X1m)
(X21, X22, ..., X2m)
           ...
(Xn1, Xn2, ..., Xnm),
and the corresponding key image vector is:
(I1, I2, ..., Im), 
    where the key images are defined as: 
    (I1=x1*Hp(Xs1), I2=x2*Hp(Xs1), ..., Im=xm*Hp(Xs1)), 
        where s is an index of true public key vector 
        between the decoys above.

Then the key image vector is put to the signature, and the P and G tensors are built on the fly as:

G11=G 
G12=Hp(X11)
G21=G 
G22=Hp(X21)
     ...
     ...
Gn1=G
Gn2=Hp(Xn1)
  Note: G on the right side of the equations above is the generator.
P111=X11, P112=X12, ..., P11m=X1m
P121=I1 , P122=I2 , ..., P12m=Im
P211=X21, P212=X22, ..., P21m=X2m
P221=I1 , P222=I2 , ..., P22m=Im
                    ...
                    ...
Pn11=Xn1, Pn12=Xn2, ..., Pn1m=Xnm
Pn21=I1 , Pn22=I2 , ..., Pn2m=Im

In this case the signature size is (sizeof(ec_point)*m+sizeof(int)*(n+1)), as the signature carries m key images.

Comparison with the MLSAG

The MLSAG scheme allows to prove similar statement for key vectors, and the MLSAG signature size is O(m*(n+1)), whereas the scheme presented above takes only O(m+n+1).

To be precise, the statement that can be proven with the MLSAG slightly differs from the statement that can be proven with the above scheme. The difference is:

Key image vector defined for the generalized scheme:
(I1=x1*Hp(Xs1), I2=x2*Hp(Xs1), ..., Im=xm*Hp(Xs1))
Key image vector defined in the MLSAG paper:
(I1=x1*Hp(Xs1), I2=x2*Hp(Xs2), ..., Im=xm*Hp(Xsm))

A limitation connected to this difference is described below.

Limitation on the public keys for the case if the key images are put to the signature

The purpose of the key image vectors is to provide linkability between the proofs generated with the equal private key vectors without breaking anonymity. Let’s look into details.

It’s clear, that the both key image vector definitions are good for finding the proofs generated with the equal private key vectors.

The only case, where the first definition can break anonymity, is if an adversary knows a private key for some linear combination of Xs1,…,Xsm. In this case the adversary can break the signer anonymity:

Suppose, adversary knows z and (a1, ..., am), such that:
z*G=a1*Xs1+a2*Xs2+...+am*Xsm
Then, he can find a signature signed with (x1, ..., xm), 
such that (Xs1=x1*G, ...,Xsm=xm*G), by checking:
z*Hp(Xs1)?=a1*I1+a2*I2+...+am*Im

This imposes the following limitation on the public key vectors and, subsequently, on the elements of the tensor P: nobody, except for those who are allowed to deanonymize a signature (i.e. except for the signer and wallet balance auditors), has to know a private key for any linear combination of the public keys in the vector.

With this limitation the anonymity is kept.

This limitation holds for the auditable wallet scheme.

Reduction to the auditable wallet scheme

The generalized scheme can be reduced to the auditable wallet scheme (although with slightly altered coefficients), if we take m=2 and k=2 and define tensors P and G as follows:

For each i=1, …,n: 
                   Gi1=G   , Gi2=Hp(Pi)
                   Pi11=Pi , Pi12=Ti
                   Pi21=I  , Pi22=Ï
Note: here bold letters relate to the auditable wallet scheme, whereas the normal letters relate to the generalized scheme above.

Let’s check, that the limitation on the public keys in the key vector (P, T) holds:

Public key vector:
(P=Hs(r*A)*G+B, T=Hs(r*D)*D)
Alice knows Hs(r*A)=a1 and Hs(r*D)=a2. Suppose, she knows z, a3, a4, such that: 
z*G=a3*P+a4*T=a3*(a1*G+B)+a4*(a2*D)=a3*a1*G+a3*B+a4*a2*D
That means, that she knows y, a5, such that:
y*G=a3*B+a5*D
This is in contradiction with the DL assumption, as the private keys b and d are not known to Alice and chosen at random by Bob.

Extension for signing a message

The extension is easy: a message is to be added as the first argument to Hs(…) everywhere above.

Summary for both schemes

The proposed generalized scheme allows to prove compound statements for private key vectors of any length without taking additional space for the signature.

The signature size is sizeof(int)*(n+1) for the general case, where n is the number of decoys. For the case, when the key image vector is included into signature, the signature size is sizeof(ec_point)*m+sizeof(int)*(n+1).

The generalized scheme can be reduced to the scheme for auditable wallets using key vectors of length 2 and proving 2 statements for each key in the vectors. The auditable wallet scheme signature size is sizeof(ec_point)*2+sizeof(int)*(n+1).

Both schemes are memory efficient, they can be good candidates to implement the auditability and, maybe, some more features in the Cryptonote-based blockchains.

Security

All notes about the security from my previous post are valid for the above schemes, although I don’t provide any formal security proof. My point is that a formal proof is possible under one of the common assumptions.

Continuation is in the following post.