One-Time, Zero-Sum Ring Signature
Conner Fromknecht
November 12, 2015

1Introduction

Is Bitcoin a currency? The jurisdictions of institutions all over the world haveculminated in everything but a unanimous decision. In practice, Bitcoin offers
the majority of features present in typical fiat currencies such as payments ofarbitrary amount and exchanges for another currency. However, Bitcoin fails tomeet one of the key properties of a true currency—fungibility.
Not all Bitcoins are created equal. Since the transaction history is public,
so too are the balances and payments made by its participants. After any
transaction is completed, the receiver is able to view the complete history of thecoin. If the coin’s history includes transactions that are known to be a part ofa scandal, the receiver can choose to reject the payment. This inherently makessome Bitcoin less valuable than others, since accepting tainted coins assumes therisk that the next receiver may not accept them. By definition, this inequality
between coins prevents Bitcoin from being fungible.
The goal of this work is to design a more fungible cryptocurrency. In orderto do so, we tackle two distinct problems that allow a third party to discriminate
against the coins used in a standard Bitcoin transaction. The first is linkability,
which allows an individual to trace the history of a transaction and determine
the accounts that have held the coin before. This work builds upon much of
CryptoNote’s [4] anonymous transaction scheme to ensure the destination is
obfuscated, preventing third parties from explicitly backwards constructing apath to the sender.
However, this alone is not enough. The transaction amounts are still visible,
which allows any two transactions of equal amounts to be possibly linked, andthus jeopardizing unlinkability. Therefore, our solution must also hide transaction amounts. This work begins with a similar approach to the one outlined by
Gregory Maxwell’s Confidential Transaction scheme [2]. This allows the sender
to prove that the value is within a certain range, say [0, 2l ). In order to publicly verify this, the signer must coordinate the blinding factors and amountsof different inputs such that they result in a zero sum. However, when using
CryptoNote’s ring signatures, the signer has no control over the blinding factorsof other inputs. Thus, we propose a new ring signature construction, called aOne-Time, Zero-Sum Ring Signature (OZRS) that proves the output amount is1

2

CONSTRUCTION

2equal to exactly one of the committed input values. It also proves that a commitment receives a new blinding factor after each transaction and allows only
the recipient to learn the amount enclosed. Furthermore, the size of an OZRS
is the same as the One-Time Ring Signatures used in the standard CryptoNoteprotocol.
By combining the unlinkability and confidentiality properties of this work,
the receiver of a transaction is able to verify its amount but also learns nothing
about the coin’s history. Since this is true for any future recipient, the receiver
can accept the payment as is without concern that it may be rejected by anotherparty.

2Construction

Building on CryptoNote’s architecture, this work requires relatively simple changes
to the high level protocol. The modifications include adding a single field to atransaction output and replacing the One-Time Ring Signature with an OZRS.
Furthermore, every transaction amount is committed using a Pedersen Commitment and accompanied by a range proof using the Borromean scheme describedin [3]. For simplicity, we assume that the range proof is done in binary, but theresults can be extended to any publicly known encoding.

2.1

Transactions

