7 posts tagged with "ZK"

Not all random numbers in a program need to be highly secure. For instance, when deciding what's for dinner, a basic random module provided by the programming language is usually sufficient. However, in cases generating sensitive data such as nonces and private keys, the randomness should be unpredictable. The occurrence of predictable random data should never happen, but unfortunately, sometimes it does.

In August 2023, a vulnerability related to weak randomness in the Bitcoin development toolkit Libbitcoin Explorer was disclosed by Milk Sad, which resulted in an estimated loss of over $900,000 USD worth of cryptocurrency assets. This leads us to the fundamental question of the article: How do we properly generate random numbers?

Random Number Generators in Software​

To address the fundamental question, we first need to understand the different types of number generators.

Like flipping a coin or rolling a die, a computer can also generate random numbers using various sources, including device drivers and external sources such as network packets and mouse movements. These external sources are diverse enough that predicting the random numbers is considered impossible, and this randomness is referred to as true randomness.

However, computers cannot solely rely on external sources for randomness. When a large amount of randomness is required in a short period, the values from external sources may not change sufficiently to provide adequate entropy. Moreover, reading values from external sources can be slower. Therefore, when a large amount of random numbers is needed, a common method is to obtain a short-length seed from a true randomness source and use this seed as input to generate random numbers. This is called a pseudorandom number generator (PRNG).

The main difference between a PRNG and a true random number generator (TRNG), which generates true random numbers, lies in reproducibility. With a PRNG, the sequence is deterministic, meaning that the same sequence is reproduced if the seed is the same. In contrast, with a TRNG, the sequence is entirely random and cannot be reproduced.

However, not all PRNGs are secure. (Although the meaning of secure can be accepted as meaning "unpredictable", we will discuss what secure formally means in the CSPRNG section.)

Let's first consider a simple 32-bit PRNG, denoted as $\text{PRNG}(s) = {x_0, x_1, \dots}$, where

and where $s$ represents the seed and $a, b$ are fixed constants. This PRNG is known as a linear congruential generator (LCG) and is straightforward for efficiently generating random numbers. However, once $x_i$ is observed, then all other elements in the sequence $x\_{i+1}, x\_{i+2}, \dots$ can be derived. Furthermore, its period is limited to at most $2^{32}$, which is insufficient. One approach to mitigate these issues is to truncate some bits. For example, Java's random employs a 48-bit state, and each generated number is the 32 most significant bits. However, this truncation only marginally improves its statistical characteristics and security. It is still easy to derive the seed given multiple captured elements, and the sequence can be predicted forwards and backwards arbitrarily long. This Github repository is one example to break Java's random.

Another PRNG known as the Mersenne Twister is utilized in languages such as Python and C++. The Mersenne Twister still relies on relatively simple operations but has a long period of $2^{19937} - 1$. Despite Mersenne Twister offering better security compared to LCGs, it is still predictable. Once the 624 consecutive 32-bit random numbers are given, then the inner state can be reconstructed, rendering the sequence predictable. You may refer to this Github repository.

The default random-number--generation functions provided by most programming languages prioritize performance over security. If robust security is a priority, then a cryptographic secure pseudorandom number generator (CSPRNG) must be employed.

CSPRNG​

A CSPRNG is a PRNG that is cryptographically secure because its output is as unpredictable and unbiased as a TRNG. It is therefore defined in terms of indistinguishability: if a PRNG $G$ is indistinguishable from a TRNG, then $G$ is called a CSPRNG.

To understand its mathematical properties, let’s take a look at an example game played between Alice and Bob.

1. Alice generates a sequence, either one generated from the TRNG or one from the PRNG $G$, each with probability $1/2$.
2. Alice provides the generated sequence to Bob.
3. Bob's objective is to guess whether the sequence originated from a TRNG or the PRNG. If Bob's guess is correct, he wins; conversely, if Bob's guess is incorrect, Alice wins.

If Bob takes a random guess, then the rate he wins at is exactly $1/2$. This value of $1/2$ can be considered as a baseline. However, if the PRNG $G$ exhibits unusual characteristics, then Bob's advantage can be higher than $1/2$. For example, if the first element always being fixed to an odd number, then Bob's strategy is to answer PRNG if the sequence starts with an odd number and answer TRNG otherwise. When the sequence is generated by the PRNG, Bob's guess is always correct. However, if the sequence is generated by the TRNG, Bob's guess is right with $1/2$ probability. In this scenario, Bob's winning rate is $(1/2) \times 1 + (1/2) \times (1/2) = 3/4$, which is $1/4$ higher than the baseline. In other words, Bob has a $1/4$ advantage. If $G$ is CSPRNG, then this advantage should be negligible. When this advantage is smaller than $2^{-128}$, we say the CSPRNG achieves 128-bits security.

When a PRNG’s inner state can be reconstructed or its next number can be predicted, it is possible to distinguish the output of a PRNG from a TRNG. This does not happen with CSPRNGs because their output is indistinguishable from a TRNG (unless its seed is somehow revealed or compromised). In other words, CSPRNGs must be resilient to any kind of "seed recovery" attacks.

For further details, we recommend referring to these lecture notes from Princeton University.

Vulnerabilities From a Weak Random​

But is a CSPRNG truly important in properly generating random numbers? Yes. When sensitive data is generated using a weak PRNG, it can lead to significant security problems. The Common Weakness Enumeration (CWE) also includes entries related to randomness vulnerabilities, such as "CWE-334: Small Space of Random Values", "CWE-335: Incorrect Usage of Seeds in PRNG", and "CWE-338: Use of Cryptographically Weak PRNG". These types of vulnerabilities have been known for a long time but still continue to appear. Here are several real-world examples resulting from a weak random.

Milk Sad (CVE-2023-39910)​

Milk Sad refers to a vulnerability in the Libbitcoin Explorer cryptocurrency wallet tool. This vulnerability was discovered during an investigation into lost funds.

The primary issue revolves around a PRNG used in the bx seed command. This command generates a pseudorandom seed, as shown in the following example:

bx seed -b 192
d915107990a42dfb2ea5762729002d47a4748e0f24aceb61

At first glance, it appears to be random. However, this PRNG used in the command has two critical flaws:

1. The PRNG is based on the Mersenne Twister, which is not a CSPRNG.
2. The seed for the PRNG is chosen based on the current time, providing only 32 bits of entropy.

While the Mersenne Twister can be hard to predict if the output is short and the seed has sufficient entropy, in this case, the seed is improperly chosen, allowing attackers to brute-force the private key generated by the bx seed command. Although there were warning statements on the bx seed wiki page, they may not have been sufficiently emphasized to users. It is suspected that even developers might have overlooked this issue, as the wiki landing page included an example of creating a new wallet address with the bx seed command without any warnings.

Initially, the Libbitcoin team responded by stating that the bx seed command was never intended to be cryptographically secure, and they had no plans to address it. However, they later released a patch that removed the command.

In addition to Milk Sad, Cake Wallet, Profanity Ethereum address tool (CVE-2022-40769), and Trust Wallet (CVE-2023-31290) are other examples of vulnerabilities where seeds are generated with incorrect way.

ECDSA Nonce Misuse​

The digital signature scheme is a cryptographic scheme that a signer who has the private key can generate a signature $\sigma$ for a message $m$ and a verifier who knows the corresponding public key can verify the validity of the signature $\sigma$.

An Elliptic Curve Digital Signature Algorithm (ECDSA) is a digital signature scheme over elliptic curves. In cryptocurrencies, ECDSA allows to ensure that transactions are made by the legitimate wallet owner. However, ECDSA, when misused, has a significant security vulnerability related to a nonce denoted as $k$. The nonce is a randomly generated value used during signature generation.

While ECDSA is secure when used correctly, the nonce $k$ introduces a potential security weakness, most notably in cases of nonce reuse. This vulnerability allows an attacker to recover a secret key from a signature if the same nonce is reused for the same secret key. If the nonce is chosen with high entropy, the nonce will not collide. However, if the nonce is generated with low entropy, the nonce can collide. In 2013, weaknesses in the PRNG used in Android led to nonce reuse, resulting in the theft of a substantial amount of Bitcoin (see here).

Furthermore, choosing a nonce in an insecure way, such as concatenating half of the transaction hash and half of the private key, can also lead to a leakage of the private key (as seen here). Given sufficient messages, even a small leakage of less than one bit per nonce can be exploited, too. As biased nonce generation can lead to a complete compromise, this makes secure nonce generation extremely important.

In summary, generating the nonce $k$ securely and randomly, without bias, is crucial in an ECDSA. To address this issue, RFC 6979 recommends using the result of running an HMAC-DRBG with the private key and the hash value of the message as seeds to generate the nonce $k$. This approach helps mitigate the risks associated with nonce misuse in ECDSA.

For further details, we recommend referring to this blog post from Trail of Bits.

CSPRNG Constructions​

Then how can we construct a CSPRNG?

In 2006, the National Institute of Standards and Technology (NIST) published a technical publication titled Recommendation for Random Number Generation Using Deterministic Random Bit Generators. In this document, four CSPRNGs are suggested:

1. Hash-DRBG
2. HMAC-DRBG
3. CTR-DRBG
4. Dual_EC_DRBG

(Note: DRBG stands for deterministic random bit generators, which means the same as a CSPRNG.)

Among these, Dual_EC_DRBG was withdrawn in 2014 due to the discovery of a backdoor. The backstory is interesting but off-subject. You can find more information here if you are curious.

In our discussion of PRNGs, we focused on the basic form where the PRNG is initialized with a seed, and then it generates pseudorandom numbers. In this basic form, it is impossible to provide additional entropy to the PRNG. However, allowing the infusion of additional entropy during operation can enhance security. Without this capability, a PRNG could be entirely compromised if its state or entropy source is compromised for a period. On the other hand, if it is possible to provide additional entropy, the PRNG can recover to a secure state after sufficient entropy is supplied. Importantly, its internal state must change each time new entropy is provided.

These are three key components of a PRNG:

1. $\textsf{Setup}(s)$: PRNG is initialized with a seed $s$.
2. $\textsf{Refresh}(I)$: PRNG accepts a new entropy $I$.
3. $\textsf{Next}(n)$: PRNG generates the $n$ bits output based on the current state.

Now let's take a look into how to generate a cryptographic secure PRNG. Excluding Dual_EC_DRBG, the other three CSPRNGs are based on the symmetric primitive, such as hash functions and block ciphers. This choice is reasonable because standardized algorithms for hash functions and block ciphers exist, and their security properties are widely accepted. Even if a vulnerability is found for a specific symmetric primitive, it's not a catastrophic scenario because transitioning to more secure algorithms is relatively easier than constructing new DRBGs.

As it is the most straightforward, Hash-DRBG is the best example to demonstrate how a CSPRNG works.

