This is a conversation space in the Substack app that I set up exclusively for my subscribers — kind of like a group chat or live hangout. I’ll post short prompts, thoughts, and updates that come my way, and you can jump into the discussion.

To join our chat, you’ll need to download the Substack app, now available for both iOS and Android. Chats are sent via the app, not email, so turn on push notifications so you don’t miss conversation as it happens.

Read more

1. Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs)

2. Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go)

3. ZK SNARKS vs ZK STARKS

4. ZK Rollups

What are ZK Rollups?

Blockchain is a distributed ledger technology, which means that every node on the network has a copy of the entire blockchain. This approach ensures security, immutability, and transparency, but it comes at a cost of scalability. As the number of nodes on the network grows, the amount of data that needs to be processed and stored increases, making the blockchain slower and more expensive to use.

To address this issue, developers have been working on different scaling solutions. One of the most promising ones is ZK Rollups.

ZK Rollups is a layer 2 scaling solution that aims to improve the scalability and efficiency of blockchain networks. Layer 2 solutions are built on top of the main blockchain and enable off-chain processing of transactions, reducing the load on the main chain.

The "Zero-Knowledge" part of ZK Rollups refers to the use of cryptographic proofs to verify the validity of the batch transaction without revealing the details of each individual transaction. This ensures the security and privacy of the users while still allowing for efficient and cost-effective transaction processing.

In a ZK Rollup, transactions are processed off-chain by a group of validators, who bundle them together into a single transaction. The validators then create a ZK proof that attests to the correctness of the transaction, without revealing any sensitive information about the transaction itself. The ZK proof is then submitted to the main blockchain (like ethereum), which verifies its validity and stores it as a single transaction.

Here is an example of how a ZK Rollup works:

1. User A wants to send 1 ETH to User B.

2. User A submits their transaction to the ZK Rollup operator, along with a small fee to cover the gas costs of processing the transaction.

3. The ZK Rollup operator aggregates User A's transaction with several other transactions into a single batch transaction. The ZK Rollup operator can be considered on the layer 2 solution.

4. The ZK Rollup operator generates a Zero-Knowledge proof that proves the validity of the batch transaction without revealing the details of each individual transaction.

5. The ZK Rollup operator submits the batch transaction and Zero-Knowledge proof to the Ethereum blockchain, which verifies the proof and processes the transaction.

6. User B receives the 1 ETH from User A, and the transaction is recorded on the Ethereum blockchain.

Why do we need ZK Rollups?

Blockchain networks like Ethereum are facing scalability issues due to their limited transaction processing capacity. Ethereum can process around 15 transactions per second (tps), while Visa, for example, can process up to 24,000 tps. As the number of users and transactions on the network grows, the network becomes slower and more expensive to use.

Moreover, as the size of the blockchain grows, the cost of storing it increases, making it more challenging for new users to join the network. For example, the Ethereum blockchain has grown to over 1 TB in size, making it challenging for small-scale nodes to store and process the entire blockchain.

ZK Rollups address these issues by enabling off-chain processing of transactions, reducing the load on the main chain, and decreasing the amount of data that needs to be processed and stored on the blockchain. This approach increases the transaction processing capacity of the network, reduces transaction fees, and makes it easier for new users to join the network.

ZK Rollup solutions

Several ZK Rollup solutions are currently under development, aiming to improve the scalability and efficiency of different blockchain networks. Some of the most promising ones include:

1. Optimistic Rollups: Optimistic Rollups use a similar approach to ZK Rollups, but instead of using ZK proofs, they use a fraud proof mechanism to ensure the correctness of the off-chain transactions. Optimistic Rollups are currently being developed for Ethereum and other blockchain networks.

2. ZK Sync: ZK Sync is a ZK Rollup solution that is being developed for Ethereum. It can process up to 2,000 tps and reduces the transaction fees by up to 100x.

3. Loopring: Loopring is a decentralized exchange (DEX) that uses ZK Rollups to improve the scalability and efficiency of the exchange. It can process up to 2,000 tps and has a gas cost that is 10x lower than Ethereum's.

Core Architecture

The core architecture of a ZK Rollup consists of two main components: the on-chain smart contract and the off-chain data availability component.

1. On-chain Smart Contract: The on-chain smart contract is responsible for verifying the validity of transactions submitted by users and for updating the state of the ZK Rollup on the main blockchain. The smart contract also maintains a Merkle tree of the transactions included in the ZK Rollup, which is used to generate a proof that can be verified by anyone.

2. Off-chain Data Availability: The off-chain component of the ZK Rollup is responsible for storing the actual transaction data and computing the proofs that are submitted to the smart contract. This off-chain component can be thought of as a separate chain that processes transactions off-chain and periodically submits the final state of the ZK Rollup to the main blockchain. The off-chain component can be implemented in various ways, such as using a sidechain or a state channel network. immudb can be used as an off-chain data aggregator.

The process of using a ZK Rollup involves several steps:

1. Users submit transactions to the off-chain component of the ZK Rollup.

2. The off-chain component processes the transactions and generates a proof of their validity. The proof is submitted to the smart contract on the main blockchain.

3. The smart contract verifies the proof and updates the state of the ZK Rollup on the main blockchain.

4. Users can withdraw their funds from the ZK Rollup by submitting a withdrawal request to the smart contract.

By using Zero-Knowledge proofs, ZK Rollups allow multiple transactions to be bundled together into a single transaction, reducing the amount of data that needs to be stored and processed on the main blockchain. This significantly improves the scalability of the network and reduces transaction fees.

HOW DO ZK-ROLLUPS SCALE ETHEREUM?

Transaction data compression

ZK-rollups extend the throughput on Ethereum’s base layer by taking computation off-chain, but the real boost for scaling comes from compressing transaction data. Ethereum’s block size limits the data each block can hold and, by extension, the number of transactions processed per block. By compressing transaction-related data, ZK-rollups significantly increase the number of transactions processed per block.

ZK-rollups can compress transaction data better than optimistic rollups since they don't have to post all the data required to validate each transaction. They only have to post the minimal data required to rebuild the latest state of accounts and balances on the rollup.

Recursive proofs

An advantage of zero-knowledge proofs is that proofs can verify other proofs. For example, a single ZK-SNARK can verify other ZK-SNARKs. Such "proof-of-proofs" are called recursive proofs and dramatically increase throughput on ZK-rollups.

Currently, validity proofs are generated on a block-by-block basis and submitted to the L1 contract for verification. However, verifying single block proofs limits the throughput that ZK-rollups can achieve since only one block can be finalized when the operator submits a proof.

Recursive proofs, however, make it possible to finalize several blocks with one validity proof. This is because the proving circuit recursively aggregates multiple block proofs until one final proof is created. The L2 operator submits this recursive proof, and if the contract accepts it, all the relevant blocks will be finalized instantly. With recursive proofs, the number of ZK-rollup transactions that can be finalized on Ethereum at intervals increases.

Building a simple ZK-ROLLUP operator with immudb

In a ZK Rollup architecture, the off-chain data availability component is responsible for storing the actual transaction data and computing the proofs that are submitted to the smart contract. We will use immudb to store this data in a tamper-proof and auditable manner, ensuring that the data cannot be modified or deleted.

Here's how it would work:

1. Users submit transactions to the off-chain component of the ZK Rollup.

2. The off-chain component stores the transaction data in immudb, ensuring its integrity and immutability. immudb has inbuilt support to generate merkle proofs for the batched transactions, which can be stored in the ZK-rollup’s state. A cryptographic hash of the Merkle tree’s root of the batched transactions is stored in the on-chain contract, allowing the rollup protocol to track changes in the state of the ZK-rollup.

3. The off-chain component generates a SNARK/STARK proof of the transaction data's validity, which is submitted to the smart contract on the main blockchain.

4. The smart contract verifies the proof and updates the state of the ZK Rollup on the main blockchain.

Let’s define a minimal example by defining the initial structs:

package main

import (
	"context"
	"encoding/json"
	"fmt"
	"math/rand"

	"github.com/codenotary/immudb/pkg/api/schema"
	"github.com/codenotary/immudb/pkg/client"
	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
)

// User represents a user of the ZK Rollup
type User struct {
	address string
	balance int
}

// Transaction represents a transaction on the ZK Rollup
type Transaction struct {
	from     string
	to       string
	amount   int
	sequence int
}

// Define the batch transaction struct
type BatchTransaction struct {
	Transactions []Transaction
}

// InitUsers initializes the users of the ZK Rollup
func InitUsers() []User {
	users := []User{
		{
			address: "user1",
			balance: 100,
		},
		{
			address: "user2",
			balance: 100,
		},
		{
			address: "user3",
			balance: 100,
		},
	}
	return users
}

// InitTransactions initializes the transactions on the ZK Rollup
func InitTransactions(users []User) []Transaction {
	transactions := []Transaction{}
	for i := 0; i < 10; i++ {
		from := users[rand.Intn(len(users))].address
		to := users[rand.Intn(len(users))].address
		amount := rand.Intn(10)
		sequence := i
		transactions = append(transactions, Transaction{from, to, amount, sequence})
	}
	return transactions
}

State commitments

The rollup transitions to a new state after the execution of a new set of transactions. The operator who initiated the state transition is required to compute a new state root and submit to the on-chain contract. This can be done by adding the transaction batch and committing it as a single immudb transaction, which provides the batch merkle root, and inclusion proofs, allowing users to prove a transaction was included in the batch, and also to store the root state to capture the state change.

func main() {
	// Initialize users and transactions
	users := InitUsers()
	transactions := InitTransactions(users)
	batch := BatchTransaction{transactions}
	// Create an immudb client
	immuClient, err := client.NewImmuClient(client.DefaultOptions())
	if err != nil {
		fmt.Println(err)
		return
	}
	defer immuClient.Disconnect()

	// Create a database for the ZK Rollup off-chain component
	dbName := "ZKRollupOffChainComponent"
	_, err = immuClient.CreateDatabaseV2(context.Background(), dbName, nil)
	if err != nil {
		fmt.Println(err)
		return
	}
	immuClient.UseDatabase(context.Background(), &schema.Database{DatabaseName: dbName})

	// Store transaction data in Immudb
	txns := make([]*schema.KeyValue, len(transactions))
	for _, t := range transactions {
		key := []byte(fmt.Sprintf("%s_%s_%d", t.from, t.to, t.sequence))
		value := []byte(fmt.Sprintf("%d", t.amount))
		txns = append(txns, &schema.KeyValue{Key: key, Value: value})
	}
	batchHeader, _ := immuClient.SetAll(context.Background(), &schema.SetRequest{KVs: txns})

	// Batch Merkle root
	fmt.Println("Batch Merkle root: ", batchHeader.BlRoot)
	// Batch transaction ID
	fmt.Println("Batch transaction ID: ", batchHeader.GetId())

	// Verify inclusion of transaction data in the batch Merkle root
	immuClient.VerifiedGetAt(context.Background(), txns[0].Key, batchHeader.GetId())
}

Validity proofs

Validity proofs allow parties to prove the correctness of a statement without revealing the statement itself—hence, they are also called zero-knowledge proofs. ZK-rollups use validity proofs to confirm the correctness of off-chain state transitions without having to re-execute transactions on Ethereum. These proofs can come in the form of a ZK-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) or ZK-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge).

Both SNARKs and STARKs help attest to the integrity of off-chain computation in ZK-rollups, although each proof type has distinctive features.

Proof generation

The ZK-Rollup operator can aggregate the transactions into a single immudb transaction and compile inputs for the proving circuit to compile into a succinct ZK-proof. Inserting this into immudb helps as it generates:

• A Merkle root comprising all the transactions in the single batch immudb transaction.

• Provide inclusion proofs for transactions to prove inclusion in the batch.

This Merkle root reflects the sole change in the ZK-rollup's state.

A very minimal example to illustrate the example is below:

// Define the circuit struct
type RollupCircuit struct {
	BatchTransaction BatchTransaction `gnark:",public"`
}

// Define declares the circuit constraints
func (circuit *RollupCircuit) Define(api frontend.API) error {
	return nil
}

	// Generate a proof of the transaction data's validity
	// and submit it to the smart contract on the main blockchain using GNARK
	// Use gnark to generate a ZK proof that proves the validity of the batch transaction
	var pk groth16.ProvingKey
	var vk groth16.VerifyingKey

	// Define the circuit, generate the proving key and verifying key, and generate the proof
	var circuit RollupCircuit
	circuit.BatchTransaction = batch

	// Generate the proving key and verifying key
	const (
		nbConstraints = 1 << 10
		pkFile        = "rollup.pk"
		vkFile        = "rollup.vk"
	)

	// groth16 zkSNARK: Setup
	ccs, _ := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
	pk, vk, _ = groth16.Setup(ccs)

	// witness definition with some transaction
	assignment := RollupCircuit{}
	witness, _ := frontend.NewWitness(&assignment, ecc.BN254.ScalarField())
	publicWitness, _ := witness.Public()

	// groth16: Prove & Verify
	proof, _ := groth16.Prove(ccs, pk, witness)
	groth16.Verify(proof, vk, publicWitness)
	// Store the batch transaction and ZK proof in immudb

	// Serialize the batch transaction and ZK proof
	batchBytes, err := json.Marshal(batch)
	if err != nil {
		panic(err)
	}

	proofBytes, err := json.Marshal(proof)
	if err != nil {
		panic(err)
	}

	// Store the batch transaction and ZK proof in immudb
	_, err = immuClient.Set(context.Background(), []byte("batch"), batchBytes)
	if err != nil {
		panic(err)
	}

	_, err = immuClient.Set(context.Background(), []byte("proof"), proofBytes)
	if err != nil {
		panic(err)
	}

	fmt.Println("Batch transaction and ZK proof stored in immudb!")

	// Send the proof to the layer 1 (or ethereum) smart contract

	// Verify the proof and update the state of the ZK Rollup on the main blockchain (like ethereum)

You can then save the proof in immudb and send it to the layer 1 solution.

Conclusion

• ZK Rollups represent an innovative and promising solution to the scalability problem faced by many blockchain networks today. By aggregating transactions off-chain and using zero-knowledge proofs to verify their validity on-chain, ZK Rollups can significantly increase the transaction throughput of a blockchain while maintaining its security and decentralization. Several projects, including Loopring, zkSync, and Polygon, have already implemented ZK Rollups or are working on developing their own solutions.

• immudb can play a significant role in supporting ZK Rollups. By providing a secure and efficient off-chain data storage solution, immudb can help enable ZK Rollups to process a larger volume of transactions with greater efficiency and security. In addition, immudb's support for cryptographic proofs, such as inclusion and consistency proofs, can help ensure the validity and integrity of the data stored in the off-chain database.

Reference

• https://ethereum.org/en/developers/docs/scaling/zk-rollups/

• https://github.com/ConsenSys/gnark

• https://immudb.io/

1. Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs)

2. Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go)

3. ZK SNARKS vs ZK STARKS

4. ZK Rollups

Introduction

Zero-knowledge proofs (ZKP) have been around for a while, but it wasn't until the advent of blockchain technology that their potential applications became apparent. ZKPs provide an effective way to prove knowledge of something without revealing any additional information. You can find more information on ZKP in the article here.

Arriqaaq Newsletter

The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs

This article is part of a four series introduction to Zero-Knowledge Proofs: Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs) Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go…

Read more

3 years ago · Farhan

Overview

There are two main types of ZKP systems: zk-SNARKs and zk-STARKs.

zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. zk-SNARKs are a type of ZKP that enables one party (the prover) to convince another party (the verifier) that they possess knowledge of a particular secret without revealing any information about the secret itself. zk-SNARKs are widely used in many blockchain applications such as privacy coins, private smart contracts, and other privacy-oriented applications.

zk-STARK stands for Zero-Knowledge Scalable Transparent Argument of Knowledge. zk-STARKs, on the other hand, are a more recent development in the world of ZKPs. Unlike zk-SNARKs, zk-STARKs do not rely on a trusted setup, making them more transparent and secure. zk-STARKs are more complex and computationally expensive than zk-SNARKs, but they offer more scalability and flexibility.

Interactive and Non-interactive what?

Interactive and non-interactive proofs are two types of proof systems used in cryptography and computer science. In simple terms, a proof system is a method for proving the validity of a statement or computation.

An interactive proof system requires communication between the prover and verifier. The prover sends a series of messages to the verifier, who then checks the messages and sends a response back to the prover. This process continues until the verifier is satisfied with the proof or decides to reject it. The main advantage of interactive proof systems is that they can be more efficient than non-interactive proof systems for certain types of problems.

A non-interactive proof system requires only a single message from the prover to the verifier. This makes it more efficient and easier to use in some scenarios, but also makes it more vulnerable to attacks.

In general, interactive proof systems are more powerful than non-interactive proof systems. They can prove more complex statements and can be more secure in some cases. However, non-interactive proof systems have their own advantages, such as being more efficient and easier to use in certain scenarios.

Explain it like I’m 5

Suppose you have a puzzle where you need to find the two numbers that add up to 10, but you can't just tell someone else what those numbers are. Instead, you need to give them a clue that they can use to check whether your solution is correct or not.

With zk-SNARKs, the clue would be something like this: "I know two numbers that add up to 10, but I can't tell you what they are. However, if you multiply them together, you'll get 21." Now the person checking your answer can multiply the two numbers together and see if they get 21. If they do, they know you solved the puzzle correctly.

However, this method has a downside. While the person checking your answer can be sure that you have the correct solution, they can't learn anything else from your clue. They don't know anything about how you arrived at your solution or what the actual numbers are.

Now, let's look at zk-STARKs. With zk-STARKs, your clue would be more like this: "I know two numbers that add up to 10, and if you follow these specific mathematical steps, you'll be able to verify my solution without me telling you what the numbers are."

In this case, the person checking your answer would use the mathematical steps you provided to verify your solution without actually learning the numbers themselves. This means they can check your answer and also learn additional information, such as how you arrived at your solution and how confident you are in your answer.

So, the main difference between zk-SNARKs and zk-STARKs is that zk-SNARKs give a single proof that can be easily checked, but without revealing much about the solution. Whereas zk-STARKs require a more complex set of mathematical steps to verify, but can reveal more information about the solution.

Explain it like I’m a pro!

Imagine you have a secret number x and a public number y, and you want to prove that you know a number z such that z is the product of x and y, without revealing x or z. In other words, you want to prove that z = x * y without revealing what x or z are.

With zk-SNARKs, you could use a so-called "quadratic arithmetic program" (QAP) to represent this computation as a set of polynomial equations, and then use those equations to generate a proof. However, as we saw in the previous example, the size of the proof depends on the size of the circuit, which can be quite large.

