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 = 
1
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.



81
82
83
84
85
86
87
88
89
90
 
# File 'lib/merkletree.rb', line 81

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.



79
80
81
 
# File 'lib/merkletree.rb', line 79

def leaves
  @leaves
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



78
79
80
 
# File 'lib/merkletree.rb', line 78

def root
  @root
end

Class Method Details



14
15
16
 
# File 'lib/merkletree/version.rb', line 14

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

.calc_hash(data) ⇒ Object 



163
164
165
166
167
 
# File 'lib/merkletree.rb', line 163

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



128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/merkletree.rb', line 128

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 



64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/merkletree.rb', line 64

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



53
54
55
56
57
58
59
60
61
62
 
# File 'lib/merkletree.rb', line 53

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 



18
19
20
 
# File 'lib/merkletree/version.rb', line 18

def self.root
  File.expand_path( File.dirname(File.dirname(File.dirname(__FILE__))) )
end

.version ⇒ Object 



10
11
12
 
# File 'lib/merkletree/version.rb', line 10

def self.version
  VERSION
end

Instance Method Details

#build_tree ⇒ Object 



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/merkletree.rb', line 93

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