Merkle Tree Verifier (java, written by Codex)

Codex wrote this java project from the task below. It installed and ran 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 Java project for a clean Ubuntu 22.04 machine with only JDK 17+ installed. Include:
- Source code
- pom.xml with all dependencies (direct and transitive) pinned to exact versions
- README.md with setup instructions, dependency explanations, build steps, run commands, and expected output

[]

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.merkle</groupId>
    <artifactId>merkle-tree-verifier</artifactId>
    <version>1.0.0</version>
    <packaging>jar</packaging>

    <name>Merkle Tree Verifier</name>
    <description>Builds Merkle trees from file collections for integrity verification and efficient change detection</description>

    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    </properties>

    <dependencies>
        <!-- Bouncy Castle: cryptographic provider for secure hash functions -->
        <dependency>
            <groupId>org.bouncycastle</groupId>
            <artifactId>bcprov-jdk18on</artifactId>
            <version>1.77</version>
        </dependency>

        <!-- Picocli: command-line argument parsing with annotations -->
        <dependency>
            <groupId>info.picocli</groupId>
            <artifactId>picocli</artifactId>
            <version>4.7.5</version>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-jar-plugin</artifactId>
                <version>3.3.0</version>
                <configuration>
                    <archive>
                        <manifest>
                            <mainClass>merkle.MerkleTreeVerifier</mainClass>
                        </manifest>
                    </archive>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>

# Merkle Tree Verifier (Java - Trial 1)

## Description

A Java command-line application that builds Merkle trees from file collections for integrity verification and efficient change detection. Uses Bouncy Castle as the cryptographic provider for secure hashing and Picocli for a rich command-line interface with argument parsing.

## Dependencies

- **bouncy-castle** (bcprov-jdk18on 1.77) - A comprehensive Java cryptographic provider offering a wide range of hash algorithms (SHA-256, SHA-512, SHA3, BLAKE2, etc.) used for computing file hashes and combining node hashes in the Merkle tree construction.
- **picocli** (4.7.5) - A modern Java command-line parsing framework with annotation-based argument definition, automatic help generation, type conversion, and subcommand support. Provides the CLI interface for specifying directories, algorithms, and verification options.

## Features

- Build Merkle trees from any directory of files
- Support for multiple hash algorithms via Bouncy Castle (SHA-256, SHA-512, SHA3, etc.)
- Verify directory integrity against a known root hash
- Detect changes between two directories by comparing Merkle trees
- Generate inclusion proofs for individual files
- Visual tree structure display with hash previews
- Export tree structure to file
- Command-line interface with --help, --version, and option flags

## Building and Running

```bash
mvn clean package
java -jar target/merkle-tree-verifier-1.0.0.jar /path/to/directory
```

## CLI Usage

```bash
# Build a Merkle tree from a directory
java -jar merkle-tree-verifier.jar /path/to/dir

# Use SHA-512 instead of SHA-256
java -jar merkle-tree-verifier.jar /path/to/dir -a SHA-512

# Verify against a known hash
java -jar merkle-tree-verifier.jar /path/to/dir -v <expected_hash>

# Compare two directories
java -jar merkle-tree-verifier.jar /path/to/dir1 --diff /path/to/dir2

# Save tree structure to file
java -jar merkle-tree-verifier.jar /path/to/dir -o tree_output.txt
```

package merkle;

import org.bouncycastle.jce.provider.BouncyCastleProvider;
import org.bouncycastle.util.encoders.Hex;
import picocli.CommandLine;
import picocli.CommandLine.Command;
import picocli.CommandLine.Option;
import picocli.CommandLine.Parameters;

import java.io.*;
import java.nio.file.*;
import java.security.*;
import java.util.*;
import java.util.concurrent.Callable;
import java.util.stream.Collectors;

/**
 * Merkle Tree Verifier - Builds Merkle trees from file collections for
 * integrity verification and efficient change detection.
 *
 * Uses Bouncy Castle for cryptographic hash functions and Picocli for
 * command-line interface.
 */
@Command(name = "merkle-tree", mixinStandardHelpOptions = true, version = "1.0.0",
         description = "Builds Merkle trees from file collections for integrity verification.")
public class MerkleTreeVerifier implements Callable<Integer> {

    @Parameters(index = "0", description = "Directory to build Merkle tree from")
    private String directory;

