range_proof.go

// Package proof range proof via sum of three squares (3SPR)
// Paper: Removing the Strong RSA Assumption from Arguments over the Integers
// Link: https://eprint.iacr.org/2016/128
package proof

import (
	"bytes"
	"crypto"
	"crypto/sha256"
	"math/big"
)

const (
	rpChallengeStatement = "c = (g^x)(h^r), x is non-negative"
	sha256Len            = 32
	rpCommitLen          = sha256Len * 5
)

var rpB = big.NewInt(4096) // bound B

// RangeProof is the proof for range proof
type RangeProof struct {
	// c = (g^x)(h^r)
	c *big.Int
	// commitment of x,
	// containing c1, c2, c3, ci = (g^xi)(h^ri),
	// which x = x1^2 + x2^2 + x3^2
	commit3 Int3
	// the commitment delta
	commitment rpCommitment
	// the response to the challenge
	response *rpResponse
}

// NewRangeProof generates a new proof for range proof
func NewRangeProof(c *big.Int, commit3 Int3, commitment rpCommitment, response *rpResponse) *RangeProof {
	return &RangeProof{
		c:          c,
		commit3:    commit3,
		commitment: commitment,
		response:   response,
	}
}

// rpCommitment is the range proof commitment generated by the prover
type rpCommitment [rpCommitLen]byte

// rpChallenge is the challenge for range proof
type rpChallenge struct {
	statement string   // the statement for the challenge
	g, h, n   *big.Int // public parameters: G, H, N
	a, b      *big.Int // the range [a, b]
	c3        Int3     // commitment of x containing c1, c2, c3
}

// newRPChallenge generates a new challenge for range proof
func newRPChallenge(pp *PublicParameters, a, b *big.Int, c3 Int3) *rpChallenge {
	return &rpChallenge{
		statement: rpChallengeStatement,
		g:         pp.G,
		h:         pp.H,
		n:         pp.N,
		a:         a,
		b:         b,
		c3:        c3,
	}
}

// Serialize generates the serialized data for range proof challenge in byte format
func (r *rpChallenge) serialize() []byte {
	var buf bytes.Buffer
	buf.WriteString(r.statement)
	buf.WriteString(r.g.String())
	buf.WriteString(r.h.String())
	buf.WriteString(r.n.String())
	buf.WriteString(r.a.String())
	buf.WriteString(r.b.String())
	for _, c := range r.c3 {
		buf.WriteString(c.String())
	}
	return buf.Bytes()
}

// sha256 generates the SHA256 hash of the range proof challenge
func (r *rpChallenge) sha256() []byte {
	hashF := crypto.SHA256.New()
	_, err := hashF.Write(r.serialize())
	if err != nil {
		panic(err)
	}
	hashResult := hashF.Sum(nil)
	return hashResult
}

// bigInt serializes the range proof challenge to bytes, generates the SHA256 hash of the byte data,
// and convert the hash to big integer
func (r *rpChallenge) bigInt() *big.Int {
	hashVal := r.sha256()
	return new(big.Int).SetBytes(hashVal)
}

// rpResponse is the response sent by the prover after receiving verifier's challenge
type rpResponse struct {
	Z4  Int4
	T4  Int4
	TAU *big.Int
}

// newRPCommitment generates a new commitment for range proof
func newRPCommitment(d4 Int4, d *big.Int) rpCommitment {
	var dByteList [int4Len][]byte
	for i := 0; i < int4Len; i++ {
		dByteList[i] = d4[i].Bytes()
	}
	dBytes := d.Bytes()
	hashF := crypto.SHA256.New()
	var sha256List [int4Len][]byte
	for i, dByte := range dByteList {
		_, err := hashF.Write(dByte)
		if err != nil {
			panic(err)
		}
		sha256List[i] = hashF.Sum(nil)
		hashF.Reset()
	}
	var commitment rpCommitment
	for idx, s := range sha256List {
		copy(commitment[idx*sha256Len:(idx+1)*sha256Len], s)
	}
	_, err := hashF.Write(dBytes)
	if err != nil {
		panic(err)
	}
	copy(commitment[rpCommitLen-sha256Len:], hashF.Sum(nil))
	return commitment
}