Hash-DRBG​

Hash-DRBG is a DRBG built from the cryptographic hash function denoted as $H$. To aid in understanding, we will introduce a simplified version. In this version, we denote the state as $S$.

1. $\textsf{Setup}(s)$: Initialize the state as $S = H(s)$.
2. $\textsf{Refresh}(I)$: Update the state as $S = H(S \|\| I)$.
3. $\textsf{Next}(n)$:
   • Generate a sequence $R = H(S) \|\| H(S+1) \|\| ... \|\| H(S+k)$ where $k$ is the smallest number that $\|R\| \geq n$.
   • Update the state as $S = H(S \|\| H(S))$.
   • Return the leftmost $n$ bits of $R$.

These three DRBGs (Hash-DRBG, HMAC-DRBG, and CTR-DRBG) are constructed using symmetric primitives, and their security can be proven based on the security properties of these symmetric primitives, utilizing the concept of indistinguishability.

Note that there may be a slight gap between the claimed security of these DRBGs and their theoretical analysis, as strong assumptions are made in the proofs. However, these DRBGs are generally considered secure enough for real-world use, and their security has been the subject of ongoing research until relatively recently, as evidenced by papers presented in EUROCRYPT 2019 (such as An Analysis of the NIST SP 800-90A Standard).

How to Properly Generate Random Numbers​

To properly generate random numbers, there are only two things we need to keep in mind. First, the seed should be generated from enough entropy, and second, a CSPRNG should be used instead of a weak PRNG, such as default random modules in each language. (For more, see this post, which enumerates the methods to generate secure random numbers in various programming languages.)

Conclusion​

In this article, we've discussed the mathematical definitions of CSPRNGs and studied vulnerabilities in the wild. While these vulnerabilities are relatively easy to detect and defend against, their occurrence can lead to the exposure of sensitive information and significant damage.

As PRNGs are a fundamental component in almost every software program, there is always a risk that a developer might improperly generate random numbers for sensitive data. Therefore, it is essential for developers to ensure that random numbers are generated in a secure way and that auditors track the logic for the PRNG in code.

About Us​

Zellic is a smart contract auditing firm founded by hackers, for hackers. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants. Whether you’re developing or deploying smart contracts, Zellic’s experienced team can prevent you from being hacked.

Contact us for an audit that’s better than the rest. Real audits, not rubber stamps.

If you think you’d be a good fit to work at Zellic, we’re hiring!

Introduction​

Last time, we explored the fundamentals of zkSNARKS and their applications in blockchains. We introduced the following:

• zkEVMs and how they increase transaction speed and scalability on the Ethereum network
• zkBridges and how they enable secure exchanges between different cryptocurrencies
• ZK programming languages and how they simplify the development of ZK circuits for software engineers

For a refresher on these aspects of the ZK landscape, see Part 1 here.

Having laid the foundation of the ZK landscape, let’s take a look at a few more applications of zero-knowledge: ZK payments, ZK hardware acceleration, and zkVMs. With these applications in mind, we’ll have taken a brief look at some of the most notable areas of the landscape and arrived at the end of our tour.

As a brief overview of ZK payments, we'll cover an introduction to fully private and secure transactions. For ZK hardware acceleration, we'll cover how zkSNARKs are used to speed up cryptographic operations. Lastly, for zkVMs, we'll cover how zkSNARKs are used to increase the speed of any blockchain network, not just Ethereum.

ZK Payments​

Bitcoin, Ethereum, and Solana are all public cryptocurrencies, which means that all transactions, accounts, and data are public. However, in some cases, private transactions are necessary. ZK payments aim to use ZK proofs to ensure three criteria:

1. Private transaction amounts. The amount of money transferred between accounts must be hidden to other users. Only the sender and the receiver know how many coins were transferred.
2. Private user identities. Traditional public blockchains often expose the addresses of the sender and receiver. On the other hand, ZK payments ensure the privacy of the addresses in public.
3. Private transaction history. Information such as transaction history and account balance is kept hidden from the public blockchain. While data is still being uploaded to the main chain, sensitive information is kept secret.

On the surface level, public blockchains seem to be private. Take for example this Ethereum address. Does this look like a person's identity?

0xB256227cfc6209fCC7bA1c4acb9329721Acb89d4

Although it might not look like it, the person's transactions and activities are public. These bits of information allow for others to trace a person's identity and be able to fairly quickly monitor their blockchain usage at all times.

The bulk of ZK payments is made through designs based on Zcash. In a nutshell, Zcash allows users to transfer coins on the Zcash blockchain, giving users the choice of keeping their transactions public or private.

Transactions on Zcash use a UTXO structure similar to Bitcoin's. When a sender processes a transaction, the sender posts two notes. One note contains the sender's new balance, while the other contains the amount of money being sent. To stay private, these notes are encrypted with ChaCha20-Poly1305. ChaCha20 is a symmetric encryption algorithm similar to AES and was chosen in this instance for its fast encryption speed. Only the sender and receiver can decrypt the notes with their own set of keys. The two new encrypted notes are then hashed and committed into a central Merkle tree.

Up to this point, the public is unable to verify the transaction since the notes are encrypted. This is where ZKPs come in. Older versions of Zcash, before the release of Sapling activation in 2018, used BCTV14, a slower, older, more energy-intensive proving system than Groth16. Given that Groth16 was created in 2016, Zcash stuck with BCTV14 to ensure the safety of Groth16 before implementing Sapling activation two years later. With Sapling activation, Groth16 is chosen for its fast proving/generating speeds. This allows others to verify the validity of the private transaction without revealing any data on the users themselves.

(As a fun fact, these proving systems are both named after the research papers that originally proposed them. BCTV14 was published in 2014 by authors whose names start with B, C, T, and V. The Groth16 paper was published in 2016 by Jens Groth.)

Zcash specifically uses two ZK circuits and a value-commitment check:

1. Spend circuit. The spend statement is a ZK proof that is in charge of making sure a transaction is able to go through correctly. This circuit creates a proof that confirms to a verifier that the note and Merkle path is valid, the original spender is authorized to perform this transaction, the previous note is nullified, and the balances on the two new notes add up to the original note.

2. Output circuit. The output statement is a ZK proof in the creation of new coins. It allows verifiers to confirm that the note created for the coin is valid along with the value commitment.

3. (Homomorphic) Pedersen commitment. The Pedersen commitment, used by Zcash (Zcash Protocol Specification, p. 18), is used whenever a value is committed. The homomorphic property allows Pedersen commits to be added and subtracted. For example, to ensure coins aren't created/destroyed during a transaction, the value commit to the sender's new balance can be added to the value commit to the sent coins and checked to ensure the total amount of coins stays the same.

ZK Hardware Acceleration​

Our next stop is on accelerating ZKP generation. Currently, generating ZKPs for transactions is a time- and resource-consuming process. However, work is in progress to speed this up using specialized hardware. Proof generation has gone from the usage of CPUs to now GPUs and even specially designed circuits on FPGAs.

CPUs are slow. They are used for everyday computation that isn't fit for math-intensive ZK proof generation. People gradually moved to use GPUs since graphic cards were designed to perform special-purpose, vectorized calculations at much faster speeds (e.g., gaming and high--frame rate video streaming). However, GPUs were still designed for a wide variety of uses. The community began to explore solutions leveraging FPGAs, which are even more specialized.

FPGAs are pieces of hardware that can be bought off the shelf. Users can reconfigure the circuits inside to fit specific circuit requirements. Rather than having dedicated sections of GPUs/CPUs for everyday computer calculations, the entire FPGA circuitry can be changed and dedicated to ZK. The most time-consuming parts of proof generation come from two categories.

1. (Fast) Fourier transforms (FFTs). A ZKP typically uses Fourier transforms to perform division over an elliptic pairing. Although FFTs run in subexponential time, they are still the bulk of a ZKP generation.

2. Multiplications. Most ZKPs consist of elliptic curve multiplications, which are computationally expensive. Since a single gate cannot express an elliptic operation, multiple binary gates must be stringed together in order to perform elliptic operations.

To address these challenges and speed up the proof-generation process, a solution can be found through the development of application-specific integrated circuits (ASICs), specialized pieces of hardware specifically built for the purpose of ZKP generation. By hardwiring the required mathematical operations into hardware, ASICs can perform these computations much more efficiently and in parallel, dramatically reducing the time taken to generate ZKPs.

The use of ASICs for ZKP generation offers several advantages, including increased speed, reduced power consumption, and improved scalability. These specialized hardware solutions can optimize the most time-consuming operations, allowing zkSNARKs to be more practical for high-performance applications, such as privacy-preserving transactions, secure communications, and verifiable computations.

However, using ASICs comes with drawbacks as well. ASICs are best suited for mature applications that rarely change, like SHA-256 POW mining. On the other hand, ZKP generation continues to evolve rapidly. Designing custom ASICs for ZKPs requires significant resources, and it's essential to ensure the security of the hardware to prevent potential attacks. Additionally, unlike FPGAs, once an ASIC is hardwired, it is permanently ingrained in the chip. If the ZKP algorithm is changed or an update is needed, a whole new ASIC must be used and the original would be useless. Not to mention the tape-out costs of creating ASICs, typically ranging from $2 to $3 million. Thus, the development costs of ASICs have made them prohibitive for ZKPs so far.

One example is Cysic, whose approach is based on FPGAs and ASICs. Customers submit the ZK circuit they seek to accelerate, and Cysic builds it for them. Without relying on GPUs, FPGAs and ASICs are much faster, resulting in less time and resources during proof generation.

zkVMs​

Now let's travel to our last stop on ZK virtual machines (zkVMs), also known as zkCPUs. Contrary to zkEVMs from the last blog, zkVMs is a broader concept applicable to any binary program, making it more versatile in its use cases. zkVMs run precompiled binaries and generate a verifiable proof that the binary ran correctly. This proof can be independently verified by anyone without needing to see the actual inputs, outputs, or intermediate values of the computation.

Unlike zkEVMs, zkVMs are also not tied down to a blockchain. zkVMs can be used for general purposes that are not run on Ethereum. Since zkVMs take precompiled binaries as an input, programs can be written in a variety of programming languages such as Rust, C, and C++, all compiled languages. Considering that Solidity development is often a bottleneck, access to the broader ecosystem of general software is a major benefit.

Inside the zkVM, each assembly instruction in the binary is associated with an R1CS gate to check for verification. For example, in pseudocode, it might look something like this:

if instruction is "add a, b":
    add constraint for c = add a,b
else if instruction is "mul a, b":
    add constraint for c = mul a,b

However, zkVMs have certain limitations. Due to the large amount of assembly instructions and R1CS gates for each instruction, it is typically more suitable for smaller binaries with a manageable complexity. Running larger and more complex programs might be impractical or less efficient using a zkVM. For larger binaries, circuits need to be optimized in order to allow for fast ZKP generation. Specific computations need a more optimized method to prevent slowdowns in the zkVM.

