Module: Melos::Struct::RatchetTree

Defined in:
lib/melos/struct/ratchet_tree.rb

Class Method Summary collapse

Class Method Details

.add_leaf_node(tree, node_to_insert) ⇒ Object 



127
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/melos/struct/ratchet_tree.rb', line 127

def self.add_leaf_node(tree, node_to_insert)
  inserted = false
  inserted_node_index = 0
  # if there is a blank in tree, insert there
  tree.each_with_index do |node, node_index|
    if Melos::Tree.leaf?(node_index)
      if tree[node_index].nil?
        tree[node_index] = node_to_insert
        inserted = true
        inserted_node_index = node_index
        break
      end
    else
      # do nothing to a parent
    end
  end
  # if not, extend tree
  if !inserted
    tree << nil
    tree << node_to_insert
    inserted_node_index = tree.count - 1
  end
  # then update unmerged list up till root
  inserted_leaf_index = inserted_node_index / 2
  current_node_index = inserted_node_index
  while(current_node_index != Melos::Tree.root(tree.count))
    if tree[current_node_index] && tree[current_node_index].node_type == 0x02
      tree[current_node_index].parent_node.unmerged_leaves << inserted_leaf_index
    end
    current_node_index = Melos::Tree.parent(current_node_index, tree.count)
  end

  return inserted_leaf_index
end

.calculate_commit_secret(suite, ratchet_tree, update_path, sender_leaf_index, receiver_leaf_index, path_secret) ⇒ Object

Raises:

  • (ArgumentError) 


295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
 
# File 'lib/melos/struct/ratchet_tree.rb', line 295

def self.calculate_commit_secret(suite, ratchet_tree, update_path, sender_leaf_index, receiver_leaf_index, path_secret)
  receiver_node_index = receiver_leaf_index * 2

  filtered_direct_path = Melos::Tree.filtered_direct_path(ratchet_tree, sender_leaf_index * 2)
  raise ArgumentError.new('malformed update path') unless filtered_direct_path.count == update_path.nodes.count
  overlap_node = Melos::Tree.overlap_with_filtered_direct_path(receiver_node_index, filtered_direct_path, Melos::Tree.n_leaves(ratchet_tree))
  overlap_index = filtered_direct_path.find_index { _1 == overlap_node}

  path_secret_n = path_secret
  index = overlap_index
  while filtered_direct_path[index] != Melos::Tree.root(Melos::Tree.n_leaves(ratchet_tree))
    path_secret_n = Melos::Crypto.derive_secret(suite, path_secret_n, "path")
    index += 1
  end
  Melos::Crypto.derive_secret(suite, path_secret_n, "path") # commit secret is node's path_secret +1
end

.calculate_parent_hash(tree, node_index, sibling, suite) ⇒ Object 



87
88
89
90
91
 
# File 'lib/melos/struct/ratchet_tree.rb', line 87

def self.calculate_parent_hash(tree, node_index, sibling, suite)
  parent_node = tree[node_index].parent_node
  sibling_hash = tree_hash_except(tree, sibling, parent_node.unmerged_leaves, suite)
  Melos::Crypto.parent_hash(suite, parent_node.encryption_key, parent_node.parent_hash, sibling_hash)
end

.calculate_parent_hashes(suite, ratchet_tree, leaf_index_from, update_path_nodes) ⇒ Object 



216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/melos/struct/ratchet_tree.rb', line 216

def self.calculate_parent_hashes(suite, ratchet_tree, leaf_index_from, update_path_nodes)
  hashes = []
  filtered_direct_path = Melos::Tree.filtered_direct_path(ratchet_tree, leaf_index_from * 2)
  # count down from root, calculate parent hash
  calculated_parent_hash = ""
  # node_index = Melos::Tree.root(Melos::Tree.n_leaves(ratchet_tree))
  # puts "fdp count: #{filtered_direct_path.count}"
  # puts "update path count: #{nodes_from_update_path.count}"
  hashes[filtered_direct_path.count] = ''
  (filtered_direct_path.count - 1).downto(0) do |path_index|
    node_index = filtered_direct_path[path_index]
    leaf_node_index = leaf_index_from * 2
    sibling_node_index = Melos::Tree.sibling_from_leaf(leaf_node_index, node_index, Melos::Tree.n_leaves(ratchet_tree))
    encryption_key = update_path_nodes[path_index].encryption_key
    sibling_hash = Melos::Struct::RatchetTree.tree_hash(ratchet_tree, sibling_node_index, suite)
    calculated_parent_hash = Melos::Crypto.parent_hash(suite, encryption_key, calculated_parent_hash, sibling_hash)
    hashes[path_index] = calculated_parent_hash
  end

  hashes
