Jeremy Rubin's Blog

Here you'll find an assorted mix of content from yours truly. I post about a lot of things, but primarily Bitcoin.

categories: Bitcoin, Shenzhen Journey.


CheckSequenceVerify DISCOURAGE_UPGRADABLE_NOPS Defect

The other day I was writing some tests for BIP-119 (shoutout Gloria for the detailed feedback on improving tests). I noticed something peculiar while attempting to write static test vectors for CTV. This peculiar thing led me to discover a minor flaw in Bitcoin’s interpreter – it isn’t going to break anything in the short term, but it has implications for how certain upgrades might be done in the future.

In the interpreter we pass specific flags in at different times to check different rules at different times. This is used because we generally want the Mempool to be “restrictive” and block validation to be unrestrictive. That sounds like the opposite of what you would want, but it’s because we want to ensure that we never break a consensus rule, so our mempool is “strict” to protect e.g. a miner from making a bad block, because our node’s understanding of consensus validation is less strict so we always know the mempool is full of stuff that will pass consensus.

One of the specific types of “stricter” that is in the mempool is for things that may be changed in the future. For example, Taproot (a change proposed to Bitcoin) uses a Witness V1 script. Before Taproot activates, Witness V1 Scripts are always valid no matter if they’re signed or not. After it activates, a new rule takes effect in consensus, and Witness V1 Scripts will be processed in accordance with Taproot’s rules. Because the Mempool is stricter, it never lets in any Witness V1 script spends until it knows how to properly validate it. That way, for a miner who doesn’t want to upgrade to Taproot, they can use the old rules in their Mempool and not ever mine a bad block.

One of the flags used for this purpose is DISCOURAGE_UPGRADABLE_NOPS. A NOP is simply an opcode in bitcoin that has no effect (nada). In the future, someone could add a rule to that NOP (e.g., check that the stack args present when the NOP executes satisfy some properties or the transaction is invalid, but do not remove anything from the stack so that the old consensus rules still seem correct). This is sufficient for consensus, but maybe people have decided that they want to create a bunch of outputs with NOPs in it because they are cute. Then, a fork that would add new semantics to a NOP would have the impact of locking people out of their wallets. To prevent this, the Mempool uses the rule DISCOURAGE_UPGRADABLE_NOPS which makes it so that if you try to broadcast an output script with a NOP it gets bounced from the Mempool (but not consensus of course, should a deviant miner mine such a transaction). Hopefully our users get the message to not use NOPs because we… discourage upgradable nops.

CheckSequenceVerify (CSV) was one such NOP before it grew up to be a big n’ important opcode. Essentially all that CSV does is check that the sequence field is set in a particular manner. This lets you set relative block and time lock (e.g., takes this much time before a coin is spendable again). However, it’s possible that we might come up with new kinds of lock times in the future, so we have a bit we can set in the sequence that makes it ignored for consensus purposes. Maybe in the future, someone would find something nice to do with it, eh?

This is the sequence verification code:

case OP_CHECKSEQUENCEVERIFY:
{
    if (!(flags & SCRIPT_VERIFY_CHECKSEQUENCEVERIFY)) {
        // not enabled; treat as a NOP3
        break;
    }

    if (stack.size() < 1)
        return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);

    // nSequence, like nLockTime, is a 32-bit unsigned integer
    // field. See the comment in CHECKLOCKTIMEVERIFY regarding
    // 5-byte numeric operands.
    const CScriptNum nSequence(stacktop(-1), fRequireMinimal, 5);

    // In the rare event that the argument may be < 0 due to
    // some arithmetic being done first, you can always use
    // 0 MAX CHECKSEQUENCEVERIFY.
    if (nSequence < 0)
        return set_error(serror, SCRIPT_ERR_NEGATIVE_LOCKTIME);

    // To provide for future soft-fork extensibility, if the
    // operand has the disabled lock-time flag set,
    // CHECKSEQUENCEVERIFY behaves as a NOP.
    if ((nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) != 0)
        break;

    // Compare the specified sequence number with the input.
    if (!checker.CheckSequence(nSequence))
        return set_error(serror, SCRIPT_ERR_UNSATISFIED_LOCKTIME);

    break;
}

Spot anything funky? Look closer…

    // To provide for future soft-fork extensibility, if the
    // operand has the disabled lock-time flag set,
    // CHECKSEQUENCEVERIFY behaves as a NOP.
    if ((nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) != 0)
        break;