RISC Zero is a zkVM developed for general-purpose use. On a simple level, a binary is used as the input and the VM extracts each assembly instruction. For example, here is how memory loads are handled in RISC Zero:

pub fn ram_load(&mut self, triple: &TripleWord) -> Result<bool> {
    trace!("RAM_LOAD[{}]: {triple:?}", self.cycle);
    self.start();
    self.code[ControlIndex::RamLoad] = BabyBearElem::ONE;
    self.code[ControlIndex::Info] = BabyBearElem::new(triple.addr);
    (
        self.code[ControlIndex::Data1Lo],
        self.code[ControlIndex::Data1Hi],
    ) = split_word16(triple.data[0]);
    (
        self.code[ControlIndex::Data2Lo],
        self.code[ControlIndex::Data2Hi],
    ) = split_word16(triple.data[1]);
    (
        self.code[ControlIndex::Data3Lo],
        self.code[ControlIndex::Data3Hi],
    ) = split_word16(triple.data[2]);
    self.next()
}

After extracting all assembly instructions, they are run one by one as listed below. Along the way, constraints are added to the main circuit, which proves the validity of the program.

pub fn body(&mut self) -> Result<()> {
    debug!("BODY");
    loop {
        self.start();
        self.code[ControlIndex::Body] = BabyBearElem::ONE;
        if !self.next_fini(FINI_TAILROOM)? {
            break;
        }
    }
    Ok(())
}

Rather than using a zkSNARK, RISC Zero uses a zkSTARK that includes four processing phases. Phase 1 is essentially the commitment phase. The prover creates trace polynomials after each step and commits them to a Merkle tree. Phase 2 allows the validator to validate the polynomials and send PLONK-mixing parameters, which the prover uses to generate Merkle roots. Phase 3 and Phase 4 use the DEEP-FRI technique, which asks the prover for values of a polynomial outside of the original Merkle tree commitments. Of course, this is a vast oversimplification of the entire process.

Conclusion​

This two-part article toured the fundamentals of ZKPs — from zkSNARKs and their implications in zkEVMs, ZK programming languages, and zkBridges all the way to ZK payments, ZK hardware acceleration, and zkVMs. The world of zero-knowledge is a vast and fascinating one, and we’ve just touched the surface.

This guide can be used to kickstart further exploration of ZKPs. ZKPs have become increasingly important to ensure the security and validity of transactions on the blockchain as well as prove knowledge in other aspects. As the ZK landscape continues to evolve and expand, the potential for real-world applications will grow exponentially.

Special thanks to fellow Zellic engineer Mohit Sharma for his help and input in this article.

About Us​

Zellic is a smart contract auditing firm founded by hackers, for hackers. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants. Whether you’re developing or deploying smart contracts, Zellic’s experienced team can prevent you from being hacked.

Contact us for an audit that’s better than the rest. Real audits, not rubber stamps.

Introduction​

In this article, we will be looking at the recently released Cairo 1.0, Starknet's native language. We will give a brief introduction to Cairo and Starknet, explore some security features of Cairo, and look at some potential pitfalls when writing contracts in Cairo. For anyone considering writing contracts in Cairo, this article will give you a starting point and some things to consider when writing secure code.

Meet Cairo 1.0​

Cairo 1.0 is a Rust-inspired language designed to allow anyone to create STARK-provable smart contracts. It is the native language of Starknet, which is a zkRollup designed for high throughput and low gas costs. For the purposes of this article, we will be focusing on the security features of Cairo when used to write smart contracts on Starknet.

First, let's begin by walking through a simple contract written in Cairo 1.0:

#[contract]
mod hello {
    use starknet::get_caller_address;
    use starknet::ContractAddress;

    struct Storage {
        last_caller: ContractAddress,
    }

    #[event]
    fn Hello(from: ContractAddress, value: felt252) {}


    #[external]
    fn say_hello(message: felt252) {
        let caller = get_caller_address();
        last_caller::write(caller);
        Hello(caller, message);
    }

    #[view]
    fn get_last_caller() -> ContractAddress {
        last_caller::read()
    }
}

If you have used Rust before, then the above code might look familiar, as Cairo 1.0 is heavily inspired by it. If you are unfamiliar with it, then starklings-cairo1 is a great place to start. Starklings is to Cairo what Rustlings is to Rust, a set of small, interactive exercises to help you learn the language.

The default type of variable in Cairo 1.0 is a field element called felt252, which is an integer in the range $0 \leq x < P$, where $P$ is a very large prime $P = 2^{251} + 17 * 2^{192}+1$. (For a more detailed explanation, see the felt-type section in The Cairo Programming Language book.) All other types in Cairo are built on top of felt252 such as the integer types of u8 to u256. It is recommended to use these higher-level types when possible as they provide additional safety features such as overflow protection.

When writing Starknet contracts, there are a few special attributes that are used to allow the compiler to generate the correct code. The #[contract] attribute is used to define a Starknet contract, similar to the contract keyword in Solidity.

A contract may be required to interact with another contract or to have some knowledge about the current execution state (for example, the caller address). This is where system calls come in, which allow the contract to interact with and use services from the Starknet OS. Most of the time the system calls are abstracted away or hidden behind helper methods, but you can see a list of the available system calls here.

The #[event] attribute is used to define an event that can be emitted by the contract. Similar to Solidity, events are used to notify the outside world of state changes in the contract and are emitted using the emit_event_syscall system call or by calling the helper function generated by the compiler, which is annotated with the #[event] attribute.

The #[external] attribute is used to define a function that can be called by the outside world, similar to the external keyword in Solidity. The #[view] attribute is designed to indicate that a function does not modify the contract state, although this is not enforced by the compiler, so state changes are possible if the function is called on chain.

The struct Storage is a special struct that the compiler uses to generate helper methods for interacting with the contract's storage using the low-level system calls storage_read_syscall and storage_write_syscall. In a Starknet contract, the storage is a map of $2^{251}$ slots that can each be read or modified. Each slot is a felt that is initially set to 0. The fields in the Storage struct are turned into modules with read and write methods that automatically calculate the correct location in the storage map (see here for how the address is calculated) and can be used to read and write to the storage.

Before you can deploy a contract on Starknet, the contract class must first be declared on the network. Each declared class on the network is represented by a clash hash (see here for how the hash is calculated), which uniquely identifies it and can be used to deploy new contract instances.

Beyond Ethereum: Starknet Accounts​

Unlike Ethereum, Starknet does not have externally owned accounts (EOAs). Instead, accounts are special contracts that can define their own logic and rules. Here is the interface for a generic account contract:

#[account_contract]
mod Account {
    use starknet::ContractAddress;

    #[constructor]
    fn constructor(public_key_: felt252);

    fn isValidSignature() -> felt252;

    #[external]
    fn __validate_deploy__(
        class_hash: felt252, contract_address_salt: felt252, public_key_: felt252
    ) -> felt252;

    #[external]
    fn __validate_declare__(class_hash: felt252) -> felt252;

    #[external]
    fn __validate__(
        contract_address: ContractAddress, entry_point_selector: felt252, calldata: Array<felt252>
    ) -> felt252;

    #[external]
    #[raw_output]
    fn __execute__(mut calls: Array<Call>) -> Span<felt252>;
}

For a contract to be a valid account, it must at least implement the __validate__ and __execute__ functions and optionally implement the others. The __validate__ function should ensure that the transaction was initiated by the account owner, and the __execute__ function will perform the remaining actions. (See the "Validate and execute" section of the Starknet documentation for more details.)

The implementation could be as simple as checking an ECDSA signature, or it could be anything from a multi-sig to allowing multicalls. For a more in-depth look at accounts, see the Starknet documentation, the chapter "Account Abstraction" in The Starknet Book, and OpenZepplin's account implementation.

Potential Pitfalls in Cairo​

One of the main benefits of Starknet being a zkRollup is that contracts written in Cairo allow for execution traces to be proved and verified on Ethereum L1. It has been designed to provide flexibility, but this also could lead to insecure code. In this section, we will look at some potential pitfalls.

Overflows​

When using integer types such as u128 and u256, there is now some nice built-in overflow protection that will cause a panic --- for example,

    let a: u128 = 0xffffffffffffffffffffffffffffffff;
    let b: u128 = 1;
    let c: u128 = a + b;

    // Run panicked with [39878429859757942499084499860145094553463 ('u128_add Overflow'), ].

This is not the case when using felts directly as overflows are still possible:

    let a: felt252 = 0x800000000000011000000000000000000000000000000000000000000000000;
    let b: felt252 = 1;
    let c: felt252 = a + b;
    c.print();

    // [DEBUG] (raw: 0)

Reentrancy​

If you mark a trait with the #[abi] attribute, then the compiler will automatically generate two dispatchers based on the trait name; for example, for the trait ICallback, the generated names will be ICallbackDispatcher and ICallbackLibraryDispatcher. A dispatcher is a simple struct that wraps the call_contract syscall, allowing you to call other contracts. The library dispatcher is different in that the current contract's context and storage will be used when executing the external code, similar to delegatecall in Solidity. (See The Cairo Programming Language's section on dispatchers for more details.)

Since the contract dispatcher passes control to the external contract, it is possible for the external contract to call back into the current contract, which could lead to reentrancy bugs. For example, consider the following contract:

#[abi]
trait ICallback {
    #[external]
    fn callback();
}

#[contract]
mod reentrancy {
    use option::OptionTrait;

    use starknet::get_caller_address;
    use starknet::ContractAddress;
    use super::ICallbackDispatcher;
    use super::ICallbackDispatcherTrait;


    struct Storage {
        balances: LegacyMap::<ContractAddress, u256>,
        claimed: LegacyMap::<ContractAddress, bool>,
    }

    #[external]
    fn claim(callback: ContractAddress) {
        let caller = get_caller_address();
        if !claimed::read(caller) {
            ICallbackDispatcher { contract_address: callback }.callback();
            balances::write(caller, balances::read(caller) + 100);
            claimed::write(caller, true);
        }
    }

    #[external]
    fn transfer(to: ContractAddress, amount: u256) {
        let caller = get_caller_address();
        balances::write(caller, balances::read(caller) - amount);
        balances::write(to, balances::read(to) + amount);
    }

    #[view]
    fn get_balance(addr: ContractAddress) -> u256 {
        balances::read(addr)
    }
}

The claim function allows a user to claim 100 tokens from the contract if they have not already claimed them, but since the callback happens before the state is updated, it's possible for a contract to call the claim function repeatedly and claim as many tokens as they want:

use starknet::ContractAddress;

#[abi]
trait IClaim {
    #[external]
    fn claim(callback: ContractAddress);
}

