Monthly Archives: November 2015

Watermarked tokens and pseudonymity on public blockchains

Posted on by
3

As mentioned a couple weeks ago I have published a new research paper entitled: “Watermarked tokens and pseudonymity on public blockchains”

In a nutshell: despite recent efforts to modify public blockchains such as Bitcoin to secure off-chain registered assets via colored coins and metacoins, due how they are designed, public blockchains are unable to provide secure legal settlement finality of off-chain assets for regulated institutions trading in global financial markets.

The initial idea behind this topic started about 18 months ago with conversations from Robert Sams, Jonathan Levin and several others that culminated into an article.

The issue surrounding top-heaviness (as described in the original article) is of particular importance today as watermarked token platforms — if widely adopted — may create new systemic risks due to a distortion of block reorg / double-spending incentives.  And because of how increasingly popular watermarked projects have recently become it seemed useful to revisit the topic in depth.

What is the takeaway for organizations looking to use watermarked tokens?

The security specifications and transaction validation process on networks such as the Bitcoin blockchain, via proof-of-work, were devised to protect unknown and untrusted participants that trade and interact in a specific environment.

Banks and other institutions trading financial products do so with known and trusted entities and operate within the existing settlement framework of global financial markets, with highly complex and rigorous regulations and obligations.  This environment has different security assumptions, goals and tradeoffs that are in some cases opposite to the designs assumptions of public blockchains.

Due to their probabilistic nature, platforms built on top of public blockchains cannot provide definitive settlement finality of off-chain assets. By design they are not able to control products other than the endogenous cryptocurrencies they were designed to support.  There may be other types of solutions, such as newer shared ledger technology that could provide legal settlement finality, but that is a topic for another paper.

This is a very important issue that has been seemingly glossed over despite millions of VC funding into companies attempting to (re)leverage public blockchains.  Hopefully this paper will help spur additional research into the security of watermarking-related initiatives.

I would like to thank Christian Decker, at ETH Zurich, for providing helpful feedback — I believe he is the only academic to actually mention that there may be challenges related to colored coins in a peer-reviewed paper.  I would like to thank Ernie Teo, at SKBI, for creating the game theory model related to the hold-up problem.  I would like to thank Arthur Breitman and his wife Kathleen for providing clarity to this topic.  Many thanks to Ayoub Naciri, Antony Lewis, Vitalik Buterin, Mike Hearn, Ian Grigg and Dave Hudson for also taking the time to discuss some of the top-heavy challenges that watermarking creates.  Thanks to the attorneys that looked over portions of the paper including (but not limited to) Jacob Farber, Ryan Straus, Amor Sexton and Peter Jensen-Haxel; as well as additional legal advice from Juan Llanos and Jared Marx.  Lastly, many thanks for the team at R3 including Jo Lang, Todd McDonald, Raja Ramachandran and Richard Brown for providing constructive feedback.

Watermarked Tokens and Pseudonymity on Public Blockchains

A brief literature review

Posted on by
Reply

[Note: the following literature review was originally included in a new paper but needed to be removed for space and flow considerations]

How has previous research looked at information security?

Academic literature covering distributed computing and economics of information security and specifically peer-to-peer networks “Before Bitcoin” spans several decades.

Surveying literature (Lua et al. 2004; Hoffman et al. 2007; Momani and Challa 2009) we can see that there have been dozens of attempts to create decentralized peer-to-peer reputation systems that needed to be self-organizing, Sybil-resistant and fault tolerant.1

For instance, the Content Addressable Network (CAN), Chord, Kademlia and the Cooperative File System (CFS) each had a variety of characteristics that attempted to stave off abuse from attackers due to the environments they operated in (e.g., a distributed decentralized P2P infrastructure). Some used public-private key pairs, content hashes and others used NodeID.

These surveys also looked at Distributed Hash Trees (DHT) which have been known to be vulnerable to a number of attacks including Eclipse attacks, where the peering network itself comes under attack (which Bitcoin’s network is also prone to).2

What about other game theory issues? For example in (Lua et al., 2004) the authors wrote that:3

The ability to overcome free-rider problems in P2P overlay networks will definitely improve the system’s reliability and its value.

Sybil attacked termed by Douceur4 described the situation whereby there are a large number of potentially malicious peers in the system and without a central authority to certify peers’ identities. It becomes very difficult to trust the claimed identity. Dingledine et al.,5 proposes puzzles schemes, including the use of micro-cash, which allows peers to build up reputations. Although this proposal provides a degree of accountability, this still allows a resourceful attacker to launch attacks.

This is the same problem discussed above, that (Rosenfeld 2012) runs into regarding how to pay nodes on an open network.

How do these researchers believe it could be solved or fixed? According to (Lua et al., 2004):6

