rht/merkle-tree

An implementation of a Merkle Tree in PHP

2.0.0 2020-11-02 05:11 UTC

Requires

• php: >=7.0

Requires (Dev)

• php-coveralls/php-coveralls: ^2.4
• phpunit/phpunit: ^6.5 || ^7.5 || ^8.5 || ^9.4
• sanmai/phpunit-legacy-adapter: ^6 || ^8

BSD-2-Clause

• Matt Nagi

README

This is an implementation of a hash tree or Merkle Tree for PHP.

Install

Install via Composer (make sure you have composer in your path or in your project).

Put the following in your package.json:

{
    "require": {
        "rht/merkle-tree": "*"
    }
}

Then run composer install.

Usage For A Fixed Size Tree

Usage of a hash tree requires a user to provide a hashing function that each node will use to do its hashing. This function must accept a single string argument and must always return a string. It should never throw an exception.

If desired, you can also provide a callback for when the entire hash tree has been actually finished, rather than checking for it each time yourself.

<?php
use Rht\Merkle\FixedSizeTree;

require 'vendor/autoload.php';

// basically the same thing bitcoin merkle tree hashing does
$hasher = function ($data) {
    return hash('sha256', hash('sha256', $data, true), true);
};

$finished = function ($hash) {
    echo implode('', unpack('H*', $hash)) . "\n";
};

$tree = new FixedSizeTree(16, $hasher, $finished);

$tree->set(0, 'Science');
$tree->set(1, 'is');
$tree->set(2, 'made');
$tree->set(3, 'up');
$tree->set(4, 'of');
$tree->set(5, 'so');
$tree->set(6, 'many');
$tree->set(7, 'things');
$tree->set(8, 'that');
$tree->set(9, 'appear');
$tree->set(10, 'obvious');
$tree->set(11, 'after');
$tree->set(12, 'they');
$tree->set(13, 'are');
$tree->set(14, 'explained');
$tree->set(15, '.'); // this will echo the string 'c689102cdf2a5b30c2e21fdad85e4bb401085227aff672a7240ceb3410ff1fb6'

This fork of https://github.com/pleonasm/merkle-tree has a FixedSizeTree which implements a Merkle Patricia Tree the same way Ethereum does. While pleonasm/merkle-tree implements it in the same way bitcoins do. There are other ways to actually deal with a tree width that is not a perfect square.

If there is a need for the other method, I would not be opposed to adding it.

Upgrading from 1.0

The difference between 1.0 and 2.0 from the outside should be very minimal. If you're only using the public interface of FixedSizeTree minus a few error handling changes, then you should be good to go.

The new implementation is greatly simplified and is far faster for large trees. My latest benchmark put 1.0 taking 100 seconds to fill a 10000 item tree while 2.0 takes 0.2 seconds.

That said, it is technically a backwards incompatible change so a major version bump is in order.

License

You can find the license for this code in the LICENSE file