---
title: Generic Tangle
tags: RFC, draft
---

# Summary

This RFC proposes a new crate - `bee-tangle` - that introduces functionalities for an in-memory Tangle cache implementation and transaction buffer, that sits infront of the storage layer, and reduces the amount of disk reads and writes. Since research around the IOTA protocol is still ongoing and changes in the details are quite likely, the proposal accomodates for that by making the `Tangle` abstraction itself generic o

# Motivation

The IOTA distributed ledger is built on top of a specific type of directed acyclic graph (DAG). This datastructure consists of vertices where each of them can reference at least one or at most 2 other vertices, but can be referenced `n` times.

# Detailed design

This RFC proposes ...

## `TransactionRef`

use bee_transaction::bundled::BundledTransaction as Transacion;

/// A thread-safe reference to a `bee_transaction:BundledTransaction`.
#[derive(Clone)]
struct TransactionRef(Arc<Transaction>);

impl Deref for TransactionRef {
    type Target = Transaction;

    fn deref(&self) -> &Self::Target {
        &*self.0
    }
}

## `Vertex`

The Tangle is a graph datastructure, that can be described as a tuple of two sets `(V, E)`, whereby `V` denotes the set of all vertices, and `E` the set of all edges that exist in the graph.

#[derive(Clone)]
struct Vertex<T>
where
    T: Clone + Copy,
{
    transaction: TxRef,
    metadata: T,
}

impl<T> Vertex<T>
where
    T: Clone + Copy,
{
    fn new(transaction: Tx, metadata: T) -> Self {
        Self {
            transaction: TxRef(Arc::new(transaction)),
            metadata,
        }
    }

    fn trunk(&self) -> &TxHash {
        self.transaction.trunk()
    }

    fn branch(&self) -> &TxHash {
        self.transaction.branch()
    }

    fn transaction(&self) -> &TxRef {
        &self.transaction
    }

    fn metadata(&self) -> &T {
        &self.metadata
    }

    fn metadata_mut(&mut self) -> &mut T {
        &mut self.metadata
    }
}

## `Tangle`

/// A foundational, thread-safe graph datastructure to represent the IOTA Tangle.
struct Tangle<T>
where
    T: Clone + Copy,
{
    vertices: DashMap<TxHash, Vertex<T>>,
    children: DashMap<TxHash, HashSet<TxHash>>,
    tips: DashSet<TxHash>,
}

TODO: can we just derive `Default`?

### Tangle API

//
fn insert(&self, hash: TxHash, transaction: Tx, metadata: T) -> Option<TxRef> { }


// 
fn get(&self, hash: &TxHash) -> Option<TxRef> { }

fn contains(&self, hash: &TxHash) -> bool

fn get_metadata(&self, hash: &TxHash) -> Option<T>

/// Updates the metadata of a particular vertex.
fn set_metadata(&self, hash: &TxHash, metadata: T) {

/// Updates the metadata of a vertex.
fn update_metadata<Update>(&self, hash: &TxHash, update: Update)
where
    Update: Fn(&mut T),
{ }

/// Returns the number of transactions in the Tangle.
fn len(&self) -> usize { }

/// Returns the children of a vertex.
fn get_children(&self, hash: &TxHash) -> HashSet<TxHash> { }

## Traversal

# Drawbacks

* Uses ternary hashes for comparison
* Hashmaps

# Rationale and Alternatives

* Transactions are uniquely identified by their transaction hash. Therefore it seems self-evident to build the graph datastructure on top of hashmaps. Performing walks on the tangle becomes a series of hashmap lookups and hash comparisons. Especially in the case of ternary hashes this might be sub-optimal. On the other hand, this makes the implementation and memory management very straight forward;
* Instead of using `TxHash` as key for the hashmaps/sets, one could introduce a `struct TxKey(Option<TxIndex>, TxHash)`, and derive `Eq, PartialEq, Hash` for this type together with an internar that produces a `TxIndex`.

# Unresolved questions

* The Tangle implementation is - at the moment - only generic over the metadata stored alongside a transaction. It might be useful to generalize also over the concrete type of transaction.