multiexp: handle pippenger multiexps with part precalc

4 files changed, 29 insertions, 21 deletions

diff --git a/src/ringct/bulletproofs.cc b/src/ringct/bulletproofs.cc
index 9e4d85534..a3af9264e 100644
--- a/src/ringct/bulletproofs.cc
+++ b/src/ringct/bulletproofs.cc
@@ -73,15 +73,15 @@ static const rct::keyV twoN = vector_powers(TWO, maxN);
 static const rct::key ip12 = inner_product(oneN, twoN);
 static boost::mutex init_mutex;
 
-static inline rct::key multiexp(const std::vector<MultiexpData> &data, bool HiGi)
+static inline rct::key multiexp(const std::vector<MultiexpData> &data, size_t HiGi_size)
 {
-  if (HiGi)
+  if (HiGi_size > 0)
   {
     static_assert(128 <= STRAUS_SIZE_LIMIT, "Straus in precalc mode can only be calculated till STRAUS_SIZE_LIMIT");
-    return data.size() <= 128 ? straus(data, straus_HiGi_cache, 0) : pippenger(data, pippenger_HiGi_cache, get_pippenger_c(data.size()));
+    return HiGi_size <= 128 && data.size() == HiGi_size ? straus(data, straus_HiGi_cache, 0) : pippenger(data, pippenger_HiGi_cache, HiGi_size, get_pippenger_c(data.size()));
   }
   else
-    return data.size() <= 64 ? straus(data, NULL, 0) : pippenger(data, NULL, get_pippenger_c(data.size()));
+    return data.size() <= 64 ? straus(data, NULL, 0) : pippenger(data, NULL, 0, get_pippenger_c(data.size()));
 }
 
 static inline bool is_reduced(const rct::key &scalar)
@@ -118,7 +118,7 @@ static void init_exponents()
   }
 
   straus_HiGi_cache = straus_init_cache(data, STRAUS_SIZE_LIMIT);
-  pippenger_HiGi_cache = pippenger_init_cache(data, PIPPENGER_SIZE_LIMIT);
+  pippenger_HiGi_cache = pippenger_init_cache(data, 0, PIPPENGER_SIZE_LIMIT);
 
   MINFO("Hi/Gi cache size: " << (sizeof(Hi)+sizeof(Gi))/1024 << " kB");
   MINFO("Hi_p3/Gi_p3 cache size: " << (sizeof(Hi_p3)+sizeof(Gi_p3))/1024 << " kB");
@@ -142,7 +142,7 @@ static rct::key vector_exponent(const rct::keyV &a, const rct::keyV &b)
     multiexp_data.emplace_back(a[i], Gi_p3[i]);
     multiexp_data.emplace_back(b[i], Hi_p3[i]);
   }
-  return multiexp(multiexp_data, true);
+  return multiexp(multiexp_data, 2 * a.size());
 }
 
 /* Compute a custom vector-scalar commitment */
@@ -169,7 +169,7 @@ static rct::key cross_vector_exponent8(size_t size, const std::vector<ge_p3> &A,
     sc_mul(multiexp_data.back().scalar.bytes, extra_scalar->bytes, INV_EIGHT.bytes);
     multiexp_data.back().point = *extra_point;
   }
-  return multiexp(multiexp_data, false);
+  return multiexp(multiexp_data, 0);
 }
 
 /* Given a scalar, construct a vector of powers */
@@ -839,6 +839,7 @@ bool bulletproof_VERIFY(const std::vector<const Bulletproof*> &proofs)
 
   std::vector<MultiexpData> multiexp_data;
   multiexp_data.reserve(nV + (2 * (10/*logM*/ + logN) + 4) * proofs.size() + 2 * maxMN);
+  multiexp_data.resize(2 * maxMN);
 
   PERF_TIMER_START_BP(VERIFY_line_24_25_invert);
   const std::vector<rct::key> inverses = invert(to_invert);
@@ -1011,10 +1012,10 @@ bool bulletproof_VERIFY(const std::vector<const Bulletproof*> &proofs)
   multiexp_data.emplace_back(tmp, rct::H);
   for (size_t i = 0; i < maxMN; ++i)
   {
-    multiexp_data.emplace_back(m_z4[i], Gi_p3[i]);
-    multiexp_data.emplace_back(m_z5[i], Hi_p3[i]);
+    multiexp_data[i * 2] = {m_z4[i], Gi_p3[i]};
+    multiexp_data[i * 2 + 1] = {m_z5[i], Hi_p3[i]};
   }
