src/zerocoin/Commitment.cpp

   1 /**
   2  * @file       Commitment.cpp
   3  *
   4  * @brief      Commitment and CommitmentProof classes 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 <stdlib.h>
  14 #include "Zerocoin.h"
  15
  16 namespace libzerocoin {
  17
  18 //Commitment class
  19 Commitment::Commitment(const IntegerGroupParams* p,
  20                                    const Bignum& value): params(p), contents(value) {
  21         this->randomness = Bignum::randBignum(params->groupOrder);
  22         this->commitmentValue = (params->g.pow_mod(this->contents, params->modulus).mul_mod(
  23                                  params->h.pow_mod(this->randomness, params->modulus), params->modulus));
  24 }
  25
  26 const Bignum& Commitment::getCommitmentValue() const {
  27         return this->commitmentValue;
  28 }
  29
  30 const Bignum& Commitment::getRandomness() const {
  31         return this->randomness;
  32 }
  33
  34 const Bignum& Commitment::getContents() const {
  35         return this->contents;
  36 }
  37
  38 //CommitmentProofOfKnowledge class
  39 CommitmentProofOfKnowledge::CommitmentProofOfKnowledge(const IntegerGroupParams* ap, const IntegerGroupParams* bp): ap(ap), bp(bp) {}
  40
  41 // TODO: get parameters from the commitment group
  42 CommitmentProofOfKnowledge::CommitmentProofOfKnowledge(const IntegerGroupParams* aParams,
  43         const IntegerGroupParams* bParams, const Commitment& a, const Commitment& b):
  44         ap(aParams),bp(bParams)
  45 {
  46         Bignum r1, r2, r3;
  47
  48         // First: make sure that the two commitments have the
  49         // same contents.
  50         if (a.getContents() != b.getContents()) {
  51                 throw std::invalid_argument("Both commitments must contain the same value");
  52         }
  53
  54         // Select three random values "r1, r2, r3" in the range 0 to (2^l)-1 where l is:
  55         // length of challenge value + max(modulus 1, modulus 2, order 1, order 2) + margin.
  56         // We set "margin" to be a relatively generous  security parameter.
  57         //
  58         // We choose these large values to ensure statistical zero knowledge.
  59         uint32_t randomSize = COMMITMENT_EQUALITY_CHALLENGE_SIZE + COMMITMENT_EQUALITY_SECMARGIN +
  60                               std::max(std::max(this->ap->modulus.bitSize(), this->bp->modulus.bitSize()),
  61                                        std::max(this->ap->groupOrder.bitSize(), this->bp->groupOrder.bitSize()));
  62         Bignum maxRange = (Bignum(2).pow(randomSize) - Bignum(1));
  63
  64         r1 = Bignum::randBignum(maxRange);
  65         r2 = Bignum::randBignum(maxRange);
  66         r3 = Bignum::randBignum(maxRange);
  67
  68         // Generate two random, ephemeral commitments "T1, T2"
  69         // of the form:
  70         // T1 = g1^r1 * h1^r2 mod p1
  71         // T2 = g2^r1 * h2^r3 mod p2
  72         //
  73         // Where (g1, h1, p1) are from "aParams" and (g2, h2, p2) are from "bParams".
  74         Bignum T1 = this->ap->g.pow_mod(r1, this->ap->modulus).mul_mod((this->ap->h.pow_mod(r2, this->ap->modulus)), this->ap->modulus);
  75         Bignum T2 = this->bp->g.pow_mod(r1, this->bp->modulus).mul_mod((this->bp->h.pow_mod(r3, this->bp->modulus)), this->bp->modulus);
  76
  77         // Now hash commitment "A" with commitment "B" as well as the
  78         // parameters and the two ephemeral commitments "T1, T2" we just generated
  79         this->challenge = calculateChallenge(a.getCommitmentValue(), b.getCommitmentValue(), T1, T2);
  80
  81         // Let "m" be the contents of the commitments "A, B". We have:
  82         // A =  g1^m  * h1^x  mod p1
  83         // B =  g2^m  * h2^y  mod p2
  84         // T1 = g1^r1 * h1^r2 mod p1
  85         // T2 = g2^r1 * h2^r3 mod p2
  86         //
  87         // Now compute:
  88         //  S1 = r1 + (m * challenge)   -- note, not modular arithmetic
  89         //  S2 = r2 + (x * challenge)   -- note, not modular arithmetic
  90         //  S3 = r3 + (y * challenge)   -- note, not modular arithmetic
  91         this->S1 = r1 + (a.getContents() * this->challenge);
  92         this->S2 = r2 + (a.getRandomness() * this->challenge);
  93         this->S3 = r3 + (b.getRandomness() * this->challenge);
  94
  95         // We're done. The proof is S1, S2, S3 and "challenge", all of which
  96         // are stored in member variables.
  97 }
  98
  99 bool CommitmentProofOfKnowledge::Verify(const Bignum& A, const Bignum& B) const
 100 {
 101         // Compute the maximum range of S1, S2, S3 and verify that the given values are
 102         // in a correct range. This might be an unnecessary check.
 103         uint32_t maxSize = 64 * (COMMITMENT_EQUALITY_CHALLENGE_SIZE + COMMITMENT_EQUALITY_SECMARGIN +
 104                                  std::max(std::max(this->ap->modulus.bitSize(), this->bp->modulus.bitSize()),
 105                                           std::max(this->ap->groupOrder.bitSize(), this->bp->groupOrder.bitSize())));
 106
 107         if ((uint32_t)this->S1.bitSize() > maxSize ||
 108                 (uint32_t)this->S2.bitSize() > maxSize ||
 109                 (uint32_t)this->S3.bitSize() > maxSize ||
 110                 this->S1 < Bignum(0) ||
 111                 this->S2 < Bignum(0) ||
 112                 this->S3 < Bignum(0) ||
 113                 this->challenge < Bignum(0) ||
 114                 this->challenge > (Bignum(2).pow(COMMITMENT_EQUALITY_CHALLENGE_SIZE) - Bignum(1))) {
 115                 // Invalid inputs. Reject.
 116                 return false;
 117         }
 118
 119         // Compute T1 = g1^S1 * h1^S2 * inverse(A^{challenge}) mod p1
 120         Bignum T1 = A.pow_mod(this->challenge, ap->modulus).inverse(ap->modulus).mul_mod(
 121                         (ap->g.pow_mod(S1, ap->modulus).mul_mod(ap->h.pow_mod(S2, ap->modulus), ap->modulus)),
 122                         ap->modulus);
 123
 124         // Compute T2 = g2^S1 * h2^S3 * inverse(B^{challenge}) mod p2
 125         Bignum T2 = B.pow_mod(this->challenge, bp->modulus).inverse(bp->modulus).mul_mod(
 126                         (bp->g.pow_mod(S1, bp->modulus).mul_mod(bp->h.pow_mod(S3, bp->modulus), bp->modulus)),
 127                         bp->modulus);
 128
 129         // Hash T1 and T2 along with all of the public parameters
 130         Bignum computedChallenge = calculateChallenge(A, B, T1, T2);
 131
 132         // Return success if the computed challenge matches the incoming challenge
 133         if(computedChallenge == this->challenge) {
 134                 return true;
 135         }
 136
 137         // Otherwise return failure
 138         return false;
 139 }
 140
 141 const Bignum CommitmentProofOfKnowledge::calculateChallenge(const Bignum& a, const Bignum& b, const Bignum &commitOne, const Bignum &commitTwo) const {
 142         CHashWriter hasher(0,0);
 143
 144         // Hash together the following elements:
 145         // * A string identifying the proof
 146         // * Commitment A
 147         // * Commitment B
 148         // * Ephemeral commitment T1
 149         // * Ephemeral commitment T2
 150         // * A serialized instance of the commitment A parameters
 151         // * A serialized instance of the commitment B parameters
 152
 153         hasher << std::string(ZEROCOIN_COMMITMENT_EQUALITY_PROOF);
 154         hasher << commitOne;
 155         hasher << std::string("||");
 156         hasher << commitTwo;
 157         hasher << std::string("||");
 158         hasher << a;
 159         hasher << std::string("||");
 160         hasher << b;
 161         hasher << std::string("||");
 162         hasher << *(this->ap);
 163         hasher << std::string("||");
 164         hasher << *(this->bp);
 165
 166         // Convert the SHA256 result into a Bignum
 167         // Note that if we ever change the size of the hash function we will have
 168         // to update COMMITMENT_EQUALITY_CHALLENGE_SIZE appropriately!
 169         return Bignum(hasher.GetHash());
 170 }
 171
 172 } /* namespace libzerocoin */