Here, where we say it behaves as a NOP we don’t check any rules and skip the checks.

See where the problem lies? If we ever did get around to a future upgrade here, then old miners who refuse to upgrade would be more than happy to accept invalid transactions into their mempool, and then following the fork, would end up mining invalid blocks leading to potential network partitions.

That would be bad! Let’s not do that.

What we really should be doing is:

    // To provide for future soft-fork extensibility, if the
    // operand has the disabled lock-time flag set,
    // CHECKSEQUENCEVERIFY behaves as a NOP.
    if ((nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) != 0) {
        if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS)
            return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS);
        break;
    }

Which is exactly what I propose to do in this PR.

If this solution is adopted, then after the last release of the Bitcoin Core Implementation that has the unpatched code goes End-of-Life, we could safely deploy new sequence rules. Because it takes a while for software to go EOL, I hope we can patch this soon.



Infrastructure Bill: It's Go Time for Radical Self Custody

TL;DR: click here to answer call to action

The infrastructure bill draft has been circulating which contains language that would have massive impact for the crypto ecosystem (and Bitcoin) in the United States, and most likely globally. The broad implication of the proposed bill is that many types of service provider would be categorized as brokers, even if fully ‘non custodial’. E.g., a coinjoin coordinator might be a broker, even if they never take control of the funds, because they are facilitating a transaction. There’s a lot of nuance, and the language is still being changed, so we’ll see where it lands. But that’s not the point of this blog post.

The point of this blog post is that we need to hurry the fuck up and improve the self-sovereign software available and widely used by bitcoiners. You heard me right, hurry the fuck up.

While there’s space for debate around perfect designs and optima for protocol improvements, these discussions take years to turn into code running in end users wallets. I do not believe that we have time to leisurely improve self-sovereign custody solutions while regulators figure out a wrench to throw in our spokes.

Why am I so concerned about this bill in particular? A confidential source tells me that this language came out of the blue, an executive branch driven regulatory ninja attack of sorts. Normally, when the government looks to regulate an industry, the provisions and terms get floated around by legislators for a long while with industry input, comment periods, and more. Then, when a bill or other rules get passed, it’s something that the industry has at least had a chance to weigh in on and prepare for. My source claims no one has seen the clauses in the infrastructure bill before, and they infer that may mean this is a part of a broader crack-down coming from specific political personalities and agencies. This means we may be seeing government actions further restricting users’ rights in the pipeline much sooner than anyone could anticipate.

I’ve long been saying that we should be deploying BIP-119 CTV for congestion control before we see broad congestion on the network. If you wait until a problem is manifest, it can take years to deploy a solution. This merits proactivity in solving a problem before it comes. Today, the need to improve self-custody looms urgently on the horizon.

CTV is not a panacea solution. It doesn’t magically fix all custodial issues. But, along with Sapio, it does offer a pathway to dramatically improving self custody options, letting users customize vault smart contracts which do not depend on any third parties. Deploying CTV now is an opportunity to put in motion the wheels for broad ecosystem support for these enhanced custody protocols. We may come up with better options in the future which may obsolete CTV in place of more clever technologies. I cheer those efforts. But we need solutions for Tomorrow.

A soft fork activation for CTV could be deployable for Bitcoin imminently, should the community embrace it. The spec is nearly 2 years old, the code has required only small updates to be mergeable with other changes to Bitcoin Core. The review burden is 185 lines of consensus code, and a couple hundred lines of tests. To that end I believe it is prudent for the Bitcoin community to embrace the deployment of CTV and I’m calling on the community to soft-signal intent for a soft-fork activation of CTV.

We cannot control what rules state authorities attempt to mandate. But we can individually control our own compliance with measures we see as unjust, and as a community we can advance technologies and solutions that ensure that choice remains squarely in the hands of every user and not the service providers they may use.



BIP-118 What Gets Hashed Chart

As a part of my ongoing review of BIP-118 I put together a chart of what gets hashed under the current proposal.

BIP-118 Chart

Not tightly checked to be free of errors, but I figured such a chart would be helpful for folks evaluating BIP-118.

