Merkle tree using elliptic curve hashes

[HarryR]

In order to use ECC as part of a merkle tree we need to construct a scheme where the collision resistance property is retained at every level, and where proof of the leaf preimage is required.

For zkSNARK circuits it's cheapest if the base point is fixed, this allows pre-computation of exponents of the basepoint to be used as constants in the circuit, so the doubling step is essentially eliminated - and the circuit performs only one addition step for each bit of the scalar exponent - instead of one doubling per bit of the scalar exponent and an additional addition step for every one bit of the scalar.

More specifically we want the Merkle tree to be compatible with Montgomery coordinates from the leaf to the root without requiring conversion to affine coordinates. This implies that the Montgomery X coordinate is maintained throughout, as is the Edwards Y coordinate.

Another restriction is that a third party will be proving the circuit so you can't have any secret information, so for a public key you must provide an EdDSA signature which proves ownership, then the circuit proves that entry exists in the Merkle tree.

Once an EdDSA signature has been provided, then the Y coordinate from the Edwards point of the public key can be used, then converted to Montgomery form, then the tree operates on the Montgomery curve.

The problem is that, for each step in the tree, the user must provide the adjacent point (in this case, just the X coordinate), this introduces an opportunity for malleability.

So an algorithm for the tree is:

def merkletree(P, path):
    BL = # [fixed base point, in montgomery form]
    BR = # [fixed base point, in montgomery form]
    Mx = edwards_xy_to_mont_x(P.x, P.y)
    Mz = 1
    for is_right, path_x in path:
        if is_right:
            Mx,Mz = BL^path_x + BR^Mx
        else:
            Mx,Mz = BL^Mx + BR^path_x
        Mx, Mz = mont_xz_rescale(Mx, Mz)
    return mont_xz_to_edwards_y(Mx, Mz)

Where the resulting Mx is the root of the tree, which can be converted to Edwards YZ coordinates - but it can't be converted to affine coordinates because we don't have a modulo square root function that works on-chain (too expensive). This requires two fixed-point scalar multiplications, one addition and one re-scale per level of the tree.

Is there anything that's more efficient?

[HarryR]

Using the new montgomery form multiplier this can be reduced to 2 constraints per bit.

One thing remaining is to convert the Y coordinate of the resulting point to its bitwise representation again so it can be used as input to another scalar multiply operation.

[HarryR]

Optimised pedersen hashes have now been implemented:

• https://github.com/HarryR/ethsnarks/blob/master/src/jubjub/pedersen_hash.cpp

This can be adopted to be used with the merkle tree:

• https://github.com/HarryR/ethsnarks/blob/master/src/gadgets/merkle_tree.cpp
• https://github.com/HarryR/ethsnarks/blob/master/ethsnarks/merkletree.py