# A ZK-SNARK based Proof of Assets Protocol for Bitcoin Exchanges

B Swaroopa Reddy
<EMAIL_ADDRESS>
###### Abstract

This paper proposes a protocol for Proof of Assets of a bitcoin exchange using
the Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (ZK-SNARK)
without revealing either the bitcoin addresses of the exchange or balances
associated with those addresses. The proof of assets is a mechanism to prove
the total value of bitcoins the exchange has authority to spend using its
private keys. We construct a privacy-preserving ZK-SNARK proof system to prove
the knowledge of the private keys corresponding to the bitcoin assets of an
exchange. The ZK-SNARK tool-chain helps to convert an NP-Statement for proving
the knowledge of the private keys (known to the exchange) into a circuit
satisfiability problem. In this protocol, the exchange creates a Pedersen
commitment to the value of bitcoins associated with each address without
revealing the balance. The simulation results show that the proof generation
time, size, and verification time are efficient in practice.

###### Index Terms:

Bitcoin Exchange, Zero-Knowledge Proofs, ZK- SNARK, Proof of Assets, Rank1
Constraint System, Quadratic Arithmetic Programs, Pedersen Commitment.

##  I Introduction

Blockchain technology gained popularity due to its immutability,
trustlessness, and decentralized architecture. Every public blockchain network
is associated with a corresponding virtual currency named cryptocurrency (or
shortly crypto). Satoshi Nakamoto introduced the first crypto called bitcoin
with the deployment of the bitcoin blockchain [1] in 2009. The blockchain
networks issue cryptocurrency through a mechanism known as the mining process,
e.g., the Proof-of-Work [1] mechanism in bitcoin. The field of
cryptocurrencies is ever-expanding, and as of today, there are more than
$4000$ cryptocurrencies in existence. Bitcoin has achieved one trillion-dollar
market capitalization [2] as there is huge demand from institutional and
retail investors. Other popular cryptocurrencies are Ethereum [3], Ripple [4],
Zerocash [5], Stellar [6], Monero [7], etc.

In a blockchain network, every owner of the crypto holds a private key to
spend the crypto through a chain of digital signatures [1]. If private keys
are stolen or misplaced or the device where the private key stored crashes,
the owner loses crypto ownership. So, the users prefer to keep their crypto
holdings with exchanges like coinbase [8], binance [9], etc. The crypto
exchanges facilitate crypto trading for fiat currencies or other
cryptocurrencies and gain profits through commissions/brokerage charges,
listing charges, etc. The exchanges act as an intermediary between buyer and
seller by using the mechanism of order-book, similar to the traditional stock
exchanges.

The crypto exchanges accept deposits from users through bank transfers or
other standard means of deposit. The exchanges hold the private keys on behalf
of the users and provides authentication facility through username and
password to authenticate the customer’s identity and also provide the recovery
facility in case of customer forgets or lost authentication details. So, the
customers are free from storing private keys for their cryptocurrencies. But
there is a risk of missing customer assets maintained by exchanges as in the
case of Mt.Gox exchange [10] due to internal or external frauds. In the
traditional banking system, the central bank imposes restrictions on the
commercial banks to maintain a fraction of their total liabilities called
fractional reserve ratio [11] as reserves, expecting that only a fraction of
depositors seek to withdraw funds at the same time. But, the crypto community
is expecting a fully solvent exchange instead of proving a fractional solvency
of exchange’s reserves.

In this paper, we propose a proof of assets protocol for a bitcoin exchange
based on the ZK-SNARK proof system [12], [13]. ZK-SNARK is an advancement in
the zero-knowledge proofs. Zcash protocol proposed in [14] uses ZK-SNARK for
constructing the decentralized anonymous payments. ZK-SNARK is a succinct,
non-interactive zero-knowledge proof which facilitates the public
verifiability of the proof of a witness. ZK-SNARKs enable the prover to
convince the verifier on any non-deterministic decision circuits (NP-
statements) with auxiliary information (witness) and public inputs without
revealing the witness. A trusted third party takes the circuit as input and
generates a common reference string (CRS) consisting of proving and
verification keys needed to prove and verify the statement of the ZK-SNARK
scheme.

In this framework, we define the non-deterministic circuit as a statement for
verifying the knowledge of all the private keys owned by the exchange to prove
the value of bitcoin assets held by the exchange. The exchange acts as a
prover of its total assets and the customers of the exchange play the role of
a verifier in the ZK-SNARK proof system. The proof of exchange assets is
equivalent to proving ownership of the private keys associated with the
bitcoin addresses111In this work, the bitcoin addresses are the P2PK (Pay to
Public Key) addresses [15] where the public keys corresponding to the private
keys are called the bitcoin addresses. owned by an exchange to match the
liabilities of the exchange to the customers.

The exchange as a prover takes the private keys as an auxiliary input, public
keys and the corresponding balances as public inputs. The exchange take the
proving key and the inputs (auxiliary and public) as input parameters and
constructs the proof for the witness. The exchange outputs a Pedersen
commitment [16] to the balance associated with the key pair (part of the
auxiliary input). The customers are the public verifiers for verifying the
knowledge of the private key to acknowledge the reserves/assets of the
exchange from the proof generated by exchanges. The proof size is succinct and
it does not leaks the private keys (witness) used in the proof construction.
The proposed protocol also preserves the privacy of the exchange as the proof
system neither reveals the bitcoin addresses information nor the value of the
bitcoins held by the exchange.

The results demonstrate that the construction of the proof requires a few
hours on an ordinary computer which could be reduced further on a server with
high-end processors, which allows the prover to generate proof of assets very
frequently. The ZK-SNARK system generates the proof of size, approximately 128
bytes per private key, and the customer can verify the proof of exchange
assets in the order of minutes.

The rest of the paper is organized as follows - In section II, we discuss the
related work. Section III describes the preliminaries. In section IV, we
discuss the proposed Proof of Assets protocol. In section V, we present the
results and discussion. Section VI concludes the paper and gives future
directions of the research.

##  II Related Work

In [17], the authors discuss the proof of reserves for bitcoin exchange. The
maxwell’s proof of reserves discloses the number of bitcoins an exchange holds
and the bitcoin addresses for which it knows the private keys. This framework
uses the Merkle tree approach to prove the exchange’s liabilities by including
each customer’s funds as a leaf of the Merkle tree. The proof of assets is a
straightforward approach of providing signatures with all private keys owned
by the exchange.

In Provisions [18], the authors propose a privacy-preserving proof of solvency
for bitcoin exchanges using crypto primitives like zero-knowledge proofs [19,
20], and Pedersen commitments [16]. Provisions discusses three protocols –
Proof of assets, proof of liabilities, and proof of solvency. It also
discusses the proof of non-collusion between exchanges. The proof of assets
$\Sigma$ protocol proves the knowledge of exchange’s assets by providing
Pedersen commitments to the amounts of bitcoins the exchange holds for a set
of known public keys. It also proves the knowledge of a binary value using
Pedersen commitments if it knows the private keys corresponding to the known
public keys. The proof of liabilities provides the Pedersen commitments to
balances of each customer associated with the exchange and the Pedersen
commitments to the bits of the binary representation of the customer’s
balance. The proof of solvency proves that the difference between the assets
and liabilities is either a zero or a positive (if an exchange is a surplus).
In the optional proof of non-collusion protocol, the exchange creates two
lists to prove the knowledge of a non-collision with any other exchange. The
first list consists of Pedersen commitments to the private keys corresponding
to the known public keys and the second list consists of public keys generated
with a base change. The exchange proves that the second list is a permutation,
unblinding, and base change of the first list.

In [21], an exchange constructs a transaction as proof of reserves with all
the bitcoin UTXOs spendable by the exchange by adding an extra invalid input
such that the exchange is unable to spend its own UTXOs. So, this approach
discloses all the UTXOs of the exchange along with the public keys owned by an
exchange.

##  III Preliminaries

In this section, we describe the background on cryptographic primitives used
in the protocol - Ellicptic curves, Pedersen commitments and ZK-SNARK. In this
work, we stick to the Elliptic curve cryptography [22] used in bitcoin to
prove the ownership of private keys corresponding to the bitcoin addresses.

###  III-A Point Addition and Point Double

Let $\mathbb{E}$ (including a point at infinity $\mathcal{O}$) be a group of
order $q$ corresponding to points on the elliptic curve $y^{2}=x^{3}+ax+b$
over a finite field $\mathbb{F}_{p}$. The addition operation $+$ on
$\mathbb{E}$ [23] is defined as follows -

If $P(x_{1},y_{1})$ and $Q(x_{2},y_{2})$, then $P+Q=(x_{3},y_{3})$, where

$x_{3}=m^{2}-(x_{1}+x_{2}),\hskip 5.69046pty_{3}=m(x_{1}-x_{3})-y_{1}$ (1)

and,

$m=\begin{cases}\frac{y_{2}-y_{1}}{x_{2}-x_{1}},&\text{if }P\neq Q\\\
\frac{3x_{1}^{2}+a}{2y_{1}},&\text{otherwise}\end{cases}$

###  III-B Bitcoin public and private keys

Let $G\in\mathbb{E}$ be a generator or base point. The public key $K$ (bitcoin
address) corresponding to the private key
$k\in\mathbb{Z}_{q}=\\{1,2,\dots,q-1\\}$ is calculated as a scalar
multiplication [23] of $k$ with $G$.

$K=kG=G+G+\dots+G\hskip 2.84544pt(k\hskip 2.84544pttimes)$ (2)

Calculating $k$ from $K$ is called the discrete logarithm problem [24] which
is assumed to be hard.

###  III-C Pedersen Commitments

Pedersen commitment [16] $c\in\mathbb{E}$ is used to perfectly hide a message
$m\in\mathbb{Z}_{q}$. Let $H\in\mathbb{E}$ be an another generator independent
of $G$ and ensure that the discrete logarithm of $H$ for $G$ is unknown. The
Pedersen commitment $c$ to a message $m$ is

$c=mG+bH$ (3)

Where $b\in\mathbb{Z}_{q}$ is a randomly chosen blinding factor. The
commitment $c$ completely hides the message $m$ and it is opened by revealing
$m$ and $b$, one can check $mG+bH\stackrel{{\scriptstyle?}}{{=}}c$. The
Pedersen commitments are additively homomorphic.

###  III-D Non-Interactive zero-knowledge argument of knowledge for an NP
language [14]

