State machine replication (SMR) uses consensus as its core component for reaching agreement among a group of processes, in order to provide fault-tolerant services. Most SMR protocols, such as Paxos and Raft, are designed in the partial synchrony model. Partially synchronous protocols rely on timing assumptions to elect a special role (such as the leader), which may become the performance bottleneck under a heavy workload. From an engineering perspective, partially synchronous protocols have to wait for a pre-defined period of time and implement a (complicated) failover mechanism in order to replace the faulty leader. In contrast, asynchronous protocols are immune to such problems.

Byzantine fault tolerant (BFT) consensus protocols are becoming an appealing solution to blockchains. As most blockchain systems are deployed on Wide Area Networks (WANs), with each node acting on behalf of its entity, partially synchronous BFT protocols that rely on network synchrony to elect a single leader can be ill-suited. In contrast, asynchronous protocols have no such timing assumptions. Existing asynchronous protocols confront challenges in terms of both flexibility and performance.

Blockchain(e.g., Bitcoin) has widespread use in digital currency, which is entirely public to all participants, revealing users' privacy and transaction details. Anonymous blockchains without auditing capability can offer strong privacy guarantees, they could be used by illegal activities. However, anonymous blockchains with auditing capability suffer from two limitations: (i) inefficient auditing capability; (ii) lower degree of decentralization. To address these problems, this paper presents IAP, an instant auditing protocol based on anonymous blockchain with strong anonymity guarantees, which uses audit node cluster to implement decentralized instant auditing. The experimental results show that IAP only needs 60 milliseconds to complete an audit on average with 16 audit nodes, which accounts for one thousand of a complete transaction time. IAP can still complete efficient auditing when there are more than half of the nodes are honest in the audit node cluster. Moreover, its performance is virtually unaffected by increased number of transactions.