#[contract]
mod hello {
    use starknet::get_caller_address;
    use starknet::get_contract_address;

    use super::IClaimDispatcher;
    use super::IClaimDispatcherTrait;

    struct Storage {
        count: u256,
    }

    #[external]
    fn callback() {
        if (count::read() < 10) {
            count::write(count::read() + 1);
            IClaimDispatcher { contract_address: get_caller_address() }.claim(get_contract_address());
        } else {
            count::write(0);
        }
    }
}

When using the library dispatcher, you must provide a class hash instead of a contract address, so you cannot accidentally use the wrong dispatcher. The executed code will use the same context and storage as the current contract, so the class hash must be trusted.

Storage Clashes​

When using the storage struct, the underlying address of the storage slot is calculated using sn_keccak(variable_name) (sn_keccak is the first 250 bits of the Keccak256 hash). If you are using other modules or external libraries that have a similar storage struct, then it's possible for the storage slots to be identical and overwrite each other. For example, consider the following contract:

// foo.cairo
#[contract]
mod foo {
    struct Storage {
        num: u256,
    }

    fn get_num() -> u256 {
        num::read()
    }

    fn set_num(n: u256) {
        num::write(n);
    }

}


// bar.cairo
use super::foo::foo;

#[contract]
mod bar {
    struct Storage {
        num: u128,
    }

    #[external]
    fn set_num(n: u128) {
        num::write(n)
    }

    #[view]
    fn get_num() -> u128 {
        num::read()
    }

    #[view]
    fn foo_get_num() -> u256 {
        super::foo::get_num()
    }

    #[external]
    fn foo_set_num(n: u256) {
        super::foo::set_num(n);
    }
}

Both of the setters are writing to the same storage slot, except one is expecting a u256 and the other a u128, so when calling set_num, the bottom 128 bits of num will be set and the top 128 bits will not be changed. For example, if we call foo_set_num with 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff, then set_num with 0x1234 then foo_get_num, we get the following output:

starknet call --address 0x005e942196b3e1adfac0e1d2664d69671188237db343067ab61048e63957487c --function foo_get_num
4660 0xffffffffffffffffffffffffffffffff

The Next Chapter: Cairo 2.0​

Even though 1.0 has only just been released, the language keeps evolving, and 2.0 will be released soon. The majority of code will be compatible, and there will be a six-month period where both syntaxes will be valid. The main incoming changes are designed to allow the compiler to enforce that view functions do not modify the state of the contract, making it much more explicit and easier to know if a function will modify the state. The new interface syntax will be something similar to the following:

#[starknet::interface]
trait ICounterContract<TContractState> {
   fn increase_counter(ref self: TContractState, amount: u128);
   fn decrease_counter(ref self: TContractState, amount: u128);
   fn get_counter(self: @TContractState) -> u128;
}

The trait for a Starknet interface is now required to explicitly state whether it requires a ref to the contract state, which allows it to be modified and implicitly returned at the end of a function, whereas the "@" symbol indicates that the contract state is an immutable snapshot and cannot be modified. For more information, see the full details of the upcoming changes at the official community post.

Cairo: The Verdict​

The changes from Cairo 0 to 1.0 are a great step towards making the language easy to use and adding some nice security features. The upcoming changes in Cairo 2.0 will make it easier to reason about where the state is modified and help catch mistakes earlier. However, it is still possible to write insecure code, and so it is important to understand the underlying system, the potential pitfalls, and how to avoid them.

Digging Deeper: Cairo Resources​

• The Cairo Programming Language
• starklings-cairo1
• starknet-cairo-101

About Us​

Zellic is a smart contract auditing firm founded by hackers, for hackers. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants. Whether you’re developing or deploying smart contracts, Zellic’s experienced team can prevent you from being hacked.

Contact us for an audit that’s better than the rest. Real audits, not rubber stamps.

Introduction​

In our last post, we discussed the design rationale and performance of various ZK-friendly hash functions. These include MiMC, Poseidon, Vision, and Rescue. Although the structures may differ slightly, the underlying concept remains the same: representing the circuit as simple expressions in a large field, it allows efficient proof in terms of both prover execution time and proof size. However, the question remains: Are they truly secure enough to be entrusted with billions of dollars? Let's dive into the attacks that are particularly effective against ZK-friendly hash functions.

ZK-Friendly Hash Functions​

From a high-level perspective, ZK-friendly hash functions are constructed using algebraically simple keyed permutations, called arithmetization-oriented ciphers (AOCs). AOCs are based on either SPN or Feistel networks. Then the permutations are transformed into hash functions using the sponge framework.

(In addition, new permutations have been proposed recently, such as this and this. Both were accepted to CRYPTO 2023. We recommend checking out these papers because they offer significant performance benefits.)

As keyed permutations are structured as multiple rounds of linear and nonlinear operations, the higher the round count, the more secure the hash function but the worse the performance. The designers must consider every possible attack and determine the lower bounds of the round count required to mitigate them.

Maturation Takes Time, Including AOCs​

Unfortunately, although the designers carefully consider every possible attack and even add security margins, this is not strong evidence that the structure is safe. As we will see in the examples presented in this post, even if the designer has done their best, there may be new attacks that the designer has not considered. Even peer-reviewed papers published in top conferences can be vulnerable to attacks. For instance, a cipher targeting homomorphic encryption named Chaghri was published in ACM CCS 2022, but an attack was discovered only three months after its publication.

New primitives often become adopted by industry after enough time has passed since their publication. This is independent of the claims made in the original paper and is instead based on the fact that enough people have analyzed them to determine that they are mature enough for practical use.

And from a designer's perspective, it is important to consider a variety of attacks, including those we will discuss as well as those evolving, to create a robust security design.

In this post, we will discuss algebraic attacks that are particularly efficient against ZK-friendly hash functions and should be taken into consideration, including attacks on the actual proposed primitive. Although you do not extensive ZK knowledge to understand this article, you may check out our latest ZK related blog post if you are a beginner to ZK.

Algebraic Attacks​

Before starting to introduce algebraic attacks, we should clarify targets of attacks. The basic secure properties of hash functions are preimage resistance, second-preimage resistance, and collision resistance. Therefore, the attacker's primary goal is to recover preimages or find collision pairs. However, from the point of view of designers, it is hard to convince someone that a their hash function satisfies security properties.

Meanwhile, ZK hash functions are usually based on the block ciphers. Once the key is fixed, the block cipher becomes a permutation, and these permutations are transformed into hash functions using the sponge framework. It is mathmetically proven that the hash function derived from sponge construction is secure if the permutation is secure. Therefore, instead of demonstrating security for the hash function directly, designers show that a block cipher used inside the sponge construction is secure. Conversely, an attacker would like to show that the block cipher is insecure. For example, if attacker is given plaintext-ciphertext pairs $(P_i, C_i)$ and enable to recover key $K$ faster than testing all the possible key candidates, it is called key-recovery attack. If the block cipher is insecure, it weakens the designer's claim that the hash function created from the block cipher is secure.

ZK-friendly hash functions are represented by simple expressions in a large field. In traditional cipher design, the strongest attacks are considered to be statistical attacks called differential and linear cryptanalysis. However, when the field is large, these attacks are not suitable even for a small number of rounds. On the other hand, targeting low arithmetic complexity in attacks is effective.

Interpolation Attack​

An interpolation attack is an attack that constructs a polynomial corresponding to the encryption function without knowing the key. Let $E_k : \mathbb F_q \rightarrow \mathbb F_q$ be an encryption function. For a fixed key $k$, the polynomial $E_k(x)$ can be constructed using Lagrange interpolation --- for example, when we consider two rounds of MiMC, $E_k(x) = ((x+k)^3 + k + c_1)^3 + k$. This is a polynomial with degree $9$ in terms of $x$.

Once the attacker constructs the polynomial $E_k(x)$, then can obatin ciphertext of any plaintext, which has the same effect as knowing the key. Moreover, the attacker may extract key $k$ from $E_k(x)$ because the coefficients of $x^8$ is $9k$.

When a polynomial has a degree of $d$, the complexity of constructing a Lagrange interpolation polynomial is $O(d\log d)$. Therefore, the degree of the polynomial used to represent the encryption function should be high enough. For instance, in the MiMC, the round number $r$ is determined as $r = \lceil \log_3 q \rceil$ to ensure that the degree $d$ attains the maximum degree of $q-1$.

An interpolation attack targets a univariate equation in terms of plaintext. If the plaintext is $\mathbb F_q^m$ instead of $\mathbb F_q$, then this attack cannot be applied directly.

GCD Attack​

The GCD attack is a key recovery attack that involves computing the GCD. In the GCD attack, the variable is the key $K$. We denote the encryption function as $E(K, x)$. For the plaintext-ciphertext pair $(x, y)$, we have $E(K, x) - y = 0$ for $K = k$. Now, let's consider two polynomials derived from the two pairs $(x_1, y_1)$ and $(x_2, y_2)$. Both $E(K, x_1) - y_1$ and $E(K, x_2) - y_2$ have a common factor of $(K-k)$, because $E(k, x_1) - y_1 = E(k, x_2) - y_2 = 0$. ($K$ denotes the variable of the key, and $k$ is the actual value of the key.) This common factor can be determined by computing the GCD.

The complexity of finding the GCD of two polynomials with a degree of $d$ is $O(d\log^2d)$. Therefore, keeping the maximum degree also thwarts this attack. Fortunately, degree grows exponentially as the number of rounds increases, so designers can build defenses against interpolation attacks and GCD attacks without much difficulty.

The GCD attack targets a univariate equation in terms of a key. If the key is in $\mathbb F_q^m$ instead of $\mathbb F_q$, then this attack cannot be applied directly.

Invariant Subfields Attack​

If the round constants or linear layers are poorly chosen, the ciphertext range may be limited to the subfields. For instance, consider the case where the field is $\mathbb F\_{2^n}$ and $\mathbb F\_{2^m}$ is a subfield of $\mathbb{F}\_{2^n}$. This implies that $m$ divides $n$. If all the round constants $c_i$ and the key $k$ in MiMC are in the subfield $\mathbb F\_{2^m}$, an adversary can ensure that $E_k(x) \in \mathbb F\_{2^m}$ by selecting a plaintext $x \in \mathbb F\_{2^m}$, and this reduces the possible key space $2^n$ to $2^m$ for an attacker --- for example, in MiMC, if the field is $\mathbb F\_{2^{128}}$ and all round constants $c_i$ and the key $k$ are in the $\mathbb F\_{2^{64}}$. Then, if the attack setting is chosen as a plaintext attack, an attacker may notice that the ciphertext is always in $\mathbb F\_{2^{64}}$ if the plaintext is in $\mathbb F\_{2^{64}}$. Therefore, an attacker is trying to test only $2^{64}$ key candidates instead of $2^{128}$.

