François-Xavier Wicht

Untraceability mechanisms in privacy-preserving cryptocurrencies impose constraints on system design. We study how different untraceability notions affect the synchronization power of systems that maintain sender privacy by atomically updating sets of accounts, where only some accounts have their balances modified while others are updated purely for privacy. We introduce the constant untraceable asset transfer (CUAT) object, a shared-memory abstraction with confidentiality and sender untraceability. Each transfer operates on an anonymity set of fixed size λ and atomically invalidates old accounts while creating new ones for all members. When two transfers use overlapping anonymity sets, at most one can succeed, forcing coordination between processes. We characterize the consensus number through the conflict graph on anonymity sets, and we organize the analysis by the round structure of transfers: one-round protocols, in which each process makes a single transfer, and multi-round protocols, in which a process may perform several transfers and adapt later ones to earlier outcomes. One-round protocols force the masking sets to form a clique in the conflict graph; multi-round protocols only require a bipartite intersection across two valency classes, and the consensus number can strictly exceed the one-round value. Under weak untraceability, which protects against adversaries observing a single transaction, CUAT has unbounded consensus number already with one-round protocols. Under strong untraceability, which protects against adversaries observing complete transaction histories, we prove an exact characterization: strong untraceability holds on a history if and only if every account appears in the same number of anonymity sets across that history. Uniformity constrains both the conflict graph’s clique number and a refined incidence-based count over the bipartite biclique at a critical configuration, yielding upper bounds in both the one-round and multi-round regimes; for an infinite family of anonymity-set sizes, projective-plane constructions match these bounds and we determine the consensus number exactly. Finally, we show that no CUAT implementation can guarantee starvation-freedom under asynchronous scheduling. These results characterize the relationship between untraceability requirements and synchronization power in constant-state private payment systems.

Private BitTorrent trackers enforce upload-to-download ratios to prevent free-riding, but suffer from three critical weaknesses: reputation cannot move between trackers, centralized servers create single points of failure, and upload statistics are self-reported and unverifiable. When a tracker shuts down, users lose their contribution history and cannot prove their standing to new communities. We address these problems by storing reputation in smart contracts and replacing self-reports with cryptographic attestations. Peers sign receipts for received pieces; the tracker aggregates them via BLS signatures and updates reputation. If a tracker is unavailable, peers fall back to an authenticated distributed hash table (DHT): stored reputation acts as a public key infrastructure (PKI), preserving access control without the tracker. Reputation is portable across tracker failures through single-hop migration in factory-deployed contracts. We also address the privacy implications of publishing public keys and reputations tied to private trackers on a public ledger: we propose ephemeral session keys to prevent linking peer identities, zero-knowledge membership proofs for anonymous DHT participation, and confidential reputation using homomorphic commitments. We formalize the security requirements, prove four security properties under standard cryptographic assumptions, and evaluate a prototype. Measurements show that transfer receipts add less than 5% end-to-end overhead with typical piece sizes. To minimize signing overhead, we adopt a hybrid signature scheme: ECDSA signs individual piece receipts at transfer time for low per-operation latency, while BLS serves as the overarching scheme, enabling compact aggregation of many receipts into a single proof at report time. This design reduces client-side signing cost by an order of magnitude compared to using BLS throughout.

Anonymous cryptocurrencies attracted much attention over the past decade, yet ensuring both integrity and privacy in an open system remains challenging. Their transactions preserve privacy because they do not reveal on which earlier transaction they depend, specifically which outputs of previous transactions are spent. However, achieving privacy imposes a significant storage overhead due to two current limitations. First, the set of potentially unspent outputs of transactions grows indefinitely because the design hides cryptographically which one have been consumed; and, second, additional data must be stored for each spent output to ensure integrity, that is, to prevent that it can be spent again. We introduce a privacy-preserving payment scheme that mitigates these issues by randomly partitioning unspent outputs into fixed-size bins. Once a bin has been referenced in as many transactions as its size, it is pruned from the ledger. This approach reduces storage overhead while preserving privacy. We first highlight the scalability benefits of using smaller untraceability sets instead of considering the entire set of outputs, as done in several privacy-preserving cryptocurrencies. We then formalize the security and privacy notions required for a scalable, privacy-preserving payment system and analyze how randomized partitioning plays a key role in both untraceability and scalability. To instantiate our approach, we provide a construction based on Merkle trees, which ensures efficient argument systems and easy pruning of the state. We finally show the storage benefits of our scheme and analyze its resilience against large-scale flooding attacks using empirical transaction data.

Considerable work explores blockchain privacy notions. Yet, it usually employs entirely different models and notations, complicating potential comparisons. In this work, we use the Transaction Directed Acyclic Graph (TDAG) and extend it to capture blockchain privacy notions (PDAG). We give consistent definitions for untraceability and unlinkability. Moreover, we specify conditions on a blockchain system to achieve each aforementioned privacy notion. Thus, we can compare the two most prominent privacy-preserving blockchains – Monero and Zcash, in terms of privacy guarantees. Finally, we unify linking heuristics from the literature with our graph notation and review a good portion of research on blockchain privacy.

Secure aggregation enables a group of mutually distrustful parties, each holding private inputs, to collaboratively compute an aggregate value while preserving the privacy of their individual inputs. However, a major challenge in adopting secure aggregation approaches for practical applications is the significant computational overhead of the underlying cryptographic protocols, e.g. fully homomorphic encryption. This overhead makes secure aggregation protocols impractical, especially for large datasets. In contrast, hardware-based security techniques such as trusted execution environments (TEEs) enable computation at near-native speeds, making them a promising alternative for reducing the computational burden typically associated with purely cryptographic techniques. Yet, in many scenarios, parties may opt for either cryptographic or hardware-based security mechanisms, highlighting the need for hybrid approaches. In this work, we introduce several secure aggregation architectures that integrate both cryptographic and TEE-based techniques, analyzing the trade-offs between security and performance.