arXiv:2002.01847v1 [cs.CR] 5 Feb 2020

Zendoo: a zk-SNARK Verifiable Cross-Chain
Transfer Protocol Enabling Decoupled andDecentralized Sidechains
Alberto Garoffolo
alberto@horizen.global
HorizenDmytro Kaidalov
dmytro.kaidalov@iohk.io
IOHK Research

Roman Oliynykov
roman.oliynykov@iohk.io
IOHK Research
V.N.Karazin Kharkiv National University
January 2020

Abstract
Sidechains are an appealing innovation devised to enable blockchain scalability and extensibility.
The basic idea is simple yet powerful: construct a parallel chain – sidechain – with desiredfeatures, and provide a way to transfer coins between the mainchain and the sidechain.
In this paper, we introduce Zendoo, a construction for Bitcoin-like blockchain systems that allows the creation and communication with sidechains of different types without knowing their internal structure. We consider a parent-child relationship between the mainchain and sidechains,
where sidechain nodes directly observe the mainchain while mainchain nodes only observe cryptographically authenticated certificates from sidechain maintainers. We use zk-SNARKs toconstruct a universal verifiable transfer mechanism that is used by sidechains.
Moreover, we propose a specific sidechain construction, named Latus, that can be built on topof this infrastructure, and realizes a decentralized verifiable blockchain system for payments. We
leverage the use of recursive composition of zk-SNARKs to generate succinct proofs of sidechain
state progression that are used to generate certificates’ validity proofs. This allows the mainchain
to efficiently verify all operations performed in the sidechain without knowing any details about
those operations.

Contents
1 Introduction
1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
4

2 Preliminaries
2.1 Cryptographic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Recursive SNARKs Composition for State Transitions . . . . . . . . . . . . . . .

5563 General Overview
3.1 Main Components of a Sidechain Design . . . . . . . . . . . . . . . . . . . . . . .

7
8

4 Zendoo: a Cross-Chain Transfer Protocol for Sidechains
4.1 Cross-Chain Transfer Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Forward Transfers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Backward Transfers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2.1 Mainchain Managed Withdrawals . . . . . . . . . . . . . . . . .
4.1.2.2 Withdrawal Safeguard . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Sidechain Transactions Commitment . . . . . . . . . . . . . . . . . . . . .
4.2 Bootstrapping Sidechains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9
10
10
11
14
16
16
17

5 The Latus Sidechain
18
5.1 Consensus Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.1.1 Withdrawal Epochs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Accounting Model and System State . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2.1 System State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 Transactional Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3.1 Payment Transaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3.2 Forward Transfers Transaction . . . . . . . . . . . . . . . . . . . . . . . . 24
5.3.3 Backward Transfer Transaction . . . . . . . . . . . . . . . . . . . . . . . . 25
5.3.4 Backward Transfer Requests Transaction . . . . . . . . . . . . . . . . . . 26
5.4 State Transition Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.4.1 Performance and Incentives . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.5 Cross-Chain Transfer Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.5.1 Mainchain Block Reference . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.5.2 Forward Transfers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.5.3 Backward Transfers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.5.3.1 Withdrawal Certificate . . . . . . . . . . . . . . . . . . . . . . . 32
5.5.3.2 Backward Transfer Request . . . . . . . . . . . . . . . . . . . . . 34
5.5.3.3 Ceased Sidechain Withdrawal . . . . . . . . . . . . . . . . . . . . 35
6 Conclusions36

7 Acknowledgments

36

Appendix A MST Delta

38

2

1

Introduction

Since the inception of the Bitcoin cryptocurrency in 2008 [20], the topic of decentralized ledger
technology has received significant attention among experts from various areas. Bitcoin became
the first decentralized payment system based on peer-to-peer networking. Its key feature – theabsence of centralized control – is claimed to be the disruptive innovation that will help build
more robust, fair, and transparent financial systems. Bitcoin inspired the appearance of manyother systems based on the same principle of decentralization with a variety of different features.
With the increasing use of Bitcoin and similar blockchain systems, their inherent limitations
became apparent: limited throughput, increased latency, reduced ability to scale and expand
functionality, etc. [10]. Even more important is that such decentralized systems are challenging
to update since there is no single decision-making entity. Even a small protocol change requires
a cumbersome process of community agreement, which makes the introduction of new featuresdifficult.
Sidechains, proposed by A. Back et.al. in 2014 [5], is an appealing concept that allows one
to work around the constraints of a single decentralized blockchain. The basic idea is simple:
to create a separate blockchain with whatever functionality is needed and provide a way tocommunicate with the main blockchain (Fig. 1). Communication means the ability to transfer
a mainchain native asset (e.g. bitcoins) to and from a sidechain.
Main Blockchain (e.g. Bitcoin)

Sidechain A (smart contracts)

Sidechain B (fast transactions)Sidechain C (governance)

Figure 1: Sidechains. The main blockchain provides basic cryptocurrency functionality while
sidechains implement specific functions.
This way, for instance, a blockchain system, like Bitcoin, can be extended with additional
functionalities (such as smart contracts [3]) implemented in a separate sidechain, which uses thesame native asset, hence remaining in the Bitcoin ecosystem.
In this paper, we propose Zendoo, a universal construction for Bitcoin-like blockchain systems
that allows the creation and communication with sidechains of different types without knowing
their internal structure (e.g. what consensus protocol is used, what types of transactions aresupported, etc.). In fact, the sidechain may not even be a blockchain but can be any systemthat uses the standardized method to communicate with the mainchain.
Specifically, we consider a parent-child relationship between the mainchain and sidechains,
where sidechain nodes directly observe the mainchain while mainchain nodes only observe cryptographically authenticated certificates from sidechain maintainers. Among other things, suchcertificates authorize transfers coming from sidechains. Certificate authentication and validation
are achieved by using zk-SNARKs [6], which enable constant-sized proofs of arbitrary computations. The main feature of our construction is that sidechains are allowed to define their own
zk-SNARKs, thus establishing their own rules for authentication and validation. The fact thatall zk-SNARK proofs comply with the same verification interface used by the mainchain enables
great universality as the sidechain can use an arbitrary protocol for authenticating its certificates. E.g., the sidechain may adopt a centralized solution where the zk-SNARK just verifies

3

that a certificate is signed by an authorized entity (like in [5]) or, for instance, a decentralized
chain-of-trust model as in [13].
Moreover, we propose a specific sidechain construction, named Latus, that can be built on
top of this infrastructure, and realizes a decentralized verifiable blockchain system. We leverage
the use of recursive composition of zk-SNARKs to generate succinct proofs of sidechain state
progression (as in [19]) that are used to generate certificate proofs for the mainchain. This allows
the mainchain to efficiently verify all operations performed in the sidechain without knowing
any details about those operations.
The paper is structured in the following way: section [2] provides basic definitions that areused throughout the paper; section [3] provides a general overview of the sidechain concept;
section [4] provides details about the proposed cross-chain communication protocol Zendoo andintroduces basic interfaces imposed by the mainchain side; section [5] provides details of theLatus sidechain construction.

1.1

Related Work

The concept of sidechains was first introduced by A. Back et.al. in 2014 [5]. They introduced
a general notion of a 2-way peg and described two operational modes – synchronous and asynchronous – to implement interactions between pegged chains. The synchronous mode implies
that both main and side chains are aware of each other and can verify transfer transactions
directly, while the asynchronous mode relies on validators to process transfers.
Notable construction of sidechains was presented in [25, 18] and called Drivechains. It
aims to deploy sidechains on top of the Bitcoin network. While forward transfers (from themainchain to a sidechain) are processed by providing SPV proofs (like the synchronous mode in[5]), backward transfers rely upon validators. Validators in Drivechains are mainchain miners
who observe sidechains and endorse transfers.
The first formal treatment of sidechains was proposed by P. Gaži, A. Kiayias, and D. Zindrosin [13]. In addition, they presented a sidechain construction for proof-of-stake blockchains wheresidechain nodes directly observe and confirm forward transfers while backward transfers are
confirmed by certifiers chosen among sidechain block forgers.
Our previous proposal on sidechains [12] presents a flexible model which allows the construction of different types of sidechains whose internal structures are unknown to the mainchain.
It relies on certifiers to confirm backward transfers in the mainchain. Though, in this modelcertifiers are chosen randomly from a pool of certifiers registered directly in the mainchain.
Mentioned constructions differ from our current proposal in various aspects, most notably
because they either assume that the mainchain observes sidechains directly or relies on someintermediary to confirm transfers. In addition, they do not provide flexibility (except [12]),which means that a sidechain construction (e.g. consensus protocol) cannot be chosen freely.
In [16], A. Kiayias and D. Zindros proposed implementation of the sidechain protocol forthe proof-of-work blockchains based on smart contracts. Another notable sidechain construction that relies on smart contracts is called Plasma and was presented in [22] by J. Poon and
V. Buterin. On the contrary, our construction does not rely on smart contracts.
One of the main features of the construction presented in this paper is the usage of zkSNARKs for enabling verifiable cross-chain communication. zk-SNARK has initially been proposed as a zero-knowledge protocol which allows proving possession of some information without
revealing it [6]. However, this technique is suited for more than simply securing information but
also for solving scalability issues: it enables succinct constant size proofs of almost arbitrarycomputations. For instance, using the recursive composition of zk-SNARKs [19, 8] it is possible4

to construct a succinct proof of state transition virtually for any number of transactions. We
were inspired by these techniques while designing our sidechain construction.
A notable sidechain construction that also relies on zk-SNARKs is ZK Rollup [14]. It is alayer 2 solution based on smart contracts for scaling transaction throughput in Ethereum [2].
The basic idea is that transactions are carried out off-chain while the information about entailed
state transitions together with a zk-SNARK proof of their validity is submitted to the contract.
It still requires submission of some limited information about each transaction on-chain toprevent data availability attacks thus limiting scalability. Our construction differs from ZK
Rollup in many aspects, most notably because we do not push sidechain transaction data to themainchain.
There are many other attempts to construct cross-chain transfer mechanisms including the
Liquid project [9], Polkadot [30], Interledger [27], Cosmos [1], and many others. They propose
various solutions that are different from our construction.

2

Preliminaries

In this section, we introduce definitions of several cryptographic constructions that are usedthroughout the paper. We defer formal descriptions (especially of the recursive SNARKs composition) for a separate paper and define here only basic notations needed to describe theproposed sidechain construction.

2.1

Cryptographic Definitions

Definition 2.1. Collision-Resistant Hash Function (CRH). A hash function H is collisionresistant if the probability of finding two different input strings a and b such that H(a) = H(b)is negligible (more formal definition can be found, e.g., in [15]).
Whenever we refer to a hash function, we suppose it is collision-resistant.
Definition 2.2. Merkle Hash Tree (MHT). The Merkle Hash Tree, or simply Merkle Tree
(MT), is a binary tree data structure where the value of an internal node is computed as thehash of values of its children, and the value of a leaf node is the direct hash of a data block
represented by this leaf (see Fig. 2) [23, 21].
h1= H(h21 | h22)h1h21= H(h31 | h32)h22= H(h33 | h34)

h21

h22
h32

h31

h33

h34

h41= H(data1)

h41

h42

h43

h44

h45

h46

h47

h48

data1

data2

data3

data4

data5

data6

data7

data8

Figure 2: Merkle Hash Tree.
We call the top-level node (h1 in Fig. 2) the root hash of the MHT. Given that a collisionresistant hash function is used to calculate tree nodes, we can consider root hash as a tree5

