fmerg / pymerkle Goto Github PK

100% |████████████████████████████████| 61kB 1.1MB/s 
Complete output from command python setup.py egg_info:
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/tmp/pip-build-iEVtr_/pymerkle/setup.py", line 3, in <module>
    import pymerkle
  File "pymerkle/__init__.py", line 1, in <module>
    from .tree_tools import merkle_tree
  File "pymerkle/tree_tools.py", line 17
    hash_type='sha256',
            ^
SyntaxError: invalid syntax

----------------------------------------

Command "python setup.py egg_info" failed with error code 1 in /tmp/pip-build-iEVtr_/pymerkle/

How can I know that the firstRoot (or challenge) is present in the proof object? I explain...

The proof of consistency verifies that no information was removed/modified between the two roots. To do so (if I understand well), it (I) uses some nodes to verify/calculate the firstRoot, and (II) uses other nodes to verify/calculate the secondRoot (https://www.rfc-editor.org/rfc/rfc9162#name-example).

Therefore, given the proof object, you must (1) execute the function proof.verify(); (2) verify the firstRoot; and (3) verify second root. I imagine that the step 3 involves comparing the secondRoot with the proof.commitment. However, I cannot see how to execute the step 2... I can't see how to get the firstRoot from the proof object.

Example. Given the following code:

from pymerkle import MerkleTree

tree = MerkleTree()

for data in [b'foo', b'bar', b'baz', b'qux', b'quux']:
    tree.encrypt(data)

state1 = tree.get_root_hash()

for data in [b'corge', b'grault', b'garlpy']:
    tree.encrypt(data)

state2 = tree.get_root_hash()

proof = tree.generate_consistency_proof(challenge=state1)
proof.verify()

The consistency proof verifies the consistency between state1 and state2.

The proof object is

    ----------------------------------- PROOF ------------------------------------

    uuid        : 66f2bcbd-9e61-11ed-b276-5ccd5b98eb1b

    timestamp   : 1674837669 (Fri Jan 27 13:41:09 2023)
    provider    : 66ee004e-9e61-11ed-b5de-5ccd5b98eb1b

    hash-type   : SHA256
    encoding    : UTF-8
    security    : ACTIVATED


       [0]   +1   2552e3cbf21513bf4b7a8134e4e4a2e1cd8857cc7fe8a51a455ec226e5cf1e6c
       [1]   +1   2e219794e81e9bb22e230e7f40906eecb4cfcc289e1af253d88b23634266c5a2
       [2]   +1   1c0c3f2623f61894bb6ab743c75efe35632b67985777b7017dedcddc3720aae9
       [3]   -1   5b80e74a146a8a28cf4623b7a2463112f2b98633e4c11874e74117f55f8f291c

    offset      : 1

    commitment  : e45204e846a110051b8848afa80d195317c25554358c5d4e2e1363993dd8537b

    -------------------------------- END OF PROOF --------------------------------

I imagine that you can compare the state2 with proof.commitment. But I cannot see how to verify state1 using this proof...

Can you help me?

Is there a way to make this pymerkle on-disk durable? Keybase's implementation of a merkle tree exposes an key-value interface where you can plug in a durable key-value datastore. https://github.com/keybase/node-merkle-tree

Hello,

I've recently encountered an issue with the resolve method in the code (proof.py). The problem arises from the usage of the match/case statement, a feature that was introduced in Python 3.10. This causes syntax errors when the code is run in environments with Python versions lower than 3.10.

Here is the problematic code snippet:

def resolve(self):
    # ...
    match bit:
        case 0:
            result = self.hash_nodes(result, value)
        case 1:
            result = self.hash_nodes(value, result)
        case _:
            raise Exception('Invalid bit found')
    # ...

To make the code more compatible across different Python environments, I propose changing the match/case statement to an if/elif/else statement. Here's what the revised code would look like:

def resolve(self):
    # ...
    if bit == 0:
        result = self.hash_nodes(result, value)
    elif bit == 1:
        result = self.hash_nodes(value, result)
    else:
        raise Exception('Invalid bit found')
    # ...

This change would not alter the function's behavior and would greatly improve the code's compatibility.

Let me know if you have any questions or require further information.

Hi @fmerg,

Thanks for sharing this cool project.

I'm currently working on stress testing my application, and I've encountered an issue that I believe is related to the codebase. During the stress test, I'm intermittently receiving an "IndexError: pop from an empty deque" error coming from "tree.get_state()".

Under normal circumstances it seems to be functioning correctly, however under stress conditions with many clients, this error is triggered. I've reviewed the code and I've seen you already profiled that particular section of code which made me think maybe is a known issue.

I'm reaching out to see if you or anyone else has encountered a similar issue or if you have any insights into what might be causing this error. Your expertise in this matter would be greatly appreciated.

Thank you in advance for your help. Please let me know if you need more information or if you'd like to discuss this further.

Best regards,
Guillem

def add_record(count, payload):
    leaf_index = tree.append_entry(payload)
    leaf_hash = tree.get_leaf(leaf_index)
    tree_state = tree.get_state(leaf_index)
    tree_index = tree.append_log(leaf_id=leaf_index, digest=tree_state)
    return leaf_index, leaf_hash, tree_index, tree_state

Traceback (most recent call last):
    File "/app/app/controllers/tree.py", line 85, in add_record
        tree_state = tree.get_state(leaf_index)
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 146, in get_state
        return self._get_root(0, size)
               ^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 379, in _get_root
        node = _get_subroot(offset, width)
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 304, in _get_subroot
        return self._get_subroot_uncached(offset, width)
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 348, in _get_subroot_uncached
        rnode = popleft()
                ^^^^^^^^^
IndexError: pop from an empty deque

I'm having problems when creating proofs from dicts or JSON files.

>>> from pymerkle import MerkleTree, validateProof, validationReceipt
>>> 
>>> tree = MerkleTree()                                           # Empty SHA256/UTF-8 Merkle-tree with
>>>                                                               # defense against second-preimage attack
... 
>>> for _ in range(665):                                          # Update the tree with 666 records
...     tree.encryptRecord(bytes('%d-th record' % _, 'utf-8'))
... 
>>> _audit = tree.auditProof('12-th record')                      # Request audit-proof for the given record        
>>> 
>>> validateProof(target_hash=tree.rootHash(), proof=_audit)           # Quick validation of the above proof (True)
True

Afterwards, I get the serialized representation of the proof:

>>> x = _audit.serialize()
>>> 
>>> from pymerkle.proof import Proof

And I create a new proof:

>>> new_proof = Proof(from_dict=x)

Validating new proofs throws this exception:

>>> validateProof(target_hash=tree.rootHash(), proof=new_proof)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/<MY_USER>/.local/lib/python3.7/site-packages/pymerkle/validations.py", line 46, in validateProof
    proof.body['proof_path'], proof.body['proof_index'])
  File "/home/<MY_USER>/.local/lib/python3.7/site-packages/pymerkle/hashing.py", line 230, in multi_hash
    signed_hashes[i][1], signed_hashes[i + 1][1])
  File "/home/<MY_USER>/.local/lib/python3.7/site-packages/pymerkle/hashing.py", line 174, in hash
    first.decode(encoding=self.ENCODING),
AttributeError: 'str' object has no attribute 'decode'

How to get checksum for merkle proof?

Was just wondering if this implementation made use of the sakura tree hash mode standards to prevent hash collisions (appending extra bits to make sure that there is a differentiation between the intermediate nodes and the root)? Will Kangaroo-Twelve ever be implemented with this as well?