Home

Grupo 7 | Proyecto de Algoritmos y Estructuras de Datos (CS2023) - Teoría 2 | UTEC

Aplicación transaccional con Blockchain en un solo host

Integrantes

• Arteaga Montes, Stuart Diego @SDAM26
• Cahuana Condori, Kelvin Andreí @andrewkc
• Antúnez Alfaro, Max Bryam @MaxAntunez404

1. Introducción

El proyecto se enfoca en la aplicación y exploración de las capacidades del blockchain en un entorno de un solo host. El blockchain, como tecnología de registro distribuido, es ampliamente reconocido por su fiabilidad y seguridad en la gestión de transacciones en diversos sectores. En este proyecto, nos enfocaremos en diseñar y desarrollar una aplicación transaccional que aproveche los beneficios del blockchain, como la inmutabilidad, la transparencia y la seguridad, para gestionar y registrar transacciones de manera eficiente y confiable. Al explorar estas ventajas y limitaciones en un entorno de menor escala y mayor control, podremos obtener una comprensión más profunda de cómo funciona el blockchain y su potencial aplicativo.

2. Descripción del caso de estudio planteado

El proyecto plantea un caso de estudio enfocado en la creación de un sistema de transacciones utilizando las estructuras de datos aprendidas en el curso. Como parte de este proyecto, se introducirá una nueva moneda denominada Messicoin para ser utilizada en el sistema. A través de este caso de estudio, se busca adquirir una comprensión práctica de cómo el blockchain y las criptomonedas pueden desempeñar un papel fundamental en la creación de sistemas de transacciones seguros, eficientes y descentralizados. Además, el proyecto permitirá evaluar el impacto de la implementación de una criptomoneda propia en un sistema transaccional y analizar los beneficios y desafíos que esto conlleva.

3. Importancia del Blockchain

La importancia del blockchain en un sistema de transacciones radica en su capacidad para proporcionar transparencia, seguridad y confianza en el registro y la validación de las transacciones. A continuación, se detallan algunos puntos clave sobre la importancia del blockchain en este contexto:

• Seguridad reforzada : Los datos son sensibles y cruciales, y blockchain puede cambiar significativamente la forma en que se puede visualizar la información crítica. Al crear un registro que no se puede modificar y que cuenta con cifrado end-to-end, blockchain ayuda a prevenir el fraude y la actividad no autorizada. Los problemas de privacidad también se pueden abordar en blockchain mediante el anonimato de los datos personales y el uso de permisos para evitar el acceso.
• Mayor transparencia : Sin blockchain, cada organización debe mantener una base de datos separada. Debido a que blockchain utiliza un registro distribuido, las transacciones y los datos se registran de manera idéntica en múltiples ubicaciones.
• Trazabilidad instantánea : Blockchain crea una pista de auditoría que documenta la procedencia de un activo en cada paso de su recorrido. Esto es particularmente útil en las industrias en las que los consumidores están preocupados por cuestiones ambientales o de derechos humanos que rodean a un producto, o en una industria con problemas de falsificación y fraude.
• Mayor eficiencia y velocidad Los procesos tradicionales que involucran mucho papeleo consumen mucho tiempo, son propensos a errores humanos y, a menudo, requieren la mediación de terceros. Al optimizar estos procesos con blockchain, las transacciones se pueden completar de manera más rápida y eficiente.
• Automatización Las transacciones pueden incluso automatizarse con "contratos inteligentes", que aumentan su eficiencia y aceleran aun más dicho proceso. Una vez que se cumplen las condiciones preestablecidas se activará automáticamente el siguiente paso en la transacción o proceso.

4. Explicación de la estructura de datos Blockchain

La clase BlockChain se compone de una DoubleList, es decir, una lista doblemente enlazada que almacena punteros a objetos de tipo Block. También se almacena un puntero al bloque actual el cual es el último en haber sido añadido a la cadena.

template <typename T>
class BlockChain {
private:
    DoubleList<Block<T>*> chain;
    Block<T>* current; 
    void createGenesisBlock();
    
public:
    BlockChain();
    Block<T>* getBlock(int id) const;
    void addRegister(T reg);
    void updateRegister(T new_reg, int id_block, int id_reg);
    void removeRegister(int id_block, int id_reg); 
    void display();
    int size();
    Index<T>* index{};