end

.decrypt_path_secret(suite, ratchet_tree, encryption_priv_tree, update_path, sender_leaf_index, receiver_leaf_index, group_context, leaves_to_remove = []) ⇒ Object

Raises:

  • (ArgumentError) 


238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
 
# File 'lib/melos/struct/ratchet_tree.rb', line 238

def self.decrypt_path_secret(suite, ratchet_tree, encryption_priv_tree, update_path, sender_leaf_index, receiver_leaf_index, group_context, leaves_to_remove = [])
  receiver_node_index = receiver_leaf_index * 2

  filtered_direct_path = Melos::Tree.filtered_direct_path(ratchet_tree, sender_leaf_index * 2)
  # puts "filtered direct path: #{filtered_direct_path}"
  raise ArgumentError.new('malformed update path') unless filtered_direct_path.count == update_path.nodes.count
  overlap_node = Melos::Tree.overlap_with_filtered_direct_path(receiver_node_index, filtered_direct_path, Melos::Tree.n_leaves(ratchet_tree))
  # puts "overlap node: #{overlap_node}"
  overlap_index = filtered_direct_path.find_index { _1 == overlap_node }
  overlap_node_index = filtered_direct_path[overlap_index]
  # puts "overlap index: #{overlap_index}"
  copath_node_index = Melos::Tree.copath_nodes_of_filtered_direct_path(ratchet_tree, sender_leaf_index * 2)[overlap_index]
  # puts "copath node: #{copath_node_index}"
  resolution_of_copath_node = Melos::Tree.resolution(ratchet_tree, copath_node_index)
  resolution_of_copath_node = resolution_of_copath_node - leaves_to_remove.map{ _1 * 2 } # leaf index -> node index
  # puts "resolution: #{resolution_of_copath_node}"

  priv_key = nil
  priv_index = nil
  resolution_of_copath_node.each_with_index do |res, idx|
    if encryption_priv_tree[res]
      priv_key = encryption_priv_tree[res]
      priv_index = idx
    end
  end

  if priv_key.nil?
    raise ArgumentError.new("priv key not found in tree (sender leaf index: #{sender_leaf_index})")
  end
  target_update_path_node = update_path.nodes[overlap_index]
  target_encrypted_path_secret = target_update_path_node.encrypted_path_secret[priv_index]
  raise ArgumentError.new('# of resolution of copath node does not match with # of encrypted path secrets') unless target_update_path_node.encrypted_path_secret.count == resolution_of_copath_node.count

  # puts "priv_key: #{to_hex priv_key}"
  path_secret = Melos::Crypto.decrypt_with_label(suite, priv_key, "UpdatePathNode", group_context.raw, target_encrypted_path_secret.kem_output, target_encrypted_path_secret.ciphertext)

  # place private keys based on path secret
  update_encryption_priv_tree(suite, ratchet_tree, encryption_priv_tree, overlap_node_index, path_secret)

  path_secret
end

.dump_tree(tree) ⇒ Object

just a test function



313
314
315
316
317
318
319
320
321
322
323
 
# File 'lib/melos/struct/ratchet_tree.rb', line 313

def self.dump_tree(tree)
  tree.each_with_index do |node, index|
    if node.nil?
      puts "#{index}, nil"
    elsif node.parent_node
      puts "#{index}, PN (#{Melos::Util.to_hex(node.public_encryption_key)[0, 8]}) - #{node.parent_node.unmerged_leaves}"
    else
      puts "#{index}, LN (#{Melos::Util.to_hex(node.public_encryption_key)[0, 8]})"
    end
  end
end

.has_parent_hash(tree, child_index, parent_hash_value) ⇒ Object 



110
111
112
113
114
115
116
117
118
119
 
# File 'lib/melos/struct/ratchet_tree.rb', line 110

def self.has_parent_hash(tree, child_index, parent_hash_value)
  resolutions = Melos::Tree.resolution(tree, child_index)
  resolutions.each do |node_index|
    if tree[node_index]&.parent_hash_in_node == parent_hash_value
      # if any of the resolution of specified child has matching parent_hash_value then parent is Parent-Hash Valid wrt that child
      return true
    end
  end
  return false
