Skip to content

CoinRandomnessSchnorrSignature

Jump to bottom
random.zebra edited this page Jun 30, 2019 · 5 revisions

Abstract

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

Background

The PublicCoinSpend class was introduced (with version 3) subclassing the (version 2) CoinSpend class, after the recent libzerocoin exploits in order to bypass 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.

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

Field Type Max Size (bytes) Notes
OP_ZEROCOINPUBLICSPEND uint8_t 1 value = 195 (c3)
CoinSpend Version uint8_t 1 value = 3
Coin SerialNumber CBigNum 32  
Coin Randomness CBigNum 32  
Coin PublicKey CPubKey 32  
vchSig vector<unsigned char> 73  

Motivation

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 in fact about the same size of 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 &boxV; 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- pk = h^v mod p
 2- set k <-- random secret element in Zq
 3- r = h^k mod p
 4- alpha = Hash(zcparams ║ pk ║ r ║ M) mod q
 5- 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 ║ pk ║ rv ║ M) mod q}
 --------------------------------------------
 output:    -> result -- verification outcome: true, false

.

Additional Changes

Another proposed change in this version is to remove the coin serial number for v2 coins from the serialization.
For version 2 zerocoins, in fact, the serial number is deterministically computable from the coin public key and, being the public key already part of the serialized object, there is no need to add further overhead (just one byte for the coin version).
Also, in this way, the verifier doesn't need to check that the coin serial number and the hashed public key match since the former is derived from the latter in the constructor.

Therefore, saving 32 bytes of the coin randomness and 32 bytes of the coin serial number, allows us to add the 64 bytes of the Schnorr signature for v2 coins too while keeping the same size as previous version.

Each v4 spend input (including the script and the 40 bytes required for prevout and sequence) has a size of about ~220 bytes for v2 coins and ~147 for v1 coins, once serialized.

Specification

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

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

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