authenticator: it is impossible to tamper even a single bit of data in the tree without alsochanging the root hash.
An important feature of the Merkle tree structure is that it produces a concise proof of aparticular data block’s membership in a tree with the particular root hash. E.g., if one wants toprove that data4 (Fig. 2) is included in the MHT tree with the root hash h1 , they just need toprovide a verifier with the data block along with a tuple of internal nodes (h43 , h31 , h22 ) that willallow recalculating the tree root and comparing it to the provided root h1 . We call it Merkle
proof.
Definition 2.3. Succinct Non-Interactive Argument of Knowledge (SNARK).
A SNARK is a proving system consisting of a triplet of algorithms (Setup, Prove, Verify) thatallows proving satisfiability of a set of inputs to an arithmetic constraint system (see, e.g., [6, 7]
for more formal definition and properties analysis).
We define an arithmetic constraint system as a set of polynomials over a finite field F in
variables (x1 , ..., xr , y1 , ..., ys ). A satisfying assignment for the given constraint system C is an
assignment of F elements to xi and yj such that all polynomials evaluate to zero. We indicate
a satisfying assignment as C(a, w), where a = (a1 , ..., ar ), ai ∈ F and w = (w1 , ..., ws ), wj ∈ F .
We refer to a as public input and w as witness.
Then, the algorithms (Setup, P rove, V erif y) are defined such that
1. (pk, vk) ← Setup(C, 1λ ) bootstraps SNARK for a constraint system C under security
parameter λ. The bootstrapped SNARK is specified by a pair of keys (pk, vk) which
are a proving key and a verification key correspondingly.
2. π ← P rove(pk, a, w) evaluates a proof π, which confirms that (a, w) is a satisfying
assignment for C.
3. true/f alse ← V erif y(vk, a, π) verifies that π is a valid proof attesting to the satisfying
assignment (a, w) for the constraint system C.
Algorithms (Setup, P rove, V erif y) satisfy the following properties:
1. Completeness. For any constraint system C and (a, w), if π ← P rove(pk, a, w) is avalid proof, then V erif y(vk, a, π) is always true.
2. Knowledge soundness. If a pair (a, w) is not a satisfying assignment for C, thenthe probability of obtaining π such that V erif y(vk, a, π) = true is negligible.
3. Succinctness. For every constraint system C bootstrapped with (pk, vk) and everya ∈ F r , the size of a proof and verification time is polynomial in λ.

2.2

Recursive SNARKs Composition for State Transitions

Here, we provide a high-level definition of the recursive proof composition technique that is usedin our sidechain model to construct succinct proofs of state transitions. The idea of recursive
proofs has been discussed, e.g., in [6, 19, 8]. What follows is based principally on the construction
described in [19].
Definition 2.4. State Transition System. A state transition system is defined by a set of
all possible states S, a set of all possible transitions T , and a transition function update(ti , si ),where si ∈ S and ti ∈ T , which returns a new state si+1 or ⊥ in case (ti , si ) does not constitutea valid input for the update function.
Speaking informally, we would like to define a SNARK that attests to many iterative statetransitions. E.g., if we have transitions (t1 , t2 , ..., tn ) that are applied sequentially to state s1 to6

produce state sn+1 , we would like to have a succinct proof of the following statement: “there
exist such (t1 , ..., tn ) so that update(tn , update(tn−1 , update(..., update(t1 , s1 )))) = sn+1 ”.
By applying this to blockchain, we will be able to provide succinct proofs of transition
between some states si and sj (i < j). The state can be represented, for instance, as a listof unspent transaction outputs [29], while transitions are regular blockchain transactions thatspend some outputs and create new ones. This construction is of great value for verifiablesidechains.
Definition 2.5. Recursive SNARKs for state transition systems. We define recursive
SNARKs composition as a tuple of SNARKs (Base, M erge) such that:
1. Base is a SNARK for a single transition that proves the existence of such t so thatsi+1 = update(t, si ). It is defined by a triplet (Setup, Prove, Verify) such that:• (pk Base , vk Base ) ← Setup(1λ ) bootstraps Base SNARK;• π Base ← P rove(pk Base , (si , si+1 ), (ti )) evaluates a proof π Base that confirms si+1 =update(ti , si );• true/f alse ← V erif y(vk Base , (si , si+1 ), π Base ) verifies that π Base is a valid proof
attesting state transition from si to si+1 .
2. Merge is a SNARK that merges two other SNARKs (either Base or Merge) proving thevalidity of transition between states si and sj (i + 1 < j). It is defined by a triplet (Setup,
Prove, Verify) such that:• (pk M erge , vk M erge ) ← Setup(1λ ) bootstraps Merge SNARK;• π M erge ← P rove(pk M erge , (si , sj ), (sk , π1a , π2a )) evaluates a proof π M erge that confirms π1a , π2a are valid SNARKs (a ∈ {Base, M erge}), which attest state transitions
from si to sk and from sk to sj correspondingly. Altogether, it proves a valid transition from si to sj (i < k < j);• true/f alse ← V erif y(vk M erge , (si , sj ), π M erge ) verifies that π M erge is a valid proof
attesting state transition from si to sj , i < j.
We intentionally omit specifics of the recursive SNARKs composition, which in reality ismore sophisticated. More details on the topic can be found, for instance, in [19, 8]. We defer
the details of our construction for a separate paper. At this point, we provided only basic
definitions, which allow us to describe the sidechain protocol while abstracting away the detailsof the SNARKs construction.

3

General Overview

This section gives an overview of the sidechain concept in general and the main components ofany sidechain design. We also briefly discuss our proposed solutions.
Before going any further, we want to introduce abstract definitions of the terms mainchain
and sidechain that are used throughout this paper.
Definition 3.1. Mainchain (MC). The mainchain is a blockchain system based on the Bitcoin
backbone protocol model [11], which maintains a public ledger of asset-transfer transactions.
Additionally, the mainchain supports a standardized mechanism to register and interact withseparate sidechain systems. By interaction, we mean the cross-chain transfer protocol, whichenables sending a native asset to a sidechain and receiving it back in a secure and verifiable way
without the need to know anything about the internal sidechain construction or operations.
7Definition 3.2. Sidechain (SC). The sidechain is a separate system attached to the mainchain
by means of a cross-chain transfer protocol.
Speaking informally, we consider the mainchain to be a blockchain platform that supports
basic payment functionality with some native asset Coin (e.g. Bitcoin [20], Horizen [26], etc.).
Then, the sidechain is an attached domain-specific platform that also uses the Coin asset (butnot limited to it). In our model, we consider a single mainchain with many sidechains attached
to it.
The definition of a sidechain (as in Def. 3.2) does not imply the usage of any particular
data structure or consensus algorithm. The mainchain is totally agnostic to the sidechain
construction. It can be another decentralized blockchain, some centralized database maintainedby the predefined authority, or more generally, an arbitrary application.
The need to introduce sidechains in a general payment-based blockchain system comes fromthe need to allow the creation of different blockchain applications that use the same mainchain
asset. Creation of such applications directly on the mainchain is not always possible due to inherent technological limitations, such as restricted throughput, expensive storage, etc. Sidechains
effectively solve these problems.

3.1

Main Components of a Sidechain Design

Analyzing existing attempts to design sidechains [12, 5, 25, 18, 16, 13, 14], we may outline threebasic components that underlie any sidechain architecture:
1. Mainchain consensus protocol (MCP).
2. Cross-chain transfer protocol (CCTP).
3. Sidechain consensus protocol (SCP).
Depending on a specific design, these components can be highly coupled with each other or
decoupled so that the mainchain is almost independent from any particular sidechain implementation.
In our construction, we aspire to multipurposeness and, thus, designing a system so that
the MCP and SCP are completely decoupled. The CCTP is naturally a bridge between themand is unified and fixed by the mainchain consensus protocol. On the other end, the SCP canbe freely defined by a sidechain developer. This allows a variety of different sidechains withdifferent purposes to thrive while not requiring any changes to the mainchain.
Cross-chain transfer protocol. The CCTP protocol defines the communication between
the mainchain and sidechain(s). Basically, it is a 2-way peg protocol that allows sending coinsback and forth. At a high level, it defines two basic operations:• Forward Transfer, and• Backward Transfer.
A forward transfer sends coins from the mainchain to a sidechain. A backward transfer,correspondingly, moves coins back from the sidechain to the mainchain. These operations are thecornerstone of overall sidechain construction. The backward transfer is of particular importancesince we do not want to oblige the mainchain to track sidechains and, thus, it cannot directly
verify the validity of withdrawals coming from them. That is why most of the focus in developing
sidechains is directed toward constructing secure and reliable backward transfers.
In our approach, Zendoo, we consider a forward transfer as a special transaction on the
mainchain that destroys coins and provides sidechain-specific metadata allowing a user to receive8

coins in the sidechain. Implementation of forward transfers is straightforward as it does not
require the mainchain to know anything about the sidechain state for validation.
A more complex procedure is required for backward transfers. They are initiated in thesidechain as special transactions, batched in a withdrawal certificate, and propagated to themainchain for processing. Since we do not want the MC to follow the SC state – as thiswould impose enormous computational and storage burden on the MC and, thus, undermine thewhole point of having sidechains – the question arises how to implement validation of backward
transfers in the most efficient and secure way.
In our previous paper [12], this problem has been addressed by introducing into the systema special type of decentralized actors – certifiers – that were registering themselves in the MC
and were responsible for signing withdrawal certificates. Although the safety of this approachhas been shown, it requires certain assumptions about an honest majority of certifiers, which,in some scenarios, may not be the case.
In Zendoo, we avoid direct reliance on certifiers or any other special type of actors assigned tovalidate withdrawal certificates. Instead, we are going to leverage SNARKs [6, 7, 19] to provide
means for the mainchain to effectively validate withdrawals.
Sidechain consensus protocol. We consider the SCP as a generalized notion that encompasses all the details about a particular sidechain construction such as consensus algorithm,
accounting system, types of supported transactions, incentives mechanism, a protocol for withdrawal certificate generation, etc. Also, importantly, each sidechain defines its own SNARK1
that is used to validate withdrawal certificates. This provides flexibility to define its own rules
for backward transfers. For instance, a sidechain can adopt a chain-of-trust model [13] or eventhe certifiers model [12]. It is completely decoupled from the mainchain consensus protocol,
which will just invoke a unified verifier to validate a proof.
Even though the SCP can be designed in different ways, we propose one specific constructionof a decentralized verifiable sidechain based on the Ouroboros protocol [17]. We will call thisconstruction Latus. In short, we are going to use recursive composition of SNARKs to generate
succinct proofs of sidechain state transitions. Each withdrawal certificate commits to the SC
state whereas the SNARK proof validates transition between states committed by successive
withdrawal certificates. Since backward transfers are a part of the sidechain state transition,
they are also validated by the proof.
The following section [4] introduces Zendoo, a cross-chain communication protocol for sidechains
which is principally about the definition of the transfer protocol and how a new sidechain canbe registered in the mainchain. It defines the sidechains design from the mainchain point ofview. Then, in section [5], we describe in detail the proposed sidechain construction Latus.

4

Zendoo: a Cross-Chain Transfer Protocol for Sidechains

The following section provides details about the communication protocol between the mainchain
and sidechains, which is primarily represented by the cross-chain transfer protocol. We show
how the CCTP protocol is integrated in the mainchain, what interfaces are provided, and how
a new sidechain can be created.
1 Speaking more formally, here, we refer to an arithmetic constraint system (arithmetic circuit) that is compiled
for each sidechain and defines the logic of the SNARK. Note that the interface of the verifier is defined by themainchain so – even though the internal logic of the SNARK may be different for different sidechains – generated
proofs can be verified in the standardized way.

