Cryptographic constructs and blockchain technology

Now, we'll present some advanced topics in cryptography that not only are important on their own, but are also relevant to blockchain technology due to their various applications in this space.

Homomorphic encryption

Usually, public key cryptosystems, such as RSA, are multiplicative homomorphic or additive homomorphic, such as the Paillier cryptosystem, and are called partially homomorphic systems. Additive Partially Homomorphic Encryptions (PHEs) are suitable for e-voting and banking applications.

Until recently, there has been no system that supported both operations, but in 2009, a fully homomorphic system was discovered by Craig Gentry. As these schemes enable the processing of encrypted data without the need for decryption, they have many different potential applications, especially in scenarios where maintaining privacy is required, but data is also mandated to be processed by potentially untrusted parties, for example, cloud computing and online search engines.

Recent development in homomorphic encryption have been very promising, and researchers are actively working to make it efficient and more practical. This is of particular interest in blockchain technology, as described later in this book, as it can solve the problem of confidentiality and privacy in the blockchain.

Signcryption

Signcryption is a public key cryptography primitive that provides all of the functions of a digital signature and encryption. Yuliang Zheng invented signcryption, and it is now an ISO standard, ISO/IEC 29150:2011. Traditionally, sign then encrypt or encrypt then sign schemes are used to provide unforgeability, authentication, and non-repudiation, but with signcryption, all the services of digital signatures and encryption such as confidentiality are provided at a cost that is less than that of the sign then encrypt scheme.

Signcryption enables Cost (signature & encryption) << Cost (signature) + Cost (Encryption) in a single logical step. This means that the cost of applying a digital signature and encrypting a message in the same logical step is lower, compared to a scheme where a message is first signed and then encrypted in two independent steps. This property makes signcryption an efficient scheme.

Secret sharing

Secret sharing is the mechanism of distributing a secret among a set of entities. All entities within a set get a unique part of the secret after it is split into multiple parts. The secret can be reconstructed by combining all or some parts (a certain number or threshold) of the secret. The individual secret shares/parts, on their own, do not reveal anything about the secret.

This concept can be visualized through the following diagram:

Figure 4.12: Secret sharing scheme

Commitment schemes

Commitment schemes are usually described as a digital cryptographic equivalent of a sealed envelope. A commitment itself does not reveal any information about the actual value inside it. This scheme runs in two phases, namely:

• Commit phase
• Open phase

The commit phase provides two security features; that is, hiding and binding:

• The hiding property is required to ensure that the recipient party cannot find any information or reveal the committed value before the open phase.
• The binding property ensures that once the sender has committed to a value, that value or message cannot be changed.

The open phase (also called the unveil phase) is where the receiver receives some additional information from the sender. This allows the receiver to establish the value hidden (concealed) by the commitment with a proof that the sender has not modified the value after the commitment, that is, that the sender has not deceived during the commit phase.

Commitment schemes are used for building zero-knowledge protocols and range proof protocols. The key idea behind commitment schemes is that they allow someone to secretly commit to a value with the ability to reveal it later. These schemes prevent parties from changing their committed value later, after they've committed to a value.

A prime example of a commitment scheme is the Pedersen commitment scheme.

In the next section, we'll introduce zero-knowledge proofs, which is an exciting subject and a very ripe area for research. Already, various major blockchains and cryptocurrencies makes use of zero-knowledge proofs to provide privacy. A prime example is Zcash (https://z.cash).

Zero-knowledge proofs

Zero-Knowledge Proofs (ZKPs) were introduced by Goldwasser, Micali, and Rackoff in 1985. These proofs are used to prove the validity of an assertion without revealing any information whatsoever about the assertion. There are three properties of ZKPs that are required: completeness, soundness, and the zero-knowledge property.

Completeness ensures that if a certain assertion is true, then the verifier will be convinced of this claim by the prover.

The soundness property makes sure that if an assertion is false, then no dishonest prover can convince the verifier otherwise.

The zero-knowledge property, as the name implies, is the key property of ZKPs, whereby it is ensured that absolutely nothing is revealed about the assertion except whether it is true or false.

In literature, usually, an analogy known as "Ali Baba's Cave" is used to explain zero-knowledge proofs.

The following diagram shows a variant of this analogy of how the zero-knowledge protocol works. It shows two characters called Peggy and Victor whose roles are Prover and Verifier, respectively. Peggy knows a secret magic word to open the door in a cave, which is shaped like a ring. It has a split entrance and has a magic door in the middle of the ring that blocks the other side. We have also labeled the left and right entrances as A and B. Victor wants to know the secret, but Peggy does not want to reveal it. However, she would like to prove to Victor that she does know the secret:

Figure 4.13: Analogy of the zero-knowledge mechanism

Now, there are several steps that are taken by both Peggy and Victor to reach a conclusion regarding whether Peggy knows the secret or not:

1. First, Victor waits outside the main cave entrance and Peggy goes in the cave.
2. Peggy randomly chooses either the A or B entrance to the cave.
3. Now, Victor enters the cave and shouts either A or B randomly, asking Peggy to come out of the exit he named.
4. Victor records which exit Peggy comes out from.

Now, suppose Victor asked Peggy to come out from exit A and she came out from exit B. Victor then knows that Peggy does not know the secret. If Peggy comes out of exit A, then there is a 50% chance that she does know the secret, but this also means that she may have got lucky and chose A to enter in the first place, and now has just returned without needing to go through the magic door at all. Now, if this routine is performed several times, and given that Victor is choosing A or B at random, with each run (round) of this routine (protocol), the chances of Peggy getting lucky diminish. If Peggy repeatedly manages to emerge from the entrance that Victor has named, then it is highly probable that Peggy does know the secret to open the magic door.

Note that during this process, Peggy has not revealed the secret at all, but still managed to convince Victor with high probability that she does know the secret.

A ZKP comprises the following phases:

1. Witness phase: In this phase, the prover sends proof of the statement and sends it to the verifier.
2. Challenge phase: In this phase, the verifier chooses a question (challenge) and sends it to the prover.
3. Response phase: In this phase, the prover generates an answer and sends it as a response to the verifier. The verifier then checks the answer to ascertain whether the prover really knows the statement.

This scheme can also be visualized using the following diagram, which shows how the zero-knowledge protocol generally works and what steps the prover and verifier take in order to successfully run the protocol:

Figure 4.14: A zero-knowledge proof scheme

Even though zero-knowledge is not a new concept, these protocols have sparked a special interest among researchers in the blockchain space due to their privacy properties, which are very much desirable in finance and many other fields, including law and medicine. A prime example of the successful implementation of a zero-knowledge proof mechanism is the Zcash cryptocurrency. In Zcash, the zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk-SNARK) is implemented to provide anonymity and confidentiality.

Applications of ZKP include proof of ownership, that is, proof that the prover is the owner of some secret or a private key without revealing the nature of it. ZKPs can also be used to prove that the prover is a member of some organization or group, without revealing their identity. Another use case could be proof of age, where the prover proves that they are, for example, older than 25 years, but do not want to reveal their exact age. Another application could be where citizens can pay taxes without revealing their income.

Zero-knowledge protocols are usually interactive as they require repeated interactions between the prover and the verifier, but there are protocols that do not require any interaction between a prover and a verifier. These type of ZKPs are called non-interactive types of proofs. A prominent example is the zk-SNARK. Before the introduction of zk-SNARKs, ZKPs were considered not very practical because of the complexity that arises from the requirements of repeated interaction between the prover and the verifier and a large proof size.

zk-SNARKs

The zk-SNARK is a variant of ZKPs that is more efficient and simpler to use and implement.

Zk-SNARKs have several properties, which are described here:

• Zero knowledge (zk): This property allows a prover to convince a verifier that an assertion (statement) is true without revealing any information about it.

  A statement in this context is any computer program that terminates and does not take too long to run, that is, not too many cycles.

• Succinct (S): This property allows for a small proof that is very quick to verify and is succinct.
• Non-interactive (N): This property allows the prover to prove a statement without any interaction with the verifier.
• ARguments of Knowledge (ARKs): These are the arguments to convince the verifier that the prover's assertion is true. Remember that we discussed soundness and completeness earlier. In the case of ARKs, the prover has a computational soundness property, meaning that the prover is computationally bounded, and it is computationally infeasible for it to cheat the verifier.

Zk-SNARKs have been implemented in different blockchains. The most prominent example is Zcash, which uses it for its shielded transactions feature to provide confidentiality and anonymity. Support for cryptographic primitives required for zk-SNARKs has also been introduced in the Ethereum blockchain with the Byzantium release.

Zk-SNARK proofs are generated by following a number of different steps. Generating SNARKs for a program (statement) is not a simple process as it requires the program to be converted into a circuit with a very specific format. This specific form is called the Quadratic Arithmetic Program (QAP). The process of proof generation is as follows:

Figure 4.15: zk-SNARK construction

