Relic Protocol on Twitter: "🚀 Relic v2 is now live on Ethereum and zkSync Era! 🚀Discover the full potential of Ethereum's historical state with lightning-fast transactions and cost-effective gas fees on zkSync Era.Try out Relic v2 at https://t.co/12D72qro0K and mint an Ethereum birth certificate NFT. / Twitter"

🚀 Relic v2 is now live on Ethereum and zkSync Era! 🚀Discover the full potential of Ethereum's historical state with lightning-fast transactions and cost-effective gas fees on zkSync Era.Try out Relic v2 at https://t.co/12D72qro0K and mint an Ethereum birth certificate NFT.

Activity on L2s has skyrocketed in recent months, as both users and developers are seeking fast transactions and low fees. The zkSync Era mainnet launched in March 2023, and currently supports the most user activity among the Ethereum L2s. Relic trustlessly bridges all of Ethereum’s data to zkSync Era, supporting all of Relic’s L1 features with dramatically lower fees.

The combination of trustless historical data access and negligible transaction fees creates completely new possibilities, even for applications on the Ethereum L1. For example, it is now practical to implement fully on-chain snapshot voting, where voting takes place on zkSync Era based on a snapshot of Ethereum data from Relic, and the results are bridged back to Ethereum to execute the governance decision. Similarly, any other Ethereum state proofs which are too expensive to perform on L1 can now be done cheaply on zkSync Era before trustlessly bridging the results back for use on Ethereum.

We are excited to partner with the developer community and explore the many novel uses for Ethereum data on zkSync Era.

Relic V2 Deployed on zkSync Era was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

Block Hash Oracle

In order to verifiably access Ethereum state, you first need to know the hash of the block containing the data. Unfortunately, the EVM only exposes the previous 256 blockhashes, so trustlessly accessing older data on-chain requires some magic. Both Relic and Axiom use ZK-SNARKs to verifiably compress the block hash history into Merkle trees, allowing smart contracts to efficiently verify block hashes all the way back to genesis. Our ZK-circuit design for this process was documented in an earlier post, and Axiom’s design is quite similar.

State Proof Verification

Once you have a verified block hash, the state inside the block can be verified via Merkle-Patricia-Trie (MPT) proofs. The primary difference between Relic and Axiom is in how these state proofs are verified. Relic verifies the MPT proofs directly on-chain via a highly optimized Solidity verifier, while Axiom verifies the MPT proofs inside of a ZK-SNARK. While Relic also has ZK-circuits for MPT verification, they are not yet used in production, due to the inherent tradeoffs:

1. Gas costs: SNARKs are expensive to verify on-chain (~500k gas), while well-optimized EVM code can verify MPT proofs for much cheaper (~100k on average). However, a SNARK verifier can theoretically verify multiple MPT proofs simultaneously for the same flat gas cost, while the native MPT verifier’s cost multiplies with each fact.
2. Proof times: SNARK proofs can take minutes to generate, while fetching a raw MPT proof from an archive node takes less than a second.

We believe most use-cases will require only a few state proofs, and thus will be cheaper and faster using on-chain MPT verification rather than on-chain SNARK verification. See the table at the end of this post for a direct comparison of gas costs and proof times for each of the demo applications.

If a use case requires access to lots of historical state, aggregating the state verifications into a single SNARK will likely reduce overall gas costs. In these cases, the long proving times may be worth the gas savings. In fact, Relic’s ephemeral facts system unlocks the possibility of aggregating state proofs from different applications into a single SNARK, potentially reducing gas costs for even the most simple use-cases. Expect more details on this soon!

Although ZK-SNARKs also have privacy preserving properties, this is not relevant for most use cases. If a user needs to associate their public address with a fact that they prove, then they will not benefit from doing their proof “in secret”. It is possible that some specialized use cases may benefit from privacy preserving proofs, but this will also require that the ZK-proofs are generated by the user rather than a third-party prover.

dApp Integrations

Another major benefit to on-chain MPT verification is that integrations become much simpler. Relic has open SDKs, allowing any Ethereum developer to tap into historical state in their applications. Axiom’s approach thus far requires building a custom low-level ZK-circuits for each use-case, which are both difficult to develop and difficult to reason about.

Every Relic demo application is written in Solidity and Typescript using the public Relic SDKs, demonstrating that any Ethereum developer can build these powerful applications without needing to write complex ZK-circuits.

Relic’s smart contracts were designed with both immutability and extensibility in mind. Relic’s core smart contract is the Reliquary (a container for Relics), which serves as both a central fact registry and an extensible prover registry. The Reliquary code is immutable, but allows Relic governance to add new fact proving modules with efficiency, usability, or security improvements. Every fact stored in the Reliquary is immutably tagged with its prover, allowing other dApps to choose the level of extensibility that fits their use case, whether it be full immutability or full forward-compatibility.

Currently, Axiom requires each dApp to be responsible for deciding which Axiom contracts store and prove each piece of data. Furthermore, there is currently no unified interface for proving and accessing data, which requires ad-hoc handling by on-chain applications.

Scaling Approach

One large benefit of performing state verification in ZK-circuits is that it enables additional verifiable computation to be performed on the data before bringing it on chain. To this end, Axiom promises to enable applications which are otherwise too expensive to run on-chain.

However, expensive computations are not only expensive on-chain; they are also expensive to prove using ZK-circuits. This expense manifests as latency (high proving times) and server costs. The upside is that these costs are borne by only one party, rather than every Ethereum node. The downside is that it reintroduces centralization risks. Correctly written ZK-circuits ensure computational integrity, but they do not ensure liveness or censorship-resistance. These properties can be achieved with a decentralized set of incentivized provers, but this is a difficult problem which even many ZK-rollups have yet to fully solve.

Relic’s approach to scaling verifiable compute is simple: don’t reinvent the wheel. Thanks to the hard work of many teams (zkSync, Polygon, Scroll, Consensys, Kakarot, etc), various types of ZK-EVMs are now a reality. As a result, Relic’s existing EVM state verification can be seamlessly composed with any EVM-compilable language (e.g., Solidity) for arbitrary verifiable computation. This approach both simplifies developer integrations and enables tapping into existing decentralized proving networks (for instance, those powering ZK-rollups).

It’s clear that ZK-SNARKs are crucial to scaling verifiable computation, and Relic intends to build on the most Ethereum-aligned and developer-friendly ZK tech: ZK-EVMs.

Demo App Comparison

Note: Relic’s exact gas costs vary slightly from proof-to-proof, so these values are approximate. Each row is an apples-to-apples cost comparison of performing the same proof, using the default values from the Axiom demo page where possible.

If you’d like to try out the demo apps, you can find Relic’s demos here and Axiom’s demos here. The source code for the Relic demos can be found on GitHub.

Birth Certificate / Account Age

Axiom’s Account Age demo is comparable to Relic’s Birth Certificate app, in that they both use state proofs to prove an Ethereum account’s age on-chain. However, Relic’s app also mints the user a fully on-chain Soulbound Token to show off. Despite the additional functionality, Relic’s app still uses substantially less gas and generates the proof in less than two seconds.

UniV2 TWAP

Uniswap V2 was designed with time-weighted average price (TWAP) oracles in mind. To compute the TWAP of any asset pair between any two blocks, you only need to access the pair’s on-chain state at each block. Before Relic and Axiom, this was difficult to do on-chain because accessing old contract state was prohibitively expensive. Now, we can build completely trustless on-chain TWAP oracles with very reasonable costs!

This is the most complex of the demo apps, as it verifies multiple storage slots at each block. Despite this complexity, Relic’s optimized MPT verification still uses less gas for nearly every TWAP calculation, including popular trading pairs like ETH / USDC.

RANDAO

This simple demo app allows trustless access to the RANDAO value from any post-merge Ethereum block. Note that RANDAO is slightly biasable by Ethereum block proposers, so this value should not be used as a perfectly fair random value. Paradigm recently published a randomness beacon design combining RANDAO with VDFs to produce fully unbiasable and trustless random data on-chain.

For this demo, both Relic and Axiom are low-cost, because RANDAO values are stored directly in Ethereum block headers, so no MPT proof verification is needed.

Custom (storage slots)

