CLSAG optimizations

1 files changed, 135 insertions, 129 deletions

diff --git a/src/ringct/rctSigs.cpp b/src/ringct/rctSigs.cpp
index 074812156..2e56dad58 100644
--- a/src/ringct/rctSigs.cpp
+++ b/src/ringct/rctSigs.cpp
@@ -168,12 +168,17 @@ namespace rct {
 
     // Generate a CLSAG signature
     // See paper by Goodell et al. (https://eprint.iacr.org/2019/654)
-    clsag CLSAG_Gen(const key &message, const keyV & P, const key & p, const keyV & C, const key & z, const unsigned int l, const multisig_kLRki *kLRki, key *mscout, key *mspout) {
+    //
+    // The keys are set as follows:
+    //   P[l] == p*G
+    //   C[l] == z*G
+    //   C[i] == C_nonzero[i] - C_offset (for hashing purposes) for all i
+    clsag CLSAG_Gen(const key &message, const keyV & P, const key & p, const keyV & C, const key & z, const keyV & C_nonzero, const key & C_offset, const unsigned int l, const multisig_kLRki *kLRki, key *mscout, key *mspout) {
         clsag sig;
         size_t n = P.size(); // ring size
         CHECK_AND_ASSERT_THROW_MES(n == C.size(), "Signing and commitment key vector sizes must match!");
+        CHECK_AND_ASSERT_THROW_MES(n == C_nonzero.size(), "Signing and commitment key vector sizes must match!");
         CHECK_AND_ASSERT_THROW_MES(l < n, "Signing index out of range!");
-        CHECK_AND_ASSERT_THROW_MES(scalarmultBase(z) == C[l], "C does not match z!");
         CHECK_AND_ASSERT_THROW_MES((kLRki && mscout) || (!kLRki && !mscout), "Only one of kLRki/mscout is present");
         CHECK_AND_ASSERT_THROW_MES((mscout && mspout) || !kLRki, "Multisig pointers are not all present");
 
@@ -212,8 +217,8 @@ namespace rct {
         scalarmultKey(aH,H,a);
 
         // Aggregation hashes
-        keyV mu_P_to_hash(2*n+3); // domain, I, D, P, C
-        keyV mu_C_to_hash(2*n+3); // domain, I, D, P, C
+        keyV mu_P_to_hash(2*n+4); // domain, I, D, P, C, C_offset
+        keyV mu_C_to_hash(2*n+4); // domain, I, D, P, C, C_offset
         sc_0(mu_P_to_hash[0].bytes);
         memcpy(mu_P_to_hash[0].bytes,config::HASH_KEY_CLSAG_AGG_0,sizeof(config::HASH_KEY_CLSAG_AGG_0)-1);
         sc_0(mu_C_to_hash[0].bytes);
@@ -223,40 +228,43 @@ namespace rct {
             mu_C_to_hash[i] = P[i-1];
         }
         for (size_t i = n+1; i < 2*n+1; ++i) {
-            mu_P_to_hash[i] = C[i-n-1];
-            mu_C_to_hash[i] = C[i-n-1];
+            mu_P_to_hash[i] = C_nonzero[i-n-1];
+            mu_C_to_hash[i] = C_nonzero[i-n-1];
         }
         mu_P_to_hash[2*n+1] = sig.I;
         mu_P_to_hash[2*n+2] = sig.D;
+        mu_P_to_hash[2*n+3] = C_offset;
         mu_C_to_hash[2*n+1] = sig.I;
         mu_C_to_hash[2*n+2] = sig.D;
+        mu_C_to_hash[2*n+3] = C_offset;
         key mu_P, mu_C;
         mu_P = hash_to_scalar(mu_P_to_hash);
         mu_C = hash_to_scalar(mu_C_to_hash);
 
         // Initial commitment
-        keyV c_to_hash(2*n+4); // domain, P, C, message, aG, aH
+        keyV c_to_hash(2*n+5); // domain, P, C, C_offset, message, aG, aH
         key c;
         sc_0(c_to_hash[0].bytes);
         memcpy(c_to_hash[0].bytes,config::HASH_KEY_CLSAG_ROUND,sizeof(config::HASH_KEY_CLSAG_ROUND)-1);
         for (size_t i = 1; i < n+1; ++i)
         {
             c_to_hash[i] = P[i-1];
-            c_to_hash[i+n] = C[i-1];
+            c_to_hash[i+n] = C_nonzero[i-1];
         }
-        c_to_hash[2*n+1] = message;
+        c_to_hash[2*n+1] = C_offset;
+        c_to_hash[2*n+2] = message;
 
         // Multisig data is present
         if (kLRki)
         {
             a = kLRki->k;
-            c_to_hash[2*n+2] = kLRki->L;
-            c_to_hash[2*n+3] = kLRki->R;
+            c_to_hash[2*n+3] = kLRki->L;
+            c_to_hash[2*n+4] = kLRki->R;
         }
         else
         {
-            c_to_hash[2*n+2] = aG;
-            c_to_hash[2*n+3] = aH;
+            c_to_hash[2*n+3] = aG;
+            c_to_hash[2*n+4] = aH;
         }
         c = hash_to_scalar(c_to_hash);
         
@@ -295,8 +303,8 @@ namespace rct {
             ge_dsm_precomp(H_precomp.k, &Hi_p3);
             addKeys_aAbBcC(R,sig.s[i],H_precomp.k,c_p,I_precomp.k,c_c,D_precomp.k);
 
-            c_to_hash[2*n+2] = L;
-            c_to_hash[2*n+3] = R;
+            c_to_hash[2*n+3] = L;
+            c_to_hash[2*n+4] = R;
             c_new = hash_to_scalar(c_to_hash);
             copy(c,c_new);
             
@@ -320,99 +328,8 @@ namespace rct {
         return sig;
     }
 
-    clsag CLSAG_Gen(const key &message, const keyV & P, const key & p, const keyV & C, const key & z, const unsigned int l) {
-        return CLSAG_Gen(message, P, p, C, z, l, NULL, NULL, NULL);
-    }
-
-    // Verify a CLSAG signature
-    // See paper by Goodell et al. (https://eprint.iacr.org/2019/654)
-    bool CLSAG_Ver(const key &message, const keyV & P, const keyV & C, const clsag & sig)
-    {
-        size_t n = P.size(); // ring size
-        CHECK_AND_ASSERT_MES(n == C.size(), false, "Signing and commitment key vector sizes must match!");
-        CHECK_AND_ASSERT_MES(n == sig.s.size(), false, "Signature scalar vector is the wrong size!");
-        for (size_t i = 0; i < n; ++i)
-            CHECK_AND_ASSERT_MES(sc_check(sig.s[i].bytes) == 0, false, "Bad signature scalar!");
-        CHECK_AND_ASSERT_MES(sc_check(sig.c1.bytes) == 0, false, "Bad signature commitment!");
-
-        key c = copy(sig.c1);
-        key D_8 = scalarmult8(sig.D);
-        geDsmp I_precomp;
-        geDsmp D_precomp;
-        precomp(I_precomp.k,sig.I);
-        precomp(D_precomp.k,D_8);
-
-        // Aggregation hashes
-        keyV mu_P_to_hash(2*n+3); // domain, I, D, P, C
-        keyV mu_C_to_hash(2*n+3); // domain, I, D, P, C
-        sc_0(mu_P_to_hash[0].bytes);
-        memcpy(mu_P_to_hash[0].bytes,config::HASH_KEY_CLSAG_AGG_0,sizeof(config::HASH_KEY_CLSAG_AGG_0)-1);
-        sc_0(mu_C_to_hash[0].bytes);
-        memcpy(mu_C_to_hash[0].bytes,config::HASH_KEY_CLSAG_AGG_1,sizeof(config::HASH_KEY_CLSAG_AGG_1)-1);
-        for (size_t i = 1; i < n+1; ++i) {
-            mu_P_to_hash[i] = P[i-1];
-            mu_C_to_hash[i] = P[i-1];
-        }
-        for (size_t i = n+1; i < 2*n+1; ++i) {
-            mu_P_to_hash[i] = C[i-n-1];
-            mu_C_to_hash[i] = C[i-n-1];
-        }
-        mu_P_to_hash[2*n+1] = sig.I;
-        mu_P_to_hash[2*n+2] = sig.D;
-        mu_C_to_hash[2*n+1] = sig.I;
-        mu_C_to_hash[2*n+2] = sig.D;
-        key mu_P, mu_C;
-        mu_P = hash_to_scalar(mu_P_to_hash);
-        mu_C = hash_to_scalar(mu_C_to_hash);
-
-        keyV c_to_hash(2*n+4); // domain, P, C, message, L, R
-        sc_0(c_to_hash[0].bytes);
-        memcpy(c_to_hash[0].bytes,config::HASH_KEY_CLSAG_ROUND,sizeof(config::HASH_KEY_CLSAG_ROUND)-1);
-        for (size_t i = 1; i < n+1; ++i)
-        {
-            c_to_hash[i] = P[i-1];
-            c_to_hash[i+n] = C[i-1];
-        }
-        c_to_hash[2*n+1] = message;
-        key c_p; // = c[i]*mu_P
-        key c_c; // = c[i]*mu_C
-        key c_new;
-        key L;
-        key R;
-        geDsmp P_precomp;
-        geDsmp C_precomp;
-        geDsmp H_precomp;
-        size_t i = 0;
-        ge_p3 hash8_p3;
-        geDsmp hash_precomp;
-
-        while (i < n) {
-            sc_0(c_new.bytes);
-            sc_mul(c_p.bytes,mu_P.bytes,c.bytes);
-            sc_mul(c_c.bytes,mu_C.bytes,c.bytes);
-
-            // Precompute points
-            precomp(P_precomp.k,P[i]);
-            precomp(C_precomp.k,C[i]);
-
-            // Compute L
-            addKeys_aGbBcC(L,sig.s[i],c_p,P_precomp.k,c_c,C_precomp.k);
-
-            // Compute R
-            hash_to_p3(hash8_p3,P[i]);
-            ge_dsm_precomp(hash_precomp.k, &hash8_p3);
-            addKeys_aAbBcC(R,sig.s[i],hash_precomp.k,c_p,I_precomp.k,c_c,D_precomp.k);
-
-            c_to_hash[2*n+2] = L;
-            c_to_hash[2*n+3] = R;
-            c_new = hash_to_scalar(c_to_hash);
-            CHECK_AND_ASSERT_MES(!(c_new == rct::zero()), false, "Bad signature hash");
-            copy(c,c_new);
-
-            i = i + 1;
-        }
-        sc_sub(c_new.bytes,c.bytes,sig.c1.bytes);
-        return sc_isnonzero(c_new.bytes) == 0;
+    clsag CLSAG_Gen(const key &message, const keyV & P, const key & p, const keyV & C, const key & z, const keyV & C_nonzero, const key & C_offset, const unsigned int l) {
+        return CLSAG_Gen(message, P, p, C, z, C_nonzero, C_offset, l, NULL, NULL, NULL);
     }
 
     // MLSAG signatures
@@ -816,12 +733,14 @@ namespace rct {
         size_t i;
         keyM M(cols, tmp);
 
-        keyV P, C;
+        keyV P, C, C_nonzero;
         P.reserve(pubs.size());
         C.reserve(pubs.size());
+        C_nonzero.reserve(pubs.size());
         for (const ctkey &k: pubs)
         {
             P.push_back(k.dest);
+            C_nonzero.push_back(k.mask);
             rct::key tmp;
             subKeys(tmp, k.mask, Cout);
             C.push_back(tmp);
@@ -829,7 +748,7 @@ namespace rct {
 
         sk[0] = copy(inSk.dest);
         sc_sub(sk[1].bytes, inSk.mask.bytes, a.bytes);
-        clsag result = CLSAG_Gen(message, P, sk[0], C, sk[1], index, kLRki, mscout, mspout);
+        clsag result = CLSAG_Gen(message, P, sk[0], C, sk[1], C_nonzero, Cout, index, kLRki, mscout, mspout);
         memwipe(sk.data(), sk.size() * sizeof(key));
         return result;
     }
@@ -913,29 +832,116 @@ namespace rct {
         catch (...) { return false; }
     }
 
-    bool verRctCLSAGSimple(const key &message, const clsag &clsag, const ctkeyV & pubs, const key & C) {
+    bool verRctCLSAGSimple(const key &message, const clsag &sig, const ctkeyV & pubs, const key & C_offset) {
         try
         {
             PERF_TIMER(verRctCLSAGSimple);
-            //setup vars
-            const size_t cols = pubs.size();
-            CHECK_AND_ASSERT_MES(cols >= 1, false, "Empty pubs");
-            keyV Pi(cols), Ci(cols);
-            ge_p3 Cp3;
-            CHECK_AND_ASSERT_MES_L1(ge_frombytes_vartime(&Cp3, C.bytes) == 0, false, "point conv failed");
-            ge_cached Ccached;
-            ge_p3_to_cached(&Ccached, &Cp3);
-            ge_p1p1 p1;
-            //create the matrix to mg sig
-            for (size_t i = 0; i < cols; i++) {
-                    Pi[i] = pubs[i].dest;
-                    ge_p3 p3;
-                    CHECK_AND_ASSERT_MES_L1(ge_frombytes_vartime(&p3, pubs[i].mask.bytes) == 0, false, "point conv failed");
-                    ge_sub(&p1, &p3, &Ccached);
-                    ge_p1p1_to_p3(&p3, &p1);
-                    ge_p3_tobytes(Ci[i].bytes, &p3);
+            const size_t n = pubs.size();
+
+            // Check data
+            CHECK_AND_ASSERT_MES(n >= 1, false, "Empty pubs");
+            CHECK_AND_ASSERT_MES(n == sig.s.size(), false, "Signature scalar vector is the wrong size!");
+            for (size_t i = 0; i < n; ++i)
+                CHECK_AND_ASSERT_MES(sc_check(sig.s[i].bytes) == 0, false, "Bad signature scalar!");
+            CHECK_AND_ASSERT_MES(sc_check(sig.c1.bytes) == 0, false, "Bad signature commitment!");
+            CHECK_AND_ASSERT_MES(!(sig.I == rct::identity()), false, "Bad key image!");
+
+            // Cache commitment offset for efficient subtraction later
+            ge_p3 C_offset_p3;
+            CHECK_AND_ASSERT_MES(ge_frombytes_vartime(&C_offset_p3, C_offset.bytes) == 0, false, "point conv failed");
+            ge_cached C_offset_cached;
+            ge_p3_to_cached(&C_offset_cached, &C_offset_p3);
+
+            // Prepare key images
+            key c = copy(sig.c1);
+            key D_8 = scalarmult8(sig.D);
+            CHECK_AND_ASSERT_MES(!(D_8 == rct::identity()), false, "Bad auxiliary key image!");
+            geDsmp I_precomp;
+            geDsmp D_precomp;
+            precomp(I_precomp.k,sig.I);
+            precomp(D_precomp.k,D_8);
+
+            // Aggregation hashes
+            keyV mu_P_to_hash(2*n+4); // domain, I, D, P, C, C_offset
+            keyV mu_C_to_hash(2*n+4); // domain, I, D, P, C, C_offset
+            sc_0(mu_P_to_hash[0].bytes);
+            memcpy(mu_P_to_hash[0].bytes,config::HASH_KEY_CLSAG_AGG_0,sizeof(config::HASH_KEY_CLSAG_AGG_0)-1);
+            sc_0(mu_C_to_hash[0].bytes);
+            memcpy(mu_C_to_hash[0].bytes,config::HASH_KEY_CLSAG_AGG_1,sizeof(config::HASH_KEY_CLSAG_AGG_1)-1);
+            for (size_t i = 1; i < n+1; ++i) {
+                mu_P_to_hash[i] = pubs[i-1].dest;
+                mu_C_to_hash[i] = pubs[i-1].dest;
+            }
+            for (size_t i = n+1; i < 2*n+1; ++i) {
+                mu_P_to_hash[i] = pubs[i-n-1].mask;
+                mu_C_to_hash[i] = pubs[i-n-1].mask;
+            }
+            mu_P_to_hash[2*n+1] = sig.I;
+            mu_P_to_hash[2*n+2] = sig.D;
+            mu_P_to_hash[2*n+3] = C_offset;
+            mu_C_to_hash[2*n+1] = sig.I;
+            mu_C_to_hash[2*n+2] = sig.D;
+            mu_C_to_hash[2*n+3] = C_offset;
+            key mu_P, mu_C;
+            mu_P = hash_to_scalar(mu_P_to_hash);
+            mu_C = hash_to_scalar(mu_C_to_hash);
+
+            // Set up round hash
+            keyV c_to_hash(2*n+5); // domain, P, C, C_offset, message, L, R
+            sc_0(c_to_hash[0].bytes);
+            memcpy(c_to_hash[0].bytes,config::HASH_KEY_CLSAG_ROUND,sizeof(config::HASH_KEY_CLSAG_ROUND)-1);
+            for (size_t i = 1; i < n+1; ++i)
+            {
+                c_to_hash[i] = pubs[i-1].dest;
+                c_to_hash[i+n] = pubs[i-1].mask;
+            }
+            c_to_hash[2*n+1] = C_offset;
+            c_to_hash[2*n+2] = message;
+            key c_p; // = c[i]*mu_P
+            key c_c; // = c[i]*mu_C
+            key c_new;
+            key L;
+            key R;
+            geDsmp P_precomp;
+            geDsmp C_precomp;
+            geDsmp H_precomp;
+            size_t i = 0;
+            ge_p3 hash8_p3;
+            geDsmp hash_precomp;
+            ge_p3 temp_p3;
+            ge_p1p1 temp_p1;
+
+            while (i < n) {
+                sc_0(c_new.bytes);
+                sc_mul(c_p.bytes,mu_P.bytes,c.bytes);
+                sc_mul(c_c.bytes,mu_C.bytes,c.bytes);
+
+                // Precompute points for L/R
+                precomp(P_precomp.k,pubs[i].dest);
+
+                CHECK_AND_ASSERT_MES(ge_frombytes_vartime(&temp_p3, pubs[i].mask.bytes) == 0, false, "point conv failed");
+                ge_sub(&temp_p1,&temp_p3,&C_offset_cached);
+                ge_p1p1_to_p3(&temp_p3,&temp_p1);
+                ge_dsm_precomp(C_precomp.k,&temp_p3);
+
+                // Compute L
+                addKeys_aGbBcC(L,sig.s[i],c_p,P_precomp.k,c_c,C_precomp.k);
+
+                // Compute R
+                hash_to_p3(hash8_p3,pubs[i].dest);
+                ge_dsm_precomp(hash_precomp.k, &hash8_p3);
+                addKeys_aAbBcC(R,sig.s[i],hash_precomp.k,c_p,I_precomp.k,c_c,D_precomp.k);
+
+                c_to_hash[2*n+3] = L;
+                c_to_hash[2*n+4] = R;
+                c_new = hash_to_scalar(c_to_hash);
+                CHECK_AND_ASSERT_MES(!(c_new == rct::zero()), false, "Bad signature hash");
+                copy(c,c_new);
+
+                i = i + 1;
             }
-            return CLSAG_Ver(message, Pi, Ci, clsag);
+            sc_sub(c_new.bytes,c.bytes,sig.c1.bytes);
+            return sc_isnonzero(c_new.bytes) == 0;
         }
         catch (...) { return false; }
     }