This attack can be easily prevented by selecting a random round constant, such as a nothing-up-my-sleeve number. In other words, if an implementation utilizes custom round constants and the rationale behind their selection is undisclosed, there may be vulnerabilities to an invariant subfield attack. Please note that the invariant subfield attack is only effective on binary fields, as prime fields do not have subfields.

Linearization​

Linearization is a technique that represents multivariate equations as linear equations by transforming every monomial as new variables. Consider below the multivariate equations in $\mathbb F\_{11}$:

Then, by replacing every monomial to new variables like so,

the equations become a system of linear equations, and they can be easily solvable by Gaussian elimination.

Let $n$ be a number of unique monomials and $m$ be a number of equations. To solve given equations using linearization, $n \leq m$ must be hold, and the time complexity is $O(n^\omega)$, where $\omega$ is the minimum exponent for the complexity of matrix multiplication. At least every element in the matrix should be checked before multiplication, lower bounds of $\omega = 2$. And the current state-of-the-art algorithm is $\omega = 2.371866$. To show a resistance on the linearization, the designer should claim the number of monomials $n$ is enough that attack complexity is higher than expected security parameters.

For example, for $\mathbb F_q$ with $q \approx 2^{128}$, let key be $k = (k_0, k_1, k_2) \in \mathbb F_q^3$. The designer wants to show this primitive has 128-bits security. If $E(k, x)$ has a max degree $2^{48}-1$, then the number of monomials that can be constructed from the equation is approximately $2^{48 \times 3} = 2^{144}$, since the degrees of $k_1, k_2, k_3$ vary $0$ to $2^{48}$. Then the linearization time complexity is $O((2^{144})^\omega) \geq O(2^{288})$, even if we assume that $\omega = 2$. Therefore, this primitive is secure against linearization.

Meanwhile, the important question is of whether all the monomials can actually appear. If the expression is sparse and most of the monomials don't actually occur, then the attack may be possible. Therefore, the designer should claim that most of monomials have appeared theoretically, or experimentally shown using toy parameters.

Gröbner Basis Attack​

The Gröbner basis attack is a method for solving a multivariate system by computing the Gröbner basis. Algebraic structures of AOCs allow us to build multivariate equations for key and intermediate values. For example, let's consider three rounds of MiMC. Let $I_1$ and $I_2$ be the outputs of the first and second S-boxes, respectively.

Then, given plaintext-ciphertext pair $(x, y)$, we have a multivariate system:

The benefits of this multivariate system compared to the univariate system $y = (((x+k)^3 + k + c_1)^3 + k + c_2)^3 + k$ is that the degree of the equations are much lower. If we can solve this multivariate system for $k, I_1, I_2$, then the key is recovered. However, while univariate equations are easily solvable using well-studied algorithms like the Kaltofen-Shoup algorithm if the degree is not that high, there is no efficient algorithm for a multivariate system.

Instead of solving a multivariate system directly, the Gröbner basis of multivariate equations always contains a univariate equation. Once we find the Gröbner basis of the given equations, we obtain a univariate equation that we can solve.

So, what is the Gröbner basis? Understanding the Gröbner basis requires a very high level of mathematical proficiency; therefore, we would like to provide only a brief sketch and omit the details. For a deeper understanding of the technical knowledge, we recommend referring to this paper.

Let's consider the following multivariate system:

We can find another multivariate equation that has the same solutions as the above multivariate system by calculating $f' = m_1 \cdot f_1 + m_2 \cdot f_2$, where $m_1$ and $m_2$ are monomials. For example, we choose $m_1 = y$ and $m_2 = x$. Then $f_3 = m_1 \cdot f_1 + m_2 \cdot f_2 = y(x^2 - y^3 - y - 1) + x(-xy + x - y) = -y^4 - y^2 - y + x^2 - xy$. It is clear that the solution of the system ${f_1, f_2}$ is also the solution of $f_3$.

The Gröbner basis of the given multivariate system is earned by repeating the above calculations appropriately. The Gröbner basis has important characteristics:

1. The solutions of the system derived from the Gröbner basis are the same as the original multivariate system, and
2. The Gröbner basis has a univariate equation.

For example, the Gröbner basis of ${f_1, f_2}$ is ${g_1 = x + y^4 - y^3 + y^2 - y - 1, g_2 = y^5 - 2y^4 + 2y^3 - 2y^2 - y + 1 }$. Since $g_2$ is the univariate equation for $y$, $y$ is recovered from $g_2$. After that, $x$ is recovered by substituting $y$ into the obtained solution. The $(x, y)$ recovered from the Gröbner basis are also solutions of the original system.

The red (resp. blue) line denotes the zeroes of $g_1$ (resp. $g_2$). Images created from WolframAlpha.

To summarize, the Gröbner basis attack follows the following steps.

1. Calculate a Gröbner basis.

2. Identify a univariate polynomial in the given basis and solve for its roots.

3. Substitute this solution into the Gröbner basis and repeat Step 2.

Let's consider the time complexity of a Gröbner basis attack. For $L$ equations with degrees $d_1, \dots, d_L$ over $n$ variables, we define $P(x) = \frac{\prod_i(1-x^{d_i})}{(1-x)^n}.$

The degree of regularity $D_r$ is defined as the degree of the term with the first nonpositive coefficient in $P(x)$. The time complexity of calculating a Gröbner basis is estimated as $\binom{n + D_r}{D_r}^\omega,$ where $n$ is the number of variables and $D_r$ is the degree of regularity.

This value may not be intuitive, but it can be understood that as the number of variables $n$ decrease, the number of equations $L$ increase, and the degree of equations $d_i$ decrease, the system becomes easier to attack.

Attack Examples​

Generally, designers consider all of the above attacks in their primitives and choose their round numbers. However, there might be variants for each of these structures, and attackers try to find them to break the primitives.

We will introduce several attacks for the ZK-friendly hash functions. These attacks result in specification changes or design withdrawals.

Interpolation Attacks on MiMC​

The first attack is an interpolation attack on MiMC, which was proposed by Chaoyun Li and Bart Preneel (in this paper). We have discussed that for $r$ rounds of MiMC, the degree $d$ of the interpolation polynomial is $d = 3^r$. An attacker would need at least $3^r+1$ pairs to construct this polynomial, with a time complexity of $d\log d$. Furthermore, the memory complexity $(3^r + 1) \cdot \|\mathbb F\|$ represents the total memory required to store each coefficient. MiMC designers claim that if memory complexity is limited, then the number of rounds can be reduced. For example, the author suggests that 38 rounds are sufficient for MiMC-129/129 when the available bytes are limited to $2^{64}$ bytes.

However, Li and Preneel found novel attacks that construct partial polynomials. This attack uses only a negligible amount of memory. Although an attacker may have access to $3^r+1$ data points, it is impossible to recover the exact polynomial due to memory limitations. However, it is possible to recover only the second-highest term of the interpolated polynomial. (Please refer to section 3.3 in the paper for more information.) Once the second-highest term is recovered from the interpolation, the value of key $k$ can be determined as the second highest-term, $3^r \cdot k$.

This attack indicates that for MiMC-129/129, the full 82 rounds are necessary, even with restrictions on the memory available to the attacker. However, these results do not affect the security claims of the full round MiMC.

There is an another attack against MiMC that aims the full round MiMC using higher-order differential cryptanalysis (read more here). However, this attack is faster than a brute-force attack but requires $2^{n-1}$ chosen data for binary field $\mathbb F\_{2^n}$. Therefore, it is not considered as a realistic threat.

Gröbner Basis Attack on Jarvis and Friday​

Jarvis and Friday are a ZK-friendly block cipher and a hash function, respectively (read more here). Since Friday is the Merkle-Damgård construction of Jarvis, it is enough to discuss the structures of Jarvis only. Similar to the S-box used in AES, Jarvis employs an inverse S-box as a nonlinear layer. The inverse S-box in the field $\mathbb F\_{2^n}$ is defined as $inv(x) = x^{2^n-2}$. If $x = 0$, then $inv(x) = 0$, and $x \times inv(x) = 1$ otherwise.

The structure of Jarvis is relatively simple. The round function is composed of the inverse S-box, degree $4$ polynomials $B$ and $C$. $B(x)$ and $C(x)$ are formed as follows: $B(x) = b_4 \cdot x^4 + b_2 \cdot x^2 + b_1 \cdot x^1 + b_0 \cdot x^0$ and $C(x) = c_4 \cdot x^4 + c_2 \cdot x^2 + c_1 \cdot x^1 + c_0 \cdot x^0$. These equations are the same as those used in Vision. Finally, one round of Jarvis can be represented as $\textsf{Jarvis}\_i(s) = C(B^{-1}(inv(s))) + K_r$, where $i$ represents the round number index.

The inverse S-box is also utilized in their key schedule, as shown below.

Even with just one or two inverse S-boxes, it is possible to achieve maximum degrees. Moreover, the cost for SNARK/STARK is relatively low because only verifying $x(1-xy) = 0$ and $y(1-xy) = 0$ is sufficient to check for $y = inv(x)$. The authors considered several attacks and suggested using 10, 11, 12, and 14 rounds for $n = 128, 160, 192, 256$, respectively.

However, they did not consider Gröbner basis attacks, and according to this paper, Jarvis is vulnerable to such attacks.

If only the key is treated as a variable, then the equation is univariate. However, the degree is high, making it difficult to recover the key. However, if we add every intermediate value as variables, the system becomes multivariate. With these intermediate values, the degree becomes dramatically lower and allows to mount Gröbner basis attacks.

For each round, $x_i = B^{-1}(inv(s))$ is considered as a variable.

The following equations are given:

• $(C(x_i) + k_i) \cdot B(x\_{i+1}) = 1$: $r-1$ equations of degree $8$.
• $B(x_1) \cdot (p + k_0) = 1$: One equation of degree $5$.
• $C(x_r) = c + k_r$: One equation of degree $4$.
• $(k\_{i+1}+c_i) \cdot k_i = 1$: $r$ equations of degree $2$.

There are $2\cdot r+1$ variables $x_1, \dots, x_r$ and $k_0, \dots, k_r$ with $2\cdot r+1$ equations. Unfortunately this breaks only a reduced round of Jarvis, but with the optimizations suggested in the paper, the number of variables are decreased and succeed in attacking the full round of Jarvis (see section 4.2 of the paper).

From this attack, we realized that with intermediate variables, the expression could be represented in a different form to make the attack possible. In particular, ZK-friendly hash functions often allow expressions to be represented in low degrees if they are well-transformed for efficiency, but care must be taken not to make them vulnerable to a Gröbner basis attack.

Invariant Subspace Attacks on Starkad​

