TL;DR (Summary)

The Kroma team is declaring 2025 as the breakthrough year of Web3 mass adoption, focusing company resources and strategy accordingly. While previously focused on technology and research, the team will now balance efforts by also prioritizing business, partnerships, and user acquisition, particularly through Kropot.

Key Priorities

• L2: Achieving Stage 1 as the top priority
  - Ensuring security while enhancing decentralization remains the highest priority.
• ZKP (Zero-Knowledge Proof): Collaboration with specialists like Succinct
  - Strengthening collaborations with expert teams to implement ZK proofs in a stable and cost-efficient manner.
• Acquiring 3 million Kropot users
  - By the end of 2025, Kroma aims to reach 3 million Kropot users, fostering an organic transaction-driven Web3 ecosystem.

Kroma’s ecosystem growth directly correlates with the value of the $KRO token. To establish a positive cycle, the following three initiatives will be implemented:

1. Buyback Fund
   - A portion of Kropot’s revenue will be used to purchase $KRO from the market, which will then be locked long-term or burned.
2. Deflationary Mechanism
   -Implementing mechanisms to gradually reduce or control $KRO supply, ensuring long-term value protection for token holders.
3. Real Token Demand Creation
   - Introducing models where businesses and projects must hold and lock up a certain amount of $KRO for promotions within Kropot.

These measures will establish a clear positive cycle: Kropot’s growth → Increased ad/promotion revenue → Buyback & Deflation → Rising token value → Ecosystem expansion. This will drive Kroma’s L2 toward mainstream adoption.

I. Kroma’s Journey So Far

The Kroma project was launched in 2022 to drive Web3 adoption, well before the explosion of Layer 2s and zkVM narratives. Since then, Kroma has made numerous technical advancements, including:

• World’s first Zero-Knowledge Fault Proof (ZK Fault Proof)
• First permissionless validator system in OP Stack
• Joining OP Superchain
• Developing ZK technology & Native Account Abstraction, receiving OP RetroPGF Grant (appox. 160,000 OP)
• Receiving OP Superchain Grant (500,000 OP) for Web3 adoption via Kropot

Despite these technological achievements, Web3 mass adoption remains unfulfilled. However, the emergence of faster and cheaper L2s has led to wider adoption of EIP-4337 (Account Abstraction), and Ethereum’s upcoming Pectra upgrade (EIP-7702) will enable Smart Account functionalities for EOAs, making Web3 accessibility even easier.

With this foundation, Kroma is declaring 2025 as the breakthrough year for Web3 adoption, following a strategic roadmap.

II. Kropot: The Super App for Web3 Adoption

Kropot is designed to simplify Web3 onboarding to an unprecedented level, allowing anyone to easily access Web3 services. It eliminates the common pain points of Web3 users — wallet creation, seed phrase backups, and complex transaction signatures — while providing a seamless mobile experience similar to Web2.

Key Features of Kropot

• Social Login & Account Abstraction: Users can sign up with email/SNS accounts. It allows non-custodial wallet structures without gas fees.
• High Scalability: While app-based, it seamlessly integrates with web environments for smooth Web2/Web3 transitions.
• Sustainability: Built-in revenue models (ads, promotions) enable growth without reliance on token incentives.
• Extreme Usability: Daily engagement with missions, mini-games, and rewards ensures high user retention.

Even the best technology is meaningless if no one uses it. While Kropot’s ultimate vision is to be a super app, the Kroma team carefully analyzed where to start. The reward app model, which has been immensely popular in recent years, was identified as the ideal Web3 onboarding gateway.

Traditional reward apps often restrict point usage to their own ecosystem, whereas Web3-based reward apps convert points into tokens, unlocking limitless utility. This is Web3’s unique advantage and a key factor in attracting Web2 users.

Since its Android app launch on February 4, 2025, Kropot has experienced exponential growth. The number of total registered users is skyrocketing, nearing 100,000 and surpassing the initial 25,000 pre-registrations. Also, ongoing partnerships are expanding Kropot’s point utility.

Kropot’s objectives as a reward app are as follows:

• Sustainable User Acquisition
  - Revenue from ads, promotions, and partner airdrops will ensure a steady influx of new users while engaging existing ones with reward-based content.
• Seamless Web3 Onboarding via Account Abstraction
  - Kropot will serve as an effortless entry point for Web2 users into Web3 without barriers or education.
• Ecosystem Contribution via Cash Flow Generation
  - Revenue streams from ads, promotions, and offerwalls will fuel Kroma’s ecosystem, strengthening the $KRO token through buybacks and deflationary mechanisms.

Kropot’s core features are:

• Reward-based missions & content: Users engage in daily tasks to earn rewards, boosting ecosystem activity.
• Mini-games with competitive elements: Light competition and community-driven gameplay encourage long-term retention.
• Kroma ID (Account Abstraction): Streamlined onboarding via EIP-4337, making Web3 features accessible even to blockchain novices.
• AI-powered assistant “Kropet”
  - Personalized rewards & missions: AI-driven user behavior analysis for custom incentives.
  - Interactive pet evolution: Frequent engagement enhances AI pet intelligence, creating a unique digital companion.
  - Bridging daily life, gaming, and investment: Kropet simplifies Web3 complexity while maximizing app retention.

III. Scaling Kropot’s Ecosystem

Kropot is uniquely positioned to bridge Web2 and Web3, enabling simultaneous promotions and partnerships across both ecosystems. By leveraging its large user base, Kropot will drive significant ad revenue. Users who naturally onboard into Web3 via Kropot can explore deeper Web3 services, while those content with reward apps can enjoy familiar experiences through in-app advertising.

The following is a projected revenue & ARU (Active Registered Users) growth based on revenue data from other market reward apps:

According to the scenario, the expected revenue of 3 million ARU is over $200,000 per month, and with 5 million ARU, the expected revenue will surpass $300,000 per month. A portion of the revenue will be allocated to the $KRO token buyback fund.

The Kroma team is hustling for the following objectives:

• 100,000 ARU in 30 days (post-launch)
• 1 million ARU in 180 days
• 3 million ARU in 1 year

IV. Kroma’s Core Technical Advancements

While Kropot is crucial, the underlying Kroma Network must also function optimally to support Web3 adoption. On February 11, 2025, Kroma successfully transitioned to zkVM which took us more than 9 months, and now we are prepared to resolve long-standing challenges.

1. Achieving Stage 1 Optimistic Rollup
   a. With zkVM, Kroma can now validate L1 derivation pipelines, moving closer to Stage 1 compliance.
   b. Vitalik Buterin has stated that non-Stage 1 L2s will be irrelevant by 2025, making this an urgent priority.
   c. We expect to achieve Stage 1 by April 2025.
2. Launching Kroma DAO for $KRO Stakers
   a. Users who stake KGH NFTs or $KRO will be eligible for the Kroma DAO, gaining voting power based on their stake.
   b. Governance participants will share Kroma’s sequencer revenue (in ETH), incentivizing active participation. Also, they may get distributed any unclaimed $KRO tokens that are reserved for airdrops
3. Designing a Multi-ZK Proof System for Stage 2
   a. Post-Kroma DAO launch, the focus will shift to multi-proof system design, paving the way for Stage 2.
   b. Kroma will collaborate with more ZK teams and explore a fully ZK Rollup future.

V. The Road Ahead

The journey toward Web3 mass adoption will be long, but Kroma has already proven its technical excellence. In 2025, Kroma will drive Web3 adoption through:

• Kropot: The super app offering a seamless, innovative yet practical user experience.
• Kroma ID: Maximizing Account Abstraction for easy wallet & account management.
• Kropet (AI Agent): Personalized engagement & high retention.
• $KRO Tokenomics 2.0: Sustainable cash flow & token value enhancement.

Ensuring blockchain accessibility for all by breaking the barrier between Web2 and Web3 is our mission. We will put our best efforts to achieve this mission, strengthening the Kroma ecosystem with Kropot’s explosive growth. The possibilities ahead of us are endless.

We extend our deepest gratitude to everyone joining us on this vision and journey. We will do our utmost to ensure that the upcoming year, 2025, is remembered as the turning point for Web3 mass adoption.

Thank you for joining us on this journey.

Sincerely,

TK Park
CEO
Lightscale Holdings PTE., Ltd.

A Letter to KRO Holders was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

A New Beginning

Kroket has been evolving, and as we continue to refine our vision, we realized it was time for a fresh identity — one that better reflects our mission, brand, and the exciting future ahead.

So, we’re officially rebranding Kroket to Kropot. 🎉

Why the Change?

The name Kropot represents more than just a rebrand — it embodies our vision for Web3 mass adoption. ‘Pot’ symbolizes a treasury of rewards, fueling an ecosystem where engagement translates into real value.

But this rebrand isn’t just about a name change — it also serves as a fresh start to remind users of the exciting ways to maximize their rewards! With Kropot, users can swap their points for OP and KRO tokens, making rewards more versatile and valuable. 😎 This shift is part of our broader mission to simplify Web3 onboarding and ensure a rewarding experience for everyone.

Rest assured — everything you love stays the same, or maybe even better! 🙌 The experience, rewards, and seamless onboarding remain unchanged, just with a new name and an even stronger commitment to our mission.

Where Can You Find Kropot?

The transition has already taken place across platforms, so you can now find Kropot live on Google Play and the App Store.

• Download here: https://kropot.io/

If you’re already a user, there’s nothing you need to do — just update the app and continue stacking rewards. 🫡

What’s Next?

This rebrand is just the beginning. We have major plans for Kropot’s expansion, new features, and even more rewarding experiences for our users and, NFT and KRO holders. Stay tuned for what’s coming next.

And for those of you feeling nostalgic — don’t worry, Kroket will always hold a special place in our hearts. RIP Kroket (2025–2025, 44 days 😇), gone but never forgotten.

Now, onwards and upwards with Kropot. See you!💚

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant | Kropot App

Kroket is Now Kropot — A New Name, The Same Mission was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

The Kroma network has successfully upgraded to version v2.1.1+geth.v0.6.1 (Kroma MPT hardfork). This hard fork transitions Kroma’s state storage from ZK Trie to Merkle Patricia Trie (MPT) and shifts the fault-proof system from Scroll’s zkEVM to Succinct’s zkVM. These changes will improve performance, reduce maintenance complexity, and ensure compatibility with the OP Stack. We have worked with our partners at Succinct to make these changes possible.

Why Transition from zkEVM to zkVM?

We transitioned from zkEVM to zkVM for several technological and operational reasons:

1. Faster and Cheaper Proof Generation

zkVMs have matured significantly in the last two years, and Succinct’s SP1 is leading the charge. Multi-machine orchestration was a key feature in our decision to adopt SP1. This splits the proving process into smaller computational cycles, allowing machines to parallelize proof generation and merge them efficiently at the final stage. This significantly improves performance, decreases proving costs, and reduces the total runtime.

2. Simplified Circuit Maintenance

Maintaining our zkEVM required constant updates to its ZK circuits. Every new transaction type forced us to rewrite the supercircuit, which was both labor-intensive and time-consuming. Auditing these circuits was a costly and lengthy process. SP1 eliminates much of this complexity because we only need to maintain the guest program.

3. Proofs Including Derivation Pipeline

When using Scroll’s zkEVM, we could not include the validation of the L1 derivation pipeline in the ZK proofs. This made Kroma’s proof system incomplete, and resolving this problem was a top priority for our team. By using Kona* as a guest program of SP1, we were able to prove the derivation pipeline, leading to a more complete proof system.