9

4.1

Cross-Chain Transfer Protocol

The cross-chain transfer protocol is the cornerstone of our sidechain design as it connects the
mainchain with all sidechains spawned from it. Its main function is to allow sending coins
to sidechains and receiving them back in a secure and reliable way. This section provides ahigh-level specification of forward and backward transfers and how they are integrated into themainchain.
4.1.1

Forward Transfers

The design of forward transfers is straightforward and similar to many existing proposals forsidechains [5, 25, 18, 16, 13] as well as to our original proposal [12].
On the mainchain side, it is implemented as a special type of operation (we will call it Forward
Transfer ) that destroys coins and provides metadata for withdrawing coins in a sidechain. Then,
it is the responsibility of the sidechain to sync forward transfers from the MC and issue thecorresponding amount of coins.
Definition 4.1. Forward Transfer (FT). Forward Transfer is an operation that moves coinsfrom the original blockchain A (the mainchain) to the destination sidechain B. It is represented
by a tuple of the form:def

F T = (ledgerId, receiverM etadata, amount),
where:− a unique identifier of a previously created and active sidechain towhich coins are transferred;amount− a number of coins to transfer;receiverM etadata − some metadata for receiving sidechain B (e.g., a receiver’s address); its
structure is not fixed in the mainchain and can consist of different
variables of predefined types depending on a sidechain’s construction;
its semantic meaning is not known to the mainchain.
ledgerId

There can be several approaches to integrate forward transfers on the mainchain side depending on its details. For instance, forward transfer can be a separate transaction type which
destroys coins in the mainchain, or, in the case of a UTXO-based blockchain system (e.g. Bitcoin or Horizen), we can consider FT as a special unspendable transaction output in a regularmulti-input multi-output transaction [29, 4].
To be more specific and facilitate further reading, we assume that the mainchain has a
UTXO-based accounting model2 . Then, a regular transaction with forward transfers may havethe following structure:
2 It is in line with our own implementation of sidechains, which is going to be deployed on the Horizen
mainchain.

10

type Transaction {Inputs: {Input(addr: 0x013A.., amount: 5, signature: 0x034B..),
Input(addr: 0x0930.., amount: 3, signature: 0x1AA1..),...
}
Outputs: {Output(addr: 0x023B.., amount: 1),
Output(addr: 0x0732.., amount: 2),
ForwardTransfer(ledgerId: 0x300C.., receiverInfo : 0x139D.., amount: 2),
ForwardTransfer(ledgerId: 0x300C.., receiverInfo : 0x893D.., amount: 3),...
}}
Given that an FT is a non-spendable output, it basically destroys coins in the mainchain,and the amount of transferred coins is verified by the mainchain as part of the overall transaction
verification.
4.1.2

Backward Transfers

The backward transfer protocol allows coins to move from a sidechain to the mainchain, and, asin [12] and [13], it relies on the idea of batched transfers. This means that all requested backward
transfers submitted to the sidechain during a certain period – called the “withdrawal epoch” –are collected in a special withdrawal certificate and pushed to the mainchain for processing.
Withdrawal certificates are more than just a container for backward transfers, they are akind of sidechain heartbeat that is periodically submitted to the mainchain even though there
might be no backward transfers3 .
A withdrawal epoch is defined by a range of MC blocks. Withdrawal epochs for different
sidechains are not aligned and may have a different length (epoch len parameter is set uponsidechain creation), and, therefore, the entire system runs asynchronously.
Let us define an MC block B that belongs to a specific epoch as Bjep id , where ep id is theepoch number and j ∈ [0, epoch len) is the serial number of the block within the epoch (Fig. 3).
Withdrawal certificate
for epoch i-1

Bi0

Bi1

Withdrawal certificate
for epoch iBi2

Bilen-1Bi+10i-th withdrawal
epoch

Bi+11

Bi+12

Bi+1len-1(i+1)-th withdrawal
epoch

Figure 3: Withdrawal epochs in the mainchain. Note that withdrawal epochs for different
sidechains may not overlap. It depends on parameters that have been set upon sidechain creation.
The sidechain is obliged to submit a withdrawal certificate for epoch i during the firstsubmit len blocks of the epoch i + 1 (submit len is a system parameter). If a withdrawal
3 Later, in section [5], we will show how this can be leveraged to construct secure verifiable sidechains byproviding their state commitments as part of withdrawal certificates

11certificate has not been submitted during this time, the sidechain is considered ceased (seeDef. 4.2) and no more withdrawal certificates for this sidechain will be accepted by the mainchain(however, the funds can still be withdrawn with a ceased sidechain withdrawal [4.1.2.1]).
Definition 4.2. Ceased Sidechain. A sidechain is deemed ceased by the mainchain if a
withdrawal certificate for that sidechain has not been submitted on time, i.e. a certificate forwithdrawal epoch i has not been submitted during the first submit len blocks of the epoch i+14 .
Note that the mainchain consensus protocol does not impose any rules on how exactly awithdrawal certificate should be generated and by whom it should be submitted. It is up to thesidechain to define corresponding procedures. We only assume that it is submitted by means ofa special transaction in the mainchain.
As it has been mentioned, a withdrawal certificate contains backward transfers. We may
consider them as requests that are fulfilled once included in the withdrawal certificate andpropagated to the mainchain. There are no restrictions for how backward transfers should besubmitted and collected (e.g. it can be a separate transaction on the SC side).
Definition 4.3. Backward Transfer (BT). Backward Transfer is an operation that moves
coins from the sidechain B to the original mainchain A. It is represented by a tuple of the form:def

BT = (receiverAddr, amount),
where:
receiverAddr − an address in the mainchain where transferred coins should be credited;amount− the number of transferred coins.
There can be different approaches to integrate backward transfers in the mainchain. Following the assumption of a UTXO-based mainchain, a BT can be represented by a special output
in a transaction with a withdrawal certificate.
Definition 4.4. Withdrawal Certificate (WCert). Withdrawal certificate is a standardized posting that allows sidechains to communicate with the mainchain. Its main functionsare:1) delivering backward transfers to the MC; and2) serving as a heartbeat message enabling the MC to identify SC status.
It is represented by a tuple of the form:def

W Cert = (ledgerId, epochId, quality, BT List, proof data, proof ),where:
ledgerId − an identifier of the sidechain for which WCert is created;
epochId − a number of a withdrawal epoch;
quality− an integer value that indicates the quality of this withdrawal certificate(explained later);
BT List − a list of backward transfers included in this withdrawal certificate;
proof data − input data to a SNARK verifier;proof− a SNARK proof.
4 Even though this requirement may seem strong, it is necessary to provide certain properties which we discusslater. We also explore the possibility to provide more flexibility for withdrawal certificate submission

12Now, we discuss in more detail the substance of certificate parameters as it is one of themost important parts of the sidechain design.
As it has been briefly outlined, the basis of the proposed construction is that there are no
special entities that authorize withdrawal certificates (e.g., like certifiers in [12] or slot leadersin [13]). Instead, the certificate authorization and validation rely completely on the included
SNARK proof, and the SNARK itself is defined by the sidechain. The mainchain knows only theverification key – which is registered upon sidechain creation – and the interface of the verifier,which is unified for all sidechains. If the SNARK proof and public parameters are valid, thenthe certificate gets included and processed in the mainchain.
Withdrawal certificate quality. It might happen that several withdrawal certificates appear for the same sidechain in the same withdrawal epoch5 . Since only one WCert should beselected among them and given that the mainchain does not know about the sidechain consensus
protocol and does not track its state, there should be a mechanism for the mainchain to decide
which certificate is the best one. Such a mechanism is realized through the quality parameter:
the mainchain adopts a certificate with the highest quality or the one that was submitted firstin case there are several certificates with equal qualities. The validity of the quality parameteris enforced by the SNARK proof.
Withdrawal certificate verification. Verification of a newly submitted WCert on the mainchain is performed using the following basic rules:
WCert Verification
1. ledgerId should be an identifier of a currently active sidechain;
2. epochId should be a valid withdrawal epoch number for the ledgerId (rememberthat the certificate should be submitted during the first submit len blocks of theepoch following the one, for which such certificate was created);
3. quality should be higher than the quality of the previously submitted withdrawal
certificate for this epoch; if it is the first WCert for this epoch - any quality is
accepted;
4. proof should be a valid SNARK proof whose verification key vkW Cert is set uponsidechain registration;
SNARK verification is the most essential part of the verification procedure as it encapsulatesverification of backward transfers and other parameters provided within the certificate. The
basic SNARK verifier interface is the following:true/f alse ← V erif y(vkW Cert , public input, proof ),defpublic input = (wcert sysdata, M H(proof data)),where:
5 Even though it should not happen under normal operation, it may be the case, for instance, if the sidechain
is a blockchain system, which experiences a continuous fork, or due to some malicious activity13

− a SNARK verification key registered upon the sidechain creation;− a part of the public input, which is unified for all sidechains andenforced by the mainchain (explained further);
proof data
− a part of the input data that is defined by the sidechain and passedalong the withdrawal certificate; it is basically a list of variables ofpredefined types whose semantics are not known to the mainchain;
M H(proof data) − a root hash of a Merkle tree where leaves are variables from proofdata; itis essential for the SNARK to keep a list of public inputs short, thus we
combine them in a tree and pass the root hash only6 ;proof− a SNARK proof itself submitted as a part of the certificate.
vkW Cert
wcert sysdata

wcert sysdata parameter plays an important role from the security standpoint. The idea is
to allow the mainchain to verify the proof against some public input parameters that are definedby the protocol. For instance, the BTList and quality parameters that are part of the certificate
must be verified before being used by the mainchain. Another example is the mainchain block
hashes of the epoch boundaries that must be verified to guarantee that the proof refers to thecurrent epoch and the active chain.
wcert sysdata is represented by the tuple of the following form:
def

i−1), B(ilast )),wcert sysdata = (quality, M H(BT List)), H(Blast

where:
quality− the quality parameter from the withdrawal certificate;
M H(BT List) − a root hash of a Merkle tree where leaves are backward transfers from the
BTList provided within the certificate;i−1
H(Blast )− a block hash of the last mainchain block in the withdrawal epoch i − 1(given that the certificate is for the epoch i);i)− a block hash of the last mainchain block in the withdrawal epoch i.
H(BlastThe generalized SNARK verifier provides flexibility to implement different SNARKs fordifferent sidechain models. For instance, one may want to implement the sidechain with acentralized cross-chain transfer protocol where withdrawal certificates are verified by a signaturefrom an authorized entity. Or, conversely, a completely decentralized verifiable sidechain can beconstructed as will be discussed in [5 The Latus Sidechain]).
Succinct proofs and constant time verification make the overall sidechain design particularly
appealing as it does not impose a significant burden for the mainchain.
4.1.2.1

Mainchain Managed Withdrawals

There might be cases when a user would want to request a backward transfer directly from themainchain rather than creating a BT in the SC. For instance, it would allow users to withdraw
funds in case of a misbehaving (e.g., maliciously controlled sidechain that censors submission of
backward transfers) or ceased sidechain.
Hence, we introduced two additional mechanisms that allow users to make withdrawals
directly in the mainchain:
1. Backward transfer request (BTR), and2. Ceased sidechain withdrawal (CSW).
6 A full payload of proofdata is provided during the proof generation as a witness.

