Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

How to Use Bitcoin to Design Fair Protocols

Iddo Bentov, Ranjit Kumaresan

Published Jan 1, 2014• 0 citations
OpenAlex

Abstract

We study a model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty. We then show how the Bitcoin network can be used to achieve the above notion of fairness in the two-party as well as the multiparty setting (with a dishonest majority). In particular, we propose new ideal functionalities and protocols for fair secure computation and fair lottery in this model. One of our main contributions is the definition of an ideal primitive, which we call F?CR (CR stands for “claim-or-refund”), that formalizes and abstracts the exact properties we require from the Bitcoin network to achieve our goals. Naturally, this abstraction allows us to design fair protocols in a hybrid model in which parties have access to the F?CR functionality, and is otherwise independent of the Bitcoin ecosystem. We also show an efficient realization of F?CR that requires only two Bitcoin transactions to be made on the network. Our constructions also enjoy high efficiency. In a multiparty setting, our protocols only require a constant number of calls to F?CR per party on top of a standard multiparty secure computation protocol. Our fair multiparty lottery protocol improves over previous solutions which required a quadratic number of Bitcoin transactions.

Related papers

Fair Two-Party Computations via the BitCoin Deposits.

Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski +1 more

Abstract. We show how the Bitcoin currency system (with a small modification) can be used to obtain fairness in any two-party secure computation protocol in the following sense: if one party aborts the protocol after learning the output then the other party gets a financial compensation (in bitcoins). One possible application of such protocols is the fair contract signing: each party is forced to complete the protocol, or to pay to the other one a fine. We also show how to link the output of this protocol to the Bitcoin currency. More precisely: we show a method to design secure two-party protocols for functionalities that result in a “forced ” financial transfer from one party to the other. Our protocols build upon the ideas of our recent paper “Secure Multiparty Computations on Bitcoin ” (Cryptology ePrint Archive, Report 2013/784). Compared to that paper, our results are more general, since our protocols allow to compute any function, while in the previous paper we concentrated only on some specific tasks (commitment schemes and lotteries). On the other hand, as opposed to “Secure Multiparty Computations on Bitcoin”, to obtain security we need to modify the Bitcoin specification so that the transactions are “non-malleable ” (we discuss this concept in more detail in the paper). 1

•Jan 1, 2013•20 citations

Amortizing Secure Computation with Penalties

Ranjit Kumaresan, Iddo Bentov

Motivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty to every other party that did not receive the output. These works show how to design protocols for secure computation with penalties that guarantees that either fairness is guaranteed or that each honest party obtains a monetary penalty from the adversary. Protocols for this task are typically designed in an hybrid model where parties have access to a "claim-or-refund" transaction functionality denote FCR*.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 24, 2016•65 citations

Constant-round linear-broadcast secure computation with penalties

Takeshi Nakai, Kazumasa Shinagawa

It is known that Bitcoin enables achieving fairness in secure computation by imposing monetary penalties on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (2014) [9] introduced the claim-or-refund functionality that can be implemented via Bitcoin. They achieved secure computation with penalties with O(n) rounds and O(n) broadcasts for any function, where n is the number of parties. After that, Kumaresan and Bentov (2014) [8] showed a constant-round protocol. Unfortunately, this protocol requires O(n2) broadcasts. As far as we know, no protocol achieves O(1) rounds and O(n) broadcasts based on Bitcoin. This work accomplishes such efficiency in secure computation with penalties. We first show a protocol in a slightly relaxed setting called secure computation with non-equivalent penalties. This setting is the same as secure computation with penalties except that every honest party receives more than a predetermined amount of compensation, while the previous one requires that every honest party receives the same amount of compensation. Namely, our setting allows the compensations for honest parties to be non-equivalent. Moreover, we present a technique to remove the non-equivalence of our protocol without sacrificing efficiency. We then propose a new ideal functionality called claim-refund-or-give that can be implemented via Bitcoin.

arXiv:2206.06010•Theoretical Computer Science•Apr 12, 2023•5 citations

