The Mathematics of Digital Cash

Joey Yandle

2018-12-23

While traditional cryptocurrencies were groundbreaking in many ways, they lacked the privacy protections

that cash inherently provides. This document will explore the math which can provide some of those protections.

The goal is to build a cryptocurrency which deserves the name Digital Cash.

There are many papers which outline, deﬁne, use, mutate, expand on, or cite the following techniques. But

these papers invariably use diﬀerent terminology, swapping variable names and using various subsets as needed.

In this document, I will endeavor to be both thorough and strongly consistent, which should not only make the

math easier to understand, but also expose the deep connections and demonstrate how each piece builds on the

previous.

1 Notation

We deﬁne a hash function H

as a function that maps an unbounded list of arbitrarily-sized binary inputs to

an output set O of n bits:

= { i

, i

, ... | b ∈ {0, 1}, k ∈ N, i ∈ b

...b

} 7→ { b

...b

| b ∈ {0, 1} }

If we do not deﬁne n, then we assume it is implementation dependent, but that the output set is still bounded

at some n bits:

= { i

, i

, ... | b ∈ {0, 1}, k ∈ N, i ∈ b

...b

} 7→ { b

...b

| b ∈ {0, 1} }

2 Schnorr Proofs and the Fiat Shamir Transform

Schnorr proofs [1] allow the owner of a private key to demonstrate that ownership to someone who knows

the corresponding public key. It is an interactive 3-move protocol, i.e. a Sigma protocol. But like all Sigma

protocols, it can be made non-interactive using the Fiat-Shamir transform [2]. This allows the protocol to

function as a signature.

Let g be a generator in a ﬁnite group G of prime order p ∈ P, with private key x ∈ Z

, and public key

y = g

. The prover chooses a random v ∈ Z

, then sets t = g

In the interactive version of the protocol, the prover sends t to the veriﬁer, who responds with the challenge

c. This way the prover cannot choose t after seeing c, which would allow the prover to cheat. To make this

non-interactive, Fiat and Shamir proposed to choose c based on a hash including t, which prevents the prover

from cheating, since c depends on t:

c = H(g, y, t) (1)

The prover then deﬁnes r as below, and calculates it from (v, c, x):

r = v − cx (2)

This is equivalent algebraically to

v = r + cx

We can use this derived expression for v to expand t:

t = g

= g

r+cx

= g

)

= g

(3)

So if t = g

, then the prover must have known x. Otherwise the prover would not have been able to

construct a proper r, allowing the equation to balance. The set (r, c, t) thus forms the proof of ownership of y.

3 Ring signatures

A Schnorr proof allows us to sign a public key, proving we know the corresponding private key. But the signature

is tied to a single key, which is bad for privacy. It would be better to construct a one out of many signature, to

prove that we knew the private key for one out of N public keys. Such a signature is called a ring signature [3].

Start with public key y for which the prover knows the private key x, and as before, choose a random v ∈ Z

. To mix in an additional key y

whose private key x

is unknown, select a random r

and c

. The prover sets

c as follows, using the values known to calculate it:

c = H(g

, g

) − c

(4)

This is equivalent algebraically to:

c + c

= H(g

, g

)

Now that the prover has c, r is as before:

r = v − cx (5)

The prover then sends (y, r, c, y

, r

, c

) to the veriﬁer, who then calculates the hash

H(g

, g

)

Since g

= g

, the two hashes are identical. Thus

c + c

= H(g

, g

) (6)

So if

c is equal to the hash, then the prover must have known x for some y. And since the prover can put

the real (y, r, c) in either position, there is no way for the veriﬁer to know which key was actually signed.

We can do the same for any number of additional public keys y

: choose a random (r

, c

) which is added

to the hash in the form of g

then subtracting the new c

from the hash to form the real c. Then

c will

be equal to the hash for both prover and veriﬁer.

3.1 Linkable Ring Signatures

Now that we can use ring signatures to hide which public key is being signed, we have a new problem: assuming

each public key corresponds to a spendable output, how do we know which output was actually spent? We need

a way to track this to prevent double spends, but in such a way that we preserve the privacy which the ring

signature grants.

First we construct a key image [3], which is a commitment to the public key used but cannot be used to ﬁnd

the public or private keys, and is unique:

I = H(y)

(7)

We then add a term to the hash for each y that uses the key image. For the real y, we know that

H(y)

= H(y)

H(y)

= H(y)

(H(y)

)

= H(y)

(8)

Putting the real y ﬁrst, the prover hash becomes:

H(g

, H(y)

, g

, H(y

)

) (9)

We deﬁne c as before, then solve for the hash:

c = H(g

, H(y)

, g

, H(y

)

) − c

(10)