An NP language is a set of statements $L$ such that if an instance $z\in L$,
then there exists a witness $w$, that proves the membership of the statement
$z$ in $L$ in polynomial time. In a non-interactive zero-knowledge argument of
knowledge for an NP language $L$, prover convinces verifier that it has
knowledge of auxiliary input $w$ for $z\in L$ without revealing $w$ to the
verifier. In our protocol, we use ZK-SNARK to prove and verify the membership
of the instance $z$ in $L$. ZK-SNARK uses a trick to reduce any NP-statement
$L$ to circuit satisfiabilty problem (NP complete problem). The NP-statement
is converted to non-deterministic decision circuit $C$ such that the input to
the statement is transformed as the input to the circuit $C$.

###  III-E ZK-SNARK

ZK-SNARK [25, 12, 13] is a variant of Zero-knowledge proof of knowledge [19],
[20] with succinct proof. ZK-SNARK is used to prove and verify any instance
belongs to an NP language $L$. Let $L$ be an NP statement and $C$ represents
the non deterministic decision circuit for the instance $z$. The ZK-SNARK
toolchain takes the circuit $C$ of the instance $z$ as input and generates ZK-
SNARK proof system as described in Fig. 1.

$L$: NP-statement circuit $C$ Arithmetic/Boolean Gates $R1CS$ QAP/QSP ZK-SNARK

Figure 1: Overview of the ZK-SNARK Toolchain

Initially, the circuit $C$ for $z\in L$ is converted into arithmetic gates
consisting of wires with values (from a field $\mathbb{F}_{p}$) connected to
multiplication ($*$) and addition ($+$) gates. Similarly, boolean circuits
operate over bits with gates like OR, AND, XOR, etc. Next, we convert the
algebraic gates into a Rank1 constraint system (R1CS) [26], which is a group
of three vectors ($\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$) and t is a
solution vector to the R1CS such that

$\textbf{t}.\textbf{a}*\textbf{t}.\textbf{b}=\textbf{t}.\textbf{c}$ (4)

where $(.)$ represents the dot product. The vector t ensures the satisfaction
of the constraint (4). There are as many constraints as the number of
algebraic gates in the system. The length of the vectors is equal to the total
number of variables used in the circuit. The detailed explanation of the R1CS
constraint system is discussed with examples in [26].

The next step is converting $R1CS$ into a Quadratic Arithmetic Program (QAP)/
Quadratic Span Program (QSP) [25] form to implement the same logic as $R1CS$.
A QAP $Q$ over a field $\mathbb{F}_{p}$ is defined as a tuple consisting of
the three sets of $m+1$ polynomials and a target polynomial

$Q=\left(\\{u_{i}(x)\\}_{i=0}^{m},\\{v_{i}(x)\\}_{i=0}^{m},\\{w_{i}(x)\\}_{i=0}^{m},t(x)\right)$
(5)

Suppose, if there exists $l+1$ public inputs and $m-l$ auxiliary inputs (or
witness), then the QAP $Q$ computes $C$ iff a prover needs to prove that he
knows a secret called witness $w=(a_{l+1},\dots,a_{m})\in\mathbb{F}^{m-l}$,
which satisfies the following equation with public inputs
$z=(a_{0}=1,a_{1}\dots,a_{l})\in\mathbb{F}^{l+1}$ such that $t(x)$ divides
$p(x)$ (i.e., $p(x)=t(x)h(x)$), where

$p(x)=\left(\sum_{i=0}^{m}a_{i}u_{i}(x)\right).\left(\sum_{i=0}^{m}a_{i}v_{i}(x)\right)-\left(\sum_{i=0}^{m}a_{i}w_{i}(x)\right)$
(6)

The construction of the polynomials of $Q$ is discussed in [25, 12, 26]. The
polynomials in $Q$ and $h(x)$ are specific to a particular circuit $C$
corresponding to an instance of $L$ and independent of public or auxiliary
inputs. Finally, the polynomials of $Q$ are used in the construction of the
ZK-SNARK proof system.

More formally, the relation between the circut satisfiability of an
arithmentic circuit
$C:\mathbb{F}_{p}^{l+1}\times\mathbb{F}_{p}^{m-l}\rightarrow\mathbb{F}_{p}^{k}$
and NP-language $L$ is defined by the relation
$\mathcal{R}:=\\{(z,w)\in\mathbb{F}_{p}^{l+1}\times\mathbb{F}_{p}^{m-l}\hskip
2.84544pts.t.\hskip 2.84544ptC(z,w)=\mathbf{0}^{k}\\}$ and its language
$L:=\\{z\in\mathbb{F}_{p}^{l+1}:\exists w\in\mathbb{F}_{p}^{m-l}\hskip
2.84544pts.t.\hskip 2.84544ptC(z,w)=\mathbf{0}^{k}\\}$.

In this paper, we stick to the ZK-SNARK framework proposed by Groth in [13] as
this protocol consists of a shorter proof with $3$ group elements ($2$
elements from group $\mathbb{G}_{1}$ and $1$ element from group
$\mathbb{G}_{2}$) compared to $9$ group elements in Pinocchio protocol [12].
Also the proof construction and verification times are less in Groth’s
protocol compared to Pinocchio’s protocol.

ZK-SNARK framework proposed in [13] is a set of three probabilistic polynomial
time (PPT) algorithms defined as follows:

1\. Setup Phase: $\sigma\leftarrow Setup(C,1^{\lambda})$

A trusted third party takes $C$ as input and generates common reference string
$\sigma$ as follows:

  * •

Pick $\alpha$, $\beta$, $\gamma$, $\delta$, $x\leftarrow\mathbb{F^{*}}$, set
$\mathbf{\tau}=(\alpha$, $\beta$, $\gamma$, $\delta$, $x$)

  * •

compute $\sigma=\left([\sigma_{1}]_{1},[\sigma_{2}]_{2}\right)$, where

$\displaystyle\begin{split}\sigma_{1}&=\begin{pmatrix}\alpha,\beta,\delta,\left\\{x^{i}\right\\}_{i=0}^{n-1},\left\\{\frac{\beta
u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right\\}_{i=0}^{l}\\\
\left\\{\frac{\beta u_{i}(x)+\alpha
v_{i}(x)+w_{i}(x)}{\delta}\right\\}_{i=l+1}^{m},\left\\{\frac{x^{i}t(x)}{\delta}\right\\}_{i=0}^{n-2}\end{pmatrix},\\\
\sigma_{2}&=\begin{pmatrix}\beta,\gamma,\delta,\left\\{x^{i}\right\\}_{i=0}^{n-1}\end{pmatrix}\end{split}$
(7)

Where, $[.]_{1}$ denotes elements on the group $\mathbb{G}_{1}$ and, $[.]_{2}$
denotes elements on the group $\mathbb{G}_{2}$.

2\. Proving phase:$(\pi,y)\leftarrow
Prove\left(\sigma,\\{a\\}_{i=0}^{m}\right)$

The prover computes the proof $\pi$ from the public statement
$z=\left\\{a_{i}\right\\}_{i=0}^{l}$ and witness
$w=\left\\{a_{i}\right\\}_{i=l+1}^{m}$ as follows

  * •

Pick randomly $r$, $s\leftarrow\mathbb{Z_{p}^{*}}$

  * •

Compute proof $\pi=\left([A]_{1},[B]_{2},[C]_{1}\right)$, where

$\displaystyle\begin{split}A&=\alpha+\sum_{i=0}^{m}a_{i}u_{i}(x)+r\delta,\hskip
5.69046ptB=\beta+\sum_{i=0}^{m}a_{i}v_{i}(x)+s\delta\\\
C&=\frac{\sum_{i=l+1}^{m}a_{i}\left(\beta u_{i}(x)+\alpha
v_{i}(x)+w_{i}(x)\right)+h(x)t(x)}{\delta}\\\ &+As+Br-rs\delta\end{split}$ (8)

This algorithm also computes the output ($y$) of the circuit $C$.

3\. Verification phase: $b\leftarrow
Verify\left(\sigma,\\{a\\}_{i=0}^{l}\right)$, $b\in\\{0,1\\}$

The verifier use the public inputs $\left\\{a_{i}\right\\}_{i=0}^{l}$ to
verify the proof $\pi$ and accepts the proof if and only if

$\displaystyle\begin{split}[A]_{1}.[B]_{2}&=[\alpha]_{1}.[\beta]_{2}+[C]_{1}.[\delta]_{2}\\\
&+\sum_{i=0}^{l}a_{i}\left[\frac{\beta u_{i}(x)+\alpha
v_{i}(x)+w_{i}(x)}{\gamma}\right]_{1}.[\gamma]_{2}\end{split}$ (9)

The above construction of the ZK-SNARK protocol is a non-interactive zero-
knowledge arguement of knwoledge with perfect completeness and perfect zero-
knowledge (Theorem 2 of [13]).

##  IV The proposed Proof of Assets Protocol

The protocol consists of three major entities - Trusted third party, Prover -
crypto exchange $\mathcal{E}$ and, Verifier - customer $\mathcal{C}$ of the
exchange $\mathcal{E}$, who holds crypto assets with $\mathcal{E}$. In Proof
of Assets protocol, the exchange proves the total bitcoins over which it has
the ownership authority to spend. In the proposed protocol, the exchange
$\mathcal{E}$ proves its total assets in zero-knoweldge and also it preserves
the privacy without revealing its public key addresses and associated
balances. The exchange $\mathcal{E}$ generates a ZK-SNARK proof for an NP-
statement which says $\mathcal{E}$ knows the private keys for a subset of
bitcoin addresses (public keys) and also computes a Pedersen commitment to its
bitcoin assets.

Let $\mathbf{PK}$ be the set of total bitcoin public keys on the blockchain.

$\mathbf{PK}=\left\\{y_{1},y_{2},\dots,y_{k}\right\\}\subseteq\mathbb{E}$ (10)

Let $x_{1}$, $x_{2}$, $\dots$, $x_{k}$ $\in\mathbb{Z}_{p}$ are the set of
private keys corresponding to the public keys from the set $\mathbf{PK}$, such
that $y_{i}=x_{i}G$ for $i=1,2,\dots,k$.

Let $\mathbf{S_{own}}$ be the subset of the public keys for which the exchange
knows the private keys and $\mathbf{S_{own}}\subset\mathbf{PK}$. If
$\mathcal{E}$ provides proofs only for the private keys associated with
addresses in $\mathbf{S_{own}}$, it revals the bitcoin addresses and total
assets owned by $\mathcal{E}$. So, $\mathcal{E}$ takes an anonymity set
$\mathbf{S_{anon}}=\left\\{y_{1},y_{2},\dots,y_{n}\right\\}$ ($n<k$) such that
$\mathbf{S_{anon}}\subset\mathbf{PK}$ and
$\mathbf{S_{anon}}\supset\mathbf{S_{own}}$ to prove the assets owned by
$\mathcal{E}$.

Let $s_{i}\in\left\\{0,1\right\\}$ denotes which public keys the exchange
knows the private key. If $s_{i}=1$, then the exchange knows the private key
$x_{i}$ corresponding to the bitcoin address $y_{i}\in\mathbf{S_{own}}$. Let
$v_{i}$ denotes the amount of bitcoins associated with address
$y_{i}\in\mathbf{S_{anon}}$ and
$\mathbf{V}=\left\\{v_{1},v_{2},\dots,v_{n}\right\\}$, the total assets of the
exchange called $\mathcal{E}_{Assets}$ is defined as

$\mathcal{E}_{Assets}=\sum_{i=1}^{n}s_{i}v_{i}=\sum_{y_{i}\in\mathbf{S_{own}}}v_{i}$
(11)

###  IV-A The NP-statement PoA for Proof of Assets

We construct a Proof of Assets protocol for an exchange to prove the ownership
of the bitcoins it hold. We use ZK-SNARK and Pedersen commitment to prove
exchange’s assets in zero-knowledge. The ownership of the bitcoin is defined
by $s_{i}$, which can be evaluated by checking the equation
$y_{i}\stackrel{{\scriptstyle?}}{{=}}x_{i}G$. To preserve the integity and
privacy of the exchange, $x_{i}$ and $s_{i}$ are used as a part of the witness
in the construction of the ZK-SNARK proof system. The Pedersen commitment
hides $v_{i}$ through the secret $r_{i}$.

Let $F=PoA(z_{i},w_{i})$ be the NP-statement or the non-deterministic decision
function with the public inputs $z_{i}=\left\\{y_{i},v_{i}\right\\}$ and the
witness $w_{i}=\left\\{x_{i},s_{i},r_{i}\right\\}$, then the NP-statement PoA
for proving the exchange’s ownership on $x_{i}$ is defined as

”Either I know the private key $x_{i}$ corresponding to a public key $y_{i}$
in which case $s_{i}=1$ and $c_{i}$ is the commitment to the value $v_{i}$ or
I don’t know the private key $x_{i}$ corresponding to the public key $y_{i}$
in which case $s_{i}=0$ and $c_{i}$ is the commitment to the value $0$.”

The statement PoA is captured by the relation
$\mathcal{R}_{PoA}=\\{(z_{i},w_{i})\in\mathbb{F}_{p}^{l+1}\times\mathbb{F}_{p}^{m-l}\hskip
2.84544pts.t.\hskip 2.84544ptC_{PoA}(z_{i},w_{i})=c_{i}\\}\\}$ and its
corresponding language is $L:=\\{z_{i}\in\mathbb{F}_{p}^{l+1}:\exists
w_{i}\in\mathbb{F}_{p}^{m-l}s.t.(z_{i},w_{i})\in\mathcal{R}_{PoA}\\}$. Where
$C_{PoA}$ is an arithmetic circuit representation of the statement PoA and the
tuple $(z_{i},w_{i})$ represents the values assigned to variables $a_{j}$, for
$j=1,2,\dots,m$ in (6).