14

We consider each of them as a special type of transaction. Similar to withdrawal certificates,
such operations are secured by SNARK proofs.
The BTR is used to withdraw funds from an active sidechain if for some reason a user cannot
create a backward transfer inside the sidechain. The idea is that all BTRs submitted to themainchain will be synchronized to the sidechain and processed there to verify their legitimacy
and include the corresponding backward transfers in the next WCert using the standard flow.
Such processing can be enforced by the withdrawal certificate SNARK to force a maliciously
controlled sidechain to process user’s withdrawals7 . Importantly, the BTR does not lead to a
direct coin transfer in the mainchain.
The CSW is used to withdraw funds from ceased sidechains. Since withdrawal certificatesare not allowed for ceased sidechains, it becomes the only way to retrieve funds. A valid CSW
makes direct payment to the submitter.
Definition 4.5. Backward transfer request (BTR). The BTR is a generic request for abackward transfer that is submitted on the mainchain. It is represented by the following tuple:def

BT R = (ledgerId, receiver, amount, nullif ier, proof data, proof ),where:
ledgerId − an identifier of the sidechain, for which BTR is created;
receiver − an address of the receiver on the mainchain;amount − the number of coins to be transferred;nullif ier − a unique identifier of claimed coins;
proof data − input data to a SNARK verifier;proof− a SNARK proof.
As in the case with a withdrawal certificate, the SNARK for the BTR is defined by thesidechain and represented by the verification key vkBT R , which is set upon sidechain registration.
The syntax of the proof data and proof are the same as for the withdrawal certificate. The
basic interface of the SNARK verifier is the following:true/f alse ← V erif y(vkBT R , public input, proof ),defpublic input = (btr sysdata, M H(proof data)),where:
vkBT R is a SNARK verification key for the BTR registered upon the sidechain creation;
btr sysdata, proof data, M H(·), and proof have the same meaning as similar parametersin the withdrawal certificate.
btr sysdata is defined as:def

btr sysdata = (H(Bw ), nullif ier, receiver, amount),
where H(Bw ) is a block hash of the mainchain block where the latest withdrawal certificate
for this sidechain has been submitted.
Definition 4.6. Ceased Sidechain Withdrawal (CSW). The CSW is an operation thatallows the movement of coins from the ceased sidechain B to the original mainchain A. It isrepresented by a tuple of the following form:
def

CSW = (ledgerId, receiver, amount, nullif ier, proof data, proof ),where all parameters have the same meaning as in the case of the BTR.
7 Note that it is up to a sidechain construction to define exactly how BTRs are processed (for example, theLatus sidechain construction [5 The Latus Sidechain] introduces its own method for enforcing BTRs processing).

15

As it can be seen, BTR and CSW have the same structure, though conceptually they are
different because CSW performs direct payment while BTR does not. The interface of the
SNARK verifier for the CSW is completely the same as for the BTR.
Additionally, we discuss the role of nullifiers in both BTR and CSW. In the mainchain, anullifier is an abstract identifier of claimed coins. The mainchain will not allow the submissionof two transactions with the same nullifier. The main reason for having the nullifier is to prevent
repeated submission of BTRs or CSWs that try to withdraw the same coins (thus, essentiallydoing double spend). Since the mainchain does not maintain the sidechain state, at the very
least, for ceased sidechains, it requires some abstract double-spend prevention mechanism, whichis exactly what is provided by nullifiers.
Note that both BTR and CSW are just complementary operations to allow more flexibility
in some subtle use cases or in the case of a malfunctioning sidechain. It is up to the sidechain
to define how they are used. For instance, one can omit defining these operations at all (e.g.,
by setting vkBT R and vkCSW to NULL), thus completely relying on the normal withdrawal
procedure through withdrawal certificates.
4.1.2.2

Withdrawal Safeguard

The safeguard is a special feature introduced to prevent unlimited withdrawals from asidechain to the mainchain in the case of the malicious sidechain. The essence of the safeguard
function is to maintain the balance of each created sidechain and to prevent withdrawing anamount larger than what was previously transferred to that sidechain. A similar idea wasintroduced in [13] and [12].
Implementation of the safeguard feature is simple: for each created sidechain, a specialbalance variable is maintained by the mainchain. Each forward transfer increases the balance by
the transferred number of coins, and each withdrawal certificate, or ceased sidechain withdrawal
reduces the balance by the withdrawn amount. The WCert and CSW cannot withdraw morecoins than are stored in the sidechain balance.
This feature prevents possible implications of sidechain corruption. It guarantees that only
the transferred number of coins can be withdrawn back to the mainchain. Even in the case of
total corruption or a maliciously constructed sidechain, an adversary cannot mint coins out ofthin air.
4.1.3

Sidechain Transactions Commitment

So far, we defined 4 types of actions (that are either separate transactions or outputs in a regulartransaction) that determine cross-chain communication from the mainchain point of view:
1. Forward Transfer (FT).
2. Withdrawal Certificate (WCert).
3. Backward Transfer Request (BTR).
4. Ceased sidechain withdrawal (CSW).
To facilitate efficient implementation of the synchronization between the mainchain andsidechains, we modify the structure of a mainchain block header to include an additional valuethat commits to all sidechain-related actions in the MC block (except the CSW because it isused only when the SC is ceased). This value is a root hash of a Merkle tree that contains
16

all transactions or outputs related to any sidechain (see Fig. 4). We call it the Sidechain
Transactions Commitment (SCTxsCommitment).
SCTxsCommitment
h1

SC1Hash: h21 = H(h31 | h32 | SC1)SC2Hash

h21
h31

h32

FTHash

h24

….

….

….

BTRHashh41

FT1SC1SC4Hashh23

WCertHash

TxsHashh51

SC3Hash

h22

h42

….

….

WCertSC1h58
BTR4SC1

Figure 4: Sidechain transactions commitment tree. The root hash h1 commits to all sidechain
related transactions (for all sidechains) included in the MC block. All SCXHash, where X is a
sidechain identifier, are ordered by the id and commit to all transactions related to the sidechain
X. W CertHash commits to the WCert for the sidechain X (if present); only one WCert isallowed for each sidechain. T xsHash commits to FTs and BTRs.
Having SCT xsCommitment in the MC block header allows SC nodes to synchronize andverify SC-related transactions without the need to transmit the entire MC block. Also, it allows
the construction of a SNARK proving that all SC-related transactions of the specific MC block
have been processed correctly.

4.2

Bootstrapping Sidechains

We assume that the mainchain implements a special transaction that allows one to create asidechain. Such a transaction can be submitted by anyone, and it registers the SC in the
mainchain and sets its unique identifier and some system parameters. Once the sidechain iscreated, a schedule of withdrawal epochs is defined deterministically, and forward/backward
transfers must be processed in the mainchain.
The following set of SC parameters are set upon creation:

17

Sidechain configuration− a unique identifier of the sidechain that has not been used;− the block number in the mainchain, from which the firstwithdrawal epoch begins; this parameter defines when thesidechain becomes active;− the length of a withdrawal epoch (in MC blocks);
epoch lensubmit len− the period length – starting from the first block of thewithdrawal epoch – when a withdrawal certificate for theprevious epoch must be submitted to the mainchain;
wcert vk
− a SNARK verification key vkW Cert for WCert proofs;− a SNARK verification key vkBT R for BTR proofs;
btr vkcsw vk− a SNARK verification key vkCSW for CSW proofs;
wcert proof data − the definition of the proofdata structure for the withdrawal
certificate; it defines the number and types of included
data elements;
btr proof data − the definition of the proofdata structure for the BTR;
csw proof data − the definition of the proofdata structure for the CSW.
ledgerId
start block

Customizable parameters give flexibility in choosing those, which are suitable for a particularsidechain. The triplet (cer vk, btr vk, csw vk) is especially important as it defines how themainchain verifies backward communication from the sidechain. These keys define SNARKs forcorresponding operations eventually enabling different designs for sidechains.

5

The Latus Sidechain

In the previous section, we described the general sidechain design. Mostly, it was about defining
the cross-chain transfer protocol, which provides a communication interface with the mainchain.
In this section, we focus on a specific sidechain construction. We give an example of how adecentralized verifiable sidechain can be built on top of the given CCTP.
The general idea is to utilize a recursive composition of SNARKs to construct a succinct
proof of the sidechain state progression for the period of a withdrawal epoch. Then, a SNARK
for a withdrawal certificate is constructed so that it proves correct sidechain state transition
for the whole epoch and validates backward transfers. This allows the mainchain to efficiently
verify the sidechain without having to rely on any intermediary – such as certifiers [12] – andstill be oblivious to the sidechain construction and interactions within.
In this section, we provide details of the proposed Latus sidechain that implements decentralized permissionless blockchain BSC with a proof-of-stake based consensus protocol. We consider
BSC as a simple ledger of payment transactions. We assume that BSC does not possess its own
native asset and, instead, uses only Coin asset transferred from the mainchain by means of the
CCTP. Additionally, we assume that the mainchain is a classical proof-of-work based blockchain
system with Nakamoto consensus [20] (e.g., Horizen [26]).

5.1

Consensus Protocol

We use a similar consensus protocol as in our previous proposal [12] with some minor adjustments. It is based on a modified version of the Ouroboros proof-of-stake consensus protocol [17].

18In Ouroboros, time is divided into epochs with a predefined number of slots. Each slot is
assigned with a slot leader who is authorized to generate a block during this slot. Slot leadersof a particular epoch are chosen randomly before the epoch begins from the set of all sidechain
stakeholders (Fig. 5). The protocol operates in a synchronous environment where each slot
takes a specific amount of time (e.g., 20 seconds).
Epoch i-submitted block-

missed block

Epoch i+1

Figure 5: A general scheme of an epoch. Note that even though there is an assigned slot leader
for each slot, the leader may skip block generation, and in this case, the slot remains empty.
Epoch. An epoch is a sequence of the k successive slots Epi = (sli0 , sli1 , ..., slik−1 ), where kis the predefined length of the epoch and i is the epoch sequence number.
Slot. A slot is a specific period in time during which a slot leader is authorized to issue
a block. Each slot has the corresponding slot leader who is chosen randomly before the epoch
begins. A slot leader may skip generating a block, in this case, the following block will refer tothe latest generated block.
Slot Leader. The slot leader of the slot slij is a stakeholder who was authorized by the Slot
Leader Selection Procedure to forge a block at slot slij .
Slot Leader Selection Procedure. The slot leader selection procedure Select(SDEpi , rand)
is a procedure that selects all slot leaders of the epoch Epi according to the fixed stake distribution SDEpi and some random value rand. The stake distribution SDEpi is fixed before theepoch Epi begins. The randomness rand is revealed only after the stake distribution is fixed.
In our construction, we additionally introduce binding with the mainchain. This implies thatsidechain blocks contain references to mainchain blocks so that their history is preserved in thesidechain. The chain resolution algorithm is altered to enforce that the sidechain follows thelongest mainchain branch.
As a “mainchain block reference”, we consider a whole mainchain block header together withtransactions related to the referencing sidechain.
Sidechain block forgers are obliged to keep mainchain references consistent and ordered when
included in SC blocks. A sidechain block SBj can contain a reference to the mainchain block
Bi if and only if
1. the block Bi is a valid mainchain block, and2. references to all previous mainchain blocks Bk , k ∈ {η, η + 1, ..., i − 1} have been alreadyincluded in sidechain blocks (also considering the current one, as a sidechain block may
contain more than one reference), where η is the genesis reference (Fig. 6).
Even though it is not mandatory for the block forgers to include mainchain references, we
assume that honest block forgers will do this to support the cross-chain transfer protocol between
chains. It is also possible to construct an incentive mechanism for block forgers who include
references. For instance, users who initiate forward/backward transfers may pay some fee from
19

