Skip to content

CoinRandomnessSchnorrSignature

Jump to bottom
random-zebra edited this page Jun 29, 2019 · 5 revisions

Abstract

This document describes a new type of PublicCoinSpend, marked with version number 4.

Motivation

The PublicCoinSpend class was introduced (with version 3) subclassing the (version 2) CoinSpend class, after the recent libzerocoin exploits in order to by-pass the broken P1 proof.
This came at the cost of the Zerocoin protocol privacy. As the name suggests, in fact, PublicCoinSpends are not private.

This de-anonymized spend process happens in the following way:

  • each input reveals the mint transaction output (containing the public coin value C) referencing the previous outpoint, just like regular basecoin transactions reference UTXOs in their inputs.
  • the input scriptSig starts with a new opcode OP_ZEROCOINPUBLICSPEND (0xc3) and contains the zerocoin secrets (serial number S and randomness v).
  • the transaction outputs are signed with the coin's private key.
The verifier checks that the minted coin C, referenced by the spend input, is indeed a commitment to the secrets published in the input script (C = Comm(S,v)), that the serial number S was not already spent, and lastly verifies the signature.

This approach presents a serious issue if applied to version 1 zerocoins since they have no keypair associated with them.
Without the signature, in fact, the present scheme is trivially vulnerable to man-in-the-middle attacks.

So a different approach is required for spending version 1 zPIVs.
The solution proposed in this document offers an additional layer of protection to v2 zerocoins too for a little added communication cost (version 4 spend inputs are only 32 bytes bigger than those of version 3).

Overview

A naive solution to the problem would be to leverage the libzerocoin SerialNumberSignatureOfKnowledge and publish it along with the commitment to the coin, y, and the commitment randomness, R.
The verifier should check that y = Comm(C, R) and then use y to verify the signature of knowledge.

On one hand this would be highly expensive in terms of performance (making spends production and verification slower by orders of magnitude) and communication costs (adding about 20kB of overhead to each spend). On the other, it would also be redundant, as revealing the public coin value defeats the purpose of having a Zero-Knowledge signature of knowledge and a commitment to the coin.

An alternative solution is offered by the protocol described here, which allows the spender to prove knowledge of the secret randomness v without publishing it, thus fixing the malleability issue affecting the previous version.

The basic idea is to create a Schnorr signature over the hash of the transaction outputs using the coin randomness as private key.

Rationale

The following observations make the adoption of the Schnorr signature algorithm a convincing solution.

  • The coinCommitmentgroup is a Schnorr group having modulus p of 1024 bits (thus in which the discrete logarithm problem can be safely assumed to be hard) and order q of 256 bits (making dSHA256 a convenient choice for hash function).
  • The coin randomness is a random element in the allowed group Zq (thus can be used as private signing key, sk, in the Schnorr algorithm).
  • The verifier can compute the public verification key pk (= h^v mod p) from the data already at his disposal (public Zerocoin parameters, public coin value, coin serial number) thus no further overhead is needed on the script beside the signature (which is already very short: only twice the size of the coin randomness).

Signature Algorithm

The following pseudocode shows the signature and verification algorithms (as usual ║ denotes concatenation of binary strings):

Signature 

 inputs:    <- (p, q, h) -- Zerocoin params: modulus, order and generator of coinCommitmentGroup
            <- M -- message to sign: ptxHash
            <- v -- coin randomness
 --------------------------------------------
 1- set k <-- random secret element in Zq
 2- r = h^k mod p
 3- alpha = Hash(zcparams ║ r ║ M) mod q
 4- beta = (k - v * alpha) mod q
 --------------------------------------------
 outputs:   -> (alpha, beta) -- signature components

Verification 

 inputs:    <- (p, q, g, h)  -- Zerocoin params: modulus, order and generators of coinCommitmentGroup
            <- (alpha, beta) -- signature components
            <- M -- message to sign: ptxHash
            <- C -- public coin value
            <- S -- coin serial number
 --------------------------------------------
 1- pk = C * g^{-S} mod p
 2- rv = (pk^alpha) * (h^beta) mod p
 3- result = {alpha == Hash(zcparams ║ rv ║ M) mod q}
 --------------------------------------------
 output:    -> result -- verification outcome: true, false

.

Specification

The following table shows the structure of the PublicCoinSpend v4 input script:

Field Type Size (bytes) Notes
OP_ZEROCOINPUBLICSPEND uint8_t 1 value = 195 (c3)
CoinSpend Version uint8_t 1 value = 4 after enforcement
Coin SerialNumber CBigNum 32  
Schnorr Signature CoinRandomnessSchnorrSignature 64  
Coin PublicKey CPubKey 32 only for v2+ zerocoins
vchSig vector<unsigned char> 73 only for v2+ zerocoins

Reference Implementation

https://github.com/random-zebra/PIVX/tree/2019_randomness-schnorr

Want to contribute to this Wiki?

Fork it and send a pull request.

Clone this wiki locally