Cryptographic Hash Functions
Mathematical function with three attributes
- takes any string as input
- produces fixed-size output
- efficiently computable
For cryptocurrencies, we need cryptographically secure has functions, which have three additional properties:
- Collision-Free – There is never an X input and a Y input that have different values but equal Hash values (those inputs run through the hash function). We need to understand that theoretically collisions do exist, but functionally we don’t find them because we would have to run through 2^130 randomly chosen inputs, which is a gigantic number of computations.
- There is no hash function proven to be collision free
- To apply this collision free principle, if we know that H(x) = H(y), that the hash function for x equals the hash function for y, then we can assume x = y. This means that if we take a big file with a long string and run it through a hash function, we receive some return. We can then store that return. Then, when we run another big file and receive a return, we can compare the returns. If they are equal, then we can assume that the big files full of text are also identical.
- This helps us remember documents we have processed and identify them in the future.
- This is only useful because the hash is small compared to the overall file, so comparing the small figure is faster and less intensive then comparing the large files.
- Hiding – If we are given the output of the hash function, then there is no feasible way to identify the input. Given H(x), we have no way to find x.
- Hiding doesn’t work unless there are a large number of possible values of x
- and that no value is particularly prevalent over other values
- x must be in a decision set that is spread out to prevent a brute-force method of trying different values of x
- To make this happen, our hash function appends a number (r) chosen from a highly spread out distribution to x. If r is sufficiently spread out, it becomes impossible to crack x
- this is the idea of commitment, we set the value for r while hiding that value from anyone else. Then, after we deliver the commitment to its recipient, we divulge the value of r
- Given r, we can’t find x
- this is the idea of commitment, we set the value for r while hiding that value from anyone else. Then, after we deliver the commitment to its recipient, we divulge the value of r
- Hiding doesn’t work unless there are a large number of possible values of x
- Puzzle-Friendly – More complicated. If you wanted to result in a particular value (y), and k is chosen from a spread out distribution, it’s infeasible to find the exact x you need to result in the y you are looking for.
SHA-256 Hash Function
This is the function that bitcoin uses. It takes the message you are hashing and breaks the file up into blocks of 512 bits each. Because the message won’t fit perfectly in the blocks, we add padding to the end of each block. Once padded so each block is the correct length, we then chop message up and you apply a 256 bit lookup figure (from a standards document) to each block.
Start with this 256 bit value. Add it to the 1st message block. This increases the block size to 768 bits, so we use a compression algorithm (c) at each step to fit the block back to create a 256 bit return. This return is then concatenated with message block 2, then run through the compression function (c) to create a new 256 bit return. At each step when the function is applied, the message is added logically to the previous return and shipped to the next step in the function.
Once you reach the end, you’ve consumed all the message blocks and the padding, resulting in a final 256 bit return which we call a hash. As long as the function is collision free, then the entire hash function is also collision free.
A hash pointer is a simple pointer to where info is stored, then together with that pointer we store a cryptographic hash of the information. We use regular pointers to retreive information from memory, whereas with hash pointers we can BOTH retrieve the info and verify that it hasn’t changed. Hash pointers tell us where something is and what it’s value was.
We can take almost any data structure (linked list, binary tree, etc) and rebuild that data structure using hash pointers instead of pointers. We can build a linked list with hash pointers (called a blockchain), where one hash pointer points to a block of data that has a reference to the hash pointer for the previous block of data, and so on.
Blockchains, linked lists with hash pointers, offer a tamper-evident log functionality. If an adversary were to attempt to change the value of data somewhere along the blockchain, that new data would have a different cryptographic hash than the old data. The hash pointer that points to that data would detect that the new hash is different from the previously recorded hash, alerting us to tampering.
One work around would be for an attacker to alter the cryptographic hash pointer that leads to their updated block of code. In theory, they could alter the hash pointer to reflect their new data, thus tricking the system. In practice, however, as all hash pointers are contained within the block of data, changing any hash pointer would also change the data associated with that hash pointer. If someone where to alter a hash pointer, the hash pointer before it in the chain would be able to detect the change. As long was we have an initial hash pointer, which an attacker would not be able to access, we will always have a method of detecting changes in our blockchain.
We can also build a binary tree with hash pointers, creating whats called a Merkle Tree. At the bottom, we have blocks of data. Up one level, we have two hash pointers each pointing to a separate block of data. Up one level, we have two hash pointers each pointing to a separate block of two hash pointers, who themselves point to individual pieces of data. We keep going up the binary tree until we reach the root hash pointer, which would need to be securely stored. This is also tamper evident because changing any block of data requires changing the hash pointer, and we can only change so many hash pointers before we reach the root, which is secure. Merkle Trees are more efficient in how they can be transversed to confirm blocks of data. In mathematical terms, verifying blocks in a Merkle Tree takes on the order of (O) log n.
Another variant of a Merkle Tree is a sorted Merkle Tree. In this, we sort the blocks at the bottom of the tree in some order, say alphabetical or numerical. Now we can show if a block is not in our tree in O(log n) time/space because we can show the items before and after our desired block. As it is sorted, if we can show there is no block between our before and after, we can show that the block DOES NOT exist.
In fact, we can use hash pointers in any pointer-based data structure, as long as there are no cycles.
Digital signatures are the other core component to understand crytographic technologies. Digital signatures mimic paper signatures in the following ways:
- Only you can sign your own signature
- Anybody can verify your signature vs. someone else’s
- Your signature is tied to a particular object such that your signature denotes your acceptance or atleast awareness of that object / document.
- This means your signature can’t be copied and pasted to another document
To create a digital signature, we need to be able to perform these three operations:
- GenerateKeys(KeySize) = (sk, pk)
- We tell key generation subroutine the size of the keys we will be generating
- This will generate both a secret signing key (sk) and a public verification key (pk). Signing key is used to make your signature, whereas public key is given out to anyone withing to verify your key.
- This can be a randomized algorithm, in fact, it should be randomized to generate different keys for different people.
- Sign(sk, message) = sig
- The next step is the sign operation. You take your secret key and any message upon which you would like to apply your signature.
- This operation returns sig, which is a signature (some collection of bits that represents your signature)
- This can also be a randomized algorithm.
- Verify(pk, message, sig) = isValid
- The last step is the verification method. In this, we take our public key, the message the signature is applied to, and the sig.
- Returns true or false if the signature is valid or not.
Requirements for Signatures
Digital signatures, at a more technical level, must fullfill a few properties:
- Valid signatures will always verify
- That is, if you have a verify function verify(pk, message, sign(sk, message)) and all the pieces of the verify method are true, then the final value will be true and the sig will verify.
- Can’t Forge Signatures
- If adversary knows public key and is able to find signatues on some messages, they are unable to then produce a verifiable key on another message of their choosing.
The algorithms we use to generate keys must be randomized and they need a good source of randomness. If you algorithm isn’t random enough, then attackers can figure out your scheme. Intelligence Agencies routinely issue attacks to test the randomness of an algorithm, so the people whom know target randomness as their exploit, letting you know how important it is.
There is a limit to the message size you can sign because the algorithms run on strings of fixed length. An option is to use the hash of a message, as opposed to the message itself. The message could be any length, but the hash would only be the 256 bit representation.
A look into the future. If you sign your hash pointers, then your digital signature covers the entire structure of your data. For example, if you were to sign the hash pointer at the end of a blockchain, you would be in effect signing all the data in the entire blockchain!
Bitcoin uses ECDSA (Elliptic Curve Digital Signature Algorithm) to generate keys, sign messages, and verify packages. As it relies on extensive mathematical operations that I don’t understand, I’ll just wave my hand at it and throw it in the black box. The key to ECDSA is having good randomness during the generateKeys() or sign() functions. If you have bad randomness, there is a good chance you’ll leak your private key.
Public Keys as Identities
As a thought experiement, I want you to think of the public key as the identity for the sender of the message. If you have a valid signature, it can be throught of as the private key (pk) says the message (msg). The public key is an actor in the system, and is able to make statements within that system. For someone to make statement for pk, you would have to know sk. In that instance, if you know sk and pk, you are able to make public statements for pk. That creates an identity in the system which only you can speak from.
If you want to make your public key your identity, then you must understand that you can make a new identify whenever you want. We can generate new sk and pk by running our generateKeys() function. The new pk is then the public name of your new identity. This is going to be a big string, so you’ll want to use the Hash(pk) to generate a 256 bit representation of your pk. Pk is the public name to identify the identify, while sk is the secret that lets you “speak for” and issue statements in that identities voice.
You have complete control of the identity because only you know your secret key (sk). The other take away is that if your pk looks random enough, then nobody will ever know your true identity behind the pk “identity”.
These ideas lead to decentralized identity management. DIM allows anybody to create a new identify at any time, and to have as many identities as they wish. Bitcoin, for example, uses these identifies and calls them “addresses”. You can also try to be anonymous by creating a new identities temporarily, then trashing them whenever you wish. The address is a public key, or more accurately, the hash of a public key.
Your addresses are not connected to your real-world identity. However, if your identity engages in a series of actions over time, an acute observer can make inferences based on your activity.
Understanding a Simple Cryptocurrency
Lets take an imaginary example: GoofyCoin. In GoofyCoin, Goofy can create coins and sign them with his digital signature. He can also give those coins to other people, signed with his digital signature and the recipients digital signature. Recipients can then give those coins to others, signed with the recipients digital signature and the new recipients digital signature. Each transaction points to the previous transaction with a hash pointer, so recipient two has a transaction with a hash pointer towards recipient ones first transaction. Recipient 1 also has a hash pointer towards the coin that Goofy created, thus establishing its veracity. This is an example of a simple blockchain.
GoofyCoin has a serious problem, however. If Recipient 1 gives her coin to another recipient, Recipient 3, then there are two transactions that both point back to the coin that Goofy gave recipient 1. Both recipients 2 and 3 have valid-looking transactions, and if they don’t know about eachother, they would be think they own a GoofyCoin. When a user shares the same coin with multiple other users, that is a double-spending attack. This is the most important problem for a crytopcurrency to solve. It’s the main design challenge when building a crytocurrency.
To do this, we use ScroogeCoin. For his coin, Scrooge publishes a history of all transactions in ScroogeCoin (a block chain) and signs it with his digital signature. It is a series of blocks with transaction ID’s that point to the previous transaction block, with it’s own transactionID. The blocks contain:
- Transaction Data for 1 transaction
- Transaction ID
- Hash Pointer to previous transaction in block chain
Scrooge uses that hash pointer that represents this entire structure and digitally signs it. Then, if anyone wanted to verify a transaction, they could find it with Scrooge’s public key and the transaction history.
Special Note – In practice, as in BitCoin, we will combine multiple transactions into each block. For theory, however, it’s easier to think of 1 transaction per block.
By publishing the history, Scrooge allows us to detect double-spending attacks. If Receipient 1 tries to give the same coin to multiple people, they all can check the public transaction register to see that she only has the one coin. Scrooge himself can see the transaction and prevent the double-spend, but so can everyone else that has access to the public block chain.
In ScroogeCoin, there are two tranactions. CreateCoins is the transaction to create new coins. When a coin is created, it gets a serial number, a relative value, and a recipient(represented by the public key for that recipient).
This data structure gives us access to another representation, CoinID. CoinID is represented by the transactionID and the serial number. So if we CreateCoins with a transactionID of 73, and we create 3 new coins, each new coin would have a coinID = 73(0), 73(1), and 73(2), with 73(0) being the first new coin created during createCoins transaction number 73.
CreateCoins transactions are always valid because this is the very definition of the system created by Scrooge.
The other transaction is PayCoins. This transaction consumes and destroys some coins while creating new coins of the same total value for different recipients.
In the data structure, we have consumed coinID’s, those coins which will be deleted from the system and replaced with new coins. We add up the value of the destroyed coins and then issue a new createCoins instance, where we build new coins and assign them values based on the values of the coinID’s that were destroyed (they must add up to the same total value). These new coins are given new recipients, and then the transaction is digitally signed by everyone who is paying into the transaction to prove authenticity.
The rules for PayCoins state that a transaction is valid iff (if and only if):
- consumed coins must be valid
- consumed coins can’t be already consumed (no double spend)
- total value of consumed coins must equal total value of created coins
- signed by owners of all consumed coins
It’s important to note that ScroogeCoins are immutable. They cannot be altered in any way. They cannot be transferred, subdivided, or combined in any way. However, you can use transactions to transfer, subdivide, or combine your coins. For example, you could create a new transaction that consumed all of your coins and created a single new coin of the same total value, then give those coins back to yourself. This would be an example of combining your ScroogeCoins.
ScroogeCoin will work, but we depend on Scrooge’s honesty. If he wants to cheat, he can, or if he gets lazy, the whole system falls apart. The problem is centralization. Is there a way to deScroogify ScroogeCoin? Can we run this system without a central, trusted authority?
Yes, but we need to provide Scrooge’s services in a decentralized way, in which no particular party is trusted. We need to agree on a public blockchain that everyone uses to store transactions. We need to find a way for all users to agree on which transactions are valid. Also, we need to assign ID’s to transactions in a decentralized manner. Solving these problems will create a cryptocurrency very similar to BitCoin!
Centralization vs Decentralization
Before we dive in, it’s important to note that decentralization is not an all-or-nothing endeavor. Almost no system is purely one or the other. For example, email, which is based on Simple Mail Transmission Protocol (SMTP), is a decentralized protocol, but the use of email is dominated by centralized webmail services like Gmail and Yahoo and Outlook.
Aspects of Decentralization
- Who maintains ledger?
- Who has authority over which transactions are valid?
- Who creates new coins?
- Who determines how the rules of the system change?
- How can we exchange coins?
BitCoin uses aspects of decentralization that go beyond the protocol. BitCoin exchanges, which allow you to convert BitCoins to other currency, are decentralized to a degree. Wallet software and service providers are also decentralized to varying degrees.
BitCoin operates on a peer-to-peer network, which is very decentralized and has a low barrier to entry. BitCoin mining, while technically open to anyone, has seen a concentration of power due to high investment costs that is often seen as undesirable. This has become very centralized. Updates to the software are handled by core developers that are trusted by the community, giving them much power and central authority.
BitCoin relies on distributed consensus. It is one of the key technical challenges when creating decentralized e-cash. There are dedicated or research into protocols for distributed consensus.
We want distributed consensus to give us reliablity in distributed systems. Especially in massive distributed systems (think Facebook databases), we want all our systems to have all data or none at all. If we make a post on facebook, all facebook servers need to see that post in order to show it to my friends worldwide. If only a few servers showed it, the data would not by synchronized across the system and our system would be unreliable. Alternatively, if none of the systems saved the data, we would simply inform the user of an error and ask that they retype everything.
Distributed concensus protocols simply state that once the protocol terminates, all correct nodes must decide on the same value (called the concensus value). The second rule is that the value they decide upon cannot be arbitrary and must have been proposed by one of the correct nodes. By correct nodes, we refer to fully functioning units in the system, not those which could have errors or could be malicious.
How Bitcoin integrats Distributed Concensus Protocols
Bitcoin is a peer-to-peer system, so transactions are broadcast on all bitCoin nodes. If Alice pays Bob one BitCoin, then that transaction is sent to all bitCoin nodes in the system. The transaction data-structure has three key pieces of info:
- Signature of sender (Alice)
- Public Key of recipient (Bob)
- Hash pointer to previous transaction for same coin. In this case, the hash pointer will point to the transaction that got Alice the BitCoin, thus proving her ownership and ability to transfer the coin to Bob.
The nodes are trying to react consensus on which transaction happen and the order of the transactions. In theory, this works as follows:
- Nodes have a sequence of transaction blocks (instead of each transaction, they agree on a block of transactions for improved speed) that they have reached consensus upon.
- Nodes have a set of outstanding transactions that they have heard about
- consensus has not occured on outstanding transactions, so each node could possibly have different outstanding transactions.
That is an example of how BitCoin works in theory, but in practice it is much different. THis is because consensus over largely distributed networks is a difficult technical problem to overcome. It’s hard because:
- Nodes crash
- Nodes can often be malicious
- Networks are imperfect
- not all nodes are directly connected
- there could be faults in the network (broken data lines, etc)
- latency – Because networks don’t necessarily share clocks, there is no notion of global time
- Not all nodes will agree on timestamps
Distributed concensus models were mostly created for database systems, and not for bitCoin. For this reason, BitCoin actually works better in practice than it does in theory! However, it’s important to stay up on theory as it can help predict unforeseen attack vectors.
What Does BitCoin Do Differently?
Bitcoin introduces the idea of incentives. Because BitCoin is a currency, they can actually pay participants incentives for behaving honestly.
BitCoin also embraces randomness. There is no start and stop point for distributed consensus, it is a long process that happens over large time scales, around 1 hour in most instances. As time moves forward, the blocks you are interested in are more likely to become part of the concensus. Additionally, the possiblility that you are incorrect about a transaction also goes down exponentially as time moves forward.
BitCoin – Consensus without Identity: The Block Chain
Consensus algorithms typically require nodes to have an identity, however, BitCoin does away with this notion. We would want identities in order to use node ID’s for any protocols we wish to run. Node identities would also help with security.
Why Don’t BitCoin Nodes have Identities
Decentralized nodes in Peer-2-Peer networks don’t have the authority to create new node identities. Additionally, you have no way to very that nodes aren’t creating new identities at will (called a Sybil attack when an attacker creates new nodes to make it look like there is a bunch of activity, when it is really just one person).
Another reason for BitCoin to avoid identities is privacy. BitCoin is build around pseudonymity, so even if it were possible to give nodes identities, BitCoin wouldn’t want this approach.
Because we don’t have identities to tell attackers from good guys, we need a different way to reach consensus. In BitCoin, nodes are selected at random then they direct which transaction should be recorded next in the block chain. Other nodes would then approve the transaction by adding it to their block chains, or they would disapprove by omiting that block and moving to the next proposed block.
Remember that each block contains a hash of the block that it extends. By using this hash, nodes are able to reference blocks and tell the rest of the block chain which nodes they are extending.
BitCoin Consensus Algorithm
- New transactions are broadcast to all nodes
- Each node is constantly listening to network and collects the new transactions into a block
- In each round of proposal, a randomly chosen node gets to broadcast its transaction block to the network (this block is all of the outstanding transactions that the node has heard about)
- Other nodes accept the block only if all transactions are valid
- Valid transactions have valid digital signatures and the coins must be unspent)
- If accepted, the nodes will include a hash of this newest block in the nodes next block
- If rejected, the nodes will omit this block and use the hash of the most recent valid block instead
As a transaction receive more confirmations (each time the transaction is recorded in the block chain), the likelihood of a double-spending attack is reduced exponentially. A good rule of thumb is to use 6 confirmations to know for sure that a transaction will be represented in the consensus block chain.
Incentives and Proof of Work
Assuming that nodes are honest in their transactions is problematic because people can make good money in fooling the system, so Bitcoin uses incentives to promote honest behavior. This is compounded because there is no way to penalize a bad actor due to the inherent anonymity (nodes do not have identity) when using Bitcoin.
There are two separate incentive machanisms:
- Block reward – The creator of a block includes a special transaction in the block, and that transaction is a coin-creation transaction along with a recipient of the transaction. In essence, this is a payment a node can make to itself for proposing a BitCoin block. That payment is then only certified if their block gets into the Consensus Chain, thus providing a mechanism for rewarding actual transactions.. Interesting note – BitCoin began by offering 50 BitCoins for a successful transaction, and this is halved every 4 years.
- This is, in fact, the only way that new BitCoins are created. Thus BitCoin is able to cap the total number of BitCoins in circulation at 21 million. Additionally, BitCoin will stop paying this reward in 2140, so no new BitCoins will ever be created after that point, unless a rule change is proposed.
- Transaction Fee – The creator of any transaction can choose to make the output value of their BitCoin less than the input value. In essence, this creates a small difference in value which is then paid to the block creator for confirming the transaction. This transaction fee is voluntary and is treated like a tip.
- Imagine you are a node who proposed a block with 200 transactions. That is 200 transaction fees that you could receive if that block is added to the consensus chain!
- As block reward becomes less and less, this transaction fee will increase in importance and become mandatory.
Proof of Work
BitCoin is almost there in it’s viability, but there are a few concerns left. Namely, how to choose a random node and how to prevent everyone from owning a BitCoin node. These problems are solved with Proof of Work.
Here is the key idea: instead of choosing random node, we approximate choosing a random node by selecting nodes based on resources that, in theory, no one entity can monopolize. Those resources are:
- Computing Power – This is also called proof-of-work where nodes are selecting in proportion to their computing power
- Ownership – This is called proof-of-stake and nodes are selected in proportion to their ownership of the currency. This isn’t used in BitCoin, but it is used by many alternative coins
Proof-of-work allows nodes to compete with eachother based on computing power for the right to create blocks. This also makes it moderately harder to create new identities.
The proof-of-work system in BitCoin is called Hash Puzzles. To create a block, the proposing node must include a nonce along with the normal block chain payload (pointer to previous block and list of transactions). What happens is the nonce, the previous block link, and the text list of transactions are part of a long string. This string is then hashed and that hash output has to be a very small number. In fact, it must fit in something called a target space which is a small portion of the total output space of the hash.
It is moderately difficult to find a nonce that satisfies the requirement of hashing the entire block and receiving a particular output. The theory is that if the hash function is secure, then the only way to find the nonce is to brute-force different combinations until you get lucky.
Mathematically, if target space is 1% of output space for the hash, then you will have to try on average 100 different nonce’s to find the right one. Another way to look at it is that only 1 in 100 nonces will work to satisfy the requirement. In reality, the target space is much, much smaller than 1 percent.
Because the nonce is so tough to find, you need a great processor to try different combinations to solve the hash puzzle. Nodes are constantly competing to solve the hash puzzles. Once in a while, a node will get lucky and find the nonce, allowing that node to then propose the next block of transactions.
Properties of Proof-of-Work
- The puzzle must be difficult to compute. There are 1020 hashes/block, so a 1% target space would mean it is 1 / 1020 of the size of out output space of the hash. This is too much computation for smaller processors, like laptops or raspberry pi’s, so only some nodes even bother to participate. These nodes are called miners.
- This cost should be parameterizable, or it should change over time. The target space is to be recalculated every two weeks and must create a situation where, on average, a new hash puzzle can be solved every 10 minutes. This means that as competition goes up and the amount of block found increases, the system will make it tougher to find blocks, so your difficulty in finding them will increase. The rate at which you find blocks is dependent on what other miners are doing.
- It works out that the probability of completing a hash puzzle is equal to the fraction of global hash power you control. More and better hardware gives you more puzzles.
- That 10 minutes figure (block latency) is invariant because, if we propose blocks at a faster pace, there will be mistakes and the total number of transactions contained within each block will be smaller than it is today. From 10 to 5 minutes would be okay, but anything shorter would cause problems.
- Attacks are infeasible as long as a majority of miners, weighted by hash power, follow the protocols are are good actors. This is because if there is a proponderance of hash power dedicated to good actors, then there is greater than a 50% chance than any new block will contain valid transactions.
- Solving hash puzzles is probablistic. There is no way to find a nonce, you must try a bunch and land on the right number. Because of this, we can show that the mean time for an individual miner to find a block is equal to 10 minutes / fraction of hash power that individual miner has.
- Trivial to very that a node has solved the hash puzzle correctly. Once nonce is published to block, even though the nonce can take days to find, it is trivial (simple) to verify that the supplied nonce does indeed satisfy the requirements. This is important because miners can verify eachother quickly and easily, and the nonce is difficult to find, so we can easily prove that the miner did the work.
The obvious question is: is it profitable to mine? As we’ve seen, we need to compute 1020 hashes to find a single block, which is quite costly unless you have a ton of hash-power at your disposal. Of course, with more hash-power comes a larger electricity bill to power all those computations. And with the reward being lowered regularly, should you invest in BitCoin mining or cryptocurrency mining of any sort?
Short answer: no. Unless you already have the horsepower and advantageous electricity providers, with BitCoin where it is at right now it is not profitable. This can change should the value of BitCoin appreciate dramatically, but as of now you should not get into mining.
Transactions are the building blocks upon which the currency is built on. These transactions are recorded on the consensus block chain in an append-only ledger, so we can only add transactions, not edit transactions already on the ledger.
This transaction-based ledger must be contrasted with an account-based ledger. It is intuitive to think that, when you send BitCoins to someone, there is a data structure somewhere that records your BitCoin balance and the balance of the recipient. When the transaction occurs, those balances should change. This requires a lot more effort to coordinate and is easily exploited, so BitCoin does NOT work like this.
Instead, BitCoin only records the transaction. These transactions have an input and an output, along with a unique identifier. The input of a transaction is a pointer to a previous transaction, along with it’s index in the output array. For example, a BitCoin creation example would have 0 inputs and 25 BitCoin output. This transaction is unsigned.
Spending those BitCoins would involve an input that points to the first transaction (BitCoin creation) along with index  to denote from any other transactions in the block. The output would then be the number of BitCoins transacted and the recipient address, along with a transaction showing the remainder of her BitCoins going back to her. This transaction would be signed by the sender.
|1||0||25 -> Alice||Not Signed|
|2||1||17 -> Bob, 8 -> Alice||Alice|
|3||2||6 -> David, 2 -> Alice||Alice|
|4||2||3 -> Bob, 3 -> David||David|
Notice that after Alice sends 17 BitCoins to Bob, she must then send 8 back to herself to show her current balance in BitCoins. These are called change addresses and the idea is that you always completely consume your BitCoins in every transaction. Alice must use all 25 coins from transaction 1 in transaction 2. If you want to keep some coins, you just add a second piece to the transaction and send the coins back to yourself. Then, to determine if an account has enough BitCoins to make a transaction, you only have to look at the previous pointer, which should show exactly how many
In reality, each transaction isn’t numbered like this, but rather the cryptographic hash of the transaction is the transaction ID. Additionally, each separate transaction in the block has it’s own ID, which is the hash of that transaction.
In the event that you have, like in the above example, multiple transactions sending coins to a recipient (Bob), you can combine them by merging the transactions. We could add another transactions like this:
|5||2, 4||20 -> Bob||Alice, David|
As you can see, the input is pointers to 2 separate transactions that we are merging into the output, and paying the full amount to Bob. Now he can spend the coins more easily.
We can also create joint payments from two (or more) senders to one (or more) recipient. It would look like this:
|5||3, 4||5 -> Carol||Alice, David|
Recall that the total number of BitCoins shown in the output of the previous transaction must be consumed by the input of this transaction, then passed to the output.
In reality, a BitCoin transaction doesn’t look like a line item in a table, it is text-based code which has:
- Size of transaction
- Number of inputs
- Number of Outputs
- Hash of the transaction (Transaction ID)
- Lock time
- An array of inputs that have the same form
- They specify a previous transaction block along with the index of the particular transaction you are referring to
- Transaction Value, with the some of all values being less than the sum of the inputs
- Recipient Address
We know that BitCoin transactions have output addresses, but did you know that the address is really a script? In fact, the Input is also a script, and the two scripts are concatenated then executed. This single script must execute completely with no errors in order to verify the transaction.
The Input script is called scriptSig and the output script is called scriptPubKey. This is because, in it’s simplest form, the input script specifies a signature while the output script specifies a public key (address).
BitCoin uses it’s own scripting language called “Script”, which has been built specifically for BitCoin. It has these properties:
- simple – It can handle arithmetic, conditionals, and crypto (hash function, signature verification)
- compact – there are only 256 instructions in the language (15 disables and 75 reserved for future use)
- support for cryptography – language supports special functions for hashing and verification
- stack-based – No variables, only way to write data to memory is to push it onto the stack
- limits on time / memory
- no looping – every instruction is executed exactly once in a top to bottom fashion.
- not Touring complete
- no halting problem, no infinite loops, you can look at the code and know exactly how many steps must be taken for the program to complete.
Lets look at a sample script and examine it:
<sig> <pubKey> OP_DUP OP_HASH160 <pubKeyHash?> OP_EQUALVERIFY OP_CHECKSIG
This is a script to send a BitCoin to another address. The sender has to specify the public key of the recipient and the recipient has to specify a signature.
The first piece is the <sig> and <pubKey> components, which are derived from the input of the transaction. These calls are known as data instructions and are simple in a stack-based language. When a data instruction is invoked, the data related to that instruction is simply pushed onto the stack.
Once first piece is pushed to the stack, we then execute the next script piece which is specified by the sender of the BitCoins. OP_DUP is a command to pop the top stack item off of the stack and replace it with two duplicates of the same item. This duplicates the public key on the memory stack.
The next step takes the public key on the top of the stack and converts it to a cryptographic hash of the public key.
Now we reach <pubKeyHash?>, which is another data instruction for adding a hash of the public key the sender used to direct the transaction to the top of the stack. That is, the sender supplies a public key to identify the recipient, and this is the hash of that public key. It should be the recipients public key.
With the two public key hashes on the top of the stack, we run OP_EQUALVERIFY, which checks if the two data instructions are equal. If they are not, we throw and error and the validation fails.
OP_EQUALVERIFY then consumes the public key hashes on the top of the stack and we are left with the public key and the signature. Since we have already verified the public keys are identical, all that is left is to verify the signature.
OP_CHECKSIG function will then verify that the entire transaction was successfully signed. If successful, the <pubKey> and <sig> are popped off the stack (thus clearing the stack) and the script results in a “yes”.
BitCoin scripts can only have two outcomes: either complete with no errors or fail and the transaction will not be accepted into block chain.
It is important to note that almost 99.9% of transactions on the bitCoin network are of the variety we examined, when a sender has to sign a bitcoin and send it to a public key. This is because nodes on the consensus chain whitelist known scripts and often times will not run any script they do not recognize. It’s not that other scripts can’t be used, but it is more difficult to use them.
Applications of BitCoin Scripts
BitCoin scripts can be used to create some interesting transactions.
It is commonly the case that a buyer doesn’t want to pay until a product ships, but a seller doesn’t want to ship until they get paid. To resolve this, you can use a 3rd party escrow account.
Alice can create a MULTISIG transaction (requires multiple verifiable signatures to complete) with Bob and a 3rd party. This multisig transaction will only go through with 2 of the 3 signatures. When this transaction is copied to the blockchain, the coins will be in escrow and 2 of the 3 signees can direct where those coins will go.
Now Bob can ship without worrying about being shorted. If Alice receives the shipment and is happy, then she can create another transaction, taking the coins from the escrow transaction, and send it to Bob with his signature. The third party is not needed here.
If there is a problem, however, and Alice does not get what she paid for, the third party can step in and adjudicate the dispute, sending the coins to the party she feels deserves them.
It can take up to an hour for a block to be verified in the blockchain and confirmed by 6 blocks. If a seller does not have the ability to verify the transaction, how do they know they got paid?
Alice can talk to her back and have the bank create a transaction from one of it’s green addresses. This transaction is signed by the bank and uses bank funds. It is a bank-controlled address that comes with a guarantee that it can never be double-spent.
Interesting to note that the first 2 companies to offer this service have collapsed because of double spending attacks. The guarantee is a real-world idea and there is no programming mechanisms enforcing it.
Efficient Micro Payments
If Alice wants to make small, continuous payments to Bob but doesn’t want to incur a transaction fee for every payment, she can use serial micro payments.
You start with a single lump sum payment that is as large as Alice could incur and you create a multisig transaction that requires Alice and Bob to sign. With this set up, Alice would begin using the service and send over small transactions at regular intervals. These transactions would take many from the MULTISIG transaction and pay to Bob, with the remainder paid to Alice. Each transaction will increment the amount paid to Bob and decrement the amount paid back to Alice.
Note that these small transactions are not recorded to the blockchain, only the lump sum payment. When Alice is done using the service, she can send the final micro-transaction, which totals how much she needs to pay to Bob and the amount that she needs to send back to herself. Bob can then publish this final transaction to the blockchain, thus paying himself and sending the remainder to Alice.
Technically speaking, this micro-payment protocol creates a huge number of double spends. Bob should not sign any of these micro transactions to keep them out of the block chain. The other difficulty is if Bob does not sign the final transaction and simply hold the lump sum in escrow.
To prevent this, Alice and Bob can sign a timed refund transaction that contains a LOCK time. If the final transaction is not published before the LOCK time, all the BitCoins are sent back to Alice. The lock_time parameter can be added to transactions to tell miners not to add this block to the blockchain until the timestamp has elapsed.
These advanced scripts are called smart contracts because they rely on technical mechanisms to enforce the contract. Other examples include:
- Multiplayer lotteries
- Coin-Swapping Protocols
- and more!
How are BitCoin blocks actually put together? Why do we put transactions into blocks?
BitCoin transactions are bundled together into blocks to create a single unit for miners to compute. It also makes hashing the transactions shorter, because you only need one hash for the block that contains multiple transactions. This makes it easier to verify.
So what does a block in the block chain look like?
The block chain is a creative use of two different data types. There is the chain of blocks that look like:
|previous transaction: H ( )||previous transaction: H ( )|
|transaction: H ( )||transaction: H ( )|
recall that the stuff in parenthesis are pointers and the H stands for hash, so these are hashed pointers. Each block in the blockchain has a hashed pointer to the previous transaction for said address, along with the current transaction for that same address. The previous transaction is used to prove that the address actually owns the bitcoins it is using in the current transaction.
Within the current transaction, we have hash pointers that lead to a Hash Tree (Merkle Tree) of the transactions in that block. Each node in the tree holds two pieces of data:
|Transaction: H ( )||Transaction: H ( )|
|Trans: H ( )||Trans: H ( )||Trans: H ( )||Trans: H ( )|
The top level blocks hold hash pointers to lower-level blocks. To prove that a transaction is included in a specific block, you only need the path through the Merkle Tree.
You’ve now seen what the blocks look like, but what about in actual code? In code, the block is broken up in two parts:
- Block Header – The block header contains the meta information about the block. It also contains the pieces of the mining puzzle. It has the hash, time, pointer to the previous block, nonce, Merkel Root, etc. This is the only piece of the block that becomes hashed during mining. To verify chain of blocks, you need only look at the block header.
- Block Body – The actual transactions themselves, not hashed.
The BitCoin Network
This is a Peer-to-Peer network where all nodes are equal. No central nodes. No master nodes. All connections between nodes is random. This ad-hoc protocol runs on TCP port 8333. New nodes can join the network at any time and older, non-responding nodes are forgotten after 3hrs of inactivity.
To join the network, you first need to download the BitCoin client application, and then spin your machine up as a node. Once you’re fired up, you have to find atleast one node that is currently on the network, which is called a seed node. There are lists of seed nodes that you can connect to, probably do some Google-Fu for BitCoin seed node.
Once you have you’re seed node, you send a message to that node requesting addresses to all the nodes that the seed is connected to. You can then send those newly discovered nodes the address request, which will help connect you to the nodes they know about. After subsequent iterations, you’ll have a bunch of discovered nodes. You are now able to choose which ones you would like to peer with, thus joining you on the BitCoin network.
Why Join the BitCoin Network?
The network administers the block chain, so if you wish to have a transaction recorded, then you need to be on the network. The process of registering a transaction on the block chain is called transaction propagation.
It works like this:
- Your desired transaction is submitted to your node
- Your node broadcasts the new transaction (gossip protocol) to its neighbors.
- Those nodes now register your transaction in their pending transaction pool, which holds all the transactions the node has heard about but are not in the block chain yet.
- Once pooled, the neighbor nodes then broadcast the same new transaction their neighbors, which add the transaction to the pending pool and then broadcast again to their neighbors.
- This keeps going until nodes try to broadcast the transaction to other nodes that already have it in their pool. This is the mechanism that prevents the broadcasts from going on forever.
How Do Nodes Know Whether to Propagate Transactions?
One of the most important services that nodes provide is validation of the transactions. They run the script to make sure that it completes. They check if the BitCoin sender does in fact have the BitCoins they are sending. If all checks out, then they broadcast the transactions.
Errors could come in the form of invalid transaction or modified scripting (the node will check the script to a whitelist and will not run it if there is anything in the script not represented in the whitelist). There is also an error thrown if the node has seen the transaction before. Finally, if the node thinks there is a user trying to double-spend the same BitCoins, it will not broadcast the transaction.
The same propagation method is used when a miner discovers a block and broadcasts the new block to the network. Other nodes will add the block to the chain if:
- hash is valid
- proposed block has all valid transaction
- proposed block builds on the current longest chain – only relay new blocks if they come at the end of the chain, not at some earlier point.
Limitations of BitCoin
There are some hard-coded limits that BitCoin chose before it opened in 2009, and before it became a sought-out currency product. Most importantly:
- 10 minute average block creation time
- 1 million bytes per block
- 20,000 signature operation per block
- 21 Million BitCoin in circulation
- BitCoin mining credits started at 50 and is halved every 4 years
- Only about 7 transaction per second
- Cryptographic limits
- Only 1 signature algorithm (ECDSA/P256)
- hard-coded hash functions
- primitives might break by 2040
Most of these issues are built in and will not be fixed in order to get away from hard-forking BitCoin nodes. BitCoin can soft fork (introduction of Pay per script) but the community does not want any changes that makes older nodes invalid when interacting with newer nodes. They also don’t want to change the incentive structure when people have invested a lot of capital in the way things are.
How to Store and Use BitCoins
The important piece that you need when storing your BitCoin in the secret signing key, so BitCoin storage is really about managing these keys.
It is simplest to store BitCoins on your local device. Unfortunately, storing keys on your local device, while convenient, is not very secure and isn’t the most robust method of securing and storing your secret keys.
You can also use wallet software that keeps track of your coins and provides a pleasant user interface. Pro Tip – If you store your coins in wallets, have multiple different addresses in that same wallet and send your coins to the different addresses. For instance, you could have a separate BitCoin address and key combination for each coin. This gives most privacy while still being relatively easy to use (wallet software manages addresses and keys for you).
To spend your coins, you need recipient addresses which you can send to. There are two ways that addresses are conveyed:
- Text string (base58 notation)
- QR Code
Hot Storage vs Cold Storage
You’re going to have to store your BitCoins with a mix of online and offline storage mechanisms, also called hot and cold storage, respectively.
- Hot Storage – Online wallets are convenient but risky
- Cold Storage – Offline safes are safer but more difficult to access
The key is to use separate keys and addresses with the different storage mechanisms. But how do you move coins between the storage types?
Your cold storage will be safe and secure even if your hot storage (connected) is attacked, so they need separate keys. Beyond that, the storage mechanisms need to know about eachother, so they need separate addresses that they can each keep logged. Logging the keys also helps you transfer BitCoins back and forth.
The great thing about cold storage is that even though it is offline, the addresses used to accept BitCoins are always working, so we can transfer coins from the hot storage to the cold even when the cold is offline and not connected to anything. If you feel that you have too much money in your hot storage, simply transfer some of it to cold.
Because we want every coin to have it’s own address, we want to send coins from our hot wallet to a different address each time we deposit one in the cold storage. Here is how to set one up:
- generateKeysHeir – Issue an API call to generate heirarchical keys. Usually, the system will generate a public key (address) and private key to verify connection. Instead, the Heir flag at the end creates address generation info and private key generation info.
- Then, with the address generation info, we can issue a genAddr (generate address) call and pass an integer (i), thus creating the ith address to send BitCoins to.
- Similarly, we can use genKey (generate key) on the private key side and pass an integer, thus creating the ith private key.
This system has two very important qualities. Firstly, the ith address and the ith key match up in the same way as the generic call to generate keys. This means you have perfect sets of addresses and keys that you can use for sending BitCoins.
The other quality is that the address generation scheme doesn’t expose anything about the addresses, so we can give our address generation info to another party without worrying about it being hacked.
To set up our storage solution with hierarchical keys, we perform this sequence:
- Perform generateKeysHier on the cold storage
- Keep private key generation info on the cold side
- Take address generation info and pass to the hot storage. Now the hot storage can create as many addresses as needed without communication to the cold storage
- On the cold side, you can then generate the corresponding keys without needing to communicate
- This setup only requires the initial connection to send the address generation info to the hot side. Other than that, there is no coordination between the sides, keeping the cold storage safe and offline.
How Does Cold Storage Work?
There are many ways you can store your coins offline, including:
- Store your keys on a physical device, then put that device in a safe
- Brain Wallet – This is an encryption scheme for scrambling the data you want to keep safe. Requires the user to enter a passphrase to decrypt.
- Paper Wallet – Print important info to paper and then store the key documents.
- Tamperproof Device – Device that will safely store keys or creates keys for you in a secure manner.
Sharing and Splitting Keys
Storing your keys in one place leaves you vulnerable, so we want to be able to split them up and store them in multiple places to make our BitCoins more secure. This is called Secret Sharing.
The idea behind secret sharing is to break the key up into N pieces, then share K of those pieces to reconstruct the secret. If you have less than K pieces, you don’t learn anything about the secret.
When you combine secret sharing with Multi-Sig, you make a system where you can break up the shares of the key, then use those shares to sign your transaction rather than have to combine the shares again to make the signature.
Online Wallets and Exchanges
Online wallets are analogous to local wallets, but the info is stored in the cloud. The UI will run in a browser or application and the server will sends coded and store keys for you. You can then log in to access you wallet.
Online wallets are convenient and works across devices, but there are definitely security concerns and you data can become vulnerable is site becomes compromised.
BitCoin Exchanges are business that offer Bank-like Services. You deposit BitCoins (and fiat currency like $) and the “bank” promises to pay you back later whenever you want.
You can then make and receive BitCoin payments and even buy/sell BitCoins for fiat currency. To do this, they match buyers and sellers and try to come to a mutually acceptable price. NOTE – These transactions are not recorded in BlockChain, only in exchange ledgers.
The pros of BitCoin Exchanges are that they connect CryptoCurrencies with Fiat Currencies, allowing you to exchange them back and forth. However, this benefit comes with the same kinds of risks that banks have. You are susceptible to bank runs (not enough money to pay back deposits), malicious money schemes, and cyber attacks.
All of these issues have occurred to BitCoin Exchanges. In fact, the data is not encouraging and almost half of BitCoin Exchanges close due to some failure similar to the scenarios described above.
Proof of Reserve
BitCoin Exchanges are able to prove their holdings and their deposits through cryptographic techniques:
- Exchange can prove it’s holdings by sending itself BitCoins in a valid transaction.
- Example – if Exchange says it has 100 BitCoins, it can create a valid transaction sending 100 BitCoins to itself. If that transaction is recorded to the BlockChain, than they have proven they have the BitCoins they say.
- Exchanges can prove their depositors by creating a Merkle Tree that has each account at the bottom and hash pointers in the binary tree towards the top root. These hash pointers are then summed to show that there are not more accounts than represented in the tree.
- With these two figures, you can determine the fractional reserve (percentage of deposits on hand) for the Exchange. They can prove this reserve to you.
So you have a BitCoin and you want to buy something. The merchant wants to receive the payment in BitCoins but then convert that to fiat currency. They want it to be easy and they want low risk. How do we make this work?
Payment services are used to bridge this gap. They make it some a buyer can use their BitCoins conveniently while assuming the risk involved for the merchant.
BitCoin relies on transaction fees to keep all parties honest. Whenever a transaction is added to the block chain, it might also have a transaction fee. Because we cannot create BitCoins, the value of inputs should always be close to the value of the outputs. When the value of the input is a little larger, that difference is the transaction fee, paid to the miner for finding the block with your transaction.
You are free to set your own transaction fee, but as a general rule, higher transaction fees result in faster addition of your transaction to the block chain.
You don’t need to pay a fee if your transaction is less than 1000 bytes. Otherwise, the consensus fee structure state that transaction fees are typically .0001 BTC per 1000 bytes. The approximate transaction size is: (148 bytes * number of inputs) + (34 bytes * number of outputs) + 10 bytes for headroom.
Most miners adhere to this fee structure and if you choose not to follow it, your transactions might take a long time before being recorded in the block chain. Additionally, miners prioritize transaction based on fees and a priority formula (looks at how long your transactions have been waiting divided by the size of your transaction). Most wallet software and payment services include the consensus fee structure as part of their operations.
Currency Exchange Markets
Bitcoin is a market so the price fluctuates, but there are services like https://bitcoincharts.com/markets/ or https://localbitcoins.com/ that offer ways to purchase bitcoins and see there value relative to other sellers. There are also BitCoin trading Meet Ups where you can meet with people in real life.
The markets match buyers and sellers. They are large markets so there is a notion of consensus price, and there should always be a supply of bitcoins. The Supply and demand are used to set the price.
The supply of Bitcoins = coins in circulation (13.1B up to 21B eventually) + demand deposits. Only include demand deposits when demand deposits can actually be sold in the market.
2 main sources of demand. 1 is as a way to mediate fiat-currency transactions. The transaction mediation function has a direct correlation to the price, as the demand for the service increases, the price increases. 2nd is the Bitcoin that are purchased for investment.
Bitcoin depends on miners to validate transactions and build blocks in blockchain. Here is how to be a BitCoin miner in 6 easy steps:
- Join the network and listen for transactions
- Validate proposed transactions
- Listen for new blocks, maintain the block chain
- Validate the block to make sure the transactions contained within are valid
- Assemble a new valid block
- Find the nonce to make the block valid (this is the difficult computational step)
- Hope everybody accepts your new block
Within these steps, the validation portion is the only part that BitCoin needs. The rest is incentive for miners to actually perform the validation.
Finding A Valid Block
There are two main hash-based data structures. The block chain which points to the next block, and the Merkel Tree within the block that points to the transactions.
- The first thing you do as miner is assemble all outstanding transactions into Merkel Tree.
- Then you create block header to point to the previous block.
- Then you search (guess different numbers and test to see if they work) over nonce field and try to get hast to have the same number of zero’s as the nonce.
The difficulty in finding the nonce that satisfies the requirements is recalculated every two weeks, based upon the difficulty the previous miners had in finding nonces for the last 2016 blocks. Blocks should be found once ever 10 minutes, and difficulty is ratcheted to create this situation. This means, over time the mining difficulty will generally increase, as more hash-power comes online, the difficulty will keep going up.
SHA-256 is a general purpose cryptographic hash function. It was published in 2001 as part of a larger collection (the SHA-2 family) of hash-functions by the NSA. It remains unbroken, but it does have known weaknesses. The SHA-3 family is already in standardization.
SHA functions work at the bit level. The password is divided into 8 discreet 32-bit words, and each has a bitwise operation performed on it. Then the resultant words are added together MOD 32. That would be 1 round of SHA-2. A complete run of the algorithm consists of 80 rounds, meaning there are 80 different constants that are used during the bitwise operation.
Weird Quirk – When mining bitcoin, you actually compute SHA-256 function twice. We don’t know why this is.
Mining was first performed by general purpose CPU’s. The can perform the task, but at current difficulty levels it will take over 100,000 years to find a single block. Due to this poor performance, people started using GPU’s. GPU’s offer high parrallism, so you can compute multiple hashes at the same time. You can also drive multiple graphics cards from one CPU, further multiplying your hasing power. They also have high throughput (how quickly you are finding blocks). They were first used for mining in 2010.
GPU’s also offer overclocking, where you run the card much faster than designed, which of course degrades performance and can break the card. There is a measure called “Goodput”, which is the throughput times the success rate. This means that it is worth overclocking your CPU by a huge 50% even with a high error rate of 30%. This can lead you to find valid cards more quickly.
GPU’s have disadvantages. GPU hardware is wasted during mining because you don’t utilize all the features. They have poor cooling and get quite hot when next to eachother. They have a large power draw.
In the end, how much better are they. You can safely get 10x the amount of processing power from a GPU, dropping time dramatically. However, it will still take over 100 years, so GPU mining isn’t as common anymore.
In 2011, GPU’s were replaced with FPGAs (Field Programmable Gate Array). They are designed to offer hardware like performance but allow the customer to reprogram them in the field. The offer excellent bitwise performance, better cooling, and extensive optimization options.
FPGA’s also have disadvantes. They have high power draws and lots of errors, they are poorly optimized for 32 bit work, they require advanced knowledge and are more expensive. Finally, in the end, they only offer marginal performance over GPU’s. However, if you knew what you were doing, you could drop the time to find a block to 25 years, or 5 times faster than GPU’s.
Bitcoin ASICS (Application Specific Integrated Circuits) are designed from scratch to mine bitcoins. They are only bitcoin miners. There are lots of options, but they have long ship times and low stock. They are designed to run at full speed and always on. They are perhaps the fastest chips ever produced for a particular purpose. These drop the average time to find bitcoins down to months.
The market dynamics weren’t kind to ASICS as they first came out. Most board technology is obsolete within 6 months, while most of the profits from the rig were generated within the first 6 weeks of the ASICS release. Then combine the shipping delays and most early customers would have lost money on the proposition.
This paints an unfavorable picture of mining, so why would anyone do it? Well, the value of a BitCoin keeps rising and can make mining profitable for you. Even so, most of the miners who bought machinery would have done better if they simply invested in BitCoin, held on during the appreciation, then sold for a profit.
Professional Mining Centers have popped up around the world. One is Genesis-Mining, which I used and lost almost $100 in a year.
Energy Consumption and Ecology
Computation requires energy (Landauer’s Principle), in fact, to flip one bit requires energy measured in joules. Because hash functions are non-reversible, energy consumption is inevitable.
Three steps in the process requires energy:
- Embodied Energy – Energy in building and shipping equipment
- Electrical Energy – The energy consumption of running the algorithms
- Cooling Energy – The energy spent on cooling the equipment
Over time and at scale, the embodied and electrical energy requirements should become more efficiently used. Cooling, on the opposite, will go up as more electricity and equipment is used.
We don’t know precisely how much energy is being used in BitCoin. One estimate says we are using 900 MegaWatts per second. A lower bound estimate says we are only using 150 MegaWatts, but we are somewhere in between. The whole BitCoin network is using a large power plant worth of electricity.
As an aside, it is important to note that any financial system requires energy. BitCoin does not expend more energy than any of these functions. The wasteful idea comes from the fact that you are solving computations that don’t really do anything, and you’re using a lot of energy to solve them. However, these computations are critical for safely and securely maintaining the currency system, just as moving gold from one fort to another would be important to a bank, even though the act of physically moving it is trivial. If BitCoin is useful currency, then electricity use usefully used.
A wonderful idea for offsetting this consumption is a data furnace. With this, you are using the heat generated by your mining equipment to provide heat for your home or office. So, instead of buying a space heater, you’d buy a mining rig. The efficiency of doing this isn’t that much worse than electric heaters.
Mining is complex and there is no assurance that you will find the multiple blocks you need to find in order to make the money you want. Historically, to spread risk over small entrepreuers, a risk pool is created. For the same reasons, mining pools are created:
In a mining pool, all participants attempt to mine a block, with the same pool manager receiving the returns. Once the revenue is received from finding a block, the pool manager distributes the funds according to how much work was performed by each member, minus a small cut for the manager.
We can tell how much work someone is performing by outputting shares. It is rare to find an actual block, but there are a lot of almost-blocks that, once transmitted to pool manager, can give an indication of how much work is being performed.
There are quite a few protocols for running mining pools. There is an API for communicating between managers and miners. Often, hardware will support the protocols at the mining hardware, so your miner can hook right in a get the instructions from the pool.
The first pools appeared in 2010 and by 2014 about 90% of all miners were in a pool. Today, 2 mining pools, G.Hash and Discuss Plus, control half of the hash power.
Mining pools are great in that they spread the risk and make it easier to mine profitably. However, they lead to centralization and discourages individual miners from running full BitCoin nodes. Previously, all miners had to run a fully validated node, now a days the manager is the only one who runs nodes.
Mining Incentives and Strategies
There is some game-theory that says you can make more money with different mining strategies.
You could launch a forking attack where you send bitcoin but then add a fake transaction 6 blocks up the chain to move that BitCoin to another address you hold. If you have more than 50% (the attack becomes progressively easier the higher about 50% you control) of the global hash power, your fake transaction would become record and your real transaction would become invalid. This attack is detectable and can easily be reversed. This would also likely crash the bitcoin exchange rate.
It would be very expensive to buy the computers are ASICS necessary to control over 50% of global hash, so another idea is to bribe other miners to create the 50% control.
To defend against forking, Bitcoin performs regular checkpointing, which occurs when the developers decide a single point in time where they will not accept any transactions before that date.
You have the option to not announce the discovery of a block, giving you the opportunity to find the next block in the chain before anyone else. This has the side-effect of forcing everyone else to mine blocks that will be discarded when you announce yours. This is also called Selfish Mining.
If you wanted to blacklist transactions from a specific address, you could refuse to mine any chain that included transactions from this address. If you have more than 50% hash power, you could effectively shut out that address and make their currency worthless.
BitCoin addresses are public key hashes, not real identities. We don’t use our real names, but we do use a publicly identifiable “identity”. Computer scientists call this pseudonymity. In computer science, ananymity = pseudonymity + unlinkability.
Unlinkability occurs when different interactions with the same system are not linkable to eachother. This means you can’t tell if a single user has logged in more than once.
Pseudonymity is not privacy. In fact, it is not difficult to link back to a real life identity if you have enough pseudonymity logins. Also, many BitCoin services require real identities.
In the context of Bitcoin, unlinkability would make it difficult to link the different addresses of the same user. It should also be difficult to link different transactions from same user. It should also be difficult to link the sender of a payment to it’s recipient.
However, this unlinkability would be difficult to achieve completely, so we introduce the concept of anonymity set. This is the size of the crowd that you are blending into. If the set is sufficiently large, it becomes more and more difficult to find links between members of the set.
Ethics of Annonymity
Block chain based currencies have all transactions publicly and permanently traceable. Without anonymity, your privacy is much worse using crypro than traditional banking.
Money laundering is a big concern of BitCoin. This is mitigated by the fact that it is difficult to move large sums of money into and out of the BitCoin ecosystem. Once the funds are in BitCoin it is easy to move, but getting a large sum of BitCoins and cashing them out is difficult to do with anonymity.
Annonymity and Decentralization are often in conflict because decentralization is achieved via public traceability.
How to De-Anonymize Bitcoin
A way to peek behind the curtain of anonymity is to linking addresses together. To do this, watch for shared spending transactions, when multiple payees are paying one payer. The payees are either one person with multiple addresses or a group that all operates together. There are ways around this, like CoinJoin.
Another way is to watch for change addresses. You can only send the full amount of an address in a transaction, so if you don’t want to use all the funds, remember that Bitcoin supports unlimited inputs and outputs. All you have to do is create a new addresses, then send your payment to the recipient and the remainder in the account to a change address.
One thing to watch for is that change addresses are often only ever used once, so they can be traced back through a concept called “Idioms of Use” or understanding the idiosyncratic features of most default wallet software. Wallet software will automatically create a new change address then never use it again, so this feature can be monitored and exploited by adversaries. To limit this, reuse some change addresses.
A best practice is to always receive Bitcoins at a new address, never reuse an address to gain receive Bitcoin from another user. Another best practice is to use Bitcoin through Tor.
In many instances, to protect anonymity, use an intermediary. This is the idea behind anonymity. If you pay coins to intermediary, who then creates new transactions bundling your coins with others, and then use those intermediary funds to complete a transaction, someone watching the public blockchain can’t tie your deposit to the transaction, obfuscating you.
Dedicated Mixing Services offer this. They promise not to keep records and they never ask for your real life identity. This is in contrast to wallets, which typically require identity. At the very least, if they don’t ask for real life identity, the wallet service knows the address of all of your accounts, so they can be easily used to track you down.
Currently, the anonymity properties of mixes are lacking. There are, however, 4 recommendations:
- Mutliple mixes should be performed in a series, with a backend API to standardize this practice.
- There should be a uniform chunk size to the transactions to make them indistinguishable.
- Desktop software should be able to communicate with mix services (through API), not web interfaces
- Fee structure should be all-or-nothing. Currently, a small percentage is taken as mix fee. What should happen is mix should send the full chunk most of the time, but a small fraction of the time it should take the whole chunk for itself.
The next problem is that users must trust the mix service providers. Trust is enhanced by:
- Staying in business for a long time (build reputation)
- If chunk sizes are small, then user will make lots of transactions and the users can test the service for themselves to ensure things are working properly.
- Warranties can be provided by the mix to the client, and if the mix cheats then the client can publicize this breach of trust.
In decentralized mixing, you work with a community that mixes with eachother. Main proposal is called a CoinJoin. In this scheme, different users come together to create a single bitcoin transaction that combines all of their inputs (inputs are of equal value). The transaction would then have multiple outputs. You would then perform multiple rounds of this decentralized mixing.
- Users find eachother
- Exchange input/output addresses
- Construct transaction
- Submit transaction and collect signatures from each member of group. Group members much check that their output address is included to make sure they will get their money)
- Broadcast the transaction
Zerocoin and Zerocash
Zerocoin and Zerocash are alternative anonymous protocols with better efficiency, however the protocols are incompatible with BitCoin. The makers plan to release it as an alt-coin.
Zerocoin offers a Protocol-level mixing where anonymity is guaranteed. As Zerocoin is a protocol, we will call the coins built by this protocol BaseCoins. The key about Basecoins is that they can be converted into Zerocoins and back again freely. When you do this, it breaks the link between the original basecoin and the newly converted basecoin.
To perform this conversion, Zerocoins offer cryptographic proof that you own a coin and that coin can’t be spent by anyone else. Miners can then verify these proofs, giving you the right to redeem a new Bascecoin in exchange for the Zerocoin.
Zerocoins come into existance by minting. Anyone can make one and they have a base value once put onto blockchain. Minting entails:
- Generate long, random serial number to make public, then generate random secret (private) then hash the two serial numbers. This is called a committment.
- Now put that committment on the blockchain with 1 basecoin as input. This spends the basecoin to mint 1 Zerocoin.
- To later spend the Zerocoin, reveal the serial number. Miners will then confirm that the serial number hasn’t been used before.
- You then pick any arbitrary zerocoin in the blockchain, and that becomes your new Basecoin.
Zerocash takes the cryptography to the next level. It is more efficient to the point where you can run the system without any basecoins. All transactions are zerocoins, so zerocash becomes untraceable. Splitting and merging transactions can be performed entire in Zerocash. The BlockChain only records the existence of the transactions, not any of the details.
There is a catch. To set up the protocol, you need secret keys that are destroyed and cannot be known by anyone else. This is difficult, how can an entity set up the system and then convince everyone that they have destroyed the tools they can use to cheat the system.
Levels of Anonymity
|Bitcoin||Pseudonymous||Transaction Graph Analysis||Default|
|Single Mix||Mix||Transaction Graph Analysis||Usable today|
|Mix Chain||Mix||Study Side Channels||Bitcoin-compatible|
|Zerocoin||Cryptographic Mix||Study Side Channels||Altcoin|
|Zerocash||Untraceable||None||Altcoin, setup problem|
Tor and Silk Road
BitCoin anonymity becomes more powerful when combined with anonymous communication channels (Tor). It works by the Tor client choosing a path over node computers (Tor specs say you should hop over 3 different nodes) with all nodes being encrypted. When you are through the nodes, you are then connected to the service you are attempting to reach, but an attacker cannot see how you got there if atleast one of the nodes is not compromised.
Layered Encryption is used to communicate between us and ever Tor node. To ensure that the message you send reaches it’s recipient, you encrypt the next node destinations into the transmitting packages. This means, If I want to communicate with Bob over a three-hop Tor network, I encrypt three separate keys, one for each hop. This way no one node can know the destination IP address, breaking the link between my IP and their IP.
When I send the message to the first node, it is triple-encrypted. The first layer of encryption is removed by the first node, the next node IP address is read, then the message is sent to the next node with two levels of encryption. The 2nd node strips the 2nd-level, reads the 3rd node IP, then sends it with a single level of encryption. The 3rd node (called the exit node) strips this, reads the Bob’s IP, then sends the unencrypted message to Bob. An attacker watching Bob would only know that a message came from a node to Bob, not that the message came from me.
Known as a hidden service, the server wants to hide it’s address. To create a hidden service, the server connects to a Tor node (rendezvous point) through the Tor protocol. It them publishes the mapping between the domain name and the address of the rendezvous point. The client can then connect to the rendezvous point by visiting the onion address.
Silk Road relies on anonymous communication using the Tor protocol and anonymous payments using BitCoins and other cryptocurriencies. Silk Road then used a rating system to establish some form of security (that you will get what you pay for) and they left shipping up to the participants (although they did recommend setting up an anonymous PO Box).
Consensus in Bitcoin
Consensus is critical among peers to make Bitcoin work. You need consensus on what rules should be applied to make the Bitcoin ecosystem operate effectively. You need a consensus about history in that you agree on which transactions are recorded in the blockchain. Lastly, you need consensus on the value of Bitcoins (every currency needs this). These 3 forms of consensus rely upon eachother.
BitCoin Core Software
Open-source software (MIT license) that is the most widely used Bitcoin software. Even alternative Bitcoin software follows the rules and protocols established by the Bitcoin core software. The Bitcoin Core defines the rule book for Bitcoin.
Bitcoin Improvement Proposals (BIPs) are formal improvement proposals that include technical spec and rationale. They are published in numbered series and each BIP has a champion who publicizes and pushes adoption.
There is a core team of 6 (including Shatoshi Nakamoto) that pushes new rules to the Bitcoin spec. They write default rules, but they cannot force people to play by those rules. Rules can be forked at any time, so different rule sets can be used by different community members, giving power back to the community as opposed to the centralized core team.
When forking, you create a branch in the blockchain, with one side valid under certain rules, and the other branch invalid under those certain rules. The forks will never merge again. At the moment of the fork, it is like you create separate currencies and the blockchains will continue to grow incompatibly to eachother.
After a hard fork, the community can:
- start an altcoin with one of the branches.
- If the fork represents a fight between the community on how to proceed, the branches will fight for market share and eventually force one of the branches to disappear. . Each branch claims to be the “real” Bitcoin.
Bitcoin Stakeholders: Who is in Charge?
Game theory concept: Whichever party has the most advantageous position should an agreement not be reached is in the most advantageous position for the deal itself. The likely winner of a fight is often the winner of the argument, even if no blows are thrown.
In a struggle for the rulebook of Bitcoin, the WordPress Core Developers have the most power and almost everyone uses their code and follows their rules. It can be said that the core team hold the consensus on the rules. The miners also have power because they make the blocks that record transactions, creating the historical record. If a majority of miners make consensus, then they can extend the longest branch and take make decisions on rules. Investors buy and hold a lot of the Bitcoins, so they determine the relative value. Investors hold the consensus of Bitcoins value.
For example, should a hard-fork occur, it is the investors that will put their money behind one of the competing branches, thus deciding which branch wins and is percieved to be legitimate.
Finally, merchants and customers have a great deal of power because the value in Bitcoin is using the currency in a transaction. The merchants and customers control the transactions, so they drive the long-term price of Bitcoin. Payment services also have a great deal of power, as merchants and customers aren’t worried about how they are getting paid or paying, just that they can use what they have as currency in a transaction, and at the end of the line get real-world currency.
To succeed, the crypto requires all of these parties, so they all have power to control the outcome of Bitcoin.
One thing to know is the Bitcoin Foundation. It was established in 2012, it pays the core development team, and it lobbies governments to evangelize Bitcoin. It is not in charge of Bitcoin and it’s success relies on how much support it can attract and retain from the community.
The Foundation is controversial. Members have gotten into legal and financial trouble. Many believe that Bitcoin shouldn’t lobby, it should be above government. Lastly, community members don’t feel that foundation members aren’t representative of community, creating dissonance.
In reality, no one entity is in control of Bitcoin. However, everyone has a stake in Bitcoin because it is the consensus of everyone that allows Bitcoin to operate.
Roots of Bitcoin
There are 2 precursors of Bitcoin to discuss:
- Cypherpunk movement – Belief that government would be better with a minimal ruleset and leaving citizens alone. It is a fake-ass libertarian bent that is only available to affluent white men and those close to them. The anti-government bent in the late 70’s brought us strong cryptographic utilities like public key cryptography.
- In order to create this cypherpunk world, they would need an anonymous way of bartering with eachother. Chaum et al. made great headway in a early digital cash spec that lent itself heavily to the creation of Bitcoin.
Bitcoin began in 2008 with whitepaper written by Satoshi Nakamoto. It was released along with open-source software to implement Bitcoin. We don’t know much about Satoshi Nakamoto. It is almost certainly a pseudonym, with the real identity unknown. Within the Bitcoin ecosystem, Satoshi has a special signature that lets people know that he/she really existed and contributed to the blockchain.
Satoshi has barely been heard from since 2010 and owns lots of Bitcoins because of early mining activities. He was originally the only miner, and Bitcoins in those accounts are valuable. However, those coins have not been cashed out, so people are closely watching accounts to see if they can figure out who Satoshi is.
Who Satoshi is doesn’t matter. Any special influece he/she has is only because of special feelings among the community, not because Satoshi has any power over rules of function in Bitcoin.
Bitcoin in Governments
Countries don’t like crypto’s because they lose capital controls, the state’s ability to control the flow of capital. In order for government to remain control, they must separate capital from cryptocurrency system.
Certain crimes that require anonymity are enabled by crytocurrencies. Tax evasion becomes much easier as well. Illegal items are also sold more commonly on cryptocurrency markets, Silk Road is a great example of this.
It is hard to keep the real world and virtual world separate. And it is hard to stay anonymous for a long time. Always remember that cash flows are simple to follow, BTC gained by nefarious means is untouchable.
Anti-Money Laundering Efforts
Anti-Money Laundering are capital controls that prevent large sums of money fro moving between underground and legitimate economy without detection. A concept that goes along with this is called Know You Customer (KYC). It requires financial institutions to identify and authenticate clients. The KYC business also must watch for anomalous behavior from their clients.
In the US, there are mandatory reporting requirements:
- Must file currency transaction report for transactions over $10,000
- Companies must watch for clients who structure transactions in order to avoid reporting
- if you make lots of $9,000 dollar transactions, this can be structuring to avoid the hard cap
Alt-Coin Mining Puzzles
Mining puzzles determine the incentive system, so puzzles are at the heart of Bitcoin. You want to make the puzzles difficult to attacks are costly, but not too hard or miners would not participate. Miners want compensation for the bandwidth they add to the network.
Essential Puzzle Requrements include:
- simple to verify solutions
- adjustable difficulty so puzzle can be tweeked as users come and go from network.
- the ability to find blocks should be proportional to the hashpower contributed
- if a user has 2X the hashpower you do, they are twice as likely to find block nonce.
ASIC Resistant Puzzles
These are the most sought after alt-mining puzzles. As BitCoin mining moved from the CPU nodes to ASIC chips, which blow away both CPU’s and graphics cards for speed in finding blocks. This isn’t the best situation as normal users have no incentive to participate in this part of the Bitcoin ecosystem, centralizing the mining power in the hands of few and few operatives. For this reason, puzzles are developed to prevent large ASIC manufacturers from dominating.
Memory Hard Puzzles
Since 80’s processing speed has increased exponentially, along with storage and memory, however the processing speed is growing faster. If puzzles are created that utilize storage and memory, as opposed to processing, this can dilute the advantage that ASIC’s have over smaller miners.
Scrypt is the most popular Memory Hard Puzzle. It was created by Colin Percival in 2009 and is a memory hard has function. It’s essentially the same puzzle as default Bitcoin, but the SHA2 hash is replaced with Scrypt hash. It has a constant time/memory tradeoff, so the puzzle can be solved with a fixed amount of memory. You can try to solve with less memory, but it will take longer to solve the puzzle.
Scrypt is the most widely used alternative mining puzzle and is also used in security packages and for password hashing. This gives users more confidence in the underlying technology. Scrypt has two main steps:
- Fill memory with random values
- Read from memory in random order
Our goal is to compute the scrypt hash function of input string x. To do this, we calculate the SHA2 hash of x, and place that in memory as V1. In the next memory location, we place V2, which is the hash V1. V3, therefore, is the hash function applied to the input string 3 times. And so on so Vn = Hn(x).
That is step one, in the next step we read back the values from memory in random order. We use an accumulator that is initialized with the hash of the final V stored in memory. We then use the accumulator to pick a index (i) in the array. It then hashes the value in this index and replaces the accumulator with either the hash of the accumulator or the hash of the value. After N iterations, the final value of the accumulator is the value of the hash function.
Scrypt is memory hard because as you reduce the amount of values stored, you increase the processing loops needed to find the values. However, it has disadvantages because the proof is also memory hard, so checking the work is more difficult. Additionally, Scrypt ASICs are already in production and are faster than your computer.
Another great option for ASIC proof mining puzzles is to change the puzzle periodically, so that hardware miners can’t keep up with the changes and more nimble software miners are given the advantage. However, its an open question as to how puzzles can change and still meet security requirements.
Proof of Useful Work
It would be nice if mining puzzles had some social benefit. Mining consumes a significant amount of power which is used to solve SHA2 puzzle, but doesn’t do anything beyond that. How can we make mining better for the world, which would make it better for the miners?
In mining puzzles, you use computation power to find what you are looking for. This is a needle in a haystack problem, so similiar problems can be addressed by the miners, with hopefully a sociological benefit. Protein folding or searching for aliens would be a good example of needle in a haystack problems that could be mined with some outside benefit.
To run this distributed computing project, you would need a trusted administrator to manage the system. You would need randomly generated problems, which wouldn’t have the practical use you are looking for.
A different approach would be to instead focus on investment in Bitcoin mining infrastructure. There has been over $100 million invested by miners into the network, is there some way to make all the bandwidth useful? There are storage mining Altcoins that use the computer storage as opposed to processing power.
Nonoutsourceable puzzles are puzzles that make mining consolidation more costly. Today, most miners are part of mining pools, with an administrator who represents a centralization of power. The more power they get, the more likely they are to become attacked.
To prevent this, the system encourages miners to find solutions for themselves and reap the rewards for themselves, as opposed to in a mining pool. The approach would be to require all miners to have private and public keys for signing their solutions. Then, when a solution is found, they do not need to submit anything to an administrator, they have everything they need to spend the Bitcoin for themselves.
In essence, to find the solution you need the private key, and with the private key you are able to submit the solution yourself and reap the rewards yourself.
Proof-of-stake mining puzzles introduce the concept of removing the power consumption and equipment from the mining process. In this scheme, you would send Bitcoins to an address which would then perform a lottery and distribute Bitcoins to a winner or winners. You wouldn’t spend money on equipment or electricity, but you would spend money on buying your raffle ticket.
This would be better for the environment and savings would be distributed to the entire network. Bitcoin users are also stakeholders and have incentives to be good stewards, so this system would remove some of the adversarial nature in finding blocks. There wouldn’t be a technology advantage, so the field would be leveled.
Virtual mining also has security advantages in that someone cannot simply buy up 51% of the mining hashpower to perform an attack. Since mining hashpower is obsolete, an attacker would have to buy up 51% of all the crypocurrency to become a controlling stakeholder. This would be more difficult and costly.
Virtual Mining Variations:
- Proof-of-Stake – The value of your coin grows over time if not used. Spending the coin resets the value.
- Proof-of-Burn – When mining, you send a coin to an unspendable address, essentially burning your coin that you use in the lottery.
- Proof-of-Deposit – Similiar to burn, but deposited coins are time locked, not destroyed. You can eventually get it back, but you lose the opportunity-cost of whatever transaction you could have made during the interim.
- Proof-of-Activity – Anyone with a coin is automatically entered into the lottery. If you win, then you have to submit a signed transaction taking possession of the coin within a certain amount of time.
Bitcoin as a Platform
The Bitcoin blockchain is an append-only log in that we can only add to the ledger, and what is there will be there forever. We also have a notion of order, so one thing came before another thing. We can expand this concept to become a form of secure timestamping.
We would want to be able to prove that something happened at time t, if possible without revealing what actually happened, just that something happened. Hashing creates a committment to the data being hashed. If we publish a committment to something happening, we publish the hash, which is certainly unique and cannot be reverse engineered to find out what actually happened, just that something happened.
Later on, we can reveal what happened, and can prove that we had knowledge of what happened because of the properties of hash functions. This would be useful for proof of knowlege. Suppose we have a patent idea but we don’t want to publish it, we can publish a hash of the idea, then if we had to prove that we had the idea before someone else, we can look backwards in time and prove when you had the idea.
It would also be useful in voting. When you send in a vote, the receiver would publish a hash of your vote, committing to your vote and showing when it came in. There are also applications in betting. You could commit to betting that something will happen, then you can later prove that commitment and either receive your winnings or pay or loses.
Bitcoin as Smart Property
Because every coin has a long history recorded in the blockchain, thus identifing each Bitcoin separate from eachother and making each coin unique with a unique history. They are not considered fungible (each unit has the exact same value), but can this history property be useful? It can by writing metadata into the transaction signature, and can be used in many different ways.
Using Bitcoin for Secure Multi-Party Lottery
Thanks to hash committments, we can build a lottery system with provable randomness and secure payment. Here is what it would look like:
- Participants publish a hash of their lottery numbers. If I choose 15 as my lottery number, I publish a hash commitment of 15 (my nonce). Other participants choose different numbers and publish the hashes of their nonces.
- After the first phase completes, everyone then reveals their chosen numbers and the other participants check what they reveal against their hash to see if it matches the nonce.
- We can then xor the chosen numbers by eachother and hash that result, then mod the result by the number of participants, narrowing the result to one of the participants.
- Finally, use a switch statement to read out the winner and you have performed a successful lottery.
- You can use timed commitments to make this scheme even more secure and fool-proof
Bitcoin and Randomness
In our current lottery system, each party introduces data to create randomness. However, is there a way to create randomness with Bitcoin without having inputs from all the participants.
For instance, each year the NBA lottery is considered to be rigged. Is there a way to prove randomness?
The idea is to create a cryptographic beacon that periodically spits out completely random data, with these features:
- Uniform randomness
- No party can predict in advance
- All parties can see the same values
Public displays of randomness using wheels or dice are easy to show in person, but difficult to establish trust remotely.
The National Institute of Science and Technology has constructed a randomness beacon that uses entangled photons, however one must trust that NIST is implementing everything in a trustworthy fashion. They have a feed on the web and we can simply listen to the server for the randomness.
We would need to use a natural phenomena that everyone can observe but cannot be rigged. Think sun spots or cosmic radiation, it is there and random and can be observed by anyone. This data is slow to change and requires an observing party, any other way?
We can use the changes in the stock market and create a randomness beacon. It is difficult to predict low-level fluctuations in stock prices, so randomness is good and manipulating the stock market would be super costly. This method is susceptible to insider attacks from people running stock market.
How could we use the block chain? We can use the random nonces that miners are finding as a randomness beacon. We would need to extract the nonce from every block, then every time a block is published we would get a new piece of random data. This would work great as long as the payout is less than the value of a Bitcoin, but wouldn’t work when there is millions being moved (like the NBA draft).
Prediction Markets and Bringing Real-World Data into Bitcoin
The block chain can be extended with metadata to include real-world facts. This can be stock prices, sports scores, even presidential results. When this data is added to the block chain, scripts can then be run to check this data and, if it comes from a trusted source, wagers can be placed on this data.
So, if the block chain updates all basketball games scores at the end of each quarter, you could place a wager on the scores at the end of quarters and run the entire scheme through Bitcoin.
Prediction markets are markets where you can trade shares in a potential future event, shares are worth a value if the event happens, 0 value if event does not occur. Economists love prediction markets because they offer glimpses into how people truly feel and what they really believe will occur. However, they are difficult to regulate and have come into many problems in this country.
Can we make a decentralized prediction market with Bitcoin? We would need to decentralize payment and settlement of debts, which is easy with Bitcoin. We can either use an arbiter to escrow wagered funds, or an alt-coin that can support everything we need.
We would also need arbitration to decide winners and make sure they get paid. The arbiter has a lot of power and we would want to decentralize this power. One idea is to have all users vote on real-world result, with incentives for user to vote honestly.
Lastly, we would need to keep an order book as prediction markets hold two figures, the lowest price for a share and the highest price someone would buy a share at. In a decentralized world, share orders would be submitted to miners, and miners would then match the buyers and sellers. We then pay the miners transaction fees based on the spread between low and hi price points.
The first Bitcoin-like derived Altcoin systems were introduced in 2011, two years after Bitcoin was adopted. Then, in 2013, the number of altcoins jumped dramatically.
Altcoins begin their life cycle very similarly to Bitcoin. There is a genesis block which creates the coin and a transaction history to initialize the value. Bitcoin is by far the biggest kid the block, it has up-to 95% of cryptocurrency market capitalization.
Most Altcoins have some distinguishing factor that makes them interesting to study. Some have better security or mining puzzles. They can have additional anonymity properties. They can change the built in parameters, thus adjusting monetary policy. They are often targeted at a common-interest community, providing some features that serve that community.
Namecoin differentiates itself by the inclusion of a domain name. This is a decentralized replacement of the domain name registration system. You can’t access namecoin over normal browser, but you can use plugins that allow for .bit addresses.
Also launched in 2011, Litecoin features memory-hard puzzle mining to prevent ASICS from dominating mining. However, Litecoin ASICS are now in use.
We have many metrics for comparing Altcoins:
- Market cap – This is an overestimate in available liquidity, and doesn’t factor coins that are out of circulation. If a coin is unusable, the market can’t denote this.
- Exchange volume – We have to look at 3rd party exchanges, which can be manipulated deliberately.
- Total Hashpower – This is the amount of computation the community contributes to mining the cryptocurrency. This only works for similar mining puzzles.
- Merchant Support – Difficult to measure, but offers a glimpse and the real world value of the crypto.
How Bitcoins and Altcoins Interact
Bitcoins and Altcoins are in competition together, but they don’t have to behave with hostility towards eachother. Altcoins are suseptable to attack because large mining pools can overpower smaller cryptocurrencies, as happened to CoiledCoin in 2012.
Usually, you can only mine on one crytocurrency at a time. You can, of course, divide your hashpower towards two separate crytos, but it will take longer to find each one. This makes bootstrapping difficult (it’s hard to convince people to use your system if no one is using it and other miners would have to stop mining Bitcoin and switch to yours). Merge mining allows you to mine on Bitcoin and the Altcoin at the same time without splitting your hash power.
In merge mining, every attempt to find the nonce for the Altcoin is also a valid attempt to find a nonce in the Bitcoin ecosystem. It does this by adding metadata (an alternative header) to the scriptSig. The alternative header has a pointer to a valid previous block and the Altcoins merkel tree. All data that is needed for Altcoin is encoded in ScriptSig. You compete one hash and it can be the Bitcoin solution, the Altcoin solution, or even both!
Merge mining makes it easier to get people to participate in your crypto. However, it makes the Altcoin more susceptible to attack by large miners or pools.
Tying Transactions Together Between Block Chains
In general, no one transaction has any particular connection to any other transaction on a separate cryptocurrency. There is no way of referring one transaction to another when changing ecosystems.
If Alice wants to send one Bitcoin to Bob and Bob wants to send one Namecoin to Alice, who goes first if they don’t trust eachother. We want to tie the transactions so that they either both complete, or neither transactions go through. This process is called an Atomic Cross Chain Swap.
In essence, each party creates a deposit and a refund. If the deposit does not complete on time for each party, then they are both refunded. No party can claim a deposit without also allowing the other party to also claim the deposit (through secret keys). This technique does require more transactions to complete, so most exchanges between cryptos happen at exchanges.
Lifecycle of an Altcoin
In general, here are the steps for creating an Altcoin:
- Fork the existing code base and block chain for an existing cryptocurrency
- Add in technical features or modify parameters to create the system you desire.
- Get people to join your network by announcing source code on forums
- Bootstrap Altcoin – make people find your coin valuable
- Get miners
- Get Stakeholders
- Build development community
- Must buy and sell them in exchanges or marketplace
- Altcoin Infrastructure
- Tipbots or faucets that allow you to give someone else portions of your crypto. Tipbots announce the gift and tell the client how to claim the Altcoins. Faucets give out small amounts of Altcoins for signing up for email or visiting web page, we choose the goal.
- Branding – You need to brand your Altcoin and market it for growth.
- Exchanges – You need to be able to exchange your currency for other currency or for products / services.
- Testing and Block Explorer to examine code base and block chain
- We then need to allocate our Altcoins and fundraise
- There are many options: You can give a bunch of crypto to the founders, you can sell your crypto for a different crypto, you can use a proof-of-burn system that destroys a different crypto to earn a unit of yours, you can grandfather in Bitcoin ownership and give one Altcoin for each person with 1 Bitcoin, or you can just give it out to people (target peer leaders).
Watch out for pump and dump schemes:
- Begin with a target that has low value Altcoin
- Buy up a bunch of the currency
- Launch a marketing campaign to change public perception
- Once price rises, sell out coins
- End the marketing campaign and let the Altcoin got back to a low value
We have looked at a few ways to launch an Altcoin. In one situation, we give Altcoins to everyone with Bitcoins, on the other end of the spectrum, we give an Altcoin to anyone who destroys their Bitcoin. This has the effect of removing that Bitcoin from circulation, it would be better if we instead placed the Bitcoin in an escrow, and at some later date we could trade-back the Altcoin for our original Bitcoin. This would be called Bilateral Pegging.
This isn’t possible because the Bitcoin block chain doesn’t hold info about other coins, but this could be changed in a Side Chain proposal. Rather than hold the data for Altcoins in the Bitcoin block chain, we can use SPV proofs. SPV allows a thin client to process block chain information about a transaction without downloading and processing the entire block chain. Rather than inspecting full block chain, you would only need to evaluate the block headers.
The Future of Bitcoin
The Block Chain as a Vehicle for Decentralization
By using private and public keys in the block chain, we can create ownership of a real-world asset. Then, we can also transfer ownership easily through signed transactions.
If we take the example of selling a car, we can create a larger transaction that combines the payment transfer with the ownership transfer.
We can extrapolate this idea to hold all records in block chain, which then hold the ledger of vehicle ownership along with payment details.
Levels of Decentralization
There are 4 levels of decentralization:
- Single mandatory intermediary – Think the DMV, to sell a car you must get them to authorize the transaction.
- Multiple competing intermediaries – Think auto-emissions, there are many different places to take your car for an emissions test
- Threshold of intermediaries – Multiple intermediaries must agree with eachother
- No intermediary – Unmanaged by a central authority.
Routes to Block Chain Integration
4 different avenues to get into block chain
- Deploy Altcoin on Bitcoin Block Chain – this is easy to deploy but your new features might not be represented adequately
- Embedding – Use the Bitcoin block chain, but encode real world information onto the block chain. You can use the OP code fore 30 arbitrary characters, send to unspendable address, or use multi signatures to embed complex representation into block chain. This will likely result in unwanted transactions recorded in the block chain.
- Side Chains – Merge-mined alternative chain. It is great for a Bitcoin test bed. This method avoids polluting the block chain
- Altcoin – This is creating a separate, alternative block chain. This lets you expand with features till your heart’s content, however you have to build your own system and ensure security, which you can just leave to Bitcoin using the other methods.
What Can We Decentralize?
Concensus technologies allow the block chain to be used as a current state in purely digital systems, like domain names (think Namecoin). Storage technologies and pay-for-proof schemes can also be set up in decentralized way. Finally, we can generate random numbers and perform lotteries in a purely decentralized way using the block chain.
Can Be Represented Digitally
While not purely digital, a number of concepts can be represented digitally without a centralized authority. Real-world currencies can be modeled. Stocks and other assets can also be represented and managed in a decentralized system. Not only can the block chain record transactions, but we can also use atomicity to link the payments for the asset to the issuance of the asset, making sure that you get what you pay for.
Property ownership can be moved to a decentralized system through the use of smart property systems (think a car that looks to the block chain for ownership information) and atomic exchange parameters.
Complex contracts like crowdfunding models and even financial derivatives can be managed completely using block chain technologies in a decentralized system. Derivatives have an underlying asset that is traded on block chain. The derivative price depends on the price of the underlying asset. Can write rules to receive payout if asset price fluctuates in a way that you predict.
It is important to note that your payout rules will be based on the changes in price. Therefore, your script needs to have a trusted source of price changes in order to accurately receive your payouts. This secure source is called a data feed.
Markets and Auctions
We can perform most functions of online markets (Craigslsit) or auctions (Ebay), but we still need to match buyers to sellers in a decentralized fashion. The concept is to create a partial transaction that accurately describes exactly what you are seeking to sell and at what price. This partial transaction is broadcast to the network, but not added to block chain.
A potential buyer can then examine the partial transaction and ensure that it represents something they would like to purchase. If so, they can complete the transaction, sign it with their keys, and broadcast the transaction to the block chain, thus transferring ownership of the asset in question.
Auctions would be performed in a similar fashion, expect the partial transaction generated by the seller couldn’t be completed by any one buyer. Instead, they have to sign the transaction, then return it to seller, who also has to sign off for the transaction to be added to block chain. Thus, the seller can acquire different bids and choose the one they like.
A method to assert real-world facts into the block chain. Arbiters would control the inflow of information, with the block chain and consensus then making the final decision. Arbiters are still a form of decentralization, but by having multiple you dilute their power and all their reputation to decide if they are trusted or not.
There might be a large incentive for the arbiters to lie. To prevent this, you can have a threshold of arbiters which requires a certain number of arbiters to agree upon an outcome.
In this concept, cloud scripts would be able to enter into contracts with real people. They use data feeds to understand the state of the world. For semi-autonomous agents, there would be a voting population that can direct the decisions made by the agent.
Because there is no way to tie transactions together between real-world fiat currencies and Bitcoin, in order for Alice to buy Carol’s Bitcoin using USD, Carol would have to send the Bitcoin and hope Alice sends a check. Or Alice has to send the check and hope Carol gives her the coins, there is no atomicity or enforcement mechanism.
Of course, you can go through a trusted intermediary (like Bob, a trusted mutual friend), who holds both payments and disburses them once both are complete. There can be two separate transactions, so Alice and Carol never have to transact with eachother. This idea can be extended to a P2P network where nodes connect through trust relationships.
When Decentralization is a Good Idea
A cypherpunk goal is to replace large, human institutions with technological alternatives. We want alternative legal, social and financial systems that don’t depend on identity. One thing we need to think about as we decentralize is security.
Security is complex and involves 3 different mechanisms:
- Preventative – Stop it before it happens
- Detective – Realize that something happened
- Corrective controls – Reverse whatever happened and possibly take punitive measures.
In the real-world, law enforcement relies heavily on the last two and leaves the first mechanism up to your discretion. For decentralization, preventative measures are the most effective.
In Bitcoin, security is even more difficult because we add in key security, which is critical and if your keys are compromised your Bitcoin is also compromised. The software is also likely to have bugs, making the software attack vector the most profitable for Bitcoin pirates.
You can, of course, have fall-back measures to enhance security, but these inevitably become intermediaries and your system becomes less decentralized.
Dispute Mediation is also complex
The judicial system has evolved for hundreds of years and is very good (depending on your perspective) at administering dispute resolution. Technology isn’t good at solving what is a fundamentally human issue. In fact, technology can make dispute mediation more difficult to achieve.
Crypto and the State
The State will inevitably come about as a method to scale up society past small groups while still retaining the trust community members have between one another. We inherently don’t trust eachother, but we trust in law enforcement (to an extent) and we trust that we have recourse should we be harmed by an adversary.
Curiously, these benefits are also provided by cryptographic communications. The state and cryto deliver a similar benefit, even though different technological means are used. Crypto and the State working together is the real goal, as dismantlement the state is not an option.
We want compelling use-cases for decentralization. If there are abuses of power or inefficient regulation, then crypto can step in and act as a hedge against abusive governments. How can they integrate instead of replace existing systems? How can legal and regulatory practices be adopted by crypto? These questions will direct the future or crypto.