Relic supports proving many types of historical state, including log emissions, storage slots, and more! If multiple storage slots from the same contract and block are required, Relic’s MultiStorageSlotProver gives an efficient way to batch prove storage values. Axiom’s “Custom” demo gives a similar capability (currently limited to 10 slots), but for a fixed proof verification cost (the only variable cost is due to on-chain storage). As a result, Axiom’s demo is cheaper when simultaneously proving more than 6 slots from the same account.

Conclusion

The biggest difference between Relic and Axiom is how state proofs are verified: Axiom verifies all state proofs in ZK-SNARKs, while Relic uses both ZK-SNARKs and on-chain MPT verification to minimize the high costs and latency of ZK proving. Developers can integrate with Relic using Solidity and Typescript (rather than through custom ZK-circuits), and ZK-EVMs allow for substantially more complex apps to be built on Relic while remaining entirely trustless.

If you are interested in building a history-powered dApp, check out our docs and feel free to reach out to the Relic team on Discord with any questions or feature requests!

Relic vs Axiom: A Technical Comparison was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

How it works

Rounds

Daily Gas Floor (DGF) divides time into rounds consisting of 8192 blocks (roughly 27 hours), where its price feed contains the minimum base fee from each round. During a round, DGF discovers the price from the previous round in a decentralized way (described below). After this full round of discovery, the price is finalized and made available.

Operation and Incentives

DGF discovers prices using a combination of Relic’s historical block header proofs and economic incentives. This relies on two open and permissionless roles:

• Submitters submit block headers which contain the submitter’s claimed minimum base fee. DGF validated the block header using Relic, and tracks the minimum submission. After the end of the round, the first submitter of the minimum price can claim a reward.
• Depositors deposit ETH to fund the rewards, incentivizing price submission. Depositors are charged for the rewards in a round-robin fashion, and have the privileged ability to query the price feed, as long as their balance remains nonzero.

The submission reward scales up linearly throughout the round with the goal of finding a fair reward surpassing the current cost of submission. Note that submission rewards are MEV, and a competitive set of submitters should ensure that rewards are minimal.

For gas efficiency, depositors are stored using a circular linked list, allowing for cheap insertion and deletion while also preserving the round-robin ordering. New depositors are added to the front of the queue, favoring earlier depositors.

Why is Relic needed?

The EVM’s history access is limited to the last 256 block hashes. Efficiently accessing data from older blocks is a difficult problem, but is exactly what Relic’s block hash oracle solves. Relic uses zk-SNARKs to reduce long hash chains to compact Merkle trees, allowing applications such as DGF to securely access historical blocks with very little gas overhead.

Concrete Example

Suppose Alice and Bob are two parties who want to query DGF’s price feed on-chain, so Alice deposits 1 ETH and Bob deposits 2 ETH. Because they will be charged for rewards in a round-robin, Bob’s deposit should last roughly twice as long as Alice’s before needing to be topped up again.

Now suppose Xavier and Yolande are each acting as submitters, hoping to claim the rewards each round. Even if Xavier could profit from submitting the incorrect price (i.e. not the minimum from the round), it only takes one honest submitter (Yolande) to make Xavier’s submission be wasted gas. So, Xavier and Yolande are both incentivized to submit the correct price and will race to do so.

However, suppose that gas prices are currently very high, so it would cost .02 ETH to submit the price while DGF’s minimum reward is only .01 ETH. Throughout the round, DGF’s reward for the round will gradually scale up to to some maximum (say, .1 ETH). As soon as this reward passes the current cost of submission, Yolande submits the block header and locks in the reward. DGF charges a depositor this reward, reducing Bob’s balance and locking up the reward until Yolande decides to claim it. Once the round is finalized, Alice and Bob may query the settled price.

In practice, Alice and Bob would likely be DeFi protocols, while Xavier and Yolande would likely be MEV bots.

For more details, check out the code and accompanying documentation, or join our Discord to discuss!

Use cases

The primary use case for such an oracle is derivative settlement. A gas price derivative used to hedge against prolonged gas price spikes could be valuable to any party that uses gas on a regular basis, such as rollup sequencers or oracle nodes.

It is sometimes thought that high volatility makes gas price derivatives impractical. However, the minimum base fee each round is substantially less volatile than the average:

Comparison to other solutions

The closest alternative is Chainlink’s fast gas oracle. This oracle has different goals — its price feed is much higher throughput, but is highly volatile and relies on trusted oracle nodes for relaying.

Limitations and Future work

Manipulation

One limitation to any gas price oracle is potential for price manipulation. For our case, some block proposers may have the opportunity to produce artificially empty blocks, which may reduce the minimum base fee below what the natural block-space demand would produce. EIP-1559 specifies that completely empty blocks reduce the base fee by only 12.5%, so substantially impacting the price requires controller many adjacent proposers. Producing empty blocks also comes at the cost of priority fees and MEV.

Variations

Because Relic gives provable access to historical account balances, contract storage, and log emissions, this design can be easily adapted to create price oracles for any on-chain data. This includes AMM prices, NFT prices, and more!

Other Limitations

There are a few known limitations to the current design:

1. The described design only supports price functions where candidate values are pairwise comparable (such as `min` or `max`), i.e. given any two candidate prices, we can always eliminate one of them. Functions such as `mean` or `median` require more context to compute, and would likely be more practical to compute off-chain and prove on-chain with a zk-SNARK.
2. Charging depositors in a round-robin has low amortized cost and is very gas-efficient, but may result in an unfair distribution of charges in the short-term if some rounds are especially expensive. Finding ways to more fairly distribute these costs (while keeping gas costs low) is left as future work.
3. Submission reward bounds are hard-coded and don’t scale arbitrarily high, which could theoretically affect liveness. In practice, the current maximum reward should cover gas prices well above 500 gwei. Fully addressing this issue is difficult, as depositors may assign vastly different values to liveness on any given round.

Disclaimer

This code is meant as a proof-of-concept and is not yet intended for use in production. Feedback or contributions are always welcome! Feel free to get in touch on GitHub or on our Discord.

Building Trustless Price Oracles was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

This example will go through how to build an airdrop to trustlessly distribute our new airdrop token as a 1:1 match for any tokens the user held in block 15,000,000. Our code will be split up into the on-chain component and the front end that users can easily interact with.

We won’t go over every line of the source, but we’ll at least cover the main aspects of how things are done so it should be easy to modify for your own needs. You can also see the finished example in action.

Smart Contract

While the code is available online, we’ll go into it step by step here.

In Solidity we’ll import a few things provided by Relic:

• interfaces/IReliquary.sol provides the interface to the Reliquary, which stores the proven historical state data we want to access
• lib/Storage.sol provides helpers for interfacing with contract storage slots
• lib/FactSigs.sol provides the signatures we must pass to the Reliquary to indicate what data we’re trying to verify

And since we’re making an airdrop ERC-20 token, we’ll just import the ERC-20 template from OpenZeppelin.

/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.12;

import "@openzeppelin/contracts/token/ERC20/ERC20.sol";
import "@relicprotocol/contracts/lib/FactSigs.sol";
import "@relicprotocol/contracts/lib/Storage.sol";
import "@relicprotocol/contracts/interfaces/IReliquary.sol";

contract Token is ERC20 {
}

Now the first thing we need to do is figure out the storage slot structure for our token. Assuming a pretty standard ERC-20 token, this is likely just a matter of determining the storage slot offset for something like a balance map of owners to their tokens. Notably, it doesn’t matter if this is public or private, either way it’s still on the blockchain!

For most token type contracts to figure out the offset, you can use this super simple tool. If the contract has a more complicated structure, you may need to manually inspect it to determine how to do this. This guide can help in that situation.

For USDT, we just enter the address of USDT and a current token holder, and we get an offset of 2.

We can stick that in a simple helper function that is public in case users of our contract want to verify any of the internal calculations.

function slotForUSDTBalance(address who) public pure returns (bytes32) {
    return Storage.mapElemSlot(
        bytes32(uint(2)),
        bytes32(uint256(uint160(who)))
    );
}

With that in hand, we can start coding our smart contract. We can simply ask Relic for the value at that storage slot for the block we care about and interpret it as a uint256. Because we are querying a storage slot value, we use the storageSlotFactSig to create our query.

