Grail technical docs

Table of contents

Abstract

The paper introduces BitSNARK and Grail, systems designed to optimize Bitcoin Rollup Bridges. BitSNARK is an improvement over BitVM, providing better efficiency and reduced complexity for verifying SNARK proofs on the Bitcoin blockchain. Grail implements BitSNARK, enabling practical and scalable Bitcoin Rollup Bridges.

Introduction

The paper discusses the historical challenges of scaling Bitcoin while maintaining decentralization and computational expressivity. Gregory Maxwell's introduction of SNARKs as a potential solution remained theoretical due to perceived implementation barriers. Robin Linus's BitVM in 2023 demonstrated the potential for Turing-complete smart contracts on Bitcoin, but practical limitations persisted. BitSNARK aims to overcome these limitations, optimizing for SNARK verification and reducing complexity.

BitSNARK

BitSNARK is a software library for verifying SNARK proofs on Bitcoin. It focuses on zkSNARK verification, offering a faster and less costly solution than general-purpose systems. The BitSNARK VM uses a simplified register-based processor with three instructions (addmod, andbit, equal), making the verification protocol more efficient and secure.

Interactive Verification Protocol

This part is still lacking:

  • What is being proved specifically?
  • Snark pseudocode.
  • Check for any missing things.
  • Expand on the PegIn process.
  • Do operators take part here too? Or only in the bridge functionallity standalone?

The Interactive Verification Protocol is a core component of BitSNARK, designed to facilitate secure and efficient verification of zkSNARK proofs on the Bitcoin blockchain. This protocol involves a two-party interaction between a prover and a verifier, enabling the execution and verification of computations with minimal on-chain data and reduced complexity.

Key Features of the Interactive Verification Protocol

Two-Party Interaction:

The protocol is initiated by a prover who provides an input and the result of a computation.

This computation corresponds to a full execution of a BitSnark trace and it's derivated changes.

The verifier has the opportunity to challenge the prover's claims if they suspect an error or fraud.

Challenge and Response Mechanism:

The interaction is structured as a series of challenges and responses.

The prover commits to intermediate states of the computation, allowing the verifier to select specific points to challenge.
Each step of the protocol involves a time-locked transaction, ensuring that both parties are incentivized to participate honestly and promptly.

Unsure if the time-lock is for every step inside the BitSnark trace. If so, doesn't it take forever to run this step of the protocol?
If it is not, what are the things that this time-locks mentioned in the paper are based on?
Carlos

Protocol Steps:

  1. Initial Commitment: The prover starts by revealing the input and the result of the computation.
  2. Challenge Issuance: The verifier selects a segment of the computation they believe might be incorrect and issues a challenge.
  3. Proof of Execution: The prover responds by providing proof that the challenged segment was executed correctly.
  4. Verification: This process continues iteratively, halving the segments of computation and verifying them, until the prover commits to a single BitSNARK operation.

Dispute Resolution:

If a verifier successfully proves a discrepancy in the prover's claims, the funds remain locked, and the verifier is rewarded from the initial transaction output created by the prover.

If no challenge is issued within the allowed time, or if the verifier fails to prove the claim, the funds are unlocked for the prover.

I assume that here, not only the funds are unlocked but also the profit of the prover is rewarded (coming from user fee or whatever)
Carlos

Efficiency:

The protocol's complexity is logarithmic (O(log(n))), allowing for efficient handling of large computations by dividing the verification steps into manageable parts.
The use of pre-signed transactions and a simplified instruction set (only three instructions: ADDMOD, ANDBIT, EQ) further streamlines the verification process.

Incentive Structure:

Both the prover and the verifier are economically incentivized to act honestly.
The prover deposits a stake, which can be forfeited in case of fraudulent behavior.
The verifier also stakes funds to initiate challenges, deterring unfounded/wrong disputes.

Carlos
This is missing the incentives of the prover (benefits in particular).
Why would a prover like to stake and work here? In exchange of fees I assume. If so, we need to say from where do they come

Security and Scalability