Secure Computation with Non-Equivalent Penalties in Constant Rounds

Takeshi Nakai, Kazumasa Shinagawa

It is known that Bitcoin enables to achieve fairness in secure computation by imposing a monetary penalty on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (Crypto 2014) showed that it could be realized with O(n) rounds and O(n) broadcasts for any function, where n is the number of parties. Kumaresan and Bentov (CCS 2014) posed an open question: "Is it possible to design secure computation with penalties that needs only O(1) rounds and O(n) broadcasts?" In this work, we introduce secure computation with non-equivalent penalties, and design a protocol achieving this functionality with O(1) rounds and O(n) broadcasts only. The new functionality is the same as secure computation with penalties except that every honest party receives more than a predetermined amount of compensation while the previous one requires that every honest party receives the same amount of compensation. In particular, both are the same if all parties behave honestly. Thus, our result gives a partial answer to the open problem with a slight and natural modification of functionality.

OASIcs : OpenAccess Series in Informatics•Jan 1, 2022•1 citation

Secure multi-party computation with legally-enforceable fairness

Takeshi Nakai, Kazumasa Shinagawa

Abstract Fairness is a security notion of secure computation and cannot always be achieved if an adversary corrupts a majority of parties in standard settings. Lindell (CT-RSA 2008) showed that imposing a monetary penalty on an adversary can circumvent the impossibility. He formalized such a security notion as “legally enforceable fairness" for the two-party setting based on the ideal trusted bank functionality and showed a protocol achieving the requirements. Based on the same framework, we introduce secure multi-party computation with legally enforceable fairness that is applicable for an arbitrary number of parties. Further, we propose two protocols that realize our introduced functionality. The first one achieves O(n) rounds and $$O(n \alpha )$$ O ( n α ) fees, where n is the number of parties, and $$\alpha $$ α is a parameter for the penalty amount. The fee refers to the balance amount in the bank required at the beginning of the protocol, which evaluates the difficulty of participating in the protocol in a financial sense. The second one achieves O(1) rounds and $$O(n^2 \alpha )$$ O ( n 2 α ) fees.

International Journal of Information Security•Aug 29, 2024•4 citations

Resource Fairness and Composability of Cryptographic Protocols.

Juan A. Garay, Philip MacKenzie, Manoj Prabhakaran +1 more

Abstract. We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. In this model we specify the ideally fair functionality as allowing parties to “invest resources ” in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a “wrapper.”) Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. Turning to constructions, we define a “commit-prove-fair-open ” functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as “timelines.” With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security. 1

