  We present TRAIL: an algorithm that uses a novel consensus procedure to
tolerate failed or malicious shards within a blockchain-based cryptocurrency.
Our algorithm takes a new approach of selecting validator shards for each
transaction from those that previously held the assets being transferred. This
approach ensures the algorithm's robustness and efficiency. TRAIL is presented
using PBFT for internal shard transaction processing and a modified version of
PBFT for external cross-shard validation. We describe TRAIL, prove it correct,
analyze its message complexity, and evaluate its performance. We propose
various TRAIL optimizations: we describe how it can be adapted to other
Byzantine-tolerant consensus algorithms, how a complete system may be built on
the basis of it, and how TRAIL can be applied to existing and future sharded
blockchains.
