This paper presents a middleware for providing a mobile ad hoc network with tamperproof provenance-aware storage, even when some fraction of devices can be Byzantine. Important considerations include fast propagation of updates, data consistency, and low power consumption. Leveraging entanglement techniques from blockchain protocols but carefully avoiding high power consumption and reliance on continuous network connectivity, we design new distributed data structures that can support useful distributed applications such as emergency response and IoT networks. Using both trace-based simulations and experiments with an Android-based prototype, we demonstrate the practicality of such a middleware.