Note: Kona is a suite of portable implementations of the OP Stack rollup state transition, namely the derivation pipeline and the block execution logic.

Building on SP1 and Succinct’s Prover Network

We built our fault proof system on top of OP Succinct, which combines the modularity of the OP Stack with SP1, Succinct’s state-of-the-art zkVM. OP Succinct serves as a wrapper for Kona, a Rust implementation of the OP Stack rollup state transition function, and it generates ZK proofs through a simple API call.

Fundamentally, the combination of these technologies allows any rollup to implement ZK fault proving or full validity proving. Proving workloads are outsourced to the Succinct Prover Network, which generates proofs at low latency and affordable costs. Kroma is among the early adopters of Succinct’s Prover Network, and we’re excited to show what this technology can do for our users.

State Migration: Ensuring a Seamless Transition

Transitioning to a zkVM required migrating the entire state from ZK Trie to MPT. The Kroma team initially used ZK Trie to maintain compatibility with zkEVM, but with zkVM, MPT became the necessary choice. MPT not only improves performance but also aligns Kroma more closely with the OP Stack.

State migration, however, is one of the most complex tasks in a blockchain upgrade, as it directly handles user assets — a single mistake can have catastrophic consequences. To ensure a flawless transition, the Kroma team dedicated over six months to rigorous testing and simulations. Also, Kroma prioritized chain liveliness by implementing a zero-downtime migration process rather than taking the easier route of temporarily halting the network for migration.

Benefits of Using MPT and Future OP Stack Upstreaming

With the adoption of MPT, Kroma’s codebase is now much more aligned with the OP Stack, except for its unique and innovative validator system. Previously, Kroma’s reliance on zkEVM made it difficult to stay up to date with OP Stack improvements. This move removes these barriers, enabling faster upstreaming of OP Stack updates.

Next Steps for Kroma

The Kroma team has outlined the following roadmap for the near future:

• Upstream OP Stack: With a more streamlined codebase, Kroma will integrate the latest updates from the OP Stack more efficiently.
• Complete Proof System for Stage 1: Now that we have validated the L1 derivation pipeline, the only blocker for Stage 1 is resolving an issue where deletion of the output that lost a challenge leads to successive wins of challenger regardless of the correctness of the output following the deleted output.
• Develop a Multi-Proof System for Stage 2: Kroma aims to use multiple zkVMs to establish an on-chain provable bug detection mechanism. The Security Council would only act if proving results differ, which would indicate a bug in one of the zkVMs. With this multi-proof system, Kroma can aim for Stage 2.
• Kroma DAO Formation: In the long run, protocol upgrades should be governed by Kroma DAO rather than the Security Council. The team plans to introduce a detailed governance framework outlining the formation and operation of Kroma DAO.

Conclusion

The Kroma network’s upgrade to version v2.1.1+geth.v0.6.1 marks a significant leap forward in efficiency, maintainability and security. The move from zkEVM to zkVM, the adoption of MPT, and the choice of SP1 and the Succinct’s Prover Network collectively enhance Kroma’s capabilities while ensuring alignment with the OP Stack. Looking ahead, Kroma’s focus on upstreaming OP Stack, refining the proof system, and establishing a decentralized governance model through Kroma DAO will further solidify its position as a leading Layer 2 network.

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

Kroma’s transition to zkVM Fault Proof was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

GM Kroma Community!

In the fast-paced blockchain industry, it is important to establish a strong and competitive identity to solidify a project’s branding. What do you guys think of Kroma’s best standout identity in terms of Layer 2 branding?

In my personal opinion, is that; Kroma is a pioneer in fostering ‘Superchain Asia.’ Kroma is the first project that proposed the terminology ‘Superchain Asia’ to expand Superchain presence across Asia. Kroma already executed a series of Superchain Asia events in 2024 EDCON and KBW.

The goal of ‘Superchain Asia’ is to enhance the visibility of Superchain projects in Asia, foster collaboration among Superchain-related initiatives, and create a space for networking among professionals and developers interested in Superchain.

👩🏻‍💻 Superchain Asia Dev-Nexus

On January 11, the ‘Superchain Asia Dev-Nexus’ was held to encourage more builders to onboard into the Superchain ecosystem. Unlike previous Superchain events at EDCON and KBW, this event took a more developer-focused approach, diving deeper into how each project contributes to the Superchain ecosystem on the dev side and the technologies they are leveraging.

⚡️ Lightning Talk

Kroma — Harry: Bringing Mass to Web3 with Account Abstraction

Harry, the blockchain developer at Kroma, started the first lightning talk session about Account Abstraction (AA), emphasizing that the AA-integrated ‘Kroket’ (Web3 Quest App platform that Kroma is building) can bring mass adoption to the Superchain. He also pointed out that developing AA is the way Kroma contributes to the Superchain ecosystem.

Mint Blockchain — Rose: Unlocking the Future of NFTs: Scaling and Innovating with Mint Blockchain on the Superchain Ecosystem

Rose, the Head of the Ecosystem at Mint Blockchain, highlighted the achievements of the Mint Blockchain ecosystem and explained its NFT structure. She also shared exciting future plans, including grant opportunities for builders within the Mint ecosystem, emphasizing Mint Blockchain’s role as a bridge to onboard more builders into the broader Superchain ecosystem.

Soneium — Alan: ​How did we enable the interop from Astar to Soneium and finally Superchain?

Well NOW this is the ‘REAL’ dev-focused presentation I could say. Alan, a front-end engineer at Soneium, went through Optimism’s Superchain docs (Gitbook) in detail, providing clear instructions on how to start building on the Superchain. He examined the docs line by line, explaining how to implement and develop a roll-up solution based on the OP Stack for each project.

Uniswap — Gen: ​Road to Unichain Mainnet and how to get onboard

Gen, Korea Community Partner at Uniswap Labs, delivered a presentation answering every question she might get in the Q&A session (What is Unichain, Wen Unichain Mainnet, etc.), ensuring all their curiosities were covered. Furthermore, Gen introduced all of Uniswap’s grant programs to encourage more builders to join Unichain, contributing to the Superchain ecosystem’s expansion. Her perfect lightning talk expanded the future of Unichain users at that moment FOR SURE.

🎙️ Panel Talk

Topic: How was 2024 & What’s New in 2025 (Wrap-Up and Vision)

Alicia, the marketer at Kroma, took on the role of panel moderator and guided the discussion smoothly from start to finish.

Steve, a product manager at Kroma, joined the panel in this session and mentioned that Kroma had been very busy in 2024 with the launch of two products (Spectrum, KCU) and their listing at the end of last year. Alan from Soneium shared the key goals Soneium is focusing on as they head into 2025. While Rose from Mint introduced the plans for the Superchain Asia event in Taiwan hosted by them at the late January, she also mentioned Base as a Layer 2 project she would like to collaborate in 2025. Gen from Unichain was asked with the question that ‘Is Unichain an Ethereum killer?’, and she said that the increasing expectations from users for Unichain are making her excited as well.

🔥 Activity & Networking

There was also a fun activity at the end! We held a Dalgona game inspired by Squid Game, where participants had to carve out the shapes of the project logos. (I’m sure you can guess which logo was the easiest. lol) The top 5 fastest players who completed the game received surprise prizes. Compared to the formal and strict vibe of lightning talks, the panel talk and activity were light and casual, allowing participants to relax and enjoy the event fully.

One of the proudest moments for me as an event organizer was seeing people approach the lightning talk speakers during the networking session to ask questions. It was a sign that more builders and blockchain professionals are getting onboard with the Superchain ecosystem — which is exactly the goal of this event!

So!

This was the recap of Kroma’s third ‘Superchain Asia’ event. With each edition, we’re seeing projects grow within the Superchain ecosystem. The first event focused on introducing each project and how they onboarded on Superchain, while the second event explored their contribution plan to the ecosystem. Today, we dove deeper into the dev-focused ‘how’ of these contributions. I’m excited to see how the next event progresses. Ideally, it would be great to discuss the results of these contributions, or maybe hear from the marketing side! 👀

That’s all for now.

Thank you, community!

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

[Recap] Superchain Asia Dev-Nexus was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

Ashjeong작성, Ryan Kim 번역

해당 글은 Ryan Kim (@chokobole33), Baz (@0xBATZOR) 그리고 EthanYoo(@zkEthanYoo) 가 피드백과 리뷰를 해주셨고, 이에 대해 감사의 인사를 드립니다.

영문 버전의 글은 여기에서 확인할 수 있습니다.

목차

Preface

2-파티 GMW
• 불리언 게이트
• XOR
• AND

불리언 GMW 프로토콜 요약

n-파티 불리언 GMW
• 1 단계
• 2a 단계
• 2b 단계
• 총 AND 게이트 비용
• 3 단계

산술 회로

결론

Preface

오데드 골드리드(Oded Goldreid), 실비오 미칼리(Silvio Micali), 아비 위그더슨(Avi Wigderson)에 의해 만들어진 GMW는 n ≥ 2인 경우의 n-파티를 위한 불리언 또는 산술 회로용 다자간 연산(MPC) 프로토콜입니다. 이 글에서는 단순화를 위해 GMW에서 불리언 회로를 만드는 방법에 초점을 맞춥니다.

2-파티 GMW

우선 2-파티 GMW부터 시작해 보겠습니다. 두 파티, 즉 앨리스와 밥이 있고, 2개의 입력 비트(i와 j)가 하나의 불리언 게이트에 입력되며, 출력 비트는 k라고 가정해 보겠습니다.

GMW 프로토콜에서 각 파티는 자신이 알고 있는 입력 비트에 대해 다른 파티와 비밀 공유 과정을 거칩니다.

앨리스의 입력 비트 i의 경우, 앨리스는 밥에게 보낼 랜덤 비트 공유 sᵇᵢ ​를 선택합니다. 동시에 자신의 개인 비트 공유 sᵃᵢ​를 생성하며,이는 sᵃᵢ ⊕ sᵇᵢ = i를 만족합니다.

밥의 경우는 그 반대입니다. 밥은 앨리스에게 보낼 랜덤 비트 공유 sᵃⱼ​를 선택합니다. 이후 자신의 개인 비트 공유 sᵇⱼ​를 생성하며, 이는 sᵃⱼ⊕ sᵇⱼ = j를 만족합니다.

따라서 단일 게이트는 각 파티에 의해 다음과 같이 표현됩니다.

여기서 모든 파티의 출력은 최종 결과를 얻기 위해 모든 파티 간에 XOR 연산됩니다.

불리언 게이트

XOR와 AND 게이트로 전체 불리언 회로를 만들 수 있으므로, 2-파티 GMW 시스템에서 XOR와 AND 게이트를 어떻게 구현할 수 있는지 살펴보겠습니다.

XOR

XOR 게이트는 이 시나리오에서 매우 간단하게 구현할 수 있습니다. XOR 게이트란, 출력 k가 (i ⊕ j) = (sᵃᵢ⊕sᵇᵢ)⊕(sᵃⱼ⊕sᵇⱼ) = (sᵃᵢ⊕sᵃⱼ)⊕(sᵇᵢ⊕sᵇⱼ) 와 같다는 의미입니다. 즉, 각 파티는 자신의 공유값에 대해 XOR 연산을 수행할 수 있으며, 모든 파티의 최종 출력 값을 XOR 연산하여 전체 XOR 결과를 얻을 수 있습니다.