    void loadData(std::string filename);
};

La clase Block se compone de un CircularArray en donde se almacena los objetos de tipo Transfer. Por defecto, se debe guardar una cantidad de 5 transacciones en un bloque para que se pueda minar. Además de los otros atributos es importante mencionar al objeto de tipo MerkleTree que se encarga de obtener el "hash root" a partir de todas las transacciones que hay en un bloque.

template <typename T, int N = 5>
class Block {
private:
    static int difficulty;
    static int adjustInterval;
    static int blockSinceAdj;

    std::time_t time_stamp;
    std::string actual_hash; 
    std::string prev_hash; 
    MerkleTree<T> hashTree{};
    bool is_valid;
    int nonce; 
    int id;

public: 
    CircularArray<T, N> data{};
    Block();
    
    void addRegister(T reg); 
    void removeRegister(int index); 
    T& getRegister(int index);

    bool mineBlock();
    bool validateHash(); 
    int size();

    void setId(int id);
    void setPrevHash(std::string prev_hash);
    std::string getHash();
    int getId();

private:
    void adjDifficulty(int& difficulty, long elapsedTime); 
    std::string calculateHash() const;
    bool meetsTarget(const std::string& hash, int difficult);
    
    template <typename T1, int N1>
    friend std::ostream& operator<<(std::ostream& os, const Block<T1, N1>& block);
};

4.1. Estrategia para asegurar la integridad del contenido

Para garantizar la integridad de los datos, se implementaron funciones que permiten obtener el hash de los objetos utilizados. En este caso, se utilizó la biblioteca OpenSSL, la cual proporciona herramientas y algoritmos criptográficos confiables para el cálculo de hashes.

Al utilizar la función de SHA256 de OpenSSL, se pudo obtener un valor hash único para cada objeto utilizado, lo que permite verificar posteriormente si el contenido de los objetos ha sido modificado o manipulado de alguna manera. Esta estrategia de cálculo de hashes asegura que la integridad del contenido se mantenga a lo largo del tiempo y proporciona una medida de confianza en la autenticidad de los datos.

4.2. Implementación del "proof of work"

Previos:

• A cada bloque se le asigna un hash único que se almacena en el atributo actual_hash. Este se obtiene a partir de los siguientes 4 atributos:

  • prev_hash: Hash del bloque anterior.
  • time_stamp: Momento en que se creo el bloque.
  • nonce: Número variable y arbitrario utilizado para encontrar un hash válido del bloque.
  • hashTree: Atributo de tipo MerkleTree que se encarga de obtener el hash de todas las transacciones en conjunto. Este hash de todas las transacciones en conjunto de un bloque se llama hash_root y obtiene invocando a la función hashTree.getRootHash()

• Todo esto es posible haciendo uso del algoritmo criptográfico sha256 que se obtiene del headerfile <openssl/sha.h>.

• Para que el proceso de minado sea más realista, hemos implementado 3 variables estáticas en la clase Block que servirán para ajustar la dificultad para minar un bloque. Estas variables son:

// Dificultad actual para minar un bloque (cantidad de ceros que debe haber al inicio del hash)
template <typename T, int N>
int Block<T, N>::difficulty = 1;

// Cantidad de bloques minados que se debe esperar para llamar a la función `adjDifficulty` que ajusta la difultad. 
template <typename T, int N>
int Block<T, N>::adjustInterval = 3; 

// Contador de bloques minados, toma valores desde 0 hasta el valor de `adjustInterval`. 
template <typename T, int N>
int Block<T, N>::blockSinceAdj = 0;

• Funciones auxiliares para ajustar la dificultad:

// retorna true si el hash tiene al inicio una cantidad de ceros igual al valor de difficult
template <typename T, int N>
bool Block<T, N>::meetsTarget(const std::string& hash, int difficult) {
    std::string prefix(difficult, '0');
    is_valid = (hash.substr(0, difficult) == prefix);
    return is_valid;
}

template <typename T, int N>
void Block<T, N>::adjDifficulty(int& difficulty, long elapsedTime) {
    // elapsedTime: numero de milisegundos que se demora en minar un bloque
    if (difficulty == 1) {
        ++difficulty;
    }
    else if (elapsedTime > 1 && difficulty > 1) 
        --difficulty;
}

