\(\text{Trac}^{2}\) ZChain: Trackability and Traceability of Graph Data in Blockchain with Linkage Privacy

Blockchain's tamper-proof, decentralized qualities make it perfect for running shared provenance applications in a distributed setting, such as auditing data sharing or monitoring supply chains. However, blockchain presents challenges when it comes to storing sensitive provenance data, including the data records themselves and their connection, because (1) records cannot be modified due to tamper-proofness, (2) efficient graph tracking/tracing is required for a provenance system on the blockchain, and (3) the linkages between records should be kept from unauthorized users, including the blockchain maintainers. Existing methods either lack sufficient privacy protection, only support simple structures, or inadvertently reveal linkage volume with the UTXO model. We present \(\text{Trac}^{2}\) ZChain, which is based on our previous work Trac \({}^{2}\) Chain[57], a framework that provides complete linkage privacy (i.e., no leakages from record sizes) and full tracking/tracing functions for blockchain-stored provenance graphs. The innovative graph storage architecture presented in [57] enables the generation of provenance dependencies for arbitrary graph structures while maintaining the tamper-proofness of blockchain. However, the previous work does not provide the blockchain with the ability to verify the authenticity of the provenance record, which should be an essential property of any blockchain-based system. In \(\text{Trac}^{2}\) ZChain, we modified the original Trac \({}^{2}\) Chain protocols to make it feasible to apply zero-knowledge proof, which allows blockchain peers to verify the correctness of the on-chain provenance functions without learning private information. The evaluation and comparison demonstrate that \(\text{Trac}^{2}\) ZChain achieves efficient provenance functions, verification of records, and linkage privacy protections, and has reasonable overhead compared to the state-of-the-art approaches.