Here we describe how to construct a single output transaction, where someuser is trying to send the value v 0 to the standard address (A = aG, B = bG).
These steps operate in addition to the unmodified CryptoNote protocol, unlessotherwise specified here.
When building a single output transaction, the signer also chooses a random
number q ∈ ZN and adds the blind seed Q = qG to the transaction output.
The signer then computes y 0 = HS (qB) which is called the output blinding
factor, where B is taken to be the receiver’s public key. Using y 0 , the output
commitment C 0 = y 0 G + v 0 H is constructed by first deterministically generating
blinding factors γ (i) to commit each of the l bits βi in v 0 . These blinding factors
are computed byγ (1) = HS (y 0 )(Piy 0 − j=1 γ (j)(i+1)γ=HS (γ (i) ):i=l−1: otherwise.

PlThe signer then outputs the final C 0 = i=1 ci , where ci = γ (i) G + βi H and βi
is either 2i or 0 depending on the ith bit of v 0 . Each ci and γ (i) is further used
to construct the range proof of C 0 using the techniques in [3].
A receiver uses the blind seed to compute y 0 = HS (bQ) where b is taken to
be the receiver’s super secret private key. A receiver with knowledge of y 0 is alsoable to recover each of the γ (i) blinding factors. Then, he can recover the bits

2CONSTRUCTION

3of v 0 by checking ci − γ (i) G = 0 or di − γ (i) G = 0, where the challenge publickey di = ci − 2i H. If the first is true, then βi = 0; if the second check passes
then βi = 2i . Note that the signer of a transaction could pick Q0 6= qG, which
results in different γ (i) with high probability. The receiver can easily detect thisevent if both ci and di failed the above test. In this case, the receiver shouldnot accept the transaction as payment, since he will be unable to spend it.
2.1.1

Multiple Outputs

Supporting transactions with m outputs only requires a small modification tothe single output case. We compute one Ci0 = yi0 G + vi0 H for each output
amountas described above,
Pmproviding a range proof for each. We then computePm
C 0 = i=1 Ci0 and y 0 = i=1 yi0 . Note that each output now has its own blind
seed, so they can each be recovered independently. Lastly, instead of creating
a single transaction public key R = rG, we create one for each output. This
allows the outputs of a transaction to be spent independently of each other,much like how they are in Bitcoin.
2.1.2

Transaction StructureThis section describes the format of a transaction incorporating the abovechanges. The construction of the OZRS is described in the subsequent section.
INPUT
Key Image:I = x∗ HP (x∗ )Input Transaction Hashes:{HS (Ti )}nOUTPUT
Transaction Public Keys:{Ri = ri G}m

Destination Keys:{Pi = HS (ri Ai )G + Bi }m

Blind Seeds:{Qi = qi G}m

Commitments:{Ci0 = yi0 G + vi0 H}m

Range Proofs:{πl (Ci0 )}m

SIGNATURE
OZRS:

2.2

Π = (e, r1 , . . . , rn , s1 , . . . , sn )One-Time, Zero-Sum Ring Signature

For any transaction with n inputs and m outputs, let X = {Xi = xi G}i∈[1,n]be the set of input destination keys and ∗ ∈ [1, n] to be the index of signer’s
public key X∗ . Furthermore, let C = {Ci = yi G + vi H}i∈[1,n] be the set input
commitments, where each Ci commits each Xi to the value vi . We call each yi
an input blinding factor. After constructing a transaction, the signer also holds

2CONSTRUCTION

4

the new output blinding factor y 0 and total output value v 0 in000

C =y G+v H =mX

Ci0 =

i=1

m
X

yi0 G + vi0 H,

i=1

where each Ci0 represents an individual output commitment. Here we present aring signature formulation constructed as an AOS ring signature [1] that uses athree-way chameleon hash to prove the following properties:
1. The signer knows at least one secret key xi for a public key Xi
2. The signer knows the secret key x∗ corresponding to the preimage I =x∗ HP (X∗ ) of X∗ .
3. The sum of the output commitments C 0 holds a value equal to the sender’s
input C∗ .
More formally, the ring signature is a Non-Interactive, Zero-Knowledge Proofof Knowledge on a message M such that all values other than {xi }, {yi }, {vi },y 0 , v 0 , {yi0 }, {vi0 } and are known to the prover, defined
NiZKPoK[M ]({xi }, {yi }, {vi }, y 0 , v 0 , {yi0 }, {vi0 }) : {∃i : C 0 − Ci = (y 0 − yi )G∧ Xi = xi G
∧ I = xi HP (Xi )}.
The One-Time, Zero-Sum Ring Signature scheme consists of the four operations (Gen, Sign, Verify, Link).
• Gen(N, G) → (a, A)
Choose a ← ZN at random.
Compute A = aG and output (a, A).

• Sign(M, C, C 0 , y 0 , y∗ , x∗ , X) → ΠCompute the signing key’s preimage and commitment differences
I = x∗ HP (X∗ )0(1)0Di = C − Ci = (y − yi )G.

(2)

2
Next, we build the non-interactive challenge e. Choose k1 , k2 ← ZN
atrandom. Starting at index ∗, compute(1)e∗ = HS (M || k1 G || k2 G || k2 HP (X∗ ))REFERENCES

5(·)

Continue computing successive ei , wrapping around after i = n, until(2)e∗−1 using the following steps
2
ri , si ← ZN

(3)

(2)
(1)
ei = HS (ei )
(1)
(1)
(2)
(2)
ei+1 = HS (M || ri G − ei Di || si G − ei Xi || si HP (Xi ) − ei I)

(4)
(5)

(1)

Lastly, we set r∗−1 , s∗−1 so that the hash hits e∗ by(1)r∗−1 = k1 + e∗−1 (y 0 − y∗ )(2)s∗−1 = k2 + e∗−1 x∗(1)Assign e = e1

and output the final proof Π = (e, r1 , . . . , rn , s1 , . . . , sn ).

• Verify(Π, M, C, C 0 , X, I) → {0, 1}
First compute each commit difference Di using equation (2). Starting(1)(·)
with e = e1 , compute the forward ei for i ∈ [1, n] using relations (4)and (5). The verifier then checks that(2)(2)
e = HS (M || rn G − e(1)n Dn || sn G − en Xn || sn HP (Xn ) − en I)

and Link(I) fails. If both of these are met, return 1. Otherwise, return 0.

• Link(I) → {0, 1}
Let I be the set of all spent preimages. Return 1 if I ∈ I, otherwise return0.

References[1] M. Abe, M. Ohkubo, and K. Suzuki. 1-out-of-n signatures from a variety ofkeys. In Advances in Cryptology - ASIACRYPT, 2002.
[2] G. Maxwell. Confidential transactions. https://people.xiph.org/~greg/
confidential_values.txt, 2015.
[3] G. Maxwell and A. Poelstra. Borromean ring signatures. http://diyhpl.
us/~bryan/papers2/bitcoin/Borromean%20ring%20signatures.pdf,
2015.
[4] N. van Saberhagen. Cryptonote. https://cryptonote.org/whitepaper.
pdf, 2013.