Bulletproof aggregated verification and tests

Also constrains bulletproofs to simple rct, for simplicity

4 files changed, 83 insertions, 91 deletions

diff --git a/src/ringct/rctSigs.cpp b/src/ringct/rctSigs.cpp
index 2e2b07fcc..2175d1659 100644
--- a/src/ringct/rctSigs.cpp
+++ b/src/ringct/rctSigs.cpp
@@ -390,7 +390,7 @@ namespace rct {
       hashes.push_back(hash2rct(h));
 
       keyV kv;
-      if (rv.type == RCTTypeSimpleBulletproof || rv.type == RCTTypeFullBulletproof)
+      if (rv.type == RCTTypeBulletproof)
       {
         kv.reserve((6*2+9) * rv.p.bulletproofs.size());
         for (const auto &p: rv.p.bulletproofs)
@@ -651,8 +651,7 @@ namespace rct {
     //   must know the destination private key to find the correct amount, else will return a random number
     //   Note: For txn fees, the last index in the amounts vector should contain that
     //   Thus the amounts vector will be "one" longer than the destinations vectort
-    rctSig genRct(const key &message, const ctkeyV & inSk, const keyV & destinations, const vector<xmr_amount> & amounts, const ctkeyM &mixRing, const keyV &amount_keys, const multisig_kLRki *kLRki, multisig_out *msout, unsigned int index, ctkeyV &outSk, RangeProofType range_proof_type, hw::device &hwdev) {
-        const bool bulletproof = range_proof_type != RangeProofBorromean;
+    rctSig genRct(const key &message, const ctkeyV & inSk, const keyV & destinations, const vector<xmr_amount> & amounts, const ctkeyM &mixRing, const keyV &amount_keys, const multisig_kLRki *kLRki, multisig_out *msout, unsigned int index, ctkeyV &outSk, hw::device &hwdev) {
         CHECK_AND_ASSERT_THROW_MES(amounts.size() == destinations.size() || amounts.size() == destinations.size() + 1, "Different number of amounts/destinations");
         CHECK_AND_ASSERT_THROW_MES(amount_keys.size() == destinations.size(), "Different number of amount_keys/destinations");
         CHECK_AND_ASSERT_THROW_MES(index < mixRing.size(), "Bad index into mixRing");
@@ -662,11 +661,10 @@ namespace rct {
         CHECK_AND_ASSERT_THROW_MES((kLRki && msout) || (!kLRki && !msout), "Only one of kLRki/msout is present");
 
         rctSig rv;
-        rv.type = bulletproof ? RCTTypeFullBulletproof : RCTTypeFull;
+        rv.type = RCTTypeFull;
         rv.message = message;
         rv.outPk.resize(destinations.size());
-        if (!bulletproof)
-          rv.p.rangeSigs.resize(destinations.size());
+        rv.p.rangeSigs.resize(destinations.size());
         rv.ecdhInfo.resize(destinations.size());
 
         size_t i = 0;
@@ -675,46 +673,11 @@ namespace rct {
         for (i = 0; i < destinations.size(); i++) {
             //add destination to sig
             rv.outPk[i].dest = copy(destinations[i]);
-            //compute range proof (bulletproofs are done later)
-            if (!bulletproof)
-            {
-                rv.p.rangeSigs[i] = proveRange(rv.outPk[i].mask, outSk[i].mask, amounts[i]);
-            #ifdef DBG
-                CHECK_AND_ASSERT_THROW_MES(verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]), "verRange failed on newly created proof");
-            #endif
-            }
-        }
-
-        rv.p.bulletproofs.clear();
-        if (bulletproof)
-        {
-            std::vector<uint64_t> proof_amounts;
-            size_t amounts_proved = 0;
-            while (amounts_proved < amounts.size())
-            {
-                size_t batch_size = 1;
-                if (range_proof_type == RangeProofMultiOutputBulletproof)
-                  while (batch_size * 2 + amounts_proved <= amounts.size())
-                    batch_size *= 2;
-                rct::keyV C, masks;
-                std::vector<uint64_t> batch_amounts(batch_size);
-                for (i = 0; i < batch_size; ++i)
-                  batch_amounts[i] = amounts[i + amounts_proved];
-                rv.p.bulletproofs.push_back(proveRangeBulletproof(C, masks, batch_amounts));
+            //compute range proof
+            rv.p.rangeSigs[i] = proveRange(rv.outPk[i].mask, outSk[i].mask, amounts[i]);
             #ifdef DBG
-                CHECK_AND_ASSERT_THROW_MES(verBulletproof(rv.p.bulletproofs.back()), "verBulletproof failed on newly created proof");
+            CHECK_AND_ASSERT_THROW_MES(verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]), "verRange failed on newly created proof");
             #endif
-                for (i = 0; i < batch_size; ++i)
-                {
-                  rv.outPk[i + amounts_proved].mask = C[i];
-                  outSk[i + amounts_proved].mask = masks[i];
-                }
-                amounts_proved += batch_size;
-            }
-        }
-
-        for (i = 0; i < outSk.size(); ++i)
-        {
             //mask amount and mask
             rv.ecdhInfo[i].mask = copy(outSk[i].mask);
             rv.ecdhInfo[i].amount = d2h(amounts[i]);
@@ -744,7 +707,7 @@ namespace rct {
         ctkeyM mixRing;
         ctkeyV outSk;
         tie(mixRing, index) = populateFromBlockchain(inPk, mixin);
-        return genRct(message, inSk, destinations, amounts, mixRing, amount_keys, kLRki, msout, index, outSk, RangeProofBorromean, hwdev);
+        return genRct(message, inSk, destinations, amounts, mixRing, amount_keys, kLRki, msout, index, outSk, hwdev);
     }
     
     //RCT simple    
@@ -766,35 +729,61 @@ namespace rct {
         }
 
         rctSig rv;
-        rv.type = bulletproof ? RCTTypeSimpleBulletproof : RCTTypeSimple;
+        rv.type = bulletproof ? RCTTypeBulletproof : RCTTypeSimple;
         rv.message = message;
         rv.outPk.resize(destinations.size());
-        if (bulletproof)
-          rv.p.bulletproofs.resize(destinations.size());
-        else
+        if (!bulletproof)
           rv.p.rangeSigs.resize(destinations.size());
         rv.ecdhInfo.resize(destinations.size());
 
         size_t i;
         keyV masks(destinations.size()); //sk mask..
         outSk.resize(destinations.size());
-        key sumout = zero();
         for (i = 0; i < destinations.size(); i++) {
 
             //add destination to sig
             rv.outPk[i].dest = copy(destinations[i]);
             //compute range proof
-            if (bulletproof)
-              rv.p.bulletproofs[i] = proveRangeBulletproof(rv.outPk[i].mask, outSk[i].mask, outamounts[i]);
-            else
+            if (!bulletproof)
               rv.p.rangeSigs[i] = proveRange(rv.outPk[i].mask, outSk[i].mask, outamounts[i]);
             #ifdef DBG
-            if (bulletproof)
-                CHECK_AND_ASSERT_THROW_MES(verBulletproof(rv.p.bulletproofs[i]), "verBulletproof failed on newly created proof");
-            else
+            if (!bulletproof)
                 CHECK_AND_ASSERT_THROW_MES(verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]), "verRange failed on newly created proof");
             #endif
-         
+        }
+
+        rv.p.bulletproofs.clear();
+        if (bulletproof)
+        {
+            std::vector<uint64_t> proof_amounts;
+            size_t n_amounts = outamounts.size();
+            size_t amounts_proved = 0;
+            while (amounts_proved < n_amounts)
+            {
+                size_t batch_size = 1;
+                if (range_proof_type == RangeProofMultiOutputBulletproof)
+                  while (batch_size * 2 + amounts_proved <= n_amounts && batch_size * 2 <= 16)
+                    batch_size *= 2;
+                rct::keyV C, masks;
+                std::vector<uint64_t> batch_amounts(batch_size);
+                for (i = 0; i < batch_size; ++i)
+                  batch_amounts[i] = outamounts[i + amounts_proved];
+                rv.p.bulletproofs.push_back(proveRangeBulletproof(C, masks, batch_amounts));
+            #ifdef DBG
+                CHECK_AND_ASSERT_THROW_MES(verBulletproof(rv.p.bulletproofs.back()), "verBulletproof failed on newly created proof");
+            #endif
+                for (i = 0; i < batch_size; ++i)
+                {
+                  rv.outPk[i + amounts_proved].mask = C[i];
+                  outSk[i + amounts_proved].mask = masks[i];
+                }
+                amounts_proved += batch_size;
+            }
+        }
+
+        key sumout = zero();
+        for (i = 0; i < outSk.size(); ++i)
+        {
             sc_add(sumout.bytes, outSk[i].mask.bytes, sumout.bytes);
 
             //mask amount and mask
@@ -857,14 +846,10 @@ namespace rct {
     //   must know the destination private key to find the correct amount, else will return a random number    
     bool verRct(const rctSig & rv, bool semantics) {
         PERF_TIMER(verRct);
-        CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull || rv.type == RCTTypeFullBulletproof, false, "verRct called on non-full rctSig");
-        const bool bulletproof = is_rct_bulletproof(rv.type);
+        CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull, false, "verRct called on non-full rctSig");
         if (semantics)
         {
-          if (bulletproof)
-            CHECK_AND_ASSERT_MES(rv.outPk.size() == n_bulletproof_amounts(rv.p.bulletproofs), false, "Mismatched sizes of outPk and bulletproofs");
-          else
-            CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.p.rangeSigs.size(), false, "Mismatched sizes of outPk and rv.p.rangeSigs");
+          CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.p.rangeSigs.size(), false, "Mismatched sizes of outPk and rv.p.rangeSigs");
           CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.ecdhInfo.size(), false, "Mismatched sizes of outPk and rv.ecdhInfo");
           CHECK_AND_ASSERT_MES(rv.p.MGs.size() == 1, false, "full rctSig has not one MG");
         }