Perhaps the BIPs (generally, incl 34x) could be updated to present the information in such a chart – at least for me it’s much clearer than following a bunch of conditional logic (maybe if there’s ever desire for some consensus refactoring this could be a table in the code replacing the cond logic). A few highlighted nuances:

  • input index is never signed (i previously thought one mode signed it). Key reuse under APOAS | Default and APOAS | All is a bit extra unsafe given susceptibility to the “half-spend” problem. This limits usability of APO for covenants a-la CTV because you can’t stop someone from adding inputs to your contract nor can you prevent half-spend problems when reusing addresses.
  • APO signs the Amounts, APOAS never does.
  • APO signs both the SPK and the Tapleaf hash, meaning that APO binds itself to the entire script rather than just it’s fragment. There’s no setting which is “just this fragment”
  • APO’s signature binds it to a specific script fragment within a taproot key, but not a specific script path
  • the flag “default” is not really a flag at all – when default is used (as a or’d byte) there are different results than when default is inferred (by absence of a byte) (this is maybe a bitcoin core specific quirk).
  • There are 16 different possible modes total, so all combinations of flags mean something (advisable or not as with ACP | None)
  • *| Default and *| All overlap, so there’s an opportunity to either reserve or assign 4 additional sighash modes if desired. These could cover some of the gaps above, or be saved for future purposes rather than be wasted now. Another point of interest is – not to rock the boat – but because BIP-118 is defining a new key type we could do away with the notion that sighash flags are “flags” and convert to an enum (e.g., numbered 0-256 for whatever combination of fields each would incur) and give each signature type a sensible name, rather than thinking of things as a combo of flags (e.g., APOAS is not some intersection of what APO and ACP do independently).


Quantum Proofing Bitcoin with a CAT

no cats harmed in the making of this post

I recently published a blog post about signing up to a 5 byte value using Bitcoin script arithmetic and Lamport signatures.

By itself, this is neat, but a little limited. What if we could sign longer messages? If we can sign up to 20 bytes, we could sign a HASH160 digest which is most likely quantum safe…

What would it mean if we signed the HASH160 digest of a signature? What the what? Why would we do that?

Well, as it turns out, even if a quantum computer were able to crack ECDSA, it would yield revealing the private key but not the ability to malleate the content of what was actually signed. I asked my good friend and cryptographer Madars Virza if my intuition was correct, and he confirmed that it should be sufficient, but it’s definitely worth closer analysis before relying on this. While the ECDSA signature can be malleated to a different, negative form, if the signature is otherwise made immalleable there should only be one value the commitment can be opened to.

If we required the ECDSA signature be signed with a quantum proof signature algorithm, then we’d have a quantum proof Bitcoin! And the 5 byte signing scheme we discussed previously is a Lamport signature, which is quantum secure. Unfortunately, we need at least 20 contiguous bytes… so we need some sort of OP_CAT like operation.

OP_CAT can’t be directly soft forked to Segwit v0 because it modifies the stack, so instead we’ll (for simplicity) also show how to use a new opcode that uses verify semantics, OP_SUBSTRINGEQUALVERIFY that checks a splice of a string for equality.

Fun Fact: OP_CAT existed in Bitcoin untill 2010, when Satoshi “secretly” forked out a bunch of opcodes. So in theory the original Bitcoin implementation supported Post Quantum cryptography out of the box!

... FOR j in 0..=5
    <0>
    ... FOR i in 0..=31
        SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <2**i> ADD ELSE <H(K_j_i_0)> EQUALVERIFY ENDIF
    ... END FOR
    TOALTSTACK
... END FOR

DUP HASH160

... IF CAT AVAILABLE
    FROMALTSTACK
    ... FOR j in 0..=5
        FROMALTSTACK
        CAT
    ... END FOR
    EQUALVERIFY
... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
    ... FOR j in 0..=5
        FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
    ...  END FOR
    DROP
... END IF

<pk> CHECKSIG

That’s a long script… but will it fit? We need to verify 20 bytes of message each bit takes around 10 bytes script, an average of 3.375 bytes per number (counting pushes), and two 21 bytes keys = 55.375 bytes of program space and 21 bytes of witness element per bit.

It fits! 20*8*55.375 = 8860, which leaves 1140 bytes less than the limit for the rest of the logic, which is plenty (around 15-40 bytes required for the rest of the logic, leaving 1100 free for custom signature checking). The stack size is 160 elements for the hash gadget, 3360 bytes.

