aboutsummaryrefslogtreecommitdiff
path: root/src/ringct
diff options
context:
space:
mode:
Diffstat (limited to 'src/ringct')
-rw-r--r--src/ringct/CMakeLists.txt2
-rw-r--r--src/ringct/bulletproofs.cc877
-rw-r--r--src/ringct/bulletproofs.h4
-rw-r--r--src/ringct/multiexp.cc665
-rw-r--r--src/ringct/multiexp.h71
-rw-r--r--src/ringct/rctOps.cpp35
-rw-r--r--src/ringct/rctOps.h7
-rw-r--r--src/ringct/rctSigs.cpp335
-rw-r--r--src/ringct/rctSigs.h10
-rw-r--r--src/ringct/rctTypes.cpp88
-rw-r--r--src/ringct/rctTypes.h43
11 files changed, 1801 insertions, 336 deletions
diff --git a/src/ringct/CMakeLists.txt b/src/ringct/CMakeLists.txt
index c8dcdca26..29f166a3b 100644
--- a/src/ringct/CMakeLists.txt
+++ b/src/ringct/CMakeLists.txt
@@ -30,11 +30,13 @@ set(ringct_basic_sources
rctOps.cpp
rctTypes.cpp
rctCryptoOps.c
+ multiexp.cc
bulletproofs.cc)
set(ringct_basic_private_headers
rctOps.h
rctTypes.h
+ multiexp.h
bulletproofs.h)
monero_private_headers(ringct_basic
diff --git a/src/ringct/bulletproofs.cc b/src/ringct/bulletproofs.cc
index fd15ffbc4..abe4ef18d 100644
--- a/src/ringct/bulletproofs.cc
+++ b/src/ringct/bulletproofs.cc
@@ -30,14 +30,17 @@
#include <stdlib.h>
#include <openssl/ssl.h>
+#include <openssl/bn.h>
#include <boost/thread/mutex.hpp>
#include "misc_log_ex.h"
#include "common/perf_timer.h"
+#include "cryptonote_config.h"
extern "C"
{
#include "crypto/crypto-ops.h"
}
#include "rctOps.h"
+#include "multiexp.h"
#include "bulletproofs.h"
#undef MONERO_DEFAULT_LOG_CATEGORY
@@ -47,27 +50,99 @@ extern "C"
#define PERF_TIMER_START_BP(x) PERF_TIMER_START_UNIT(x, 1000000)
+#define STRAUS_SIZE_LIMIT 128
+#define PIPPENGER_SIZE_LIMIT 0
+
namespace rct
{
static rct::key vector_exponent(const rct::keyV &a, const rct::keyV &b);
-static rct::keyV vector_powers(rct::key x, size_t n);
+static rct::keyV vector_powers(const rct::key &x, size_t n);
+static rct::keyV vector_dup(const rct::key &x, size_t n);
static rct::key inner_product(const rct::keyV &a, const rct::keyV &b);
static constexpr size_t maxN = 64;
-static rct::key Hi[maxN], Gi[maxN];
-static ge_dsmp Gprecomp[64], Hprecomp[64];
+static constexpr size_t maxM = BULLETPROOF_MAX_OUTPUTS;
+static rct::key Hi[maxN*maxM], Gi[maxN*maxM];
+static ge_p3 Hi_p3[maxN*maxM], Gi_p3[maxN*maxM];
+static std::shared_ptr<straus_cached_data> straus_HiGi_cache;
+static std::shared_ptr<pippenger_cached_data> pippenger_HiGi_cache;
static const rct::key TWO = { {0x02, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 } };
-static const rct::keyV oneN = vector_powers(rct::identity(), maxN);
+static const rct::key MINUS_ONE = { { 0xec, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 } };
+static const rct::key MINUS_INV_EIGHT = { { 0x74, 0xa4, 0x19, 0x7a, 0xf0, 0x7d, 0x0b, 0xf7, 0x05, 0xc2, 0xda, 0x25, 0x2b, 0x5c, 0x0b, 0x0d, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0a } };
+static const rct::keyV oneN = vector_dup(rct::identity(), maxN);
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)
+{
+ if (HiGi)
+ {
+ 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()));
+ }
+ else
+ return data.size() <= 64 ? straus(data, NULL, 0) : pippenger(data, NULL, get_pippenger_c(data.size()));
+}
+
+static bool is_reduced(const rct::key &scalar)
+{
+ rct::key reduced = scalar;
+ sc_reduce32(reduced.bytes);
+ return scalar == reduced;
+}
+
+static void addKeys_acc_p3(ge_p3 *acc_p3, const rct::key &a, const rct::key &point)
+{
+ ge_p3 p3;
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&p3, point.bytes) == 0, "ge_frombytes_vartime failed");
+ ge_scalarmult_p3(&p3, a.bytes, &p3);
+ ge_cached cached;
+ ge_p3_to_cached(&cached, acc_p3);
+ ge_p1p1 p1;
+ ge_add(&p1, &p3, &cached);
+ ge_p1p1_to_p3(acc_p3, &p1);
+}
+
+static void add_acc_p3(ge_p3 *acc_p3, const rct::key &point)
+{
+ ge_p3 p3;
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&p3, point.bytes) == 0, "ge_frombytes_vartime failed");
+ ge_cached cached;
+ ge_p3_to_cached(&cached, &p3);
+ ge_p1p1 p1;
+ ge_add(&p1, acc_p3, &cached);
+ ge_p1p1_to_p3(acc_p3, &p1);
+}
+
+static void sub_acc_p3(ge_p3 *acc_p3, const rct::key &point)
+{
+ ge_p3 p3;
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&p3, point.bytes) == 0, "ge_frombytes_vartime failed");
+ ge_cached cached;
+ ge_p3_to_cached(&cached, &p3);
+ ge_p1p1 p1;
+ ge_sub(&p1, acc_p3, &cached);
+ ge_p1p1_to_p3(acc_p3, &p1);
+}
+
+static rct::key scalarmultKey(const ge_p3 &P, const rct::key &a)
+{
+ ge_p2 R;
+ ge_scalarmult(&R, a.bytes, &P);
+ rct::key aP;
+ ge_tobytes(aP.bytes, &R);
+ return aP;
+}
+
static rct::key get_exponent(const rct::key &base, size_t idx)
{
static const std::string salt("bulletproof");
std::string hashed = std::string((const char*)base.bytes, sizeof(base)) + salt + tools::get_varint_data(idx);
- return rct::hashToPoint(rct::hash2rct(crypto::cn_fast_hash(hashed.data(), hashed.size())));
+ const rct::key e = rct::hashToPoint(rct::hash2rct(crypto::cn_fast_hash(hashed.data(), hashed.size())));
+ CHECK_AND_ASSERT_THROW_MES(!(e == rct::identity()), "Exponent is point at infinity");
+ return e;
}
static void init_exponents()
@@ -77,13 +152,27 @@ static void init_exponents()
static bool init_done = false;
if (init_done)
return;
- for (size_t i = 0; i < maxN; ++i)
+ std::vector<MultiexpData> data;
+ for (size_t i = 0; i < maxN*maxM; ++i)
{
Hi[i] = get_exponent(rct::H, i * 2);
- rct::precomp(Hprecomp[i], Hi[i]);
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&Hi_p3[i], Hi[i].bytes) == 0, "ge_frombytes_vartime failed");
Gi[i] = get_exponent(rct::H, i * 2 + 1);
- rct::precomp(Gprecomp[i], Gi[i]);
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&Gi_p3[i], Gi[i].bytes) == 0, "ge_frombytes_vartime failed");
+
+ data.push_back({rct::zero(), Gi[i]});
+ data.push_back({rct::zero(), Hi[i]});
}
+
+ straus_HiGi_cache = straus_init_cache(data, STRAUS_SIZE_LIMIT);
+ pippenger_HiGi_cache = pippenger_init_cache(data, 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");
+ MINFO("Straus cache size: " << straus_get_cache_size(straus_HiGi_cache)/1024 << " kB");
+ MINFO("Pippenger cache size: " << pippenger_get_cache_size(pippenger_HiGi_cache)/1024 << " kB");
+ size_t cache_size = (sizeof(Hi)+sizeof(Hi_p3))*2 + straus_get_cache_size(straus_HiGi_cache) + pippenger_get_cache_size(pippenger_HiGi_cache);
+ MINFO("Total cache size: " << cache_size/1024 << "kB");
init_done = true;
}
@@ -91,15 +180,16 @@ static void init_exponents()
static rct::key vector_exponent(const rct::keyV &a, const rct::keyV &b)
{
CHECK_AND_ASSERT_THROW_MES(a.size() == b.size(), "Incompatible sizes of a and b");
- CHECK_AND_ASSERT_THROW_MES(a.size() <= maxN, "Incompatible sizes of a and maxN");
- rct::key res = rct::identity();
+ CHECK_AND_ASSERT_THROW_MES(a.size() <= maxN*maxM, "Incompatible sizes of a and maxN");
+
+ std::vector<MultiexpData> multiexp_data;
+ multiexp_data.reserve(a.size()*2);
for (size_t i = 0; i < a.size(); ++i)
{
- rct::key term;
- rct::addKeys3(term, a[i], Gprecomp[i], b[i], Hprecomp[i]);
- rct::addKeys(res, res, term);
+ multiexp_data.emplace_back(a[i], Gi_p3[i]);
+ multiexp_data.emplace_back(b[i], Hi_p3[i]);
}
- return res;
+ return multiexp(multiexp_data, true);
}
/* Compute a custom vector-scalar commitment */
@@ -108,44 +198,24 @@ static rct::key vector_exponent_custom(const rct::keyV &A, const rct::keyV &B, c
CHECK_AND_ASSERT_THROW_MES(A.size() == B.size(), "Incompatible sizes of A and B");
CHECK_AND_ASSERT_THROW_MES(a.size() == b.size(), "Incompatible sizes of a and b");
CHECK_AND_ASSERT_THROW_MES(a.size() == A.size(), "Incompatible sizes of a and A");
- CHECK_AND_ASSERT_THROW_MES(a.size() <= maxN, "Incompatible sizes of a and maxN");
- rct::key res = rct::identity();
+ CHECK_AND_ASSERT_THROW_MES(a.size() <= maxN*maxM, "Incompatible sizes of a and maxN");
+
+ std::vector<MultiexpData> multiexp_data;
+ multiexp_data.reserve(a.size()*2);
for (size_t i = 0; i < a.size(); ++i)
{
- rct::key term;
-#if 0
- // we happen to know where A and B might fall, so don't bother checking the rest
- ge_dsmp *Acache = NULL, *Bcache = NULL;
- ge_dsmp Acache_custom[1], Bcache_custom[1];
- if (Gi[i] == A[i])
- Acache = Gprecomp + i;
- else if (i<32 && Gi[i+32] == A[i])
- Acache = Gprecomp + i + 32;
- else
- {
- rct::precomp(Acache_custom[0], A[i]);
- Acache = Acache_custom;
- }
- if (i == 0 && B[i] == Hi[0])
- Bcache = Hprecomp;
- else
- {
- rct::precomp(Bcache_custom[0], B[i]);
- Bcache = Bcache_custom;
- }
- rct::addKeys3(term, a[i], *Acache, b[i], *Bcache);
-#else
- ge_dsmp Acache, Bcache;
- rct::precomp(Bcache, B[i]);
- rct::addKeys3(term, a[i], A[i], b[i], Bcache);
-#endif
- rct::addKeys(res, res, term);
+ multiexp_data.resize(multiexp_data.size() + 1);
+ multiexp_data.back().scalar = a[i];
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&multiexp_data.back().point, A[i].bytes) == 0, "ge_frombytes_vartime failed");
+ multiexp_data.resize(multiexp_data.size() + 1);
+ multiexp_data.back().scalar = b[i];
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&multiexp_data.back().point, B[i].bytes) == 0, "ge_frombytes_vartime failed");
}
- return res;
+ return multiexp(multiexp_data, false);
}
/* Given a scalar, construct a vector of powers */
-static rct::keyV vector_powers(rct::key x, size_t n)
+static rct::keyV vector_powers(const rct::key &x, size_t n)
{
rct::keyV res(n);
if (n == 0)
@@ -161,6 +231,24 @@ static rct::keyV vector_powers(rct::key x, size_t n)
return res;
}
+/* Given a scalar, return the sum of its powers from 0 to n-1 */
+static rct::key vector_power_sum(const rct::key &x, size_t n)
+{
+ if (n == 0)
+ return rct::zero();
+ rct::key res = rct::identity();
+ if (n == 1)
+ return res;
+ rct::key prev = x;
+ for (size_t i = 1; i < n; ++i)
+ {
+ if (i > 1)
+ sc_mul(prev.bytes, prev.bytes, x.bytes);
+ sc_add(res.bytes, res.bytes, prev.bytes);
+ }
+ return res;
+}
+
/* Given two scalar arrays, construct the inner product */
static rct::key inner_product(const rct::keyV &a, const rct::keyV &b)
{
@@ -232,6 +320,12 @@ static rct::keyV vector_scalar(const rct::keyV &a, const rct::key &x)
return res;
}
+/* Create a vector from copies of a single value */
+static rct::keyV vector_dup(const rct::key &x, size_t N)
+{
+ return rct::keyV(N, x);
+}
+
/* Exponentiate a curve vector by a scalar */
static rct::keyV vector_scalar2(const rct::keyV &a, const rct::key &x)
{
@@ -243,6 +337,17 @@ static rct::keyV vector_scalar2(const rct::keyV &a, const rct::key &x)
return res;
}
+/* Get the sum of a vector's elements */
+static rct::key vector_sum(const rct::keyV &a)
+{
+ rct::key res = rct::zero();
+ for (size_t i = 0; i < a.size(); ++i)
+ {
+ sc_add(res.bytes, res.bytes, a[i].bytes);
+ }
+ return res;
+}
+
static rct::key switch_endianness(rct::key k)
{
std::reverse(k.bytes, k.bytes + sizeof(k));
@@ -345,6 +450,7 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
PERF_TIMER_START_BP(PROVE_v);
rct::addKeys2(V, gamma, sv, rct::H);
+ V = rct::scalarmultKey(V, INV_EIGHT);
PERF_TIMER_STOP(PROVE_v);
PERF_TIMER_START_BP(PROVE_aLaR);
@@ -380,12 +486,14 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
CHECK_AND_ASSERT_THROW_MES(test_aR == v_test, "test_aR failed");
#endif
+try_again:
PERF_TIMER_START_BP(PROVE_step1);
// PAPER LINES 38-39
rct::key alpha = rct::skGen();
rct::key ve = vector_exponent(aL, aR);
rct::key A;
rct::addKeys(A, ve, rct::scalarmultBase(alpha));
+ A = rct::scalarmultKey(A, INV_EIGHT);
// PAPER LINES 40-42
rct::keyV sL = rct::skvGen(N), sR = rct::skvGen(N);
@@ -393,10 +501,23 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
ve = vector_exponent(sL, sR);
rct::key S;
rct::addKeys(S, ve, rct::scalarmultBase(rho));
+ S = rct::scalarmultKey(S, INV_EIGHT);
// PAPER LINES 43-45
rct::key y = hash_cache_mash(hash_cache, A, S);
+ if (y == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step1);
+ MINFO("y is 0, trying again");
+ goto try_again;
+ }
rct::key z = hash_cache = rct::hash_to_scalar(y);
+ if (z == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step1);
+ MINFO("z is 0, trying again");
+ goto try_again;
+ }
// Polynomial construction before PAPER LINE 46
rct::key t0 = rct::zero();
@@ -405,7 +526,7 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
const auto yN = vector_powers(y, N);
- rct::key ip1y = inner_product(oneN, yN);
+ rct::key ip1y = vector_sum(yN);
rct::key tmp;
sc_muladd(t0.bytes, z.bytes, ip1y.bytes, t0.bytes);
@@ -437,7 +558,7 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
PERF_TIMER_START_BP(PROVE_step2);
const auto HyNsR = hadamard(yN, sR);
- const auto vpIz = vector_scalar(oneN, z);
+ const auto vpIz = vector_dup(z, N);
const auto vp2zsq = vector_scalar(twoN, zsq);
const auto aL_vpIz = vector_subtract(aL, vpIz);
const auto aR_vpIz = vector_add(aR, vpIz);
@@ -454,11 +575,19 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
// PAPER LINES 47-48
rct::key tau1 = rct::skGen(), tau2 = rct::skGen();
- rct::key T1 = rct::addKeys(rct::scalarmultKey(rct::H, t1), rct::scalarmultBase(tau1));
- rct::key T2 = rct::addKeys(rct::scalarmultKey(rct::H, t2), rct::scalarmultBase(tau2));
+ rct::key T1 = rct::addKeys(rct::scalarmultH(t1), rct::scalarmultBase(tau1));
+ T1 = rct::scalarmultKey(T1, INV_EIGHT);
+ rct::key T2 = rct::addKeys(rct::scalarmultH(t2), rct::scalarmultBase(tau2));
+ T2 = rct::scalarmultKey(T2, INV_EIGHT);
// PAPER LINES 49-51
rct::key x = hash_cache_mash(hash_cache, z, T1, T2);
+ if (x == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step2);
+ MINFO("x is 0, trying again");
+ goto try_again;
+ }
// PAPER LINES 52-53
rct::key taux = rct::zero();
@@ -500,7 +629,7 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
for (size_t i = 0; i < N; ++i)
{
Gprime[i] = Gi[i];
- Hprime[i] = scalarmultKey(Hi[i], yinvpow);
+ Hprime[i] = scalarmultKey(Hi_p3[i], yinvpow);
sc_mul(yinvpow.bytes, yinvpow.bytes, yinv.bytes);
aprime[i] = l[i];
bprime[i] = r[i];
@@ -525,13 +654,21 @@ Bulletproof bulletproof_PROVE(const rct::key &sv, const rct::key &gamma)
// PAPER LINES 18-19
L[round] = vector_exponent_custom(slice(Gprime, nprime, Gprime.size()), slice(Hprime, 0, nprime), slice(aprime, 0, nprime), slice(bprime, nprime, bprime.size()));
sc_mul(tmp.bytes, cL.bytes, x_ip.bytes);
- rct::addKeys(L[round], L[round], rct::scalarmultKey(rct::H, tmp));
+ rct::addKeys(L[round], L[round], rct::scalarmultH(tmp));
+ L[round] = rct::scalarmultKey(L[round], INV_EIGHT);
R[round] = vector_exponent_custom(slice(Gprime, 0, nprime), slice(Hprime, nprime, Hprime.size()), slice(aprime, nprime, aprime.size()), slice(bprime, 0, nprime));
sc_mul(tmp.bytes, cR.bytes, x_ip.bytes);
- rct::addKeys(R[round], R[round], rct::scalarmultKey(rct::H, tmp));
+ rct::addKeys(R[round], R[round], rct::scalarmultH(tmp));
+ R[round] = rct::scalarmultKey(R[round], INV_EIGHT);
// PAPER LINES 21-22
w[round] = hash_cache_mash(hash_cache, L[round], R[round]);
+ if (w[round] == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step4);
+ MINFO("w[round] is 0, trying again");
+ goto try_again;
+ }
// PAPER LINES 24-25
const rct::key winv = invert(w[round]);
@@ -567,179 +704,540 @@ Bulletproof bulletproof_PROVE(uint64_t v, const rct::key &gamma)
return bulletproof_PROVE(sv, gamma);
}
-/* Given a range proof, determine if it is valid */
-bool bulletproof_VERIFY(const Bulletproof &proof)
+/* Given a set of values v (0..2^N-1) and masks gamma, construct a range proof */
+Bulletproof bulletproof_PROVE(const rct::keyV &sv, const rct::keyV &gamma)
{
+ CHECK_AND_ASSERT_THROW_MES(sv.size() == gamma.size(), "Incompatible sizes of sv and gamma");
+ CHECK_AND_ASSERT_THROW_MES(!sv.empty(), "sv is empty");
+ for (const rct::key &sve: sv)
+ CHECK_AND_ASSERT_THROW_MES(is_reduced(sve), "Invalid sv input");
+ for (const rct::key &g: gamma)
+ CHECK_AND_ASSERT_THROW_MES(is_reduced(g), "Invalid gamma input");
+
init_exponents();
- CHECK_AND_ASSERT_MES(proof.V.size() == 1, false, "V does not have exactly one element");
- CHECK_AND_ASSERT_MES(proof.L.size() == proof.R.size(), false, "Mismatched L and R sizes");
- CHECK_AND_ASSERT_MES(proof.L.size() > 0, false, "Empty proof");
- CHECK_AND_ASSERT_MES(proof.L.size() == 6, false, "Proof is not for 64 bits");
+ PERF_TIMER_UNIT(PROVE, 1000000);
- const size_t logN = proof.L.size();
- const size_t N = 1 << logN;
+ constexpr size_t logN = 6; // log2(64)
+ constexpr size_t N = 1<<logN;
+ size_t M, logM;
+ for (logM = 0; (M = 1<<logM) <= maxM && M < sv.size(); ++logM);
+ CHECK_AND_ASSERT_THROW_MES(M <= maxM, "sv/gamma are too large");
+ const size_t logMN = logM + logN;
+ const size_t MN = M * N;
+
+ rct::keyV V(sv.size());
+ rct::keyV aL(MN), aR(MN);
+ rct::key tmp;
- // Reconstruct the challenges
- PERF_TIMER_START_BP(VERIFY);
- PERF_TIMER_START_BP(VERIFY_start);
- rct::key hash_cache = rct::hash_to_scalar(proof.V[0]);
- rct::key y = hash_cache_mash(hash_cache, proof.A, proof.S);
+ PERF_TIMER_START_BP(PROVE_v);
+ for (size_t i = 0; i < sv.size(); ++i)
+ {
+ rct::addKeys2(V[i], gamma[i], sv[i], rct::H);
+ V[i] = rct::scalarmultKey(V[i], INV_EIGHT);
+ }
+ PERF_TIMER_STOP(PROVE_v);
+
+ PERF_TIMER_START_BP(PROVE_aLaR);
+ for (size_t j = 0; j < M; ++j)
+ {
+ for (size_t i = N; i-- > 0; )
+ {
+ if (j >= sv.size())
+ {
+ aL[j*N+i] = rct::zero();
+ }
+ else if (sv[j][i/8] & (((uint64_t)1)<<(i%8)))
+ {
+ aL[j*N+i] = rct::identity();
+ }
+ else
+ {
+ aL[j*N+i] = rct::zero();
+ }
+ sc_sub(aR[j*N+i].bytes, aL[j*N+i].bytes, rct::identity().bytes);
+ }
+ }
+ PERF_TIMER_STOP(PROVE_aLaR);
+
+ // DEBUG: Test to ensure this recovers the value
+#ifdef DEBUG_BP
+ for (size_t j = 0; j < M; ++j)
+ {
+ uint64_t test_aL = 0, test_aR = 0;
+ for (size_t i = 0; i < N; ++i)
+ {
+ if (aL[j*N+i] == rct::identity())
+ test_aL += ((uint64_t)1)<<i;
+ if (aR[j*N+i] == rct::zero())
+ test_aR += ((uint64_t)1)<<i;
+ }
+ uint64_t v_test = 0;
+ if (j < sv.size())
+ for (int n = 0; n < 8; ++n) v_test |= (((uint64_t)sv[j][n]) << (8*n));
+ CHECK_AND_ASSERT_THROW_MES(test_aL == v_test, "test_aL failed");
+ CHECK_AND_ASSERT_THROW_MES(test_aR == v_test, "test_aR failed");
+ }
+#endif
+
+try_again:
+ rct::key hash_cache = rct::hash_to_scalar(V);
+
+ PERF_TIMER_START_BP(PROVE_step1);
+ // PAPER LINES 38-39
+ rct::key alpha = rct::skGen();
+ rct::key ve = vector_exponent(aL, aR);
+ rct::key A;
+ rct::addKeys(A, ve, rct::scalarmultBase(alpha));
+ A = rct::scalarmultKey(A, INV_EIGHT);
+
+ // PAPER LINES 40-42
+ rct::keyV sL = rct::skvGen(MN), sR = rct::skvGen(MN);
+ rct::key rho = rct::skGen();
+ ve = vector_exponent(sL, sR);
+ rct::key S;
+ rct::addKeys(S, ve, rct::scalarmultBase(rho));
+ S = rct::scalarmultKey(S, INV_EIGHT);
+
+ // PAPER LINES 43-45
+ rct::key y = hash_cache_mash(hash_cache, A, S);
+ if (y == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step1);
+ MINFO("y is 0, trying again");
+ goto try_again;
+ }
rct::key z = hash_cache = rct::hash_to_scalar(y);
- rct::key x = hash_cache_mash(hash_cache, z, proof.T1, proof.T2);
- PERF_TIMER_STOP(VERIFY_start);
+ if (z == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step1);
+ MINFO("z is 0, trying again");
+ goto try_again;
+ }
- PERF_TIMER_START_BP(VERIFY_line_60);
- // Reconstruct the challenges
- rct::key x_ip = hash_cache_mash(hash_cache, x, proof.taux, proof.mu, proof.t);
- PERF_TIMER_STOP(VERIFY_line_60);
+ // Polynomial construction by coefficients
+ const auto zMN = vector_dup(z, MN);
+ rct::keyV l0 = vector_subtract(aL, zMN);
+ const rct::keyV &l1 = sL;
- PERF_TIMER_START_BP(VERIFY_line_61);
- // PAPER LINE 61
- rct::key L61Left = rct::addKeys(rct::scalarmultBase(proof.taux), rct::scalarmultKey(rct::H, proof.t));
+ // This computes the ugly sum/concatenation from PAPER LINE 65
+ rct::keyV zero_twos(MN);
+ const rct::keyV zpow = vector_powers(z, M+2);
+ for (size_t i = 0; i < MN; ++i)
+ {
+ zero_twos[i] = rct::zero();
+ for (size_t j = 1; j <= M; ++j)
+ {
+ if (i >= (j-1)*N && i < j*N)
+ {
+ CHECK_AND_ASSERT_THROW_MES(1+j < zpow.size(), "invalid zpow index");
+ CHECK_AND_ASSERT_THROW_MES(i-(j-1)*N < twoN.size(), "invalid twoN index");
+ sc_muladd(zero_twos[i].bytes, zpow[1+j].bytes, twoN[i-(j-1)*N].bytes, zero_twos[i].bytes);
+ }
+ }
+ }
- rct::key k = rct::zero();
- const auto yN = vector_powers(y, N);
- rct::key ip1y = inner_product(oneN, yN);
- rct::key zsq;
- sc_mul(zsq.bytes, z.bytes, z.bytes);
- rct::key tmp, tmp2;
- sc_mulsub(k.bytes, zsq.bytes, ip1y.bytes, k.bytes);
- rct::key zcu;
- sc_mul(zcu.bytes, zsq.bytes, z.bytes);
- sc_mulsub(k.bytes, zcu.bytes, ip12.bytes, k.bytes);
- PERF_TIMER_STOP(VERIFY_line_61);
+ rct::keyV r0 = vector_add(aR, zMN);
+ const auto yMN = vector_powers(y, MN);
+ r0 = hadamard(r0, yMN);
+ r0 = vector_add(r0, zero_twos);
+ rct::keyV r1 = hadamard(yMN, sR);
- PERF_TIMER_START_BP(VERIFY_line_61rl);
- sc_muladd(tmp.bytes, z.bytes, ip1y.bytes, k.bytes);
- rct::key L61Right = rct::scalarmultKey(rct::H, tmp);
+ // Polynomial construction before PAPER LINE 46
+ rct::key t1_1 = inner_product(l0, r1);
+ rct::key t1_2 = inner_product(l1, r0);
+ rct::key t1;
+ sc_add(t1.bytes, t1_1.bytes, t1_2.bytes);
+ rct::key t2 = inner_product(l1, r1);
- CHECK_AND_ASSERT_MES(proof.V.size() == 1, false, "proof.V does not have exactly one element");
- tmp = rct::scalarmultKey(proof.V[0], zsq);
- rct::addKeys(L61Right, L61Right, tmp);
+ PERF_TIMER_STOP(PROVE_step1);
- tmp = rct::scalarmultKey(proof.T1, x);
- rct::addKeys(L61Right, L61Right, tmp);
+ PERF_TIMER_START_BP(PROVE_step2);
+ // PAPER LINES 47-48
+ rct::key tau1 = rct::skGen(), tau2 = rct::skGen();
+
+ rct::key T1 = rct::addKeys(rct::scalarmultH(t1), rct::scalarmultBase(tau1));
+ T1 = rct::scalarmultKey(T1, INV_EIGHT);
+ rct::key T2 = rct::addKeys(rct::scalarmultH(t2), rct::scalarmultBase(tau2));
+ T2 = rct::scalarmultKey(T2, INV_EIGHT);
+ // PAPER LINES 49-51
+ rct::key x = hash_cache_mash(hash_cache, z, T1, T2);
+ if (x == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step2);
+ MINFO("x is 0, trying again");
+ goto try_again;
+ }
+
+ // PAPER LINES 52-53
+ rct::key taux;
+ sc_mul(taux.bytes, tau1.bytes, x.bytes);
rct::key xsq;
sc_mul(xsq.bytes, x.bytes, x.bytes);
- tmp = rct::scalarmultKey(proof.T2, xsq);
- rct::addKeys(L61Right, L61Right, tmp);
- PERF_TIMER_STOP(VERIFY_line_61rl);
-
- if (!(L61Right == L61Left))
+ sc_muladd(taux.bytes, tau2.bytes, xsq.bytes, taux.bytes);
+ for (size_t j = 1; j <= sv.size(); ++j)
{
- MERROR("Verification failure at step 1");
- return false;
+ CHECK_AND_ASSERT_THROW_MES(j+1 < zpow.size(), "invalid zpow index");
+ sc_muladd(taux.bytes, zpow[j+1].bytes, gamma[j-1].bytes, taux.bytes);
}
+ rct::key mu;
+ sc_muladd(mu.bytes, x.bytes, rho.bytes, alpha.bytes);
- PERF_TIMER_START_BP(VERIFY_line_62);
- // PAPER LINE 62
- rct::key P = rct::addKeys(proof.A, rct::scalarmultKey(proof.S, x));
- PERF_TIMER_STOP(VERIFY_line_62);
+ // PAPER LINES 54-57
+ rct::keyV l = l0;
+ l = vector_add(l, vector_scalar(l1, x));
+ rct::keyV r = r0;
+ r = vector_add(r, vector_scalar(r1, x));
+ PERF_TIMER_STOP(PROVE_step2);
- // Compute the number of rounds for the inner product
- const size_t rounds = proof.L.size();
- CHECK_AND_ASSERT_MES(rounds > 0, false, "Zero rounds");
+ PERF_TIMER_START_BP(PROVE_step3);
+ rct::key t = inner_product(l, r);
- PERF_TIMER_START_BP(VERIFY_line_21_22);
- // PAPER LINES 21-22
- // The inner product challenges are computed per round
- rct::keyV w(rounds);
- for (size_t i = 0; i < rounds; ++i)
+ // DEBUG: Test if the l and r vectors match the polynomial forms
+#ifdef DEBUG_BP
+ rct::key test_t;
+ const rct::key t0 = inner_product(l0, r0);
+ sc_muladd(test_t.bytes, t1.bytes, x.bytes, t0.bytes);
+ sc_muladd(test_t.bytes, t2.bytes, xsq.bytes, test_t.bytes);
+ CHECK_AND_ASSERT_THROW_MES(test_t == t, "test_t check failed");
+#endif
+
+ // PAPER LINES 32-33
+ rct::key x_ip = hash_cache_mash(hash_cache, x, taux, mu, t);
+ if (x_ip == rct::zero())
{
- w[i] = hash_cache_mash(hash_cache, proof.L[i], proof.R[i]);
+ PERF_TIMER_STOP(PROVE_step3);
+ MINFO("x_ip is 0, trying again");
+ goto try_again;
}
- PERF_TIMER_STOP(VERIFY_line_21_22);
- PERF_TIMER_START_BP(VERIFY_line_24_25);
- // Basically PAPER LINES 24-25
- // Compute the curvepoints from G[i] and H[i]
- rct::key inner_prod = rct::identity();
+ // These are used in the inner product rounds
+ size_t nprime = MN;
+ rct::keyV Gprime(MN);
+ rct::keyV Hprime(MN);
+ rct::keyV aprime(MN);
+ rct::keyV bprime(MN);
+ const rct::key yinv = invert(y);
rct::key yinvpow = rct::identity();
- rct::key ypow = rct::identity();
+ for (size_t i = 0; i < MN; ++i)
+ {
+ Gprime[i] = Gi[i];
+ Hprime[i] = scalarmultKey(Hi_p3[i], yinvpow);
+ sc_mul(yinvpow.bytes, yinvpow.bytes, yinv.bytes);
+ aprime[i] = l[i];
+ bprime[i] = r[i];
+ }
+ rct::keyV L(logMN);
+ rct::keyV R(logMN);
+ int round = 0;
+ rct::keyV w(logMN); // this is the challenge x in the inner product protocol
+ PERF_TIMER_STOP(PROVE_step3);
- PERF_TIMER_START_BP(VERIFY_line_24_25_invert);
- const rct::key yinv = invert(y);
- rct::keyV winv(rounds);
- for (size_t i = 0; i < rounds; ++i)
- winv[i] = invert(w[i]);
- PERF_TIMER_STOP(VERIFY_line_24_25_invert);
+ PERF_TIMER_START_BP(PROVE_step4);
+ // PAPER LINE 13
+ while (nprime > 1)
+ {
+ // PAPER LINE 15
+ nprime /= 2;
- for (size_t i = 0; i < N; ++i)
+ // PAPER LINES 16-17
+ rct::key cL = inner_product(slice(aprime, 0, nprime), slice(bprime, nprime, bprime.size()));
+ rct::key cR = inner_product(slice(aprime, nprime, aprime.size()), slice(bprime, 0, nprime));
+
+ // PAPER LINES 18-19
+ L[round] = vector_exponent_custom(slice(Gprime, nprime, Gprime.size()), slice(Hprime, 0, nprime), slice(aprime, 0, nprime), slice(bprime, nprime, bprime.size()));
+ sc_mul(tmp.bytes, cL.bytes, x_ip.bytes);
+ rct::addKeys(L[round], L[round], rct::scalarmultH(tmp));
+ L[round] = rct::scalarmultKey(L[round], INV_EIGHT);
+ R[round] = vector_exponent_custom(slice(Gprime, 0, nprime), slice(Hprime, nprime, Hprime.size()), slice(aprime, nprime, aprime.size()), slice(bprime, 0, nprime));
+ sc_mul(tmp.bytes, cR.bytes, x_ip.bytes);
+ rct::addKeys(R[round], R[round], rct::scalarmultH(tmp));
+ R[round] = rct::scalarmultKey(R[round], INV_EIGHT);
+
+ // PAPER LINES 21-22
+ w[round] = hash_cache_mash(hash_cache, L[round], R[round]);
+ if (w[round] == rct::zero())
+ {
+ PERF_TIMER_STOP(PROVE_step4);
+ MINFO("w[round] is 0, trying again");
+ goto try_again;
+ }
+
+ // PAPER LINES 24-25
+ const rct::key winv = invert(w[round]);
+ Gprime = hadamard2(vector_scalar2(slice(Gprime, 0, nprime), winv), vector_scalar2(slice(Gprime, nprime, Gprime.size()), w[round]));
+ Hprime = hadamard2(vector_scalar2(slice(Hprime, 0, nprime), w[round]), vector_scalar2(slice(Hprime, nprime, Hprime.size()), winv));
+
+ // PAPER LINES 28-29
+ aprime = vector_add(vector_scalar(slice(aprime, 0, nprime), w[round]), vector_scalar(slice(aprime, nprime, aprime.size()), winv));
+ bprime = vector_add(vector_scalar(slice(bprime, 0, nprime), winv), vector_scalar(slice(bprime, nprime, bprime.size()), w[round]));
+
+ ++round;
+ }
+ PERF_TIMER_STOP(PROVE_step4);
+
+ // PAPER LINE 58 (with inclusions from PAPER LINE 8 and PAPER LINE 20)
+ return Bulletproof(V, A, S, T1, T2, taux, mu, L, R, aprime[0], bprime[0], t);
+}
+
+Bulletproof bulletproof_PROVE(const std::vector<uint64_t> &v, const rct::keyV &gamma)
+{
+ CHECK_AND_ASSERT_THROW_MES(v.size() == gamma.size(), "Incompatible sizes of v and gamma");
+
+ // vG + gammaH
+ PERF_TIMER_START_BP(PROVE_v);
+ rct::keyV sv(v.size());
+ for (size_t i = 0; i < v.size(); ++i)
{
- // Convert the index to binary IN REVERSE and construct the scalar exponent
- rct::key g_scalar = proof.a;
- rct::key h_scalar;
- sc_mul(h_scalar.bytes, proof.b.bytes, yinvpow.bytes);
+ sv[i] = rct::zero();
+ sv[i].bytes[0] = v[i] & 255;
+ sv[i].bytes[1] = (v[i] >> 8) & 255;
+ sv[i].bytes[2] = (v[i] >> 16) & 255;
+ sv[i].bytes[3] = (v[i] >> 24) & 255;
+ sv[i].bytes[4] = (v[i] >> 32) & 255;
+ sv[i].bytes[5] = (v[i] >> 40) & 255;
+ sv[i].bytes[6] = (v[i] >> 48) & 255;
+ sv[i].bytes[7] = (v[i] >> 56) & 255;
+ }
+ PERF_TIMER_STOP(PROVE_v);
+ return bulletproof_PROVE(sv, gamma);
+}
+
+/* Given a range proof, determine if it is valid */
+bool bulletproof_VERIFY(const std::vector<const Bulletproof*> &proofs)
+{
+ init_exponents();
+
+ PERF_TIMER_START_BP(VERIFY);
+
+ // sanity and figure out which proof is longest
+ size_t max_length = 0;
+ for (const Bulletproof *p: proofs)
+ {
+ const Bulletproof &proof = *p;
+
+ // check scalar range
+ CHECK_AND_ASSERT_MES(is_reduced(proof.taux), false, "Input scalar not in range");
+ CHECK_AND_ASSERT_MES(is_reduced(proof.mu), false, "Input scalar not in range");
+ CHECK_AND_ASSERT_MES(is_reduced(proof.a), false, "Input scalar not in range");
+ CHECK_AND_ASSERT_MES(is_reduced(proof.b), false, "Input scalar not in range");
+ CHECK_AND_ASSERT_MES(is_reduced(proof.t), false, "Input scalar not in range");
+
+ CHECK_AND_ASSERT_MES(proof.V.size() >= 1, false, "V does not have at least one element");
+ CHECK_AND_ASSERT_MES(proof.L.size() == proof.R.size(), false, "Mismatched L and R sizes");
+ CHECK_AND_ASSERT_MES(proof.L.size() > 0, false, "Empty proof");
- for (size_t j = rounds; j-- > 0; )
+ max_length = std::max(max_length, proof.L.size());
+ }
+ CHECK_AND_ASSERT_MES(max_length < 32, false, "At least one proof is too large");
+ size_t maxMN = 1u << max_length;
+
+ const size_t logN = 6;
+ const size_t N = 1 << logN;
+ rct::key tmp;
+
+ // setup weighted aggregates
+ rct::key Z0 = rct::identity();
+ rct::key z1 = rct::zero();
+ rct::key Z2 = rct::identity();
+ rct::key z3 = rct::zero();
+ rct::keyV z4(maxMN, rct::zero()), z5(maxMN, rct::zero());
+ rct::key Y2 = rct::identity(), Y3 = rct::identity(), Y4 = rct::identity();
+ rct::key y0 = rct::zero(), y1 = rct::zero();
+ for (const Bulletproof *p: proofs)
+ {
+ const Bulletproof &proof = *p;
+
+ size_t M, logM;
+ for (logM = 0; (M = 1<<logM) <= maxM && M < proof.V.size(); ++logM);
+ CHECK_AND_ASSERT_MES(proof.L.size() == 6+logM, false, "Proof is not the expected size");
+ const size_t MN = M*N;
+ rct::key weight = rct::skGen();
+
+ // Reconstruct the challenges
+ PERF_TIMER_START_BP(VERIFY_start);
+ rct::key hash_cache = rct::hash_to_scalar(proof.V);
+ rct::key y = hash_cache_mash(hash_cache, proof.A, proof.S);
+ CHECK_AND_ASSERT_MES(!(y == rct::zero()), false, "y == 0");
+ rct::key z = hash_cache = rct::hash_to_scalar(y);
+ CHECK_AND_ASSERT_MES(!(z == rct::zero()), false, "z == 0");
+ rct::key x = hash_cache_mash(hash_cache, z, proof.T1, proof.T2);
+ CHECK_AND_ASSERT_MES(!(x == rct::zero()), false, "x == 0");
+ rct::key x_ip = hash_cache_mash(hash_cache, x, proof.taux, proof.mu, proof.t);
+ CHECK_AND_ASSERT_MES(!(x_ip == rct::zero()), false, "x_ip == 0");
+ PERF_TIMER_STOP(VERIFY_start);
+
+ PERF_TIMER_START_BP(VERIFY_line_61);
+ // PAPER LINE 61
+ sc_muladd(y0.bytes, proof.taux.bytes, weight.bytes, y0.bytes);
+
+ const rct::keyV zpow = vector_powers(z, M+3);
+
+ rct::key k;
+ const rct::key ip1y = vector_power_sum(y, MN);
+ sc_mulsub(k.bytes, zpow[2].bytes, ip1y.bytes, rct::zero().bytes);
+ for (size_t j = 1; j <= M; ++j)
+ {
+ CHECK_AND_ASSERT_MES(j+2 < zpow.size(), false, "invalid zpow index");
+ sc_mulsub(k.bytes, zpow[j+2].bytes, ip12.bytes, k.bytes);
+ }
+ PERF_TIMER_STOP(VERIFY_line_61);
+
+ PERF_TIMER_START_BP(VERIFY_line_61rl_new);
+ sc_muladd(tmp.bytes, z.bytes, ip1y.bytes, k.bytes);
+ std::vector<MultiexpData> multiexp_data;
+ multiexp_data.reserve(proof.V.size());
+ sc_sub(tmp.bytes, proof.t.bytes, tmp.bytes);
+ sc_muladd(y1.bytes, tmp.bytes, weight.bytes, y1.bytes);
+ for (size_t j = 0; j < proof.V.size(); j++)
{
- size_t J = w.size() - j - 1;
+ sc_mul(tmp.bytes, zpow[j+2].bytes, EIGHT.bytes);
+ multiexp_data.emplace_back(tmp, proof.V[j]);
+ }
+ rct::addKeys(Y2, Y2, rct::scalarmultKey(multiexp(multiexp_data, false), weight));
+ rct::key weight8;
+ sc_mul(weight8.bytes, weight.bytes, EIGHT.bytes);
+ sc_mul(tmp.bytes, x.bytes, weight8.bytes);
+ rct::addKeys(Y3, Y3, rct::scalarmultKey(proof.T1, tmp));
+ rct::key xsq;
+ sc_mul(xsq.bytes, x.bytes, x.bytes);
+ sc_mul(tmp.bytes, xsq.bytes, weight8.bytes);
+ rct::addKeys(Y4, Y4, rct::scalarmultKey(proof.T2, tmp));
+ PERF_TIMER_STOP(VERIFY_line_61rl_new);
+
+ PERF_TIMER_START_BP(VERIFY_line_62);
+ // PAPER LINE 62
+ sc_mul(tmp.bytes, x.bytes, EIGHT.bytes);
+ rct::addKeys(Z0, Z0, rct::scalarmultKey(rct::addKeys(rct::scalarmult8(proof.A), rct::scalarmultKey(proof.S, tmp)), weight));
+ PERF_TIMER_STOP(VERIFY_line_62);
+
+ // Compute the number of rounds for the inner product
+ const size_t rounds = logM+logN;
+ CHECK_AND_ASSERT_MES(rounds > 0, false, "Zero rounds");
+
+ PERF_TIMER_START_BP(VERIFY_line_21_22);
+ // PAPER LINES 21-22
+ // The inner product challenges are computed per round
+ rct::keyV w(rounds);
+ for (size_t i = 0; i < rounds; ++i)
+ {
+ w[i] = hash_cache_mash(hash_cache, proof.L[i], proof.R[i]);
+ CHECK_AND_ASSERT_MES(!(w[i] == rct::zero()), false, "w[i] == 0");
+ }
+ PERF_TIMER_STOP(VERIFY_line_21_22);
+
+ PERF_TIMER_START_BP(VERIFY_line_24_25);
+ // Basically PAPER LINES 24-25
+ // Compute the curvepoints from G[i] and H[i]
+ rct::key yinvpow = rct::identity();
+ rct::key ypow = rct::identity();
+
+ PERF_TIMER_START_BP(VERIFY_line_24_25_invert);
+ const rct::key yinv = invert(y);
+ rct::keyV winv(rounds);
+ for (size_t i = 0; i < rounds; ++i)
+ winv[i] = invert(w[i]);
+ PERF_TIMER_STOP(VERIFY_line_24_25_invert);
+
+ for (size_t i = 0; i < MN; ++i)
+ {
+ // Convert the index to binary IN REVERSE and construct the scalar exponent
+ rct::key g_scalar = proof.a;
+ rct::key h_scalar;
+ sc_mul(h_scalar.bytes, proof.b.bytes, yinvpow.bytes);
- if ((i & (((size_t)1)<<j)) == 0)
+ for (size_t j = rounds; j-- > 0; )
{
- sc_mul(g_scalar.bytes, g_scalar.bytes, winv[J].bytes);
- sc_mul(h_scalar.bytes, h_scalar.bytes, w[J].bytes);
+ size_t J = w.size() - j - 1;
+
+ if ((i & (((size_t)1)<<j)) == 0)
+ {
+ sc_mul(g_scalar.bytes, g_scalar.bytes, winv[J].bytes);
+ sc_mul(h_scalar.bytes, h_scalar.bytes, w[J].bytes);
+ }
+ else
+ {
+ sc_mul(g_scalar.bytes, g_scalar.bytes, w[J].bytes);
+ sc_mul(h_scalar.bytes, h_scalar.bytes, winv[J].bytes);
+ }
}
- else
+
+ // Adjust the scalars using the exponents from PAPER LINE 62
+ sc_add(g_scalar.bytes, g_scalar.bytes, z.bytes);
+ CHECK_AND_ASSERT_MES(2+i/N < zpow.size(), false, "invalid zpow index");
+ CHECK_AND_ASSERT_MES(i%N < twoN.size(), false, "invalid twoN index");
+ sc_mul(tmp.bytes, zpow[2+i/N].bytes, twoN[i%N].bytes);
+ sc_muladd(tmp.bytes, z.bytes, ypow.bytes, tmp.bytes);
+ sc_mulsub(h_scalar.bytes, tmp.bytes, yinvpow.bytes, h_scalar.bytes);
+
+ sc_muladd(z4[i].bytes, g_scalar.bytes, weight.bytes, z4[i].bytes);
+ sc_muladd(z5[i].bytes, h_scalar.bytes, weight.bytes, z5[i].bytes);
+
+ if (i != MN-1)
{
- sc_mul(g_scalar.bytes, g_scalar.bytes, w[J].bytes);
- sc_mul(h_scalar.bytes, h_scalar.bytes, winv[J].bytes);
+ sc_mul(yinvpow.bytes, yinvpow.bytes, yinv.bytes);
+ sc_mul(ypow.bytes, ypow.bytes, y.bytes);
}
}
- // Adjust the scalars using the exponents from PAPER LINE 62
- sc_add(g_scalar.bytes, g_scalar.bytes, z.bytes);
- sc_mul(tmp.bytes, zsq.bytes, twoN[i].bytes);
- sc_muladd(tmp.bytes, z.bytes, ypow.bytes, tmp.bytes);
- sc_mulsub(h_scalar.bytes, tmp.bytes, yinvpow.bytes, h_scalar.bytes);
+ PERF_TIMER_STOP(VERIFY_line_24_25);
- // Now compute the basepoint's scalar multiplication
- // Each of these could be written as a multiexp operation instead
- rct::addKeys3(tmp, g_scalar, Gprecomp[i], h_scalar, Hprecomp[i]);
- rct::addKeys(inner_prod, inner_prod, tmp);
+ // PAPER LINE 26
+ PERF_TIMER_START_BP(VERIFY_line_26_new);
+ multiexp_data.clear();
+ multiexp_data.reserve(2*rounds);
- if (i != N-1)
+ sc_muladd(z1.bytes, proof.mu.bytes, weight.bytes, z1.bytes);
+ for (size_t i = 0; i < rounds; ++i)
{
- sc_mul(yinvpow.bytes, yinvpow.bytes, yinv.bytes);
- sc_mul(ypow.bytes, ypow.bytes, y.bytes);
+ sc_mul(tmp.bytes, w[i].bytes, w[i].bytes);
+ sc_mul(tmp.bytes, tmp.bytes, EIGHT.bytes);
+ multiexp_data.emplace_back(tmp, proof.L[i]);
+ sc_mul(tmp.bytes, winv[i].bytes, winv[i].bytes);
+ sc_mul(tmp.bytes, tmp.bytes, EIGHT.bytes);
+ multiexp_data.emplace_back(tmp, proof.R[i]);
}
+ rct::key acc = multiexp(multiexp_data, false);
+ rct::addKeys(Z2, Z2, rct::scalarmultKey(acc, weight));
+ sc_mulsub(tmp.bytes, proof.a.bytes, proof.b.bytes, proof.t.bytes);
+ sc_mul(tmp.bytes, tmp.bytes, x_ip.bytes);
+ sc_muladd(z3.bytes, tmp.bytes, weight.bytes, z3.bytes);
+ PERF_TIMER_STOP(VERIFY_line_26_new);
}
- PERF_TIMER_STOP(VERIFY_line_24_25);
-
- PERF_TIMER_START_BP(VERIFY_line_26);
- // PAPER LINE 26
- rct::key pprime;
- sc_sub(tmp.bytes, rct::zero().bytes, proof.mu.bytes);
- rct::addKeys(pprime, P, rct::scalarmultBase(tmp));
-
- for (size_t i = 0; i < rounds; ++i)
- {
- sc_mul(tmp.bytes, w[i].bytes, w[i].bytes);
- sc_mul(tmp2.bytes, winv[i].bytes, winv[i].bytes);
-#if 1
- ge_dsmp cacheL, cacheR;
- rct::precomp(cacheL, proof.L[i]);
- rct::precomp(cacheR, proof.R[i]);
- rct::addKeys3(tmp, tmp, cacheL, tmp2, cacheR);
- rct::addKeys(pprime, pprime, tmp);
-#else
- rct::addKeys(pprime, pprime, rct::scalarmultKey(proof.L[i], tmp));
- rct::addKeys(pprime, pprime, rct::scalarmultKey(proof.R[i], tmp2));
-#endif
- }
- sc_mul(tmp.bytes, proof.t.bytes, x_ip.bytes);
- rct::addKeys(pprime, pprime, rct::scalarmultKey(rct::H, tmp));
- PERF_TIMER_STOP(VERIFY_line_26);
+ // now check all proofs at once
PERF_TIMER_START_BP(VERIFY_step2_check);
- sc_mul(tmp.bytes, proof.a.bytes, proof.b.bytes);
- sc_mul(tmp.bytes, tmp.bytes, x_ip.bytes);
- tmp = rct::scalarmultKey(rct::H, tmp);
- rct::addKeys(tmp, tmp, inner_prod);
+ ge_p3 check1;
+ ge_scalarmult_base(&check1, y0.bytes);
+ addKeys_acc_p3(&check1, y1, rct::H);
+ sub_acc_p3(&check1, Y2);
+ sub_acc_p3(&check1, Y3);
+ sub_acc_p3(&check1, Y4);
+ if (!ge_p3_is_point_at_infinity(&check1))
+ {
+ MERROR("Verification failure at step 1");
+ return false;
+ }
+ ge_p3 check2;
+ sc_sub(tmp.bytes, rct::zero().bytes, z1.bytes);
+ ge_double_scalarmult_base_vartime_p3(&check2, z3.bytes, &ge_p3_H, tmp.bytes);
+ add_acc_p3(&check2, Z0);
+ add_acc_p3(&check2, Z2);
+
+ std::vector<MultiexpData> multiexp_data;
+ multiexp_data.reserve(2 * maxMN);
+ for (size_t i = 0; i < maxMN; ++i)
+ {
+ sc_sub(tmp.bytes, rct::zero().bytes, z4[i].bytes);
+ multiexp_data.emplace_back(tmp, Gi_p3[i]);
+ sc_sub(tmp.bytes, rct::zero().bytes, z5[i].bytes);
+ multiexp_data.emplace_back(tmp, Hi_p3[i]);
+ }
+ add_acc_p3(&check2, multiexp(multiexp_data, true));
PERF_TIMER_STOP(VERIFY_step2_check);
- if (!(pprime == tmp))
+
+ if (!ge_p3_is_point_at_infinity(&check2))
{
MERROR("Verification failure at step 2");
return false;
@@ -749,4 +1247,19 @@ bool bulletproof_VERIFY(const Bulletproof &proof)
return true;
}
+bool bulletproof_VERIFY(const std::vector<Bulletproof> &proofs)
+{
+ std::vector<const Bulletproof*> proof_pointers;
+ for (const Bulletproof &proof: proofs)
+ proof_pointers.push_back(&proof);
+ return bulletproof_VERIFY(proof_pointers);
+}
+
+bool bulletproof_VERIFY(const Bulletproof &proof)
+{
+ std::vector<const Bulletproof*> proofs;
+ proofs.push_back(&proof);
+ return bulletproof_VERIFY(proofs);
+}
+
}
diff --git a/src/ringct/bulletproofs.h b/src/ringct/bulletproofs.h
index 3061d272e..b86202ccc 100644
--- a/src/ringct/bulletproofs.h
+++ b/src/ringct/bulletproofs.h
@@ -40,7 +40,11 @@ namespace rct
Bulletproof bulletproof_PROVE(const rct::key &v, const rct::key &gamma);
Bulletproof bulletproof_PROVE(uint64_t v, const rct::key &gamma);
+Bulletproof bulletproof_PROVE(const rct::keyV &v, const rct::keyV &gamma);
+Bulletproof bulletproof_PROVE(const std::vector<uint64_t> &v, const rct::keyV &gamma);
bool bulletproof_VERIFY(const Bulletproof &proof);
+bool bulletproof_VERIFY(const std::vector<const Bulletproof*> &proofs);
+bool bulletproof_VERIFY(const std::vector<Bulletproof> &proofs);
}
diff --git a/src/ringct/multiexp.cc b/src/ringct/multiexp.cc
new file mode 100644
index 000000000..21957b94c
--- /dev/null
+++ b/src/ringct/multiexp.cc
@@ -0,0 +1,665 @@
+// Copyright (c) 2017, The Monero Project
+//
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without modification, are
+// permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice, this list of
+// conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice, this list
+// of conditions and the following disclaimer in the documentation and/or other
+// materials provided with the distribution.
+//
+// 3. Neither the name of the copyright holder nor the names of its contributors may be
+// used to endorse or promote products derived from this software without specific
+// prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// 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.
+//
+// Adapted from Python code by Sarang Noether
+
+#include "misc_log_ex.h"
+#include "common/perf_timer.h"
+extern "C"
+{
+#include "crypto/crypto-ops.h"
+}
+#include "common/aligned.h"
+#include "rctOps.h"
+#include "multiexp.h"
+
+#undef MONERO_DEFAULT_LOG_CATEGORY
+#define MONERO_DEFAULT_LOG_CATEGORY "multiexp"
+
+//#define MULTIEXP_PERF(x) x
+#define MULTIEXP_PERF(x)
+
+#define RAW_MEMORY_BLOCK
+//#define ALTERNATE_LAYOUT
+//#define TRACK_STRAUS_ZERO_IDENTITY
+
+// per points us for N/B points (B point bands)
+// raw alt 128/192 4096/192 4096/4096
+// 0 0 52.6 71 71.2
+// 0 1 53.2 72.2 72.4
+// 1 0 52.7 67 67.1
+// 1 1 52.8 70.4 70.2
+
+// Pippenger:
+// 1 2 3 4 5 6 7 8 9 bestN
+// 2 555 598 621 804 1038 1733 2486 5020 8304 1
+// 4 783 747 800 1006 1428 2132 3285 5185 9806 2
+// 8 1174 1071 1095 1286 1640 2398 3869 6378 12080 2
+// 16 2279 1874 1745 1739 2144 2831 4209 6964 12007 4
+// 32 3910 3706 2588 2477 2782 3467 4856 7489 12618 4
+// 64 7184 5429 4710 4368 4010 4672 6027 8559 13684 5
+// 128 14097 10574 8452 7297 6841 6718 8615 10580 15641 6
+// 256 27715 20800 16000 13550 11875 11400 11505 14090 18460 6
+// 512 55100 41250 31740 26570 22030 19830 20760 21380 25215 6
+// 1024 111520 79000 61080 49720 43080 38320 37600 35040 36750 8
+// 2048 219480 162680 122120 102080 83760 70360 66600 63920 66160 8
+// 4096 453320 323080 247240 210200 180040 150240 132440 114920 110560 9
+
+// 2 4 8 16 32 64 128 256 512 1024 2048 4096
+// Bos Coster 858 994 1316 1949 3183 5512 9865 17830 33485 63160 124280 246320
+// Straus 226 341 548 980 1870 3538 7039 14490 29020 57200 118640 233640
+// Straus/cached 226 315 485 785 1514 2858 5753 11065 22970 45120 98880 194840
+// Pippenger 555 747 1071 1739 2477 4010 6718 11400 19830 35040 63920 110560
+
+// Best/cached Straus Straus Straus Straus Straus Straus Straus Straus Pip Pip Pip Pip
+// Best/uncached Straus Straus Straus Straus Straus Straus Pip Pip Pip Pip Pip Pip
+
+namespace rct
+{
+
+static inline bool operator<(const rct::key &k0, const rct::key&k1)
+{
+ for (int n = 31; n >= 0; --n)
+ {
+ if (k0.bytes[n] < k1.bytes[n])
+ return true;
+ if (k0.bytes[n] > k1.bytes[n])
+ return false;
+ }
+ return false;
+}
+
+static inline rct::key div2(const rct::key &k)
+{
+ rct::key res;
+ int carry = 0;
+ for (int n = 31; n >= 0; --n)
+ {
+ int new_carry = (k.bytes[n] & 1) << 7;
+ res.bytes[n] = k.bytes[n] / 2 + carry;
+ carry = new_carry;
+ }
+ return res;
+}
+
+static inline rct::key pow2(size_t n)
+{
+ CHECK_AND_ASSERT_THROW_MES(n < 256, "Invalid pow2 argument");
+ rct::key res = rct::zero();
+ res[n >> 3] |= 1<<(n&7);
+ return res;
+}
+
+static inline int test(const rct::key &k, size_t n)
+{
+ if (n >= 256) return 0;
+ return k[n >> 3] & (1 << (n & 7));
+}
+
+static inline void add(ge_p3 &p3, const ge_cached &other)
+{
+ ge_p1p1 p1;
+ ge_add(&p1, &p3, &other);
+ ge_p1p1_to_p3(&p3, &p1);
+}
+
+static inline void add(ge_p3 &p3, const ge_p3 &other)
+{
+ ge_cached cached;
+ ge_p3_to_cached(&cached, &other);
+ add(p3, cached);
+}
+
+rct::key bos_coster_heap_conv(std::vector<MultiexpData> data)
+{
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(bos_coster, 1000000));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(setup, 1000000));
+ size_t points = data.size();
+ CHECK_AND_ASSERT_THROW_MES(points > 1, "Not enough points");
+ std::vector<size_t> heap(points);
+ for (size_t n = 0; n < points; ++n)
+ heap[n] = n;
+
+ auto Comp = [&](size_t e0, size_t e1) { return data[e0].scalar < data[e1].scalar; };
+ std::make_heap(heap.begin(), heap.end(), Comp);
+ MULTIEXP_PERF(PERF_TIMER_STOP(setup));
+
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(loop, 1000000));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(pop, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(pop));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(add, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(add));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(sub, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(sub));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(push, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(push));
+ while (heap.size() > 1)
+ {
+ MULTIEXP_PERF(PERF_TIMER_RESUME(pop));
+ std::pop_heap(heap.begin(), heap.end(), Comp);
+ size_t index1 = heap.back();
+ heap.pop_back();
+ std::pop_heap(heap.begin(), heap.end(), Comp);
+ size_t index2 = heap.back();
+ heap.pop_back();
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(pop));
+
+ MULTIEXP_PERF(PERF_TIMER_RESUME(add));
+ ge_cached cached;
+ ge_p3_to_cached(&cached, &data[index1].point);
+ ge_p1p1 p1;
+ ge_add(&p1, &data[index2].point, &cached);
+ ge_p1p1_to_p3(&data[index2].point, &p1);
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(add));
+
+ MULTIEXP_PERF(PERF_TIMER_RESUME(sub));
+ sc_sub(data[index1].scalar.bytes, data[index1].scalar.bytes, data[index2].scalar.bytes);
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(sub));
+
+ MULTIEXP_PERF(PERF_TIMER_RESUME(push));
+ if (!(data[index1].scalar == rct::zero()))
+ {
+ heap.push_back(index1);
+ std::push_heap(heap.begin(), heap.end(), Comp);
+ }
+
+ heap.push_back(index2);
+ std::push_heap(heap.begin(), heap.end(), Comp);
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(push));
+ }
+ MULTIEXP_PERF(PERF_TIMER_STOP(push));
+ MULTIEXP_PERF(PERF_TIMER_STOP(sub));
+ MULTIEXP_PERF(PERF_TIMER_STOP(add));
+ MULTIEXP_PERF(PERF_TIMER_STOP(pop));
+ MULTIEXP_PERF(PERF_TIMER_STOP(loop));
+
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(end, 1000000));
+ //return rct::scalarmultKey(data[index1].point, data[index1].scalar);
+ std::pop_heap(heap.begin(), heap.end(), Comp);
+ size_t index1 = heap.back();
+ heap.pop_back();
+ ge_p2 p2;
+ ge_scalarmult(&p2, data[index1].scalar.bytes, &data[index1].point);
+ rct::key res;
+ ge_tobytes(res.bytes, &p2);
+ return res;
+}
+
+rct::key bos_coster_heap_conv_robust(std::vector<MultiexpData> data)
+{
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(bos_coster, 1000000));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(setup, 1000000));
+ size_t points = data.size();
+ CHECK_AND_ASSERT_THROW_MES(points > 0, "Not enough points");
+ std::vector<size_t> heap;
+ heap.reserve(points);
+ for (size_t n = 0; n < points; ++n)
+ {
+ if (!(data[n].scalar == rct::zero()) && !ge_p3_is_point_at_infinity(&data[n].point))
+ heap.push_back(n);
+ }
+ points = heap.size();
+ if (points == 0)
+ return rct::identity();
+
+ auto Comp = [&](size_t e0, size_t e1) { return data[e0].scalar < data[e1].scalar; };
+ std::make_heap(heap.begin(), heap.end(), Comp);
+
+ if (points < 2)
+ {
+ std::pop_heap(heap.begin(), heap.end(), Comp);
+ size_t index1 = heap.back();
+ ge_p2 p2;
+ ge_scalarmult(&p2, data[index1].scalar.bytes, &data[index1].point);
+ rct::key res;
+ ge_tobytes(res.bytes, &p2);
+ return res;
+ }
+
+ MULTIEXP_PERF(PERF_TIMER_STOP(setup));
+
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(loop, 1000000));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(pop, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(pop));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(div, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(div));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(add, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(add));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(sub, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(sub));
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(push, 1000000)); MULTIEXP_PERF(PERF_TIMER_PAUSE(push));
+ while (heap.size() > 1)
+ {
+ MULTIEXP_PERF(PERF_TIMER_RESUME(pop));
+ std::pop_heap(heap.begin(), heap.end(), Comp);
+ size_t index1 = heap.back();
+ heap.pop_back();
+ std::pop_heap(heap.begin(), heap.end(), Comp);
+ size_t index2 = heap.back();
+ heap.pop_back();
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(pop));
+
+ ge_cached cached;
+ ge_p1p1 p1;
+ ge_p2 p2;
+
+ MULTIEXP_PERF(PERF_TIMER_RESUME(div));
+ while (1)
+ {
+ rct::key s1_2 = div2(data[index1].scalar);
+ if (!(data[index2].scalar < s1_2))
+ break;
+ if (data[index1].scalar.bytes[0] & 1)
+ {
+ data.resize(data.size()+1);
+ data.back().scalar = rct::identity();
+ data.back().point = data[index1].point;
+ heap.push_back(data.size() - 1);
+ std::push_heap(heap.begin(), heap.end(), Comp);
+ }
+ data[index1].scalar = div2(data[index1].scalar);
+ ge_p3_to_p2(&p2, &data[index1].point);
+ ge_p2_dbl(&p1, &p2);
+ ge_p1p1_to_p3(&data[index1].point, &p1);
+ }
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(div));
+
+ MULTIEXP_PERF(PERF_TIMER_RESUME(add));
+ ge_p3_to_cached(&cached, &data[index1].point);
+ ge_add(&p1, &data[index2].point, &cached);
+ ge_p1p1_to_p3(&data[index2].point, &p1);
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(add));
+
+ MULTIEXP_PERF(PERF_TIMER_RESUME(sub));
+ sc_sub(data[index1].scalar.bytes, data[index1].scalar.bytes, data[index2].scalar.bytes);
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(sub));
+
+ MULTIEXP_PERF(PERF_TIMER_RESUME(push));
+ if (!(data[index1].scalar == rct::zero()))
+ {
+ heap.push_back(index1);
+ std::push_heap(heap.begin(), heap.end(), Comp);
+ }
+
+ heap.push_back(index2);
+ std::push_heap(heap.begin(), heap.end(), Comp);
+ MULTIEXP_PERF(PERF_TIMER_PAUSE(push));
+ }
+ MULTIEXP_PERF(PERF_TIMER_STOP(push));
+ MULTIEXP_PERF(PERF_TIMER_STOP(sub));
+ MULTIEXP_PERF(PERF_TIMER_STOP(add));
+ MULTIEXP_PERF(PERF_TIMER_STOP(pop));
+ MULTIEXP_PERF(PERF_TIMER_STOP(loop));
+
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(end, 1000000));
+ //return rct::scalarmultKey(data[index1].point, data[index1].scalar);
+ std::pop_heap(heap.begin(), heap.end(), Comp);
+ size_t index1 = heap.back();
+ heap.pop_back();
+ ge_p2 p2;
+ ge_scalarmult(&p2, data[index1].scalar.bytes, &data[index1].point);
+ rct::key res;
+ ge_tobytes(res.bytes, &p2);
+ return res;
+}
+
+static constexpr unsigned int STRAUS_C = 4;
+
+struct straus_cached_data
+{
+#ifdef RAW_MEMORY_BLOCK
+ size_t size;
+ ge_cached *multiples;
+ straus_cached_data(): size(0), multiples(NULL) {}
+ ~straus_cached_data() { aligned_free(multiples); }
+#else
+ std::vector<std::vector<ge_cached>> multiples;
+#endif
+};
+#ifdef RAW_MEMORY_BLOCK
+#ifdef ALTERNATE_LAYOUT
+#define CACHE_OFFSET(cache,point,digit) cache->multiples[(point)*((1<<STRAUS_C)-1)+((digit)-1)]
+#else
+#define CACHE_OFFSET(cache,point,digit) cache->multiples[(point)+cache->size*((digit)-1)]
+#endif
+#else
+#ifdef ALTERNATE_LAYOUT
+#define CACHE_OFFSET(cache,point,digit) local_cache->multiples[j][digit-1]
+#else
+#define CACHE_OFFSET(cache,point,digit) local_cache->multiples[digit][j]
+#endif
+#endif
+
+std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data, size_t N)
+{
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(multiples, 1000000));
+ if (N == 0)
+ N = data.size();
+ CHECK_AND_ASSERT_THROW_MES(N <= data.size(), "Bad cache base data");
+ ge_cached cached;
+ ge_p1p1 p1;
+ ge_p3 p3;
+ std::shared_ptr<straus_cached_data> cache(new straus_cached_data());
+
+#ifdef RAW_MEMORY_BLOCK
+ const size_t offset = cache->size;
+ cache->multiples = (ge_cached*)aligned_realloc(cache->multiples, sizeof(ge_cached) * ((1<<STRAUS_C)-1) * std::max(offset, N), 4096);
+ CHECK_AND_ASSERT_THROW_MES(cache->multiples, "Out of memory");
+ cache->size = N;
+ for (size_t j=offset;j<N;++j)
+ {
+ ge_p3_to_cached(&CACHE_OFFSET(cache, j, 1), &data[j].point);
+ for (size_t i=2;i<1<<STRAUS_C;++i)
+ {
+ ge_add(&p1, &data[j].point, &CACHE_OFFSET(cache, j, i-1));
+ ge_p1p1_to_p3(&p3, &p1);
+ ge_p3_to_cached(&CACHE_OFFSET(cache, j, i), &p3);
+ }
+ }
+#else
+#ifdef ALTERNATE_LAYOUT
+ const size_t offset = cache->multiples.size();
+ cache->multiples.resize(std::max(offset, N));
+ for (size_t i = offset; i < N; ++i)
+ {
+ cache->multiples[i].resize((1<<STRAUS_C)-1);
+ ge_p3_to_cached(&cache->multiples[i][0], &data[i].point);
+ for (size_t j=2;j<1<<STRAUS_C;++j)
+ {
+ ge_add(&p1, &data[i].point, &cache->multiples[i][j-2]);
+ ge_p1p1_to_p3(&p3, &p1);
+ ge_p3_to_cached(&cache->multiples[i][j-1], &p3);
+ }
+ }
+#else
+ cache->multiples.resize(1<<STRAUS_C);
+ size_t offset = cache->multiples[1].size();
+ cache->multiples[1].resize(std::max(offset, N));
+ for (size_t i = offset; i < N; ++i)
+ ge_p3_to_cached(&cache->multiples[1][i], &data[i].point);
+ for (size_t i=2;i<1<<STRAUS_C;++i)
+ cache->multiples[i].resize(std::max(offset, N));
+ for (size_t j=offset;j<N;++j)
+ {
+ for (size_t i=2;i<1<<STRAUS_C;++i)
+ {
+ ge_add(&p1, &data[j].point, &cache->multiples[i-1][j]);
+ ge_p1p1_to_p3(&p3, &p1);
+ ge_p3_to_cached(&cache->multiples[i][j], &p3);
+ }
+ }
+#endif
+#endif
+ MULTIEXP_PERF(PERF_TIMER_STOP(multiples));
+
+ return cache;
+}
+
+size_t straus_get_cache_size(const std::shared_ptr<straus_cached_data> &cache)
+{
+ size_t sz = 0;
+#ifdef RAW_MEMORY_BLOCK
+ sz += cache->size * sizeof(ge_cached) * ((1<<STRAUS_C)-1);
+#else
+ for (const auto &e0: cache->multiples)
+ sz += e0.size() * sizeof(ge_cached);
+#endif
+ return sz;
+}
+
+rct::key straus(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache, size_t STEP)
+{
+ CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache->size >= data.size(), "Cache is too small");
+ MULTIEXP_PERF(PERF_TIMER_UNIT(straus, 1000000));
+ bool HiGi = cache != NULL;
+ STEP = STEP ? STEP : 192;
+
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(setup, 1000000));
+ static constexpr unsigned int mask = (1<<STRAUS_C)-1;
+ std::shared_ptr<straus_cached_data> local_cache = cache == NULL ? straus_init_cache(data) : cache;
+ ge_cached cached;
+ ge_p1p1 p1;
+ ge_p3 p3;
+
+#ifdef TRACK_STRAUS_ZERO_IDENTITY
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(skip, 1000000));
+ std::vector<uint8_t> skip(data.size());
+ for (size_t i = 0; i < data.size(); ++i)
+ skip[i] = data[i].scalar == rct::zero() || ge_p3_is_point_at_infinity(&data[i].point);
+ MULTIEXP_PERF(PERF_TIMER_STOP(skip));
+#endif
+
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(digits, 1000000));
+ std::unique_ptr<uint8_t[]> digits{new uint8_t[256 * data.size()]};
+ for (size_t j = 0; j < data.size(); ++j)
+ {
+ unsigned char bytes33[33];
+ memcpy(bytes33, data[j].scalar.bytes, 32);
+ bytes33[32] = 0;
+ const unsigned char *bytes = bytes33;
+#if 1
+ static_assert(STRAUS_C == 4, "optimized version needs STRAUS_C == 4");
+ unsigned int i;
+ for (i = 0; i < 256; i += 8, bytes++)
+ {
+ digits[j*256+i] = bytes[0] & 0xf;
+ digits[j*256+i+1] = (bytes[0] >> 1) & 0xf;
+ digits[j*256+i+2] = (bytes[0] >> 2) & 0xf;
+ digits[j*256+i+3] = (bytes[0] >> 3) & 0xf;
+ digits[j*256+i+4] = ((bytes[0] >> 4) | (bytes[1]<<4)) & 0xf;
+ digits[j*256+i+5] = ((bytes[0] >> 5) | (bytes[1]<<3)) & 0xf;
+ digits[j*256+i+6] = ((bytes[0] >> 6) | (bytes[1]<<2)) & 0xf;
+ digits[j*256+i+7] = ((bytes[0] >> 7) | (bytes[1]<<1)) & 0xf;
+ }
+#elif 1
+ for (size_t i = 0; i < 256; ++i)
+ digits[j*256+i] = ((bytes[i>>3] | (bytes[(i>>3)+1]<<8)) >> (i&7)) & mask;
+#else
+ rct::key shifted = data[j].scalar;
+ for (size_t i = 0; i < 256; ++i)
+ {
+ digits[j*256+i] = shifted.bytes[0] & 0xf;
+ shifted = div2(shifted, (256-i)>>3);
+ }
+#endif
+ }
+ MULTIEXP_PERF(PERF_TIMER_STOP(digits));
+
+ rct::key maxscalar = rct::zero();
+ for (size_t i = 0; i < data.size(); ++i)
+ if (maxscalar < data[i].scalar)
+ maxscalar = data[i].scalar;
+ size_t start_i = 0;
+ while (start_i < 256 && !(maxscalar < pow2(start_i)))
+ start_i += STRAUS_C;
+ MULTIEXP_PERF(PERF_TIMER_STOP(setup));
+
+ ge_p3 res_p3 = ge_p3_identity;
+
+ for (size_t start_offset = 0; start_offset < data.size(); start_offset += STEP)
+ {
+ const size_t num_points = std::min(data.size() - start_offset, STEP);
+
+ ge_p3 band_p3 = ge_p3_identity;
+ size_t i = start_i;
+ if (!(i < STRAUS_C))
+ goto skipfirst;
+ while (!(i < STRAUS_C))
+ {
+ ge_p2 p2;
+ ge_p3_to_p2(&p2, &band_p3);
+ for (size_t j = 0; j < STRAUS_C; ++j)
+ {
+ ge_p2_dbl(&p1, &p2);
+ if (j == STRAUS_C - 1)
+ ge_p1p1_to_p3(&band_p3, &p1);
+ else
+ ge_p1p1_to_p2(&p2, &p1);
+ }
+skipfirst:
+ i -= STRAUS_C;
+ for (size_t j = start_offset; j < start_offset + num_points; ++j)
+ {
+#ifdef TRACK_STRAUS_ZERO_IDENTITY
+ if (skip[j])
+ continue;
+#endif
+ const uint8_t digit = digits[j*256+i];
+ if (digit)
+ {
+ ge_add(&p1, &band_p3, &CACHE_OFFSET(local_cache, j, digit));
+ ge_p1p1_to_p3(&band_p3, &p1);
+ }
+ }
+ }
+
+ ge_p3_to_cached(&cached, &band_p3);
+ ge_add(&p1, &res_p3, &cached);
+ ge_p1p1_to_p3(&res_p3, &p1);
+ }
+
+ rct::key res;
+ ge_p3_tobytes(res.bytes, &res_p3);
+ return res;
+}
+
+size_t get_pippenger_c(size_t N)
+{
+// uncached: 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9
+// cached: 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9
+ if (N <= 2) return 1;
+ if (N <= 8) return 2;
+ if (N <= 16) return 3;
+ if (N <= 64) return 4;
+ if (N <= 128) return 5;
+ if (N <= 256) return 6;
+ if (N <= 1024) return 7;
+ if (N <= 2048) return 8;
+ return 9;
+}
+
+struct pippenger_cached_data
+{
+ size_t size;
+ ge_cached *cached;
+ pippenger_cached_data(): size(0), cached(NULL) {}
+ ~pippenger_cached_data() { aligned_free(cached); }
+};
+
+std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t N)
+{
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(pippenger_init_cache, 1000000));
+ if (N == 0)
+ N = data.size();
+ CHECK_AND_ASSERT_THROW_MES(N <= data.size(), "Bad cache base data");
+ ge_cached cached;
+ std::shared_ptr<pippenger_cached_data> cache(new pippenger_cached_data());
+
+ cache->size = N;
+ 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);
+
+ MULTIEXP_PERF(PERF_TIMER_STOP(pippenger_init_cache));
+ return cache;
+}
+
+size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &cache)
+{
+ 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)
+{
+ CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache->size >= data.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");
+
+ 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;
+
+ rct::key maxscalar = rct::zero();
+ for (size_t i = 0; i < data.size(); ++i)
+ {
+ if (maxscalar < data[i].scalar)
+ maxscalar = data[i].scalar;
+ }
+ size_t groups = 0;
+ while (groups < 256 && !(maxscalar < pow2(groups)))
+ ++groups;
+ groups = (groups + c - 1) / c;
+
+ for (size_t k = groups; k-- > 0; )
+ {
+ if (!ge_p3_is_point_at_infinity(&result))
+ {
+ ge_p2 p2;
+ ge_p3_to_p2(&p2, &result);
+ for (size_t i = 0; i < c; ++i)
+ {
+ ge_p1p1 p1;
+ ge_p2_dbl(&p1, &p2);
+ if (i == c - 1)
+ ge_p1p1_to_p3(&result, &p1);
+ else
+ ge_p1p1_to_p2(&p2, &p1);
+ }
+ }
+ for (size_t i = 0; i < (1u<<c); ++i)
+ buckets[i] = ge_p3_identity;
+
+ // partition scalars into buckets
+ for (size_t i = 0; i < data.size(); ++i)
+ {
+ unsigned int bucket = 0;
+ for (size_t j = 0; j < c; ++j)
+ if (test(data[i].scalar, k*c+j))
+ bucket |= 1<<j;
+ if (bucket == 0)
+ continue;
+ 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]);
+ }
+ else
+ buckets[bucket] = data[i].point;
+ }
+
+ // sum the buckets
+ ge_p3 pail = ge_p3_identity;
+ for (size_t i = (1<<c)-1; i > 0; --i)
+ {
+ if (!ge_p3_is_point_at_infinity(&buckets[i]))
+ add(pail, buckets[i]);
+ if (!ge_p3_is_point_at_infinity(&pail))
+ add(result, pail);
+ }
+ }
+
+ rct::key res;
+ ge_p3_tobytes(res.bytes, &result);
+ return res;
+}
+
+}
diff --git a/src/ringct/multiexp.h b/src/ringct/multiexp.h
new file mode 100644
index 000000000..559ab664a
--- /dev/null
+++ b/src/ringct/multiexp.h
@@ -0,0 +1,71 @@
+// Copyright (c) 2017, The Monero Project
+//
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without modification, are
+// permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice, this list of
+// conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice, this list
+// of conditions and the following disclaimer in the documentation and/or other
+// materials provided with the distribution.
+//
+// 3. Neither the name of the copyright holder nor the names of its contributors may be
+// used to endorse or promote products derived from this software without specific
+// prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// 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.
+//
+// Adapted from Python code by Sarang Noether
+
+#pragma once
+
+#ifndef MULTIEXP_H
+#define MULTIEXP_H
+
+#include <vector>
+#include "crypto/crypto.h"
+#include "rctTypes.h"
+#include "misc_log_ex.h"
+
+namespace rct
+{
+
+struct MultiexpData {
+ rct::key scalar;
+ ge_p3 point;
+
+ MultiexpData() {}
+ MultiexpData(const rct::key &s, const ge_p3 &p): scalar(s), point(p) {}
+ MultiexpData(const rct::key &s, const rct::key &p): scalar(s)
+ {
+ CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&point, p.bytes) == 0, "ge_frombytes_vartime failed");
+ }
+};
+
+struct straus_cached_data;
+struct pippenger_cached_data;
+
+rct::key bos_coster_heap_conv(std::vector<MultiexpData> data);
+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);
+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);
+
+}
+
+#endif
diff --git a/src/ringct/rctOps.cpp b/src/ringct/rctOps.cpp
index 50693bad7..6c3c4500e 100644
--- a/src/ringct/rctOps.cpp
+++ b/src/ringct/rctOps.cpp
@@ -60,6 +60,17 @@ namespace rct {
//Various key generation functions
+ bool toPointCheckOrder(ge_p3 *P, const unsigned char *data)
+ {
+ if (ge_frombytes_vartime(P, data))
+ return false;
+ ge_p2 R;
+ ge_scalarmult(&R, curveOrder().bytes, P);
+ key tmp;
+ ge_tobytes(tmp.bytes, &R);
+ return tmp == identity();
+ }
+
//generates a random scalar which can be used as a secret key or mask
void skGen(key &sk) {
random32_unbiased(sk.bytes);
@@ -193,15 +204,33 @@ namespace rct {
//Computes aH where H= toPoint(cn_fast_hash(G)), G the basepoint
key scalarmultH(const key & a) {
- ge_p3 A;
ge_p2 R;
- CHECK_AND_ASSERT_THROW_MES_L1(ge_frombytes_vartime(&A, H.bytes) == 0, "ge_frombytes_vartime failed at "+boost::lexical_cast<std::string>(__LINE__));
- ge_scalarmult(&R, a.bytes, &A);
+ ge_scalarmult(&R, a.bytes, &ge_p3_H);
key aP;
ge_tobytes(aP.bytes, &R);
return aP;
}
+ //Computes 8P
+ key scalarmult8(const key & P) {
+ ge_p3 p3;
+ CHECK_AND_ASSERT_THROW_MES_L1(ge_frombytes_vartime(&p3, P.bytes) == 0, "ge_frombytes_vartime failed at "+boost::lexical_cast<std::string>(__LINE__));
+ ge_p2 p2;
+ ge_p3_to_p2(&p2, &p3);
+ ge_p1p1 p1;
+ ge_mul8(&p1, &p2);
+ ge_p1p1_to_p2(&p2, &p1);
+ rct::key res;
+ ge_tobytes(res.bytes, &p2);
+ return res;
+ }
+
+ //Computes aL where L is the curve order
+ bool isInMainSubgroup(const key & a) {
+ ge_p3 p3;
+ return toPointCheckOrder(&p3, a.bytes);
+ }
+
//Curve addition / subtractions
//for curve points: AB = A + B
diff --git a/src/ringct/rctOps.h b/src/ringct/rctOps.h
index f8889af5c..50645821c 100644
--- a/src/ringct/rctOps.h
+++ b/src/ringct/rctOps.h
@@ -63,6 +63,8 @@ namespace rct {
static const key I = { {0x01, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 } };
static const key L = { {0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 } };
static const key G = { {0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66 } };
+ static const key EIGHT = { {0x08, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 } };
+ static const key INV_EIGHT = { { 0x79, 0x2f, 0xdc, 0xe2, 0x29, 0xe5, 0x06, 0x61, 0xd0, 0xda, 0x1c, 0x7d, 0xb3, 0x9d, 0xd3, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x06 } };
//Creates a zero scalar
inline key zero() { return Z; }
@@ -83,6 +85,7 @@ namespace rct {
keyM keyMInit(size_t rows, size_t cols);
//Various key generation functions
+ bool toPointCheckOrder(ge_p3 *P, const unsigned char *data);
//generates a random scalar which can be used as a secret key or mask
key skGen();
@@ -119,6 +122,10 @@ namespace rct {
key scalarmultKey(const key &P, const key &a);
//Computes aH where H= toPoint(cn_fast_hash(G)), G the basepoint
key scalarmultH(const key & a);
+ // multiplies a point by 8
+ key scalarmult8(const key & P);
+ // checks a is in the main subgroup (ie, not a small one)
+ bool isInMainSubgroup(const key & a);
//Curve addition / subtractions
diff --git a/src/ringct/rctSigs.cpp b/src/ringct/rctSigs.cpp
index cc966c44b..fe0cd9c57 100644
--- a/src/ringct/rctSigs.cpp
+++ b/src/ringct/rctSigs.cpp
@@ -45,30 +45,6 @@ using namespace std;
#define CHECK_AND_ASSERT_MES_L1(expr, ret, message) {if(!(expr)) {MCERROR("verify", message); return ret;}}
namespace rct {
- bool is_simple(int type)
- {
- switch (type)
- {
- case RCTTypeSimple:
- case RCTTypeSimpleBulletproof:
- return true;
- default:
- return false;
- }
- }
-
- bool is_bulletproof(int type)
- {
- switch (type)
- {
- case RCTTypeSimpleBulletproof:
- case RCTTypeFullBulletproof:
- return true;
- default:
- return false;
- }
- }
-
Bulletproof proveRangeBulletproof(key &C, key &mask, uint64_t amount)
{
mask = rct::skGen();
@@ -78,6 +54,15 @@ namespace rct {
return proof;
}
+ Bulletproof proveRangeBulletproof(keyV &C, keyV &masks, const std::vector<uint64_t> &amounts)
+ {
+ masks = rct::skvGen(amounts.size());
+ Bulletproof proof = bulletproof_PROVE(amounts, masks);
+ CHECK_AND_ASSERT_THROW_MES(proof.V.size() == amounts.size(), "V does not have the expected size");
+ C = proof.V;
+ return proof;
+ }
+
bool verBulletproof(const Bulletproof &proof)
{
try { return bulletproof_VERIFY(proof); }
@@ -85,6 +70,13 @@ namespace rct {
catch (...) { return false; }
}
+ bool verBulletproof(const std::vector<const Bulletproof*> &proofs)
+ {
+ try { return bulletproof_VERIFY(proofs); }
+ // we can get deep throws from ge_frombytes_vartime if input isn't valid
+ catch (...) { return false; }
+ }
+
//Borromean (c.f. gmax/andytoshi's paper)
boroSig genBorromean(const key64 x, const key64 P1, const key64 P2, const bits indices) {
key64 L[2], alpha;
@@ -285,6 +277,7 @@ namespace rct {
for (j = 0; j < dsRows; j++) {
addKeys2(L, rv.ss[i][j], c_old, pk[i][j]);
hashToPoint(Hi, pk[i][j]);
+ CHECK_AND_ASSERT_MES(!(Hi == rct::identity()), false, "Data hashed to point at infinity");
addKeys3(R, rv.ss[i][j], Hi, c_old, Ip[j].k);
toHash[3 * j + 1] = pk[i][j];
toHash[3 * j + 2] = L;
@@ -389,7 +382,7 @@ namespace rct {
std::stringstream ss;
binary_archive<true> ba(ss);
CHECK_AND_ASSERT_THROW_MES(!rv.mixRing.empty(), "Empty mixRing");
- const size_t inputs = is_simple(rv.type) ? rv.mixRing.size() : rv.mixRing[0].size();
+ const size_t inputs = is_rct_simple(rv.type) ? rv.mixRing.size() : rv.mixRing[0].size();
const size_t outputs = rv.ecdhInfo.size();
key prehash;
CHECK_AND_ASSERT_THROW_MES(const_cast<rctSig&>(rv).serialize_rctsig_base(ba, inputs, outputs),
@@ -398,7 +391,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)
@@ -659,7 +652,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, bool bulletproof, hw::device &hwdev) {
+ 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");
@@ -669,13 +662,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.bulletproofs.resize(destinations.size());
- else
- rv.p.rangeSigs.resize(destinations.size());
+ rv.p.rangeSigs.resize(destinations.size());
rv.ecdhInfo.resize(destinations.size());
size_t i = 0;
@@ -685,17 +675,10 @@ namespace rct {
//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, amounts[i]);
- else
- rv.p.rangeSigs[i] = proveRange(rv.outPk[i].mask, outSk[i].mask, amounts[i]);
+ rv.p.rangeSigs[i] = proveRange(rv.outPk[i].mask, outSk[i].mask, amounts[i]);
#ifdef DBG
- if (bulletproof)
- CHECK_AND_ASSERT_THROW_MES(verBulletproof(rv.p.bulletproofs[i]), "verBulletproof failed on newly created proof");
- else
- CHECK_AND_ASSERT_THROW_MES(verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]), "verRange 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
-
//mask amount and mask
rv.ecdhInfo[i].mask = copy(outSk[i].mask);
rv.ecdhInfo[i].amount = d2h(amounts[i]);
@@ -725,12 +708,13 @@ 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, false, hwdev);
+ return genRct(message, inSk, destinations, amounts, mixRing, amount_keys, kLRki, msout, index, outSk, hwdev);
}
//RCT simple
//for post-rct only
- rctSig genRctSimple(const key &message, const ctkeyV & inSk, const keyV & destinations, const vector<xmr_amount> &inamounts, const 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, bool bulletproof, hw::device &hwdev) {
+ rctSig genRctSimple(const key &message, const ctkeyV & inSk, const keyV & destinations, const vector<xmr_amount> &inamounts, const 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) {
+ const bool bulletproof = range_proof_type != RangeProofBorromean;
CHECK_AND_ASSERT_THROW_MES(inamounts.size() > 0, "Empty inamounts");
CHECK_AND_ASSERT_THROW_MES(inamounts.size() == inSk.size(), "Different number of inamounts/inSk");
CHECK_AND_ASSERT_THROW_MES(outamounts.size() == destinations.size(), "Different number of amounts/destinations");
@@ -746,35 +730,74 @@ 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;
+ if (range_proof_type == RangeProofPaddedBulletproof)
+ {
+ rct::keyV C, masks;
+ rv.p.bulletproofs.push_back(proveRangeBulletproof(C, masks, outamounts));
+ #ifdef DBG
+ CHECK_AND_ASSERT_THROW_MES(verBulletproof(rv.p.bulletproofs.back()), "verBulletproof failed on newly created proof");
+ #endif
+ for (i = 0; i < outamounts.size(); ++i)
+ {
+ rv.outPk[i].mask = rct::scalarmult8(C[i]);
+ outSk[i].mask = masks[i];
+ }
+ }
+ else 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 <= BULLETPROOF_MAX_OUTPUTS)
+ 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 = rct::scalarmult8(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
@@ -822,7 +845,7 @@ namespace rct {
mixRing[i].resize(mixin+1);
index[i] = populateFromBlockchainSimple(mixRing[i], inPk[i], mixin);
}
- return genRctSimple(message, inSk, destinations, inamounts, outamounts, txnFee, mixRing, amount_keys, kLRki, msout, index, outSk, false, hwdev);
+ return genRctSimple(message, inSk, destinations, inamounts, outamounts, txnFee, mixRing, amount_keys, kLRki, msout, index, outSk, RangeProofBorromean, hwdev);
}
//RingCT protocol
@@ -837,13 +860,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");
+ CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull, false, "verRct called on non-full rctSig");
if (semantics)
{
- if (rv.type == RCTTypeFullBulletproof)
- CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.p.bulletproofs.size(), false, "Mismatched sizes of outPk and rv.p.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");
}
@@ -860,19 +880,13 @@ namespace rct {
tools::threadpool::waiter waiter;
std::deque<bool> results(rv.outPk.size(), false);
DP("range proofs verified?");
- for (size_t i = 0; i < rv.outPk.size(); i++) {
- tpool.submit(&waiter, [&, i] {
- if (rv.p.rangeSigs.empty())
- results[i] = verBulletproof(rv.p.bulletproofs[i]);
- else
- results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]);
- }, true);
- }
+ 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 < rv.outPk.size(); ++i) {
+ for (size_t i = 0; i < results.size(); ++i) {
if (!results[i]) {
- LOG_PRINT_L1("Range proof verified failed for output " << i);
+ LOG_PRINT_L1("Range proof verified failed for proof " << i);
return false;
}
}
@@ -906,17 +920,26 @@ namespace rct {
//ver RingCT simple
//assumes only post-rct style inputs (at least for max anonymity)
- bool verRctSimple(const rctSig & rv, bool semantics) {
+ bool verRctSemanticsSimple(const std::vector<const rctSig*> & rvv) {
try
{
- PERF_TIMER(verRctSimple);
+ PERF_TIMER(verRctSemanticsSimple);
- CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeSimpleBulletproof, false, "verRctSimple called on non simple rctSig");
- if (semantics)
+ tools::threadpool& tpool = tools::threadpool::getInstance();
+ tools::threadpool::waiter waiter;
+ std::deque<bool> results;
+ std::vector<const Bulletproof*> proofs;
+ size_t max_non_bp_proofs = 0, offset = 0;
+
+ for (const rctSig *rvp: rvv)
{
- if (rv.type == RCTTypeSimpleBulletproof)
+ CHECK_AND_ASSERT_MES(rvp, false, "rctSig pointer is NULL");
+ const rctSig &rv = *rvp;
+ 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)
{
- CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.p.bulletproofs.size(), false, "Mismatched sizes of outPk and rv.p.bulletproofs");
+ CHECK_AND_ASSERT_MES(rv.outPk.size() == n_bulletproof_amounts(rv.p.bulletproofs), false, "Mismatched sizes of outPk and bulletproofs");
CHECK_AND_ASSERT_MES(rv.p.pseudoOuts.size() == rv.p.MGs.size(), false, "Mismatched sizes of rv.p.pseudoOuts and rv.p.MGs");
CHECK_AND_ASSERT_MES(rv.pseudoOuts.empty(), false, "rv.pseudoOuts is not empty");
}
@@ -927,28 +950,22 @@ namespace rct {
CHECK_AND_ASSERT_MES(rv.p.pseudoOuts.empty(), false, "rv.p.pseudoOuts is not empty");
}
CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.ecdhInfo.size(), false, "Mismatched sizes of outPk and rv.ecdhInfo");
- }
- else
- {
- // semantics check is early, and mixRing/MGs aren't resolved yet
- if (rv.type == RCTTypeSimpleBulletproof)
- CHECK_AND_ASSERT_MES(rv.p.pseudoOuts.size() == rv.mixRing.size(), false, "Mismatched sizes of rv.p.pseudoOuts and mixRing");
- else
- CHECK_AND_ASSERT_MES(rv.pseudoOuts.size() == rv.mixRing.size(), false, "Mismatched sizes of rv.pseudoOuts and mixRing");
- }
- const size_t threads = std::max(rv.outPk.size(), rv.mixRing.size());
+ if (!bulletproof)
+ max_non_bp_proofs += rv.p.rangeSigs.size();
+ }
- std::deque<bool> results(threads);
- tools::threadpool& tpool = tools::threadpool::getInstance();
- tools::threadpool::waiter waiter;
+ results.resize(max_non_bp_proofs);
+ for (const rctSig *rvp: rvv)
+ {
+ const rctSig &rv = *rvp;
- const keyV &pseudoOuts = is_bulletproof(rv.type) ? rv.p.pseudoOuts : rv.pseudoOuts;
+ const bool bulletproof = is_rct_bulletproof(rv.type);
+ const keyV &pseudoOuts = bulletproof ? rv.p.pseudoOuts : rv.pseudoOuts;
- if (semantics) {
key sumOutpks = identity();
for (size_t i = 0; i < rv.outPk.size(); i++) {
- addKeys(sumOutpks, sumOutpks, rv.outPk[i].mask);
+ addKeys(sumOutpks, sumOutpks, rv.outPk[i].mask);
}
DP(sumOutpks);
key txnFeeKey = scalarmultH(d2h(rv.txnFee));
@@ -956,52 +973,100 @@ namespace rct {
key sumPseudoOuts = identity();
for (size_t i = 0 ; i < pseudoOuts.size() ; i++) {
- addKeys(sumPseudoOuts, sumPseudoOuts, pseudoOuts[i]);
+ addKeys(sumPseudoOuts, sumPseudoOuts, pseudoOuts[i]);
}
DP(sumPseudoOuts);
//check pseudoOuts vs Outs..
if (!equalKeys(sumPseudoOuts, sumOutpks)) {
- LOG_PRINT_L1("Sum check failed");
- return false;
+ LOG_PRINT_L1("Sum check failed");
+ return false;
}
- results.clear();
- results.resize(rv.outPk.size());
- for (size_t i = 0; i < rv.outPk.size(); i++) {
- tpool.submit(&waiter, [&, i] {
- if (rv.p.rangeSigs.empty())
- results[i] = verBulletproof(rv.p.bulletproofs[i]);
- else
- results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]);
- }, true);
+ if (bulletproof)
+ {
+ for (size_t i = 0; i < rv.p.bulletproofs.size(); i++)
+ proofs.push_back(&rv.p.bulletproofs[i]);
}
- waiter.wait(&tpool);
-
- for (size_t i = 0; i < results.size(); ++i) {
- if (!results[i]) {
- LOG_PRINT_L1("Range proof verified failed for output " << i);
- return false;
- }
+ else
+ {
+ for (size_t i = 0; i < rv.p.rangeSigs.size(); i++)
+ tpool.submit(&waiter, [&, i, offset] { results[i+offset] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); });
+ offset += rv.p.rangeSigs.size();
}
}
- else {
- const key message = get_pre_mlsag_hash(rv, hw::get_device("default"));
-
- results.clear();
- results.resize(rv.mixRing.size());
- for (size_t i = 0 ; i < rv.mixRing.size() ; i++) {
- tpool.submit(&waiter, [&, i] {
- results[i] = verRctMGSimple(message, rv.p.MGs[i], rv.mixRing[i], pseudoOuts[i]);
- }, true);
+ if (!proofs.empty() && !verBulletproof(proofs))
+ {
+ LOG_PRINT_L1("Aggregate range proof verified failed");
+ return false;
+ }
+
+ waiter.wait(&tpool);
+ for (size_t i = 0; i < results.size(); ++i) {
+ if (!results[i]) {
+ LOG_PRINT_L1("Range proof verified failed for proof " << i);
+ return false;
}
- waiter.wait(&tpool);
+ }
- for (size_t i = 0; i < results.size(); ++i) {
- if (!results[i]) {
- LOG_PRINT_L1("verRctMGSimple failed for input " << i);
- return false;
- }
+ return true;
+ }
+ // we can get deep throws from ge_frombytes_vartime if input isn't valid
+ catch (const std::exception &e)
+ {
+ LOG_PRINT_L1("Error in verRctSemanticsSimple: " << e.what());
+ return false;
+ }
+ catch (...)
+ {
+ LOG_PRINT_L1("Error in verRctSemanticsSimple, but not an actual exception");
+ return false;
+ }
+ }
+
+ bool verRctSemanticsSimple(const rctSig & rv)
+ {
+ return verRctSemanticsSimple(std::vector<const rctSig*>(1, &rv));
+ }
+
+ //ver RingCT simple
+ //assumes only post-rct style inputs (at least for max anonymity)
+ bool verRctNonSemanticsSimple(const rctSig & rv) {
+ try
+ {
+ PERF_TIMER(verRctNonSemanticsSimple);
+
+ 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)
+ CHECK_AND_ASSERT_MES(rv.p.pseudoOuts.size() == rv.mixRing.size(), false, "Mismatched sizes of rv.p.pseudoOuts and mixRing");
+ else
+ CHECK_AND_ASSERT_MES(rv.pseudoOuts.size() == rv.mixRing.size(), false, "Mismatched sizes of rv.pseudoOuts and mixRing");
+
+ const size_t threads = std::max(rv.outPk.size(), rv.mixRing.size());
+
+ std::deque<bool> results(threads);
+ tools::threadpool& tpool = tools::threadpool::getInstance();
+ tools::threadpool::waiter waiter;
+
+ const keyV &pseudoOuts = bulletproof ? rv.p.pseudoOuts : rv.pseudoOuts;
+
+ const key message = get_pre_mlsag_hash(rv, hw::get_device("default"));
+
+ results.clear();
+ results.resize(rv.mixRing.size());
+ for (size_t i = 0 ; i < rv.mixRing.size() ; i++) {
+ tpool.submit(&waiter, [&, i] {
+ results[i] = verRctMGSimple(message, rv.p.MGs[i], rv.mixRing[i], pseudoOuts[i]);
+ });
+ }
+ waiter.wait(&tpool);
+
+ for (size_t i = 0; i < results.size(); ++i) {
+ if (!results[i]) {
+ LOG_PRINT_L1("verRctMGSimple failed for input " << i);
+ return false;
}
}
@@ -1010,12 +1075,12 @@ namespace rct {
// we can get deep throws from ge_frombytes_vartime if input isn't valid
catch (const std::exception &e)
{
- LOG_PRINT_L1("Error in verRct: " << e.what());
+ LOG_PRINT_L1("Error in verRctNonSemanticsSimple: " << e.what());
return false;
}
catch (...)
{
- LOG_PRINT_L1("Error in verRct, but not an actual exception");
+ LOG_PRINT_L1("Error in verRctNonSemanticsSimple, but not an actual exception");
return false;
}
}
@@ -1031,7 +1096,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");
@@ -1044,6 +1109,8 @@ namespace rct {
DP("C");
DP(C);
key Ctmp;
+ CHECK_AND_ASSERT_THROW_MES(sc_check(mask.bytes) == 0, "warning, bad ECDH mask");
+ CHECK_AND_ASSERT_THROW_MES(sc_check(amount.bytes) == 0, "warning, bad ECDH amount");
addKeys2(Ctmp, mask, amount, H);
DP("Ctmp");
DP(Ctmp);
@@ -1059,7 +1126,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");
@@ -1072,6 +1139,8 @@ namespace rct {
DP("C");
DP(C);
key Ctmp;
+ CHECK_AND_ASSERT_THROW_MES(sc_check(mask.bytes) == 0, "warning, bad ECDH mask");
+ CHECK_AND_ASSERT_THROW_MES(sc_check(amount.bytes) == 0, "warning, bad ECDH amount");
addKeys2(Ctmp, mask, amount, H);
DP("Ctmp");
DP(Ctmp);
@@ -1087,12 +1156,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 5a9b2dd44..ae8bb91d7 100644
--- a/src/ringct/rctSigs.h
+++ b/src/ringct/rctSigs.h
@@ -119,14 +119,16 @@ 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, bool bulletproof, 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, bool bulletproof, 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);
bool verRct(const rctSig & rv, bool semantics);
static inline bool verRct(const rctSig & rv) { return verRct(rv, true) && verRct(rv, false); }
- bool verRctSimple(const rctSig & rv, bool semantics);
- static inline bool verRctSimple(const rctSig & rv) { return verRctSimple(rv, true) && verRctSimple(rv, false); }
+ bool verRctSemanticsSimple(const rctSig & rv);
+ bool verRctSemanticsSimple(const std::vector<const rctSig*> & rv);
+ bool verRctNonSemanticsSimple(const rctSig & rv);
+ static inline bool verRctSimple(const rctSig & rv) { return verRctSemanticsSimple(rv) && verRctNonSemanticsSimple(rv); }
xmr_amount decodeRct(const rctSig & rv, const key & sk, unsigned int i, key & mask, hw::device &hwdev);
xmr_amount decodeRct(const rctSig & rv, const key & sk, unsigned int i, hw::device &hwdev);
xmr_amount decodeRctSimple(const rctSig & rv, const key & sk, unsigned int i, key & mask, hw::device &hwdev);
diff --git a/src/ringct/rctTypes.cpp b/src/ringct/rctTypes.cpp
index 5650b3ba1..90ed65df0 100644
--- a/src/ringct/rctTypes.cpp
+++ b/src/ringct/rctTypes.cpp
@@ -28,6 +28,8 @@
// 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 "cryptonote_config.h"
#include "rctTypes.h"
using namespace crypto;
using namespace std;
@@ -209,4 +211,90 @@ namespace rct {
return vali;
}
+ bool is_rct_simple(int type)
+ {
+ switch (type)
+ {
+ case RCTTypeSimple:
+ case RCTTypeBulletproof:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ bool is_rct_bulletproof(int type)
+ {
+ switch (type)
+ {
+ case RCTTypeBulletproof:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ bool is_rct_borromean(int type)
+ {
+ switch (type)
+ {
+ case RCTTypeSimple:
+ case RCTTypeFull:
+ 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");
+ CHECK_AND_ASSERT_MES(proof.L.size() == proof.R.size(), 0, "Mismatched bulletproof L/R size");
+ static const size_t extra_bits = 4;
+ static_assert((1 << extra_bits) == BULLETPROOF_MAX_OUTPUTS, "log2(BULLETPROOF_MAX_OUTPUTS) is out of date");
+ CHECK_AND_ASSERT_MES(proof.L.size() <= 6 + extra_bits, 0, "Invalid bulletproof L size");
+ CHECK_AND_ASSERT_MES(proof.V.size() <= (1u<<(proof.L.size()-6)), 0, "Invalid bulletproof V/L");
+ CHECK_AND_ASSERT_MES(proof.V.size() * 2 > (1u<<(proof.L.size()-6)), 0, "Invalid bulletproof V/L");
+ CHECK_AND_ASSERT_MES(proof.V.size() > 0, 0, "Empty bulletproof");
+ return proof.V.size();
+ }
+
+ size_t n_bulletproof_amounts(const std::vector<Bulletproof> &proofs)
+ {
+ size_t n = 0;
+ for (const Bulletproof &proof: proofs)
+ {
+ size_t n2 = n_bulletproof_amounts(proof);
+ CHECK_AND_ASSERT_MES(n2 < std::numeric_limits<uint32_t>::max() - n, 0, "Invalid number of bulletproofs");
+ if (n2 == 0)
+ return 0;
+ n += n2;
+ }
+ return n;
+ }
+
+ size_t n_bulletproof_max_amounts(const Bulletproof &proof)
+ {
+ CHECK_AND_ASSERT_MES(proof.L.size() >= 6, 0, "Invalid bulletproof L size");
+ CHECK_AND_ASSERT_MES(proof.L.size() == proof.R.size(), 0, "Mismatched bulletproof L/R size");
+ static const size_t extra_bits = 4;
+ static_assert((1 << extra_bits) == BULLETPROOF_MAX_OUTPUTS, "log2(BULLETPROOF_MAX_OUTPUTS) is out of date");
+ CHECK_AND_ASSERT_MES(proof.L.size() <= 6 + extra_bits, 0, "Invalid bulletproof L size");
+ return 1 << (proof.L.size() - 6);
+ }
+
+ size_t n_bulletproof_max_amounts(const std::vector<Bulletproof> &proofs)
+ {
+ size_t n = 0;
+ for (const Bulletproof &proof: proofs)
+ {
+ size_t n2 = n_bulletproof_max_amounts(proof);
+ CHECK_AND_ASSERT_MES(n2 < std::numeric_limits<uint32_t>::max() - n, 0, "Invalid number of bulletproofs");
+ if (n2 == 0)
+ return 0;
+ n += n2;
+ }
+ return n;
+ }
+
}
diff --git a/src/ringct/rctTypes.h b/src/ringct/rctTypes.h
index f6987d3f3..ffc4df3ed 100644
--- a/src/ringct/rctTypes.h
+++ b/src/ringct/rctTypes.h
@@ -190,6 +190,8 @@ namespace rct {
Bulletproof() {}
Bulletproof(const rct::key &V, const rct::key &A, const rct::key &S, const rct::key &T1, const rct::key &T2, const rct::key &taux, const rct::key &mu, const rct::keyV &L, const rct::keyV &R, const rct::key &a, const rct::key &b, const rct::key &t):
V({V}), A(A), S(S), T1(T1), T2(T2), taux(taux), mu(mu), L(L), R(R), a(a), b(b), t(t) {}
+ Bulletproof(const rct::keyV &V, const rct::key &A, const rct::key &S, const rct::key &T1, const rct::key &T2, const rct::key &taux, const rct::key &mu, const rct::keyV &L, const rct::keyV &R, const rct::key &a, const rct::key &b, const rct::key &t):
+ V(V), A(A), S(S), T1(T1), T2(T2), taux(taux), mu(mu), L(L), R(R), a(a), b(b), t(t) {}
BEGIN_SERIALIZE_OBJECT()
// Commitments aren't saved, they're restored via outPk
@@ -211,6 +213,11 @@ namespace rct {
END_SERIALIZE()
};
+ size_t n_bulletproof_amounts(const Bulletproof &proof);
+ size_t n_bulletproof_max_amounts(const Bulletproof &proof);
+ size_t n_bulletproof_amounts(const std::vector<Bulletproof> &proofs);
+ size_t n_bulletproof_max_amounts(const std::vector<Bulletproof> &proofs);
+
//A container to hold all signatures necessary for RingCT
// rangeSigs holds all the rangeproof data of a transaction
// MG holds the MLSAG signature of a transaction
@@ -222,9 +229,9 @@ namespace rct {
RCTTypeNull = 0,
RCTTypeFull = 1,
RCTTypeSimple = 2,
- RCTTypeFullBulletproof = 3,
- RCTTypeSimpleBulletproof = 4,
+ RCTTypeBulletproof = 3,
};
+ enum RangeProofType { RangeProofBorromean, RangeProofBulletproof, RangeProofMultiOutputBulletproof, RangeProofPaddedBulletproof };
struct rctSigBase {
uint8_t type;
key message;
@@ -241,7 +248,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
@@ -302,21 +309,25 @@ 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();
- PREPARE_CUSTOM_VECTOR_SERIALIZATION(outputs, bulletproofs);
- if (bulletproofs.size() != outputs)
+ uint32_t nbp = bulletproofs.size();
+ FIELD(nbp)
+ if (nbp > outputs)
return false;
- for (size_t i = 0; i < outputs; ++i)
+ PREPARE_CUSTOM_VECTOR_SERIALIZATION(nbp, bulletproofs);
+ for (size_t i = 0; i < nbp; ++i)
{
FIELDS(bulletproofs[i])
- if (outputs - i > 1)
+ if (nbp - i > 1)
ar.delimit_array();
}
+ if (n_bulletproof_max_amounts(bulletproofs) < outputs)
+ return false;
ar.end_array();
}
else
@@ -339,7 +350,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;
@@ -357,7 +368,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;
@@ -383,7 +394,7 @@ namespace rct {
ar.delimit_array();
}
ar.end_array();
- if (type == RCTTypeSimpleBulletproof)
+ if (type == RCTTypeBulletproof)
{
ar.tag("pseudoOuts");
ar.begin_array();
@@ -407,12 +418,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;
}
};
@@ -517,6 +528,10 @@ namespace rct {
//int[64] to uint long long
xmr_amount b2d(bits amountb);
+ bool is_rct_simple(int type);
+ bool is_rct_bulletproof(int type);
+ bool is_rct_borromean(int type);
+
static inline const rct::key &pk2rct(const crypto::public_key &pk) { return (const rct::key&)pk; }
static inline const rct::key &sk2rct(const crypto::secret_key &sk) { return (const rct::key&)sk; }
static inline const rct::key &ki2rct(const crypto::key_image &ki) { return (const rct::key&)ki; }
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 08:57:12 +0000