Financial Cryptography and Data Security : 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers

This book constitutes revised selected papers from the proceedings of the 26th International Conference on Financial Cryptography and Data Security, FC 2022, which was held in Grenada during May 2022. The 32 full papers and 4 short papers included in this book were carefully reviewed andselected from 159 submissions. They were organized in topical sections as follows: tokenomics; MPC (mostly); privacy; ZKP; old-school consensus; mostly payment networks; incentives; not proof of work; performance; measurements. Preface Organization Contents Tokenomics Maximizing Extractable Value from Automated Market Makers 1 Introduction 2 Automated Market Makers 3 The MEV Game 4 Solving the MEV Game 4.1 Price Minimization 4.2 Constructing the Inner Layers 5 Related Work 6 Conclusions References Kicking-the-Bucket: Fast Privacy-Preserving Trading Using Buckets 1 Introduction 2 Our Proposed Auction Algorithms 3 Secure Implementations of the Algorithms 3.1 Setup 3.2 Bucket Match 3.3 Volume Match 4 Leakage 5 Runtimes References Speculative Multipliers on DeFi: Quantifying On-Chain Leverage Risks 1 Introduction 2 Background 2.1 DeFi 2.2 Price Oracles 2.3 Automated Market Maker 2.4 Financial Leverage 2.5 Leverage in DeFi 2.6 Liquidations 3 On-Chain Leverage System 3.1 Formal Leverage Model 3.2 AMM Model 4 Analytical Evaluation 4.1 Impermanent Loss Risk 4.2 Arbitrage Risk 4.3 Liquidation Risk 4.4 Maximum Reasonable On-Chain Leverage 5 Empirical Evaluation 5.1 User Behavior in On-Chain Leverage Platforms 5.2 Empirical Analysis of Risks 6 Related Work 7 Conclusion References MPC (Mostly) Explainable Arguments 1 Introduction 1.1 Contribution 1.2 Related Work 2 Preliminaries 3 Explainable Arguments 3.1 Interactive Explainable Arguments 3.2 Non-interactive Explainable Arguments 4 Non-interactive Explainable Arguments 5 Robust-Witness Encryption and Interactive Explainable Arguments 5.1 Fully Explainable Arguments from Robust Witness Encryption 6 Applications 7 Conclusions References MPCCache: Privacy-Preserving Multi-Party Cooperative Cache Sharing at the Edge 1 Introduction 2 Related Work and Technical Overview of MPCCache 3 Cryptographic Preliminaries 4 Our Decentralized MPCCache Construction 4.1 A Special Case of Our First Phase 4.2 A General Case of Our First Phase 4.3 Our Second Phase: k-priority Construction 4.4 Putting All Together: MPCCache 5 Our Server-Aided MPCCache 6 Implementation 6.1 k-priority Performance 6.2 MPCCache Performance 6.3 Comparison with Prior Work References Multi-party Updatable Delegated Private Set Intersection 1 Introduction 2 Related Work 3 Preliminaries 3.1 Pseudorandom Functions and Permutation 3.2 Hash Tables 3.3 Horner's Method 3.4 Bloom Filter 3.5 Representing Sets by Polynomials 4 Feather: Multi-party Updatable Delegated PSI 4.1 An Overview of Feather's Definition 4.2 An Overview of Feather's Protocols 4.3 Feather Setup 4.4 Feather Update Protocol 4.5 Feather PSI Computation Protocol 5 Asymptotic Cost Analysis 5.1 Communication Complexity 5.2 Computation Complexity 6 Concrete Cost Evaluation 6.1 Choice of Parameters 6.2 Concrete Communication Cost Analysis 6.3 Concrete Computation Cost Analysis 7 Conclusion References Privacy The Effect of False Positives: Why Fuzzy Message Detection Leads to Fuzzy Privacy Guarantees? 1 Introduction 2 Fuzzy Message Detection 3 System and Threat Model 4 Privacy Guarantees in FMD 4.1 Recipient Unlinkability 4.2 Relationship Anonymity 4.3 Temporal Detection Ambiguity 5 Differential Privacy Analysis 6 Evaluation 6.1 Uncovering the Relationship Graph 6.2 Breaking Temporal Detection Ambiguity 7 Conclusion A FMD in More Details B Formal Definitions of Security and Privacy Guarantees C Differential Privacy Relaxations and Proofs D Game-Theoretical Analysis E Attacks on Privacy References Differential Privacy in Constant Function Market Makers 1 Introduction 2 Preliminaries 2.1 Constant Function Market Makers 2.2 Differential Privacy 3 Problem Construction 3.1 Threat Model 3.2 Simple Uniform Random Execution 3.3 Uniform Random Execution 3.4 Differential Privacy 4 Worst-Case Bounds and Path Deficiency 4.1 Mechanism Curvature 4.2 Path Deficiency 4.3 Private PAC Learning and Adversarial Bounds 5 Differentially (Non)-private MEV Reduction 6 Conclusion A Differential Privacy Results B Price Tree Height Is Close to Trade Tree Height C Proof of Claim 1 D Proof of Claim 2 E Proof of Claim 3 F Convex Trade Splitting G Splitting Trades: Concentration H Path Dependency and Generic Chaining I Path Dependency in Uniswap References Anonymous Tokens with Public Metadata and Applications to Private Contact Tracing 1 Introduction 1.1 Our Contribution 1.2 Comparison to Anonymous Credentials 1.3 Related Work 1.4 Chronology 2 Definitions for Anonymous Tokens 3 Anonymous Token Protocols 3.1 Secure Key Transformation 3.2 Anonymous Tokens with Public Metadata 3.3 Tokens with Private Metadata and Public Verification 4 Performance and Comparison 4.1 Anonymous Single-Use Tokens with Public Metadata 4.2 Comparison 4.3 Telemetry Collection in WhatsApp 5 Application to Contact Tracing 6 Conclusion References ZKP SnarkPack: Practical SNARK Aggregation 1 Introduction 2 Preliminaries 3 Pair Group Commitment Schemes 4 MT-IPP Scheme 5 SnarkPack: Aggregation Scheme A Cryptographic Primitives A.1 SNARKs A.2 Commitment Schemes A.3 Polynomial Commitments A.4 KZG Polynomial Commitment B Assumptions in GGM B.1 ASSGP Assumption in GGM B.2 ASDGP Assumption in GGM C Groth16 Scheme D Building Blocks for Aggregation D.1 Relation for MT-IPP E Final Commitment Keys References On Interactive Oracle Proofs for Boolean R1CS Statements 1 Introduction 1.1 Our Contributions 1.2 Techniques 1.3 Other Related Work 2 Preliminaries 2.1 Reverse Multiplication Friendly Embedding 2.2 R1CS, Lincheck and Rowcheck 3 Simplified Construction 3.1 Characterisation of R1CS 3.2 Linear Hashing 3.3 Modular Lincheck 3.4 An RS-Encoded IOP for R1CS from Modular Lincheck 4 Efficient Construction 4.1 Batching Modular Linchecks and Packing Vectors 4.2 An Efficient RS-Encoded IOP for R1CS 5 Comparisons References Zero Knowledge Proofs Towards Verifiable Decentralized AI Pipelines 1 Introduction 1.1 Related Work 1.2 Our Contributions 2 Verifiable Provenance in Decentralized AI Pipelines 2.1 Decentralized Model Fairness 3 Overview 3.1 Building Blocks 3.2 Optimizations 3.3 Simultaneous Permutation 3.4 Consistent Memory Access 3.5 Our Techniques in Perspective 4 Privacy Preserving Dataset Operations 5 Privacy Preserving Model Inference: Decision Trees 6 Experimental Evaluation A Preliminaries A.1 Commitment Scheme A.2 Zero Knowledge Arguments A.3 Commit and Prove SNARKs B Security Analysis C Secure Protocols C.1 Simultaneous Permutation C.2 Consistent Memory Access C.3 Aggregation Operation References Old-School Consensus Be Aware of Your Leaders 1 Introduction 2 Model and Problem Definition 2.1 Leader-Aware SMR 3 Leader-Aware SMR: The Framework 3.1 Leader-Based Round (LBR) 3.2 The Pacemaker 3.3 Leader-Rotation - The Missing Component 4 Carousel: A Novel Leader-Rotation Algorithm 4.1 Correctness 5 Implementation 6 Evaluation 6.1 Benchmark in Ideal Conditions 6.2 Performance Under Faults 7 Conclusions A Correctness References Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback 1 Introduction 2 Preliminaries 3 Jolteon Design 4 Ditto Design 5 Implementation 6 Evaluation 6.1 Evaluation of Jolteon 6.2 Evaluation of Ditto 7 Related Work 8 Conclusion References Quick Order Fairness 1 Introduction 2 Related Work 3 System Model and Preliminaries 4 Revisiting Order Fairness 4.1 Limitations 4.2 Differential Order-Fairness 5 Quick Order-Fair Atomic Broadcast Protocol 5.1 Overview 5.2 Implementation 6 Complexity 7 Conclusion References Mostly Payment Networks Analysis and Probing of Parallel Channels in the Lightning Network 1 Introduction 2 Background 3 Probing Model 3.1 Examples 3.2 Generalized Geometrical Model 3.3 Challenge of Probing Multi-channel Hops 3.4 Enhanced Probing 4 Evaluation 4.1 Data Source 4.2 Metrics 4.3 Results 5 Discussion 5.1 Limitations 5.2 Attack Cost and Trade-Offs 5.3 Payment Flow Inference 5.4 Countermeasures 6 Related Work 7 Conclusion References Hide & Seek: Privacy-Preserving Rebalancing on Payment Channel Networks 1 Introduction 2 Preliminaries 2.1 Payment Channels Networks 2.2 Network Flows 3 Protocol Overview and Model 3.1 System Model 3.2 Protocol Overview 3.3 Desired Properties and Threat Model 4 The Hide & Seek Protocol 4.1 Exploration Phase 4.2 Execution Phase 5 Analysis 6 Limitations and Extensions 7 Related Work 8 Conclusion and Future Work 9 Appendix: Reduction of the Rebalancing Problem to Min-Cost Flow References Short Paper: A Centrality Analysis of the Lightning Network 1 Introduction 1.1 Our Contributions 1.2 Related Work 1.3 Organization 2 Preliminaries 3 Methodology 4 Centrality Analysis 4.1 Historic Betweenness Analysis of the Lightning Network 4.2 Inequality in the Lightning Network 4.3 Analysis of the Top 10 Nodes 5 Future Work References Resurrecting Address Clustering in Bitcoin 1 Introduction 2 Building a Ground Truth Data Set 2.1 Data Collection and Overview 2.2 Refining the Candidate Set of Ground Truth Transactions 2.3 Assessing the Final Set of Ground Truth Transactions 2.4 Data Release 3 Predicting Change Outputs 3.1 Assessing Individual Change Heuristics 3.2 Threshold Vote 3.3 Random Forest Classifier 3.4 Additional Model Validation 4 Clustering Change Outputs 4.1 Naive Merging Leads to Cluster Collapse 4.2 Constraints Prevent Cluster Collapse 5 Impact on Blockchain Analyses 5.1 Increased Cashout Flows from Darknet Markets to Exchanges 5.2 Improved Estimate of Velocity 5.3 Comparison to the Meiklejohn et al. Heuristic 6 Conclusion References Incentives ABSNFT: Securitization and Repurchase Scheme for Non-Fungible Tokens Based on Game Theoretical Analysis 1 Introduction 1.1 Main Contributions 1.2 Related Works 2 NFT Securitization and Repurchase Scheme 2.1 Basic Setting of NFT Smart Contract 2.2 NFT Securitization Process 2.3 NFT Repurchase Process 2.4 NFT Restruction Process 3 Two-Player Repurchase Stackelberg Game 3.1 Analysis Under Complete Information 3.2 Analysis of Bayesian Stackelberg Equilibrium 4 Repeated Two-Player Stackelberg Game 5 Multi-player Repurchase Stackelberg Game 5.1 Analysis of Stackelberg Equilibrium 6 Discussion 6.1 A Blockchain Solution to Budget Constraints 6.2 A Blockchain Solution to Lazy Bidders 7 Conclusion References Decentralisation Conscious Players and System Reliability 1 Introduction 2 Modelling System Reliability and Normalised Total Effort 3 Equilibria Between Decentralisation Conscious Players 3.1 The Impact of a Reward 3.2 Social Optimum 4 Robustness of Decentralisation Conscious Players to Variations by Others 4.1 Change in Number of Players 4.2 Deviation from an Equilibrium 4.3 Non-myopic Players 4.4 Coalition-Resistance 5 Dynamics of Decentralisation Conscious Players 6 Discussion 6.1 The Role of Decentralisation Conscious Players 6.2 Modelling Constraints 6.3 Related Work 7 Conclusion References Towards Overcoming the Undercutting Problem 1 Introduction 1.1 Contributions 1.2 Related Work 2 Preliminaries 3 Mining Game Featuring Undercutting Strategy 3.1 Miner's Winning Probability 4 Game Analysis 4.1 Giving Up if One Block Behind 5 System Evaluation 5.1 Data Collection and Experiment Setup 5.2 Experiment Results 6 Conclusion A Giving Up After Two Blocks Behind References Arbitrage Attack: Miners of the World, Unite! 1 Introduction 1.1 Related Work 1.2 Our Contributions 2 Preliminaries 2.1 Blockchains 2.2 Oracle 3 Decentralized Oracle Model 3.1 Participants 3.2 Enquiry Process 4 Arbitrage Attack 4.1 Mining Pools' Influence on Decentralized Oracle 4.2 Arbitrage Attack Model 4.3 Attack Feasibility 5 Game Theory Analysis 5.1 Game Model Forming 5.2 Nash Equilibrium Strategy 5.3 Price of Anarchy 6 Conclusion, Limitations and Extensions A Proofs B Algorithm References Suborn Channels: Incentives Against Timelock Bribes 1 Introduction 2 Background and Notation 2.1 Bitcoin 2.2 Payment Channels 3 Incentive Analysis 3.1 Model 3.2 Conditionally Timelocked Game and Analysis 4 Timelock Bribe Analysis 4.1 Timelock Bribe 4.2 Timelock Bribe in DMC 4.3 Improving DMC Incentives: Simple Suborn Channels 4.4 Incentivizing DMC Across Branches: Suborn Channels 4.5 Timelock Bribe in LN 4.6 Fixing LN Incentives 5 Related Work 6 Conclusion and Future Work 6.1 Future Work 6.2 Conclusion A Suborn Transactions Script for Incentivized DMC B Omitted Proofs References Sliding Window Challenge Process for Congestion Detection 1 Introduction 2 Related Work 3 Preliminaries and Definitions 3.1 Challenge-Response Protocols 3.2 Blockchain Congestion 3.3 Desirable Properties of Protocols 4 Uncongested Period Protocols 4.1 Strawman Protocols 4.2 Sliding Window (K-out-of-N) Protocol 4.3 Application to Challenge-Response Protocols 5 Implementation 6 Conclusion References Short Paper: On Game-Theoretically-Fair Leader Election 1 Introduction 2 Model 2.1 Coalition Resistant Protocols 3 Lower Bound 4 Conclusion References Not Proof of Work The Availability-Accountability Dilemma and Its Resolution via Accountability Gadgets 1 Introduction 1.1 Accountability and Dynamic Participation 1.2 Availability-Accountability Dilemma and Resolution via Accountability Gadgets 1.3 Related Work 1.4 Outline 2 Model 3 The Availability-Accountability Dilemma 4 Accountability Gadgets 4.1 Protocol Description 4.2 Security Properties 5 Experimental Evaluation References Three Attacks on Proof-of-Stake Ethereum 1 Introduction 2 Proof-of-Stake Ethereum: The Gasper Protocol 2.1 Model 2.2 Protocol 3 A Refined Reorg Attack 3.1 Motivation 3.2 Refined Reorg Strategy 4 A Refined Liveness Attack 4.1 Motivation 4.2 High-Level Idea 4.3 Detailed Description 4.4 Experimental Evaluation 5 Reorg Attack Using Probabilistic Network Delay 5.1 Motivation 5.2 Refined Strategy Using Probabilistic Network Delay 6 Discussion 6.1 Ex Ante vs Ex Post Reorgs 6.2 Reaping Higher Fees and MEV via the Attack 6.3 Reorgs Cause Attestation Overflow 6.4 Delaying Finality References Permissionless Consensus in the Resource Model 1 Introduction 1.1 Overview of Our Model 1.2 Main Results 1.3 Technical Overview 1.4 Related Work 1.5 Paper Organization 2 Graph Consensus Problem 2.1 Preliminaries for Graphs 2.2 Graph Consensus Protocol 3 Main Protocol 3.1 Protocol Description 3.2 Theorem Statement 3.3 Proof Overview References Performance Plumo: An Ultralight Blockchain Client 1 Introduction 2 Overview 3 Threat Model 4 Ultralight Clients 4.1 Ultralight Clients 4.2 An Ultralight Client Compiler 4.3 The Plumo Ultralight Client 5 SNARK-Friendly Signatures and Hashing 5.1 BBSGLRY: Non-interactive Aggregate Multisignatures 5.2 Composite Algebraic-Symmetric Hash Functions 6 Implementation 6.1 Optimizations 6.2 Evaluation References SoK: Blockchain Light Clients 1 Introduction 1.1 What is a Light Client? 1.2 Light Client Implementations in Major Blockchain Systems 1.3 Related Systematization of Knowledge Works 2 Cryptographic Building Blocks 2.1 Succinct Set Representation and Proofs 2.2 Hash Functions and Signatures 3 Definitions 3.1 Light Client Properties 3.2 Underlying Assumptions 4 Generic Techniques to Build Light Clients 4.1 Header Verification and Consensus Evolution 4.2 Compressing the State 4.3 Removing the State 4.4 Leveraging Game-Theoretic Assumptions 5 Systematization Methodology 6 Existing Light Client Constructions: Insights and Gaps 6.1 Stateless Blockchains for Light Clients 6.2 Reducing Bootstrapping and Synchronization Costs 6.3 Smart-Contract Based Approaches and Blockchain Interoperability 7 Conclusion A Towards the Light Client Goal References Achieving Almost All Blockchain Functionalities with Polylogarithmic Storage 1 Introduction 2 Model and Notation 3 Preliminaries 4 Trimming Protocol 5 Security Definitions 6 Security Results for Hybrid Nodes 7 Optimizing State Storage with Stateless Blockchains 8 Future Directions References Measurements Short Paper: On the Claims of Weak Block Synchronization in Bitcoin 1 Introduction 2 Background 2.1 Block Propagation in Bitcoin 2.2 Bitcoin Network Monitors 3 Our Measurements and Analysis 3.1 Empirical Evidence of Inaccurate Measurements 3.2 Discovered Problems in Two Monitors 3.3 Block Propagation Measured by Our Fixed RPC-based Monitor 3.4 Justification of Fast Block Propagation 3.5 Ethical Considerations 4 Future Work 5 Conclusion References India's ``Aadhaar'' Biometric ID: Structure, Security, and Vulnerabilities 1 Introduction 1.1 Paper Overview 2 Background 2.1 Related Work 3 Snapshot: Aadhaar System Design 3.1 Enrollment Ecosystem 3.2 Authentication Ecosystem 3.3 CIDR (Central Identities Data Repository) 4 Security Landscape 4.1 Hardware Security and Certification 4.2 Key Management and Device Registration 4.3 Biometric Deduplication and Locking 5 Security, Privacy and Attacks 5.1 Threat Actors 5.2 Forbidden Attack: A Cryptographic Challenge 5.3 Privacy Issues 6 Media Allegations Analysis 7 Conclusion A Background B Abbreviations C Supplementary Material References Short Paper: What Peer Announcements Tell Us About the Size of the Bitcoin P2P Network 1 Introduction 2 Related Work 3 Background on Bitcoin Peers 4 PAL Method and Results 5 Validation 6 Observation of ADDR Spam in July and August 2021 7 Conclusion References An Empirical Study of Two Bitcoin Artifacts Through Deep Learning 1 Introduction 2 Related Work 2.1 Code Stylometry 2.2 Text-Based Bitcoin Authorship Attribution 3 Deep Learning for Bitcoin Artifacts 4 Source Code Tracing: Tracing the Authorship of Bitcoin V0.1.0 4.1 Data Collection 4.2 Data Balancing with Mutants 4.3 Data Preprocessing, Modeling, and Validation 4.4 Prediction Results and Interpretation 5 Document Tracing: Tracing the Authorship of the Bitcoin White Paper 5.1 Data Collection 5.2 Data Modeling 5.3 Prediction Results and Interpretation 6 Discussions 7 Summary References Author Index This book constitutes revised selected papers from the proceedings of the 26th International Conference on Financial Cryptography and Data Security, FC 2022, which was held in Grenada during May 2022. The 32 full papers and 4 short papers included in this book were carefully reviewed and selected from 159 submissions. They were organized in topical sections as follows: tokenomics; MPC (mostly); privacy; ZKP; old-school consensus; mostly payment networks; incentives; not proof of work; performance; measurements