end

.merge_update_path(suite, ratchet_tree, leaf_index, update_path) ⇒ Object 



195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
 
# File 'lib/melos/struct/ratchet_tree.rb', line 195

def self.merge_update_path(suite, ratchet_tree, leaf_index, update_path)
  node_index_of_leaf = leaf_index * 2
  filtered_direct_path = Melos::Tree.filtered_direct_path(ratchet_tree, node_index_of_leaf)
  nodes_from_update_path = update_path.nodes

  parent_hashes = calculate_parent_hashes(suite, ratchet_tree, leaf_index, update_path.nodes)
  # update parent nodes on path
  filtered_direct_path.each_with_index do |node_index, path_index|
    parent_node = Melos::Struct::ParentNode.create(
      encryption_key: nodes_from_update_path[path_index].encryption_key,
      parent_hash: parent_hashes[path_index + 1],
      unmerged_leaves: []
    )
    node = Melos::Struct::Node.new_parent_node(parent_node)
    ratchet_tree[node_index] = node
  end
  # update leaf
  node = Melos::Struct::Node.new_leaf_node(update_path.leaf_node)
  ratchet_tree[node_index_of_leaf] = node
end

.new(stream) ⇒ Object 



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
# File 'lib/melos/struct/ratchet_tree.rb', line 14

def self.new(stream)
  array = []
  data = Melos::Vec.parse_stringio(stream)
  data_stream = StringIO.new(data)
  while !data_stream.eof?
    presence = data_stream.read(1).unpack1('C')
    case presence
    when 0
      array << nil
    when 1
      node = Melos::Struct::Node.new(data_stream)
      array << node
    end
  end
  array
end

.parse(stream) ⇒ Object 



9
10
11
12
 
# File 'lib/melos/struct/ratchet_tree.rb', line 9

def self.parse(stream)
  stream = StringIO.new(stream) if stream.is_a?(String)
  new(stream)
end

.raw(array) ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/melos/struct/ratchet_tree.rb', line 31

def self.raw(array)
  buf = ''
  array.each do |optional_node|
    if optional_node.nil?
      buf += [0].pack('C')
    else
      buf += [1].pack('C')
      buf += optional_node.raw
    end
  end

  Melos::Vec.from_string(buf)
end

.remove_leaf_node(tree, leaf_index_to_remove) ⇒ Object 



175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/melos/struct/ratchet_tree.rb', line 175

def self.remove_leaf_node(tree, leaf_index_to_remove)
  node_index = leaf_index_to_remove * 2
  tree[node_index] = nil
  # blank the intermediate nodes along the path from sender's leaf to root
  current_node_index = node_index
  while(current_node_index != Melos::Tree.root(tree.count))
    if tree[current_node_index] && tree[current_node_index].node_type == 0x02
      tree[current_node_index] = nil
    end
    current_node_index = Melos::Tree.parent(current_node_index, tree.count)
  end
  # then truncate tree
  Melos::Tree.truncate!(tree)
end

.root_tree_hash(suite, tree) ⇒ Object 



190
191
192
193
 
# File 'lib/melos/struct/ratchet_tree.rb', line 190

def self.root_tree_hash(suite, tree)
  root_index = Melos::Tree.root(Melos::Tree.n_leaves(tree))
  tree_hash(tree, root_index, suite)
end

.tree_hash(tree, node_index, suite) ⇒ Object 



45
46
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
 
# File 'lib/melos/struct/ratchet_tree.rb', line 45

def self.tree_hash(tree, node_index, suite)
  node = tree[node_index]
  if Melos::Tree.leaf?(node_index)
    # is a leaf node
    leaf_index = node_index / 2
    leaf_node_hash_input = [leaf_index].pack('L>')
    if node.nil?
      leaf_node_hash_input += [0].pack('C')
    else
      leaf_node_hash_input += [1].pack('C') + node.leaf_node.raw
    end

    tree_hash_input = [1].pack('C') + leaf_node_hash_input
  else
    # is a parent node, so calculate using ParentNodeHashInput
    parent_node_hash_input = ''
    if node.nil?
      parent_node_hash_input += [0].pack('C')
    else
      parent_node_hash_input += [1].pack('C') + node.parent_node.raw
    end
    parent_node_hash_input += Melos::Vec.from_string(tree_hash(tree, Melos::Tree.left(node_index), suite))
    parent_node_hash_input += Melos::Vec.from_string(tree_hash(tree, Melos::Tree.right(node_index), suite))

    tree_hash_input = [2].pack('C') + parent_node_hash_input
  end

  # The RFC omits the actual definition of calculating a tree hash...
  # it could totally be a ExpandWithLabel-ish thing...
  Melos::Crypto.hash(suite, tree_hash_input)
