Pedersen vs Poseidon Merkle Tree Gas Comparison

[0xDegenDeveloper]

Hey guys quick question. I'm running some tests to compare the gas consumption for both tree types to determine the cheaper one to use in my contract (typical WL mint setup).

Other devs I'm working with initially said that Poseidon would be cheaper for 1) Creating the leaf hash & 2) Verifying the (root, leaf, proof) call.

My gas tests are calling .verify() using the same root, leaf, and proof (proof -> list of length 20).

On Goerli, the gas consumption for Pedersen is 1698 and for Poseidon is 1701. And the breakdown on Katana is

• Pedersen: Steps: 6748 | ECDSA: 1 | L1 Gas: 2448 | Pedersen: 36 | Range Checks: 230
• Poseidon: Steps: 7329 | ECDSA: 1 | L1 Gas: 2448 | Pedersen: 16 | Poseidon Builtin: 40 | Range Checks: 230

Can you guys offer any input ? Am I getting incorrect outputs ? Or is the initial assumption of Poseidon being cheaper wrong ?

[feltroidprime]

Hi.
The gas fees you're getting on Starknet is currently using the same weight for Pedersen and Poseidon Hash. However they are " wrong " compared to their real costs.

This is due to the layout used that has some specific ratios between number of steps and number of builtin used, and it effectively limits the number of builtin you can use in a given cairo program relatively to the number of steps.

However this is fortunately going to change with dynamic layouts, where depending on the number of resources you've used in your transaction, you will be charged accordingly and precisely because they will compute a layout specially made for what you've used.

Basically you should view your cairo program as a matrix.
1 step in the VM is ~ 50 Cells.
1 Range check is worth ~ 1 step as well (not 16x!!)
1 Poseidon is 600 cells
1 Pedersen is 3000 cells

Note that the gas usage you see locally (not on testnet or mainnet) with the latest version of cairo reflects this dynamic cost property.
So you should compare your two versions locally and not on chain if you want to see the difference.

I suggest looking at this if you want to learn more :

https://starkware.medium.com/builtins-and-dynamic-layouts-e419a73e29e
https://www.youtube.com/watch?v=ee3S83TaKM4

TLDR : continue using poseidon and trust the process.

[milancermak]

Hey, thanks for the write-up here and below 🙏

You write that a range check is worth ~1 step - is that because it uses ~50 cells? This doc however still mentions a range check being 16x more expensive (in gas terms) than a step, so which is it?

Note that the gas usage you see locally (not on testnet or mainnet) with the latest version of cairo reflects this dynamic cost property. So you should compare your two versions locally and not on chain if you want to see the difference.

By latest version you mean 2.5.0-dev.0?

Also, do you know what is the most reliable way to measure gas usage of a function? Is it sth to do with withdraw_gas or just having a test fn and seeing the output of the test runner is enough?

[feltroidprime]

you should assume the gas you have when you run a function locally will eventually be one day the gas you'll have on starknet when the dynamic layouts are here. It's better to optimize this rather than the gas you have on a actual tx today.

within this cost framework a range check is the same as a step and not 16x!

Also within this dynamic layout the 'charged by the limiting factor' will disappear, everything will add up but with their real costs.

And For withdraw gas stuff i have no idea what it is.

[feltroidprime]

Btw I didn't read your code but based on the resources you've posted it seems you have an overhead, you should use the hades permutation directly if you are not already :
https://github.com/starkware-libs/cairo/blob/a666087aca1e614468cfdb8fc681fc0cf588e6b9/corelib/src/poseidon.cairo#L8 as hades_permutation(x,y,2) and get your result as the first output, do not use poseidon_hash_span even if it feels more convenient it should be used only for longer than 2 arrays.