Starkad is a ZK-friendly hash function that has the same structure as Poseidon, with the only difference being that Starkad uses binary fields while Poseidon uses prime fields. The authors of Poseidon initially proposed both Starkad and Poseidon, but they have since withdrawn Starkad.

Let's review the structures of Starkad. The S-box layer in the middle is made of partial S-box layers. This would reduce the R1CS or AET cost.

The purpose of the linear layer is to spread local changes onto the entire state. In Starkad, the linear layer is a Cauchy matrix, which is defined by $M[i,j] = \frac{1}{x_i + y_j}$ for the entries of ${x_i}\_{1 \leq i \leq m}$ and ${y_i}\_{1 \leq i \leq m}$, which are pairwise distinct, and $x_i + y_j \neq 0$, where $i \in {1, \dots, m}$ and $j \in {1, \dots, m}$. To generate the sequences ${x_i}\_{1 \leq i \leq m}$ and ${y_i}\_{1 \leq i \leq m}$, a constant $r$ and a starting point $x_0$ are first chosen. The variables $x_i$ and $y_i$ are defined as follows: $x_i = x_0 + i - 1$ and $y_i = x_i + r$. The matrix is generated and fixed once, and the designers choose $x_0 = 0$ and $r = m$, where $m$ represents the number of words in each layer.

However, this MDS matrix allows for large invariant subspaces that pass through the entire middle partial S-box rounds without activating any S-boxes. This renders the middle $R_P$ rounds linear, as noted in the attack paper. More precisely, for a certain invariant subspace $V$, if $\Delta \in V$ and $x \oplus y = \Delta$, then $F(x) \oplus F(y) = L(\Delta)$, where $F$ represents the middle layer and $L$ represents a linear transformation. This affects security in terms of both statistical and algebraic cryptanalysis.

Although this attack can be mitigated by selecting a value for $m$ that is not divisible by 4 or by choosing another secure MDS matrix, designers decided to dismiss Starkad and let only Poseidon remain.

Conclusion​

In this post, we've discussed several algebraic attacks and their usages in the primitives. When designing new AOCs, be sure to consider whether they are secure against attacks like the ones mentioned in this post. This is an active area of research, so it is recommended to periodically check places like the Cryptology ePrint Archive for new attacks.

About us​

Zellic is a smart contract auditing firm founded by hackers, for hackers. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants. Whether you’re developing or deploying smart contracts, Zellic’s experienced team can prevent you from being hacked.

Contact us for an audit that’s better than the rest. Real audits, not rubber stamps.

If you think you’d be a good fit to work at Zellic, we’re hiring!

Introduction​

Zero-knowledge proofs (ZKPs) represent a family of cryptographic protocols that enable one party (denoted the prover) to produce proofs of knowledge for a set of values denoted witness values. The proofs allow the prover to prove knowledge of the witness values to another party (denoted the verifier) without disclosing any additional information about the values themselves.

The aforementioned mechanism extends quite naturally to proving computational integrity --- in other words, a particular computation has been performed correctly and honestly. Every operation in a computation may be represented as a constraint on the inputs and outputs of the operation. If a prover presents the output for a computation, along with a proof that they know has valid state values for every constraint in the computation, verifying the proof is equivalent to verifying that the output was computed correctly for some inputs. Therefore, the verifier is assured of the validity of the output without having to perform the computation.

Most notably, ZK proofs are used in cryptocurrencies to improve trust, privacy, and stability on the blockchain. By increasing the level of security without compromising the integrity of transactions, ZK proofs play a crucial role in these decentralized systems. In this blog, we will take a surface level walk-through of the landscape and real-world applications of zkSNARKs.

What Are zkSNARKs?​

Specifically, zkSNARKs is an acronym for zero-knowledge succinct noninteractive argument of knowledge.

1. ZK: ZK stands for zero-knowledge. As explained above, it allows a verifier to verify that a proof made by a prover is valid. Also, the verifier does not learn anything about the specific information in the proof. This characteristic ensures a high level of privacy as it allows sensitive information to remain hidden while still providing sufficient proof of its legitimacy.
2. S: S stands for succinct. This means that the length of the proof has to be relatively small. How small? Usually, these proofs are only a few hundred bytes in length. The small size of the proofs allow for blazing fast verification in only a few milliseconds.
3. N: N stands for noninteractive. This property is by far the most important property of zkSNARKs. A noninteractive proof means that the proof can be generated without any interaction from the verifier. Once the proof is created, it can be sent to a verifier, who can then confirm or refute the proof. The lack of interaction means that the proof can be publicly posted for anyone to verify without the need to communicate to the original prover.
4. AR: AR stands for argument (of) and goes along with the next letter.
5. K: K stands for knowledge. Combining with AR, the letters "ARK" stand for argument of knowledge. An argument of knowledge is a type of proof where a prover convinces a verifier that they have knowledge of a certain piece of information. This is done under a computational assumption; it's computationally infeasible for a dishonest prover to convince a verifier of a false statement. This is different from the zero-knowledge property since it focuses more on the soundness of the proof.

zkSNARKs are important mostly due to their noninteractive property. On the blockchain, it is infeasible to communicate with every user and have each verify a proof. It is much easier for the prover to post a proof to the public and have anyone verify it without having to communicate back to the prover.

Applications Into Blockchains & Real World​

zkEVMs​

Due to the increasing popularity of Ethereum, transaction times have been longer, fees have increased, and scalability has become a challenge. A solution to these challenges is by using zkEVMs along with zkRollups to help solve these problems. A zkEVM is a combination of zero-knowledge proofs with the Ethereum Virtual Machine. It essentially uses ZKPs to prove that a transaction happened in the zkEVM.

More specifically, the zkEVM lives on a Layer 2, a separate blockchain that utilizes and extends the main Ethereum chain. Now, smart contracts can be uploaded and the EVM runs the smart contract byte code. To prove that a state change occurred when interacting with a smart contract, the ZK part of the zkEVM creates a noninteractive proof that anyone can verify on that transaction.

As the blockchain increases in the number of blocks, it becomes computationally infeasible to go through every block. zkRollups come to the rescue. Put simply, zkRollups take a large chunk of user transactions and squeeze them into one mega block. It also attaches a proof onto this new block, which allows anyone to verify that the new block was made up of a large chunk of transactions. zkRollups offer a solution to the ever-increasing number of blocks on the blockchain.

By "rolling up" a large number of transactions into a single block, it greatly reduces the amount of data needed to be stored on the blockchain, increasing scalability and efficiency. Instead of having each transaction directly uploaded to the blockchain, transactions are bundled up first and then uploaded.

This is Polygon’s solution:

Polygon is one of the first creators of zkEVMs. Polygon is a Layer 2 scalability solution that uses a zkEVM for users to interact with to increase the speed of transactions and lower transaction fees. Right now, the main Ethereum chain can handle around 30 transactions per second (TPS). By uploading transactions to Polygon, they can be processed at speeds of up to 2,000 TPS. To achieve this speed, Polygon uses a side chain where lots of transactions are bundled up through a zkRollup before being sent to the main Ethereum blockchain to reduce the total communication to the main chain.

Along with faster transaction speeds, the cost per transaction is also reduced. Polygon achieves this in the same way by using zkRollups. Since the interaction with the main Ethereum blockchain is minimal, the gas fees for each interaction is shared across all the transactions that were rolled up. This splits a normal gas fee of about $20 to a few pennies for every user.

zkBridges​

As more and more cryptocurrencies are created and the blockchain ecosystem diversifies, the demand for communicating and exchanging different coins increases. Given that each cryptocurrency is on its own blockchain, crypto bridges are used to transfer coins from one blockchain to another. Right now, two popular ways that people trade cryptocurrencies are through a centralized trusted party or by verifying consensus.

A centralized party for exchanging different cryptocurrencies is the same as currency exchange in the real world. A bank or a trusted party allows one to deposit some coins in exchange for other coins. This trusted party acts as a market maker. However, there are a few problems with this. First, in order for this exchange to occur, the market maker must have enough of both coins (i.e., liquidity) to perform a trade. Using Ethereum and Polygon MATIC as an example, if one wants to exchange their Ethereum for MATIC, the centralized trusted party must have enough MATIC coins to meet the value of the Ethereum coins being traded. If no one is trading from MATIC back to Ethereum, then the process stops: there isn’t enough MATIC to cover for the Ethereum coins. Second, if the central party is untrustworthy, they could steal all the deposited coins and disappear into thin air (i.e., a rug pull).

The zkBridge between Ethereum and Polygon MATIC.

Another solution to the crypto exchange problem is through zkBridges. It brings ZK proofs with crypto bridges to provide exchanges between different cryptocurrencies that use the EVM without the need of an intermediate trusted party. Let's use a transaction between Ethereum and Polygon as an example.

When a transaction is made and a block is created on the main Ethereum blockchain, it needs to be validated. To accomplish this, validators create a proof of consensus by using their own keys to sign the block. After a certain number of validators have signed the block and the signatures are verified, there becomes a consensus that the block is indeed valid.

After achieving a proof of consensus, a Merkle proof is created for the specific block and transaction and sent to a smart contract on the Polygon chain. Since smart contracts cannot communicate with each other cross-chain, a middle party is still used. However, these middle parties are more trustworthy since they can't mess with the proofs without invalidating them.

Succinct Labs takes advantage of this and uses a modified proof of consensus and Merkle proofs to achieve a zkBridge on cryptocurrencies that use the EVM. For Succinct Labs, a proof of consensus is formed by using 512 validators that are rotated every 27 hours to sign all new block headers on the main Ethereum chain with Groth16 (used by Tornado Cash). These proofs can be validated very efficiently on chain due to the constant-time proof verification of Groth16. When the validity of the proof is determined, a Merkle proof is used to relay the transaction across the cross-chain completing the zkBridge and allowing coin exchange.

zkProgramming Languages​

In the development of ZK proofs or ZK circuits, Rust is typically chosen as the language to write them in. However, this requires both an understanding of the Rust language and an understanding of ZK circuits and libraries. Right now, most ZK libraries are quite bare. Developers are required to read large amounts of documentation just to find out how to use a function safely.

Due to this, the innovation of ZK technologies has been quite slow. The goal of a ZK programming language is to simplify the development of ZK circuits. By moving all the complex math behind the scenes, writing ZK circuits can be treated as writing conditionals in a normal programming language. It would allow regular software engineers without a deep understanding of how ZK circuits work to create them efficiently.

The need for ZK programming languages arises from the fact that coding up ZK circuits involves lots of math and cryptographic operations. Understanding these concepts require specialized knowledge in areas like cryptography and number theory. This creates a barrier for software engineers who may not have a strong background in these domains. Instead of using a ZK library to create constraints for a conditional statement, an if statement written in Noir is automatically converted to a circuit conditional. For example, to set a value a that depends on a boolean b without Noir,

let a = b*f(x) + (1-b)*g(x);

