Bitcoin and related concepts


Warning: Invalid argument supplied for foreach() in /var/www/html/wp-content/plugins/papercite/lib/BibTex_osbib.php on line 185

Warning: Invalid argument supplied for foreach() in /var/www/html/wp-content/plugins/papercite/lib/BibTex_osbib.php on line 185

Bitcoin-160

This post contains my notes in my attempt to describe the ecosystem surrounding Bitcoin and cryptocurrency in general as well as some other concepts that I have researched for my thesis in Computer Science.

The reader is assumed to have a basic understanding of how Bitcoin works.

If you are interested, the referenced papers are collected in BibTeX format here.

Hashcash

Hashcash is a system originally proposed as a way to combat spam, and introduces the idea of CPU cost-functions [1], which are parameterisable expensive to compute, but relatively cheap to verify.

The idea is that a client who wants to send an email would have to spend CPU resources to complete a challenge from an email server in order to identify the client as an honest email-sender. The problem for email-spammers is then that they have to spend CPU resources for every email they want to send, and this will essentially make mass-emailing a very expensive task.

The difficulty of the challenge can be adjusted to increase or decrease the average time required to solve it. Specifically, the difficulty is to find a nonce that, when hashed along with the challenge string yields a bit string that starts with a certain amount of zeros. Adjusting the amount of zeros required adjusts the difficulty by making it twice as hard for each additional zero bit.

Bitcoin uses this principle to mine coins, where the challenge string of a block is the hash of the previous block in the chain, and the difficulty of the challenge is adjusted every two weeks to keep the average solve time close to 10 minutes.

Colored Coins

Colored Coins is an extra layer on top of the existing Bitcoin infrastructure that allows for adding special properties (or colors) to certain bitcoins. This system is transparent to the ordinary bitcoin network, as colored transactions abide by the same rules as regular bitcoin transactions, while imposing additional requirements to designate colored transactions [2]. As such, Colored Coins create a subnetwork inside the existing bitcoin network.

A bitcoin is colored if it can be traced back to a certain origin which has been defined as an issuer for a specific color.

The extra requirements for colored transactions are basically the following:

  • Inputs and outputs are sorted by color, with uncolored coins at the end.
  • The same order of colors is used for both inputs and outputs.
  • For each color, the total value of all inputs is equal to the total value of outputs; only
    uncolored coins can have a greater input value than output.

Quote from [3]:

Anything which is (1) representable as a digital asset, and (2) a ``rivalrous good'', meaning that only one person can own it at a time, is potentially fair game for representation in the Bitcoin blockchain.

However, Bitcoin does not include any facilities for doing this by default; to do any of these things, an additional protocol is required. And BitcoinX [Colored Coins] intends to accomplish just that.

Colored coins intro on GitHub wiki page

Mastercoin

Mastercoin is an alternate coin which, instead of creating its own network and blockchain, piggybacks on top of the Bitcoin network and acts as a higher-level layer similar to how HTTP utilizes the TCP/IP protocol for serving web pages.

Mastercoin has a wide array of new features including user currencies, decentralized currency exchanges, smart contracts and savings wallets [4], thus exposing features equivalent to those provided by Colored Coins as well as extra features which are not part of Colored Coins.

By containing embedding additional data in regular bitcoin-transactions, Mastercoin claims to be able to layer additional functionality and logic atop the existing Bitcoin network.

A problem with this approach, as noted by many observers [5] [6], is inherent in the fact that the basic Bitcoin network handles and validates all transactions --- including Mastercoin transactions. Combining this with the fact that the Mastercoin protocol requires additional logic to check the validity and consistency of Mastercoin transactions, leaves us with the problem that although the Bitcoin foundation of a validated transaction is valid, the Mastercoin transaction doesn't have to. One can easily imagine how this could lead to inconsistencies where different clients report e.g. different amounts of Mastercoin paid in the same transaction.

As a result of Mastercoin's promise of separate user currencies, anyone is able to create their own currency for their own purposes, free of charge (Although the currency is free to create, each Mastercoin (and derived user currencies) transaction charges 0.00006 BTC which goes to the Mastercoin Foundation). This has resulted in, among other things, the announcement of BitCongress, a open source voting system protocol.

Namecoin

