Trustless Bitcoin Bridge Creation with Witness Encryption - #27 by leohio - Cryptography - Ethereum Research Ethereum Research Trustless Bitcoin Bridge Creation with Witness Encryption Cryptography leohio February 8, 2022, 7:14am 3 Thank you for the better TLDR than mine. JustinDrake: TLDR: Using an MPC secure with just one honest participant, generate a mint Bitcoin address with the secret key witness encrypted under a proof that the wrapped token was burned. TR;DR of the mechanism: Only the person who can make a zkp proof of WBTC burn, or in other words, the person who burned WBTC, can know all N multisig private keys and unlock the bitcoin using special decryption. On the other hand, a malicious person has to collude with all the other N people who set the private key, so if there is even one honest person among the N people, they cannot steal it. It’s 99% attack tolerant because they cannot kill the liveness either. wdai February 9, 2022, 8:38pm 5 This is a fascinating application of witness encryption! To check my understanding, as this part of the bridge is not too explicitly described: the N different deposit address generators (let’s call them bridge managers, since they together do control the funds deposited) would need to manage the total deposited funds to make sure they give out WE ciphertexts to secret keys that holds specific amount of Bitcoins, correct? For example, if there is a single deposit of 2 BTC and then two later withdrawal of 1 BTC each. The bridge managers (generators) need to first split the 2 BTC in the Bitcoin UTXO to two UTXOs holding 1 BTC each. One remark regarding N-of-N multi-signature: since Bitcoin taproot upgrade and the support for Schnorr signatures, the coalition of N “generators” can actually support any threshold T, not just N-of-N–each manager (generator) can release via WE their Shamir-secret share of the actual secret key holding the coins. And if my above understanding is correct, then one should investigate holistically the differences between releasing secret keys (or shares) via WE and simply providing threshold signatures in the withdraw. To recall briefly the threshold signature based bridge: Deposit works similarly to what is sketched here. For each withdraw: the N bridge managers would independently verify the validity of a withdraw claim (proof of burn of WBTC and BTC withdraw address) and conduct a threshold signing session to transfer the BTC out to the withdraw address (fund splitting can be done at this step). Some first remarks regarding the differences (again, if my understanding of your system is correct): WE solution does not require interaction between the bridge managers (generators / key holders) Threshold signing does not rely on additional hardness assumptions that WE require and is more widely-studied (e.g. DFINITY is close to deploying threshold ECDSA on their mainnet. Threshold Schnorr is arguably simpler, e.g.this paper from 2001.) The actual trust assumption on the bridge managers, for both liveness and security, on the N bridge managers could be the same between the two solutions, in that one could select any threshold T. 2 Likes Killari February 11, 2022, 2:56pm 7 Sounds super interesting! I don’t really understand how can you recover the private key as a proof of burn of WTC? Is there some kind of light client in question that you produce a proof that there is enough PoW on top of the transaction you did? 1 Like leohio February 11, 2022, 5:45pm 8 I’m glad to have you interested in this. Killari: how can you recover the private key as a proof of burn of WTC? This is the exact part Witness Encryption is in charge of. Cipher texts of Witness Encryption can be decrypted when the set circuit is satisfied. We set a zkp circuit verifying that WBTC token is burned on Ethereum Layer1 by a withdrawer, as a circuit of Witness Encryption. The recent Witness Encryption is getting realistic rapidly. ADP Exact Cover Killari: Is there some kind of light client in question that you produce a proof that there is enough PoW on top of the transaction you did? The proof of difficulty and the proof of rightness on Ethereum PoS can be also verified by zkp circuits. There no need of light clients to verify the bridge, this is why this is described like this. leohio: No need for any node with liveness. Also, to complete the proof of rightness on Ethereum PoS, the proof of publishment of Ethereum PoS activity is on the Bitcoin blockchain OP_RETURN and included in the input of the zkp circuit. This prevents the colluded PoS validators from forking the chain privately to fake the WBTC burning on it. leohio: The Bitcoin script specification allows the ”OP_RETURN script” (Script Bitcoin Wiki, n.d.) to write arbitrary data into the transaction. 1 Like leohio February 11, 2022, 6:48pm 9 I am fed back the concern that the circuitry of the WE may become inconsistent during a hard fork, making decryption impossible, but this is solvable and something we did not mention in this paper for simplicity. In a simple construction, we consider the block header as a target for signature by PoS validators, but what we really want the circuit to validate is the irreversible inclusion of the states into the Merkle Root. The circuit should be fine as long as this is satisfied. If we hard fork to a Layer1 configuration that does not have irreversible inclusion, that would put Layer1 in danger. leohio February 12, 2022, 8:08am 10 Thank you so much for the feedback with the information on the many protocols. I think the priority is answering this part. wdai: And if my above understanding is correct, then one should investigate holistically the differences between releasing secret keys (or shares) via WE and simply providing threshold signatures in the withdraw. The difference is simply here: If the threshold is T of N of the multi-sig, Safety Byzantine fault tolerance of multi-sig with witness encryption: N-1 / N (99% tolerance) Safety Byzantine fault tolerance of multi-sig with Shnorr threshold signature: T / N Liveness Byzantine fault tolerance of multi-sig with witness encryption: N / N (No one can stop it) Liveness Byzantine fault tolerance of multi-sig with Shnorr threshold signature: N-T / N (If N-T+1 nodes go offline, the system stops) The trade-off of Safety(Security) and Liveness shifts to a better way. So I can say this part stronger, “There’re no key holders, there’re cipher text holders.” wdai: WE solution does not require interaction between the bridge managers (generators / key holders) DFINITY’s threshold and its chain-key technology are quite smart but they are still relying on the online/liveness assumption of the validator in the subnet. wdai: Threshold signing does not rely on additional hardness assumptions that WE require and is more widely-studied (e.g. DFINITY is close to deploying threshold ECDSA on their mainnet. Threshold Schnorr is arguably simpler, e.g.this paper from 2001 .) And about here, wdai: For example, if there is a single deposit of 2 BTC and then two later withdrawal of 1 BTC each. The bridge managers (generators) need to first split the 2 BTC in the Bitcoin UTXO to two UTXOs holding 1 BTC each. The deposit addresses are one-time-use and with fixed amounts, since once the secret key is revealed by the decryption of WE, the decryptor can take everything from this private key after that. There’s no split of UTXOs in this system. To prevent the collision during the time before a several blocks confirmation, the deposit address needs to be booked by the depositor. The generators are different from depositors, and this fact is misleading as this system relies on the liveness/online assumption of somebody. This system is independent of generators by the MPC setup including multi-sig. This setup has features similar to the Power of Tau ceremony of zkSNARKs. I’m looking forward to having your feedback again. experience February 12, 2022, 2:09pm 11 Very interesting proposal, I had been looking forward to promising applications of Witness Encryption and this looks like it! I have many questions but let’s start with three: 1/ Is it correct that in your proposed scheme, the entire set of key pairs for deposit addresses is generated in an initial trusted setup, such that when we run out of addresses, another trusted ceremony would need to take place? 2/ Are you suggesting to store the ciphertexts in an on-chain contract? I imagine this would be a mapping to keep track of which ciphertexts have been decrypted by users who completed a withdrawal request. 3/ You say that the proof of inclusion can be verified by zkp circuits ifor Ethereum PoS too, but how exactly would you go about this without your proof program running a node that connects to the network? For PoW we can just verify that the cumulative proof of work of the series of block header (of which one contains the event log) is sufficiently high with minimal security tradeoffs, but on PoS you need to verify that you have the correct genesis state, and that the majority of signers that signed a block are indeed mainnet signers, and not signers of some other locally spawned fork Brilliant idea overall, looking forward to reading more about this! 1 Like Killari February 12, 2022, 2:49pm 12 Hey, Thank you for the reading material :). I checked them through and I think I understand this better now. I think you need to be able to formulate Ethereum light client as a exact cover problem, which then reveals the private key of the bitcoin deposit. In PoW version you make the client just verify the pow and that it contains the right transactions (the deposit and the wbtc burn). In PoS you do the same but with validator signatures. This made me to start to think how to attack this system, and the clear way to attack this is that when someone makes a btc deposit and mints the wbtc, you fork the Ethereum chain and start mining. Let’s assume we require 10 eth blocks worth of PoW in the proof. This would mean that once a deposit is made, attacker starts to mine on PRIVATE fork of the Ethereum starting from the deposit block. Once the attacker has been able to mine 10 blocks, they can produce the proof and steal the money. This fork is never published, there’s no direct competition. The only competition is that someone could withdraw the money using the purposed way. To perform this attack, the miner needs to be able to produce 10 blocks worth of work. This cost should be higher than what the btc deposit is worth, for the system to be economically to secure by game theory. Ofcourse a suicidal whale could burn more money to steal the btc. However, this attack gets worse, as the attacker can steal ALL the deposits with the same 10 proof of work blocks… To combat this I guess one could make the withdrawal process work in a way that you can only withdraw one deposit at once and then you need to wait some amount of time until a new withdrawal can be started. This ensures that each robbery would require the same 10 pow blocks. This would hinder the usability of the protocol. Do you happen to have a discord server or similar to chat more about this topic? It would be interesting to collaborate! leohio February 12, 2022, 4:25pm 13 experience: I have many questions but let’s start with three: Yes, let’s!! experience: another trusted ceremony would need to take place? Yes, we need it when we are short of deposit addresses. experience: Are you suggesting to store the ciphertexts in an on-chain contract? Yes, on-chain or on a data-shard is the best way. Anyway, we need put data related to the ciphertexts to the input of zkp circuits which are proving the relationship between deposit addresses and ciphertexts. Without this, a depositor can put bitcoin into a faked deposit address. This circuit needs to guarantee that withdrawers can decrypt the ciphertexts when they burn Wrapped BTC, as described in this part. leohio: The generator of each component of the N-of-N multi-signature address should first generate proof that each ciphertext was correctly constructed with the WE scheme using the NIZK proof system. Then, about this. experience: but on PoS you need to verify that you have the correct genesis state, and that the majority of signers that signed a block are indeed mainnet signers, and not signers of some other locally spawned fork This is prevented like this way. This is not my idea but Barry’s idea. leohio: the proof of publishment of Ethereum PoS activity is on the Bitcoin blockchain OP_RETURN and included in the input of the zkp circuit. This prevents the colluded PoS validators from forking the chain privately to fake the WBTC burning on it. First of all, the block signers of the faked offchain blockchain can be slashed and punished when only one honest person publishes it, among the colluded signers. This is the slash mechanism of Ethereum against the double votes to the fork. But when the colluded signers use MPC to eliminate the honest person, this security collapses. Then the signs or the hint/index of the signs should be published on Bitcoin blockchain. The OP_RETURN space is rather small, so some kind of an index to search this sign data is better to be written in OP_RETURN. Finally, the colluded signers cannot generate faked chains out of the network secretly. leohio February 12, 2022, 5:05pm 14 Thank you so much for attacking this virtually! Killari: However, this attack gets worse, as the attacker can steal ALL the deposits with the same 10 proof of work blocks… To combat this I guess one could make the withdrawal process work in a way that you can only withdraw one deposit at once and then you need to wait some amount of time until a new withdrawal can be started. This ensures that each robbery would require the same 10 pow blocks. This would hinder the usability of the protocol. I think this is exactly what we intended to prevent with this mechanism. leohio: This is prevented like this way. This is not my idea but Barry’s idea. leohio: the proof of publishment of Ethereum PoS activity is on the Bitcoin blockchain OP_RETURN and included in the input of the zkp circuit. This prevents the colluded PoS validators from forking the chain privately to fake the WBTC burning on it. First of all, the block signers of the faked offchain blockchain can be slashed and punished when only one honest person publishes it, among the colluded signers. This is the slash mechanism of Ethereum against the double votes to the fork. But when the colluded signers use MPC to eliminate the honest person, this security collapses. Then the signs or the hint/index of the signs should be published on Bitcoin blockchain. The OP_RETURN space is rather small, so some kind of an index to search this sign data is better to be written in OP_RETURN. Finally, the colluded signers cannot generate faked chains out of the network secretly. Is this answering your question? This is the cost comparison between the mega slash event of 1/3 of PoS validators and unlocking all of the Wrapped BTC in this system in the worst case, and there’s no guarantee to succeed this attack while the mega slash will certainly happen. igorsyl June 8, 2023, 3:39am 16 @leohio @KanaPalladium : thank you for working on this! A couple of questions: What progress has been made since this post was published over a year ago, and is the prototype described above available publicly? In the meantime, the current prototype requires about 20 minutes to encrypt a message using a tiny problem. Therefore, we need to develop various speedup methods to implement a real-world Wrapped Bitcoin. 2 Likes leohio July 16, 2023, 8:56pm 17 I made sure that “KanaPalladium” was not my co-author more than one year ago. Sorry to be late for reporting this. My co-author, whose name was encrypted, said he had no account named “KanaPalladium.” And his name is not “Hiro.” The person who uses the account knows me I guess, but please don’t receive any invitation from him just in case. Ignore the account if he talks about “investment to WE project.” Encrypting the author’s name was a mistake. I highly recommend people not to try it. igorsyl: What progress has been made since this post was published over a year ago, and Basically, no update, and just waiting for new WEs. But signature-based WE (https://fc23.ifca.ai/preproceedings/189.pdf) can be useful enough to update this architecture. ADP can remain the best unless we have the multi-pairing. The weakness of ADP is that one gate increases the length of cipher-text (memory consumption) 4x. So, the direction is to make it with fewer constraints or to update WE to avoid ADP. 3 Likes kravets August 1, 2023, 1:38am 19 AI summary of recent practical WE algos app.cognosys.ai Take a look at this agent from Cognosys This is agent carrying out the following objective: Summarize the state of the art in practical Witness Encryption algorithms with sub 1000 bytes ciphertext kravets August 3, 2023, 10:46pm 20 Links 2, 3, 4 here are the paper, the presentation PDF and the video of what might be the state of the art in WE https://www.google.com/search?q=google.com+🔎+On+Succinct+Arguments+and+Witness+Encryption+from+Groups+presentation+-+Google+Search&oq=google.com+🔎+On+Succinct+Arguments+and+Witness+Encryption+from+Groups+presentation+-+Google+Search&aqs=chrome..69i57.1511j0j1&sourceid=chrome&ie=UTF-8 leohio October 30, 2023, 12:52pm 21 When using Witness Encryption (WE) for a Bitcoin bridge, there’s potential for the most efficient construction to be a Drivechain without the need for BIP300. If WE is efficient, a Drivechain can be built without the BIP300 soft fork, and with Drivechain in place, a trustless Bitcoin bridge becomes feasible. To start, Drivechain (BIP300+Blind Merge Mining) can create a trustless Bitcoin Bridge. Concerning the unlocking of bitcoin through the hashrate escrow, a vote is taken based on hash power using a specific oracle. This oracle is set up to verify BTC burns that are wrapped by Ethereum’s stateless client. The essence of this efficiency is that instead of incorporating the Burn’s Proof into a circuit as in the original plan with Witness Encryption (WE), miners with incentives will simply verify it. This means that the proof of this Burn and the Ethereum blockchain itself can be entirely removed from WE. In constructing a Drivechain using WE, the method to execute hashrate escrow is using WE to unlock private keys instead of Bitcoin’s new opcode. The method to make this private key a 1/N security remains the same as the original proposal of this page. Essentially, it just involves integrating the difficulty adjustment, accumulated hash power value, hash calculation of block verification, and signature by the bundle’s destination into the circuit. This is far more efficient than the original plan which verified the entire Ethereum chain with a WE circuit. Beyond the construction of WE, another challenge is whether the developed Drivechain will be sufficiently recognized by miners, and if a mistaken bundle is created, whether a soft fork will truly occur. There’s an inherent incentive on this matter. If miners act rationally, it will inherit the security of Bitcoin’s Layer1. Reference: ttps://github.com/bitcoin/bips/blob/master/bip-0300.mediawiki ttps://github.com/bitcoin/bips/blob/master/bip-0301.mediawiki https://www.truthcoin.info/blog/drivechain/#drivechain-a-simple-spv-proof leohio October 31, 2023, 7:55pm 23 The idea of Drivechain has many discussions of its security influence on the Bitcoin protocol. So what you said makes some sense. What I refer to the trustless bridge discussion is not about whether or not each is a good idea. At least, this post (and the comment) is talking about the theoretical facts. 1 Like Ethan November 14, 2023, 5:14am 24 Very interesting solution. I have a little question. If someone forked both Ethereum&Bitcoin privately, s/he can unlock BTC without being slashed, so the security depends on the cost comparison between min(slash, BTC-fork) and unlocking all of the wrapped BTC? leohio November 14, 2023, 8:48pm 25 Please note these facts. if and only if one person in the validators of the private fork publishes the off-chain block, validators of that faked chain get slashed. BTC’s private fork does not help since they need to pour so much Proof of Work to make the private fork. devfans November 16, 2023, 8:23am 26 Hi, correct me if I am wrong. Assuming the below condition: Alice deposits 1 BTC to a deposit address generated by the generators and gets the ciphertext CT, and then mints 1 WBTC on the Ethereum chain. The current Ethereum PoS network is maintained by a group of validators, say it’s group A. And a group named B, is a 2/3 subset of the group A. Say after a year, the group B validators exited the PoS network and withdraw their stake. Then they forked the chain from the checkpoint one year before, thus they wont get slashed even they publish the headers in OP_RETURNs, while they can still burn 1 WBTC to the contract to forge a witness to satisfy the circuit, thus recover the private key with Alice’s ciphertext CT. Does this assumption hold? This a common case for a PoS network according to my understanding. BTW, is there an implemented PoC version of this brilliant idea? Published somewhere to check? or A plan to implement it? leohio December 17, 2023, 8:41am 27 devfans: Alice deposits 1 BTC to a deposit address generated by the generators and gets the ciphertext CT, and then mints 1 WBTC on the Ethereum chain. The ciphertexts get generated when the deposit address is generated. So it already exists before he/she deposits BTC there. devfans: Then they forked the chain from the checkpoint one year before, thus they wont get slashed even they publish the headers in OP_RETURNs, while they can still burn 1 WBTC to the contract to forge a witness to satisfy the circuit, If the BLS signature on a forked chain is published in OP_RETURN, they get slashed. And even trying that is dangerous for them since only one honest node can reveal that to make them slashed. devfans: BTW, is there an implemented PoC version of this brilliant idea? Published somewhere to check? or A plan to implement it? The update is here. It’s not fully inheriting the security assumption, but this is the practical approach that comes after this post. https://ethresear.ch/t/octopus-contract-and-its-applications/ ← previous page Home Categories FAQ/Guidelines Terms of Service Privacy Policy Powered by Discourse, best viewed with JavaScript enabled