Merkle-Sum Sparse Merkle Tree (MS-SMT) in Elixir

A Merkle-Sum Sparse Merkle Tree (MS-SMT) is a data structure that combines the features of a Merkle tree and a sum tree, allowing for efficient proofs of inclusion and accumulation of values. It's particularly useful for securely storing large amounts of data with the ability to verify the integrity and sum of the data efficiently.

This Elixir implementation provides a simple and efficient MS-SMT library for use in your projects.

Table of Contents

• Merkle-Sum Sparse Merkle Tree (MS-SMT) in Elixir
  • Table of Contents
  • Installation
  • Usage
    • Basic Operations
    • Generating and Verifying Proofs
  • API Reference
    • MSSMT.new/0
    • MSSMT.insert/3
    • MSSMT.get/2
    • MSSMT.delete/2
    • MSSMT.root_hash/1
    • MSSMT.total_sum/1
    • MSSMT.merkle_proof/2
    • MSSMT.verify_proof/4
  • Development
  • Contributing
  • License

Installation

To use mssmt in your Elixir project, add it to your list of dependencies in mix.exs:

def deps do
  [
    {:mssmt, git: "https://github.com/AbdelStark/mssmt.git", tag: "v0.1.0"}
  ]
end

Then run:

mix deps.get

Usage

Basic Operations

# Import the MSSMT module
import MSSMT

# Create a new empty MS-SMT
tree = MSSMT.new()

# Insert key-value pairs
key1 = :crypto.strong_rand_bytes(32)
key2 = :crypto.strong_rand_bytes(32)
tree = MSSMT.insert(tree, key1, "value1", 100)
tree = MSSMT.insert(tree, key2, "value2", 200)

# Retrieve a value
{:ok, retrieved_value, retrieved_sum} = MSSMT.get(tree, key)

# Delete a key-value pair
{:ok, tree} = MSSMT.delete(tree, key1)

# Calculate root hash
root_hash = MSSMT.root_hash(tree)  # Returns a 32-byte binary hash

# Calculate total sum
total_sum = MSSMT.total_sum(tree)  # Returns 150

Generating and Verifying Proofs

key1 = :crypto.strong_rand_bytes(32)
key2 = :crypto.strong_rand_bytes(32)
key3 = :crypto.strong_rand_bytes(32)
tree = MSSMT.new()
tree = MSSMT.insert(tree, key1, "value1", 100)
tree = MSSMT.insert(tree, key2, "value2", 200)
tree = MSSMT.insert(tree, key3, "value3", 300)

proof = MSSMT.generate_proof(tree, key1)

root_hash = MSSMT.root_hash(tree)

# Verify the proof
is_valid = MSSMT.verify_proof(root_hash, key1, "value1", proof)  # Returns true

# Verify with incorrect value
is_valid = MSSMT.verify_proof(root_hash, key1, "value2", proof)  # Returns false

# Verify with incorrect key
is_valid = MSSMT.verify_proof(root_hash, key2, "value2", proof)  # Returns false

API Reference

MSSMT.new/0

Creates a new empty Merkle-Sum Sparse Merkle Tree.

Example:

tree = MSSMT.new()

MSSMT.insert/3

Inserts a key-value pair into the tree.

• Parameters:
  • tree: The current tree.
  • key: A binary representing the key.
  • value: A numeric value associated with the key.
  • sum: The sum of the value.

Example:

key = :crypto.strong_rand_bytes(32)
{:ok, tree} = MSSMT.insert(tree, key, "value1", 100)

MSSMT.get/2

Retrieves the value associated with a key.

• Parameters:
  • tree: The current tree.
  • key: A binary representing the key.

Returns: The value and sum associated with the key, or {:error, :not_found} if the key does not exist.

Example:

{:ok, retrieved_value, retrieved_sum} = MSSMT.get(tree, key)

MSSMT.delete/2

Deletes a key-value pair from the tree.

• Parameters:
  • tree: The current tree.
  • key: A binary representing the key.

Example:

key = :crypto.strong_rand_bytes(32)
{:ok, tree} = MSSMT.delete(tree, key)

MSSMT.root_hash/1

Calculates the root hash of the tree.

• Parameters:
  • tree: The current tree.

Returns: A 32-byte binary hash representing the root of the tree, or nil if the tree is empty.

Example:

root_hash = MSSMT.root_hash(tree)

MSSMT.total_sum/1

Calculates the total sum of all values in the tree.

• Parameters:
  • tree: The current tree.

Returns: The total sum as a number.

Example:

total_sum = MSSMT.total_sum(tree)

MSSMT.merkle_proof/2

Generates a proof of inclusion for a given key.

• Parameters:
  • tree: The current tree.
  • key: A binary representing the key.

Returns: A list of nodes required to verify the inclusion of the key.

Example:

key = :crypto.strong_rand_bytes(32)
proof = MSSMT.merkle_proof(tree, key)

MSSMT.verify_proof/4

Verifies a proof of inclusion for a given key and value.

• Parameters:
  • root_hash: The root hash of the tree.
  • key: A binary representing the key.
  • value: The numeric value associated with the key.
  • proof: The proof generated by generate_proof/2.

Returns:true if the proof is valid, false otherwise.

Example:

key = :crypto.strong_rand_bytes(32)
is_valid = MSSMT.verify_proof(root_hash, key, "value1", 100, proof)

Development

To set up the project for development:

1. Clone the repository:

   git clone https://github.com/AbdelStark/mssmt.git
   cd mssmt

2. Install dependencies:

   mix deps.get

3. Run tests:

   mix test

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

When contributing, please:

• Write clear, concise commit messages.
• Write tests for new functionality.
• Ensure all tests pass before submitting.

License

This project is licensed under the MIT License - see the LICENSE file for details.