// RPProver refers to the Prover in zero-knowledge integer range proof
type RPProver struct {
	pp     *PublicParameters // public parameters
	r      *big.Int          // r
	sp     *big.Int          // security parameter, kappa
	c      *big.Int          // c = (g^x)(h^r)
	a, b   *big.Int          // a, b, range [a, b]
	ca     *big.Int          // ca = (c * g^(-a))^4 mod n
	sigma  *big.Int          // random selected parameter sigma in [0, 2^(B + 2kappa)*n]
	x4     Int4              // x0 = (b-x), and three square sum of 4(b-x)(x-a) + 1 = x1^2 + x2^2 + x3^2
	c3     Int3              // commitment of three square sum of x: c1, c2, c3, ci = (g^xi)(h^ri)
	randM4 Int4              // random coins: m0, m1, m2, m3, mi is in [0, 2^(B + 2kappa)]
	r4     Int4              // r0 = -r, and random coins: r1, r2, r3, ri is in [0, n]
	randS4 Int4              // random coins: s0, s1, s2, s3, si is in [0, 2^(2kappa)*n]
}

// NewRPProver generates a new range proof prover
func NewRPProver(pp *PublicParameters, r, a, b *big.Int) *RPProver {
	prover := &RPProver{
		pp: pp,
		r:  r,
		a:  a,
		b:  b,
		sp: big.NewInt(securityParam),
	}
	return prover
}

// Prove generates the proof for range proof
func (r *RPProver) Prove(x *big.Int) (*RangeProof, error) {
	r.c = calC(r.pp, r.r, x)
	r.ca = calCa(r.pp, r.a, r.c)
	r.x4[0] = new(big.Int).Sub(r.b, x)
	r.r4[0] = r.r
	cx, err := r.commitForX(x)
	if err != nil {
		return nil, err
	}
	commitment, err := r.commit()
	if err != nil {
		return nil, err
	}
	response, err := r.response()
	if err != nil {
		return nil, err
	}
	return NewRangeProof(r.c, cx, commitment, response), nil
}

// calculate parameter c, c = (g^x)(h^r) mod n
func calC(pp *PublicParameters, r, x *big.Int) (c *big.Int) {
	c = new(big.Int).Exp(pp.G, x, pp.N)
	opt := iPool.Get().(*big.Int)
	defer iPool.Put(opt)
	c.Mul(c, opt.Exp(pp.H, r, pp.N))
	c.Mod(c, pp.N)
	return
}

// calculate parameter Ca, Ca = (c * g^(-a))^4 mod n
func calCa(pp *PublicParameters, a, c *big.Int) (ca *big.Int) {
	negA := new(big.Int).Neg(a)
	defer iPool.Put(negA)
	opt := new(big.Int).Exp(pp.G, negA, pp.N)
	defer iPool.Put(opt)
	ca = new(big.Int).Set(c)
	ca.Mul(ca, opt)
	ca.Exp(ca, big4, pp.N)
	return
}

// commitForX generates the commitment for x
func (r *RPProver) commitForX(x *big.Int) (Int3, error) {
	// calculate three squares that 4(b-x)(x-a) + 1 = x1^2 + x2^2 + x3^2
	target := iPool.Get().(*big.Int).Sub(r.b, x)
	defer iPool.Put(target)
	opt := iPool.Get().(*big.Int).Sub(x, r.a)
	defer iPool.Put(opt)
	r.x4[0].Sub(r.b, x)
	target.Mul(target, opt)
	target.Lsh(target, 2)
	target.Add(target, big1)
	ts, err := ThreeSquares(target)
	if err != nil {
		return Int3{}, err
	}
	for i := 0; i < int3Len; i++ {
		r.x4[i+1] = ts[i]
	}
	// TODO: different from paper, to be clarified
	r.r4[0] = new(big.Int).Neg(r.r)
	// calculate commitment for x
	var rc Int3
	if rc, err = newThreeRandCoins(r.pp.N); err != nil {
		return Int3{}, err
	}
	for i := 0; i < int3Len; i++ {
		r.r4[i+1] = rc[i]
	}
	c3 := newRPCommitFromFS(r.pp, rc, ts)
	r.c3 = c3
	return c3, nil
}

// newRPCommitFromFS generates a range proof commitment for a given integer
func newRPCommitFromFS(pp *PublicParameters, coins Int3, ts Int3) (cList Int3) {
	opt := iPool.Get().(*big.Int)
	defer iPool.Put(opt)
	for i := 0; i < int3Len; i++ {
		cList[i] = new(big.Int).Exp(pp.G, ts[i], pp.N)
		cList[i].Mul(cList[i], opt.Exp(pp.H, coins[i], pp.N))
		cList[i].Mod(cList[i], pp.N)
	}
	return
}