AND

AND 게이트를 구현하는 것은 약간 더 복잡합니다. AND 게이트의 출력 k 가 (i ⋀ j) = (sᵃᵢ⊕sᵇᵢ)⋀(sᵃⱼ⊕sᵇⱼ)이어야 하기 때문에, 각 파티가 단독으로 AND 게이트 출력의 일부를 계산할 수는 없습니다. 대신, 아래 논리적 동치 문장에 따라 (sᵃᵢ⊕sᵇᵢ)⋀(sᵃⱼ⊕sᵇⱼ)을 변환합니다.

결과 문장을 자세히 살펴보면, 전반부의 (sᵃᵢ⋀sᵃⱼ)와 (sᵇᵢ⋀sᵇⱼ) 부분은 앨리스와 밥 각각이 쉽게 계산할 수 있습니다. 하지만 후반부 (sᵃᵢ⋀sᵇⱼ)⊕(sᵇᵢ⋀sᵃⱼ)는 두 파티 간의 일부 통신이 필요해 보입니다.

이 후반부를 파티 간에 전달하기 위해, 한 파티를 송신자(앨리스)로, 다른 파티를 수신자(밥)로 설정합니다.

앨리스는 자신의 공유값 sᵃᵢ​와 sᵃⱼ​를 알고 있지만, 밥의 공유값 sᵇᵢ​와 sᵇⱼ​는 알지 못합니다. 그러나 앨리스는 밥의 각 공유값이 0 또는 1이라는 것을 알고 있습니다. 이를 바탕으로, 앨리스는 sᵇᵢ​와 sᵇⱼ​의 가능한 조합 (0, 0), (0, 1), (1, 0), (1, 1) 을 사용하여 (sᵃᵢ⋀sᵇⱼ)⊕(sᵇᵢ⋀sᵃⱼ)의 4가지 가능한 결과를 생성할 수 있습니다. 아래 표는 sᵃᵢ​와 sᵃⱼ​가 각각 0과 1일 때의 가능한 결과를 보여줍니다.

다음으로, 앨리스는 랜덤 비트 r (예: 여기서는 r = 0)을 생성하고, 모든 가능한 결과를 ⊕r로 계산하여 암호화합니다.

