Loading...

Summer Research Fellowship Programme of India's Science Academies

Fairness in blockchain

B Sriram

College of Engineering Guindy, Chennai, Tamil Nadu 600025

Professor C. Pandu Rangan

Indian Institute of Technology Madras, Chennai, Tamil Nadu 600036

Abstract

Blockchain is a tamper-proof, distributed ledger that can be used to store values of any kind and can be accessed by anyone if it is public. It is the backbone of cryptocurrencies like Bitcoin and many other decentralized apps. Blockchain is used in several industries such as healthcare, real estate, banking, data storage, IoT and new use cases are being discovered. Blockchain technology market is expected to reach 60 billion USD by 2024. While blockchain has solved the double spending and Byzantine Generals problem by proof-of-work consensus method and has several use cases apart from its use as a cryptocurrency, blockchain technology still needs to efficiently solve problems such as scalability, throughput and fairness for its wide adoption. In the proposed work, we focus on the fairness of blockchain network. A technology or protocol that does not discriminate against the honest and correctly participating members is said to be fair. Transacting on a fair protocol ensures that honest parties receive the goods for their payment while the dishonest parties get penalized for their misbehavior. The definition of fairness varies for different application depending on the context. In the context of online payment for goods, fairness can be stated as getting a receipt or possibly the item for the payment by the buyer and getting the money by the seller. Though it is impossible to achieve fairness completely, we can come up with many workarounds to achieve maximal fairness. Our goal is to use blockchain as a tool for achieving fairness in online transactions.

Keywords: sharing economy, fair protocols, privacy protecting protocols, unlinkable contingent payments

Abbreviations

Abbreviations
TTransaction
 BTC Bitcoin
 HSecure hash function
HTLC  Hash Time Locked Contract 
 PK Public Key 
 MPC Multi Party Computation
 h Hashed message
 TTP Trusted Third Party
UTXO  Unspent Transcaction Output
 PCN Payment Channel Network
 ULCP Unlinkable Contingent Payments

INTRODUCTION

Background

Blockchain is an aggregate of many cryptographic primitives that enable us to perform tasks that were hard to do. However blockchain should provide fairness and protect privacy of the users for its mainstream adoption.

Blockchain

Blockchain is a cryptographic primitive where the information is stored in a block and the blocks containing information are chained together in a tamper proof way. It’s an append-only distributed ledger where its current state is replicated among several nodes. To achieve the ordering of information, a block in the blockchain links to its previous block. The nodes in the blockchain run a consensus protocol to achieve the agreement on the current state of the blockchain. 

In Bitcoin and other cryptocurrencies, transactions (mostly monetary) happening over the network are collected in block and special nodes called miners run consensus algorithm to append the block into the blockchain. In Bitcoin, a consensus algorithm called proof-of-work is followed where miners have to find a nonce value for the block that satisfies the current difficulty level set by the network.

Bitcoin algorithm

In Bitcoin [1]​, participants can create transactions to exchange bitcoins with each other. A transaction can be abstracted as a set of inputs, set of outputs and amount of coins exchanged. The total sum of the set of outputs must be less or equal to the total sum of set of inputs. The remaining input amount is given to the miner as the transaction fee. Basically, a transaction is just the transfer of UTXO from one address to the other. A transaction is valid if 

  • Inputs referenced in the transaction reference previous valid outputs.
  • Sum of inputs >= Sum of outputs
  • The inputs of the transaction have not been spent in previous blocks.
  • The scriptSig in the transaction satisfy scriptPubKeys of the referenced transactions.

Bitcoin uses proof-of-work consensus mechanism to achieve a consensus state on the blockchain. Special nodes called ‘miners’ compete with each other to solve a puzzle and the first miner that successfully publish the solution get few bitcoins as reward. Mining is the process through which new bitcoins are brought into circulation. Since the total supply of bitcoin is 21 million, the mining reward gets halved every four years. Miners also get the transaction fees associated with transactions included in the mined block as reward.

There is a possibility that two miners M1, M2 mine valid blocks B1, B2 respectively and publish them to the network at the same time. The network choose a block Bi that has the most work done. The other valid block that is not included in the chain is called a ‘orphan block’.

Block has the following structure:

  • Previous block header hash.
  • Timestamp
  • Difficulty
  • Nonce
  • Merkle Root
  • List of transactions

Miner hash the block and if the hashed value is lesser than the current difficulty set by the network, the block is valid. Miner publish this block to the network and claim the reward. The reward is specified in the coinbase transaction of the block.