// commit composes the commitment for range proof
func (r *RPProver) commit() (rpCommitment, error) {
	// pick m0, m1, m2, m3, mi is in [0, 2^(B + 2kappa)]
	powMLmt := iPool.Get().(*big.Int).Set(r.sp)
	defer iPool.Put(powMLmt)
	powMLmt.Lsh(powMLmt, 1)
	powMLmt.Add(powMLmt, rpB)
	mLmt := iPool.Get().(*big.Int).Exp(big2, powMLmt, nil)
	defer iPool.Put(mLmt)
	m4, err := newFourRandCoins(mLmt)
	if err != nil {
		return rpCommitment{}, err
	}
	r.randM4 = m4
	// pick s0, s1, s2, s3, si is in [0, 2^(2kappa)*n]
	sLmt := iPool.Get().(*big.Int).Exp(big4, r.sp, nil)
	defer iPool.Put(sLmt)
	sLmt.Mul(sLmt, r.pp.N)
	var s4 Int4
	if s4, err = newFourRandCoins(sLmt); err != nil {
		return rpCommitment{}, err
	}
	r.randS4 = s4
	// pick sigma in [0, 2^(B + 2kappa)*n]
	sLmt.Lsh(sLmt, uint(rpB.Int64()))
	var sigma *big.Int
	if sigma, err = freshRandCoin(sLmt); err != nil {
		return rpCommitment{}, err
	}
	r.sigma = sigma
	// calculate commitment
	d4 := r.firstPartH(m4, s4)
	d := r.secondPartH(m4)
	c := newRPCommitment(d4, d)
	return c, nil
}

// firstPartH calculates h0, h1, h2, h3, hi = (g^mi)(h^si) mod n
func (r *RPProver) firstPartH(m, s Int4) Int4 {
	var h4 Int4
	opt := iPool.Get().(*big.Int)
	defer iPool.Put(opt)
	for i := 0; i < int4Len; i++ {
		h := new(big.Int).Exp(r.pp.G, m[i], r.pp.N)
		h.Mul(h, opt.Exp(r.pp.H, s[i], r.pp.N))
		h4[i] = h.Mod(h, r.pp.N)
	}
	return h4
}

// secondPartH calculates h = (h^(sigma))*(c^(m0)_a)*(product of (ci^(-mi))) mod n
func (r *RPProver) secondPartH(m Int4) *big.Int {
	// prefix = h^sigma * c_a^m_0
	result := iPool.Get().(*big.Int).Exp(r.pp.H, r.sigma, r.pp.N)
	defer iPool.Put(result)
	opt := iPool.Get().(*big.Int)
	defer iPool.Put(opt)
	opt.Exp(r.ca, r.randM4[0], r.pp.N)
	result.Mul(result, opt)
	result.Mod(result, r.pp.N)
	// ci^(-mi)
	negM := iPool.Get().(*big.Int)
	defer iPool.Put(negM)
	// product of ci^(-mi) mod n, for i = 1, 2, 3
	for i := 0; i < int3Len; i++ {
		result.Mul(
			result,
			opt.Exp(r.c3[i], negM.Neg(m[i+1]), r.pp.N),
		)
		result.Mod(result, r.pp.N)
	}
	// product of ci^(-mi)
	return result
}

// calChallengeBigInt calculates the challenge for range proof in big integer format
func (r *RPProver) calChallengeBigInt() *big.Int {
	challenge := newRPChallenge(r.pp, r.a, r.b, r.c3)
	return challenge.bigInt()
}

// response generates the response for verifier's challenge
func (r *RPProver) response() (*rpResponse, error) {
	e := r.calChallengeBigInt()
	// zi = e * xi + mi, for i = 0, 1, 2, 3
	var z4 Int4
	for i := 0; i < int4Len; i++ {
		z4[i] = new(big.Int).Mul(e, r.x4[i])
		z4[i].Add(z4[i], r.randM4[i])
	}
	// ti = e * ri + si, for i = 0, 1, 2, 3
	var t4 Int4
	for i := 0; i < int4Len; i++ {
		t4[i] = new(big.Int).Mul(e, r.r4[i])
		t4[i].Add(t4[i], r.randS4[i])
	}

	// tau = sigma + e * (4 * x0 * r0 - product of xi * ri, for i = 1, 2, 3)
	sumXR := iPool.Get().(*big.Int)
	defer iPool.Put(sumXR)
	sumXR.SetInt64(0)
	opt := iPool.Get().(*big.Int)
	defer iPool.Put(opt)
	for i := 1; i < int4Len; i++ {
		sumXR.Add(sumXR, opt.Mul(r.x4[i], r.r4[i]))
	}
	tau := new(big.Int).Mul(r.x4[0], r.r4[0])
	// TODO: different from paper, to be clarified
	tau.Lsh(tau, 2)
	tau.Add(tau, sumXR)
	tau.Mul(tau, e)
	tau.Add(tau, r.sigma)
	response := &rpResponse{
		Z4:  z4,
		T4:  t4,
		TAU: tau,
	}
	return response, nil
}