With zk-STARKs, on the other hand, the proof size is independent of the size of the circuit. Instead of representing the computation as a set of equations, you represent it as a sequence of constraints, which are essentially statements of the form "the difference between the values of these two polynomials at this point is equal to zero". In our example, the constraints might look something like:

• x * y - z = 0 (i.e., the product of x and y equals z)

• x^2 - x = 0 (i.e., x is a binary number)

• y^2 - y = 0 (i.e., y is a binary number)

• z^2 - z = 0 (i.e., z is a binary number)

You can then use a process called "low-degree extension" to convert these constraints into a set of polynomial equations, which can be evaluated much more efficiently than with zk-SNARKs. The resulting proof is then a succinct, non-interactive argument that the computation was performed correctly, without revealing any information about the secret inputs x or z.

So, as stated above, the key difference between zk-SNARKs and zk-STARKs is that zk-SNARKs are based on representing computations as a set of polynomial equations, while zk-STARKs are based on representing them as a sequence of constraints. While both approaches can be used to generate succinct, non-interactive proofs of computation, zk-STARKs have the advantage of being independent of the size of the circuit being proven, at the cost of being somewhat more complex to implement and use.

zk-SNARK in Detail

You can play with zksnarks with example code here:

Arriqaaq Newsletter

Unlocking the Power of Zero Knowledge Proofs with Gnark and Go

This article is part of a four series introduction to Zero-Knowledge Proofs: Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs) Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go…

Read more

3 years ago · 1 like · Farhan

The core concept behind zk-SNARKs is that they enable a prover to convince a verifier that they have knowledge of a certain piece of information, without actually revealing that information.

In order to understand how this works, it is important to understand the basics of elliptic curve cryptography. Elliptic curve cryptography is a form of public key cryptography that relies on the difficulty of solving certain mathematical problems.

In particular, elliptic curve cryptography relies on the difficulty of solving the discrete logarithm problem. The discrete logarithm problem is the problem of finding x in the equation:

y=g^x mod p

where y, g, and p are known values.

In elliptic curve cryptography, this problem is generalized to the problem of finding a point P such that:

Q=xP

where Q is a known point, P is a generator point, and x is an unknown scalar.

The basic idea behind zk-SNARKs is to use this mathematical problem to create a proof that a certain statement is true. In order to do this, the prover creates a "circuit" that represents the statement they want to prove. The circuit is essentially a graph of logical operations that takes in some inputs and produces some outputs.

The prover then maps the circuit to an elliptic curve, creating a set of equations that represent the circuit. They then use these equations to generate a proof, which is a set of values that demonstrate that the circuit is true.

The verifier can then use these values to verify the proof, without actually knowing the inputs to the circuit. This is the essence of zk-SNARKs - they allow a prover to create a proof that a certain statement is true, without revealing any information about the statement itself.

Components of the proof

The components of a zk-SNARK proof can be broken down into three parts:

1. Primary Inputs (or Public Inputs): These are the inputs that the verifier can see and are usually known by all parties. Examples include the transaction data, the hash of the previous block, and the public keys of the participants.

2. Auxiliary Inputs (or Private Inputs): These are additional inputs required to prove the validity of the computation. Examples include the private keys of the participants and any other confidential information.

3. Proof: This is a succinct proof that the computation was carried out correctly. It is a small, fixed-size string that can be quickly verified by the verifier. The proof is usually generated by a prover who has access to both the primary and auxiliary inputs.

The zk-SNARK proof is constructed in two phases:

1. Trusted Setup Phase: In this phase, a setup algorithm is run to generate the proving and verification keys. The proving key is used by the prover to generate proofs, while the verification key is used by the verifier to verify the proofs. The setup algorithm is run only once, and the keys generated are used for all subsequent proofs.

2. Proof Generation Phase: In this phase, the prover takes the primary and auxiliary inputs and uses them to generate the proof. This involves performing a series of mathematical calculations on the inputs to produce a statement that can be verified using the verification key. The resulting proof is then sent to the verifier along with the primary inputs.

The verifier then takes the primary inputs and the proof and uses them to verify that the computation was carried out correctly. If the verification is successful, the verifier can be sure that the prover had access to the correct inputs and that the computation was performed correctly without revealing any of the private inputs.

zk-STARK in Detail

A STARK proof system is built on top of the concept of a low-degree polynomial. A polynomial is a function of the form f(x) = a0 + a1x + a2x^2 + ... + anx^n, where ai are coefficients and n is the degree of the polynomial. A polynomial can represent a wide range of functions, including addition, multiplication, and other arithmetic operations.

A low-degree polynomial is a polynomial with a small degree that approximates the computation we want to prove. For example, if we want to prove that 2 + 2 = 4, we can represent this computation as a low-degree polynomial. One way to do this is to define a polynomial f(x) = (x - 2)(x - 2) - 4x + 8. When we evaluate this polynomial at x = 0, we get f(0) = 4, which proves that 2 + 2 = 4.

To create a STARK proof, we need to do the following steps:

1. Construct a polynomial that represents the computation we want to prove.

2. Choose a random point in the polynomial domain and evaluate the polynomial at this point.

3. Repeat step 2 for a number of other random points.

4. Use the values obtained in step 2 and 3 to construct a polynomial that approximates the original polynomial.

5. Publish the STARK proof.

The STARK proof is a set of points that represents the approximation polynomial. The proof can be verified by checking that the polynomial is correct at a small number of random points. This makes the proof scalable and efficient, as it only requires a small number of computations to verify the proof. Here is an example:

Unlike zk-SNARKs, zk-STARKs do not require a trusted setup phase, which makes them more transparent and easier to audit. In a trusted setup phase, a setup ceremony is performed to generate the parameters that are used in the proof system. These parameters are then used to generate the proofs, but if the setup is compromised, the entire system can be broken. With zk-STARKs, there is no need for a trusted setup phase, which makes them more resistant to attacks.

One of the drawbacks of zk-STARKs is that they require more computational resources than zk-SNARKs. This is because the proof size is larger, and the verification process requires more computations. However, with recent advancements in hardware and algorithms, zk-STARKs are becoming more feasible for real-world applications.

Overall, zk-STARKs are a promising technology for providing efficient and scalable proof systems for complex computations. They offer a high degree of transparency and auditability, making them suitable for applications that require a high level of security and trust.

Components

The components of a zk-STARK proof are different from those of a zk-SNARK proof. A zk-STARK proof consists of:

1. Trace: A sequence of values that represents the computation being proven. The trace is a sequence of public inputs, intermediate values, and private inputs.

2. Polynomial: A polynomial that represents the computation being proven. The polynomial is a high-degree polynomial whose coefficients are computed from the trace.

3. Prover's commitment: A commitment to the polynomial that allows the verifier to verify the correctness of the proof without knowing the polynomial.

4. Proof of polynomial evaluations: A proof that demonstrates that certain evaluations of the polynomial are correct. This proof is done using polynomial interpolation and is the core of the zk-STARK protocol.

In contrast to the zk-SNARK proof, the zk-STARK proof does not require a trusted setup phase, and the verification process is more transparent and efficient, making it a promising technology for large-scale blockchain applications.

Performance Comparison

According to the awesome ZKP repo:

According to Elena Nadilinski's slides from Devcon4:

According to Zooko Wilcox's (Zcash) keynote from Devcon4:

It's worth noting that these are broad generalizations, and there are many factors that can affect the performance and security of both zkSNARKs and zkSTARKs in practice. Additionally, different use cases may require different trade-offs between proof size, verification time, and computational complexity, so it's important to carefully evaluate which technology is most appropriate for a particular application.

Conclusion

ZK-SNARKs and ZK-STARKs are two popular types of non-interactive proofs that have widespread use in blockchain technology for their ability to provide privacy and scalability.

While ZK-SNARKs and ZK-STARKs share some similarities, they differ in key ways such as their security assumptions, proof size, and efficiency. The choice between ZK-SNARKs and ZK-STARKs depends on the specific use case and the desired tradeoffs between security, proof size, and efficiency.

In the next article, we will dive deeper into Zk-Rollups and play with some code examples.

In recent years, zero-knowledge proof (ZKP) systems have become increasingly popular due to their ability to provide privacy and security in various applications. Gnark is one such system that has been gaining traction in the ZKP space. It allows developers to build circuits and generate proofs that can be used to verify certain computations without revealing any sensitive information. If you are new to ZK Proofs, read my article on the introduction to this topic.

Arriqaaq Newsletter

The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs

This article is part of a four series introduction to Zero-Knowledge Proofs: Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs) Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go…

Read more

3 years ago · Farhan

However, building a secure and scalable infrastructure to store and manage these proofs can be a challenge. This is where immudb, a lightweight and immutable database, comes in. In this article, we will explore how to integrate Gnark with immudb to securely store and verify circuit proofs.

What is immudb?

immudb is a general purpose immutable database that provides a tamper-proof and auditable ledger with the help of cryptographic proofs. It uses a Merkle tree structure to ensure that every change made to the database is cryptographically verifiable. This makes immudb ideal for storing sensitive information that needs to be audited and secured. You can learn more about immudb here.

https://immudb.io/

Arriqaaq Newsletter

Deep dive into the internals of an immutable database, immudb

Table of Contents Introduction About immudb Basic Building Blocks Append-only logs Merkle Tree Timed BTree Persistence Lifecycle of a transaction in immudb Introduction I've been working on a fast immutable database, called immudb (developed by Codenotary), and was very curious about the immutable nature of storage. I have written this blog to explain how data is…

Read more

3 years ago · Farhan

Every record that is added to immudb is given a unique hash, which is used to construct a Merkle tree. This hash provides a cryptographic proof that the record has not been tampered with.

What is Gnark?

Gnark is a zero-knowledge proof (ZKP) system that allows developers to build circuits and generate proofs that can be used to verify certain computations without revealing any sensitive information. It uses a circuit-based approach to build proofs, which means that developers can build circuits that represent a specific computation and generate a proof that can be used to verify the result of that computation. If you are interested in learning more about GNARK, refer to my article here.

Arriqaaq Newsletter

Unlocking the Power of Zero Knowledge Proofs with Gnark and Go

This article is part of a four series introduction to Zero-Knowledge Proofs: Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs) Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go…

Read more

3 years ago · Farhan

Let's take a simple example to illustrate how to build a circuit using Gnark. Suppose we want to create a circuit that verifies whether a given number x is equal to 42. We can express this as a Boolean constraint using the following equation:

x**3 + x + 5 = y

To build this circuit using Gnark, we can write the following Go code:

package main

import (
	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
)

// CubicCircuit defines a simple circuit
// x**3 + x + 5 == y
type CubicCircuit struct {
	// struct tags on a variable is optional
	// default uses variable name and secret visibility.
	X frontend.Variable `gnark:"x"`
	Y frontend.Variable `gnark:",public"`
}

// Define declares the circuit constraints
// x**3 + x + 5 == y
func (circuit *CubicCircuit) Define(api frontend.API) error {
	x3 := api.Mul(circuit.X, circuit.X, circuit.X)
	api.AssertIsEqual(circuit.Y, api.Add(x3, circuit.X, 5))
	return nil
}

func main() {
	// compiles our circuit into a R1CS
	var circuit CubicCircuit
	ccs, _ := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)

	// groth16 zkSNARK: Setup
	pk, vk, _ := groth16.Setup(ccs)

	// witness definition
	assignment := CubicCircuit{X: 3, Y: 35}
	witness, _ := frontend.NewWitness(&assignment, ecc.BN254.ScalarField())
	publicWitness, _ := witness.Public()

	// groth16: Prove & Verify
	proof, _ := groth16.Prove(ccs, pk, witness)
	groth16.Verify(proof, vk, publicWitness)
}

In this example, we define a circuit using the frontend package provided by Gnark. We then define an input variable x and set its value to 3. We define the constraints using the AssertIsEqual method, which checks whether the expression x**3 + x + 5 = y is true.