+ c = H(g

, H(y)

, g

, H(y

)

So as before,

c is equal to the hash. The prover now sends (I, y, r, c, y

, r

, c

) to the veriﬁer, who can

check that their hash is still equal to

c + c

= H(g

, H(y)

, g

, H(y)

) (11)

Since the key image I is now tied to the signature, any attempt to sign two diﬀerent ring signatures with

the same y will result in the same I, so preventing double spends is easy. You just keep track of which key

images have previously been used, and reject any new signatures with a previously used I.

3.2 Linkable Spontaneous Anonymous Group Signatures

Linkable ring signatures do a good job of proving ownership while obscuring origins, but they get large as the

number of mixins rises. LSAG signatures address this by constructing the c terms via an iterative process, so

it is only necessary to send one of them. For a large ring, this results in nearly 33% space savings.

Consider a set of public keys y

, i ∈ {0, , n−1} with a secret index j which denotes the public key to which we

know the corresponding private key x. As before, choose random v, and r

∀i 6= j. As with linkable signatures,

deﬁne I = H(y

)

. Then deﬁne

= g

(12)

= H(y

)

(13)

j+1

= H(L

, R

) (14)

For the remaining i ∈ {j + 1, , n, , j − 1} ( mod n so n goes to zero, then back to j)

= g

(15)

= H(y

)

(16)

i+1

= H(L

, R

) (17)

...

= H(L

j−1

, R

j−1

) (18)

Now that we have c

, we can deﬁne

= v − c

x (19)

Then we can calculate L

and R

as we did for all L

and R

, using r

and c

, and the values should be equal

to the original L

and R

calculated using v. The prover now sends (I, y

, r

, , y

n−1

, r

n−1

, c

) to the veriﬁer.

The veriﬁer can reconstruct all (c

, L

, R

) and then check that c

= c

3.3 Multilayered LSAG Signatures

LSAG signatures allow a compact representation of a linked ring signature, but each real key needs its own

signature, and there is no way to associate the real keys with interleaved data.

The MLSAG solves this by using key vectors rather than single keys [4]. So key y

is instead a vector of m

keys

= (y

i,0

, ..., y

i,m−1

) (20)

As before, there exists a secret index j, for which we know the private keys to each public key. Each r

now also a vector, and

= (r

i,0

, ..., r

i,m−1

) (21)

∀i 6= j, r

consists of random numbers.

The prover proceeds as with an LSAG, starting with index j. v is now a vector of m elements. The L

j,k

and

j,k

entries are calculated in the same way, but using y

j,k

and v

. c

j+1

is calculated using all L

j,k

and R

j,k

= g

(22)

j,k

= H(y

j,k

)

(23)

j+1

= H(L

j,0

, R

j,0

, ..., L

j,m−1

, R

j,m−1

) (24)

As before, the prover calculates the remaining L

and R

using the corresponding c

, r

, and I, and the hash

for c

i+1

contains the full set of L

i,k

and R

i,k

= g

i,k

(25)

i,k

= H(y

)

i,k

(26)

i+1

= H(L

i,0

, R

i,0

, ..., L

i,m−1

, R

i,m−1

) (27)

... (28)

= H(L

j−1,0

, R

j−1,0

, ..., L

j−1,m−1

, R

j−1,m−1

) (29)

Now that we have c

, we can calculate the r

j,k

as before:

j,k

= v

− c

(30)

The prover sends the same set of (I, y

, r

, ..., y

m−1

, r

m−1

, c

) as for LSAG, but each y

and r

is now a

vector. The veriﬁer again calculates the full set of c

, with corresponding L

and R

, and checks that c

= c

3.4 Signing external data

Schnorr proofs and ring signatures do a good job of signing public keys, with a variety of options for obfuscating

mixins and consolidating space. But it is often desirable to sign external data, such as a transaction body. This

way the signature validates not only ownership of the inputs, but also locks the signature to the spent outputs,

amounts, or any other metadata which is necessary to prevent transaction malleability.

To sign external data d, take a hash of it then prepend it to the signature hash. But hashing the external data

directly can lead to collisions, which obviates the point of hashing. So it is common to use domain separators

in the hash:

m = H(”transaction body”, d) (31)

For a standard linkable ring signature, the prover would do the following:

c + c1 = H(m, g

, H(y)

, g

, H(y)

) (32)

The veriﬁer also has access to the external data, and does the same calculation:

m = H(”transaction body”, d) (33)

c + c1 = H(m, g

, H(y)

, g

, H(y)

) (34)

This links the signature to the external data, and if the data is altered the veriﬁer signature will fail validation.

4 Conﬁdential Transactions

Using linkable ring signatures, we can obscure (but not hide) the real inputs to a transaction. However, the

amounts of each input must be visible in order to show that the transaction does not generate free coins: the

sum of the inputs must equal the sum of the outputs. How can we hide the actual amounts, while keeping the

ability to check that the transaction is balanced?

4.1 Pedersen Commitments

We can again use the diﬃculty of solving discrete logarithms to hide the real amounts behind a commitment.

The naive approach would be to simply raise our group generator g to the value v:

C = g

(35)

Then we can check that the sum of the input values is equal to the sum of the outputs:

+ v

= v

+ v

(36)

= g

(37)

= g

(38)

= C

(39)

So to check that the transaction is balanced, we check the product of the input commitments against the

product of the output commitments: if they are equal, then the transaction is balanced.

This simple approach does not work, however, because the range of values in a cryptocurrency is usually

only [0, 2

). So an attacker can brute force any commitment by trying all 2

possible values. To prevent this,

we add a random blinding factor s to the commitment [4]:

C = g

(40)

This requires another generator h, which is usually deﬁned as a hash-to-group of the generator g. If the

group is a prime order group, then any element of the group is a generator, and so a simple hash will suﬃce.

Otherwise, care must be made to assure that h is orthogonal to g.

Now when we check the transaction balance, we end up with

(41)

= g

−s

−v

(42)

But if the transaction is balanced, then v

+ v

− v

= 0, so

= g

−s

(43)

We deﬁne the sum of the input blinding factors minus the output blinding factors to be

z = s

+ s

− s

(44)

Which means that the ratio of the product of the commitments is now just g

, and thus we know the private

key z which corresponds to the public key generated from the commitments:

= g

(45)

We already know how to sign a public key if we know the private key, which means we can sign this

commitment to zero, and a veriﬁer can check it. This allows a veriﬁer to validate the transaction is balanced.

4.2 Range Proofs

Now that the values can be hidden, we have a new problem. Since we are checking that the sum of the inputs

matches the sum of the outputs, what happens if one of the output values is negative? The transaction will be

balanced, but we will end up minting new coins. How can we prevent this? The answer is via the use of range

proofs [4].

First, consider a n-bit binary expansion of v:

v = b

+ b

+ ... + b

n−1

(46)

If v is in the range [0, 2

) then we know that each b

∈ 0, 1. Remember that we committed to v with

C = g

. Choose a series of s

such that

n−1

= s (47)

Then write commitments for each bit in the binary expansion thus

= g

(48)

As before, the sum of the values in these commitments will be equal to v, but also the sum of the bit blinding

factors s

will also equal s. So

= C (49)

This allows the validator to check that the binary expansion is valid. And if each b

∈ 0, 1, then one of the

following must be a commitment to zero:

, g

−2

} (50)