Namecoin is a clone of Bitcoin with a slightly augmented protocol to allow for reserving, registering and updating names. A name is basically a key in a decentralized key/value store, and "owning" (having registered) a key allows you to change the value associated with that key.

This has multiple possible uses including, but not limited to, DNS, TLS, timestamping, and broadcasting/messaging (See http://namecoin.info). In fact, the currently most widespread use of Namecoin is as a decentralized DNS with the .bit TLD (http://dot-bit.org). It should be noted, however, that use of the .bit domain requires using a Namecoin-enabled DNS-server or proxy, as it is not part of the standard TLD's maintained by IANA (Internet Assigned Numbers Authority).

Although Namecoin and Bitcoin are very similar, Namecoin uses a different blockchain. However, since Namecoin supports the concept of merge mining, it is possible to mine on both blockchains at the same time.

Merge mining

Merge mining is a way for miners to spend their computing resources mining for more than one blockchain; they try to solve one challenge, but the answer to this challenge is acceptable for both or all blockchains that are mined for.
In practice, this allows for other altcoins to harness the computing power of Bitcoin miners to increase their own security and challenge difficulty.

Technically (See http://bitcoin.stackexchange.com/a/275), it works by taking the hash of the previous block in the altcoin and including it in a transaction in the new Bitcoin block. Merge miners then try to solve the challenge of this Bitcoin block, and the altcoin blockchain accepts the solution to the Bitcoin block as a valid solution to its own block because the hash of the previous altcoin block is included in the Bitcoin block. This way, a miner is essentially mining in two blockchains instead of one.

Of course, this requires the altcoin to allow merge mining, i.e. accept the proof-of-work of Bitcoin (or another blockchain) as valid proof-of-work for its own chain. It is worth noting that Bitcoin doesn't support merge mining, but other altcoins do, such as NameCoin. This means that NameCoin will accept a solved Bitcoin block as a valid solution to its own blockchain, but not the other way around. (The challenge difficulty required may (and probably will) differ between NameCoin and Bitcoin, meaning that a given solution may only be accepted by one of the coins; if NameCoin requires only 40 zero bits, while Bitcoin requires 60, a solution with 50 zero bits will only be acceptable by NameCoin, while a solution with 60 or more is accepted by both coins.)

It has little impact on the Bitcoin blockchain. (http://bitcoin.stackexchange.com/a/1288 argues that over time, it could impact the monetary value of Bitcoin), but for the altcoin there is great benefit to reap; since it is virtually cost-free for the Bitcoin miner to also merge mine for the altcoin and promises a greater return that just mining Bitcoins, the altcoin block generation timing will be more predictable and the security will increase through the increase in miners.

Zerocoin

Zerocoin was initially proposed as an extension to the Bitcoin protocol designed to improve upon the Bitcoin privacy model [7] [8]: In Bitcoin, since all transactions are public information, it is possible to trace all spendings back to previous transactions and this imposes a privacy weakness that is generally acknowledged by the Bitcoin community [7].

Bitcoin users currently circumnavigate this weakness by using third party money laundering services, which essentially shuffles the coins of different users, leaving the coins untraceable.

Zerocoin is an attempt to mitigate this weakness by breaking the link between individual transactions without adding trusted parties, while preserving cryptographic proof that the transactions actually took place through the use of digital commitments, one-way accumulators [9], and zero-knowledge proofs.

Conceptually, it works as follows [7]: Imagine that all users share access to a physical bulletin board. To mint a zerocoin with a value of e.g. $1, a user Alice pins $1 of physical currency to the public bulletin board, along with some data C that will later allow her to prove that she has indeed pinned $1 to the board.

Later, when Alice wants to spend her $1, she must prove (The proof is provided as a non-interactive zero-knowledge proof) that she knows of a C on the bulletin board and that she knows a hidden value that will ``open'' C. If she can prove these two things, she is allowed to pick any $1 note from the bulletin board, and it will then be impossible to link her initially posted dollar-bill with her newly claimed note.

Zerocoin isn't compatible with the existing Bitcoin network, which would require an upgrade to make Zerocoin work. On November 16th 2013 it was announced (See https://twitter.com/matthew_d_green/status/401797786347114496) that Zerocoin would be released as its own cryptocurrency instead of being integrated with Bitcoin.

CoinJoin

CoinJoin is a proposition (See https://bitcointalk.org/index.php?topic=279249.0) by moderator gmaxwell of the Bitcoin forum to address the same privacy issues as Zerocoin, but without requiring a change to the Bitcoin protocol. That is, the proposed CoinJoin transactions are completely valid Bitcoin transactions.

The idea is that two or more users who want to make payments, join their payments together into a single transaction that requires all users to sign it before it can be included in the blockchain. Such a joint transaction "is externally indistinguishable from a transaction created through conventional use", and it is then much harder (if not impossible) for an observer of the transaction to link inputs from one person to outputs from the same person.

The principles of CoinJoin improves privacy not just for the people using it, but also for everyone else, because the more people use it, the less likely it will be that multiple inputs in one transaction comes from the same person. Thus, correlating different inputs with the same person becomes more error prone.

On November 17th 2013, Blockchain.info announced their implementation of CoinJoin (See https://twitter.com/blockchain/status/402224010492006400/) named Shared Coin (https://sharedcoin.com/).

Mix Networks

A Mix Network is a kind of routing protocol that create untraceable (or at least, hard-to-trace) communications through the use of chains of multiple links between the sender and the receiver. The concepts behind Mix Networks are first described by David L. Chaum in 1981 [10].

Say that Alice wants to send a message to Bob --- First Alice prepares her message to Bob and puts it in an envelope EB with Bob's address on it. She then takes this envelope and puts it in a new envelope EM0 with the address of a computer M0 known as a mix. This mix opens its own envelope, sees the envelope with Bob's address on it and sends the inner envelope to Bob.

Extending this mechanism with more mixes yields a chain where each link only knows about the computers right before and after in the chain, and thus only the sender has knowledge of both the sender and the receiver. This assumption doesn't hold if (1) an attacker controls all the mixes in the chain or (2) an attacker monitors the entire network and the mixes in the chain aren't used by anyone else. In case 1, controlling all the mixes means that an attacker can trace a message's way from sender to receiver. In case 2, monitoring the network enables an attacker to trace communication from the sender to the first mix, first mix to second mix, etc, to the receiver. If these mixes aren't used for anything else, the attacker can retrace the path of the message.

Using a variant of this mechanism also allows the receiver to reply to the sender without knowing who the sender is by having the sender include an untraceable return address in the original message.

In essence, Mix Networks allows one party to anonymously communicate with another party, and the other party to reply to the first party, where only the first party knows of both endpoints in the communication.

Bitmessage

Bitmessage is a system that enables trust-less encrypted peer-to-peer communication between a sender and one or multiple receivers [11]. It is built upon the many of the same principles as Bitcoin:

  • Addresses are hashes of public keys
  • Every message sent must include a proof-of-work to prevent flooding (The whitepaper proposes that "an average computer must expend an average of four minutes of work in order to send a typical message".)
  • Messages, like Bitcoin transactions, are broadcast to all nodes in the network

Each message sent to the network doesn't directly include the receiver's address, but is encrypted using the public key associated with the address. This entails that every node (every possible receiver) will have to try to decrypt the message using their own private key; only the intended receiver can successfully decrypt a message and failure for a party to decrypt a message implies that the party was not the intended receiver of the message.

This system requires all peers to store all messages in order to determine which ones were intented for them. It is this very requirement that ensures the anonymity of the receiver since it is not possible to determine the intended receiver by looking at who has received the encrypted message.

In order to allow scalability, the Bitmessage system automatically divides the nodes into large clusters or streams when the amount of messages sent reaches a certain threshold. Also, in the pursuit of scalability and minimizing storage requirements of the individual peers, the system imposes a maximum message lifetime of two days, after which the message must be resent if the receiver hasn't acknowledged that it has received the message (The whitepaper [11] describes an acknowledgement method (passive operating mode) that allows for anonymous acknowledgement of received messages through other peers).

Helios Voting System

The Helios voting system is a web-based open-audit voting system, the first of its kind, conceived in 2008 [12]. Open-audit meaning that everyone can verify the election results as correct, and individual voters can verify that their vote was correctly captured and is part of the final tally.

As part of the election process with Helios cryptographic proofs for correctness are generated and made publicly available. In fact, the integrity of a Helios election relies on auditors verifying the final results and proofs and on voters verifying their individual vote to verify the integrity of the final election results.

It is important to note that Helios does not try to solve the voter coercion problem, but proposes the system for communities or organizations that do not "suffer from nearly the same coercion risk as high-stakes government elections".

The Helios protocol is based on the Benaloh vote-casting approach [13] and the Sako-Kilian mixnet [14].

[1] A. Back, "Hashcash - a denial of ſervice counter-measure," , 2002.
[Bibtex]
@TECHREPORT{Back:2002:HDS,
author = {Adam Back},
title = {Hashcash - A Denial of Service Counter-Measure},
institution = {},
url={http://www.hashcash.org/papers/hashcash.pdf},
urldate = {2013-12-18},
year = {2002}
}
[2] M. Rosenfeld, "Overview of colored coins," , 2012.
[Bibtex]
@online{ColoredCoins1,
author="Rosenfeld, Meni",
title="Overview of Colored Coins",
year=2012,
month=12,
url={https://bitcoil.co.il/BitcoinX.pdf},
urldate={2013-12-17}
}
[3] Y. Assia, V. Buterin, L. Hakim, and M. Rosenfeld, "Colored coins - bitcoinx," , 2013.
[Bibtex]
@online{ColoredCoins2,
author="Assia, Y. and Buterin, V. and Hakim, L. and Rosenfeld, M.",
title="Colored Coins - BitcoinX",
year=2013,
month=12,
url={http://coloredcoins.org/about/resources/},
urldate={2013-01-13}
}
[4] M. Foundation, "The master protocol / mastercoin complete ſpecification," , 2013.
[Bibtex]
@online{MastercoinSpec,
author="Mastercoin Foundation",
title="The Master Protocol / Mastercoin Complete Specification",
year=2013,
url={https://github.com/mastercoin-MSC/spec/blob/master/README.md},
urldate={2014-01-14},
}
[5] killerstorm (Reddit user), "Mastercoin is a joke," , 2014.
[Bibtex]
@online{MastercoinIsAJoke,
author="(Reddit user), killerstorm",
title="Mastercoin is a joke",
year=2014,
url={http://www.reddit.com/r/Bitcoin/comments/1rpx26/mastercoin_is_a_joke/},
urldate={2014-01-14}
}
[6] V. Buterin, "Mastercoin: a ſecond-generation protocol on the bitcoin blockchain," , 2013.
[Bibtex]
@online{MastercoinSGPBB,
author="Buterin, Vitalik",
title="Mastercoin: A Second-Generation Protocol on the Bitcoin Blockchain",
year=2013,
month=11,
url={http://bitcoinmagazine.com/7961/mastercoin-a-second-generation-protocol-on-the-bitcoin-blockchain/},
urldate={2014-01-14}
}
[7] I. Miers, C. Garman, M. Green, and A. D. Rubin, "Zerocoin: anonymous distributed e-cash from bitcoin," , 2013.
[Bibtex]
@techreport{Miers:2013:ZAD,
author={Miers, Ian and Garman, Christina and Green, Matthew and Rubin, Aviel D},
title={Zerocoin: Anonymous Distributed E-Cash from Bitcoin},
institution={},
url={http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf},
urldate={2013-12-19},
year={2013}
}
[8] M. Green, "Zerocoin: making bitcoin anonymous," , 2013.
[Bibtex]
@online{ZerocoinRelease,
author="Green, Matthew",
title="Zerocoin: making Bitcoin anonymous",
year=2013,
month=04,
url={http://blog.cryptographyengineering.com/2013/04/zerocoin-making-bitcoin-anonymous.html},
urldate={2014-01-13}
}
[9] J. Benaloh and M. de Mare, "One-way accumulators: a decentralized alternative to digital ſignatures," in Workshop on the theory and application of cryptographic techniques on advances in cryptology, Secaucus, NJ, USA, 1994, pp. 274-285.
[Bibtex]
@inproceedings{Benaloh:1994:OWA,
author = {Benaloh, Josh and de Mare, Michael},
title = {One-way Accumulators: A Decentralized Alternative to Digital Signatures},
booktitle = {Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology},
series = {EUROCRYPT '93},
year = {1994},
isbn = {3-540-57600-2},
location = {Lofthus, Norway},
pages = {274--285},
numpages = {12},
url = {http://www.cs.stevens.edu/~mdemare/pubs/owa.pdf},
urldate = {2013-12-19},
acmid = {188354},
publisher = {Springer-Verlag New York, Inc.},
address = {Secaucus, NJ, USA},
}
[10] [doi] D. L. Chaum, "Untraceable electronic mail, return addresses, and digital pseudonyms," Commun. acm, vol. 24, iss. 2, pp. 84-90, 1981.
[Bibtex]
@article{Chaum:1981:UEM,
author = {Chaum, David L.},
title = {Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms},
journal = {Commun. ACM},
issue_date = {Feb. 1981},
volume = {24},
number = {2},
month = feb,
year = {1981},
issn = {0001-0782},
pages = {84--90},
numpages = {7},
url = {http://doi.acm.org/10.1145/358549.358563},
doi = {10.1145/358549.358563},
acmid = {358563},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {digital signatures, electronic mail, privacy, public key cryptosystems, security, traffic analysis},
}
[11] J. Warren, "Bitmessage: a peer-to-peer message authentication and delivery ſystem," , 2012.
[Bibtex]
@online{Bitmessage,
author="Warren, Jonathan",
title="Bitmessage: A Peer-to-peer Message Authentication and Delivery System",
year=2012,
month=11,
url={https://bitmessage.org/bitmessage.pdf},
urldate={2013-12-18}
}
[12] B. Adida, "Helios: web-based open-audit voting," in Proceedings of the 17th conference on ſecurity ſymposium, Berkeley, CA, USA, 2008, pp. 335-348.
[Bibtex]
@inproceedings{Adida:2008:HWO,
author = {Adida, Ben},
title = {Helios: Web-based Open-audit Voting},
booktitle = {Proceedings of the 17th Conference on Security Symposium},
series = {SS'08},
year = {2008},
location = {San Jose, CA},
pages = {335--348},
numpages = {14},
url = {https://www.usenix.org/legacy/events/sec08/tech/full_papers/adida/adida.pdf},
urldate = {2013-12-18},
acmid = {1496734},
publisher = {USENIX Association},
address = {Berkeley, CA, USA},
}
[13] J. Benaloh, "Simple verifiable elections," in Proceedings of the uſenıx/accurate electronic voting technology workshop 2006 on electronic voting technology workshop, Berkeley, CA, USA, 2006, pp. 5-5.
[Bibtex]
@inproceedings{Benaloh:2006:SVE,
author = {Benaloh, Josh},
title = {Simple Verifiable Elections},
booktitle = {Proceedings of the USENIX/Accurate Electronic Voting Technology Workshop 2006 on Electronic Voting Technology Workshop},
series = {EVT'06},
year = {2006},
location = {Vancouver, B.C., Canada},
pages = {5--5},
numpages = {1},
url = {https://www.usenix.org/legacy/event/evt06/tech/full_papers/benaloh/benaloh.pdf},
urldate = {2013-12-18},
acmid = {1251008},
publisher = {USENIX Association},
address = {Berkeley, CA, USA},
}
[14] K. Sako and J. Kilian, "Receipt-free mix-type voting ſcheme: a practical ſolution to the ımplementation of a voting booth," in Proceedings of the 14th annual ınternational conference on theory and application of cryptographic techniques, Berlin, Heidelberg, 1995, pp. 393-403.
[Bibtex]
@inproceedings{Sako:1995:RMV,
author = {Sako, Kazue and Kilian, Joe},
title = {Receipt-free Mix-type Voting Scheme: A Practical Solution to the Implementation of a Voting Booth},
booktitle = {Proceedings of the 14th Annual International Conference on Theory and Application of Cryptographic Techniques},
series = {EUROCRYPT'95},
year = {1995},
isbn = {3-540-59409-4},
location = {Saint-Malo, France},
pages = {393--403},
numpages = {11},
url = {https://gnunet.org/sites/default/files/SK.pdf},
urldate = {2013-12-18},
acmid = {1755052},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
}

About the author

Jesper Borgstrup Jesper is a Masters student of computer science at the University of Copenhagen.

Leave a Reply

Your email address will not be published. Required fields are marked *

* Copy This Password *

* Type Or Paste Password Here *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>