Security

The protocol's design ensures that even a single honest verifier can prevent fraudulent transactions. The interactive nature and the economic incentives make it robust against various attack vectors.

  • Add all requirements needed such that we can consider a proof correct.
  • Add a diagram of all the proof checks being done. What checks do we need? What inputs? Which ones are pub? Whic private?

Scalability

By reducing on-chain data and utilizing off-chain computations, the protocol scales efficiently with minimal impact on the Bitcoin network. The logarithmic complexity ensures that large computations can be verified with relatively few steps.

Grail Bridge

Grail is a system enabling asset transfers between Bitcoin (Layer 1) and Rollups (Layer 2). Operators play a key role in monitoring and assisting with deposits and withdrawals. Grail uses Taproot addresses and SNARK proofs to lock and transfer funds securely between Bitcoin and Rollups.

Key components and Roles

Operators:

  • Role: Operators are responsible for monitoring the bridge operations and assisting users with deposits and withdrawals.
  • Responsibilities: They must constantly monitor both the Bitcoin and Rollup networks, participate in protocol steps, and maintain active internet endpoints for peer-to-peer interactions.
  • Requirements: A minimum of two operators is required to keep the protocol functional, but the system can support more operators as needed.

Carlos
How do we ensure:

  • Liveness (now two parties need to be up always, in pair. Which makes it even harder than having only a sequencer).
  • Censorship resistance. In this case, it's really hard to see/argue how we can reach it. One may say that having a pool of Operators can make it. But with TornadoCash-style bans. It can happen that censorship is reached.

Operator Registration and Resignation:

  • To become an operator, an agent must create a public key identity and an exit secret. They then register with the bridge’s smart contract, depositing a required stake as a guarantee.
  • Operators can recover their stake upon exiting the protocol role, provided they have not violated any protocol rules. Exiting involves revealing the exit secret to ensure they cannot participate in future protocol exchanges.

Multi-Signature Identity:

The active group of operators maintains a multi-signature identity used to pre-sign transactions and optimize operational costs. The MuSig2 two-round protocol is employed to create Schnorr signatures approved by the entire operator set.

Carlos
I need more deteils in this part.
What is this Multisig optimizing and what is it understood by operational costs in the paper?

Grail Bridge Deposit

The deposit process involves initiating, confirming, and completing a deposit. Users specify funding UTXOs, and operators generate pre-signed transactions to facilitate the transfer of funds.

Grail Bridge Deposit Process

To manage deposits efficiently, three smart contract functions coordinate the operations:

  1. Initiate Deposit:
    A user specifies a set of funding UTXOs (Unspent Transaction Outputs) on the Bitcoin network and requests an address to make a deposit.
    Operators collaborate to generate an address and pre-signed transactions.

Carlos
THis needs to be expanded. How pre-signed transactions specifically help the protocol here?
Why do Operators need to collaborate? Which ones? Whitelist? Random? All of them?

  1. Confirm Deposit:
    Once a set of operators has signed the required transactions, the deposit is confirmed. The user can then transfer the funds, verifying that the address and transactions are correctly signed.

Carlos
Which are the required transactions to be signed by the operators? These pre-seigned transactions mentioned avobe right?
What does it take to confirm the Deposit?
Is there any way on which the signed transactions can be tricked or the user can be lied such that we can confirm but never complete?
Do Operators actually need to prove they've done all the Pre-Signing correctly? Can they trick/be tricked by the user somehow?

  1. Complete Deposit:
    Upon proof of transfer to the accepted bridge deposit address on the Bitcoin network, the equivalent amount of the rollup’s ERC20 token is transferred to the user in the rollup. The locked UTXOs are registered in the smart contract.

Carlos
Expand on SNARK stuff once the issue avobe is clarified.

image
Does the image represent that the ERC20 contract will verify a proof and depending on it, will transfer to the deposit address?.

If so, Is any of these 2 mentioned in the paper?

  • Proof of transaction inclusion on the bitcoin network
  • Proof that a variable on the bridge smart contract reached a particular state