We will use then query the Reliquary with the verifyFactNoFee function.

(
    bool exists, uint64 version, bytes memory data
) = reliquary.verifyFactNoFee(
    USDT,
    FactSigs.storageSlotFactSig(
        slotForUSDTBalance(who),
        blockNum
    )
);

We care here about the exists (to ensure someone has proven this storage slot) and the data (to see what was present in the storage slot). The version field can be used if we care about which internal prover Relic used to prove the fact, but that doesn’t really matter here.

Assuming the value exists, we can parse the dataeasily using

require(exists, "storage proof missing");
uint priorUSDTBalance = Storage.parseUint256(data);

That’s basically all we need — just a few pieces of glue and sanity checks remain. We need to ensure once people claim their tokens, they can’t repeat multiple times. This just requires a simple map like mapping(address => bool) public claimed to easily track. We can stick everything together into a mint function and call the OpenZeppelin _mintfunction with the priorUSDTBalance to actually transfer the amount to our user.

function mint(address who) external {
    require(claimed[who] == false, "already claimed");

    (bool exists, , bytes memory data) = reliquary.verifyFactNoFee(
        USDT,
        FactSigs.storageSlotFactSig(
            slotForUSDTBalance(who),
            blockNum
        )
    );

    require(exists, "storage proof missing");
    claimed[who] = true;

    uint priorUSDTBalance = Storage.parseUint256(data);
    _mint(who, priorUSDTBalance);
}

Then a few other fields to set up and establish the address for USDT and the reliquary, as well as setting the block to use for our claim window snapshot. Since we’re using USDT, we should also set decimals in our contract to return 6, to match the native USDT value.

That’s pretty much it! You can check out the full code here.

We also need to deploy our contract, being sure to pass in addresses for the Reliquary and USDT, as well as setting which block we want to use for our checks.

Front End

Once again feel free to skip ahead to the finished source if you wish.

To make things easier for users, we also need a front end they can use to interact with this. The main necessary feature here is the ability for users to prove their USDT claims and mint their airdrop without needing to worry about the details.

Once again, Relic SDKs make this simple. We’ll use ethers as well to easily interact with Ethereum.

import * as ethers from "ethers";
import { RelicClient, utils } from "@relicprotocol/client";

We’ll need to reference our addresses for USDT and our newly deployed Airdrop contract. We’ll also want a multicall contract for a bit later on.

const addresses = {
    ADUSDT: "0xc2Ed14521e009FDe80FC610375769E0C292FC12d",
    USDT: "0xdAC17F958D2ee523a2206206994597C13D831ec7",
    MAKERDAOMULTICALL: "0xeefBa1e63905eF1D7ACbA5a8513c70307C1cE441",
};

Creating the actual proof is pretty simple:

const client = await RelicClient.fromProvider(provider.value);
const prover = await client.storageSlotProver();
const storageSlot = utils.mapElemSlot(
    2,           // The slot we found earlier
    userAddress, // The customer's wallet address
);

const proveTx = await prover.prove(
    BLOCK,
    addresses.USDT,
    storageSlot,
);

This will use Relic’s Web2 API to generate a proof of the specified storage slot in the USDT contract at the specified block. Note that while this uses a Web2 endpoint controlled by Relic for convenience, the actual proof is verified on-chain — so there is no room for manipulation by a centralized authority. It is also possible to construct the same proof yourself with an Ethereum archive node, it’s just more tedious.

Before we issue this proof on chain, we can also aggregate it with our actual mint transaction. This way users don’t have to approve (and pay for) two separate transactions.

const ADUSDT = new ethers.Contract(addresses.ADUSDT, [
    "function mint(address who) public"
]);

const Multicall = new ethers.Contract(addresses.MAKERDAOMULTICALL, [
    "function aggregate(tuple(address target, bytes callData)[] memory calls) public returns (uint256 blockNumber, bytes[] memory returnData)"
]);

const mintTx = await adusdt.populateTransaction.mint(userAddress);

const multicall = Multicall.connect(signer.value);

proveAndMintTx = [
    { target: proveTx.to, callData: proveTx.data },
    { target: mintTx.to, callData: mintTx.data },
]

const res = await multicall.aggregate(proveAndMintTx);
await res.wait();

Keep in mind here the mint function on chain only needs to know the address of the user. The actual value of the tokens distributed to them is entirely dependent on what they proved in the previous transaction.

There’s quite a bit still needed to turn this into a usable web front end, but this handles the basics for issuing a proof to the Reliquary.

A few things that would help user friendliness are:

• stopping the user if they have already claimed their tokens (the example code handles this)
• showing what the results of a proof and mint will be before doing it on chain (the example code handles this)
• only minting and not proving if the user has already proven the slot

The full source adds more overhead to use Vue and interact with web wallets cleanly. However the main body of the code is straightforward.

Modifications

While this example was straight-forward, one can easily add slight changes to better suit their needs.

Block Range

While our airdrop only handled the use case of token holders from a single block, you may wish to extend this to a wider range of blocks. Luckily, this is quite simple! Users will be incentivized to pick the block for themselves with the largest balance, so we just need to update our code to check the low and high end of the range, and then modify the mint function to also accept the block number for which a user is claiming their airdrop.

Payout Structure

This example uses a 1:1 payout format, meaning each USDT held gives one airdrop token. However, this could trivially be modified. For example, we may wish to scale the rewards to benefit smaller holders, so we can take the square root of the old balance before minting. Or we can reward all holders equally, so we simply allow a user to mint one token regardless of their prior holdings.

import "@openzeppelin/contracts/utils/math/Math.sol";

...

_mint(who, Math.sqrt(priorUSDTBalance));  // sqrt of balance

Any deterministic payout structure can easily be added with just a simple modification to our mint function, such as this square root modification. And importantly, as the payout structure must be committed to the blockchain, it is completely transparent and decentralized. If the airdrop creator attempted to pay out more to their friends, the logic for that exception would need to be committed.

Gas Optimizations

There are two main gas optimizations that the Relic team plans to implement that should decrease the cost of these proofs. The first is to allow projects to commit intermediate values of the proof for later use. For example, the account state Merkle Root for the USDT account at block 15,000,000 could be committed and re-used by all users of this example airdrop, cutting down on gas significantly.

Fortunately, this change will not require modifications to the code. This change can be done transparently by Relic and update the API code when completed to make the proveTx use the most efficient method possible.

The second main optimization is to not require the proven storage slot value be stored on-chain to access it. Because we are doing our prove and mint operations in the same transaction, we may be able to optimize some of those costs. However, the airdrop contract will need to be modified to take advantage of this optimization.

Eligibility Criteria

The criteria for this airdrop were very simple, just based on owning a single token. However, there are a number of other criteria that one may wish to use.

Any other type of activity that can be viewed from a storage slot can easily be worked into this same format — just change around which storage slot is being proven and you’re good to go.

Other types of activity are currently in-the-works for Relic, such as transaction receipts and log events. (Follow us on Twitter or Discord to stay up-to-date for when these are available in the SDK). With these criteria such as “all users that interacted with a certain contract” will be as simple to use as the storage slot check.

For combining multiple eligibility criteria, things are a bit more complicated. The main difficulty is simply creating a simple way for users to select the criteria that apply to them. Chaining together multiple facts from Relic is not difficult to do in a smart contract, but doing so may not be gas efficient.

Wrap Up

Overall, the code required to make this example work is quite small! Most of the complexity simply arises from making a web front end that is easy to use. Using Relic to verify facts on chain is only a couple lines of code, and generating the proofs in Javascript is similar.

Although this is already a very powerful primitive for on chain applications, Relic is under heavy development to add more features. If you want to stay in touch for updates, suggest new features, ask questions, or just hang out, join our Discord or follow us on Twitter.

And as a reminder, you can view the source code for this (and other!) examples on our Github. Check back regularly as more projects are added to give an idea of what can be built with Relic.

Better Airdrops (Part II-the Details) was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

Airdrops can be broken down into three separate stages:

1. Determining eligible users
2. Publishing eligible users on-chain
3. Token transfer

Normally airdrops are totally new tokens, so there is also an implicit step 0 to create the token contract. That’s a whole separate discussion though, and doesn’t change based on the particular airdrop strategy, so we’ll not worry too much about that piece.

