PreprintPDF Available

Trustless, privacy-preserving blockchain bridges

Authors:
Preprints and early-stage research may not have been peer reviewed yet.

Abstract

In this paper, we present a protocol for facilitating trust-less cross-chain cryptocurrency transfers that preserve privacy of bridge withdrawals. We leverage zero-knowledge primitives that are commonly used to design cryptocurrency mixing protocols to provide similar functionality but across two or more blockchains. To that end, we receive cryptocurrency mixing for free through the bridge operations and de-scribe how to extend these protocols to incentivise bridge transfers using past ideas. We describe how resulting protocols lead to similar vampire style attacks coined in the Uniswap vs. Sushiswap saga but across chains.
arXiv:2102.04660v1 [cs.CR] 9 Feb 2021
Trustless, privacy-preserving blockchain bridges
Drew Stone
drew@webb.tools
Abstract. In this paper, we present a protocol for facilitating trust-
less cross-chain cryptocurrency transfers that preserve privacy of bridge
withdrawals. We leverage zero-knowledge primitives that are commonly
used to design cryptocurrency mixing protocols to provide similar func-
tionality but across two or more blockchains. To that end, we receive
cryptocurrency mixing ”for free” through the bridge operations and de-
scribe how to extend these protocols to incentivise bridge transfers using
ideas from [9]. We describe how resulting protocols lead to similar vam-
pire attacks coined in the Uniswap vs. Sushiswap saga but across chains
and discuss incentivisation mechanisms.
1 Introduction
Cross-chain bridges are popular mechanisms for transferring native cryptocur-
rency assets to new blockchains. Oftentimes, bridges serve to bring new liquidity
in the form of new cryptocurrency assets to a new or existing blockchain protocol.
Other attractions for using cross-chain bridges are to utilise certain cryptocur-
rencies with more expressive scripting engines, such as utilising bridged Bitcoin
[10] assets on Ethereum [14] in various smart contracts. The range of applica-
tions utilising bridged assets ranges from simple exchange between new currency
pairs to various liquidity mining schemes and more.
The mechanisms for building bridges exist in both centralized (custodial ) and
decentralized (non-custodial) forms. Custodial systems however are objectively
worse in theory albeit simpler to implement in practice because a user entrusts
their cryptocurrency with another, potentially malicious, entity. For that pur-
pose, it is ever more crucial to build secure and robust, decentralized blockchain
bridges to transfer cryptocurrencies across ledgers.
The main ingredient for building decentralized blockchain bridges is a light-
client, a system that verifies proofs of work of other blockchains. If both blockchains
being bridged can support the existence of a light-clients for each respective
chain, then a bridge can be built to transfer cryptocurrencies between them.
1
2
1.1 Coin Mixers
Cryptocurrency mixers have been popular since the creation of Bitcoin [10].
A cryptocurrency mixer is a system that allows holders of cryptocurrency to
anonymize their cryptocurrency holdings by depositing fixed sized amounts and
withdrawing fixed sized amounts to new addresses such that linking these actions
is considered hard. The goal of a cryptocurrency mixer is to anonymize any link
between deposits (inputs) and withdrawals (outputs),
A mixer is only as good as its anonymity set, defined as the set of potential
deposits a withdrawal could link to. It is crucial to grow the anonymity set in
practice to achieve large levels of privacy.
1.2 DeFi
The rise of decentralized finance gives us interesting mechanisms for bootstrap-
ping large anonymity sets. DeFi ”farming” schemes present new ways for in-
centivising users to participate in new cryptocurrency protocols by giving early
users governance tokens that offers voting rights and/or direct cash-flows within
the protocol. We cast the design of private bridge protocols in a similar light, dis-
tributing a useless tokens to participants of the bridge based on certain criteria
such as the time one remains locked in one side of the bridge.
1.3 Our Contributions
In this paper, we combine these three concepts, light clients,mixers, and DeFi
incentivisation techniques to build a trustless and private cryptocurrency bridge.
We outline our protocol in the form of a smart contract that manages the state
and functionality necessary for both a light client and a bridge. We achieve
private bridge transfers by utilising succinct zero-knowledge proofs to verify
the validity of withdrawals and prevent double-spending. While we utilise light
clients within our system, we defer formalisation of light client work to previous
research and focus primarily on the bridge mechanism.
1.4 Related Work
Light clients are well studied mechanisms for making blockchains interoperable.
One main crtieria for designing light clients is ensuring they are trustless, through
the ability to verify proofs of work and consensus of other blockchains. Light
clients are required to store data, in the form of block headers, of these other
blockchains. Over time, the storage costs of these headers because non-negligable
and so more thoughtful designs are necessary. Proposals such as NiPoPoWs [8],
FlyClients [2], and Plumo [5] present ways of optimising light-client designs
3
using zero-knowledge proofs. We draw inspiration from these designs to design
a protocol for our specific application.
Privacy in cryptocurrencies is well-studied from both a mechanism design
and analysis perspective. Much work has gone into designing private and scalable
cryptocurrency protocols using zero-knowledge proofs, starting from the original
ZeroCash work [12] to the initial Monero work [11] which utilises linkable ring
signatures to facilitate a cryptocurrency protocol. Cryptocurrency mixers on he
other hand present ways of adding privacy to blockchain protocols without such
functionality baked in. Prposals such as Zether [3] aim to build ZeroCash-like
functionality on Ethereum [14] in a smart contract. Similar in spirit, we design
our protocol on muliple smart contracts.
An example of a cryptocurrency mixer-like system on Bitcoin [10] is the
CoinJoin protocol [4] for Bitcoin and any UTXO based blockchain. CoinJoin
allows users to combine many transaction inputs and outputs within a single
transaction to obfuscate the flow of funds.
2 Preliminaries
We denote by 1λthe security parameter of our protocols and negl(λ) a negligable
function in λ. We denote by ·||· the concatenation of two elements, in binary
string representations.
We will restrict our focus to operating over a prime, finite-field Fpfor prime
number pZ. In our protocols our prime number pis on the order of λbits.
We denote PPT as polynomial, probabilistic time.
2.1 Hash functions
We let H:{0,1}Fpbe a cryptographic hash function that maps binary
strings to elements in Fp. We denote by $
a random sampling from a set.
Definition 1. A family of cryptographic hash functions His called collision-
resistant if PPT adversaries A, given H$
− H, the probability that Afinds
x, y such that H(x) = H(y)is negl(λ).
2.2 zkSNARKs
A zero-knowledge Succinct Non-interactive Argument of Knowledge (zkSNARK)
is a computation proof of an NP relation Rthat allows a prover Pthe ability to
demonstrate knowledge of a witness wfor a statement xto a verifier Vwithout
disclosing any information about the witness w. We aim to use a zkSNARK pro-
tocol that achieves zero-knowledge,succinctness,soundness, and completeness.
4
Zero-knowledge: Proofs πgenerated by Pfor (x, w)∈ R disclose no infor-
mation about the witness w.
Succinctness: Proofs πgenerated by Pfor (x, w)∈ R are small and do
not scale with the complexity of R.
Soundness: If Vaccepts a proof πgenerated by P, with probability 1
negl(λ)Pknows (x, w)∈ R.
Completeness: If Pknows (x, w)∈ R then they can generate a proof π
that Vaccepts with probability 1 negl(λ).
We utilise zkSNARKs for arithmetic circuits outlined in the original Zero-
Cash [12] protocol and [9]. Transformations from NP relations Rto arithmetic
circuits allow an individual to encode circuits whose satisfiability rests on know-
ing elements of R. We denote the circuit generated by Ras C.
Statements xin our relation Rhave both public and private inputs due to
the ability to hide parts of a satisfying witness wfor x. We will describe public
parameters and public inputs for our zero-knowledge proof system using this
font.
Definition 2. A zkSNARK protocol for an arithmetic circuit Cis composed of
a trio of algorithms: ( Setup, Prove, Verify).
(pp) Setup(1λ, C)generates a set of public parameters pp Fk
pwhere
kis a parameter derived from the circuit C.
πProve(pp, x, w)generates a proof proof πusing a statement xand
witness w.
bVerify(pp, x, π)outputs a boolean value b∈ {0,1}depending on if
the proof πis satisfying for the statement x.
We require this protocol to provide soundness,completeness, and zero-knowledge
as well as succinctness and simulation-extractability. We refer the reader to [7]
for formal explanations of these properties.
2.3 Merkle Trees
We utilise binary, merkle trees as the foundation of our mixing protocols. We
denote preimages of leaves in our merkle tree as z∈ {0,1}. Leaves in the tree
are elements y=H(z)Fpfor a collision-resistant hash function H$
− H.
Building the tree follows the standard algorithm of repeatedly hashing pairs of
child elements until a single element, the merkle root, remains.
We denote by Ian instance of a merkle tree and its merkle root MRIand
refer to the state of the merkle root and instance at time tas MRt
Iand It. We
will drop the twhen the context is clear. We define a function pathI(y) to be
the merkle proof path for a leaf y.
5
Definition 3. A merkle tree instance Iis defined with the algorithms (Setup,
Add, Verify, Prove, Verify Snark).
(pp, I)Setup(h, λ, C)generates a merkle tree instance Iwith height
hand public paramters for a merkle tree root reconstruction circuit Cwith
security parameter λ. For this, we run ZK.Setup(λ, C)from our zkSNARK
protocol as a subroutine.
bAdd(y, I)adds a leaf yFpto the merkle tree instance I, returning
a bit for failure/success b∈ {0,1}.
bVerify(y, pathIt(y), It)verifies a merkle path proof for a leaf yin a
merkle tree instance Itby re-computing a merkle root MRBand returning a
bit for failure/success b∈ {0,1}if MRB=MRt
I.
πIProve(pp,sn, r, s, I )generates a proof πIfor the following relation:
RMRI=(x, w)
w= (r, s, pathI(H(r||s))) sn =H(r)
x:= Verify(H(r||s),path(H(r||s),MRI) = 1
We generate a proof for this relation using ZK.Prove(pp, x, w, MRt
I)as a
subroutine. MRt
Iis a public input, wis a private input.
bVerify Snark(pp,sn, πI, I)verifies a zero-knowledge proof πIby run-
ning ZK.Verify(pp, x, πI,MRI,sn)from our zkSNARK protocol as a sub-
routine. A merkle root MRIand nullifier sn are provided as public inputs to
the verifier.
Note: We will eventually abuse the notation for Prove and Verify Snark to
satisfy a zkSNARK that verifies the statement representing the OR relation of
RIbut with 2 merkle roots of merkle tree instances, RMRA∪ RMRB. For this we
add extra inputs to our functional definitions.
Proposition 1. The ( Setup, Prove, Verify Snark) algorithms define a zk-
SNARK protocol that preserves soundness, completeness, zero-knowledge, suc-
cinctness, and witness-extractability properties.
Proof. It follows from [12] that we can build an arithmetic circuit for the relation
Ras well as generate succinct proofs that preserve soundness,completeness,zero-
knowledge, and which are simulation-extractable as long as our collision-resistant
hash function Hadmits a circuit that has polynomially many constraints and is
polynomial-time verifiable. This is not a strict requirement as there exists many
so called SNARK-friendly hash functions with low arithmetic complexity defined
over prime fields, such as MiMC [1] and Poseidon [6]. We refer to these papers
for proofs of their polynomial time verifiability.
2.4 Smart contracts
A smart contract is a piece of software that is executed within the execution
context of a blockchain protocol. A smart contract is considered ”smart” be-
cause it allows for generalised computational that is often turing-complete. For
6
background on smart contract blockchains, refer to Ethereum [14], which was
the first to implement these primitives.
For our purposes, we assume smart contracts are stateful programs with O(1)
read/write access. We can instantiate a variety of algorithms on these smart
contracts and interact with them through a peer-to-peer network.
3 Model
We restrict our attention to two smart-contract blockchain protocols Aand B
and a private bridge between them referenced by a smart contract S. Extending
this to n > 2 chains requires replicating Son more chains in a similar fashion
as is described. Sexists on both Aand Bbut may manage different states, we
denote these differences by SAand SB. We will also omit these subscripts when
we discuss shared functionality. To that end, we require that the smart-contract
engines for Aand Bare compatible; they support the same cryptographic prim-
itives and computational programs necessary for deploying and using S. For
the rest of the paper, we will assume that Aand Bare built using the same
blockchain platform.
We require the existence of light-clients on Aand Bof one another, such that
an external user can verify proofs of transactions and state of blockchain Bon
Aand vice versa with high probability of success 1 negl(λ). These light-clients
have a delay Duntil which transactions and state can be considered safe by
users on the bridged chain. Our delay Dis bounded in the presence of a single
honest light-client relayer who cannot be censored. Ssupports this functionality
through the algorithms (Setup, Add Header, Add Bridge State). We will
describe these algorithms in later sections.
The smart contract Ssupports algorithms (Setup, Deposit, Withdraw)
in order to operate the bridge. Sis also capable of owning a non-zero balance
of cryptocurrency of each blockchain. In a typical blockchain environment, users
have balances and spend them. We also assume that Shas the functionality to
own a balance and spend tokens on blockchains Aand B. This functionality will
be encoded into S.
4 Protocol
We let Sbe a smart contract that supports a light-client functionality and bridge
functionality. Light client functionality means that Scan process and verify
proofs of work or finality of other blockchains, in order to track their consensus
states. In a bridged network with S, light-client relayers share proofs of work
as well as information about bridge operations – deposits and withdrawals – for
A, SAon SBand vice versa.
7
Suses two types of bridge related state. The first is a merkle tree instance I
with fixed depth or height h. This tree supports the API defined above, with the
exception that Prove does not need to exist on S. The second type are arrays,
which we will use to store the serial numbers sn supplied when a user verifies
a zero-knowledge proof on SAand SBthrough relaying state back and forth.
We also have some state for handling light-client functionality. Each of these
data structures are initialised as empty. We denote the cryptocurrency being
sent over our bridge as $T, without loss of generality $Tcan be native to either
blockchain.
With this simplistic infrastructure deployed and operational, the high-level
protocol works as follows: A user udecides to transfer a non-zero number of
tokens $Tto blockchain B.
1. A mechanism designer constructs the circuit Cfor merkle tree membership
verification and selects the hash function H$
− H.
2. Sis deployed to both Aand B. We generate public parameters pp for both
using MT.Setup(h, λ, C) and setup Swith a genesis state for the light-client.
3. ugenerates random values r, s $
Fp
4. uinteracts with SAand deposits a fixed sized deposit dof $Tinto SA
and appends a merkle leaf zto IA, the merkle tree instance on A, using
Add(z, IA).
5. ugenerates a proof πIAof their deposit using MT.Prove(pp,sn, r, s, IA, IB).
6. umay submit proofs to withdraw their tokens after a delay D.
7. uwithdraws from SB, minting a wrapped $Ton B, by submitting the proof
generated previously, using MT.Verify Snark(pp,sn, πI,MRA,MRB).
With this informal description we now define the smart contract facilitating
this protocol and prove relevant properties about it.
8
4.1 Smart contract design
Bridge Contract SAfor blockchain
// Bridge related state variables
Merkletree IA
Fp[ ] nullifiers
{0,1}256[ ] Aroots
{0,1}256[ ] Broots
// Light client related state variables
{0,1}[ ] Bheaders
{0,1}initialised =false
Setup(B0, h, λ, C)
Add Header(Bi, φ)
Add Bridge State(C,S, k)
Deposit(v, z)
Withdraw(πI,MRt
A,MRt
B,sn)
Definition 4. We let nullifiers be a set of public nullifiers exposed on SAand
relayed to SAby the light-client relayers when new proofs are submitted for ver-
ification on SB.
Definition 5. We let Aroots be an array of roots that represent intermediate
states of IA. Elements of this collection are denoted by MRt
Afor an arbitrary
index t.
Definition 6. We let B roots be an array of roots that represent intermediate
states of IB. Elements of this collection are denoted by MRt
Bfor an arbitrary
index t.
Definition 7. We let B roots be an array of headers of Bthat have been verified
by the light client functionality.
Descriptions of our interface follow:
Setup(B0, h, λ, C) - Calls MT.Setup(h, λ, C ) and initialises the first block
header Bby adding to B headers and B roots.
Add Header(Bi, φ) - A function verifying a proof of a proof of work ϕfor
a new block header Bi.
Add Bridge State(C,S, k) - A function to verify updates to SB’s merkle
tree and add valid roots to B roots. This uses the header stored at B headers[k]
when the light client is initialised.
9
Deposit(v, z ) - Validates the deposit vand calls MT.Add(z, I). This func-
tion deducts a balance of vcoins from the sender.
Withdraw(πI,MRA,MRB,sn) - Validates the merkle roots are valid, i.e.
that they exist in the respective collections Aroots, B roots and also validates
that sn /nullifiers. Then, it calls MT.Verify Snark with the arguments
(ppI,sn, πI,MRA,MRB). If it succeeds, we withdraw funds to the sender.
Proposition 2. There exists a time DDsuch that a user can transfer tokens
from SAto SB.and withdraw them successfully on SB.
Proof. Once usuccessfully executes Deposit at time ton SA, we know that in
time D, the merkle root MRt+D
Awill be recorded in the array Aroots. Thus at
time t+D,ucan generate a proof πfor the membership of their deposit in either
the root of the native merkle instance OR one collected in the auxiliary storage.
Due to the completeness of our protocol, ucan successfully convince the verifier
on the smart contract function Verify Snark with probably at least 1 negl(λ).
4.2 Withdrawals
Once a user udeposits value into the tree, it is imperative that they cannot
double-withdraw from the system, a problem similar to the double spending
problem. We prevent this with the following observation and modification.
– Observation: A user ucan only double spend if the nullifiers sn used have
not been relayed to the bridged blockchain. Since we assume relayed informa-
tion arrives after delay D, a user uwould need to submit both withdrawals
within D.
Modification #1: All withdrawals suffer from a required delay of D+O(1)
in processing time, defined below. When a user submits the same nullifier to
both instances of S, the system will find out about the respective action in
time D, which is enough to cancel the withdrawal when detected.
Modification #2: When a relayer updates the nullifier set, we require that
each new nullifier added is checked for existence on the contract already to
find these duplicates mentioned above.
Proposition 3. With the modifications above, a user ucannot double withdraw
tokens.
Proof. Due to the soundness requirement, we don’t worry about proof forgery
as that occurs with negligable probability. Rather we restrict our attention to
whether any race condition exists in allowing double withdrawals.
Suppose a user usubmits 2 withdrawals at time tusing the same serial
number sn. This means at time tthe nullifier is exposed on both SAand SBand
appended to its respective collection. At time t+D, both SAand SBwill have
10
learned of new nullifiers exposed on each respective contract. When checking
existence for each new update, there will be a duplicate at sn, causing both
withdrawals to be canceled since an equal action is taken on the other smart
contract.
Without loss of generality, suppose usubmits the withdrawal at time ton
Aand waits tbefore submitting on B.sn will be recorded on Aand when the
withdrawal on SBis relayed at t+t+D, it will be cancelled on SA. Similarly,
when sn is relayed to SBat time t+D, it will result in a verifiable duplicate on
SB. Both deposits will be cancelled.
Proposition 4. A processing delay of D+ǫfor ǫ=O(1) is sufficient to secure
the system against double withdrawals.
Proof. We remark that if the time needed to check existence of a value in the
array data structure is not O(1) then we will switch it for a data structure
with O(1) search lookups. From above, we showed that if withdrawals were
delayed by Dtime then at least information about a double withdrawal will
be transmitted through the relayer system. The earliest withdrawal transaction
would be cancelled, followed by the later withdrawal being cancelled. Thus any
additional constant ǫof time is sufficient for delaying the possibility of not seeing
the necessary information to detect a double withdrawal.
4.3 Storage Complexity
Storing data for each of the necessary components is not for free. The storage
complexity of our contract is on the order of the light-client storage complexity
and the bridge functionality, which grow linearly in the presence of new infor-
mation. However, light-client headers are likely to be larger in size that nullifiers
and merkle roots, therefore the storage complexity O(S) = O(a light client) is
on the order of the light client’s storage requirements.
There are potential ways of reducing storage however, since blockchains are
resource bound and optimisations are worth implementing in production. We
describe future work at the end of the paper.
4.4 A free mixer
In our protocol, we describe a modification to the zkSNARK described in the
merkle tree algorithms, specifically one that takes as input 2 merkle roots. A keen
reader might notice that proving the OR relation of membership, in the native
blockchain or in the target blockchain, generalises the capabilities for users with
support for the functionailty of a mixer as well. Users who deposit on SAcan
also withdraw from SAor SB, and they cannot reuse a nullifer for this action
between these nullifiers are tracked in a growing list nullifiers that is kept up to
date with delay Don both instances of S.
11
Why is this a good thing? Users of blockchains Aor Butilising $Tcan utilise
the services of the bridge mechanism for mixer purposes specifically, effectively
creating a larger anonymity set for all the users combined. This is due to the
fact that our proofs are proofs over a combination of merkle tree accumulators
rather than a single one.
5 Incentives
Recent work from [9] as well as Tornado Cash [13] defined various schemes
for incentivising liquidity into mixers. In this paper, we present an additional
mechanism we could layer similar incentives onto. By participating on both sides
of the bridge, users would earn tokens, potentially to shielded addresses, where
rewards scale with the length they remained locked in their respective side of
the bridge. We document a naive mechanism for issuing rewards below that is
not optimal for privacy and discuss improvements thereafter.
5.1 A naive approach
The naive approach to rewards is to reward users for locking for at least a time
t. A user can prove that their deposit has been in the system for that time by
proving the deposit is accumulated in an older merkle root, one created before t
time from current root.
This approach may limit the privacy of the system in practice, since users
would likely open themselves up to fingerprinting attacks using statistical timing
techniques. As is referenced in the Tornado Cash anonymity mining scheme, it
is thus necessary to reward users where these parameters are kept as private
inputs to a zkSNARK circuit. Additionally, we would require that not only the
time locked remains private but also the amount earned, such that rewards are
issued to shielded addresses. We leave further investigation into this schemes to
future work.
5.2 Vampire Attacks
A vampire attack is an homage to a vampire sucking blood from its victim. These
bridge mechanism can be used in a similar fashion, to suck liquidity onto new
blockchains. Since users are rewarded for providing liquidity on each side of the
bridge in order to facilitate private transfers, users are incentivised to lock up
tokens on both sides, causing liquidity to distribute across the bridge.
12
6 Conclusion
6.1 Discussion
In this paper, we outlined a mechanism for executing privacy-preserving bridge
transfers by utilising 2 mixer-like mechanisms on both blockchains of the bridge.
We briefly discussed the storage concerns and incentives of using this mechanism
by rewarding an individual with a governance token that scales with their time
locked on each side of the bridge.
6.2 Future Directions
It is worth considering optimisations to the storage complexity of the system.
While we leave proofs of this to future work, we note that non-membership proofs
present interesting tools for proving an element’s non-membership in an accu-
mulated value. One can consider merkle-izing the set of nullifiers and verfiably
tracking the latest root of all reported nullifiers. A user’s withdraw proof could
then additionally prove that a serial number sn is not accumulated in nullifiers
merkle root, eliminating the need to store a potentially large collection of data.
Additonally, there is interesting incentive work to be done. For example, when
rewards are different on each side of the bridge, liquidity might flow towards
these incentives. The effects of this scheme can be investigated to understand
how liquidity of cryptocurrency assets across different blockchains is affected.
References
[1] Martin Albrecht et al. “MiMC: Efficient encryption and cryptographic
hashing with minimal multiplicative complexity”. In: International Con-
ference on the Theory and Application of Cryptology and Information Se-
curity. Springer. 2016, pp. 191–219.
[2] Benedikt B¨unz et al. Flyclient: Super-Light Clients for Cryptocurrencies.
Cryptology ePrint Archive, Report 2019/226. https://eprint.iacr.org/2019/226.
2019.
[3] Benedikt B¨unz et al. “Zether: Towards Privacy in a Smart Contract World.”
In: IACR Cryptol. ePrint Arch. 2019 (2019), p. 191.
[4] CoinJoin.url:https://en.bitcoin.it/wiki/CoinJoin.
[5] Ariel Gabizon et al. “Plumo: Towards Scalable Interoperable Blockchains
Using Ultra Light Validation Systems”. In: (2020).
[6] Lorenzo Grassi et al. “Poseidon: A new hash function for zero-knowledge
proof systems”. In: Proceedings of the 30th USENIX Security Symposium.
USENIX Association. 2020.
[7] Jens Groth. “On the size of pairing-based non-interactive arguments”. In:
Annual international conference on the theory and applications of crypto-
graphic techniques. Springer. 2016, pp. 305–326.
13
[8] Aggelos Kiayias, Andrew Miller, and Dionysis Zindros. Non-Interactive
Proofs of Proof-of-Work. Cryptology ePrint Archive, Report 2017/963.
https://eprint.iacr.org/2017/963. 2017.
[9] Duc V. Le and Arthur Gervais. AMR:Autonomous Coin Mixer with Pri-
vacy Preserving Reward Distribution. 2020. arXiv: 2010.01056 [cs.CR].
[10] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. 2009.
url:http://www.bitcoin.org/bitcoin.pdf.
[11] Shen Noether. Ring Signature Confidential Transactions for Monero. Cryp-
tology ePrint Archive, Report 2015/1098. https://eprint.iacr.org/2015/1098.
2015.
[12] Eli Ben Sasson et al. “Zerocash: Decentralized anonymous payments from
bitcoin”. In: 2014 IEEE Symposium on Security and Privacy. IEEE. 2014,
pp. 459–474.
[13] Tornado.Cash Governance Proposal. Tornado.Cash has become the largest.. .
— by Tornado Cash — Dec, 2020 — Medium.https://tornado-cash.medium.com/tornado-cash-governance-proposal-a55c5c7d0703.
(Accessed on 12/22/2020).
[14] Gavin Wood et al. “Ethereum: A secure decentralised generalised trans-
action ledger”. In: Ethereum project yellow paper 151.2014 (2014), pp. 1–
32.
ResearchGate has not been able to resolve any citations for this publication.
Conference Paper
We explore cryptographic primitives with low multiplicative complexity. This is motivated by recent progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where primitives from symmetric cryptography are needed and where linear computations are, compared to non-linear operations, essentially “free”. Starting with the cipher design strategy “LowMC” from Eurocrypt 2015, a number of bit-oriented proposals have been put forward, focusing on applications where the multiplicative depth of the circuit describing the cipher is the most important optimization goal. Surprisingly, albeit many MPC/FHE/ZK-protocols natively support operations in \(\text {GF}({p})\) for large p, very few primitives, even considering all of symmetric cryptography, natively work in such fields. To that end, our proposal for both block ciphers and cryptographic hash functions is to reconsider and simplify the round function of the Knudsen-Nyberg cipher from 1995. The mapping \(F(x) := x^3\) is used as the main component there and is also the main component of our family of proposals called “MiMC”. We study various attack vectors for this construction and give a new attack vector that outperforms others in relevant settings. Due to its very low number of multiplications, the design lends itself well to a large class of applications, especially when the depth does not matter but the total number of multiplications in the circuit dominates all aspects of the implementation. With a number of rounds which we deem secure based on our security analysis, we report on significant performance improvements in a representative use-case involving SNARKs.
Conference Paper
Non-interactive arguments enable a prover to convince a verifier that a statement is true. Recently there has been a lot of progress both in theory and practice on constructing highly efficient non-interactive arguments with small size and low verification complexity, so-called succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs). Many constructions of SNARGs rely on pairing-based cryptography. In these constructions a proof consists of a number of group elements and the verification consists of checking a number of pairing product equations. The question we address in this article is how efficient pairing-based SNARGs can be. Our first contribution is a pairing-based (preprocessing) SNARK for arithmetic circuit satisfiability, which is an NP-complete language. In our SNARK we work with asymmetric pairings for higher efficiency, a proof is only 3 group elements, and verification consists of checking a single pairing product equations using 3 pairings in total. Our SNARK is zero-knowledge and does not reveal anything about the witness the prover uses to make the proof. As our second contribution we answer an open question of Bitansky, Chiesa, Ishai, Ostrovsky and Paneth (TCC 2013) by showing that linear interactive proofs cannot have a linear decision procedure. It follows from this that SNARGs where the prover and verifier use generic asymmetric bilinear group operations cannot consist of a single group element. This gives the first lower bound for pairing-based SNARGs. It remains an intriguing open problem whether this lower bound can be extended to rule out 2 group element SNARGs, which would prove optimality of our 3 element construction.
Article
A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending. We propose a solution to the double-spending problem using a peer-to-peer network. The network timestamps transactions by hashing them into an ongoing chain of hash-based proof-of-work, forming a record that cannot be changed without redoing the proof-of-work. The longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power. As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network, they'll generate the longest chain and outpace attackers. The network itself requires minimal structure. Messages are broadcast on a best effort basis, and nodes can leave and rejoin the network at will, accepting the longest proof-of-work chain as proof of what happened while they were gone.
Zether: Towards Privacy in a Smart Contract World
  • Benedikt Bünz
