FIELD_SIZE need to change. Is this possible?

[gmisiakoulis]

Hello,

I am trying to use the MerkleTreeWithHistory.sol smart contract, and I am trying to pass address type (converted to bytes32), as _insert function expects, and raise an error, when reaching the hashLeftRight. The error states: "_left should be inside the field", which means that the uint256 representation of an address produce a number greater that the FIELD_SIZE.

Is this possible to change? And if yes, how?

I am trying to use the circom-ecdsa circuit located here. The circuit expects as input a ethereum private key, extracts the public key and calculates the eth address as the BigInt representation, which later this BigInt is going to be passed to a Merkle Tree as leaf.
Meaning that if we pass an address 0x7c5E44C6074Fb29B309f4AbAE9bF790ba338A208, the circuit returns 710017116651888399609443089319006059204116521480.

Now I managed to do the same with solidity, but the MerkleTreeWithHistory.sol return the aforementioned error. The circuit works fine without problems. A solution would be to incread the FIELD_SIZE, but I do not know whether it is feasible or not.

Thanks in advance.

[TheBojda]

I'm not a ZKP expert, but as I know FIELD_SIZE is a large prime number for the finite field math, and I'm not sure that you can change it.

MerkleTreeWithHistory is from the source code of TornadoCache, and it is for storing the commitments which are 31 bytes. Why would you store addresses here?

Btw, an Ethereum address is 20 bytes, so it should be smaller than the FIELD_SIZE.

[gmisiakoulis]

The idea is that we use ZKP circuit, to prove that a user is eligible to perform specific operations on a smart contract. For example if we had a Merkle Tree with N users (thus N addresses), someone can prove that his address exists in the Merkle Tree, either using software of onchain to fetch the pathElements and pathIndices. These variables would then be imported in this circuit which is an extension of the link I provided above:

include "./MerkleTreeChecker.circom";
include "./eth_addr.circom";

template VotingLeaderEligibilityChecker(n, k, levels) {
 signal input privkey[k];
 signal input pathElements[levels];
 signal input pathIndices[levels];
 signal output root;

 // PrivKeyToAddr will compute the address given the private key
 // Keys are encoded as (x, y) pairs with each coordinate being
 // encoded with k registers of n bits each
 component privToAddr = PrivKeyToAddr(n, k);
 for (var i = 0; i < k; i++) {
        privToAddr.privkey[i] <== privkey[i];
 }
 
 // Verifies that merkle proof is correct for given merkle root and a leaf
 // pathIndices input is an array of 0/1 selectors telling whether given pathElement 
 // is on the left or right side of merkle path
 component merkleTreeChecker = MerkleTreeChecker(levels);
 merkleTreeChecker.leaf <== privToAddr.addr; 
 for (var i = 0; i < levels; i++) {
        merkleTreeChecker.pathElements[i] <== pathElements[i];
        merkleTreeChecker.pathIndices[i] <== pathIndices[i];
 }

 root <== merkleTreeChecker.root;
}

component main = VotingLeaderEligibilityChecker(64, 4, 3);

This circuit expects the user's private key, pathElements and pathIndices as private inputs and calculates the root.
The circuit is working very well using the output of the software function calculateMerkleRootAndPath and calculates the same root. Now the problem is in this line: merkleTreeChecker.leaf <== privToAddr.addr;, the privToAddr.addr returns the address in BIGINT type, much larger.

The addresses are indeed 20 bytes, but the circuit output is a BIGINT number, so we had to do the same with Solidity using the following convertion:

 function addressToBigint(address _addr) public pure returns (uint256) {
  // Convert the address to a uint160, then to a uint256
  uint256 bigintValue = uint256(uint160(_addr));
  return bigintValue;
 }

in order to be consistent with the circuit's output. The _insert function expects bytes32 which we do the convention, but when the function reaches the hasLeftRight function, which expects the uint256 type as input, there the problem appears.

As I can see and please correct me I am wrong or if you have any ideas, either a way must be found to convert the BIGINT circuit output to hex address type and pass the address as leaf in the MerkleTreeChecker and then convert the address to bytes32 (not the BIGINT) in Solidity, or probably we need to cut some bytes from the BIGINT from both circuit and Solidity, in order to be consistent.

Do you have any ideas?

[TheBojda]

Hmm. One of the possible solutions is if you split your address into parts (10-10 bytes), and calculates the mimc hash of it as TC calculates the commitment from the nullifier and the secret (https://github.com/TheBojda/zk-merkle-tree/blob/main/src/zktree.ts#L21). This hash should be small enough.

What I don't really understand is the context of this thing. Why do you need addresses in the tree? Why don't you use commitments and nullifiers to prove you have permission? Only the user knows the secret to generate the zkp for the nullifier, so a nullifier is something like a public key, and the secret is like a private key. I don't know your whole use case, but it could be implemented simply in the original way (using commitment, secret, and nullifier).

[gmisiakoulis]

Yes, excellent question, the user still have to provide the proofs about the creation of the nullifier. The main idea behind this, is if we have voting groups (specific users that can vote) for one election. The voter could provide zkp Merkle Proofs for on-chain verification and if the root existed in the history then the user would be able to proceed with the commitment and nullifier procedure. This is to prove the eligibility of a voter to vote in a specific election.

[TheBojda]

If I understand well, you don't need ZKP for this because you don't have to hide the address of the voter in the registration phase. Simply build a Merkle tree off-chain, and store the Merkle root. When the user sends the commitment, she has to also send a Merkle proof (no ZKP needed) that proves she is in the group. So the registration is public, and only the voting itself (by using the nullified) is anonymous.

There are many implementations for verifying Merkle proofs, like OpenZeppelin's util: https://docs.openzeppelin.com/contracts/5.x/api/utils#MerkleProof

[gmisiakoulis]

Well, in ZKP it is considered a very good practice instead of sending the actual Merkle Proof, to send ZKP proofs to a Verifier, stating that you possess a Merkle Proof that can resolve to a Merkle's Tree Root. This is considered safer option as you eventually hide the actual Merkle Proof from the public, and you pass it as input to a ZKP circuit. The output of this circuit is the root. If the root exists in history this means that the Prover is right and has actual and correct Merkle Proofs in his possession.