Zero-knowledge Proofs for Relaying Block Headers between Dogecoin and Ethereum

Introduction

The purpose of this post is to describe the possibilities as well as the limitations of the use of zero-knowledge proofs (zk proofs) in bridging Dogecoin to Ethereum. Previous attempts of decentralized bridges taking advantage of Ethereum’s smart contracting were built on fraud proofs (e.g. [1], [2]). In these approaches special entities called challengers, who observe the data inserted into Ethereum through so-called relayers, start a challenge-response game when they spot incorrect data. This requires setting up economic incentives for the challengers which is a notoriously non-easy task: they should only be compensated for successful challenges, but must also be incentivised to stay alert during the time no challenges are necessary — which, in fact, should be the normal situation. Additionally, challenge periods must be reasonably long making the entire bridging process longer (although it might not be that critical for a bridge than it is for usual transactions as in rollups). With zk proofs no incorrect data can enter Ethereum in the first place, basing the security of the bridge on the security of the source chain, i.e. Dogecoin. Only availability of the data can be a concern which depends on the activity of the relayers. Their activity can be compensated by setting the right incentives. Hence, zk proofs are an interesting alternative to fraud proofs (see also zk-rollups vs optimistic rollups).

In this context it is not the zero-knowledge part of zk proofs which is important, i.e. the privacy of the prover’s knowledge, but the soundness of the prover’s knowledge: a short proof allows the verifier to check the correctness of the result of a long computation without running the computation itself. In essence, what is of interest here, is that the the relayer takes the role of the prover and calculates the SCRYPT hash function used in Dogecoin’s proof of work (PoW), where the verifier is run inside the Ethereum virtual machine (EVM). As SCRYPT is far too costly in the EVM, using zk proofs allows us to calculate the SCRYPT hash off-chain, and leaves the on-chain smart contract with the much smaller task of only verifying the correctness of the hash value by checking the proof.

The problem is that this “only verifying” in the previous sentence can still refer to a too large computation that makes the zk relaying bridge too expensive to maintain. This article focuses on proving the existence of a transaction in Dogecoin in the manner of a simplified payment verification (SPV) verifiable inside an Ethereum smart contract (more details see below). We will also mention other important aspects when bridging Dogecoin to Ethereum, and discuss two alternatives for batching block information. The main focus of this post is set to the proof of a correct PoW for 1 block header exemplifying it with the Groth16 zk proof system and estimating the computational effort using the circom library.

Background & Related Work on zk-Based Bridges

A zk-based relaying bridge is best understood when we first forget about the zk proofs. A relaying bridge design aims at validating the Dogecoin consensus inside Ethereum. To do so, relayers send every block header to an Ethereum smart contract which verifies that the PoW was done, i.e. that the block header hashes to a value lower than the current target value. This approach assumes that it is economically infeasible to build a longer chain than the one of the honest miners, and that at least one honest relayer is actively sending the most recent blocks.

The major problem of this approach relies in implementing the SCRYPT hash function used in Dogecoin for the consensus, which is a memory-hard hash function that is extremely costly to run inside the EVM. High computational costs, large calldata, and huge storage costs make this approach infeasible. The essence of using zk proofs is to replace this computational burden by off-loading the heavy computation and batching several blocks into one zk proof which only requires a succinct on-chain validation.

Once we have valid block headers in Ethereum, recall that we can make use of the simplified payment verification (SPV) idea: since each block header contains the Merkle root of all transactions of that block, we can from there prove with certainty the existence of every transaction in this block via a Merkle proof — witnessing the existence of a Doge transaction inside Ethereum.

But what are zk proofs? Well, we won’t explain this topic in all its amplitude. There are many places to learn about them (for example here is a source with many useful links and here you can make your own first SNARK proof). In a nutshell, zk proof systems consist of three algorithms (or two if the proof system is transparent, i.e. one without a trusted setup such as STARKs):

1. Key Generation:

• Input: the program for which we want to prove the correctness of the result (in form of an arithmetic circuit C, or something equivalent) & “randomness” (here enters the trusted setup — STARKS omit this entire step).
• Output: proving key pk and verifying key vk.

2. Prover:

• Input: public input data x for circuit C, private input data w for circuit C, proving key pk.
• Output: proof of the statement for public input x and private input w.

3. Verifier:

• Input: public data x, proof , verifying key vk.
• Output: Boolean true or false, i.e. if proof is correct or false implying that the prover knows or doesn’t know a private input such that the statement holds and is correct!

Let’s take our use case as an example of a zk proof: PoW. In this case, the statement we want prove to be correct is that the SCRYPT hash of a block header is smaller than a target value, i.e. “SCRYPT(block header) < target”. For the key generation the arithmetic circuit C (or other arithmetizations such AIRs) that represents the program is the SCRYPT hash function and the just mentioned inequality. The prover runs the Prover algorithm with input block header and target as well as the proving key to generate a proof affirming that she knows the public input block header (everyone can see it, we don’t bother about privacy here, so no private input) which correctly satisfies the condition “SCRYPT(block header) < target”. The verifier uses the verifying key, the public input block header, and when the algorithm outputs true, she can be sure that this block header hashes to a value which is smaller than the target without calculating the computationally expensive SCRYPT hash nor doing the inequality check, but “just” verifying the proof. This way, we offload the hard work executed by the prover to the off-chain component and use only the lightweight proof verification for the on-chain part by running the verifier algorithm inside the smart contract.

