Cointime

Download App
iOS & Android

Lookup Singularity via MMR

From etheresearch by Hmac512

Lookup Singularity via MMR

Introduction

What I will show is that if we have a public merkle mountain range where existence within it implies correctness, then this primitive can be used to achieve the lookup singularity. What I mean is you can enable complex lookup tables for sha256 hash, merklizing leaves, or potentially even EVM storage proofs.

There are optimistic and immediate finality variations of this scheme which balance certain trade offs.

Background

Lookup tables are an incredible innovation in the world of ZKPs. They allow for much faster proving for complex computation like a Sha256 hash. Barry Whitehat coined the term the lookup singularity (Lookup Singularity - General - zk research 1) to represent how they can drastically improve the performance of SNARKs.

Standard lookup tables require pre-computing an entire table, and committing it during circuit compilation. Therefore these tables cannot be updated after the keys are generated. The cost of committing the table is amortized over all the lookups used during proving. There is a negligible per-lookup cost for these types of constructions (eg plonk-lookup). The obvious limitation here is that it’s impractical for lookup tables that are very large, say 32-bit float arithmetic (2^64 rows).

Justin Thaler wrote papers for a new system called Jolt/Lasso which sacrifices the low per-lookup cost in order to get more complex lookups. This is done by using multivariate polynomials to represent the lookup table as a polynomial evaluation. This makes it so you don’t need the full table in memory to use in a circuit, but increases the per-lookup cost. See Lasso/src/subtables/lt.rs at 823da601422d17f7c150631947b33a9db1ad5b98 · a16z/Lasso

These constructions don’t practically allow for lookup tables of truly complex operations like a sha256 hash. Say I had 100 leaves and I wanted to merklize them to compute the root. No existing lookup table construction can help you with this.

Trusted lookup table oracle

One very easy way to increase the performance and utility of a lookup table is to use a trusted source. Imagine I wanted to multiply 2 floating point numbers, I can submit the lookup via an API to a service that returns the lookup table with a snark-friendly signature. In practice we would batch all the look ups together with one signature.

The beauty of this approach is you can enable truly arbitrary lookup operations, which would dramatically improve the performance of your circuits. You also get a custom lookup table for each proof you generate. This approach would drastically decrease circuit complexity.

One thing to note is that for any sensitive parts of the circuit you may wish to do it without the table oracle to preserve privacy. Alternatively you could include extra unnecessary lookups to obfuscate which were used. This approach lets you offload any parts of the circuit which can be public into a lookup table. Essentially a selectively disclosed computation ZKP.

However, the issue here is that the trusted party can secretly sign incorrect lookups in order to forge a proof and attack a system. The idea I want to present is to solve this malicious lookup oracle problem via crypto-economic methods.

What if there was a better way?

Securing with crypto-economic security

The obvious place to start is have the lookup oracle stake a large amount of ETH/USDC/etc. If I can coerce the oracle to give me a malicious result, I can generate a fraud proof (ZKP or smart contract) in order to claim a reward.

This works well to prevent the oracle from colluding with someone else. This however fails in the situation where the oracle is also the one requesting the lookup. There is no economic incentive to claim your own stake.

The only way to solve this problem is to force the oracle to publicly disclose every lookup table that it generates. This can be done with a merkle mountain range (MMR). The key insight you need to see is that existence within the public MMR directly implies correctness. We then construct the circuits to check for existence within a MMR, and we then compare with the root of the trusted, public MMR.

Overall Solution

First you use a merkle mountain range w/ a zk friendly hash to commit tables into a smart contract. A MMR is advantageous because:

  1. Scales virtually infinitely
  2. Short inclusion proofs
  3. Quick to update proofs

In order to avoid confusion, I want to emphasize the MMR does not merklize a full lookup table. Instead each leaf in the MMR can be a custom lookup table(s) for a particular proof generated. Each leaf can be multiple tables, as a circuit might offload multiple operations to a table. The MMR may include duplicate lookups.

The lookup table used during proving only needs to include the entries needed. This is the key advantage of this approach.

