diff options
Diffstat (limited to 'src/ringct/rctSigs.cpp')
-rw-r--r-- | src/ringct/rctSigs.cpp | 343 |
1 files changed, 195 insertions, 148 deletions
diff --git a/src/ringct/rctSigs.cpp b/src/ringct/rctSigs.cpp index ed1f8cc0e..8efd6a07c 100644 --- a/src/ringct/rctSigs.cpp +++ b/src/ringct/rctSigs.cpp @@ -29,101 +29,64 @@ // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "misc_log_ex.h" +#include "common/perf_timer.h" +#include "common/task_region.h" +#include "common/thread_group.h" +#include "common/util.h" #include "rctSigs.h" -#include "cryptonote_core/cryptonote_format_utils.h" +#include "cryptonote_basic/cryptonote_format_utils.h" using namespace crypto; using namespace std; +#undef MONERO_DEFAULT_LOG_CATEGORY +#define MONERO_DEFAULT_LOG_CATEGORY "ringct" + namespace rct { - - //Schnorr Non-linkable - //Gen Gives a signature (L1, s1, s2) proving that the sender knows "x" such that xG = one of P1 or P2 - //Ver Verifies that signer knows an "x" such that xG = one of P1 or P2 - //These are called in the below ASNL sig generation - - void GenSchnorrNonLinkable(key & L1, key & s1, key & s2, const key & x, const key & P1, const key & P2, int index) { - key c1, c2, L2; - key a = skGen(); - if (index == 0) { - scalarmultBase(L1, a); - hash_to_scalar(c2, L1); - skGen(s2); - addKeys2(L2, s2, c2, P2); - hash_to_scalar(c1, L2); - //s1 = a - x * c1 - sc_mulsub(s1.bytes, x.bytes, c1.bytes, a.bytes); - } - else if (index == 1) { - scalarmultBase(L2, a); - hash_to_scalar(c1, L2); - skGen(s1); - addKeys2(L1, s1, c1, P1); - hash_to_scalar(c2, L1); - sc_mulsub(s2.bytes, x.bytes, c2.bytes, a.bytes); + //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; + key c; + int naught = 0, prime = 0, ii = 0, jj=0; + boroSig bb; + for (ii = 0 ; ii < 64 ; ii++) { + naught = indices[ii]; prime = (indices[ii] + 1) % 2; + skGen(alpha[ii]); + scalarmultBase(L[naught][ii], alpha[ii]); + if (naught == 0) { + skGen(bb.s1[ii]); + c = hash_to_scalar(L[naught][ii]); + addKeys2(L[prime][ii], bb.s1[ii], c, P2[ii]); + } } - else { - throw std::runtime_error("GenSchnorrNonLinkable: invalid index (should be 0 or 1)"); + bb.ee = hash_to_scalar(L[1]); //or L[1].. + key LL, cc; + for (jj = 0 ; jj < 64 ; jj++) { + if (!indices[jj]) { + sc_mulsub(bb.s0[jj].bytes, x[jj].bytes, bb.ee.bytes, alpha[jj].bytes); + } else { + skGen(bb.s0[jj]); + addKeys2(LL, bb.s0[jj], bb.ee, P1[jj]); //different L0 + cc = hash_to_scalar(LL); + sc_mulsub(bb.s1[jj].bytes, x[jj].bytes, cc.bytes, alpha[jj].bytes); + } } - } - - //Schnorr Non-linkable - //Gen Gives a signature (L1, s1, s2) proving that the sender knows "x" such that xG = one of P1 or P2 - //Ver Verifies that signer knows an "x" such that xG = one of P1 or P2 - //These are called in the below ASNL sig generation - bool VerSchnorrNonLinkable(const key & P1, const key & P2, const key & L1, const key & s1, const key & s2) { - key c2, L2, c1, L1p; - hash_to_scalar(c2, L1); - addKeys2(L2, s2, c2, P2); - hash_to_scalar(c1, L2); - addKeys2(L1p, s1, c1, P1); - - return equalKeys(L1, L1p); + return bb; } - //Aggregate Schnorr Non-linkable Ring Signature (ASNL) - // c.f. http://eprint.iacr.org/2015/1098 section 5. - // These are used in range proofs (alternatively Borromean could be used) - // Gen gives a signature which proves the signer knows, for each i, - // an x[i] such that x[i]G = one of P1[i] or P2[i] - // Ver Verifies the signer knows a key for one of P1[i], P2[i] at each i - asnlSig GenASNL(key64 x, key64 P1, key64 P2, bits indices) { - DP("Generating Aggregate Schnorr Non-linkable Ring Signature\n"); - key64 s1; - int j = 0; - asnlSig rv; - rv.s = zero(); - for (j = 0; j < ATOMS; j++) { - GenSchnorrNonLinkable(rv.L1[j], s1[j], rv.s2[j], x[j], P1[j], P2[j], (int)indices[j]); - sc_add(rv.s.bytes, rv.s.bytes, s1[j].bytes); - } - return rv; + //see above. + bool verifyBorromean(const boroSig &bb, const key64 P1, const key64 P2) { + key64 Lv1; key chash, LL; + int ii = 0; + for (ii = 0 ; ii < 64 ; ii++) { + addKeys2(LL, bb.s0[ii], bb.ee, P1[ii]); + chash = hash_to_scalar(LL); + addKeys2(Lv1[ii], bb.s1[ii], chash, P2[ii]); + } + key eeComputed = hash_to_scalar(Lv1); //hash function fine + return equalKeys(eeComputed, bb.ee); } - //Aggregate Schnorr Non-linkable Ring Signature (ASNL) - // c.f. http://eprint.iacr.org/2015/1098 section 5. - // These are used in range proofs (alternatively Borromean could be used) - // Gen gives a signature which proves the signer knows, for each i, - // an x[i] such that x[i]G = one of P1[i] or P2[i] - // Ver Verifies the signer knows a key for one of P1[i], P2[i] at each i - bool VerASNL(const key64 P1, const key64 P2, const asnlSig &as) { - DP("Verifying Aggregate Schnorr Non-linkable Ring Signature\n"); - key LHS = identity(); - key RHS = scalarmultBase(as.s); - key c2, L2, c1; - int j = 0; - for (j = 0; j < ATOMS; j++) { - hash_to_scalar(c2, as.L1[j]); - addKeys2(L2, as.s2[j], c2, P2[j]); - addKeys(LHS, LHS, as.L1[j]); - hash_to_scalar(c1, L2); - addKeys(RHS, RHS, scalarmultKey(P1[j], c1)); - } - key cc; - sc_sub(cc.bytes, LHS.bytes, RHS.bytes); - return sc_isnonzero(cc.bytes) == 0; - } - //Multilayered Spontaneous Anonymous Group Signatures (MLSAG signatures) //These are aka MG signatutes in earlier drafts of the ring ct paper // c.f. http://eprint.iacr.org/2015/1098 section 2. @@ -150,7 +113,7 @@ namespace rct { // Gen creates a signature which proves that for some column in the keymatrix "pk" // the signer knows a secret key for each row in that column // Ver verifies that the MG sig was created correctly - mgSig MLSAG_Gen(key message, const keyM & pk, const keyV & xx, const unsigned int index, size_t dsRows) { + mgSig MLSAG_Gen(const key &message, const keyM & pk, const keyV & xx, const unsigned int index, size_t dsRows) { mgSig rv; size_t cols = pk.size(); CHECK_AND_ASSERT_THROW_MES(cols >= 2, "Error! What is c if cols = 1!"); @@ -239,7 +202,7 @@ namespace rct { // Gen creates a signature which proves that for some column in the keymatrix "pk" // the signer knows a secret key for each row in that column // Ver verifies that the MG sig was created correctly - bool MLSAG_Ver(key message, const keyM & pk, const mgSig & rv, size_t dsRows) { + bool MLSAG_Ver(const key &message, const keyM & pk, const mgSig & rv, size_t dsRows) { size_t cols = pk.size(); CHECK_AND_ASSERT_MES(cols >= 2, false, "Error! What is c if cols = 1!"); @@ -255,6 +218,11 @@ namespace rct { } CHECK_AND_ASSERT_MES(dsRows <= rows, false, "Bad dsRows value"); + for (size_t i = 0; i < rv.ss.size(); ++i) + for (size_t j = 0; j < rv.ss[i].size(); ++j) + CHECK_AND_ASSERT_MES(sc_check(rv.ss[i][j].bytes) == 0, false, "Bad ss slot"); + CHECK_AND_ASSERT_MES(sc_check(rv.cc.bytes) == 0, false, "Bad cc"); + size_t i = 0, j = 0, ii = 0; key c, L, R, Hi; key c_old = copy(rv.cc); @@ -319,7 +287,7 @@ namespace rct { sc_add(mask.bytes, mask.bytes, ai[i].bytes); addKeys(C, C, sig.Ci[i]); } - sig.asig = GenASNL(ai, sig.Ci, CiH, b); + sig.asig = genBorromean(ai, sig.Ci, CiH, b); return sig; } @@ -331,6 +299,9 @@ namespace rct { // mask is a such that C = aG + bH, and b = amount //verRange verifies that \sum Ci = C and that each Ci is a commitment to 0 or 2^i bool verRange(const key & C, const rangeSig & as) { + try + { + PERF_TIMER(verRange); key64 CiH; int i = 0; key Ctmp = identity(); @@ -340,14 +311,18 @@ namespace rct { } if (!equalKeys(C, Ctmp)) return false; - if (!VerASNL(as.Ci, CiH, as.asig)) + if (!verifyBorromean(as.asig, as.Ci, CiH)) return false; return true; + } + // we can get deep throws from ge_frombytes_vartime if input isn't valid + catch (...) { return false; } } key get_pre_mlsag_hash(const rctSig &rv) { keyV hashes; + hashes.reserve(3); hashes.push_back(rv.message); crypto::hash h; @@ -361,13 +336,14 @@ namespace rct { hashes.push_back(hash2rct(h)); keyV kv; + kv.reserve((64*3+1) * rv.p.rangeSigs.size()); for (auto r: rv.p.rangeSigs) { for (size_t n = 0; n < 64; ++n) - kv.push_back(r.asig.L1[n]); + kv.push_back(r.asig.s0[n]); for (size_t n = 0; n < 64; ++n) - kv.push_back(r.asig.s2[n]); - kv.push_back(r.asig.s); + kv.push_back(r.asig.s1[n]); + kv.push_back(r.asig.ee); for (size_t n = 0; n < 64; ++n) kv.push_back(r.Ci[n]); } @@ -467,6 +443,7 @@ namespace rct { //Ver: // verifies the above sig is created corretly bool verRctMG(const mgSig &mg, const ctkeyM & pubs, const ctkeyV & outPk, key txnFeeKey, const key &message) { + PERF_TIMER(verRctMG); //setup vars size_t cols = pubs.size(); CHECK_AND_ASSERT_MES(cols >= 1, false, "Empty pubs"); @@ -505,6 +482,9 @@ namespace rct { //This does a simplified version, assuming only post Rct //inputs bool verRctMGSimple(const key &message, const mgSig &mg, const ctkeyV & pubs, const key & C) { + try + { + PERF_TIMER(verRctMGSimple); //setup vars size_t rows = 1; size_t cols = pubs.size(); @@ -519,8 +499,11 @@ namespace rct { } //DP(C); return MLSAG_Ver(message, M, mg, rows); + } + catch (...) { return false; } } + //These functions get keys from blockchain //replace these when connecting blockchain //getKeyFromBlockchain grabs a key from the blockchain at "reference_index" to mix with @@ -583,6 +566,7 @@ namespace rct { // 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, unsigned int index, ctkeyV &outSk) { 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"); for (size_t n = 0; n < mixRing.size(); ++n) { CHECK_AND_ASSERT_THROW_MES(mixRing[n].size() == inSk.size(), "Bad mixRing size"); @@ -644,6 +628,7 @@ namespace rct { 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"); + CHECK_AND_ASSERT_THROW_MES(amount_keys.size() == destinations.size(), "Different number of amount_keys/destinations"); CHECK_AND_ASSERT_THROW_MES(index.size() == inSk.size(), "Different number of index/inSk"); CHECK_AND_ASSERT_THROW_MES(mixRing.size() == inSk.size(), "Different number of mixRing/inSk"); for (size_t n = 0; n < mixRing.size(); ++n) { @@ -728,34 +713,54 @@ namespace rct { //decodeRct: (c.f. http://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 - bool verRct(const rctSig & rv) { + bool verRct(const rctSig & rv, bool semantics) { + PERF_TIMER(verRct); CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull, false, "verRct called on non-full rctSig"); - 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"); + if (semantics) + { + 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"); + } + else + { + // semantics check is early, we don't have the MGs resolved yet + } // some rct ops can throw try { - size_t i = 0; - bool tmp; - DP("range proofs verified?"); - for (i = 0; i < rv.outPk.size(); i++) { - tmp = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); - DP(tmp); - if (!tmp) { - LOG_ERROR("Range proof verification failed for input " << i); + if (semantics) { + std::deque<bool> results(rv.outPk.size(), false); + tools::thread_group threadpool(tools::thread_group::optimal_with_max(rv.outPk.size())); + + tools::task_region(threadpool, [&] (tools::task_region_handle& region) { + DP("range proofs verified?"); + for (size_t i = 0; i < rv.outPk.size(); i++) { + region.run([&, i] { + results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); + }); + } + }); + + for (size_t i = 0; i < rv.outPk.size(); ++i) { + if (!results[i]) { + LOG_PRINT_L1("Range proof verified failed for output " << i); return false; } + } } - //compute txn fee - key txnFeeKey = scalarmultH(d2h(rv.txnFee)); - bool mgVerd = verRctMG(rv.p.MGs[0], rv.mixRing, rv.outPk, txnFeeKey, get_pre_mlsag_hash(rv)); - DP("mg sig verified?"); - DP(mgVerd); - if (!mgVerd) { - LOG_ERROR("MG signature verification failed"); - return false; + + if (!semantics) { + //compute txn fee + key txnFeeKey = scalarmultH(d2h(rv.txnFee)); + bool mgVerd = verRctMG(rv.p.MGs[0], rv.mixRing, rv.outPk, txnFeeKey, get_pre_mlsag_hash(rv)); + DP("mg sig verified?"); + DP(mgVerd); + if (!mgVerd) { + LOG_PRINT_L1("MG signature verification failed"); + return false; + } } return true; @@ -768,48 +773,92 @@ namespace rct { //ver RingCT simple //assumes only post-rct style inputs (at least for max anonymity) - bool verRctSimple(const rctSig & rv) { - size_t i = 0; + bool verRctSimple(const rctSig & rv, bool semantics) { + try + { + PERF_TIMER(verRctSimple); CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple, false, "verRctSimple called on non simple rctSig"); - 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.pseudoOuts.size() == rv.p.MGs.size(), false, "Mismatched sizes of rv.pseudoOuts and rv.p.MGs"); - CHECK_AND_ASSERT_MES(rv.pseudoOuts.size() == rv.mixRing.size(), false, "Mismatched sizes of rv.pseudoOuts and mixRing"); - - key sumOutpks = identity(); - for (i = 0; i < rv.outPk.size(); i++) { - if (!verRange(rv.outPk[i].mask, rv.p.rangeSigs[i])) { - LOG_ERROR("Range proof verified failed for input " << i); - return false; - } - addKeys(sumOutpks, sumOutpks, rv.outPk[i].mask); + if (semantics) + { + 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.pseudoOuts.size() == rv.p.MGs.size(), false, "Mismatched sizes of rv.pseudoOuts and rv.p.MGs"); } - DP(sumOutpks); - key txnFeeKey = scalarmultH(d2h(rv.txnFee)); - addKeys(sumOutpks, txnFeeKey, sumOutpks); - - bool tmpb = false; - key message = get_pre_mlsag_hash(rv); - key sumPseudoOuts = identity(); - for (i = 0 ; i < rv.mixRing.size() ; i++) { - tmpb = verRctMGSimple(message, rv.p.MGs[i], rv.mixRing[i], rv.pseudoOuts[i]); - addKeys(sumPseudoOuts, sumPseudoOuts, rv.pseudoOuts[i]); - DP(tmpb); - if (!tmpb) { - LOG_ERROR("verRctMGSimple failed for input " << i); - return false; + else + { + // semantics check is early, and mixRing/MGs aren't resolved yet + 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::thread_group threadpool(tools::thread_group::optimal_with_max(threads)); + + if (semantics) { + key sumOutpks = identity(); + for (size_t i = 0; i < rv.outPk.size(); i++) { + addKeys(sumOutpks, sumOutpks, rv.outPk[i].mask); + } + DP(sumOutpks); + key txnFeeKey = scalarmultH(d2h(rv.txnFee)); + addKeys(sumOutpks, txnFeeKey, sumOutpks); + + key sumPseudoOuts = identity(); + for (size_t i = 0 ; i < rv.pseudoOuts.size() ; i++) { + addKeys(sumPseudoOuts, sumPseudoOuts, rv.pseudoOuts[i]); + } + DP(sumPseudoOuts); + + //check pseudoOuts vs Outs.. + if (!equalKeys(sumPseudoOuts, sumOutpks)) { + LOG_PRINT_L1("Sum check failed"); + return false; + } + + results.clear(); + results.resize(rv.outPk.size()); + tools::task_region(threadpool, [&] (tools::task_region_handle& region) { + for (size_t i = 0; i < rv.outPk.size(); i++) { + region.run([&, i] { + results[i] = verRange(rv.outPk[i].mask, rv.p.rangeSigs[i]); + }); + } + }); + + for (size_t i = 0; i < results.size(); ++i) { + if (!results[i]) { + LOG_PRINT_L1("Range proof verified failed for output " << i); + return false; } + } } - DP(sumPseudoOuts); - - //check pseudoOuts vs Outs.. - if (!equalKeys(sumPseudoOuts, sumOutpks)) { - LOG_ERROR("Sum check failed"); - return false; + else { + const key message = get_pre_mlsag_hash(rv); + + results.clear(); + results.resize(rv.mixRing.size()); + tools::task_region(threadpool, [&] (tools::task_region_handle& region) { + for (size_t i = 0 ; i < rv.mixRing.size() ; i++) { + region.run([&, i] { + results[i] = verRctMGSimple(message, rv.p.MGs[i], rv.mixRing[i], rv.pseudoOuts[i]); + }); + } + }); + + 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 (...) { return false; } } //RingCT protocol @@ -824,8 +873,7 @@ namespace rct { // 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) { CHECK_AND_ASSERT_MES(rv.type == RCTTypeFull, false, "decodeRct called on non-full rctSig"); - CHECK_AND_ASSERT_THROW_MES(rv.p.rangeSigs.size() > 0, "Empty rv.p.rangeSigs"); - CHECK_AND_ASSERT_THROW_MES(rv.outPk.size() == rv.p.rangeSigs.size(), "Mismatched sizes of rv.outPk and rv.p.rangeSigs"); + CHECK_AND_ASSERT_THROW_MES(rv.outPk.size() == rv.ecdhInfo.size(), "Mismatched sizes of rv.outPk and rv.ecdhInfo"); CHECK_AND_ASSERT_THROW_MES(i < rv.ecdhInfo.size(), "Bad index"); //mask amount and mask @@ -853,8 +901,7 @@ namespace rct { xmr_amount decodeRctSimple(const rctSig & rv, const key & sk, unsigned int i, key &mask) { CHECK_AND_ASSERT_MES(rv.type == RCTTypeSimple, false, "decodeRct called on non simple rctSig"); - CHECK_AND_ASSERT_THROW_MES(rv.p.rangeSigs.size() > 0, "Empty rv.p.rangeSigs"); - CHECK_AND_ASSERT_THROW_MES(rv.outPk.size() == rv.p.rangeSigs.size(), "Mismatched sizes of rv.outPk and rv.p.rangeSigs"); + CHECK_AND_ASSERT_THROW_MES(rv.outPk.size() == rv.ecdhInfo.size(), "Mismatched sizes of rv.outPk and rv.ecdhInfo"); CHECK_AND_ASSERT_THROW_MES(i < rv.ecdhInfo.size(), "Bad index"); //mask amount and mask |