Related work: The first work on this topic with focus on the Doge-Ethereum bridge was done by using Bullet-Proofs and Truebit’s challenge response game. An early complete implementation of this idea ([1]) used superblocks to further reduce costs. In [2] an iteration of this line of work is described, but all approaches make use of economic collateral. The work described in [3] uses zk SNARKs to bridge Bitcoin to Ethereum purely relying on zk proofs. This approach is the basis of one of our approaches outlined here, adapted to the Doge-Ethereum context.

Things to Accomplish & Challenges

As already said, the verifiability of the correctness of the SCRYPT hash function is essential for the PoW proof. The SCRYPT hash function generates and makes use of a long random vector (about 128 KB) which becomes split in small pieces (128 Bytes) which are accessed randomly, and are the input for Salsa20/8 (see here). So we must handle and construct an arithmetic circuit representing the xor operations, Salsa’s add-rotate-xor operations, as well as the storage of the random vector. To make the circuit as small as possible, we will use pre-computations which can be done beforehand even outside the circuit.

But there are some more non-trivial aspects to have in mind:

1. Dogecoin uses Merge Mining with Litecoin: Dogecoin’s block header is similar to the Bitcoin block header format, but also contains merge mining data, i.e., a Litecoin block header with the Dogecoin block hash in the Litecoin coinbase tx and a partial Merkle tree to prove inclusion of this coinbase tx. This causes different ‘statements’ (or programs) and input sizes as the Merkle trees may be of different depths. The challenge is due to the fact that circuits have to consume fixed input sizes.
2. Dogecoin uses the DigiShield algorithm to adjust the target difficulty after each new block (as opposed to Bitcoin where difficulty becomes adjusted after every 2016 blocks). The calculation involves simple arithmetic operations which are easy to realize within an arithmetic circuit, but all data has to be available, especially critical when using tricks to batch block headers and storing only every x block headers on-chain.
3. Beyond the PoW validation, the bridge must also validate the correct hash chain of the block headers. Dogecoin uses for chaining the block headers SHA256d for which zk proofs already exist. There must be a mechanism in place to treat possible forks, but this is not related to zk proofs.
4. Storing and validating all block headers would make a heavy use of memory inside the EVM and would be a more than necessary computational effort. To reduce costs, the bridge should make use of batching several block headers and send only the last block header of the batch to the smart contract. We will consider two possible approaches to achieve this.

Solution for PoW: Abstract Concept

The program description

Let’s describe the program we have to translate into an arithmetic circuit (“arithmetization”). As mentioned earlier, the program for the PoW is basically evaluating the SCRYPT hash function for an input a. SCRYPT has several parameters to choose which we don’t get into here. Just for those who want to know, in Doge they are chosen as follows: N=1024, r=1, p=1.

Roughly, what the algorithm does is this:

A. B <- PBKDF_HMAC256(passphrase, salt, 1, 128) (PBKDF is a password-based key derivation function)

B. ROMIX(B, 1024):

1. X <- B
   for i in 1023:
   V_i <- X
   X <- BlockMix(X)
   Long Random Vector V_0||V_1|| …. || V_1023; V_i 128 bytes long

2. j <- Integrify(X) mod 1024
X <- BlockMix(X xor V_j)
return X (“EXPENSIVE SALT”)

C. Final Step: hash = PBKDF_HMAC256(passphrase, EXPENSIVE SALT, 1, Desired KeyLength)

We focus in the last section on the BlockMix used in the above code to roughly estimate the circuit complexity. The algorithm for block mixing is:

How would this translate into a zk proof statement?

ZK Proof Statement
The off-chain program runs the SCRYPT hash function (in an arithmetic circuit), but we would allow some pre-computations to make the circuit size smaller. In particular, we assume that the long random vector is already computed, and that also the access pattern is known in advance by the prover. Basically:

• Prover: Pre-computes the random vector and the memory access pattern to avoid additional expensive xor operations. The program starts with step B.2 only executing the block mixing as the access pattern is pre-computed, too. It must also compute the final step, i.e. HMAC_SHA256.
  - Input: public input: block header, block header hash (or in fact the target), private input: long random vector, random access pattern.
  - Output: proof , the value of SCRYPT (or boolean when we work with target).
• Verifier:
  - Input: vk, proof, block header, block header hash.
  - Output: boolean (“0” if prover 1 was run correctly).

What is roughly the complexity of this program? In summary:

• 1024 times xor: X xor V_j
• 1024 Salsa20/8
• final step: HMAC_SHA256
• (not mentioning to go from bits to finite field elements and the necessary range proofs)