• Arithmetic circuit: The first step in zk-SNARK construction is to convert a logical step of a computation into the smallest possible units comprised of basic arithmetic operations. Arithmetic operations include addition, subtraction, multiplication, and division. In the arithmetic circuit, the computation is presented as wires and gates, representing the flow of inputs and arithmetic operation performed on the inputs.
• R1CS: R1CS is the abbreviation of Rank 1 Constraint System (R1CS). Basically, this system is a set of constraints that allows all the steps in the arithmetic circuit to be verified, and also confirms that, at the end of the process, the output is as expected.
• QAP: The prover makes use of QAPs to construct proof for the statement. In R1CS, the verifier has to check many different constraints, but with a QAP representation of the circuit, all the different constraints can be bundled into only a single constraint. Finally, QAP is used in the zk-SNARK protocol to prove the assertion through the prover and verifier.

Zk-SNARKs are not a silver bullet to privacy problems. Instead, like many other technologies, there are pros and cons.

The biggest criticism of zk-SNARKs is the initial trusted setup. This trusted setup can be influenced and compromised. However, if done correctly, it does work, but there is, however, always a chance that the initial setup was compromised and no one will ever be able to find out. This is the issue that has been addressed in zk-STARKs.

zk-STARKs

Zero-knowledge Scalable Transparent ARguments of Knowledge (zk-STARKs) are a new type of ZKP that has addressed several limitations in zk-SNARKs.

This scheme was designed by Eli-Ben Sasson et al.

The key differences between the zk-STARK and zk-SNARK schemes are listed in the following table:

Even though this scheme is more efficient, post-quantum resistant, scalable, and transparent, the biggest limitation is its size of proof, which is a few hundred kilobytes compared to zk-SNARKs' 288 bytes. This is seen as a problem in public blockchains where large proofs may pose a problem to scalability and performance.

Zero-knowledge range proofs—ZKRPs

ZKRPs are used to prove that a number is between a certain range. This can be useful when, for example, someone does not want to reveal their salary but is willing to only reveal the range between which their salary lies. Range proofs can also be used for age checks without requiring the prover to reveal their exact age.

In this section, we have covered the very interesting topic of ZKPs and their relevant techniques and developments. ZKPs is a very active area of research, especially in the context of blockchains, where this technology can provide much needed privacy and confidentiality services on public blockchain networks. Next, we'll introduce different types of digital signatures.

Different types of digital signatures

We previously covered digital signatures, but that was an introduction to standard digital signatures. Now, we'll provide an overview of different types of digital signatures and their relevance and applications in blockchain technology.

Blind signatures

Blind signatures were introduced by David Chaum in 1982. They are based on public key digital signature schemes, such as RSA. The key idea behind blind signatures is to get the message signed by the signer, without actually revealing the message. This is achieved by disguising or blinding the message before signing it, hence the name blind signatures.

This blind signature can then be verified against the original message, just like a normal digital signature. Blind signatures were introduced as a mechanism to allow the development of digital cash schemes. Specifically, a blind signature can provide unlinkability and anonymity services in a distributed system, such as a blockchain.

The blind signature scheme is also used in building Blindcoin, which is used in the Mixcoin protocol for Bitcoin to hide user addresses from the mixing service. Mixcoin protocol allows anonymous payments in the Bitcoin network, but the user addresses are still visible to the mixing service. Blindcoin is a protocol that addresses this limitation.

Multisignatures

In this scheme, a group of entities signs a single message. In other words, multiple unique keys held by their respective owners are used to sign a single message. This scheme was introduced in 1983 by Itakura et al. in their paper A Public-key Cryptosystem Suitable for Digital Multisignatures, vol. 71, Nec Research & Development (1983), pp. 474-480. Multisignatures are also sometimes called multiparty signatures in literature.

In blockchain implementations, multisignatures provide the ability to allow transactions to be signed by multiple users, which results in increased security. This is also called multi-sig and has been implemented in Bitcoin. These schemes can be used in such a way that the requirement of a number of signatures can be set in order to authorize transactions. For example, a 1-of-2 multisignature can represent a joint account where either one of the joint account holders is required to authorize a transaction by signing it. As another variation, for example, a 2-of-2 multisignature can be used in a scenario where both joint account holders' signatures are required to sign the transaction. This concept is also generalized as m of n signatures, where m is the minimum number of required signatures and n is the total number of signatures. This concept can be visualized with the following diagram:

Figure 4.16: Multi signature scheme