In other words, for a given PoA instance $z_{i}$, the witness $w_{i}$ is valid
iff:

  1. 1.

The private key ($x_{i}$) should match the public key ($y_{i}$) or not, i.e.
$s_{i}\in\\{0,1\\}$.

  2. 2.

The commitment $c_{i}$ (output of the circuit $C_{PoA}$) is computed
correctly, i.e., $c_{i}\stackrel{{\scriptstyle?}}{{=}}s_{i}v_{i}G+r_{i}H$.

###  IV-B Arithmentic Circuit $C_{PoA}$ for verifying NP-statement PoA

As shown in Fig. 1, ZK-SNARK is a proof system for arithmetic circuit
satisfiability problem to prove the witness $w_{i}$ for an instance $z_{i}$.
So, we express the checks in the NP-Statement PoA to arithmetic circuit
$C_{PoA}$ as depicted in Fig. 2. There are three subcircuits in $C_{PoA}$ \-
Scalar multiplication circuit $C_{MUL}$, Comparision circuit $C_{CMP}$, and
Pedersen commitment circuit $C_{PED}$. Each individual circuit consists of
arithmetic gates for ${}^{\prime}*^{\prime}$, ${}^{\prime}+^{\prime}$,
${}^{\prime}-^{\prime}$ or ${}^{\prime}/^{\prime}$. As per the R1CS constraint
equation (4), each gate can be represented as a tuple
$(\textbf{a},\textbf{b},\textbf{c},\textbf{t})$ called a constraint.

$x_{i}$ $y_{i}$ $C_{MUL}(x_{i},G)$ $C_{CMP}(y^{\prime}_{i},y_{i})$
$\vspace{-1cm}y_{i}^{{}^{\prime}}=x_{i}.G$ $v_{i}=bal(y_{i})$ $s_{i}*v_{i}$
$s_{i}$ $C_{PED}(b_{i},r_{i})$ $b_{i}$ $r_{i}$ $c_{i}=b_{i}G+r_{i}H$

Figure 2: Circuit $C_{PoA}$ for the NP-statement $PoA$

####  IV-B1 Scalar Multiplication circuit verification:

The circuit $C_{MUL}$ is the scalar multiplication of $x_{i}$ with base point
$G$. It is used to test whether the exchange $\mathcal{E}$ knows the private
key $x_{i}$ matches to the corresponding public key $y_{i}$. The scalar
multiplication is defined as

$y_{i}=x_{i}G=G+G+\dots+G\hskip 5.69046pt(x_{i}\hskip 2.84544pttimes)$ (12)

Where, $x_{i}$ and $x,y$-coordinates of the $G$ are $256$-bit numbers over the
field $\mathbb{F}_{p}$ used for bitcoin addresses. Instead of constructing
$x_{i}$ number of point addition circuits of $G$, we construct $C_{MUL}$ from
$256$ point addition circuits. Initially, scalar $x_{i}$ is unpacked into a
vector $xvec_{i}$ of $256$-bits with $257$ constraints222Each constraint
represnts a single arithmetic gate..

Let $P_{add}$ be a point addition circuit. We construct $P_{add}$ gadget with
$3$ arithmetic gates as per point addition for elliptic curve points defined
in (1). We process $2$-bits (out of 256 bits) of $x_{i}$ at a time to reduce
the number of $P_{add}$ gadgets to half of the total number of bits (i.e to
$128$) by adding an extra constraint (total of $4$ constraints per $P_{add}$)
for the product of the two bits of $x_{i}$.

Algorithm 1 describes the construction of $C_{MUL}$ circuit using $P_{add}$
circuits. In every iteration, we compute the accumulation of constant $G$
(i.e. $a$, $b$, $c$ for $j=0,\dots,numbits$) as the input to $P_{add}$
circuit. In each iteration, the powers $a$, $b$, $c$ are computed from their
previous values. For simplicity, a point (accumulator) on the curve other than
$G$ or $H$ is added to the output of the circuit $C_{MUL}$ and substracted at
the end with additional $P_{add}$ circuit. The summary of the total number of
constraints (or arithmetic gates) required to construct the proof for
$C_{MUL}$ circuit is listed in Table I.

TABLE I: Size of circuit $C_{MUL}$ Gate count for $C_{MUL}$
---
Unpacking $x_{i}$ to $xvec_{i}$ | $257$
Scalar Multiplication ($128$ $P_{add}$ circuits) | $512$
($P_{add}$ (Point addition)) | (4)
Accumulator ($P_{add}$) |  $3$
Total | $772$
Algorithm 1 Scalar Mltiplication circuit $C_{MUL}$

Auxilary input \- $\left\\{x_{i}\right\\}$
Public input \- $\left\\{numbits,G,y_{i}\right\\}$

1:procedure $C_{MUL}$($x_{i}$, $G$, $numbits$, $y_{i}$)

2: Unpack $x_{i}$ into a vector $xvec_{i}$ of length $numbits$

3: while $j<numbits$ do

4: Compute $a=2^{j}.1.G$, $b=2^{j}.2.G$, $c=2^{j}.3.G$

5: if $xvec_{i}[j]==0\&xvec_{i}[j+1]==0$ then

6: $out[k]=P_{add}(out[k-1],0)$

7: else if $xvec_{i}[j]==1\&xvec_{i}[j+1]==0$ then

8: $out[k]=P_{add}(out[k-1],a)$

9: else if $xvec_{i}[j]==0\&xvec_{i}[j+1]==1$ then

10: $out[k]=P_{add}(out[k-1],b)$

11: else

12: $out[k]=P_{add}(out[k-1],c)$

13: end if

14: $j=j+2$, $k=k+1$

15: end while

16: $y_{i}=out\left[\frac{numbits}{2}-1\right]$

17:end procedure

####  IV-B2 Comparison circuit verification:

The comparison function $CMP$ compares the output of the scalar multiplication
$y_{i}^{{}^{\prime}}$ with the input $y_{i}$. The circuit ensures the
comparison of $x$, $y$ coordinates of $y^{\prime}_{i}$ and $y_{i}$ to yield a
binary output $s_{i}$. This is achieved using a single constraint to obtain
the product of $sx$ and $sy$ as $s$, where $sx$ and $sy$ are the outputs for
comparing $x$ and $y$ coordinates of $y^{\prime}_{i}$, $y_{i}$ respectively.
We also add a constriant to $C_{CMP}$ circuit to ensures that
$s_{i}\in\\{0,1\\}$ using the operation $s_{i}*s_{i}=s_{i}$. So, we express
the $C_{CMP}$ circuit using two constriants.

####  IV-B3 Pedersen Commitment circuit Verification:

$C_{PED}$ circuit evaluates the Pedersen commitment of $b_{i}=s_{i}.v_{i}$
with a randomly chosen blinding factor $r_{i}$ which yields an output
$c_{i}=b_{i}G+r_{i}H$. This circuit requires two $C_{MUL}$ circuits, an
arithmetic gate for computing $b_{i}$. Since the total bitcoin supply is
limited to $21$ million coins, the value of $v_{i}$ is bounded by $2^{z}$,
where $z\in[0,51]$. So, the total number of constraints for the first
$C_{MUL}$ circuit, i.e., $b_{i}G$ depends on the maximum value of $z$. Since
the blinding factor $r_{i}\in\mathbb{Z}_{q}$, the second multiplication is
similar to the $C_{MUL}$ circuit discussed in Table I. The summary of the
total number of constraints required to construct a proof for $C_{PED}$
circuit is listed in Table II.

