Abstract: Payment Channel Network (PCN) provides the off-chain settlement of transactions. It is one of the most promising solutions to solve the scalability issue of the blockchain. Many routing techniques in PCN have been proposed. However, both incentive attack and privacy protection have not been considered in existing studies. In this paper, we present an auction-based system model for PCN routing using the Laplace differential privacy mechanism. We formulate the cost optimization problem to minimize the path cost under the constraints of the Hashed Time-Lock Contract (HTLC) tolerance and the channel capacity. We propose an approximation algorithm to find the top \mathcalK shortest paths constrained by the HTLC tolerance and the channel capacity, i.e., top \mathcalK -restricted shortest paths. Besides, we design the probability comparison function to find the path with the largest probability of having the lowest path cost among the top \mathcalK -restricted shortest paths as the final path. Moreover, we apply the binary search to calculate the transaction fee of each user. Through both theoretical analysis and extensive simulations, we demonstrate that the proposed routing mechanism can guarantee the truthfulness and individual rationality with the probabilities of 1/2 and 1/4, respectively. It can also ensure the differential privacy of the users. The experiments on the real-world datasets demonstrate that the privacy leakage of the proposed mechanism is 73.21% lower than that of the unified privacy protection mechanism with only 13.2% more path cost compared with the algorithm without privacy protection on average.