Skip to main content

One post tagged with "Bitcoin"

View All Tags

· 11 min read
Dominik Harz

Contracts can be used to enforce agreements between entities. To this extent, smart contracts have been proposed by Nick Szabo and implemented for example in Bitcoin. This article covers the basics of mechanism design of smart contracts in the context of Bitcoin. Mechanism design is concerned with creating or encoding preferences in an agreement. Hence, an author of a smart contract can create a mechanism that enforces certain behaviour of the agents (or humans) interacting with the contract. Essentially, the author of the contract wants to reward desired behaviours and punish undesired behaviours. This is widely used in cryptocurrency protocols including the Lightning Network or Ethereum-based protocols such as Casper or TrueBit.

Use Case: Agents having access to sensors could sell the sensor data they are collecting to agents willing to buy this data. This represents a simple contract where a resource is exchanged for a price. Bitcoin in combination with payment channels secure the payments and allow for micro-payments. Thus, one has to design protocols integrating with these existing technologies to achieve for example secure decentralised data exchanges.

Bitcoin and smart contracts

Nakamoto introduced Bitcoin as a way to send money between peers without trusted third parties [2]. In Nakamoto consensus the heaviest chain is considered having correct transactions as most miners have contributed to this specific chain by solving a proof of work (PoW) puzzle. Assuming that the majority of players in the system are honest (i.e. 50%+150\% + 1), the heaviest chain represents the "true" state of the network.

Bitcoin also included the capability of executing smart contracts with Bitcoin Script [3]. A smart contract is a piece of software which formalises a relationship between entities much like a legal contract [4]. However, the idea is to use secure computer protocols and include game theoretic elements to cover aspects that cannot be adequately verified in the protocol. Szabo argues that smart contracts cover interactions including search, negotiation, commitment, performance, and adjudication.

Rational agents

Agents in decentralised systems are self-interested [5]. Hence, protocols facilitating (economic) interactions between agents need to account for autonomous agents to behave rationally. A set of agents P={1...n}P = \{1 ... n\} is considered to be rational if they seek maximise their utility uiu_i depending on some function [5] [6] [1]. This is especially relevant in decentralised systems, where we have to assume agents act only in their interest. Agents can apply multiple strategies sSs \in S within a negotiation [1]. We have to assume that agents will execute actions θΘ\theta \in \Theta based on ss that optimises their utility including cheating, lying, breaking contracts, and hiding their intentions. However, we also assume that agents that interact can find an outcome ωΩ\omega \in \Omega that increases or optimises uiu_i.

Mechanism design

Mechanism design is used to encode preferences in an agreement. Essentially, a "designer" defines a preferred social choice which, under the assumption of rational agents, the mechanism is intended to favour [6]. Considering a contract CC as an agreement between agents, CC implements a mechanism M=(Σ,g)M = (\Sigma, g) [7]. The outcome of the mechanism gg depends on the actions of agents Σ\Sigma. MM implements a rule ff. Rational agents would only enter CC or follow CC if ff is the result of the dominant strategies or Nash equilibrium of the agents.

An agent will have multiple options to enter contracts with other agents. To ensure that the proposed contract CC is chosen, we want to have it incentive compatible. Loosely speaking incentive compatibility of a mechanism occurs when the utility uiu_i of each agent ii is maximised when an agent is "truth-telling" (i.e. the dominant strategy). In games without money, non-trivial choices (e.g. more than two contracts, multiple potential agents, multiple different terms) lead either to incentive incompatibility, or the social choice function is a dictatorship according to the Gibbard--Satterthwaite theorem. However, in Bitcoin, we can construct games with money.

Games in Bitcoin

In games with money, a Vickery-Clarke-Groves (VCG) mechanism maximises social welfare. A VCG mechanism is incentive compatible. Hence an agent strives to implement a contract as such a mechanism. To construct such games the mechanism the Clarke pivot rule can be applied [6]. Agents in Bitcoin are playing a game with strict incomplete information. One could argue that an agent could potentially analyse actions of an agent as transactions are public. However, as agents might take multiple identities (Sybil), this is a non-trivial task, and thus, we will not consider it in this case. We further assume that agents have independent private values, i.e. resources subject to trade do not depend on the other agents.