TABLE II: Size of circuit $C_{PED}$ Gate count for $C_{PED}$
---
Arithmetic Gate $\left(b_{i}=s_{i}*v_{i}\right)$ |  $1$
$C_{MUL}$ for $b_{i}G$ | $155$
$C_{MUL}$ for $r_{i}H$ | $769$
Accumulator ($P_{add}$) |  $3$
Total | $928$

Finally, by combining all the circuits, a total of $1702$ constraints are
required to prove circuit $C_{PoA}$ for NP-statement PoA. When $\mathcal{E}$
wants to provide a proof $\pi_{i}$ for $y_{i}\in\mathbf{S_{anon}}$ and
$y_{i}\not\in\mathbf{S_{own}}$, it can directly compute the proof with only
considering the Pedersen commitment circuit $C_{PED}$ by directly taking
$s_{i}=0$ to reduce the number of constriants to $928$.

###  IV-C The Proof of Assets protocol

The proof of Assets protocol shown in Table III for bitcoin exchanges is
constructed based on the ZK-SNARK framework illustrated in Section III. The
proposed protocol satisfies the following properties.

  * •

No probabilistic polynomial time (PPT) adversarial exchange can provide a
commitment to the balance which exceeds the actual amount it owns as the
$v_{i}$ is a public input to the ZK-SNARK proof system.

  * •

No PPT adversarial exchange will be able to provide existence of $v_{i}$ in
$C_{Assets}$ for an address $y_{i}\not\in\mathbf{S_{own}}$.

  * •

No PPT adversary will be able to distinguish the address in the
$\mathbf{S_{anon}}$ belongs to the $\mathbf{S_{own}}$.

TABLE III: Proof of Assets Protocol For $i\in[1,n]$ Public input from
blockchain: $z_{i}=(y_{i},v_{i}$) Exchange’s private input (witness):
$w_{i}=(x_{i},s_{i},r_{i})$ Verifier’s input from Exchange: $c_{i}$,
$C_{Assets}$ 1. Setup phase: The trusted third party generates the CRS
$\sigma$ for the NP-statement PoA. 2. Proving phase: (a) For $i\in[1,n]$ – The
exchange $\mathcal{E}$ constructs the proof $\pi_{i}\leftarrow
Prove(\sigma,z_{i},w_{i})$ (13) – Compute the output from $w_{i}$ and $z_{i}$
$\displaystyle r_{i}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{Z}_{q}$
$c_{i}=s_{i}v_{i}G+r_{i}H$ (14) (b) Compute the commitment to total assets
$C_{Assets}=\left(\sum_{i=1}^{n}b_{i}\right)G+\left(\sum_{i=1}^{n}r_{i}\right)H$
(15) 3. Verification phase: The customer verify the following (a) For
$i\in[1,n]$ $b_{1,i}\in\\{0,1\\}\leftarrow Verify(\sigma,z_{i},c_{i},\pi_{i})$
(16) (b) $b_{2,i}\in\\{0,1\\}\leftarrow Verify(\sigma,C_{Assets},\pi_{i})$
(17) (c) The verifier checks
$C_{Assets}\stackrel{{\scriptstyle?}}{{=}}\sum_{i=0}^{n}c_{i}$ (18)

####  IV-C1 CRS Setup:

A trusted third party construct a ZK-SNARK’s common-reference string $\sigma$
(7) for the NP-statement PoA as per the ZK-SNARK toolchain described in Fig.
1. First, it construct a QAP $Q$ from the circut $C_{PoA}$ for the statement
PoA, then it generates $\sigma=\left([\sigma_{1}]_{1},[\sigma_{2}]_{2}\right)$
using $Q$ and trapdoor information $\alpha$, $\beta$, $\gamma$, $\delta$,
$x\leftarrow\mathbb{Z}_{q}$.

####  IV-C2 Generation of the proof:

The crypto exchange $\mathcal{E}$ (Prover) constructs a proof $\pi_{i}$ to
prove the knowledge of a private key $x_{i}$ corresponding to the public key
$y_{i}$. As per (8), $\mathcal{E}$ needs to provide valid
assignments333Assignments refer to the coeffiecients $a_{i}$’s that satify the
polynomial $P(x)$ in (6). The problem of polynomial satisfiabilty is converted
into proving and verification mechanism shown in (8) and (9).
$\\{a_{ij}\\}_{j=0}^{m}$ to generate $\pi_{i}=(A_{i},B_{i},C_{i})$, for all
$i=[1,n]$. Where, $\\{a_{ij}\\}_{j=0}^{l}$ represents the public input
$z_{i}=(y_{i},v_{i})$ from the blockchain and $\\{a_{ij}\\}_{j=l+1}^{m}$
represents the $\mathcal{E}$’s auxiliary input
$w_{i}=\left\\{x_{i},s_{i},b_{i},r_{i},t_{i}\right\\}$. Where, $t_{i}$ is the
assignments for all the internal wires of the circuit $C_{PoA}$ excluding
$s_{i}$ and $b_{i}$.

The prover also provide output $c_{i}$ to the verifier, which is a Pedersen
commitment to $b_{i}=s_{i}v_{i}$, for all $i=1,\dots,n$. If the exchange knows
the private key $x_{i}$, then $s_{i}=1$ and $c_{i}$ is the commitment to
balance $v_{i}$, other wise it is a commitment to value zero.

$c_{i}=\begin{cases}v_{i}G+r_{i}H,&\text{if }s_{i}=1\\\
r_{i}H,&\text{otherwise}\end{cases}$ (19)

Since the commitments are homomorphically additive, the Pedersen commitment
for the total assets is

$C_{Assets}=\left(\sum_{i=1}^{n}b_{i}\right)G+\left(\sum_{i=1}^{n}r_{i}\right)H=\sum_{i=1}^{n}c_{i}$
(20)

####  IV-C3 Verification of the proof and total assets:

The customer $\mathcal{C}$ (Verifier) of $\mathcal{E}$ verifies the proof
$\pi_{i}$, for $i=1,\dots,n$ along with the proof for $C_{Assets}$.
$\mathcal{C}$ takes the public inputs $z_{i}=(y_{i},v_{i})$ which are the
assignments to $\\{a_{ij}\\}_{j=0}^{l}$ and the proof $\pi=(A,B,C)$ to check
(9). The customer also needs to check commitment to $\mathcal{E}_{Assets}$
using $c_{i}$’s as per (18).

In Proof of Assets protocol, the exchange $\mathcal{E}$ convinces the verifier
that

  * •

If exchange knows the private key $x_{i}$, then $s_{i}=1$ and the
corresponding balance $v_{i}$ added to the commitment $C_{Asset}$.

  * •

The commitment $C_{Assets}$ is the commitment to the total assets
$\sum_{i=1}^{n}s_{i}v_{i}$ of the exchange.

###  IV-D Security and Privacy analysis

In this section, we discuss the security properties of the proposed Proof of
Assets protocol - completeness, sondness and statistical zero-knowledge. We
also discuss the privacy of the exchange.

Consider a proof of assets protocol run between an exchange $\mathcal{E}$ and
a customer $\mathcal{C}$. Let $out_{\mathcal{C}}^{PoA}\in\\{Accept,Reject\\}$
be the output of $\mathcal{C}$ based on the verification checks (a), (b) and
(c) in verification phase of the protocol.

######  Lemma IV.1.

The above construction of the proof of assets protocol satisfies the
completeness, sondness and statistical zero-knwoledge properties.

###### Proof.

The proof for the security properties of the Proof of Assets protocol is
straightforward from the construction of the ZK-SNARK proof system.
Completeness: The customer $\mathcal{C}$ needs to check (16) and (17) based on
the verification step of the ZK-SNARK construction given in (9). If the prover
and verifier use the valid assignments for the coefficients
$\\{a_{ij}\\}_{j=0}^{m}$ in computing (8) and (9), i.e
$(z_{i},w_{i})\in\mathcal{R}_{PoA}$, then the $b_{1,i}=1$ and $b_{2,i}=1$.
Since $b_{2,i}=1$, then (18) also verified. It implies that
$Pr[out_{\mathcal{C}}^{PoA}=Accept]=1.$
Soundness: Suppose an adversial exchange $\mathcal{A_{\mathcal{E}}}$ wants to
prove invalid assignments to the witness $\\{a_{ij}\\}_{j=l+1}^{m}=w_{i}$ for
a given $z_{i}$. For example, if $\mathcal{A_{\mathcal{E}}}$ change the values
of the assignments corresponding to $s_{i}$ or the balance $v_{i}$ on his
favour, then $(z_{i},w_{i})\not\in\mathcal{R}_{PoA}$ or $z_{i}\not\in
L_{PoA}$. The verification test fails in verifying the proof $\pi_{i}$ (i.e.,
$b_{1,i}=b_{2,i}=0$). It implies that $Pr[out_{\mathcal{C}}^{PoA}=Accept]=0.$
Statistical Zero-knowledge: We need to show that there exist a polynomial time
simulator $S$ which generates a proof (without knowing witness $w_{i}$) which
is statistically identical to the real proof generated by $\mathcal{E}$ using
$z_{i}$ and $w_{i}$.

The trapdoor information $\tau$ generated in the setup phase of the ZK-SNARK
construction consists of elements that are drwan uniformly from the field
$\mathbb{F}_{p}$. The field elements $U_{i}$, $V_{i}$ and $X_{wit,i}$ encoded
in the proof $\pi_{i}$ as per (8) are statistically uniform. Where,

$\displaystyle
U_{i}=\sum_{j=0}^{m}a_{ij}u_{j}(x),V_{i}=\sum_{j=0}^{m}a_{ij}v_{j}(x),$
$\displaystyle X_{wit,i}=\sum_{j=l+1}^{m}a_{ij}\left(\beta u_{j}(x)+\alpha
v_{j}(x)+w_{j}(x)\right)$

The prover uses the tuple $(z_{i},w_{i})$ in computing $U_{i}$, $V_{i}$ and
$X_{wit,i}$. So, the field elements $A_{i}$, $B_{i}$ and $C_{i}$ of proof
$\pi_{i}$ are from a uniform distribution.

