Fully Anonymous Decentralized Identity Supporting Threshold Traceability with Practical Blockchain

Decentralized identity (DID) holds significant potential for applications in Web3, such as digital markets and financial systems. Traditional DID paradigms offer a degree of privacy but struggle to prevent the link analysis on user behaviours and repeated public key usage. Anonymity is not fully achieved, as users' real identities or public keys are exposed to the issuing authority, while introducing high public key management complexity. Besides, existing anonymous credential schemes lack effective mechanisms for threshold traceability, not meeting Web3's distributed governance requirements. In this paper, we propose FADID-TT, a Fully Anonymous DID system supporting Threshold Tracing with practical blockchain, to tackle the above challenges. Firstly, we propose a distributed identity registration scheme based on secret sharing. A committee composed of distributed issuing authorities is responsible for issuing user's secret key shares and no single entity in the system can obtain a user's real identity or public key, achieving anonymity to authority. Moreover, we design a fully anonymous DID system combined with anonymous signatures and decentralized anonymous credentials (DAC). A service provider can only use the committee public key to verify a user identity, eliminating the need for user public keys, fully resisting link attacks, and reducing the user public key management complexity from O(n) to O(1). Furthermore, we design a publicly verifiable threshold tracing mechanism that enables committee members to collaboratively trace the identity of a malicious user without compromising privacy guarantees. FADID-TT realizes publicly verifiable tracing via zero-knowledge proofs. Finally, we give comprehensive security analysis and concrete performance evaluation. In addition to evaluate each part of proposal, we also deploy FADID-TT on two well-known blockchain platforms including Hyperledger Fabric (permissioned) and Ethereum (permissionless) to demonstrate the practical feasibility of FADID-TT.