We discuss further the complexity estimation in the last section. Note that the verifier needs to receive as call-data the proof, the block header and its hash value (or, more precisely, the target), and the verifying key (of Groth16).

Batches

The reason to use batches is to reduce the on-chain computational effort and storage size. We describe two possible ways, the first is described in [3] and the second relies on recursive proofs.

Approach 1: In the first approach the idea is to make use of the private input to reduce the on-chain complexity. Again, it is not about privacy, but as you can see in the description of the verifier algorithm, private inputs are only used by the prover in the off-chain component for proof generation (which should be efficient, too, but it’s not the most critical bottleneck), but on-chain validation requires only the public input. Since the verifier algorithm is run on-chain, the general philosophy is to use the minimum data necessary as the public data, and leave the rest as the private data. This minimizes the computational overhead (less calldata) & storage in the relay contract. Instead of validating on-chain one block header hx at a time, we validate a batch bN=(hx, … hx+N-1) of N block headers and store only the last one hx+N-1 on-chain in the contract. The block headers hx, … hx+N-2 are put as private inputs, and do not need to be sent on-chain!

Prover (Off-chain): “Receives a batch bN of block headers and the last block of the previous batch, and validates the PoW (scrypt hash) as well as the correctness of the hash chain.

• Input: bk,N=(hk,x, … hk,x+N-1), last block hk-1,x+N-1 of the previous batch, and proving key pk.
• Output: proof

Verifier: Validates the correctness of the batch of block headers bN=(hx, … hx+N-1).

• Input: last block header hk,x+N-1 of current batch and last block header hk-1,x+N-1 of previous batch bk-1,N , and verifying key vk.
• Output: 0 or 1 depending on whether the batch is valid or not.

The verifier runs inside the smart contract, and depending on the relation between circuit size — which might grow with the number of blocks in the batch — and verification run time, we get something which is feasible to verify on-chain (see below).

Approach 2: The second approach makes use of proof recursion. An excellent primer on recursive proofs can be found here. Again, we restrict to the basic concept and how to apply it to our use case. In proof recursion, proofs not only prove the current statement, but also the validity of a previous proof of the same statement whose result is used as input for the current step (“proof-carrying data”). To achieve this, both the current statement and the verification of the previous proof must run in the verifying algorithm. Applied to our case: with only one proof at block height n we can prove the validity of the proof of the PoW at height n-1 plus the PoW at block height n. If we iterate this (proof of previous proof of previous proof …) we can validate a batch of blocks (say recursion to n-m) with a single proof while keeping the proof size and the verification time independent of the batch size. Additionally, assume various relayers providing proofs for different periods, then these can be aggregated and validity can be put in one proof. Recursion is quite a recent topic (requires good paris of elliptic curves) and finding EVM compatible code easy to deploy is not straight-forward.

Proof batches without recursion could be simpler to start with …

ZK Proof Systems

There are many proof systems, and our comparison is not claiming to be exhaustive. Nevertheless, it should give a good intuition for performance aspects, EVM compatibility, and the possibility of using it in recursions. The candidates we looked at a bit closer were the following:

• Groth16 and Plonk (and its successors)
• Halo2 from the Zcash team. Here is a good source for explanation.
• STARKs from StarkWare with their Cairo language for ethSTARK .
• Plonky2 from Polygon.

In the following table we summarize some facts about those zk proof systems to see their strengths and weaker aspects. The number N roughly describe the complexity of the circuit in terms of the number of constraints (or multiplication gates). Without defining this term precisely, the importance is the relation between the circuit size and the algorithms, especially the verifier algorithm and proof size. In the case of AIR based STARKs the constraints are different from the ones of circuits, but we don’t get into the subtleties here.

Evaluation / Next Steps

In our first attempt we focused on the first approach using Groth 16 (and also Plonk) leaving batches aside. Using the circom library we started implementing the add-rotate-xor of the Salsa20/8 hash function. Using the curve BN-128 we have:

Assuming the pre-computation of the long random vector and the access pattern, our initial code using circom would suggest a minimum of 177846 constraints.

This is roughly 6 times larger than SHA256_2. Therefore, the prover would require more computational effort in this scale compared to SHA256_2 (well, at least). Nevertheless, as the verifier in Groth16 is constant in circuit size, and since the input is of double size compared to the one used in [3] due to merge mining, we would expect roughly a doubled gas cost of 194,000 gas as consumed in their relay contract.

Above we say “at least” as we did not consider the memory cost for the 128 KB long random vector nor access pattern costs. After approving feasibility, the next step would be to tackle batches, compare costs with proof systems without setups, and address the challenges mentioned earlier!

References

[1] I. Bejarano, C. Juattos, O. Guindzberg: Dogethereum Alpha Release.

[2] J. Teutsch, M. Straka, and D. Boneh: Retrofitting a two-way peg between blockchains, 2019.

[3] M. Westerkamp, J. Eberhardt: zkRelay: Facilitating Sidechains using zkSNARK-based Chain-Relays. 2020.

Research by Hartwig Mayer in collaboration with Martin Scheerer.

Contact: zkp.dochdoch at gmail dot com.