Consider the simulator $S$ in Table IV for generating the proof $\pi_{i}$. The
simulator picks random $A_{i}$ and $B_{i}$ from uniform distribution and
determine the value of $C_{i}$ from $A_{i}$, $B_{i}$, $\sigma$ and $X_{pub,i}$
which is also distributed uniformly. Where,
$X_{wit,i}=\sum_{j=0}^{l}a_{ij}\left(\beta u_{j}(x)+\alpha
v_{j}(x)+w_{j}(x)\right)$, which is computed from
$z_{i}=\\{a_{ij}\\}_{j=0}^{l}$. So, the simulated proof has also similar
probabilty distribution to the real proof generated by $\mathcal{E}$ using the
witness $w_{i}$. Thus, the Proof of Assets protocol satisfies the statistical
zero-knowledge.

TABLE IV: Simulator for generating proof $\pi_{i}$ 1. Picks $\alpha$, $\beta$,
$\gamma$, $\delta$, $x\leftarrow\mathbb{F^{*}}$, set $\mathbf{\tau}=(\alpha$,
$\beta$, $\gamma$, $\delta$, $x$) 2. Picks random polynomials for $Q$ and
generates the CRS $\sigma=(\sigma_{1},\sigma_{2})$. 3. Pick $A_{i}$, $B_{i}$
$\leftarrow\mathbb{F}$ 4. Determine $C_{i}$ from verification equation (9)
using $A_{i}$, $B_{i}$, $\sigma$ and $\\{a_{ij}\\}_{j=0}^{l}=z_{i}$.

The privacy of $\mathcal{E}$ depends on the value of $s_{i}\in\\{0,1\\}$ as it
captures if $\mathcal{E}$ knows a private key or not. We define an experiment
and we call $AddressPrivacy^{\mathcal{D}}_{y_{i},c_{i}}$. It denotes that for
all $y_{i}\in\mathbf{S_{anon}}$ a distinguisher $\mathcal{D}$ tries
distinguish $y_{i}\in\mathbf{S_{own}}$ or not balance $v_{i}\in z_{i}$ and
output commitment $c_{i}$. The experiment for a single instance $z_{i}\in
L_{PoA}$ is defined as follows:

  1. 1.

The public parameters are generated as $\mathbb{E},p,q,G,H\leftarrow
Gen(1^{\lambda})$, where $\lambda$ is the security parameter.

  2. 2.

$\mathcal{E}$ picks $b_{i}\leftarrow\\{0,1\\}$.

  3. 3.

$\mathcal{E}$ picks $r_{i}\in\mathbb{Z}_{q}$ and computes
$c_{i}=b_{i}v_{i}G+r_{i}H$ and it determine the corresponding ZK-SNARK proof
$\pi_{i}$ for $(z_{i},w_{i})\in\mathcal{R}_{PoA}$.

  4. 4.

Let $z_{i}$, $c_{i}$ and $\pi_{i}$ are inputs to a polynomial time
distinguisher $\mathcal{D}$.

$b^{\prime}_{i}=\mathcal{D}(z_{i},c_{i},\pi_{i})$ (21)

  5. 5.

If $b^{\prime}_{i}=b_{i}$, then $\mathcal{D}$ succeeds. Otherwise it fails.

######  Definition IV.1.

For every $i\in[1,n]$ and $y_{i}\in\mathbf{S_{anon}}$, the proposed proof of
assets protocol provides privacy of bitcoin address $y_{i}$ if for every PPT
distinguisher $\mathcal{D}$ in the
$AddressPrivacy^{\mathcal{D}}_{y_{i},c_{i}}$ experiment with
$Pr[AddressPrivacy^{\mathcal{D}}_{y_{i},c_{i}}=1]=Pr[b^{\prime}_{i}=b_{i}]\leq\frac{1}{2}+negl(\lambda)$.

The PPT distinguisher $\mathcal{D}$ can always toss a coin to guess
$b^{\prime}_{i}\in\\{0,1\\}$ (that gives a probability of $\frac{1}{2}$) or
$\mathcal{D}$ can get a unique $r_{i}\in\mathbb{Z_{q}}$ to guess
$b^{\prime}_{i}$ with negligible probability $\frac{1}{|q|}$ (Where $|q|$ is
polynomial in security parameter $\lambda$). The above definition illustrates
that for every $\mathcal{D}$ with inputs $z_{i}=(y_{i},v_{i})$ should not
determine if the $y_{i}$’s balance $v_{i}$ is included in the $C_{Assets}$
with an advantage not more than negligibly close to $\frac{1}{2}$.

TABLE V: Performance of the single $C_{PoA}$ circuit Proof construction time | 0.2433 sec
---|---
Verififcation time | 0.0042 sec
Proof size |  $192$ bytes
TABLE VI: Performance of Proof of Assets protocol n |  $|\mathbf{S_{own}}|$ ($\%$ $n$) |  Construction time (seconds) |  Verification time (seconds) |  Proof size (MB)
---|---|---|---|---
$100$ |  25 |  $16.96$ |  $0.456$ |  $0.01914$
$100$ |  50 |  $19.55$ |  $0.455$ |  $0.01914$
$100$ |  75 |  $24.76$ |  $0.455$ |  $0.01914$
$1000$ |  25 |  $166.026$ |  $4.528$ |  $0.1914$
$1000$ |  50 |  $191.942$ |  $4.514$ |  $0.1914$
$1000$ |  75 |  $217.934$ |  $4.512$ |  $0.1914$
$10000$ |  25 |  $1657.54$ |  $45.36$ |  $1.914$
$10000$ |  50 |  $1913.79$ |  $45.07$ |  $1.914$
$10000$ |  75 |  $2196.55$ |  $45.09$ |  $1.914$

######  Lemma IV.2.

The proposed proof of assets protocol provides privacy of addresses owned by
$\mathcal{E}$ under the discrete log (DL) [24] assumption.

###### Proof.

Suppose an adversarial exchange $\mathcal{A_{\mathcal{E}}}$ wants to solve a
DL problem. $\mathcal{A_{\mathcal{E}}}$ picks $b_{i}\in\\{0,1\\}$ and
determine $c_{i}=b_{i}v_{i}G+r_{i}G$ (step 2 in
$AddressPrivacy^{\mathcal{D}}_{y_{i},c_{i}}$ experiment). It gives
$(z_{i}=(y_{i},v_{i}),c_{i}and\pi_{i})$ as input to $\mathcal{D}$. Since,
$\mathcal{D}$ is a PPT algorithm, $\mathcal{A_{\mathcal{E}}}$ also a PPT
algorithm.
The generators $G$ and $H$ are chosen uniformly and independetly from
$\mathbb{E}$. We have $G=kH$, for some unknown $k$ ($k$ is not known to
$\mathcal{A_{\mathcal{E}}}$).

$y_{i}=x_{i}G,\hskip 5.69046ptc_{i}=\begin{cases}(kv_{i}+r_{i})H,&\text{if
}b_{i}=1\\\ r_{i}H,&\text{otherwise}\end{cases}$ (22)

If $b^{\prime}_{i}=\mathcal{D}(z_{i},c_{i},\pi_{i})$, then
$\mathcal{A_{\mathcal{E}}}$ outputs $b^{\prime}_{i}$. Suppose $\mathcal{D}$’s
success probability $Pr[b^{\prime}_{i}=b_{i}]>\frac{1}{2}+negl(\lambda)$, then
$\mathcal{A_{\mathcal{E}}}$)’s success probability is also larger than
$\frac{1}{2}+negl(\lambda)$. The PPT adversary can solve the DL problem, this
is a contradiction. Thus, $\mathcal{D}$ has an advantage less than
$\frac{1}{2}+negl(\lambda)$ to reveal the privacy of the exchange.

##  V Implementation and Performance evaluation

We have implemented the Proof of Assets protocol in $C++$ using the libsnark
library [27] developed by scipr-lab. The implementation consists of the
following elements.
Protoboard. A protoboard is a virtual prototype which collect all the circuits
similar to a prototyping board to attch all the circuits and chips in the
electronic circuit board. We need to allocate all the public and auxiliary
inputs used in the ZK-SNARK proof system to the protoboard. Protoboard is
defined as

$\displaystyle protoboard<FieldT>pb;$

Gadgets. The libsnark library provides several gadgets. For example, we use
packing gadget (for unpacking a scalar $x_{i}$ to $xvec_{i}$ as discussed in
section IV-B1) in this work. We construct a PoA_gadget to implement circuit
$C_{PoA}$ for PoA. The PoA_gadget gadget checks the correctsness of the NP-
staement PoA and is defined as

$\displaystyle PoA\\_gadget<FieldT>POA(pb,public\hskip
2.84544ptinputs,witness);$

and generate the R1CSS constraints,

$\displaystyle POA\rightarrow generate\\_r1cs\\_constarints();$

Finally, after giving all the input (public and witness) values by the prover
($\mathcal{E}$) the following function generates the witness to all the
internal wires of the circuit $C_{PoA}$ and outputs Pedersen commitment
$c_{i}$.

$\displaystyle POA\rightarrow generate\\_r1cs\\_witness();$

We divide the implementation of PoA_gadget for PoA into three subcircuits or
gadgets. The scalar multiplication gadget (scalr_mul) verifies the knowledge
of $\mathcal{E}$ on private key $x_{i}$. The comparison gadget (cmp_gadget)
checks the equality of the computed public key ($y^{\prime}_{i}$) from the
given input address ($y_{i}$). Finally, the Pedersen commitment gadget
(Pedersen_gadget) verifies the commitment $c_{i}$ to the balance $v_{i}$. Each
of these gadgets consists for functions for generating $R1CS$ constriants and
generating witness similar to the main gadget. The PoA_gadget generates a
total of $1702$ constraints for each instance
$(z_{i},w_{i})\in\mathcal{R}_{PoA}$.

We performed tests on a personal computer with Intel(R) Core(TM) $i9-9900K$
CPU $@$ $3.60$GHz processor with $16$GB RAM using a single core. The details
of the proof construction time by an exchange $\mathcal{E}$, proof
verification time by the customer $\mathcal{C}$, and the proof size are
described in Table V. The proof construction time depends on the number of the
ZK-SNARK circuit’s constraints. The proof size is the combination of size of
$3$ group elements of each proof $\pi_{i}$ and size of the Pedersen commitment
to $v_{i}$.

Table VI illustrates the performance of the Proof of Assets protocol with the
size of the set $\mathbf{S_{anon}}$ ($n$). We test the protocol for
$n=100,1000$ and, $10000$. We choose $|\mathbf{S_{own}}|$ as $25\%$, $50\%$
and $75\%$ of $n$. We assume $\mathcal{E}$ provides proofs for
$n-|\mathbf{S_{own}}|$ number of addresses by considering $s_{i}=0$ for all
$y_{i}\not\in\mathbf{S}_{own}$ to reduce the proof construction time. The
proof construction time includes the time required for the construction of the
proofs for $n$ number of $C_{PoA}$ and the time required to generate the proof
for the Pedersen commitment $C_{Assets}$ (20). Similarly, for the proof
verification and proof size.