    @Option(names = {"-a", "--algorithm"}, description = "Hash algorithm (default: SHA-256)",
            defaultValue = "SHA-256")
    private String algorithm;

    @Option(names = {"-v", "--verify"}, description = "Verify against a stored root hash")
    private String expectedHash;

    @Option(names = {"-o", "--output"}, description = "Output file for the tree structure")
    private String outputFile;

    @Option(names = {"--diff"}, description = "Compare with another directory")
    private String compareDir;

    static {
        Security.addProvider(new BouncyCastleProvider());
    }

    /**
     * Represents a node in the Merkle tree.
     */
    static class MerkleNode {
        String hash;
        String label;
        MerkleNode left;
        MerkleNode right;
        boolean isLeaf;

        MerkleNode(String hash, String label) {
            this.hash = hash;
            this.label = label;
            this.isLeaf = true;
        }

        MerkleNode(String hash, MerkleNode left, MerkleNode right) {
            this.hash = hash;
            this.left = left;
            this.right = right;
            this.label = "internal";
            this.isLeaf = false;
        }
    }

    /**
     * Computes the hash of a file using the specified algorithm via Bouncy Castle.
     */
    public static String hashFile(Path filePath, String algorithm) throws Exception {
        MessageDigest digest = MessageDigest.getInstance(algorithm, "BC");
        byte[] buffer = new byte[8192];

        try (InputStream is = Files.newInputStream(filePath)) {
            int bytesRead;
            while ((bytesRead = is.read(buffer)) != -1) {
                digest.update(buffer, 0, bytesRead);
            }
        }

        return Hex.toHexString(digest.digest());
    }

    /**
     * Computes the hash of a combined string (for internal nodes).
     */
    public static String hashCombined(String left, String right, String algorithm)
            throws Exception {
        MessageDigest digest = MessageDigest.getInstance(algorithm, "BC");
        digest.update(left.getBytes("UTF-8"));
        digest.update(right.getBytes("UTF-8"));
        return Hex.toHexString(digest.digest());
    }

    /**
     * Collects all files from a directory recursively and returns sorted paths.
     */
    public static List<Path> collectFiles(Path directory) throws IOException {
        if (!Files.isDirectory(directory)) {
            throw new IOException("Not a directory: " + directory);
        }

        return Files.walk(directory)
                .filter(Files::isRegularFile)
                .sorted()
                .collect(Collectors.toList());
    }

    /**
     * Builds leaf nodes from a list of files.
     */
    public static List<MerkleNode> buildLeafNodes(List<Path> files, String algorithm)
            throws Exception {
        List<MerkleNode> leaves = new ArrayList<>();

        for (Path file : files) {
            String hash = hashFile(file, algorithm);
            leaves.add(new MerkleNode(hash, file.getFileName().toString()));
        }

        return leaves;
    }

    /**
     * Builds a Merkle tree from a list of leaf nodes.
     */
    public static MerkleNode buildTree(List<MerkleNode> nodes, String algorithm)
            throws Exception {
        if (nodes.isEmpty()) {
            return new MerkleNode("empty", "empty");
        }

        if (nodes.size() == 1) {
            return nodes.get(0);
        }

        // Pad to even number if necessary
        if (nodes.size() % 2 != 0) {
            nodes.add(nodes.get(nodes.size() - 1));
        }

        List<MerkleNode> parentLevel = new ArrayList<>();
        for (int i = 0; i < nodes.size(); i += 2) {
            String combinedHash = hashCombined(
                    nodes.get(i).hash, nodes.get(i + 1).hash, algorithm);
            parentLevel.add(new MerkleNode(combinedHash, nodes.get(i), nodes.get(i + 1)));
        }

        return buildTree(parentLevel, algorithm);
    }

    /**
     * Builds a complete Merkle tree from a directory.
     */
    public static MerkleNode buildFromDirectory(Path directory, String algorithm)
            throws Exception {
        List<Path> files = collectFiles(directory);
        System.out.println("Found " + files.size() + " files in " + directory);

        List<MerkleNode> leaves = buildLeafNodes(files, algorithm);
        return buildTree(leaves, algorithm);
    }