•Jan 1, 2005•16 citations
We study a model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty. We then show how the Bitcoin network can be used to achieve the above notion of fairness in the two-party as well as the multiparty setting (with a dishonest majority). In particular, we propose new ideal functionalities and protocols for fair secure computation and fair lottery in this model. One of our main contributions is the definition of an ideal primitive, which we call F?CR (CR stands for “claim-or-refund”), that formalizes and abstracts the exact properties we require from the Bitcoin network to achieve our goals. Naturally, this abstraction allows us to design fair protocols in a hybrid model in which parties have access to the F?CR functionality, and is otherwise independent of the Bitcoin ecosystem. We also show an efficient realization of F?CR that requires only two Bitcoin transactions to be made on the network. Our constructions also enjoy high efficiency. In a multiparty setting, our protocols only require a constant number of calls to F?CR per party on top of a standard multiparty secure computation protocol. Our fair multiparty lottery protocol improves over previous solutions which required a quadratic number of Bitcoin transactions.
Abstract. We show how the Bitcoin currency system (with a small modification) can be used to obtain fairness in any two-party secure computation protocol in the following sense: if one party aborts the protocol after learning the output then the other party gets a financial compensation (in bitcoins). One possible application of such protocols is the fair contract signing: each party is forced to complete the protocol, or to pay to the other one a fine. We also show how to link the output of this protocol to the Bitcoin currency. More precisely: we show a method to design secure two-party protocols for functionalities that result in a “forced ” financial transfer from one party to the other. Our protocols build upon the ideas of our recent paper “Secure Multiparty Computations on Bitcoin ” (Cryptology ePrint Archive, Report 2013/784). Compared to that paper, our results are more general, since our protocols allow to compute any function, while in the previous paper we concentrated only on some specific tasks (commitment schemes and lotteries). On the other hand, as opposed to “Secure Multiparty Computations on Bitcoin”, to obtain security we need to modify the Bitcoin specification so that the transactions are “non-malleable ” (we discuss this concept in more detail in the paper). 1
Motivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty to every other party that did not receive the output. These works show how to design protocols for secure computation with penalties that guarantees that either fairness is guaranteed or that each honest party obtains a monetary penalty from the adversary. Protocols for this task are typically designed in an hybrid model where parties have access to a "claim-or-refund" transaction functionality denote FCR*.
It is known that Bitcoin enables achieving fairness in secure computation by imposing monetary penalties on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (2014) [9] introduced the claim-or-refund functionality that can be implemented via Bitcoin. They achieved secure computation with penalties with O(n) rounds and O(n) broadcasts for any function, where n is the number of parties. After that, Kumaresan and Bentov (2014) [8] showed a constant-round protocol. Unfortunately, this protocol requires O(n2) broadcasts. As far as we know, no protocol achieves O(1) rounds and O(n) broadcasts based on Bitcoin. This work accomplishes such efficiency in secure computation with penalties. We first show a protocol in a slightly relaxed setting called secure computation with non-equivalent penalties. This setting is the same as secure computation with penalties except that every honest party receives more than a predetermined amount of compensation, while the previous one requires that every honest party receives the same amount of compensation. Namely, our setting allows the compensations for honest parties to be non-equivalent. Moreover, we present a technique to remove the non-equivalence of our protocol without sacrificing efficiency. We then propose a new ideal functionality called claim-refund-or-give that can be implemented via Bitcoin.
It is known that Bitcoin enables to achieve fairness in secure computation by imposing a monetary penalty on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (Crypto 2014) showed that it could be realized with O(n) rounds and O(n) broadcasts for any function, where n is the number of parties. Kumaresan and Bentov (CCS 2014) posed an open question: "Is it possible to design secure computation with penalties that needs only O(1) rounds and O(n) broadcasts?" In this work, we introduce secure computation with non-equivalent penalties, and design a protocol achieving this functionality with O(1) rounds and O(n) broadcasts only. The new functionality is the same as secure computation with penalties except that every honest party receives more than a predetermined amount of compensation while the previous one requires that every honest party receives the same amount of compensation. In particular, both are the same if all parties behave honestly. Thus, our result gives a partial answer to the open problem with a slight and natural modification of functionality.
Abstract Fairness is a security notion of secure computation and cannot always be achieved if an adversary corrupts a majority of parties in standard settings. Lindell (CT-RSA 2008) showed that imposing a monetary penalty on an adversary can circumvent the impossibility. He formalized such a security notion as “legally enforceable fairness" for the two-party setting based on the ideal trusted bank functionality and showed a protocol achieving the requirements. Based on the same framework, we introduce secure multi-party computation with legally enforceable fairness that is applicable for an arbitrary number of parties. Further, we propose two protocols that realize our introduced functionality. The first one achieves O(n) rounds and O(nα)O(n \alpha )O(nα) O ( n α ) fees, where n is the number of parties, and α\alpha α α is a parameter for the penalty amount. The fee refers to the balance amount in the bank required at the beginning of the protocol, which evaluates the difficulty of participating in the protocol in a financial sense. The second one achieves O(1) rounds and O(n2α)O(n^2 \alpha )O(n2α) O ( n 2 α ) fees.
Abstract. We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. In this model we specify the ideally fair functionality as allowing parties to “invest resources ” in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a “wrapper.”) Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. Turning to constructions, we define a “commit-prove-fair-open ” functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as “timelines.” With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security. 1