We then compile the circuit into a rank-1 constraint system (R1CS) using the ToR1CS method. We generate the proving and verification keys using the Groth16Setup method. We create a proof using the Groth16Prove method and verify it using the `Groth16Verify

Why use ZK Proofs with immudb?

Firstly, immudb's immutable nature makes it ideal for storing the state of the circuit. The circuit's state is an essential part of zero-knowledge proof systems, and immutability guarantees that the state cannot be changed after it has been committed to the database. This is a critical requirement for any system that needs to provide tamper-evident data storage.

Secondly, immudb provides efficient storage and retrieval of key-value pairs, which is the data structure used by gnark to store the circuit's public inputs and proofs. The integration of gnark and immudb allows for efficient and secure storage and retrieval of these key-value pairs.

Thirdly, immudb's support for cryptographic authentication and authorization mechanisms ensures that only authorized parties can access the circuit's data. This provides an additional layer of security and trust in the zero-knowledge proof system.

Lastly, immudb's easy-to-use API and seamless integration with gnark make it a great choice for implementing zero-knowledge proof systems. With immudb, developers can focus on building and verifying the circuit while immudb takes care of secure and tamper-evident storage.

Hence integration of gnark with immudb provides an efficient and secure solution for building and verifying zero-knowledge proof circuits. Immudb's immutable storage, efficient key-value store, cryptographic authentication and authorization mechanisms, and easy-to-use API make it an excellent choice for developers looking to build robust zero-knowledge proof systems.

Integrating Gnark with immudb

Now that we have a basic understanding of immudb and Gnark, let's dive into how we can integrate these two systems to store and verify circuit proofs.

Step 1: Set up immudb

The first step is to set up immudb. You can download the immudb binary from the official website here and install it on your system. Once installed, you can start immudb by running the following command:

wget https://github.com/codenotary/immudb/releases/download/v1.4.1/immudb-v1.4.1-linux-amd64
mv immudb-v1.4.1-linux-amd64 immudb
chmod +x immudb

# run immudb in the foreground to see all output
./immudb

# or run immudb in the background
./immudb -d

This will start the immudb server on the default port 3322. You can also specify a custom port by passing the --port flag.

Step 2: Set up Gnark

Next, we need to set up Gnark. You can install Gnark by running the following command:

go get -u github.com/consensys/gnark/...

This will install Gnark and its dependencies on your system.

Step 3: Build a Circuit and Generate a Proof

Once Gnark is installed, we can start building circuits and generating proofs. In this example, we will build a simple circuit that adds two numbers and generate a proof that can be used to verify the result of the computation.

1. Import the necessary packages in your Go program:

   package main
   
   import (
   	"context"
   	"encoding/json"
   	"fmt"
   
   	"github.com/codenotary/immudb/pkg/client"
   	"github.com/consensys/gnark-crypto/ecc"
   	"github.com/consensys/gnark/backend/groth16"
   	"github.com/consensys/gnark/frontend"
   	"github.com/consensys/gnark/frontend/cs/r1cs"
   )

2. Define the circuit you want to store in immudb. For example, let's say you want to create a circuit that verifies the multiplication of two numbers:

   // Define the circuit struct
   type RollupCircuit struct {
   	BatchTransaction BatchTransaction `gnark:",public"`
   }
   
   // Define declares the circuit constraints
   func (circuit *RollupCircuit) Define(api frontend.API) error {
   	return nil
   }

3. Generate the proving and verification keys for the circuit:

   	// Use gnark to generate a ZK proof that proves the validity of the batch transaction
   	var pk groth16.ProvingKey
   	var vk groth16.VerifyingKey
   
   	// Define the circuit, generate the proving key and verifying key, and generate the proof
   	var circuit RollupCircuit
   	circuit.BatchTransaction = batch
   
   	// Generate the proving key and verifying key
   	const (
   		nbConstraints = 1 << 10
   		pkFile        = "rollup.pk"
   		vkFile        = "rollup.vk"
   	)
   
   	// groth16 zkSNARK: Setup
   	ccs, _ := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
   	pk, vk, _ = groth16.Setup(ccs)
   
   	// witness definition with some transaction
   	assignment := RollupCircuit{}
   	witness, _ := frontend.NewWitness(&assignment, ecc.BN254.ScalarField())
   	publicWitness, _ := witness.Public()
   
   	// groth16: Prove & Verify
   	proof, _ := groth16.Prove(ccs, pk, witness)
   	groth16.Verify(proof, vk, publicWitness)

4. Connect to immudb and store the keys and circuit:

   // connect to immudb
   options := client.DefaultOptions().WithAddress("127.0.0.1").WithPort(3322)
   client, err := client.NewImmuClient(options)
   if err != nil {
       log.Fatal(err)
   }
   
   	// Serialize the batch transaction and ZK proof
   	batchBytes, err := json.Marshal(batch)
   	if err != nil {
   		panic(err)
   	}
   
   	proofBytes, err := json.Marshal(proof)
   	if err != nil {
   		panic(err)
   	}
   
   	// Store the batch transaction and ZK proof in immudb
   	_, err = client.Set(context.Background(), []byte("batch"), batchBytes)
   	if err != nil {
   		panic(err)
   	}
   
   	_, err = client.Set(context.Background(), []byte("proof"), proofBytes)
   	if err != nil {
   		panic(err)
   	}
   

5. Retrieve the keys and circuit from immudb:

   // retrieve the keys and circuit from immudb
   pkBytes, err := client.Get(context.Background(), []byte("proof"))
   if err != nil {
       log.Fatal(err)
   }

That's it! Now you can use the keys and circuit to generate and verify proofs with the circuit stored in immudb in an immutable format.

This article is part of a four series introduction to Zero-Knowledge Proofs:

1. Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs)

2. Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go)

3. ZK SNARKS vs ZK STARKS

4. ZK Rollups

   ---

Introduction

In the previous article, I’ve explained what Zero knowledge proofs (ZKPs) are a and it’s many potential applications, from enhancing privacy in blockchain transactions to improving security in cloud computing. As a programmer, you’d like to get hands on with code for understanding a complex topic. This article provides examples in Go for playing around and understanding ZK Proofs with the help of GNARK.

Gnark is a popular open-source library for building ZKPs in Go. We'll use Gnark to create a simple zero knowledge proof that demonstrates the basic concepts of ZKPs.

https://github.com/ConsenSys/gnark

What is Gnark?

Gnark is a high-performance, open-source library for creating zero-knowledge proofs, specifically zkSNARK applications. We will go into details of SNARKs vs STARKs in the next article as I wanted to explain with code how ZK Proofs work.

Gnark provides a high-level language for specifying the proof's logic, and its API allows developers to easily create, verify, and deploy zero-knowledge proofs. It also includes a built-in compiler that transforms the high-level language into a low-level representation that can be run on a variety of platforms.

Gnark is Go-based. It uses a DSL (domain-specific language) to specify circuits, which are then compiled down to an R1CS (Rank-1 Constraint System) that can be used to generate a proof. Gnark also provides a set of pre-built circuit components, such as SHA-256 and elliptic curve arithmetic, that can be used to build more complex circuits.

Features of Gnark

Gnark comes with a host of features that make it a popular choice among developers. Here are some of its key features:

1. User-Friendly: Gnark has been designed with user-friendliness in mind. Its high-level language, based on the Golang programming language, makes it easy for developers to write and deploy zero-knowledge proofs.

2. Extensible: Gnark is designed to be highly extensible, with support for a variety of cryptographic primitives, including elliptic curve cryptography, pairing-based cryptography, and more.

3. High-Performance: Gnark is highly optimized for performance, with a compiler that generates efficient code that can be run on a variety of platforms.

4. Security: Gnark uses state-of-the-art cryptographic techniques to ensure the security and privacy of its users.

5. Interoperability: Gnark is designed to work seamlessly with other blockchain frameworks, such as Ethereum, and is also compatible with other cryptographic libraries.

Key components of GNARK

1. Circuit Definition Language (Circom): It is a DSL for defining arithmetic circuits. It allows the user to define a circuit that takes in input variables, performs some computations on those variables, and produces an output.

2. Constraint System: It is a collection of constraints that the circuit must satisfy. The constraints are usually defined in terms of arithmetic relations between variables. Gnark provides a variety of constraint systems such as R1CS (Rank-1 Constraint System), PLONK (Permutation-based, Linear-complexity, Overlogarithmic, Non-interactive, Knowledge-proofs), and Aurora.

3. Proving Key and Verification Key: The proving key is used by the prover to generate a proof, while the verification key is used by the verifier to verify the proof. Both keys are generated from the circuit and constraint system.

4. Proof: It is a cryptographic proof generated by the prover, which can be verified by anyone using the verification key.

5. Verifier: It is a component that verifies the proof using the verification key.

6. Witness: It is a set of input variables that satisfy the constraints defined in the circuit.

7. Prover: It is a component that generates a proof using the circuit, constraint system, and witness.

Example

Here's an example in Go that demonstrates how to use some of the components of Gnark.

The Circuit

Our example will use a simple arithmetic circuit that takes a secret input, squares it, and outputs the result. Here's what the circuit looks like in code:

package main

import (
	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
)

// CubicCircuit defines a simple circuit
// x**3 + x + 5 == y
type CubicCircuit struct {
	// struct tags on a variable is optional
	// default uses variable name and secret visibility.
	X frontend.Variable `gnark:"x"`
	Y frontend.Variable `gnark:",public"`
}

// Define declares the circuit constraints
// x**3 + x + 5 == y
func (circuit *CubicCircuit) Define(api frontend.API) error {
	x3 := api.Mul(circuit.X, circuit.X, circuit.X)
	api.AssertIsEqual(circuit.Y, api.Add(x3, circuit.X, 5))
	return nil
}

Generating the Proof

Now that we have our circuit defined, we can use Gnark to generate a zero knowledge proof. Here's what the code looks like:

func main() {
	// compiles our circuit into a R1CS
	var circuit CubicCircuit
	ccs, _ := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)

	// groth16 zkSNARK: Setup
	pk, vk, _ := groth16.Setup(ccs)

	// witness definition
	assignment := CubicCircuit{X: 3, Y: 35}
	witness, _ := frontend.NewWitness(&assignment, ecc.BN254.ScalarField())
	publicWitness, _ := witness.Public()

	// groth16: Prove & Verify
	proof, _ := groth16.Prove(ccs, pk, witness)
	groth16.Verify(proof, vk, publicWitness)
}

In the main function, we create a new Circuit with a secret input of 42. We then define the curve and the proving scheme, and use the ToWitness method to generate a witness for the circuit. Next, we use the Setup method to generate a proving key, and the Prove method to generate a proof.

Verifying the Proof

Finally, we can verify the proof using Gnark. Here's the code:

// Verify the proof
verificationKey := provingKey.VerificationKey()
err = scheme.Verify(proof, verificationKey, witness)
if err != nil {
    panic(err)
}

fmt.Println("Zero knowledge proof generated and verified successfully!")

To verify the proof, we need the verification key that corresponds to the proving key. We generate this key using the VerificationKey method on the proving key. Then, we use the Verify method to verify the proof using the verification key and the witness.

Real World Application

Now let’s dive into multiple examples for gnark. We will look into the following examples:

1. Zero-Knowledge authentication scheme

2. Secure Messaging Protocol

1) Zero-Knowledge authentication scheme

Suppose you want to prove to a service that you know the password to your account without actually revealing the password. Normally, you would simply enter the password and the service would check it against its database. But with zero-knowledge proofs, you can prove that you know the password without actually revealing it.

Here's how it would work:

1. First, you would convert your password into a circuit using a tool like libsnark. The circuit would be a set of mathematical equations that represent your password.

2. Next, you would generate a random string of bits, called a "witness", that satisfies the equations of the circuit.

3. You would then send the circuit and the witness to the service you want to authenticate with, without revealing your password.

4. The service would then run the circuit with the provided witness and verify that the equations hold true. If they do, the service knows that you must know the password that generated the circuit.

5. Finally, the service would grant you access to your account.

In this way, you have proven to the service that you know your password without actually revealing it. This is a powerful application of zero-knowledge proofs that can improve the security and privacy of authentication systems.

Conclusion

Gnark is a powerful library for building zero-knowledge proof circuits in Go. With its intuitive syntax and extensive features, it allows developers to easily create and verify complex proofs with minimal effort.

Although Gnark is still a relatively new library, its active development and growing community suggest that it will continue to evolve and improve over time. As more developers discover the benefits of zero-knowledge proofs and their applications, we can expect Gnark to play a vital role in securing our digital world.

You can visit Consensys website for more.

This article is part of a four series introduction to Zero-Knowledge Proofs:

1. Introduction (The Magic of Proving Without Revealing: An Introduction to Zero-Knowledge Proofs)

2. Example of ZK Proofs in Go (Unlocking the Power of Zero Knowledge Proofs with Gnark and Go)

3. ZK SNARKS vs ZK STARKS

4. ZK Rollups

Introduction

Have you ever played the game "I Spy" as a kid? One person would choose an object in the room, and the other person had to guess what it was by asking yes or no questions. It was a fun way to pass the time, but what if I told you that "I Spy" could actually be a lesson in cryptography?

With Zero Knowledge Proofs, you can prove to your friend that you know what object they chose without revealing how you figured it out. It's like a secret spy mission, but with math instead of gadgets. Zero-knowledge proofs (ZKPs) are a powerful cryptographic tool that allow one party to prove to another that they possess certain knowledge, without revealing what that knowledge is. This has many useful applications, from proving identity and ownership to securing financial transactions and more. In this article, we'll explore the concept of zero-knowledge proofs and how they work, with some examples to help you understand this powerful tool.

What is a Zero Knowledge Proof?

A zero-knowledge proof is a method of proving the validity of a statement without revealing any information beyond the statement's validity. This allows one party (the prover) to prove to another party (the verifier) that they have knowledge of a particular fact or piece of information, without actually revealing that fact or information.
In other words, a zero-knowledge proof is like a magician's trick - the prover is able to prove they know something, but they don't reveal how they know it or what it is they know. This is done using complex mathematical algorithms that generate a proof that can be verified by the verifier.

Want to find an easy way to test it out? Try out with tis awesome example! ZK Crush

Explain it like I’m 5

This is a story about Alex and Jack, who found a cave that has a door in the middle and this door only opens when someone knows the secret to open this door. So Alex knows the secret to open the door in the cave, and wants to prove to Jack that he knows this secret without revealing it to him.

So, Alex and Jack agree on naming both paths (let's call them paths A and B).

1. In the first step, Alex is inside the cave and he can choose whichever path he wants, in this particular case “A” or “B”.

2. After Alex choose “A”, Jack enters the cave and ask him to come outside appearing from the “B” path.

3. Because Alex knows the secret to open the door, he came out for the “B” path and Jack can verify that he actually knows the secret.

To summarise, the activity that Alex and Jack repeat is:

1. Alex enters the cave.

2. Alex takes a random path.

3. Jack enters the cave.

4. Jack asks Alex to come from a random path.

5. Alex returns using the path Jack mentioned

How do Zero Knowledge Proofs Work?

At a high level, the idea is to create a secure and private conversation between the prover and the verifier, where the prover convinces the verifier that they have the required knowledge without actually revealing it. The conversation usually consists of multiple rounds of communication, with each round involving the prover and verifier exchanging messages and performing some calculations.

During these rounds, the prover uses their knowledge to create a proof that they possess the information that the verifier is interested in. The proof is typically in the form of a mathematical statement or calculation, which the verifier can check to confirm that the prover is telling the truth without learning any additional information.

To ensure the privacy and security of the communication, zero knowledge proofs rely on complex mathematical algorithms and cryptographic techniques. These techniques are designed to ensure that the proof is valid, while preventing the prover from being able to generate a fake proof or the verifier from being able to extract any additional information beyond what is necessary.

It is hard to understand ZK proofs without concrete examples. There are multiple examples in this article, but before that, there are some conditions to be aware of.

Conditions for Zero Knowledge Proofs

1. Completeness: If the statement being proven is true, then an honest verifier will be convinced of its truth by an honest prover.

2. Soundness: If the statement being proven is false, then no cheating prover can convince an honest verifier that it is true.

3. Zero-knowledge: The verifier learns nothing other than the fact that the statement being proven is true. In other words, the proof does not reveal any additional information beyond the truth of the statement being proven.

The zero-knowledge condition is the most important of these three conditions. A zero-knowledge proof must not reveal any information about the secret being proved other than its truth. The verifier should not be able to learn anything else about the secret being proved, such as its value or any other related information.

Examples, examples, and more examples!

To make this more understandable, let's consider an example of a zero-knowledge proof in action with multiple examples:

Example #1: Password Verification

Suppose that you have a piece of information, such as a password or a secret phrase, and you want to prove to someone that you know it, without revealing the information itself.

You can use a zero-knowledge proof to do this as follows:

1. You and the verifier agree on a mathematical puzzle or problem, such as finding the factors of a large number.

2. You then use your knowledge of the secret information to solve the puzzle or problem. For example, you could use your knowledge of the password to compute the factors of a specially chosen number.

3. You present your solution to the verifier, who can verify that your solution is correct without learning anything about your secret information.

4. You repeat this process multiple times with different puzzles or problems, to convince the verifier that you truly know the secret information.

The verifier can be confident that you know the secret information, because you were able to solve the mathematical puzzles or problems, which is only possible if you possess the necessary knowledge. However, because the verifier only sees the solutions to the puzzles, and not the secret information itself, the proof is zero-knowledge.

In this example, the mathematical puzzle or problem serves as a stand-in for the secret information, and the solution to the puzzle serves as a proof that you know the secret. The verifier does not gain any additional knowledge beyond the fact that you know the secret, and the proof does not reveal anything about the secret information itself.

In the simple example I gave, the conditions for a zero-knowledge proof are met as follows:

1. Completeness: The proof is complete, because if you truly know the secret information, you will be able to solve the mathematical puzzles or problems.

2. Soundness: The proof is sound, because the verifier can verify that your solution to the mathematical puzzle or problem is correct, using a publicly known algorithm.

3. Zero-knowledge: The proof is zero-knowledge, because the verifier only learns that you know the secret information, and nothing else. The verifier does not learn anything about the secret information itself, such as the password or the factors of the number, beyond the fact that you know it. Therefore, the proof does not reveal any additional information about the secret.

Example #2: Flip a coin

Suppose you have two coins, one of which is biased to come up heads more often than tails, and the other of which is fair (i.e., comes up heads and tails with equal probability). You know which coin is which, but you want to prove to a friend that you can tell them apart, without revealing which coin is which.

Here's how you can use a zero-knowledge proof to do this:

1. You randomly select one of the two coins, and you flip it several times in secret.

2. You present the resulting sequence of coin flips to your friend, without revealing which coin you flipped.

3. Your friend then flips one of the two coins in front of you, and asks you to identify which coin it is.

4. You can then use your knowledge of the secret sequence of coin flips to identify which coin your friend flipped, without revealing which coin is which.

5. You repeat this process several times with different secret sequences of coin flips, to convince your friend that you can truly tell the coins apart.

In this example, the sequence of coin flips serves as a stand-in for the knowledge of which coin is biased and which is fair. By using a different secret sequence of coin flips for each round, you can prove that you truly know which coin is which, without revealing which coin is biased and which is fair.

The zero-knowledge aspect of the proof comes from the fact that your friend does not learn anything about which coin is biased and which is fair beyond the fact that you can tell them apart. Your friend does not learn which coin you flipped or which sequence of flips you used to make your determination, so the proof does not reveal any additional information about the coins themselves.

The conditions for a zero-knowledge proof are met in the coin-flipping example as follows:

1. Completeness: The proof is complete, because if you truly know which coin is biased and which is fair, you will be able to tell them apart based on the sequence of coin flips, and your friend will be convinced that you can do so.

2. Soundness: The proof is sound, because your friend can verify that you are correctly identifying the coins, by flipping one of them in front of you and checking your answer. This means that your friend can be confident that you are not simply guessing or randomly choosing a coin.

3. Zero-knowledge: The proof is zero-knowledge, because your friend does not learn anything about which coin is biased and which is fair beyond the fact that you can tell them apart. Your friend does not learn which coin you flipped, or which sequence of coin flips you used to make your determination. Therefore, the proof does not reveal any additional information about the coins themselves, beyond the fact that you know which is biased and which is fair.
   

Example #3: Guess the prime number

Imagine you have two large prime numbers, p and q, and you want to prove to a friend that you know their product n=pq, without revealing the values of p and q. How can you prove this using a zero-knowledge proof?

One way to do this is to use a variation of the RSA algorithm. Here's how it works:

1. You choose a random number r, and compute a new number s = r^2 mod n.

2. You send s to your friend, along with a claim that you know the values of p and q such that n = pq.

3. Your friend chooses a random number e (either 0 or 1) and sends it to you.

4. If e=0, you send r to your friend as a proof that you know the values of p and q. If e=1, you compute and send s/r to your friend.

5. Your friend can verify that you either know p and q (in the case where e=0), or that s/r is a valid square root of s mod n (in the case where e=1), without learning anything about the values of p and q themselves.

This is a zero-knowledge proof, because your friend learns nothing about p and q beyond the fact that their product is n, and your ability to prove this fact without revealing any additional information. The conditions of completeness, soundness, and zero-knowledge are met, because you can prove that you know p and q by sending r, or by computing s/r and sending that instead (if e=1), and your friend can verify that you know p and q or that s/r is a valid square root of s mod n, without learning anything else about the values of p and q.

The conditions for zero-knowledge proofs are met in the following way:

1. Completeness: The prover knows a prime number p and a factorization of n as p*q, and can prove this to the verifier by computing q = n/p and sending both p and q to the verifier.

2. Soundness: The prover cannot prove knowledge of any p and q that do not correctly factorize n, because there is no way to find a pair of numbers that correctly factorize n without knowing its prime factors.

3. Zero knowledge: The prover does not reveal any information about their knowledge of the prime factors of n beyond the fact that they know a prime number p and its corresponding factor q, which is already known to the verifier. Thus, the prover does not reveal any additional information about the prime factors of n.
   

Types of Zero Knowledge Proofs

There are several types of zero-knowledge proofs, each with their own strengths and weaknesses. Some of the most common types of zero-knowledge proofs include:

1. Interactive Zero Knowledge Proofs: In this type of zero-knowledge proof, the prover and the verifier interact with each other to establish the proof. The prover sends a series of messages to the verifier, who responds with challenges. The prover then uses these challenges to generate further responses until the proof is established.

2. Non-Interactive Zero Knowledge Proofs: This type of zero-knowledge proof requires only one message from the prover to the verifier. The proof is established without any further interaction between the two parties.

3. Statistical Zero Knowledge Proofs: In a statistical zero-knowledge proof, the proof is established with high probability but not with absolute certainty. This means that there is a small chance that the proof is incorrect, but this chance is so small that it is considered negligible.

4. Succinct Non-Interactive Argument of Knowledge (SNARKs): SNARKs are a type of zero-knowledge proof that are highly efficient and scalable. They are used in a variety of applications, including blockchain technology, machine learning, and more. Like other zero-knowledge proof systems, SNARKs allow one party (the prover) to prove to another party (the verifier) that they have knowledge of a certain piece of information, without revealing any other details about that information.

   
   The key feature of SNARKs is that they are "succinct", meaning that the proof size is much smaller than the size of the original data being proven. This makes SNARKs highly efficient and scalable for use in a variety of applications, including blockchain technology, machine learning, and more.

Applications of Zero Knowledge Proofs

Here are some of the most common applications of ZKPs:

1. Identity Verification - ZKPs can be used to prove that you are who you say you are, without revealing any personal information. This has applications in online authentication, digital signatures, and access control.

2. Ownership Verification - ZKPs can be used to prove that you own a particular asset, without revealing any information about the asset itself. This has applications in supply chain management, intellectual property protection, and digital asset ownership.

3. Financial Transactions - ZKPs can be used to prove the validity of financial transactions, without revealing any information about the transaction itself. This has applications in cryptocurrency, online payments, and other digital financial transactions.

4. Data Privacy - ZKPs can be used to protect the privacy of sensitive data, by allowing parties to perform computations on the data without revealing the data itself. This has applications in healthcare, finance, and other industries that require the processing of sensitive data.

5. Elections - ZKPs can be used to ensure the integrity of elections, by allowing voters to verify that their vote was counted without revealing how they voted. This has applications in online voting and other forms of electronic voting.

6. Cryptography - ZKPs are a powerful tool in modern cryptography, allowing for secure communication and authentication. This has applications in military and intelligence operations, as well as in the private sector for secure messaging and other applications.

Zero Knowledge Proofs and Compliance

Zero-knowledge proofs (ZKPs) can be used in Kubernetes and regulatory compliance in a variety of ways. Here are some examples:

1. Kubernetes Security - ZKPs can be used to improve the security of Kubernetes clusters by providing a way to authenticate nodes without revealing any sensitive information. For example, ZKPs can be used to ensure that nodes in a Kubernetes cluster are running authorized software without revealing the specific details of the software.

2. Compliance Auditing - ZKPs can be used to prove compliance with regulations such as GDPR, HIPAA, and PCI DSS without revealing any sensitive information. For example, ZKPs can be used to prove that data has been encrypted and stored securely without revealing the specific details of the encryption or storage mechanism.

3. Access Control - ZKPs can be used to provide secure access control to Kubernetes resources without revealing any sensitive information. For example, ZKPs can be used to prove that a user has the required permissions to access a specific Kubernetes resource without revealing the specific details of those permissions.

4. Secure Data Sharing - ZKPs can be used to securely share data between Kubernetes clusters or between different organizations without revealing any sensitive information. For example, ZKPs can be used to prove that a specific piece of data has been shared between two parties without revealing the contents of the data.

5. Auditing Kubernetes Deployments - ZKPs can be used to prove that Kubernetes deployments are operating as intended without revealing the details of the deployment or the data being processed. This can help ensure that Kubernetes deployments are functioning as expected and can be useful for auditing purposes.

By allowing parties to prove things without revealing sensitive information, ZKPs can help protect against data breaches and ensure regulatory compliance. As the use of Kubernetes continues to grow, we can expect to see more and more applications of ZKPs in this area.

In the coming post, we will dive deeper into the following inshaAllah.

• Example in Golang for ZK Proofs

• SNARKs / STARKs

• ZK Rollups

Before we dive deeper into the different data layouts on disk, it is important to understand the various data layout patterns. In a database, there are different ways in which data is written to disk, including row-based and column-based data layout.

1. Row-based storage: In row-based storage, data for a single row of a table is stored together in one block or page on disk. This means that all the columns of a given row are stored together, which can make it efficient for operations that need to retrieve an entire row of data at once, such as SELECT queries. However, row-based storage can be less efficient for operations that only need to access a subset of the columns in a table.

2. Column-based storage: In column-based storage, each column of a table is stored separately on disk, which means that all the values for a given column are stored together. This can be more efficient for operations that only need to access a subset of the columns in a table, as the database can avoid reading in unnecessary data. Column-based storage can also be more efficient for certain types of queries, such as those that involve aggregations or calculations that only involve one column.

3. Hybrid storage: Some databases use a hybrid storage approach that combines both row-based and column-based storage. In this approach, the database may store frequently accessed columns in a column-based format and less frequently accessed columns in a row-based format. This can provide the benefits of both approaches, but can also be more complex to implement and manage.

4. Compressed (or Block Compressed) storage: Databases can also use compression techniques to reduce the amount of data that needs to be written to disk. For example, the database may use a compression algorithm to reduce the size of data before writing it to disk, and then decompress it when reading it back into memory. This can help to save disk space and reduce I/O operations, but can also add some overhead to the database's processing.

Row-Oriented Data Layout

Row-based storage algorithms work by storing the data for each row of a table together in a block or page on disk. When a database needs to read or write a row of data, it reads or writes the entire block that contains the row.

Here's an example of how a row-based storage algorithm might work:

Suppose we have a table with the following columns: "ID", "Name", "Age", and "Address". Each row of the table contains a unique ID, along with the name, age, and address of a person.

With row-based storage, the data for each row of the table is stored together in a block or page on disk. For example, the first row might be stored in a block that contains the following data:

ID | Name | Age | Address

1 | John | 30 | 123 Main Street

The second row might be stored in a block that contains the following data:

ID | Name | Age | Address

2 | Mary | 25 | 456 Elm Street

When the database needs to read a row of data, it reads the entire block that contains the row. For example, if we want to retrieve the data for the row with ID 1, the database would read the block that contains that row, which includes all the columns of the table.

Similarly, when the database needs to write a row of data, it writes the entire block that contains the row. For example, if we want to update the age of the person with ID 1, the database would write the entire block that contains that row, including the updated age.

Row-based storage can be efficient for operations that need to retrieve or update entire rows of data, but can be less efficient for operations that only need to access a subset of the columns in a table. Column-based storage can be more efficient for those types of operations.

Column-Oriented Data Layout

Column-based storage algorithms store data by organizing it into columns, rather than rows. In a column-based storage model, each column is stored separately on disk, with all values for that column grouped together. This allows for more efficient and selective access to data, as queries can be optimized to only access the columns needed for a particular operation.

When a new row is added to the database in a column-based storage system, the values for each column are added to the appropriate column files. This means that the same column file can be updated independently of the other columns, which can result in better write performance in certain situations. Additionally, because column data is stored together, it can be compressed more efficiently, reducing the amount of storage required on disk.

In order to retrieve data from a column-based storage system, a query is executed that specifies which columns are needed for the operation. The system retrieves only the relevant columns from disk, rather than retrieving the entire row as in a row-based storage system. This can result in faster query performance and reduced I/O overhead.

A popular example of a column-based storage algorithm is Apache Cassandra, which is a highly scalable and distributed database system used by many large companies, such as Netflix and Twitter.

In Cassandra, data is stored in a distributed fashion across multiple nodes, and each node stores data in a column-family format, which is a collection of columns. Within each column family, columns are stored separately on disk, with all values for a particular column stored together. Each column can have its own sorting and indexing, which enables highly efficient and selective access to data.

When new data is added to a column family, the values for each column are added to the appropriate column file on disk. This means that the same column file can be updated independently of the other columns, which can result in better write performance in certain situations. Additionally, because column data is stored together, it can be compressed more efficiently, reducing the amount of storage required on disk.

Wide-column stores

Column-oriented databases are not similar to wide column stores, such as BigTable or HBase, where data is stored using a column-family data model. In a wide column store, data is organized into column families, which are sets of columns that are related to each other. Each column family can have a different set of columns, and each column can have a different data type. This layout is best for storing data retrieved by a key or a sequence of keys.

The data in a wide column store is stored in rows, with each row identified by a unique row key. Within each row, the data is stored in columns, with each column identified by a column name. The values of the columns can be of different data types, such as strings, integers, or binary data.

One of the key features of wide column stores is their ability to scale horizontally across multiple nodes, which makes them well-suited for handling large volumes of data. They also support flexible schema designs, as the data model can be easily adapted to changing requirements without requiring a schema migration.

Examples of wide column stores include Apache Cassandra, Apache HBase, and Amazon DynamoDB. They are commonly used in applications such as real-time analytics, high-traffic web applications, and large-scale content management systems.

Pros vs Cons

Row-oriented databases and column-oriented databases have their own pros and cons. I listed a few here that can hopefully help you make a decision.

Row-based and column-based storage are two different approaches to storing data in a database. Each approach has its own advantages and disadvantages, which can make one more suitable than the other depending on the specific use case. Here are some of the key pros and cons of each approach:

Row-based storage:

Pros:

• Best suited for OLTP applications.

• Works well for transactional workloads where data is frequently updated, as each row is stored contiguously on disk and can be easily updated in-place.

• Good for accessing entire records, as all columns are stored together in each row.

• Generally easier to understand and work with for developers and DBAs.

Cons:

• Can be inefficient for analytical workloads where queries only need to access a subset of columns from a large table, as all columns must be read even if only a few are needed.

• Can lead to I/O inefficiencies if the table contains a large number of columns, as reading an entire row can result in reading many unneeded columns.

• Can be less efficient for compressing data, as each row may contain many columns with repeated values.

Column-based storage:

Pros:

• Best suited for OLAP application.

• Efficient for analytical workloads, as queries can be designed to read only the columns needed for the analysis, reducing I/O and improving query performance.

• Can be more efficient for compressing data, as repeated values in each column can be easily identified and stored more compactly.

• Good for handling large data sets, as only the needed columns are read, reducing the amount of data read from disk.

Cons:

• Can be less efficient for transactional workloads where data is frequently updated, as each column is stored separately and must be updated in multiple locations.

• Can be more complex to manage and understand for developers and DBAs, as data is stored across multiple columns.

• Can be less efficient for accessing entire records, as each column must be read separately and assembled into a row.

Row-based storage is well-suited for transactional workloads with small to medium-sized tables, while column-based storage is better for analytical workloads with large tables and complex queries that access a subset of columns.

We will dive deeper into the data layout in the next article.

#database #sql #algorithms #systemdesign #datastructures #sql #nosql

Arriqaaq Newsletter

#Day9 - Storage Engines (Fragmented LSM Tree)

Fragmented Log-Structured Merge Trees (FLSM) is a database storage algorithm that uses skip lists to manage the structure of the data. It was first introduced in the paper published by #VMware Research on #PebblesDB In this algorithm, the data is stored in fragments or chunks in a log-structured manner. The data is kept in a sorted manner, and the search…

Read more

3 years ago · Farhan

TLDR, ART increased performance of my database 2x when compared to a skiplist. The code for an Adaptive Radix Trie (ART) implemented by me is below.

GitHubarriqaaq

The Need

I was in search of a data structure to support prefix searches for keys in a Redis like in-memory store that I'd made called FlashDB. Currently, string key-value pairs were stored on the backend as a skip list. The design choice was not the best, but to support fast query speed and prefix searches, I assumed ordering the keys in lexical order would be helpful. It wasn't efficient and the benchmarks showed the performance of simple key-value searches would be very slow.

The algorithms behind search engines are nearly countless. The most common one used is a prefix tree, also known as a Trie. Tries are used for building key-value stores and indexes, after search trees (like B-trees and red-black trees) and hash tables.

The Search

There are 3 kinds of data structures to maintain indexes in memory.

• Binary tree: T tree is old and not optimized for modern CPU architecture. B+ tree is more cache-friendly but tempers with the predictive comparison from modern CPU. FAST is great for modern CPU architectures, but it does not support incremental updates.

• Hash table: Efficient in memory indexes but only support single-point queries. Updates and deletion can be expensive when they require reorganising the hash table.

• Tries: Have a number of very appealing properties - for example, the height of a trie is independent of the number of keys it contains, and a trie requires no rebalancing when updated. The complexity of tries grows with the length of the key, not the number of elements in the structure. They suffer bad space performance when the keys are sparse.

Paper Trail had published this interesting article long back on optimised Radix Tries. Radix Tries have good properties like:

• Complexity depends on key length, not the number of elements

• There no need for rebalancing: two different insert orders result in the same tree

• Keys are store in lexicographical order

• Keys are implicitly stored in the path

What’s wrong with ordinary tries?

Let’s imagine how we might implement a trie, as simply as we can. A single node in a trie corresponds to a key prefix; a sequence of characters that is a prefix of one or more keys in the tree. But we know what its prefix is by the path we took to get to it, so we don’t need to store it. All we need is a way to find its children.

To find the children, we need to know how to get to all the nodes that represent key prefixes one character longer than the current one, and that’s what the children array is for. Here we’re assuming an 8-bit alphabet, with 256 possible characters per letter, or a fan-out of 256.

The paper calls the width of a single character the span of the trie, and it’s a critical parameter as it determines a trade-off between the fan-out of each node, and the height of the trie, since if you can pack more of a value into a single node by having a larger span, you need fewer nodes to describe the whole string.

The problem, as you can no-doubt see, is that there’s a possibility of a lot of wasted space in each node. Imagine a radix trie containing foo, fox and fat. The root node would have one valid pointer, to f, which would have two valid pointers, to a and o. a would have a pointer to t, and o would have pointers to o and x.

So our trie would have 6 nodes, but a total of 6 * 26 = 156 pointers, of which 150 / 156 = 96% are empty and therefore wasted space! At 8-bytes per pointer, that’s already over 1K wasted space to store just 9 bytes of information.

The paper introduces ART, an adaptive radix tree (trie) for efficient indexing in main memory. It quotes the lookup performance surpasses highly tuned, read-only search trees, while supporting very efficient insertions and deletions as well. At the same time, ART is very space efficient and solves the problem of excessive worst-case space consumption, which plagues most radix trees, by adaptively choosing compact and efficient data structures for internal nodes. It maintains the data in sorted order, which enables additional operations like range scan and prefix lookup.

Perfect! Now time to implement it.

The Implementation

ART uses 3 techniques to make radix tree a viable option:

• Dynamic node size

• Path compression

• Lazy expansion

Dynamic node size

Inner nodes of the radix tree use a "span" s, they store 2^s pointers. So for a k-bit key, the height of the tree is k/s. Radix trees are smaller than binary trees if the number of elements n is n > 2^(k/s). For pure lookups, a higher span is better. But space usage is bad because most of the pointers are nulls.

ART uses a large span with different fanouts. When inserting, if the node is too small, it is replaced by a larger one. If underfull, the node is replaced with a smaller one.

They use a span of 8 bits to ease the implementation (the radix tree used in Linux uses a 6 bits span). Because changing the fanout of the node for every update operation would be counterproductive, They choose 4 different node sizes:

• Node4 is the smaller inner node, it contains a maximum of 4 children nodes stored as arrays

• Node16 is a larger Node4. For efficient lookup, it can use SIMD operations

• Node48 uses an indirection layer to store children node

• Node256 uses a single array of 2^span = 256 length

func newNode4() *Node {
	in := &innerNode{
		nodeType: Node4,
		keys:     make([]byte, Node4Max),
		children: make([]*Node, Node4Max),
		meta: meta{
			prefix: make([]byte, MaxPrefixLen),
		},
	}
	return &Node{innerNode: in}
}

func newNode16() *Node {
	in := &innerNode{
		nodeType: Node16,
		keys:     make([]byte, Node16Max),
		children: make([]*Node, Node16Max),
		meta: meta{
			prefix: make([]byte, MaxPrefixLen),
		},
	}

	return &Node{innerNode: in}
}

func newNode48() *Node {
	in := &innerNode{
		nodeType: Node48,
		keys:     make([]byte, Node256Max),
		children: make([]*Node, Node48Max),
		meta: meta{
			prefix: make([]byte, MaxPrefixLen),
		},
	}

	return &Node{innerNode: in}
}

func newNode256() *Node {
	in := &innerNode{
		nodeType: Node256,
		children: make([]*Node, Node256Max),
		meta: meta{
			prefix: make([]byte, MaxPrefixLen),
		},
	}

	return &Node{innerNode: in}
}

Path compression

If the sequence of single-child nodes does not end in a leaf, ART uses path compression. This collapses the sequence of nodes, but into the node at the end of the sequence that has more than one child. That is, consider inserting CAST and CASH into an empty trie; path compression would create a node at the root that has the CAS prefix, and two children, one for T and one for H. That way the trie doesn’t need individual nodes for the C->A->S sequence.

Lazy expansion

Two techniques are described that allows the trie to shrink its height if there are nodes that only have one child. They reduce the impact of having either strings with a unique suffix (lazy expansion) or a common prefix (path compression). Figure 6 in the paper illustrates both techniques clearly.

func (n *Node) shrink() {
	in := n.innerNode

	switch n.Type() {
	case Node4:
		c := in.children[0]
		if !c.IsLeaf() {
			child := c.innerNode
			currentPrefixLen := in.prefixLen

			if currentPrefixLen < MaxPrefixLen {
				in.prefix[currentPrefixLen] = in.keys[0]
				currentPrefixLen++
			}

			if currentPrefixLen < MaxPrefixLen {
				childPrefixLen := min(child.prefixLen, MaxPrefixLen-currentPrefixLen)
				copyBytes(in.prefix[currentPrefixLen:], child.prefix, childPrefixLen)
				currentPrefixLen += childPrefixLen
			}

			copyBytes(child.prefix, in.prefix, min(currentPrefixLen, MaxPrefixLen))
			child.prefixLen += in.prefixLen + 1
		}

		replaceNode(n, c)

	case Node16:
		n4 := newNode4()
		n4in := n4.innerNode
		n4in.copyMeta(n.innerNode)
		n4in.size = 0

		for i := 0; i < len(n4in.keys); i++ {
			n4in.keys[i] = in.keys[i]
			n4in.children[i] = in.children[i]
			n4in.size++
		}

		replaceNode(n, n4)

	case Node48:
		n16 := newNode16()
		n16in := n16.innerNode
		n16in.copyMeta(n.innerNode)
		n16in.size = 0

		for i := 0; i < len(in.keys); i++ {
			idx := in.keys[byte(i)]
			if idx > 0 {
				child := in.children[idx-1]
				if child != nil {
					n16in.children[n16in.size] = child
					n16in.keys[n16in.size] = byte(i)
					n16in.size++
				}
			}
		}

		replaceNode(n, n16)

	case Node256:
		n48 := newNode48()
		n48in := n48.innerNode
		n48in.copyMeta(n.innerNode)
		n48in.size = 0

		for i := 0; i < len(in.children); i++ {
			child := in.children[byte(i)]
			if child != nil {
				n48in.children[n48in.size] = child
				n48in.keys[byte(i)] = byte(n48in.size + 1)
				n48in.size++
			}
		}

		replaceNode(n, n48)
	}
}

Alternatively, the node can also grow as required when the children are more than the maximum keys a node can hold.

func (n *innerNode) grow() {
	switch n.nodeType {
	case Node4:
		n16 := newNode16().innerNode
		n16.copyMeta(n)
		for i := 0; i < n.size; i++ {
			n16.keys[i] = n.keys[i]
			n16.children[i] = n.children[i]
		}
		replace(n, n16)

	case Node16:
		n48 := newNode48().innerNode
		n48.copyMeta(n)

		index := 0
		for i := 0; i < n.size; i++ {
			child := n.children[i]
			if child != nil {
				n48.keys[n.keys[i]] = byte(index + 1)
				n48.children[index] = child
				index++
			}
		}

		replace(n, n48)

	case Node48:
		n256 := newNode256().innerNode
		n256.copyMeta(n)

		for i := 0; i < len(n.keys); i++ {
			child := (n.findChild(byte(i)))
			if child != nil {
				n256.children[byte(i)] = *child
			}
		}

		replace(n, n256)

	case Node256:
	}
}

The Prefix Search Method

// Prefix Scan
tree.Insert([]byte("api"), "bar")
tree.Insert([]byte("api.com"), "bar")
tree.Insert([]byte("api.com.xyz"), "bar")
leafFilter := func(n *art.Node) {
	if n.IsLeaf() {
		fmt.Println("value=", string(n.Key()))
	}
}
tree.Scan([]byte("api"), leafFilter)

The Benchmarks

I tested loading a dictionary of 235886 words into each tree. Here are the results.

// ART tree
BenchmarkWordsArtTreeInsert-16   14	  79622476 ns/op  46379858 B/op	 1604123 allocs/op
BenchmarkWordsArtTreeSearch-16   43	  28123512 ns/op         0 B/op	       0 allocs/op

// Radix tree
BenchmarkWordsRadixInsert-16     12	  96886770 ns/op  50057340 B/op	 1856741 allocs/op
BenchmarkWordsRadixSearch-16     33	  40109553 ns/op         0 B/op	       0 allocs/op

// Skiplist
BenchmarkWordsSkiplistInsert-16   4	 271771239 ns/op  32366958 B/op	 1494019 allocs/op
BenchmarkWordsSkiplistSearch-16   8	 135836216 ns/op         0 B/op	       0 allocs/op

How did it improve flashdb? Well, almost twice as fast! Here are the benchmarks for the string store:

Skip list

BenchmarkFlashDBPutValue64B-16      	  159992	      7208 ns/op	    1461 B/op	      19 allocs/op
BenchmarkFlashDBPutValue128B-16     	  175634	      9499 ns/op	    2003 B/op	      19 allocs/op
BenchmarkFlashDBPutValue256B-16     	  148362	      9278 ns/op	    3322 B/op	      19 allocs/op
BenchmarkFlashDBPutValue512B-16     	  120865	     16542 ns/op	    6037 B/op	      19 allocs/op
BenchmarkFlashDBGet-16              	 1881042	       643.9 ns/op	      32 B/op	       2 allocs/op

ART Trie

BenchmarkFlashDBPutValue64B-16     	  204318	      5129 ns/op	    1385 B/op	      19 allocs/op
BenchmarkFlashDBPutValue128B-16    	  231177	      5318 ns/op	    1976 B/op	      16 allocs/op
BenchmarkFlashDBPutValue256B-16    	  189516	      6202 ns/op	    3263 B/op	      15 allocs/op
BenchmarkFlashDBPutValue512B-16    	  165580	      8110 ns/op	    5866 B/op	      16 allocs/op
BenchmarkFlashDBGet-16             	 4053836	       294.9 ns/op	      32 B/op	       2 allocs/op

References

• Beating hash tables with trees? The ART-ful radix trie

• How Radix trees made blocking IPs 5000 times faster

• Reading notes: The Adaptive Radix Tree
  
  

Fragmented Log-Structured Merge Trees (FLSM) is a database storage algorithm that uses skip lists to manage the structure of the data. It was first introduced in the paper published by #VMware Research on #PebblesDB

In this algorithm, the data is stored in fragments or chunks in a log-structured manner. The data is kept in a sorted manner, and the search for the data is performed through the use of skip lists. Skip lists are a type of data structure that provides fast search times in large datasets. The skip lists are used to index the fragments, which in turn allows for fast access to the data. The merge operation in FLSM combines smaller fragments into larger ones to reduce the number of I/O operations required, which results in improved performance.

Understanding the Problem

One fundamental problem that remains is the high write amplification of key-value stores for write-intensive workloads. Write amplification is the ratio of total write IO performed by the store to the total user data. High write amplification is bad because:

• It increases the load on storage devices such as SSDs, which have limited write cycles before the bit error rate becomes unacceptable

• results in frequent device wear out and high storage

• reduces write throughput

• Write amplification also reduces write throughput: in the RocksDB [20] key-value store, it results in write throughput being reduced to 10% of read throughput 

Key-value stores such as LevelDB and RocksDB are built on top of the log-structured merge trees (LSM) data structure, and their high write amplification can be traced back to the data structure itself (§2). LSM stores maintain data in sorted order on storage, enabling efficient querying of data. However, when new data is inserted into an LSMstore, existing data is rewritten to maintain the sorted order, resulting in large amounts of write IO.

Key idea to reduce write amplification

The Fragmented Log-Structured Merge Trees (FLSM), combines ideas from the Skip List and Log-Structured Merge trees data structures along with a novel compaction algorithm. FLSM strikes at the root of write amplification by drastically reducing (and in many cases, eliminating) data rewrites, instead fragmenting data into smaller chunks that are organized using guards on storage. Guards allow FLSM to find keys efficiently. Write operations on LSM stores are often stalled or blocked while data is compacted (rewritten for better read performance); by drastically reducing write IO, FLSM makes compaction significantly faster, thereby increasing write throughput.

Root cause for write amplification

Figure 2 illustrates compaction in a LSM key-value store. The key-value store contains two sstables in Level 1 initially. Let us assume that Level 0 is configured to hold only one sstable at a time; when this limit is reached, compaction is triggered. At time t1, one sstable is added, and a compaction is triggered is at t2. Similarly, sstables are added at t3 and t5 and compactions are triggered at t4 and t6. When compacting a sstable, all sstables in the next level whose key ranges intersect with the sstable being compacted are rewritten. In this example, since the key ranges of all Level 0 sstables intersect with key ranges of all Level 1 sstables, the Level 1 sstables are rewritten every time a Level 0 sstable is compacted. In this worst-case example, Level 1 sstables are rewritten three times while compacting a single upper level. Thus, the high write amplification of LSM key-value stores can be traced to multiple rewrites of sstables during compaction.

How it works?

FLSM can be seen as a blend of an LSM data structure with a Skip List along with a novel compaction algorithm that overall reduces write amplification and increases write throughput. The fundamental problem with log-structured merge trees is that sstables are typically re-written multiple times as new data is compacted into them. FLSM counters this by fragmenting sstables into smaller units. Instead of rewriting the sstable, FLSM’s compaction simply appends a new sstable fragment to the next level. Doing so ensures that data is written exactly once in most levels; a different compaction algorithm is used for the the last few highest levels. FLSM achieves this using a novel storage layout and organizing data using guards.

In the classical LSM, each level contains sstables with disjoint key ranges (i.e., each key will be present in exactly one sstable). The chief insight in this work is that maintaining this invariant is the root cause of write amplification, as it forces data to be rewritten in the same level. The FLSM data structure discards this invariant: each level can contain multiple sstables with overlapping key ranges, so that a key may be present in multiple sstables. To quickly find keys in each level, FLSM organizes the sstables into guards (inspired from the Skip-List data structure.

Each level contains multiple guards. Guards divide the key space (for that level) into disjoint units. Each guard Gi has an associated key Ki , chosen from among keys inserted into the FLSM. Each level in the FLSM contains more guards than the level above it; the guards get progressively more fine-grained as the data gets pushed deeper and deeper into the FLSM. For more details, I've attached the paper for reference below.

Disadvantages

1. Complexity: The algorithm is complex and can be difficult to understand, which makes implementation and maintenance challenging.

2. Overhead: The algorithm requires a lot of memory, which can result in performance degradation and slow data retrieval times.

3. Slower read performance

Reference

• https://research.vmware.com/files/attachments/0/0/0/0/0/2/7/sosp17-pebblesdb.pdf

Database Internals Newsletter

#Day8 - Storage Engines (Fractal Tree)

Fractal Trees are a type of index structure used in databases to store and manage data on disk. It gained attention when it was used as storage algorithms in databases such as RocksDB and TokuDB (acquired by Percona). These databases use Fractal Trees for high-performance, scalable indexing and storage of large amounts of data. The Fractal Tree algorith…

Read more

3 years ago · Farhan

Fractal Trees are a type of index structure used in databases to store and manage data on disk. It gained attention when it was used as storage algorithms in databases such as RocksDB and TokuDB (acquired by Percona). These databases use Fractal Trees for high-performance, scalable indexing and storage of large amounts of data. The Fractal Tree algorithm is designed to provide fast and efficient indexing, improved compression, and support for range queries and updates.

Understanding the problem

Let's understand three concepts to understand this topic better. Write, Space and Read Amplification.

Read amplification is the number of I/O’s required to read a particular query.

Space amplification refers to the increase in the amount of disk space required to store data in a database, compared to the original size of the data. It can occur as a result of various factors, such as the fragmentation, overhead required for data structures, duplicated data, or storage algorithms that result in increased storage usage. For example, B trees typically achieve only 75% space utilization due to fragmentation inside the B-tree blocks. Thus B trees suffer a space amplification of 4/3.

Write amplification is the amount of data written to storage compared to the amount of data that the application wrote. LSM trees and Fractal-Tree indexes both provide significant advantages over traditional B-trees. For example, if a database row contains 100 bytes, and a B tree such as InnoDB employs 16KiB pages, then the B tree may perform 16KiB of I/O to write a single 100-byte row, for a write amplification of 160, compared to a write amplification of 30 to 70 for the other data structures.

Write amplification is a problem on both rotating disks and solid-state disk (SSD), but for different reasons. For SSD, write amplification is a problem because flash-based SSD’s can be written to only a finite number of times. A B-tree performing random updates can easily use up a flash. Lower write amplification can help to reduce cost because you can buy cheaper flash (with fewer write cycles), and you may be able to provision a higher fraction of your flash storage to store useful data since the write blocks are larger. Larger write blocks help SSD.

To summarise the problem,

• B-trees are good at lookup, but bad at insert.

• LSM Trees are good at insert, but bad at lookup.

• Is there a data structure that is about as good as a B-Tree for lookup, but has insertion performance closer to LSM Trees or append-only files?

The answer is, Fractal Trees.

How does it work?

Fractal Trees combines the advantages of B-trees and LSM-trees. The main idea behind Fractal Trees is to maintain an optimal balance between fast lookups (as in B-trees) and fast write performance (as in LSM-trees).

In a fractal tree index, a buffer is used to temporarily store updates and deletions before they are eventually merged into the main tree structure. The buffer helps improve write performance by reducing the number of disk I/O operations required to modify the index. The contents of the buffer are periodically merged with the main tree in a process known as "flushing". By using a buffer, fractal tree indexes can effectively balance the trade-off between write performance and index size, making them well-suited for use in high-performance database systems.

It is very similar to the B tree, except it has extra buffers, which happen to be empty. When a data record is inserted into the tree, instead of traversing the entire tree the way a B tree would, we simply insert the data record into the buffer at the root of the tree. Eventually the root buffer will fill up with new data records. At that point the Fractal Tree index copies the inserted records down a level of the tree. Eventually the newly inserted records will reach the leaves, at which point they are simply stored in a leaf node as a B-tree would store them. The data records descending through the buffers of the tree can be thought of as messages that say “insert this record”. Fractal Tree indexes can use other kinds of messages, such as messages that delete a record, or messages that update a record. (You can refer to the original papers in the reference section to dive in more details)

What are the disadvantages of Fractal Trees?

Fractal trees, like any other data structure, have certain limitations and drawbacks. Some of the disadvantages of fractal trees include:

1. Complexity: Fractal trees are a complex data structure and may require more effort to implement and maintain compared to other data structures.

2. Performance trade-offs: Fractal trees may offer improved performance in certain use cases, but may not be the best choice for all types of workloads. For example, they may not be well suited for large sequential scans or write-intensive workloads.

3. Fractal index trees do not achieve high write throughput by taking advantage of large sequential writes, and do not employ in-memory indexes.

4. Limited adoption: Fractal trees are a relatively new data structure, and as such, may not have as much support and community resources available compared to more established structures such as B-trees.

Which databases use Fractal Trees?

Fractal Trees are used as storage algorithms in databases such as RocksDB, TokuDB, and PerconaFT. These databases use Fractal Trees for high-performance, scalable indexing and storage of large amounts of data. The Fractal Tree algorithm is designed to provide fast and efficient indexing, improved compression, and support for range queries and updates.

References

• http://www-db.deis.unibo.it/courses/TBD/Lezioni/mysqluc-2010-fractal-trees.pdf

• http://www.pandademo.com/wp-content/uploads/2017/12/A-Comparison-of-Fractal-Trees-to-Log-Structured-Merge-LSM-Trees.pdf

• https://www.slideshare.net/tmcallaghan/20131112-plukfractaltreestheorytopractice

Database Internals Newsletter

#Day7 - Storage Engines (LSM-Tree)

LSM (Log-Structured Merge) tree is a data storage algorithm used for storing and managing large amounts of data in a log-structured way. It is a variant of the B-tree, which is a type of self-balancing tree data structure. The LSM tree is designed to handle high write loads and high levels of data fragmentation. It uses a log-structured approach for stor…

Read more

3 years ago · Farhan

#database #sql #algorithms #systemdesign #arriqaaq #datastructures #immudb #mysql #postgres #mongodb #berkeleydb #tile38

LSM (Log-Structured Merge) tree is a data storage algorithm used for storing and managing large amounts of data in a log-structured way. It is a variant of the B-tree, which is a type of self-balancing tree data structure.

The LSM tree is designed to handle high write loads and high levels of data fragmentation. It uses a log-structured approach for storing data, which provides efficient write performance, scalability, and data durability. It is a popular choice for databases and distributed systems which handle high write loads and high levels of data fragmentation.

How do LSM trees work?

An LSM tree is composed of two types of data structures: memtables and sstables (sorted string tables). Memtables are small, frequently written-to data structures that hold recently added data. Sstables are larger, less frequently written-to data structures that hold older data that has been merged from memtables.

When new data is added to the LSM tree, it is first written to the active memtable. Once the memtable reaches a certain size, it is merged with one or more existing sstables to form a new sstable. This process, known as compaction, helps to reduce fragmentation and improve overall performance.

The LSM tree also uses a technique called write-ahead logging (WAL) to ensure data consistency and durability in the event of system crashes or power failures. This involves writing changes to a log file before they are committed to the LSM tree, so that any incomplete changes can be rolled back in the event of an interruption.

When a query is made, LSM tree first checks the memtable for the required data, if it is not found, it will check the sstables in order of recentness. This design gives a trade-off between read performance and write performance. It is optimized for write-heavy workloads, but with a cost of slower read performance.

What are the advantages of LSM-Tree?

1. High write performance: LSM trees are optimized for write-heavy workloads, as they allow new data to be added to the tree quickly and efficiently. The log-structured approach used by LSM trees reduces the need for random writes, which can slow down write performance in traditional B-trees.

2. Scalability: LSM trees can handle large amounts of data and high levels of data fragmentation, making them well-suited for use in databases and distributed systems. They can scale to handle very large datasets and handle high write-loads.

3. Data durability: LSM trees use write-ahead logging (WAL) to ensure data consistency and durability in the event of system crashes or power failures. This helps to protect data from loss or corruption.

4. Compaction: LSM trees use a compaction process to merge small, frequently written-to data structures called memtables into larger, less frequently written-to data structures called sstables. This helps to reduce fragmentation and improve overall performance.

5. Disk Space efficiency: LSM tree's compaction process helps in reducing the disk space usage by removing the duplicate keys.

What are the disadvantages of LSM-Tree?

1. Slower read performance: Because LSM trees are optimized for write-heavy workloads, read performance can be slower than in traditional B-trees. This is because read requests may need to check multiple sstables in order to find the requested data.

2. Increased disk space usage: LSM trees can use more disk space than traditional B-trees because of the compaction process, which creates multiple sstables. Each sstable contains a copy of the same data, which can lead to increased disk space usage.

3. Increased write amplification: LSM trees can lead to increased write amplification, which is the number of writes that must be performed to the storage device in order to update a single logical value. This is because the compaction process generates many small writes that are spread across multiple sstables.

4. Not good for update-heavy workloads: LSM tree is not well suited for update-heavy workloads, where data is frequently updated or deleted. As the LSM tree stores the data in sorted order, it can cause a lot of disk I/O when updating the data.

5. Large memory requirements: LSM tree requires a large amount of memory to hold the memtable, which can be a problem for systems with limited memory.

6. Not good for random access workloads: LSM tree is not well suited for random access workloads, where data is accessed randomly. As the LSM tree stores the data in sorted order, it can cause a lot of disk I/O when accessing the data randomly.

How databases that use LSM-Tree guarantee durability from server crashes?

LSM tree uses WAL to write data changes to a log file before committing them to the LSM tree. This way, if there is any interruption, the LSM tree can restore the data to its previous state by replaying the log file, ensuring data consistency and durability.

When a new data is added to the LSM tree, it is first written to the active memtable. Before committing the changes to the memtable, the changes are also written to a log file. This log file is called write-ahead log (WAL). The WAL acts as a buffer between the memtable and the hard disk.

In the event of a system crash or power failure, the LSM tree can use the WAL to restore the memtable to its previous state. The log records are replayed from the WAL to restore the in-memory data structures. This process helps to ensure that any changes that were in progress at the time of the interruption are rolled back, so that the data remains consistent.

Once the data is written to the WAL, it can then be committed to the memtable. After that, the memtable can be compacted with one or more existing sstables to form a new sstable. The WAL file is then truncated, and the process repeats.

What types of databases are LSM trees useful for?

LSM (Log-Structured Merge) trees are well-suited for databases and distributed systems that handle high write loads and high levels of data fragmentation. They are particularly well-suited for the following types of databases:

1. Time-series databases: LSM trees are well-suited for time-series data, which is naturally sorted by time. They can handle large amounts of data and high write loads, making them a good choice for storing time-series data such as sensor data, financial data, and log data.

2. Big Data databases: LSM trees are well-suited for storing large amounts of data and can handle high write loads, making them a good choice for big data databases. They are used in distributed systems such as Apache Cassandra and Google's Bigtable.

3. Append-only workloads: LSM trees are well-suited for append-only workloads, where new data is added but no data is deleted or modified. This is because the compaction process can handle high levels of data fragmentation, and the WAL can ensure data durability.

4. Event sourcing databases: LSM trees are well-suited for event sourcing databases, where the data is stored as a series of events. They can handle large amounts of data and high write loads, making them a good choice for storing event data.

5. IoT databases: LSM trees are well-suited for IoT databases, where large amounts of data are generated by IoT devices. They can handle high write loads and high levels of data fragmentation, making them a good choice for storing IoT data.

What popular databases use LSM-Trees?

Several popular databases use LSM (Log-Structured Merge) Trees as their underlying data storage algorithm, including:

1. Apache Cassandra: Cassandra is a highly scalable, distributed NoSQL database that uses LSM trees for data storage. It is designed to handle large amounts of data across many commodity servers, and is used by many large organizations, including Netflix, eBay, and Twitter.

2. Google Bigtable: Bigtable is a distributed NoSQL database that is used internally by Google for many of its services, including Google Earth, Google Maps, and Gmail. It is based on LSM trees and is designed to handle very large amounts of data.

3. HBase: HBase is an open-source, distributed NoSQL database that is built on top of the Hadoop Distributed File System (HDFS). It is modeled after Google's Bigtable and uses LSM trees for data storage.

4. RocksDB: RocksDB is an open-source embedded key-value store that is based on LSM trees. It is a library that can be used as a storage engine for various databases such as MySQL, Redis and MongoDB.

5. LevelDB: LevelDB is an open-source key-value store that is also based on LSM trees. It is designed to be a fast, low-level storage engine for key-value data.

6. Badger: Badger is an open-source key-value store that uses LSM (Log-Structured Merge) trees as its underlying data storage algorithm. It is built on top of the RocksDB library, which is also based on LSM trees.

Notes:

1) Issues with compaction in LSM-Tree

Compaction is an important process in LSM (Log-Structured Merge) trees, as it helps to maintain the performance of the database by merging multiple smaller sstables into larger ones. However, compaction can also cause some issues for LSM trees, including:

1. Increased write amplification: As compaction generates many small writes that are spread across multiple sstables, it can lead to increased write amplification, which is the number of writes that must be performed to the storage device in order to update a single logical value.

2. Performance degradation during compaction: Compaction can cause performance degradation, as it can require a lot of disk I/O and CPU resources. This can cause the database to slow down or become unresponsive during compaction.

3. Difficulty in handling large amounts of data: LSM trees can have difficulty handling very large amounts of data, as the compaction process can generate a large number of sstables.

To address these issues, a specific compaction strategy called "Levelled Compaction" is used in some LSM tree-based databases. In this approach, the data is divided into levels, and each level contains a set of sstables (Sorted String Table). Each level is roughly 10 times larger than the previous level. When a new sstable is added to the highest level, if the number of sstables in that level exceeds a certain threshold, the compaction process begins. The compaction process merges some of the sstables in that level into larger sstables, and the resulting sstables are moved to the next lower level.

The advantage of this approach is that it reduces the number of sstables that need to be compacted at any given time, which reduces the write amplification and improves the performance of the database. It also allows for more efficient use of disk space, as the smaller sstables in the higher levels are merged into larger sstables in the lower levels. This approach is used in some LSM tree-based databases such as RocksDB and LevelDB.

2) LSM-Tree + B-Tree

A combined approach of B-tree and LSM (Log-Structured Merge) tree is sometimes used in databases to take advantage of the strengths of both data structures. This approach is sometimes referred to as a "hybrid" approach.

In this approach, a B-tree is used for read-heavy workloads, as it provides efficient lookups and range queries. The B-tree is also used for small updates and deletions, as it can handle these operations efficiently.

On the other hand, an LSM tree is used for write-heavy workloads, as it can handle high write loads and high levels of data fragmentation. The LSM tree is also used for large updates and deletions, as it can handle these operations efficiently.

The use of a B-tree and an LSM tree together allows the database to take advantage of the strengths of both data structures, and can provide improved performance and scalability. This approach is used in some databases like RocksDB and LevelDB.

3) Other approaches

There has been a fair bit of further work building on the LSM approach. Yahoo developed a system called Pnuts which combines LSM with B trees and demonstrates better performance. There are also related approaches which have similar properties but retain an overarching structure. These include Fractal Trees and Stratified Trees. 

We will try discussing fractal trees next.

#database #sql #algorithms #systemdesign #arriqaaq #datastructures #immudb #mysql #postgres #mongodb #berkeleydb #tile38

A B-tree is a disk-based storage engine algorithm that is commonly used in databases to organize and store data on disk. A B-tree is a type of self-balancing search tree data structure that is characterized by having a variable number of child nodes per parent node. The "B" in B-tree stands for "balanced", which refers to the fact that the tree is kept balanced to ensure that the height of the tree is logarithmic with respect to the number of elements in the tree.

In a B-tree disk-based storage engine algorithm, data is stored in nodes, and each node has a number of keys and corresponding values. Each node also has a fixed number of pointers to its child nodes. When a new key-value pair is added to the B-tree, the tree is traversed to find the appropriate location for the new pair. If the node is full, it is split into two nodes, and the middle key is promoted to the parent node. This process continues until a new root node is created, if needed.

What are the advantages of B-Tree?

B-tree is widely used in databases, particularly relational databases, due to its ability to handle large amounts of data, its efficient search, insert and delete operations, and its ability to support range queries.

1. Efficient for large data sets: B-tree is well-suited for handling large amounts of data, it is a self-balancing data structure which means the height of the tree is logarithmic with respect to the number of elements in the tree, this makes search, insert and delete operations efficient even when the tree is large.

2. Efficient search: B-tree allows for efficient search operations, it allows to search for a key in a logarithmic time with respect to the number of elements in the tree.

3. Range queries: B-tree allows to perform range queries which means it can search for a range of keys. This feature is particularly useful in databases, where it's needed to retrieve data based on a range of keys.

4. Concurrency: B-tree supports concurrency, this means multiple threads can access the tree simultaneously, making it suitable for multi-threaded and multi-user applications.

What are the disadvantages of B-Tree?

B-tree has several disadvantages compared to other disk-based storage engine algorithms, such as:

1. Space overhead: B-tree requires additional space to store the tree structure and pointers, this can lead to increased disk usage and can be a concern for storage-constrained systems.

2. Large memory footprint: B-tree requires a large amount of memory to store the tree structure, this can be a concern for memory-constrained systems.

3. Slow random writes: B-tree performs well with sequential writes and random reads, but it can be slow with random writes because a random write may cause a split in the tree, which can be time-consuming.

4. High disk I/O: B-tree requires high disk I/O due to its disk-based storage and its need to access disk frequently to read and write data.

5. Limited scalability: B-tree's scalability is limited by the maximum number of keys that can fit in a single node.

6. Limited compression: B-tree's compression is limited when compared with other algorithms like LSM-tree.

Which databases use B-Tree?

1. MySQL: Uses the InnoDB storage engine, which is based on B-tree data structure.

2. immuDB: Uses B-Tree for indexing.

3. PostgreSQL: Uses B-tree as its default index.

4. MongoDB: MongoDB, a popular open-source NoSQL document-oriented database, uses B-tree indexes for organizing data in collections

5. Berkeley DB: Berkeley DB is a family of embedded key-value database libraries, it's a library that provides a high-performance embedded database for key/value data, Berkeley DB uses a b-tree data structure to store data on disk.

6. RocksDB: RocksDB is an embeddable persistent key-value store, it's a library that provides an embeddable, persistent key-value store for fast storage, it uses a b-tree data structure to store data on disk

7. LMDB: LMDB is an ultra-fast, ultra-compact key-value embedded data store, it uses a B+tree data structure which is similar to a hash table, it stores data on disk, it's used in some systems such as OpenLDAP, OpenVPN, and Postfix.

Variations of B-Tree for storing multi dimensional data

A variation of B-tree is used to organize and store multi-dimensional data in databases using the following different algorithms:

1. R-tree: An R-tree is a type of B-tree that is specifically designed to store and query multi-dimensional data, such as geographical data or data with multiple attributes. R-trees are used to index spatial data, they store the bounding boxes of the data and this allows for efficient range queries.

2. B+tree with multiple keys: A B+tree can be extended to support multiple keys, one key can be used as the primary key and additional keys can be used as secondary keys. In this way, a B+tree can be used to index data with multiple attributes and it allows for efficient queries based on the secondary keys.

3. B+tree with multiple levels: A B+tree can have multiple levels, each level can be used to index a different attribute, this allows for efficient queries based on different attributes.

Application of B-Tree for storing multi dimensional data

There are several databases that use B-tree for multi-dimensional data. These databases use B-tree for multi-dimensional data, particularly for spatial data using R-tree implementation and operations like distance and intersection. They are widely used in GIS (Geographic Information System) systems, spatial data applications, and other systems that require efficient storage and retrieval of spatial data. Some examples are:

1. Tile38: Tile38 is an in-memory geolocation data store, spatial index, and realtime geofencing server. It supports a variety of object types including lat/lon points, bounding boxes, XYZ tiles, Geohashes, and GeoJSON. It is based on R-tree and Quad-tree.

2. PostgreSQL: PostgreSQL uses an extension called PostGIS, which is based on the R-tree data structure, it can be used to index and query spatial data, it supports complex spatial data types and operations such as distance, area, and intersection.

3. MySQL: MySQL has a plugin called MyISAM Spatial, which is based on the R-tree data structure. It can be used to index and query spatial data, it supports spatial data types like points, lines, and polygons, and operations like distance and intersection.

4. SQLite: SQLite uses an extension called SpatiaLite, which is based on the R-tree data structure. It can be used to index and query spatial data, it supports spatial data types like points, lines, and polygons, and operations like distance and intersection.

5. MongoDB: MongoDB uses a data structure called "2d Indexes" which is based on the R-tree data structure. It can be used to index and query spatial data, it supports spatial data types like points, lines, and polygons, and operations like distance and intersection.

6. Berkeley DB: Berkeley DB can be used with a library called libspatialite, which is based on the R-tree data structure. It can be used to index and query spatial data, it supports spatial data types like points, lines, and polygons, and operations like distance and intersection.

#database #sql #algorithms #systemdesign #arriqaaq #datastructures #immudb #mysql #postgres #mongodb #berkeleydb #tile38

A Hash Index is also used as a disk-based storage algorithm that uses a hash table data structure to store data, it's used to store data in a way that allows for fast lookup and retrieval of data based on a key. A hash index uses a hash function to map the key to an index in the hash table, where the value can be found.

In a database, a Hash index is used to improve the performance of search operations, it's especially useful when the data is accessed randomly, it's also used to organize the data on disk, it's a more efficient way of storing data as it does not need to traverse the tree structure like in B-tree indexes, it's also smaller in size compared to B-tree indexes, this is because a hash index stores only the key-value pairs, and not the actual data.

However, the Hash index algorithm has some limitations, for example, it's not recommended for large databases, as it can take a lot of memory, also it can lead to collisions when the same hash value is assigned to different keys, this can lead to data loss or corruption. Additionally, Hash index algorithms are not suitable for range queries as they are not ordered.

Hash vs BTree

The Hash and Btree access methods are used when logical record numbers are not the primary key used for data access. (If logical record numbers are a secondary key used for data access, the Btree access method is a possible choice, as it supports simultaneous access by a key and a record number.)

Keys in Btrees are stored in sorted order and the relationship between them is defined by that sort order. For this reason, the Btree access method should be used when there is any locality of reference among keys. Locality of reference means that accessing one particular key in the Btree implies that the application is more likely to access keys near to the key being accessed, where "near" is defined by the sort order. For example, if keys are timestamps, and it is likely that a request for an 8AM timestamp will be followed by a request for a 9AM timestamp, the Btree access method is generally the right choice. Or, for example, if the keys are names, and the application will want to review all entries with the same last name, the Btree access method is again a good choice.

There is little difference in performance between the Hash and Btree access methods on small data sets, where all, or most of, the data set fits into the cache. However, when a data set is large enough that significant numbers of data pages no longer fit into the cache, then the Btree locality of reference described previously becomes important for performance reasons. For example, there is no locality of reference for the Hash access method, and so key "AAAAA" is as likely to be stored on the same database page with key "ZZZZZ" as with key "AAAAB". In the Btree access method, because items are sorted, key "AAAAA" is far more likely to be near key "AAAAB" than key "ZZZZZ". So, if the application exhibits locality of reference in its data requests, then the Btree page read into the cache to satisfy a request for key "AAAAA" is much more likely to be useful to satisfy subsequent requests from the application than the Hash page read into the cache to satisfy the same request. This means that for applications with locality of reference, the cache is generally much more effective for the Btree access method than the Hash access method, and the Btree access method will make many fewer I/O calls.

However, when a data set becomes even larger, the Hash access method can outperform the Btree access method. The reason for this is that Btrees contain more metadata pages than Hash databases. The data set can grow so large that metadata pages begin to dominate the cache for the Btree access method. If this happens, the Btree can be forced to do an I/O for each data request because the probability that any particular data page is already in the cache becomes quite small. Because the Hash access method has fewer metadata pages, its cache stays "hotter" longer in the presence of large data sets. In addition, once the data set is so large that both the Btree and Hash access methods are almost certainly doing an I/O for each random data request, the fact that Hash does not have to walk several internal pages as part of a key search becomes a performance advantage for the Hash access method as well.

In the absence of information on application data and data access patterns, for small data sets either the Btree or Hash access methods will suffice. For data sets larger than the cache, we normally recommend using the Btree access method. If you have truly large data, then the Hash access method may be a better choice.

Database which uses hash index

#BerkeleyDB: Berkeley DB is a family of embedded key-value database libraries, it's a library that provides a high-performance embedded database for key/value data. Berkeley DB uses a hash table data structure to store data, it's used for data management and data protection, it's suitable for embedded systems, and it's also used in some systems such as Apple's Time Machine and Mac OS X's Spotlight search feature. They have an extensive article on this topic here.

#database #sql #algorithms #systemdesign #arriqaaq #datastructures

Today we discuss Page-oriented disk-based storage engine algorithm, which is widely used in databases like MySQL and SQLite.

Page-oriented storage is a disk-based storage engine algorithm that stores data in fixed-size pages, where each page corresponds to a specific location in memory. Each page is a fixed-size block of data that is stored on disk.

In this approach, when a new piece of data is added to the database, the storage engine looks for an available page to store the data. Once a page is found, the storage engine stores the new data in the page. This can help to improve performance, as the disk head does not need to move as frequently to access the data and it's also useful for small files that can be stored in a single page.

In page-oriented storage, the data is stored in pages, which are the smallest unit of data that can be read or written by the storage engine. The storage engine uses these pages to store data in the table. Page oriented storage engine update the value in place (in its original page), instead of appending data to latest segment file.

Page-oriented storage algorithms are used in some databases such as Microsoft SQL Server, MySQL and SQLite.

What is the difference between Page-oriented storage and extents?

Page-oriented storage is a storage algorithm that stores data in fixed-size pages, it's more suitable for small files that can be stored in a single page.

Extents is a block-oriented storage algorithm that stores data in fixed-size blocks or chunks of data on disk, it's more efficient for large files that require a large amount of contiguous disk space.

What are the different data structures used?

Page-oriented storage engine algorithms use different data structures to organize the data on disk, the most common data structures used are:

1. B-tree: This is a balanced tree data structure that allows for efficient search and retrieval of data. B-tree is used in many page-oriented storage engines such as MyISAM, MS SQL Server and SQLite.

2. Heap: This is a simple data structure that stores data in an unordered heap file, it's typically used to store temporary tables, or small tables that are not accessed frequently.

How does #MYSQL use Page-oriented storage engine algorithm?

MySQL uses a storage engine system that allows to choose different storage engine to store data on disk. One of the storage engine that MySQL supports is MyISAM, which uses a Page-oriented storage disk-based storage engine algorithm.

MyISAM uses fixed-size pages to store data on disk, each page is typically 16KB. When a table is created, the storage engine splits the table into pages and stores them on disk. Each page is then assigned an index that the storage engine uses to locate the page in the file system.

The MyISAM storage engine uses a B-tree data structure to organize the data on disk. The B-tree is a balanced tree data structure that allows for efficient search and retrieval of data.

How does #SQLite use Page-oriented storage engine algorithm?

SQLite is a software library that implements a self-contained, serverless, zero-configuration, transactional SQL database engine. SQLite uses a page-oriented storage algorithm to store data on disk. Each page is typically 1KB or 2KB in size and all pages are the same size.

In SQLite, when a table is created, the storage engine splits the table into pages and stores them on disk. Each page is then assigned an index that the storage engine uses to locate the page in the file system. The pages are used to store the data rows, indexes, and other information in the database. The data rows are stored in a B-tree data structure, this allows for efficient search and retrieval of data.

SQLite uses a technique called "transactions" to manage the data on disk, Transactions are used to ensure consistency and integrity of the data on disk. SQLite supports two types of transactions: deferred and immediate. The deferred transaction is used to execute a series of SQL statements and commit them as a single transaction, while immediate transaction is used to execute a single SQL statement and commit it immediately.

How to decide between Page-oriented storage and extents?

The choice between using a Page-oriented storage engine algorithm or an Extents algorithm depends on the specific use case and the requirements of the database or file system.

Page-oriented storage is more suitable for small files that can be stored in a single page, and it's more efficient when the data is accessed randomly, because the disk head does not need to move as frequently to access the data. This type of storage algorithm is also well suited for databases that handle a large number of small transactions, such as online transaction processing (OLTP) systems.

On the other hand, Extents are more efficient for large files that require a large amount of contiguous disk space, such as large images, videos, and audio files, also it's more efficient when the data is accessed sequentially, because the disk head does not need to move as frequently to access the data. This type of storage algorithm is also well suited for databases that handle large amounts of data, such as data warehousing and business intelligence (BI) systems.

Note:

InnoDB, which is a storage engine used by MySQL and other database management systems, uses extents to store data on disk.

In InnoDB, an extent is a sequence of contiguous blocks on disk that are used to store data. When a table is created, the storage engine looks for an available extent to store the data. Once an extent is found, the storage engine divides it into smaller pages and stores the new data in one of these pages.

InnoDB uses a technique called "multi-versioning" to implement a form of data compression, by storing multiple versions of the same data in a single extent. This can reduce the number of extents needed to store a given amount of data, which can help to reduce disk I/O and improve performance.

We will dive into each database internals in the last 10 days of this series.

Arriqaaq Newsletter

#Day3 - Storage Engines (Extents)

Extents is a disk-based storage algorithm that is used in some database management systems (DBMSs) to store and retrieve data. The main goal of Extents is to minimize disk I/O by allocating large blocks of disk space instead of small blocks. It is a block-oriented storage algorithm, which means that it stores data in fixed-size blocks or chunks of data …

Read more

3 years ago · Farhan

#database #sql #algorithms #systemdesign #arriqaaq #datastructures

Extents is a disk-based storage algorithm that is used in some database management systems (DBMSs) to store and retrieve data. The main goal of Extents is to minimize disk I/O by allocating large blocks of disk space instead of small blocks. It is a block-oriented storage algorithm, which means that it stores data in fixed-size blocks or chunks of data on disk, rather than on a per-page basis. Each extent is a sequence of contiguous blocks on disk, and when a file is created, it is allocated space in one or more extents.

In this approach, when a new piece of data is added to the database, the databases looks for a large block of free space, called an "extent", to store the data. Once an extent is found, the database divides it into smaller blocks and stores the new data in one of these blocks. This can help to reduce disk I/O and improve performance, as the disk head does not need to move as frequently to access the data.

Extents are also used to reduce fragmentation. Extents are allocated in a contiguous block, which means that the data is stored in a contiguous block on disk. This reduces fragmentation and can improve performance, as the disk head does not need to move as frequently to access the data.

In some databases, the extents are also used to implement a form of data compression, by storing multiple rows of data in a single block. This can reduce the number of blocks needed to store a given amount of data, which can help to reduce disk I/O and improve performance.

Which databases use this approach?

The Extents disk-based storage algorithm is used in some databases such as Oracle, IBM Informix and Microsoft SQL Server.

In Oracle, the Extents are used in the Automatic Storage Management (ASM) feature, which is a volume manager and file system for Oracle Database files. ASM uses extents to manage the space allocation for the data files, temp files and control files of the database.

In Microsoft SQL Server, the Extents are used in the Storage Engine, the SQL Server Storage Engine uses extents to manage the space allocation for the data and index pages. Extents are 8 contiguous pages (8KB) that are used to store the data in a SQL Server database. Each extent is composed of eight 8 KB pages which are physically located next to each other on disk.

In IBM Informix database, an extent consists of a collection of contiguous pages that store data for a given table.When you create a table, the database server allocates a fixed amount of space to contain the data to be stored in that table. (See Tables.) When this space fills, the database server must allocate space for additional storage. The physical unit of storage that the database server uses to allocate both the initial and subsequent storage space is called an extent.

Use of extents in file systems

Apple File System (APFS) is a file system developed by Apple for their operating systems. APFS uses extents to store files on disk and to minimize disk I/O. Extents in APFS are the basic unit of space allocation and are used to track the allocation of disk space within the file system.

In APFS, an extent is a sequence of contiguous blocks on disk. When a file is created, it is allocated space in one or more extents. When a file is deleted, the extents that were allocated to it are freed up and made available for use by other files. This can help to reduce fragmentation and improve performance, as the disk head does not need to move as frequently to access the data.

APFS also uses a technique called "sparse extents" which is an optimization of the traditional extent-based storage. Sparse extents allow the file system to allocate disk space to a file only when it's needed and not when the file is created, this allows to save disk space and it's more efficient.

Extents vs Page-oriented storage

In contrast, page-oriented storage refers to a storage algorithm that stores data in fixed-size pages, where each page corresponds to a specific location in memory. Each page is a fixed-size block of data that is stored on disk, and when a file is created, it is allocated space in one or more pages.

Both Extents and Page-oriented storage algorithms are used in databases and file systems, but they are different and have different use-cases. Extents are more efficient for large files that require a large amount of contiguous disk space, whereas Page-oriented storage is more suitable for small files that can be stored in a single page.

Dropbox use of extents in the magic pocket storage

Quoting from their article, “Magic Pocket organizes blocks into extents—containers of blocks—typically 1-2 GB in size. When an extent is open, it is able to accept writes; new blocks can be appended until the extent reaches its maximum size. Once full, the extent is closed, making it immutable and read-only.

These extents were already ideal for SMR disk sequential-only workloads. Because Magic Pocket's storage engine was setup to guarantee sequential writes and map extents onto a fixed set of SMR zones, we didn’t have to change much to support SMR-style sequential writes.

Our storage engine’s existing implementation of open extents stored block metadata—such as block length and hashes—on SSD cache disks, while raw block data was stored on SMR disks. To get rid of the SSD cache, we would have to store both block metadata and raw block data on the same SMR disk.

We introduced a new extent format which stored block metadata and raw block data inline. On startup, the storage engine would parse the data on extents into metadata and raw data. It would then build an in-memory index mapping each block to its offset in the extent. On each new block write, blocks were inlined with their metadata, serialized, and committed to the SMR disk directly.”

https://dropbox.tech/infrastructure/increasing-magic-pocket-write-throughput-by-removing-our-ssd-cache-disks

#database #sql #algorithms #systemdesign #arriqaaq #datastrutures #microsoftsqlserver #oracle #ibm #informix

Let's understand storage engines with a simple technique, append-only files. Remember, a storage engine is responsible for physically storing and retrieving the data within a database.

Append-only files are a storage technique that is used in databases to store data on disk. This approach is based on the idea that data is written to the file only once, and once written, the data cannot be modified or deleted.

In this approach, data is stored in a series of append-only files, with each file representing a specific period of time or a specific data set. When a new piece of data needs to be stored, it is written to the end of the current file. As the file grows, the database can periodically create a new file to store new data.

The main advantage of using append-only files as a storage engine is that they are extremely simple to implement and maintain. Because the data is never modified or deleted, there is no need for complex data structures or algorithms to manage the data. In addition, this approach can be used to store data in a highly compressed format, which can save disk space and improve performance.

However, this approach also has some limitations. Because the data cannot be modified or deleted, it can lead to a large number of files, which can make it difficult to manage the data. In addition, this approach can make it more difficult to update or delete data, as each file must be read in its entirety to find the data that needs to be updated or deleted.

To overcome these limitations, some databases combine append-only file storage with other storage techniques, such as indexing, to make it easier to find and update data. They also implement compaction algorithms to reduce the number of files and the disk space consumed by the data.

How is it used with indexing?

Append-only files can be used to store offsets of indexed data in a B-Tree index in a database. This approach is known as an "offset B-Tree" or "B-Tree on append-only file".

In this approach, the B-Tree index structure is stored in memory, while the indexed data is stored in an append-only file on disk. Each node in the B-Tree index contains a set of keys and corresponding offsets, which point to the location of the indexed data in the append-only file. In immudb, the database I am currently working on, we use this same technique for indexing.

When a new piece of data is indexed, it is added to the end of the append-only file, and the corresponding offset is added to the B-Tree index. When a query is made, the B-Tree index is searched to find the correct offset, and the indexed data is retrieved from the append-only file using the offset.

This approach has several advantages. The B-Tree index can be kept in memory, which speeds up search operations. The append-only file allows for fast, sequential writes, which improves write performance. Additionally, the use of offsets allows for more efficient storage of the indexed data, as the data can be stored in a highly compressed format.

Note:

• Append-only files are a useful storage technique for immutable databases and blockchain ledgers that do not allow for any updates or deletions to the data once it has been written. In #immudb, we use this same approach. The main advantage of using append-only files in an immutable database is that the data can be stored in an immutable format, which means that it is not possible to modify or delete the data once it has been written. This ensures that the data remains consistent and can be used for auditing or other purposes.

• Log-Structured Merge Trees (LSM Trees) use append-only files for a fast and efficient disk-based storage engine. We will discuss LSM trees later. Basically LSM Trees works by writing new data to a log-structured append-only file. As the file grows, the DBMS periodically performs a merge operation that sorts and compacts the data in the file, creating a new B-tree (or hash table or the index of your choice). #Prometheus time-series database engine is also based on a similar technique.

#30daysofdatabases series debunks database internals to make it easy to understand for everyone, helping engineers understand better the reasons behind performance bottlenecks in any database. Hopefully this inspires you to build one on your own.

#database #sql #algorithms #systemdesign #arriqaaq #datastrutures

In 2022, I got the chance to work on databases entirely, alhamdulillah.

1) I created my own database from scratch #flashdb (https://lnkd.in/gkP7fQ25)
2) I started work on a fast immutable database #immudb (https://lnkd.in/gcn6yry2)

To make database internals easy to understand for everyone, I am starting a small series #30daysofdatabases to understand how databases are constructed, helping engineers understand better the reasons behind performance bottlenecks in any database. Hopefully this inspired you to build one on your own.

Query Engine vs Storage Engine

The query engine and storage engine are two separate components of a database that perform different functions.

A query engine, also known as a query processor, is responsible for processing queries and returning the requested data to the user. It receives SQL or other query language statements (like PromQL or influxQL) from the application, and converts them into a series of instructions that the database server can understand. The query engine also performs tasks such as parsing and optimizing the query. ACID properties are usually implemented on the query engine of a database.

A storage engine is responsible for physically storing and retrieving the data within a database. It interacts with the file system or other storage subsystem to read and write data to disk or other storage media. The storage engine also manages the data structures and algorithms used to organize and retrieve the data, such as B-trees, LSM Trees, Merkle Trees, Append-only files, Paged Binary Trees, FD-trees, Lazy B-Trees or simple hash tables.

Notes:

- ACID transactions are usually implemented on the query engine of a database using a combination of techniques, such as two-phase commit, locking, and transaction logs, to ensure that the database remains in a consistent state, even in the presence of concurrent transactions, and that all changes made by a transaction are persisted to disk, so they can survive system failures.

- Query parsers basically take a string of text (in this case, a database query) and convert it into a data structure, such as an abstract syntax tree (AST), that can be more easily understood and processed by the database. Query parsers are usually pluggable in a well designed database. Here is an example of how we do it in #immudb https://lnkd.in/gDnw_AdS

In summary, the query engine is responsible for handling the communication between the user and the database server, interpreting and executing the query, while the storage engine is responsible for managing the physical storage of data, it uses different techniques and algorithms to store and retrieve the data efficiently. Together, these two layers form the foundation of a database management system, providing the functionality needed to store, retrieve, and manipulate data.

#database #sql #algorithms #systemdesign #arriqaaq #datastructures

Details on my work:

1) Building a database in Go from scratch: https://lnkd.in/gshJyeig
2) Working on a fast immutable database:
https://lnkd.in/gKMdJBTZ

Table of Contents

• Introduction

• About immudb

• Basic Building Blocks

  • Append-only logs

  • Merkle Tree

  • Timed BTree

• Persistence

• Lifecycle of a transaction in immudb

Introduction

I've been working on a fast immutable database, called immudb (developed by Codenotary), and was very curious about the immutable nature of storage. I have written this blog to explain how data is stored in an immutable manner in the database and to understand the data structures (and cryptographic) algorithms used internally.

Immutable databases are used for tracking changes in sensitive data, and for auditing purposes. Tamper-evident data means you can cryptographically prove that the data hasn’t been unexpectedly changed. Knowing the provenance, integrity, and sequence in which your data was created means you’ll be able to monitor that the data has not been modified by an unknown user in an unauthorized way, which simplifies regulatory compliance and audit. This is an essential feature within the scope of many activities that collect critical user information and solve issues like insider attack threats, abuses, and patterns on the system through an audit.

A few decades back, storage was expensive, and so was CPU. This is why research in the past on database storage strongly considered storing information efficiently whilst utilising the least amount of space on disk. Few of the earliest users of databases were finance (and accounting) companies, as it made sense to store their ledger (or accounting) data in a database. Accounting ledgers are immutable. Entries are only appended to the ledger. Due to disk constraints, many databases added the support to UPDATE a record to utilise the disk efficiently. This is one reason why modern database storage systems are a bit complicated when compared to append-only storage. And this is why they are slow too, as efficient on disk data management (which requires UPDATES) requires complex data management techniques.

About immudb

immudb is an open source Immutable Database that supports Cryptographical verification, tamper-resistance, and audit. It has support for both Key-Value and SQL and has high-performance and scalability solutions when compared to its competitors in the market.

Let's dive deep into how a record is stored on disk by immudb, and the data structures and algorithms used internally.

Basic Building Blocks

immudb consists of the following data structures:

• Append-only Logs

• Merkle Trees

• Timed B-Tree

Append-Only Logs

Append-only log, also called write-ahead log, is a family of techniques for providing atomicity and durability (two of the ACID properties) in database systems. An append-only log is an auxiliary disk-resident structure used for crash and transaction recovery. Append-only log files keep a record of data changes that occur by writing each change to the end of the file. In doing this, anyone could recover the entire dataset by replaying the append-only log from the beginning to the end. It is also fast, as compared to other database storage systems, because writes are only being appended to a file.

It is a fundamental building block for our immutable database system. Since new updates are layered over the previous ones, developers can time-travel and look into the past versions of a record.

Merkle tree

A Merkle tree is an authenticated data structure organized as a tree.

Authenticated means the integrity of the data structure can be efficiently verified using the (Merkle) root of the tree. The dataset cannot be altered without changing the Merkle root. The underlying data structure is organized as a tree, where each parent node is obtained by hashing the data from the child nodes in the layer below.

This is how a merkle tree is built:

1. Individually hash each element of the original dataset into a leaf node.

2. Hash together pairs of leaf nodes and store the resulting value in a parent branch node. The hashing function to obtain a leaf or branch node is different.

3. Keep hashing pairs of branch nodes until you get to a single top branch node, the root of the tree.

Unlike an ordinary Merkle tree, immudb tree can produce inclusion and consistency proofs that allow verifying if a particular key is present in the transaction (inclusion proof) and if the later version includes everything in the earlier version, and all new entries come after the entries in the older version (consistency proof).

Inclusion Proof

Inclusion proofs tell us to not simply trust the record, but to verify it by asking for proof.

Why create a tree when a hash chain could just work as such? Well, with a tree, it is possible to create proofs-of-inclusion for any data present in the original dataset. When a client gets a record from immudb, it does not simply trust the record. Instead, it requests an inclusion proof from the log and verifies that the proof is valid. This links the content of that record back to a tree head hash. The client then calculates the hash of the record and the chain of hashes up the tree to the tree head hash.

The root hash is the only part that needs to be stored on chain. To prove a certain value, you provide all the hashes that need to be combined with it to obtain the root. For example, to prove C you provide D, H(A-B), and H(E-H).

There are two entities involved in a proof-of-inclusion: the Verifier and the Prover. The Verifier’s responsibility is to check that certain data is part of the original dataset, while the role of the Prover is to prepare the proof and give it to the Verifier.

Inclusion Proof calculation is as follows:

1. Verifier sends the Prover the transaction for which it wishes to obtain a proof-of-inclusion.

2. The Prover finds this transaction in the Merkle tree and its index, indicating the transaction position in the tree.

3. The Prover collects the intermediary hashes, and the transaction root and sends them to the Verifier.

4. The Verifier uses the hashes and the transaction data it already has to recalculate the Merkle root and check that the root is equal to the one it originally had.

Consistency proof

Consistency proofs tell us nothing was tampered with.

A consistency proof verifies the consistency between a log at two points in time. It verifies that the later version includes everything in the earlier version, in the same order, and all new entries come after the entries in the older version.

Attack resistance

Merkle trees that accept input datasets with varying length are susceptible to second pre-image attacks. In a second pre-image attack, the goal of the attacker is to find a second input that hashes to the same value of another given input x. In Merkle trees, this corresponds to having two different input datasets giving the same Merkle root. To solve this problem, we prepend a different flag to the data before hashing it, depending on whether the resulting node is a leaf or branch node.

immudb Merkle Tree internals

immudb maintains three types of merkle trees:

Main Merkle Tree
Each database has one main Merkle Tree where its inputs are built from transaction hashes/ This tree is persisted in the storage layer. It is also appendable - each new transaction adds one extra leaf node with transaction hash (Alh) and rebuilds the path to the root.

Internal Merkle Tree
Each transaction contains its internal Merkle Tree built from Key-Value-Metadata entries that are part of that single transaction. The root hash of that Merkle Tree (EH) along with transaction metadata and additional linear proof information is used to build the transaction hash that is then input for the main Merkle Tree. This tree is not stored on disk and is recalculated on-demand from data that is building up the transaction.

Linear proof
The additional linear proof for the transaction is a mechanism implemented in immudb that is meant for handling peak transaction writes where the writes are much faster than the main Merkle Tree recalculation. It also forms a linear chain for all transactions since the beginning of the database.

You can read more about the proofs in detail in this excellent documentation from the team here.

Timed B-Tree

Indexing is the first thing that comes to mind when we consider a database's performance. B-tree is an m-way tree that self-balances itself. Due to their balanced structure, such trees are frequently used to manage and organise enormous databases and facilitate searches, especially range queries. A B-Tree index speeds up data access because the storage engine doesn’t have to scan the whole table to find the desired data.

A B-tree:

• keeps keys in sorted order for sequential traversing

• uses a hierarchical index to minimize the number of disk reads

• uses partially full blocks to speed up insertions and deletions

• keeps the index balanced with a recursive algorithm

immudb stores the index in a slightly modified version of a typical B-Tree, called a timed B-tree. A TBtree (a timed B-Tree) stores indexes for records in a database for lookups by the full key, a key range, or a key prefix. They are useful only if the lookup uses a leftmost prefix of the index. The index is useful for the following kinds of queries:

• Match the full key

• Match a leftmost prefix

• Match a range of values

• Match one part exactly and match a range on another part

As the tree’s nodes are sorted, they are helpful for both lookups and ORDER BY queries (finding keys in sorted order). In general, if a B-Tree can help find a row in a particular way, it can help you sort rows by the same criteria. So, the index will be helpful for ORDER BY clauses that match all the types of lookups we just listed. Why is this required you may ask? For SQL support.

SQL support

Our SQL support layer is built on top of the TBtree too. Any SQL schema for a table contains information about the column and datatype.

CREATE TABLE table_name (
    column1 datatype,
    column2 datatype,
    column3 datatype,
   ....
);

immudb stores the schema and records for a table as any other key-value pair in it's append-only log storage. But to identify the SQL records, a prefix is appended on the key to help identify the schema (or catalog in immudb terminology).

With help of B-Tree for lookups by the full key, a key range, or a key prefix, immudb managed B-Tree support. Also revisions/history for keys are stored in the TBtree, this provides support for fast time-travel for any key by just querying the index.

Note that the values are not stored against the key in the Btree, rather we store the offset of the value in the value-log (explained below) against a key for faster lookups.

Transaction support

Each new transaction in immudb currently creates a snapshot to allow concurrent operations on the database. I'll write more on how MVCC support works in immudb in an upcoming blog.

Persistence (storage on disk)

The immudb storage layout consists of the following append-only logs per database:

• AHT: Append-only Hash Tree. Each database has one main Merkle Tree where its inputs are built from transaction hashes. This tree is persisted in the storage layer. It is also appendable - each new transaction adds one extra leaf node with transaction hash (Alh) and rebuilds the path to the root. The AHT (Append-only Hash Tree) is a versioned Merkle tree where records are stored as digests left-to-right at the lowest level, following an append-only model. Like a hash chain, this AHT is persistent, with the difference that it supports efficient inclusion and consistency proofs. We can see that the AHT grows always from left to right. This growth property allows us to make efficient claims about the past because we can reconstruct old versions of the tree by pruning specific branches from right to left.

• Transaction Log: An append-only log for storing the transaction headers for a transaction. This helps in reading the header information of a transaction easily, as the header size is fixed.

• Commit Log: An append-only log for storing the information about the commits to a database. This log stores the transaction in an ordered way and is used for database recovery as transactions written in this log can be considered fully committed.

• Value Log: An append-only log for storing the actual values of key-value pairs within a transaction. The underlying data structure is again an append-only log. This log is kept separate for faster reads, and because many other data structures internally refer to the values, storing it in a separate log provides ease of access. The B-Tree index and transaction headers do not store the value itself but refer to the offset of the value in the value-log appendable.

• Index Log: An append-only log for storing the index for transactions in a database. Internally, immudb uses a B-Tree to index database records, and provide SQL support, and the index log is the B-Tree storage on disk.

Lifecycle of a transaction in immudb

When a transaction is sent to the immudb server, the following events take place:

• Key-Values are encoded in a transaction

• The values are recorded in the value-log appendable, and the offset of those values are stored in the transaction header (transaction log).

• The accumulated linear hash (ALH) is built by chaining the hash of the current transaction + previous transactions ALH + the inner hash of the transaction. This value is then appended to the AHT where the merkle tree is stored and proofs are requested from.

• There could be many concurrent transactions happening on the server, and the commit log stores information of transaction ordering. The Transaction header offset (from the transaction log) and size of the transaction are the only information stored in the commit log.

• Lastly the keys and value offset information is stored in the B-Tree index, and the indexing happens asynchronously and can be recreated on a restart of the database.

References

• https://docs.immudb.io/

• https://github.com/codenotary/immudb-issues/blob/feat/analysis-of-proofs/PROOFS.md#no-validation-of-db-uuid-and-db-name-when-storing-state

You can check out the codebase here, also feel free to raise any doubts you have by creating an issue or joining our Discord:

Subscribe now

TLDR; RFC#6962 implementation of merkle tree

Recently I'd been reading on the application of immutable databases for tracking changes in sensitive data, and for auditing purposes. That got me thinking on how they work underneath. This blog is an attempt to understand the data structures/cryptographic algorithms used in building such a system.

Traditional database records are mutable, and therefore there is no way to know for sure if your data has been compromised. Tamper-evident logs solve this problem. Tamper-evident logs means you can cryptographically prove that the data hasn’t been unexpectedly changed. Knowing the provenance, integrity and sequence your data was created means you’ll be able to monitor third-party ecosystems and simplify regulatory compliance. You can trust the data you rely on.

Security Audits

This has a variety of use cases in the industry we work in. Permissioned systems have a flaw, an assumption that they are secure. Many database or log systems run on untrusted servers or are subject to malicious attacks from insiders and, therefore, vulnerable to tampering. Organizations depend on widely-used database systems to store their data and try to limit the kind of operations users can perform on them by using authentication, hardening rules and access control mechanisms.

Permissionless systems (like Blockhain) implement zero trust from grounds up. Suppose we have a continuous sequence of records: access logs, event logs, transaction logs, secrets, configuration files or any sequenceable data. Such sequence can be materialized in one or multiple log files and therefore provide an audit trail to understand the activity of a system. And so, it may be subject to queries by users who want to diagnose problems. The evidence one seeks in these sorts of diagnostic investigations often takes the form of statements of existence and order.

A tamper-evident log stores an accurate, immutable and verifiable history of activity. This is an example of a verifiable system. You could use them to track credits and debits in banking transactions, access logs to sensitive healthcare records, cryptographic hashes of software packages, compliance artifacts of regulated activities, or modifications to a document.

Use cases of Tamper-evident Logs

Discourage Insider Threats

A tamper-evident log makes it impossible for a malicious insider to cover their tracks. A tamper-evident log discourages malicious behaviour by increasing the chance of discovery.

Simplify regulatory compliance

A tamper-evident log keeps you in control of your audit artifacts and gives auditors confidence. Regulated industries require companies to collect and retain many types of compliance records. Auditors need to verify the integrity and nonrepudiation of those records.

By using a tamper-evident to store compliance records, you can keep them in one place and simplify presenting them to an auditor. You can cryptographically prove they haven't been tampered with.

A tamper-evident log is a more efficient way of presenting compliance records to an auditor who can easily verify their history and integrity.

Monitor third-party ecosystems

A tamper-evident log enables multiple parties to monitor each others' actions. Where organisations can be required to publish data about their actions, a tamper-evident log can hold a permanent record of this data. Certificate Transparency discourages misbehaviour of Certificate Authorities by making their actions public. Tamper-evident logs can frustrate software supply chain attacks by providing a shared, global view of the content of packages.

Applications of Tamper-evident Logs

The best example of an application of an immutable log is how the Public Go Module Ecosystem. Sigstore is another such example.

If you've been in the Golang community for long, in the initial days, there were so many proxy servers available to download modules from, that one would not know which one to trust or not. What if some malicious snippet has been inserted? An attacker able to intercept the connection to the proxy server or github.com (or an attacker able to break into one of those systems, or a malicious module author) would be able to cause goget to download different code tomorrow, and goget would not notice. There was no way to verify until the introduction of the Go checksum database.

Module Authentication with go.sum

The Certificate Transparency project is based on a data structure called a transparent log. The transparent log is hosted on a server and made accessible to clients for random access, but clients are still able to verify that a particular log record really is in the log and also that the server never removes any log record from the log. Separately, third-party auditors can iterate over the log checking that the entries themselves are accurate. These two properties combined mean that a client can use records from the log, confident that those records will remain available in the log for auditors to double-check and report invalid or suspicious entries. Clients and auditors can also compare observations to ensure that the server is showing the same data to everyone involved.

Checksum Database

The Go checksum database runs at https://sum.golang.org/ and serves the following endpoints:

• /latest will serve a signed tree size and hash for the latest log.

• /lookup/M@V will serve the log record number for the entry about module M version V, followed by the data for the record (that is, the go.sum lines for module M version V) and a signed tree hash for a tree that contains the record. If the module version is not yet recorded in the log, the notary will try to fetch it before replying. Note that the data should never be used without first authenticating it against the signed tree hash and authenticating the signed tree hash against the client's timeline of signed tree hashes.

• /tile/H/L/K[.p/W] will serve a log tile. The optional .p/W suffix indicates a partial log tile with only W hashes. Clients must fall back to fetching the full tile if a partial tile is not found. The record data for the leaf hashes in /tile/H/0/K[.p/W] are served as /tile/H/data/K[.p/W] (with a literal data path element).

The Go team at Google runs the Go checksum database as a service to the Go ecosystem, similar to running godoc.org and golang.org.

Proxying a Checksum Database

A module proxy can also proxy requests to the checksum database. The general proxy URL form is <proxyURL>/sumdb/<databaseURL>. If GOPROXY=https://proxy.site then the latest signed tree would be fetched using https://proxy.site/sumdb/sum.golang.org/latest. Including the full database URL allows a transition to a new database log, such as sum.golang.org/v2.

Before accessing any checksum database URL using a proxy, the proxy client should first fetch <proxyURL>/sumdb/<sumdb-name>/supported. If that request returns a successful (HTTP 200) response, then the proxy supports proxying checksum database requests. In that case, the client should use the proxied access method only, never falling back to a direct connection to the database. If the /sumdb/<sumdb-name>/supported check fails with a “not found” (HTTP 404) or “gone” (HTTP 410) response, the proxy is unwilling to proxy the checksum database, and the client should connect directly to the database. Any other response is treated as the database being unavailable.

A corporate proxy may want to ensure that clients never make any direct database connections. The optional /sumdb/supported endpoint, along with proxying actual database requests, lets such a proxy ensure that a go command using the proxy never makes a direct connection to sum.golang.org. But simpler proxies may wish to focus on serving only modules and not checksum data—in particular, module-only proxies can be served from entirely static file systems, with no special infrastructure at all. Such proxies can respond with an HTTP 404 or HTTP 410 to the /sumdb/supported endpoint, so that clients will connect to the database directly.

go command client

The go command verifies the log as it uses it, ensuring that every record it reads is actually in the log and that no observed log ever drops a record from an earlier observed log.

The go command refers to $GOSUMDB to find the name and public key of the Go checksum database. That variable defaults to the sum.golang.org server.

The go command then caches the latest signed tree size and tree hash in $GOPATH/pkg/sumdb/<sumdb-name>/latest. It will cache lookup results and tiles in $GOPATH/pkg/mod/download/cache/sumdb/<sumdb-name>/lookup/path@version and $GOPATH/pkg/mod/download/cache/sumdb/<sumdb-name>/tile/H/L/K[.W]. This way, go clean -modcache deletes cached lookup results and tiles but not the latest signed tree hash, which should be preserved for detection of timeline inconsistency. No go command (only a manual rm -rf $GOPATH/pkg) will wipe out the memory of the latest observed tree size and hash. If the go command ever does observe a pair of inconsistent signed tree sizes and hashes, it will complain loudly on standard error and fail the build.

Data structures underneath the hood

Well, that was the point of this article, isn't it? I was checking out the Certificate Transparency project in detail and then stumbled upon the paper Verifiable data structures.  A verifiable data structure is a class of data structure that lets people efficiently agree, with cryptographic certainty, that the data contained within it is correct.

I read through the RFC for Certificate Transparency, to check for the data structures used underneath, and Merkle Trees was the answer.

Merkle Trees are the most famous of these and have been used for decades because they can enable efficient verification that a particular piece of data is included among many records - as a result they also form the basis of most blockchains.

Merkle tree

A binary tree that stores values at the lowest level of the tree and uses cryptographic hash functions. While leaves compute the hash of their own attributes, parents derive the hash of their children’s hashes concatenated left-to-right. Therefore the hash rooted at a particular subtree is recursively dependent on all its descendants, effectively serving as a succinct summary for that subtree.

Membership proof

A Merkle tree can prove values to be present by constructing efficient membership proofs. Each proof must include a Merkle audit path, and it is verified by recomputing all hashes, bottom up, from the leaf that the proof concerns towards the root. The proof is believed to be valid if the recomputed root hash matches that of the original Merkle tree, but to be convincing it requires a trustworthy root (e.g., signed by a trusted party or published periodically in a newspaper).

Merkle audit path

A Merkle audit path for a leaf is the list of all additional nodes in the Merkle tree required to compute the Merkle Tree Hash for that tree. If the root computed from the audit path matches the true root, then the audit path is proof that the leaf exists in the tree.

RFC Deep Dive

The Tree

A simple array of byte entries

type (
	// Path is a list of nodes required for proving inclusion or consistency.
	Path [][sha256.Size]byte

	// Tree implements a general purpose Merkle tree.
	Tree struct {
		entries [][]byte
	}
)

The Merkle Hash

Logs use a binary Merkle Hash Tree for efficient auditing.  The hashing algorithm is SHA-256 [FIPS.180-4] (note that this is fixed for this experiment, but it is anticipated that each log would be able to specify a hash algorithm).  The input to the Merkle Tree Hash is a list of data entries; these entries will be hashed to form the leaves of the Merkle Hash Tree.  The output is a single 32-byte Merkle Tree Hash.  Given an ordered list of n inputs, D[n] = {d(0), d(1), ..., d(n-1)}, the Merkle Tree Hash (MTH) is thus defined as follows:

func (t *Tree) hash(D [][]byte) [sha256.Size]byte {
	n := uint64(len(D))
	/*
		The hash of an empty list is the hash of an empty string:
		MTH({}) = SHA-256().
	*/
	if n == 0 {
		return sha256.Sum256(nil)
	}
	/*
		The hash of a list with one entry (also known as a leaf hash) is:
		MTH({d(0)}) = SHA-256(0x00 || d(0)).
	*/
	if n == 1 {
		c := []byte{LeafPrefix}
		c = append(c, D[0]...)
		return sha256.Sum256(c)
	}

	/*
		For n > 1, let k be the largest power of two smaller than n (i.e.,
		k < n <= 2k).  The Merkle Tree Hash of an n-element list D[n] is then
		defined recursively as
		MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])),
		where || is concatenation and D[k1:k2] denotes the list {d(k1),
		d(k1+1),..., d(k2-1)} of length (k2 - k1).  (Note that the hash
		calculations for leaves and nodes differ.  This domain separation is
		required to give second preimage resistance.)
		Note that we do not require the length of the input list to be a
		power of two.  The resulting Merkle Tree may thus not be balanced;
		however, its shape is uniquely determined by the number of leaves.
		(Note: This Merkle Tree is essentially the same as the history tree
		[CrosbyWallach] proposal, except our definition handles non-full
		trees differently.)
	*/
	k := largestPowerOf2LessThan(n)

	c := []byte{NodePrefix}
	x := t.hash(D[0:k])
	c = append(c, x[:]...)
	x = t.hash(D[k:n])
	c = append(c, x[:]...)
	return sha256.Sum256(c)
}

Merkle Audit Paths (or Proofs)

A Merkle audit path for a leaf in a Merkle Hash Tree is the shortest list of additional nodes in the Merkle Tree required to compute the Merkle Tree Hash for that tree.  Each node in the tree is either a leaf node or is computed from the two nodes immediately below it (i.e., towards the leaves).  At each step up the tree (towards the root), a node from the audit path is combined with the node computed so far.  In other words, the audit path consists of the list of missing nodes required to compute the nodes leading from a leaf to the root of the tree.  If the root computed from the audit path matches the true root, then the audit path is proof that the leaf exists in the tree.

func (t *Tree) path(m uint64, D [][]byte) Path {
	/*
		The path for the single leaf in a tree with a one-element input list
		D[1] = {d(0)} is empty:
		PATH(0, {d(0)}) = {}
	*/
	n := uint64(len(D))
	p := make(Path, 0)
	if n == 1 && m == 0 {
		return p
	}

	/*
		For n > 1, let k be the largest power of two smaller than n.  The
		path for the (m+1)th element d(m) in a list of n > m elements is then
		defined recursively as
		PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and
		PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k,
		where : is concatenation of lists and D[k1:k2] denotes the length
		(k2 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before.
	*/
	k := largestPowerOf2LessThan(n)
	if m < k {
		p = append(p, t.path(m, D[0:k])...)
		p = append(p, t.hash(D[k:n]))
	} else {
		p = append(p, t.path(m-k, D[k:n])...)
		p = append(p, t.hash(D[0:k]))
	}
	return p
}

Merkle Consistency Proofs

Merkle consistency proofs prove the append-only property of the tree. A Merkle consistency proof for a Merkle Tree Hash MTH(D[n]) and a previously advertised hash MTH(D[0:m]) of the first m leaves, m <= n, is the list of nodes in the Merkle Tree required to verify that the first m inputs D[0:m] are equal in both trees.  Thus, a consistency proof must contain a set of intermediate nodes (i.e., commitments to inputs) sufficient to verify MTH(D[n]), such that (a subset of) the same nodes can be used to verify MTH(D[0:m]).  We define an algorithm that outputs the (unique) minimal consistency proof.

func (t *Tree) proof(m uint64, D [][]byte) Path {
	/*
		Given an ordered list of n inputs to the tree, D[n] = {d(0), ...,
		d(n-1)}, the Merkle consistency proof PROOF(m, D[n]) for a previous
		Merkle Tree Hash MTH(D[0:m]), 0 < m < n, is defined as:
		PROOF(m, D[n]) = SUBPROOF(m, D[n], true)
		The subproof for m = n is empty if m is the value for which PROOF was
		originally requested (meaning that the subtree Merkle Tree Hash
		MTH(D[0:m]) is known):
		SUBPROOF(m, D[m], true) = {}
	*/
	n := uint64(len(D))
	if 0 < m && m < n {
		return t.subProof(m, D, true)
	}
	return nil
}

func (t *Tree) subProof(m uint64, D [][]byte, b bool) Path {
	/*
	   The subproof for m = n is the Merkle Tree Hash committing inputs
	   D[0:m]; otherwise:
	   SUBPROOF(m, D[m], false) = {MTH(D[m])}
	   For m < n, let k be the largest power of two smaller than n.  The
	   subproof is then defined recursively.
	   If m <= k, the right subtree entries D[k:n] only exist in the current
	   tree.  We prove that the left subtree entries D[0:k] are consistent
	   and add a commitment to D[k:n]:
	   SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])
	   If m > k, the left subtree entries D[0:k] are identical in both
	   trees.  We prove that the right subtree entries D[k:n] are consistent
	   and add a commitment to D[0:k].
	   SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])
	   Here, : is a concatenation of lists, and D[k1:k2] denotes the length
	   (k2 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before.
	   The number of nodes in the resulting proof is bounded above by
	   ceil(log2(n)) + 1.
	*/

	path := make(Path, 0)
	n := uint64(len(D))

	if m == n {
		if !b {
			path = append(path, t.hash(D))
		}
		return path
	}

	if m < n {
		k := largestPowerOf2LessThan(n)

		if m <= k {
			path = append(path, t.subProof(m, D[0:k], b)...)
			path = append(path, t.hash(D[k:n]))
		} else {
			path = append(path, t.subProof(m-k, D[k:n], false)...)
			path = append(path, t.hash(D[0:k]))
		}
	}
	return path
}

Example

The binary Merkle Tree with 7 leaves:

               hash
              /    \
             /      \
            /        \
           /          \
          /            \
         k              l
        / \            / \
       /   \          /   \
      /     \        /     \
     g       h      i      j
    / \     / \    / \     |
    a b     c d    e f     d6
    | |     | |    | |
   d0 d1   d2 d3  d4 d5

   The audit path for d0 is [b, h, l].

   The audit path for d3 is [c, g, l].

   The audit path for d4 is [f, j, k].

   The audit path for d6 is [i, k].
   
The same tree, built incrementally in four steps:

       hash0          hash1=k
       / \              /  \
      /   \            /    \
     /     \          /      \
     g      c         g       h
    / \     |        / \     / \
    a b     d2       a b     c d
    | |              | |     | |
   d0 d1            d0 d1   d2 d3

             hash2                    hash
             /  \                    /    \
            /    \                  /      \
           /      \                /        \
          /        \              /          \
         /          \            /            \
        k            i          k              l
       / \          / \        / \            / \
      /   \         e f       /   \          /   \
     /     \        | |      /     \        /     \
    g       h      d4 d5    g       h      i      j
   / \     / \             / \     / \    / \     |
   a b     c d             a b     c d    e f     d6
   | |     | |             | |     | |    | |
   d0 d1   d2 d3           d0 d1   d2 d3  d4 d5

   The consistency proof between hash0 and hash is PROOF(3, D[7]) = [c,
   d, g, l].  c, g are used to verify hash0, and d, l are additionally
   used to show hash is consistent with hash0.

   The consistency proof between hash1 and hash is PROOF(4, D[7]) = [l].
   hash can be verified using hash1=k and l.

   The consistency proof between hash2 and hash is PROOF(6, D[7]) = [i,
   j, k].  k, i are used to verify hash2, and j is additionally used to
   show hash is consistent with hash2.

You can find the entire code here

References

• https://security.googleblog.com/2021/07/verifiable-design-in-modern-systems.html#:~:text=A verifiable data structure is,contained within it is correct.

• https://transparency.dev/verifiable-data-structures/

• https://go.googlesource.com/proposal/+/master/design/25530-sumdb.md

• http://transparency.dev/application/strengthen-discovery-of-encryption-keys/

• https://cs.brown.edu/research/pubs/pdfs/2003/Tamassia-2003-ADS.pdf

• https://www.links.org/files/RevocationTransparency.pdf

• https://github.com/BBVA/qed/blob/dc74bcf1b3035493afb95ec046d1f837972bac02/docs/source/internals/glossary.rst