Class: MerkleTree

Inherits:
Object
  • Object
show all
Defined in:
lib/merkletree/version.rb,
lib/merkletree.rb

Overview

note: use class (!) for now and NOT module

Defined Under Namespace

Classes: Node

Constant Summary collapse

MAJOR = 
0
MINOR = 
1
PATCH = 
0
VERSION = 
[MAJOR,MINOR,PATCH].join('.')

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ MerkleTree

Returns a new instance of MerkleTree.



61
62
63
64
65
66
67
68
69
70
 
# File 'lib/merkletree.rb', line 61

def initialize( *args )
  if args.size == 1 && args[0].is_a?( Array )
     hashes = args[0]   ## "unwrap" array in array
  else
     hashes = args      ## use "auto-wrapped" splat array
  end

  @hashes = hashes
  @root   = build_tree
end

Instance Attribute Details

#leaves ⇒ Object (readonly)

Returns the value of attribute leaves.



59
60
61
 
# File 'lib/merkletree.rb', line 59

def leaves
  @leaves
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



58
59
60
 
# File 'lib/merkletree.rb', line 58

def root
  @root
end

Class Method Details



16
17
18
 
# File 'lib/merkletree/version.rb', line 16

def self.banner
  "merkletree/#{VERSION} on Ruby #{RUBY_VERSION} (#{RUBY_RELEASE_DATE}) [#{RUBY_PLATFORM}]"
end

.calc_hash(data) ⇒ Object 



142
143
144
145
146
 
# File 'lib/merkletree.rb', line 142

def self.calc_hash( data )
  sha = Digest::SHA256.new
  sha.update( data )
  sha.hexdigest
end

.compute_root(*args) ⇒ Object

shortcut/convenience - compute root hash w/o building tree nodes



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/merkletree.rb', line 107

def self.compute_root( *args )
  if args.size == 1 && args[0].is_a?( Array )
     hashes = args[0]   ## "unwrap" array in array
  else
     hashes = args      ## use "auto-wrapped" splat array
  end

  ## todo/fix: handle hashes.size == 0 case
  ##   - throw exception - why? why not?
  ##   -  return empty node with hash '0' - why? why not?

  if hashes.size == 1
    hashes[0]
  else
    ## while there's more than one hash in the list, keep looping...
    while hashes.size > 1
      # if number of hashes is odd e.g. 3,5,7,etc., duplicate last hash in list
      hashes << hashes[-1]   if hashes.size % 2 != 0

      ## loop through hashes two at a time
      hashes = hashes.each_slice(2).map do |left,right|
         ## join both hashes slice[0]+slice[1] together
         hash = calc_hash( left + right )
      end
    end

    ## debug output
    ## puts "current merkle hashes (#{hashes.size}):"
    ## pp hashes
    ### finally we end up with a single hash
    hashes[0]
  end
end

.compute_root_for(*args) ⇒ Object 



44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/merkletree.rb', line 44

def self.compute_root_for( *args )
  if args.size == 1 && args[0].is_a?( Array )
     transactions = args[0]   ## "unwrap" array in array
  else
     transactions = args      ## use "auto-wrapped" splat array
  end

  ## for now use to_s for calculation hash
  hashes = transactions.map { |tx| calc_hash( tx.to_s ) }
  self.compute_root( hashes )
end

.for(*args) ⇒ Object

convenience helpers



33
34
35
36
37
38
39
40
41
42
 
# File 'lib/merkletree.rb', line 33

def self.for( *args )
   if args.size == 1 && args[0].is_a?( Array )
      transactions = args[0]   ## "unwrap" array in array
   else
      transactions = args      ## use "auto-wrapped" splat array
   end
   ## for now use to_s for calculation hash
   hashes = transactions.map { |tx| calc_hash( tx.to_s ) }
   self.new( hashes )
end

.root ⇒ Object 



20
21
22
 
# File 'lib/merkletree/version.rb', line 20

def self.root
  "#{File.expand_path( File.dirname(File.dirname(File.dirname(__FILE__))) )}"
end

.version ⇒ Object 



12
13
14
 
# File 'lib/merkletree/version.rb', line 12

def self.version
  VERSION
end

Instance Method Details

#build_tree ⇒ Object 



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/merkletree.rb', line 73

def build_tree
  level = @leaves = @hashes.map { |hash| Node.new( hash, nil, nil ) }

  ## todo/fix: handle hashes.size == 0 case
  ##   - throw exception - why? why not?
  ##   -  return empty node with hash '0' - why? why not?

  if @hashes.size == 1
    level[0]
  else
    ## while there's more than one hash in the layer, keep looping...
    while level.size > 1
      ## loop through hashes two at a time
      level = level.each_slice(2).map do |left, right|
        ## note: handle special case
        # if number of nodes is odd e.g. 3,5,7,etc.
        #   last right node is nil  --  duplicate node value for hash
        ##   todo/check - duplicate just hash? or add right node ref too - why? why not?
        right = left   if right.nil?

        Node.new( MerkleTree.calc_hash( left.value + right.value ), left, right)
      end
      ## debug output
      ## puts "current merkle hash level (#{level.size} nodes):"
      ## pp level
    end
    ### finally we end up with a single hash
    level[0]
  end
end