Class: MSSMT::CompressedProof

Inherits:
Proof
  • Object
show all
Defined in:
lib/mssmt/proof.rb

Overview

Compressed MS-SMT merkle proof. Since merkle proofs for a MS-SMT are always constant size (255 nodes), we replace its empty nodes by a bit vector.

Instance Attribute Summary collapse

Attributes inherited from Proof

#nodes

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Proof

#compress

Constructor Details

#initialize(nodes, bits) ⇒ CompressedProof

Constructor its parents to arrive at the root of the MS-SMT. This allows us to efficiently compress proofs by not including any pre-computed nodes.

Parameters:

  • nodes (Array(MSSMT::BranchNode|MSSMT::LeafNode)) —

    Siblings that should be hashed with the leaf and

  • bits (Array) —

    bits determines whether a sibling node within a proof is part of the empty tree.



46
47
48
49
 
# File 'lib/mssmt/proof.rb', line 46

def initialize(nodes, bits)
  super(nodes)
  @bits = bits
end

Instance Attribute Details

#bits ⇒ Object (readonly)

Returns the value of attribute bits.



39
40
41
 
# File 'lib/mssmt/proof.rb', line 39

def bits
  @bits
end

Class Method Details

.decode(data) ⇒ MSSMT::CompressedProof

Decode compressed proof.

Parameters:

  • compressed (String) —

    proof with binary fomat.

Returns:



54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/mssmt/proof.rb', line 54

def self.decode(data)
  buf = data.is_a?(StringIO) ? data : StringIO.new(data)
  nodes_len = buf.read(2).unpack1("n")
  nodes =
    nodes_len.times.map do
      ComputedNode.new(buf.read(32), buf.read(8).unpack1("Q>"))
    end
  bytes = buf.read(MSSMT::Tree::MAX_LEVEL / 8)
  bits = unpack_bits(bytes.unpack("C*"))
  CompressedProof.new(nodes, bits)
end

Instance Method Details

#==(other) ⇒ Object 



94
95
96
97
 
# File 'lib/mssmt/proof.rb', line 94

def ==(other)
  return false unless other.is_a?(CompressedProof)
  bits == other.bits && nodes == other.nodes
end

#decompress ⇒ MSSMT::Proof

Decompress a compressed merkle proof by replacing its bit vector with the empty nodes it represents.

Returns:



68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/mssmt/proof.rb', line 68

def decompress
  count = 0
  full_nodes = []
  bits.each.with_index do |b, i|
    if b
      full_nodes << Tree.empty_tree[Tree::MAX_LEVEL - i]
    else
      full_nodes << nodes[count]
      count += 1
    end
  end
  Proof.new(full_nodes)
end

#encode ⇒ String

Encode the compressed proof.

Returns:

  • (String) —

    encoded string.



84
85
86
87
88
89
90
91
92
 
# File 'lib/mssmt/proof.rb', line 84

def encode
  buf = [nodes.length].pack("n")
  nodes.each do |node|
    buf << node.node_hash
    buf << [node.sum].pack("Q>")
  end
  buf << pack_bits.pack("C*")
  buf
end