The construction time, verification time, and proof size increases linearly
with $n$. The results show that the Proof of Assets protocol is efficient in
practice as the regular PC constructs the proof in less than an hour and the
proof size is less than $\approx 15$ MB for $n=10000$ with short verification
time. The performance of the protocol will be improved on servers with high-
end processors.

##  VI Conclusions and Future Research

In this paper, we described the ZK-SNARK based proof of assets protocol for
bitcoin exchanges by preserving the privacy of the exchanges without revealing
the public keys or the balances associated with the public keys. This is
achieved by proving the knowledge of the private keys associated with the
public keys (Bitcoin P2PK addresses) using the ZK-SNARK mechanism with
Pedersen commitment as the output of the circuit. We also analyse the security
and privacy properties of the proposed protocol. Through the simulation
results, we showed the efficiency of the protocol for proof construction,
verification and proof size. In the future, we foresee the construction of the
proof of assets protocol for bitcoin P2PKH (Pay to Public Key Hash) addresses
by proving the knowledge of the hash preimage through the ZK-SNARK framework.
We may also combine these proof of assets protocols with proof of liabilities
by proving the membership of customer funds using the set-membership proofs
and ZK-SNARK mechanism.

## References

  * [1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2009. [Online]. Available: http://www.bitcoin.org/bitcoin.pdf
  * [2] CoinMarketCap. [Online]. Available: https://coinmarketcap.com/
  * [3] Ethereum. [Online]. Available: https://ethereum.org/en/
  * [4] Ripple. [Online]. Available: https://ripple.com/
  * [5] Zerocash. [Online]. Available: http://zerocash-project.org/
  * [6] Stellar. [Online]. Available: https://www.stellar.org/
  * [7] Monero. [Online]. Available: https://www.getmonero.org/
  * [8] Coinbase. [Online]. Available: https://www.coinbase.com/
  * [9] Binance. [Online]. Available: https://www.binance.com/en
  * [10] M. Gox. [Online]. Available: https://en.wikipedia.org/wiki/$Mt._$Gox
  * [11] FRR. [Online]. Available: https://www.investopedia.com/terms/r/reserveratio.asp
  * [12] B. Parno, J. Howell, C. Gentry, and M. Raykova, “Pinocchio: Nearly practical verifiable computation,” in _2013 IEEE Symposium on Security and Privacy_ , 2013, pp. 238–252.
  * [13] J. Groth, “On the size of pairing-based non-interactive arguments,” in _Advances in Cryptology – EUROCRYPT 2016_ , M. Fischlin and J.-S. Coron, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016, pp. 305–326.
  * [14] E. Ben Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza, “Zerocash: Decentralized anonymous payments from bitcoin,” in _2014 IEEE Symposium on Security and Privacy_ , 2014, pp. 459–474.
  * [15] bit2me, “P2pk.” [Online]. Available: https://academy.bit2me.com/en/what-is-a-p2pk/
  * [16] T. P. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” in _Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology_ , ser. CRYPTO ’91. Berlin, Heidelberg: Springer-Verlag, 1991, p. 129–140.
  * [17] “Proving-bitcoin-reserves.” [Online]. Available: https://web.archive.org/web/20170114112433/https://iwilcox.me.uk/2014/proving-bitcoin-reserves.
  * [18] G. G. Dagher, B. Bünz, J. Bonneau, J. Clark, and D. Boneh, “Provisions: Privacy-preserving proofs of solvency for bitcoin exchanges,” in _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 720–731. [Online]. Available: https://doi.org/10.1145/2810103.2813674
  * [19] U. Feige and A. Shamir, “Witness indistinguishable and witness hiding protocols,” in _Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing_ , ser. STOC ’90. New York, NY, USA: Association for Computing Machinery, 1990, p. 416–426. [Online]. Available: https://doi.org/10.1145/100216.100272
  * [20] C. P. Schnorr, “Efficient signature generation by smart cards,” _J. Cryptol._ , vol. 4, no. 3, p. 161–174, Jan. 1991. [Online]. Available: https://doi.org/10.1007/BF00196725
  * [21] Blocksream, “Standardizing bitcoin proof of reserves.” [Online]. Available: https://blockstream.com/2019/02/04/en-standardizing-bitcoin-proof-of-reserves.
  * [22] D. Hankerson, A. J. Menezes, and S. Vanstone, _Guide to Elliptic Curve Cryptography_ , 1st ed. Springer Publishing Company, Incorporated, 2010.
  * [23] ——, _Guide to Elliptic Curve Cryptography_. Berlin, Heidelberg: Springer-Verlag, 2003, ch. 3, pp. 96–106.
  * [24] S. D. Galbraith and P. Gaudry, “Recent progress on the elliptic curve discrete logarithm problem,” Cryptology ePrint Archive, Report 2015/1022, 2015, https://ia.cr/2015/1022.
  * [25] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, “Quadratic span programs and succinct nizks without pcps,” Cryptology ePrint Archive, Report 2012/215, 2012, https://eprint.iacr.org/2012/215.
  * [26] B. Vitalik. [Online]. Available: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649.
  * [27] scipr lab, “Libsnark.” [Online]. Available: https://github.com/scipr-lab/libsnark.


# New Quantitative Deformation Lemma and New Mountain Pass Theorem

Liang Ding1, 3, Fode Zhang2, and Shiqing Zhang1,
1Department of Mathematics and Yangtze Center of Mathematics,
Sichuan University
Chengdu 610064, People’s Republic of China
2Department of Mathematics
Kunming University of Science and Technology
Yunnan 650093, People’s Republic of China
3Department of Basis Education
Dehong Vocational College
Mangshi, Yunnan, 678400
People’s Republic of China
Email: lovemathlovemath@126.com(Liang Ding), Email: lnsz-zfd@163.com(Fode
Zhang)Corresponding author’s email: zhangshiqing@scu.edu.cn(Shiqing Zhang),

Abstract In this paper, we obtain a new quantitative deformation Lemma so that
we can obtain more critical points, especially for supinf critical value
$c_{1}$, $x=\varphi^{-1}(c_{1})$ is a new critical point. For $infmax$
critical value $c_{2}$, we can obtain two new critical points $x=0$ (valley
point) and $x=e$(peak point) ,comparing with Willem’s variant of the mountain
pass theorem of Ambrosetti-Rabinowitz,in which
$\varphi(e)\leq\varphi(0)<c_{2}$, but in our new mountain pass theorem,
$\varphi(e)=c_{2}$.
Key words Critical Points; Quantitative Deformation Lemma; Mountain Pass Lemma
2010 MR Subject Classification 47H10, 47J30, 39A10.

##  1 Introduction

In 1973, Ambrosetti and Rabinowitz [1] presented the famous Mountain Pass
Theorem. Later, there were many variants and generalizations([2]-[14]).
Specially, Willem [11] gave the Quantitative Deformation Lemma and the
corresponding mountain pass theorem. It is well known that quantitative
deformation lemma is a very powerful tool to obtain mountain pass theorem, and
the mountain pass theorem has proved to be a power tool in many areas of
analysis. But to our best knowledge, very few works have been done for
quantitative deformation lemma or mountain pass theorem in the past thirty
years.

In this paper, we extend the quantitative deformation lemma in [11] so that we
can obtain more critical points, especially for supinf critical value $c_{1}$,
$x=\varphi^{-1}(c_{1})$ is a new critical point. Moreover,as an application of
our deformation lemma,a new mountain pass theorem is given. Comparing with the
mountain pass type theorem in [11], $\varphi(e)\leq\varphi(0)<c_{2}$, but in
our new mountain pass theorem, $\varphi(e)=c_{2}$, so that our new mountain
pass theorem can not be obtained by the quantitative deformation lemma in
[11];besides, in our theorem, if $\varphi$ satisfies $(PS)_{c_{2}}$ condition,
we can obtain two new critical points $x=0$ (valley point) and $x=e$ (peak
point).

The organization of this paper is as following. In section $2$, the
quantitative deformation lemma in [11] and the corresponding mountain pass
theorem in [11] are given. In section $3$, on the basis of the quantitative
deformation lemma in [11], we prove the new quantitative deformation lemma. In
section $4$, as an application of our deformation lemma, our new mountain pass
theorem is given.

##  2 Preliminaries

For convenience, we introduce the Quantitative Deformation Lemma in [11] and
the corresponding Mountain Pass Type Theorem in [11] as the following:

######  Lemma 2.1.

(Quantitative deformation lemma) Let $X$ be a Hilbert space, $\varphi\in
C^{2}(X,\mathbb{R})$, $c\in\mathbb{R}$, $\varepsilon>0$. Assume that

$\big{(}\forall
u\in\varphi^{-1}([c-2\varepsilon,c+2\varepsilon])\big{)}:\|\varphi^{\prime}(u)\|\geq
2\varepsilon.$

Then there exists $\eta\in$ $C(X,X)$, such that

  * $(a)$

$\eta(u)=u$, $\forall
u\notin\varphi^{-1}\big{(}[c-2\varepsilon,c+2\varepsilon]\big{)}$.

  * $(b)$

$\eta(\varphi^{c+\varepsilon})\subset\varphi^{c-\varepsilon}$, where
$\varphi^{c-\varepsilon}:=\varphi^{-1}\big{(}(-\infty,c-\varepsilon]\big{)}$.

######  Theorem 2.1.

(Mountain pass type theorem) Let $X$ be a Hilbert space, $\varphi\in
C^{2}(X,\mathbb{R})$, $e\in X$ and $r>0$ be such that $\|e\|>r$ and

$\displaystyle b:=\inf_{\|u\|=r}\varphi(u)>\varphi(0)\geq\varphi(e).$ (2.1)

Then, for each $\varepsilon>0$, there exists $u\in X$ such that

  * $(i)$

$c-2\varepsilon\leq\varphi(u)\leq c+2\varepsilon$,

  * $(ii)$

$\|\varphi^{\prime}(u)\|<2\varepsilon$,

where

$c:=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)}$

and

$\Gamma:=\\{\gamma\in C\big{(}[0,1],X\big{)}:\gamma(0)=0,\gamma(1)=e\\}.$

######  Definition 2.1.

([14])Let $X$ be a Banach space, $\varphi\in C^{1}(X,\mathbb{R})$ and
$c\in\mathbb{R}$. The function $\varphi$ satisfies the $(PS)_{c}$ condition if
any sequence $(u_{n})\subset X$ such that