Now let’s get a bit deeper into the details for how to implement the rest.

Eligibility

There are a number of criteria one may want to use for determining who is eligible for an airdrop. Some airdrops are simply sent to a handful of known individuals (influencers, investors, etc.), but when it comes to dApps, normally the goal is to send tokens to users. To determine who was a user, the most common criteria are based on possessing tokens in a time window, or interacting with a contract/app in a time window.

Actually turning that idea into a list of users can get tricky. Let’s imagine we want to determine who held a common token (e.g. USDT), at a specific block (e.g. 15,000,000). If we search online for solutions to this problem, there are two general solutions:

• Write a program to use an archive node to go through all blocks up to 15,000,000 and check who has interacted with USDT. Either track the balances, or simulate a balanceOfcall for each of the potential holders.
• Find a blockchain analytics company online that has an API you can use for this query (probably for a small fee). Depending on the data you get from the API, you may still need to write a bit of code.

Checking interactions within a time window is likely much simpler. Assuming the smart contract emits events when users interact (such as Transfer events for our USDT example), we can just scan the eligibility range for those events. Again, this will require using an API or archive node and some code. However, this will be a bit simpler to implement compared to finding all holders — perhaps why interactions in a time window are a common criteria for airdrops today.

The choice between these two eligibility criteria mostly depends on the project. For something with an ERC-20 or ERC-721 token, it probably makes sense to use token holders in a range — a long time hodler may not have any transfers after their early purchases, but may still be an active user. For something like a DEX, it may make more sense to base eligibility on interactions, and depending on the circumstances, there may in fact be no other reasonable criteria.

Either way, when determining whether to write the code to handle the eligibility list yourself or using external APIs to assist, the primary concern is correctness: is your code correct, are the APIs returning the correct values, and are your queries fetching the data you expect them to. Hopefully there are some known addresses which should be eligible and some which should not be eligible that can be used to test the results to help gain confidence.

A secondary concern is cost: whether using an archive node or another API service, there may be small fees associated. Luckily these fees are likely to be minor, probably between $10-$100USD.

Bulk Transfer

To handle both publishing eligible users and transferring tokens to them, there are a number of ways to perform “bulk transfers”. The basic idea here is to simply take the list generated in step 1 and send tokens directly.

There are some benefits here: this is conceptually very simple, and users don’t need to do anything to receive their tokens. In some ways this is the epitome of airdrops, but it is not without drawbacks.

The main issue is cost. Using our running example of USDT tokens at block 15,000,000 we’d have over four million users to reimburse. In the most optimistic scenario, this would still require setting at least four million storage slots in Ethereum. Each store would cost at least 21,000 gas, which at 20 Gwei gas prices leads to at least 1680 ETH required for the airdrop — a little over $2.5 million USD right now.

There are actually some additional costs here too. This can’t fit in a single transaction, so will need to be split across several. There are also other operations aside from the storage write that will increase the gas usage.

Some commercial services offer bulk transfers as a service: you can enter a list of addresses and they will deal with the on-chain transfer. However, this adds even greater costs. These services vary in price but tend to be around 15,000 transfers for 1 ETH which would give an additional 266 ETH or about $400,000 USD.

It is hopefully obvious that there are some pretty fundamental limitations with this approach. While it may seem simple, it is cost prohibitive in most circumstances.

Merkle Tree

Fundamentally, the bulk transfer doesn’t work because storing too much data on-chain is expensive. On the one hand, this is unavoidable. For four million users to receive tokens, there need to be four million storage slots used, which means a lot of gas spent.

However, we can amortize this cost through our users. This has a big advantage too: it’s entirely possible not all of those four million users want to claim their airdrops. For example maybe the value for which they are eligible is too low to be worth it, maybe they lost control to their wallet, or any number of possibilities. In that sense, it’s possible we can shortcut the total amount of gas that needs to be spent.

But how can we do this securely? If we need to only write a small number of values on-chain, how can we still include all eligible user accounts and no one else?

The answer is Merkle Trees! These lovely cryptographic constructions allow a single storage slot containing a Keccak-256 hash to describe all of the accounts we want. For a user to claim their airdrop, they simply have to provide a Merkle Proof that their address was included in the published Merkle Tree. This proof will be relatively short: logarithmic in the number of accounts in the tree.

So the procedure for this looks like:

• build a Merkle Tree of the eligible users
• submit the Merkle Root to the minting contract
• provide front-end for users to build Merkle Proofs of their eligibility
• verify Merkle on-chain and mint tokens

While there are some Solidity libraries to help build the smart contract side of this, it definitely requires more development effort compared to the bulk transfer approach. Additionally, building the tree must be done off-chain, which limits transparency and means a centralized party is responsible for the construction.

It is also possible to extend the Merkle Tree approach to do more than just give an equal amount of tokens to everyone who is eligible. If the Merkle Tree is created as a list of account, eligible_amount tuples, then one can set differing amounts per user easily as well.

Issues

There are a couple shortcomings with the two approaches so far.

The first is the reliance on off-chain calculations to make both of them work. How do we know the airdrop creator did not mess up their list? Or worse, what if they intentionally manipulated the airdrop amounts to benefit themselves or harm others? Once a Merkle Root is committed, or a bulk transfer is complete, it is not possible to rescind it and start over. Users are not involved in the creation of the lists used to generate either solution: they must trust and rely on the protocol creator.

While today there may not be any airdrops victim to this issue, it is difficult to verify. It also goes against the idea of decentralization. In an ideal world, there would be no need to trust the airdrop creator to be honest. Why can’t we simply build a fully decentralized and trustless airdrop?

The next issue is simply that these approaches require a lot of resources: for bulk transfers that is primarily money. For Merkle Tree systems, it requires development effort: one must create a smart contract to verify the Merkle Tree, a user interface to assist in proof generation, and the actual tree must be generated that is compatible with both.

Another Way

The first realization is that creating a Merkle Tree of something like previous token holders is actually redundant — Ethereum already has one! The entire blockchain history is based on storing data in cryptographically secure data structures like Merkle Patricia Tries, and then linking them together with more Keccak hashes in blocks.

Luckily there is also an easy way to use this data on-chain using Relic Protocol. The basic idea is then pretty simple:

• use Relic to prove historic ownership of a token in a block range
• mint tokens to anyone who has such a proof

Luckily this is quite easy to implement thanks to the provided SDKs.

If you want to read more about how to actually implement this, check out our follow-on article with a full walk-through here.

How does this method compare to the Merkle Tree approach? For one, it saves a lot of effort. Developers don’t need to attempt to query full Ethereum nodes to determine who is eligible for how many tokens. The actual Merkle Tree is already built and just waiting to be used!

Using historic state also means there is no centralized or trusted authority. If the airdrop developers wanted to drop more tokens to themselves or prevent some deserving users from claiming their tokens, it would not be possible without publishing the malfeasance in the token contract that anyone could view.

There is one downside though, which is gas usage. Because the proof issued on-chain requires linking it to a historical block, there is a bit of extra overhead compared to a pure Merkle Proof. Luckily, that is something the developers of Relic are working on. By caching data from popular blocks (such as the relevant account storage root in the block for an airdrop), the gas costs would be competitive with plain Merkle Proofs.

Wrap Up

There are a number of reasons why an application may want to airdrop tokens to its users. As a developer, there are constant compromises between code complexity, decentralization/transparency, cost, and ease of use. Relic takes the substantial benefits of Merkle Tree based airdrops and extends them, benefiting from the substantial cost reduction over bulk transfers while also increasing decentralization and transparency and making it simpler to code.

If you want to use Relic for your next airdrop (or other dApp), be sure to check out our next post in the series to learn more about the detailed implementation of airdrops with Relic. If you have questions, comments, or just want to stay up to date, join our Discord or follow us on Twitter. For more info for developers, check out our docs, and look over our source and examples on Github!

Better Airdrops was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

Motivation

We’ll first give some motivation for our scaling approach, which we hope has some general lessons about scaling blockchain applications.

Quick Recap of State Proofs

Ethereum block headers contain commitments to the entire state (as of the end of the block). Given a block header, smart contracts can use Merkle-Patricia Trie (MPT) proofs to verify any account data, storage slot, transaction data, or receipt contained in the block.

