Merkle root creation and verification in Zencode

[jaromil]

Given an array or dictionary (which can also be deep) and a position in it, plus an hash function (default SHA3-512), produce a Merkle root hash of all the data below the pointer, recursively.

When I create the merkle root of '''
When I create the merkle root of '' at position ''

The 'position' may be searched as a string among the keys of the dictionary (slow and prone to errors) or be better a pointed address or also leverage pointer function defined in PR #752

Consequently make a verification statement that verifies the integrity of a data structure (possibly at position)

When I verify the merkle root '' of ''
When I verify the merkle root '' of '' at position ''

Mockup code in Lua:

local crypto = require("crypto") -- Ensure you have a crypto library for hashing, such as luacrypto or similar

-- Function to hash data using SHA-256
local function hash(data)
    return crypto.digest("sha256", data)
end

-- Function to create a Merkle tree from a table of data
local function create_merkle_tree(data_table)
    local tree = {}

    -- Hash each piece of data and add to the tree
    for _, data in ipairs(data_table) do
        table.insert(tree, hash(data))
    end

    -- Build the tree by hashing pairs of nodes until a single hash (the root) is obtained
    while #tree > 1 do
        local temp_tree = {}
        for i = 1, #tree, 2 do
            if i + 1 <= #tree then
                local concatenated_hashes = tree[i] .. tree[i + 1]
                table.insert(temp_tree, hash(concatenated_hashes))
            else
                table.insert(temp_tree, tree[i])
            end
        end
        tree = temp_tree
    end

    return tree[1] -- The Merkle root
end

-- Function to verify the integrity of a Merkle tree
local function verify_merkle_tree(data_table, merkle_root)
    local computed_root = create_merkle_tree(data_table)
    return computed_root == merkle_root
end

-- Example usage
local data = {
    "data1",
    "data2",
    "data3",
    "data4"
}

local merkle_root = create_merkle_tree(data)
print("Merkle Root: " .. merkle_root)

local is_valid = verify_merkle_tree(data, merkle_root)
print("Is the Merkle tree valid? " .. tostring(is_valid))

-- Modify data to test verification
data[2] = "tampered_data"
local is_valid_after_tampering = verify_merkle_tree(data, merkle_root)
print("Is the Merkle tree valid after tampering? " .. tostring(is_valid_after_tampering))

[matteo-cristino]

what a nice issue to be the 1000th 🎉🎊

[jaromil]

ahahah true! I didn't realized. fun issue indeed 😃🪽