The Z ILLIQA Technical Whitepaper[Version 0.1]
August 10, 2017
The Z ILLIQA Teamm www.zilliqa.com B enquiry@zilliqa.com 7 @zilliqa

consensus and network protocols. Therefore, even though reengineering the parameters of the existing protocols in say
Bitcoin or Ethereum (e.g., the block size or the block rate)
may show some speedup, to support applications that needprocessing of thousands of Tx/s however requires rethinking
the underlying protocols from scratch.
We present Z ILLIQA— a new blockchain platform that isdesigned to scale in transaction rates. As the number of miners
in Z ILLIQA increases, its transaction rates are expected toincrease as well. Specifically, Z ILLIQA’s design allows its
transaction rates to roughly double with every few hundred
nodes added to its network. As of this writing, the Ethereummining network is over 30,000 nodes. At Ethereum’s present
capacity, Z ILLIQA would expect to process about a thousand
times the transaction rates of Ethereum.
Z ILLIQA is a redesign from scratch and has been underresearch and development for over 2 years. The cornerstonein Z ILLIQA’s design is the idea of sharding — dividing themining network into smaller consensus groups called shards
each capable of processing transactions in parallel. If themining network of Z ILLIQA is say 8000 miners, Z ILLIQA
automatically creates 10 sub-networks each of size 800 miners,
in a decentralized manner without a trusted co-ordinator. Now,
if one sub-network can agree on a set of (say) 100 transactions
in one time epoch, then 10 sub-networks can agree on a totalof 1000 transactions in aggregate. The key to aggregating
securely is to ensure that sub-networks process different transactions (with no overlaps) without double-spending.
The assumptions are similar to existing blockchain-based
solutions. We assume that the mining network will have a fraction of malicious nodes/identities with a total computational
power that is a fraction (< 1/4) of the complete network.
It is based on a standard proof-of-work scheme, however, it
has a new two-layer blockchain structure. It features a highly
optimized consensus algorithm for processing shards.
Z ILLIQA further comes with an innovative special-purpose
smart contract language and execution environment that leverage the underlying architecture to provide a large scale andhighly efficient computation platform. The smart contract
language in Z ILLIQA follows a dataflow programming style,where the smart contract can be represented as a directed
graph. Nodes in the graph are operations or functions, while

Abstract—Existing cryptocurrencies and smart contract platforms are known to have scalability issues, i.e., the number oftransactions they are capable of processing per second is limited,
usually less than 10. As the number of applications utilizing
public cryptocurrencies and smart contract platforms grow, thedemand for processing high transaction rates in the order ofhundreds and thousands of Tx/s is increasing.
In this work, we present Z ILLIQA— a new blockchain platformthat is designed to scale in transaction rates. As the number ofminers in Z ILLIQA increases, its transaction rates are expected toincrease. At Ethereum’s present network size of 30,000 miners,
Z ILLIQA would expect to process about a thousand times thetransaction rates of Ethereum. The cornerstone in Z ILLIQA’s
design is the idea of sharding — dividing the mining network
into smaller shards each capable of processing transactions inparallel.
Z ILLIQA further proposes an innovative special-purpose smart
contract language and execution environment that leverages theunderlying architecture to provide a large scale and highly
efficient computation platform. The smart contract language in
Z ILLIQA follows a dataflow programming style which makes it
ideal for running large-scale computations that can be easily
parallelized. Examples include simple computations such as
search, sort and linear algebra computations, to more complex
computations such as training neural nets, data mining, financial
modeling, scientific computing and in general any MapReducetask.

I. I NTRODUCTION
Cryptocurrencies and smart contract platforms are becoming a shared computational resource. One could view theseplatforms as a new generation of computers that synchronize
over thousands of individual computers. However, existing
cryptocurrencies and smart contract platforms have widely
recognized limitations in scaling. Average transaction rates in
Bitcoin [1], Ethereum [2], and related cryptocurrencies havebeen limited to below 10 (usually about 3-7) transactions
per second (Tx/s). As the number of applications utilizing
public cryptocurrencies and smart contract platforms grow, thedemand for processing high transaction rates in the order ofhundreds of Tx/s is increasing. A global payment network
would likely require tens of thousands of Tx/s in capacity.
Can we build a decentralized and open blockchain platform
capable of processing at that scale?
The limitations in scaling up existing protocols are somewhat fundamental — they are rooted in the design of the1

an arc between two nodes represent the output of the first andthe input to the second. A node gets activated (or operational)
as soon as all of its inputs become valid and thus a dataflow
contract is inherently parallel and suitable for decentralized
systems such as Z ILLIQA.
The sharded architecture is ideal for running large-scalecomputations that can be easily parallelized. Examples include
simple computations such as search, sort and linear algebra
computations, to more complex computations such as training a neural net, data mining, financial modeling, scientificcomputing and in general any MapReduce task among others.
This document outlines the technical design of Z ILLIQA
blockchain protocol. Z ILLIQA has a new, conceptually clean
and modular design. It has six layers: the cryptographic layer(Section III), data layer (Section IV), the network layer (Section V), the consensus layer (Section VI), the smart contract
layer (Section VII) and the incentive layer (Section VIII).
Before we present the different layers, we first discuss thesystem settings, underlying assumptions and threat modelin Section II.

Further, all byzantine nodes can collude together. We assume
that the total computation power of the byzantine adversaries
is still confined to standard cryptographic assumptions ofprobabilistic polynomial-time adversaries.
We however assume that messages from honest nodes (inthe absence of network partition) can be delivered to honest
destinations after a certain bound δ, but δ may be time-varying.
The bound δ is used to ensure liveness but not safety [3]. In
case such timing and connectivity assumptions are not met, it
becomes possible for byzantine nodes to delay the messages
significantly (simulating a gain in computation power) or
worse “eclipse” the network [4]. In the event of network
partition, as dictated by the CAP theorem, one can only choose
between consistency and availability [5]. In Z ILLIQA, wechoose to be consistent and sacrifice availability.
III. C RYPTOGRAPHIC L AYER
The cryptographic layer defines the cryptographic primitives used in Z ILLIQA. Similar to several other blockchain
platforms, Z ILLIQA relies on elliptic curve cryptography for
digital signatures and a memory-hard hash function for proofof-work (PoW).
Throughout this whitepaper, we extensively use SHA3 [6]hash function to present our design. SHA3 is originally basedon Keccak [7] which is widely used in different blockchain
platforms in particular Ethereum. In the near future, we may
switch to Keccak to enable better interoperability with otherplatforms.

II. S YSTEM S ETTING AND A SSUMPTIONS
Entities in Z ILLIQA. There are two main entities in
Z ILLIQA: users and miners. A user is an external entity
who uses Z ILLIQA’s infrastructure to transfer funds or run
smart contracts. Miners are the nodes in the network who
run Z ILLIQA’s consensus protocol and get rewarded for theirservice. In the rest of this whitepaper, we interchangeably use
the terms miner and node.
Z ILLIQA’s mining network is further divided into several
smaller networks referred to as a shard. A miner is assigned
to a shard by a set of miners called DS nodes. This set of DS
nodes is also referred to as the DS committee. Each shard andthe DS committee has a leader. The leaders play an importantrole in the Z ILLIQA’s consensus protocol and for the overall
functioning of the network.
Each user has a public, private key pair for a digital signature scheme and each miner in the network has an associatedIP address and a public key that serves as an identity.
Intrinsic token. Z ILLIQA has an intrinsic token called
Zillings or ZILs for short. Zillings give platform usage rights
to the users in terms of using it to pay for transaction
processing or run smart contracts. Throughout this whitepaper,
any reference to amount, value, balance or payment, should
be assumed to be counted in ZIL.
Adversarial model. We assume that the mining network at
any point of time has a fraction of byzantine nodes/identities
with a total computational power that is at most f < n4 of thecomplete network, where 0 ≤ f < 1 and n is the total sizeof the network. The factor 14 is an arbitrary constant bounded
away from 31 selected as such to yield reasonable constantparameters. We further assume that honest nodes are reliable
during protocol runs, and failed or disconnected nodes arecounted in the byzantine fraction.
Byzantine nodes can deviate from the protocol, drop or
modify messages and send different messages to honest nodes.