To save on gas, the actual lookup tables do not need to be put on-chain, we can use an optimistic approach where just the commitments of the tables are stored. The details around off-chain data availability will not be discussed here.

In situations where we want quick finality, you can have a contract verify table validity before adding it to the global MMR. The trade off is it will cost more. The optimistic approach actually allows for much more complicated look ups (eg call a smart contract w/ some input at a block height)

There are a few variations these tables can be utilized, but the custom lookup table is always an input into the primary circuit. This is nice because in a mobile app setting this enables us to generate a snark and its corresponding tables very quickly. What remains is proving the table used is in the global lookup tree. The mobile app can submit the zkp + lookup table to an infrastructure provider which will finalize the snark.

The infrastructure provider can verify the table validity, and submit it for inclusion into the trusted MMR. Once included, an inclusion proof can be generated. The original snark can be recursively updated to verify the table used exists within the global MMR. The root of the MMR then becomes a public input of the resulting ZKP. The location of the table can optionally be disclosed as well.

The overall trade-off is pretty simple. For the price of waiting a bit to submit/verify the proof, you get fast and memory efficient snarks client-side. The waiting to submit can be handled for the user with infrastructure.

Complex fraud proofs are not required for the optimistic variation. A smart contract can be used to check validity of entries when prompted.

Conclusion

I am very confident the above would work, and yield dramatic performance gains to client-side snark proving.

For the optimistic variation we can enable truly complex lookups that simplify ZKPs around EVM storage proofs. The tradeoff for very complex look ups would be a longer settlement time. The settlement time can be decreased if you limit the lookup operations in complexity (sha256, floating point operations etc).

In the immediate finality variation, there will be a larger financial cost for each addition to the MMR. I suspect the EVM would be prohibitively expensive, especially at scale. To optimize this approach it would be best to build a new chain. As of the time of writing, Solana is doing 3500 TPS at a tx fee around $0.0002. If you reduced the complexity of the execution environment you would get more TPS for cheaper.

Alternative Perspective

It hit me after my initial post that there is an alternative use case for the technique described above where a MMR is unnecessary.

From the perspective of the prover, generating the main ZKP is done in two parts

  1. Compute lookup table(s) for circuit
  2. Use table(s) as a public input to generate the ZKP

From here we have a ZKP and a list of assumptions the ZKP is made on. The other use case is the prover can offload some of the heavy parts of the circuit to infrastructure to validate the assumptions, and recursively update the ZKP.

Pretty neat

EVM
Comments

All Comments

