Module: Sigstore::Internal::Merkle

Defined in:
lib/sigstore/internal/merkle.rb

Defined Under Namespace

Classes: InclusionProofSizeError, InvalidInclusionProofError, MissingHashError, MissingInclusionProofError

Class Method Summary collapse

Class Method Details

.chain_border_right(seed, hashes) ⇒ Object 



105
106
107
108
109
 
# File 'lib/sigstore/internal/merkle.rb', line 105

def self.chain_border_right(seed, hashes)
  hashes.reduce(seed) do |acc, hash|
    hash_children(hash, acc)
  end
end

.chain_inner(seed, hashes, log_index) ⇒ Object 



94
95
96
97
98
99
100
101
102
103
 
# File 'lib/sigstore/internal/merkle.rb', line 94

def self.chain_inner(seed, hashes, log_index)
  hashes.each_with_index do |hash, i|
    seed = if ((log_index >> i) & 1).zero?
             hash_children(seed, hash)
           else
             hash_children(hash, seed)
           end
  end
  seed
end

.decompose_inclusion_proof(log_index, tree_size) ⇒ Object 



82
83
84
85
86
87
 
# File 'lib/sigstore/internal/merkle.rb', line 82

def self.decompose_inclusion_proof(log_index, tree_size)
  inner = (log_index ^ (tree_size - 1)).bit_length
  border = (log_index >> inner).to_s(2).count("1")

  [inner, border]
end

.hash_children(left, right) ⇒ Object 



111
112
113
114
 
# File 'lib/sigstore/internal/merkle.rb', line 111

def self.hash_children(left, right)
  data = "\u0001#{left}#{right}".b
  OpenSSL::Digest.new("SHA256").digest(data)
end

.hash_leaf(data) ⇒ Object 



89
90
91
92
 
# File 'lib/sigstore/internal/merkle.rb', line 89

def self.hash_leaf(data)
  data = "\u0000#{data}".b
  OpenSSL::Digest.new("SHA256").digest(data)
end

.root_from_inclusion_proof(log_index, tree_size, proof, leaf_hash) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/sigstore/internal/merkle.rb', line 47

def self.root_from_inclusion_proof(log_index, tree_size, proof, leaf_hash)
  if log_index >= tree_size
    raise InclusionProofSizeError,
          "Log index #{log_index} is greater than tree size #{tree_size}"
  end

  if leaf_hash.bytesize != 32
    raise InvalidInclusionProofError,
          "Leaf hash has wrong size, expected 32 bytes, got #{leaf_hash.size}"
  end

  if proof.any? { |i| i.bytesize != 32 }
    raise InvalidInclusionProofError,
          "Proof hashes have wrong sizes, expected 32 bytes, got #{proof.inspect}"
  end

  inner, border = decompose_inclusion_proof(log_index, tree_size)

  if proof.size != inner + border
    raise InclusionProofSizeError,
          "Inclusion proof has wrong size, expected #{inner + border} hashes, got #{proof.size}"
  end

  intermediate_result = chain_inner(
    leaf_hash,
    (proof[...inner] || raise(MissingHashError, "missing left hashes")),
    log_index
  )

  chain_border_right(
    intermediate_result,
    proof[inner..] || raise(MissingHashError, "missing right hashes")
  )
end

.verify_inclusion(index, tree_size, proof, root, leaf_hash) ⇒ Object

Raises:



37
38
39
40
41
42
43
44
45
 
# File 'lib/sigstore/internal/merkle.rb', line 37

def self.verify_inclusion(index, tree_size, proof, root, leaf_hash)
  calc_hash = root_from_inclusion_proof(index, tree_size, proof, leaf_hash)

  return if calc_hash == root

  raise InvalidInclusionProofError,
        "Inclusion proof contains invalid root hash: " \
        "expected #{root.unpack1("H*")}, calculated #{calc_hash.unpack1("H*")}"
end

.verify_merkle_inclusion(entry) ⇒ Object

Raises:



27
28
29
30
31
32
33
34
35
 
# File 'lib/sigstore/internal/merkle.rb', line 27

def self.verify_merkle_inclusion(entry)
  inclusion_proof = entry.inclusion_proof
  raise MissingInclusionProofError, "Rekor entry has no inclusion proof" unless inclusion_proof

  leaf_hash = hash_leaf(entry.canonicalized_body)
  verify_inclusion(inclusion_proof.log_index, inclusion_proof.tree_size,
                   inclusion_proof.hashes,
                   inclusion_proof.root_hash, leaf_hash)
end