tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

test_mozilla_merkle.py (4588B)

      1 import codecs
      2 import hashlib
      3 import random
      4 import unittest
      5 
      6 import mozunit
      7 from mozharness.mozilla.merkle import InclusionProof, MerkleTree
      8 
      9 decode_hex = codecs.getdecoder("hex_codec")
     10 encode_hex = codecs.getencoder("hex_codec")
     11 
     12 # Pre-computed tree on 7 inputs
     13 #
     14 #         ______F_____
     15 #        /            \
     16 #     __D__           _E_
     17 #    /     \         /   \
     18 #   A       B       C     |
     19 #  / \     / \     / \    |
     20 # 0   1   2   3   4   5   6
     21 hash_fn = hashlib.sha256
     22 
     23 data = [
     24    decode_hex("fbc459361fc111024c6d1fd83d23a9ff")[0],
     25    decode_hex("ae3a44925afec860451cd8658b3cadde")[0],
     26    decode_hex("418903fe6ef29fc8cab93d778a7b018b")[0],
     27    decode_hex("3d1c53c00b2e137af8c4c23a06388c6b")[0],
     28    decode_hex("e656ebd8e2758bc72599e5896be357be")[0],
     29    decode_hex("81aae91cf90be172eedd1c75c349bf9e")[0],
     30    decode_hex("00c262edf8b0bc345aca769e8733e25e")[0],
     31 ]
     32 
     33 leaves = [
     34    decode_hex("5cb551f87797381a24a5359a986e2cef25b1f2113b387197fe48e8babc9ad5c7")[0],
     35    decode_hex("9899dc0be00306bda2a8e69cec32525ca6244f132479bcf840d8c1bc8bdfbff2")[0],
     36    decode_hex("fdd27d0393e32637b474efb9b3efad29568c3ec9b091fdda40fd57ec9196f06d")[0],
     37    decode_hex("c87292a6c8528c2a0679b6c1eefb47e4dbac7840d23645d5b7cb47cf1a8d365f")[0],
     38    decode_hex("2ff3bdac9bec3580b82da8a357746f15919414d9cbe517e2dd96910c9814c30c")[0],
     39    decode_hex("883e318240eccc0e2effafebdb0fd4fd26d0996da1b01439566cb9babef8725f")[0],
     40    decode_hex("bb13dfb7b202a95f241ea1715c8549dc048d9936ec747028002f7c795de72fcf")[0],
     41 ]
     42 
     43 nodeA = decode_hex("06447a7baa079cb0b4b6119d0f575bec508915403fdc30923eba982b63759805")[
     44    0
     45 ]
     46 nodeB = decode_hex("3db98027c655ead4fe897bef3a4b361839a337941a9e624b475580c9d4e882ee")[
     47    0
     48 ]
     49 nodeC = decode_hex("17524f8b0169b2745c67846925d55449ae80a8022ef8189dcf4cbb0ec7fcc470")[
     50    0
     51 ]
     52 nodeD = decode_hex("380d0dc6fd7d4f37859a12dbfc7171b3cce29ab0688c6cffd2b15f3e0b21af49")[
     53    0
     54 ]
     55 nodeE = decode_hex("3a9c2886a5179a6e1948876034f99d52a8f393f47a09887adee6d1b4a5c5fbd6")[
     56    0
     57 ]
     58 nodeF = decode_hex("d1a0d3947db4ae8305f2ac32985957e02659b2ea3c10da52a48d2526e9af3bbc")[
     59    0
     60 ]
     61 
     62 proofs = [
     63    [leaves[1], nodeB, nodeE],
     64    [leaves[0], nodeB, nodeE],
     65    [leaves[3], nodeA, nodeE],
     66    [leaves[2], nodeA, nodeE],
     67    [leaves[5], leaves[6], nodeD],
     68    [leaves[4], leaves[6], nodeD],
     69    [nodeC, nodeD],
     70 ]
     71 
     72 known_proof5 = decode_hex(
     73    "020000"
     74    + "0000000000000007"
     75    + "0000000000000005"
     76    + "0063"
     77    + "20"
     78    + encode_hex(leaves[4])[0].decode()
     79    + "20"
     80    + encode_hex(leaves[6])[0].decode()
     81    + "20"
     82    + encode_hex(nodeD)[0].decode()
     83 )[0]
     84 
     85 
     86 class TestMerkleTree(unittest.TestCase):
     87    def testPreComputed(self):
     88        tree = MerkleTree(hash_fn, data)
     89        head = tree.head()
     90        self.assertEqual(head, nodeF)
     91 
     92        for i in range(len(data)):
     93            proof = tree.inclusion_proof(i)
     94 
     95            self.assertTrue(proof.verify(hash_fn, data[i], i, len(data), head))
     96            self.assertEqual(proof.leaf_index, i)
     97            self.assertEqual(proof.tree_size, tree.n)
     98            self.assertEqual(proof.path_elements, proofs[i])
     99 
    100    def testInclusionProofEncodeDecode(self):
    101        tree = MerkleTree(hash_fn, data)
    102 
    103        # Inclusion proof encode/decode round trip test
    104        proof5 = tree.inclusion_proof(5)
    105        serialized5 = proof5.to_rfc6962_bis()
    106        deserialized5 = InclusionProof.from_rfc6962_bis(serialized5)
    107        reserialized5 = deserialized5.to_rfc6962_bis()
    108        self.assertEqual(serialized5, reserialized5)
    109 
    110        # Inclusion proof encode known answer test
    111        serialized5 = proof5.to_rfc6962_bis()
    112        self.assertEqual(serialized5, known_proof5)
    113 
    114        # Inclusion proof decode known answer test
    115        known_deserialized5 = InclusionProof.from_rfc6962_bis(known_proof5)
    116        self.assertEqual(proof5.leaf_index, known_deserialized5.leaf_index)
    117        self.assertEqual(proof5.tree_size, known_deserialized5.tree_size)
    118        self.assertEqual(proof5.path_elements, known_deserialized5.path_elements)
    119 
    120    def testLargeTree(self):
    121        TEST_SIZE = 5000
    122        ELEM_SIZE_BYTES = 16
    123        data = [
    124            bytearray(random.getrandbits(8) for _ in range(ELEM_SIZE_BYTES))
    125            for _ in range(TEST_SIZE)
    126        ]
    127        tree = MerkleTree(hash_fn, data)
    128        head = tree.head()
    129 
    130        for i in range(len(data)):
    131            proof = tree.inclusion_proof(i)
    132 
    133            self.assertTrue(proof.verify(hash_fn, data[i], i, len(data), head))
    134            self.assertEqual(proof.leaf_index, i)
    135            self.assertEqual(proof.tree_size, tree.n)
    136 
    137 
    138 if __name__ == "__main__":
    139    mozunit.main()