Line 69: Line 69:
 
For i in range [0..63]
 
For i in range [0..63]
 
<math>S_1=(e\cdot\text{ROTR}^6(x))\ \oplus\ (e\cdot\text{ROTR}^{11}(x)\ \oplus\ (e \text{ROTR}^{25}(x))</math>
 
<math>S_1=(e\cdot\text{ROTR}^6(x))\ \oplus\ (e\cdot\text{ROTR}^{11}(x)\ \oplus\ (e \text{ROTR}^{25}(x))</math>
 +
<br>
 
<math>ch=(e\land\ f)\ \oplus\ (\neg e\land g)</math>
 
<math>ch=(e\land\ f)\ \oplus\ (\neg e\land g)</math>
 +
<br>
 
<math>T_1=h+S_1+ch+k[i]+w[i]</math>
 
<math>T_1=h+S_1+ch+k[i]+w[i]</math>
 +
<br>
 
<math>S_0=(a\cdot\text{ROTR}^2(x))\ \oplus\ (a\cdot\text{ROTR}^{13}(x)\ \oplus\ (a \text{ROTR}^{22}(x))</math>
 
<math>S_0=(a\cdot\text{ROTR}^2(x))\ \oplus\ (a\cdot\text{ROTR}^{13}(x)\ \oplus\ (a \text{ROTR}^{22}(x))</math>
 +
<br>
 
<math>maj=(a\land\ b)\ \oplus\ (a\land c)\ \oplus\ (b\land c)</math>
 
<math>maj=(a\land\ b)\ \oplus\ (a\land c)\ \oplus\ (b\land c)</math>
 +
<br>
 
<math>T_2=S_0+maj</math>
 
<math>T_2=S_0+maj</math>
 +
<br>
 
<math>h = g</math>
 
<math>h = g</math>
 +
<br>
 
<math>g = f</math>
 
<math>g = f</math>
 +
<br>
 
<math>f = e</math>
 
<math>f = e</math>
 +
<br>
 
<math>e = d + T_1</math>
 
<math>e = d + T_1</math>
 +
<br>
 
<math>d = c</math>
 
<math>d = c</math>
 +
<br>
 
<math>c = b</math>
 
<math>c = b</math>
 +
<br>
 
<math>b = a</math>
 
<math>b = a</math>
 +
<br>
 
<math>a = T_1+T_2</math>
 
<math>a = T_1+T_2</math>
 
</li>
 
</li>
 
<li>
 
<li>
 +
<math>h_0=h_0+a</math>
 +
<br>
 +
<math>h_1=h_1+b</math>
 +
<br>
 +
<math>...</math>
 +
<br>
 +
<math>h_7=h_7+h</math>
 +
</li>
 +
<li>
 +
\text{hash}=h_0\text{ append }h_1\text{ append }...\text{ append }h_7
 
</li>
 
</li>
 
</ol>
 
</ol>

Revision as of 10:41, 30 November 2022

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.
  • 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 $

Phase 2: Compression

Let:
$ h0...h7 $ 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)
$ \sigma^0=(W^{i-15}\text{ROTR}^7(x))\ \oplus\ (W^{i-15}\text{ROTR}^{18}(x))\ \oplus\ (W^{i-15}\text{SHR}^3(x)) $
$ \sigma^1=(W^{i-2}\text{ROTR}^{17}(x))\ \oplus\ (W^{i-2}\text{ROTR}^{19}(x))\ \oplus\ (W^{i-2}\text{SHR}^{10}(x)) $
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] $ S_1=(e\cdot\text{ROTR}^6(x))\ \oplus\ (e\cdot\text{ROTR}^{11}(x)\ \oplus\ (e \text{ROTR}^{25}(x)) $
    $ ch=(e\land\ f)\ \oplus\ (\neg e\land g) $
    $ T_1=h+S_1+ch+k[i]+w[i] $
    $ S_0=(a\cdot\text{ROTR}^2(x))\ \oplus\ (a\cdot\text{ROTR}^{13}(x)\ \oplus\ (a \text{ROTR}^{22}(x)) $
    $ 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 $
  5. $ h_0=h_0+a $
    $ h_1=h_1+b $
    $ ... $
    $ h_7=h_7+h $
  6. \text{hash}=h_0\text{ append }h_1\text{ append }...\text{ append }h_7

What is Cryptocurrency?

What is cryptocurrency? Everyone knew the cryptocurrency on TV or 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 benefits and risk of the cryptocurrency. Therefore, this project will show what cryptocurrency is, how it works and what methods are used.

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


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, to it. For those who don't know, a hashing algorithm is one of the most fundamental tools in cryptology. It takes an input string of any length and outputs a fixed length binary string. Furthermore, hashing algorithms have the following properties: The same input will always map to the same output, small changes in the input will have drastic changes in the output, and the security of the operation comes from the fact that you can't compute the inverse efficiently. In other words, given an output, you can't compute the input without checking every possible input until you get a match.

Going back to the cryptographic puzzles of Proof of Work, a ledger and number are combined and hashed. If the leading numbers of the binary output is zero, then the number hashed is a winning candidate. Once a winning number is found, it's broadcasted to the network and verified by other users.

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

Security Tradeoffs

Different Environmental Impacts

Be sure to have data here on Ethereum energy usage before and after the switch to proof of Stake.

Regulatory Issues

Conclusion

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

Prof. Math. Ohio State and Associate Dean
Outstanding Alumnus Purdue Math 2008

Jeff McNeal