Grail Bridge Withdrawals

Withdrawals can be initiated by operators or users, involving SNARK proofs to transfer funds securely. The system supports coordinated and operator-assisted withdrawals, ensuring smooth operations and minimizing wait times.

Withdrawal Mechanisms

  • Operator-Initiated Withdrawal:

    • Request Withdrawal: An operator holding tokens on L2 initiates a withdrawal request, specifying the amount and target Bitcoin address.

    Carlos
    This is simply an operator leaving the protocol and getting their stake back right? Also the benefits earned so far? Or not?

    • Assignment of UTXOs: The smart contract on L2 collects the equivalent amount of tokens from the operator and assigns a set of UTXOs (locked funds on Bitcoin) to the operator's Bitcoin address.
    • Proof of Ownership: The operator must provide a zkSNARK proof that they control the assigned UTXOs.
    • Execution: Upon verification of the proof, the UTXOs are unlocked, and the Bitcoin is transferred to the operator’s specified address.

Carlos
This

  • Coordinated Withdrawal:
    If all operators are available and cooperating, withdrawals can be completed with a group signature, avoiding the need for zk-proof calculation and commitment.

Carlos
The info here is minimal and not clear at all how should it work or if should even be mentioned.
Need to expand on this a lot.

  • Operator-Assisted Withdrawal:
    Users can request withdrawals, which can be fulfilled by operators holding Bitcoin. The bridge smart contract facilitates a swap, with operators getting a fee for their service. This minimizes wait times and simplifies the user experience.

image

  • Initiate withdrawal: The user specifies an amount and target address. The smart contract collects the funds and registers the withdrawal request.
  • Operator assignment: Wn operator responds and selects a set of UTXOs they control to service the request. The withdrawal gets assigned to them. As soon as the state is confirmed, they transfer Bitcoin to the target address using the preselected UTXOs.
  • Complete withdrawal: the operator completes the operation by presenting a proof of inclusion in the Bitcoin blockchain of the transaction to the target address. The smart contract transfers the target amount in tokens to the operator.

So the operator is getting tokens instead of being burn? If that's the case, this is not inline with which I discussed in the previous call.

Proofs

Grail uses zkSNARK proofs for transaction inclusion on the Bitcoin network and state transitions on the bridge smart contract. These proofs enhance security and support the bridge's operations.

  • Proof of Transaction Inclusion on the Bitcoin Network:
    Given a transaction hash, a zkSNARK proof is generated to confirm that the transaction was included in a specific block and followed by a predefined number of confirmations.

Carlos
How do we account for confirmations in a proof?
This requires a deeper formalisation!

  • Proof of State Transition of the Bridge Smart Contract on L2:
    These proofs confirm that a UTXO has been assigned to an operator for withdrawal or that a stake has been released after an operator has resigned. Proofs can be constructed based on transaction inclusion on the Bitcoin network or storage state on the rollup’s smart contract.

Carlos
Confirmation of two exclusive things is complex. (Doable of course but also expensive and more difficult).
Would love to go deeper into this and take more notes such that I can get a better sense.

Security and Incentive Structure

  • Security: The system ensures that funds are securely maintained with 1-of-n assurance, meaning any honest operator can prevent abuse.
  • Incentives: Operators are incentivized through fees for facilitating withdrawals and penalties for dishonest behavior, ensuring the system operates smoothly and securely.

Reverse Bridge L2 -> BTC

No info in the paper is mentioned about it.
Keep on this tomorrow trying to elaborate all the info I know and continue formalizing.

L2 settles on BTC

BitVM vs BitVM2

@elmol's Questions

Component Overview

Just trying to corroborate my understanding of the components overview:

  1. Question: From the introduction: BitSNARK is described as a software library that allows verifying SNARK proofs on the Bitcoin blockchain. Does this mean that it only allows the verification of any SNARK proof "on chain" in Bitcoin? So, it cannot be seen as a zk-rollup, right?
    Answer:
Select a repo