Efficient data structures in Blockchain / Solidity - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Merkle Tree in blockchain?

A Merkle Tree is a tree data structure where each leaf node is a hash of a data block, and each non-leaf node is a hash of its children. It allows efficient and secure verification of large data sets.

beginner

Why are hash maps useful in blockchain?

Hash maps provide fast data retrieval by using a hash function to map keys to values, which helps in quick lookups of transactions or account states in blockchain systems.

intermediate

Explain the role of Patricia Tries in Ethereum.

Patricia Tries combine prefix trees and hash trees to efficiently store and retrieve key-value pairs, enabling Ethereum to manage its state with fast lookups and secure proofs.

beginner

What makes linked lists less efficient for blockchain data storage?

Linked lists require sequential access, which is slower for lookups compared to trees or hash maps. This makes them less suitable for blockchain where fast verification is needed.

intermediate

How do bloom filters improve blockchain performance?

Bloom filters are space-efficient probabilistic data structures that quickly test whether an element is in a set, reducing the need to check every transaction and improving performance.

What is the main advantage of using a Merkle Tree in blockchain?

A Reducing block size

B Faster transaction processing

C Efficient verification of data integrity

D Increasing mining rewards

Merkle Trees allow efficient and secure verification of large data sets by hashing data in a tree structure.

Which data structure combines prefix trees and hash trees in Ethereum?

A Binary Search Tree

B Patricia Trie

C Linked List

D Bloom Filter

Patricia Tries efficiently store and retrieve key-value pairs in Ethereum by combining prefix and hash trees.

What is a key benefit of using bloom filters in blockchain?

A Space-efficient membership testing

B Exact data retrieval

C Faster mining

D Increasing block size

Bloom filters quickly test if an element is in a set using little space, improving performance.

Why are linked lists less preferred for blockchain data storage?

A They require sequential access slowing lookups

B They use too much memory

C They are too complex to implement

D They do not support hashing

Linked lists require sequential access which slows down data lookups compared to trees or hash maps.

Hash maps in blockchain help mainly with:

A Storing blocks sequentially

B Generating new blocks

C Encrypting transactions

D Fast data retrieval using keys

Hash maps provide fast lookups by mapping keys to values, useful for quick access to blockchain data.

Describe how Merkle Trees help ensure data integrity in blockchain.

Think about how small changes affect hashes and how the tree helps check data quickly.

Explain the importance of Patricia Tries in managing Ethereum's state.

Consider how Ethereum needs to store and verify many accounts and contracts efficiently.

Practice

1. Which data structure is best for quickly finding a user's balance by their blockchain address?

easy

A. Array

B. Mapping (key-value pairs)

C. Struct

D. Linked list

Solution

1. Step 1: Understand the need for quick lookup

   We want to find a balance by address fast, so we need a structure that supports direct access by key.

2. Step 2: Identify the best data structure

   Mappings provide key-value pairs allowing O(1) access by address, unlike arrays or structs which require searching.

3. Final Answer:

   Mapping (key-value pairs) -> Option B

4. Quick Check:

   Fast key-based lookup = Mapping [OK]

Hint: Use mappings for direct key lookups in blockchain [OK]

Common Mistakes:

• Choosing arrays which require looping to find an address
• Using structs alone without a key for lookup
• Thinking linked lists are efficient for random access

2. Which of the following is the correct syntax to declare a mapping from address to uint in Solidity?

easy

A. mapping(address => uint) balances;

B. mapping(address, uint) balances;

C. mapping[address] uint balances;

D. mapping{address: uint} balances;

Solution

1. Step 1: Recall Solidity mapping syntax

   Mappings use the syntax mapping(keyType => valueType) variableName;

2. Step 2: Match the correct syntax

   mapping(address => uint) balances; matches this exactly: mapping(address => uint) balances;

3. Final Answer:

   mapping(address => uint) balances; -> Option A

4. Quick Check:

   Correct mapping syntax uses '=>' [OK]

Hint: Remember mapping uses '=>' between key and value types [OK]

Common Mistakes:

• Using commas instead of '=>' in mapping
• Using square brackets or curly braces incorrectly
• Omitting the semicolon at the end

3. What will be the output of this Solidity code snippet?

struct User { uint id; string name; }
User[] users;
users.push(User(1, "Alice"));
users.push(User(2, "Bob"));
string memory name = users[1].name;

medium

A. "Alice"

B. Empty string

C. Compilation error

D. "Bob"

Solution

1. Step 1: Understand array indexing

   Arrays start at index 0, so users[0] is Alice, users[1] is Bob.

2. Step 2: Identify the accessed element

   The code accesses users[1].name, which is "Bob".

3. Final Answer:

   "Bob" -> Option D

4. Quick Check:

   Index 1 in array = "Bob" [OK]

Hint: Remember arrays start at zero index [OK]

Common Mistakes:

• Confusing index 1 with index 0
• Assuming structs print as variable names
• Expecting compilation error due to string usage

4. Identify the error in this Solidity code snippet:

mapping(address => uint) balances;
function addBalance(address user, uint amount) public {
  balances[user] += amount;
}

medium

A. Cannot use '+=' on mapping values

B. Function lacks visibility modifier

C. No initialization needed for mapping values

D. Mapping keys must be uint, not address

Solution

1. Step 1: Check mapping usage

   Mappings default to zero for uint values if key not set, so no initialization needed.

2. Step 2: Verify function and operation

   Using '+=' on balances[user] is valid; function has public visibility.

3. Final Answer:

   No initialization needed for mapping values -> Option C

4. Quick Check:

   Mapping uint defaults to 0, so '+=' works [OK]

Hint: Mapping values default to zero, no init needed [OK]

Common Mistakes:

• Thinking mapping values must be initialized before use
• Confusing visibility modifiers
• Assuming keys must be uint instead of address

5. You want to store user profiles with id, name, and balance, and quickly find a profile by id. Which data structure combination is most efficient in Solidity?

hard

A. Mapping from id to struct

B. Array of structs only

C. Struct with embedded array

D. Linked list of structs

Solution

1. Step 1: Analyze the need for quick lookup by id

   Quick lookup by id requires direct access, which arrays or linked lists cannot provide efficiently.

2. Step 2: Choose the best data structure

   Mapping from id to struct allows O(1) access to user profiles by id, combining grouping (struct) and fast lookup (mapping).

3. Final Answer:

   Mapping from id to struct -> Option A

4. Quick Check:

   Fast key access + grouped data = mapping to struct [OK]

Hint: Use mapping from id to struct for fast profile lookup [OK]

Common Mistakes:

• Using arrays which require looping to find id
• Using linked lists which are slow for random access
• Embedding arrays inside structs without mapping