The preceding diagram shows the signing process on the left-hand side, where m is the number of different users, and holding m unique signatures signs a single transaction. When the validator or verifier receives it, all the signatures in it need to be individually verified.

The Openchain and Multichain blockchains make use of multisignature schemes.

Threshold signatures

This scheme does not rely on users to sign the message with their own unique keys; instead, it requires only one public key and one private key, and results in only one digital signature. In multisignature, the resultant message contains digital signatures from all signers and requires verification individually by the verification party, but in threshold signatures, the verifier has to verify only one digital signature. The key idea in the scheme is to split the private key into multiple parts, and each signer keeps their own share of the private key. The signing process requires each user to use their respective share of the private key to sign the message. The communication between signers is governed by a specific communication protocol. In contrast with multisignatures, the threshold signatures result in a smaller transaction and are quicker to verify. A disadvantage, however, is that in order for threshold signatures to work, all signers must remain online, whereas in multisignatures, the signature can be provided asynchronously; that is, users can provide signatures whenever they are available. From another angle, there could be a scenario in multisignatures where a user can withhold their signature maliciously, which could be disadvantageous. Threshold signatures can also be used to provide anonymity services in a blockchain network:

Figure 4.17: Threshold signature scheme

The preceding diagram shows the signing process on the left-hand side, where m number of different users, holding different parts (shares) of a digital signature, sign a single transaction. When the validator or verifier receives it, only one signature needs to be verified.

Aggregate signatures

Aggregate signatures are used to reduce the size of digital signatures. This scheme is particularly useful in scenarios where multiple digital signatures are in use. The core idea is to aggregate multiple signatures into a single signature, without increasing the size of the signature of a single message. It is simply a type of digital signature that supports aggregation. The small aggregate signature is enough to provide verification to the verifier that all users did sign their original messages. Aggregate signatures are commonly used to reduce the size of messages in network and security protocols. For example, the size of digital certificate chains in Public Key Infrastructure (PKI) can be reduced significantly by compressing all signatures in the chain into a single signature. Boneh–Lynn–Shacham (BLS) aggregate signatures is a popular example of the aggregate signature. BLS has also been used in various blockchains, and especially in Ethereum 2.0.

Ring signatures

Ring signatures were introduced in 2001 by Ron Rivest, Adi Shamir, and Yael Tauman.

Ring signature schemes allow a mechanism where any member of a group of signers can sign a message on behalf of the entire group. The key requirement here is that the identity of the actual signer who signed the message must remain unknown (computationally infeasible to determine) to an outside observer. It looks equally likely that anyone of the trusted group of signers could have signed the message, but it is not possible to figure out who actually signed the message. Each member of the ring group keeps a public key and a private key. Ring signatures can be used to provide anonymity services. This scheme is used in CryptoNote and Monero.

In this section, we covered different types of digital signatures, their operation, and their relevance to blockchains. In the next section, we will introduce encoding schemes and some relevant examples.

Encoding schemes

Other than cryptographic primitives, binary-to-text encoding schemes are also used in various scenarios. The most common use is to convert binary data into text so that it can either be processed, saved, or transmitted via a protocol that does not support the processing of binary data. For example, images can be stored in a database encoded in base64, which allows a text field to be able to store a picture. Another encoding, named base58, was popularized by its use in Bitcoin and is addressed in detail in Chapter 6, Introducing Bitcoin.

Base64

The base64 encoding scheme is used to encode binary data into printable characters.

We can do a quick experiment using the OpenSSL command line:

$ openssl rand 16 -base64

4ULD5sJtGeoSnogIniHp7g==

The preceding command has generated a random sequence of 16 bits and then, using the -base64 switch, it has converted that into a base64 text string. Base64 converts from 8 bits to a 6-bit ASCII representation. This is useful for storage and transmission, especially in cases where binary data handling could lead to incompatibility between systems. This mechanism is a flexible way to represent binary data as ASCII, which can be easily and universally stored and transmitted.

Base58

The base58 scheme was first introduced with Bitcoin and is used to encode integers into alphanumeric strings. The key idea behind this encoding scheme is to avoid non-alphanumeric characters and also those characters that look similar and could lead to ambiguity; for example, a lower-case L (l) may look like the number one (1). This feature is especially useful because Bitcoin addresses must not have any confusion about the character representation; otherwise, it could lead to wrongly sending bitcoins to some non-existent or incorrect address, which is clearly a financial loss. This ingenious encoding scheme avoids this type of situation by ignoring similar looking characters.

We will explore base58 and its role in generating Bitcoin addresses in detail in Chapter 6, Introducing Bitcoin.