마지막으로, 앨리스는 이 “암호화된 가능한 결과” 표를 1-out-of-4 oblivious transfer (OT) 프로토콜로 전달합니다. 한편, 밥은 자신의 공유값 sᵇᵢ = 0, sᵇⱼ= 1을 같은 OT 프로토콜에 입력합니다. OT를 통해 밥은 자신의 공유값에 해당하는 r⊕((sᵃᵢ⋀sᵇⱼ)⊕(sᵇᵢ⋀sᵃⱼ) 값을 얻습니다. 이 과정에서 밥은 나머지 세 가지 암호화된 가능한 결과를 알 수 없으며, 앨리스도 밥이 어떤 값을 얻었는지 알 수 없습니다.

앨리스의 계산과 1-out-of-4 OT 프로토콜에서 밥과의 상호작용 결과로, 양쪽의 AND 게이트 결과를 결정할 수 있습니다. 앨리스는 자신의 AND 게이트 결과를 (sᵃᵢ⋀sᵃⱼ)에 랜덤 비트 r를 XOR한 값으로 설정합니다.밥은 자신의 AND 게이트 결과를 (sᵇᵢ⋀sᵇⱼ)에 OT 결과 r⊕(sᵃᵢ⋀sᵇⱼ)⊕(sᵇᵢ⋀sᵃⱼ)를 XOR한 값으로 설정합니다.결과적으로, 양쪽의 AND 게이트 결과를 XOR하면 랜덤 비트 r가 상쇄되어 (i ⋀ j)가 성공적으로 계산됩니다.

불리언 GMW 프로토콜 요약

따라서 GMW의 전체 프로세스는 다음과 같이 요약될 수 있습니다.

1. 모든 파티는 자신의 입력 비트에 대한 비밀 공유값을 서로 공유합니다.
2. 모든 파티는 회로를 개별적으로 계산합니다.
   a. XOR 게이트를 만나면, 각 파티는 자신의 입력 공유값을 XOR합니다.
   b. AND 게이트를 만나면, 각 파티는 모든 다른 파티와 1-out-of-4 OT를 수행하고 자신의 입력 공유값의 AND 결과에 이를 XOR합니다.
3. 모든 파티가 회로 계산을 완료하면, 각 파티의 최종 결과를 XOR하여 다자간 연산의 최종 결과를 얻습니다.

이 단계별 과정은 GMW가 n-파티(n ≥ 2)로 구현될 때도 동일하게 적용됩니다.

n-파티 불리언 GMW

n-파티 버전의 GMW에서 단계를 살펴보겠습니다.

“1. 모든 파티는 자신의 입력 비트의 비밀 공유값을 서로 공유합니다.”

여기서는 앨리스와 밥이 비밀 비트 공유값을 공유한 과정과 동일한 과정을 따릅니다.

예를 들어, 파티 1 (P₁​)이 알고 있는 랜덤 입력 비트 h에 대해, P₁​은 n−1n-1n−1개의 랜덤 비트 공유값 s²ₕ, s³ₕ,…, sⁿ⁻¹ₕ, sⁿₕ를 생성하여 다른 파티 P₂, P₃,…, Pₙ₋₁, Pₙ​에게 보냅니다. 이후 P₁​은 자신의 비트 공유값s¹ₕ​를 생성하며, 이는 h = s¹ₕ⊕s²ₕ⊕s³ₕ⊕…⊕sⁿ⁻¹ₕ⊕sⁿₕ을 만족합니다:

이 비트 공유 과정은 모든 파티의 모든 입력 비트에 대해 수행되며, 이를 통해 각 파티는 회로를 개별적으로 계산할 수 있도록 입력 비트의 공유값을 가지게 됩니다.

이제 2-파티 예제를 확장하여 앨리스, 밥에 캐롤을 추가해 3-파티 예제를 살펴보겠습니다.

“2a. XOR 게이트가 있는 경우, 각 파티는 자신의 입력 공유값을 XOR 연산합니다.”

실제로, 2-파티 설명과 마찬가지로, 각 파티는 자신의 공유값을 서로 XOR 연산하여 개인적인 XOR 연산 결과를 도출합니다. 이후, 모든 파티의 결과를 XOR 연산하면 최종 XOR 다자간 계산 결과가 도출됩니다.

“2b. AND 게이트가 있는 경우, 각 파티는 1-out-of-4 OT를 통해 다른 모든 파티와 통신하고, 자신의 입력 공유값의 AND 결과에 OT 결과를 XOR 연산합니다.”

2-파티 버전에서 사용된 논리적 동치 문장은 다음과 같이 일반화할 수 있습니다:

우리의 비트 공유 표현으로, 이는 다음과 같습니다:

2-파티 예제와 마찬가지로, 노란색으로 표시된 부분은 각 파티가 자신의 계산만으로 수행할 수 있는 영역(즉, “…자신의 입력 공유값의 AND”)이고, 파란색으로 표시된 부분은 두 파티 간의 통신이 필요한 영역입니다. 더 구체적으로, 파란색 부분은 다음과 같이 그룹화할 수 있습니다:

첫 번째 부분 (sᵃᵢ⋀sᵇⱼ)⊕(sᵇᵢ⋀sᵃⱼ)은 2-파티 예제에서 앨리스와 밥 사이에 OT를 사용한 문장과 동일합니다. 두 번째 부분 (sᵇᵢ⋀sᶜⱼ)⊕(sᶜᵢ⋀sᵇⱼ)은 밥과 캐롤 간의 OT가 필요하며, 세 번째 부분 (sᵃᵢ⋀sᶜⱼ)⊕(sᶜᵢ⋀sᵃⱼ)은 앨리스와 캐롤 간의 OT가 필요합니다.
(“…각 파티는 다른 모든 파티와 1-out-of-4 OT를 통해 통신합니다…”).

따라서 n-파티 간 최종 AND 결과는 각 파티의 개별 계산 결과에 다른 모든 파티와의 OT 결과를 XOR 연산한 값이 됩니다. 모든 파티 간의 OT 쌍을 도식화하기 어려우므로, 아래 그림에서는 앨리스, 밥, 캐롤의 3-파티 예제만을 보여줍니다:

총 AND 게이트 비용

조금 한 발 떨어져서, 전체 회로에서 파티 간 통신 비용을 생각해 봅시다. XOR 게이트는 통신 비용이 없단는 걸 기억해주시기 바랍니다.

Since all AND gates at the same level can be run in parallel (such as AND gates 1 and 2 in the figure above), yet all AND gates in succession must be run in order (as in AND gate 1 must be computed before AND gate 3 in the figure above), the total number of rounds of communication between parties equals the depth of the circuit in terms of AND gates (depth = 2 in the figure above). Additionally, each AND gate requires Cⁿ₂ = (n(n-1))/2 total OT processes to take place (total number of unique party pairs). This means that in total, there are (depth of the circuit in terms of AND gates) * (n(n-1))/2 total OTs occurring in a given circuit, a significant communication cost for a circuit with many AND gates.

모든 AND 게이트가 같은 레벨에 있다면(위 그림에서 AND 게이트 1과 2처럼) 병렬로 실행될 수 있습니다. 하지만 연속적으로 배치된 AND 게이트는 차례대로 실행되어야 합니다(위 그림에서 AND 게이트 1이 계산된 후에야 AND 게이트 3을 계산할 수 있음). 따라서 파티 간의 총 통신 라운드 수는 회로의 AND 게이트에 대한 깊이(위 그림에서 깊이 = 2)와 같습니다. 추가적으로, 각 AND 게이트는 총 Cⁿ₂ = (n(n-1))/2개의 OT 프로세스를 필요로 합니다(고유한 파티 쌍의 총 수). 이 말은, 주어진 회로에서 발생하는 총 OT의 수는 (AND 게이트에 대한 회로 깊이) * (n(n-1))/2 와 같다는 말입니다. AND 게이트가 많은 회로의 경우, 이는 상당한 통신 비용이 될 수 있습니다.

“3. 모든 파티가 회로 계산을 마치면, 각 파티의 최종 결과를 XOR 연산하여 다자간 계산의 최종 결과를 도출합니다.”

위 문장에서 설명된 것처럼, 모든 파티의 회로 최종 결과는 XOR 연산되어 전체 결과를 도출합니다. 이는 각 파티가 자신의 중간 결과를 다른 파티에 노출하지 않는다는 것을 의미합니다.

산술 회로

While I showed the boolean version of GMW, this protocol also works for arithmetic circuits. Instead of XOR and AND gates, arithmetic circuits use addition and multiplication gates. Additionally, while the secret shares for an input h are calculated as s¹ₕ⊕s²ₕ⊕s³ₕ⊕…⊕sⁿ⁻¹ₕ⊕sⁿₕ for the boolean version, for the arithmetic version, hequals s¹ₕ+s²ₕ+s³ₕ+…+sⁿ⁻¹ₕ+sⁿₕ. Therefore, the addition operation will become free (like how XOR gates are free) and the multiplication operation requires communication between parties (similar to AND gates).

앞서 GMW의 불리언 버전을 설명했지만, 이 프로토콜은 산술 회로에도 적용됩니다. 불리언 회로에서 XOR와 AND 게이트를 사용하는 대신, 산술 회로는 덧셈과 곱셈 게이트를 사용합니다.또한, 입력 h에 대한 비밀 공유값이 불리언 버전에서는 s¹ₕ⊕s²ₕ⊕s³ₕ⊕…⊕sⁿ⁻¹ₕ⊕sⁿₕ​로 계산되지만, 산술 버전에서는 s¹ₕ+s²ₕ+s³ₕ+…+sⁿ⁻¹ₕ+sⁿₕ로 계산됩니다. 따라서, 덧셈 연산은 XOR 게이트처럼 통신 비용이 없는 “무료” 연산이 되며, 곱셈 연산은 AND 게이트와 마찬가지로 파티 간 통신이 필요합니다.

결론

GMW는 비밀 공유 개념에 기반하여 XOR 게이트가 무료이고 AND 게이트가 비용이 드는 독창적인 n-파티 MPC 프로토콜로 자리 잡고 있습니다. 프로토콜 시작 시, 각 AND 게이트에서, 그리고 회로 계산 종료 시에 파티 간 통신이 필요합니다.

읽어주셔서 감사합니다! 다음 MPC 아티클에서 만나요~

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

GMW: 입력값 쉐어와 커뮤니케이션 was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

We’re thrilled to introduce Kroket, our brand-new Web3 app that makes earning rewards easy, fun, and engaging. Whether you’re a Web3 enthusiast or totally new to it, Kroket is here to make Web3 tech accessible to everyone.

🎉 Turning Everyday Tasks into Real World Rewards

With Kroket, you can complete simple tasks like quizzes, mini-games, or other fun missions to earn points. These points can be turned into digital assets like KRO and OP or exchanged for real-world rewards like coupons and vouchers. It’s our way of turning everyday activities into something more rewarding!

🔑 Simplifying Web3 with Kroma ID

At the heart of Kroket is Kroma ID, our solution for making Web3 interactions smoother. Forget the hassle of managing private keys or worrying about gas fees — we’ve got that covered. Kroma ID lets you navigate Web3 effortlessly, using any token for gas payments while interacting with dApps in just a few clicks.

🤝 Growing the Web3 Ecosystem

But Kroket isn’t just about rewards — it’s also about growing the Web3 ecosystem. We’re working with amazing dApps to connect them with engaged, high-quality users. By building these partnerships, we’re helping developers reach verified users, drive real utility, and create meaningful connections that keep users coming back.

🚀 What’s Next for Kroket?

And we’re just getting started! Coming soon to Kroket:

• Kropet, a gamified feature where you can care for virtual pets and earn rewards.
• More interactive content and educational resources to help you dive deeper into the world of Web3.

📲 Start Earning Today

Ready to jump in? Download Kroket today at https://kroket.app and start earning rewards while exploring Web3 in the most intuitive way possible.

“Kroket is more than just an incentive-based app,” said TK, CEO of Kroma. “It is designed to allow users to experience Web3 naturally, without requiring a deep understanding of complex technologies. We hope that more people will discover the convenience and possibilities of Web3 while enjoying tangible benefits through Kroket.”

This is just the beginning of what’s possible with Kroket. We’re here to make Web3 practical, enjoyable, and accessible to everyone. Whether you’re diving in for the first time or exploring new possibilities, Kroket is your gateway to the decentralized world.

Read more in the press release here.

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

Kroma Just Launched ‘Kroket,’ the Incentive-Driven Web3 App was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

Ryan Kim (@chokobole33) 작성

해당 글은 Ashjeong, fakedev9999 (@fakedev9999) 그리고 Baz (@0xBATZOR) 가 피드백과 리뷰를 해주셨고, 이에 대해 감사의 인사를 드립니다.

영문 버전의 글은 여기에서 확인할 수 있습니다.

초록

이 문서는 Brakedown 프로토콜의 목표와 과정을 직관적으로 설명하는 것을 목표로 합니다.

목차

• 서론

• 배경
- 왜 Merkle Tree 연산을 사용하는가?
- 선형 코드(Linear Code)
- 텐서 곱(Tensor Product)

• 프로토콜 설명
- 간단한 개요
- 선형 시간 인코딩(Linear-time Encoding)
- 희소 다중 선형 다항식(Sparse Multilinear Polynomial) 에 대한 선형 시간 커밋
- R1CS 를 Sumcheck 로 치환

• 결론

서론

Brakedown 은 “R1CS 에 대한 증명을 가능한 한 빠르게 생성하려면 어떻게 해야 하는가?”라는 질문에서 시작됩니다. 이 프로토콜은 O(N) 필드 연산으로 증명 생성을 달성할 수 있는 스킴을 제시합니다. 이를 위해 선형 시간으로 작동하는 인코딩 방식을 도입합니다. 유사한 기술이 BCG 에서도 사용되었지만, Brakedown 은 보다 실용적인 접근으로 차별화됩니다. 또한 신뢰 설정(trusted setup)을 요구하지 않으며, 양자 저항성을 제공할 수 있고, 필드 독립적(field-agnostic)이어서 더욱 실용적입니다.

배경

왜 Merkle Tree 연산을 사용하는가?

O(N) 길이의 벡터에 대해 커밋할 때, 관련된 연산의 복잡도는 일반적으로 다음과 같습니다:

• FFT 연산 → O(N⋅log⁡N) 필드 연산
• Merkle Tree 연산 → O(N) 해시 연산
• MSM 연산 → Pippenger 알고리즘을 사용할 경우, O(N⋅λ/log⁡(N⋅λ)) 그룹 연산

O(N)을 달성하기 위해 O(N⋅log⁡N)인 FFT 연산은 사용할 수 없습니다. 마찬가지로, 그룹 연산이 필드 연산보다 느리기 때문에 MSM 연산도 피해야 합니다. 대신, 커밋을 위해 Merkle Tree 연산이 사용됩니다.

선형 코드(Linear Code)

코드워드의 선형 결합이 역시 코드워드가 되는 경우, 해당 코드는 선형 코드라고 합니다.

일반적으로 사용되는 Reed-Solomon (RS) 코드는 이 속성을 만족하며, 따라서 선형 코드입니다. (이 속성 덕분에 RS 기반 FRI에서 폴딩 연산을 사용할 수 있습니다.)

RS 코드에서 전통적으로 사용되는 인코딩 함수는 FFT 연산을 포함합니다. 그러나 앞서 언급한 제한으로 인해 다른 인코딩 방법을 찾아봐야 합니다.

텐서 곱(Tensor Product)

텐서 곱은 서로 다른 벡터 공간에서 벡터 v 와 u 의 모든 가능한 조합을 생성하는 연산입니다. 예를 들어, q₁ = [a, b] 이고 q₂ = [x, y, z] 인 경우, 두 벡터 간의 텐서 곱은 다음과 같은 행렬이 됩니다:

또한, 텐서 곱은 다음과 같이 Multi Linear Extension (MLE) 계산을 표현하는 데 사용될 수 있습니다:

예를 들어 l = 2 일 때, MLE 는 다음과 같이 계산됩니다:

프로토콜 설명

간단한 개요

프로토콜은 크게 커밋 단계, 테스트 단계, 평가 단계의 세 단계로 나뉩니다.

커밋 단계

이 단계에서는 입력 행렬에 커밋하며, 다음 과정을 거칩니다:

1. 행렬 u 가 입력으로 주어지며, 여기서 uᵢ ​는 i-번째 행을 나타냅니다.

2. 주어진 비율 ρ 에 따라, 길이가 c 인 각 행이 길이가 N 인 행으로 인코딩되어 r×N 행렬 û 가 생성됩니다. 증명자는 이 û 행렬을 Merkle 해시를 사용하여 검증자에게 커밋합니다.

테스트 단계

이 단계에서는 인코딩이 올바르게 수행되었는지를 검증하며, 다음 과정을 포함합니다:

1. 검증자는 랜덤 값 α 를 샘플링하여 증명자에게 보냅니다.

2. 증명자는 α 를 사용하여 u′ 를 계산하고 이를 검증자에게 보냅니다.

3. 검증자는 1 에서 N 사이의 값을 l 개 샘플링하여 다음 등식을 테스트합니다:

이 등식은 코드워드가 선형 코드이기 때문에 성립합니다. 즉, 행렬의 행들을 먼저 인코딩한 후 RLC 를 수행하는 것과, 먼저 RLC 를 수행한 후 인코딩하는 것이 동일합니다.
“Concrete Optimizations to the Commitment Scheme(Section 4)” 에 따르면, 다항식 커밋 스킴을 사용하는 경우 테스트 단계를 생략할 수 있습니다.

계산 단계

이 단계는 테스트 단계와 동일한 검사를 수행하지만 인코딩 없이 진행되며, 다음 과정을 포함합니다:

1. 검증자는 q₁ ​∈ Fʳ 을 샘플링합니다.

2. 증명자는 u′′ 를 계산하여 검증자에게 보냅니다. (테스트 단계의 2와 동일합니다.)

3. 검증자는 q₂ ​∈ Fᶜ 을 샘플링하여 다음 등식을 테스트합니다: (테스트 단계의 3과 동일합니다.) 여기서 q₁ ​과q₂ ​의 텐서 곱이 벡터로펼쳐집니다.

예를 들어, r = 2 이고 c = 2 일 때, 다음과 같은 이유로 등식이 성립합니다:

분석

증명 생성 시간은 인코딩 및 커밋 연산에 따라 달라집니다. Merkle Tree 가 커밋에 사용되므로, 인코딩이 선형 시간 내에 수행되면 전체 실행 시간은 O(N) 입니다.

증명 구조는 다음으로 구성됩니다:

• c: 테스트 단계 2 및 계산 단계 3 에서 사용되는 필드.
• r⋅l: 테스트 단계 3 및 계산 단계 4 에서 샘플링된 필드.
• α: l 개의 쿼리에 필요한 오프닝 증명 크기.

검증 시간은 O(r⋅l) 입니다. 증명 생성은 빠르지만, 증명 크기와 검증 시간은 r 에 비례합니다.

선형 시간 인코딩(Linear-time Encoding)

The figure above illustrates the linear-time encoding method used in Brakedown. For a given rate ρ, Enc(x) is a function that generates a vector of length n⋅ρ⁻¹ from an input vector x of length n. The output is divided into three parts: (x, z, v). The encoding Enc(x) proceeds as follows:

위 그림은 Brakedown 에서 사용되는 선형 시간 인코딩 방법을 보여줍니다. 주어진 비율 ρ 에 대해, Enc(x) 는 길이 n 의 입력 벡터 x 로부터 길이 n⋅ρ⁻¹ 의 벡터를 생성하는 함수입니다. 출력은 (x, z, v) 세 부분으로 나뉩니다. Enc(x) 의 인코딩은 다음과 같이 진행됩니다:

Vec Enc(Vec x) {
  if (x.size() < 900) {
    // 논문 5장에서 언급했듯이,임계값은 900으로 설정됩니다.
    // RS encoding 의 계산 오버헤드가 입력 크기의 제곱에 비례하지만, 
    // 이 부분의 시간 기여가 미미하기 때문에 허용됩니다.
    return RSEnc(x);
  }
  // A 는 희소행렬입니다.
  Matrix A = SampleMatrixA();
  CHECK_EQ(A.rows(), x.size());
  CHECK_EQ(A.cols(), kAlpha * x.size());
  Vec y = x * A ;
  Vec z = Enc(y);
  // B 는 희소행렬입니다.
  Matrix B = SampleMatrixB();
  CHECK_EQ(B.rows(), z.size());
  CHECK_EQ(B.cols(), (kRateInv * - 1 - kAlpha * kRateInv) * x.size());
  Vec v = z * B;
  return Concatenate(x, z, v);
}

인코딩된 출력의 속성

인코딩 결과 w = Enc(x) 에 대해, 매개변수 β 가 주어질 때 zero norm ∥w∥₀ 과 거리 δ 는 다음과 같이 정의됩니다:

해밍 가중치(Hamming weight)라고도 알려진 zero norm 은 x 에서 0이 아닌 요소의 개수를 나타냅니다:

인코딩의 실행 시간은 입력 벡터 x 의 길이에 비례합니다. 이 인코딩 방법과 관련된 증명은 논문 5.1장에서 자세히 설명되어 있습니다.

희소 다중선형 다항식에 대한 선형 시간 커밋

희소 다중 선형 다항식(Sparse Multilinear Polynomial) 에 대한 선형 시간 커밋

Spartan 의 기법을 사용하여 입력 벡터를 선형 시간 안에 커밋할 수 있습니다.

벡터를 희소 행렬로 표현

예를 들어, 벡터를 다음과 같은 행렬로 변환할 수 있습니다.

• 행(Row) = 4
• 열(Column) = 4
• 0이 아닌 요소(N) = 4
• 전체 요소(M) = 16

단순히 기본 다항식 커밋 스킴을 사용하는 경우 계산 복잡도는 O(M) 이 됩니다.

행렬의 희소 표현

희소 표현은 R, C, V를 사용하여 다음과 같이 정의됩니다:

1. R,C,V 의 각 행은 희소 행렬에서 하나의 0 이 아닌 항목을 정의합니다.
2. M_{Rᵢ,Cᵢ}=Vᵢ

희소 다항식 D 정의

희소 다항식 D 는 다음과 같이 정의됩니다:

이전 예제를 기반으로 row ,col, val 및 b⁻¹ 은 다음과 같이 계산됩니다.

그러므로 D 는 다음과 같이 계산됩니다:

커밋 및 오프닝 단계

1. rₓ​ 및 rᵧ ​가 주어졌을 때, 증명자는 오라클 Eᵣₓ​ 및 Eᵣᵧ ​를 제공합니다.

2. 증명자와 검증자는 다음 식에 대해 sumcheck 프로토콜을 수행합니다:

3. sumcheck의 마지막 라운드에서 검증자는 다음을 확인합니다:

증명자의 Eᵣₓ​ 및 Eᵣᵧ​ 주장 검증을 위해 오프라인 메모리 검증(Offline Memory Checking)방법이 사용됩니다. (자세한 내용은 논문 6장의 Detour: offline memory checking을 참조하십시오.)

R1CS를 Sumcheck 로의 치환

Brakedown 은 R1CS 를 위한 증명 스킴입니다. sumcheck 프로토콜은 Brakedown의 핵심이기 때문에, R1CS는 sumcheck 형식으로 치환되어야 합니다. R1CS는 다음과 같이 정의됩니다:

이는 다음과 같이 sumcheck 형식으로 변환될 수 있습니다 (설명을 단순화했으며, 자세한 내용은 논문 7장을 참조하십시오):

결론

Brakedown 은 R1CS 에 대한 증명 생성을 위해 선형 시간 인코딩 및 선형 시간 커밋을 도입하여 O(N) 필드 연산으로 증명 생성을 가능하게 합니다. 그러나 앞서 언급했듯이, 증명의 크기가 크고 검증 시간이 느리다는 단점이 있습니다. 이러한 특성은 다음 결과에서 명확히 드러납니다:

위 그림은 논문에서 발췌한 것으로, Brakedown 의 다항식 커밋 스킴 성능을 벤치마크한 결과를 보여줍니다. 그림에서 알 수 있듯이, Commit 및 Open 연산은 Ligero 만큼 빠르지만, Verify 및 Communication 단계는 비교된 스킴들 중 가장 느립니다.

This figure, also taken from the paper, shows that Brakedown achieves the fastest Prove time and is among the fastest for Encode time. However, it also confirms that Verify remains slow, and the Proof Size is the largest.

또 다른 그림은 Brakedown 이 가장 빠른 Prove 시간을 달성했으며, Encode 시간에서도 가장 빠른 수준임을 보여줍니다. 그러나 Verify 시간이 여전히 느리고, Proof Size 가 가장 크다는 점도 확인됩니다.

Brakedown은 이후 개선되어 Orion, Orion+, Vortex 그리고 Binius 등의 후속 작업에 사용되었습니다.

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

Brakedown 분해하기 was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

Written by Ryan Kim (@chokobole33)

Special thanks to Ashjeong (Ashjeong), fakedev9999 (@fakedev9999), Baz (@0xBATZOR) for feedback and review.

This article is also available in Korean.

Abstract

This document aims to intuitively explain the goals and processes of the Brakedown protocol.

Table of Contents

• Introduction

• Background
- Why use Merkle Tree operations?
- Linear Code
- Tensor Product

• Protocol Explanation
- Brief Overview
- Linear-time Encoding
- Linear-time Commitments for Sparse Multilinear Polynomial
- Reduction of R1CS to Sumcheck

• Conclusion

Introduction

Brakedown originates from the question, “How can we generate proofs for R1CS as quickly as possible?” It presents a scheme that achieves proof generation with O(N) field operations. To accomplish this, it introduces a method of encoding that operates in linear time. While similar techniques were used in BCG, Brakedown distinguishes itself by being more practical. Additionally, it does not require a trusted setup, may offer quantum resistance, and is field-agnostic, making it more practical.

Background

Why use Merkle Tree operations?

When committing to an O(N)-length vector, the operations involved generally have the following complexities:

• FFT Operations → O(N⋅log⁡N) field operations
• Merkle Tree Operations → O(N) hash operations
• MSM Operations → Using Pippenger’s algorithm, O(N⋅λ/log⁡(N⋅λ)) group operations

To achieve O(N), FFT operations, which are O(N⋅log⁡N), cannot be used. Similarly, MSM operations are avoided because group operations are slower than field operations. Instead, Merkle Tree operations are utilized for commitment.

Linear Code

If the linear combination of codewords is also a codeword, the code is called a linear code.

Reed-Solomon (RS) codes, which are commonly used, satisfy this property and are therefore linear codes. (This property allows the folding operation to be used in RS-based FRI.)

The traditional encoding function used in RS-codes involves FFT operations. However, due to the limitations mentioned earlier, alternative encoding methods must be explored.

Tensor Product

The Tensor Product is an operation that generates all possible combinations of two vectors v and u from different vector spaces. For example, if q₁ = [a, b] and q₂ = [x, y, z], the tensor product between the two is the following matrix:

Additionally, the tensor product can be used to express a Multi Linear Extension (MLE) evaluation like so:

For example, when l = 2, the MLE evaluation is calculated as follows:

Protocol Explanation

Brief Overview

The protocol is divided into three phases: Commitment Phase, Testing Phase and Evaluation Phase.

Commitment Phase

This phase commits to the input matrix, with the following steps:

1. A matrix u is provided as an input, where uᵢ represents the i-th row.

2. For a given rate ρ, each row of length c is encoded into a row of length N, producing an r×N matrix û. The prover commits this û matrix to the verifier using Merkle hash.

Testing Phase

This phase verifies whether the encoding was performed correctly, with the following steps:

1. The verifier samples a random scalar α and sends it to the prover.

2. The prover computes u′ using the random value α and sends it to the verifier:

3. The verifier tests the following equality by sampling l values between 1 and N:

This holds because the codeword is linear code. That is, encoding the rows of the matrix and then performing RLC is equivalent to performing RLC first and then encoding.
According to Section 4, “Concrete Optimizations to the Commitment Scheme,” the testing phase can be skipped if a Polynomial Commitment Scheme is used.

Evaluation Phase

This phase performs identical checks as in the testing phase but without encoding, with the following steps:

1. The verifier samples q₁ ​∈ Fʳ.

2. The prover computes u′′ and sends it to the verifier: (Identical to Testing Phase 2.)

3. The verifier tests the following equality by sampling q₂ ​∈ Fᶜ: (Identical to Testing Phase 3.) Here, tensor product between q₁ and q₂ are flattened to the vector.

For example, when r = 2 and c = 2, the equation holds due to the following reasoning:

Analysis

The proof generation time depends on the encoding and commitment operations. Since Merkle Tree is used for commitments, as long as encoding is performed in linear time, the overall execution time is O(N).

The proof structure consists of:

• c: Fields used in Testing Phase Step 2 and Evaluation Phase Step 3.
• r⋅l: Fields sampled during Testing Phase Step 3 and Evaluation Phase Step 4.
• α: Opening proof size required for l-queries.

Verification time is O(r⋅l). While proof generation is fast, the proof size and verification time is directly proportional with r.

Linear-time Encoding

The figure above illustrates the linear-time encoding method used in Brakedown. For a given rate ρ, Enc(x) is a function that generates a vector of length n⋅ρ⁻¹ from an input vector x of length n. The output is divided into three parts: (x, z, v). The encoding Enc(x) proceeds as follows:

Vec Enc(Vec x) {
  if (x.size() < 900) {
    // As mentioned in Section 5 of the paper,
    // the threshold is set at 900.
    // Quadratic-time operations are acceptable here
    // since their time contribution is negligible.
    return RSEnc(x);
  }
  // A is a sparse matrix.
  Matrix A = SampleMatrixA();
  CHECK_EQ(A.rows(), x.size());
  CHECK_EQ(A.cols(), kAlpha * x.size());
  Vec y = x * A ;
  Vec z = Enc(y);
  // B is a sparse matrix.
  Matrix B = SampleMatrixB();
  CHECK_EQ(B.rows(), z.size());
  CHECK_EQ(B.cols(), (kRateInv * - 1 - kAlpha * kRateInv) * x.size());
  Vec v = z * B;
  return Concatenate(x, z, v);
}

Properties of the Encoded Output

For the encoded result w = Enc(x), given the parameter β, the zero norm ∥w∥₀ and distance δ are given by:

The zero norm, also known as Hamming weight, represents the number of non-zero elements in x:

The execution time of encoding is proportional to the input vector x’s length. Proofs related to this encoding method are detailed in Section 5.1 of the paper.

Linear-time Commitments for Sparse Multilinear Polynomials

Using techniques from Spartan, the input vector can be committed in linear time.

Representing the Vector as a Sparse Matrix

For example, the vector can be converted into a matrix as follows. Here, Rows = 4, Cols = 4, Non-zero Elements (N) = 4, Total Elements (M) = 16:

Simply using a naive polynomial commitment scheme would require a computational complexity of O(M).

Sparse Representation of the Matrix

The sparse representation is defined using R, C and V as the following:
1. Each row of R,C,V defines a single non-zero entry in the sparse matrix.

2. M_{Rᵢ,Cᵢ}=Vᵢ

Defining Sparse Polynomial D

The sparse polynomial D is defined as:

Here is an example calculation of row, col, val and b⁻¹ based on the previous example of a sparse matrix.

Therefore, D will be calculated as so:

Commitment and Opening Steps

1. Given rₓ and rᵧ, the prover provides oracles Eᵣₓ and Eᵣᵧ:

2. The prover and verifier perform a sumcheck protocol for the equation:

3. At the final round of sumcheck, the verifier checks the following:

To verify the prover’s claims of Eᵣₓ and Eᵣᵧ, an Offline Memory Checking method is employed (refer to Detour: offline memory checking in Section 6 of the paper for details).

Reduction of R1CS to Sumcheck

Brakedown is a proving scheme for R1CS. Since the sumcheck protocol is integral to Brakedown, R1CS must be reduced to a sumcheck format. R1CS is defined as:

This can be converted into a sumcheck format as follows (simplified for illustration; see Section 7 for details):

Conclusion

Brakedown introduces linear-time encoding and linear-time commitment for generating proofs for R1CS, enabling proof generation with O(N) field operations. However, as mentioned earlier, the proof size is large, and the verification time is slow. These characteristics are evident in the following results:

The above figure, taken from the paper, benchmarks the performance of Brakedown’s Polynomial Commitment Scheme. As shown, while Commit and Open operations are as fast as Ligero, the Verify and Communication stages are the slowest among the compared schemes.

This figure, also taken from the paper, shows that Brakedown achieves the fastest Prove time and is among the fastest for Encode time. However, it also confirms that Verify remains slow, and the Proof Size is the largest.

Brakedown has since been improved and used in subsequent works, including Orion, Orion+, Vortex, and Binius.

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

Let’s break down Brakedown was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

Baz (@0xBATZOR) 작성, Ryan Kim (@chokobole33)번역

해당 글은 Ryan Kim (@chokobole33), Ashjeong, fakedev9999 (@fakedev9999) 그리고 EthanYoo (@zkEthanYoo)가 피드백과 리뷰를 해주셨고, 이에 대해 감사의 인사를 드립니다.

영문 버전의 글은 여기에서 확인할 수 있습니다.

Motivation

유한체(finite field)를 선택할 때 다음 요소들 사이에서 균형을 맞추는 트레이드오프가 존재합니다:

1. 효율적인 산술 구현: 메르센 소수와 같은 특수한 형태의 작은 크기의 소수체는 표준 하드웨어 아키텍처에서 더 빠른 산술 연산을 가능하게 합니다.
2. 효율적인 FFT 지원: STARK 의 인코딩 프로세스에 필수적인 효율적인 FFT 를 지원하려면, 유한체가 2-adicity 가 큰 부분군을 포함하는 smooth 한 곱셈군(multiplicative subgroup)을 가져야 합니다.

산술 연산에 가장 효율적인 필드 중 하나인 메르센 필드로, 이는 p = 2ᵉ − 1 형태의 소수로 정의됩니다. 특히 p=²³¹−1 는 32-비트 아키텍처에서 매우 효율적인 산술을 제공합니다.

2³² = 2 mod ²³¹ — 1이므로, 2³²⋅xₕᵢ+xₗₒ ​로 인코딩된 넓은 곱은 2⋅x ​ₕᵢ+xₗₒ 로 간단히 축소됩니다. 그러나 p−1=2⋅3²⋅7⋅11⋅31⋅151⋅331 이므로, 곱셈군은 효율적인 Cooley-Tukey Fast Fourier Transforms (FFT)에 유용한 2-adicity 부분군을 포함하지 않습니다.

Circle Group

p = 3 mod 4 일 때, 복소수 확장체 Fₚ/(X²+1) 는 다음과 같이 정의될 수 있습니다.

p = 1 mod 4일 경우, X² + 1 = 0 은 해를 가지며, 이는 르장드르 기호(egendre Symbol) 에 따라 −1/p=(−1)^{(p−1)/2}=1 이기 때문입니다. 이는 −1 이 이차 잉여(quadratic residue)임을 의미하며, X² + 1은 (X−a)(X+a) 로 표현될 수 있어 Fₚ/(X²+1) 가 체(field)가 되지 않음을 나타냅니다.

Fₚ​ 위의 단위 원(unit circle)은 대수적 집합 C(Fₚ)={(x,y)∈Fₚ² : x²+y²=1} 또는 복소수 표현으로 다음과 같이 정의됩니다:

z̄ 는 z̄=x+iy 의 켤레 복소수 x−iy 를 나타냅니다.

보조정리 1 (Unit Circle Group): Fₚ 를 p=3 mod 4 인 소수체라고 하자. 그러면 단위 원 군 C(Fₚ​​) 는 C(Fₚ​)ᕽ 에서의 (p+1)-th roots of unity 와 같으며, 차수(order)는 p+1 입니다.

증명: zᵖ=(x+iy)ᵖ=xᵖ+(iy)ᵖ=x+(iᵖ)y=x−iy=zˉ이므로 x²+y²=z⋅zˉ=zᵖ+1 입니다. 따라서 C(Fₚ)={z∈C(Fₚ​)ᕽ:zᵖᐩ ¹ =1} 이며, 이는 (p+1)-roots of unity 의 집합을 의미합니다. ∣C(Fₚ)×∣=p²−1 이 p+1 로 나누어떨어지므로, 단위 원 군은 차수가 p+1인 유일한 부분군이어야 합니다.

Group Operations

C(Fₚ) 의 p+1 개의 점은 다음과 같은 군 연산을 통해 군을 형성합니다:

이 식은 cos(α+β) 와 sin(α+β) 공식을 닮았으며, 단위 원 위에서의 회전에 해당합니다.

이 군의 항등원(identity element)은 (1,0) 이며, P=(Pₓ​,Pᵧ​)∈C(Fₚ)에 대해, P 에 의한 변환(회전)을 정의할 수 있습니다.

군 연산에 따른 제곱 함수는 이차 함수(quadratic map)로 표현됩니다.

군의 역원(inverse)은 다음과 같은 1차 함수로 주어집니다: J(x,y):=(x,−y)

따라서 π 는 x-축과 이루는 각도를 두 배로 증가시키는 연산으로 생각할 수 있고, J는 x-축에 대한 대칭으로 해석될 수 있습니다.

Twin-coset and Standard Position Coset

먼저 그림 2는 원 군(circle group)에서의 부분군(subgroup)을 보여줍니다.

부분군의 코셋(coset)을 취한다는 것은, 해당 부분군의 각 점을 동일한 양만큼 회전시키는 것을 의미합니다.

정의 n≥1일 때, Gₙ₋₁ 을 |Gₙ₋₁|​=2ⁿ⁻¹인 C(Fₚ) 의 순환 부분군(cyclic subgroup)이라고 합시다. 서로소(disjoint) 집합 Q⋅Gₙ₋₁​∩Q⁻¹⋅Gₙ₋₁​=∅ 의 합집합인 D=Q⋅Gₙ₋₁​∪Q⁻¹⋅Gₙ₋₁​​ 를 크기가 N=2ⁿ 인 twin-coset 이라고 부릅니다.

주목 Twin-coset 에 대한 역원 연산은 자기 자신으로 매핑됩니다.

정의 Gₙ₋₁​​ 의 twin-coset D 가 다시 Gₙ ​​의 코셋이 되는 특수한 경우 D 를 standard position coset 이라고 부릅니다.

논문에서의 보조정리 3: n≥2 일 때 크기가 2ⁿ 인 twin-coset D 의 π(D) 는 크기가 2ⁿ⁻¹ 인 twin-coset 입니다. 또한 D 가 standard position coset 이라면, π(D) 도 standard position coset 입니다.

증명: π(D)=π(Q⋅Gₙ₋₁∪Q⁻¹⋅Gₙ₋₁)=π(Q)⋅ Gₙ₋₂ ∪ π(Q⁻¹)Gₙ₋₂ ​ 그리고 만약 D=Q⋅Gₙ ​이 standard position cose t이라면 π(Q⋅Gₙ)=π(Q)⋅Gₙ₋₁​ 이므로 π(D) 도standard position coset 입니다.

다항식들의 공간(Space of Polynomials)

정의 F 를 Fₚ ​의 확장체라고 하자. 원 곡선(circle curve) 위에서,n≥0 인 짝수 n 에 대해, Lₙ(F) 를 F 의 계수를 가지며 전체 차수가 N/2 이하인 이변수(bi-variate) 다항식들의 공간으로 정의합니다.

Circle STARK 에서, Lₙ(F) 의 이변수 다항식은 고전적인 단변수 증명에서의 저차 확장(low-degree extension)에 해당합니다. Lₙ(F) 의 중요한 속성은 다음과 같습니다.

1. 회전 불변성(rotation invariance): 이는 인접 관계(next-neighbour relation)와 효율적인 인코딩에 필요합니다.
2. 좋은 분리 가능성(good separability): 최대 거리 분리 가능 코드(Maximum Distance Separable Codes) 로 이어집니다.

Vanishing Polynomial

정의 2≤N<p+1 일 때, D 를 크기가 N 인 C(Fₚ​) 의 부분집합으로 합시다. D 에서 0으로 평가되는 Lₙ=Lₙ(Fₚ) 의 모든 0 이 아닌 다항식을 해당 집합 D 의 vanishing polynomial 이라고 부릅니다. D 를 점 Pₖ​,Qₖ​(1≤k≤N/2) 의 쌍으로 분해하고, 이 쌍을 통과하는 선형 함수들의 곱을 취하면 vanishing polynomial 이 존재함을 확인할 수 있습니다.

n = 2 일 때 D=Q⋅Gₙ₋₁​∪Q⁻¹⋅Gₙ₋₁ 인 twin-coset 에 대해, 보조정리 3에 따라 πⁿ⁻¹(D) 는 크기가 2 인 twin-coset 이 됩니다. 즉, xᴅ​,yᴅ​∈D 에 대해 πⁿ⁻¹(D)={(xᴅ,yᴅ​),(xᴅ​,−yᴅ​)} 의 형태가 됩니다. 그러므로 이러한 경우에는 다음과 같은 vanishing polynomial 을 정의할 수 있습니다.

이 때 vₙ​(x,y):=πₓ​∘πⁿ⁻¹(x,y) 이고, πₓ​​ 는 x-축으로의 사영(projection)을 나타냅니다.

D 가 standard position coset 이라면, πⁿ⁻¹(D) 는 다시 standard position coset 이며 xᴅ=0 이 됩니다 (그림 4 의 오른쪽 이미지 참조). 이 경우 vᴅ​(x,y):=vₙ​(x,y) 이고, vᴅ​ 는 O(n) 의 필드 연산만으로 계산할 수 있습니다 (각 단계에서 덧셈 2 회, 곱셈 1 회가 필요합니다).

정의 F 에서 값을 가지며 계산 도메인 D 인 circle code 는 다음 공간에서 가지는 선형 코드(linear code)입니다.

Circle FFT

논문에서의 정의 1. (CFFT-friendly prime). n≥1 이고 p 가 소수일 때, p+1 이 2ⁿ⁺¹ 로 나누어 떨어지게 하는 충분히 큰 n 이 존재한다면, 이를 CFFT-friendly 소수라고 합니다. 이러한 n 은 supported order 라 하고, N=2ⁿ 은 supported domain 의 크기라고 합니다.

논문에서의 정의 4. 0≤j≤2ⁿ-1 인 정수 j 에 대해 (j₀,…,jₙ₋₁)∈{0,1}ⁿ 를 이용해 이진수로 표현해봅시다. 위수(order) 가 n 인 FFT 기저, Bₙ​​ 은 다음과 같이 다항식으로 정의됩니다.

다항식 공간 X²+Y²−1: F[X,Y]/(X²+Y²−1) 를 생각해봅시다. 여기서Y²≡1−X² 이므로, 모든 y² 을 1−x² 로 치환할 수 있습니다. 따라서 모든 다항식은 deg(Y)≤1 인 형태로 표현될 수 있습니다. 즉, f(X,Y)∈F[X,Y]/(X²+Y²−1) 는 다음과 같은 표준형(canonical form) 으로 나타낼 수 있습니다.

f₀​(X) 와 f₁​(X) 는 이렇게 계산될 수 있습니다.

(J-folding) 첫 단계 ϕⱼ​ (혹은 πₓ):

직관적으로, f₀​ 은 f 와 f ∘ J 의 평균이고, f₁​은 차이를 2y 로 나눈 값입니다.

(π-folding) 다음 단계:

이 과정을 상수 함수가 나올 때까지 재귀적으로 반복합니다.

그러면 cₖ=fₖ₀,…,kₖₙ₋₁∈F 를 얻을 수 있고, 여기서 k=k₀+k₁2+…+kₙ₋₁2ⁿ⁻¹, 0≤k≤2ⁿ-1 입니다.

그림 6 에서 f₀​(x) 는 갑자기 4개의 점만 남습니다. 이는 f₀​(x) 가 실제로 (−A,−B,B,A)에서만 계산되며, x 에 의해서 매개변수화되기 때문입니다. 이를 원(circle) 위에 시각화하여 그룹 연산을 쉽게 이해할 수 있습니다.

1. f₀₀(C)​: f₀​(A) 와 f₀​​(−A) 의 평균.
2. f₀​₀​​(−C): f₀​​(B) 와 f₀​​(−B) 의 평균.

여기서 C 는 어디서 왔을까요? C=2A²−1 이고, A²+B²=1 이기 때문에 −C=2B²−1 로됩니다.

정리 2 p 를 n≥1 을 supported order 로 하는 CFFT-friendly 소수라 하고, D⊂C(Fₚ) 를 크기∣D∣=2ⁿ 인 twin-coset 이라고 합시다. D 위의 함수 f∈Fᴰ 가 Fₚ ​의 확장체 F 에서 값을 가지면, 위 알고리즘은 FFT 기저 Bₙ ​에 대해 다음 계수들을 출력합니다:

여기서 cₖ​∈F, 0≤k≤2ⁿ-1 이고, 이 계수들은 D 위에서 f 로 계산됩니다.

Low degree test over the Circle

프로토콜 1 (Circle FRI). D 를 크기가 ∣D∣=2ᴮ⁺ⁿ 인 standard position coset 이라 합시다. 여기서 B≥1, n≥1 입니다. C=Cₙ​(F,D)는 ρ=∣D∣/(N+1​) 인 비율(rate)을 가지는 circle code 로 정의됩니다. 여기서 N=2ⁿ 입니다. 주어진 근접성 매개변수(proximity parameter) θ∈(0,1−ρ​) 에 대해, 함수 f∈Fᴰ 가 circle code C 에 θ-근접함을 입증하는 IOP (Interactive Oracle Proof)는 다음과 같은 커밋 단계(commit phase)와 질의 단계(query phase)로 구성됩니다.

COMMIT phase:

QUERY phase: (executed by the Verifier)

Batch Circle FRI

프로토콜 2 (batch Circle FRI). 프로토콜 1과 동일한 가정하에서, f₁,…,fₗ​∈Fᴰ 로 이루어진 함수 배치(batch)가 circle code Cₙ​(F,D) 의 코드워드와 (1−θ)-agreement 를 가지는지에 대한 IOP 증명은 다음과 같습니다. 첫 번째 단계로, 검증자(verifier)로부터 난수 λb​←F 를 제공받으면, 증명자(prover)는 다음 선형 결합의 값을 D 에서 계산합니다:

증명자와 검증자는 f 에 대해 프로토콜 1을 실행합니다. 단, 질의 단계(query phase)는 배칭(batching)에 대한 검증을 각 질의마다 추가로 포함하여 확장됩니다.

CircleSTARK

Circle STARK 에서는 n≥1 일 때 C(Fₚ) 의 크기가 N=2ⁿ 인 standard position coset H⊂C(Fₚ) 이 trace domain 입니다. trace 는 t₁,…,t_w∈Fₚᴺ 와 같이 열 단위로 됐으며, H 위에 일반적인 방식으로 배치됩니다. 이 값들은 G 의 생성자를 사용한 그룹 변환 T 를 통해 표현됩니다. trace column 들은 총 차수가 N/2 이하인 다항식으로 보간(interpolated)되며,

이는 pᵢ∈Lₙ(Fp) 를 의미합니다. 이러한 다항식들은 다음과 같은 제약 조건 집합을 만족합니다:

여기서 sᵢ​∈Lₙ(Fp​) 는 미리 정의된 selector polynomial 입니다.

각 제약 조건(constraint)은 다음을 만족하는 다항식입니다:

• 총 차수는 twin-coset 의 최대 크기 이하.
• selector 변수 S 의 차수는 최대 1.

정의. 계산 도메인(evaluation domain)은 H 의 최소 두 배 크기를 가지는 standard position coset D⊆C(Fp​) 입니다. CircleSTARK 에서의 다항식은 일반적으로 이 도메인 위에서 그 값으로 커밋됩니다.

논문에서의 보조 정리 2. p 를 supported order 가 m≥1 인 CFFT-friendly 소수라 하고, k≤m 일 때 Gₖ ​를 위수가 2ᵏ 인 부분군으로 정의합시다. 그러면 D⊆C(Fₚ​)/Gₘ은 Gₘ₋₁ 에 불변이고, J 는 N=2ⁿ 인 twin-coset 들로 분해될 수 있습니다. 특히, 크기 M=2ᵐ 인 standard position coset D 는 다음과 같습니다.

여기서 Q 는 위수가 2ᵐ⁺¹ 인 C(Fₚ​​) 의 원소입니다.

IOP for AIR

이제, 이러한 모든 준비를 마쳤다면, AIR의 충족 가능성(satisfiability)에 대한 IOP 는 다음과 같이 구성될 수 있습니다.

첫 번째 라운드에 증명자(prover)는 평가 도메인 D 에서 trace polynomial p₁,…,p_w​∈Lₙ(Fₚ​​) 의 값을 twin-coset 들로 분해하여 계산하고, 해당 오라클(oracle)을 검증자(verifier)에게 공유합니다.

두 번째 라운드에 검증자는 random challenge β←F 를 Fₚ ​의 적절히 큰 확장체 F 에서 균일하게 추출하여 전송합니다. 이 random challenge 는 제약 다항식(constraint polynomials)을 단일 다항식으로 축소하는 데 사용됩니다.

이는 trace domain H 에서 성립해야 합니다. 이제, H 위의 vanishing polynomial vₕ ​를 계산하여 다음과 같이 복합 제약 다항식(composite constraint polynomial)을 작성합니다.

H 의 크기가 부과하는 차수 제한(degree bound)을 유지하기 위해, 몫 다항식 q∈L₍ₔ₋₁₎ₙ​(F) 을 다음과 같이 나누어야 합니다. 여기서 q₁,…,q₍ₔ₋₁₎∈L₍ₔ₋₁₎ₙ​(F) 입니다.

증명자는 계산 도메인 D 위에서 오라클들을 준비하고 이를 λ 와 함께 검증자에게 전송합니다.

모든 오라클이 준비되면, 다음 단계는 DEEP ALI 입니다. 이 단계에서는 제약 조건의 충족 가능성을 단일 지점 몫(single-point quotients) 위에서의 저차 테스트로 축소합니다. (다시 말하면, 이 단계는 저차 테스트를 다항식 커밋먼트 스킴(polynomial commitment scheme)으로 변환합니다.) 검증자는 random point γ→C(F)∖(D∪H)를 증명자에게 줍니다. 이에 대해 증명자는 vᵢ=qᵢ(γ) 와 함께 vᵢ,₀=pᵢ(γ),vᵢ,₁=pᵢ(T(γ)) 을 오픈합니다. 마지막으로 증명자와 검증자는 DEEP quotients 의 실수(real) 및 허수(imaginary) 부분에 대한 저차 테스트(low-degree test)를 진행합니다.

Conclusion

CircleFFT 의 초기 구현은 단일 스레드 환경에서 1.4 배의 성능 향상을 보여주었습니다. 이를 기반으로 Starknet 의 차세대 prover 인 Stwo(“STARK Two”)는 현재 prover 인 Stone(“STARK One”)을 개선 및 대체하기 위해 설계되었습니다.

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

CircleSTARK 이해하기 was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.

Written by Baz (@0xBATZOR)

Special thanks to Ryan Kim (@chokobole33), Ashjeong, fakedev9999 (@fakedev9999) and EthanYoo (@zkEthanYoo) for feedback and review.

This article is also available in Korean.

Motivation

There is a trade-off between selecting finite fields that allow for:

1. Efficient Arithmetic Implementations: Smaller prime fields, particularly those of special forms like Mersenne primes, enable faster arithmetic operations on standard hardware architectures.
2. Efficient FFT Support: Fields need to have smooth multiplicative groups with large two-adic subgroups to support efficient FFTs, which are crucial for STARKs’ encoding processes.

One of the most efficient fields for arithmetic seem to be Mersenne fields, defined by primes of the form p = 2ᵉ − 1. In particular, the prime p=2³¹−1 enables very efficient arithmetic on 32-bit architectures.

Since 2³² = 2 mod 2³¹-1, a widened product encoded as 2³²⋅xₕᵢ+xₗₒ​ is trivially reduced to a much smaller quantity, 2⋅x ​ₕᵢ+xₗₒ​. However, as p−1=2⋅3²⋅7⋅11⋅31⋅151⋅331, the multiplicative group lacks two-adic subgroups, which are useful for efficient Cooley-Tukey Fast Fourier Transforms (FFTs).

Circle Group

For p=3 mod 4, a complex extension field Fₚ/(X²+1) can be defined as:

For p=1 mod 4, X² + 1=0 has a solution since by Legendre Symbol: −1/p=(−1)^{(p−1)/2}=1. This means that −1 is a quadratic residue and X²+1 can be written as (X−a)(X+a) making Fₚ/(X²+1) not a field.

The unit circle over Fₚ​ is the algebraic set C(Fₚ)={(x,y)∈Fₚ² : x²+y²=1}, or in complex representation:

where z̄ denotes the conjugate x−iy of z̄=x+iy.

Lemma 1 (Unit circle group). Let ​ Fₚ​ be a prime field with p=3 mod 4. Then the unit circle group C(Fₚ​​) equals the group of (p+1)-th roots of unity in C(Fₚ​)ᕽ, and has order p+1.

Proof: Notice that zᵖ=(x+iy)ᵖ=xᵖ+(iy)ᵖ=x+(iᵖ)y=x−iy=zˉ so x²+y²=z⋅zˉ=zᵖᐩ ¹. Therefore, C(Fₚ)={z∈C(Fₚ​)ᕽ:zᵖᐩ ¹ =1} which means C(Fₚ​) is set of all (p+1)-th roots of unity. Since ∣C(Fₚ)×∣=p²−1 is divisible by p+1, the unit circle group must be the unique subgroup of order p+1.

Group Operations

The p+1 points of C(Fₚ) form a group with the group operation:

Notice that this equation resembles the cos(α+β) and sin(α+β) formulas and is equivalent to rotation over the unit circle.

The group has (1,0) as its identity element, and for any P=(Pₓ​,Pᵧ​)∈C(Fₚ), we shall call

the translation(rotation) by P.

The squaring map with respect to the group operation is the quadratic map

and group inverses are given by the degree-one map J(x,y):=(x,−y)

So you can think of π as doubling the angle it forms with the x-axis and J as a reflection by the x-axis.

Twin-coset and Standard Position Coset

First, Figure 2 shows how the subgroups would look like in the circle group.

Taking a coset of a subgroup means that each point in the subgroup will be rotated by the same amount.

Definition Let Gₙ₋₁​ be a cyclic subgroup of C(Fₚ) of size ∣Gₙ₋₁|​=2ⁿ⁻¹ for n≥1. Any disjoint union D=Q⋅Gₙ₋₁​∪Q⁻¹⋅Gₙ₋₁​​ with Q⋅Gₙ₋₁​∩Q⁻¹⋅Gₙ₋₁​=∅ is called twin-coset of size N=2ⁿ.

Remark Twin-coset maps to itself under inverse since

Definition In the exceptional case that a twin-coset D of subgroup Gₙ₋₁​ is again a coset of the subgroup Gₙ​, we call D a standard position coset.

Lemma 3 from the paper. If D is a twin-coset of size 2ⁿ, n≥2, then its image π(D) is a twin-coset of size 2ⁿ⁻¹. In addition, if D is a standard position coset, so is π(D).

Proof: π(D)=π(Q⋅Gₙ₋₁∪Q⁻¹⋅Gₙ₋₁)=π(Q)⋅ Gₙ₋₂ ∪ π(Q⁻¹)Gₙ₋₂ ​ and if D=Q⋅Gₙ ​is a standard position coset, then π(Q⋅Gₙ)=π(Q)⋅Gₙ₋₁​, which means π(D) is also a standard position coset.

Space of Polynomials

Definition Let be F an extension field of Fₚ. Over the circle curve, for any even integer n≥0 we define Lₙ(F) as the space of all bi-variate polynomials with coefficients in F, and of total degree at most N/2,

For a circle STARK the bi-variate polynomials from Lₙ(F) are what low-degree extensions are for classical univariate proofs. The crucial properties of Lₙ(F) are:

1. rotation invariance, which is needed for the next-neighbour relation and efficient encoding
2. good separability, leading to maximum distance separable codes.

Vanishing Polynomial

Definition Let D be a subset of C(Fₚ​) of even size N, where 2≤N<p+1. We call any non-zero polynomial from Lₙ=Lₙ(Fₚ), which evaluates to zero over D a vanishing polynomial of the set D. Decomposing D into pairs of points Pₖ​,Qₖ​,1≤k≤N/2 and taking the product of linear functions going through these pairs,

shows that vanishing polynomials do exist.

Given a twin-coset D=Q⋅Gₙ₋₁​∪Q⁻¹⋅Gₙ₋₁, using Lemma 3, we can see πⁿ⁻¹(D) will result in a twin-coset of size 2. In other words, it is in the form of πⁿ⁻¹(D)={(xᴅ,yᴅ​),(xᴅ​,−yᴅ​)} for some xᴅ​,yᴅ​∈D. We therefore may take

with vₙ​(x,y):=πₓ​∘πⁿ⁻¹(x,y) where πₓ​​ is the projection onto the x-axis.

And when D is a standard position coset, its image πⁿ⁻¹(D) is again a standard position coset and thus xᴅ=0 (see Figure 4, rightmost image). In this case vᴅ​(x,y):=vₙ​(x,y) and vᴅ​ can be evaluated by only O(n) field operations (2 addition and 1 multiplication in each step).

Definition The circle code with values in F and evaluation domain D, is linear code with code words from the space:

Circle FFT

Definition 1 from the paper. (CFFT-friendly prime). Any prime p for which (p+1) is divisible by 2ⁿ⁺¹ for sufficiently large n≥1, will be called CFFT-friendly, and any such n is a supported order, and N=2ⁿ a supported domain size.

Definition 4 from the paper. For any integer j from the interval 0≤j≤2ⁿ-1, let (j₀,…,jₙ₋₁)∈{0,1}ⁿ denote its bit representation. The FFT-basis of order n is the family Bₙ​ of polynomials:

Consider bi-variate polynomials modulo X²+Y²−1: F[X,Y]/(X²+Y²−1). Here Y²≡1−X² so we can replace all y² by 1−x² and hence, all polynomials in F[X,Y]/(X²+Y²−1) can be represented with polynomials with deg(Y)≤1.

This means any f(X,Y)∈F[X,Y]/(X²+Y²−1) can be represented as canonical form:

And we can calculate f₀​(X) and f₁​(X) by:

(J-folding) First step ϕⱼ​ aka πₓ:

More intuitively, f₀​ is taking the average of f and f ∘ J while f₁​ is the difference between them divided by 2y.

(π-folding) Next step:

This step is repeated recursively until we get constant functions of the form:

These make up a constant cₖ=fₖ₀,…,kₖₙ₋₁∈F, for each k in the interval 0≤k≤2ⁿ-1, where k=k₀+k₁2+…+kₙ₋₁2ⁿ⁻¹.

In Figure 6, f₀​(x) suddenly has only 4 points. This is because f₀​(x) actually has only 4 evaluation points (−A,−B,B,A) and is only parametrized by x. It is visualized on a circle for easier group operation visualization. To elaborate:

1. f₀₀(C) is the average of f₀​(A) and f₀​​(−A).
2. f₀​₀​​(−C) is the average of f₀​​(B) and f₀​​(−B).

But where did C come from? It denotes 2A²−1, while −C is 2B²−1 since A²+B²=1 because they are from a standard position coset of size 8.

Theorem 2 Let p be a CFFT-friendly prime supporting the order n≥1, take D⊂C(Fₚ) a twin-coset of size ∣D∣=2ⁿ. Given f∈Fᴰ a function over D with values in an extension field F of Fₚ, the above described algorithm outputs the coefficients cₖ​∈F, 0≤k≤2ⁿ-1, with respect to the FFT basis Bₙ​, so that

evaluates to f over D.

Low degree test over the Circle

Protocol 1 (Circle FRI). Let D be a standard position coset of size ∣D∣=2ᴮ⁺ⁿ, where B≥1 and n≥1, and let C=Cₙ​(F,D) be the circle code with rate ρ=∣D∣/(N+1​), where N=2ⁿ. For given proximity parameter θ∈(0,1−ρ​), the interactive oracle proof of a function f∈Fᴰ being θ-close to the circle code C, consists of a commit phase and a subsequent query phase, which are as follows.

COMMIT phase:

QUERY phase: (executed by the Verifier)

Batch Circle FRI

Protocol 2 (batch Circle FRI). Under the same assumptions as Protocol 1, the interactive oracle proof for a batch of functions f₁,…,fₗ​∈Fᴰ having correlated (1−θ)-agreement to a codeword from Cₙ​(F,D), is as follows. In the first step, given a random challenge λb​←F from the verifier, the prover computes the values of the linear combination:

​over D. Now, both prover and verifier run Protocol 1 on f , with its query phase extended by a check of the batching at each of the queries.

CircleSTARK

In circle STARK, the trace domain is the standard position coset H⊂C(Fₚ) of a cyclic and proper subgroup G=Gₙ​ of the circle curve C(Fₚ), of size N=2ⁿ, with n≥1, and the trace is organised column-wise t₁,…,t_w∈Fₚᴺ , each placed over the domain H in the usual manner, using the group translation T by a generator of G for the timeline. The trace columns are interpolated by polynomials

of total degree at most N/2, meaning that pᵢ∈Lₙ(Fₚ) and these polynomials are subject to set of constraints, say

for i=1,…,C, holding over the entire domain H, where sᵢ​∈Lₙ(Fp​) is a predefined selector polynomial.

Each constraint is a polynomial

of total degree at most the maximum number of twin-coset of size N, and the degree in the selector variable S is at most 1.

Definition. The evaluation domain is a standard position coset D⊆C(Fp​), of at least double the size of trace domain H. The polynomials in the circle STARK will be generally committed by their values over this domain.

Lemma 2 from the paper. Let p be a CFFT-friendly prime supporting the order m≥1, and Gₖ​ denote the subgroup of order 2ᵏ for k≤m. Then any subset of D⊆C(Fₚ​)/Gₘ​ which is invariant under Gₘ₋₁ and J can be decomposed into twin-cosets of size N=2ⁿ, for any n≤m. In particular for a standard position coset D of size M=2ᵐ,

where Q is an element from C(Fₚ​​) of order 2ᵐ⁺¹.

IOP for AIR

Now, once we have all these, the interactive oracle proof for the satisfiability of the AIR can be constructed as follows:

In the first round, the prover computes the values of its trace polynomials p₁,…,pᵥᵥ​∈Lₙ(Fₚ​​) over the evaluation domain D using its decomposition into twin-cosets and shares their oracles denoted by

with their verifier.

In the second round, the verifier sends random challenge β←F, drawn uniformly from a suitably large extension field F of Fₚ​​, which is used to reduce the constraint polynomials into a single one:

which should hold over trace domain H. To prove this, the vanishing polynomial over H, vₕ​, is computed so the composite constraint polynomial can now be written as:

​To keep with the degree bound imposed by the size of H, the quotient q∈L₍ₔ₋₁₎ₙ​(F) needs to be split into polynomials q₁,…,q₍ₔ₋₁₎∈L₍ₔ₋₁₎ₙ​(F)

Then, the prover sets up the oracles

for their values over the evaluation domain D, and sends them, together with λ, to the verifier.

Having all oracles in place, the next step is DEEP ALI, which reduces satisfiability of the constraints to a low-degree test on single-point quotients. (In lose terms, this step turns low-degree test into a polynomial commitment scheme.)

In this step, the verifier responds with a random point γ→C(F)∖(D∪H). In return, the prover opens the values vᵢ,₀=pᵢ(γ),vᵢ,₁=pᵢ(T(γ)) for each i=1,…,w as well as v₁,…,v₍ₔ₋₁₎​ of q₁,…,q₍ₔ₋₁₎​ at γ. Eventually, both prover and verifier engage in a low-degree test for the real and imaginary parts of the DEEP quotients:

Conclusion

The initial implementation of CircleFFT demonstrated a performance improvement by a factor of 1.4 in a single-threaded setup. Building on this foundation, Starknet’s next-generation prover, Stwo (“STARK Two”), is designed to enhance and eventually replace the current prover, Stone (“STARK One”).

About Kroma

As Asia’s leading Layer 2 solution built on the Superchain, Kroma is the first OP Stack rollup with an active fault proof system utilizing zkEVM.
Kroma will transition to a universal ZK Rollup once the generation of ZK proofs becomes more cost-efficient and faster — using its original modular ZK backend library, Tachyon.

Kroma plans to push for gamified web3 experience backed by its strengths in gaming, consumer applications, Asia market, and technical capabilities for true universal web3 adoption.

Follow us:

Website | Twitter | Discord | Warpcast | Github | Docs | Ecosystem | Brand Kit | Grant

Understanding CircleSTARK was originally published in Kroma on Medium, where people are continuing the conversation by highlighting and responding to this story.