c-geek / merkle

Node.js module implementing Merkle tree algorithm
MIT License
125 stars 32 forks source link

Add 2 functions given by some contributor #10

Closed c-geek closed 8 years ago

c-geek commented 8 years ago

Someone proposed 2 tree traversal functions by e-mail.

Would be nice to test them and integrate if it works as expected:

function ProofPaths(tree) {
  var Paths = [];  
  var Leafs = tree.level(tree.depth());
  for(var n = 0; n < Leafs.length; n++) {
    Paths.push({
      proof: Leafs[n],
      path: ProofPath(tree, n)
    });
  }
  return Paths;
}
function ProofPath(tree, n) {
  var Path = []; 
  var Leafs = tree.level(tree.depth());
  if(n < Leafs.length) {
    var nParent = Math.floor(n/2);        
    for(l = tree.depth() - 1; l >= 0; l--) {
      var ParentLevel = tree.level(l);
      var ChildLevel = tree.level(l+1);
      Path.push({
        left: ChildLevel[2*nParent],
        parent: ParentLevel[nParent],
        right: (2*nParent+1) >= ChildLevel.length ? "" : ChildLevel[2*nParent+1]
      });
      nParent = Math.floor(nParent/2);
    }
  }
  return Path;
}
jasonbukowski commented 8 years ago

I have recently published a companion module to this one which builds these same proof paths. It will construct the proof path, has an option to include/exclude the 'parent' values as they can be seen as redundant, can be called with either a tree leaf index or a target index value, and includes tests.

https://github.com/Tierion/merkle-proof

I'm open to to creating a new branch in this project and integrating my proof path code and tests into this if you'd like.

c-geek commented 8 years ago

Would be very glad to see a pull request of yours about it. If tests pass, I will integrate it for sure and increment version too.

c-geek commented 8 years ago

Fixed in #11.