src/zerocoin/SerialNumberSignatureOfKnowledge.cpp

   1 /**
   2 * @file       SerialNumberSignatureOfKnowledge.cpp
   3 *
   4 * @brief      SerialNumberSignatureOfKnowledge class for the Zerocoin library.
   5 *
   6 * @author     Ian Miers, Christina Garman and Matthew Green
   7 * @date       June 2013
   8 *
   9 * @copyright  Copyright 2013 Ian Miers, Christina Garman and Matthew Green
  10 * @license    This project is released under the MIT license.
  11 **/
  12
  13 #include "Zerocoin.h"
  14
  15 namespace libzerocoin {
  16
  17 SerialNumberSignatureOfKnowledge::SerialNumberSignatureOfKnowledge(const Params* p): params(p) { }
  18
  19 SerialNumberSignatureOfKnowledge::SerialNumberSignatureOfKnowledge(const
  20         Params* p, const PrivateCoin& coin, const Commitment& commitmentToCoin,
  21         uint256 msghash):params(p),
  22         s_notprime(p->zkp_iterations),
  23         sprime(p->zkp_iterations) {
  24
  25         // Sanity check: verify that the order of the "accumulatedValueCommitmentGroup" is
  26         // equal to the modulus of "coinCommitmentGroup". Otherwise we will produce invalid
  27         // proofs.
  28         if (params->coinCommitmentGroup.modulus != params->serialNumberSoKCommitmentGroup.groupOrder) {
  29                 throw ZerocoinException("Groups are not structured correctly.");
  30         }
  31
  32         Bignum a = params->coinCommitmentGroup.g;
  33         Bignum b = params->coinCommitmentGroup.h;
  34         Bignum g = params->serialNumberSoKCommitmentGroup.g;
  35         Bignum h = params->serialNumberSoKCommitmentGroup.h;
  36
  37         CHashWriter hasher(0,0);
  38         hasher << *params << commitmentToCoin.getCommitmentValue() << coin.getSerialNumber();
  39
  40         vector<Bignum> r(params->zkp_iterations);
  41         vector<Bignum> v(params->zkp_iterations);
  42         vector<Bignum> c(params->zkp_iterations);
  43
  44
  45         for(uint32_t i=0; i < params->zkp_iterations; i++) {
  46                 //FIXME we really ought to use one BN_CTX for all of these
  47                 // operations for performance reasons, not the one that
  48                 // is created individually  by the wrapper
  49                 r[i] = Bignum::randBignum(params->coinCommitmentGroup.groupOrder);
  50                 v[i] = Bignum::randBignum(params->serialNumberSoKCommitmentGroup.groupOrder);
  51         }
  52
  53         // Openssl's rng is not thread safe, so we don't call it in a parallel loop,
  54         // instead we generate the random values beforehand and run the calculations
  55         // based on those values in parallel.
  56 #ifdef ZEROCOIN_THREADING
  57         #pragma omp parallel for
  58 #endif
  59         for(uint32_t i=0; i < params->zkp_iterations; i++) {
  60                 // compute g^{ {a^x b^r} h^v} mod p2
  61                 c[i] = challengeCalculation(coin.getSerialNumber(), r[i], v[i]);
  62         }
  63
  64         // We can't hash data in parallel either
  65         // because OPENMP cannot not guarantee loops
  66         // execute in order.
  67         for(uint32_t i=0; i < params->zkp_iterations; i++) {
  68                 hasher << c[i];
  69         }
  70         this->hash = hasher.GetHash();
  71         unsigned char *hashbytes =  (unsigned char*) &hash;
  72
  73 #ifdef ZEROCOIN_THREADING
  74         #pragma omp parallel for
  75 #endif
  76         for(uint32_t i = 0; i < params->zkp_iterations; i++) {
  77                 int bit = i % 8;
  78                 int byte = i / 8;
  79
  80                 bool challenge_bit = ((hashbytes[byte] >> bit) & 0x01);
  81                 if (challenge_bit) {
  82                         s_notprime[i]       = r[i];
  83                         sprime[i]           = v[i];
  84                 } else {
  85                         s_notprime[i]       = r[i] - coin.getRandomness();
  86                         sprime[i]           = v[i] - (commitmentToCoin.getRandomness() *
  87                                                       b.pow_mod(r[i] - coin.getRandomness(), params->serialNumberSoKCommitmentGroup.groupOrder));
  88                 }
  89         }
  90 }
  91
  92 inline Bignum SerialNumberSignatureOfKnowledge::challengeCalculation(const Bignum& a_exp,const Bignum& b_exp,
  93         const Bignum& h_exp) const {
  94
  95         Bignum a = params->coinCommitmentGroup.g;
  96         Bignum b = params->coinCommitmentGroup.h;
  97         Bignum g = params->serialNumberSoKCommitmentGroup.g;
  98         Bignum h = params->serialNumberSoKCommitmentGroup.h;
  99
 100         Bignum exponent = (a.pow_mod(a_exp, params->serialNumberSoKCommitmentGroup.groupOrder)
 101                            * b.pow_mod(b_exp, params->serialNumberSoKCommitmentGroup.groupOrder)) % params->serialNumberSoKCommitmentGroup.groupOrder;
 102
 103         return (g.pow_mod(exponent, params->serialNumberSoKCommitmentGroup.modulus) * h.pow_mod(h_exp, params->serialNumberSoKCommitmentGroup.modulus)) % params->serialNumberSoKCommitmentGroup.modulus;
 104 }
 105
 106 bool SerialNumberSignatureOfKnowledge::Verify(const Bignum& coinSerialNumber, const Bignum& valueOfCommitmentToCoin,
 107         const uint256 msghash) const {
 108         Bignum a = params->coinCommitmentGroup.g;
 109         Bignum b = params->coinCommitmentGroup.h;
 110         Bignum g = params->serialNumberSoKCommitmentGroup.g;
 111         Bignum h = params->serialNumberSoKCommitmentGroup.h;
 112         CHashWriter hasher(0,0);
 113         hasher << *params << valueOfCommitmentToCoin <<coinSerialNumber;
 114
 115         vector<CBigNum> tprime(params->zkp_iterations);
 116         unsigned char *hashbytes = (unsigned char*) &this->hash;
 117 #ifdef ZEROCOIN_THREADING
 118         #pragma omp parallel for
 119 #endif
 120         for(uint32_t i = 0; i < params->zkp_iterations; i++) {
 121                 int bit = i % 8;
 122                 int byte = i / 8;
 123                 bool challenge_bit = ((hashbytes[byte] >> bit) & 0x01);
 124                 if(challenge_bit) {
 125                         tprime[i] = challengeCalculation(coinSerialNumber, s_notprime[i], sprime[i]);
 126                 } else {
 127                         Bignum exp = b.pow_mod(s_notprime[i], params->serialNumberSoKCommitmentGroup.groupOrder);
 128                         tprime[i] = ((valueOfCommitmentToCoin.pow_mod(exp, params->serialNumberSoKCommitmentGroup.modulus) % params->serialNumberSoKCommitmentGroup.modulus) *
 129                                      (h.pow_mod(sprime[i], params->serialNumberSoKCommitmentGroup.modulus) % params->serialNumberSoKCommitmentGroup.modulus)) %
 130                                     params->serialNumberSoKCommitmentGroup.modulus;
 131                 }
 132         }
 133         for(uint32_t i = 0; i < params->zkp_iterations; i++) {
 134                 hasher << tprime[i];
 135         }
 136         return hasher.GetHash() == hash;
 137 }
 138
 139 } /* namespace libzerocoin */