end

.tree_hash_except(tree, node_index, unmerged_leaves, suite) ⇒ Object 



77
78
79
80
81
82
83
84
85
 
# File 'lib/melos/struct/ratchet_tree.rb', line 77

def self.tree_hash_except(tree, node_index, unmerged_leaves, suite)
  new_tree = tree.dup
  unmerged_leaves.each do |leaf_index|
    node_index_to_remove = leaf_index * 2
    new_tree[node_index_to_remove] = nil
  end

  tree_hash(new_tree, node_index, suite)
end

.update_encryption_priv_tree(suite, ratchet_tree, encryption_priv_tree, start, path_secret) ⇒ Object 



280
281
282
283
284
285
286
287
288
289
290
291
292
293
 
# File 'lib/melos/struct/ratchet_tree.rb', line 280

def self.update_encryption_priv_tree(suite, ratchet_tree, encryption_priv_tree, start, path_secret)
  filtered_direct_path = Melos::Tree.filtered_direct_path(ratchet_tree, start)
  secret = path_secret
  filtered_direct_path = [start] + filtered_direct_path

  filtered_direct_path.each do |n_i|
    node_secret = Melos::Crypto.derive_secret(suite, secret, "node")
    encryption_priv, encryption_pub = Melos::Crypto.derive_key_pair(suite, node_secret)
    encryption_priv_tree[n_i] = encryption_priv
    # puts "n_i #{n_i}: ps: #{to_hex secret} -> ns: #{to_hex node_secret} -> pub: #{to_hex encryption_pub}"
    # p Melos::Crypto.encapsulation_key_pair_corresponds?(suite, encryption_priv, ratchet_tree[n_i].public_encryption_key)
    secret = Melos::Crypto.derive_secret(suite, secret, "path")
  end
end

.update_leaf_node(tree, node_to_update, leaf_index_of_sender) ⇒ Object 



162
163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/melos/struct/ratchet_tree.rb', line 162

def self.update_leaf_node(tree, node_to_update, leaf_index_of_sender)
  node_index = leaf_index_of_sender * 2
  tree[node_index] = node_to_update
  # blank the intermediate nodes along the path from sender's leaf to root
  current_node_index = node_index
  while(current_node_index != Melos::Tree.root(tree.count))
    if tree[current_node_index] && tree[current_node_index].node_type == 0x02
      tree[current_node_index] = nil
    end
    current_node_index = Melos::Tree.parent(current_node_index, tree.count)
  end
end

.verify_parent_hash_at(tree, node_index, suite) ⇒ Object 



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/melos/struct/ratchet_tree.rb', line 93

def self.verify_parent_hash_at(tree, node_index, suite)
  node = tree[node_index]
  if Melos::Tree.leaf?(node_index)
    false # maybe an ArgumentError, because there is no verifying a ParentHash on a leaf node
  else
    if node.nil?
      true
    else
      left_index  = Melos::Tree.left(node_index)
      right_index = Melos::Tree.right(node_index)

      # either the node at node_index is Parent-Hash Valid wrt someone in left tree or someone in right tree
      has_parent_hash(tree, left_index, calculate_parent_hash(tree, node_index, right_index, suite)) || has_parent_hash(tree, right_index, calculate_parent_hash(tree, node_index, left_index, suite))
    end
  end
end

.verify_parent_hash_of_tree(tree, suite) ⇒ Object 



121
122
123
124
125
 
# File 'lib/melos/struct/ratchet_tree.rb', line 121

def self.verify_parent_hash_of_tree(tree, suite)
  parent_indexes = (1..((tree.count - 1) / 2)).map { _1 * 2 - 1} # this makes node_indexes of odd numbers
  parent_indexes_from_bottom_to_top = parent_indexes.sort_by { Melos::Tree.level(_1) } # this sorts node_indexes based on level
  parent_indexes_from_bottom_to_top.all? { verify_parent_hash_at(tree, _1, suite) } # this makes it so that nodes are evaluated from lower level to higher level
end