# Hashing

### 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.

{% content-ref url="/pages/t1PPod6BKRUOKfin2NHh" %}
[Hashing](/battlezips/development/circomlib/hashing.md)
{% endcontent-ref %}

As 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](https://docs.circom.io/getting-started/writing-circuits/): 

```
pragma circom 2.0.0;

/*This circuit template checks that c is the multiplication of a and b.*/  

template Multiplier2 () {  

   // Declaration of signals.  
   signal input a;  
   signal input b;  
   signal output c;  

   // Constraints.  
   c <== a * b;  
}
```

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.&#x20;

Put even simpler, pretend that the operation `a * b` is our hash function.&#x20;

* `a` and `b` represent a [preimage](https://river.com/learn/terms/p/preimage/#:~:text=A%20preimage%20is%20the%20data,hash%20of%20a%20public%20key.), the data being hidden or [checksum](https://en.wikipedia.org/wiki/Checksum)'d for integrity
* `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.&#x20;

### 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):

<figure><img src="/files/jTVOFvnonpZmIxUlSkkG" alt=""><figcaption></figcaption></figure>

When Alice runs [`newGame()`](https://github.com/BattleZips/BattleZips/blob/master/contracts/BattleshipGame.sol#L82) or Bob runs [`joinGame()`](https://github.com/BattleZips/BattleZips/blob/master/contracts/BattleshipGame.sol#L100), the following code runs, given inputs of a [`board.circom`](https://github.com/BattleZips/BattleZips/blob/master/zk/circuits/board.circom) proof and the board hash:

```
...
/// PROVE THE HASH IS OF A VALID BOARD CONFIGURATION ///
require(
    bv.verifyProof(a, [b_0, b_1], c, [_boardHash]),
    "Invalid Board Config!"
);
/// STORE THE BOARD HASH IN THE CONTRACT ///
// _game = game lobby
// .participants[1] means bob/ joinGame; [0] would be alice/ newGame
games[_game].participants[1] = _msgSender();
games[_game].boards[1] = _boardHash;
...
```

Logically, this can be broken down to a sort of informational escrow:

1. using the [`bv`](https://github.com/BattleZips/BattleZips/blob/master/contracts/IVerifier.sol#L4-L11) ([deployed](https://github.com/BattleZips/BattleZips/blob/master/contracts/BoardVerifier.sol)) on-chain zkSNARK verifier, use the proof`(a, b_0, b_1, c)`to convince the smart contract that `_boardHash`is the MiMC7 hash of a valid battleship board, as encoded by `board.circom`
2. 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`](https://github.com/BattleZips/BattleZips/blob/master/zk/circuits/shot.circom) from the end user to the smart contract. Notice that in [`turn()`](https://github.com/BattleZips/BattleZips/blob/master/contracts/BattleshipGame.sol#L135-L143), 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](https://github.com/iden3/circomlib/blob/master/circuits/mimc.circom), [mimcsponge.circom](https://github.com/iden3/circomlib/blob/master/circuits/mimcsponge.circom)]
* drivers: \[[mimc7.js](https://github.com/iden3/circomlibjs/blob/main/src/mimc7.js), [mimcsponge.js](https://github.com/iden3/circomlibjs/blob/main/src/mimcsponge.js)]
* EdDSA templates: \[[eddsamimc.circom](https://github.com/iden3/circomlib/blob/master/circuits/eddsamimc.circom), [eddsamimcsponge.circom](https://github.com/iden3/circomlib/blob/master/circuits/eddsamimcsponge.circom)]
* contract generators: \[[mimc7\_gencontract.js](https://github.com/iden3/circomlibjs/blob/main/src/mimc7_gencontract.js), [mimcsponge\_gencontract.js](https://github.com/iden3/circomlibjs/blob/main/src/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.

<details>

<summary>Zero Knowledge</summary>

</details>

<details>

<summary>JavaScript</summary>

</details>

<details>

<summary>Solidity</summary>

</details>

## Poseidon

<details>

<summary><a href="https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom">Zero Knowledge</a></summary>

The use of the Poseidon hash function in Circom is quite simple. The [`Poseidon`](https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom#L198-L208) template is shown below:

```
template Poseidon(nInputs) {
    signal input inputs[nInputs];
    signal output out;

    component pEx = PoseidonEx(nInputs, 1);
    pEx.initialState <== 0;
    for (var i=0; i<nInputs; i++) {
        pEx.inputs[i] <== inputs[i];
    }
    out <== pEx.out[0];
}
```

Let's individually note the properties before demonstrating the component use:

* Supplying the `nInputs` template parameter determines the number of signals that will be hashed together
  * Note that this is not limited to 6 like the Poseidon solidity contract
* The component is used simply by assigning `nInputs` number of signals in the `inputs` signal array
* Once all inputs have been assigned, the Poseidon hash of the values can be accessed with the output signal `out`

In practice, we can look to the BattleZips updated RollupNC repository. Specifically, lets take a look at the process of hashing an account leaf for the state tree in [`balance_leaf.circom`](https://github.com/BattleZips/RollupNC/blob/master/zk/circuits/helpers/balance_leaf.circom) (see *Examples > RollupNC > Account/ State Tree* for context), where each account leaf is the Poseidon hash of 5 values:

```
pragma circom 2.0.3;

include "../../../node_modules/circomlib/circuits/poseidon.circom";

template BalanceLeaf() {

    /// SIGNAL IO ///
    signal input pubkey[2]; // Account EdDSA pubkey [x, y]
    signal input balance; // Account token balance
    signal input nonce; // Number of transactions made by the account
    signal input tokenType; // Token registry index for token type
    signal output out; // Poseidon hash of account (account leaf)
    
    /// HASH ACCOUNT DATA INTO ACCOUNT LEAF ///
    component balanceLeaf = Poseidon(5);
    balanceLeaf.inputs[0] <== pubkey[0];
    balanceLeaf.inputs[1] <== pubkey[1];
    balanceLeaf.inputs[2] <== balance;
    balanceLeaf.inputs[3] <== nonce; 
    balanceLeaf.inputs[4] <== tokenType;

    out <== balanceLeaf.out;
}
```

In this case, we assign the Poseidon component's `nInputs` parameter to `5` to ingest the two `pubkey` points, the `balance`, the `nonce`, and the `tokenType`. These items must be assigned to the array in proper order. Once `nInputs` assignments are made to each index of the  of the `balanceLeaf.inputs[]` array, we can access the Poseidon hash with `balanceLeaf.out`.

Lastly, you can find the [first party unit test for the Poseidon circuit in the circomlib repo](https://github.com/iden3/circomlibjs/blob/main/test/poseidon.js).

</details>

<details>

<summary><a href="https://github.com/iden3/circomlibjs/blob/main/src/poseidon_wasm.js">JavaScript</a></summary>

The circomlibjs library includes a JS component for Poseidon. Your application will very frequently use the JavaScript hasher to work with this data on the client side, including use in both Solidity and the Circom circuits (see more on browser inclusion of circomlibjs assets in *Development > SnarkJS > Browser).*

To employ the hash function, let's use the [BattleZips updated RollupNC unit tests](https://github.com/BattleZips/RollupNC/blob/master/test/0.js#L62-L67) (edited slightly here):

```
const { buildPoseidon } = require('circomlibjs')

...
it('Deposit #1 (COORDINATOR ADDRESS)', async () => {
    // instantiate poseidon hasher from circomlibjs
    const poseidon = await buildPoseidon();
    ...
    // generate account leaf
    // A.K.A. Poseidon hash of the eddsa key, balance, nonce, tokenType
    const data = [...l2Pubkey, 0, 0, 0];
    const leaf = F.toObject(poseidon(data));
    ...
})
...
```

Poseidon is a popular hash function and you should not have trouble finding its use within the open-source code contained in *Ecosystem > Projects.* You can start with the [circomlibjs Poseidon unit tests](https://github.com/iden3/circomlibjs/blob/main/test/poseidon.js) for the first party demonstration of use.

</details>

<details>

<summary><a href="https://github.com/iden3/circomlibjs/blob/main/src/poseidon_gencontract.js">Solidity</a></summary>

</details>

Note: Poseidon is colloquially and [theoretically](https://eprint.iacr.org/2019/458.pdf) 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](https://github.com/BattleZips/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](https://github.com/rollupnc/RollupNC).

## SHA-256

BattleZips V1 was forked (almost entirely transformed at that) from [`zkbattleship-circuit`](https://github.com/tommymsz006/zkbattleship-circuit/blob/master/circom/battleship_sha256.circom) written by an unaffiliated GitHub user [`tommymsz006`](https://github.com/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](https://github.com/zcash/zcash/issues/2234) and [ethresear.ch](https://ethresear.ch/t/cheap-hash-functions-for-zksnark-merkle-tree-proofs-which-can-be-calculated-on-chain/3176).
>
> For this battleship use case, taking [circom's hash](https://iden3-docs.readthedocs.io/en/latest/iden3_repos/research/publications/zkproof-standards-workshop-2/pedersen-hash/pedersen.html) 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:
>
> ```
> > ./zkcompile battleship_pedersen.circom 
> # Wires: 3540
> # Constraints: 708
> # Private Inputs: 15
> # Public Inputs: 4
> # Outputs: 1
> > ./zkcompile battleship_sha256.circom 
> # Wires: 31366
> # Constraints: 29785
> # Private Inputs: 15
> # Public Inputs: 4
> # Outputs: 1
> ```

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`](https://github.com/iden3/circomlib/blob/master/circuits/sha256/sha256compression.circom). Being SHA-256, you can use standard solidity and javascript libraries. [There are third party circom templates for keccak256 as well.](https://github.com/vocdoni/keccak256-circom) 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://battlezips.gitbook.io/battlezips/development/circomlib/hashing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.