// RPVerifier refers to the Verifier in zero-knowledge integer range proof
type RPVerifier struct {
	pp         *PublicParameters // public parameters
	sp         *big.Int          // security parameters
	a, b       *big.Int          // the range [a, b]
	commitment rpCommitment      // commitment, delta = H(d1, d2, d3, d4, d)
	c4         Int4              // c0 = c^(-1)*g^b mod n, c1, c2, c3 are the commitments of x
	ca         *big.Int          // ca = (c*g(-a))^4 mod n
}

// NewRPVerifier generates a new range proof verifier
func NewRPVerifier(pp *PublicParameters, a, b *big.Int) *RPVerifier {
	verifier := &RPVerifier{
		pp: pp,
		sp: big.NewInt(securityParam),
		a:  a,
		b:  b,
	}
	return verifier
}

// Verify verifies the range proof
func (r *RPVerifier) Verify(proof *RangeProof) bool {
	r.c4[0] = new(big.Int).ModInverse(proof.c, r.pp.N)
	opt := iPool.Get().(*big.Int)
	defer iPool.Put(opt)
	r.c4[0].Mul(r.c4[0], opt.Exp(r.pp.G, r.b, r.pp.N))
	r.c4[0].Mod(r.c4[0], r.pp.N)
	for i := 1; i < int4Len; i++ {
		r.c4[i] = proof.commit3[i-1]
	}
	opt.Neg(r.a)
	opt.Exp(r.pp.G, opt, r.pp.N)
	r.ca = new(big.Int).Mul(proof.c, opt)
	r.ca.Mod(r.ca, r.pp.N)
	r.ca.Exp(r.ca, big4, r.pp.N)
	r.commitment = proof.commitment
	return r.VerifyResponse(proof.response)
}

// challenge generates a challenge for prover's commitment
func (r *RPVerifier) challenge() *big.Int {
	var c3 Int3
	for i := 0; i < int3Len; i++ {
		c3[i] = r.c4[i+1]
	}
	challenge := newRPChallenge(r.pp, r.a, r.b, c3)
	return challenge.bigInt()
}

// VerifyResponse verifies the response, if accepts, return true; otherwise, return false
func (r *RPVerifier) VerifyResponse(response *rpResponse) bool {
	c := r.challenge()
	// the first 4 parameters: (g^zi)(h^ti)(ci^(-e)) mod n
	var firstFourParams Int4
	negC := iPool.Get().(*big.Int).Neg(c)
	defer iPool.Put(negC)
	opt := iPool.Get().(*big.Int)
	defer iPool.Put(opt)
	for i := 0; i < int4Len; i++ {
		firstFourParams[i] = new(big.Int).Exp(r.pp.G, response.Z4[i], r.pp.N)
		firstFourParams[i].Mul(
			firstFourParams[i],
			opt.Exp(r.pp.H, response.T4[i], r.pp.N),
		)
		firstFourParams[i].Mul(
			firstFourParams[i],
			opt.Exp(r.c4[i], negC, r.pp.N),
		)
		firstFourParams[i].Mod(firstFourParams[i], r.pp.N)
	}

	// prefix = h^tau * g^e * c_a^z_0 mod n
	lastH := new(big.Int).Exp(r.pp.H, response.TAU, r.pp.N)
	defer iPool.Put(lastH)
	lastH.Mul(lastH, opt.Exp(r.pp.G, c, r.pp.N))
	lastH.Mod(lastH, r.pp.N)
	lastH.Mul(lastH, opt.Exp(r.ca, response.Z4[0], r.pp.N))
	lastH.Mod(lastH, r.pp.N)
	//product of (ci^zi)(h^t)(c^(-e)) mod n
	for i := 1; i < int4Len; i++ {
		opt.Neg(response.Z4[i])
		lastH.Mul(
			lastH,
			opt.Exp(r.c4[i], opt, r.pp.N),
		)
		lastH.Mod(lastH, r.pp.N)
	}

	hashF := sha256.New()
	var sha256List [int4Len][]byte
	for i := 0; i < int4Len; i++ {
		_, err := hashF.Write(firstFourParams[i].Bytes())
		if err != nil {
			panic(err)
		}
		sha256List[i] = hashF.Sum(nil)
		hashF.Reset()
	}
	_, err := hashF.Write(lastH.Bytes())
	if err != nil {
		panic(err)
	}
	h := hashF.Sum(nil)
	var commitment rpCommitment
	for i := 0; i < int4Len; i++ {
		copy(commitment[i*sha256Len:(i+1)*sha256Len], sha256List[i])
	}
	copy(commitment[rpCommitLen-sha256Len:], h)
	return commitment == r.commitment
}