So either the ﬁrst or the second terms will reduce to g

, and since the prover know s

he can sign the ring.

We don’t need linkability, so we can use basic ring signatures of size 2. The prover of course knows which term

is actually a commitment to zero, and can sign accordingly.

The range proof thus consists of the n bit commitments C

and corresponding ring signatures. The veriﬁer

checks the validity of each bit proof, and then veriﬁes that

C =

(51)

5 Bulletproofs

Range proofs allow us to verify that output commitments are not negative, but they use a lot of space; each

output range proof consists of 64 separate ring signatures. It would be preferable to somehow consolidate them,

and there are a variety of techniques to do so. Bulletproofs [5] are a compact way to represent aggregated range

proofs, and result in signiﬁcant space savings.

Bulletproofs are not just useful as aggregated range proofs; more generally, they also have the ability to

represent arbitrary arithmetic circuits. They have similar functionality with zkSNARKs, but require no trusted

setup.

5.1 Notation

The bulletproofs paper uses several notation systems. Some were innovative, like the use of boldfaced group

elements to represent that they were arrays. Some were just obscure, like using the ◦ operator to denote pairwise

multiplication of vectors, But other, like using the python[: n] array slicing operator were verbose and annoying.

So pretty much everyone who implented, or tried to explain bulletproofs, emded up replacing something with

their own. Here I will limit myself to replacing the [: n] operator with B for the bottom half and T for the top.

We can do this because we are only ever dealing with powers of two, so it is never ambiguous.

5.2 Improved Inner Product Argument

The heart of a bulletproof is a vector commitment that links a committed value with an inner product. The

prover uses a recursive protocol that at every step cuts the size of the vectors in half and generates a new

commitment, until only a single element remains, then sends the ﬁnal values with the corresponding generators

and commitment as the proof. The veriﬁer checks that the ﬁnal commitment is valid, then unwinds the stack.

So for some (g, h) ∈ G

, (a, b) ∈ Z

, (u, P ) ∈ G, c ∈ Z

, let P = g

and c = ha, bi. The goal is to ﬁnd

a way to prove knowledge of a and b to someone who knows P and c, without revealing them. To do this, the

prover adds the inner product to the commitment itself:

P = g

· u

ha,bi

(52)

Since the goal is to shrink the problem in half, let n

= n/2. Since (g, h) are still size n, split each into

bottom (g

, h

) and top (g

, h

), with the ﬁrst n

elements in the bottom vector and the second n

in the

top. Then for some a

, a

, b

∈ Z

, deﬁne the function H to operate on the split vectors.

H(a

, a

, b

, c) = g

· u

(53)

We can deﬁne P in terms of H, splitting the real (a, b) as well into bottom and top:

P = g

· u

ha,bi

(54)

= g

· u

ha,bi

(55)

= H(a

, a

, b

, ha, bi) (56)

H is additively homomorphic:

