In this section of the lesson, we will deal with the three main cryptographic primitives on which Bitcoin is based: the hash algorithms, the digital signature algorithm, the Merkle trees, and the hashcash algorithm.
Cryptographic hash function
A cryptographic hash function (or summary function) is an algorithm that takes as input any data of any length (the message ) and returns a string of fixed-length bits (the hash ).
The main characteristics of an ideal cryptographic hash function are the following:
Historically, hash functions have had diverse and varied applications in the context of cryptography, as they are used in digital signatures, in authentication algorithms, in fingerprinting systems or also to verify data integrity (a form of checksum).
Bitcoin defines the use of two types of hash algorithms: SHA-256 and RIPEMD-160.
SHA-256 (Secure Hash Algorithm). It is the main hash algorithm used in the Bitcoin protocol. It belongs to the family of SHA-2 hash functions designed by the NSA and accepted by NIST as the standard to be used in hashing algorithms by the North American administration, to replace its more immediate predecessor, SHA-1, of which they are known. several security vulnerabilities.
RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest). In addition to the previous hashing algorithm, Bitcoin uses another algorithm in cases where a shorter hash is required. It was created in 1996 and belongs to the RIPEMD family, of which there are algorithms with 128, 160, 256 and 320-bit output lengths. Then, Bitcoin uses the 160-bit version, like SHA-1, but with the main difference that RIPEMD was created under the auspices of an open research community as opposed to SHA-1, which was designed by the NSA.
It should be noted that Bitcoin always generates a hash result of applying a hash algorithm twice over any data, in order to increase the security against cryptanalysis.
Digital signature
Bitcoin uses a digital signature based on public key cryptography to authenticate data and correctly verify who is authorized to transfer coins. More specifically, Bitcoin defines the use of elliptic curve cryptography (ECC, Elliptic Curve Cryptography) using the algorithm ECDSA (Elliptic Curve Digital Signature Algorithm), DSA version based on the elliptic curve. The ECC algorithms are based on the complexity of solving certain mathematical problems in relation to the algebraic structure of the elliptic curves on finite fields. Generally, it is assumed that solving the discrete logarithm of an element of an elliptic curve chosen at random from a public base point is computationally unfeasible (ECDLP, Elliptic Curve Discrete Logarithm Problem).
With respect to public key algorithms based on the factorization of very large integers composed of two or more prime factors (such as RSA), the most relevant advantage of ECC is the reduction of key size for the same level of security. Thus, taking as reference a document of recommendations of the SEC (Standards for Efficient Cryptography) [ SECrecom ], for a certain level of security (in bits), only a key of twice the size of the security level required is needed. In Table 3.2.1 you can compare the size of the keys for ECDSA and for the key module for RSA / DSA to obtain equivalent security levels.
Bitcoin uses the elliptic curve specified in the secp256k1 recommendation of Table 3.2.1. Therefore, the signatures provide strength equivalent to 128 bits with only a key size of 256 bits. Using the classic versions of RSA / DSA, the size of the key should be 3,072 bits for this same level of security.
In this lesson it is out of the objectives to know the mathematical parameters, the way to generate the keys and how the signature is calculated and its validity are verified by the ECDSA signature algorithm. However, additional information about these processes can be obtained from these links: ECC and ECDSA.
Merkle trees
A Merkle tree or hash tree is a construction in the form of a tree of values where each interior node (nodes that do not end nodes) is the result of applying a hash function (be SHA-1, SHA-2, etc.) on the value of the child nodes until it reaches a root node called Merkle root of the tree. They can be binary (each inner node has two descendants, Figure 3.2.1) or not (each inner node has a certain number of descendants). The functionality of these algorithms is to enable the integrity and inclusion of all the data of large data structures to be verified efficiently and safely. In addition, they can be considered as a generalization of hash chains ( hash chains), where the verification of an element is proportional to the logarithm of the number of nodes of the tree, unlike the hash chains, where the cost is linear with the number of hashes contained in the chain.
Hashcash algorithm
Hashcash [ hashcashPaper ] is a proof-of-work system initially designed in 1997 to limit spam in email or denial-of-service attacks. It is a method by which extra information is added to the header of an email to prove that the legitimate sender has invested a certain calculation capacity to send the message. If this is proven, it implies that the issue is not a spammer.
Taking a hash algorithm, hashcash requires the sender to calculate a hash that contains 20 bits to zero on the left. The only way that the issuer has to generate this information is through iteratively applying the hash algorithm (brute force) over the original information and iteratively incrementing an integer until the calculation result (the hash) meets the condition of the number of bits to zero previous. The receiver can verify that this information is effectively valid with a negligible computational cost, equivalent to a single hash. Instead, the issuer has to perform 2 20hashes on average until you find a valid result. Since the generation time of a single hash is predictable (depending on the calculation capacity available), the time needed to generate the hash with 20 leading zeros is predictable on average. In this way, if the issuer has taken the trouble to generate this information with the workload involved, it is shown that he is not a spammer. On the other hand, for a spammer, the necessary computational capacity is linear with respect to the number of emails to be sent, which implies that work is slow and the use of resources increases considerably, making the viability of sending spam not really so positive in practice. In Figure 3.2.2. an example is shown to visualize the operation of the hashcash algorithm:
"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 000003af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9
Figure 3.2.2. Practical example of hashcash operation.
In the previous practical example, it can be seen how the issuer would have to change the Nonce up to 4251 times and generate the same amount of hashes until finding a result with the number of zeros to the left specified.
Cryptographic hash function
A cryptographic hash function (or summary function) is an algorithm that takes as input any data of any length (the message ) and returns a string of fixed-length bits (the hash ).
The main characteristics of an ideal cryptographic hash function are the following:
- Efficiency in computing. You must provide a quick calculation of the hash from an input message.
- Preimage resistance. It must be computationally very difficult to generate the message from which the summary has been derived.
- Resistance to the second preimagen . It must be computationally very difficult, given a message, to get a second message that generates the same hash.
- Resistance to the collision . It must be computationally very difficult to generate two different messages and that the hash of them be the same.
Historically, hash functions have had diverse and varied applications in the context of cryptography, as they are used in digital signatures, in authentication algorithms, in fingerprinting systems or also to verify data integrity (a form of checksum).
Bitcoin defines the use of two types of hash algorithms: SHA-256 and RIPEMD-160.
SHA-256 (Secure Hash Algorithm). It is the main hash algorithm used in the Bitcoin protocol. It belongs to the family of SHA-2 hash functions designed by the NSA and accepted by NIST as the standard to be used in hashing algorithms by the North American administration, to replace its more immediate predecessor, SHA-1, of which they are known. several security vulnerabilities.
RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest). In addition to the previous hashing algorithm, Bitcoin uses another algorithm in cases where a shorter hash is required. It was created in 1996 and belongs to the RIPEMD family, of which there are algorithms with 128, 160, 256 and 320-bit output lengths. Then, Bitcoin uses the 160-bit version, like SHA-1, but with the main difference that RIPEMD was created under the auspices of an open research community as opposed to SHA-1, which was designed by the NSA.
It should be noted that Bitcoin always generates a hash result of applying a hash algorithm twice over any data, in order to increase the security against cryptanalysis.
Digital signature
Bitcoin uses a digital signature based on public key cryptography to authenticate data and correctly verify who is authorized to transfer coins. More specifically, Bitcoin defines the use of elliptic curve cryptography (ECC, Elliptic Curve Cryptography) using the algorithm ECDSA (Elliptic Curve Digital Signature Algorithm), DSA version based on the elliptic curve. The ECC algorithms are based on the complexity of solving certain mathematical problems in relation to the algebraic structure of the elliptic curves on finite fields. Generally, it is assumed that solving the discrete logarithm of an element of an elliptic curve chosen at random from a public base point is computationally unfeasible (ECDLP, Elliptic Curve Discrete Logarithm Problem).
With respect to public key algorithms based on the factorization of very large integers composed of two or more prime factors (such as RSA), the most relevant advantage of ECC is the reduction of key size for the same level of security. Thus, taking as reference a document of recommendations of the SEC (Standards for Efficient Cryptography) [ SECrecom ], for a certain level of security (in bits), only a key of twice the size of the security level required is needed. In Table 3.2.1 you can compare the size of the keys for ECDSA and for the key module for RSA / DSA to obtain equivalent security levels.
Bitcoin uses the elliptic curve specified in the secp256k1 recommendation of Table 3.2.1. Therefore, the signatures provide strength equivalent to 128 bits with only a key size of 256 bits. Using the classic versions of RSA / DSA, the size of the key should be 3,072 bits for this same level of security.
In this lesson it is out of the objectives to know the mathematical parameters, the way to generate the keys and how the signature is calculated and its validity are verified by the ECDSA signature algorithm. However, additional information about these processes can be obtained from these links: ECC and ECDSA.
Merkle trees
A Merkle tree or hash tree is a construction in the form of a tree of values where each interior node (nodes that do not end nodes) is the result of applying a hash function (be SHA-1, SHA-2, etc.) on the value of the child nodes until it reaches a root node called Merkle root of the tree. They can be binary (each inner node has two descendants, Figure 3.2.1) or not (each inner node has a certain number of descendants). The functionality of these algorithms is to enable the integrity and inclusion of all the data of large data structures to be verified efficiently and safely. In addition, they can be considered as a generalization of hash chains ( hash chains), where the verification of an element is proportional to the logarithm of the number of nodes of the tree, unlike the hash chains, where the cost is linear with the number of hashes contained in the chain.
Hashcash algorithm
Hashcash [ hashcashPaper ] is a proof-of-work system initially designed in 1997 to limit spam in email or denial-of-service attacks. It is a method by which extra information is added to the header of an email to prove that the legitimate sender has invested a certain calculation capacity to send the message. If this is proven, it implies that the issue is not a spammer.
Taking a hash algorithm, hashcash requires the sender to calculate a hash that contains 20 bits to zero on the left. The only way that the issuer has to generate this information is through iteratively applying the hash algorithm (brute force) over the original information and iteratively incrementing an integer until the calculation result (the hash) meets the condition of the number of bits to zero previous. The receiver can verify that this information is effectively valid with a negligible computational cost, equivalent to a single hash. Instead, the issuer has to perform 2 20hashes on average until you find a valid result. Since the generation time of a single hash is predictable (depending on the calculation capacity available), the time needed to generate the hash with 20 leading zeros is predictable on average. In this way, if the issuer has taken the trouble to generate this information with the workload involved, it is shown that he is not a spammer. On the other hand, for a spammer, the necessary computational capacity is linear with respect to the number of emails to be sent, which implies that work is slow and the use of resources increases considerably, making the viability of sending spam not really so positive in practice. In Figure 3.2.2. an example is shown to visualize the operation of the hashcash algorithm:
"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 000003af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9
Figure 3.2.2. Practical example of hashcash operation.
In the previous practical example, it can be seen how the issuer would have to change the Nonce up to 4251 times and generate the same amount of hashes until finding a result with the number of zeros to the left specified.
Comments
Post a Comment