Recommended for you

  • NPC Labs Closes $18M Funding Round to Build GameFi Ecosystem on Base Protocol

    NPC Labs, a developer focused on building a GameFi ecosystem on the Base protocol, has raised $18 million in a funding round led by Pantera Capital. The company plans to use the funds to act as a core contributor to B3.fun, a Base gaming ecosystem, and build GameFi products that are accessible to non-crypto native users. NPC Labs aims to make crypto gaming more accessible to the average person and plans to build discovery portals such as Basement.fun to help users get into these games. Other participants in the funding round included Collab+Currency, Sfermion, Mirana Ventures, Bitscale Capital, and Mantle EcoFund.

  • eBay’s NFT Marketplace KnownOrigin Announces Suspension of Operations

    According to reports from foreign media, NFT marketplace KnownOrigin, which was acquired by eBay in June 2022, has announced that it will be closing its on-chain marketplace and minting functions. In February of this year, eBay laid off 30% of KnownOrigin's employees, causing concerns about the platform's future. The recent announcement confirms these concerns, with the company stating that it has decided to cease operations due to changes in the NFT market. KnownOrigin states that "all KnownOrigin NFTs are minted on the Ethereum blockchain. This means that ownership is provable and these tokens can be publicly traded on secondary markets such as OpenSea and MagicEden."

  • U.S. House Speaker calls on Biden to resign "immediately"

    After Biden announced his withdrawal from the election, Republican House Speaker Johnson called on Biden to resign "immediately". Johnson said in a statement, "If Biden is not suitable to run for president, he is not suitable to be president. He must immediately resign from the presidency." Johnson said that more than 14 million Americans chose Biden as the Democratic presidential candidate, but the party that called itself "Democratic" announced that their votes were invalid. As the Speaker of the House of Representatives, Johnson ranks second in the presidential succession order, second only to Harris.

  • U.S. House Speaker calls on Biden to resign "immediately"

    After Biden announced his withdrawal from the race, Republican Speaker of the House of Representatives, Johnson, called on Biden to resign "immediately". Johnson said in a statement, "If Biden is not suitable to run for president, he is not suitable to be president. He must resign as president immediately." Johnson said that more than 14 million Americans chose Biden as the Democratic presidential candidate, but the party that calls itself "Democratic" declared their votes invalid. As the Speaker of the House of Representatives, Johnson ranks second in the presidential succession order, second only to Harris. When asked about some Republican congressmen calling on Biden to resign as president, the White House said that Biden "looks forward to completing his term." Senate Republican leader McConnell also accused the Democrats of "trying to overturn the will of the American people expressed in the national primaries," but did not call for Biden to resign as president.

  • All 30,971 MKRs associated with the MakerDAO team have been sold

    After 4 months of continuous selling pressure, the MKR related addresses with MakerDAO team have finally completed the transfer of 30,971 MKR ($92.08M) after 126 days. With the recent transfer of the final 2,228 MKR ($6.27M) to Binance in the past two days, it may indicate that their selling has been completed. From March 18th to July 22nd, during the past 4 months, the address has been continuously transferring 30,971 MKR ($92.08M) to the exchange in several hundred MKR increments, with an average selling price of about $2,973.

  • Harris expresses hope to win Democratic presidential nomination

    US Vice President Kamala Harris posted on X, saying, "On behalf of the American people, I thank Joe Biden for his extraordinary leadership as President of the United States and his contributions to our country over the past decades. I am honored to have the support of the President, and my goal is to win the Democratic Party's presidential nomination."

  • Trump: Those who concealed Biden's condition from the public for a long time need to be investigated

    According to Jinse Finance, Trump said in an interview with Primetime that those who have long concealed Biden's illness from the public need to be investigated. Vice presidential candidate JD Vance added that if the Democrats really want him to step down, his cabinet members should invoke the 25th Amendment.

  • Cointime July 21th News Express

    1.More than 12,000 BTC flowed out of Binance in the past 7 days 2.So far this month, US Bitcoin ETF purchases are 41,1583.A smart investor bought another $213.78 worth of BTC 9 hours ago4.USDC circulation increased by about 200 million in the past week5.A whale transferred $2.1 million worth of SNX to Binance 4 hours ago, or a loss of 13% 6.6.5 million USDT transferred from Kraken to Bitfine7.In the past 24 hours, the total amount of liquidation in the entire network was 60.86 million US dollars, and the amount of liquidation in BTC was 12.87 million US dollars 8.In the past two hours, three USDT transfer transactions totaling nearly 190 million occurred on the TRON and Ethereum chains. 9.The total Ethereum contract holdings on the entire network reported $14.798 billion, a 24-hour decrease of 0.62%. 10.Suspected early investors transferred $1.91 million worth of ONDO to Bybit

  • Cointime July 20th News Express

    1. BlackRock IBIT saw a total net inflow of $705 million this week

  • Hong Kong Legislative Council Member: The issuance and trading system of tokenized bond-related products can be shared with the mainland

    Hong Kong Legislative Council member Chan Chun-ying stated that the new productivity of Hong Kong's financial industry is currently mainly developed around digital and green themes. Regarding virtual assets, Hong Kong regulatory agencies should establish relevant trading platforms, stablecoin issuances, testing and operational mechanisms, capture digital development trends, and share relevant regulatory experience with the mainland. At the same time, Hong Kong's tokenized bond development is leading the world, and relevant product issuances, trading systems can be shared with the mainland or guide more mainland companies to issue, together meeting international market demand.