How Algorithms of BuChain work?

J
J
Sep 3, 2018 · 5 min read

by PAK, JESSICA and SHIH, PEI-LEI

Today we will explore some fundamental concepts of hash algorithm and public key & private key encryption, which are basic for blockchain.

With several techniques from different fields integrated in, blockchain generates a new technical architecture of its own. Also, hash algorithm and cryptography enlarge the ground for self-proof trust and security management of it.

A Good Hash Algorithm

To make it easier to understand, we can say that hash algorithm enables one-way operations to encrypt messages, by which the plaintext will be encoded by cipher as ciphertext, and such operations can’t be reversed. A GOOD hash algorithm shall be:

Having very good speed. During one-way operation with limited time and resources as well as plaintext and hash algorithm given, one can hash messages pretty quick.

Really hard to reverse. One can scarcely reverse or crack info, from given hashes to get those plaintexts which are buried deep.

Sensitive about input changes. Even with the slightest change, the hash value of original messages will differ entirely.

Avoid collisions. There will be extremely small chances for two plaintexts to have the same hash value after ciphered. Barely impossible for now, you may say.

Basic Structure for How Hash Works

Here are some essential parameters for each block:

Prev_Hash: which is calculated by previous block of the current one.

Timestamp: for how long it takes to generate a block.

Tx_Hash: which is the hash generated by packing all transactions.

Basically, three parameters above will be in every blockchain. Except timestamp, the rest of the two require hash function.

Data Structure of BuChain

MD5 (Message-Digest Algorithm 5) and SHA (Secure Hashing Algorithm) are the most popular hash algorithms that you may heard about. Hash functions are widely applied in blockchain, such as:

  1. Computing the address, public key and private key of certain node in blockchain.
  2. Hashing algorithms applied by Merkle Patricia Trie, which is a tree-shape data structure which mixed Merkle Trie and Prefix Trie.

If you have a background of data storage knowledge, skip this part. If you don’t, let’s spend some time on what exactly Merkle Trie is. It’s quite easy to understand.

Merkle Tree

Merkle Tree data structure

First, what is Merkle Tree?

Merkle tree is used to authenticate data. In dataset, key is string and value is integer. Since Root Hash can only be influenced by dataset here, we could verify the consistency of two datasets then. For every set of (K, V), K determines where data is in the tree and V settles the hash of data. Therefore, Root Hash is set by (K, V) dataset. Every time data is modified, added or deleted, to target the change, we just need to find out in which path that the changed node is. It is impossible to fake data without changing value of root. That’s the feature of Merkle Tree.

Trie (also called digital tree, radix tree or prefix tree)

An ordered tree data structure

However, in Prefix Tree (also known as Digital Tree or Radix Tree), the key will be the path of a node. As a data structure that has several branches, Prefix Tree is used to optimize for searching.

In Prefix Tree, character is not included in Root Nodes, instead of that, every single Children Node has a character in. The characters on the path from one Root Node to a certain node will string up together, and the string is the key of this certain node. Also, for Children Nodes under this certain node, the character of each Children Node varies.

Patricia Tree

How Patricia Tree Works

Merkle Patricia Tree

Merkle Patricia Tree (MPT) of BuChain

Here is Merkle Patricia Tree. If we combine Prefix Tree and Merkle Tree, we can not only speed up the comparison, but also optimize the check and search of data.

Encryption of Public & Private Key

There are symmetrical and asymmetrical algorithms for encryption, differs by whether the keys are the same.

  1. Digital signature of public key is operated on-line. Somehow it works like ‘signing’ in the actual physical world which can be objectively verified.
  2. Digital signature identifies signer’s ID and ensures non-repudiation once data changes.
  3. Every transaction on blockchain system shall be ‘signed’ digitally.

Asymmetrical encryption enables three features above in an easier way.

Asymmetrical Encryption

Here is how it works in blockchain.

  1. First, key pairs, both public and private, shall be generated. User keeps the private key and sends the public key to other users.
  2. Later, sign on some specific message by private key and get signature data of the message.
  3. Then you can verify the signature if you have the public key.
Elliptic-curve cryptography (ECC)

ECC (Elliptic Curve Cryptography) is a type of public key cryptography, also an asymmetric algorithm like RSA and ElGamal. Since ECC can offer the same level of cryptographic strength at much smaller key sizes, when key sizes are set, ECC will offer stronger security.

Our public blockchain uses ed25519 for signatures and verifications. Such algorithm was first released by Daniel J. Bernstein in 2006. Using elliptic curve to encrypt, sign and exchange key, by which account address is generated by public key and ensured as unique. Opened-up design of ed25519 sets very simple and clear parameters. Rather concise and explicit for no doubts to arise.

Features of Ed25519

Ed25519 is safe. Even an ECC digital signature scheme is mathematically safe, it may not be practically secured since there’s a huge chance that it might be compromise by cache, time and malicious inputs. Curve25519, however, is well-designed and reduces error as much as possible, and practically is the safest encryption algorithm ever.

Ed25519 is fast. Curve25519 is the fastest encryption algorithm for now.

Conclusion

Here are only few parts of our BuChain intro. I will keep on posting and updating here.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade