No reason to be afraid of modern cryptography for consensus

Nearly all cryptocurrency projects use asymmetric cryptography for signing transactions. All transactions are put into a block and the protocol must come to a consensus that decides whether the block will be eventually added to blockchain or not. The first consensus was Bitcoin PoW and currently PoS is on the rise. Both PoW and PoS consensus use cryptographic tools. However, many people believe that only the cryptographic tool used in PoW is a valid solution and any different approach cannot work within PoS. We would like to show you that there is no strong reason to believe that.

We do not want to explain to you how exactly cryptographic tools work or how they are used to solve a particular problem in a given project. We would like to highlight the basic principles of cryptography. You should understand why cryptography is secure and under which conditions. After that, we will show you how modern cryptography tools Verifiable Random Function and Key Evolving Signature can be used in Ouroboros PoS consensus.

Nevertheless, we have recently explained the basics of asymmetric cryptography and hashing for wallet users. It can help you to understand the basics:

https://medium.com/@Cardanians_io/cryptography-for-cardano-wallet-users-6b43d989ee8b

Asymmetric cryptography

Asymmetric cryptography or public cryptography is an essential component of cryptocurrencies like Bitcoin and others. These cryptographic techniques ensure that the source of transactions is legitimate and that hackers can not steal users' funds. People sending transactions might not realize that since everything is done by a wallet. Under the hood, there is a pair of keys. A private key that must be kept secret and a public key that can be broadcasted out to the network.

Bitcoin uses Elliptic Curve Digital Signature Algorithm (ECDSA) to create a set of the private key and corresponding public key. The public key is then used with a hash function to create the public address that Bitcoin users use to send and receive funds. The private key is kept secret and is used to sign a digital transaction to make sure the origin of the transaction is legitimate.

Why cryptography works?

RSA (Rivest–Shamir–Adleman) is another asymmetric cryptographic algorithm. For our explanation, we use RSA since it is easy to understand the base concept. We do not want to explain to you how RSA works but mainly why it is secure. We simplify it as much as possible. If you would like to know how RSA works in more details you can check the link below. However, you do not need it to get the point of the article. 

https://hackernoon.com/how-does-rsa-work-f44918df914b

The RSA algorithm is based on the fact that finding the factors of a large composite number is difficult. When the integers are prime numbers, the problem is called prime factorization. Let’s have a look at the formula below. We will play a bit with it.

P * Q = N

Try to find prime numbers P and Q for the formula below. You can use a calculator (try to think about how you could solve it):

P * Q = 3127

If you try to find P and Q you can succeed but you will probably spend some time on it. However, if you pick prime number yourself the task is very simple. So if you pick P and Q you get the result nearly immediately.

53 * 59 = N

As you can see, you are able to find the solution N for the formula above easily.

The point and the reason why cryptography works is that there is no quick algorithm that would be able to find the solution for the first formula quickly in real-time. Imagine how difficult would be the task for much higher prime numbers.

We have simplified it a bit and RSA is more complicated than just that. What you should understand is that the only possible known method of how to find P and Q for given N is to make many attempts. How many? P and Q can be so big prime numbers that the latest desktop computer would spend years to find the solution.

If you want to break the RSA cryptography you would have to use the so-called brute force attack and try to find a private key from a known public key. The computer would have to make many attempts to find a solution for P * Q = 3127. However, this example is very simple. As we said, with much higher prime numbers (via factorization) the task is significantly complicated.

So, important is the length of the key. The higher prime numbers P and Q are the higher will be N. So more complicated the task will be for a computer trying to break the key.

Alternatively, you can try to find some algorithm that would solve the task without brute force. Just some algorithm that would lead to the result immediately. If you manage that you will probably get the Nobel price. It is not probably possible. At least the best mathematic brains in the world think so.

How big prime numbers are used in reality? Nowadays, the length of the key can be from 2048 to 3072 bits, so prime numbers are from 1024 to 2048 bits. The shortest prime number is 2 ⁵¹² what is a number with 150 numerals. However, it is too small a number nowadays for modern computers.