Explicación:

• La implementación de "la prueba de trabajo" se realizó en la función miembro mineBlock de la clase Block.

• Cuando se completa la cantidad máxima de transacciones en un bloque se procede a minarlo. Para esto se inicializa la variable startTime con el momento actual. En segundo lugar, se obtiene el hash_root de las transacciones. Luego se entra en un bucle while y se incrementa el valor de nonce para calcular el hash del bloque en base a los atributos mencionados anteriormente. Para ello se llama a la función calculateHash y mientras la función meetsTarget retorne falso se seguirá haciendo más iteraciones en un blucle while con el valor de nonce incrementado en uno en cada iteración. El proceso de obtener el hash del bloque se repite llamando a la función calculateHash hasta que eventualmente se encuentre un hash válido, es decir, que cumpla que comience con una cantidad de ceros igual al valor de la variable difficulty en ese momento. Después, cuando se sale del while se calcula la cantidad de milisegundos que se demoro en minar el bloque y a partir de eso y el valor de difficulty en ese momento se ajusta o no la difultad a llamar a la función adjDifficulty. Finalmente se retorna si un booleano indicando si el bloque es válido.

// Proof of work
template <typename T, int N>
bool Block<T, N>::mineBlock() {
    if (!data.is_full()) 
        throw std::runtime_error("Not allowed to mine an incomplete block");

    std::string hash;
    auto startTime = std::chrono::steady_clock::now();
    hashTree.hasher(data);
    do {
        nonce++;
        hash = calculateHash();
    } while (!meetsTarget(hash, difficulty));

    auto endTime = std::chrono::steady_clock::now();
    auto elapsedTime = std::chrono::duration_cast<std::chrono::milliseconds> (
        endTime - startTime
    ).count();

    actual_hash = hash; // Update block hash after finding valid nonce
    ++blockSinceAdj;
    if (blockSinceAdj >= adjustInterval) {
        adjDifficulty(difficulty, elapsedTime);
        blockSinceAdj = 0;
    }
    return is_valid;
}

template <typename T, int N>
std::string Block<T, N>::calculateHash() const {
    std::ostringstream oss;
    oss << prev_hash << time_stamp << nonce << hashTree.getRootHash();

    const std::string str = oss.str();
    unsigned char digest[SHA256_DIGEST_LENGTH];
    SHA256(reinterpret_cast<const unsigned char*>(str.c_str()), str.length(), digest);

    oss.str("");
    oss << std::hex << std::setfill('0');
    for (unsigned char c : digest) {
        oss << std::setw(2) << static_cast<int>(c);
    }

    return oss.str();
}

Adicional

• Funciones usadas para obtener el hash de cada transacción de un bloque usando métodos de la clase MerkleTree y finalmente encontrar el hash_root.

template <typename T, int N>
void MerkleTree<T, N>::hasher(CircularArray<T, N>& data) {
    hashes.clear(); // remined
    for (int i = 0; i < data.size(); ++i) {
        std::string hash = calculateHash(data[i]);
        hashes.push_back(hash);
    }

    auto hashes_ = hashes;
    // Build the Merkle tree by combining the hashes
    while (hashes_.size() > 1) {
        std::vector<std::string> new_hashes;
        for (std::size_t i = 0; i < hashes_.size(); i += 2) {
            if (i + 1 < hashes_.size()) {
                std::string combined_hash = combineHashes(hashes_[i], hashes_[i + 1]);
                new_hashes.push_back(combined_hash);
            } else {
                new_hashes.push_back(hashes_[i]);
            }
        }
        hashes_ = std::move(new_hashes);
    }

    // Set the final root hash
    root_hash = hashes_.empty() ? "" : hashes_[0];
}

template <typename T, int N>
std::string MerkleTree<T, N>::calculateHash(T& item) const {
    std::ostringstream oss;
    oss << item.getAmount();
    oss << item.getSender();
    oss << item.getReceiver();
    oss << item.getIdBlock();
    oss << item.getTimeStamp();
    const std::string str = oss.str();
    return hashString(str);
}

template <typename T, int N>
std::string MerkleTree<T, N>::combineHashes(std::string& hash1, std::string& hash2) const {
    std::string combined = hash1 + hash2;
    return hashString(combined);
}