With a ZK programming language, it's as simple as

if b {
    let a = f(x);
} else {
    let a = g(x);
}

without the boolean algebra behind it.

Noir is a ZK programming language created by Aztec to bridge the gap between software engineers and ZK circuits. By using a Rust-like language and syntax, developers don’t have to relearn a new language and can create ZK circuits easily. Additionally, Noir already implemented a lot of useful ZK gadgets in their standard library including Merkle proofs, ECDSA, field methods, and more. For example, using a Merkle proof is as easy as this:

use dep::std;

fn main(message : [Field; 62], index : Field, hashpath : [Field; 40], root : Field) {
    let leaf = std::hash::hash_to_field(message);
    let merkle_root = std::merkle::compute_merkle_root(leaf, index, hashpath);
    assert(merkle_root == root);
}

However, Noir doesn't compile code directly to a ZK circuit. During compilation, the written code compiles into an intermediate phase called the abstract circuit intermediate representation (ACIR). It compiles all code into R1CS, which allows users to choose the best proving system needed for their use. The ACIR code is then finally compiled with the chosen proving system on the abstract circuit virtual machine (ACVM), which acts as a ACIR compiler.

Conclusion​

Overall zk-SNARKs provide a powerful tool for enhancing privacy and trust in blockchain systems. With a diverse range of applications (zkEVMs, zkBridges, zkProgramming languages), they can fit into a wide variety of needs on the blockchain. By allowing parties to prove integrity of computational results, ZK opens avenues for not only privacy applications but delegating computations since off-loaded workloads can be computed verifiably.

Special thanks to fellow Zellic engineer Mohit Sharma for their help and input in this article.

About Us​

Zellic is a smart contract auditing firm founded by hackers, for hackers. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants. Whether you’re developing or deploying smart contracts, Zellic’s experienced team can prevent you from being hacked.

Contact us for an audit that’s better than the rest. Real audits, not rubber stamps.

Introduction​

Hash Function​

A cryptographic hash function is one of the basic primitives for cryptography. (In this article, the word hash function will mean cryptographic hash function unless otherwise noted.) A cryptographic hash function satisfies the below three secure properties:

1. Preimage resistance: Given hash value $h$, it is hard to find any input message $m$ that $f(m) = h$.
2. Second-preimage resistance: Given input message $m$, it is hard to find message $m'(\neq m)$ that $f(m')=f(m)$.
3. Collision resistance: It is hard to find any two different input messages $m_1,m_2(\neq m_1)$ that $f(m_1)=f(m_2)$.

Cryptographic schemes such as digital signatures, message authentication codes, commitment schemes, and authentications are built on top of hash function. For example, the preimage resistance property of a hash function enables the proof-of-work system in cryptocurrency. SHA-2 and SHA-3 are common examples of hash functions, and they are adopted for general purposes.

Usage of Hashes in the ZK protocol​

A hash function is also useful in the ZK protocol. One famous example is the membership check in a Merkle tree. For a Merkle root $r$, the prover will claim knowledge of the witness $w_1,\dots,w_n$ such that

to prove their knowledge of element $w_1$, which is a member of the Merkle tree. We already discussed this usage in our previous post, “How Does Tornado Cash Work?”.

Traditional uses of hash functions can be utilized in the ZK protocol as well, such as integrity checks using vanilla hash computation, retrieving pseudorandom strings from the fixed length seed, and signing transactions.

Why Are ZK-Friendly Hash Functions Required?​

The standardized hash functions such as SHA-2 and SHA-3 are extensively studied, and their security is widely believed. Moreover, traditional software and hardware implementations of them are efficient compared to their competitors.

So when we need to evaluate a hash in ZK protocols, it seems nice to use SHA-2 or SHA-3. However, many ZK protocols are using relatively unfamiliar hash functions such as MiMC, Poseidon, and Rescue instead of SHA-2 and SHA-3.

The main reason for this is that efficiency in ZK protocols is determined in quite different ways from traditional metrics such as running time, power consumption, and gate count. The efficiency of the circuits in ZK protocols depends on their algebraic structure.

Generally, if the circuit is represented as simple expressions in a large field, it allows efficient proof in terms of prover execution time and proof size. Unfortunately, traditional hash functions are inappropriate for this.

For example, SHA-2 is about 50--100 times more inefficient than ZK-friendly hash functions when the hash is computed in zk-STARK. This huge performance gap demonstrates the need for a ZK-friendly hash function.

In this post, we will introduce several ZK-friendly hash functions that are introduced in famous conferences and journals. It might be fun to focus on the design rationale for each hash function.

ZK Protocols​

We first discuss the ZK protocols. Rather than trying to fully understand the protocols, we'll focus on their high-level characteristics and what the metric is to determine efficiency.

zk-SNARK​

zk-SNARK is an acronym that stands for zero-knowledge succinct non-interactive argument of knowledge.

1. Zero-knowledge: Verifier learns nothing other than the statement is true.
2. Succinct: Proof size and verifier time is sublinear.
3. Non-interactive: Needs no interaction between prover and verifier.
4. Argument of knowledge: Not only for existence of input $x$ but also prover's knowledge of $x$.

While there are several ways to build a protocol that satisfies the above characteristics, such as linear PCP + pairing-based cryptography, constant-round polynomial IOP, and polynomial commitment scheme + IOP-based, Groth16 based on the linear PCP and pairing-based cryptography is the most widely used one.

Groth16 and many other zero-knowledge proof systems such as Aurora, Ligero, and Bulletproofs are evaluating the circuit in Rank-1 Constraint System (R1CS) form.

R1CS Examples​

The R1CS is a system of equations, where each equation is defined by a triplet of vectors $(\vec{a}\_i,\vec{b}\_i,\vec{c}\_i)$ such that $(\vec{a}\_i \cdot \vec{s}) \times (\vec{b}\_i \cdot \vec{s}) = (\vec{c}\_i \cdot \vec{s})$.

For example, $y = x^3$ can be interpreted as two equations defined by a triplet of vectors (with intermediate value $z = x^2$):

In the SNARK setting, the cost is determined by the number of constraints in the R1CS. For example, $x^\alpha$ for the constant $\alpha$ requires $\lceil \log_2(\alpha) \rceil$ constraints. This implies that $x^5$ and $x^7$ have the same cost in the SNARK setting.

zk-STARK​

zk-STARK is an acronym that stands for zero-knowledge scalable transparent argument of knowledge.

1. Zero-knowledge: Verifier learns nothing other than that the statement is true.
2. Scalable: Prover time is quasilinear; proof size and verifier time is sublinear.
3. Transparent: No trusted setup is needed.
4. Argument of knowledge: Not only for existence of input $x$ but also for prover's knowledge of $x$.

Any protocol that satisfies the above conditions is called a zk-STARK. However, zk-STARK often refers to the protocol in the paper where the concept was first proposed. We also refer to the protocol in that paper as zk-STARK in this article.

To evaluate the circuits in a STARK setting, the circuit should be transformed into algebraic intermediate representation (AIR).

AIR Examples​

We give an example of computing a Fibonacci sequence. The Fibonacci sequence is defined as $\begin{aligned} a_0 &= 1, \\ a_1 &= 1, \\ a_i &= a\_{i-1} + a\_{i-2} \text{ for } i \geq 2. \end{aligned}$

The prover wants to prove that $a\_{7} = 21$. Then an algebraic execution trace (AET), an execution trace of a computation of the Fibonacci sequence, is

And the AIR constraints described in the polynomial forms are

1. $a_0 -1 = 0,$
2. $a_1 -1 = 0,$
3. $a\_{i} - a\_{i-1} + a\_{i-2} = 0 \text{ for } 2 \leq i \leq 7,$
4. $a_7 = 21.$

Let $t$ be a number of rows and $w$ be a number of columns in AET. Then the size of the AET is $t \cdot w$. Moreover, let $d$ be the maximal degree of an AIR constraint. In our case, $t = 8, w = 1, d = 1$. The efficiency of a zk-STARK is determined by $t, w, d$. For each circuit, the efficiency is compared by measuring $t \cdot w \cdot d$.

ZK-Friendly Hash Functions​

Roughly speaking, the simpler the algebraic representation of a given circuit, the more efficient it is for both R1CS and AIR representations. Therefore, cryptographers began to design structures that were both algebraically simple and still secure. We often called these ciphers as arithmetization-oriented ciphers (AOCs).

For AOCs, most traditional symmetric cryptanalysis such as differential and linear cryptanalysis are generally less relevant. The most powerful attack type for AOCs is algebraic attack, such as Gröbner basis, linearization, GCD, and interpolation attack. Once the designer decides their cipher's design, the round number is chosen to be safe from those attacks.

On the other hand, this field is relatively new and interesting attacks (see examples one, two, three, and four) have been claimed, often resulting in ciphers being broken or parameters being modified, but we'll talk about those in the next post.

Let's take a look at the design rationale behind the different AOCs.

MiMC​

MiMC is the first ZK-friendly hash function, introduced in ASIACRYPT 2016. Although more efficient ZK-friendly hash functions are suggested after MiMC, MiMC is still widely used in many applications since it is considered mature compared to the other ZK-friendly hash functions.

The design of MiMC is extremely simple: a function $F(x) := x^3$ is iterated with subkey additions. This concept was already proposed by Nyberg and Knudsen in the 1990s, called KN-Cipher.

MiMC-$n/n$​

We first take a look at a block cipher. The block cipher is constructed by iterating $r$ rounds, where each round function is described as $F_i(x) = (x + k + c_i)^3$. In the round function, $c_i$ is a round constant and $k$ is a key, and the field is $\mathbb F_q$ where $q$ is a large prime or $q = 2^n$. The encryption process is defined as $$ E_k(x) = (F_{r-1} \circ F_{r-2} \circ \dots \circ F_0)(x) + k. $$

