Crypto Stands for Cryptography
The whales that every cryptocurrency rests on (or takes off from) are cryptographic algorithms. Bitcoin has just two - hash function and digital signature. It may comes as a surprise, but encryption (or concealment of information) is not even mentioned in the original article of Satoshi Nakamoto. (To be clear, the private keys of users are stored encrypted, but that is just a function of the specific wallet, not the protocol, described in the original whitepaper).
Let’s take a closer look at these two whales:
Hash function is a function that can be used to map data of arbitrary (but finite) size to data of a fixed size. For instance, a string
I am selling a GTX 1080 GPU
may turn into
12e6fa4e89a97ea2
by way of various mathematical operations on that string’s source bytes. Hash functions have the remarkable property of the so-called “avalanche” effect: if an input is changed slightly, the output changes significantly. Thus, for instance,
I am selling a GTX 1081 GPU
may become
0a9eeee64b55d39a
Consequently, hash functions can be considered “unique fingerprints” for data, which makes them irreplaceable for keeping data in the blockchain (essentially, a chain of hashes) immutable and transactions irreversible.Digital signature is a mathematical scheme that Alice can use to prove authorship (or possession) of something and Bob can use to check that authorship. Essentially it is similar to a regular handwritten signature on a piece of paper. Cryptocurrencies use digital signatures in two ways: firstly, they guarantee authorship of a certain transfer, secondly, they prevent a malicious person from tampering with a transaction (swapping the sender, for instance), since the original signature would not be verifiable anymore. This second property is facilitated by using digital signatures on the transaction hash.
By and large, blockchain operation does not require any other “whales”: the signature proves ownership of the coins and other digital assets, and hashing guarantees data integrity and immutability. But there are a great variety of digital signature and hashing algorithms! In addition to this, certain algorithms can be implemented on a broad range of mathematical objects. And last but not least, mathematical operations can be executed differently: for example, one can count 2⁸ as 2₀*2₁*...*2₇ (seven multiplications) or as (((2²)²)²) (three squares).
In this regard Bytecoin stands apart from most cryptocurrencies. It is not just about the fundamentally different kind of signatures (ring signatures are used to prove authorship in an anonymous fashion, without pointing to the author), but about a distinct mathematical apparatus (Twisted Edwards curves) and a distinct software library for basic cryptographic operations, written by well-known cryptographer D.J. Bernstein.
Digital Signatures
Hash functions will be described in greater detail in the next article. Before going into detail about ring signatures in Bytecoin let’s look at mainstream digital signature algorithms existing now.
A digital signature is a public key cryptosystem. In such a system Alice has the private key x (known only to her) as well as public key P = Bˣ (known to everyone). B is the public parameter of a cryptosystem, that is chosen beforehand and is known to everyone as well. Since cryptography involved in digital signatures uses very large numbers (1000...00 - 77 zeroes and more), it is almost impossible to bruteforce a private key, knowing only P and B. In addition there is no effective algorithm for searching the so-called discrete logarithm (x is a logarithm of P to base B) - at least it is considered to be that way now.
Alice can use the private key to create a signature and everyone can use the public key to verify it. The signature proves that Alice, and only Alice, has created it. Hence this condition is true as long as the private key is kept secret.
ElGamal
The ElGamal scheme of 1985 (Taher Elgamal) is the forefather of modern digital signature algorithms. In its formula base
Bʰ⁽ᴹ⁾ = Pᴿ * Rˢ, where
h(M) - hash of the message being signed,
R = Bᵏ,
k - random number picked by Alice.
The pair of numbers (R, s) constitute the signature that Alice makes for public message verification.
In order for this formula to be true, Alice needs to find the corresponding value s. It is not difficult, since she knows all other elements of the equation. We can substitute the values to make sure:
Bʰ⁽ᴹ⁾ = Pᴿ * Rˢ
Bʰ⁽ᴹ⁾ = (Bˣ)ᴿ * (Bᵏ)ˢ
Bʰ⁽ᴹ⁾ = B⁽ˣᴿ⁾ * B⁽ᵏˢ⁾
Bʰ⁽ᴹ⁾ = B⁽ˣᴿ⁺ᵏˢ⁾
h(M) = xR+ks
s = (h(M)-xR)/k
We can see that value s depends on private key x and message M, so:
a) this signature would not work for different message M₂;
b) any attempts to forge the signature without the key x are equal to bruteforcing.
Schnorr
The ElGamal scheme has seen some improvements after 1985 (we will omit them for conciseness). In 1990 Claus Schnorr published his version of a digital signature, which is based on equation Bˢ = R*Pʰ⁽ᴿᴹ⁾. In order to create a signature (R,s), Alice needs to calculate s = x*h(R,M) – k.
As one can see the calculations have got simpler (for example, there is no need to divide large numbers). In addition, value s can be noticeably smaller without affecting the cryptographic strength of the algorithm, so the size of the signature decreases (formally speaking, value s is contained in a small subset of a larger set of numbers, but the intruder still has to deal with the bigger set when bruteforcing). Among other things, the requirements to hash function h become less strict: it does not have to be collision-resistant - a property that is difficult to prove in practice.
Another important property of a Schnorr signature is the aggregate signature. If you have signatures (R₁,s₁) and (R₂,s₂) for message M, then you can turn them into one signature (R₃,s₃) = (R₁*R₂, s₁+s₂). Even if you have 10 signatures, they are turned into one, which speeds up the verification by 10 times. This property is very useful in cryptocurrencies, when transactions often contain multiple signatures of the same message (the transaction itself).
EC(DSA)
Finally, 1991 has seen the appearance of the DSA (Digital Signature Algorithm), which has been adopted as NIST standard a few years later. It is as well based on the ElGamal algorithm (the signature is (R,s) as before), yet was technologically inferior to it:
R = Bʰ⁽ᴹ⁾/ˢ * P⁽ᴿ/ˢ⁾
Particularly, the division operations were still needed and the hash function had to be collision-resistant. This could be due to the fact that the Schnorr signature was covered by patent until 2008 or that the NSA got involved.
One way or another, the DSA is used in the majority of software these days, in particular, Bitcoin and its forks (to be exact, ECDSA, DSA’s counterpart on elliptic curves). It can’t be said that this signature is weak, but there are cases of improper use of DSA, which caused catastrophic (in terms of cryptography) consequences.
For instance, number k, which Alice picks, should by no accident be random: if it is not, anyone can find the secret key by the signature:
R = Bʰ⁽ᴹ⁾/ˢ * P⁽ᴿ/ˢ⁾
Bᵏ = Bʰ⁽ᴹ⁾/ˢ * Bˣᴿ/ˢ
Bᵏ = B⁽ʰ⁽ᴹ⁾/ˢ ⁺ ˣᴿ/ˢ⁾
k = h(M)/s + xR/s
x = (ks - h(M))/R
Even if the same value k is used in two different signatures (R,s₁) и (R,s₂), the key can be found:
R = B⁽ʰ⁽ᴹ¹⁾/ˢ¹⁾ * B⁽ˣᴿ/ˢ¹⁾
R = B⁽ʰ⁽ᴹ²⁾/ˢ²⁾ * B⁽ˣᴿ/ˢ²⁾
h(M₁)/s₁ + x*R/s₁ = h(M₂)/s₂ + x*R/s₂
x*(R/s₁ – R/s₂) = h(M₂)/s₂ - h(M₁)/s₁
x = (h(M₂)/s₂ - h(M₁)/s₁) / (R/s₁ – R/s₂)
It is with this method that PlayStaytion 3’s key was hacked in 2010. This is barely a hack, since Sony published the data that was used to find the key by applying the algorithm incorrectly.
Ring Signature
All digital signature algorithms mentioned so far have one common property - they explicitly point out the author of the signature (via their public key). Bytecoin and other CryptoNote-based currencies use ring signature in transactions, which can be validated by not one, but multiple public keys, hence not pointing to the author.
We will not go into great detail about the ring signature algorithm, you can do so here. It is worth noting, that it is based on the Schnorr formula Bˢᶦ = Rᵢ*Pʰ⁽ᴿᶦ,ᴹ⁾. There is not one, but 2N such statements (where N is the number of public keys in the ring). The signature includes a set of 2N pairs (Rᵢ,sᵢ), and the hash function is applied to all these elements at once. Thus it can be stated that CryptoNote one-time ring signatures are a “ring extension” to the Schnorr signature with all its advantages.
It is necessary to point out that we have shown equations for “regular numbers”, but at the moment they are based on points of elliptic curves. All of the mentioned algorithms have implementations in the elliptic world, used in action. In the next article we will talk about why elliptic curves are better than “regular numbers” and why some curves are better than others (here is where the cryptocurrencies differ).
- The Bytecoin Development Team