MC

SC

Figure 6: An example of the sidechain binding to the mainchain.
each transaction. The incentive mechanism is beyond the scope of the current paper as we only
provide an example of a sidechain consensus protocol.
The binding to the mainchain provides two important properties of our sidechain construction:
1. Deterministic synchronization between the MC and the SC. When the sidechain
block SBi refers to the mainchain block Bj , it explicitly acknowledges all transactions
included in the block Bj . It means that if Bj contains any transactions related to thissidechain (by transactions, we mean forward transfers and backward transfer requests),
such transactions are immediately included in the sidechain (see Fig. 7).
MC Block i
MC Block Header (MBHi)
mc_tx1MC->SC
mc_tx2MCSC Block j
SC Block Header
mc_tx1MC->SC

References to MC
blocksSynchronized txs
from MCsc_tx1SC
sc_tx2SC

Regular SC
transactions

MBHi

Figure 7: An example of transaction synchronization between the mainchain andthe sidechain: MC block Bi contains one SC-related transaction mc tx1M C→SC ,which is also included in the SC block SBj because it refers to Bi .
2. Mainchain forks resolution. It is known that Nakamoto consensus does not provide
finality on a chain of blocks [24]. It means that there is always a non-zero probability
that some sub-chain of MC blocks will be reverted and substituted by another sub-chain
with the more cumulative work. Such behaviour is normally handled by the mainchain
but may be disastrous for the sidechain because M C → SC transactions that are alreadyconfirmed in the sidechain may be reverted in the mainchain. The binding eliminates suchsituations because in the case of a fork in the MC, SC blocks that refer to forked blocks
in the MC would also be reverted.
Security. The standard procedure for proving blockchain consensus protocol security requires demonstrating the ability of the protocol to satisfy two fundamental properties of a
distributed ledger: liveness and persistence [11]. Liveness ensures that transactions broadcasted by honest parties will be eventually included in the ledger, and persistence ensures thatonce a transaction is confirmed by one honest node, it will also be confirmed by all other honest
20

nodes (so that eventually it becomes final and immutable). Such properties are usually provenunder certain assumptions, such as honest majority among protocol participants, etc. We refer
the interested readers to the original Ouroboros paper [17] for an exhaustive list of assumptions
and properties analysis.
Since the proposed consensus protocol also incorporates binding with the mainchain, it
implies an additional assumption of the honest hashing power majority in the mainchain.
We suppose that under these assumptions the proposed protocol derives security guarantees
provided by original Ouroboros and Nakamoto consensus protocols.
We want to emphasize that different types of sidechains may adopt different consensus protocols
that better suit specific use cases (e.g., fast coin transferring support). A sidechain consensus
protocol (including the one described in this section) is not the focus of this research and needs
further analysis.
5.1.1

Withdrawal Epochs

As it has been described in section [4.1.2 Backward Transfers], the Cross-Chain Transfer Protocol
introduces the notion of a withdrawal epoch8 (WE), which is defined as a fixed-length rangeof MC blocks (length is set upon SC creation). The concept of withdrawal epochs is essential
for commanding backward transfers.
Following this design, we also introduce withdrawal epochs in a sidechain which coincidewith the mainchain withdrawal epochs. A WE is defined as a range of SC blocks where the firstand last blocks of the range are determined by references to the first and last MC blocks in thecorresponding withdrawal epoch in the MC (see Fig. 8).
Withdrawal epoch N
MCSC

Withdrawal epoch N

Figure 8: An example of a withdrawal epoch in the sidechain.
Even though a withdrawal epoch in the SC may have variable length (as it depends on whencorresponding MC blocks will be referenced), the binding between chains allows to deterministically define the boundaries of the WE in the sidechain.
More formally, if the withdrawal epoch W EiM C of size len in the MC is defined by a sequenceof blocks W EiM C = (Bi0 , Bi1 , ..., Bilen−1 ), then the corresponding withdrawal epoch in the SC
can be determined as:
W EiSC = (SBi0 , SBi1 , ..., SBik ),where:
len−1n– SBi0 is an immediate descendant of the block SBi−1
which refers to the MC block Bi−1
MC(the last one in the withdrawal epoch W Ei−1 ); and– SBik is the block that refers to Bilen−1 .
8 Note that withdrawal epochs are independent from epochs in the Ouroboros consensus protocol.

21Note that to simplify implementation, it might be needed to restrict SC blocks to not referto several MC blocks on the boundaries of the withdrawal epoch (i.e., if the SC block refers to0
Bilen−1 it cannot also refer to the next MC block Bi+1).
It is important to restate that the notion of the withdrawal epoch is independent from epochsin the Ouroboros consensus protocol.

5.2

Accounting Model and System StateThe Latus blockchain adopts the UTXO-based accounting model [21] where the state is represented by a set of unspent outputs combined into a fixed-size Merkle tree (see Fig. 9). We callsuch a tree a Merkle State Tree (MST). Lowercase mstt stands to denote the root hash of
the M STt tree at the moment t.
The depth DM ST of the MST tree is a fixed system parameter that also constrains the total
number of UTXOs that can exist in the system to be at most 2DM ST (see Fig. 9).
We consider each leaf of the MST as a UTXO slot that can be “occupied ” or “empty” at agiven moment. We introduce the deterministic function M ST P osition(utxoi ) that returns the
position of some unspent output utxoi if it is included in the tree. Note that the utxo position
does not depend on the current state of the MST.
mst

h21

h22
h32

h31

h33

h34

h41= H(utxo1)

h48= H(Null)

h41

h42

h43

h44

h45

h46

h47

h48

utxo1

∅

∅

∅

utxo2

∅

utxo3

∅

Figure 9: An example of the Merkle State Tree with DM ST = 3. A leaf of the tree is either anunspent output or N ull value. The tree contains 3 occupied and 5 empty slots. The function
M ST P osition returns the position of a given utxo in the tree, e.g., M ST P osition(utxo2 ) = 4.
The unspent transaction output (UTXO) is defined as a tuple (addr, amount, nonce) where• addr is an address of the UTXO owner who possesses the corresponding private key
that allows to spent it;• amount is the number of coins secured by the UTXO; and• nonce is a unique identifier of the UTXO.
5.2.1

System State

Provided with the MST structure, which is the core of a sidechain state, we define an overall
SC system state at the moment t as a tuple:
defstatet = (M STt , backward transf erst ),where backward transf ers is a list of backward transfers initiated in the current withdrawal
epoch. backward transf ers is transient and reset every new withdrawal epoch.

22

5.3

Transactional Model

There are 4 types of transactions defined in the Latus sidechain that realize basic payment
functionality and cross-chain transfer protocol. To simplify the model, we consider them aslogical transactions, though we stress that a real-world implementation can be optimized sothat a single transaction on the blockchain may combine several logical transactions (even withdifferent types).
The transactions are the following:
1. Payment (PTx) – transfers coins within the sidechain.
2. Backward Transfer (BTTx) – initiates transfer of coins from the SC to the MC.
3. Forward Transfers (FTTx) - receives coins transferred from the mainchain.
4. Backward Transfer Requests (BTRTx) - initiates coin transfer from the SC to the
MC. In contrast to BTTx, BTRTx contains BTRs initially submitted in the mainchain
and then synchronized to the SC.
Whereas PTx and BTTx are inherently SC-defined transactions (thus, submitted and processed in the sidechain), FTTx and BTRTx are MC-defined transactions (they encapsulate
FTs and BTRs that are initially submitted to the MC). We describe each type in detail in thefollowing sections.
5.3.1

Payment Transaction

We define a regular payment as a multi-input multi-output transaction [29]:type PaymentTx {inputs: List [UTXO];
signatures : List [Signature ];outputs: List [UTXO];}
where:
1. inputs are some unspent outputs from previous transactions, spending of which are authorized by signatures, and2. the total coin’s value of inputs is equal or greater than the total coin’s value of outputs.
The state transition function update for the payment transaction is defined in the following
way:statei+1 = update(txpay , statei ),where statei+1 [backward transf ers] is unchanged and statei+1 [M ST ] is derived from statei [M ST ]by
1. removing all UTXOs that are inputs in txpay and substituting them with N ull to produce
M STi− ; and2. sequentially adding to M STi− all UTXOs that are outputs in txpay according to
M ST P osition(utxoj ).

23

5.3.2

Forward Transfers Transaction

Forward transfers allow one to send coins from the mainchain to a sidechain. As such, FTs
are first submitted to the MC and processed there (destroying coins) and then, by means ofdeterministic synchronization, are included and processed in the sidechain. Recall from [4.1.1
Forward Transfers] the basic structure of a forward transfer on the mainchain side:def

F T = (ledgerId, receiverM etadata, amount).
receiverM etadata is defined by the sidechain construction and in Latus it is just a receiveraddress and a payback address on the MC needed in case of transfer failure:def

receiversM etadata = (receiverAddr, paybackAddr).
A single MC block may contain several forward transfers related to different sidechains.
The sidechain will synchronize FTs present in the referenced MC block by including a special
F orwardT ransf ers transaction (FTTx) in the SC block. Such FTTx specifies all forward
transfers from the referenced MC block that are related to this specific sidechain. From thesidechain perspective, we can consider FTTx as a coinbase transaction (the one that creates
new coins [28]) that is authorized by the mainchain.
We assume that a particular forward transfer may fail so that coins cannot be received by
the sidechain. In this case, coins are sent back to the mainchain by creating a corresponding
backward transfer. It is done automatically upon FTTx execution in the sidechain.
The reasons for FT failure can be different. For instance, FT’s receiverM etadata may bemalformed (recall that the MC does not validate semantics of FT’s receiverM etadata) or someother sidechain-specific failures occur (e.g., it may happen that M ST P osition(outputnew ) maps
newly created output to an already occupied slot in M STi , thus causing a collision).
The basic structure of the ForwardTransfers transaction is the following:type ForwardTransfersTx (mcid: BlockID, ft: List[FT]) {outputs: List [UTXO];
rejectedTransfers : List [BackwardTransfer]}where:− an identifier of the MC block whose forward transfers aresynchronized;ft− a list of forward transfers from the MC block mcid related to thesidechain where FTTx occurs;
outputs− outputs created for the transferred coins; each valid forward transfer
spawns a corresponding output with the same amount of coins;rejectedT ransf ers − a list of backward transfers for failed forward transfers; each failed
forward transfer spawns a corresponding backward transfer with thesame amount of coins.
mcid

The state transition function update for the FTTx is defined in the following way:statei+1 = update(txF T , statei ),24where:1. statei+1 [M ST ] is derived from statei [M ST ] by sequentially adding all UTXOs that are
outputs in txF T according to M ST P osition(utxoj );2. statei+1 [backward transf ers] is derived from statei [backward transf ers] by appending
rejectedT ransf ers from txF T .
Note that failed forward transfers are recovered with the backward transfer mechanism
through a withdrawal certificate at the end of the epoch. Recall that the MC knows nothing
about the SC state and cannot know that an FT is failed; thus, we use the standard mechanism
to reclaim coins in the MC.
5.3.3

Backward Transfer Transaction