$\varphi(u_{n})\rightarrow c,\varphi^{\prime}(u_{n})\rightarrow 0$

has a convergent subsequence.

##  3 New Quantitative Deformation Lemma

######  Theorem 3.1.

Let $X$ be a Hilbert space, $\varphi\in C^{2}(X,\mathbb{R})$,
$c\in\mathbb{R}$, $\varepsilon>0$. Assume that

$\displaystyle\big{(}\forall
u\in\varphi^{-1}([c-2\varepsilon,c+2\varepsilon])\big{)}:\|\varphi^{\prime}(u)\|\geq
2\varepsilon.$

Then there exists $\eta\in$ $C(X,X)$, such that

  * $(a\,^{\prime})$

$\eta(u)=u$, $\forall
u\notin\varphi^{-1}\big{(}[c-2\varepsilon,c+2\varepsilon]\big{)}\backslash D$,
where $D\subseteq\varphi^{-1}\big{(}[c-0.5\varepsilon,c+\varepsilon]\big{)}$.

  * $(b\,^{\prime})$

$\eta\big{(}\varphi^{-1}[c-\varepsilon,c-0.6\varepsilon]\big{)}\subset\varphi_{*}^{c+\varepsilon}$,
where $\varphi_{*}^{c+\varepsilon}$ denotes
$\varphi^{-1}\big{(}[c+\varepsilon,+\infty)\big{)}$.

  * $(c\,^{\prime})$

$\eta\big{(}\varphi^{-1}[c+0.6\varepsilon,c+\varepsilon]\big{)}\subset\varphi^{c-\varepsilon}$,
where $\varphi^{c-\varepsilon}$ denotes
$\varphi^{-1}\big{(}(-\infty,c-\varepsilon]\big{)}$.

###### Proof.

Let us define

$\displaystyle A$
$\displaystyle:=\varphi^{-1}\big{(}[c-2\varepsilon,c+2\varepsilon]\big{)}\backslash
D,$ $\displaystyle B$
$\displaystyle:=\varphi^{-1}\big{(}[c-\varepsilon,c-0.6\varepsilon]\big{)},$
$\displaystyle C$
$\displaystyle:=\varphi^{-1}\big{(}[c+0.6\varepsilon,c+\varepsilon]\big{)},$
$\displaystyle\psi(u)$
$\displaystyle:=\frac{[dist(u,C)-dist(u,B)]dist(u,X\backslash
A)}{[dist(u,C)+dist(u,B)]dist(u,X\backslash A)+dist(u,B)dist(u,C)},$

so that $\psi$ is locally Lipschitz continuous, $\psi=1$ on $B$, $\psi=-1$ on
$C$ and $\psi=0$ on $X\backslash$ $A$.
Let us also define the locally Lipschitz continuous vector field

$\displaystyle f(u)$ $\displaystyle:=$
$\displaystyle\psi(u)\|\nabla\varphi(u)\|^{-2}\nabla\varphi(u),\quad\ \ u\in
A,$ $\displaystyle:=$ $\displaystyle 0,\quad\ \ u\in X\backslash A.$

It is clear that $\|f(u)\|\leq(2\varepsilon)^{-1}$ on $X$. For each $u\in$
$X$, the Cauchy problem

$\displaystyle\frac{d}{dt}\sigma(t,u)$ $\displaystyle=$ $\displaystyle
f\big{(}\sigma(t,u)\big{)},$ $\displaystyle\sigma(0,u)$ $\displaystyle=$
$\displaystyle u,$

has a unique solution $\sigma(\cdot,u)$ defined on $\mathbb{R}$. Moreover,
$\sigma$ is continuous on $\mathbb{R}\times X$(see e.g. [15]). The map $\eta$
defined on $X$ by $\eta(u):=\sigma(2\varepsilon,u)$ satisfies
$(a\,^{\prime})$. Since

$\displaystyle\frac{d}{dt}\varphi\big{(}\sigma(t,u)\big{)}$ $\displaystyle=$
$\displaystyle\bigg{(}\nabla\varphi\big{(}\sigma(t,u)\big{)},\frac{d}{dt}\sigma(t,u)\bigg{)}$
(3.1) $\displaystyle=$
$\displaystyle\bigg{(}\nabla\varphi\big{(}\sigma(t,u)\big{)},f\big{(}\sigma(t,u)\big{)}\bigg{)}$
$\displaystyle=$ $\displaystyle\psi\big{(}\sigma(t,u)\big{)},$

If

$\displaystyle\sigma(t,u)\in\varphi^{-1}\big{(}[c-\varepsilon,c-0.6\varepsilon]\big{)}=B,\quad\
\ \forall t\in[0,2\varepsilon],$

then

$\psi(\sigma(t,u))=1.$

So, we obtain from (3.1),

$\displaystyle\varphi\big{(}\sigma(2\varepsilon,u)\big{)}$ $\displaystyle=$
$\displaystyle\varphi(u)+\int_{0}^{2\varepsilon}\frac{d}{dt}\varphi\big{(}\sigma(t,u)\big{)}dt$
$\displaystyle=$
$\displaystyle\varphi(u)+\int_{0}^{2\varepsilon}\psi\big{(}\sigma(t,u)\big{)}dt$
$\displaystyle\geq$ $\displaystyle c-\varepsilon+2\varepsilon=c+\varepsilon,$

and $(b\,^{\prime})$ is also satisfied.
Finally, similar to prove $(b\,^{\prime})$, we prove $(c\,^{\prime})$.
If

$\displaystyle\sigma(t,u)\in\varphi^{-1}\big{(}[c+0.6\varepsilon,c+\varepsilon]\big{)}=C,\quad\
\ \forall t\in[0,2\varepsilon],$

then

$\psi(\sigma(t,u))=-1.$

So, we obtain from (3.1),

$\displaystyle\varphi\big{(}\sigma(2\varepsilon,u)\big{)}$ $\displaystyle=$
$\displaystyle\varphi(u)+\int_{0}^{2\varepsilon}\frac{d}{dt}\varphi\big{(}\sigma(t,u)\big{)}dt$
$\displaystyle=$
$\displaystyle\varphi(u)+\int_{0}^{2\varepsilon}\psi\big{(}\sigma(t,u)\big{)}dt$
$\displaystyle\leq$ $\displaystyle c+\varepsilon-2\varepsilon=c-\varepsilon,$

and $(c\,^{\prime})$ is also satisfied.

######  Remark 3.1.

By Theorem 3.1, we get more critical points than the Quantitative Deformation
Lemma in [11]. All the domain $D$ in Theorem 3.1, especially for $supinf$
critical value $c$, $x=\varphi^{-1}(c)$ are all new critical points.

######  Remark 3.2.

In Lemma $2.1$, there are two conclusions, but in Theorem 3.1, there are three
conclusions.

##  4 An Example (New Mountain Pass Theorem)

Let $X$ be a Hilbert space, $\varphi\in C^{2}(X,\mathbb{R})$, $e\in X$ and
$r>0$ be such that $\|e\|>r$ and

$\varphi(0)=c_{1},\quad\ \ \varphi(e)=c_{2},\quad\ \ c_{1}\neq c_{2},$

and

$c_{1}:=\sup_{\gamma\in\Gamma}\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},\,\,\,\,c_{2}:=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},$

where

$\Gamma:=\\{\gamma\in
C\big{(}[0,1],X\big{)}:\gamma(\frac{1}{4})=0,\gamma(\frac{1}{2})=e\\}.$

Then, for each $\varepsilon>0$, there exists $u^{\ast}\in X$ and
$u^{\triangle}\in X$ such that

  * $(\mathrm{I})$

$c_{1}-2\varepsilon\leq\varphi(u^{\ast})\leq c_{1}+2\varepsilon$,

  * $(\mathrm{II})$

$\|\varphi^{\prime}(u^{\ast})\|<2\varepsilon$.

  * $(\mathrm{III})$

$c_{2}-2\varepsilon\leq\varphi(u^{\triangle})\leq c_{2}+2\varepsilon$,

  * $(\mathrm{IV})$

$\|\varphi^{\prime}(u^{\triangle})\|<2\varepsilon$.

###### Proof.

Obviously, for each $\varepsilon>0$, (I) and (III) are easy to get. Next, we
prove (II) and (IV).
Suppose that at least one of (II) and (IV) is not true. Then, we can get the
contradiction:

Case 1. We assume that (II) is not true. It means that there exists
$\varepsilon$ such that

$\|\varphi^{\prime}(u^{\ast})\|\geq 2\varepsilon.$

From

$c_{1}:=\sup_{\gamma\in\Gamma}\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},\,\,\,\,c_{2}:=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},$

and $c_{1}\neq c_{2}$, we get $c_{1}<c_{2}$ or $c_{1}>c_{2}$. Then, Case 1 can
be divided into two parts.

Firstly, when $c_{1}<c_{2}$, let
$\varepsilon_{1}=\min\\{\frac{c_{2}-c_{1}}{4},\,\varepsilon\\}$. It is clear
that

$\|\varphi^{\prime}(u^{\ast})\|\geq 2\varepsilon_{1}.$

and for $\varepsilon_{1}$, (I) is still easy to get.

From $\varepsilon_{1}=\min\\{\frac{c_{2}-c_{1}}{4},\,\varepsilon\\}$, we
obtain

$c_{1}+2\varepsilon_{1}\leq
c_{1}+2\times\frac{c_{2}-c_{1}}{4}=c_{1}+\frac{c_{2}-c_{1}}{2}=\frac{c_{2}}{2}+\frac{c_{1}}{2}<c_{2}.$

It means that

$c_{2}>c_{1}+2\varepsilon_{1}.$

In Theorem 3.1, we can take $D=\\{u\in X\mid\varphi(u)=c_{1}\\}$. Consider
$\beta=\eta\circ\gamma$, where $\eta$ is given by Theorem 3.1. Using
$(a\,^{\prime})$, we have,

$\displaystyle\beta(\frac{1}{4})$ $\displaystyle=$
$\displaystyle\eta\big{(}\gamma(\frac{1}{4})\big{)}=\eta(0)=0.$
$\displaystyle\beta(\frac{1}{2})$ $\displaystyle=$
$\displaystyle\eta\big{(}\gamma(\frac{1}{2})\big{)}=\eta(e)=e,$

so that $\beta\in\Gamma$. From

$c_{1}:=\sup_{\gamma\in\Gamma}\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},$

there exist $\gamma\in\Gamma$ and $\varepsilon_{2}>0$ such that

$c_{1}-\varepsilon_{2}\leq\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)}\leq
c_{1}-0.6\varepsilon_{2}.$