-  if (!(multiexp(multiexp_data, false) == rct::identity()))
+  if (!(multiexp(multiexp_data, 2 * maxMN) == rct::identity()))
   {
     PERF_TIMER_STOP(VERIFY_step2_check);
     MERROR("Verification failure");
diff --git a/src/ringct/multiexp.cc b/src/ringct/multiexp.cc
index fb2f18551..178f92267 100644
--- a/src/ringct/multiexp.cc
+++ b/src/ringct/multiexp.cc
@@ -564,12 +564,13 @@ struct pippenger_cached_data
   ~pippenger_cached_data() { aligned_free(cached); }
 };
 
-std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t N)
+std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t start_offset, size_t N)
 {
   MULTIEXP_PERF(PERF_TIMER_START_UNIT(pippenger_init_cache, 1000000));
+  CHECK_AND_ASSERT_THROW_MES(start_offset <= data.size(), "Bad cache base data");
   if (N == 0)
-    N = data.size();
-  CHECK_AND_ASSERT_THROW_MES(N <= data.size(), "Bad cache base data");
+    N = data.size() - start_offset;
+  CHECK_AND_ASSERT_THROW_MES(N <= data.size() - start_offset, "Bad cache base data");
   ge_cached cached;
   std::shared_ptr<pippenger_cached_data> cache(new pippenger_cached_data());
 
@@ -577,7 +578,7 @@ std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<Mu
   cache->cached = (ge_cached*)aligned_realloc(cache->cached, N * sizeof(ge_cached), 4096);
   CHECK_AND_ASSERT_THROW_MES(cache->cached, "Out of memory");
   for (size_t i = 0; i < N; ++i)
-    ge_p3_to_cached(&cache->cached[i], &data[i].point);
+    ge_p3_to_cached(&cache->cached[i], &data[i+start_offset].point);
 
   MULTIEXP_PERF(PERF_TIMER_STOP(pippenger_init_cache));
   return cache;
@@ -588,9 +589,11 @@ size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &ca
   return cache->size * sizeof(*cache->cached);
 }
 
-rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache, size_t c)
+rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache, size_t cache_size, size_t c)
 {
-  CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache->size >= data.size(), "Cache is too small");
+  if (cache != NULL && cache_size == 0)
+    cache_size = cache->size;
+  CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache_size <= cache->size, "Cache is too small");
   if (c == 0)
     c = get_pippenger_c(data.size());
   CHECK_AND_ASSERT_THROW_MES(c <= 9, "c is too large");
@@ -598,6 +601,7 @@ rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<
   ge_p3 result = ge_p3_identity;
   std::unique_ptr<ge_p3[]> buckets{new ge_p3[1<<c]};
   std::shared_ptr<pippenger_cached_data> local_cache = cache == NULL ? pippenger_init_cache(data) : cache;
+  std::shared_ptr<pippenger_cached_data> local_cache_2 = data.size() > cache_size ? pippenger_init_cache(data, cache_size) : NULL;
 
   rct::key maxscalar = rct::zero();
   for (size_t i = 0; i < data.size(); ++i)
@@ -641,7 +645,10 @@ rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<
       CHECK_AND_ASSERT_THROW_MES(bucket < (1u<<c), "bucket overflow");
       if (!ge_p3_is_point_at_infinity(&buckets[bucket]))
       {
-        add(buckets[bucket], local_cache->cached[i]);
+        if (i < cache_size)
+          add(buckets[bucket], local_cache->cached[i]);
+        else
+          add(buckets[bucket], local_cache_2->cached[i - cache_size]);
       }
       else
         buckets[bucket] = data[i].point;
diff --git a/src/ringct/multiexp.h b/src/ringct/multiexp.h
index 559ab664a..b52707933 100644
--- a/src/ringct/multiexp.h
+++ b/src/ringct/multiexp.h
@@ -61,10 +61,10 @@ rct::key bos_coster_heap_conv_robust(std::vector<MultiexpData> data);
 std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data, size_t N =0);
 size_t straus_get_cache_size(const std::shared_ptr<straus_cached_data> &cache);
 rct::key straus(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache = NULL, size_t STEP = 0);
-std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t N =0);
+std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t start_offset = 0, size_t N =0);
 size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &cache);
 size_t get_pippenger_c(size_t N);
-rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache = NULL, size_t c = 0);
+rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache = NULL, size_t cache_size = 0, size_t c = 0);
 
 }
 
diff --git a/tests/performance_tests/multiexp.h b/tests/performance_tests/multiexp.h
index b8b87b3a6..b6e86ebd4 100644
--- a/tests/performance_tests/multiexp.h
+++ b/tests/performance_tests/multiexp.h
@@ -78,9 +78,9 @@ public:
       case multiexp_straus_cached:
         return res == straus(data, straus_cache);
       case multiexp_pippenger:
-        return res == pippenger(data, NULL, c);
+        return res == pippenger(data, NULL, 0, c);
       case multiexp_pippenger_cached:
-        return res == pippenger(data, pippenger_cache, c);
+        return res == pippenger(data, pippenger_cache, 0, c);
       default:
         return false;
     }