A backward transfer transaction (BTTx) allows one to create a request for a backward transfer
in the sidechain that will be included in the next withdrawal certificate and then passed andprocessed in the mainchain.
type BackwardTransferTx {inputs: List [UTXO];
signatures : List [Signature ];backwardTransfers: List[BackwardTransfer];}
where:
1. inputs are some unspent outputs from previous transactions (spending of which is authorized by signatures);
2. backwardTransfers are data about receivers of coins on the mainchain side; recall from
[4.1.2 Backward Transfers] that the basic structure of a backward transfer isdef

BT = (receiverAddr, amount);
3. the total coin value of inputs is equal or greater to the total coin value of backwardTransfers.
The state transition function update for a backward transfer transaction is defined as:statei+1 = update(txBT , statei ),where:
1. statei+1 [M ST ] is derived from statei [M ST ] by removing all UTXOs that are inputs in
txBT ; and2. statei+1 [backward transf ers] is derived from statei [backward transf ers] by appending
backwardT ransf ers from txBT .
Essentially, we can consider backwardT ransf ers in txBT as specialized outputs that areunspendable on the sidechain but used to reclaim coins in the mainchain (when transferred bymeans of a withdrawal certificate). In this respect, BTTx transaction is a special case of regular
payment transaction where all outputs are backward transfers.
More details about the entire backward transfer flow can be found in [5.5.3 Backward Transfers].

25

5.3.4

Backward Transfer Requests Transaction

The Backward Transfer Request (BTR), which is submitted to the MC, is similar to BTTx in
the sense that it allows one to create a request that will result in a backward transfer in the next
withdrawal certificate if the request is legitimate (e.g., claimed coins were present at the momentof BTR inclusion in the SC block). The difference from BTTx is that BTR is submitted in the
mainchain and is used in situations when BTTx cannot be used for some reason. Recall from
[4.1.2.1 Mainchain Managed Withdrawals] the basic structure of the BTR on the mainchain
side:
def