This can probably be made a bit more efficient by expanding to a ternary representation.

        SWAP hash160 DUP <H(K_j_i_0)> EQUAL  IF DROP  ELSE <3**i> SWAP DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_i_1)> EQUALVERIFY ADD  ENDIF ENDIF

This should bring it up to roughly 85 bytes per trit, and there should be 101 trits (log(2**160)/log(3) == 100.94), so about 8560 bytes… a bit cheaper! But the witness stack is “only” 2121 bytes…

As a homework exercise, maybe someone can prove the optimal choice of radix for this protocol… My guess is that base 4 is optimal!

Taproot?

What about Taproot? As far as I’m aware the commitment scheme (Q = pG + hash(pG || m)G) can be securely opened to m even with a quantum computer (finding q such that qG = Q might be trivial, but suppose key path was disabled, then finding m and p such that the taproot equation holds should be difficult because of the hash, but I’d need to certify that claim better). Therefore this script can nest inside of a Tapscript path – Tapscript also does not impose a length limit, 32 byte hashes could be used as well.

Further, to make keys reusable, there could be many Lamport keys comitted inside a taproot tree so that an address could be used for thousands of times before expiring. This could be used as a measure to protect accidental use rather than to support it.

Lastly, Schnorr actually has a stronger non-malleability property than ECDSA, the signatures will be binding to the approved transaction and once Lamport signed, even a quantum computer could not steal the funds.



CheckSigFromStack for 5 Byte Values

I recently published a blog post about covenants on Bitcoin.

Readers were quick to point out I hadn’t fully explained myself on a claim I made that you can do a form of CheckSigFromStack in Bitcoin today.

So I thought it would be worthwhile to fully describe the technique – for the archives.

There are two insights in this post:

  1. to use a bitwise expansion of the number
  2. to use a lamport signature

Let’s look at the code in python and then translate to bitcoin script:

def add_bit(idx, preimage, image_0, image_1):
    s = sha256(preimage)
    if s == image_1:
        return (1 << idx)
    if s == image_0:
        return 0
    else:
        assert False

def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Hash, Hash]]):
    acc = 0
    for (idx, preimage) in enumerate(witnesses):
        acc += add_bit(idx, preimage, keys[idx][0], keys[idx][1])
    return x

So what’s going on here? The signer generates a key which is a list of pairs of hash images to create the script.

To sign, the signer provides a witness of a list of preimages that match one or the other.

During validation, the network adds up a weighted value per preimage and checks that there are no left out values.

Let’s imagine a concrete use case: I want a third party to post-hoc sign a sequence lock. This is 16 bits. I can form the following script:

<pk> checksigverify
0
SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD ELSE <H(K_1_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD ELSE <H(K_3_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD ELSE <H(K_4_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD ELSE <H(K_5_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD ELSE <H(K_6_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD ELSE <H(K_7_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD ELSE <H(K_8_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD ELSE <H(K_9_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> ADD ELSE <H(K_10_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> ADD ELSE <H(K_11_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> ADD ELSE <H(K_12_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> ADD ELSE <H(K_13_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> ADD ELSE <H(K_14_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> ADD ELSE <H(K_15_0)> EQUALVERIFY ENDIF
CHECKSEQUENCEVERIFY

In order to sign a 16 bit value V, the owner of K simply puts on the stack the binary representation of V indexed into the K. E.g., to sign 53593, first expand to binary 0b1101000101011001, then put the appropriate K values on the stack.

K_15_1
K_14_1
K_13_0
K_12_1
K_11_0
K_10_0
K_9_0
K_8_1
K_7_0
K_6_1
K_5_0
K_4_1
K_3_1
K_2_0
K_1_0
K_0_1
<sig>

This technique is kind of bulky! It’s around 80x16 = 1280 length for the gadget, and 528 bytes for the witnesses. So it is doable, if not a bit expensive. There might be some more efficient scripts for this – would a trinary representation be more efficient?

The values that can be signed can be range limited either post-hoc (using OP_WITHIN) or internally as was done with the 16 bit value circuit where it’s impossible to do more than 16 bits.

Keys can be reused across scripts, but signatures may only be constructed one time because a third party could take two signed messages and construct an unintended value (e.g., if you sign both 4 and 2 then a third party could construct 6).

There are certain applications where this could be used for an effect – for example, an oracle might have a bonding contract whereby posessing any K_i_0 and K_i_1 allows the burning of funds.


© 2011-2021 Jeremy Rubin. All rights reserved.