Having some sort of incentive model using economic and game theories, for P2P peers to collaborate is crucial to create an economy of equilibrium. When non-cooperative users benefit from free-riding on others’ resources, the tragedy of the commons7 is inevitable. Such incentives implementation in P2P overlay services would also provide a certain level of self-regulatory auditing and accounting behavior for resource sharing.

As shown above, despite rhetoric at Bitcoin-related conferences, many of the challenges facing Bitcoin today are in fact known problems facing decentralized peer-to-peer networks in general. The problem space for preventing Sybil attacks was and is relatively well-defined, Bitcoin again side-steps the actual solution by making it economically expensive, but not technically impossible to conduct history-reversing attacks, or even Sybil attacks on the gossip network.

P2Prep is a reputation system designed to “mitigate the effects of selfish and malicious peers in an anonymous, completely decentralized system.”8

How did it do this?

The system guards the anonymity of users and the integrity of packets through the use of public key cryptography. All replies are signed using the requester’s public key, protecting the identity of the responder and the integrity of the data. Only the requester is able to decrypt the packet and check the validity of the information.9

Credence (Walsh and Sirer 2006) is another peer-to-peer reputation system that uses gossip-based techniques to disseminate information.10 It defends itself:11

A key security consideration in the Credence system is the use of mechanisms to prevent spoofed votes or votes generated by fake identities. The system guards against such attacks by issuing digital certificates in an anonymous but semi-controlled fashion. The authors propose to mitigate Sybil attacks by requiring expensive computation on the part of the client before the server grants a new digital certificate. Every voting statement is digitally signed by the originator and anyone can cryptographically verify the authenticity of any given voting statement.

In (Momani and Challa 2010) the authors looked at security and trust concepts surrounding wireless sensor networks (WSN). At first glance this may seem unrelated to peer-to-peer networks but there are many similarities:12

The security issue has been raised by many researchers [14 – 24], and, due to the deployment of WSN nodes in hazardous and/or hostile areas in large numbers, such deployment forces the nodes to be of low cost and therefore less reliable or more prone to overtaking by an adversary force. Some methods used, such as cryptographic authentication and other mechanisms [25 – 32], do not entirely solve the problem. For example, adversarial nodes can have access to valid cryptographic keys to access other nodes in the network. The reliability issue is certainly not addressed when sensor nodes are subject to system faults. These two sources of problems, system faults and erroneous data or bad routing by malicious nodes, can result in the total breakdown of a network and cryptography by itself is insufficient to solve these problems. So new tools from different domains social sciences, statistics, e-commerce and others should be integrated with cryptography to completely solve the unique security attacks in WSNs, such as node capturing, Sybil attacks, denial of service attacks, etc.

In their survey they identified previous research that had looked at some of these same issues including In (Xiong and Liu 2003) where the authors attempted to build a reputation-based trust model for peer-to-peer distributed commerce platforms and use game theory to ameliorate the trust parameters by threats from malicious attacks.13

Going back more than fifteen years we can see that other researchers (Lamport 1998) and (Castro and Liskov 1999), that successful attempts were made to “use cryptographic techniques to prevent spoofing and replays and to detect corrupted messages” on a network that replicates services in the face of Byzantine faults.14

Volumes more can and will likely be written covering the research on these specific topics due in large part to the integral role that different types of information and financial networks play in the lives of consumers and businesses alike.

  1. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes by Lua et al.; A Survey of Attack and Defense Techniques for Reputation Systems by Kevin Hoffman, David Zage and Cristina Nita-Rotaru; and Survey of trust models in different network domains by Mohammad Momani and Subhash Challa [↩]
  2. Eclipse Attacks on Bitcoin’s Peer-to-Peer Network by Heilman et al. [↩]
  3. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes by Lua et al., p. 11 [↩]
  4. J. R. Douceur, “The sybil attack,” in Proceedings of the First International Workshop on Peer-to-Peer Systems , March 7-8 2002, pp. 251– 260. [↩]
  5. R.   Dingledine,   M.   J.   Freedman,   and   D.   Molnar,   “Accountability measures for peer-to-peer systems,” in Peer-to-Peer: Harnessing the Power of Disruptive Technologies , D. Derickson, Ed.     O’Reilly and Associates, November. [↩]
  6. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes by Lua et al., p. 20 [↩]
  7. G. Hardin, “The tragedy of the commons,” Science , vol. 162, pp. 1243– 1248, 1968. [↩]
  8. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes by Lua et al., p. 28. Among other startups, Mnet was a peer-to-peer distributed data store, whose (former) employees would go on to help create BitTorrent and Tahoe-LAFS. This was during the same survey period. [↩]
  9. Ibid, p. 29 [↩]
  10. Experience with an Object Reputation System for Peer-to-Peer Filesharing by Kevin Walsh and Emin Gün Sirer [↩]
  11. A Survey of Attack and Defense Techniques for Reputation Systems by Kevin Hoffman, David Zage and Cristina Nita-Rotaru, p. 30 [↩]
  12. Survey of trust models in different network domains by Mohammad Momani and Subhash Challa [↩]
  13. A Reputation-Based Trust Model for Peer-to-Peer eCommerce Communities by Li Xiong and Ling Liu [↩]
  14. Practical Byzantine Fault Tolerance by Miguel Castro and Barbara Liskov. According to Leslie Lamport, in The Part-Time Parliament, p. 23: “The Paxon Parliament protocol provides a distributed, fault-tolerant imiplmentation of the database system.” [↩]

