Re: [bitcoin-dev] Proposed BIP for OP_CAT
Ethan Heilman via bitcoin-dev writes: > Hi everyone, > > We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode. > https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki This is really nice to see! AFAICT you don't define the order of concatenation, except in the implementation[1]. I think if A is top of stack, we get BA, not AB? 520 feels quite small for script templates (mainly because OP_CAT itself makes Script more interesting!). For example, using OP_TXHASH and OP_CAT to enforce that two input amounts are equal to one output amount takes about 250 bytes of Script[2] :( So I have to ask: 1. Do other uses feel like 520 is too limiting? 2. Was there a concrete rationale for maintaining 520 bytes? 10k is the current script limit, can we get closer to that? :) 3. Should we restrict elsewhere instead? After all, OP_CAT doesn't change total stack size, which is arguably the real limit? Of course, we can increase this limit in future tapscript versions, too, so it's not completely set in stone. Thanks! Rusty. [1] Maybe others are Bitcoin Core fluent, but I found it weird that it's not simply `valtype vch1 = popstack(stack);`, and `vch3.reserve(vch1.size() + vch2.size());` was just a weird detail. [2] https://rusty.ozlabs.org/2023/10/22/amounts-in-script.html ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Examining ScriptPubkeys in Bitcoin Script
Brandon Black writes: > On 2023-10-20 (Fri) at 14:10:37 +1030, Rusty Russell via bitcoin-dev wrote: >> I've done an exploration of what would be required (given >> OP_TX/OP_TXHASH or equivalent way of pushing a scriptPubkey on the >> stack) to usefully validate Taproot outputs in Bitcoin Script. Such >> functionality is required for usable vaults, at least. > > So you're proposing this direction as an alternative to the more > constrained OP_UNVAULT that replaces a specific leaf in the taptree in a > specific way? I think the benefits of OP_UNVAULT are pretty big vs. a > generic construction (e.g. ability to unvault multiple inputs sharing > the same scriptPubkey to the same output). I would have to write the scripts exactly (and I'm already uncomfortable that I haven't actually tested the ones I wrote so far!) to properly evaluate. In general, script makes it hard to do N-input evaluation (having no iteration). It would be useful to attempt this though, as it might enlighted us as to OP_TXHASH input selection: for example, we might want to have an "all *but* one input" mode for this kind of usage. Dealing with satsoshi amounts is possible, but really messy (that's my next post). >> TL;DR: if we have OP_TXHASH/OP_TX, and add OP_MULTISHA256 (or OP_CAT), >> OP_KEYADDTWEAK and OP_LESS (or OP_CONDSWAP), and soft-fork weaken the >> OP_SUCCESSx rule (or pop-script-from-stack), we can prove a two-leaf >> tapscript tree in about 110 bytes of Script. This allows useful >> spending constraints based on a template approach. > > I agree that this is what is needed. I started pondering this in > response to some discussion about the benefits of OP_CAT or OP_2SHA256 > for BitVM. Given these examples, I think it's clear that OP_MULTISHA256 is almost as powerful as OP_CAT, without the stack limit problems. And OP_2SHA256 is not sufficient in general for CScriptNum generation, for example. > Personally I'd use OP_TAGGEDCATHASH that pops a tag (empty tag can be > special cased to plain sha256) and a number (n) of elements to hash, > then tagged-hashes the following 'n' elements from the stack. That's definitely a premature optimization to save two opcodes. Cheers, Rusty. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
> This opcode would be activated via a soft fork by redefining the opcode > OP_SUCCESS80. Why OP_SUCCESS80, and not OP_SUCCESS126? When there is some existing opcode, it should be reused. And if OP_RESERVED will ever be re-enabled, I think it should behave in the same way, as in pre-Taproot, so it should "Mark transaction as invalid unless occuring in an unexecuted OP_IF branch". Which means, " OP_VERIFY" should be equivalent to " OP_NOTIF OP_RESERVED OP_ENDIF". On 2023-10-21 07:09:13 user Ethan Heilman via bitcoin-dev wrote: Hi everyone, We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode. https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki OP_CAT was available in early versions of Bitcoin. It was disabled as it allowed the construction of a script whose evaluation could create stack elements exponential in the size of the script. This is no longer an issue in the current age as tapscript enforces a maximum stack element size of 520 Bytes. Thanks, Ethan ==Abstract== This BIP defines OP_CAT a new tapscript opcode which allows the concatenation of two values on the stack. This opcode would be activated via a soft fork by redefining the opcode OP_SUCCESS80. When evaluated the OP_CAT instruction: # Pops the top two values off the stack, # concatenate the popped values together, # and then pushes the concatenated value on the top of the stack. OP_CAT fails if there are less than two values on the stack or if a concatenated value would have a combined size of greater than the maximum script element size of 520 Bytes. ==Motivation== Bitcoin tapscript lacks a general purpose way of combining objects on the stack restricting the expressiveness and power of tapscript. For instance this prevents among many other things the ability to construct and evaluate merkle trees and other hashed data structures in tapscript. OP_CAT by adding a general purpose way to concatenate stack values would overcome this limitation and greatly increase the functionality of tapscript. OP_CAT aims to expand the toolbox of the tapscript developer with a simple, modular and useful opcode in the spirit of Unix[1]. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable: * Tree Signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. [2] * Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely requires the ability to hash and concatenate values on the stack. [3] * Non-equivocation contracts [4] in tapscript provide a mechanism to punish equivocation/double spending in Bitcoin payment channels. OP_CAT enables this by enforcing rules on the spending transaction's nonce. The capability is a useful building block for payment channels and other Bitcoin protocols. * Vaults [5] which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html OP_CAT is sufficent to build vaults in Bitcoin. * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 which would allow the creation of simple covenants and other advanced contracts without having to presign spending transactions, possibly reducing complexity and the amount of data that needs to be stored. Originally shown to work with Schnorr signatures, this result has been extended to ECDSA signatures. [6] The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script for which an evaluation could have memory usage exponential in the size of the script. For instance a script which pushed an 1 Byte value on the stack then repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack value whose size was greater than 1 Terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 Bytes. ==Specification== Implementation if (stack.size() < 2) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); valtype vch1 = stacktop(-2); valtype vch2 = stacktop(-1); if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); valtype vch3; vch3.reserve(vch1.size() + vch2.size()); vch3.insert(vch3.end(), vch1.begin(), vch1.end()); vch3.insert(vch3.end(), vch2.begin(), vch2.end()); popstack(stack); popstack(stack); stack.push_back(vch3); The value of MAX_SCRIPT_ELEMENT_SIZE is 520
Re: [bitcoin-dev] OP_Expire and Coinbase-Like Behavior: Making HTLCs Safer by Letting Transactions Expire Safely
> By redefining a bit of the nVersion field, eg the most significant bit, we > can apply coinbase-like txout handling to arbitrary transactions. We already have that in OP_CHECKSEQUENCEVERIFY. You can have a system with no coinbase transactions at all, and use only OP_CHECKSEQUENCEVERIFY on the first transaction, and set sequence numbers to put a relative locktime of 100 blocks. Also, if you think some soft-fork is needed anyway, then I recommend building it around already existing OP_CHECKSEQUENCEVERIFY, than reinvent the wheel. > Redefining an existing OP_Nop opcode, OP_Expire would terminate script > evaluation with an error This one is also already there. We have reserved opcodes, like OP_RESERVED. You can do something like " OP_IF OP_RESERVED OP_ENDIF", and then, if "" is triggered in the Script, the whole transaction is marked as invalid. But if that condition is false, then everything is fine, and you can continue executing next opcodes. Again, the situation is the same as in previous case: build it around OP_RESERVED, that is just "OP_EXPIRE" with a different name than you want, and then the only thing you need, is soft-forking a proper condition on the stack. On 2023-10-21 02:09:55 user Peter Todd via bitcoin-dev wrote: On Mon, Oct 16, 2023 at 05:57:36PM +0100, Antoine Riard via bitcoin-dev wrote: > Here enter a replacement cycling attack. A malicious channel counterparty > can broadcast its HTLC-preimage transaction with a higher absolute fee and > higher feerate than the honest HTLC-timeout of the victim lightning node > and triggers a replacement. Both for legacy and anchor output channels, a > HTLC-preimage on a counterparty commitment transaction is malleable, i.e > additional inputs or outputs can be added. The HTLC-preimage spends an > unconfirmed and unrelated to the channel parent transaction M and conflicts > its child. The basic problem here is after the HTLC-timeout path becomes spendable, the HTLC-preimage path remains spendable. That's bad, because in this case we want spending the HTLC-preimage - if possible - to have an urgency attached to it to ensure that it happens before the previous HTLC-timeout is mined. So, why can't we make the HTLC-preimage path expire? Traditionally, we've tried to ensure that transactions - once valid - remain valid forever. We do this because we don't want transactions to become impossible to mine in the event of a large reorganization. A notable example of this design philosophy is seen in Bitcoin's rules around coinbase outputs: they only become spendable after 100 more blocks have been found; a 100 block reorg is quite unlikely. Enter the OP_Expire and the Coinbase Bit soft-fork upgrade. # Coinbase Bit By redefining a bit of the nVersion field, eg the most significant bit, we can apply coinbase-like txout handling to arbitrary transactions. Such a transaction's outputs would be treated similarly to a coinbase transaction, and would be spendable only after 100 more blocks had been mined. Due to this requirement, these transactions will pose no greater risk to reorg safety than the existing hazard of coinbase transactions themselves becoming invalid. Note how such a transaction is non-standard right now, ensuring compatibility with existing nodes in a soft-fork upgrade. # OP_Expire Redefining an existing OP_Nop opcode, OP_Expire would terminate script evaluation with an error if: 1) the Coinbase Bit was not set; or 2) the stack is empty; or 3) the top item on the stack was >= the block height of the containing block This is conceptually an AntiCheckLockTimeVerify: where CLTV _allows_ a txout to become spendable in a particular way in the future, Expire _prevents_ a txout from being spent in a particular way. Since OP_Expire requires the Coinbase Bit to be set, the reorg security of OP_Expire-using transactions is no worse than transactions spending miner coinbases. # How HTLC's Would Use OP_Expire Whenever revealing the preimage on-chain is necessary to the secure functioning of the HTLC-using protocol, we simply add an appropriate OP_Expire to the pre-image branch of the script along the lines of: If Expire Drop Hash EqualVerify CheckSig ElseIf # HTLC Expiration conditions ... EndIf Now the party receiving the pre-image has a deadline. Either they get a transaction spending the preimage mined, notifying the other party via the blockchain itself, or they fail to get the preimage mined in time, reverting control to the other party who can spend the HTLC output at their leisure, without strict time constraints. Since the HTLC-expired branch does *not* execute OP_Expire, the transaction spending the HTLC-expired branch does *not* need to set the Coinbase Bit. Thus it can be spent in a perfectly normal transaction, without restrictions. # Delta Encoding Expiration Rather than having a specific Coinbase Bit, it may also be feasible to encode the expiration height as a delta against a
Re: [bitcoin-dev] Full Disclosure: CVE-2023-40231 / CVE-2023-40232 / CVE-2023-40233 / CVE-2023-40234 "All your mempool are belong to us"
Could this be addressed with an OP_CSV_ALLINPUTS, a covenant opcode that requires *all* inputs to have a matching nSequence, and using `1 OP_CSV_ALLINPUTS` in the HTLC preimage branch? This would prevent using unconfirmed outputs in the HTLC-preimage-spending transaction entirely, which IIUC should protect it against the replacement cycling attack. (If desirable, this could alternatively be OP_CSV_OTHERINPUTS to allow the HTLC output itself to be spent immediately via the preimage branch, and only require that the other inputs added for fees are confirmed.) On Mon, Oct 16, 2023 at 8:03 PM Antoine Riard via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > (cross-posting mempool issues identified are exposing lightning chan to > loss of funds risks, other multi-party bitcoin apps might be affected) > > Hi, > > End of last year (December 2022), amid technical discussions on eltoo > payment channels and incentives compatibility of the mempool anti-DoS > rules, a new transaction-relay jamming attack affecting lightning channels > was discovered. > > After careful analysis, it turns out this attack is practical and > immediately exposed lightning routing hops carrying HTLC traffic to loss of > funds security risks, both legacy and anchor output channels. A potential > exploitation plausibly happening even without network mempools congestion. > > Mitigations have been designed, implemented and deployed by all major > lightning implementations during the last months. > > Please find attached the release numbers, where the mitigations should be > present: > - LDK: v0.0.118 - CVE-2023 -40231 > - Eclair: v0.9.0 - CVE-2023-40232 > - LND: v.0.17.0-beta - CVE-2023-40233 > - Core-Lightning: v.23.08.01 - CVE-2023-40234 > > While neither replacement cycling attacks have been observed or reported > in the wild since the last ~10 months or experimented in real-world > conditions on bitcoin mainet, functional test is available exercising the > affected lightning channel against bitcoin core mempool (26.0 release > cycle). > > It is understood that a simple replacement cycling attack does not demand > privileged capabilities from an attacker (e.g no low-hashrate power) and > only access to basic bitcoin and lightning software. Yet I still think > executing such an attack successfully requests a fair amount of bitcoin > technical know-how and decent preparation. > > From my understanding of those issues, it is yet to be determined if the > mitigations deployed are robust enough in face of advanced replacement > cycling attackers, especially ones able to combine different classes of > transaction-relay jamming such as pinnings or vetted with more privileged > capabilities. > > Please find a list of potential affected bitcoin applications in this full > disclosure report using bitcoin script timelocks or multi-party > transactions, albeit no immediate security risk exposure as severe as the > ones affecting lightning has been identified. Only cursory review of > non-lightning applications has been conducted so far. > > There is a paper published summarizing replacement cycling attacks on the > lightning network: > > https://github.com/ariard/mempool-research/blob/2023-10-replacement-paper/replacement-cycling.pdf > > ## Problem > > A lightning node allows HTLCs forwarding (in bolt3's parlance accepted > HTLC on incoming link and offered HTLC on outgoing link) should settle the > outgoing state with either a success or timeout before the incoming state > timelock becomes final and an asymmetric defavorable settlement might > happen (cf "Flood & Loot: A Systematic Attack on The Lightning Network" > section 2.3 for a classical exposition of this lightning security property). > > Failure to satisfy this settlement requirement exposes a forwarding hop to > a loss of fund risk where the offered HTLC is spent by the outgoing link > counterparty's HTLC-preimage and the accepted HTLC is spent by the incoming > link counterparty's HTLC-timeout. > > The specification mandates the incoming HTLC expiration timelock to be > spaced out by an interval of `cltv_expiry_delta` from the outgoing HTLC > expiration timelock, this exact interval value being an implementation and > node policy setting. As a minimal value, the specification recommends 34 > blocks of interval. If the timelock expiration I of the inbound HTLC is > equal to 100 from chain tip, the timelock expiration O of the outbound HTLC > must be equal to 66 blocks from chain tip, giving a reasonable buffer of > reaction to the lightning forwarding node. > > In the lack of cooperative off-chain settlement of the HTLC on the > outgoing link negotiated with the counterparty (either > `update_fulfill_htlc` or `update_fail_htlc`) when O is reached, the > lightning node should broadcast its commitment transaction. Once the > commitment is confirmed (if anchor and the 1 CSV encumbrance is present), > the lightning node broadcasts and confirms its HTLC-timeout before I height
[bitcoin-dev] On solving pinning, replacement cycling and mempool issues for bitcoin second-layers
Hi, I think if Gleb Naumenko and myself allocate our research time on this issue, we should (hopefully) be able to come with a strong sustainable fix to the lightning network, both systematically solving pinnings and replacement cycling attacks (and maybe other mempools issues or things related like massive force-closure beyond available blockspace can absorb before pre-signed transactions timelocks expiration as mentioned in the original paper). I have not yet probed Gleb's mind on this, though we both studied those cross-layer issues together as early as 2019 / 2020, and I think we have built an intuitive understanding of the problem-space, with both practical experience of bitcoin core and rust-lightning codebases and landmark research in this area [0] [1]. If Gleb isn't too busy with Erlay in core, I'm sure he'll be enthusiastic to contribute research time at his own pace (and I might probe a bit of Elichai Turkel time to verify the maths of all sustainable lightning fixes we might propose and the risks models). All soft commitments and assuming the interest of the bitcoin community. One good advantage of long-term sustainable fixes, it should (optimistically yet to be demonstrated) lower the fee-bumping reserve value and number of UTXOs lightning users (and maybe bandwidth) have to lock continuously to use this worldwide 24 / 7 payment system. Reopened the issue on coordinated security issues handling in the LN ecosystem: https://github.com/lightning/bolts/pull/772 While I'll stay focused on solving the above problems at the base-layer where they're best solved, at least I'll stay around for a few months making transitions with the younger generation of LN devs. For transparency, I don't have any strong solution design yet at all, neither code, conceptual draft or paper ready, and game-theory and nodes network processing resources changes will have to be weighted very carefully, all under the bitcoin open and responsible process we currently have. Overall, this will take reasonable time (e.g package relay design discussions have been started in 2018 and we're only now at the hard implementation and review phase) to carry on forward. Looking forward to hearing thoughts of the Bitcoin and Lightning development protocols community. [0] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-February/002569.html [1] https://arxiv.org/pdf/2006.01418.pdf "They who face calamity without wincing, and who offer the most energetic resistance, these, be they States or individuals, are the truest heroes". - Thucydides. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
