Class: Merkle::Config

Inherits:
Object
  • Object
show all
Includes:
Util
Defined in:
lib/merkle/config.rb

Overview

Merkle tree configuration class.

Constant Summary collapse

HASH_TYPES =

Supported Hash type.

[:sha256, :double_sha256]
ELEMENT_ENCODINGS =

How the elements passed to .from_elements are turned into bytes. :hex - each element is a hex string and is decoded before hashing. :binary - each element is already a byte string and is hashed as-is. :auto - each element is decoded if it looks like hex, otherwise hashed as-is.

:auto exists to reproduce roots computed by 0.4.0 and earlier, where this was the only behaviour. Do not choose it for a new protocol: 'hello' and '68656c6c6f' resolve to the same leaf under it, and so do 'AB' and 'ab'. Note it reproduces 0.4.0, not 0.3.1 and earlier, which also padded odd-length hex ('abc' and 'abc0' shared a leaf there).

[:hex, :binary, :auto]

Constants included from Util

Util::HASH_SIZE, Util::MAX_DEPTH

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Util

#bin_to_hex, #combine_sorted, #decode_hash, #hex_string?, #node_hash?, #normalize_hash

Constructor Details

#initialize(element_encoding:, hash_type: :sha256, leaf_tag: '', branch_tag: '', sort_hashes: true) ⇒ Config

Constructor This has no default on purpose. Guessing it silently changes the merkle root. See ELEMENT_ENCODINGS before reaching for :auto. Give this and branch_tag different values so that a leaf hash can never equal an internal node hash. With both left empty the tree is not second-preimage resistant. If you enable this, Merkle::Proof's directions are not required.

Parameters:

  • element_encoding (Symbol) —

    How elements are interpreted, :hex, :binary or :auto.

  • hash_type (Symbol) (defaults to: :sha256) —

    The hashing algorithm used to hash the internal nodes.

  • leaf_tag (String) (defaults to: '') —

    Tag to use when hashing leaves.

  • branch_tag (String) (defaults to: '') —

    Tags to use when hashing internal nodes.

  • sort_hashes (Boolean) (defaults to: true) —

    Whether to sort internal nodes in lexicographical order and hash them.

Raises:

  • (ArgumentError) 


34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/merkle/config.rb', line 34

def initialize(element_encoding:, hash_type: :sha256, leaf_tag: '', branch_tag: '', sort_hashes: true)
  raise ArgumentError, "element_encoding #{element_encoding} does not supported." unless ELEMENT_ENCODINGS.include?(element_encoding)
  raise ArgumentError, "hash_type #{hash_type} does not supported." unless HASH_TYPES.include?(hash_type)
  raise ArgumentError, "leaf_tag must be string." unless leaf_tag.is_a?(String)
  raise ArgumentError, "internal_tag must be string." unless branch_tag.is_a?(String)
  raise ArgumentError, "sort_hashes must be boolean." unless sort_hashes.is_a?(TrueClass) || sort_hashes.is_a?(FalseClass)
  @element_encoding = element_encoding
  @hash_type = hash_type
  # Freeze the tags. A config is shared by every tree built with it, so mutating one in place
  # would change the root of all of them and invalidate proofs already handed out.
  @leaf_tag = leaf_tag.dup.freeze
  @branch_tag = branch_tag.dup.freeze
  @sort_hashes = sort_hashes
end

Instance Attribute Details

#branch_tag ⇒ Object (readonly)

Returns the value of attribute branch_tag.



20
21
22
 
# File 'lib/merkle/config.rb', line 20

def branch_tag
  @branch_tag
end

#element_encoding ⇒ Object (readonly)

Returns the value of attribute element_encoding.



20
21
22
 
# File 'lib/merkle/config.rb', line 20

def element_encoding
  @element_encoding
end

#hash_type ⇒ Object (readonly)

Returns the value of attribute hash_type.



20
21
22
 
# File 'lib/merkle/config.rb', line 20

def hash_type
  @hash_type
end

#leaf_tag ⇒ Object (readonly)

Returns the value of attribute leaf_tag.



20
21
22
 
# File 'lib/merkle/config.rb', line 20

def leaf_tag
  @leaf_tag
end

#sort_hashes ⇒ Object (readonly)

Returns the value of attribute sort_hashes.



20
21
22
 
# File 'lib/merkle/config.rb', line 20

def sort_hashes
  @sort_hashes
end

Class Method Details

.bitcoin(element_encoding:) ⇒ Merkle::Config

Bitcoin configuration.

Parameters:

  • element_encoding (Symbol) —

    How elements are interpreted, :hex, :binary or :auto.

Returns:



52
53
54
 
# File 'lib/merkle/config.rb', line 52

def self.bitcoin(element_encoding:)
  Config.new(element_encoding: element_encoding, hash_type: :double_sha256, sort_hashes: false)
end

.taptree(element_encoding:) ⇒ Merkle::Config

Taptree configuration.

Parameters:

  • element_encoding (Symbol) —

    How elements are interpreted, :hex, :binary or :auto.

Returns:



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

def self.taptree(element_encoding:)
  Config.new(element_encoding: element_encoding, leaf_tag: 'TapLeaf', branch_tag: 'TapBranch')
end

Instance Method Details

#encode_element(element) ⇒ String

Convert element into the byte string to be hashed, following element_encoding.

Parameters:

  • element (String) —

    An element as given to .from_elements.

Returns:

  • (String) —

    Byte string.

Raises:

  • (ArgumentError) —

    If element does not match element_encoding.



67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/merkle/config.rb', line 67

def encode_element(element)
  raise ArgumentError, "element must be string." unless element.is_a?(String)
  case element_encoding
  when :hex
    raise ArgumentError, "element must be a hex string." unless hex_string?(element)
    [element].pack('H*')
  when :binary
    element.b
  when :auto
    hex_string?(element) ? [element].pack('H*') : element.b
  end
end

#tagged_hash(data, tag = branch_tag) ⇒ String

Generate tagged hash. data is always hashed as a byte string. To hash an element written as hex, pass it through #encode_element first.

Parameters:

  • data (String) —

    The data to be hashed.

  • tag (String) (defaults to: branch_tag) —

    Tag string used tagging.

Returns:

  • (String) —

    Tagged hash value.

Raises:

  • (ArgumentError) 


85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/merkle/config.rb', line 85

def tagged_hash(data, tag = branch_tag)
  raise ArgumentError, "data must be string." unless data.is_a?(String)
  raise ArgumentError, "tag must be a String." unless tag.is_a?(String)

  data_bin = data.b

  unless tag.empty?
    tag_bin = Digest::SHA256.digest(tag).b
    data_bin = tag_bin + tag_bin + data_bin
  end

  case hash_type
  when :sha256
    Digest::SHA256.digest(data_bin)
  when :double_sha256
    Digest::SHA256.digest(Digest::SHA256.digest(data_bin))
  end
end