This is, surprisingly, the easy part of provable historical state access. The hard part is: how can smart contracts check that a given block header is valid? The Ethereum Virtual Machine (EVM) only gives access to the last 256 block hashes, so how can we know if a supposed block header from 10000 blocks ago is valid, and doesn’t actually contain commitments to incorrect data? As described in the last post, the naive solutions to this problem are completely impractical due to the costs of Ethereum storage and calldata. Thankfully, there are better ideas.

Compression: Merkle Trees

First, we drastically reduce the amount of storage required by using Merkle Trees. The idea is to divide the block history into fixed-size chunks, build a Merkle Tree of each chunk’s block hashes, and commit only these Merkle roots on-chain. When we need to verify a block hash on-chain, we provide the Merkle proof that the block hash is at the correct index in the Merkle tree.

For Relic, we chose a chunk size of 8192 blocks. This reduces the required storage slots from 15.5 million to only 2000, but still allows us to import new block hashes once per day (8192 blocks is about 27.3 hours).

This solves the storage cost problem, but how can we trust that the Merkle roots were computed correctly? We need some way to ensure that the committed Merkle Trees do not contain incorrect block hashes. Unfortunately, computing the Merkle roots on-chain by passing all of the headers in calldata is cost-prohibitive: the entire history of block headers is over 7GB of data (most of which are non-zero bytes) so this would require about 100 billion gas, or about 2000 ETH at 20 gwei gas.

First Thought: Use a Rollup

If verifying the Merkle roots costs too much on Ethereum, could we instead compute the Merkle roots on some L2 and then send a message to L1 with the verified Merkle roots?

Well, optimistic rollups still require the transaction calldata to be pushed to L1 (due to the data availability problem), so this would only marginally reduce gas costs. In the future, zk-rollups can solve the data availability problem by instead publishing only the state differences to L1, which requires much less data. Of course, validating 7GB of block header data would still require substantial fees due to high proving cost, but it should be much cheaper than an optimistic rollup. Sadly, at the time of writing, no battle-tested rollup is scalable enough for our needs.

Second Thought: Custom “Optimistic” Solution

As is common with scaling solutions, one feasible approach uses economic incentives and fraud proofs to reduce the need for trust. For an “optimistic” approach, we could publish the Merkle roots on-chain and offer a bounty to anyone who can prove the data is invalid. After all, block hashes are publicly available, so anybody should be able to validate the Merkle roots and challenge them if they are incorrect. The challenge procedure is as follows:

1. The challenger identifies the last Merkle root they believe to be incorrect.
2. The challenger calls the contract’s challenge function, which accepts an entire chunk of block headers.
3. The challenge function checks the headers’ validity, i.e. that they are properly linked to each other and that they connect to the first block of the next chunk (if there is no next chunk yet, an EVM-accessible blockhash can be used instead).
4. The challenge function computes the verifiably correct Merkle root. If it doesn’t match what was stored, the challenger receives the bounty.

(There are some ways to optimize this, but hopefully this gives the idea).

While this approach could work, it relies on economic assumptions rather than cryptographic assumptions, so some tradeoffs have to be made:

1. Settlement time: we must give sufficient time for challenges to occur before relying on the published data. As a new project, we would need an especially large challenge window to allow sufficient trust in the verification.
2. Capital inefficiency: we must lock up a meaningful amount of capital to incentivize the verification.

Our Solution: Custom SNARK Circuits

Terminology

For those who are new to zk-SNARK technology, we’ll define a few terms that we use in this section:

• (Arithmetic) Circuit: a model of computation where inputs are fed through a directed graph of operations (called gates) resulting in some outputs. An arithmetic circuit is one where the gates are addition and multiplication. As opposed to most other models of computation, a circuit represents a fixed-size computation.
• SNARK: a proof system where a prover performs some computation and generates a corresponding proof that it was performed correctly, such that a verifier can check the proof using significantly fewer resources than the prover. In most SNARK constructions, the computation is represented as an arithmetic circuit. For apps building on blockchains, the verifier is usually a smart contract.
• zk-SNARK: a SNARK where some of the inputs to the computation are hidden, meaning that verifier does not learn what the value of those inputs are — they only learn that those inputs result in the output of the computation.
• Output: a node in a circuit that is designated to be a “result” of the computation. In SNARKs, an output value is often thought of as just another public input, where the circuit computation instead enforces this input equals the expected computed value.
• Custom gates: additional operations supported by some proof system, often used because representing some operations in terms of arithmetic gates can be too costly. Most custom gate implementations use lookup tables.

Why use custom SNARKs?

The appeal of using a zk-rollup was the massive reduction in calldata costs, but the transaction costs may still be high due to proving costs. After all, we need to transmit 7GB of data and perform roughly 30 million Keccak hashes, which are notoriously expensive to do in arithmetic circuits. Implementing our own SNARK circuits has a few advantages:

1. No virtual machine overhead: zk-rollups process transactions in some virtual machine, e.g. StarkNet has the Cairo VM, while zkSync 2.0, Polygon Hermez, Scroll, and others have some type of “zk-EVM”. Although these VMs are more convenient to use than circuits, it should always be possible to squeeze out more performance at the circuit level.
2. Optimized proof system: with such a specific application in mind, we can select and optimize a proving system for our use case.
3. No cross-domain messaging: if the SNARK computation is directly verified on L1, there is no need to handle L2->L1 messaging, simplifying the logic.
4. Production-ready: while zk-rollups and zk-VMs are still being battle-tested and optimized, the underlying SNARK/STARK technologies are much easier to ship today.

Circuit Architecture

To produce validated Merkle roots, our circuits must verify two properties:

1. The input block headers are correctly linked to one another.
2. The hashes of the input block headers form the output Merkle root.

Because Keccak hashes are expensive, we won’t be able to hash an entire chunk of block hashes in a single circuit. Thankfully, our computation has a nice recursive structure which lets us divide and conquer, using two circuit designs:

Inner Circuit: takes M (some small power of 2) block headers as hidden input, verifies they are properly linked, and outputs

1. merkleRoot: the Merkle Root of the M block hashes
2. parentHash: the parent block hash from the first block header
3. lastHash: the last input block’s hash

Recursive Circuit: takes two proofs (and their outputs) as input, recursively verifies them, checks they are linked (the lastHashof the first proof equals the parentHashof the second proof), and outputs:

1. merkleRoot: the Merkle root of the two inputmerkleRoot values
2. parentHash: the parentHash from the first proof
3. lastHash: the lastHashfrom the second proof

The recursive circuit’s proofs and outputs can then be fed back into itself to recursively aggregate more and more block hashes into a single proof to verify on-chain!

Choosing a Proof System

With this circuit architecture in mind, we need a proof system which can efficiently handle Keccak hashes and recursive verification. As always, it would be nice to have no trusted setup (or at least a universal trusted setup), so we don’t have any Relic-specific toxic waste. And of course, it must be efficient to verify the proofs in the EVM, so it should either use very small fields or Ethereum’s natively supported BN-254 curve (sometimes called BN256).

There are a few options that meet these criteria, but two stood out:

1. Polygon’s Plonky2: a relatively new proof system with incredibly fast recursive proof times. However, this efficiency comes with the cost of large proof sizes, which means high calldata costs. For applications that need very high throughput (such as a zk-rollup), this is a worthwhile tradeoff. However, our use case can trade longer proof times for cheaper verification.
2. Aztec’s UltraPLONK: a more battle-tested proof system which has been used in production for zkSync, Zcash, and others. Conveniently, many of the custom gates we need (for Keccak, SHA, etc) are already implemented by Matter Labs for use in zkSync 2.0. Although the proving times are higher than Plonky2, PLONK has very small proof sizes, so verification costs are currently much lower.

Due to the cheaper verification costs and existing tooling, UltraPLONK fits our needs better. But, high proving times could pose challenges, since we must be fast enough to keep up with the stream of Ethereum blocks. Thankfully, after a few optimizations, proving times are low enough that a single low-end consumer GPU can easily keep up with the chain.

Implementation and Optimizations

Our proof system is based on the Matter Labs fork of bellman, but with a few changes:

1. Added GPU proving support based on Filecoin’s work
2. Optimized a few inner functions based on profiling results

Additionally, since proving times are roughly proportional to the number of gates, we used a few tricks to reduce the size of our circuits:

1. Used hash function gadgets based on lookup tables, greatly reducing the number of gates needed to perform hashes.
2. Used SHA-256 instead of Keccak to build our Merkle trees. Keccak must be used to compute the block hashes, but we can use any EVM-efficient hash function for our Merkle Trees. SHA-256 offers a nice balance between circuit size and EVM gas cost, due to the Ethereum precompile.
3. Modified the recursive aggregation logic to use a fixed inner-proof verification key (VK). In our case, the inner proofs come from the same circuit, so we can hard-code the verification key to reduce the number of gates needed to aggregate proofs. This comes at the cost of having a different VK for each proof size (e.g. a proof containing 8K blocks has a different VK than a proof containing 16K blocks), but we only need to support on-chain verification of a few of proof sizes.

If you’re curious, our circuit code is public on github. You may also want to check out our recursive PLONK verifier written in yul assembly, which reduces gas costs for verification on-chain.

Future Work

Our usage of SNARKs so far has enabled very cheap verification of historical block hashes in the EVM. As a result, the gas costs to access historical state are dominated by the Merkle-Patricia Trie proofs. We are experimenting with aggregating many MPT proofs into a single SNARK, which has the potential to bring the proving cost per state fact down dramatically.

Questions? Comments? Join our discord and let’s discuss!

Scaling Relic Protocol with zk-SNARKs was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

What is an NFT?

At its core, an NFT is simply a smart contract that obeys the ERC-721 token standard. The basic concept here is that there is a smart contract which tracks individual tokens, and with each token associates an owner. Because the tokens are tracked individually, we can refer to specific tokens: it makes sense to say “Alice holds token 123” and “Bob holds token 82”. This is in contrast with fungible assets: if Alice and Bob each have a dollar, nothing interesting happens if their two dollars swap.

NFTs don’t really have anything to do with artwork, except that it is one common example of non-fungible assets. Paintings, for example, are unique — Alice’s Seurat is quite different from Bob’s Picasso. But NFTs could really be anything that has a unique identifier and can be owned: software licenses, complicated financial positions, domain names, and so on.

NFTs and Art

By themselves, NFTs actually have no images associated with them. That comes from an optional extension to the ERC-721 specification to provide metadata. The tokenURI function takes in a token ID, and returns a Uniform Resource Identifier (URI) — essentially a URL, but slightly more generic. That URI points to a JSON string which contains metadata such as the name, description, and finally an image for the individual token.

So this is where the artwork comes in to play. But how are these URIs set up? There’s a dirty secret: a lot of these URIs simply point to Web2 servers. If you want to view your NFT, you (or OpenSea or other apps) will query the Web2 URI for the image data. This obviously has a lot of negative consequences:

• What if the company hosting the data decides to return something else?
• What if the company hosting the data forgets to renew their DNS record, and a malicious entity takes over?
• What if the company hosting the data gets hacked?
• What if the company hosting the data goes out of business?

Put simply, this isn’t decentralized.

IPFS

The Inter-Planetary File System (IPFS) is one way to attempt to address these problems. IPFS is effectively a decentralized file store. Each file gets a cryptographically unique identifier based on the contents of the file. By using the file contents to derive identifiers, the receiver can easily verify if the data matches the identifier it requested!

This removes one big class of issues by ensuring malicious entities can’t replace your data. However, it still has a few problems.

IPFS still requires that someone in the network hosts the data. While it ensures that any data delivered is correct, it doesn’t guarantee data is delivered at all. For popular information that many people would mirror (such as Wikipedia or popular media files) this is not a concern. But for niche files, it’s possible only one server is hosting the files. What will happen to this data in 1 year? in 10? it’s hard to say.

The next issue is that while IPFS is a popular and successful project, most users only access it through centralized gateways. Most users today access IPFS data through a limited number of gateways such as Cloudflare or ipfs.io which are very convenient, but not very decentralized. If these gateways wanted to, they could easily censor or modify data. This is not a fundamental limitation of IPFS, and hopefully more users will directly access the IPFS network in the future rather than relying on centralized gateways.

Another difficulty of using IPFS is that files cannot change. This is fundamental to its security model, but it also presents some limitations. What if the NFT’s data should change over time? This isn’t a problem for static images or videos, but there is no reason NFTs need to be static files. It also means that for NFTs generated on the fly, a component needs to exist to generate and upload the images to IPFS.

IPFS is very cool technology and a great project. But at the end of the day it’s not natively available on Ethereum. For many use cases this is acceptable or even preferable, but for an on-chain object like an NFT, introducing any off-chain dependencies is simply introducing another point of failure.

Blockchain Storage

Luckily there is another option that solves the problems of Web2 storage and IPFS: the blockchain we are already using!

Ethereum already requires data be storable and accessible. Once added to the blockchain, the data will be available permanently (at least as long as the blockchain continues to operate), and secured cryptographically the same way all data in the blockchain is.

There is one downside with this approach: resources on the blockchain are limited, so storing data can be very expensive. This just means we need to be thoughtful with what we store and how we use data to keep costs down.

Design Goals

Our first NFT associated with Relic is the “Birth Certificate”. Although the data Relic generates exists independently of the NFTs, we thought it would be a more accessible way for users to understand their data.

When a user proves their Ethereum “birth date”, Relic will issue them a Soulbound NFT. This will be generated dynamically, based on when their account was created. We want these NFTs to be fully decentralized and trustless, just as the protocol itself is.

With these requirements, we decided our best option was to build dynamic SVG NFTs on-chain.

SVGs

Scalable Vector Graphics (SVG) are a way of specifying how to draw images, rather than a collection of pixels (or raster graphic). Aside from infinite scaling, simple images can be much smaller, because their description may be very succinct. It also means it is easier to manipulate: if you want to change something from a circle to a square, or red to blue, it’s a simple change of the XML text that makes up the SVG.

The above graphic is made by the following SVG code:

<svg width="100" height="100" xmlns="http://www.w3.org/2000/svg">
<rect x="30" y="30" width="60" height="60" fill="blue"/>
<circle cx="40" cy="40" r="30" fill="red"/>
</svg>

This clocks in at 174 bytes (and can scale infinitely) compared to the PNG version at 1181 bytes.

This ability to specify and modify images with ease makes them well suited to generating on-chain. But how does this work in practice?

Implementation

The first thing we need to do is create URIs that use on-chain data. Unlike for HTTP or IPFS, there is no URI scheme for locating on-chain data by pointing to an Ethereum contract or anything like that. However, we can use data URIs. A data URI allows us to encode what we want to point to directly in the URI itself.

For example:

data:image/svg+xml;base64,PHN2ZyB3aWR0aD0iMTAwIiBoZWlnaHQ9IjEwMCIgeG1sbnM9Imh0dHA6Ly93d3cudzMub3JnLzIwMDAvc3ZnIj4KPHJlY3QgeD0iMzAiIHk9IjMwIiB3aWR0aD0iNjAiIGhlaWdodD0iNjAiIGZpbGw9ImJsdWUiLz4KPGNpcmNsZSBjeD0iNDAiIGN5PSI0MCIgcj0iMzAiIGZpbGw9InJlZCIvPgo8L3N2Zz4K

will render as the above SVG image with the circle and square.

Unfortunately, data URIs commonly use Base64 encoding which makes them a bit more annoying to work with. However, we can use OpenZeppelin’s Base64 function to handle all of the encoding natively on-chain.

Thus, the outline for our NFT metadata construction is something like:

• build a skeleton JSON top level metadata object
• build a skeleton SVG that we can inject data into for dynamic content
• insert the required data when the token is minted and Base64 the image
• put the image URI into the JSON metadata, and Base64 the JSON
• return the data from the tokenURI call

Optimizing Images

Right away we hit a few hiccups. First, the design we chose for our NFTs has 12 different animal figures, each with 5 different colors for the different agents of the Asian Zodiac. These are raster graphics that can’t easily be transformed into an SVG.

Let’s not panic: we can simply embed these images as yet another data URI inside our SVG!