A. Schnorr Signature
Z ILLIQA employs Elliptic Curve Based Schnorr Signature
Algorithm (EC-Schnorr) [8] as the base signing algorithm.
We instantiate the scheme with secp256k1 curve [9]. The
same curve is currently used in Bitcoin and Ethereum but fora different signing algorithm called ECDSA. Choosing ECSchnorr over ECDSA has several benefits that we discuss
below:
1) Non-malleability: Informally put, the non-malleability
property means that given a set of signatures generated ona message using a private key, it should be hard for anadversary to produce a new signature for the same message
that is valid for the corresponding public key. Unlike ECDSA
which is malleable, EC-Schnorr has been proven to be nonmalleable [10].
2) Multisignature: A multisignature scheme allows multiple signers to “aggregate” their signatures on a given message
into a single signature which can be authenticated against asingle public key that “aggregates” the keys of all the authorized parties. While, EC-Schnorr is natively a multisignaturescheme (see [11]), ECDSA allows creating multisignatures but
in a less flexible way.
Z ILLIQA uses EC-Schnorr based multisignatures to reduce
the signature size when multiple signatures are required on amessage. Smaller signatures are particularly important in ourconsensus protocol where multiple parties need to agree on adata by signing it.
23) Speed: EC-Schnorr is faster than ECDSA since the latter
requires computing an inverse modulo a large number. No
inversion is required in EC-Schnorr.
The exact EC-Schnorr key generation, signing and verification procedures are given in Appendix A. In the Appendix, we
also present how EC-Schnorr can be used as a multisignaturescheme.

account. A normal account is created by generating an ECSchnorr private key. A contract account is created by anotheraccount.
Each account is identified by an address derived differently
depending on its type. The address for a normal account isderived from the account’s private key. For a given private
key sk, the address Anormal is a 160-bit value computed as:
Anormal = LSB160 (SHA3-256(PubKey(sk))),B. Proof of Work

where, LSB160 (·) returns the rightmost 160 bits of the input
and PubKey(·) returns the public key corresponding to the input secret key. The address for a contract account is computedfrom the address of its creator and how many transactions thecreator account has sent, aka account nonce (described below).

Z ILLIQA uses PoW only to prevent Sybil attacks andgenerate node identities. This is in contrast to many existing blockchain platforms (in particular Bitcoin [1] andEthereum [12]), where PoW is used to reach distributed
consensus. Z ILLIQA employs Ethash [13], the PoW algorithm
used in Ethereum 1.0.
Ethash is a memory hard hash function designed to make iteasy to mine with GPUs but hard with specialized computing
hardware such as ASICs. To achieve this, Ethash computation
requires a considerable amount of memory (in GBs) and I/O
bandwidth such that the function cannot be invoked in parallelon specialized computing hardware.
Roughly speaking, Ethash takes a data (for instance a blockheader) and a nonce of 64-bits as inputs and generates a 256bits digest. The algorithm consists of four subroutines which
are run in the given order:
1) Seed generation: Seed is a SHA3-256 digest which is
updated after every 30000 blocks called an epoch. For
the first epoch it is the SHA3-256 hash of a series of
32 bytes of zeros. For every other epoch it is always the
SHA3-256 hash of the previous seed.
2) Cache generation: The seed is used to generate a pseudorandom cache using SHA3-512. The size of the cachelinearly increases with epoch. The initial size of the cacheis 16 MB.
3) Dataset generation: The cache is then used to generate
a dataset, where each “item” in the dataset depends on
only a small number of items in the cache. The dataset
is updated once every epoch so that the miners do nothave to make changes to it very frequently. The size ofthe dataset also increases linearly with epoch. The initialsize of the dataset is 1 GB.
4) Mining and Verification: Mining involves grabbing random slices of the dataset and hashing them together.
Verification uses the cache to regenerate the specificpieces of the dataset needed to compute the hash.

Acontract = LSB160 (SHA3-256(address||nonce)),where, address is the address of the creator account, andnonce is the creator’s nonce value.
Each account (whether normal or contract) is associatedwith an account state. The account state is a key, value store
and comprises of the following keys:
1) account nonce: (64 bits) A counter (initialized to0) that counts the number of transactions sent from anormal account. In case of a contract account, it counts
the number of contract creations made by the account.
2) balance: (128 bits) A non-negative value. Wheneveran account receives tokens from another account, thereceived amount is added to the account’s balance.
When an account sends tokens to another account, thebalance is reduced by the appropriate amount.
3) code hash: (256 bits) This stores SHA3-256 digestof the contract code. For a normal account it is the
SHA3-256 digest of the empty string.
4) storage root: (256 bits) Each account has a storage
which is again a key, value store with 256-bit keys and256-bit values. storage root is a SHA3-256 digest
that represents this storage. For instance, if the storage isa trie, then storage root is the digest of the root of
the trie.
The global state (state) of Z ILLIQA is a mapping between
account addresses and account states. It is implemented usinga trie like data structure.
B. Transactions
A transaction is always sent from a normal accountaddress and it updates the global state of Z ILLIQA. A
transaction has the following fields:
1) version (32 bits): Current version.
2) nonce (64 bits): A counter equal to the number oftransactions sent by the sender of this transaction.
3) to (160 bits): Destination account address. In case thetransaction creates a new contract account, this field is therightmost 160 bits of SHA3-256 of the empty string.
4) amount (128 bits): The transaction amount to be transferred to the destination address.