Such a game can be defined as follows [6]:

  • A set of players P={1,..,n}P = \{1, .., n\} exists.
  • Every player ii has a set of actions Σi\Sigma_i.
  • Every player ii has a set of types TiT_i. A value tiTit_i \in T_i is a private input to the player.
  • Every player ii has a utility function uiu_i. The utility function depends on its private input and the actions of all players ui=(ti,σ1,..,σn)u_i = (t_i, \sigma_1, .., \sigma_n).

Hence, a player must choose an action only based on his private input but without knowing the private inputs of other agents. A strategy ss describes an agent's decision to execute a specific action based on a private input. The agent will choose ss that is the best response to any σ\sigma by other agents.

However, an agent needs to optimise a specific social choice. In Bitcoin, we are not concerned with social welfare as a social choice as this is unknown to the agents and they are not naturally interested in the utility of others. In the case that only two agents are involved and we have a simple contract concerning one resource, single-parameter domains can be applied [6]. In such domains, the valuation viv_i of an agent depends only on one parameter, say obtaining the resource. Moreover, the price an agent is willing to pay is already included in the incentive mechanism.

Yet, this would only hold for the case where two agents compete for obtaining a single resource. In more complex cases, for example, adding the quality of the data, we need to apply a more complex social choice function. In these cases, variations of VCG are the only incentive compatible mechanisms [6].

Assumptions

Using the resource exchange formalisation described in [1] the following tuple defines the exchange setting:

(P,Z,(vi)iP)(P,\mathcal{Z}, (v_{i})_{i \in P})

We are assuming that two agents exist, i.e. two players P={A,B}P = \{A, B\}. Those agents are exchanging a purely digital resource for a specific price. The agents negotiate over a single resource zZz \in \mathcal{Z}. Moreover, they use a valuation function vi:2ZRv_i : 2^{\mathcal{Z}} \to \mathbb{R}. Agent AA hence defines the value vA(z)v_A(z) individually as well as agent BB in vB(z)v_B(z).

This valuation expresses the price an agent is willing to exchange the resource for, whereby we assume that vAvBv_A \leq v_B if AA is offering the resource and BB, is willing to pay for it. Otherwise, there would be no price for them agree on. In this simple case, we assume that the agents follow the negotiation protocol truthfully and that their utility UU increases when making a deal and exchanging the resource. We further assume that the agents have a way to enter such an agreement, i.e. one of them can prepare a contract that the other one can interpret and willing to commit to.

Contract

The contract CC is implemented as an Hashed Timelock Contract (HTLC) [8] with multiple transactions in the Lightning Network. Note that AA sells data zz, and BB buys it for the agreed price pp in Satoshi. To allow agents to exchange zz and atomic swap is used. This protocol has been described for cross-chain transactions but is equally useful within a single chain [9].

  1. AA stores zz on IPFS receiving H(z)H(z). AA uses this as the secret for the HTLC and sends this to BB. As AA takes the Merkle root of zz, the data can be of (almost) any size.
  2. BB prepares a transaction transferring pp to AA spendable with the signature of AA. Also, BB includes the spending condition H(input)==H(z)H(input) == H(z) based on the IPFS hash of the file. BB is also setting a time tt after which the transaction must be spent, otherwise, BB can redeem the locked funds. Last, BB sends the transaction to AA to sign it.
  3. AA signs the transaction to agree to the trade and commits it to the channel.
  4. AA reveals the H(z)H(z) to issue the payment, which gives BB H(z)H(z). BB obtains zz through IPFS.

This contract allowed an atomic swap of the file without the need to upload the file to Bitcoin. It requires both agents to be online which is a reasonable assumption for autonomous agents. The protocol does not handle the security of the file. Any party observing H(z)H(z) can access zz without paying any price. Hence, the protocol could be extended using GPG or other asymmetric encryption schemes. In that case, AA could take BB's public RSA key to encrypt zz and then store it on IPFS. This would allow private trading of the file.

Mechanism analysis

Players: AA and BB are the only players in the game. They have the same capabilities and pre-contract the same norms. Post-contract one agent has the obligation to pay for zz and the other has an obligation to provide zz. The contract is atomic. Hence, payment and delivery occur at the same time. However, there is a possible weakness in the contract. If AA reveals H(z)H(z) without having the file stored on IPFS any more, BB will not be able to retrieve the file.

Types: Both players have a valuation v(z)v(z). AA has private access to zz.