template <typename T, int N>
std::string MerkleTree<T, N>::hashString(const std::string& str) const {
    unsigned char digest[SHA256_DIGEST_LENGTH];
    SHA256(reinterpret_cast<const unsigned char*>(str.c_str()), str.length(), digest);

    std::ostringstream oss;
    oss << std::hex << std::setfill('0');
    for (unsigned char c : digest) {
        oss << std::setw(2) << static_cast<int>(c);
    }

    return oss.str();
}

5. Estructuras de datos utilizada en la aplicación

Trie:

template <typename TV>
struct TrieNode {
    std::map<char, TrieNode*> children;
    std::vector<TV> values;
};

template <typename TV>
class Trie {
public:
    Trie();
    void insert(std::string word, TV value);
    void remove(std::string word);
    template <typename FUNCT>
    std::vector<TV> starts_with(std::string prefix, FUNCT get_prefix);

private:
    TrieNode<TV>* root;
};

MerkleTree:

template <typename T, int N = 5>
class MerkleTree {
public:
    std::vector<std::string> hashes;
    std::string root_hash;

public:
    MerkleTree() = default;
    MerkleTree(CircularArray<T, N>& data);
    std::string getRootHash() const;
    void hasher(CircularArray<T, N>& data);

private:
    std::string calculateHash(T& data) const;
    std::string combineHashes(std::string& hash1, std::string& hash2) const;
    std::string hashString(const std::string& str) const;
};

Heap:

template <typename TK, typename TV>
class Heap {
public:
    enum Type {
        MAX_HEAP, MIN_HEAP
    };
private:
    struct Node {
        TK key{};
        TV value{};
    };
    Node* elements;
    int capacity;
    int n;
    Type type;

public:
    Heap(TV* keys, TK* data, int n, Type type = MAX_HEAP);
    Heap(Type type = MAX_HEAP, int capacity = 20);
    ~Heap();
    void buildFromVector(std::vector<TK> keys, std::vector<TV> data, Type type);
    int size();
    bool is_empty();
    void push(TK key, TV value);
    Node pop();
    Node top();
    std::vector<typename Heap<TK, TV>::Node> extractTheTopK(int k);
    static void sortAsc(TK* keys, TV* data, int n);
    static void sortDesc(TV* keys, TK* data, int n);

private:
    void resize();
    void resize(int newCapacity);
    bool inSize(int i);
    int Parent(int i);
    int Left(int i);
    int Right(int i);
    void heapify_down(int i);
    void heapify_up(int i);
};

ForwardList:

template <typename T>
class ForwardList {
public:
    ForwardList();
    ~ForwardList();

    T& front();
    T& back();
    void push_front(T data);
    void push_back(T data);
    T pop_front();
    T pop_back();
    void insert(T data, int index);
    void remove(int index);
    T& operator[](int index);
    bool is_empty();
    int size();
    void clear();
    void display(std::ostream& os);

private:
    struct Node {
        T data{};
        Node* next;

        Node();
        Node(T value);   
    };

    Node* head;
    int nodes;

    Node* get_tail();
    Node* prev(Node* node);
    Node* get_node(int index);
    Node* get_middle(Node* start);
};

DoubleList:

template <typename T>
class DoubleList {
public:
    DoubleList();
    ~DoubleList();
    T& front();
    T& back();
    void push_front(T data);
    void push_back(T data);
    T pop_front();
    T pop_back();
    void insert(T data, int index);
    T remove(int index);
    T& operator[](int index) const;
    bool is_empty();
    int size();
    void clear();

    typedef DoubleListIterator<T> iterator;
    iterator begin();
    iterator end();

private:
    Node<T>* head;
    Node<T>* tail;
    int nodes;
};

CircularList:

template <typename T>
class CircularList {
public:
    CircularList();
    ~CircularList();
    T& front();
    T& back();
    void push_front(T data);
    void push_back(T data);
    T pop_front();
    T pop_back();
    T insert(T data, int pos);
    bool remove(int pos);
    T& operator[](int pos);
    bool is_empty();
    int size();
    void clear();

    typedef CirculatListIterator<T> iterator;
    iterator begin();
    iterator end();

private:
    Node<T>* head; // sentinel
    int nodes;
};

CircularArray :