and $c_0$ is fixed to $0$ because $c_0$ does not affect security. (If you're interested, I recommend checking it out for yourself!)

For a field $\mathbb F_q$, $F(x) = x^3$ has an inverse if and only if $\gcd(3, q-1) = 1$. Therefore, the author suggested choosing odd $n$ for $q = 2^n$ and $q = 3k+2$ for prime $q$.

The round constants $c_i$ are not specified in the paper, but $c_i$ is recommended to be chosen randomly at first and hardcoded into the implementation. To show nothing up my sleeve on the round constants, it is often generated from the SHA-2 (or any other secure hash functions) digest of certain messages like MiMC0, MiMC1, $\dots$.

The round number is determined by $r = \lceil log_3 q \rceil$. For example, the round number $r = \lceil log_3 (2^{127}) \rceil = 81$ for a field $\mathbb F\_{2^{127}}$. We discuss the reason of this later.

$r$ rounds of MiMC-$n/n$. Images from MiMC paper.

MiMC-$2n/n$​

It is also possible to construct a block cipher with the same nonlinear permutation in a Feistel network. The round function of MiMC-$2n/n$ is described in the below figure and can be defined as $$ x_L || x_R \leftarrow x_R + (x_L + k + c_i)^3 || x_L. $$

MiMC-$2n/n$ round function. Images from here.

For each round, only half of the data is changed; therefore, the number of rounds for the Feistel version is $2 \cdot \lceil log_3 q \rceil$, which is doubled from the number of rounds of MiMC-$n/n$.

The Hash Function​

When the key is fixed at $0$, then the block cipher becomes a permutation. Given a permutation, there is a well-known construction deriving hash functions from a permutation called the sponge framework, which is proven secure and used in many other hash functions, including SHA-3.

The sponge construction. $P_i$ is input; $Z_i$ is hashed output. The unused capacity $c$ should be twice the desired collision or preimage attacks. Images from Wikipedia.

The sponge construction consists of two phases called absorb and squeeze. In the absorbing phase, the input data is absorbed into the sponge. Afterwards, the result is squeezed out.

The hash function from MiMC is also based on the sponge framework. In the absorbing phase, message blocks are added to a subset of the state, then transformed as a whole using a permutation function $f$ (in our case, an MiMC permutation). Note that all the other ZK-friendly hash functions introduced in this post are also based on the sponge framework.

Security Analysis​

While interpolation attack, GCD attack, invariant subfields attack, differential cryptanalysis, and linear cryptanalysis are considered in the paper, we will only introduce interpolation attack in here, which provides the lower bound of the round numbers. An interpolation attack constructs a polynomial corresponding to the encryption function without knowledge of the secret key. If an adversary can construct such a polynomial, then for any given plaintext, the corresponding ciphertext can be produced without knowing the secret key.

Let $E_k$ be an encryption function with degree $d$ in terms of input $x$. Then with the $d+1$ plaintext-ciphertext pairs, $E_k(x)$ can be constructed using Lagrange's theorem, and the complexity of constructing a Lagrangian interpolation polynomial is $O(d \log d)$. In our case, degree $d = 3^r$. By choosing $r = \lceil log_3 q \rceil$, the degree $d$ reaches $q - 1$ and the attack becomes infeasible.

SNARK Complexity​

Since the single constraint can square the value, there are two R1CS constraints in each round of MiMC permutation:

x2 = x*x
x3 = x2*x

To generate a 256-bits output hash for the 256-bits input $x$, the sponge construction is used. In details, calculate MiMC-$2n/n$ of $(x, 0)$, then left 256-bits are hash value. The round number is chosen as $2 \cdot \lceil log_3 (2^{256}) \rceil = 324$. Then the number of constraints is $324 \times 2 = 628$. Note that field should be chosen as $\gcd(3, q-1) = 1$, which means that $\mathbb F\_{2^{256}}$ should not be chosen.

STARK Complexity​

In AIR representations, for MiMC-$2n/n$, each row has two variables, $x_L$ and $x_R$. We denote $x_L, x_R$ in $i$-th row as $x^{(i)}\_L, x^{(i)}\_R$. Then from the round function $x_L \|\| x_R \leftarrow x_R + (x_L + k + c_i)^3 \|\| x_L$, the constraint polynomial is defined as

1. $x^{(i+1)}\_L = x^{(i)}\_R + (x^{(i)}\_L + k + c_i)^3,$
2. $x^{(i+1)}\_R = x^{(i)}\_L.$

Then the number of rows $t = 324$, the number of columns $w = 2$, and the maximal degree $d = 3$. The efficiency metric is $t \cdot w \cdot d = 1944.$

Implementations​

Although the authors suggested $x^3$ as S-box, this S-box is often replaced to other S-boxes such as $x^5, x^7$ if $\gcd(3, q-1) = 1$. For example, the BN254 field is $F_q$ for 254-bits prime $q$, which is $\gcd(3, q-1) \neq 1$. As a result, when using MiMC on the BN254, it is preferred to use $x^5$ or $x^7$ instead of $x^3$ (example 1, example 2). In this case, the round number is determined as $\log_5 q$ or $\log_7 q$, which mitigates all the attacks presented so far.

For the round constants, the authors do not specify how to generate them in the paper. Therefore, each implementation will determine the round constants by computing the hash value of strings like MiMC0 and MiMC1 using SHA-2 or SHA-3. If someone creates their own MiMC implementation without disclosing how the round constants were generated, there might be a potential vulnerability, such as being susceptible to an invariant subfields attack.

Poseidon​

Poseidon is a yet another ZK-friendly hash function suggested in USENIX 2021. Poseidon is based on the HADES design strategy, which is a generalization of a substitution-permutation network (SPN), suggested in EUROCRYPT 2020.

HADES Design Strategy​

SPN is a famous block cipher algorithm. For example, AES uses the SPN structure. By applying enough alternating rounds of substitution boxes and permutation boxes, the attacker is unable to recover a key from plaintext-ciphertext pairs.

HADES is composed of three steps: Add Round Key, SubWords, and MixLayer.

This seems to be the same approach with SPN, but the main difference between the existing SPN and HADES is that some S-box layers in HADES are partial S-box layers, which means that a single S-box is applied for the rightmost element and identity is applied for the others. The author argued that this would reduce the R1CS or AET cost.

Poseidon Hash Function​

The Poseidon hash function follows the same construction as HADES, with replacing Add Round Key to Add Round Constants. Poseidon only considers the prime field $\mathbb F_p$. Let $m$ be the number of words in each layer (to avoid confusion with the number of rows $t$ in STARK, we use $m$ instead of $t$ unlike the notation in the paper). The graphical overview is shown below.

Construction of Poseidon. $R_F = 2 \cdot R_f$ is the number of the full S-box rounds, and $R_P$ is the number of the partial S-box rounds. Images from Poseidon paper.

The S-box is defined by $\text{S-box}(x) = x^\alpha$, where $\alpha \geq 3$ is the smallest positive integer that satisfies $\gcd(\alpha, p-1) = 1$.

The purpose of the linear layer is to spread local changes onto the entire state, so usually the linear layer is chosen as an MDS matrix, and its effects are negligible on the cost. In Poseidon, the linear layer is a Cauchy matrix, which is defined by $M[i,j] = \frac{1}{x_i + y_j}$ for the entries of $\\x_i\\\_{1 \leq i \leq m}$ and $\\y_i\\\_{1 \leq i \leq m}$ are pairwise distinct and $x_i + y_j \neq 0$, where $i \in {1, \dots, m}$ and $j \in {1, \dots, m}$. This was an original suggestion in Poseidon; however, some Cauchy matrixes are insecure if there is an invariant subspace trail. We omit the details of the attack. The interested reader may refer to the paper. Therefore, the linear layer should be carefully chosen to avoid this type of attack.

The structure is highly parameterizable, and the suggested parameters for a 256-bits output hash are $m = 3, R_F = 8, R_P = 57$ for an $\alpha = 5$ over $\mathbb F_p$ with $\approx$ 256-bit $p$. $R_F = 8$ is chosen to prevent statistical attacks, and $R_P = 57$ is chosen to prevent algebraic attacks.

SNARK Complexity​

For $\alpha = 5$, S-box $x^\alpha$ is represented by three constraints:

x2 = x*x
x4 = x2*x2
x5 = x4*x

And the total S-box number is $m \cdot R_F + R_P$. Therefore, the total number of constraints for $\alpha = 5$ is $3 \cdot (m \cdot R_F + R_P)$. For $m = 3, R_F = 8, R_P = 57$, it requires $276$ R1CS constraints.

STARK Complexity​

If we maintain $m$ variables for each round, then the number of rows is $t = R_F + R_P$, the number of columns is $w = k$, and the maximal degree is $d = \alpha$. Then the efficency metric is $t \cdot w \cdot d = (R_F + R_P) \cdot m \cdot \alpha$. However, this AET representation does not take advantage of partial S-box rounds. Instead of this, by treating every S-box output as a variable, the number of rows is $t = 1$, the number of columns is $w = m \cdot R_F + R_P$, and the maximal degree $d$ is still $\alpha$. For $m = 3, R_F = 8, R_P = 57$, the efficiency metric is $t \cdot w \cdot d = 1 \cdot 81 \cdot 5 = 425$.

Vision / Rescue​

Vision / Rescue are ZK-friendly hash functions following the Marvellous design strategy. They are suggested in FSE 2020.

Marvellous Design Strategy​

Marvellous design is a substitution-permutation network parameterized by the tuple $(q, m, \pi, M, v, s)$:

• $q$ : The field is $\mathbb F_q$, with $q$ either a power of $2$ or a prime number,
• $m$ : The state is $m$ elements in $\mathbb F_q$,
• $\pi = (\pi_0, \pi_1)$ : The S-boxes,
• $M$ : An MDS matrix,
• $v$ : The first step constant, and
• $s$ : The desired security level.

In each round of a Marvellous design, a pair of S-boxes $(\pi_0, \pi_1)$ is used alternately. The difference between $\pi_0$ and $\pi_1$ is in their degree. For one, $\pi_0$ should be chosen with a high degree when evaluated forward and a lower degree when evaluated backward. The other S-box, namely $\pi_1$, is chosen with the opposite goal, meaning that it has a low degree in the forward direction and a high degree in the backward direction. This choice has three benefits:

1. No matter which direction an adversary is trying to attack, the degree is guaranteed to be high.
2. It results in the same cost for the encryption and decryption functions.
3. Owing to nonprocedural computation, the low-degree representation of each S-box can be evaluated efficiently.

For Vision / Rescue, $\pi_0$ is obtained directly from $\pi_1$: $\pi_0 = \pi_1^{-1}$.

The linear layer is chosen by the Vandermonde matrix. As described in Poseidon, there is no security claim related to the Vandermonde matrix, and any other MDS matrix should be fine.

The one interesting thing that differentiates the Marvellous from the others is that it uses a heavy key schedule. In MiMC and HADES, there is no special key schedule and the master key is added for each round. However, in Marvellous, the key schedule reuses the round function. The author claimed that this is a kind of security margin as the domain of AOCs is relatively new. Note that a heavy schedule does not affect the efficiency of hash functions from fixed-key permutations because every subkey is derived in the offline phase.

Vision​

Vision is meant to operate on binary fields with its native field $\mathbb F\_{2^n}$. To construct the S-boxes, we select degree $4$, which we denote by $B$. More precisely, there are no $x^3$ terms in $B(x)$: $B(x) = b_4 \cdot x^4 + b_2 \cdot x^2 + b_1 \cdot x^1 + b_0$. Then $B$ is linearized on $\mathbb F_2$ and it gives benefits for other computation settings such as MPC. However, it is irrelevant with the SNARK/STARK setting, so we don't discuss it any further.