IV. DATA L AYER
Broadly speaking, the data layer defines the data that
constitutes the global state of Z ILLIQA. By extension, it also
defines the data needed by the different entities in Z ILLIQA
to update its global state.
A. Accounts, Addresses and StateZ ILLIQA is an account-based system (as Ethereum). There
are two types of accounts: normal account and contract32) Transaction Blocks: As discussed earlier, a DS-Blockcontains information on the nodes who reach consensus ontransactions. TX-Block stores information on which transactions were agreed upon by the nodes in a DS-Block. Every
DS-Block is linked to multiple TX-Blocks. A TX-Block has
three parts: header, data and signature. The header
consists of the following fields:
1) type (8 bits): A TX-Block is of two types, micro
block (0x00) and final block (0x01). More on thesein Section V-D.
2) version (32 bits): Current version.
3) previous hash (256 bits): The SHA3-256 digest of
its parent block header.
4) gas limit (128 bits): Current limit for gas expenditure
per block.
5) gas used (128 bits): Total gas used by transactions inthis block.
6) number (256 bits): The number of ancestor blocks. The
genesis block has a block number of 0.
7) timestamp (64 bits): Unix’s time() at the time ofcreation of this block.
8) state root (256 bits): It is a SHA3-256 digest
that represents the global state after all transactions are
executed and finalized. If the global state is stored as atrie, then state root is the digest of the root of thetrie.
9) transaction root (256 bits): It is a SHA3-256
digest that represents the root of the Merkle tree that
stores all transactions that are present in this block.
10) tx hashes (each 256 bits): A list of SHA3-256 digests of the transactions. The signature part of thetransaction is also hashed.
11) pubkey (264 bits): It is the EC-Schnorr public key ofthe leader who proposed the block.
12) pubkey micro blocks (unlimited): It is a list of ECSchnorr public keys (each 264 bits in length). The list
contains the public keys of the leaders who proposedtransactions. The field is present only if it is a final block.
13) parent block hash (256 bits): It is the SHA3-256
digest of the previous final block header.
14) parent ds hash (256 bits): It is the SHA3-256
digest of its parent DS-Block header.
15) parent ds block number (256 bits): It is the parent DS-Block number.
The data part of a TX-Block contains the set of transactions. It has the following fields:
1) tx count (32 bits): The number of transactions in thisblock.
2) tx list (unlimited): A list of transactions.
The signature part of a TX-Block contains an ECSchnorr based multisignature. It has the following two fields:
1) signature (512 bits): The signature is an EC-Schnorr
based multisignature on the TX-Block header signed bya set of nodes. The signature is produced by a different
set of nodes depending on whether it is a micro block or5) gas price (128 bits): Gas is defined as the smallest
unit of computation. gas price is the amount that thesender is willing to pay per unit of gas for computations
incurred in the transaction processing.
6) gas limit (128 bits): The maximum amount of gas
that should be used while processing the transaction.
7) code (unlimited): An expandable byte array that specifies the contract code. It is present only when thetransaction creates a new contract account.
8) data (unlimited): An expandable byte array that specifies the data that should be used to process the transaction.
It is present only when the transaction invokes a call toa contract at the destination address.
9) pubkey (264 bits): An EC-Schnorr public key thatshould be used to verify the signature. The pubkey fieldalso determines the sending address of the transaction.
10) signature (512 bits): An EC-Schnorr signature on theentire data.
Each transaction is uniquely identified by atransaction ID — a SHA3-256 digest of the transaction
data that excludes the signature field.
C. Blocks
The Z ILLIQA protocol introduces two types of blocks (andthereby two blockchains): transaction blocks (TX-Block) anddirectory service blocks (DS-Block). TX-Block contains thetransactions sent by users, while DS-Block contains metadata
about the miners who participate in the consensus protocol.
1) DS Blocks: A DS-Block has two parts: the header
and the signature. The header part of DS-Block has thefollowing fields:
1) version (32 bits): Current version.
2) previous hash (256 bits): The SHA3-256 digest of
its parent block header.
3) pubkey (264 bits): The public key of the miner who did
PoW on this block header.
4) difficulty (64 bits): This can be calculated from theprevious block’s difficulty and the block number. It storesthe difficulty of the PoW puzzle.
5) number (256 bits): The number of ancestor blocks. The
genesis block has a block number of 0.
6) timestamp (64 bits): Unix’s time() at the time ofcreation of this block.
7) mixHash (256 bits): A digest calculated from nonce
which allows detecting DoS attacks.
8) nonce (64 bits): A solution to the PoW.
The signature part of DS-Block contains the following
two fields:
1) signature (512 bits): The signature is an EC-Schnorr
based multisignature on the DS-Block header signed by
DS nodes.
2) bitmap (1024 bits): It records which DS nodes participated in the multisignature. We denote the bitmap by abit vector B, where, B[i] = 1 if the i-th node signed theheader else B[i] = 0.
DS-Blocks form a DS blockchain.
4

a final block. Further details on the signatories is given
in Section V-D.
2) bitmap (1024 bits): It records which nodes participatedin the multisignature. We denote the bitmap by a bit
vector B, where, B[i] = 1 if the i-th node signed theheader else B[i] = 0.
The final blocks form the transaction blockchain. The
transaction blockchain does not include micro blocks.

After a successful bootstrapping phase, at any time, thecomposition of the DS nodes is stipulated by a predefined
window of size n0 . The most recent n0 nodes who havesuccessfully mined a DS-Block form the DS committee.
The average time between mining two consecutive DSBlocks is referred to as the DS-epoch. The value ofDS-epoch is set in a way to minimize the chances of twocompeting blocks. At the start of a DS-epoch, a new DS
node joins the DS committee and the oldest member of the
DS committee is churned out. This fixes the size of the DS
committee to n0 during any DS-epoch. The newest memberof the DS committee then becomes the leader and leads theconsensus protocol for the epoch (see Section VI for theconsensus protocol). This further induces a strict ordering on
the members of the DS committee.
One can show that if the DS committee size is sufficiently
large (say above 800), then among the n0 members of thecommittee at most 31 are byzantine with high probability.
2) Resolving Conflicts: Our consensus protocol (to bepresented in Section VI) does not permit forks in the DS
blockchain. The forks may occur when multiple nodes solve
the puzzle at roughly the same time. In order to resolve theconflict, each DS node retrieves the nonce field from thereceived headers and sorts them in the increasing order. Let
us suppose that the largest nonce for the i-th DS node isnimax .
The leader of the DS committee then proposes his own
header (that corresponds to the largest nonce he has seen)
and runs a consensus protocol to agree on the DS-Blockheader. The i-th DS node then agrees to accept the proposed
header only if the corresponding nonce is larger than or equal
to nimax . Once the consensus is reached, the signature partof the DS-Block is built and the agreed upon winner thenbecomes the leader.
3) Generating Shards: Once the DS committee is elected,
the actual sharding of the network can start. In order for a node
to participate in the underlying consensus protocol, it has toperform a proof-of-work (PoW2 ). The sharding protocol isrepeated at the start of every DS-epoch. The algorithm for
PoW2 is given in Algorithm 2.

V. N ETWORK L AYERZ ILLIQA has been designed to scale in transaction rates. The
main idea is that of sharding, i.e., dividing the mining network
into small shards, each capable of processing transactions inparallel. In this section, we present the idea of network andtransaction sharding.
A. Network Sharding
Network sharding, i.e., dividing the mining network into
smaller shards is a two-step process. First, a dedicated set ofnodes called the directory service committee (or DS committee) are elected which then shard the network and assign nodes
to their shard. We present these processes below in further
detail.
1) Directory Service Committee: To facilitate sharding of
the network, we first elect a group of nodes, called directory
service (DS) nodes. The DS nodes form a DS committee.
The election of DS nodes is based on a proof-of-work puzzle
that we refer to as PoW1 . The algorithm for PoW1 is given
in Algorithm 1.
Algorithm 1: PoW1 for DS committee election.
Input: i: Current DS-epoch, DSi−1 : Prev. DS committee
composition.
Output: header: DS-Block header.
1 On each competing node:// get epoch randomness from the DS blockchain// DBi−1 : Most recent DS-Block before start of i-th epoch2

r1 ← GetEpochRand(DBi−1 )// get epoch randomness from the transaction blockchain// TBj : Most recent TX-Block before start of i-th epoch3r2 ← GetEpochRand(TBj )// pk: node’s public key, IP = node’s IP address

4
5

nonce, mixHash ← Ethash-PoW(pk, IP, r1 , r2 )header ← BuildHeader(nonce, mixHash, pk)

Algorithm 2: PoW2 for shard membership.

// header includes pk and nonce among other fields// IP, header is multicast to members in the DS committee
67

Input: i: Current DS-epoch, DSi : Current DS committee
composition.
Output: nonce, mixHash: outputs of Ethash-PoW
1 On each competing node:MulticastToDSi−1 (IP, header)
return header// get epoch randomness from the DS blockchain// DBi−1 : Most recent DS-Block before start of i-th epoch

Each node that has successfully produced a valid nonce
for PoW1 earlier than other nodes proposes a header fora new DS-Block. Recall that a DS-Block has a header
and a signature part. When a node does a PoW1 , it
only generates a DS-Block header. The header is thenmulticast to the nodes in the DS committee. The DS committee
then runs a consensus on the proposed DS-Block header andthen builds a signature part. Once, 2f DS nodes have signed
the DS-Block header, it is committed to the DS blockchain.

2r ← GetEpochRand(DBi )// pk: node’s public key, IP = node’s IP address

3

nonce, mixHash ← Ethash-PoW(pk, IP, r)// IP, header is multicast to members in the DS committee

45MulticastToDSi (nonce, mixHash, pk, IP)
return nonce, mixHash

The computed valid nonce (and mixhash) for PoW2
is then multicast to the DS committee. The DS nodes will5the sender’s address, i.e., the address of the account A inthe example. As the account address is a 160-bit integer, `is bounded above as:collectively accept just enough PoW solutions to be sharded
into l consensus committees or shards, each with n0 nodes to
run consensus. Once enough number of PoW2 solutions havebeen received by the leader of the DS committee, he initiates aconsensus protocol to agree on the set of valid PoW2 solutions.
At the end of the consensus protocol, the leader generates an
EC-Schnorr multisignature signed by the DS nodes. In orderto proceed further, more than 2/3 of the DS nodes must haveagreed on the set of acceptable PoW2 solutions.
Sharding leverages a deterministic function to assign a node
to a shard. Let us assume that we need ` shards each having
n0 nodes. The nonce values are then sorted in the increasingorder and the first n0 nodes are assigned to the first shard, thenext n0 to the next shard and so on. The identity of the miner
who proposed the largest nonce within a shard is declared its
leader. This further induces a strict ordering on the membersof the shard.
One can also show that if n0 is sufficiently large (say above800), then within each shard at most 13 are byzantine with highprobability.

