-
Privacy-Preserving UCB Decision Process Verification via zk-SNARKs
Authors:
Xikun Jiang,
He Lyu,
Chenhao Ying,
Yibin Xu,
Boris Düdder,
Yuan Luo
Abstract:
With the increasingly widespread application of machine learning, how to strike a balance between protecting the privacy of data and algorithm parameters and ensuring the verifiability of machine learning has always been a challenge. This study explores the intersection of reinforcement learning and data privacy, specifically addressing the Multi-Armed Bandit (MAB) problem with the Upper Confidenc…
▽ More
With the increasingly widespread application of machine learning, how to strike a balance between protecting the privacy of data and algorithm parameters and ensuring the verifiability of machine learning has always been a challenge. This study explores the intersection of reinforcement learning and data privacy, specifically addressing the Multi-Armed Bandit (MAB) problem with the Upper Confidence Bound (UCB) algorithm. We introduce zkUCB, an innovative algorithm that employs the Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARKs) to enhance UCB. zkUCB is carefully designed to safeguard the confidentiality of training data and algorithmic parameters, ensuring transparent UCB decision-making. Experiments highlight zkUCB's superior performance, attributing its enhanced reward to judicious quantization bit usage that reduces information entropy in the decision-making process. zkUCB's proof size and verification time scale linearly with the execution steps of zkUCB. This showcases zkUCB's adept balance between data security and operational efficiency. This approach contributes significantly to the ongoing discourse on reinforcing data privacy in complex decision-making processes, offering a promising solution for privacy-sensitive applications.
△ Less
Submitted 6 June, 2024; v1 submitted 18 April, 2024;
originally announced April 2024.
-
Chu-ko-nu: A Reliable, Efficient, and Anonymously Authentication-Enabled Realization for Multi-Round Secure Aggregation in Federated Learning
Authors:
Kaiping Cui,
Xia Feng,
Liangmin Wang,
Haiqin Wu,
Xiaoyu Zhang,
Boris Düdder
Abstract:
Secure aggregation enables federated learning (FL) to perform collaborative training of clients from local gradient updates without exposing raw data. However, existing secure aggregation schemes inevitably perform an expensive fresh setup per round because each client needs to establish fresh input-independent secrets over different rounds. The latest research, Flamingo (S&P 2023), designed a sha…
▽ More
Secure aggregation enables federated learning (FL) to perform collaborative training of clients from local gradient updates without exposing raw data. However, existing secure aggregation schemes inevitably perform an expensive fresh setup per round because each client needs to establish fresh input-independent secrets over different rounds. The latest research, Flamingo (S&P 2023), designed a share-transfer-based reusable secret key to support the server continuously performing multiple rounds of aggregation. Nevertheless, the share transfer mechanism it proposed can only be achieved with P probability, which has limited reliability. To tackle the aforementioned problems, we propose a more reliable and anonymously authenticated scheme called Chu-ko-nu for multi-round secure aggregation. Specifically, in terms of share transfer, Chu-ko-nu breaks the probability P barrier by supplementing a redistribution process of secret key components (the sum of all components is the secret key), thus ensuring the reusability of the secret key. Based on this reusable secret key, Chu-ko-nu can efficiently perform consecutive aggregation in the following rounds. Furthermore, considering the client identity authentication and privacy protection issue most approaches ignore, Chu-ko-nu introduces a zero-knowledge proof-based authentication mechanism. It can support clients anonymously participating in FL training and enables the server to authenticate clients effectively in the presence of various attacks. Rigorous security proofs and extensive experiments demonstrated that Chu-ko-nu can provide reliable and anonymously authenticated aggregation for FL with low aggregation costs, at least a 21.02% reduction compared to the state-of-the-art schemes.
△ Less
Submitted 15 June, 2024; v1 submitted 23 February, 2024;
originally announced February 2024.
-
A Two-Layer Blockchain Sharding Protocol Leveraging Safety and Liveness for Enhanced Performance
Authors:
Yibin Xu,
Jingyi Zheng,
Boris Düdder,
Tijs Slaats,
Yongluan Zhou
Abstract:
Sharding is essential for improving blockchain scalability. Existing protocols overlook diverse adversarial attacks, limiting transaction throughput. This paper presents Reticulum, a groundbreaking sharding protocol addressing this issue, boosting blockchain scalability.
Reticulum employs a two-phase approach, adapting transaction throughput based on runtime adversarial attacks. It comprises "co…
▽ More
Sharding is essential for improving blockchain scalability. Existing protocols overlook diverse adversarial attacks, limiting transaction throughput. This paper presents Reticulum, a groundbreaking sharding protocol addressing this issue, boosting blockchain scalability.
Reticulum employs a two-phase approach, adapting transaction throughput based on runtime adversarial attacks. It comprises "control" and "process" shards in two layers. Process shards contain at least one trustworthy node, while control shards have a majority of trusted nodes. In the first phase, transactions are written to blocks and voted on by nodes in process shards. Unanimously accepted blocks are confirmed. In the second phase, blocks without unanimous acceptance are voted on by control shards. Blocks are accepted if the majority votes in favor, eliminating first-phase opponents and silent voters. Reticulum uses unanimous voting in the first phase, involving fewer nodes, enabling more parallel process shards. Control shards finalize decisions and resolve disputes.
Experiments confirm Reticulum's innovative design, providing high transaction throughput and robustness against various network attacks, outperforming existing sharding protocols for blockchain networks.
△ Less
Submitted 12 July, 2024; v1 submitted 17 October, 2023;
originally announced October 2023.
-
Incentive Mechanism for Uncertain Tasks under Differential Privacy
Authors:
Xikun Jiang,
Chenhao Ying,
Lei Li,
Boris Düdder,
Haiqin Wu,
Haiming Jin,
Yuan Luo
Abstract:
Mobile crowd sensing (MCS) has emerged as an increasingly popular sensing paradigm due to its cost-effectiveness. This approach relies on platforms to outsource tasks to participating workers when prompted by task publishers. Although incentive mechanisms have been devised to foster widespread participation in MCS, most of them focus only on static tasks (i.e., tasks for which the timing and type…
▽ More
Mobile crowd sensing (MCS) has emerged as an increasingly popular sensing paradigm due to its cost-effectiveness. This approach relies on platforms to outsource tasks to participating workers when prompted by task publishers. Although incentive mechanisms have been devised to foster widespread participation in MCS, most of them focus only on static tasks (i.e., tasks for which the timing and type are known in advance) and do not protect the privacy of worker bids. In a dynamic and resource-constrained environment, tasks are often uncertain (i.e., the platform lacks a priori knowledge about the tasks) and worker bids may be vulnerable to inference attacks. This paper presents HERALD*, an incentive mechanism that addresses these issues through the use of uncertainty and hidden bids. Theoretical analysis reveals that HERALD* satisfies a range of critical criteria, including truthfulness, individual rationality, differential privacy, low computational complexity, and low social cost. These properties are then corroborated through a series of evaluations.
△ Less
Submitted 6 March, 2024; v1 submitted 26 May, 2023;
originally announced May 2023.
-
Distributed and Adversarial Resistant Workflow Execution on the Algorand Blockchain
Authors:
Yibin Xu,
Tijs Slaats,
Boris Düdder,
Søren Debois,
Haiqin Wu
Abstract:
We provide a practical translation from the Dynamic Condition Response (DCR) process modelling language to the Transaction Execution Approval Language (TEAL) used by the Algorand blockchain. Compared to earlier implementations of business process notations on blockchains, particularly Ethereum, the present implementation is four orders of magnitude cheaper. This translation has the following immed…
▽ More
We provide a practical translation from the Dynamic Condition Response (DCR) process modelling language to the Transaction Execution Approval Language (TEAL) used by the Algorand blockchain. Compared to earlier implementations of business process notations on blockchains, particularly Ethereum, the present implementation is four orders of magnitude cheaper. This translation has the following immediate ramifications: (1) It allows decentralised execution of DCR-specified business processes in the absence of expensive intermediaries (lawyers, brokers) or counterparty risk. (2) It provides a possibly helpful high-level language for implementing business processes on Algorand. (3) It demonstrates that despite the strict limitations on Algorand smart contracts, they are powerful enough to encode models of a modern process notation.
△ Less
Submitted 16 November, 2022;
originally announced November 2022.
-
How to Assess Trustworthy AI in Practice
Authors:
Roberto V. Zicari,
Julia Amann,
Frédérick Bruneault,
Megan Coffee,
Boris Düdder,
Eleanore Hickman,
Alessio Gallucci,
Thomas Krendl Gilbert,
Thilo Hagendorff,
Irmhild van Halem,
Elisabeth Hildt,
Sune Holm,
Georgios Kararigas,
Pedro Kringen,
Vince I. Madai,
Emilie Wiinblad Mathez,
Jesmin Jahan Tithi,
Dennis Vetter,
Magnus Westerlund,
Renee Wurth
Abstract:
This report is a methodological reflection on Z-Inspection$^{\small{\circledR}}$. Z-Inspection$^{\small{\circledR}}$ is a holistic process used to evaluate the trustworthiness of AI-based technologies at different stages of the AI lifecycle. It focuses, in particular, on the identification and discussion of ethical issues and tensions through the elaboration of socio-technical scenarios. It uses t…
▽ More
This report is a methodological reflection on Z-Inspection$^{\small{\circledR}}$. Z-Inspection$^{\small{\circledR}}$ is a holistic process used to evaluate the trustworthiness of AI-based technologies at different stages of the AI lifecycle. It focuses, in particular, on the identification and discussion of ethical issues and tensions through the elaboration of socio-technical scenarios. It uses the general European Union's High-Level Expert Group's (EU HLEG) guidelines for trustworthy AI. This report illustrates for both AI researchers and AI practitioners how the EU HLEG guidelines for trustworthy AI can be applied in practice. We share the lessons learned from conducting a series of independent assessments to evaluate the trustworthiness of AI systems in healthcare. We also share key recommendations and practical suggestions on how to ensure a rigorous trustworthy AI assessment throughout the life-cycle of an AI system.
△ Less
Submitted 28 June, 2022; v1 submitted 20 June, 2022;
originally announced June 2022.
-
BlockNet Report: Exploring the Blockchain Skills Concept and Best Practice Use Cases
Authors:
Boris Duedder,
Vladislav Fomin,
Tan Guerpinar,
Michael Henke,
Philipp Asterios Ioannidis,
Viktorija Janaviciene,
Raimundas Matulevicius,
Mubashar Iqbal,
Natalia Straub
Abstract:
In order to explore the practical potential and needs of interdisciplinary knowledge and competence requirements of Blockchain technology, the project activity "Development of Interdisciplinary Blockchain Skills Concept" starts with the literature review identifying the state of the art of Blockchain in Supply Chain Management and Logistics, Business and Finance, as well as Computer Science and IT…
▽ More
In order to explore the practical potential and needs of interdisciplinary knowledge and competence requirements of Blockchain technology, the project activity "Development of Interdisciplinary Blockchain Skills Concept" starts with the literature review identifying the state of the art of Blockchain in Supply Chain Management and Logistics, Business and Finance, as well as Computer Science and IT-Security. The project activity further explores the academic and industry landscape of existing initiatives in education which offer Blockchain courses. Moreover, job descriptions and adverts are analyzed in order to specify today's competence requirements from enterprises. To discuss and define the future required competence, expert workshops are organized to validate the findings by academic experts. Based on the research outcome and validation, an interdisciplinary approach for Blockchain competence is developed.
A second part focuses on the development of the Blockchain Best Practices activity while conducting qualitative empirical research based on case studies with industry representatives. Therefore, company interviews, based on the theoretical basis of Output 1, explore existing Blockchain use cases in different sectors. Due to the interdisciplinary importance of Blockchain technology, these skills will be defined by different perspectives of Blockchain from across multiple mentioned disciplines. The use cases and companies for the interviews will be selected based on various sampling criteria to gain results valid for a broad scale. The analysis of the various use cases will be conducted and defined in a standardized format to identify the key drivers and competence requirements for Blockchain technology applications and their adoption. On the one hand, this approach ensures comparability, on the other hand, it facilitates the development of a structured and systematic framework.
△ Less
Submitted 8 February, 2021;
originally announced February 2021.
-
BlockNet Report: Curriculum Guidance Document
Authors:
Boris Düdder,
Haiqin Wu,
Michael Henke,
Natalia Straub,
Tan Gürpinar,
Philipp Asterios Ioannidis,
Vladislav Fomin,
Raimundas Matulevičius,
Mubashar Iqbal
Abstract:
Blockchain is a challenging topic since it is novel and fosters potential innovation. The blockchain is attractive for various disciplines, and, because of its cross-cutting nature, needs knowledge stemming from various disciplines. The devised curriculum can be instantiated specifically to meet the needs of students' groups from various disciplines. The pedagogical innovation of the project is th…
▽ More
Blockchain is a challenging topic since it is novel and fosters potential innovation. The blockchain is attractive for various disciplines, and, because of its cross-cutting nature, needs knowledge stemming from various disciplines. The devised curriculum can be instantiated specifically to meet the needs of students' groups from various disciplines. The pedagogical innovation of the project is the inclusion of interdisciplinary project groups with participant's interaction via online platforms for project-based learning activities. MOOCs and SNOCs allow blended-learning for interdisciplinary and geographically distributed student groups.
△ Less
Submitted 5 February, 2021;
originally announced February 2021.
-
A $p/2$ Adversary Power Resistant Blockchain Sharding Approach
Authors:
Yibin Xu,
Jianhua Shao,
Yangyu Huang,
Tijs Slaats,
Boris Düdder
Abstract:
Blockchain Sharding is a blockchain performance enhancement approach. By splitting a blockchain into several parallel-run committees (shards), it helps increase transaction throughput, reduce computational resources required, and increase reward expectation for participants. Recently, several flexible sharding methods that can tolerate up to $n/2$ Byzantine nodes ($n/2$ security level) have been p…
▽ More
Blockchain Sharding is a blockchain performance enhancement approach. By splitting a blockchain into several parallel-run committees (shards), it helps increase transaction throughput, reduce computational resources required, and increase reward expectation for participants. Recently, several flexible sharding methods that can tolerate up to $n/2$ Byzantine nodes ($n/2$ security level) have been proposed. However, these methods suffer from three main drawbacks. First, in a non-sharding blockchain, nodes can have different weight (power or stake) to create a consensus, and as such an adversary needs to control half of the overall weight in order to manipulate the system ($p/2$ security level). In blockchain sharding, all nodes carry the same weight. Thus, it is only under the assumption that honest participants create as many nodes as they should that a $n/2$ security level blockchain sharding reaches the $p/2$ security level. Second, when some nodes leave the system, other nodes need to be reassigned, frequently, from shard to shard in order to maintain the security level. This has an adverse effect on system performance. Third, while some $n/2$ approaches can maintain data integrity with up to $n/2$ Byzantine nodes, their systems can halt with a smaller number of Byzantine nodes. In this paper, we present a $p/2$ security level blockchain sharding approach that does not require honest participants to create multiple nodes, requires less node reassignment when some nodes leave the system, and can prevent the system from halting. Our experiments show that our new approach outperforms existing blockchain sharding approaches in terms of security, transaction throughput and flexibility.
△ Less
Submitted 2 February, 2023; v1 submitted 9 April, 2020;
originally announced April 2020.
-
Mixin Composition Synthesis based on Intersection Types
Authors:
Jan Bessai,
Tzu-Chun Chen,
Andrej Dudenhefner,
Boris Düdder,
Ugo de'Liguoro,
Jakob Rehof
Abstract:
We present a method for synthesizing compositions of mixins using type inhabitation in intersection types. First, recursively defined classes and mixins, which are functions over classes, are expressed as terms in a lambda calculus with records. Intersection types with records and record-merge are used to assign meaningful types to these terms without resorting to recursive types. Second, typed te…
▽ More
We present a method for synthesizing compositions of mixins using type inhabitation in intersection types. First, recursively defined classes and mixins, which are functions over classes, are expressed as terms in a lambda calculus with records. Intersection types with records and record-merge are used to assign meaningful types to these terms without resorting to recursive types. Second, typed terms are translated to a repository of typed combinators. We show a relation between record types with record-merge and intersection types with constructors. This relation is used to prove soundness and partial completeness of the translation with respect to mixin composition synthesis. Furthermore, we demonstrate how a translated repository and goal type can be used as input to an existing framework for composition synthesis in bounded combinatory logic via type inhabitation. The computed result is a class typed by the goal type and generated by a mixin composition applied to an existing class.
△ Less
Submitted 26 February, 2018; v1 submitted 19 December, 2017;
originally announced December 2017.
-
Typing Classes and Mixins with Intersection Types
Authors:
Jan Bessai,
Boris Düdder,
Andrej Dudenhefner,
Tzu-Chun Chen,
Ugo de'Liguoro
Abstract:
We study an assignment system of intersection types for a lambda-calculus with records and a record-merge operator, where types are preserved both under subject reduction and expansion. The calculus is expressive enough to naturally represent mixins as functions over recursively defined classes, whose fixed points, the objects, are recursive records. In spite of the double recursion that is invo…
▽ More
We study an assignment system of intersection types for a lambda-calculus with records and a record-merge operator, where types are preserved both under subject reduction and expansion. The calculus is expressive enough to naturally represent mixins as functions over recursively defined classes, whose fixed points, the objects, are recursive records. In spite of the double recursion that is involved in their definition, classes and mixins can be meaningfully typed without resorting to neither recursive nor F-bounded polymorphic types.
We then adapt mixin construct and composition to Java and C#, relying solely on existing features in such a way that the resulting code remains typable in the respective type systems. We exhibit some example code, and study its typings in the intersection type system via interpretation into the lambda-calculus with records we have proposed.
△ Less
Submitted 16 March, 2015;
originally announced March 2015.
-
Using Inhabitation in Bounded Combinatory Logic with Intersection Types for Composition Synthesis
Authors:
Boris Düdder,
Oliver Garbe,
Moritz Martens,
Jakob Rehof,
Paweł Urzyczyn
Abstract:
We describe ongoing work on a framework for automatic composition synthesis from a repository of software components. This work is based on combinatory logic with intersection types. The idea is that components are modeled as typed combinators, and an algorithm for inhabitation {\textemdash} is there a combinatory term e with type tau relative to an environment Gamma? {\textemdash} can be used to…
▽ More
We describe ongoing work on a framework for automatic composition synthesis from a repository of software components. This work is based on combinatory logic with intersection types. The idea is that components are modeled as typed combinators, and an algorithm for inhabitation {\textemdash} is there a combinatory term e with type tau relative to an environment Gamma? {\textemdash} can be used to synthesize compositions. Here, Gamma represents the repository in the form of typed combinators, tau specifies the synthesis goal, and e is the synthesized program. We illustrate our approach by examples, including an application to synthesis from GUI-components.
△ Less
Submitted 30 July, 2013;
originally announced July 2013.