This inherent structure of Bitcoin makes it vulnerable to various analyses. We shall see how the transactions made in Bitcoin can be linked together.

Fairness

In any type of trade, fairness is essential ​[2]​. Since trade is founded over trust, a participant expects that he gets what he wants in exchange for the traded items. If there is a risk that the counterparty may run way during the course of a trade, the party is discouraged to participate in the trade. In real life, a participant can trade in person to establish the trust or he may use a TTP/escrow to mediate disputes. However this includes overheads such as the availability of TTP and time taken to mediate disputes. We can use blockchain as a TTP to carry out certain trades.

Privacy in blockchain

Permissionless blockchain is a distributed ledger and the copies of blockchain are replicated in full nodes. Unless the blockchain provide an underlying privacy guarantee, all the transactions that ever occured in the network is available for everyone to see. 

In a UTXO based blockchain like Bitcoin, the inputs in a transaction refer the outputs in previous transactions. Thus the transactions made using the same addresses can be tracked and a profile can be created for the address. If the identity of the person using the address is revealed at some time, the privacy of all the addresses appearing in the transactions is broken [3].

A coin is said to be fungible if it can be interchanged with another same valued coin. A coin can be traced back to its origin just by observing the blockchain. If the inputs to the transaction appear in a malicious transaction (illegal trade, stolen coins), the coin is said to be tainted and it may not be accepted by anyone in the future as a payment. This affects fungibility of the coin and fungibility is essential to any currency.

Blind signatures

Blind signature is a cryptographic primitive which allows a person to get a message signed by the signer without revealing any content of the message to the signer. It was introduced by David Chaum in 1982.

The following is the RSA blinding protocol:

Suppose the message to be signed is mm. Suppose the private key of signer for signing the blinded message is dd.

Choose rrthat is relatively prime to NNwhere NNis a public modulus.

Raise ​ rrto the public modulus e  mod  Ne\;mod\;N

Compute m:=mre  modNm':=mr^e\;modN

Signer calculates the blinded signature as s:=(m)dmod Ns' := (m')^d mod\ Nand the sender sends ss'to sender.

Sender unblinds ss'to get s  :=  s.r1mod Ns\;:=\;s'.r^{-1} mod\ N

There are several other blinding signature scheme that work better than RSA scheme and they can be used for blinding messages.​​

Blockchain analysis heuristics

Blockchain analysis tools assumes certain heuristics to link users across multiple transactions to construct transaction graph and public key graph [3].

HEURISTIC 1. All the inputs in a transaction are controlled by the same user; i.e., for any transaction t, all PK ∈ inputs(t) are controlled by the same user.

HEURISTIC 2. The one-time change address is controlled by the same user as the input addresses; i.e., for any transaction t, the controller of inputs(t) also controls the one-time change address PK ∈ outputs(t) (if such an address exists).

However heuristic 1 is only true when the user doesn't have a single UTXO large enough for the output. In that case, user spends more than one UTXO and heuristic 1 is true. However in the cases of multisig transactions where several users cooperate to create a transaction, heuristic 1 doesn't hold. CoinJoin protocol, described in the next section, invalidates this heuristic.

Heuristic 2 doesn't hold in the cases where a user deliberately creates a transaction to invalidate it.

There are additional heuristics such as the transfer of money between participants in a transaction implies payment.

CoinJoin

CoinJoin was proposed by Gregory Maxwell [4] as a way to obfuscate the sender-receiver relationship. It breaks the heuristic 1 mentioned in the previous section that all the inputs in a transaction must have come from the same owner. The CoinJoin protocol is described below:

1. Users agree on the common denomination and create outputs by spending previous inputs.

2. Users can either use a centralized server to validate the outputs or use a decentralized mixing protocol to validate outputs.

3. In case of a centralized server, the users blind the output (see section 1.1.5) addresses while showing transaction values and input addresses and get signature from the server for blinded outputs.

4. Users unblind the outputs and submit the input and output addresses separately to the server to create a CoinJoin transaction. Since the outputs have a signature by the server, the server proceed to create the transaction.

5. Users sign the transaction and the final transaction signed by all users is submitted to the network to be included in the blockchain.