@@ -879,14 +864,10 @@ namespace rct {
           if (semantics) {
             tools::threadpool& tpool = tools::threadpool::getInstance();
             tools::threadpool::waiter waiter;
-            std::deque<bool> results(bulletproof ? rv.p.bulletproofs.size() : rv.outPk.size(), false);
+            std::deque<bool> results(rv.outPk.size(), false);
             DP("range proofs verified?");
-            if (bulletproof)
-              for (size_t i = 0; i < rv.p.bulletproofs.size(); i++)
-                tpool.submit(&waiter, [&, i] { results[i] = verBulletproof(rv.p.bulletproofs[i]); });
-            else
-              for (size_t i = 0; i < rv.outPk.size(); i++)
-                tpool.submit(&waiter, [&, i] { results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); });
+            for (size_t i = 0; i < rv.outPk.size(); i++)
+              tpool.submit(&waiter, [&, i] { results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); });
             waiter.wait(&tpool);
 
             for (size_t i = 0; i < results.size(); ++i) {
@@ -940,7 +921,7 @@ namespace rct {
         {
           CHECK_AND_ASSERT_MES(rvp, false, "rctSig pointer is NULL");
           const rctSig &rv = *rvp;
-          CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeSimpleBulletproof, false, "verRctSemanticsSimple called on non simple rctSig");
+          CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeBulletproof, false, "verRctSemanticsSimple called on non simple rctSig");
           const bool bulletproof = is_rct_bulletproof(rv.type);
           if (bulletproof)
           {
@@ -1041,7 +1022,7 @@ namespace rct {
       {
         PERF_TIMER(verRctNonSemanticsSimple);
 
-        CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeSimpleBulletproof, false, "verRctNonSemanticsSimple called on non simple rctSig");
+        CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeBulletproof, false, "verRctNonSemanticsSimple called on non simple rctSig");
         const bool bulletproof = is_rct_bulletproof(rv.type);
         // semantics check is early, and mixRing/MGs aren't resolved yet
         if (bulletproof)
@@ -1101,7 +1082,7 @@ namespace rct {
     //   uses the attached ecdh info to find the amounts represented by each output commitment 
     //   must know the destination private key to find the correct amount, else will return a random number    
     xmr_amount decodeRct(const rctSig & rv, const key & sk, unsigned int i, key & mask, hw::device &hwdev) {
-        CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull || rv.type == RCTTypeFullBulletproof, false, "decodeRct called on non-full rctSig");
+        CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull, false, "decodeRct called on non-full rctSig");
         CHECK_AND_ASSERT_THROW_MES(i < rv.ecdhInfo.size(), "Bad index");
         CHECK_AND_ASSERT_THROW_MES(rv.outPk.size() == rv.ecdhInfo.size(), "Mismatched sizes of rv.outPk and rv.ecdhInfo");
 
@@ -1129,7 +1110,7 @@ namespace rct {
     }
 
     xmr_amount decodeRctSimple(const rctSig & rv, const key & sk, unsigned int i, key &mask, hw::device &hwdev) {
-        CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeSimpleBulletproof, false, "decodeRct called on non simple rctSig");
+        CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeBulletproof, false, "decodeRct called on non simple rctSig");
         CHECK_AND_ASSERT_THROW_MES(i < rv.ecdhInfo.size(), "Bad index");
         CHECK_AND_ASSERT_THROW_MES(rv.outPk.size() == rv.ecdhInfo.size(), "Mismatched sizes of rv.outPk and rv.ecdhInfo");
 
@@ -1157,12 +1138,12 @@ namespace rct {
     }
 
     bool signMultisig(rctSig &rv, const std::vector<unsigned int> &indices, const keyV &k, const multisig_out &msout, const key &secret_key) {
-        CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull || rv.type == RCTTypeSimple || rv.type == RCTTypeFullBulletproof || rv.type == RCTTypeSimpleBulletproof,
+        CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull || rv.type == RCTTypeSimple || rv.type == RCTTypeBulletproof,
             false, "unsupported rct type");
         CHECK_AND_ASSERT_MES(indices.size() == k.size(), false, "Mismatched k/indices sizes");
         CHECK_AND_ASSERT_MES(k.size() == rv.p.MGs.size(), false, "Mismatched k/MGs size");
         CHECK_AND_ASSERT_MES(k.size() == msout.c.size(), false, "Mismatched k/msout.c size");
-        if (rv.type == RCTTypeFull || rv.type == RCTTypeFullBulletproof)
+        if (rv.type == RCTTypeFull)
         {
           CHECK_AND_ASSERT_MES(rv.p.MGs.size() == 1, false, "MGs not a single element");
         }
diff --git a/src/ringct/rctSigs.h b/src/ringct/rctSigs.h
index d1090ca77..ae8bb91d7 100644
--- a/src/ringct/rctSigs.h
+++ b/src/ringct/rctSigs.h
@@ -119,7 +119,7 @@ namespace rct {
     //decodeRct: (c.f. https://eprint.iacr.org/2015/1098 section 5.1.1)
     //   uses the attached ecdh info to find the amounts represented by each output commitment
     //   must know the destination private key to find the correct amount, else will return a random number
-    rctSig genRct(const key &message, const ctkeyV & inSk, const keyV & destinations, const std::vector<xmr_amount> & amounts, const ctkeyM &mixRing, const keyV &amount_keys, const multisig_kLRki *kLRki, multisig_out *msout, unsigned int index, ctkeyV &outSk, RangeProofType range_proof_type, hw::device &hwdev);
+    rctSig genRct(const key &message, const ctkeyV & inSk, const keyV & destinations, const std::vector<xmr_amount> & amounts, const ctkeyM &mixRing, const keyV &amount_keys, const multisig_kLRki *kLRki, multisig_out *msout, unsigned int index, ctkeyV &outSk, hw::device &hwdev);
     rctSig genRct(const key &message, const ctkeyV & inSk, const ctkeyV  & inPk, const keyV & destinations, const std::vector<xmr_amount> & amounts, const keyV &amount_keys, const multisig_kLRki *kLRki, multisig_out *msout, const int mixin, hw::device &hwdev);
     rctSig genRctSimple(const key & message, const ctkeyV & inSk, const ctkeyV & inPk, const keyV & destinations, const std::vector<xmr_amount> & inamounts, const std::vector<xmr_amount> & outamounts, const keyV &amount_keys, const std::vector<multisig_kLRki> *kLRki, multisig_out *msout, xmr_amount txnFee, unsigned int mixin, hw::device &hwdev);
     rctSig genRctSimple(const key & message, const ctkeyV & inSk, const keyV & destinations, const std::vector<xmr_amount> & inamounts, const std::vector<xmr_amount> & outamounts, xmr_amount txnFee, const ctkeyM & mixRing, const keyV &amount_keys, const std::vector<multisig_kLRki> *kLRki, multisig_out *msout, const std::vector<unsigned int> & index, ctkeyV &outSk, RangeProofType range_proof_type, hw::device &hwdev);
diff --git a/src/ringct/rctTypes.cpp b/src/ringct/rctTypes.cpp
index 72ef75780..e67637af6 100644
--- a/src/ringct/rctTypes.cpp
+++ b/src/ringct/rctTypes.cpp
@@ -28,6 +28,7 @@
 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
+#include "misc_log_ex.h"
 #include "rctTypes.h"
 using namespace crypto;
 using namespace std;
@@ -214,7 +215,7 @@ namespace rct {
         switch (type)
         {
             case RCTTypeSimple:
-            case RCTTypeSimpleBulletproof:
+            case RCTTypeBulletproof:
                 return true;
             default:
                 return false;
@@ -225,19 +226,29 @@ namespace rct {
     {
         switch (type)
         {
-            case RCTTypeSimpleBulletproof:
-            case RCTTypeFullBulletproof:
+            case RCTTypeBulletproof:
                 return true;
             default:
                 return false;
         }
     }
 
+    size_t n_bulletproof_amounts(const Bulletproof &proof)
+    {
+        CHECK_AND_ASSERT_MES(proof.L.size() >= 6, 0, "Invalid bulletproof L size");
+        return 1 << (proof.L.size() - 6);
+    }
+
     size_t n_bulletproof_amounts(const std::vector<Bulletproof> &proofs)
     {
         size_t n = 0;
         for (const Bulletproof &proof: proofs)
-            n += proof.V.size();
+        {
+            size_t n2 = n_bulletproof_amounts(proof);
+            if (n2 == 0)
+                return 0;
+            n += n2;
+        }
         return n;
     }
 
diff --git a/src/ringct/rctTypes.h b/src/ringct/rctTypes.h
index 5574c7784..894f747b8 100644
--- a/src/ringct/rctTypes.h
+++ b/src/ringct/rctTypes.h
@@ -213,6 +213,7 @@ namespace rct {
       END_SERIALIZE()
     };
 
+    size_t n_bulletproof_amounts(const Bulletproof &proof);
     size_t n_bulletproof_amounts(const std::vector<Bulletproof> &proofs);
 
     //A container to hold all signatures necessary for RingCT
@@ -226,8 +227,7 @@ namespace rct {
       RCTTypeNull = 0,
       RCTTypeFull = 1,
       RCTTypeSimple = 2,
-      RCTTypeFullBulletproof = 3,
-      RCTTypeSimpleBulletproof = 4,
+      RCTTypeBulletproof = 3,
     };
     enum RangeProofType { RangeProofBorromean, RangeProofBulletproof, RangeProofMultiOutputBulletproof };
     struct rctSigBase {
@@ -246,7 +246,7 @@ namespace rct {
           FIELD(type)
           if (type == RCTTypeNull)
             return true;
-          if (type != RCTTypeFull && type != RCTTypeFullBulletproof && type != RCTTypeSimple && type != RCTTypeSimpleBulletproof)
+          if (type != RCTTypeFull && type != RCTTypeSimple && type != RCTTypeBulletproof)
             return false;
           VARINT_FIELD(txnFee)
           // inputs/outputs not saved, only here for serialization help
@@ -307,9 +307,9 @@ namespace rct {
         {
           if (type == RCTTypeNull)
             return true;
-          if (type != RCTTypeFull && type != RCTTypeFullBulletproof && type != RCTTypeSimple && type != RCTTypeSimpleBulletproof)
+          if (type != RCTTypeFull && type != RCTTypeSimple && type != RCTTypeBulletproof)
             return false;
-          if (type == RCTTypeSimpleBulletproof || type == RCTTypeFullBulletproof)
+          if (type == RCTTypeBulletproof)
           {
             ar.tag("bp");
             ar.begin_array();
@@ -348,7 +348,7 @@ namespace rct {
           ar.begin_array();
           // we keep a byte for size of MGs, because we don't know whether this is
           // a simple or full rct signature, and it's starting to annoy the hell out of me
-          size_t mg_elements = (type == RCTTypeSimple || type == RCTTypeSimpleBulletproof) ? inputs : 1;
+          size_t mg_elements = (type == RCTTypeSimple || type == RCTTypeBulletproof) ? inputs : 1;
           PREPARE_CUSTOM_VECTOR_SERIALIZATION(mg_elements, MGs);
           if (MGs.size() != mg_elements)
             return false;
@@ -366,7 +366,7 @@ namespace rct {
             for (size_t j = 0; j < mixin + 1; ++j)
             {
               ar.begin_array();
-              size_t mg_ss2_elements = ((type == RCTTypeSimple || type == RCTTypeSimpleBulletproof) ? 1 : inputs) + 1;
+              size_t mg_ss2_elements = ((type == RCTTypeSimple || type == RCTTypeBulletproof) ? 1 : inputs) + 1;
               PREPARE_CUSTOM_VECTOR_SERIALIZATION(mg_ss2_elements, MGs[i].ss[j]);
               if (MGs[i].ss[j].size() != mg_ss2_elements)
                 return false;
@@ -392,7 +392,7 @@ namespace rct {
                ar.delimit_array();
           }
           ar.end_array();
-          if (type == RCTTypeSimpleBulletproof)
+          if (type == RCTTypeBulletproof)
           {
             ar.tag("pseudoOuts");
             ar.begin_array();
@@ -416,12 +416,12 @@ namespace rct {
 
         keyV& get_pseudo_outs()
         {
-          return type == RCTTypeSimpleBulletproof ? p.pseudoOuts : pseudoOuts;
+          return type == RCTTypeBulletproof ? p.pseudoOuts : pseudoOuts;
         }
 
         keyV const& get_pseudo_outs() const
         {
-          return type == RCTTypeSimpleBulletproof ? p.pseudoOuts : pseudoOuts;
+          return type == RCTTypeBulletproof ? p.pseudoOuts : pseudoOuts;
         }
     };