<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Wei Zhang on Medium]]></title>
        <description><![CDATA[Stories by Wei Zhang on Medium]]></description>
        <link>https://medium.com/@w.zhang?source=rss-c864c38ff720------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*lToAB1jv9dX5XejYdwMD1g.jpeg</url>
            <title>Stories by Wei Zhang on Medium</title>
            <link>https://medium.com/@w.zhang?source=rss-c864c38ff720------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 21:56:52 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@w.zhang/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Trustless Revolution: Recursive Groth16 For NFTs on Bitcoin]]></title>
            <link>https://medium.com/@w.zhang/trustless-revolution-how-recursive-groth16-is-disrupting-nfts-on-bitcoin-954a17fb4171?source=rss-c864c38ff720------2</link>
            <guid isPermaLink="false">https://medium.com/p/954a17fb4171</guid>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[decentralization]]></category>
            <category><![CDATA[nft]]></category>
            <category><![CDATA[groth16]]></category>
            <dc:creator><![CDATA[Wei Zhang]]></dc:creator>
            <pubDate>Thu, 13 Feb 2025 17:49:11 GMT</pubDate>
            <atom:updated>2025-02-27T15:11:57.114Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/815/1*2CYHJNiGY8l1ouKB5O3M8g.png" /></figure><p>Imagine a blockchain ecosystem where token swaps and Non-Fungible Token (NFT) transactions are not only secure but also lightning-fast and entirely trustless. Our breakthrough, powered by recursive Groth16, pushes the envelope of what’s possible, creating a scalable, decentralized solution that redefines NFT tokens on Bitcoin. Built on state-of-the-art zero-knowledge proof systems and inspired by the latest academic innovations, we invite you to explore how this technology can transform NFTs.</p><h4><strong>What We’ve Achieved</strong></h4><ul><li><strong>Next-Generation Atomic Swaps</strong><br> We have successfully implemented an atomic swap mechanism based on the NFT token protocol described in <a href="https://eprint.iacr.org/2023/697.pdf">this academic paper</a> by our former colleagues. Our implementation leverages recursive Groth16 to create a secure, efficiently verifiable chain of token transfers. Each token transfer also contains a bitcoin transfer as the other leg of the exchange to make it atomic.</li><li><strong>Community-Driven Innovation</strong><br>With significant contributions from experts like <a href="https://www.linkedin.com/in/federico-barbacovi-946375231/">Dr. Federico Barbacovi</a>, our approach combines deep technical expertise with a commitment to open, decentralized collaboration. We’re not just building a solution, but a community standard.</li></ul><h4><strong>How Recursive Groth16 Empowers Blockchain</strong></h4><p>While Groth16 is renowned for its compact proofs and efficient verification, making it recursive has historically been computationally demanding. Alternatives such as folding schemes exist, but they often sacrifice one or more key benefits such as proof size or efficiency in verification. Despite recent industry voices such as Vitalik’s recent post urging a move away from Groth16, we believe its unparalleled proof compactness and efficiency in verification makes it indispensable for blockchain use cases.</p><h4>Our Approach in Detail</h4><p>Given two public inputs, a transaction ID and a genesis transaction ID, and two private inputs, a serialised transaction and a prior proof when applicable, the circuit executes two main computations:</p><p>1. <strong>Transaction Hashing:</strong> hash the serialised transaction and compares the hash value with the given transaction ID.</p><p>2. <strong>Proof Verification:</strong> Validates the prior proof that shows the link between the token to be transferred and its original issuance.</p><p>We then used a modified Arkworks library <a href="https://github.com/BarbacoviF/pcd/tree/barbacovif/use-short-weierstrass-curve">ark_pcd</a> to run recursive Groth16 setup to obtain a proving key and a verifying key. The verifying key is designed to be token independent by taking token genesis transaction ID as a public input, which means one setup can serve any issuance of tokens.</p><p>When transferring a token, the sender creates a zero-knowledge proof that traces the token back to its issuance. This proof is embedded in an unlocking script with respect to an output prepared by the receiver and later verified by the blockchain network, ensuring the token’s legitimacy. The communication overhead remains constant and negligible regardless of transfer history, making it ideal for tokens that will be traded frequently.</p><p>Here are the transactions we prepared earlier on Bitcoin SV testnet using <a href="https://github.com/nchain-innovation/zkscript_package">zkscript</a>. We will publish the code for you to reproduce the same soon.</p><p>To issue an NFT, we created <a href="https://test.whatsonchain.com/tx/4857fbb2da973cab3a42cf42bc705b56a8748d2ea0fa1527abfa54021ec2f86c">a genesis transaction</a>, which is essentially just a standard Bitcoin transaction. The first output in the genesis transaction is recognised as the NFT output. We assume that the genesis transaction ID is then publicly known. <a href="https://test.whatsonchain.com/tx/62623f437e4b26dc30c2a2484a84c12cdddb521c56d2ee2780e2428d60c89cfa">The first transfer</a> of the token spends the first output from the genesis transaction. After that, for each token transfer, three Bitcoin transactions are created. A <em>zk-verifier transaction</em> sets up the verification locking script, which is spent with a Groth16 proof in a <em>proof transaction</em>. A <em>token-swap transaction</em> is then created to complete the exchange between the NFT token (first input and first output) and Bitcoin (second input and second output).</p><p><a href="https://test.whatsonchain.com/tx/edd947407b18f97bd484298c4336e46c45b66c2510f3e61d00abd2bccf3231e8">zk-verifier_1</a>, <a href="https://test.whatsonchain.com/tx/63823f84f152a92120bb6441448802614bb27610497fa3ab7323d4b47d4dbf36">proof_1</a>, token-swap_1</p><p><a href="https://test.whatsonchain.com/tx/1f237533227ef56a66b6643e4f88cbc19d239e26a609c201afd4055aeddf775f">zk-verifier_2</a>, <a href="https://test.whatsonchain.com/tx/16ca5310a2ca3f2deaadbc79415916f447425b173028bda00f0a1565223a5ae4">proof_2</a>, <a href="https://test.whatsonchain.com/tx/1c302655d42542fcc9b5f78883804b630d38bbca3a3b1e239c7b4fe7c5a4fe61">token-swap_2</a></p><p><a href="https://test.whatsonchain.com/tx/b140825f842c8875cb34eef0a7486130b80866c4509617915a60a72e4efc8feb">zk-verifier_3</a>, <a href="https://test.whatsonchain.com/tx/61bbd74b4b555e993bb9a7e842e5c95c0dd92df31017b4a4ed92c66a97885dc1">proof_3</a>, <a href="https://test.whatsonchain.com/tx/b540e7a57901002bc640c481426b4d59f245507955cf5d08902d358a428d2825">token-swap_3</a></p><p><a href="https://test.whatsonchain.com/tx/a2abe9f5faa15e55dbebdba2474d581fe8efa04f9921d13eb44230623d4297e3">zk-verifier_4</a>, <a href="https://test.whatsonchain.com/tx/ff6053aefc601c81f00c6de3d3956a500a9250da581913bee130df35dfd4705c">proof_4</a>, <a href="https://test.whatsonchain.com/tx/04a65c12a65a4ab9de251053069b29a6328c82587bee67f0ef33786957685cab">token-swap_4</a></p><p>Each token swap transaction is of size under 330 bytes. Each zk-verifier transaction is of size 414 KB, and each proof transaction is of size 291 KB.</p><p>Please note that token transactions can be on any UTXO-based blockchain such as BTC. The verification transactions are only economically feasible on Bitcoin SV at the time of writing.</p><h4><strong>Why It Matters to the Community</strong></h4><ul><li><strong>Trustless and Decentralised:</strong> Every transaction is cryptographically verifiable, eliminating reliance on centralized authorities.</li><li><strong>Security at Scale:</strong> With miner-validated proofs, each transfer is inherently secure, reinforcing the trustless nature of blockchain, at a cost of roughly <a href="https://bsvblockchain.org/compare/">0.02 USD</a> per verification.</li><li><strong>Interoperability:</strong> Our protocol can be integrated with any UTXO-based blockchain, opening doors for broad community adoption and collaboration.</li></ul><h4><strong>Real-World Impact and Community Applications</strong></h4><ul><li><strong>NFT Ecosystems</strong><br> Our technology simplifies NFT issuance and validation on Bitcoin, empowering digital artists, gamers, and content creators to leverage blockchain without compromising security or scalability.</li><li><strong>Decentralised Finance (DeFi)</strong><br> With efficient proof generation and verification, our solution can underpin complex DeFi applications that require rapid, secure, and verifiable transactions.</li><li><strong>Open-Source Collaboration</strong><br> We’re actively inviting the blockchain community to test, refine, and expand our protocol. By contributing to an open, transparent framework, you can help shape the future of decentralized token transactions.</li></ul><h4><strong>Upcoming Work</strong></h4><ul><li><strong>Universal Groth16 Framework</strong><br> We’re developing a framework to make Groth16 universal, broadening its utility across blockchain applications.</li><li><strong>Decentralised Setup via MPC</strong><br> We are going to leverage secure multi-party computation (MPC) to decentralise the Groth16 setup. This will eliminate any single point of trust, ensuring a truly trustless system.</li></ul><h4><strong>Call for collaboration and partnership</strong></h4><p>Are you passionate about decentralisation and blockchain innovation? We invite you to join our journey. Share your insights or partner with us to push the boundaries of blockchain technology. Let’s build the future together, one proof at a time.</p><p>Drop your comments, suggestions, and questions below. We value every piece of feedback from our vibrant community. If you’re excited about our approach, share this blog on your social channels.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=954a17fb4171" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Four First-Ever ZKP Verifications on Bitcoin]]></title>
            <link>https://medium.com/@w.zhang/four-first-ever-zkp-verifications-on-bitcoin-9475df11d57e?source=rss-c864c38ff720------2</link>
            <guid isPermaLink="false">https://medium.com/p/9475df11d57e</guid>
            <category><![CDATA[verifiable-computation]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[layer-2-solution]]></category>
            <dc:creator><![CDATA[Wei Zhang]]></dc:creator>
            <pubDate>Thu, 28 Nov 2024 11:55:01 GMT</pubDate>
            <atom:updated>2024-11-28T11:55:01.581Z</atom:updated>
            <content:encoded><![CDATA[<h4>Spot the Difference</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*X3k45aEzsRNlfCLiM78mXQ.png" /><figcaption>AI generated image</figcaption></figure><p>17 July 2024, <a href="https://bitcoinmagazine.com/technical/a-zero-knowledge-proof-is-verified-on-bitcoin-for-the-first-time-in-history">Starkware</a> claims that the first-ever Zero-Knowledge proof is verified on the Bitcoin testnet, Signet.</p><p>19 July 2024, <a href="https://medium.com/@w.zhang/snark-verification-on-a-bitcoin-mainnet-c467991d931c">nChain</a> claims that the first-ever Zero-Knowledge proof is verified on a Bitcoin mainnet.</p><p>23 July 2024, <a href="https://x.com/BTC_OS/status/1816180788938870815">BitcoinOS</a> claims that the first-ever Zero-Knowledge Proof is verified on the Bitcoin mainnet.</p><p>24 July 2024, <a href="https://x.com/bitvmx/status/1816123923106259394?s=19">BitVMX</a> claims that the first-ever Zero-Knowledge Proof is verified interactively on a Bitcoin testnet.</p><p>What was going on there?</p><p><strong>StarkWare</strong> used STARK, a hash-function-based proof system that requires OP_CAT to implement proof verification in-script. They tested their implementation on a BTC testnet called Signnet, which is the only one that has OP_CAT enabled. In their example, the verification script verifies that the prover knows or has computed correctly the 32nd number in the Fibonacci squared sequence. More technically speaking, the circuit underlying the computation that is verified on-chain consists of tens of additions and one multiplication, which probably resulted in less than 100 constraints. A series of 11 TapRoot transactions were created to verify the proof, with a total size of roughly 4MB. While the implementation is a toy example and the transactions are testnet transactions, it does not undermine the efforts and talents behind the success. The StarkWare team has certainly demonstrated their incredible capability to build complex Bitcoin scripts. The future of STARKs on BTC mainnet is still uncertain. The main bottleneck is likely to come from the proof size. STARK is designed to significantly improve the proof generation time. As a result, it loses succinctness in proof size. When 128-bit security is needed, the proof size and transaction size may become economically or even computationally unviable for many real-world use cases. They also have to wait for OP_CAT to be enabled on BTC mainnet, which cannot be guaranteed to happen.</p><p><strong>nChain zkScript</strong> team used Groth16, a proof system that enjoys the smallest proof size and efficient verification time. They tested their implementation on a Bitcoin mainnet called BSV, which has all the original Bitcoin arithmetic opcodes available including OP_MUL and OP_MOD on large integers. These opcodes make implementing cryptographic schemes much more feasible on BSV than on BTC. In their example, the verification script verifies that the prover has computed SHA256 correctly on an input of 5 bytes. The circuit consists of 40875 constraints. However, Groth16 has a constant proof size with respect to the number of constraints. Using existing libraries such as <a href="https://github.com/arkworks-rs">arkworks</a>, nChain has subsequently verified a circuit consisting of over 700,000 constraints on BSV mainnet to demonstrate, with <a href="https://github.com/nchain-innovation/zkscript_package/tree/main/examples/ai_inference">a toy example</a>, <a href="https://medium.com/@w.zhang/verifiable-ai-on-bitcoin-fccb66eeee71">verifiability in machine learning</a>. In both cases, the transaction is less than 500KB and to spend the output requires another transaction of around 40KB. The implementation is on BLS12–381 curve which leads to 128-bits of security. While using Groth16 creates no problem in terms of proof size or verification efficiency, it has a bottleneck in proof generation. nChain zkScipt team also implemented MNT4–753 curve to enable recursive Groth16, in which case, the bottleneck in proof generation would be hit more easily. The team is exploring other proof systems and a composition of different proof systems to expand the scope for applicable use cases.</p><p>In fact, the first one to experiment Groth16 verification in Bitcoin script was <strong>sCrypt</strong>. Their implementation resulted in a <a href="https://whatsonchain.com/tx/320ba9fb3826c0bc66beed51edf2463e958b7274921563c5c90be62deabb725f">transaction</a> of 11MB on BSV mainnet as early as 2022. Strictly speaking, nChain zkScript team can only claim that they are the first to do it practically (compliant to network policy of 500KB limit on the locking script) on the BSV mainnet.</p><p><a href="https://cryptoslate.com/open-source-zero-knowledge-proofs-now-available-on-bitcoin-via-bitsnark/"><strong>BitcoinOS</strong> has a different approach</a>. They do not require any changes to BTC. They use something called <a href="https://www.bitcoinos.build/blog/bitcoinos-open-sourcing-the-bitsnark-verification-protocol">Merkle Mesh</a>, which is to handle many decentralised verifications at scale off chain (not on Bitcoin). As the proof is not directly verified in Bitcoin script, the challenge of using Bitcoin opcodes to implement complex algorithms is avoided instead of being tackled. What we can say is that StarkWare and nChain are trying to achieve something that seems impossible while Bitcoin OS focuses on delivering a solution that could work on BTC today.</p><p><a href="https://bitvmx.org/knowledge/zero-knowledge-proof-verification-on-bitcoin"><strong>BitVMX</strong>’s approach</a> is an interesting blend of what has been mentioned so far. They use Groth16 as a proof system to show that a STARK proof has been verified correctly. This hybrid approach addresses both the bottleneck of proof generation in Groth16 and the bottleneck of proof size in STARK. STARK is first used to efficiently generate a proof that a specific computation is done correctly, resulting a non-succinct proof. Groth16 is then used to generate a succinct proof that the non-succinct STARK proof is verified correctly. Assuming that generating a Groth16 proof on the computation for verifying a STARK proof is significantly more efficient than on the computation of the specific computation, the hybrid approach is better-off. Like BitcoinOS’s approach, the Groth16 proof is verified off-chain (not on Bitcoin). BitVMX then implemented a One-Time-Signature scheme in Bitcoin script to attest to the Groth16 proof. The attestation transaction is then published on a Bitcoin testnet. Their solution also allows others to challenge the attestation. It seems that they have a great solution, but imagine their Groth16 proofs being verified on Bitcoin directly. Isn’t that even better?</p><p>It is great to see many teams are trying to bring more functionalities and utilities to Bitcoin by leveraging ZKPs. I hope this gives a clear and objective picture of the current state of zkp verification on Bitcoin. Of course, given that I am part of the nChain zkScript team, I cannot deny my unintentional bias😊. If there is anything inaccurate in the text above, please do not hesitate to contact me.</p><p>research.enquiries@nchain.com</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9475df11d57e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Now that OP_CAT is out of the bag…]]></title>
            <link>https://medium.com/@w.zhang/now-that-op-cat-is-out-of-the-bag-af8b56563f06?source=rss-c864c38ff720------2</link>
            <guid isPermaLink="false">https://medium.com/p/af8b56563f06</guid>
            <category><![CDATA[op-cat]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[bitcoin-script]]></category>
            <dc:creator><![CDATA[Wei Zhang]]></dc:creator>
            <pubDate>Thu, 17 Oct 2024 11:25:02 GMT</pubDate>
            <atom:updated>2024-10-17T15:27:28.974Z</atom:updated>
            <content:encoded><![CDATA[<h4>Possibility vs Feasibility</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aAM2iq5hlgsZUlP0UnHz5g.png" /><figcaption>Image created by DALL.E 3</figcaption></figure><h4>Adapting to Survive and Thrive</h4><p>Bitcoin Script is a <a href="https://www.forth.com/starting-forth/1-forth-stacks-dictionary/">FORTH</a>-like programming language that supports a dictionary of <a href="https://en.bitcoin.it/wiki/Script">opcodes</a>. There are 18 constant opcodes representing integers -1, 0, 1, …, 15 and 16. There is a set of opcodes dedicated to loading data during script executions; and each is used to indicate the size of the data element. The more interesting set is the functional opcodes which include flow control, stack movement, cryptographic algorithms, arithmetic and string operations. For Bitcoin Core (BTC), however, most of the opcodes related to arithmetic and string operations are disabled. OP_SIZE which determines the length of a string is the only available opcode for strings. Arithmetic operations are limited to basic addition and subtraction on 32-bit integers, capping at a maximum value of 65,536. In short, as things stand, there is no fun playing with these opcodes.</p><p>This situation was mainly caused by concerns over security. However, there was only one concrete vulnerability identified, namely, denial of service (DOS) attack. The rest of the concerns, to say the least, are not evidence-based and more about the belief that Bitcoin should stay as primitive as possible. Despite the limitations on opcodes, Bitcoin still enjoys its supremacy in market capitalisation even after Ethereum dominated the smart contract and ICO markets. Though just before the last halving in April 2024, token standards such as Ordinal and BRC20 started to emerge on BTC. This is clearly an adaptation to the market: Bitcoin needs to evolve to become fit enough to survive and thrive.</p><h4>Challenging the Status Quo — OP_CAT</h4><p>The status quo of the BTC community is challenged by <a href="https://github.com/bitcoin/bips/blob/master/bip-0347.mediawiki">BIP347</a> which proposes to re-enable OP_CAT, an opcode that concatenates two strings. The original motivation was to give developers the ability to create complex rules for spending transactions in Bitcoin Script (often referred as <a href="https://maltemoeser.de/paper/covenants.pdf">covenant </a>transactions), unlocking potential new use cases like <a href="https://nchain.com/wp-content/uploads/2022/03/WP1605_PUSHTX-and-its-Building-Blocks.pdf">self-propagating smart contracts</a>. Its usefulness is demonstrated by the recent success of a new token protocol called <a href="https://catprotocol.org/">CAT20</a>.</p><p>The support for re-enabling OP_CAT grew significantly with the realisation that OP_CAT can enable implementations of Zero-Knowledge Proof (ZKP) verification (in the form of <a href="https://starkware.co/stark/">STARKs</a>). This is a big and pleasant surprise to many as it shows that BTC is just one opcode away from having smart contract capability comparable to Ethereum. However, the truth is less convenient than it appears. The implementation of ZKP verification using OP_CAT may result in less economically viable or insecure solutions for many real-world use cases.</p><h4>The Debate</h4><p>Here is a quick summary of the arguments for and against re-enabling OP_CAT on BTC.</p><p><strong>For</strong>:</p><p>1. It brings more functionalities such as covenant transactions and on-chain ZKP verifications.</p><p>2. It requires minimal change.</p><p>3. It may bring post-quantum security.</p><p><strong>Against</strong>:</p><p>1. It violates the belief that Bitcoin should stay simple.</p><p>2. It introduces security vulnerabilities or security risks.</p><p>To put my two <em>sats </em>in the debate, I would say the choice is more of a spectrum than it is binary, ranging from “no change at all — stay primitive” to “enable all opcodes — stick to original design”, or even extending to “add new opcodes — keep innovating”. What about re-enabling “OP_MUL” for integer multiplication too? What about “OP_MOD” which can be useful for many cryptographic schemes? What about adding a new opcode OP_SNARKVERIFY for <a href="https://medium.com/@LightecXYZ/bitcoin-dev-proposal-new-opcode-op-zkp-to-enable-zkp-based-spending-authorization-7011ec9775e6">ZKP verification</a> (I would love that :P)? Enabling OP_CAT is just a choice among many. Some would probably argue “but that is the best deal in a decade: minimal change to make a huge difference”. Personally, I agree with this argument, but the implicit cost-benefit analysis behind that statement is in fact quite subjective.</p><p>I hope by now you can see that this is about striking a balance between opportunities and risks (or conventional beliefs). Striking a balance is difficult and it requires iterations. Fortunately for BTC, there are three real-world examples to gather information from.</p><h4>Learning From Others</h4><p>The first one is Bitcoin Cash (BCH). In 2019, they introduced a new opcode to allow verification of digital signatures on any data element on the stack, OP_CHECKDATASIG, which enabled use cases that were deemed valuable at the time. While most people would find it useful, it did not pick up any traction since its introduction. (If you google OP_CHECKDATASIG, you can find the top search results are from 5 years ago…)</p><p>The second example is <a href="https://www.fractalbitcoin.io/">Fractal Bitcoin</a>, a blockchain that is launched in early 2024. It uses all the opcodes that BTC uses and OP_CAT. Its popularity is reflected by its price since launch, dropping from $30 to $6, with only one major use case that is quite successful — CAT20. The developers seem to have enjoyed the excitement of using OP_CAT to create new use cases, but shortly after, they crave more.</p><p>The third example is Bitcoin Satoshi Vision (BSV), which has all the functional opcodes available as in the original Bitcoin node software including arithmetic on big integers. This allows many cryptographic operations to be performed during script execution. The main tactic BSV adopts to mitigate DOS attacks is to put a limit on memory usage for script execution. The limit is policy-based in the sense that mining nodes can adjust the limit based on their preferences but must accept other’s policy limit during block validation. Together with other policy parameters, BSV essentially passes the power from developers to miners who actually have stake in the game. The miners can adjust those parameters to be more suited for the market, and more importantly, be more adaptable for the ever-changing nature of the market. <a href="https://whatsonchain.com/tag-stats?days=all&amp;filtertags=STAS">Covenant transactions</a> on BSV mainnet can be found back in 2021 if not earlier. A Groth16 verification with bilinear pairing operations can be implemented under 500 KB, you can find <a href="https://whatsonchain.com/tx/e4cd00c1fa7dd6931dd1e45034e9d9f732e6d7d38f7826341715f488a146514c">the full script</a> on the mainnet. This is <em>not </em>an optimistic approach or using dummy security parameters. If you want to experience the power of “OP_MUL”, “OP_MOD” and the support for big integers, you can try it out yourself using <a href="https://github.com/nchain-innovation/zkscript_package">zkScript</a>.</p><h4>Possibility vs Feasibility</h4><p>OK, that was a tiny little bit bias with the intention to promote the wonderful work our team has produced. Coming back to the serious debate, if BTC wants to stay uniquely simple while all other blockchains innovate, it is unlikely for it to be economically sustainable in the long run after a couple more halvings. Enabling OP_CAT is a good opportunity to initiate a wider discussion on how BTC should move forward.</p><p>If your conclusion is to have a simple and secure blockchain that is functional just enough to support a diversified all-rounder Layer 2 or overlay networks, then I would recommend enabling OP_MUL, OP_MOD and BigNum support.</p><p>OP_CAT can make things possible, but not necessarily feasible. Why stop at being possible? Go for feasibility — real world applications! What do you think? Please share your thoughts in the comments!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=af8b56563f06" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Why bring ZKPs to Bitcoin?]]></title>
            <link>https://medium.com/@w.zhang/why-bring-zkps-to-bitcoin-3e1af3189e0c?source=rss-c864c38ff720------2</link>
            <guid isPermaLink="false">https://medium.com/p/3e1af3189e0c</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Wei Zhang]]></dc:creator>
            <pubDate>Fri, 20 Sep 2024 10:00:08 GMT</pubDate>
            <atom:updated>2024-09-30T10:27:43.797Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/653/1*wSGMaeF67giNNKnHsiDHpA.png" /><figcaption>Image generated by Dall-E 3</figcaption></figure><p>Since late 2023 there has been a surge of interest in bringing zero-knowledge proofs (ZKPs) to Bitcoin. For Ethereum, ZKPs are the hope for scalability. For Bitcoin, they are the enabler for complex and flexible smart contracts — something many thought was impossible. This is achieved by moving smart contract execution off-chain and relying on verification of ZKPs on-chain to preserve the benefits of a blockchain.</p><p>While Bitcoin communities including us are proud to achieve <a href="https://github.com/nchain-innovation/zkscript_package">ZKP verifications on-chain</a>, there is in fact an outstanding set of tricky questions that need to be answered, or at least discussed.</p><blockquote>If Bitcoin can do what Ethereum can do, so what? Why do we need two blockchains that do the same thing? Are there any differences?</blockquote><p>Of course, for a healthy market, it’s always better to have more than one option. There are also many people believing that Bitcoin is more secure than Ethereum due to its hash power, but surely there is no consensus on that. Any more convincing arguments?</p><p>Yes, there is a subtle difference between Bitcoin and Ethereum smart contracts. That is, Bitcoin is UTXO-based and Ethereum is account-based. To some extent, one can simulate the other. However, fundamentally, they can induce different use cases. The subtlety comes from the fact that in most use cases the difference can be by-passed at solution-design level.</p><p>An Ethereum smart contract is stored on-chain with a fixed account address and is expected to be called by multiple users or multiple times. On the other hand, a Bitcoin smart contract is expected to be called by one entity once. This is the defining nature of a UTXO-based blockchain: an unspent transaction output can only be spent once. For a Bitcoin smart contract to be called by multiple users or multiple times, new instances must be created based on published templates which may be customised as needed. Please see Figure 1 for illustration.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/940/1*us18KiNSozSDdPLpf3WLDg.png" /><figcaption>Figure 1. Ethereum smart contract vs Bitcoin smart contract</figcaption></figure><p>If we take these insights at face value, we can wave our hands and say that Bitcoin is better for one-time contracts and/or private contracts, while Ethereum is better for contracts that are intended for the public and/or used frequently. But this statement is nowhere near absolute. It gives a rough guideline when it comes to choosing which blockchain to build your smart contracts.</p><p>Taking peer-to-peer economy as an example, whether it is ride sharing, room renting or money lending, any interaction between two peers is different and is likely to be one-off. Bitcoin would be more situated for smart contracts in these use cases. On the other hand, ERC20 smart contracts that require interactions with many users and potentially other contracts may be better off on Ethereum.</p><p>There is a perception that Bitcoin is supposed to remain simple, like digital gold. In fact, when we submitted our academic paper about <a href="https://eprint.iacr.org/2024/1498">SNARK verification on Bitcoin</a> for double-blind peer review, one of our reviewers made the same comment. This is a hard comment to respond to. After mulling it over, we realised that economic sustainability is the key to answering the challenge.</p><p>Securely maintaining Bitcoin is very costly and will get more expensive as technology advances. The miners are fully decentralised and governed by only one thing, economic incentive. Block rewards are halved every four years, and its contribution to the economic incentive is diminishing. They are essentially subsidies for a newly established industry. Any sustainable industry must be able to survive and thrive without subsidies. That puts all the pressure on transaction fees which are the other part of the economic incentive. The economic value of the transaction fees can be interpreted as fees in bitcoin multiplied by the price of bitcoin.</p><p>We think arguing that the price would go up is just wishful thinking. It might be the case, but if a miner invested so heavily to secure Bitcoin, they would expect to have a more sustainable business model that does not rely so much on the price of Bitcoin. Therefore, there must be enough fees in bitcoin to keep the economic incentive strong and the network secure. This implies better transaction services, or more specifically, scalability and functionality. Bringing complex and flexible smart contracts to Bitcoin can certainly help to achieve that.</p><p>We hope that we have answered the questions well enough to convince you that there is value in bringing ZKPs to Bitcoin. If not, we are happy to hear your arguments supporting or against it! 😊</p><p>research.enquiries@nchain.com</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3e1af3189e0c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Verifiable AI on Bitcoin]]></title>
            <link>https://medium.com/@w.zhang/verifiable-ai-on-bitcoin-fccb66eeee71?source=rss-c864c38ff720------2</link>
            <guid isPermaLink="false">https://medium.com/p/fccb66eeee71</guid>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[verifiable-ai]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Wei Zhang]]></dc:creator>
            <pubDate>Tue, 17 Sep 2024 07:24:33 GMT</pubDate>
            <atom:updated>2024-09-17T10:19:48.316Z</atom:updated>
            <content:encoded><![CDATA[<h4>Combining AI, Blockchain and Cryptography</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*sxA00Vu5DhCaod4A" /><figcaption>Photo by <a href="https://unsplash.com/@drscythe?utm_source=medium&amp;utm_medium=referral">Dominik Scythe</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Verifiable AI is about the ability to ensure and demonstrate that an AI system operates according to its specifications, free of critical bugs, and adheres to ethical standards such as fairness, transparency, and safety — ideally without revealing proprietary information of the system. This is a relatively new research area, and we have just started exploring.</p><p>Not long ago, we successfully implemented <a href="https://medium.com/@w.zhang/snark-verification-on-a-bitcoin-mainnet-c467991d931c">verifiable computation on Bitcoin</a>. One of our AI experts made an interesting comment: “Why not apply this to machine learning?! Training is computation. Inference (processing queries) is computation. If we can do verifiable computation, then we can do verifiable training and verifiable inference.”</p><p>Interestingly, two weeks after the suggestion, Ebrahimi et al. presented an academic paper on the same topic: “Blockchain-based Federated Learning Utilizing Zero-Knowledge Proofs for Verifiable Training and Aggregation”, winning the best paper award at a conference we attended. They have <a href="https://github.com/ElmiraEbrahimi/Veriblock-FL">an implementation</a> in a simulated local Ethereum environment. Their work represents a significant step forward in integrating blockchain and cryptography with AI. Many congratulations to them!</p><p>With verifiable computation approach, we can prove cryptographically that an AI model is trained on the claimed dataset. For example, it can be proven that a generative AI model is trained on a dataset that is known to have no bias. Probably more importantly, AI developers can prove that they did not tamper with the training dataset to train an AI model for malicious intentions. We can also prove that an output of an AI model is obtained by running the specified AI model on the given input. For example, a piece of artwork can have a proof showing that it is generated by an AI model on a given prompt; or as a paid user, you can be sure that you are getting answers from ChatGPT4, not the free versions.</p><p>With this context in mind, we are proud to announce that for the first time, we successfully demonstrated verifiable inference on Bitcoin. You can find relevant <a href="https://whatsonchain.com/tx/909cf48578535b8775b90f2ad0c9187dc5b8d42cb06c533ae5f80dbc43060e2f">transactions </a>on the Bitcoin SV mainnet, and the code that generates them on <a href="https://github.com/nchain-innovation/zkscript_package">our zkScript GitHub repo</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/0*7uDaq169c3PeFeWG" /><figcaption>Recognising hand-written digits</figcaption></figure><p>We trained a simple neural network on the MNIST dataset of images of hand-written digits, achieving over 90% accuracy. The model was then run on an input image, such as one provided by a user, and produced an output predicting which digit the input image represents. A cryptographic proof was generated to verify the output was indeed produced by running the model on the specified image while hiding all the information about the model (details to be found at the end). The proof was subsequently used to claim a small amount of bitcoin on the blockchain from the user. Here, Bitcoin not only provides a decentralised independent verification platform for but also facilitates a micro-payment between a user and an AI model. What more can you ask from a blockchain?</p><p>Very well done to the team that made it possible, <a href="https://licensing.nchain.com/team/Hamid_Attar">Hamid</a>, <a href="https://licensing.nchain.com/team/Luigi_Lunardon">Luigi</a>, <a href="https://licensing.nchain.com/team/Federico_Barbacovi">Federico </a>and <a href="https://licensing.nchain.com/team/Mathieu_Ducroux">Mathieu</a>! We will continue our exploration in verifiable AI leveraging blockchain technology and cryptography. Stay tuned!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0IeslvuuymaA9OR1" /><figcaption>Photo by <a href="https://unsplash.com/@siderius_creativ?utm_source=medium&amp;utm_medium=referral">Gerard Siderius</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>PS: For those who are interested, here is some technical detail…</p><h4>Floating Points vs Integers</h4><p>The main challenge is the fact that neural networks work with floating points while zero-knowledge proofs work with integers. Fortunately, back in 2017, Jacob et al. described an approach to quantise AI models without losing accuracy in <a href="https://openaccess.thecvf.com/content_cvpr_2018/papers/Jacob_Quantization_and_Training_CVPR_2018_paper.pdf">an academic paper</a>. They needed this for migrating pre-trained AI models from powerful servers to less capable mobile devices. As part of the process, they convert floating points to integers to reduce the dimension of the model for efficiency. We managed to adapt the methodology to fit our purposes and maintain an accuracy above 90%. There are other techniques to quantise an AI model. For example, research groups such as <a href="https://docs.zama.ai/concrete-ml/explanations/quantization">ZAMA</a> are exploring quantisation-aware training where a model is trained with an awareness that the weights will be converted to integers later.</p><h4>Preserving Confidentiality of AI Models</h4><p>We used a hash function to hide the weights of the model. Only the hash value of the weights is in public. The computation circuit consists of the computations in running the AI model and in evaluating the hash function to make sure the same weights are used for both computations. For proof generation, we use libraries provided by <a href="https://github.com/arkworks-rs">arkworks</a>. Both the verification key and the proof are formatted in JSON files and passed to our zkScript tool to create locking script and unlocking script respectively. You can find the example use case <a href="https://github.com/nchain-innovation/zkscript_package/tree/main/examples#">here</a>.</p><p>We are happy to hear from you if you have any questions or comments!</p><p>research.enquiries@nchain.com</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fccb66eeee71" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[SNARK Verification on a Bitcoin Mainnet]]></title>
            <link>https://medium.com/@w.zhang/snark-verification-on-a-bitcoin-mainnet-c467991d931c?source=rss-c864c38ff720------2</link>
            <guid isPermaLink="false">https://medium.com/p/c467991d931c</guid>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Wei Zhang]]></dc:creator>
            <pubDate>Thu, 08 Aug 2024 15:21:19 GMT</pubDate>
            <atom:updated>2024-09-30T11:17:47.156Z</atom:updated>
            <content:encoded><![CDATA[<h4>The beginning of a new era for Bitcoin</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gZZX6paJd0GRgNpsYdBM1g.jpeg" /></figure><p>On 19th July 2024, a <a href="https://whatsonchain.com/tx/e4cd00c1fa7dd6931dd1e45034e9d9f732e6d7d38f7826341715f488a146514c">transaction</a> was successfully spent using a zero-knowledge proof on the Bitcoin SV mainnet. More precisely, the Bitcoin SV network successfully verified a <a href="https://eprint.iacr.org/2016/260.pdf">Groth16</a> proof as part of a transaction validation. This is the first time that it has been achieved on Bitcoin or any of its variants.</p><p>It is a significant milestone for Bitcoin as it paves the way for smart contracts on-chain. Bitcoin, perceived as lacking computation capability, can now verify proofs that computations are done correctly. This approach to smart contracts not only offers scalability but also addresses privacy concerns over a public blockchain.</p><p>Recently, BitVM and StarkWare have made similar impressive announcements. StarkWare published a series of <a href="https://mempool.space/signet/tx/ed45d9bb8ca8c4c282fd73255260689c7de1b146eadfebcfeb2dc9e7ec18b722">transactions</a> that <a href="https://www.theblock.co/post/305832/starkware-bitcoin-test-network-zk">verify a STARK proof</a>, while <a href="https://x.com/bitvmx/status/1816123923106259394?s=19">BitVM verified a SNARK proof</a>. The big difference is that all of these transactions were published on the BTC testnet (Signet) rather than mainnet. They can be moved to the mainnet only if the network enables OP_CAT, an opcode that concatenates inputs. <a href="https://scrypt.io/">sCrypt</a> were the first to implement Groth16 verification on Bitcoin SV testnet. Their <a href="https://scryptplatform.medium.com/efficient-zk-snarks-on-bitcoin-technical-explainer-880fa04ee155">5MB verification script</a> was improved by a <a href="https://github.com/frenchfrog42/zk-hackaton">hackathon entry</a> <a href="https://devpost.com/software/zkbaguette">ZkBaguette</a> who reduced its size to 1.2 MB. While all these groups, including ourselves, use different techniques and different versions of Bitcoin, we have tackled the same underlying challenge: coding up something very complex in very primitive Bitcoin opcodes.</p><p>We chose to implement Groth16 because its characteristics are well suited to optimising transaction size, and therefore transaction fees. Groth16 has the smallest proof size among all SNARKS with a very efficient verification algorithm. Our smallest implementation to date is Groth16 for the curve BLS12–381, which achieves a locking script size of 480KB and an unlocking script of 40KB. We chose to implement it on Bitcoin SV as it supports large number arithmetic and has a default script size limit of 500KB on its mainnet. Moreover, taking advantage of the low transaction fee rate on Bitcoin SV, we only paid roughly USD 0.015 for creating and spending the <a href="https://whatsonchain.com/tx/e4cd00c1fa7dd6931dd1e45034e9d9f732e6d7d38f7826341715f488a146514c">transaction</a>.</p><p>We are now in the process of refining and improving our implementation in order to deploy recursive Groth16 on-chain. This will be a critical building block for many applications. You can follow our progress on <a href="https://github.com/nchain-innovation/zkscript_package">Github</a>. You can also download the repository and test it out yourself. Any feedback is welcome!</p><p>We have written up our work in <a href="https://eprint.iacr.org/2024/1498.pdf">an academic paper</a> which will be published soon. It is the culmination of a great team effort involving the nChain Cryptography team (<a href="https://licensing.nchain.com/team/Enrique_Larraia">Enrique</a>, <a href="https://fr.linkedin.com/in/paul-germouty-01506314a">Paul</a> and <a href="https://licensing.nchain.com/team/Wei_Zhang">Wei</a>) along with our senior researcher <a href="https://licensing.nchain.com/team/Federico_Barbacovi">Federico</a>, who spent months understanding the literature behind bilinear pairings and optimising the computation with respect to the transaction size. Federico then turned our ideas on paper into transactions on Bitcoin with further optimisations to reduce the transaction size. Well done to everyone involved! We also would like to congratulate BitVM, Starkware and sCrypt for their achievements. We know very well how challenging it is!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c467991d931c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Simplified Payment Verification]]></title>
            <link>https://medium.com/nchain/simplified-payment-verification-48ac60f1b26c?source=rss-c864c38ff720------2</link>
            <guid isPermaLink="false">https://medium.com/p/48ac60f1b26c</guid>
            <category><![CDATA[bitcoin-sv]]></category>
            <category><![CDATA[instant-payment]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[digital-signatures]]></category>
            <dc:creator><![CDATA[Wei Zhang]]></dc:creator>
            <pubDate>Tue, 25 Aug 2020 11:54:11 GMT</pubDate>
            <atom:updated>2021-04-19T07:49:57.643Z</atom:updated>
            <content:encoded><![CDATA[<h4>Instant payment, signature validity, and the importance of integrity</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*lcVAc3aBC88GUXcj" /><figcaption>Photo by <a href="https://unsplash.com/@skillscouter?utm_source=medium&amp;utm_medium=referral">SkillScouter</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>The concept of Simplified Payment Verification (SPV) can be traced back to the Bitcoin white paper in 2008. It provides a scalable mechanism for verifying whether a transaction has appeared in a block. However, there are some subtle but important aspects of SPV that are often overlooked. This article will explore the role that SPV plays in enabling instant payments, data ownership, and legal compliance.</p><h3>Proof of publication in a block</h3><p>Section 8 of the Bitcoin white paper introduces SPV as the process of verifying whether a payment has been accepted by the Bitcoin network. The verifier is assumed to have access to a list of block headers, and it takes an input consisting of a Bitcoin transaction and its Merkle proof. If the Merkle proof leads to a Merkle root which appears in one of the block headers, it means that the transaction has indeed been published in that block. The process is considered as simplified because it only requires three pieces of information:</p><p>1. a list of block headers (under 52 MB at the time of writing),</p><p>2. a transaction (under 400 bytes for a simple Pay-to-Public-Key-Hash transaction¹), and</p><p>3. a Merkle proof (928 bytes assuming the block containing 1 billion transactions).</p><p>Consider a merchant, say Bob, who maintains a list of block headers. When he receives a payment transaction from his customer, say Alice, he can verify that the payment has appeared in a block as soon as its Merkle proof is obtained. If a BIP-270 process is implemented, it is Bob himself (or a receiver in general) who is responsible for sending the transaction to the Bitcoin network and obtaining a Merkle proof. This process works very well with an SPV client because the merchant has all three pieces of information required to carry out the verification.</p><p>The cost for Bob to run this system is much lower than the cost of maintaining a full copy of the blockchain. Given the lightweight nature of this mechanism in terms of storage and bandwidth, it is not difficult to see that this can be scaled up easily.</p><h3>Instant Payments</h3><p>Somewhat counter-intuitively, SPV may also be used for payments that are effectively instant. In this case, the customer, Alice, provides two transactions and one Merkle proof to the merchant, Bob. One is a payment transaction. The other is the transaction whose output is referenced by the payment transaction. Let us call it the previous transaction from now on. The Merkle proof is for the previous transaction. (The number of previous transactions required depends on the number of inputs in the payment transaction. For simplicity, we assume only one transaction is referenced in the payment transaction as an input.) Note that the payment transaction does not have a Merkle proof at this point.</p><p>One motivation for the simplified payment verification on the previous transaction is to have a fail-fast mechanism to allow Bob to detect invalid payment transactions quickly before it is sent to the Bitcoin nodes. This is because the proof that the previous transaction exists on the global ledger provides some assurance that Alice did indeed have the necessary funds at some point in the past.</p><p>In fact, there is a much more fundamental motivation to conduct this simplified payment verification on the previous transaction: to prove <em>the integrity of a transaction</em>.</p><p>The simplified payment verification on the previous transaction is to ensure the data in the previous transaction provided by the customer has not been tampered with. Before we explain this in detail, we would like to make a reasonable assumption that digital signatures are legally binding. Note that this has been the case in the UK since 2000.</p><h3>Digital signature validity</h3><p>Consider once again our favourite characters, Alice and Bob. Suppose Alice would like to purchase a games console from Bob. She sends a payment transaction to Bob.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qrKA6iwxbpxkpvjNBd1rrg.png" /><figcaption>Payment Transaction, TX_payment</figcaption></figure><p>Looking at this payment transaction, Bob can determine that it spends an output from transaction TX_previous, and assigns x amount to him as he has asked for. To be convinced of its validity, he could send this transaction to the Bitcoin nodes and wait for a response, but it would take a while. To serve his customers better, Bob realises that there is a digital signature in the payment transaction, (Sig_A,PK_A). If he can verify the digital signature and ensure it is coming from Alice, he would be happy to complete the trade as Alice would be legally responsible for her actions due to the presence of her signature. As an analogy, one can think of paying by a credit card and a signature is required to confirm the payment, where the verification of the signature is to check whether it is the same as the one on the back of the card. When the purchase is for a high value item, a photo ID may be required to assist the verification.</p><p>One implicit assumption we have made is that Bob is able to link Alice’s identity to the public key. This assumption might not hold in some cases, for example if the value of the transaction is sufficiently low. However, given the benefits of effectively instant payments and the need for auditing and national taxation, the assumption can be justified and realised via loyalty programs, certified public keys², or any other incentive or enforcing schemes. It is not unreasonable to expect that soon a provable link to identity may be a legal requirement for purchases over a certain threshold.</p><p>In general, to verify a digital signature one needs three pieces of information:</p><ol><li>the digital signature,</li><li>a public key, and</li><li>a message.</li></ol><p>We can see that Bob has the first two. However, the message depends not only on the payment transaction but also some fields in the <em>previous transaction</em>, TX_previous.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9IYCri56u4ndM3s_bez7Fg.png" /><figcaption>Previous Transaction, TX_previous</figcaption></figure><p>The signed message contains the first output from the previous transaction, namely the value and the locking script, which is referenced in the payment transaction. One might say that it would be enough for Alice to additionally provide w and OP_DUP OP_HASH160 &lt;H(PK_A)&gt; OP_EQUALVERIFY OP_CHECKSIG to Bob for him to verify the signature. However, Alice cannot prove the integrity of the data that is extracted from the previous transaction unless Alice provides the previous transaction in its entirety and its Merkle proof. The Merkle proof as an integrity proof tells Bob two things</p><p>1. the locking script is indeed asking for a digital signature with respect to a specific public key (e.g., a Pay-to-Public-Key-Hash script), and</p><p>2. the locking script has not been modified.</p><p>The importance of this integrity check on the previous transaction is often underestimated. A locking script such as OP_DROP OP_DROP OP_TRUE in the previous transaction will allow Alice to put any pair of strings that look like a signature and a public key in the unlocking script. If Bob is given only the payment transaction, he cannot tell the validity of the signature or the legitimacy of the public key. Moreover, not knowing what the locking script in the previous transaction is implies that Bob cannot assume the Bitcoin nodes would verify the signature. As the example locking script shows, there is no OP_CHECKSIG and therefore there will be no signature verification when executing the script.</p><p>Note that many data applications such as Metanet applications rely on the validity of the signature and the public key in the unlocking script of a transaction to indicate data ownerships or access rights. <em>The validity of the transaction does not imply the validity of the signature</em> unless the previous transaction is provided and shows that a signature with respect to the given public key is required³.</p><p>If Bob asks for only the locking script and the value, then it is possible for Alice to generate a new pair of private and public keys and create a fake Pay-to-Public-Key-Hash locking script corresponding to the public key. She can then sign a message so that the resulting signature is valid when Bob verifies it on the payment transaction and the fake locking script. Therefore, it is crucial for Bob to conduct a simplified payment verification on the previous transaction as an integrity check before proceeding to a signature verification.</p><p>By verifying the digital signature successfully on the message with respect to the public key that links to Alice’s identity, Bob is convinced that Alice indeed has the rightful control over w bitcoins and approved to transfer x of them to him with her digital signature. In this case, Bob is willing to complete the trade as he knows Alice would be held legally responsible if she double spends. This is how SPV enables effectively instant payments.</p><h3>Summary</h3><p>When a digital signature and a public key in an unlocking script are being used meaningfully in some context, the integrity of the previous transaction, or more precisely, the integrity of the locking script from the previous transaction becomes extremely important. The proof on the integrity ensures that the digital signature in the unlocking script will be verified as a digital signature with respect to the given public key by the Bitcoin network. As described above, this can be achieved by using simplified payment verification on the previous transaction.</p><p>As in the story of Alice and Bob, the signature and the public key (linked to Alice’s identity) are regarded as a proof of Alice agreeing to pay Bob bitcoins for her purchase. Because of this interpretation, Bob needs to make sure the signature is valid and indeed from Alice. This concept also applies to data ownership or attestation in a transaction such as Metanet applications or attesting a document in an OP_RETURN payload via a transaction.</p><p>As a takeaway message, we want to stress that SPV can be used not only for proving the existence but also <em>the integrity</em> of a published transaction, and the integrity of the transaction implies the integrity of any data embedded in that transaction.</p><h4>Footnotes</h4><p>[1] If only transaction ID is provided for the verification on its existence, the verifier needs to know the depth of the Merkle tree or that the transaction ID comes from a raw transaction in order to confirm its existence. This is to ensure that the transaction ID is indeed a leaf on the Merkle tree instead of an internal node. Either piece of knowledge may require the verifier to store or have access to some additional information.</p><p>[2] To avoid re-using certified identity keys, Alice can derive a key pair from her identity key after Bob verifies her certificate. The derivation could be achieved, for example, by using a BIP32 unhardened key path, or based on a Diffie-Hellman key exchange between Alice and Bob. This is to ensure that Bob can verify the link between the public key that is used in the payment and the certified identity public key.</p><p>[3] We thank Xiaojie Tao, CTO from Volt, independently identified the importance of the previous transaction in validating a Metanet transaction: <a href="https://www.yuque.com/docs/share/0b224413-7987-4ebf-b0e3-6b268ae18f27">https://www.yuque.com/docs/share/0b224413-7987-4ebf-b0e3-6b268ae18f27</a>, and motivated us to write this article.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=48ac60f1b26c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/nchain/simplified-payment-verification-48ac60f1b26c">Simplified Payment Verification</a> was originally published in <a href="https://medium.com/nchain">nChain</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>