coinjoin.JPG
    CoinJoin transaction

    Properties of CoinJoin transactions:

    1. CoinJoin outputs must have equal denominations. The change address should be different from the address specified in the equal denomination output.

    2. CoinJoin's anonymity set depends on number of outputs on the transaction. So while spending the output, owner must not use more than one outputs from same CoinJoin transaction. Otherwise, the transaction can be linked and the anonymity set of the transaction decreases.

    Twotx.png
      A normal Bitcoin transaction

      Schnorr signatures

      Elliptic Curve Digital Signature Algorithm is a signature algorithm used by Bitcoin to ensure that outputs of a transcation can only be spent by the owners that possess corresponding private key. However ECDSA has issues like malleability.

      Malleability: ECDSA signatures are inherently malleable. Consider an ECDSA signature (r, s). Since the elliptic curve itself is integer mod n, the signature (r, s) is also valid. So an attacker without private key can change the signature for the transaction. However Schnorr signatures [5] are provably non-malleable.

      Linearity: Individual Schnorr signatures can be added together to produce a valid full signature for a message.

      Setup phase:

      x  :=  random  number          x\;:=\;random\;number\;\;\;\;\;

        X  :=  xG        \;X\;:=\;xG\;\;\;\;

      Sign:

      r  :=  random  numberr\;:=\;random\;number

      r  :=  rGr\;:=\;rG

      e:=H(R,message)e := H(R, message)

      s:=r+e.xs := r + e.x

      Here (R,s)(R,s)is the signature.

      Verification:

      Compute e:=H(R,message)e := H(R,message)

      Consturct s1:=(s+e.x)B=sB+e.xBs1:=(s+e.x)B=sB+e.xB

      Construct s2:=sBs2 := sB

      If s1==s2s1==s2, return true.

      Scriptless scripts

      Scriptless scripts is proposed by Andrew Poelstra [6] as a way to encode contracts inside the signature. Currently, every condition that has to be satisfied to claim the outputs of a transaction are encoded publically as the output's scriptPubKey. However scriptless scripts will allow the sender to encode conditions for claiming the outputs using just signatures. Only the receiver and sender knows the condition to be satisfied to claim the amount. The valid signature for the output can allow a receiver to claim the coins while satisfying the conditions.

      Objectives of Research

      In this work, we implement various techniques to achieve fairness in permissioned and permissionless blockchain. We also see how existing techniques like CoinJoin can be used to facilitate anonymous contingent payments.

      Scope

      Trade of information for money in blockchain has serious implications to online marketplaces. Since blockchain acts as TTP, users can rely on it to perform fair trade.

      LITERATURE REVIEW

      Cleve showed that it is impossible to achieve complete fairness without honest majority [7] . This result implies that it is impossible to securely compute with fairness any function that can be used to toss a coin fairly (or) share information.

      Payment channels are proposed as a way to scale cryptocurrency payments by moving transactions off-chain and only publish the opening and closing channel states to the blockchain. Payment channels can be combined to create PCNs to scale blockchain even more efficiently. Lightning network [8] on Bitcoin and Raiden on Ethereum aim to achieve that.

      METHODOLOGY

      Sharing Economy Model

      Here we define the organisation of a sharing economy blockchain network.

      Blackbox: The underlying blockchain.

      Members

      • Owner (PKO)
      • Renter (PKR)
      • Item/Service (ID)

      Operations

       1. Owner

      List: PKO sends the list transaction for an item/service to the blackbox (includes rent rate). The blackbox checks and validates the listing for correctness and includes it to the listing. Blackbox provides a unique ID for the item/service and link the ID with PKO.

      Properties:

      • Correctness (The listed item is valid. Requires proof of ownership)
      • Incent (Gives incentive to the miner/blackbox for listing the item. Disencourage PKO to relist the item)
      • Fairness (The blackbox cannot reject a list request unless the proof is invalid. Rejection should be included in the network with reason)

      Rent

      After getting a off-chain rent request from a PKR, PKO may either reject the request or rent the item. Availability of ID may changed to ‘unavailable’.

      Properties:

      • Relational privacy (No one in the network knows PKR requested PKO for ID)
      • Correctness (Token given for rented item is valid)
      • Fairness: PKO receives/will receive payment for the item rented.
      • Timeliness: PKO can revoke the access rights for the item he rented after a certain period of time T. PKR cannot hold onto the item indefinitely.  PKO gets to change the availability of item after time T.

      Avail: Gives PKO the power to change the availability of item/service at any time (The item is always marked unavailable during the rental time).

      Receive payment: Allows the PKO to receive payment for the listed service.

      Properties:

      • Indistinguishability: No one in the network can know if the owner received payment and how much. Owner may choose to keep the item/service ‘unavailable’. 

      2. Renter

      Search: Search for the needed item/service. The blackbox checks for availability and returns the list of available items/services (IDs) requested by the PKR.

      Rent: Request to rent an item identified by its ID. PKO may either accept or reject it. PKR is notified. PKR may either go for micropayments/fixed final payment.

      Properties:

      • Fairness: PKR gets the item/service he pays for.
      • Privacy: No one in the network knows PKR requested for ID.

      Return and payment: Return and pay for the item. PKO can now adjust availability of item.

      3. Item/service: 

      Query: Lists the item/service by ID and price if available.

      Properties: 

      • Availability: Availability marked by the owner.
      • ID: Identification by unique ID
      • Proof of ownership: Carries a valid proof of ownership.

      Ensuring fairness in a sharing economy model with a intermediary

      In [9] , the authors propose the introduction of intermediary between the owner and the user to protect their privacy. 

      The basic outline of their protocol is:

      1. User gives hash of a randomly selected message to the owner whose item he wants to use. The user has to provide the voucher containing the message and signature from the intermediary to unlock item from the owner.

      2. Owner ask intermediary to create a transaction contract Toffer(V→BTC) with the hash h under the condition that intermediary has to transfer ‘a’ bitcoin to the owner if the owner produces the voucher that fulfills the transaction Toffer(V→BTC). 

      3. Intermediary checks if the hash has been used previously and publishes the transaction to the blockchain.

      4. After this transaction has been confirmed in the blockchain, the user creates a transaction  Toffer(BTC→V ) transferring ‘a+w’ bitcoin to the intermediary under the condition that the intermediary must provide a valid blind signature for blinded message m within time t.

      5. Intermediary wait for transaction  Tfulfill(BTC→V) to confirm in blockchain to prevent double spending by the user. 

      6. After intermediary produces a blind signature through Tfulfill(BTC→V ), user unblinds the message to get the valid signature.

      7. User transfer the voucher V containing message and signature produced by intermediary to the owner.

      8. Owner creates a transaction Tfulfill(V→BTC) with the voucher V and unlocks ‘a’ bitcoins from the intermediary.

      This protocol is used to break the link between user and the owner by introducing an intermediary. The parties need not trust the intermediary. The problem with the above mentioned protocol is that it is fair towards owner and the intermediary but not the user. 

      int.JPG
        The owner may abort the protocol at the highlighted step

        Consider the following scenarios.

        1. User fails to produce voucher V within time T. Thus the user paid the money and the intermediary received it. But owner is not paid and hence the item doesn’t get unlocked.

        2. Intermediary and owner are the same person with different identities (Sybil attack). The protocol is followed completely. But user has paid ‘w’ bitcoins unnecessarily to the intermediary who also happens to be the owner.

        Hence the protocol is not fair. We can modify the protocol to be fair.

        We implement the method of Zero Knowledge Contingency Payment [10]with some modifications.

        At the start of the protocol, the owner gives the user the following items:

        1. An encrypted message M (encrypted with key K) also encrypted with public key σu of the user containing the access token to the item the user wants. 

        2. Hashes H(K), H(K m2) to the user.

        3. ZK proofs that 

        1. K unlocks the encrypted message 

        2. The access token in the encrypted message gives the user access to the item

        3. H(M) is the hash of access token and H(K m2) is hash of K m2.

        Protocol:

        1. User selects m1, m2, m3 ←{0,1}k randomly where k is the length of message and sends m2, m3 to the intermediary.

        2. The user produce a transaction paying intermediary ‘a+w’ bitcoins if the intermediary solves the HTLC h1 = H(K m2) and h2 = H(m3) within time t2.

        3. Intermediary creates a transaction paying ‘a’ bitcoin to the owner if the owner solves the hashlock h3 = H(m1) and h4=H(K) and the transaction contains H(M) as metadata.

        4. User verifies whether H(M) has been published before by the owner in the blockchain.

        5. After these two transactions get confirmed in the blockchain, user gives the owner m1 thus allowing the owner to claim ‘a’ bitcoin from the intermediary by publishing m1 and K. As soon as the value of K is posted, user can decrypt the message and access the item.

        Since intermediary got m1 needed to unlock h1 = H(K m2) and h2=H(m3), he posts the solution and receives ‘a+w’ bitcoins from the user. Due to the atomicity of this protocol, fairness is ensured. 

        Properties:

        1. Fairness:

        Since the owner cannot get bitcoins until he posts the key K and the user cannot get the item until he gives owner m1, fairness is ensured. The protocol is also fair towards intermediary since he gets K needed to unlock the transaction from the blockchain.

        2. Privacy:

        1.  Relational privacy:

        There is no link between user and the owner as there are no direct transactions between them in the blockchain. Also there are no links between h1, h2, h3 and h4.

           2. Value privacy:

        Value privacy has to be ensured by the underlying blockchain..

        3. Double spending:

        Since the transactions are confirmed on the blockchain, neither the user nor the intermediary can double spend the amount locked in the transactions.

        4. Double usage:

        User can find if the owner is giving the same token to multiple persons at the same time by checking whether H(K) is present in any previous transactions.

        Disadvantages:

        1. There must be some intermediary who should have sufficient funds to pay the owner initially and the owner must be online during the transaction.

        2. Intermediary, owner and the user know each other’s identities (Public Keys).

        This protocol can be implemented directly into blockchains like Bitcoin and Ethereum without any changes to the protocol. After learning M, user can use it to trigger a smart contract for an item.

        This protocol satisfies the fairness requirements mentioned in the previous section.

        Using CoinJoin and Schnorr signatures to achieve ULCP

        CoinJoin [4] is a technique of joining a set of inputs to a set of outputs. It’s used to break the common-input-ownership heuristic which assumes that all the inputs in a transaction must have come from the same owner. 

        Assuming an anonymous and secure CoinJoin service is available we can use Schnorr signatures for ScriptPub Keys.

        Let’s say Alice wants a secret information k from Bob in exchange for 1 BTC. 

        Public key of Bob: B=bGB = bGwhere ’b’ is the private key of Bob. 

        Bob constructs R=rGR = rG, B=bGB = bG and sends Alice s=r+H(PR+Km)b  s'=r+H(P\parallel R+K\parallel m)\ast b\;

        Bob sends (s’, R+K) to Alice along with proof that K is public point of k and s’ is valid adaptor signature (i.e. There exist a signature s such that s-s’=k).  

        Alice can verify the validity of adaptor signature by computing sG=R+H(PR+Km)B  s'G=R+H(P\parallel R+K\parallel m)\ast B\; A valid signature (s,R+T) should be published to claim the coins.

          s=r+k+H(PR+Km)b  s=r+k+H(P\parallel R+K\parallel m)\ast b\;

        scriptPubKey would be : OP_SCHNORR <sG,R+T>

        scriptSig would be : <s,R+K>

        Since Alice possess adaptor signature s’, she can extract ’t’ by s-s’ and learn the secret.

        RESULTS AND DISCUSSION

        Purpose

        Further Research

        Although the first protocol unlinks the user and owner from the blockchain, it is inherently limiting in a way that the intermediary knows the identities of user and owner, amount transferred in the transaction and the information (K) transferred. 

        We need a protocol that gives intermediary no information about the link between the owner and the user. Although the CoinJoin protocol solves the issue, it needs to be refined and it needs Schnorr softfork on the Bitcoin to work.

        Unlinkable contingent payments should be mandatorily incorporated into existing privacy protecting protocols.

        CONCLUSION

        Since fairness is essential for online trade, any protocol for transferring money should enforce fairness into its design. In this work, we described some protocols to implement fairness while preserving the privacy of involved users.

        ACKNOWLEDGEMENTS

        I’d like to thank Prof. C. Pandu Rangan for his guidance and motivation throughout the course of this internship. I’d also like to thank Arasu Arun and Karan Kashyap for the stimulating group discussions and brainstorming sessions.

        I’d like to thank IAS for offering the internship.

        I’d also like to thank my brother and relatives without whom this internship couldn’t have been completed successfully.

        References

        • S. Nakamoto. (2008) Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf

        • N Asokan. (1998) Fairness in Electronic Commerce

        • Meiklejohn S, Pomarole M, Jordan G et al. (2013) A Fistful of Bitcoins: Characterizing Payments Among Men with No Names

        • https://bitcointalk.org/?topic=279249​

        • Claus P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, 1991.

        • http://diyhpl.us/wiki/transcripts/grincon/2019/scriptless-scripts-with-mimblewimble/

        • R Cleve, 1986, Limits on the security of coin flips when half the processors are faulty, Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86

        • Poon, J., Dryja, T. (2016). The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments.

        • Liu, Z., Li, Y., Liu, Y., Yuan, D. (2018). Sharing Economy Protocol with Privacy Preservation and Fairness Based on Blockchain

        • Zero Knowledge Contingent Payment https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment

        More
        Written, reviewed, revised, proofed and published with