This disclosure describes systems and methods for interlinking multiple independent and separately-scalable blockchains to provide transactional provenance. The disclosed systems and methods leverage a combination of blockchain and graph data structures to interoperate between blockchains without requiring a single data structure while still providing a single chain of custody and provenance for a particular set of actions.