Integrating, Mining and Attacking: Analyzing the Colored Coin “Game”

Posted on by
2

[Note: Below is a guest post from Ernie Teo, a post-doctorate researcher at SKBI (where I am currently a visiting research fellow).  It is referenced in a new paper covering the distorted incentives for securing public blockchains.]

Integrating, Mining and Attacking: Analyzing the Colored Coin “Game”

By Ernie G. S. Teo, Sim Kee Boon Institute for Financial Economics,
Singapore Management University

The research in this post came about when Tim Swanson invited me to look at colored coin providers and their incentives from a game theory perspective. The results are based on a number of phone conversations with Tim; I would like to take the opportunity to thank Tim for his insights on the matter. For an introduction to what colored coins are, refer to Chapter 3 in Great Chain of Numbers.

The initial question Tim wanted to know was if colored coins can be identified will miners charge excessively high fees to include these transactions. The led to a discussion of the possibilities of the colored coin issuer becoming a miner; and of an attack on the network to take control of the colored assets.

The problem proved to be very interesting as there could be many implications on the success of the system given the potential costs and benefits. Entities or players within the “game” could strategically choose to sabotage themselves if the incentives were right. In this post, I will attempt to explain this using a “sequential game” format. I will explain the various stages where choices can be made and the players involved in each stage. This will be followed by an analysis of the various outcomes and the strategic choices of each party given the incentives involved.

Before we start, I would like to disclaim that the model that follows is a simplified version of the problem and helps us to think about the potential issues that could arise. They are based on various assumptions and in no way should the results be taken at face value.

Stage 1: Before the colored coin issuer (CCI) starts operations, we assume that they will consider if they will choose to become a miner (Assuming that they can include their own transactions into blocks if no one else would). The decision maker (or player) here is the CCI, the choices available are to integrate or to not integrate.

Stage 2a: When the CCI starts issuing colored coins, it would have to decide on the fees it would pay for the transaction. We assume that the CCI is a rational entity and will choose the optimal fees. However as there are two possibilities in stage 1, there will be 2 possible fees quoted; one for a CCI whom is also a miner (integrated) and another for a CCI whom is not a miner (non-integrated). The decision maker here is the CCI and the choice is the fee quoted.

Stage 2b: This is immediately followed by the miners deciding to include the transaction in the block or not. For simplicity’s sake, we assume that there is only one miner in this game (this can be the CCI). The decision maker here is the miner and the choice is to mine the transaction or not.

If the decision in Stage 2b is not to mine, the game ends (End 1).

Stage 3: We next assume that the miner can choose to fraudulently attack the system and transfers the colored coin to itself. The decision maker here is still the miner and the choice is to attack or not.

This gives us 2 alternative endings (End 2 and End 3). The game can be described by Figure 1.

Colored Coin Teo

Figure 1: The stages of the “game”

If we consider the game, there are only 2 decision makers or players: The CCI and the miner. Next, we consider what are the possible outcomes or payoffs for each possible ending described above. This is described in Figure 2 below, there are actually 6 possibilities as there are 2 types of CCIs, integrated and non-integrated. When there is integration, there is really only one player.

Colored Coin Teo 2

Figure 2: Payoffs of the game

Having setup the game and determined the payoffs, we analyze the possibilities of each outcome. This is subject to the comparative magnitude of each payoff. Let’s start with the non-integrated outcomes, there are 3 possibilities:

  1. Not Integrated. Mined. Attacked.
  2. Not Integrated. Mined. Not Attacked.
  3. Not Integrated. Not Mined.

An attack happens if M3>M2 (this will happen if the net benefit of the attack is positive).

If M3>M2, the transaction will be mined if M3>M1. This is because the miner expects the attack to take place, the miner will thus only mine the transaction if it the payoff from mining and attacking is better than not mining. Since we assumed that M1=0, M3 will be always larger than M1. Thus When M3>M2, mining always takes place and an attack happens.

If M2>M3, the attack will not happen (this would indicate that the net benefits of the attack is negative). The transaction will be mined if M2>M1 or if the transaction fees are positive.

