Hashing
Using 1st party implementations of circuit friendly (and unfriendly) hash functions in Circom circuits
Introduction to Circom Hashing
See the Theory > Primitives > Hashing section for more of an explanation on hash functions in general, as well as the specifics of hash functions friendly to the arithmetic circuit.
HashingAs a preface, in general you can assume more inputs to make the computation of your hash more expensive both in Zero Knowledge constraints and in EVM gas. There is also an increased cost to multiple rounds of hash function/ template calls compared to a one-shot hash with multiple inputs.
You most likely have seen the equivalent of Circom's "Hello World" on their official docs:
This circuit may seem absolutely pointless without any experience. However, as a black box hashing is little more than a irreversible function to deterministically obscure data using math.
Put even simpler, pretend that the operation a * b
is our hash function.
c
represents the hash
Functionally, the "Hello World" circuit is meant to quickly convey that with the Circom DSL, individuals can prove knowledge of underlying data and prove that an encrypted value is the hash of that underlying data. From this point on, we can work with the hash in public or further in Zero Knowledge as a verifiable receipt of the underlying data contained within.
Example of Application
For instance, part of the decentralization in BattleZips V1 is derived from the contract storage of a hash proven to be a MiMC sponge hash of a valid board configuration. Consider the flow of (see Examples > BattleZips for all pseudo UML sequence diagrams for BattleZips):
When Alice runs newGame()
or Bob runs joinGame()
, the following code runs, given inputs of a board.circom
proof and the board hash:
Logically, this can be broken down to a sort of informational escrow:
store
_boardHash
for the player for the duration of that game
Once the contract has been convinced of the authenticity of the hash, we can transfer the right to input the hash for shot.circom
from the end user to the smart contract. Notice that in turn()
, the boardHash
value is recalled from EVM storage and directly assigned. The caller has no ability to assign the 0th (first) public proof input parameter, beyond their initial commitment to the board hash when creating or starting the game.
MiMC
Full support from the auxiliary first party libraries is included for both MiMC and MiMC Sponge:
templates: [mimc.circom, mimcsponge.circom]
drivers: [mimc7.js, mimcsponge.js]
EdDSA templates: [eddsamimc.circom, eddsamimcsponge.circom]
contract generators: [mimc7_gencontract.js, mimcsponge_gencontract.js]
@todo: Figure out wtf the difference between MiMC and MiMC Sponge. For this reason, we will explain the rest of the MiMC section using the MiMC Sponge circomlib construct. Know that while the exact API for the MiMC template may differ slightly from the MiMC Sponge, the actual input output functionality is exactly the same and reworking the following code for determined users of mimc.circom
should be quick.
Poseidon
Note: Poseidon is colloquially and theoretically a superior upgrade of MiMC. When dealing with 6 or less inputs to your hash function, you will most likely experience all around superior performance to MiMC. However, in the BattleZips update to RollupNC, we found that the max input size for the circomlibjs auto-generated contract was 6, meaning a transaction leaf with 8 different fields was most efficiently hashes in three rounds - hash each half of the transaction leaf separately with 4 inputs, then hash the two intermediate hashes together for the transaction leaf. This provided inferior performance to the older MiMC version of the RollupNC repository.
SHA-256
BattleZips V1 was forked (almost entirely transformed at that) from zkbattleship-circuit
written by an unaffiliated GitHub user tommymsz006
. In that README.md, they explained:
There have been different discussions on whether/how hashing can be made more efficient in arithmetic circuits for zkSNARKs use; see Zcash forum and ethresear.ch.
For this battleship use case, taking circom's hash as an example,Pedersen Hash is proved to be more efficent in terms of the resulting number of wires (>88% reduction) and constraints (>97% reduction), compared with the SHA-256 counterpart:
There is an immense cost to verifying a SHA-256 hash in Zero Knowledge. Unless your circuit's existence is predicated on the need to verify existing ECDSA signatures or SHA-256 hashes, you should not create new SHA-256 hashes to verify by starting out with SHA-256. As demonstrated above with the BattleZips board placement, if you only need the data authentication provided by SHA-256 and not SHA-256 itself you should implement a different hash function.
Nonetheless, there is first party support for SHA-256 in the form of the template sha256compression.circom
. Being SHA-256, you can use standard solidity and javascript libraries. There are third party circom templates for keccak256 as well. If you really wanted to see ZK Battleship, and can stomach translating you can check out theClever use of GitHub search should yield you additional resources to replicate in your own work.
Last updated