Originally each image was about 400kB, and we had 60 of them, totaling about 24MB of image data. On Ethereum, storage costs are roughly 20k gas/32 bytes, which would lead to a cost of 300 ETH at 20Gwei gas prices.

Maybe panicking was appropriate…

Luckily, this data will only be written once and stored forever, so instead of using storage, we can use contract data, which is about 1/3 the cost: about 5M gas/24kB, or about 100ETH at 20Gwei prices.

I still don’t think we’ve got the budget for that, so maybe we can make our images a bit smaller…

Our images were originally PNGs with transparency, which means we can’t easily use JPEG (which doesn’t support transparency). But we can use the relatively new format WebP. Without any fiddling, we can turn a 300kB PNG into a 50kB WebP image using cwebp.

To make deployment and coding easier, it would be much more convenient if we could get the image small enough to fit in a single smart contract though, which means about 24kB. Luckily we have some options: the alpha channel of the image can be compressed at a lower quality than the color channel, and we can adjust all of this until it fits in our size budget.

Now we’re talking! Using a simple script, we can adjust the quality levels of all our images until they can fit in a single contract. We’ve now brought our cost for the images to 60 x 5M gas, about 6ETH at 20Gwei prices. There is a subtle loss in quality which isn’t great, but it is acceptable for our use case.

Luckily, there is one more optimization we can do. The different colors of animals are all very similar assets. Rather than storing each image 5 times, can we use code in our SVG to modify the color?

It turns out we can do this with SVG filters! Much like adjusting the levels, curve, hue, and saturation in an imaging program, we can do that directly from code. This gives us an additional 5x reduction in costs to about 1.2 ETH at 20Gwei. Still pricey, but especially if we can wait for cheaper gas, that is quite reasonable.

The contract for each of these images is very simple:

contract Image {
    function image() external pure returns (bytes memory) {
        return 'HEX ESCAPED IMAGE DATA GOES HERE';
    }
}

Our main URI creator contract will receive the list of the image contracts in its constructor and call into them as needed to fetch the different animal images to construct the SVG.

Optimizing Text

The next issue is how to handle our text. Our designer worked hard to pick the right font, so we need to be sure to use that. However, we don’t want to link to the font on the web, because that would be centralized! Luckily we can use our favorite thing in the world: more data URIs!

Of course, our fonts are once again too large: about 150kB for each of the three separate fonts we use. Luckily there is a trick that web developers use for optimizing font sizes: because we know the set of characters we might use for each font (for example, the letter x and then 0–9 and a-f for the monospaced font), we can remove all the font information about other characters. With this, we are left with about 6kB of font data. We could probably reduce it further, but that’s within acceptable limits.

Similar to the images, we stick the fonts in a separate contract for storage — since they are small we can use one contract for all three fonts we use.

Bonus

One fun thing about SVGs is they support animations natively. This means we can easily add in animations like slowly moving the astrological signs in the doorway and scrolling the address text around the edge.

In something like a GIF this would require separate rendering for each frame and take up lots of space. But in SVG all we have to do is write a quick line like

<animate attributeName="x" from="0" to="21" dur="5s" repeatCount="indefinite"/>

and suddenly we can move a background.

We limited our animations to keep our graphics simple, but there are lots of really cool opportunities here for other projects!

The main caveat here is that some NFT viewers may not support newer SVG functionality like some filters and animations. The good news is popular browsers (Chrome, Safari, Edge, Firefox, Brave, Opera) will be fine, and any viewer that doesn’t support it will likely get upgraded in the future to support the rest of the features.

Bringing it Together

At this point we’re basically done! We’ve deployed 12 contracts of images, 1 contract of font data, and 1 contract for the SVG itself. In our case, this contract is separate from the actual ERC-721 contract for the Birth Certificate.

Our main URI creator contract’s SVG skeleton (and main JSON metadata skeleton) is also populated with a few pieces of information that may change depending on information on chain. For us that means:

• color filter applied to Zodiac animal
• background pattern for astrological sign
• direction for astrological sign animation
• text for birth date & time
• text for block number
• text for address
• data URIs to be filled in by external calls to image and font contracts

In practice this is as simple as splitting up the SVG into chunks of static content (such as the background imagery, and some of the text), and joining it together with the dynamic elements with string.concat with something like:

function image(uint256 tokenId) internal view returns (string memory) {
   return
     Base64.encode(bytes(string.concat(
        CHUNK1,
        dynamic_element1(tokenId),
        CHUNK2,
        dynamic_element2(tokenId),
                ...
        CHUNK_FINAL
    )));
}

In our case the dynamic elements are based on the token ID. However, this need not be the case: it’s possible to create a token where the dynamic elements change in response to other state or actions.

For example, one could make the animals in our NFT images grow larger over time by calculating the size dynamically every time tokenURI is called. There are lots of interesting possibilities for other NFT techniques using this!

This diagram shows the relationships between the main contracts for our NFT and should help make things a bit easier to understand. The diagram omits the internal calls for populating dynamic content in the skeletons, but contains the external calls between contracts.

Although the SVG data generated is a bit ugly, it is possible to inspect and modify the SVG data from the Relic NFTs (or any SVG NFT) by simply viewing the NFT on OpenSea or similar and using the browser view source function, or downloading it and using a text editor.

One reasonable question is: how much gas does it take to call the tokenURI function? It’s a lot. Luckily the function is a view function and can be called off-chain for “free”. So while it may not be practical to get the URI data from a smart contract, it is easy for NFT viewers like OpenSea to do so.

Takeaways

There are a few important things we’ve learned here. First, it makes sense to keep NFTs purely on-chain: it’s the only way to ensure they are as permanent and accessible as the blockchain is. Luckily, with only a bit of work, it’s possible to build NFTs in this way. This also enables richer dynamic content where the events on the blockchain can cause changes in the images.

Although purely vectorized SVGs are the ones most commonly used on-chain, we aren’t limited by this! We were able to combine raster images and vector images for a richer design. Although this cost a bit more in gas, we were able to get costs down to pretty reasonable levels.

Relic

How does this connect to the Relic Protocol ecosystem? Our soulbound tokens are not used themselves by the protocol. Because they are only issued once a user’s account is cryptographically proven to have existed in a block, they serve as an alternate representation for the facts stored by Relic. And because they are soulbound (not transferable), owning one is equivalent to the fact being stored by Relic. However, we expect applications that wish to verify account age to query the Reliquary contract rather than attempt to verify facts using NFTs.

Of course, if you would like to make one of these soulbound NFTs for yourself, you can do so at https://app.relicprotocol.com !

If you want to know more about Relic, check out the first post in our series: Building Relic

If you have any questions, feel free to let us know on Twitter or Discord

Fully On-Chain NFTs was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

While the basic idea is simple, there’s a lot that needs to happen to do this in a way that is trustless and secure.

Block Hashes

The first step is getting access to the hashes of every block in the Ethereum chain. On the one hand, this is easy: with about 15.6 million blocks and 32 bytes of Keccak hash per block, that is less than 500MB of data. While that doesn’t sound like a lot of data for 2022, unfortunately Ethereum storage looks and costs a lot less like 2022 storage and a lot more like 1956 storage.

With storage data on Ethereum costing around 20k gas per 32-byte word, it would cost about 6,240 ETH at a gas price of 20gwei to store that much data. That’s probably on par with storing 500MB of data in 1956…

Of course, we have more efficient ways to store the block hashes. Instead of storing them all individually, we can use the ubiquitous Merkle Tree. This data structure uses cryptographic hash functions — functions which take data as input, and output a fixed size blob of data called a hash. Cryptographic hash functions have a few¹ special properties:

• first pre-image resistance: given a hash, it is difficult to find data which results in that specific hash
• collision resistance: it is difficult to create any two different pieces of data which result in the same hash
• second pre-image resistance: given a piece of data, it is difficult to find other data which hashes to the same value (this is a weaker property than collision resistance)

We can combine these hashes into a tree: an arrangement of data where each node has two children nodes associated with it, and the value of a node is the hash of its two children combined. Building this up, each level of the tree has half as many nodes as the level underneath it, until we get to a single root node at the top.

This lets us use only a single cryptographic hash to commit to as much data as we like. Once the top root is fixed, the bottom data leaves cannot be changed. (Because if they could, it would mean someone could bypass one of the stated cryptographic properties of hash functions.)