blog2 `c + 1 ≤ 160.
In practice though, ` will be smaller than 100.
Once the assigned shard is identified, the transaction is thenmulticast to some nodes within the shard who then broadcast it
further. Once the transaction reaches the leader of the assigned
shard, it includes it in a TX-Block and runs the consensus
protocol.
Double spend (or replay attacks) can be easily detectedusing the nonce present in every transaction. Recall thateach transaction has a nonce that counts the number oftransactions sent from the sender’s account. Once a transaction
gets into the transaction blockchain, the nonce is updated
in the account’s state and thereby in the global state. A
transaction with a nonce value smaller than or equal to thecurrent value in the global state gets rejected by the miners.
Sharding transactions based on the sender’s account address
natively allows shard members to detect double spend as everytransaction from a sender will be processed within the sameshard.
2) Transaction Processing: All the nodes within a committee can propose transactions. These transactions are sent to theleader to run a consensus protocol on which set of transactions
forms the next TX-Block. Blocks proposed by each shard iscalled a micro block (identified by the type marker 0x00). A
micro block contains an EC-Schnorr multisignature by morethan 23 nodes from the shard. The leader also builds a bitmap
B that identifies the public keys of the signers. B[i] = 1 if
the i-th member of the shard has signed the TX-Block header.
When a shard reaches a consensus on a TX-Block, its leader
multicasts the block header and the signature to someof the DS nodes. The DS nodes then broadcast it within the
DS committee so that the block reaches its leader. The data
part of the block can be asynchronously sent to the nodes.
The DS committee then aggregates all blocks sent fromthe shards, and runs another round of the consensus protocol
among themselves to agree on the final block. A final block
is a TX-Block identified by the type marker 0x01. A final
block contains an EC-Schnorr multisignature by more than2
3 n0 nodes from the DS committee. The leader in the DS
committee also builds a bitmap B that identifies the publickeys of the signers. B[i] = 1 if the i-th member of the DS
committee has signed the TX-Block header. The final blockheader and the signature, is then multicast to somenodes within each shard. The actual TX-Block data is notsent by the DS nodes.
Within each shard the following steps are taken to process
the final block:
1) Each node in the shard verifies the EC-Schnorr multisignature using the public keys of the DS nodes. If thesignatures are valid against more than 32 n0 public keys
represented by the bitmap, then the nodes perform thenext checks.

