notes/Nash (Link Bibliography)

“notes/​Nash” links:

  1. 2013-nashx-howitworks.html




  5. 2014-zimbeck.pdf: ⁠, David Zimbeck (2014-06-07; economics):

    Crypto-currency is a form of decentralized digital currency that has changed the world of finance over the past several years. Bitcoin[6] lacks a central authority and protects anonymity, while allowing a relatively low-cost alternative to fiat. It opens the doors for international exchange of commodities and has the potential to change how business is conducted.

    The signature and scripting system that uses allows for the creation of smart contracts. Also using signatures, it is possible to create accounts that require multiple signatures (multisig accounts) as well as transactions with multiple inputs and outputs. There has been discussion of some of the current weaknesses with smart contracts.

    We address these weaknesses to make smart contracts immediately accessible on the Bitcoin network. As proposed, this protocol offers a system of commitment schemes and business protocols that greatly reduces the issues of extortion and malleability from two-party escrow⁠.

  6. 2015-bigi.pdf: ⁠, Giancarlo Bigi, Andrea Bracciali, Giovanni Meacci, Emilio Tuosto (2015-11-20; economics):

    Decentralised smart contracts represent the next step in the development of protocols that support the interaction of independent players without the presence of a coercing authority. Based on protocols à la BitCoin for digital currencies, smart contracts are believed to be a potentially enabling technology for a wealth of future applications.

    The validation of such an early developing technology is as necessary as it is complex. In this paper we combine game theory and formal models to tackle the new challenges posed by the validation of such systems [as ].

    …The purpose of BitHalo is to create unbreakable trade contracts without the need of arbiters or escrow agents, lowering substantially the costs for the 2 parties involved in the contract. Since it does not require trust, nothing in the BitHalo system is centralised. It does not require a server, just the Internet. Its peer-to-peer communication system allows the 2 parties to use email, Bitmessage, IRC, or other methods to exchange messages and data. BitHalo is off-blockchain in the sense that the record of BitHalo contracts is not kept in the blockchain, and therefore the use of BitHalo will not bloat the blockchain.

    BitHalo can be used for bartering, self-insuring, backing commodities, performing derivatives, making good-faith employment contracts, performing 2-party escrow, and more general business contracts.

    Transactions are insured by a deposit in one of the supported digital currencies (including BTC) on a joint account, double-deposit escrow. The BitHalo protocol forces each party to uphold the contract in order to achieve the most economically optimal outcome. In a typical contract exchanging a payment for goods or services, the payment can be sent either separately, using checks, money transfer, crypto-currencies, etc., or paid directly with the deposit. The deposit will only be refunded to both parties on shared consent, which has to be expressed by both parties. In the lack of expression of shared consent, the joint account will self-destruct after a time-out. Time limits and deposit amounts are all flexible and agreed upon by both parties. Dissatisfaction about the outcome of the transaction by one of the parties, for instance because of theft or deception, will lead to the destruction of the deposit due to the lack of shared consensus. When the deposit exceeds the amount being transacted, the loss typically results larger than the benefits possibly obtainable by a fraudulent behaviour. However, deposits exceeding the transacted amount may be in some cases unfeasible. In some situations, smaller deposits may incentivize one or both parties to break the contract.

    …As standard, DSCP allows 2 parties, ie. the 2 players of the protocol, to autonomously exchange money against goods without the need of a centralised arbiter. It is worth remarking that the 2 players are completely independent, not subject to any third party authority in the execution of the exchange protocol, and can, for instance, decide to leave the protocol at any time…DSCP is based on the mentioned notion of “enforced trust” in the fact that none of the 2 parties will ever be in a position in which breaking the protocol is for them advantageous. We will see that this, as expected, will be properly enforced only when the deposit, whose payment is a pre-requisite for the execution of the protocol, exceeds the value of the goods.

  7. 2018-hasan.pdf: ⁠, Haya R. Hasan, Khaled Salah (2018-06-22; economics):

    To date, building a highly trustworthy, credible, and decentralized proof of delivery (POD) systems to trace and track physical items is a very challenging task. This paper presents a blockchain based POD solution of shipped physical items that uses smart contracts of Ethereum blockchain network, in which tracking, and tracing activities, logs, and events can be done in a decentralized manner, with high integrity, reliability, and immutability.

    Our solution incentivizes each participating entity including the seller, transporter, and buyer to act honestly, and it totally eliminates the need for a third party as escrow. Our proposed POD solution ensures accountability, punctuality, integrity and auditability. Moreover, the proposed solution makes use of a Smart Contract Attestation Authority to ensure that the code follows the terms and conditions signed by the participating entities. It also allows the cancellation of the transaction by the seller, buyer and transporter based on the contract state. Furthermore, the buyer can also ask for a refund in certain justifiable cases.

    The full code, implementation discussion with sequence diagrams, testing and verification details are all included as part of the proposed solution.

    [Keywords: proof of delivery, blockchain, Ethereum, smart contracts]

  8. 2015-05-04-p2pox-overview.html

  9. 2016-kopp.pdf: ⁠, Henning Kopp, Christoph Bösch, Frank Kargl (2016-11-05; economics):

    One of the current problems of peer-to-peer-based file storage systems like Freenet is missing participation, especially of storage providers. Users are expected to contribute storage resources but may have little incentive to do so. In this paper we propose KopperCoin, a token system inspired by Bitcoin’s blockchain which can be integrated into a peer-to-peer file storage system.

    In contrast to Bitcoin, KopperCoin does not rely on a proof of work (PoW) but instead on a proof of retrievability (PoR). Thus it is not computationally expensive and instead requires participants to contribute file storage to maintain the network. Participants can earn digital tokens by providing storage to other users, and by allowing other participants in the network to download files. These tokens serve as a payment mechanism.

    Thus we provide direct reward to participants contributing storage resources.

    [Keywords: blockchain, cloud storage, cryptocurrency, peer-to-peer, proof of retrievability]

    3.4: Fetching Files: In order to fetch a file the client application needs to know the identifiers of the corresponding chunks. The file is restored by retrieving sufficiently many chunks. For successful retrieval not all chunks have to be fetched, depending on the erasure code that was applied before storing the file in the KopperCoin-network. The erasure code solves the problem of missing chunks and storage providers demanding unrealistically high prices for chunk retrieval.

    Fetching chunks works with 2-of-2 multi-signature transactions. These are transactions which can be spent if and only if 2 out of 2 parties agree to spend them. To our knowledge the mechanism was first used by NashX [23].

    Let U be a user who wants to retrieve a chunk which is stored at the provider P. Suppose U wants to pay the amount p for retrieving his file. Then U and P create a 2-of-2 multi-signature transaction where the user U inputs β+p and P inputs α . The amounts α and β are security deposits. In a next step P sends the chunk to U. The user U checks if he has received the correct chunk. In that case he signs a multi-signature transaction with 2 outputs: The provider P gets back his security deposit α, together with the price p for the chunk. In the other output the user U gets back his security deposit β. The process is illustrated in Figure 1. Above the arrows are the amounts and below the arrows are the owners of the respective amounts.

    If U wants to cheat he cannot set his security deposit β to zero or otherwise change the first transaction since this will be detected by the provider P who then refuses to sign. Nevertheless the user U can refuse to sign the 2-of-2 multi-signature transaction after retrieving the chunk, thereby losing his security deposit β.

    If the provider P cheats he can either refuse to send the chunk or refuse to sign the 2-of-2 multi-signature transaction. In both cases he will suffer a financial damage of his security deposit α and not receive the price p for retrieval of the chunk.


  11. ⁠, Aditya Asgaonkar, Bhaskar Krishnamachari (2018-06-21):

    A fundamental problem for electronic commerce is the buying and selling of digital goods between individuals that may not know or trust each other. Traditionally, this problem has been addressed by the use of trusted third-parties such as credit-card companies, mediated escrows, legal adjudication, or reputation systems. Despite the rise of blockchain protocols as a way to send payments without trusted third parties, the important problem of exchanging a digital good for payment without trusted third parties has been paid much less attention. We refer to this problem as the Buyer and Seller’s Dilemma and present for it a dual-deposit escrow trade protocol which uses double-sided payment deposits in conjunction with simple cryptographic primitives, and that can be implemented using a blockchain-based smart contract. We analyze our protocol as an extensive-form game and prove that the Sub-game Perfect Nash Equilibrium for this game is for both the buyer and seller to cooperate and behave honestly. We address this problem under the assumption that the digital good being traded is known and verifiable, with a fixed price known to both parties.

  12. 2011-witkowski.pdf: ⁠, Jens Witkowski, Sven Seuken, David C. Parkes (2011-08-04; economics):

    The most prominent way to establish trust between buyers and sellers on online auction sites are reputation mechanisms. 2 drawbacks of this approach are the reliance on the seller being long-lived and the susceptibility to whitewashing. In this paper, we introduce so-called escrow mechanisms that avoid these problems by installing a trusted intermediary which forwards the payment to the seller only if the buyer acknowledges that the good arrived in the promised condition.

    We address the incentive issues that arise and design an escrow mechanism that is incentive-compatible, efficient, interim individually rational and ex ante budget-balanced. In contrast to previous work on trust and reputation, our approach does not rely on knowing the sellers’ cost functions or the distribution of buyer valuations.

  13. 2020-mamageishvili.pdf: ⁠, Akaki Mamageishvili, Jan Christoph Schlegel (2020-05-06; economics):

    We study optimal smart contract design for monitoring an exchange of an item performed offline.

    There are 2 parties, a seller and a buyer. Exchange happens off-chain, but the status update takes place on-chain. The exchange can be verified but with a cost. To guarantee self-enforcement of the smart contract, both parties make a deposit, and the deposits must cover payments made in all possible final states. Both parties have an (opportunity) cost of making deposits.

    We discuss 2 classes of contract: In the first, the mechanism only interacts with the seller, while in the second, the mechanism can also interact with the buyer. In both cases, we derive optimal contracts specifying optimal deposits and verification policies.

    The gains from trade of the first contract are dominated by the second contract, on the whole domain of parameters. However, the first type of contract has the advantage of less communication and, therefore, more flexibility.

  14. ⁠, John Wentsworth (2020-11-08):

    A crew of pirates all keep their gold in one very secure chest, with labeled sections for each pirate. Unfortunately, one day a storm hits the ship, tossing everything about. After the storm clears, the gold in the chest is all mixed up. The pirates each know how much gold they had—indeed, they’re rather obsessive about it—but they don’t trust each other to give honest numbers. How can they figure out how much gold each pirate had in the chest?

    Here’s the trick: the captain has each crew member write down how much gold they had, in secret. Then, the captain adds it all up. If the final amount matches the amount of gold in the chest, then we’re done. But if the final amount does not match the amount of gold in the chest, then the captain throws the whole chest overboard, and nobody gets any of the gold.

    I want to emphasize two key features of this problem. First, depending on what happens, we may never know how much gold each pirate had in the chest or who lied, even in hindsight. Hindsight isn’t 20/​​​​20. Second, the solution to the problem requires outright destruction of wealth.

    The point of this post is that these two features go hand-in-hand. There’s a wide range of real-life problems where we can’t tell what happened, even in hindsight; we’ll talk about three classes of examples. In these situations, it’s hard to design good incentives/​​​​mechanisms, because we don’t know where to allocate credit and blame. Outright wealth destruction provides a fairly general-purpose tool for such problems. It allows us to align incentives in otherwise-intractable problems, though often at considerable cost.

    …Alice wants to sell her old car, and Bob is in the market for a decent quality used vehicle…Alternatively, we could try to align incentives without figuring out what happened in hindsight, using a trick similar to our pirate captain throwing the chest overboard. The trick is: if there’s a mechanical problem after the sale, then both Alice and Bob pay for it. I do not mean they split the bill; I mean they both pay the entire cost of the bill. One of them pays the mechanic, and the other takes the same amount of money in cash and burns it. (Or donates to a third party they don’t especially like, or …) This aligns both their incentives: Alice is no longer incentivized to hide mechanical problems when showing off the car, and Bob is no longer incentivized to ignore maintenance or frequent the racetrack.

    However, this solution also illustrates the downside of the technique: it’s expensive.

    [See also the exploding Nash equilibrium⁠. This parallels Monte Carlo/​​​​evolutionary solutions to RL blackbox optimization: by setting up a large penalty for any divergence from the golden path, it creates an unbiased, but high variance estimator of credit assignment. When ‘pirates’ participate in enough rollouts with enough different assortments of pirates, they receive their approximate ‘honesty’-weighted (usefulness in causing high-value actions) return. You can try to pry open the blackbox and reduce by taking into account ‘pirate’ baselines etc, but at the risk of losing unbiasedness if you do it wrong.]