RSA claims that 2048-bit keys are sufficient until 2030. An RSA key length of 3072 bits should be used if security is required beyond 2030. If you would try to crack RSA on a desktop computer you would not be able to crack it during your life.

You can try RSA yourself here:

http://travistidwell.com/jsencrypt/demo/

RSA is used to encrypt a message (put it to an unreadable text) to be secure to send it via the internet or keep it stored on a hard-disc. You can later decrypt the message and get the original readable text. Public and private keys are used for encryption and decryption. You can see the picture below to see how it works but it is not necessary to understand that for the article. It does not matter whether you use RSA or ECDSA that is currently used in Bitcoin. Principles are similar.

Important is that encryption and decryption of a piece of text or signing Bitcoin transaction is a very fast process and you do not need much computing power or time.

Cryptography is secure due to the fact that it is a computationally demanding process to break it. It is basically nearly impossible. Let’s elaborate on it more.

Brute force attack

A brute force attack, also known as an exhaustive search, is a cryptographic hack that relies on guessing possible combinations of a given cipher until the correct combination is discovered. The longer the key, the more combinations that will need to be tested. A brute force attack can be time-consuming, difficult to perform if methods such as data obfuscation are used, and at times downright impossible.

An amount of time that is necessary to break a cipher is proportional to the size of the secret key. The maximum number of attempts is equal to 2^key size, where key size is the number of bits in the key. Nowadays, it is possible to break a cipher with around 60-bit long key, by using the brute-force attack in less than one day.

For breaking ciphers using brute-force attacks, very fast specially designed supercomputers are often used. They are owned by big research laboratories or government agencies, and they contain tens or hundreds of processors. Alternatively, large networks of thousands of regular computers working together may be used to break the same cipher. Cryptographic brute-force attacks are very scalable processes.

We can rely on cryptography as long as we believe that a single entity is not able to collect sufficient computer power to break a cipher. In other words, we believe that nobody is willing to perform a brute force attack to break a secret since it would be an expensive business.

How PoW works

The principle is used the other way round in PoW consensus. PoW can also be considered as the brute force attack. It is a special kind of driven brute force attack. The bitcoin protocol is able to measure available computation power and can calculate the difficulty of a task. Thus the protocol is able to set the difficulty of the cryptographic task in a way that the correct combination will be found approximately in 10 minutes. Sometimes it is only a minute, another time it could be for one hour. 10 minutes is the approximate time if we consider more attempts in a row.

PoW uses cryptographic tool SHA-256. A cryptographic hash (sometimes called ‘digest’ or ‘hash’) is a kind of ‘signature’ for a text or a data file. SHA-256 generates an almost-unique 256-bit (32-byte) signature for a text.

SHA-256 is a hash function that takes a piece of data as an input and produces the digest as an output. Always the same digest (output) for the same input. However, if you change a single character in the input the digest will be completely different. This property is crucial to the ‘proof of work’ algorithm involved in mining.

You can try SHA-256 here:

https://emn178.github.io/online-tools/sha256.html

To successfully mine a block, miners try to change the inputs in such a way that the resulting hash (output) starts with a certain number of zeroes (difficulty target). In other words, we need an output that will satisfy the protocol requirements.

A hashing function is very fast and produces the output within a second regardless of the size of the data. However, if the protocol sets the requirement of how the digest (output) should look like then it is necessary to change a special number over and over to change the whole input. The change of the input results in different outputs. A huge amount of attempts have to be done to find the required output.

PoW uses a hashing function, not public-key cryptography. Still, both tools can be considered as cryptographic tools using some mathematical algorithms that ensure security and can be possibly broken only via a brute force attack. PoW accommodates the task complexity in order to the current hash-rate could find the solution approximately in 10 minutes.

A brute force attack requires a lot of electricity and it is what Satoshi wanted to achieve for PoW. The task has to be so complex that a significant amount of electricity is consumed. That is one of the reasons why the Bitcoin time block is set to 10 minutes and not to a few seconds. It works fine. However, it prevents scalability since producing one block per 10 minutes is not sufficient for a global protocol.

