redgold-schema 0.1.0

A relative proof conflict resolution & irreversibility service with trust modeling custodial pooling and executor contracts
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

use std::collections::HashMap;
use crate::structs::{ErrorInfo, Hash, MerkleProof};

#[derive(Debug, Clone)]
pub struct MerkleEntry {
    parent: Hash,
    left: Hash,
    right: Hash,
}

#[derive(Debug, Clone)]
pub struct MerkleTree {
    pub root: Hash,
    pub entries: Vec<MerkleEntry>,
    pub parent_lookup: HashMap<Vec<u8>, MerkleEntry>,
    pub child_to_parent: HashMap<Vec<u8>, MerkleEntry>,
}

impl MerkleTree {

    pub fn new(entries: Vec<MerkleEntry>) -> Self {

        let mut parent_lookup: HashMap<Vec<u8>, MerkleEntry> = HashMap::new();
        let mut child_to_parent: HashMap<Vec<u8>, MerkleEntry> = HashMap::new();
        for entry in &entries {
            parent_lookup.insert(entry.parent.vec(), entry.clone());
            child_to_parent.insert(entry.left.vec(), entry.clone());
            child_to_parent.insert(entry.right.vec(), entry.clone());
        }

        let x = entries.last().expect("Missing root").clone();
        Self {
            root: x.parent,
            entries,
            parent_lookup,
            child_to_parent
        }
    }

    pub fn proof(&self, leaf: Hash) -> MerkleProof {
        let mut merkle_nodes: Vec<Hash> = vec![];
        let mut active = leaf.clone();
        loop {
            let k = active.vec();
            let entry = self.child_to_parent.get(&k);
            if let Some(e) = entry {
                merkle_nodes.push(e.left.clone());
                merkle_nodes.push(e.right.clone());
                active = e.parent.clone();
            } else {
                break;
            }
        }
        MerkleProof{
            root: Some(self.root.clone()),
            leaf: Some(leaf.clone()),
            nodes: merkle_nodes
        }
    }
}

pub fn pad(hashes: &mut Vec<Hash>) {
    if hashes.len() % 2 == 1 {
        hashes.push(hashes.last().unwrap().clone());
    }
}

pub fn build_root(leafs_original: Vec<Hash>) -> Result<MerkleTree, ErrorInfo> {

    let mut leafs = leafs_original.clone();

    if leafs.is_empty() {
        return Err(ErrorInfo::error_info("Merkle tree build must have at least one leaf"));
    }

    let mut entries: Vec<MerkleEntry> = vec![];
    let mut done = false;

    while !done {
        pad(&mut leafs);
        let mut new_leafs: Vec<Hash> = vec![];
        for i in (0..leafs.len()).step_by(2) {
            let left = leafs[i].clone();
            let right = leafs[i + 1].clone();
            let parent = left.merkle_combine(right.clone());
            new_leafs.push(parent.clone());
            entries.push(MerkleEntry {
                parent,
                left,
                right,
            });
        }
        if new_leafs.len() == 1 {
            done = true
        }
        leafs = new_leafs;
    }
    
    Ok(MerkleTree::new(entries))
}