On Efficient Transaction Anonymization Methods in Blockchain

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "On Efficient Transaction Anonymization Methods in Blockchain"

By

Mr. Wangze NI


Abstract:

Blockchain technology has gained significant attention due to its remarkable
attributes such as transparency, immutability, and decentralization. However,
transparency can also lead to privacy concerns. Researchers have proposed
anonymization methods to address privacy concerns, but their efficiency needs
improvement. This thesis focuses on enhancing the efficiency of three promising
anonymization schemes: the ring signature scheme, the coin mixing scheme, and
the payment channel network schemes. The ring signature scheme mixes the sender
of a transaction into a selected group of users, making it difficult for
adversaries to distinguish the sender among the users. The coin mixing scheme
mixes several transactions into one mixing transaction and decomposes each
original output in original transactions into a set of decomposed outputs,
resulting in multiple decomposed outputs with identical values originating from
different transactions. The payment channel network scheme allows users to
track in off-chain payment channels, preventing adversaries from accessing
information about each transaction within payment channels.

My first work focuses on minimizing the size of a ring signature with required
anonymity. I define a novel concept called a recursive (c, l)-diversity ring
signature to measure the anonymity of a ring signature. Additionally, I define
the diversity-aware mixin selection problem, which aims to find a recursive (c,
l)-diversity ring signature with a minimum size. I prove that the
diversity-aware mixin selection problem is #P. To efficiently solve the
diversity-aware mixin selection problem, I propose a framework called
TokenMagic. Additionally, I propose an exponential-time algorithm called
DAMS_BFS to exactly solve the diversity-aware mixin selection problem.
Moreover, I propose two practical configuration and two approximation
algorithms, namely Progressive and Game-theoretic.

My second work focuses on minimizing the number of decomposed outputs in a
mixing transaction with required anonymity. I define a novel concept called a
c-decomposition to measure the anonymity of a set of decomposed outputs.
Additionally, I define the anonymity-aware output decomposition problem, which
aims to find a c-decomposition with a minimum size. I prove that the
anonymity-aware output decomposition problem is NP-hard. Therefore, I propose
an approximation algorithm called Boggart to solve the anonymity-aware output
decomposition problem.

My third work focuses on efficiently obtaining a rebalance solution to
effectively increase the success ratio of transactions in a payment channel
network. I define the utility of a rebalance transaction and the utility-aware
rebalance problem. To maximize the effect of improving the success ratio of
transactions, the utility-aware rebalance problem aims to find a set of
transactions with maximized utilities. I prove that the utility-aware rebalance
problem is NP-hard and cannot be approximately solved with a constant ratio.
Therefore, I propose two heuristic algorithms, namely Circuit Greedy and
UAR_DC.


Date:                   Friday, 15 December 2023

Time:                   4:00pm - 6:00pm

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Prof. Jiguang WANG (LIFS)

Committee Members:      Prof. Lei CHEN (Supervisor)
                        Prof. Dimitris PAPADOPOULOS
                        Prof. Qian ZHANG
                        Prof. Can YANG (MATH)
                        Prof. Jianliang XU (HKBU)


**** ALL are Welcome ****