Using the modern cryptographic tools in consensus

Cryptocurrencies are all about relying on cryptographic tools and they are always improved in time or new ones are invented. At the same time, available computation power is also increasing. From time to time, we have to start using longer keys. Block size in distributed networks is limited so we need to avoid using longer keys. Fortunately, some cryptographic tools got obsolete while some others have been invented or improved. So we need to change cryptographic tools every few years. Actually, Bitcoins is about to replace ECDSA by the Schnorr signature.

The question is why not use modern cryptography also within the consensus. We can achieve the same security as in the case of PoW and better scalability at the same time. There is really no strong reason to use the consensus utilizing a slow brute force attack to come to the network consensus if we can use modern cryptography.

Cardano Ouroboros PoS will use two cryptography tools: Key Evolving Signature (KES) and Verifiable Random Function (VRF). Thus, it can avoid using a brute force attack and can come to a consensus within 20 seconds and the environment that will be 50x more decentralized than Bitcoin. It is expected that will be 1000 pools in the Cardano network.

How KES and VRF is used in Ouroboros

The Ouroboros protocol is able to select a node with the right to produce a new block. There is no open competition as in PoW. Once the winner is selected the block creation costs almost nothing. This introduces a famous Nothing on stake problem, where a malicious agent can randomly try to create additional branches of the chain of any length just due to the fact that it costs nothing to create a block.

Ouroboros solves this problem by introducing slots and epochs. Every epoch has 21 600 slots. At the beginning of each epoch, a special multiparty randomness algorithm selects a set of slot-leaders for the whole epoch.

At this point, Verifiable Random Function comes into play. A Global Random Oracle produces new and fresh randomness for every epoch. The blockchain itself becomes its source of new randomness.

Randomly selected slot leaders will get the right to produce a block at a given slot. So for every epoch, there is a kind of fixed set of leaders. Thus, a random adversary cannot just come in and try to deceive the whole network. Slot-leaders are scheduled for the whole epoch and it can be easily verified that a block was produced by a scheduled slot-leader.

This mechanism protects the network from the Nothing at stake problem. An adversary cannot just randomly generate some random scam chain from the same genesis block since the set of slot-leaders would be the same from the start, and he would have to somehow corrupt the real existing nodes that were leaders at that time.

However, this introduces another vector attack. Nodes that have been selected as slot-leaders in the past could be hacked, or loose, or just sell their private keys. And if adversary would be able to collect enough such keys for the whole history of the chain he could be able to recreate it but with his transactions. In order to eliminate the possibility of a past slot-leaders to give away their keys, the Ouroboros Praos protocol decides to destroy them. So every slot-leader at the time of his slot has two key-sets: its private key as a node (like standard keys from a wallet) and a special block-signing key (derived from his private key by a special function). When his slot comes up the node produces a special key, then uses it to sign his block, and then destroys it. In the future, the adversary is not able to reproduce the same key, so he cannot get the right to recreate past slots.

At this point, Key Evolving Signature allows a node to generate a new secret key before broadcasting the new block. The public key remains the same but the secret key can be recreated. Thus a secret key can be used only once for the block signature.

You can read a great article by Carlos Lopes de Lara:

https://medium.com/@carloslopezdelara/whats-ouroboros-the-cardano-proof-of-stake-protocol-ad4b958e152e

Conclusion

Cryptocurrency projects are at the very beginning and they have to evolve to be globally scalable and able to achieve higher adoption. We can help to adopt if we have a scalable project. Bitcoin will never scale and it is naive to think that we can build everything around Bitcoin. We have to use the best available cryptography tools to deliver a scalable and still decentralized project.

Cardano will offer scalability, security, and decentralization at the highest possible level. Users relly on asymmetric cryptography and there is no reason to be scared of using Verifiable Random Function and Key Evolving Signature tools in consensus.

Source: No reason to be afraid of modern cryptography for consensus