Benedikt Bünz et al. "Zether: Towards Privacy in a Smart Contract World." In: IACR Cryptol. ePrint Arch. 2019 (2019), p. 191.
Plumo: Towards Scalable Interoperable Blockchains Using Ultra Light Validation Systems
  • Ariel Gabizon
Ariel Gabizon et al. "Plumo: Towards Scalable Interoperable Blockchains Using Ultra Light Validation Systems". In: (2020).
Poseidon: A new hash function for zero-knowledge proof systems
  • Lorenzo Grassi
Lorenzo Grassi et al. "Poseidon: A new hash function for zero-knowledge proof systems". In: Proceedings of the 30th USENIX Security Symposium. USENIX Association. 2020.
Non-Interactive Proofs of Proof-of-Work
  • Aggelos Kiayias
  • Andrew Miller
  • Dionysis Zindros
Aggelos Kiayias, Andrew Miller, and Dionysis Zindros. Non-Interactive Proofs of Proof-of-Work. Cryptology ePrint Archive, Report 2017/963. https://eprint.iacr.org/2017/963. 2017.
AMR:Autonomous Coin Mixer with Privacy Preserving Reward Distribution
  • V Duc
  • Arthur Le
  • Gervais
Duc V. Le and Arthur Gervais. AMR:Autonomous Coin Mixer with Privacy Preserving Reward Distribution. 2020. arXiv: 2010.01056 [cs.CR].