H(a

, b

, c

) · H(a

, a

, b

, c

) = H(a

+ a

, a

+ a

, b

+ b

, b

+ b

, c

+ c

) (57)

Now deﬁne L, R ∈ G:

L = H(0

, a

, b

, 0

, ha

, b

i) (58)

R = H(a

, 0

, b

, ha

, b

i) (59)

Prover sends (L, R) to the veriﬁer, who responds with the challenge x ∈ Z

. Prover then combines the left

and right parts of (a, b) into single vectors using the challenge:

= xa

+ x

−1

(60)

= x

−1

+ xb

(61)

Prover sends (a

, b

) to veriﬁer, who ﬁrst computes P

from (P, L, R, x):

= L

)

· P · R

−2

)

(62)

Veriﬁer then uses (x, a

, b

) to calculate Q

= H(x

−1

a’, xa’, xb’, x

−1

b’, ha’, b’i) (63)

Veriﬁer validates if P

= Q

. If we expand Q

we can see why:

= H(x

−1

(xa

+ x

−1

), x(xa

+ x

−1

), x(x

−1

+ xb

), x

−1

+ xb



+ x

−1

, x

−1

+ xb



)

= H(a

+ x

−2

, x

+ a

, b

+ x

, x

−2

+ b

, x

, b

i + ha, bi + x

−2

, b

i) (64)

It’s because we get the same thing when we expand P

= H(0

, x

, 0

, x

, b

i) · H(a

, a

, b

, ha, bi)·

H(x

−2

, 0

, x

−2

, x

−2

, b

= H(a

+ x

−2

, x

+ a

, b

+ x

, x

−2

+ b

, x

, b

i + ha, bi + x

−2

, b

i) (65)

So if the prover can construct (L, R, a’, b’) such that P

= Q

, then he must have known (a, b).

5.3 Range Proof Using Inner Product

Let a

be a vector with the n bits of v. Then the following must all be true:

, 2

i = v; a

◦ a

= 0

; a

= a

− 1

(66)

is deﬁned to be the negation of a

: 0 where 1, and −1 where 0. So any pairwise multiplication between

and a

will be 0.

Given a veriﬁer chosen y ∈ G, these relations are equivalent to:

, 2

i = v; ha

, a

◦ y

i = 0; ha

− 1

− a

, y

i = 0 (67)

As before, pairwise multiplication between a

and a

will be 0, regardless of multiplying by y

, and summing

the dot product will likewise be 0. And solving the third relation for 0 gives us another dot product of 0 with

our new y

Using another veriﬁer chosen z ∈ G, we can combine these into one relation:

· ha

, 2

i + z · ha

− 1

− a

, y

i + ha

, a

◦ y

i = z

v (68)

Multiplying the ﬁrst relation by z

gives us the z

v term, and since the other two relations were 0 we can

add them for free (swapping order and multiplying one by z).

If we expand the inner products, then start isolating prover and veriﬁer terms, we get:

· ha

, 2

i + z · ha

, y

i − z · h1

, y

i − z · ha

, y

i + ha

, a

◦ y

i = z

· ha

, 2

i + z · ha

, y

i − z · ha

, y

i + ha

, a

◦ y

i = z

v + z · h1

, y

Since an inner product ha, bi can be broken into a pairwise/inner product h1

, abi:

· ha

, 2

i + z · ha

, y

i − z · h1

, a

◦ y

i + ha

, a

◦ y

i = z

v + z · h1

, y



, z

· 2

+ z · y



+ ha

− z · 1

, a

◦ y

i = z

v + z · h1

, y

In order to merge the inner products via the ﬁrst term, add



−z1

, z

+ zy





− z · 1n, z

· 2

+ z · y

+ a

◦ y



= z

v + z · h1

, y

i + h−z · 1

, z2 · 2

+ z · y



− z · 1n, z

· 2

+ z · y

+ a

◦ y



= z

v + z · h1

, y

i − z ·



, z

· 2

+ z · y





− z · 1

, z

· 2

+ z · y

+ a

◦ y



= z

v + z · h1

, y

i − z3 · h1

, 2

i − z

· h1

, y



− z · 1

, z

· 2

+ z · y

+ a

◦ y



= z

v + (z − z

) · h1

, y

i − z

, 2

Let d(y, z) = (z − z

) h1

, y

i − z

, 2

i, and we get the ﬁnal form:



− z · 1

, z

· 2

+ z · y

+ a

◦ y



= z

v + d(y, z) (69)

The veriﬁer can calculate the right side (using the commitment V for v), and the problem is now reduced

to an inner product argument.

5.4 Blinding the inner product

We have shown how to make a logarithmically eﬃcient inner product argument, and how to reduce a range

proof to an inner product. But the inner product argument is not zero knowledge, so we can’t use it directly;

we must ﬁrst blind the parameters.

Let (s

, s

) be vectors of integers:

, s

) ← Z

(70)

Replace a

with (a

+ s

x) and a

with (a

+ s

x), and the inner product becomes:



+ s

x) − z1

, z

+ zy