B. Public Channel
The DS nodes publish certain information on the publicchannel, including the identities and connection informationof the DS nodes, the list of nodes in each shard, as well as
the sharding logic for transactions (explained in Section V-D).
The public channel is untrusted and is assumed to be accessibleby all nodes. In our implementation, our broadcast primitive
implements such a public channel.
A user of our blockchain who would like to submit atransaction for acceptance can then check the information
on sharding to get the shard responsible for processing hertransaction. The information published on the public channel
is expected to be signed by more than 2/3 of the DS nodes
that can be verified by any node or user.
C. New Nodes Joining Z ILLIQA
For a new node to join the network, it can attempt to solve
PoW1 to become a DS node or a PoW2 to become a memberof a shard. To this end, it would need to obtain informationon the randomness required for a PoW1 or a PoW2 from theblockchains. Once it obtains the randomness information, the
new node can submit its solution to the DS committee.
D. Transaction Sharding and Processing
As presented in Section V-A, network sharding createsshards each capable of processing transactions in parallel.
In this section, we present how a particular transaction gets
assigned to a shard and how the transactions get processed.
n
For this purpose, we use the following abstraction: A −→ B toindicate a transaction of n ZIL from the sender’s account A
to the receiver’s account B.
n1) Transaction Assignment: Any transaction say A −→ Bgets processed by a single shard. Assuming that there are `shards numbered from 0 to ` − 1, a transaction is assigned
to a shard identified by the blog2 `c + 1 rightmost bits of6

PBFT relies upon a correct leader to begin each phase andproceed when the sufficient majority exists. In case the leader
is byzantine it can stall the entire consensus protocol. To
address this challenge, PBFT offers a view change protocol
to replace the byzantine leader with another one. If thenodes do not see any progress for a bounded time, they can
independently announce the desire to change the leader. If aquorum of more than 23 n nodes decides that the leader is faulty,
then the next leader in a well-known schedule takes over.
Owing to the multicast of every node in the prepare/commit
phase, the communication complexity for PBFT in the normalcase is O(n2 ).

2) For each transaction hash included in the final blockheader, the node checks whether its correspondingtransaction content is available. If the correspondingtransaction was proposed by the shard to which the node
belongs, then the hash of the transaction data is comparedwith the hash contained in the final block header.
If the transaction was proposed by another shard, thetransaction data is shared asynchronously across shards.
3) Once the transaction data is available, the data partof the final block is reconstructed and the TX-Block isappended to the local transaction blockchain. The accountstate and the global state are accordingly updated.
4) If the transaction content is not available, the node
temporarily invalidates the sending account of that transaction in its local view of accounts so that any otherpending transactions for this account are rejected until
the local transaction content can be brought in sync withthe global state. Such rejected transactions will haveto be retried by the sending node.

B. Improving Efficiency
Classical PBFT uses message authentication code (MAC)
for authenticated communication between nodes. As MAC
requires a secret key shared between every two nodes, thenodes in one consensus group can agree on the same record
with a communication complexity of O(n2 ) per node. Dueto the quadratic complexity, PBFT becomes impractical when
the committee has over 20 nodes.
To improve the efficiency, we use the ideas inspired from
ByzCoin [15]:1) We replace MAC with digital signatures to effectively
reduce the communication overhead to O(n).
2) In the meantime, to allow the other nodes to verify theagreement, one typical way is to collect the signaturesfrom the honest majority and append them to the agreement, thereby resulting in the agreement size linear in
the size of the consensus group. To improve on this, weemploy EC-Schnorr multisignatures to aggregate several
signatures into an O(1)-size multisignature.
We however cannot directly use the classical EC-Schnorr
multisignature scheme in the PBFT setting. This is because in
the classical setting all the signers agree on signing a given
message and the signature is valid only when all the signers
have signed the message. In the PBFT setting, we only requirethat the message be signed by over 23 n nodes in the consensus
group. One of the main modification required is to maintaina bitmap B for the signers who participate in the signing
process. If the i-th node participated in the process, B[i] = 1,
else it is 0. The bitmap is build by the leader. The bitmap
can then be used by any verifier to validate the signature. The
resulting protocol is left in Appendix B.

VI. C ONSENSUS L AYER
As mentioned earlier, each shard and the DS committee haveto run a consensus protocol on the micro blocks and the final
blocks respectively. In this section, we present the consensus
layer which defines the consensus protocol to run within eachshard and the DS committee. In the rest of the discussion,
we refer to shards and the DS committees collectively as aconsensus group.
A. Practical Byzantine Fault Tolerance
The core of Z ILLIQA’s consensus protocol relies on practical byzantine fault tolerance (PBFT) protocol proposed byCastro and Liskov [3]. We however improve its efficiency byusing the idea of employing EC-Schnorr multisignature in the
PBFT protocol as developed in [14], [15]. Use of EC-Schnorr
multisignature lowers the normal case communication latencyfrom O(n2 ) to O(n) and reduces the signature size from O(n)to O(1), where n is the size of the consensus group. In thissection, we present an overview of PBFT.
In PBFT, all the nodes within a consensus group are ordered
in a sequence, and it has one primary node (or leader) and theothers are referred to as backup nodes. Every round of PBFT
has three phases as discussed below:
1) Pre-prepare phase: In this phase, the leader announces
the next record (a TX-Block in our case) that the groupshould agree on.
2) Prepare phase: Upon receiving the pre-prepare message,
every node validates its correctness and multicasts a
prepare message to all the other nodes.
3) Commit phase: Upon receiving more than 23 n prepare
messages, a node multicasts a commit message to thegroup Finally, a node waits for more than 23 commit
messages to ensure that a sufficient number of nodes
have made the same decision. Therefore, all honest nodes
accept the same valid record.

C. Z ILLIQA Consensus
In Z ILLIQA, we use PBFT as the basis consensus protocoland employ two rounds EC-Schnorr multisignatures to replace
the prepare and commit phases in PBFT. The different modifications to the PBFT phases are explained below.
1) Pre-prepare phase: As in standard PBFT, the leader
distributes a TX-Block or a statement (signed by theleader) to all the nodes in the consensus group.
2) Prepare phase: All honest nodes check the validity of
the TX-Block and the leader collects responses from
more than 2n
3 nodes. This guarantees that the statement
7

proposed by the leader is safe and consistent with all
previous histories. The signature is generated using ECSchnorr multisignature. The leader also builds the bitmap
of nodes who signed the TX-Block.
3) Commit phase: To ensure that more than 2n
3 nodesknow the fact that more than 2n
nodes
have
verifiedthe3
TX-Block, we perform a second round of EC-Schnorr
multisignature. The statement being signed is the multisignature generated from the last round.
At the end of the three phases, the consensus is reached on
the TX-Block proposed by the leader.

computations such as training a neural net, data mining,financial modeling, etc.
Z ILLIQA’s computational sharding approach relies on a
new smart contract language that is not Turing-complete but
scales much better for a multitude of applications. The smart
contract language in Z ILLIQA follows a dataflow programmingstyle [16], [17]. In the dataflow execution model, a contract
is represented by a directed graph. Nodes in the graph areprimitive instructions or operations. Directed arcs between two
nodes represent the data dependencies between the operations,
i.e., output of the first and the input to the second. A node
gets activated (or operational) as soon as all of its inputs areavailable. This stands in contrast to the classical von Neumann
execution model (as employed in Ethereum), in which an
instruction is only executed when the program counter reaches
it, regardless of whether or not it can be executed earlier.
The key advantage of employing a dataflow approach isthat more than one instruction can be executed at once. Thus,
if several nodes in the graph become activated at the sametime, they can be executed in parallel. This simple principle
provides the potential for massive parallel execution. To see
this, we present a simple sequential program in Figure 1a withthree instructions and in Figure 1b, we present its dataflow
variant. Under the von Neumann execution model, the program
would run in three time units: first computing A, then B andfinally C. The model does not capture the fact that A and B
can be independently computed. The dataflow program on theother hand can compute these two values in parallel. The nodethat performs addition gets activated as soon as A and B areavailable.

D. Leader Change
In our consensus protocol, if the leader is honest, it candrive the nodes in the consensus group to reach agreements on
new sets of transactions continuously. However, if the leader
is byzantine, it can intentionally delay or drop messages fromhonest nodes, and slow down the protocol. To penalize suchmalicious leaders, our protocol changes the leader of eachshard and the DS committee periodically. This prevents thebyzantine leader to stall the consensus protocol for an infinite
time. Since all the nodes are ordered, the next leader will beenchosen in a round robin manner.
In fact, the leader of a shard is changed after every micro
block and the leader of the DS committee is changed after
every final block. Let us assume that the size of the consensus
group is n, then within a DS-epoch, we allow a maximumof n final blocks, each final block aggregating a maximum of
1 micro block per shard.
VII. S MART C ONTRACT L AYERZ ILLIQA comes with an innovative special-purpose smart
contract language and execution environment that leverages
the underlying architecture to provide a large scale and highly
efficient computation platform. In this section, we present thesmart contract layer that employs a dataflow programmingarchitecture.

y

x

20

∗

/
A

A. Computational Sharding using Dataflow Paradigm
Z ILLIQA’s smart contract language and its execution platform is designed to leverage the underlying network andtransaction sharding architecture. The sharded architecture isideal for running computation-intensive tasks in an efficientmanner. The key idea is the following: only a subset of the
network (such as a shard) would perform the computation. We
refer to this approach as computational sharding.
In contrast with existing smart contract architectures (suchas Ethereum), computational sharding in Z ILLIQA takes avery different approach towards how to process contracts.
In Ethereum, every full node is required to perform thesame computation to validate the outcome of the computation
and update the global state. Albeit being secure, such afully redundant programming model is prohibitively expensive for running large-scale computations that can be easily
parallelized. Examples include simple computations such as
search, sort and linear algebra computations, to more complex

B

A=x∗y
B = y/20
C =A+BC(a) A simple program.

(b) Dataflow program.

+

Fig. 1: (a): A simple sequential program with three instructions(b): Its dataflow variant.
When run on the Z ILLIQA’s sharded network, each node in
the dataflow program can be eventually attributed to a single
shard or even a small subset of nodes within a shard. Hence thearchitecture is ideal for any MapReduce style computationaltasks, where some node perform the mapping task while
another node can work as a reducer to aggregate the work
done by each mapper.
In order to facilitate the execution of a dataflow program,,
Z ILLIQA’s smart contract language has the following features:
1) Operating over a virtual memory space shared globally
across the entire blockchain.
82) Locking of intermediate cells in the virtual shared memory space during execution.
3) Checkpointing intermediate results during execution committed to blockchain.

learning), it is imperative to have an infrastructure thatallows deep learning models to train on large datasets. It
is well known that training on large datasets is crucial to amodel’s accuracy. To this end, Z ILLIQA’s computational
sharding and dataflow language will be particularly useful
to build machine learning applications. It will serve as
an infrastructure that may run tools like TensorFlow1 by
tasking groups of Z ILLIQA nodes to independently perform different computations such as computing gradients,
apply activation function, compute training loss, etc.
3) Application with high complexity and high precisionalgorithms: Different from the applications mentioned
above, some applications, such as computations overfinancial models, may require high precision. Any minor
deviation in one part of the computation may incur
heavy losses in investments. Such applications can taskconsensus groups of larger number of nodes in Z ILLIQA
to allow them to cross-check the computational resultsof each other. The key challenge in offloading the computational tasks of such financial modeling algorithms toa public platform, such as Z ILLIQA, is the concern fordata privacy and intellectual property of the algorithms.
To begin with, we envision certain well known portion ofsuch computation can be placed to Z ILLIQA for efficientand secure computation first, while the future researchand development of Z ILLIQA will further strengthen theprotection of data privacy and intellectual property forsuch applications.

B. Smart Security Budgeting
Apart form the benefits of parallelization offered fromthe dataflow computation model, Z ILLIQA further provides
a flexible security budgeting mechanism for computational
sharding. This feature is enabled by sharding the computational resources in the blockchain network via an overlay
above the consensus process. Computational sharding allows
users of Z ILLIQA and applications running on Z ILLIQA to
specify the sizes of consensus groups to compute for eachof the subtasks. Each consensus group will then be tasked tocompute the same subtask, and produce the results. The user
specifies the condition on acceptance of the results, e.g., all in
the consensus group must produce the same results, or 3/4 ofthem must produce the same results, etc.
A user of the application running on Z ILLIQA can budget
how much she wants to spend on computing and security,
respectively. In particular, a user running a particular deeplearning application may spend more gas fee on running moreof different neural network tasks than letting too many nodes
repeating the same computation. In this case, she can specify
a smaller consensus group for running each neural network
computation. On the other hand, a sophisticated financial
modeling algorithm that requires greater precision may taskconsensus groups of larger number of nodes to compute thecritical portions of the algorithm to be more resilient against
potential tampering and manipulation of the results.

VIII. I NCENTIVE L AYER
A. Token Supply
Z ILLIQA has a finite supply of 21 billion ZILs. The smallest
unit being 10−12 part of a ZIL. Each final TX-Block comeswith a block reward that generates new tokens. The block
reward will be spread over a period of 10 years decreasingover time. We aim to mine roughly 80% of the tokens in thefirst 4 years and the remaining 20% in the next 6 years. The
token emission will be “smooth” in the sense that the block
reward does not reduce drastically after a certain number ofblocks. The smooth reduction in the block reward means thatthe network hashrate can be expected to be stable as the reward
reduces over gradually over time.
After 10 years, we expect to have reached significant scale
both in terms of the number of nodes in the network and users
executing transactions. By then, we expect the market to havestabilized upon certain rates of transaction fees to fully sustain
the running of the network without a need for new tokens
entering the system as rewards.

C. Scalable Applications: Examples
Z ILLIQA aims to provide a platform to run highly scalable
computations in a multitude of fields such as data mining,machine learning and financial modeling to name a few. Since
supporting efficient sharding of Turing-complete programs
is very challenging, and there exist public blockchains that
support Turing-complete smart contracts (e.g., Ethereum),
Z ILLIQA focuses on specific applications with requirements
not met today.
1) Computation with parallelizable computation load:
Scientific computing over large data is a typical example where one requires a large amount of distributed
computing power. Moreover, most of these computations
are highly parallelizable, examples include linear algebra
operations on large matrices, search in the sea of hugeamount of data and simulation on a large dataset among
others. Z ILLIQA provides such computing tasks an inexpensive and short turnaround alternative. Moreover, withthe right incentive in place with computational sharding,and security budgeting Z ILLIQA can be leveraged as areadily available and highly reliable resource for suchheavy computation load.
2) Train neural nets: With the ever growing popularity
and use cases of machine learning (in particular deep

B. Incentivizing Miners
Miners reach consensus on transactions, process them, perform computations as per the smart contract and update theglobal state. Miners are hence incentivized by requiring thesender of each transaction to pay some gas upfront.
1 https://www.tensorflow.org/

9

Recall that each final TX-Block aggregates at most one
micro block from each shard. Each micro TX-Block contains a
gas used field that stores the total gas used by transactionsin the block. Each final TX-Block also has a gas used fieldthat is a sum of all the gas used field of each micro TXBlock. Once a TX-Block is proposed, the corresponding gas
used and the block reward is almost equitably distributed
among 1) the leaders of the shards who proposed one micro
block and 2) the leader of the DS committee who proposed
the final. In case the equitable distribution is not possible, thedistribution is slightly biased towards the leader of the DS
committee. Hence, if the reward is m and the total numberof stake holders for a reward is n, then the leader of eachshard gets b mn c, while, the leader of the DS committee getsm − n · bmc.
n
As the leader of each shard is changed once a new micro
block is proposed, every member of the shard gets rewarded.
Similarly, as the leader of the DS committee is changed after
every final block, every member of the DS committee is also
rewarded.

Z ILLIQA also proposes a smart contract platform not available
in ByzCoin/OmniLedger.
Z ILLIQA’s smart contract platform takes a different approach when compared with Ethereum. Z ILLIQA’s smart
contract platform leverages the underlying sharding architecture and is based on dataflow programming. The advantagesof dataflow programs are many: inherent concurrency andparallelism, easy to reason about their correctness, naturalcomposability of functions and programs, etc.
X. F UTURE R ESEARCH D IRECTIONSBelow, we discuss some ongoing and future directions ofresearch to improve Z ILLIQA.
State sharding. With increase in Z ILLIQA’s user base andits high transaction throughput would come the following
challenge: How to efficiently handle the continuous influx ofblocks that modify the global state. This is also referred toas state sharding in the literature. In essence, state sharding
will alleviate full nodes from storing and receiving all blocks
and transactions. This way it can further reduce the storage
and communication load for nodes, and thus constitute anotherscaling-up factor to the throughput. However, it is non-trivial
to design a secure and efficient state sharding scheme, as
cross-shard communications arising from state sharding may
outweigh the performance gains. More research needs to bedone to address such additional complexities.
Secure Proof-of-Stake (SPoS). To the best of our knowledge, there has been no literature that proposes a secure
PoS scheme, and thus we base Z ILLIQA’s building blocks on
a PoW scheme. However, given the significant performancegain from PoS for consensus algorithms, it is worthwhile
investigating further into the PoS paradigm, in search for asecure and efficient PoS scheme for Z ILLIQA.
Storage pruning. We are currently exploring ways tosecurely prune the dated blocks stored on the blockchain to
reduce the storage requirements and ease the joining process
for new nodes. We may consider multi-grade storage, compression of blocks and transactions as possible solutions.
Cross-Chain support. Z ILLIQA has every intention tocomplement other public blockchains and build a healthy
ecosystem to provide end users a broad spectrum of platformsof choice for their applications. To this end, Z ILLIQA will seek
technical solutions to support gradual cross-chain communication and potentially enable cross-chain applications.
Privacy-preserving computation. It is desirable for several
applications in particular (financial modeling applications)to have strong privacy and intellectual property protection
when running on Z ILLIQA. Solutions based on Oblivious
RAM to hide access pattern on an encrypted data [21], ZKSNARK [22] to hide the input to a program, and private
function evaluation [23] to hide the contract’s business logic
are also being investigated.

IX. R ELATED W ORKZ ILLIQA is developed upon the ideas of Bitcoin-NG [18],collective signing (CoSi) [14], ByzCoin [15], Elastico [19] andOmniLedger [20].
Bitcoin-NG first proposed the idea to decouple leader election and his block proposals within Bitcoin. First, a leader
is elected by mining a keyblock who can then mint many
microblocks within the 10 minute block interval. The idea wasfurther used in ByzCoin [15].
The idea of network and transaction sharding for a Bitcoin like system was first proposed in [19]. However, network/transaction sharding alone cannot solve the scalability
issues as each shard needs to sign a TX-Block which makes
the total number of signatures linear in the number of signers.
This eventually results in a large block size and becomes abottleneck during the broadcast/multi-cast.
Multisignatures [11] provides a solution to the above problem. CoSi [14] uses an EC-Schnorr multisignature scheme todesign a protocol for collective signing. CoSi was proposed towork in a much less hostile environment than that of a publicblockchain with byzantine nodes. With several significant
enhancements we develop for the CoSi scheme, we derive asecure scheme and apply it to Z ILLIQA.
Several other proposals have surfaced to sidestep the inherent scalability limitation of existing blockchain protocols,for instance, re-parameterizing the original Bitcoin protocol(e.g. increasing block sizes), moving as much computation offchain (e.g. micropayment channels and lightening networks),
creating hierarchy of blockchains (e.g. sidechains). None ofthese protocols directly make the blockchain protocol itself
more scalable. Z ILLIQA targets the heart of the scalability
problem – its blockchain.
Z ILLIQA can be seen as an extension of ByzCoin and OmniLedger with several security and performance optimizations.

XI. CONCLUSION
In this whitepaper, we have presented Z ILLIQA’s shardingarchitecture that allows the mining network to process transactions in parallel and reach high throughput. Z ILLIQA also10

comes with a unique smart contract platform that leverages
the underlying sharing architecture and follows a dataflow
programming paradigm. The new smart contract language isideal for running computation-intensive task in an efficientmanner.

[21] E. Stefanov, M. van Dijk, E. Shi, C. W. Fletcher, L. Ren, X. Yu,
and S. Devadas, “Path ORAM: An Extremely Simple Oblivious RAM
Protocol,” in 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013,2013, pp. 299–310.
[22] E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, “Succinct NonInteractive Zero Knowledge for a von Neumann Architecture,” inProceedings of the 23rd USENIX Security Symposium, San Diego, CA,
USA, August 20-22, 2014., 2014, pp. 781–796.
[23] P. Mohassel, S. S. Sadeghian, and N. P. Smart, “Actively Secure
Private Function Evaluation,” in Advances in Cryptology - ASIACRYPT
2014 - 20th International Conference on the Theory and Applicationof Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C.,
December 7-11, 2014, Proceedings, Part II, 2014, pp. 486–505.
[24] BSI, “Technical Guideline TR-03111 Elliptic Curve Cryptography,”
Federal Office for Information Security, Tech. Rep., 01 2012.
[25] D. J. Bernstein, “Multi-user Schnorr Security, Revisited,” IACR
Cryptology ePrint Archive, vol. 2015, p. 996, 2015. [Online]. Available:
http://eprint.iacr.org/2015/996[26] M. Michels and P. Horster, “On the Risk of Disruption in Several
Multiparty Signature Schemes,” in Proceedings of the International Conference on the Theory and Applications of Cryptology and Information
Security: Advances in Cryptology, ser. ASIACRYPT ’96. London, UK,
UK: Springer-Verlag, 1996, pp. 334–345.

R EFERENCES[1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,
http://bitcoin.org/bitcoin.pdf,” 2008.
[2] E. Foundation, “Ethereum’s white paper,” https://github.com/ethereum/
wiki/wiki/White-Paper, 2014.
[3] M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance,” inProceedings of the Third Symposium on Operating Systems Design
and Implementation, ser. OSDI ’99. Berkeley, CA, USA: USENIX
Association, 1999, pp. 173–186.
[4] E. Heilman, A. Kendler, A. Zohar, and S. Goldberg, “Eclipse Attacks on
Bitcoin’s Peer-to-Peer Network,” in 24th USENIX Security Symposium(USENIX Security 15). Washington, D.C.: USENIX Association, 2015,
pp. 129–144.
[5] S. Gilbert and N. Lynch, “Brewer’s Conjecture and the Feasibilityof Consistent Available Partition-Tolerant Web Services,” in In ACM
SIGACT News, 2002, p. 2002.
[6] NIST, “Sha-3 standard: Permutation-based hash and extendable-output
functions,” 2015.
[7] B. Guido, D. Joan, P. Michaël, and V. A. Gilles, “The Keccak Reference,” 2011.
[8] C. Schnorr, “Efficient signature generation by smart cards,” J. Cryptology, vol. 4, no. 3, pp. 161–174, 1991.
[9] C. Research, “SEC 2: Recommended Elliptic Curve Domain
Parameters,” 2000. [Online]. Available: http://www.secg.org/download/
aid-386/sec2-final.pdf[10] A. Poelstra, “Schnorr Signatures are Non-Malleable in the Random
Oracle Model,” 2014.
[11] S. Micali, K. Ohta, and L. Reyzin, “Accountable-subgroup Multisignatures: Extended Abstract,” in Proceedings of the 8th ACM Conference
on Computer and Communications Security, ser. CCS ’01. New York,NY, USA: ACM, 2001, pp. 245–254.
[12] G. Wood, “Ethereum: A secure decentralised generalised transaction
ledger,” http://gavwood.com/paper.pdf, 2014.
[13] “Ethash,” https://github.com/ethereum/wiki/wiki/Ethash, Accessed onJune 27, 2017., version 23.
[14] E. Syta, I. Tamas, D. Visher, D. I. Wolinsky, P. Jovanovic, L. Gasser,
N. Gailly, I. Khoffi, and B. Ford, “Keeping authorities ”honest or bust”
with decentralized witness cosigning,” in IEEE Symposium on Security
and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016, 2016, pp.
526–545.
[15] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, andB. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” in 25th USENIX Security Symposium,
USENIX Security 16, Austin, TX, USA, August 10-12, 2016., 2016, pp.
279–296.
[16] Arvind and D. E. Culler, “Annual review of computer science vol. 1,
1986,” J. F. Traub, B. J. Grosz, B. W. Lampson, and N. J. Nilsson,
Eds. Palo Alto, CA, USA: Annual Reviews Inc., 1986, ch. Dataflow
Architectures, pp. 225–253.
[17] A. L. Davis and R. M. Keller, “Data flow program graphs,” Computer,vol. 15, no. 2, pp. 26–41, Feb. 1982.
[18] I. Eyal, A. E. Gencer, E. G. Sirer, and R. van Renesse, “Bitcoinng: A scalable blockchain protocol,” in 13th USENIX Symposium on
Networked Systems Design and Implementation, NSDI 2016, Santa
Clara, CA, USA, March 16-18, 2016, 2016, pp. 45–59.
[19] L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena,“A secure sharding protocol for open blockchains,” in Proceedings ofthe 2016 ACM SIGSAC Conference on Computer and Communications
Security, Vienna, Austria, October 24-28, 2016, 2016, pp. 17–30.
[20] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, and B. Ford,“Omniledger: A secure, scale-out, decentralized ledger,” IACR Cryptology ePrint Archive, vol. 2017, p. 406, 2017.

A PPENDIX AS CHNORR D IGITAL S IGNATURE A LGORITHM
A. EC-Schnorr (Single Signer) Scheme
EC-Schnorr works on a group where the discrete logarithm
is hard [8], [24], [25]. Z ILLIQA uses the elliptic curve groupdefined over the popular secp256k1 curve. We denote by
C := (p, G, n) the set of parameters that define the group,
where p is a prime number that specifies the underlying field
Fp , G is the base point on the curve and n (a prime) is theorder of G. EC-Schnorr also requires a cryptographic hashfunction H that we instantiate with SHA3-256 [6].
EC-Schnorr is a set of three algorithms KeyGen, Sign
and Verify that we present in this section. In the algorithms
below, for any scalar x and a point Q, we denote the scalarmultiplication by [x]Q.
1) KeyGen(C): The algorithm takes the curve parameters
C and returns a pair of public (pk) and private (sk) keys.
KeyGen(C = (p, G, n))$

1. Choose sk ← [1, n − 1],
2. Set pk ← [sk]G,
3. return (pk, sk).
2) Sign(C, pk, sk, m): This algorithm is run by the signer. It
takes the curve parameters C, a public key and a private
key pair (pk, sk) and a message to sign m ∈ {0, 1}∗ . It
returns a signature σ.
Sign(C, pk, sk, m)
1.
2.
3.
4.
5.
6.
7.
8.

11

$

Choose k ← [1, n − 1],
Set Q ← [k]G,Set r ← H(Q||pk||m) mod n,
If r = 0 Goto 1.
Set s ← k − r · sk mod n,
If s = 0 Goto 1.
Set σ ← (r, s),return σ.

3) Verify(C, σ, pk, m): This algorithm is run by a verifier
who wishes to check the validity of a signature. It takes
the curve parameters C, a signature σ, a public key pk
and a message m. It returns 1 if the signature is valid form under pk, or else returns 0.

2) Commitment Generation: Each signer Pi then choses a$
random ki ← [1, n − 1] and computes Qi = [ki ]G. Recall
that G is the base point on the elliptic curve and n is theorder of G. Pi then sends Qi to the aggregator.
3) Challenge Generation: The
P aggregator first computes theaggregated keys: pk P
= pki ∈P pki for keys in P . She
also computes Q = i Qi for Qi ’s received in the previous step. She then computes r ← H(Q||pk||m) mod n
and sends (r, Q, pk) to each Pi .
4) Response Generation: Each signer Pi first checks theintegrity of r received previously. This is done by recomputing H(Q||pk||m) and checking if it is equal to thereceived r. If the check fails then Pi aborts the protocol
or else generates si ← (ki − r · ski ) mod n and sends si
to the aggregator.
5) Response Aggregation: Aggregatorcomputes the agPgregated response s =smodn and builds ani iaggregated signature σ = (r, s). She then sends (m, σ)to the verifier.
6) Signature Verification: Verifier now checks whether thesignature is valid. She performs the following steps:a) Aggregate the public keys in P as pk 0 .
b) Check if σ is a valid EC-Schnorr signature on m forthe public key pk 0 by invoking Verify(C, σ, pk 0 , m).
Returns the output of Verify.

Verify(C, σ, pk, m)
1.
2.
3.
4.
5.
6.

Parse (r, s) ← σ,
If r, s ∈/ [1, n − 1] return 0.
Set Q ← [s]G + [r]pk,
If Q = O(neutral point) return 0.
Set v ← H(Q||pk||m) mod n,
If v = r return 1, else return 0.

B. EC-Schnorr Multisignature Scheme
1) Setting & Assumptions: EC-Schnorr can also be used
as a multisignature scheme [11]. In a multisignature scheme,
we have T signers: P1 , . . . , PT , an aggregator and a verifier.
The signers wish to jointly sign a message m. The aggregatorplays the role of a facilitator and aggregates the signatures sent
by each individual signer. The verifier verifies the aggregatedsignature. The role of aggregator and the verifier can be playedby the same entity.
Each signer Pi has her own public private key pair (pki , ski )for EC-Schnorr single signer scheme. We denote by P ={pk1 , . . . , pkT } the set of all public keys. We also assume
a public message mp known to every entity. The message mp
may be specific to the application scenario and make takethe following form: I know the private key formy public key for the session id: XXXX. The
purpose of this message is to defeat certain known attacks
on the scheme [26].
2) Multisignature Protocol: Multisignature is an interactive
protocol between signers, the aggregator and the verifier(see Figure 2 for a schematic representation). The protocol
has six steps as described below.

A PPENDIX B
M ULTISIGNATURE FOR PBFTClassical EC-Schnorr multisignature protocol as describedin Appendix A requires the participation of all the participants.
Hence, we cannot directly use it in the PBFT setting, where,
we only require that the message be signed by at least 23 n + 1
nodes in the committee. In this section, we present a tweak
to this protocol inspired from [14]. The tweak consists inmaintaining two bitmaps that record the participation in the
protocol. The modified protocol is given in Figure 3. Below,
we briefly present the protocol.
1) (One-Time) Identity Setup: This step is exactly the sameas in the classical EC-Schnorr multisignature protocol aspresented in Appendix A. Only if the set up successfully
terminates, the next steps of the protocol can start.
2) Commitment Generation: This step is similar to theclassical EC-Schnorr multisignature protocol. The only
difference being that each participant Pi also sends its
public key pki along with a Qi to the aggregator.
3) Challenge Generation: At this step the aggregator maintains a bitmap BQ [1, . . . , |P |] initialized to 0. For every(Qi , pki ) received in the previous step, the aggregator sets
BQ [i] to 1. The aggregator waits for a stipulated time tohandle network propagation delay and then computes thefollowing:Pa) The aggregated keys: pk ← pki ∈P pki · BQ [i], i.e.,
she adds the public keys for which
P she received a Qi .
b) She also computes Q ←i:BQ [i]=1 Qi for Qi ’s
received in the previous step.

1) (One-Time) Identity Setup: This step is run between
each participant and the verifier. At the start of the protocol, each signer Pi if not currently involved in anothersigning protocol generates an EC-Schnorr signature σi on
the message mp . Pi then sends (σi , pki ) to the verifier.
The verifier then performs the following checks:a) Check if pki ∈ P . If the check fails, the verifier aborts.
b) Check if each σi is a valid EC-Schnorr signature on
mp for pki , by invoking Verify(C, σi , pki , mp ). Verifier
aborts if any of these signature verifications returns
0. If all the signatures are valid, then the protocol
proceeds to the next step.
If the verifier does not receive σi for every pki in P ,she also aborts. To record whether/or not she received
a signature from Pi , she uses a bitmap Z[1, . . . , |P |].
Identity Setup is a one-time process followed by any
number of the next steps. Only if the set up successfully
terminates, the next steps of the protocol can start.
12Pi (C, mp , m, pki , ski )Verifier (C, mp , P, Z)

Aggregator (C, m, P )σi ← Sign(C, pki , ski , mp )(σi , pki )if pki ∈/ P abort
if ¬Verify(C, σi , pki , mp ) abort
Z[i] = 1
At the end of the setup phase:
if ¬Z[i] abort$ki ← [1, n − 1]Qi ← [ki ]GQi(r, Q, pk)
r0 ← H(Q||pk||m)
if r0 6= r abortsi ← (ki − r · ski ) mod nP
pk ← pki ∈P pki
PQ ← i Qir ← H(Q||pk||m)siPs ← i si mod nσ ← (r, s)(m, σ)

P
pk 0 ← pki ∈P pki
return Verify(C, σ, pk 0 , m)

Fig. 2: Multisignature using EC-Schnorr. Verifier stores a bit map Z[1, . . . , |P |], where each entry is initialized to 0.
c) She then computes r ← H(Q||pk||m) mod n andsends (r, Q, pk) to each Pi .
4) Response Generation: This step is similar to the classical
EC-Schnorr multisignature protocol. The only difference
being that each participant Pi also sends its public key
pki along with a si to the aggregator.
5) Response Aggregation: At this step the aggregator maintains a bitmap Bs [1, . . . , |P |] initialized to 0. For every(si , pki ) received in the previous step, the aggregator
checks if the received si is valid by computing Q0i ←[si ]G + [r]pki and then verifying if Q0i is equal to thereceived Qi . If the two values are equal then she sets
Bs [i] to 1. This step allows to detect participants who
send an arbitrary value of si and attempt to mount a DoS
attack. The aggregator then waits for a stipulated time tohandle network propagation delay and then computes thefollowing:a) If the two bitmaps BQ and Bs are equal, whichmeans the same set of participants sent messages to theaggregator in the commitment generation and response
generation steps, then the P
aggregator computes theaggregated response s =i si mod n and builds

an aggregated signature σ = (r, s). She then sends(σ, m, BQ ) to the verifier.
b) If the two bitmaps are not equal, which means aparticipant sent a Qi but not the corresponding si , thenthe aggregator computes the set-theoretic differenceof BQ and Bs , i.e., the set of public keys pki ∈ P
for which the aggregator received a Qi but not thecorresponding si . The corresponding set of public keys
can then be blacklisted. The aggregator re-initializes
Bs to 0 and computes the intersection between BQ and
Bs and stores it in BQ . Finally, it repeats the protocol
starting from the challenge generation step.
6) Signature Verification: The verifier first checks if thesignature was generated by at least 23 |P | + 1 participants
and then checks whether the multisignature is valid. The
rest of the steps are same as in the classical EC-Schnorr
multisignature protocol.

13Pi (C, mp , pki , ski )Aggregator (C, m, BQ , Bs , P )Verifier (C, mp , P, Z)

σi ← Sign(C, pki , ski , mp )(σi , pki )$ki ← [1, n − 1]Qi ← [ki ]G

if pki ∈/ P abort
if ¬Verify(C, σi , pki , mp ) abort
Z[i] = 1
At the end of the setup phase:
if ¬Z[i] abort(Qi , pki )if pki ∈ P then BQ [i] ← 1
1 After a certain stipulated time:P
pk ← pki ∈P pki · BQ [i]P
Q ← i:BQ [i]=1 Qir ← H(Q||pk||m) mod n(r, Q, pk)

r0 ← H(Q||pk||m)
if r0 6= r abortsi ← (ki − r · ski ) mod n(si , pki )Q0i ← [si ]G + [r]pki
if Q0i = Qi then:Bs [i] ← 1
After a certain stipulated time:
if Bs = B
PQ then:s ← ( i:Bs [i]=1 si ) mod nσ ← (r, s)else:
May blacklist BQ Bs
BQ ← BQ ∧ Bs
Bs ← 0|P |goto 1(σ, m, BQ )P

i BQ [i] < 2|P |/3 + 1 then:returnP0
pk 0 ← pki ∈P pki · BQ [i]return Verify(C, σ, pk 0 , m)if

Fig. 3: EC-Schnorr multisignature variant used in PBFT. The leader of each committee plays the role of the aggregator. The
aggregator maintains two bitmaps BQ [1, . . . , |P |] and Bs [1, . . . , |P |], while the verifier stores a bit map Z[1, . . . , |P |]. The
entries of the bitmaps are initialized to 0. BQ Bs returns a bitmap that represents the set-theoretic difference of BQ and Bs ,i.e., it represents the set of public keys pki ∈ P for which the aggregator received a Qi but not the corresponding si .

14