If Bitcoin is an inherently stateless blockchain, then how can BOS use it to verify ZK proofs?
In BitSNARK, we apply Winternitz One-Time Signatures (WOTS) to optimize the verifier by reducing data commitment size, making the entire process more efficient, and enabling essential statefulness. This article will explain how these digital signatures work, compare Lamport and Winternitz signatures, and show how they establish statefulness within BitSNARK.
What Is Blockchain Statefulness?
In blockchain, a state change is any data update, such as fund transfers, smart contract updates, or asset ownership changes. This is essential for blockchains like Ethereum, which track states to support complex applications through an account-based model that directly updates balances.
In contrast, Bitcoin uses a stateless UTXO (Unspent Transaction Output) model, where nodes only track current unspent outputs rather than their history, limiting Bitcoin’s ability to track changes over time. This distinction shapes each blockchain’s suitability for applications like DeFi and NFTs, with Ethereum enabling more dynamic functionality.
BitSNARK - Complex Computation On Bitcoin Requires Statefulness
BitSNARK, built by BitcoinOS, is a new paradigm for verifying any program on the Bitcoin network. The system runs a script where transactions are represented as succinct, fixed-size proofs. A single verifier can challenge a dishonest prover without needing majority signatures for validation.
To resolve a challenge, the prover and verifier must efficiently and securely inspect the transaction set to locate disagreements. This requires organizing and linking transactions within the ZK proof to create statefulness, ensuring transactions are correctly ordered and aware of each other. Since Bitcoin is inherently stateless, workarounds are needed to enable this stateful functionality.
One important building block to achieve this statefulness is to apply digital cryptographical signature schemes. Digital signatures are mathematical schemes for verifying the validity of digital messages or documents.
Each part of the program is divided into transactions, with signatures attached to each segment. Each segment is represented by a hash, creating a chain of transactions that allows the prover and verifier to investigate them individually. BitVM initially proposed using Lamport signatures for this, but switching to Winternitz signatures could reduce data commitment size by 50%.
WOTS Digital Signatures
Winternitz signatures were proposed by Ralph Merkle and independently by Robert Winternitz, in the early 1980s as an extension to Lamport signatures. They offer similar security properties in terms of quantum resistance, but with improved efficiency.
Winternitz signatures employ a chain structure to reduce the size of the signatures compared to Lamport. Winternitz one-time signature schemes (WOTS) enhance Lamport signatures and dramatically shrink the signature and the public-key size. However, the improvement comes at the cost of more work to generate and verify signatures.
The Winternitz signature scheme divides a message into segments, hashing each segment multiple times based on its value, but this introduces a vulnerability: if an attacker learns any segment's value, they can forge signatures by computing subsequent hashes. To counter this, the scheme uses a checksum as a critical safeguard, ensuring that any message alteration would require matching changes to the checksum, which is infeasible without the private key.
The checksum also confirms the signature's completeness and balances hash iterations across segments, providing a layer of verification that maintains the signature's integrity and security against forgery.
These signature schemes also ensure that once a commitment is made, it cannot be altered without detection. It is thus tamper proof - which maintains the integrity of stateful smart contracts and ensures that all participants can trust the recorded data.
The primary use case, in a broader sense, is to enable stateful smart contracts. Allowing commitments made in one transaction to be referenced by future transactions, they can manage the state over multiple transactions. This is key for implementing more sophisticated logic on Bitcoin.
WOTS for BitSNARK
BitSNARK is a framework that ushers in the ability to verify arbitrary transactions on Bitcoin using Winternitz signatures to create secure data commitments. A commitment, in this context, is a cryptographic guarantee that specific data exists, has been securely recorded at a precise time, and is signed. These commitments are verifiable, tamper-proof, and can be referenced in future disputes by other parties.
If the verifiers agree with the operator, operations proceed smoothly, but in cases of disagreement, each can use the other’s signed commitments to expose errors or cheating.
The way BitVM introduced digital signatures, and how BitcoinOS has implemented Winternitz in BitSNARK, is innovative in the way it uses one-time signatures to reliably commit to each state across multiple transactions. The Winternitz signatures ensure maximally efficient verification, which is essential under the constraints of operating within Bitcoin’s network performance.
Is WOTS the Future For Statefulness on Bitcoin?
The integration of these cryptographic techniques into protocols greatly enhances Bitcoin’s scripting capabilities, enabling efficient and secure stateful operations.
By supporting robust data commitments, they allow the network to process complex transactions while ensuring high security and performance. These advancements are crucial for Bitcoin’s future, as they enable more sophisticated decentralized applications, such as trust-minimized sidechain bridges and the optimistic verification of zero-knowledge proofs on Bitcoin.
For more information please visit our website, and follow BitcoinOS on X.