To prove a particular piece of data is associated with a Merkle Tree, users can present the original data, as well as the sequence of partners that were hashes along side that data as we walk up the tree as a witness. A piece of code like a smart contract can verify that this process results in the correct Merkle root at the end, meaning the data presented must have been present when the Merkle Tree was originally created. There are a few practical constraints², but this effectively solves the storage question: we can take each of our block headers and place them in a Merkle Tree. By storing Merkle roots instead of the entire sequence of data, the storage drops significantly.

Trusting Block Hashes

Of course, it is easy to push a hash on-chain and claim it is correct, but that relies on trust. How will users know that Relic pushed the correct Merkle Tree of block hashes?

Luckily, the entire purpose of blockchains is to make it possible to verify the authenticity of previous data. Each block’s header data is included in the Keccak hash calculation that describes the next block. Similar to a Merkle Tree, this means the current block hash is a commitment to all previous blocks. Therefore, as long as we can link up all of our historic blocks using successive hashing and have the final block match up with the current Ethereum state, we know that all the historic data is correct.

That all sounds great, but how can we take our Merkle Tree and verify successive hashing of all the included data? Unfortunately the answer is: we cannot.

zk-SNARKs

Well okay, that stinks. But what if instead when we create our Merkle Tree, we store some extra information that proves the original data follows the blockchain property? It turns out this is possible using zk-SNARKs. At a basic level, a SNARK³ is a way to use some data to produce a short associated witness (similar to a mathematical proof) that can be used to convince a verifier that the data has certain properties. Intuitively: a SNARK is a way to quickly prove to a third party that a (potentially difficult) computation was done correctly. The magic is that the verification process is very fast, and the associated witness is very small — perfect for the limited resources of the blockchain.

With this, we have all the basic pieces we need to create our historical data. We can “SNARKify” construction of our Merkle Tree to guarantee that the original data has the blockchain property and results in the stated Merkle root. Then we can “connect” the last block in our proof to a recent block that is still accessible from within the Ethereum Virtual Machine (EVM), by showing the recent block was created by hashing the data from our block. Thereby proving that the Merkle Tree was created from our preceding block data.

For practical reasons we do not create a single Merkle Tree for the entire Ethereum history. Instead we make several trees of fixed size. This makes Merkle proofs shorter, and makes it easier to work with as a zk-SNARK⁴, both of these keeping gas costs under control for users.

We’ll talk more about zk-SNARKs and how how Relic uses them more in a future post, but for now this is a good enough overview.

Recent Data

Phew. So now we have handled the historic block hashes, but what if someone needs a block hash from a few hours ago?

First off, Relic maintains a server running 24/7 building zk-SNARK proofs and submitting them on chain once every 8192 blocks (a little under 1 per day).

As we mentioned before, the EVM can access the last 256 block hashes of data, just shy of one hour. But what about the stuff older than 1 hour but newer than 1 day?

Luckily this problem is very similar to the one we solved before with our historical blocks: we would conceptually like to make a hash chain from the desired block to a block recent enough to be accessible from the EVM. As before, rather than attempt to submit hundreds or thousands of blocks and hash them all, the easiest way to do this is to use a SNARK.

Therefore, concurrently with 24/7 building zk-SNARK proofs of Merkle Trees for the block hashes, Relic also sets some aside that are not pushed on-chain automatically. If someone wants to use Relic to prove a fact from 2000 blocks ago, the web2 Relic API will issue their proof as a zk-SNARK of a small Merkle Tree of block headers and their inclusion in that tree, instead of simply an inclusion in one of the already published Merkle Trees.

Ethereum State

At this point we have discussed (at a high level) how to prove any historic block hash on Ethereum. This is already useful in itself for developers⁵ but most people care less about the Keccak hash of a block, and a lot more about what happened inside the block… Luckily this last step is quite straightforward.

If you’ve been paying attention so far, some of these names should jump out at you. Those things labeled stateRoot, transactionsRoot, receiptsRoot, storageRoot? Those are all roots from Merkle Trees — well technically Merkle Patricia Tries, but it’s the same idea.

If you want to prove a transaction occurred in an Ethereum block: take the block header, extract the transactionsRoot, and then create a Merkle Proof of the transaction. Similarly for other basics in Ethereum (storage, receipts, etc.).

Tying It All Together

This is just an introduction, but you now have the basic idea for how it is possible to access historical data from any point in Ethereum’s history on-chain and in a provably secure way.

Let’s walk through an example of how a user can use Relic to prove a basic fact about historical data, like “my Ethereum account has existed since 2017”⁶.

1. Smart contracts which verify zk-SNARKs for block history are deployed by Relic
2. The Relic team runs the Relic Prover off-chain to generate proofs of block headers. To make sure the block headers are accurate, they are all verified 100% on chain by the zk-SNARK circuits.
3. Users who want to prove their fact (account existed in 2017) can talk to the Relic Prover⁷ off-chain to help construct two proofs: one proving their birth block existed in the Ethereum chain (by showing it exists in the Merkle Tree of proven block hashes, or showing it is in the last 256 blocks, or using a SNARK), and another proof showing the Ethereum stateRoot Merkle Patricia Tree has an entry for their account in that block.
4. These two proofs are then submitted to the State Proof Verifier which ensures both proofs are correct.
5. The State Proof Verifier then stores the proven fact in the Reliquary⁸, to commit the fact to the blockchain for future use (without requiring proofs each time).
6. For things like Birth Certificates, a Soul Bound Token⁹ may be issued, so users get to show off their proven facts on OpenSea or similar places.

Once a fact is proven, it can easily be queried fully on-chain by any dApp by interacting with the Reliquary. Any smart contract can now easily verify facts about Ethereum state at any point in the history of the entire chain!

Stay Tuned

We hope you enjoyed learning about how Relic works! Keep track of our project on Twitter and Discord as we publish more information. Read our code in depth on our Github, and try Relic for yourself at https://app.relicprotocol.com/.

Check back for more in-depth posts about how we use zk-SNARKs, how Relic can be used by dApps, and more!

[1] There are other properties important for general use, but less important here.

[2] The size of the witness data is logarithmic in the length of the data stored. For a tree of about 16 million items, that would be 24 hashes that need to be presented in call data as a witness. This also does not allow for easy updating of the Merkle Tree as new blocks are produced.

[3] While zk-SNARKs are a special type of SNARK that provides additional privacy guarantees called “zero knowledge”, this is not important for our use case. Modern SNARKs happen to be zk-SNARKs as well, but this need not be the case.

[4] The time (and thus gas) to verify a SNARK still grow with the amount of “stuff” (called circuit size) you want to verify. Additionally, while it is fast to verify a SNARK, it is quite difficult to create them — and again the cost to build SNARKs scales with its size.

[5] You can access this data today from our contracts! Though we are still working to improve the documentation of these features.

[6] We call this a “Birth Certificate”, you can make your own at https://app.relicprotocol.com/

[7] Today it is easiest to use the Relic Prover to create this, but it is not required!

[8] A reliquary is a container for relics.

[9] Why not a transferable NFT? If Birth Certificates (or other facts) were transferable, they would have no meaning!

Building Relic was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.

Currently, smart contracts on Ethereum have surprisingly limited access to the blockchain’s data. We are changing that.

Historical Data

The Ethereum blockchain contains over 15 million blocks, in which over 1.7 billion transactions have occurred and over 200 million accounts have been created. Altogether, Ethereum’s history consists of tens of terabytes of data.

This rich set of data can be accessed by any archive node or block explorer, but is currently inaccessible to smart contracts running on chain. Relic Protocol is designed to overcome this limitation of the EVM.

Relic Protocol

Using new cryptographic tools such as zk-SNARKs, Relic Protocol gives smart contracts access to all of Ethereum’s historical data, enabling entirely new types of applications to be built.

What’s more, we’ve already deployed the foundation which makes this all possible. Follow us to stay tuned as we roll out our developer SDK, and join us on Discord to let us know what features you want to see!

Relic Protocol | Docs | Twitter | Discord | Github

Hello, We Are Relic was originally published in ChainLight Blog & Research on Medium, where people are continuing the conversation by highlighting and responding to this story.