+ (a

+ s

x) ◦ y



= z

v + d(y, z) (71)

Then construct vector polynomials l(x) and r(x) from the two sides of the inner product:

l(x) = a

+ s

x − z1

(72)

r(x) = z

+ zy

+ (a

+ s

x) ◦ y

(73)

The zeros of these vector polynomials are just the unblinded inner product terms:

l(0) = a

− z1

(74)

r(0) = z

+ zy

+ a

◦ y

(75)

The inner product then becomes

hl(0), r(0)i = z

v + d(y, z) (76)

We can express l(x) and r(x) as generic degree one polynomials

l(x) = l

+ l

x (77)

r(x) = r

+ r

x (78)

Where

= a

− z1

(79)

= s

(80)

= z

+ zy

+ a

◦ y

(81)

= s

◦ y

(82)

(83)

If we deﬁne t(x) as the inner product of the blinded vector polynomials, we get

t(x) = hl(x), r(x)i (84)

We can express this in terms of x:

t(x) = t

+ t

x + t

(85)

Where

= hl

, r

i = z

v + d(y, z) (86)

= hl

, r

i (87)

= hl

+ l

, r

+ r

i − t

− t

(88)

Proving the blinded inner product range proof now depends on simply verifying that both

= z

v + d(y, z) (89)

t(x) = hl(x), r(x)i = t

+ t

x + t

(90)

6 CryptoNote

CryptoNote [3] is a privacy focused cryptocurrency system which implements many of the techniques explored

above, plus a novel method for tying long term public keys to one time addresses. CryptoNote is deﬁned to use

elliptic curves rather than exponentials, but I will break with that to maintain consistency with the rest of the

document, and use exponentials in this section.

6.1 One time addresses

A CryptoNote key consists of a pair of public keys (A, B) with their associated private keys (a, b). To construct

a one time address, the creator of a transaction starts with a transaction private key r, and an associated

transaction public key R:

R = g

(91)

The creator then uses this, with the destination public key (A, B), to construct the one time address y. This

address is a public key, with an associated private key x:

y = g

= g

H(rA)

B (92)

The owner of the destination key (A, B) can scan the transaction one time addresses to determine if he is

the owner. He ﬁrst uses his private key (a, b) to attempt to recover the one time private key x:

x = H(Ra) + b (93)

Then raise g to this power to reconstruct the public key y:

= g

H(Ra)

(94)

If y = g

, then the destination key was the same one used to construct the one time address, and the key

owner is the owner of the one time address. Since the owner knows the private key x, he is able to sign the key

y in a ring signature, allowing him to spend it.

6.2 View keys

One time addresses allow a user to ﬁnd the transaction outputs which he owns. But this requires the user to

scan the entire blockchain, looking at every output. For users with limited storage and bandwidth, this can be

problematic. It would be preferable to allow a trusted node to do the scanning for the user, while preventing

the node from being able to spend the output.

To do this, the user can pass a tuple of his private key a with his public key B:

V = (a, B) (95)

The node can then look at each transaction, and use the view key with the transaction public key R to

attempt to reconstruct the one time public key y:

Y = g

H(Ra)

B (96)

If Y = y, then the node knows that the one time key belongs to the user, and returns it.

6.3 Ring signatures

CryptoNote uses linkable ring signatures, with external data. It deﬁnes a transaction preﬁx to be all of the

transaction data except for the ring signatures themselves, which includes the input and output public keys,

with the transaction public key and amounts. The transaction preﬁx is serialized then hashed to create the

signed message m.

7 Monero

Monero is a privacy focused cryptocurrency. In its initial implementation, it used a vanilla implementation of

cryptonote [3]. Later iterations added conﬁdential transactions, with standard range proofs [4]. Recent work

includes upgrading the range proofs with bulletproofs for signiﬁcant space savings.

7.1 RingCT

The Monero implementation of conﬁdential transactions is called RingCT [4]. It uses MLSAG signatures that

tie a set of Pedersen Commitments to a set of input keys. This is necessary because to verify a conﬁdential

transaction, it is required to have a full set of the commitments used in order to recover g

. Without the

MLSAG, any attempt to include the commitments would either be unable to recover g

, or would expose the

real input keys.

To accomplish this, the MLSAG signature adds the corresponding commitments to the public key vectors,

then passes them in the signature output:

= ((y

i,0

, C

i,0

), ..., (y

i,m−1

, C

i,m−1

)) (97)

When constructing the hashes, the prover signs a ﬁnal term which is the sum of the input commitments

minus the sum of the output commitments:

(98)

j,m

= g

(99)

j+1

= H(L

j,0

, R

j,0

, ..., L

j,m−1

, R

j,m−1

, L

j,m

) (100)

As before, if this sum is a commitment to zero, then it will take the form of a public key g

, where the user

knows the private key z. So it can be signed like any other public key in a ring signature. Since the commitment

does not need to be linkable, it is not necessary to include a R

j,m

term, or a key image. It will be necessary to

create a new v

and include an additional r

