From 9ce9f8caf6e290088711ce4d5d90c1507a837bf2 Mon Sep 17 00:00:00 2001 From: moneromooo-monero Date: Wed, 17 Jan 2018 21:50:03 +0000 Subject: bulletproofs: add multi output bulletproofs to rct --- src/ringct/rctSigs.cpp | 143 ++++++++++++++++++++++++++----------------------- 1 file changed, 77 insertions(+), 66 deletions(-) (limited to 'src/ringct/rctSigs.cpp') diff --git a/src/ringct/rctSigs.cpp b/src/ringct/rctSigs.cpp index cc966c44b..6dcb203bf 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 &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); } @@ -389,7 +374,7 @@ namespace rct { std::stringstream ss; binary_archive 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(rv).serialize_rctsig_base(ba, inputs, outputs), @@ -659,7 +644,8 @@ 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 & 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 & amounts, const ctkeyM &mixRing, const keyV &amount_keys, const multisig_kLRki *kLRki, multisig_out *msout, unsigned int index, ctkeyV &outSk, RangeProofType range_proof_type, hw::device &hwdev) { + const bool bulletproof = range_proof_type != RangeProofBorromean; 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"); @@ -672,9 +658,7 @@ namespace rct { rv.type = bulletproof ? RCTTypeFullBulletproof : RCTTypeFull; 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()); @@ -684,18 +668,46 @@ namespace rct { 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, amounts[i]); - else + //compute range proof (bulletproofs are done later) + if (!bulletproof) + { rv.p.rangeSigs[i] = proveRange(rv.outPk[i].mask, outSk[i].mask, amounts[i]); #ifdef DBG - 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"); #endif + } + } + + rv.p.bulletproofs.clear(); + if (bulletproof) + { + std::vector proof_amounts; + size_t amounts_proved = 0; + while (amounts_proved < amounts.size()) + { + size_t batch_size = 1; + if (range_proof_type == RangeProofMultiOutputBulletproof) + while (batch_size * 2 + amounts_proved <= amounts.size()) + batch_size *= 2; + rct::keyV C, masks; + std::vector batch_amounts(batch_size); + for (i = 0; i < batch_size; ++i) + batch_amounts[i] = amounts[i + amounts_proved]; + rv.p.bulletproofs.push_back(proveRangeBulletproof(C, masks, batch_amounts)); + #ifdef DBG + CHECK_AND_ASSERT_THROW_MES(verBulletproof(rv.p.bulletproofs.back()), "verBulletproof failed on newly created proof"); + #endif + for (i = 0; i < batch_size; ++i) + { + rv.outPk[i + amounts_proved].mask = C[i]; + outSk[i + amounts_proved].mask = masks[i]; + } + amounts_proved += batch_size; + } + } + for (i = 0; i < outSk.size(); ++i) + { //mask amount and mask rv.ecdhInfo[i].mask = copy(outSk[i].mask); rv.ecdhInfo[i].amount = d2h(amounts[i]); @@ -725,12 +737,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, RangeProofBorromean, hwdev); } //RCT simple //for post-rct only - rctSig genRctSimple(const key &message, const ctkeyV & inSk, const keyV & destinations, const vector &inamounts, const vector &outamounts, xmr_amount txnFee, const ctkeyM & mixRing, const keyV &amount_keys, const std::vector *kLRki, multisig_out *msout, const std::vector & index, ctkeyV &outSk, bool bulletproof, hw::device &hwdev) { + rctSig genRctSimple(const key &message, const ctkeyV & inSk, const keyV & destinations, const vector &inamounts, const vector &outamounts, xmr_amount txnFee, const ctkeyM & mixRing, const keyV &amount_keys, const std::vector *kLRki, multisig_out *msout, const std::vector & 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"); @@ -822,7 +835,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 @@ -838,10 +851,11 @@ namespace rct { bool verRct(const rctSig & rv, bool semantics) { PERF_TIMER(verRct); CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull || rv.type == RCTTypeFullBulletproof, false, "verRct called on non-full rctSig"); + const bool bulletproof = is_rct_bulletproof(rv.type); 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"); + if (bulletproof) + CHECK_AND_ASSERT_MES(rv.outPk.size() == n_bulletproof_amounts(rv.p.bulletproofs), false, "Mismatched sizes of outPk and bulletproofs"); else CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.p.rangeSigs.size(), false, "Mismatched sizes of outPk and rv.p.rangeSigs"); CHECK_AND_ASSERT_MES(rv.outPk.size() == rv.ecdhInfo.size(), false, "Mismatched sizes of outPk and rv.ecdhInfo"); @@ -858,21 +872,19 @@ namespace rct { if (semantics) { tools::threadpool& tpool = tools::threadpool::getInstance(); tools::threadpool::waiter waiter; - std::deque results(rv.outPk.size(), false); + std::deque results(bulletproof ? rv.p.bulletproofs.size() : 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); - } + if (bulletproof) + for (size_t i = 0; i < rv.p.bulletproofs.size(); i++) + tpool.submit(&waiter, [&, i] { results[i] = verBulletproof(rv.p.bulletproofs[i]); }); + else + for (size_t i = 0; i < rv.outPk.size(); i++) + tpool.submit(&waiter, [&, i] { results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); }); 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; } } @@ -912,11 +924,12 @@ namespace rct { PERF_TIMER(verRctSimple); CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple || rv.type == RCTTypeSimpleBulletproof, false, "verRctSimple called on non simple rctSig"); + const bool bulletproof = is_rct_bulletproof(rv.type); if (semantics) { - if (rv.type == RCTTypeSimpleBulletproof) + 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"); } @@ -931,7 +944,7 @@ namespace rct { else { // semantics check is early, and mixRing/MGs aren't resolved yet - if (rv.type == RCTTypeSimpleBulletproof) + 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"); @@ -943,7 +956,7 @@ namespace rct { tools::threadpool& tpool = tools::threadpool::getInstance(); tools::threadpool::waiter waiter; - const keyV &pseudoOuts = is_bulletproof(rv.type) ? rv.p.pseudoOuts : rv.pseudoOuts; + const keyV &pseudoOuts = bulletproof ? rv.p.pseudoOuts : rv.pseudoOuts; if (semantics) { key sumOutpks = identity(); @@ -967,20 +980,18 @@ namespace rct { } 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); - } + results.resize(bulletproof ? rv.p.bulletproofs.size() : rv.outPk.size()); + if (bulletproof) + for (size_t i = 0; i < rv.p.bulletproofs.size(); i++) + tpool.submit(&waiter, [&, i] { results[i] = verBulletproof(rv.p.bulletproofs[i]); }); + else + for (size_t i = 0; i < rv.p.rangeSigs.size(); i++) + tpool.submit(&waiter, [&, i] { results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); }); waiter.wait(&tpool); for (size_t i = 0; i < results.size(); ++i) { 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; } } -- cgit v1.2.3