Strategy: AA has three actions: not reveal H(z)H(z), reveal H(z)H(z) and have zz accessible, and reveal H(z)H(z) and have zz inaccessible. BB has two actions: prepare HTLC with a payment pp for AA or not. Assuming BB's valuation of vB(z)>0v_B(z) > 0, BB will propose a minimum payment. Since there is no proof of zz being available and the desired resource, BB has to account for this risk. The protocol could be improved by using concepts such as proof of replication [10]. AA will only consider revealing H(z)H(z) in the proposed HTLC if pvA(z)p \geq v_A(z). Moreover, AA might cheat BB by not making zz available. In case AA expects future trades with BB, it has a motivation to actually provide zz. BB might promise a higher pay for future interactions and adjust his valuation function to the resource zz provided by AA to a higher value since AA is based on previous direct experience trusted.

Utility: Utilities depend on the combination of strategies.

  • BB proposes HTLC with payment pp and AA reveals H(z)H(z) with zz available: uA=pvA(z)u_A = p - v_A(z) and uB=vB(z)pu_B = v_B(z) - p. Under the assumption that AA does not loose anything from selling zz.
  • BB proposes HTLC with payment pp and AA reveals H(z)H(z) with zz unavailable: uA=pvA(z)u_A = p - v_A(z) and uB=0pu_B = 0 - p.
  • BB proposes HTLC with payment pp and AA does not reveal H(z)H(z): uA=0u_A = 0 and uB=0u_B = 0.
  • BB does not propose HTLC: uA=0u_A = 0 and uB=0u_B = 0.

Social choice: Since BB proposes the contract, BB can set the social choice function. In this case, a single parameter domain is useful. The utility analysis shows that pp has the condition vA(z)pvB(z)v_A(z) \leq p \leq v_B(z). Since BB is not able to be sure that zz is available, pp will be low in the first tries as BB tries to manage his risk exposure. However, BB could argue that AA might be interested in future trades and include this as part of his utility function as an expected value. Hence, BB would only propose a contract if p<<vB(z)p << v_B(z) since otherwise the risk is too high.

References

[1] S. Fatima, S. Kraus, and M. Wooldridge, Principles of Automated Negotiation. Cambridge: Cambridge University Press, 2014 [Online]. Available: http://ebooks.cambridge.org/ref/id/CBO9780511751691

[2] S. Nakamoto, "Bitcoin: A peer-to-peer electronic cash system," 2008.

[3] Bitcoin Wiki, "Script." 2018 [Online]. Available: https://en.bitcoin.it/wiki/Script{\#}Opcodes. [Accessed: 27-Jun-2018]

[4] N. Szabo, "Formalizing and Securing Relationships on Public Networks." 1997 [Online]. Available: http://ojphi.org/ojs/index.php/fm/article/view/548/469. [Accessed: 07-Apr-2017]

[5] T. W. Sandholm and V. R. Lesser, "Leveled Commitment Contracts and Strategic Breach," Games and Economic Behavior, vol. 35, nos. 1-2, pp. 212--270, 2001.

[6] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic Game Theory, vol. 1. Cambridge: Cambridge University Press, 2007, pp. 1--754 [Online]. Available: [http://portal.acm.org/citation.cfm?doid=1785414.1785439 http://ebooks.cambridge.org/ref/id/CBO9780511800481](http://portal.acm.org/citation.cfm?doid=1785414.1785439 http://ebooks.cambridge.org/ref/id/CBO9780511800481)

[7] N. Nisan and A. Ronen, "Algorithmic Mechanism Design," Games and Economic Behavior, vol. 35, nos. 1-2, pp. 166--196, Apr. 2001 [Online]. Available: http://linkinghub.elsevier.com/retrieve/pii/S089982569990790X

[8] Bitcoin Wiki, "Hashed Timelock Contracts." 2018 [Online]. Available: https://en.bitcoin.it/wiki/Hashed{\_}Timelock{\_}Contracts. [Accessed: 28-Jun-2018]

[9] I. Bentov et al., "Tesseract: Real-Time Cryptocurrency Exchange using Trusted Hardware," 2017 [Online]. Available: http://www.cs.cornell.edu/{~}iddo/RTExchSGX.pdf

[10] A. Juels and B. Kaliski Jr., "Pors: Proofs of retrievability for large files," Proceedings of the ACM Conference on Computer and Communications Security, pp. 584--597, 2007 [Online]. Available: http://www.scopus.com/inward/record.url?eid=2-s2.0-74049101079{\&}partnerID=40{\&}md5=83cf075b3704d4fe5bfb2ccf38c39362