Transaction re-play protection

[HarryR]

There are two modes of operation for the merkle tree:

1. Updates in-place
2. Nullify & append

The first approach proves the path and preimage of a leaf, then updates it with a new leaf.

The second approach keeps the 'discarded' items in the tree, and appends a new item along with a 'nullifier' that prevents double spends.

In order to maintain privacy (e.g. not revealing which item is changing hands) the merkle tree authentication path must remain secret. In the first approach you don't get privacy if you have to provide the tree paths to a third party to roll-up, it just provides transaction aggregation.

Lets say we use the first approach for roll_up, where updates to the database are authenticated by some criteria (proof of a preimage), the authentication path is verified, and a new leaf is provided, then the new root is calculated.

The problem is if you are performing multiple updates at the same time which share intermediate nodes, one would overwrite anothers root if calculated separately as the path for the next item (which shares a common ancestor) wouldn't have the updated values.

Anyway.... that means doing in-place updates where n-items > 2 is more complicated, but lets stay on track and just solve the replay protection problem.

---

Each leaf has a unique ID, say the serial number of absolute offset at the lowest level of the tree.

You must prove, using a signature (or other piece of private information) that you are authorised to modify that leaf.

There are a few formats for the leaf:

• leaf = H(pubkey)
• leaf = H(offset, pubkey)
• leaf = H(offset, nonce, pubkey)
• leaf = H(image)
• leaf = H(offset, image)
• leaf = H(offset, nonce, image)

The offset makes that leaf unique, e.g. if two public keys were used for different leafs, a signature for a public key that's used by multiple leaves could be used to modify multiple leaves. You would need to sign H(offset, new-owner) with the public key to provide a unique signature for that specific leaf to unlock it and transfer to a new owner.

But then there's the problem if the same public key is given ownership of the leaf again, its previous signature could be used to transfer it back to whomever had it before. So we use nonce as a sequence for that specific leaf to order a series of operations and prevent replays like that.

We can't use image as proof of the preimage would need to be distributed to the transaction aggregator... which means we have to use signatures.

All of the parameters for the leaf and transaction need to be signed, these are:

• offset
• nonce
• new-owner

So: SIGN(H(old_leaf, new-owner), secret-key) is provided with the authentication path and public key (assuming it can't be recovered from the signature).

The circuit for verification would be something like:

def transaction(offset, nonce, new_owner_pubkey, pubkey, signature, path, root):
    old_leaf = H(offset, nonce, pubkey)
    assert merkle_verify(old_leaf, path) == root
    assert signature_verify(H(old_leaf, new_owner_pubkey), signature)
    new_leaf = H(offset, nonce + 1, new_owner_pubkey)
    return merkle_update(old_leaf, new_leaf, path)

This introduces a new problem: From just the leaf hash and the offset you can't determine the nonce or the public key - this is data that needs to be available.

The data that needs to be available, after each modification to the root is the new values of:

• offset, nonce, new_owner_pubkey