Then, from $(b\,^{\prime})$, we have

$\min_{t\in[0,1]}\varphi\bigg{(}\eta\big{(}\gamma(t)\big{)}\bigg{)}\geq
c_{1}+\varepsilon_{2}.$

It means that

$\min_{t\in[0,1]}\varphi\big{(}\beta(t)\big{)}\geq c_{1}+\varepsilon_{2}.$

So

$c_{1}+\varepsilon_{2}\leq\min_{t\in[0,1]}\varphi\big{(}\beta(t)\big{)}\leq
c_{1}.$

This is a contradiction. Therefore, (II) is true.

Secondly, when $c_{1}>c_{2}$, let
$\varepsilon_{1}=\min\\{\frac{c_{1}-c_{2}}{4},\,\varepsilon\\}$. It is clear
that

$\|\varphi^{\prime}(u^{\ast})\|\geq 2\varepsilon_{1},$

and for $\varepsilon_{1}$, (I) is still easy to get.

From $\varepsilon_{1}=\min\\{\frac{c_{1}-c_{2}}{4},\,\varepsilon\\}$, we
obtain

$c_{1}-2\varepsilon_{1}\geq
c_{1}-2\times\frac{c_{1}-c_{2}}{4}=\frac{c_{1}}{2}+\frac{c_{2}}{2}>c_{2}.$

It means that

$c_{2}<c_{1}-2\varepsilon_{1}.$

In Theorem 3.1, we can take $D=\\{u\in X\mid\varphi(u)=c_{1}\\}$. Consider
$\beta=\eta\circ\gamma$, where $\eta$ is given by Theorem 3.1. Using
$(a\,^{\prime})$, we have,

$\displaystyle\beta(\frac{1}{4})$ $\displaystyle=$
$\displaystyle\eta\big{(}\gamma(\frac{1}{4})\big{)}=\eta(0)=0.$
$\displaystyle\beta(\frac{1}{2})$ $\displaystyle=$
$\displaystyle\eta\big{(}\gamma(\frac{1}{2})\big{)}=\eta(e)=e,$

so that $\beta\in\Gamma$. From

$c_{1}:=\sup_{\gamma\in\Gamma}\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},$

there exist $\gamma\in\Gamma$ and $\varepsilon_{2}>0$ such that

$c_{1}-\varepsilon_{2}\leq\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)}\leq
c_{1}-0.6\varepsilon_{2}.$

Then, from $(b\,^{\prime})$, we have

$\min_{t\in[0,1]}\varphi\bigg{(}\eta\big{(}\gamma(t)\big{)}\bigg{)}\geq
c_{1}+\varepsilon_{2}.$

It means that

$\min_{t\in[0,1]}\varphi\big{(}\beta(t)\big{)}\geq c_{1}+\varepsilon_{2}.$

So

$c_{1}+\varepsilon_{2}\leq\min_{t\in[0,1]}\varphi\big{(}\beta(t)\big{)}\leq
c_{1}.$

This is a contradiction. Therefore, (II) is true.

Case 2. We assume that (IV) is not true. It means that there exists
$\varepsilon$ such that

$\|\varphi^{\prime}(u^{\triangle})\|\geq 2\varepsilon.$

From

$c_{1}:=\sup_{\gamma\in\Gamma}\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},\,\,\,\,c_{2}:=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},$

and $c_{1}\neq c_{2}$ we get $c_{1}<c_{2}$ or $c_{1}>c_{2}$. Then, Case 2 can
be divided into two parts.

Firstly, when $c_{1}<c_{2}$, let
$\varepsilon_{1}=\min\\{\frac{c_{2}-c_{1}}{4},\,\varepsilon\\}$. It is clear
that

$\|\varphi^{\prime}(u^{\triangle})\|\geq 2\varepsilon_{1}.$

and for $\varepsilon_{1}$, (III) is still easy to get.

From $\varepsilon_{1}=\min\\{\frac{c_{2}-c_{1}}{4},\,\varepsilon\\}$, we
obtain

$c_{2}-2\varepsilon_{1}\geq
c_{2}-2\times\frac{c_{2}-c_{1}}{4}=c_{2}-\frac{c_{2}-c_{1}}{2}=\frac{c_{2}}{2}+\frac{c_{1}}{2}>c_{1}.$

It means that

$c_{1}<c_{2}-2\varepsilon_{1}.$

In Theorem 3.1, we can take $D=\\{u\in X\mid\varphi(u)=c_{2}\\}$. Consider
$\beta=\eta\circ\gamma$, where $\eta$ is given by Theorem 3.1. Using
$(a\,^{\prime})$, we have,

$\displaystyle\beta(\frac{1}{4})$ $\displaystyle=$
$\displaystyle\eta\big{(}\gamma(\frac{1}{4})\big{)}=\eta(0)=0.$
$\displaystyle\beta(\frac{1}{2})$ $\displaystyle=$
$\displaystyle\eta\big{(}\gamma(\frac{1}{2})\big{)}=\eta(e)=e,$

so that $\beta\in\Gamma$. From

$c_{2}:=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},$

there exist $\gamma\in\Gamma$ and $\varepsilon_{3}>0$ such that

$c_{2}+0.6\varepsilon_{3}\leq\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)}\leq
c_{2}+\varepsilon_{3}.$

Then, from $(c_{1}\,^{\prime})$, we have

$\max_{t\in[0,1]}\varphi\bigg{(}\eta\big{(}\gamma(t)\big{)}\bigg{)}\leq
c_{2}-\varepsilon_{3}.$

It means that

$\max_{t\in[0,1]}\varphi\big{(}\beta(t)\big{)}\leq c_{2}-\varepsilon_{3}.$

So

$c_{2}\leq\max_{t\in[0,1]}\varphi\big{(}\beta(t)\big{)}\leq
c_{2}-\varepsilon_{3}.$

This is a contradiction. Therefore, (IV) is true.

Secondly, when $c_{2}<c_{1}$, let
$\varepsilon_{1}=\min\\{\frac{c_{1}-c_{2}}{4},\,\varepsilon\\}$ and take
$D=\\{u\in X\mid\varphi(u)=c_{2}\\}$, the rest of the proof is similar to the
first part of Case 2. Therefore, (IV) is true.

From Case 1 and Case 2, our new mountain pass theorem is proved.

######  Remark 4.1.

In Theorem 2.1 (Mountain pass theorem), $c$ is defined as

$c:=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)}$

where

$\Gamma:=\\{\gamma\in C\big{(}[0,1],X\big{)}:\gamma(0)=0,\gamma(1)=e\\}.$

But in our new mountain pass theorem, $c_{1}$ and $c_{2}$ are defined as

$c_{1}:=\sup_{\gamma\in\Gamma}\min_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},\quad\
\
c_{2}:=\inf_{\gamma\in\Gamma}\max_{t\in[0,1]}\varphi\big{(}\gamma(t)\big{)},$

where

$\Gamma:=\\{\gamma\in
C\big{(}[0,1],X\big{)}:\gamma(\frac{1}{4})=0,\gamma(\frac{1}{2})=e\\}.$

######  Remark 4.2.

In fact, in Theorem 2.1 (Mountain pass theorem),

$c_{2}>\varphi(0)\geq\varphi(e).$

But in our new mountain pass theorem,

$\varphi(0)=c_{1},\quad\ \ \varphi(e)=c_{2},\quad\ \ c_{1}\neq c_{2}.$

and in the proof of our new mountain pass theorem, we take $D=\\{u\in
X\mid\varphi(u)=c_{1}\\}$ in Case 1, and take $D=\\{u\in
X\mid\varphi(u)=c_{2}\\}$ in Case 2.

######  Remark 4.3.

In the example, if we do not use our Theorem 3.1 (New quantitative deformation
lemma), we can not obtain

$\beta(\frac{1}{4})=\eta\big{(}\gamma(\frac{1}{4})\big{)}=\eta(0)=0.$

Moreover, we can not obtain $\beta\in\Gamma$.

######  Remark 4.4.

An interesting point in the example is that, if $\varphi$ satisfies $(PS)_{c}$
condition, it is easy to obtain two new critical points $x=0$ and $x=e$ which
have not been obtained before.

## References

  * [1] A. Ambrosetti and P.H. Rabinowitz, Dual variational methods in critical point theory and applications, J. Funct. Anal. 14 (1973), 349-381.
  * [2] G. Barletta and S.A. Marano, Some remarks on critical point theory for locally Lipschitz functions, Glasgow Math. J. 45 (2003), 131-141.
  * [3] H. Brezis, J.M. Coron and L. Nirenberg, Free vibrations for a nonlinear wave equation and theorem of P. Rabinowitz, Comm. Pure Appl. Math, 33 (1980), 667-684.
  * [4] K.C.,Chang, Infinite dimensional Morse theory,Birkhäuser, 1993.
  * [5] N. Ghoussoub, Duality and Perturbation Methods in Critical Point Theory, Cambridge Tracts in Math. 107, Cambridge Univ. Press, Cambridge, 1993.
  * [6] H. Hofer, A geometric description of the neighbourhood of a critical point given by the Mountain Pass Theorem, J. London Math. Soc. 31 (1985), 566-570.
  * [7] I. Peral, Beyond the mountain pass: some applications. Adv. Nonlinear Stud. 12 (2012), no. 4, 819-850
  * [8] P. Pucci and J. Serrin, A Mountain Pass Theorem, J. Differential Equations 60 (1985), 142-149.
  * [9] P. Pucci and J. Serrin, Extensions of the Mountain Pass Theorem, J. Funct. Anal. 59 (1984), 185-210.
  * [10] P. Pucci, J. Serrin, The structure of the critical set in the mountain pass theorem, Trans. Amer. Math. Soc. 299, (1987), no. 1, 115-132.“
  * [11] M. Willem, Minimax Theorems, Birkhäuser,Boston, 1996.
  * [12] R. Livrea and S.A. Marano, Existence and classification of critical points for nondifferentiable functions, Adv. Differential Equations 9 (2004), 961-978.
  * [13] S.A. Marano and D. Motreanu, A deformation theorem and some critical points results for non- differentiable functions, Topol. Methods Nonlinear Anal. 22 (2003), 139-158.
  * [14] P.H. Rabinowitz, Minimax Methods in Critical Point Theory with Applications to Differential Equations, CBMS Reg. Conf. Ser. Math. 65, Amer. Math. Soc., Providence, RI, 1986\.
  * [15] Schwartz L., Cours $d^{,}$analyse, Hermann, Paris, 1991-1994.