  Blockchain technologies are facing a scalability challenge, which must be
overcome to guarantee a wider adoption of the technology. This scalability
issue is due to the use of consensus algorithms to guarantee the total order of
the chain of blocks and of the transactions within each block. However, total
order is often not fully necessary, since important advanced applications of
smart-contracts do not require a total order among all operations. A much
higher scalability can potentially be achieved if a more relaxed order can be
exploited. In this paper, we propose a novel distributed concurrent data type,
called Setchain, which improves scalability significantly. A Setchain
implements a grow-only set whose elements are not ordered, unlike conventional
blockchain operations. When convenient, the Setchain allows forcing a
synchronization barrier that assigns permanently an epoch number to a subset of
the latest elements added, agreed by consensus. Therefore, two operations in
the same epoch are not ordered, while two operations in different epochs are
ordered by their respective epoch number. We present different
Byzantine-tolerant implementations of Setchain, prove their correctness and
report on an empirical evaluation of a prototype implementation. Our results
show that Setchain is orders of magnitude faster than consensus-based ledgers,
since it implements grow-only sets with epoch synchronization instead of total
order. Since Setchain barriers can be synchronized with the underlying
blockchain, Setchain objects can be used as a sidechain to implement many
decentralized solutions with much faster operations than direct implementations
on top of blockchains. Finally, we also present an algorithm that encompasses
in a single process the combined behavior of Byzantine servers, which
simplifies correctness proofs by encoding the general attacker in a concrete
implementation.
