Blind liability proof based on bitcoin merkle trees

gistfile1.rb

# Blind liability proof based on bitcoin merkle trees
module BLProof

  def self.sha256 data
    Digest::SHA256.base64digest(data)
  end

  def self.hash_nodes a, b
    value = a[:value] + b[:value]
    hash = sha256( value.to_s + a[:hash] + b[:hash] )
    { value: value, hash: hash }
  end

  def self.build_tree nodes
    chunks = [ nodes.dup ]
    while chunks.last.size >= 2
      chunks << chunks.last.each_slice(2).map do |a, b = { hash: "", value: 0 }|
        node = hash_nodes(a, b)
        block_given? ? yield(a, b, node) : node
      end
    end
    chunks.flatten
  end

  def self.build_branch nodes, target
    branch = []
    build_tree(nodes) do |a, b, node|
      next node  unless [a, b].include?(target)
      branch << (a == target ? b : a)
      target = node
    end
    branch
  end

  def self.verify_branch branch, target, idx
    branch.map do |node|
      a, b = *( idx & 1 == 0 ? [target, node] : [node, target] )
      idx >>= 1; target = hash_nodes(a, b)
      raise "Node has negative value!"  if target[:value] < 0
      target
    end.last
  end

end


describe BLProof do

  before do
    @accounts = 5.times.map {|i| { hash: "user_#{i}", value: i } }
    @tree = BLProof.build_tree(@accounts)
    @root = @tree.last
  end

  it "should build tree" do
    @tree.last.should == { value: 10, hash: "pIy7AkGdBEsqbO+puBfCg/oVevhw8/Zt6o6BgNbstY4=" }
  end

  it "should build and verify branches" do
    @accounts.each.with_index do |account, idx|
      branch = BLProof.build_branch(@accounts, account)
      BLProof.verify_branch(branch, account, idx).should == @tree.last
    end
  end

  it "should fail verification when negative values are included in the tree" do
    @accounts.first[:value] = -10
    tree = BLProof.build_tree(@accounts)
    branch = BLProof.build_branch(@accounts, @accounts.last)
    expect do
      @accounts.each.with_index do |account, idx|
        branch = BLProof.build_branch(@accounts, account)
        BLProof.verify_branch(branch, account, idx).should == @tree.last
      end
    end.to raise_error("Node has negative value!")
  end

  it "should work for many accounts accounts" do
    2.upto(25).each do |i|
      p [:i ,i]
      accounts = i.times.map {|i| { hash: "user_#{i}", value: i } }
      tree = BLProof.build_tree(accounts)
      root = tree.last
      accounts.each.with_index do |account, idx|
        branch = BLProof.build_branch(accounts, account)
        BLProof.verify_branch(branch, account, idx).should == root
      end
    end
  end

end