src/zerocoin/AccumulatorProofOfKnowledge.cpp

   1 /**
   2  * @file       AccumulatorProofOfKnowledge.cpp
   3  *
   4  * @brief      AccumulatorProofOfKnowledge 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 AccumulatorProofOfKnowledge::AccumulatorProofOfKnowledge(const AccumulatorAndProofParams* p): params(p) {}
  18
  19 AccumulatorProofOfKnowledge::AccumulatorProofOfKnowledge(const AccumulatorAndProofParams* p,
  20         const Commitment& commitmentToCoin, const AccumulatorWitness& witness,
  21         Accumulator& a): params(p) {
  22
  23         Bignum sg = params->accumulatorPoKCommitmentGroup.g;
  24         Bignum sh = params->accumulatorPoKCommitmentGroup.h;
  25
  26         Bignum g_n = params->accumulatorQRNCommitmentGroup.g;
  27         Bignum h_n = params->accumulatorQRNCommitmentGroup.h;
  28
  29         Bignum e = commitmentToCoin.getContents();
  30         Bignum r = commitmentToCoin.getRandomness();
  31
  32         Bignum r_1 = Bignum::randBignum(params->accumulatorModulus/4);
  33         Bignum r_2 = Bignum::randBignum(params->accumulatorModulus/4);
  34         Bignum r_3 = Bignum::randBignum(params->accumulatorModulus/4);
  35
  36         this->C_e = g_n.pow_mod(e, params->accumulatorModulus) * h_n.pow_mod(r_1, params->accumulatorModulus);
  37         this->C_u = witness.getValue() * h_n.pow_mod(r_2, params->accumulatorModulus);
  38         this->C_r = g_n.pow_mod(r_2, params->accumulatorModulus) * h_n.pow_mod(r_3, params->accumulatorModulus);
  39
  40         Bignum r_alpha = Bignum::randBignum(params->maxCoinValue * Bignum(2).pow(params->k_prime + params->k_dprime));
  41         if(!(Bignum::randBignum(Bignum(3)) % 2)) {
  42                 r_alpha = 0-r_alpha;
  43         }
  44
  45         Bignum r_gamma = Bignum::randBignum(params->accumulatorPoKCommitmentGroup.modulus);
  46         Bignum r_phi = Bignum::randBignum(params->accumulatorPoKCommitmentGroup.modulus);
  47         Bignum r_psi = Bignum::randBignum(params->accumulatorPoKCommitmentGroup.modulus);
  48         Bignum r_sigma = Bignum::randBignum(params->accumulatorPoKCommitmentGroup.modulus);
  49         Bignum r_xi = Bignum::randBignum(params->accumulatorPoKCommitmentGroup.modulus);
  50
  51         Bignum r_epsilon =  Bignum::randBignum((params->accumulatorModulus/4) * Bignum(2).pow(params->k_prime + params->k_dprime));
  52         if(!(Bignum::randBignum(Bignum(3)) % 2)) {
  53                 r_epsilon = 0-r_epsilon;
  54         }
  55         Bignum r_eta = Bignum::randBignum((params->accumulatorModulus/4) * Bignum(2).pow(params->k_prime + params->k_dprime));
  56         if(!(Bignum::randBignum(Bignum(3)) % 2)) {
  57                 r_eta = 0-r_eta;
  58         }
  59         Bignum r_zeta = Bignum::randBignum((params->accumulatorModulus/4) * Bignum(2).pow(params->k_prime + params->k_dprime));
  60         if(!(Bignum::randBignum(Bignum(3)) % 2)) {
  61                 r_zeta = 0-r_zeta;
  62         }
  63
  64         Bignum r_beta = Bignum::randBignum((params->accumulatorModulus/4) * params->accumulatorPoKCommitmentGroup.modulus * Bignum(2).pow(params->k_prime + params->k_dprime));
  65         if(!(Bignum::randBignum(Bignum(3)) % 2)) {
  66                 r_beta = 0-r_beta;
  67         }
  68         Bignum r_delta = Bignum::randBignum((params->accumulatorModulus/4) * params->accumulatorPoKCommitmentGroup.modulus * Bignum(2).pow(params->k_prime + params->k_dprime));
  69         if(!(Bignum::randBignum(Bignum(3)) % 2)) {
  70                 r_delta = 0-r_delta;
  71         }
  72
  73         this->st_1 = (sg.pow_mod(r_alpha, params->accumulatorPoKCommitmentGroup.modulus) * sh.pow_mod(r_phi, params->accumulatorPoKCommitmentGroup.modulus)) % params->accumulatorPoKCommitmentGroup.modulus;
  74         this->st_2 = (((commitmentToCoin.getCommitmentValue() * sg.inverse(params->accumulatorPoKCommitmentGroup.modulus)).pow_mod(r_gamma, params->accumulatorPoKCommitmentGroup.modulus)) * sh.pow_mod(r_psi, params->accumulatorPoKCommitmentGroup.modulus)) % params->accumulatorPoKCommitmentGroup.modulus;
  75         this->st_3 = ((sg * commitmentToCoin.getCommitmentValue()).pow_mod(r_sigma, params->accumulatorPoKCommitmentGroup.modulus) * sh.pow_mod(r_xi, params->accumulatorPoKCommitmentGroup.modulus)) % params->accumulatorPoKCommitmentGroup.modulus;
  76
  77         this->t_1 = (h_n.pow_mod(r_zeta, params->accumulatorModulus) * g_n.pow_mod(r_epsilon, params->accumulatorModulus)) % params->accumulatorModulus;
  78         this->t_2 = (h_n.pow_mod(r_eta, params->accumulatorModulus) * g_n.pow_mod(r_alpha, params->accumulatorModulus)) % params->accumulatorModulus;
  79         this->t_3 = (C_u.pow_mod(r_alpha, params->accumulatorModulus) * ((h_n.inverse(params->accumulatorModulus)).pow_mod(r_beta, params->accumulatorModulus))) % params->accumulatorModulus;
  80         this->t_4 = (C_r.pow_mod(r_alpha, params->accumulatorModulus) * ((h_n.inverse(params->accumulatorModulus)).pow_mod(r_delta, params->accumulatorModulus)) * ((g_n.inverse(params->accumulatorModulus)).pow_mod(r_beta, params->accumulatorModulus))) % params->accumulatorModulus;
  81
  82         CHashWriter hasher(0,0);
  83         hasher << *params << sg << sh << g_n << h_n << commitmentToCoin.getCommitmentValue() << C_e << C_u << C_r << st_1 << st_2 << st_3 << t_1 << t_2 << t_3 << t_4;
  84
  85         //According to the proof, this hash should be of length k_prime bits.  It is currently greater than that, which should not be a problem, but we should check this.
  86         Bignum c = Bignum(hasher.GetHash());
  87
  88         this->s_alpha = r_alpha - c*e;
  89         this->s_beta = r_beta - c*r_2*e;
  90         this->s_zeta = r_zeta - c*r_3;
  91         this->s_sigma = r_sigma - c*((e+1).inverse(params->accumulatorPoKCommitmentGroup.groupOrder));
  92         this->s_eta = r_eta - c*r_1;
  93         this->s_epsilon = r_epsilon - c*r_2;
  94         this->s_delta = r_delta - c*r_3*e;
  95         this->s_xi = r_xi + c*r*((e+1).inverse(params->accumulatorPoKCommitmentGroup.groupOrder));
  96         this->s_phi = (r_phi - c*r) % params->accumulatorPoKCommitmentGroup.groupOrder;
  97         this->s_gamma = r_gamma - c*((e-1).inverse(params->accumulatorPoKCommitmentGroup.groupOrder));
  98         this->s_psi = r_psi + c*r*((e-1).inverse(params->accumulatorPoKCommitmentGroup.groupOrder));
  99 }
 100
 101 /** Verifies that a commitment c is accumulated in accumulator a
 102  */
 103 bool AccumulatorProofOfKnowledge:: Verify(const Accumulator& a, const Bignum& valueOfCommitmentToCoin) const {
 104         Bignum sg = params->accumulatorPoKCommitmentGroup.g;
 105         Bignum sh = params->accumulatorPoKCommitmentGroup.h;
 106
 107         Bignum g_n = params->accumulatorQRNCommitmentGroup.g;
 108         Bignum h_n = params->accumulatorQRNCommitmentGroup.h;
 109
 110         //According to the proof, this hash should be of length k_prime bits.  It is currently greater than that, which should not be a problem, but we should check this.
 111         CHashWriter hasher(0,0);
 112         hasher << *params << sg << sh << g_n << h_n << valueOfCommitmentToCoin << C_e << C_u << C_r << st_1 << st_2 << st_3 << t_1 << t_2 << t_3 << t_4;
 113
 114         Bignum c = Bignum(hasher.GetHash()); //this hash should be of length k_prime bits
 115
 116         Bignum st_1_prime = (valueOfCommitmentToCoin.pow_mod(c, params->accumulatorPoKCommitmentGroup.modulus) * sg.pow_mod(s_alpha, params->accumulatorPoKCommitmentGroup.modulus) * sh.pow_mod(s_phi, params->accumulatorPoKCommitmentGroup.modulus)) % params->accumulatorPoKCommitmentGroup.modulus;
 117         Bignum st_2_prime = (sg.pow_mod(c, params->accumulatorPoKCommitmentGroup.modulus) * ((valueOfCommitmentToCoin * sg.inverse(params->accumulatorPoKCommitmentGroup.modulus)).pow_mod(s_gamma, params->accumulatorPoKCommitmentGroup.modulus)) * sh.pow_mod(s_psi, params->accumulatorPoKCommitmentGroup.modulus)) % params->accumulatorPoKCommitmentGroup.modulus;
 118         Bignum st_3_prime = (sg.pow_mod(c, params->accumulatorPoKCommitmentGroup.modulus) * (sg * valueOfCommitmentToCoin).pow_mod(s_sigma, params->accumulatorPoKCommitmentGroup.modulus) * sh.pow_mod(s_xi, params->accumulatorPoKCommitmentGroup.modulus)) % params->accumulatorPoKCommitmentGroup.modulus;
 119
 120         Bignum t_1_prime = (C_r.pow_mod(c, params->accumulatorModulus) * h_n.pow_mod(s_zeta, params->accumulatorModulus) * g_n.pow_mod(s_epsilon, params->accumulatorModulus)) % params->accumulatorModulus;
 121         Bignum t_2_prime = (C_e.pow_mod(c, params->accumulatorModulus) * h_n.pow_mod(s_eta, params->accumulatorModulus) * g_n.pow_mod(s_alpha, params->accumulatorModulus)) % params->accumulatorModulus;
 122         Bignum t_3_prime = ((a.getValue()).pow_mod(c, params->accumulatorModulus) * C_u.pow_mod(s_alpha, params->accumulatorModulus) * ((h_n.inverse(params->accumulatorModulus)).pow_mod(s_beta, params->accumulatorModulus))) % params->accumulatorModulus;
 123         Bignum t_4_prime = (C_r.pow_mod(s_alpha, params->accumulatorModulus) * ((h_n.inverse(params->accumulatorModulus)).pow_mod(s_delta, params->accumulatorModulus)) * ((g_n.inverse(params->accumulatorModulus)).pow_mod(s_beta, params->accumulatorModulus))) % params->accumulatorModulus;
 124
 125         bool result = false;
 126
 127         bool result_st1 = (st_1 == st_1_prime);
 128         bool result_st2 = (st_2 == st_2_prime);
 129         bool result_st3 = (st_3 == st_3_prime);
 130
 131         bool result_t1 = (t_1 == t_1_prime);
 132         bool result_t2 = (t_2 == t_2_prime);
 133         bool result_t3 = (t_3 == t_3_prime);
 134         bool result_t4 = (t_4 == t_4_prime);
 135
 136         bool result_range = ((s_alpha >= -(params->maxCoinValue * Bignum(2).pow(params->k_prime + params->k_dprime + 1))) && (s_alpha <= (params->maxCoinValue * Bignum(2).pow(params->k_prime + params->k_dprime + 1))));
 137
 138         result = result_st1 && result_st2 && result_st3 && result_t1 && result_t2 && result_t3 && result_t4 && result_range;
 139
 140         return result;
 141 }
 142
 143 } /* namespace libzerocoin */