Revision as of 17:20, 30 November 2022 by Student27MA279F22 (Talk | contribs)

What is Hashing?

Before discussing cryptocurrency it's important to understand what hashing is. Hashing is an algorithm that takes an input of arbitrary length and produces an output of fixed length. In order for a hashing algorithm to be cryptographically secure, it must have the following properties:

  • Non-reversibility: a hashing algorithm must be a one-way operation. In otherwords, given an output, it's not realistically feasible to find the input that produced it.
    • For SHA-256, this property arises from the heavy use of the XOR operation (i.e. for $ 1100\ \oplus\ 1010=0110 $, there's 16 combinations of the LHS and RHS that equal 0110). To reverse engineer the input from a hash would require an incomprehensible number of guesses if you know nothing of the input
  • Diffusion: a change in just a single character should have drastic changes to the output
  • Determinism: the same input must always produce the same output
  • Collision resistance: finding two inputs that produce the same output should be incredibly difficult
  • Non-predictable: there should be no trend which allows you to predict portions of the output based on the input and vice versa

The most popular hashing algorithm is known as SHA-2(56) and is what powers Bitcoin. The algorithm runs in two phases


Phase 1: Preprocessing

  1. Convert the input of length $ L $ to a binary string and append a '1' bit to the end
  2. Append $ K $ '0' bits such that $ L+1+K+64\text{ mod }512 = 0 $
  3. Replace the 64 bits following $ K $ with a binary representation of $ L $
    • For example, if $ L=312 $, the remaining 64 bits would be $ 00000000\ 00000000\ ...\ 00000001\ 00111000 $

Phase 2: Compression

Let:
$ h_0...h_7 $ be the first 32 bits of the fractional part of the square roots of the first 8 primes (2...19)
$ K[0..63] $ be the first 32 bits of the fractional part of the cube roots of the first 64 primes (2...311)
$ \oplus $ be the notation assigned to the XOR operator
$ \sigma^0=(\text{ROTR}^7(W[i-15]))\ \oplus\ (\text{ROTR}^{18}(W[i-15]))\ \oplus\ (\text{SHR}^3(W[i-15])) $
$ \sigma^1=(\text{ROTR}^{17}(W[i-2]))\ \oplus\ (\text{ROTR}^{19}(W[i-2]))\ \oplus\ (\text{SHR}^{10}(W[i-2])) $
where
$ \text{ROTR}^n(x)= $circular right rotation of $ x $ by $ n $ bits
$ \text{SHR}^n(x)= $circular right shift of $ x $ by $ n $ bits

The binary input from the previous phase is split into chunks of 512. The following steps are performed on each chunk:

  1. An array $ W $ of 32-bit words with 64 entries is created. The current chunk is copied into the first 16 words
  2. For the remaining 48 entries, $ \sigma^0,\sigma^1 $ are computed as given above and the $ i^\text{th} $ entry becomes $ W^i=W^{i-16}+\sigma^0+W^{i-7}+\sigma^1 $
  3. Initialize $ a..h $ to $ h0..h7 $
  4. For i in range [0..63] $ \begin{align*} S_1&=(\text{ROTR}^6(e))\ \oplus\ (\text{ROTR}^{11}(e))\ \oplus\ (\text{ROTR}^{25}(e))\\ ch&=(e\land\ f)\ \oplus\ (\neg e\land g)\\ T_1&=h+S_1+ch+k[i]+w[i]\\ S_0&=(\text{ROTR}^2(a))\ \oplus\ (\text{ROTR}^{13}(a)\ \oplus\ (\text{ROTR}^{22}(a))\\ maj&=(a\land\ b)\ \oplus\ (a\land c)\ \oplus\ (b\land c)\\ T_2&=S_0+maj\\ h &= g\\ g &= f\\ f&=e\\ e&=d+T_1\\ d&=c\\ c&=b\\ b&=a\\ a&=T_1+T_2 \end{align*} $

  5. $ \begin{align*} h_0=h_0+a\\ h_1=h_1+b\\ ...\\ h_7=h_7+h \end{align*} $
  6. $ \text{hash}=h_0\text{ append }h_1\text{ append }...\text{ append }h_7 $

What is Cryptocurrency?

What is cryptocurrency? Cryptocurrency is a digital currency in which transactions are verified and records maintained by a decentralized system. Everyone knew the cryptocurrency on TV or the Internet because of the price of bitcoin. Some people think that this is a huge scam. They might be right because there are a lot of cryptocurrency frauds, and they caused various social problems. However, most people did not know exactly what cryptocurrency is and how it works. People only knew about the benefits and risks of cryptocurrency. Therefore, this project will show what cryptocurrency is, how it works, what methods are used, and how it impacts the society.

Why do people want to make and use cryptocurrency? The main reason was that traditional finance had some chronic problems. For example, money is centralized, so only a few companies held people’s money. You cannot get any access to the system if you are poor or have low credits. In addition, some companies or governments can know and track the movement of your money. You cannot use traditional finance if the bank is closed, and it took a lot of time to transfer money. These chronic problems of traditional finance made a cryptocurrency.


There are three characteristics: decentralized, secure and private, and speed. First, Decentralizing is the key point of cryptocurrency. Unlike traditional finance, everyone can join the system of cryptocurrency, and the system is run by consensus algorithms. Therefore, there is no owner of the currency, also it is impossible to manage the system by one person or company. This characteristic guaranteed transparency and value-neutral. Second, it is very secure and private. Unlike traditional finance, people can access without names, so every transaction is anonymous. It can be used in a crime, but it can be used in a good way too. Third, it is much faster than traditional finance. Traditional systems is actually too slow, and it took a couple of days to finish some transactions. However, cryptocurrency can finish these transactions in a few minutes.



Consensus Algorithms

Consensus Algorithms are the basic underpinning of cryptocurrency. They allow users to agree on who owns the currency without a centralized authority or physical token dictating ownership.

The consensus algorithms used by the two largest cryptocurrencies (Bitcoin and Ethereum) are Proof of Work and Proof of Stake. Here we will detail how they work, why they ensure cryptocurrencies can be secure, and how they impact the environment.

Proof of Work

The essence of Proof of Work involves users, known as miners, competing to solve cryptographic puzzles in order to verify ledgers of transactions. The user who solves the puzzle first is awarded newly minted Bitcoin.

The puzzles themselves involve taking the ledgers with a number appended to the end and applying a hashing algorithm, such as SHA256. While hashing the ledgers itself is simple, in order for the miner to win the currency, the resulting hash must start with a predetermined number of zeros. Once a miner finds a hash matching this criteria, the other miners on the network verify its correctness and if accurate, they discoverer is awarded the currency and the network moves on to the next block.

Mining Difficulty

As stated previously, puzzles are prefixed with leading zeros. The number of leading zeros is variables and changes in accordance to the number of miners on the network. The reasoning behind this is to prevent inflation of the currency. As more miners join the network, the difficulty of computing a correct hash should increase so the rate of coins entering circulation remains constant.

In the case of Bitcoin, adjustments are computed by comparing the time it should take to verify 2,016 blocks of transactions (20,160 minutes) to the time it took to find the last 2,016 blocks to create a difficulty modifier. In other words:

$ D=\frac{\text{current time}}{\text{target time}} $

Once a modifier is computed, a value indicating how many hash-functions are needed to be solved is computed as

$ \frac{D\cdot2^{32}}{600} $

Environmental Impact

The "work" portion in proof of work is the billions of hashing operations that miners are computing to find the winning number. As more miners join the network, not only is there increased energy consumption for the additional computers, but every computer is also doing more work as the difficulty increases. This essentially creates a feedback loop. Furthermore, he most popular hardware used by miners to rapidly perform these hashing operations are known as Graphical Processing Units, or GPUs for short. While these specialized processors are intended for graphical computations, their significantly lower cost compared to Application Specific Integrated Circuits (ASICs) makes them the ideal choice for miners who want to quickly receive a return of investment. Unfortunately, compared to ASICs, GPUs consume substantially more energy to operate. The most popular mining GPU, the Nvidia RTX 3090, consumes 450W when pushed to its limits.

In Feb 2017, the energy consumed by Bitcoin was estimated to be 10 TWh. Nearing the end of 2022, Bitcoin was estimated to consume as much as 132 TWh. That's more energy then what all of Denmark, Chile, and Finland, and the Netherlands independently consume.

Security of Proof of Work Algorithms

The largest threat to a decentralized network is malicious actors falisfying information to furthur their own interests. One of the benefits of Proof of Work is that in order to falsify information on the Blockchain, you'd need have control of 51% of the total computational power on the entire network. In the early days when the blockchain was small, this feat could potentially be achieved. Today, the sheer number of miners and the inconceivable size of the blockchain makes this an impossible feat to acomplish. Due to this mechanism, Proof of Work remains as the most secure consensus algorithm.

Proof of Stake

Proof of Stake is a relatively new algorithm designed to reduce the energy usage of mining cryptocurrency. It is currently used by Ethereum, the current second-biggest cryptocurrency. Whereas in a proof of work model, users expend energy to prove they have capital at risk, under proof of stake users just stake their capital directly in the form of the cryptocurrency that is being mined. This earns them the privilege of validating blocks of transactions propagated by other users and occasionally propagating their own block (and receiving the transaction fees for it). In order to encourage miners to post accurate transactions, the cryptocurrency they staked will be deleted if they behave dishonestly (by submitting false transactions) or lazily (by not posting or validating blocks when called upon to do so).

When a user mines Ethereum, they must first make a deposit (called "stake") of 32 ETH to join the validator pool.If a user doesn't have 32 ETH (currently valued at around $50,000), they can join a staking pool, which allows several users to combine their ETH to act as a single validator. Once a user is in the validator pool, they may recieve new proposed blocks of transactions from other validators on the network, and they are expected to validate these blocks as accurate or inaccurate. They may also be randomly selected to propose a block of transactions.

Now you might ask, what forces validators to actually submit accurate blocks of transactions? The answer is that validators must reach a 2/3 majority vote on a block of transactions being legitimate for it to be finalized. If a validator were to submit a false block, they would have no way to get other validators to agree to validate it. This turns the search for a valid block into a type of Keynesian beauty contest. The Keynesian beauty contest was a method for determining consensus first proposed by economist John Maynard Keynes. The idea is, in a traditional beauty contest, you tell the judges to vote for the most beautiful candidate, and they all vote their personal opinion. Keynes proposed instead asking the judges to vote for the candidate they believed the most other judges would select as most beautiful. This incentivizes the judges to vote for the candidate who best meets conventional standards of beauty (since, by definition, the conventional standards of beauty are those held by most people). In a similar way, validators in a proof of stake system are incentivized to vote for the truth instead of their personal desires (giving all the money to themselves), since the truth is the option everyone can agree on.

$ \begin{array}{c:cc} & Honestly & Dishonestly \\ \hdashline Honestly & 1,1 & 0,2 \\ Dishonestly & 0,1 & 2,2 \\ \end {array} $

Here is an example of a payoff matrix that describes the situation a validator might face when verifying transactions. Here the left column describes the validator's potential actions, and the top row describes the (aggregate) actions of the rest of the validators. Meanwhile, the left number in each ordered pair describes the validator's payoff, and the right number describes the payoff for the rest of the validators. We can read this as follows:

  • If every validator behaves honestly, they all receive a modest payout of their normal transaction fees. (top left)
  • If every validator except one behaves honestly, they all receive a payout except for the dishonest validator. (bottom left)
  • If every validator behaves dishonestly, they can all steal ETH and receive a greater payout. (bottom right)
  • If every validator but one behaves dishonestly, they can they can all steal ETH and receive a greater payout. (top right)

As you can see, every validator would prefer that they all act dishonestly and steal the ETH for themselves. However, each validator only gets a payout when acting dishonestly if most other validators do so as well. Since it is very hard to organize so many validators acting dishonestly at once, each validator would prefer the smaller but guaranteed payoff from acting honestly.

Environmental Impact

Proof of stake barely requires any processing power to mine cryptocurrency. This is because users are staking a separate asset (their ETH), so there is no need to demand users spend high amounts of computing power (careful readers will note that this is essentially "staking" computing power against the future reward of mined cryptocurrency) on mining. As a result, proof of stake mining can be done on an ordinary computer, so the same or better security can be achieved at a tiny fraction of the environmental impact.

Security of Proof of Stake Algorithms

Proof of stake offers several mechanisms to protect from attacks. The most common methods involve penalizing validators who appear to be attacking the system. Validators are penalized (through the deletion of their staked ETH) if they are in the minority preventing a block from being finalized. This prevents would-be attackers from freezing transactions by refusing to validate legitimate blocks. The penalty also increases if multiple users are voting for the same minority block, which makes 51%-style attacks much riskier as the attacker has to risk deleting a lot of ETH if the attack doesn't succeed. It is also easier for the community of legitimate users to mount a defense against a coordinated attack by staking more ETH to validate themselves - it's easier to stake more ETH than it is to buy a new mining rig. Validators who refuse to vote for a significant period of time can also eventualy be ejected from the network, ensuring that attacks are difficult to coordinate with only a limited amount of time.

In an extreme case, an attacker might be able to overcome the above challenges and control over 51% of the mining power on the network. Notably, this is much easier than under a proof of work model (though still very difficult), since a prospective attacker merely needs to have as much ETH as all other miners combined (very hard) instead of needing as much computing power as all other miners combined (impossible). In that case, they would be able to vote to give all the ETH to themselves, and other users voting against that would be penalized (for being in the minority). But there is another defense against this type of attack. Users could simply fork the blockchain, essentially splitting ETH into 2 currencies - the "real" ETH, which would have the legitimate set of transactions and contain everyone (who got the memo to join) but the attacker, and the "compromised" ETH, which would be entirely controlled by the attacker. This would not cause any problems, as everyone who uses ETH could just refuse to accept transactions on the compromised blockchain. In effect, the attacker would control a near-limitless supply of worthless money, while the rest of the ETH community could carry on as if nothing had happened.

Tradeoffs of Proof of Work vs. Proof of Stake

Different Environmental Impacts

A few years ago, government tried to regulate the mining of cryptocurrency. The biggest reason was the impact on environment. With proof of work method, miners spend a lot of energy to mine the cryptocurrency, and this usage directly leads to increasing of CO2. For example, bitcoin consumes an estimated 150 terawatt per hours, and it is more than the usage of Argentina. From this perspective, proof of stake is much better way than proof of work. For example, ETH pow consumes 78 TWH/year but ETH pos only consumes 0.0026 TWH/year. In other words, pow spend 30000 times more than pos.

Ethical Issues

Environment

The high energy consumption of Bitcoin and other proof-of-work cryptocurrencies raise severe ethical concerns. Bitcoin transactions consume approximately as much energy as a wealthy, moderately-large country each year, and climate change is a serious problem [citation needed]. These high energy costs have caused cryptocurrency mining to come under a lot of scrutiny and led to it being banned outright in China. However, it's not all doom and gloom on this end. Ethereum's switch from proof of work to proof of stake led to an over 99% reduction in energy used per transaction. Hopefully, more cryptocurrencies can follow suit and reduce their energy consumption as well.

Crime

Another problem with cryptocurrencies is their potential for use in crime. Since cryptocurrencies can be difficult to trace and transactions are irreversible, they have become a favored means for ransomware attackers and other online criminals to demand payment. They also allow international criminal organizations to move money across borders much more easily. A prime example of this is the 2021 ransomware attack on Colonial Pipeline, which shut down gasoline supplies in a large area of the US for several days until the attackers were paid approximately $9 million worth of Bitcoin. (The FBI later managed to recover about half of the ransom through undisclosed means). However, cryptocurrency is still a small (though growing) portion of crime on a global scale - the value of just money laundering in the US is about equal to the total value of all cryptocurrency in the world.

Circumventing Opression

However, not all of the impacts of cryptocurrrency are negative. The fact that cryptocurrency transactions can't be prevented or traced means that people living under opressive regimes can use them to prevent opression. For example, cryptocurrency is commonly used in remittances, the sending of money by immigrants to family members in poorer countries. A person who recently immigrated from an impoverished country like Venezuela or the Phillipines might make much more money in the US than they did in their home country, and they might want to send some of it abroad to help family members still living in poverty. However, many such countries have high taxes or prohibitions on remittances. Cryptocurrency allows for remittances to be transferred overseas without any impediments, allowing people to help overseas family members more easily.

Another example of the use of cryptocurrencies in circumventing opression is the avoidance of central bank digital currencies (CBDCs). For example, China recently released its 'digital Yuan', which allows people to store government-controlled currency online. Since it is controlled by the Chinese government, there are concerns that people or businesses who attract negative attention from the government could be essentially blacklisted from the economy by the government banning them from spending or receiving money. Furthermore, the Chinese government has experimented with an expiration date on the digital Yuan, essentially deleting people's money if it is not used by a certain time. Cryptocurrency allows people to avoid these issues (maybe another reason it's been banned in China?).

Sources

$ \sqrt{2} $ How to type math https://katex.org/docs/supported.html

Sources

https://ethereum.org/en/developers/docs/consensus-mechanisms/pow/
Information on how proof of work works.

https://ethereum.org/en/developers/docs/consensus-mechanisms/pow/mining/
Information on why mining is important for cryptocurrencies.

https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/
Information on how proof of stake works.

https://www.coinbase.com/learn/crypto-basics/what-is-proof-of-work-or-proof-of-stake
Information on the difference between PoW & PoS

https://bitcoin.org/bitcoin.pdf
Bitcoin whitepaper that started it all
https://time.com/nextadvisor/investing/cryptocurrency/proof-of-work-vs-proof-of-stake/

https://www.nytimes.com/interactive/2021/09/03/climate/bitcoin-carbon-footprint-electricity.html
Energy expenditure of pos and pow https://ethereum.org/en/energy-consumption/#:~:text=Ethereum%20is%20a%20green%20blockchain,across%20the%20entire%20global%20network

Alumni Liaison

To all math majors: "Mathematics is a wonderfully rich subject."

Dr. Paul Garrett