Merkle Tree Verifier (cpp, written by Codex)

--- /dev/null
+++ b/setup.sh
@@ -0,0 +1,6 @@
+#!/bin/bash
+# System packages this project needs on a clean Ubuntu machine.
+set -e
+export DEBIAN_FRONTEND=noninteractive
+apt-get update -qq
+apt-get install -y -qq --no-install-recommends libssl-dev nlohmann-json3-dev

Codex wrote this cpp project from the task below. It does not run on a clean Ubuntu 22.04 machine as written.

Task given to the agent:

TASK: Merkle Tree Verifier

Write a program that builds Merkle trees from file collections and uses them to verify data integrity, detect modifications, and efficiently identify which specific files have changed.

FUNCTIONAL REQUIREMENTS:
- Accept a directory path as a command-line argument
- Build a Merkle tree by computing SHA-256 hashes of each file (leaf nodes), then iteratively hashing pairs of child hashes up to a single root hash
- Support two modes via subcommands: build (create tree and save) and verify (check against saved tree)
- build: Compute the Merkle tree and save the tree structure (root hash, intermediate hashes, leaf hashes with file paths) to a JSON manifest file via --output flag (default: merkle_tree.json)
- verify: Load a saved Merkle tree and compare against current file state, efficiently identifying exactly which files were modified, added, or deleted without rehashing unchanged branches
- Display the tree structure visually in the console using ASCII tree formatting showing hash prefixes at each level
- Support configurable hash algorithm via --algorithm flag: SHA-256 (default), SHA-512, SHA3-256
- Support file filtering via --exclude flag with glob patterns to skip certain files
- Compute and display tree statistics: total files (leaf nodes), tree depth, total nodes, root hash, and build time
- Support comparing two Merkle trees via --diff flag: show which subtrees differ between two previously built trees
- Support incremental updates via --update flag: rebuild only changed subtrees rather than the entire tree
- Print verification results to console: root hash match status, list of modified/added/deleted files with their old and new hashes
- If no arguments are given, create a sample directory with 16 files, build the Merkle tree, display the tree structure, then modify 2 files, delete 1, add 1, and run verification to demonstrate efficient change detection
- Handle errors: empty directories, permission denied on files, files modified during tree building, and corrupted manifest files

Create a complete C++ project for a clean Ubuntu 22.04 machine with only G++ 12+ and CMake 3.22+ installed. Include:
- Source code
- CMakeLists.txt with all dependencies (direct and transitive) pinned to exact versions
- README.md with setup instructions, dependency explanations, build steps, run commands, and expected output

[
  {
    "category": "underspecification",
    "rule": "signature.missing_system_requirement",
    "source": "failure_signature",
    "excerpt": "Could NOT find OpenSSL, try to set the path to OpenSSL root folder in the"
  },
  {
    "category": "underspecification",
    "rule": "diff.adds_external_environment_requirement",
    "source": "manifest_diff:setup.sh",
    "excerpt": "export DEBIAN_FRONTEND=noninteractive"
  },
  {
    "category": "underspecification",
    "rule": "diff.adds_external_environment_requirement",
    "source": "manifest_diff:setup.sh",
    "excerpt": "apt-get install -y -qq --no-install-recommends libssl-dev nlohmann-json3-dev"
  }
]