Cryptography is a vast field, and this section has introduced some of the main concepts that are essential to understanding cryptography in general, and specifically from a blockchain and cryptocurrency point of view.

In the next section, we'll introduce some applications of hash functions, which we introduced in Chapter 3, Symmetric Cryptography. Hash functions are extremely important and we will explore how these constructs are used, in blockchains and generally, to build useful constructs that provide the foundation for building blockchain networks.

Applications of cryptographic hash functions

There are various constructs that have been built using basic cryptographic parameters to solve different problems in computing. These constructs are also used in blockchains to provide various protocol-specific services. For example, hash functions are used to build Merkle trees, which are used to efficiently and securely verify large amounts of data in distributed systems. Some other applications of hash functions in blockchains are to provide a number of security services.

These services are listed here:

• Hash functions are used in cryptographic puzzles such as the Proof of Work (PoW) mechanism in Bitcoin. Bitcoin's PoW makes use of the SHA-256 cryptographic hash function.
• The generation of addresses in blockchains. For example, in Ethereum, blockchain accounts are represented as addresses. These addresses are obtained by hashing the public key with the Keccak-256 hash algorithm and then using the last 20 bytes of this hashed value.
• Message digests in digital signatures.
• The creation of Merkle trees to guarantee the integrity of transaction structure in the blockchain. Specifically, this structure is used to quickly verify whether a transaction is included in a block or not. However, note that Merkle trees on their own is not a new idea; it has just been made more popular with the advent of blockchain technology.

Merkle trees are the core building blocks of all blockchains; for example, Bitcoin and Ethereum. We will explore Merkle trees in detail now.

Merkle trees

The concept of Merkle trees was introduced by Ralph Merkle. A diagram of a Merkle tree is shown here. Merkle trees enable the secure and efficient verification of large datasets:

Figure 4.18: A Merkle tree

A Merkle tree is a binary tree in which the inputs are first placed at the leaves (nodes with no children), and then the values of pairs of child nodes are hashed together to produce a value for the parent node (internal node), until a single hash value known as a Merkle root is achieved. This structure helps to quickly verify the integrity of the entire tree (entire dataset), but just by verifying the Merkle root on top of the Merkle tree, because if any change occurs in any of the hashes in the tree, the Merkle root will also change. This is the reason why the integrity of the system can be verified quickly by just looking at the Merkle root. Another advantage of Merkle trees is that there is no requirement of storing large amounts of data, only the hashes of the data, which are fixed-length digests of the large dataset. Due to this property, the storage and management of Merkle trees is easy and efficient as it takes a very small amount of space for storage. Also, due to the fact that the tree is storage efficient, the relevant proofs for integrity are also smaller in size and quick to transmit over the network, thus making them bandwidth efficient over the network.

We will explain in detail how Merkle trees are fundamental for the consistency and integrity of a blockchain and its transactions in the chapters on Ethereum and Bitcoin.

Patricia trees

To understand Patricia trees, you will need to be introduced to the concept of a trie.

A trie, or a digital tree, is an ordered tree data structure used to store a dataset.

The Practical Algorithm to Retrieve Information Coded in Alphanumeric (Patricia) tree, also known as a Radix tree, is a compact representation of a trie in which a node that is the only child of a parent is merged with its parent.

A Merkle-Patricia tree, based on the definitions of Patricia and Merkle, is a tree that has a root node that contains the hash value of the entire data structure. Merkle-Patricia trees are used in the Ethereum blockchain.

Distributed hash tables

A hash table is a data structure that is used to map keys to values. Internally, a hash function is used to calculate an index into an array of buckets from which the required value can be found. Buckets have records stored in them using a hash key and are organized into a particular order.

With the definition provided earlier in mind, we can think of a Distributed Hash Table (DHT) as a data structure where data is spread across various nodes, and nodes are equivalent to buckets in a peer-to-peer network.

The following diagram shows how a DHT works:

Figure 4.19: DHT

In the preceding diagram, data is passed through a hash function, which then generates a compact key. This key is then linked with the data (values) on the peer-to-peer network. When users on the network request the data (via the filename), the filename can be hashed again to produce the same key, and any node on the network can then be requested to find the corresponding data. A DHT provides decentralization, fault tolerance, and scalability.

In this section, we covered various applications of cryptographic hash functions. Hash functions are of particular importance in blockchains, as they are key to constructing Merkle trees, which are used in blockchains for the efficient and fast verification of large datasets. With this section, we have completed our introduction to the applications of hash functions.