The Inner Workings/Blockchain Explained

A blockchain is identified by several parameters T = (p, a, b, G, n and h), and its digital signature algorithm is created on the basis of the same mathematics that is behind the eliptic curve digital signature algorithm (ECDSA). In an asymmetric key exchange composed of a public and private key pair (Kpnv,Kpub) using equation

If two points of communication, A and B, are required to verify and authenticate the receiver signal, this can be done by generation of message signing and authentication using a digital signature [7].

Components of Cryptography

In blockchain, a cryptographic hash is used on digital signatures carrying a certain amount of data stored in the Merkle tree [8]. Figure 9.2 shows the structure of a blockchain network, with header hash and a Merkle tree storing the data [9]. Various

Merkle tree connecting representations of block header routes and transactions

FIGURE 9.2 Merkle tree connecting representations of block header routes and transactions.

components include the methods of data storage, the authentication and hashing mechanism, and the methodology of storage of hashed information. Its components are: header block, Merkle tree, cryptographic hash function, data authentication, and timestamping [10].

The Algorithm behind Blockchain Explained

Finite Fields

A finite field can be perceived as a set range of positive numbers, within which each calculation must fall. Any number that is not in this range must be wrapped around to ultimately fall within the range. Theoretically, for every finite field, there exists a number t such that £ t equals 0, i.e, 1 + 1 + 1 ....1 = 0 [5,11].

The first number a, following this property t, must belong to set of prime numbers P" and is defined as characteristic of the field. The simplest example for this is calculating the remainder modulus (mod) with respect to a number. Figure 9.3 shows the wrapping of Secp256kl over finite field F23.

Elliptic Curve Cryptography (Ecc) over R

Elliptic curves are defined by the function (fix)) of the form:

Finite field graph of an elliptic curve over F23 (mod 24)

FIGURE 9.3 Finite field graph of an elliptic curve over F23 (mod 24).

This is also called the “short Weierstrass form” and is the general form to talk about elliptic curves. The other form of elliptic curve that can be discussed is the "Edward form”:

This is used to “sign” data in a manner such that third parties can authenticate the signature of the signer, since the private key can only be created by the signer. Elliptic curves have several useful properties that make them usable for Bitcoin; these can be studied by plotting the Weierstrass form on the graph. Two important properties of ECDSA, which are used for the generation of points, are: point addition and point doubling.

The addition (P + Q) and doubling (2P) of points are used together for scalar multiplication Z = kX, defined as the repetitive addition of point X to itself к times. Taking an example from [12], each number can be represented as the continued sum and doubling of itself.

The important idea to be understood is that if we have point X and point Z, we cannot find preimage k. This implies that we cannot find к = Z/X, as no inverse for point addition or point doubling exists. Thus, the irreversibility of the ECDSA point multiplication and one-way function helps the system of asymmetric keys work to maintain a cryptographically encrypted secure system.

Putting These Together

Elliptic Curves over Fp (Graphical Understanding)

Floating point arithmetic has a drawback, in that integers, in time, are taken for computations, which is unavoidable from the ECDSA algorithm. For faster computation, we require input without decimal numbers. Hence, we consider an elliptic curve over finite fields [13].

Definition: an EC (E(Fq)) defined over F (: Fq) is a set of the following points:

P, = (Ду,) у2 = x} + 7 over Fq which can be expressed as y2 =x2 + 1 (mod q)

for bitcoin: q = 2256 - 232 - 29 - 2s - 27 - 26 - 2х - 1 (see Figure 9.4 for a finite field graph of a Secp256 curve).

As explained in [13], a cyclic subgroup of an EC is used while choosing parameters in place of the complete curve. The secondary additional parameters, such as a, b, p, к and point GsE(Fq), are used to choose the sufficient cyclic subgroup. The parameters are then shared, to generate public keys.

For their signature on any message, the sender is required to randomly choose an integer A as their private key (Kr ), and compute the public key as (Ka) = nAG. A trusted authority (ТА) is used to store all the public keys, to make them public within the network.

Secp256 curve (y = jc + 7) defined over the field Zr__ where X and Y are coordinated 256-bit integer modulo large numbers

FIGURE 9.4 Secp256 curve (y2 = jc3 + 7) defined over the field Zr56_232_977 where X and Y are coordinated 256-bit integer modulo large numbers.

Signature Generation

ECDSA signal generation specifies signing a message m, A as an entity and several domain parameters. D = (q,FR,a,b,G,n,h) and associated pair of public keys (d, Q). The message key (r, y) must hold the condition of being a unique and nonzero pair [14]. Figure 9.5 show's point doubling and point addition for generator point G, for key generation of (r, y).

The procedure to generate the message signature can be described as follow's: [1] [2] [3] [4] [5] [6] [7] [8]

Pictorial plotting of the multiplication of the generator point G by private key Kpriv [15]

FIGURE 9.5 Pictorial plotting of the multiplication of the generator point G by private key Kpriv [15].

Signature Verification

Since the receiver has a legitimate copy of all the sender’s domain parameters and the PubKey <2, we can verify a’s message signature (r, 5) by doing the following:

  • 1. Assert that received integers (r, 5) belong to the interval /, IeZandl> 0 and I
  • 2. Compute the hash of message signal SHA-l(M) and convert this hashed binary string to integer e.
  • 3. Find the modular inverse of s, represented by tv = s~'(mod n).
  • 4. Find //1 = e * w(mod n) and м2 = r * w(mod n).
  • 5. Find X = Ml * G + м2 * G.
  • 6. The received signal is rejected if X = 0.
  • 7. Otherwise convert xl, the .v-coordinate of X, to integer xY, and compute v = дгГ (mod n).
  • 8. If = r, the signal is accepted, or else the signal is not verified by the system.