j,m

in the signature:

j,m

= v

− c

z (101)

The veriﬁer uses this additional r

j,m

and c

to build a standard Schnorr term:

j+1

= H(L

j,0

, L

j,0

, ..., L

j,0

, L

j,0

, g

j,m

) (102)

As before, if the sum was a commitment to zero, then this term will be the same in the prover and veriﬁer

hashes.

8 Zcash

Zcash is one of the more technically advanced cryptosystems available on current exchanges. It uses zero-

knowledge proofs to allow for completely hidden transactions, that can still be validated externally. It divides

its address space into t-addresses, whose details are transparent, and z-addresses, which are hidden from all but

the participants. Money that passes from a t-address to a z-address cannot be tracked, even if it later goes back

to a t-address.

8.1 zkSNARKs

A zkSNARK is a zero-knowledge, short, non-interactive argument of knowledge. It allows the prover to create

a representation of an arbitrary arithmetic or logic circuit, then make proofs about assertions relative to that

circuit. The proofs are computationally diﬃcult to construct, though easier to evaluate, and require a trusted

setup between prover and veriﬁer.

9 Lelantus

There is a new Zerocoin based cryptocurrency system called Lelantus [6], released 2018-12-22. It uses conﬁdential

transactions, and claims to be able to hide the inputs fully while still being auditable.

As per Zerocoin, Lelantus uses the output commitments as the transaction inputs/outputs themselves,

rather than associating the commitments with a one time address as in RingCT. It is thus necessary to reveal

the commitment secret during the spend, similar to the way that CryptoNote reveals the key image. So it is

necessary to make the commitments double blind, or else after secret reveal it would be possible to brute force

the values as per the naive approach to Pedersen commitments. Adapting Lelantus to a more CryptoNote-ish

system could obviate this need, and allow single blinded commitments.

9.1 Σ-protocol for commitment to 0 or 1

Consider a commitment to a message m with random blinding factor r:

c = Com(m, r) (103)