The transaction will not be mined if M1≥M2. Since M2 (the transaction fee) has to be at least zero, if M2=0, the transaction will not be mined.

To summarize, there are 3 scenarios:

  1. M3>M2≥M1: The transaction is mined and an attack takes place. The CCI gets CC3NI.
  2. M2>M3 and M2>M1: The transaction is mined and an attack will not take place. Note that the inequality between M1 and M3 does not matter for this outcome. The CCI gets CC2NI.
  3. M1≥M2>M3: The transaction is not mined. The CCI gets CC1NI.

In stage 1, the CCI is making the decision to integrate. To analyze this, we need to compare the non-integrated outcomes with the integrated ones. We thus have to look at the integrated outcomes first before we discuss stage 1. The outcomes are:

  1. Mined. Attacked.
  2. Mined. Not Attacked.
  3. Not Mined.

An attack happens if CC3I>CC2I. (This again will happen if the net benefit of the attack is positive).

If CC3I>CC2I, mining will occur if CC3I>CC1I. Similar to the non-integrated case, CC3I is always larger than CC1I . In fact this case is stronger as CC1I is at most zero and is likely to be negative as it is a cost. Thus if the CCI is willing to launch an attack against itself, it will definitely mine the transaction.

If CC2I>CC3I, no attack happens. For mining to occur, CC2I≥CC1I (the CCI will prefer to mine if they are indifferent). CC2I will always be larger than CC1I unless mining fees are zero (in which case it is equal), mining will always occur if CC2I>CC3I.

For mining to not occur, CC1I>CC2I or CC1I>CC3I needs to hold. To summarize, there are 3 scenarios:

  1. CC3I>CC2I and CC3I>CC1I: The transaction will be mined and an attack occurs. CC3I is the final payoff.
  2. CC2I>CC3I and CC2I>CC1I: The transaction is mined and no attack happens. CC2I is the final payoff.
  3. CC1I>CC3I (we had determined that CC1I>CC2I could not be possible): No mining occurs. CC1I is the final payoff.

Note that we have determined that mining will always occur if the CCI chooses to integrate. Thus there are only 2 relevant scenarios instead of the 3 found in the non-integrated case. The main assumption is that the CCI miner will be able to get its transaction included on the blockchain; this could be either because it is the only miner or it has invested in sufficient computing resources to ensure it.

There are a total of 9 combinations of events detailed in Figure 3. Figure 3 also shows the conditions required for integration to occur under each scenario.

Colored Coin Teo 3

Figure 3: Analyzing the Integration Choice.

Colored Coin Teo 2

Figure 2: Payoffs of the game

Referring back to figure 2, we can make the following assumptions:

CC1NI is always larger than CC1I

CC2NI is always larger than CC2I

CC2NI is always larger than CC1I

Thus the 3 inequalities highlighted in red in Figure 4 are never possible, no integration will occur in scenario B+E, B+F and C+F.

In the other 6 scenarios, integration could occur given the right conditions. We can make some predictions on what is likely to occur.

  1. In all scenarios with event A (A+D, A+E and A+F) where the non-integrated miner attacks, it is likely that the CCI prefers to integrate.
  2. In scenario B+D, there are two possibilities. If the cost of attack is large, the CCI will not integrate. Otherwise, it will integrate and reap the benefits of launching an attack on itself.
  3. When event C occurs and no integration takes place, the transaction will not be mined and the CCI gets nothing. Integration will thus occur as long as the cost of integration is small enough. This will be relevant for scenario C+D and C+E as we has ruled out C+F earlier.

One may ask if the CCI would want to attack itself. Well, if the benefit of attacking is large, a colored coin issuer may want to attack the network to derive a onetime benefit even though the company will never be trusted afterwards. However, this is unlikely as the cost of integration has to be extremely large for the CCI to be able to successfully attack the network.

Finally to answer our initial question, let us consider the issue of whether a non-integrated miner (in the event that a colored coin transaction can be identified) will force the CCI to quote high fees in order to get the transaction included. This is only relevant in the scenarios where the CCI initially chooses not to integrate. However, if colored transactions can be identified, miners can choose not to include these transactions unless the transaction fees are high enough. The fee can only be so high that it does not force the CCI to choose integration instead. In general, we can say that this fee cannot be higher than the cost of integration (this would refer to the per transaction cost of integration on average).

Based on this “game”, will colored coins be able to exist on a network such as Bitcoin? If colored transactions can be identified, there could be 2 issues. 1. The colored assets are so valuable that the non-integrated miner would want to attack the system, 2. The fees do not incentivized non-integrated miners to include the transactions. To overcome these issues the CCI could chose to integrate (or become a miner with sufficient computing power to be able to ensure that its transactions gets recorded). However, if the cost of doing so is too high to be justifiable, the CCI is better off not operating at all.