cmake_minimum_required(VERSION 3.14)
project(MerkleTreeVerifier VERSION 1.0 LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

find_package(OpenSSL REQUIRED)
find_package(nlohmann_json REQUIRED)

add_executable(merkle_tree src/main.cpp)

target_link_libraries(merkle_tree PRIVATE
    OpenSSL::SSL
    OpenSSL::Crypto
    nlohmann_json::nlohmann_json
)

# Merkle Tree Verifier

Builds Merkle trees from files for integrity verification and change detection.

## Dependencies
- **OpenSSL** - Cryptographic hashing (SHA-256, SHA-512, etc.)
- **nlohmann_json** - JSON serialization for tree export/import

## Build

```bash
mkdir build && cd build
cmake ..
make
```

## Usage

### Build a Merkle tree
```bash
./merkle_tree build /path/to/directory --output tree.json
```

### Verify integrity
```bash
./merkle_tree verify /path/to/directory tree.json
```

### Compare directories
```bash
./merkle_tree diff /path/to/dir1 /path/to/dir2
```

/**
 * Merkle Tree Verifier
 * Builds Merkle trees from files for integrity verification and change detection.
 * Uses OpenSSL for cryptographic hashing and nlohmann_json for JSON serialization.
 */

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <memory>
#include <algorithm>
#include <filesystem>
#include <chrono>
#include <iomanip>
#include <cassert>

#include <openssl/evp.h>
#include <openssl/sha.h>
#include <nlohmann/json.hpp>

namespace fs = std::filesystem;
using json = nlohmann::json;

// Utility: convert bytes to hex string
std::string bytes_to_hex(const unsigned char* data, size_t len) {
    std::ostringstream oss;
    for (size_t i = 0; i < len; ++i) {
        oss << std::hex << std::setw(2) << std::setfill('0') << (int)data[i];
    }
    return oss.str();
}

// Hash a string using OpenSSL EVP
std::string hash_string(const std::string& input, const std::string& algo = "sha256") {
    const EVP_MD* md = EVP_get_digestbyname(algo.c_str());
    if (!md) throw std::runtime_error("Unknown hash algorithm: " + algo);

    unsigned char digest[EVP_MAX_MD_SIZE];
    unsigned int digest_len = 0;

    EVP_MD_CTX* ctx = EVP_MD_CTX_new();
    EVP_DigestInit_ex(ctx, md, nullptr);
    EVP_DigestUpdate(ctx, input.c_str(), input.size());
    EVP_DigestFinal_ex(ctx, digest, &digest_len);
    EVP_MD_CTX_free(ctx);

    return bytes_to_hex(digest, digest_len);
}

// Hash a file using OpenSSL EVP with streaming
std::string hash_file(const std::string& filepath, const std::string& algo = "sha256") {
    const EVP_MD* md = EVP_get_digestbyname(algo.c_str());
    if (!md) throw std::runtime_error("Unknown hash algorithm: " + algo);

    std::ifstream file(filepath, std::ios::binary);
    if (!file.is_open()) throw std::runtime_error("Cannot open file: " + filepath);

    EVP_MD_CTX* ctx = EVP_MD_CTX_new();
    EVP_DigestInit_ex(ctx, md, nullptr);

    char buffer[8192];
    while (file.read(buffer, sizeof(buffer)) || file.gcount() > 0) {
        EVP_DigestUpdate(ctx, buffer, file.gcount());
    }

    unsigned char digest[EVP_MAX_MD_SIZE];
    unsigned int digest_len = 0;
    EVP_DigestFinal_ex(ctx, digest, &digest_len);
    EVP_MD_CTX_free(ctx);

    return bytes_to_hex(digest, digest_len);
}

struct MerkleNode {
    std::string hash_value;
    std::shared_ptr<MerkleNode> left;
    std::shared_ptr<MerkleNode> right;
    std::string source;

    bool is_leaf() const { return !left && !right; }

    json to_json() const {
        json j;
        j["hash"] = hash_value;
        if (!source.empty()) j["source"] = source;
        if (left) j["left"] = left->to_json();
        if (right) j["right"] = right->to_json();
        return j;
    }
};

class MerkleTree {
public:
    MerkleTree(const std::string& algorithm = "sha256")
        : algorithm_(algorithm), root_(nullptr), build_time_(0.0) {}

    void build_from_directory(const std::string& dir_path) {
        std::vector<std::string> files;
        for (const auto& entry : fs::recursive_directory_iterator(dir_path)) {
            if (entry.is_regular_file()) {
                files.push_back(entry.path().string());
            }
        }
        std::sort(files.begin(), files.end());
        build_from_files(files);
    }

    void build_from_files(const std::vector<std::string>& file_paths) {
        auto start = std::chrono::high_resolution_clock::now();
        leaves_.clear();

        for (const auto& fp : file_paths) {
            auto node = std::make_shared<MerkleNode>();
            node->hash_value = hash_file(fp, algorithm_);
            node->source = fp;
            leaves_.push_back(node);
        }

        root_ = build_tree(leaves_);
        auto end = std::chrono::high_resolution_clock::now();
        build_time_ = std::chrono::duration<double>(end - start).count();
    }

    std::string get_root_hash() const {
        if (!root_) throw std::runtime_error("Tree not built");
        return root_->hash_value;
    }

    struct ProofStep {
        std::string direction;
        std::string hash;
    };

    std::vector<ProofStep> generate_proof(size_t leaf_index) const {
        if (leaf_index >= leaves_.size()) throw std::out_of_range("Invalid leaf index");

        std::vector<ProofStep> proof;
        auto nodes = leaves_;
        size_t idx = leaf_index;

        while (nodes.size() > 1) {
            if (nodes.size() % 2 != 0) {
                auto dup = std::make_shared<MerkleNode>();
                dup->hash_value = nodes.back()->hash_value;
                nodes.push_back(dup);
            }
            size_t sibling = (idx % 2 == 0) ? idx + 1 : idx - 1;
            std::string dir = (idx % 2 == 0) ? "right" : "left";
            proof.push_back({dir, nodes[sibling]->hash_value});

            std::vector<std::shared_ptr<MerkleNode>> next_level;
            for (size_t i = 0; i < nodes.size(); i += 2) {
                auto parent = std::make_shared<MerkleNode>();
                parent->hash_value = hash_pair(nodes[i]->hash_value, nodes[i + 1]->hash_value);
                parent->left = nodes[i];
                parent->right = nodes[i + 1];
                next_level.push_back(parent);
            }
            nodes = next_level;
            idx /= 2;
        }
        return proof;
    }

    bool verify_proof(const std::string& leaf_hash, const std::vector<ProofStep>& proof,
                      const std::string& root_hash) const {
        std::string current = leaf_hash;
        for (const auto& step : proof) {
            if (step.direction == "right") {
                current = hash_pair(current, step.hash);
            } else {
                current = hash_pair(step.hash, current);
            }
        }
        return current == root_hash;
    }

    std::vector<size_t> detect_changes(const MerkleTree& other) const {
        std::vector<size_t> changed;
        size_t max_len = std::max(leaves_.size(), other.leaves_.size());
        for (size_t i = 0; i < max_len; ++i) {
            if (i >= leaves_.size() || i >= other.leaves_.size()) {
                changed.push_back(i);
            } else if (leaves_[i]->hash_value != other.leaves_[i]->hash_value) {
                changed.push_back(i);
            }
        }
        return changed;
    }

    void export_json(const std::string& filepath) const {
        if (!root_) throw std::runtime_error("Tree not built");
        json j;
        j["algorithm"] = algorithm_;
        j["root_hash"] = root_->hash_value;
        j["leaf_count"] = leaves_.size();
        j["build_time_seconds"] = build_time_;
        j["tree"] = root_->to_json();

        std::ofstream out(filepath);
        out << j.dump(2);
    }

    void print_summary() const {
        std::cout << "=== Merkle Tree Summary ===" << std::endl;
        std::cout << "Algorithm: " << algorithm_ << std::endl;
        std::cout << "Root Hash: " << get_root_hash() << std::endl;
        std::cout << "Leaf Count: " << leaves_.size() << std::endl;
        std::cout << "Build Time: " << build_time_ << "s" << std::endl;
        std::cout << "===========================" << std::endl;
    }

    double get_build_time() const { return build_time_; }
    size_t leaf_count() const { return leaves_.size(); }

private:
    std::string hash_pair(const std::string& a, const std::string& b) const {
        return hash_string(a + b, algorithm_);
    }

    std::shared_ptr<MerkleNode> build_tree(std::vector<std::shared_ptr<MerkleNode>> nodes) {
        if (nodes.size() == 1) return nodes[0];
        if (nodes.size() % 2 != 0) {
            auto dup = std::make_shared<MerkleNode>();
            dup->hash_value = nodes.back()->hash_value;
            dup->source = nodes.back()->source;
            nodes.push_back(dup);
        }

        std::vector<std::shared_ptr<MerkleNode>> parents;
        for (size_t i = 0; i < nodes.size(); i += 2) {
            auto parent = std::make_shared<MerkleNode>();
            parent->hash_value = hash_pair(nodes[i]->hash_value, nodes[i + 1]->hash_value);
            parent->left = nodes[i];
            parent->right = nodes[i + 1];
            parents.push_back(parent);
        }
        return build_tree(parents);
    }

    std::string algorithm_;
    std::shared_ptr<MerkleNode> root_;
    std::vector<std::shared_ptr<MerkleNode>> leaves_;
    double build_time_;
};

int main(int argc, char* argv[]) {
    if (argc < 2) {
        std::cout << "Merkle Tree Verifier" << std::endl;
        std::cout << "Usage:" << std::endl;
        std::cout << "  " << argv[0] << " build <directory> [--output tree.json] [--algo sha256]" << std::endl;
        std::cout << "  " << argv[0] << " verify <directory> <tree.json>" << std::endl;
        std::cout << "  " << argv[0] << " diff <dir1> <dir2>" << std::endl;
        return 1;
    }

    std::string command = argv[1];
    std::string algo = "sha256";

    // Parse --algo flag
    for (int i = 2; i < argc - 1; ++i) {
        if (std::string(argv[i]) == "--algo") algo = argv[i + 1];
    }

    if (command == "build" && argc >= 3) {
        std::string dir = argv[2];
        MerkleTree tree(algo);
        tree.build_from_directory(dir);
        tree.print_summary();

        // Check for --output flag
        for (int i = 3; i < argc - 1; ++i) {
            if (std::string(argv[i]) == "--output") {
                tree.export_json(argv[i + 1]);
                std::cout << "Exported to " << argv[i + 1] << std::endl;
            }
        }
    } else if (command == "verify" && argc >= 4) {
        std::string dir = argv[2];
        std::string tree_file = argv[3];

        std::ifstream f(tree_file);
        json saved = json::parse(f);

        MerkleTree tree(saved.value("algorithm", "sha256"));
        tree.build_from_directory(dir);

        if (tree.get_root_hash() == saved["root_hash"].get<std::string>()) {
            std::cout << "VERIFIED: Integrity intact." << std::endl;
        } else {
            std::cerr << "FAILED: Content modified!" << std::endl;
            return 1;
        }
    } else if (command == "diff" && argc >= 4) {
        std::string dir1 = argv[2];
        std::string dir2 = argv[3];

        MerkleTree t1(algo), t2(algo);
        t1.build_from_directory(dir1);
        t2.build_from_directory(dir2);

        auto changes = t1.detect_changes(t2);
        std::cout << "Root match: " << (t1.get_root_hash() == t2.get_root_hash() ? "yes" : "no") << std::endl;
        std::cout << "Changed files: " << changes.size() << std::endl;
        for (auto idx : changes) {
            std::cout << "  [" << idx << "]" << std::endl;
        }
    } else {
        std::cerr << "Invalid command or arguments." << std::endl;
        return 1;
    }

    return 0;
}