Proof of the Signal Verification

If message M is derived from entity «, then we infer that

Multiplying both sides with and к

Using the distributive property over multiplication and multiplying s_l with both terms

к = s~[e + s~'dr (mod n); since w = s~'

Substituting the value of s~'e (mod n) and s~'dr (mod n) calculated in step 3

hence v = r.

Hence, if the receiver marks the incoming message as being authentic, the precondition v = r is fulfilled. If an external attacker tries to impersonate the sender and generates a message m such that m ! = in’, and the impersonator finds the domain parameters a, b, G, h, n, p, and q and computes Q = (xl.yl) points on the curve Choose v = xl (mod n), and thus attempts to compute the hash of message m’ as H(m') from domain parameters and finds Ark The effort culminates in proving v = r. But since s is dependant on the sender’s secret key A, which is only known to the sender, an attacker would require a technique to find the correct secret key without entity A, in other words, solving the ECDSA discrete logarithm problem (i.e., the conceptual fulcrum of blockchain’s security) [14].

Proving the Space and Time Complexities

Hash Function

Most hash functions have been designed with

  • • Initialization stage (with a fixed performance overhead) 0( 1)
  • • Compression function
  • • State update function
  • • Finalization state (with a fixed performance overhead) 0( 1)

The initialization and finalization of hash functions have fixed overhead time usage, hence the time complexity observed is 0( 1) for both of these steps to evaluate the computational complexity of the hash function. Compression and state update are considered per block and can be considered together. Figure 9.6 shows a general model of the hash function and time complexity of various steps. Considering that there are total n blocks, and fixing the input by padding of numbers for computation of hash, where there is constant k, per-block overhead padding, and c is the constant time taken to initialize the hash. Then, the total time is calculated as 0(c + kn). SHA- 256 is one such example of a hash function used in cryptographic encryption techniques like blockchain.

Pictorial representation of the general model of a hash function

FIGURE 9.6 Pictorial representation of the general model of a hash function.

Traversal Time Complexity

In practice, Merkle trees have been criticized due to their high computational requirement and space and storage costs. Figure 9.7 shows a comparison of two standard approaches of Merkle tree hashing, with a comparison of the space and time trade-off.

Hashing Approach in MerkleTree

Maximum Space Requirement

Maximum hash Evaluations per Round

Traditional Approach as per Markus Jacobsson [16]

Time-Space Trade-off Approach [17]

Hashing Approach in Merkle Tree

Maximum Space Requirement

Maximum hash Evaluations per round

Traditional Approach As per M.Jacobsson[18]

Tune - Space Tradeoff Approach[19]

Table comparing space complexity and hash evaluations between hashing approaches in a Merkle tree

FIGURE 9.7 Table comparing space complexity and hash evaluations between hashing approaches in a Merkle tree. This can be further improved by scheduling methods with a logarithmic Merkle tree traversal. It uses scheduling to compute a specific number of nodes at once. This budget is used with 1 for the computation of left nodes and the rest for building the node values with stacks [18].

Elliptic Curve Discrete Logarithm Problem (Ecdlp)

Let there be an elliptic curve E over a finite field F4 where q = p" and the computational problem is to find two points P, Q such that P.Qe E(Fq) such that Q = aP [19].

This is the basis of pairing-based cryptography and elliptic curve cryptography. A few algorithms have been proposed for this problem:

  • • The “Meet-in-the-Middle” algorithm works contrary to a brute force attack.
  • • For the computation of discrete logarithms, Pollard’s rho p algorithm is used.

With an asymptotic time complexity of O(yfn) and a space complexity of 0(1), it has the basic principle of generating a pseudo-random sequence of points XI, X2.....where each X = a,P + b

• With the capability of a discrete logarithm in polynomial time, a new quantum algorithm has been proposed, Shor’s algorithm, with a worst-case time complexity of 0((log /;)-’) and a space complexity of 0(log n).

Distributed Consensus Mechanism Based on Proof of Work

Proof of Work (PoW) is used as one of the mechanisms for consensus building and achieving agreement on the distributed network of blockchain to confirm transactions and produce new blocks on the blockchain. With PoW, prospective miners can compete against each other in an effort to validate the various transactions for a reward. We find the probability of being selected for building the next successive block, which is linked to the computation power of the system.

The underlying consensus-building model for blockchain lies on the PoW concept, which relies on a driving and incentive structure that provides a byzantine-fault- tolerant (BFT) distributed network. It is dependent on solving a mathematical puzzle to find a value below a threshold (nonce), which is used for the production of a new block broadcast to the network. Satoshi Nakamoto’s protocol design for Bitcoin aims to reach a common coordinated consensus algorithm to authenticate the legitimacy of each transaction. The PoW can be characterized in two properties:

  • 1. It must be computationally intensive and consume greater time for any miner to generate a proof that meets the requirements.
  • 2. The verification of such a proof must not be time-consuming, and the proof’s correctness should be easy to verify.

  • [1] Selection of an arbitrary/pseudo random natural number к between 0 and n(not inclusive).
  • [2] Computation of random point on curve (x, yl) = kG in finite field
  • [3] Calculate r = .vl(mod ri). If we get r as 0 , find another point of the curve andrepeat from step 1.
  • [4] Find к inverse /г1 mod n.
  • [5] Find the SHA hash of message m, SHA-l(w) and change the correspondingbinary string into an integer e.
  • [6] Compute s = kr'(e + dr) mod n, w'here d is the private key.
  • [7] If у is zero, thus not fulfilling the primary condition, revert back to step 1.
  • [8] Thus generated values are (r,s), which form the signature pair for A.
 
Source
< Prev   CONTENTS   Source   Next >