template <typename T, size_t N = 5>
class CircularArray {  
public:
    CircularArray();
    CircularArray(const CircularArray& other);
    CircularArray<T, N>& operator=(const CircularArray& other);

    ~CircularArray();
    void push_front(T data);
    void push_back(T data);
    T pop_front();
    T pop_back();
    void insert(T data, int index);
    T remove(int index);

    bool is_full();
    bool is_empty();
    int size() const;
    void clear();
    T& operator[](int index) const;

    template <typename T1, size_t N1>
    friend std::ostream& operator<<(std::ostream& os, CircularArray<T1, N1>& arr);

private:
    T* array;
    int back, front;
    int next(int);
    int prev(int);
};

ChainHash :

template <typename TK, typename TV>
class ChainHash {
public:
    ChainHash();
    ~ChainHash();
    void insert(TK key, TV value);
    void remove(TK key);
    TV find(TK key);
    void display();

private:
    struct Entry {
        TK key;
        TV value;

        Entry() = default;
        Entry(TK key, TV value);
    };

    ForwardList<Entry>* array;
    int capacity;
    int size;
    const int MAX_COLLISIONS = 4;
    const float MAX_LOAD_FACTOR = 0.7;

    float load_factor();
    size_t hash_function(TK key);
    void rehashing();
};

BPlusTree :

template <typename TK, typename TV>
class BPlusTree {
public:
    BPlusTree();
    ~BPlusTree();
    void insert(TK key, TV value);
    void remove(TK key);
    TV min();
    TV max();
    TV search(TK key);
    std::vector<TV> rangeSearch(TK start, TK end);
    void displayPretty();
    int height();

private:
    struct Node {
        TK* key;
        TV* value;

        Node** children;
        int count;
        bool leaf;

        Node();
        ~Node();
    };

    Node* root;
    void rangeSearch(Node* node, TK start, TK end, std::vector<TV>& report);
    void insertInternal(TK, TV, Node*, Node*);
    Node* findParent(Node*, Node*);
    void displayGivenLevel(Node* node, int level);
    void removeInternal(TK x, TV y, Node* cursor, Node* child);
};

class Transfer {
private:
    double amount;
    std::string sender;
    std::string receiver;
    std::time_t time_stamp;
    std::size_t id_block;
    
public:
    Transfer();
    Transfer(double amount, std::string sender, std::string receiver);
    double getAmount();
    std::string getSender();
    std::string getReceiver();
    std::size_t getIdBlock();
    std::string getTimeStamp();
    void setIdBlock(std::size_t index);

    friend std::ostream& operator<<(std::ostream& os, const Transfer& Transfer);
};

6. Análisis de complejidad

A continuación, se muestran los resultados de una experimentación donde se compara el tiempo de ejecución de algunas consultas utilizando las estructuras de indexación y obviándolas realizando una búsqueda lineal.

• search: Hash index vs Linear search

Input size (blocks)	Hash index time (ms)	Linear search time (ms)
10	2	5
100	3	25
1 000	2	182
10 000	3	461
100 000	3	2 190

• range_search: B+ Tree index vs Linear search

Input size (blocks)	B+ Tree index time (ms)	Linear search time (ms)
10	1	205
100	3	2 625
1 000	9	2 308
10 000	84	29 229
100 000	405	211 980

• starts_with: Trie index vs Linear search

Input size (blocks)	Trie index time (ms)	Linear search time (ms)
10	2	194
100	4	156
1 000	32	2 863
10 000	45	6 388
100 000	118	18 012

Este análisis empírico muestra el impacto de la indexación de datos sobre los tiempos de acceso.

7. Conclusiones

• El uso de estructuras de datos en la implementación de la Blockchain permite el óptimo performance de la aplicación bancaria.
• Estructuras de indexación permiten el acceso rápido y eficiente a los datos de la Blockchain.

8. Referencias bibliográficas

• Beneficios de blockchain - IBM Blockchain | IBM. (n.d.). https://www.ibm.com/mx-es/topics/benefits-of-blockchain#:~:text=Blockchain%20aumenta%20la%20confianza%2C%20la,gracias%20a%20sus%20nuevas%20eficiencias.&text=Blockchain%20para%20empresas%20utiliza%20un,acceder%20los%20miembros%20con%20permiso.