To prove that c opens to 0 or 1, pick random (a, s, t) and use them to construct (c

, c

a, s, t ∈ Z

(104)

= Com(a, s) (105)

= Com(am, t) (106)

In an interactive protocol, the prover would send (c

, c

) to the veriﬁer, who would respond with the challenge

x. To make it non-interactive, hash (c, c

, c

x = H(c, c

, c

) (107)

Either way, the prover uses x to construct (f, z

, z

) and sends it to the veriﬁer:

f = mx + a (108)

= rx + s (109)

= r(x − f) + t (110)

The veriﬁer now has the full set of (c, c

, c

, x, f, z

, z

) and accepts the proof if both of the following are

true:

= Com(f, z

) (111)

x−f

= Com(0, z

) (112)

This follows as

= Com(xm, xr) · Com(a, s) (113)

= Com(xm + a, xr + s) (114)

= Com(f, za) (115)

x−f

= Com((x − f)m, (x − f)r) · Com(am, t) (116)

= Com(xm − fm + am, (x − f)r + t) (117)

= Com(xm − (mx + a)m + am, z

) (118)

= Com(xm − m

x, z

) (119)

Since x is not 0, then x(m − m

) is only 0 when (m − m

) is 0, or when

m = m

(120)

This is only true ∀m ∈ 0, 1. So if c

x−f

= Com(0, zb), m ∈ 0, 1.

9.2 One out of Many Σ-proofs

Ring signatures allow hiding a signature in a set of mixins. But they grow in size linearly with the mixin set

size. So the mixin set must be limited, and cannot contain every transaction in the ledger. Merkle proofs

oﬀer a logarithmic sized proof for ledger inclusion, but are not zero knowledge. It would be ideal to be able

to demonstrate both ownership and leder inclusion with a single proof. One out of many proofs do this, in

logarithmic size. So every output in the ledger functions as a mixin, and the proof size scales logarithmically

with the ledger size.

Consider a set of N commitments:

= g

(121)

If we know that this set contains a commitment to 0, then we know an index l such that

N−1

i=0

(122)

is a commitment to zero. This is true because δ

= 1, while all other δ

= 0. So this product is simply c

as the rest of the c

are canceled by raising to 0.

Assuming N = 2

, extending as necessary, expand i and l in binary:

i = i

...i

(123)

l = l

...l

(124)

We can now express δ

in terms of these bits:

j=1

(125)

Combining these two terms, our commitment to 0 C becomes

C =

N−1

i=0

j=1

(126)

Next we iterate over all n bits, committing to the bits of l and proving they are all zero or one using the

previous protocol. After getting the challenge x we will generate an f , but now there is one for each bit of l:

= l

x + a

(127)

We can further deﬁne f

j,i

as a function of f

that depends on i

j,1

= f

= l

x + a

(128)

j,0

= x − f

= (1 − l

)x − a

(129)

For each i, we can take the product p

(x) of the f

j,i

terms:

(x) =

j=1

j,i

(130)

In all cases, f

j,i

will be a linear function of x, so p

(x) will be a polynomial in x of degree n; but the x term

will cancel ∀j such that l

6= i

. So ∀i 6= l, at least one of the x terms will cancel; thus

(x) =

j=1

j,i

j=1

x +

n−1

k=0

i,k

(131)

If we have x, then we can calculate this product directly. But before we have x, we can still evaluate this

polynomial algebraically. If we do so, we can determine the p

i,k

parameters in terms of a

. This allows us to

use p

i,k

once we have a

For all j = (1, ..., n) with k = j − 1:

, a

, s

, t

, ρ

) ←− Z

(132)

= Com(l

; r

) (133)

= Com(a

; s

) (134)

= Com(l

; t

) (135)

N−1

i=0

i,k

· Com(0; ρ

) (136)

The veriﬁer responds with the challenge x, or it is generated via Fiat-Shamir. Prover then uses x as per the

previous protocol to construct, ∀j:

= l

+ a

(137)

= r

x + s

(138)

= r

(x − f

) + t

(139)

The prover then constructs the ﬁnal value:

= rx

−

n−1

k=0

(140)

The veriﬁer must check the individual bit proofs:

= Com(f

; z

) (141)

x−f

= Com(0; z

) (142)

As before, the ﬁrst line proves knowledge of l

, and the second proves it was binary. Finally, the veriﬁer

checks z

against c

using c

and f

j,i

N−1

i=0

j=1

j,i

n−1

k=0

−x

= Com(0; z

) (143)

If we simplify using p

(x) and expand we can see why this is true:

N−1

i=0

j=1

j,i

n−1

k=0

−x

N−1

i=0

(x)

n−1

k=0

(

N−1

i=0

i,k

Com(0; ρ

))

−x

(144)

N−1

i=0

j=1

n−1

k=0

i,k

n−1

k=0

(

N−1

i=0

i,k

Com(0; ρ

))

−x

(145)

= c

N−1

i=0

n−1

k=0

i,k

n−1

k=0

Com(0; ρ

)

−x

n−1

k=0

(

N−1

i=0

i,k

)

−x

(146)

= Com(0; rx

)

n−1

k=0

Com(0; ρ

)

−x

n−1

k=0

N−1

i=0

i,k

n−1

k=0

N−1

i=0

−p

i,k

(147)

= Com(0; rx

)

n−1

k=0

Com(0; ρ

)

−x

(148)

Com(0; z

) = Com(0; rx

−

n−1

k=0

) (149)

= Com(0; rx

)

n−1

k=0

Com(0; ρ

)

−x

(150)

9.3 Hiding Transaction Amounts and Origins

Conﬁdential Transactions are good at hiding amounts, but it is necessary to reveal the commitments themselves

in order to prove that a transaction is balanced, i.e. that the sum of the inputs equals the sum of the outputs.

RingCT obfuscates the actual input commitments in a ring of mixins (with both addresses and commitments),

but the data is still present and subject to analysis. It would be better to be able to prove both input ownership

and transaction balance without ever showing the input commitments.

Lelantus accomplishes this via a two step process. It establishes input ownership via a set of one out of

many Σ-proofs, then uses elements of the Σ-proofs to to establish a balance proof. At no time are the input

commitments themselves revealed to the veriﬁer.

To show how the balance proof arises from the elements of the Σ-proofs, consider the following values:

= v

−

n−1

k=0

(151)

Com(0, ρ

) = g

(152)

The veriﬁer can then compute the following:

A = (

new

i=1

)

= (

new

i=1

)

= g

(Σs

(Σv

(153)

B = Com(0,

old

i=1

)

old

i=1

(

n−1

k=0

Com(0, ρ

)

) (154)

= g

(

old

i=1

−

n−1

k=0

old

i=1

(

n−1

k=0

) (155)

= h

(

old

i=1

−

n−1

k=0

old

i=1

n−1

k=0

= h

(

(156)

The ratio of A to B is thus:

(

(157)

As before, if the transaction is balanced then

(158)

And thus

= g

(

(159)

Since the prover knows the output serial numbers, this is a public key to which he knows the private key.

So it suﬃces to provide a regular Schnorr proof for this ratio to prove that the transaction is balanced, and no

input commitments have been revealed.

10 Mimblewimble

Some of the most recently released cryptocurrencies use a relatively new system called Mimblewimble [8]. The

goals are to implement a system with the beneﬁts of RingCT, but with a pruned blockchain that still veriﬁes

even after removing spent outputs. As a downside, the sender and receiver of a transaction must complete an

interactive protocol.

10.1 One Way Aggregate Signatures

While RingCT uses ring signatures with mixins to obscure the links between inputs and outputs, Mimblewimble

rather aggregates all of the transactions in a block via a technique they call One Way Aggregate Signatures [7].

Thus the individual links between the inputs and outputs of the transactions is lost, and only the block level

linking is still present. This happens naturally as a result of the transaction format.

Consider a transaction with input commitments C

and output commitments C

. As with all implemen-

tations of conﬁdential transactions, the sum of the input commitments minus the outputs will be the ratio of

their products, and this will be a public key to which the owner knows the private key:

= g

−s

= g

= C

(160)

The transaction format is thus the set (C

, ..., C

, C

, ..., C

, C

), with a signature on CT to prove the

balance. Given this format, it is trivial to combine transactions; you can simply add the new input, output, and

balance commitments to the existing set, and the balance check should still succeed with the combined sets:

(

)

(161)

A veriﬁer can check the signatures on the individual C

and the aggregated balance check; if they all succeed,

the aggregated transaction set is still valid.

Using this technique, miners will aggregate all of the transactions in a block into a single set with a single

aggregated signature. After the new block is formed, nodes can again merge the transactions from the new

block into the set of all transactions. Once this is done, any spent outputs will appear in both the output list

and the input list. Such outputs can be safely pruned from both lists, and a balance check over the entire

ledger will still be valid. This is clear, as any such transactions will appear in both the top and bottom of the

input/output ratio, and will thus cancel each other out.

Thanks to this pruning, Mimblewimble achieves its goal of maintaining a lightweight ledger, with only

unspent outputs and no inputs. This makes the ledger small, only growing with the UTXO set. And for

observers who want to analyze the ledger, there is no way to link transactions.

However, any observer who sees the advertised transactions (either a peer or a miner) has full visibility

into the money ﬂow, and can easily link transactions, since the inputs and outputs are directly listed with

no obfuscation. And all node operators get a list of the inputs and outputs in every block, which gives them

obfuscated access to the same data (though on a per block rather than per transaction level).

Since spent outputs will be removed, it will no longer be possible to validate a block using normal merkle

tree semantics, since this requires having all leaf nodes to construct the root hash. So every output will need

a separate merkle proof, to tie it to the root hash at time of block creation. Validating a block will require

validating each remaining output’s merkle proof.

Finally, while there are indeed space savings from removing inputs and spent outputs, it is necessary to store

all balance commitments C

and their associated Schnorr proofs forever. This set grows monotonically with

each added transaction.

11 MobileCoin

MobileCoin is a new cryptocurrency, whose goals are privacy, convenience, and provable correctness. The proof

of concept implementation uses CryptoNote as a transaction format, with the Stellar Consensus Protocol to

achieve blockchain consensus, rather than a wasteful proof of work. All computation on the nodes uses a secure

enclave, to prevent even node operators from having access to view keys or rings.

For maximal convenience, MobileCoin will be introduced directly into secure messaging apps, using mobile

devices’ secure storage for keys. Since there is no mining, transactions will be conﬁrmed quickly. A user will be

able to open a messaging app and quickly send untraceable money, usually within a matter of seconds.

The main weakness of CryptoNote is that the ring signatures contain the actual inputs used in the trans-

action, though these are obscured by a number of mixins. So anyone with access to the ledger can perform a

number of attacks, linking payments to their eventual destinations. This can be used in the common Overseer

scenario, where collusion between two parties can unmask the owners of coins sent by one and cashed out at

the other. So the FBI could send coins to a suspect address, then wait for those coins to make their way to an

exchange, at which point the identity of the owner of the suspect address can be determined.

To address this, MobileCoin currently drops the inputs from transactions before writing them to the ledger,

indeed before the transactions even leave the secure enclave. This guarantees full privacy from ledger analysis,

at the cost of external veriﬁability. The consensus quorum becomes the arbiter of correctness, and since the

software is open source and anyone can run a node, this functions to attest to the correctness of the ledger.

12 Acknowledgements

The author would like to thank Toby Segaran for initial help on ring signatures, and Isis Lovecruft for the initial

review.

References

[1] Schnorr signature. https://en.wikipedia.org/wiki/Schnorr%5Fsignature

[2] Fiat Shamir heuristic. https://en.wikipedia.org/wiki/Fiat%2DShamir%5Fheuristic

[3] Nicolas van Saberhagen. CryptoNote v2.0 October 17, 2013. https://www.bytecoin.org/old/whitepaper.pdf

[4] Shen Noether, Adam Mackenzie, the Monero Research Lab. Ring Conﬁdential Transactions for Monero DOI

10.5195/LEDGER.2016.34. http://eprint.iacr.org/2015/1098

[5] Benedikt Bnz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, and Greg Maxwell. Bulletproofs: Short

proofs for conﬁdential transactions and more Cryptology ePrint Archive, Report 2017/1066, 2017.

https://eprint.iacr.org/2017/1066

[6] Aram Jivanyan. Lelantus: Private transactions with hidden origins and amounts based on DDH 2018.12.22.

https://lelantus.io/lelantus.pdf

[7] Dr. Yuan Horas Mouton. Increasing Anonymity in Bitcoin.

https://download.wpsoftware.net/bitcoin/wizardry/horasyuanmouton-owas.pdf

[8] Tom Elvis Jedusor. MIMBLEWIMBLE 19 July, 2016.

https://download.wpsoftware.net/bitcoin/wizardry/mimblewimble.txt