    /**
     * Prints the tree structure to a StringBuilder.
     */
    public static void printTree(MerkleNode node, StringBuilder sb, String prefix,
                                  boolean isLast) {
        if (node == null) return;

        sb.append(prefix);
        sb.append(isLast ? "+-- " : "|-- ");
        sb.append(node.isLeaf ? node.label + " " : "[internal] ");
        sb.append(node.hash.substring(0, Math.min(16, node.hash.length())));
        sb.append("...\n");

        if (!node.isLeaf) {
            String childPrefix = prefix + (isLast ? "    " : "|   ");
            printTree(node.left, sb, childPrefix, false);
            printTree(node.right, sb, childPrefix, true);
        }
    }

    /**
     * Generates a proof path for a specific leaf.
     */
    public static List<String> generateProof(MerkleNode root, String targetHash,
                                              List<String> proof) {
        if (root == null) return null;

        if (root.isLeaf) {
            if (root.hash.equals(targetHash)) {
                return proof;
            }
            return null;
        }

        List<String> leftProof = new ArrayList<>(proof);
        leftProof.add("R:" + root.right.hash);
        List<String> result = generateProof(root.left, targetHash, leftProof);
        if (result != null) return result;

        List<String> rightProof = new ArrayList<>(proof);
        rightProof.add("L:" + root.left.hash);
        return generateProof(root.right, targetHash, rightProof);
    }

    /**
     * Detects changes between two directories by comparing their Merkle trees.
     */
    public static Map<String, String> detectChanges(Path dir1, Path dir2, String algorithm)
            throws Exception {
        Map<String, String> changes = new LinkedHashMap<>();

        List<Path> files1 = collectFiles(dir1);
        List<Path> files2 = collectFiles(dir2);

        Map<String, String> hashes1 = new LinkedHashMap<>();
        for (Path f : files1) {
            hashes1.put(dir1.relativize(f).toString(), hashFile(f, algorithm));
        }

        Map<String, String> hashes2 = new LinkedHashMap<>();
        for (Path f : files2) {
            hashes2.put(dir2.relativize(f).toString(), hashFile(f, algorithm));
        }

        for (Map.Entry<String, String> entry : hashes1.entrySet()) {
            if (!hashes2.containsKey(entry.getKey())) {
                changes.put(entry.getKey(), "DELETED");
            } else if (!hashes2.get(entry.getKey()).equals(entry.getValue())) {
                changes.put(entry.getKey(), "MODIFIED");
            }
        }

        for (String key : hashes2.keySet()) {
            if (!hashes1.containsKey(key)) {
                changes.put(key, "ADDED");
            }
        }

        return changes;
    }

    @Override
    public Integer call() throws Exception {
        System.out.println("=== Merkle Tree Verifier ===\n");
        System.out.println("Directory: " + directory);
        System.out.println("Algorithm: " + algorithm);

        Path dirPath = Paths.get(directory);
        MerkleNode root = buildFromDirectory(dirPath, algorithm);

        System.out.println("\nMerkle Root: " + root.hash);

        // Print tree structure
        StringBuilder treeSb = new StringBuilder();
        treeSb.append("\nTree Structure:\n");
        printTree(root, treeSb, "", true);
        System.out.print(treeSb);

        // Save to file if requested
        if (outputFile != null) {
            Files.writeString(Paths.get(outputFile), treeSb.toString());
            System.out.println("\nTree saved to: " + outputFile);
        }

        // Verify against expected hash
        if (expectedHash != null) {
            boolean match = root.hash.equals(expectedHash);
            System.out.println("\nVerification: " + (match ? "PASSED" : "FAILED"));
            System.out.println("Expected: " + expectedHash);
            System.out.println("Actual:   " + root.hash);
            return match ? 0 : 1;
        }

        // Diff with another directory
        if (compareDir != null) {
            System.out.println("\nComparing with: " + compareDir);
            Map<String, String> changes = detectChanges(dirPath, Paths.get(compareDir), algorithm);
            if (changes.isEmpty()) {
                System.out.println("No changes detected.");
            } else {
                System.out.println("Changes detected:");
                for (Map.Entry<String, String> entry : changes.entrySet()) {
                    System.out.println("  " + entry.getValue() + ": " + entry.getKey());
                }
            }
        }

        return 0;
    }

    public static void main(String[] args) {
        int exitCode = new CommandLine(new MerkleTreeVerifier()).execute(args);
        System.exit(exitCode);
    }
}