BT R = (ledgerId, receiver, amount, proof data, proof ).
proofdata and SNARK proof are defined by sidechain construction. In Latus, proofdata
contains an unspent output that should be consumed in the SC to provide coins for transferring:
proof data = {utxo}.
The spending right for the utxo should be enforced by the proof which is validated upon
submission in the MC.
Similar to forward transfers, a single MC block may contain several BTRs. The sidechain
synchronizes BTRs by including in the SC block a special BackwardTransferRequests transaction(BTRTx) that contains all BTRs relevant to this sidechain from the referenced MC block. Froma sidechain perspective, we can consider BTRTx as an aggregated transaction where each BTR
represents a separate backward transfer.
Some BTRs from BTRTx may be invalid when they are synced to the sidechain (e.g., amalicious user may try to spend the same utxo directly in the sidechain before BTR is synced(double-spend problem). Such BTRs are rejected by the sidechain (rejection means that they
do not spawn corresponding backward transfers and do not affect the state).
The basic BTRTx structure on the SC side is the following:type BackwardTransferRequestsTx (mcid: BlockId, btr: List[BTR]) {inputs: List [UTXO];
backwardTransfers: List[BackwardTransfer];}
where:− an identifier of the MC block whose BTRs are synchronized;− a list of backward transfer requests from the MC block mcid related
to this sidechain;
inputs− a combined list of UTXOs derived from btr.proof data of each valid
BTR;
backwardT ransf ers − a list of backward transfers for valid BTRs.

mcid
btr

The state transition function update for a BTRTx transaction is:statei+1 = update(txBT R , statei ),where:
1. statei+1 [M ST ] is derived from statei [M ST ] by removing all UTXOs that are inputs in txBT R ;2. statei+1 [backward transf ers] is derived from statei [backward transf ers] by appending
backwardT ransf ers from txBT R .
Note that correct processing of BTRs in the sidechain is to be enforced by a withdrawal
certificate SNARK proof.
26

5.4

State Transition ProofIn [5.3 Transactional Model], we defined four types of transactions that represent basic statetransitions in our sidechain system. Given that all transactions are applied sequentially in anorder defined by blocks containing them, we can consider a merged state transition for a sequenceof transactions from several blocks:
statei+k = update([tx1 , ..., txk ], statei ) = update(txk , update(txk−1 , .....update(tx1 , statei )).
In particular, we are interested in merging transitions for the whole withdrawal epoch andproving that the top-level merged transition is correct. It can be accomplished using the recursive
SNARKs composition for state transitions defined in [Def. 2.5].
The main idea is to construct a single SNARK proof of transition for the whole withdrawal
epoch which then can be attached to a withdrawal certificate proving to the mainchain the validity of everything that has happened in the sidechain – including certificate backward transfers –without actually revealing any details except state snapshots (in a form of simple hashes) before
and after transition.
We do not go deeply into the details of the SNARKs architecture which is quite sophisticatedin this case and requires separate writing to be properly explained; instead, we are going toprovide the basic idea of constructing such proof and how it is going to be used.
Let us denote by si = H(statei ) the hash value that represents statei . Note that it must be
an efficient hashing procedure as it should be implemented for a SNARK arithmetic constraint
system. For instance, we can consider H(·) as a root hash of a Merkle tree that contains all thedata from statei .
Let us assume that for each basic state transition (represented by txpay , txF T , txBT , andtxBT R ) we have a corresponding Base SNARK [Def. 2.5] which proves the correct state transition for a single txa , a ∈ {pay, F T, BT, BT R}:
πaBase ← P rove(pkaBase , (si , si+1 ), (txa )),true/f alse ← V erif y(vkaBase , (si , si+1 ), πaBase ).
Also, let us assume that we have a Merge SNARK which takes two proofs of adjacent statetransitions (Base or Merge) and combines them into a single proof:π M erge ← P rove(pk M erge , (si , si+k ), (si+j , π1b , π2c )),true/f alse ← V erif y(vk M erge , (si , si+k ), π M erge ).
where:• b, c ∈ {Base, M erge};• π1b proves that there exist such tx1 , ..., txj so that statei+j = update([tx1 , ..., txj ], statei );• π2c proves that there exist such txj+1 , ..., txk so that statei+k = update([txj+1 , ..., txk ], statei+j ).
Provided with this construction, we can recursively build a single SNARK proof of statetransition for a whole withdrawal epoch from the sequence of basic transitions. This process isvisualized in figures 10 and 11.
Figure 10 demonstrates the recursive construction of a state transition proof for a single
sidechain block. Note that the scheme is simplified; in reality, the SNARKs composition is moresophisticated and the proof itself attests not only for the correctness of basic transitions but also
for the validity of the SC block, the validity of included MC block references, their contiguity,etc.
27

Sidechain block SCi0
MBi0 referencetxFT

base_proof(statej -> statej+1)

txBTR

base_proof(statej+1 -> statej+2)

merge_proof(statej -> statej+2)
merge_proof(statej -> statej+4)

MBi1 referencetxFT

base_proof(statej+2 -> statej+3)txBTR

base_proof(statej+3 -> statej+4)

Regular SC transactions:

txpay

base_proof(statej+4 -> statej+5)
base_proof(statej+5 -> statej+6)

txpay

merge_proof(statej+2 -> statej+4)

merge_proof(statej+4 -> statej+7)
merge_proof(statej+4 -> statej+7)

base_proof(statej+6 -> statej+7)

txBT

merge_proof(statej -> statej+7)

Figure 10: Recursive composition of state transition proofs for the whole SC block. At thebottom level, there are proofs for basic transitions (represented by transactions included in theblock) which are then recursively merged into a single proof.
Figure 11 demonstrates the recursive construction of a state transition proof for an entire
withdrawal epoch. Provided with the proofs of state transitions for blocks from the previous
step, now they are merged to generate a single proof for the whole epoch which is used toconstruct a final proof for a withdrawal certificate.
In a nutshell, each withdrawal certificate W Certi for epoch i commits to the new state
stateilen produced by applying all blocks belonging to epoch i and proves correct transition fromthe statei−1
len committed by the previous withdrawal certificate. This also involves proving thatall MC blocks belonging to the withdrawal epoch are referenced and all MC transactions related
to this sidechain are processed. As forward and backward transfers are among basic transitions
they will also be proven.
merge_proof(statei-1len->stateilen)
merge_proof(statei-1len->statei1)

Initial statei-1lenmerge_proof(statei2->stateilen)
Final stateilen

base_proof(statei-1len->statei0)

base_proof(statei0->statei1)

base_proof(statei1->statei2)

SBi0

SBi1

SBi2

base_proof(stateilen-1->stateilen)
SBilenWithdrawal epoch i

Figure 11: Recursive composition of state transition proofs for the whole withdrawal epoch.
State transitions for SC blocks are considered as base transitions though they themselves arerecursively constructed from basic transitions (see Fig. 10).
Again, we stress that this description is greatly simplified just to show the basic idea ofrecursive SNARKs composition for state transitions.
28

5.4.1

Performance and Incentives

Generating a SNARK proof for each basic transition and then merging them together requires
a significant amount of computation. This task cannot be solely levied upon forgers or WCert
issuers. Currently, we are investigating different approaches.
One of the possible solutions is to introduce a special dispatching scheme that assigns generation of proofs randomly to interested parties who then do these tasks in parallel and submit
generated proofs to the blockchain. An incentive scheme provides a reward for each valid submission.
We consider this as a separate topic of research which we do not elaborate in this paper.

5.5

Cross-Chain Transfer Protocol

In the previous sections, we described the consensus protocol, accounting model, and transactional model of the proposed sidechain construction. In this section, we will focus on the
structure of the cross-chain transfer protocol on the sidechain side which is based on thosecomponents.
5.5.1

Mainchain Block Reference

In [5.1 Consensus Protocol], we briefly described the synchronization procedure between the
mainchain and sidechain, which relies on MC block referencing. Here, we describe the reference
structure in a more detailed way.
Recall that an MC block header contains the SCTxsCommitment [4.1.3 Sidechain Transactions Commitment] field that commits to all SC-related transactions/outputs in that block:
type MCBlockHeader {prevBlock: BlockId
height: Int...
scTxsCommitment: Hash...
}
ScTxsCommitment is a root hash of a Merkle tree where one of the subtrees is the Merkle
tree of transactions related to the sidechain that referenced the block (see Fig. 12).
The structure of the mainchain block reference is the following:type MCBlockReference {header: MCBlockHeader
mproof: Option[MerkleProof]
proofOfNoData: Option[MerkleProof[]]forwardTransfers: Option[FTTx]
btRequests: Option[BTRTx]
wcert: Option[WCert]}

29

SCTxsCommitment
h1
h22

h21
SC1HashSC2Hash

h31
h41

h42

h34

….

….

….

BTRHashFTHashh51

FT1SC1SC4Hashh33

WCertHash

TxsHashh

SC3Hash

h32

h52

….

….

h
BTR4SC1

Figure 12: An example of the sidechain transactions commitment tree. One of the intermediate
nodes (SC1Hash) is a root hash of the subtree that commits to all transactions related to thesidechain SC1.
where:− a header of the MC block that is referenced;− optional field: in case the MC block includes at least one transaction
related to this SC, mproof will contain a Merkle proof [Def. 2.2] forthe intermediate node in the sidechain transactions commitment treethat is a root of a subtree of transactions related to this sidechain (bythe example in Fig. 12: the subtree root for the sidechain SC1 is h31
and the corresponding Merkle proof is the tuple of nodes {h32 , h22 });in case the MC block has no transactions related to this SC, themproof must be N ull;
proof Of N oData − optional field: in case the MC block has no transactions related tothis SC, proof Of N oData contains the Merkle proof(s) necessary toprove that this ledgerId was not part of the SCT xsCommitmenttree;
f orwardT ransf ers − optional field: it is either a ForwardTransfers transaction [5.3.2
Forward Transfers Transaction] (if the MC block contains at least
one forward transfer to this sidechain) or otherwise N ull;btRequests− optional field: it is either a BackwardTransferRequests transaction[5.3.4 Backward Transfer Requests Transaction] (in case the MC
block contains at least one backward transfer request to thissidechain) or otherwise N ull;
wcert
− optional field: it is either a withdrawal certificate (in case the MC
block contains the withdrawal certificate related to this sidechain) orotherwise N ull.
headermproofProvided with mproof, forwardTransfers, btRequests, and wcert fields, the SCT xsCommitment
can be reconstructed and verified against the scTxsCommitment field included in the MC block30

header. It allows to verify that all SC-related transactions were correctly synchronized from
the MC block without the need to download and verify its body. Moreover, we can construct
a SNARK proving that the MC block reference has been correctly processed and that all SCrelated transactions have been applied – it is an essential part of constructing a state transition
proof for a withdrawal epoch [5.4 State Transition Proof].
5.5.2

Forward Transfers

In [4.1.1 Forward Transfers] and [5.3.2 Forward Transfers Transaction], we have already discussed
most of the details related to the forward transfer design both on the mainchain and sidechainsides. Here we combine everything.
In general, it looks as follows: an MC to SC transfer is represented by a pair of transactions
which we can consider as “sending” and “receiving”. “Sending” is done on the mainchain side
by means of the forward transfer defined in [4.1.1 Forward Transfers] and “receiving” is doneon the sidechain side by means of aggregated ForwardTransfers transaction defined in [5.3.2
Forward Transfers Transaction]. While “sending” destroys coins in the mainchain, “receiving”
creates the corresponding number of coins in the sidechain.
Forward transfers submitted to the mainchain become available in the sidechain at the
moment the MC block containing them is referenced in the sidechain (see Fig. 13). With theMC block reference [5.5.1 Mainchain Block Reference], a ForwardTransfers transaction (FTTx)
is included in the SC block (if there are any FTs).
Forward Transfer = (ledgerid, receiverMetadata, amount)

MC

SC

FT

FTTx

Figure 13: Forward transfers syncing from the mainchain to the sidechain.
The consistency of forward transfers included in a sidechain FTTx is verified by recalculating
the FTHash (Fig. 12) and checking the SCTxsCommitment following the procedure describedin [5.5.1 Mainchain Block Reference].
5.5.3

Backward Transfers

In general, backward transfer is a transfer of coins in the opposite direction: from the sidechain
to the mainchain. This operation is more sophisticated and thus requires several sub-protocols
to provide sufficient security and reliability.
There are three ways to withdraw coins from the sidechain to the mainchain:
1. Regular withdrawal is a standard mechanism that is used under normal conditions. It
implies the usage of a backward transfer transaction [5.3.3 Backward Transfer Transaction] and a withdrawal certificate to transfer coins to the mainchain.
2. Backward transfer request is similar to the regular withdrawal with that difference
that it is initially submitted to the mainchain [4.1.2.1 Mainchain Managed Withdrawals]
and then synchronized to the sidechain by means of [5.3.4 Backward Transfer Requests
Transaction]. The coins are transferred to the mainchain with a withdrawal certificate.
31

3. Ceased sidechain withdrawal is a mechanism that is used when the sidechain is
no longer operating. This type of withdrawal does not use withdrawal certificates andsupposes direct handling by the mainchain.
The first two types of withdrawals (regular and BTR) use the standard mechanism for
backward transfers - withdrawal certificate. Most of the details related to their submission
and processing have already been discussed in [4.1.2.1 Mainchain Managed Withdrawals], [5.3.3
Backward Transfer Transaction], and [5.3.4 Backward Transfer Requests Transaction]. The
basic principle is summarized in figure 14.
WCert

BTR

MC

includes backward transfersfrom both BTRTx and BTTx

BTR

SC

BTTx

BTRTx

Figure 14: Withdrawing coins with BT and BTR transactions.
BT

Regular withdrawal. A special BackwardTransfer transaction is submitted to the sidechain
by a user who wants to transfer coins. This transaction destroys coins in the sidechain. At theend of the withdrawal epoch, all backward transfers are collected in a withdrawal certificate
which is submitted to the mainchain where it is processed, and the corresponding number ofcoins is created in the mainchain.
Backward transfer request. BTRs are submitted to the mainchain and synchronized
to the sidechain by means of a BackwardTransferRequests transaction (analogously to forward
transfers). The consistency of BTRs included in the sidechain is verified by recalculating the
BTRHash (Fig. 12) and checking its presence in the SCTxsCommitment tree following theprocedure described in [5.5.1 Mainchain Block Reference]. After the BTR is synchronized tothe sidechain, it is processed as regular withdrawal through a withdrawal certificate.
In the following sections, we will discuss more deeply the structure and generation of a withdrawal certificate and BTR. We will also separately discuss CSW as it is conceptually different
from the first two withdrawal methods.
5.5.3.1

Withdrawal Certificate

Withdrawal certificate is a pivotal component of the backward transfer flow. Recall the basic
structure of a withdrawal certificate that is defined by the mainchain [4.1.2 Backward Transfers]:
def

W Cert = (ledgerId, epochId, quality, BT List, proof data, proof ).
While ledgerId and epochId are global parameters known to the mainchain, the semantics ofquality, proofdata, and proof are defined by the sidechain. The withdrawal certificate is createdonce per a withdrawal epoch and includes all backward transfers that have been submitted during the epoch.
Quality. The quality parameter is used by the mainchain to determine what WCert should be32

adopted in case several have been submitted for the same epoch. From the MC side, this is justan integer value which can be compared with quantities from other certificates. In the Latus
sidechain, we define the quality to be the height of the blockchain up until which the WCert
proves state transition.
Backward Transfers List. BTList is a list of backward transfers collected during a withdrawal epoch for which the certificate is created:
BT List = statei [backward transf ers],
where statei is the state of the sidechain after applying the last block in the withdrawal epoch.
Withdrawal certificate proof
Withdrawal certificate proof is a SNARK proof that validates compliance of the certificate
with a set of predefined rules.
As it is defined in [Def. 2.3], a SNARK is a proving system. Its particular instantiationis specified by a set of arithmetic constraints defining the verification rules. Each sidechain
specifies its own set of constraints for the withdrawal certificate SNARK, thus establishing its
own rules.
The basic interface for the SNARK prover and verifier is the following:
proof ← P rove(pkW Cert , public input, witness),true/f alse ← V erif y(vkW Cert , public input, proof ).
A particular instantiation of the SNARK proving system is determined by a pair of keys
– proving key pkW Cert and verifying key vkW Cert . Verifying key is registered upon sidechain
creation and cannot be changed during the SC lifetime. It completely defines the rules of thewithdrawal certificate validation (including the semantics of the public input and witness forthe prover and verifier).
Recall from [Def. 4.4] that public input for the WCert SNARK is comprised of two parts:defpublic input = (wcert sysdata, M H(proof data)),where wcert sysdata is a set of arguments enforced directly by the mainchain9 :
def

i−1
i
wcert sysdata = (quality, M T Hash(BT List), H(Blen), H(Blen));

and proof data is a set of arguments defined by the sidechain construction and passed along thewithdrawal certificate. In the Latus sidechain, it is defined as follows:defii
proof data = (H(SBlast), H(stateSBlast[M ST ]), mst delta),

wherei
H(SBlast)− a hash of the last sidechain block in the epoch i for which thecertificate is created;ii
H(stateSBlast[M ST ]) − a root hash of the MST tree derived after applying SBlast; noteithat by including H(stateSBlast[M ST ]) in proof data, thewithdrawal certificate commits to the updated sidechain state;
mst delta− a bit vector of MST modifications; given that the MST is a fixed
size Merkle tree, mst delta is also a fixed-size bit vector where each
bit represents a particular leaf in the tree; the bit is set to “1” if the
MST leaf has been modified at least once during the epoch,otherwise it is “0” (see example in [Appendix A]).
9 These arguments are explained in [4.1.2 Backward Transfers]

33

mst delta is used for proving that some utxo has not been spent since some moment in
the past (this is particularly useful for preventing data availability attacks as it allows creating
mainchain managed withdrawals without knowing the current sidechain state). E.g., to provethis, one would need to provide a utxo together with a Merkle proof of its inclusion in somestateSB k [M ST ] committed in one of the previous certificates and a list of mst delta’s fromlast
the following certificates where the corresponding bit has not been triggered to “1”.
In the Latus sidechain construction, a withdrawal certificate proof enforces the following rules:
WCert SNARK Statementi• SBlast
is the last block of the withdrawal epoch i for which the certificate is created.
i−1
i• SBlast
is connected to the SBlast
from the previous withdrawal certificate by avalid chain of blocks.
ii• H(stateSBlast[M ST ]) is a valid root of the MST for stateSBlast.

i−1• Assuming that after applying the block SBlast
the sidechain state is stateSB i−1 and
last

i
i
after the block SBlast
the state is stateSBlast, the proof verifies correct transitionifrom stateSB i−1 to stateSBlast
which means that all transactions from the subchain
lasti[SB0i , ..., SBlast] are correctly processed according to the rules from [5.3 Transactional Model].
i• MC blocks from range [B0i , ..., Blast] are referenced from the sidechain blocksii[SB0 , ..., SBlast ] (this also implies that all SC-related transactions from these blocks
have been processed).

• BT List is a valid list ofistateSBlast[backward transf ers].

backwardtransfers

thatcorresponds

toi.
• quality parameter is the height of the block SBlast• mst delta is a bit vector that reflects changes in MST between stateSB i−1 [M ST ]lastiand stateSBlast[M ST ].
In general, a withdrawal certificate proof validates correct transition for a range of blocks
that belongs to the withdrawal epoch and that this range is adjacent to the range committed in
the previous withdrawal certificate. This includes proving the correctness of backward transfers.
Given that all state transitions are proved, it becomes infeasible to create a malicious backward transfer (without creating a corresponding transaction in the sidechain), and it is infeasible
to create new coins on the sidechains without real forward transfers.
5.5.3.2

Backward Transfer Request

In [5.3.4 Backward Transfer Requests Transaction], we have already discussed how BTRs
are submitted and processed in the sidechain. Here, we only provide details about the SNARK
proof included in a BTR.
Recall that the BTR structure has been defined as follows [Def. 4.5]:
def

BT R = (ledgerId, receiver, amount, nullif ier, proof data, proof ).

34

proof data is defined by the Latus construction as:
proof data = {utxo},
where utxo is an unspent output that holds coins that a user wants to withdraw. The basic
idea is that the proof should validate the user’s right to withdraw this utxo and that this utxo
is present in the sidechain state MST committed by the last withdrawal certificate included in
the mainchain.
Note that the BTR SNARK proof is validated by the mainchain upon BTR submission.
Even though it verifies that the withdrawn utxo has been present in the last committed SC
state, it cannot guarantee that it will remain valid at the moment BTR will be synchronized
to the sidechain. This proof serves more like a pre-validation for the BTR in the mainchain to
impede submission of wittingly invalid requests.
The basic interface for the SNARK prover and verifier is the following [Def. 4.5]:
proof ← P rove(pkBT R , public input, witness),true/f alse ← V erif y(vkBT R , public input, proof ).
The verifying key vkBT R is registered upon sidechain creation. It defines the rules of the
BTR validation (including the semantics of the public input and witness for the prover andverifier).
The public input comprises two parts [Def. 4.5]:
defpublic input = (btr sysdata, M H(proof data)),def

btr sysdata = (H(Bw ), nullif ier, receiver, amount)),
where H(Bw ) is the hash of the MC block with the latest withdrawal certificate (at the moment
when BTR is included in the mainchain), receiver, amount, and nullif ier are taken from the
BTR itself. Note that btr sysdata is enforced by the mainchain so its parameters cannot be
manipulated by the BTR issuer.
A BTR proof enforces the following rules:
BTR SNARK Statement• H(Bw ) is the hash of the mainchain block where the last certificate W Certw has
been submitted for this sidechain.
• utxo ∈ statew [M ST ], where statew [M ST ] has been committed in W Certw .
• The BTR issuer has rights to spend this utxo (i.e., possesses the corresponding
private key).
• amount is equal to the utxo.amount.
• nullif ier is the hash of the utxo.
• receiver is the address of the receiver in the mainchain.

5.5.3.3

Ceased Sidechain Withdrawal

CSWs are used to allow sidechain stakeholders to withdraw coins from a ceased sidechain.

35

As it has been defined in [Def. 4.6], a ceased sidechain withdrawal is submitted to themainchain as a special transaction and performs a direct payment in the mainchain. Recall thebasic structure of the ceased sidechain withdrawal that is defined by the mainchain [Def. 4.6]:
def

CSW = (ledgerId, receiver, amount, nullif ier, proof data, proof ).
The main prerequisite for CSW validity is the existence of the claimed coins in the sidechain
state committed by the last withdrawal certificate. A sidechain user should point to the specificiunspent output from stateSBlast[M ST ] and authorize its spending. Basically, it is the same
SNARK that is used for the BTR [5.5.3.2 Backward Transfer Request]; the difference is that
now it authorizes direct payment in the mainchain, whereas in the BTR, it is essentially a
pre-validation.
We will not dive deeply into the SNARK construction for the CSW as technically it iscompletely the same as for the BTR.
In general, the CSW proof validates that a submitter owns the utxo with a particular amountof coins at the moment of the sidechain halt. Also, it enforces a nullifier which is a unique
identifier of the withdrawn utxo. Nullifiers are tracked by the mainchain to prevent withdrawalof the same coins twice.

6

Conclusions

The concept of sidechains has been acknowledged as an appealing solution for enhancing existing blockchain systems. It allows creating platforms and applications that are bound to themainchain without imposing significant burden. Yet, we have not seen wide adoption of thisconcept. We believe that the value of sidechains as a scalability solution is underestimated andseek to develop this area.
In this paper, we introduced Zendoo, a universal construction for blockchain systems thatenables the creation and communication with different sidechains without knowing their internal
structure. We also provided a specific sidechain construction, Latus, that leverages zk-SNARK
techniques to establish decentralized and verifiable cross-chain transfers.
We consider this as a research paper whose subject is still under ongoing research. In future
publications, we plan to uncover more details about specific components and properties of the
proposed sidechain construction.

7

Acknowledgments

We would like to express great appreciation to Maurizio Binello and Andrey Sobol for participating in technical discussions.
We would also like to thank Rob Viglione, Daniele Di Benedetto, Marcelo Kaihara, Luca
Cermelli, and Lyudmila Kovalchuk for reviewing and providing valuable comments.

References[1] Cosmos network, 2018. https://cosmos.network/docs/.
[2] Ethereum. a next-generation smart contract and decentralized application platform., 2018.
https://github.com/ethereum/wiki/wiki/White-Paper.

36[3] Rootstock: smart contracts on bitcoin network, 2018. https://www.rsk.co/.
[4] Andreas M. Antonopoulos. Mastering bitcoin (second edition). O’Reilly Media, Inc., 2017.
[5] A. Back, M. Corallo, L. Dashjr, M. Friedenbach, G. Maxwell, A. Miller, A. Poelstra,J. Timón, and P. Wuille. Enabling blockchain innovations with pegged sidechains, 2014.
https://blockstream.com/sidechains.pdf.
[6] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct noninteractive zero knowledge for a von neumann architecture. Cryptology ePrint Archive,
Report 2013/879, 2013.
[7] Sean Bowe and Ariel Gabizon. Making groth’s zk-snark simulation extractable in the
random oracle model. IACR Cryptology ePrint Archive, 2018:187, 2018.
[8] Sean Bowe, Jack Grigg, and Daira Hopwood. Halo: Recursive proof composition without
a trusted setup. Cryptology ePrint Archive, Report 2019/1021, 2019. https://eprint.
iacr.org/2019/1021.
[9] J. Dilley, A. Poelstra, and J. Wilkins. Strong federations: An interoperable blockchain
solution to centralized third party risks. arXiv:1612.05491, 2016. https://arxiv.org/
abs/1612.05491.
[10] Croman K. et al., editor. On Scaling Decentralized Blockchains, volume 9604 of Financial
Cryptography and Data Security, Lecture Notes in Computer Science. Springer, 07 2016.
[11] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. Advances in Cryptology - EUROCRYPT 2015. Lecture Notes in
Computer Science, vol 9057. Springer, Berlin, Heidelberg, 2015.
[12] Alberto Garoffolo and Robert Viglione. Sidechains: Decoupled consensus between chains.
arXiv:1812.05441, 2018. https://arxiv.org/abs/1812.05441.
[13] P. Gazi, A. Kiayias, and D. Zindros. Proof-of-stake sidechains. Proceedings of the IEEE
Symposium on Security & Privacy. IEEE Computer Society Press, 2019.
[14] Alex Gluchowski. Zk rollup: scaling with zero-knowledge proofs. Matter Labs, 2019. https://pandax-statics.oss-cn-shenzhen.aliyuncs.com/statics/1221233526992813.pdf.
[15] Oded Goldreich. The foundations of cryptography - volume 1, basic techniques. Cambridge
University Press, 2001.
[16] A. Kiayias and D. Zindros. Proof-of-work sidechains. Cryptology ePrint Archive, Report
2018/1048, 2018. https://eprint.iacr.org/2018/1048.
[17] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros:
A provably secure proof-of-stake blockchain protocol. CRYPTO 2017, Part I, volume 10401
of LNCS, pages 357–388. Springer, Heidelberg, 2017.
[18] S. Lerner. Drivechains, sidechains and hybrid 2-way peg designs., 2016. https://docs.
rsk.co/Drivechains_Sidechains_and_Hybrid_2-way_peg_Designs_R9.pdf.
[19] Izaak Meckler and Evan Shapiro. Coda : Decentralized cryptocurrency at scale, 2018.
https://cdn.codaprotocol.com/v2/static/coda-whitepaper-05-10-2018-0.pdf.

37

[20] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.
//bitcoin.org/bitcoin.pdf.

https:[21] Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven Goldfeder.
Bitcoin and cryptocurrency technologies: A comprehensive introduction. Princeton University Press, Princeton, NJ, USA, 2016.
[22] J. Poon and V. Buterin. Plasma: Scalable autonomous smart contracts. http://plasma.
io/.
[23] Merkle R.C. A digital signature based on a conventional encryption function. Advancesin Cryptology — CRYPTO 1987. Lecture Notes in Computer Science, vol 293. Springer,
Berlin, Heidelberg, 1988.
[24] Nicholas Stifter, Aljosha Judmayer, Philipp Schindler, Alexei Zamyatin, and Edgar Weippl.
Agreement with satoshi – on the formalization of nakamoto consensus. Cryptology ePrint
Archive, Report 2018/400, 2018. https://eprint.iacr.org/2018/400.
[25] P. Sztorc. Drivechain - the simple two way peg, november 2015., 2015. http://www.
truthcoin.info/blog/drivechain/.
[26] The Horizen Team and Community. Horizen: A blockchain platform for fully customizable decentralized applications, 2019. https://www.horizen.global/assets/files/
Horizen-White-Paper.pdf.
[27] S. Thomas and E. Schwartz. A protocol for interledger payments, 2016.
//interledger.org/interledger.pdf.

https:[28] Bitcoin Wiki. Coinbase. https://en.bitcoin.it/wiki/Coinbase.
[29] Bitcoin Wiki. Transaction. https://en.bitcoin.it/wiki/Transaction.
[30] Gavin Wood. Polkadot:vision for a heterogeneous multi-chain framework, 2016. https://polkadot.network/Polkadot-lightpaper.pdf.

Appendix A

MST Delta

Here, we provide an example of how the mst delta value from a withdrawal certificate [5.5.3.1
Withdrawal Certificate] is calculated and give some explanations on why it is needed. Note that
this relates only to the Latus sidechain construction.
In general, mst delta shows which leaves have been changed between two Merkle state trees[5.2 Accounting Model and System State] M STi and M STj , i < j (e.g., in case of a withdrawal
certificate, these are MSTs committed by the previous certificate and the current one whichshows how the system state changed during the epoch). mst delta is a bit vector that shows
what leaves of the M STi have been changed in M STj .
Let us consider the MST of depth DM ST = 3 which has an initial state M ST0 (see Fig. 15).
The MST can contain up to eight unspent outputs (equal to the number of leaves). At the
moment M ST0 , the tree contains three UTXOs {utxo1 , utxo2 , utxo3 } which are assigned to leaf
nodes 0, 4, 6 correspondingly.

38

0

1

2

3

4

5

6

7

utxo1(val=5)

∅

∅

∅

utxo2(val=3)∅

utxo3(val=1)∅

Figure 15: Merkle state tree M ST0 .
Let us assume that we have two transactions tx1 and tx2 such that:tx1 = {
inputs: {utxo1}
outputs: {utxo4(val=2), utxo5(val=3)}}
tx2 = {
inputs: {utxo4}
outputs: {utxo6(val=2)}}
Assuming that M ST P osition(utxo4 ) = 1, M ST P osition(utxo5 ) = 2, and
M ST P osition(utxo6 ) = 7, applying transactions tx1 and tx2 to the state M ST0 will provide
the following M ST1 :

0
∅

1

2

3

utxo4(val=2) utxo5(val=3) ∅4

5

utxo2(val=3)

∅

6

7

utxo3(val=1) utxo6(val=2)

Figure 16: Merkle state tree M ST1 .
It can be seen that during the transition from M ST0 to M ST1 , the leaves 0, 1, 2, 7 havebeen modified. Thus, the msd delta reflects these modifications in the bit vector:
mst delta = (11100001),
where each bit represents whether a corresponding leaf node has been modified.
Having mst delta in each withdrawal certificate allows to prove that some utxoa is contained in
M STk committed by the latest certificate, by providing proof of inclusion in some M STt , t < k,39committed by the certificate in the past, and verifying that the bit M ST P osition(utxoa ) iszero for all mst delta’s on the way from M STt to M STk .
This feature is of great value for circumventing data availability attacks, e.g., when a compromised sidechain (where the majority of stakeholders is adversarial) submits a withdrawal
certificate to the mainchain that commits to some M STk while not revealing to the public the
M STk tree itself. Having mst delta in place, a user will be able to create proof of utxo ownershipby using some previous M STk . This mechanism is used for proving utxo ownership in mainchain
managed withdrawals in the Latus sidechain construction ([5.5.3.2 Backward Transfer Request],[5.5.3.3 Ceased Sidechain Withdrawal]).

40