Let G=(V,E) be a directed graph with n vertices, and s be any designated source vertex. We address the problem of computing a sparse fault-tolerant reachability structure (or FTRS for short), namely, a subgraph H of G such that on failure of any k edges or vertices, the set of vertices reachable from s in G\F is the same as the set of vertices reachable from s in H\F. We present an algorithm for constructing an FTRS with O(2^k n) edges, and also provide a matching lower bound result.