Emulating OP_CHECKSIGFROMSTACK with a chain of OP_CHECKSIG operations

[stwenhao]

Each signature is a relation between two public keys on secp256k1, where 256-bit addition and multiplication can usually demonstrate, that a given entity can control a given private key, if it is done correctly, and if each step is verified according to the specification. However, ECDSA can also be used as a 256-bit calculator. The simplest example of such use case is when signature is placed in the output script, and user have to provide a matching public key, by using public key recovery:

Code:

<signature> OP_SWAP OP_CHECKSIG

If a given signature is signed with SIGHASH_ALL, then it is roughly equivalent to pushing message hash called z-value, converted to some public key, and modified by chosen r-value and s-value from that signature. However, public key recovery can be used more than once, and it is possible to form a chain of such operations. For example:

Code:

OP_DUP <signature> OP_SWAP OP_CHECKSIGVERIFY OP_CHECKSIG

Now, the solution is to put not only some public key, but also yet another signature, which would be valid for recovered public key (which would indirectly prove, that r-value of the signature can be controlled, and k-value is known, if it would be also signed with SIGHASH_ALL).

And that kind of chain can be continued further. We can start from "pubkeyA", allow using any "signatureB", apply public key recovery, and reach "pubkeyC", then again require "signatureD", and use public key recovery, to reach "pubkeyE". The total size of this chain is restricted by consensus rules, like maximum size of the Script, maximum number of sigops, and other similar limits.

However, by starting with some "pubkeyA", and ending the chain with some "pubkeyZ", if the final public key would have a private key, which would be equal to the hash of some arbitrary message, it would emulate OP_CHECKSIGFROMSTACK, without introducing any soft-fork, or other changes in consensus rules. It would allow wiring OP_CHECKSIGFROMSTACK as a virtual opcode, which could be replaced by a chain of opcodes, and by doing some operations on 256-bit numbers, it could be possible to translate some signed message to the proper Script.

Another interesting observation, is that OP_CHECKMULTISIG can enforce using identical z-value for all public keys in the chain. For example, here is how regular 3-of-3 multisig is made:

Code:

 Input: <sigA> <sigB> <sigC>
Output: 3 <pubkeyA> <pubkeyB> <pubkeyC> 3 OP_CHECKMULTISIG

But it can also use public key recovery, and it is possible to put all signatures inside the output script:

Code:

 Input: <pubkeyC> <pubkeyB> <pubkeyA>
Output: OP_TOALTSTACK OP_TOALTSTACK OP_TOALTSTACK <sigA> <sigB> <sigC> 3 OP_FROMALTSTACK OP_FROMALTSTACK OP_FROMALTSTACK 3 OP_CHECKMULTISIG

And then, different signatures can be executed on the same z-value, so results can be checked, if reached public keys are equal to some specific values, or not.

Another interesting hint is that SIGHASH_SINGLE can force z-value to have a constant value of "one", written in little endian, and that fact can be connected with OP_CHECKMULTISIG or OP_CHECKSIG operations on top of some Script, executed in out-of-bounds index.

Do you know, how to wire OP_CHECKSIGFROMSTACK, and write it as a combination of existing opcodes, like OP_CHECKSIG or OP_CHECKMULTISIG? Because the more I read about ECDSA, the more I am convinced, that it should be possible, and it is just a matter of writing some proper math equations, which would translate a valid signed message into a bunch of opcodes, which would execute it properly, regardless of the "txid:vout", where that Script would be placed.

I know it is possible to make things tick by doing it right, and making a soft-fork, but as more time passes, it is harder and harder to reach consensus, so it can be safely assumed, that in case of any disagreement, status quo will be preserved, so I am thinking about workarounds, if Bitcoin won't be changed in the future, and if "ossification" will be perceived as "no changes policy".

[ertil]

I can give you some hint:

Code:

 Input: <signature> <pubkey>
Output: OP_CHECKSIG

Instead of trying to recover some public key from some signature, or checking for any valid signature for a given key, just allow pushing any signature, and any public key. And then, when you will have that data on the stack, only then try to apply public key recovery on top of what was pushed (for example by using OP_2DUP just before), and check, if there is a match. From that point, you will get quite close to OP_CHECKSIGFROMSTACK, because then, all values in "s=(z+rd)/k" can be controlled by the solver. And then, if you form a bigger chain, like "OP_CHECKSIGVERIFY OP_CHECKSIG", or even "3 OP_CHECKMULTISIG", then you should know, what to do next.

[tiltedIceCream]

This is convoluted and won't work. The first problem is the assumption that you can create a spendable UTXO by embedding the signature in the output script. That runs into a circular dependency, because the sighash commits to the transaction that defines the output in the first place.

> We can start from "pubkeyA", allow using any "signatureB", apply public key recovery, and reach "pubkeyC"
I’m not sure what this is supposed to mean. In ECDSA, a signature lets you recover the public key that produced it. So unless "pubkeyC" is just the same as "pubkeyB," this step doesn’t make sense.

[ertil]

This is convoluted and won't work.

1. It is convoluted, because it is very unlikely, that a soft-fork, which would allow using OP_CHECKSIGFROMSTACK, would be activated directly. Only when convoluted solutions will be deployed, and people will see, that the same feature can be achieved, while consuming much more sigops, only then the community will agree to activate something, which would let doing the same things in less convoluted way. The same was true with transaction fees: they would never be lowered, if miners wouldn't start confirming such transactions.
2. It could work. Here is another hint: every time, when a public key is recovered, you have more than one key to choose from. If you do it properly, then you can reach a path between any two public keys. If you assume, that each OP_CHECKSIG lets you pick any of the two public keys (one recovered from R-value prefixed with 02, another with R-value prefixed with 03), then after 256 OP_CHECKSIGs, you can go from every public key, to every other public key, through a chain of signatures.

That runs into a circular dependency, because the sighash commits to the transaction that defines the output in the first place.

Each public key recovery operation will force you to put z-value of a given transaction, wrapped into some kind of public key, and adjusted by used r-value and s-value. And if you do more operations on top of what you just recovered, then you can make equations, which would work, no matter which z-value would be picked. It is all about repeating public key recovery enough times, so that you can travel through secp256k1, like you would in a binary tree. By picking different public keys down the road, you can reach a different end result, and then, if you build a path between two public keys, representing what you want to sign, and by whom, then you can convert any signed message (consuming a single sigop), into a chain of equivalent OP_CHECKSIGs (consuming hundreds of sigops).

So unless "pubkeyC" is just the same as "pubkeyB," this step doesn’t make sense.

It is the whole point, to travel from one public key to another. Each signature is just a connection between two different public keys, lying on secp256k1. One is Q-value, which is public key of the coin owner, and another is R-value, which is public key of the signature nonce. If inside a given Script, you can find a connection between two different public keys, then you can convert between convoluted and simple version, and deploy OP_CHECKSIGFROMSTACK, wrapped in hundreds of OP_CHECKSIGs.

[1440000bytes]

Not sure if this emulates CHECKSIGFROMSTACK in the way you are trying to achieve it. I found this thread interesting and wanted to share this idea:

1. CHECKSIGFROMSTACK requires 3 parameters: signature, message and public key. What if we could combine message and public key? So, public key contains the message.
2. Lets assume the message is "TEST". We encode each character in the message to hex: 54 45 53 54.
3. Generate keypairs for each hex being the first in public key after prefix.

Code:

import os
from ecdsa import SigningKey, SECP256k1
from colorama import Fore, Style, init

init(autoreset=True)

def generate_privkey():
    while True:
        key_bytes = os.urandom(32)
        if 1 <= int.from_bytes(key_bytes, "big") < SECP256k1.order:
            return SigningKey.from_string(key_bytes, curve=SECP256k1)

def find_vanity_pubkey(pattern: str):
    pattern = pattern.lower()
    attempts = 0
    while True:
        priv_key = generate_privkey()
        pub_key = priv_key.get_verifying_key()

        pub_hex = pub_key.to_string("compressed").hex()

        if pub_hex[2:4] == pattern: 
            return priv_key.to_string().hex(), pub_hex
        attempts += 1

def main():
    while True:
        pattern = input("\nEnter a 2-character hex pattern: ").strip().lower()
        if len(pattern) == 2:
            try:
                int(pattern, 16) 
                break
            except ValueError:
                print(Fore.RED + "Error: Invalid hex")
        else:
            print(Fore.RED + "Error: Enter 2 hex characters")

    priv, pub = find_vanity_pubkey(pattern)

    print(f"\nPrivate key: {priv}")
    print(f"Public key : {pub[:2]}{Fore.LIGHTCYAN_EX}[{pub[2:4]}]{Style.RESET_ALL}{pub[4:]}\n")

if __name__ == "__main__":
    main()

Code:

Enter a 2-character hex pattern: 54

Private key: 8160b69a538fb88b4d3f0c70e4441000d8ff572413c5442ba1e875333a41cb9a
Public key : 03[54]18283ba776b1f386d5ba80f778aa18b6246520d42e656d6663ff970edd89df


Enter a 2-character hex pattern: 45

Private key: 3dcc44110f5c41c70edf6ea4cb4b43ac50f5bbaf98a009cfec662d3bcb96a702
Public key : 03[45]f71ac5af4e00e0455ebcc656720a2ec8c205ab8554bc75944bf939c0a6bb5e


Enter a 2-character hex pattern: 53

Private key: 4b5d731db2ecbb6884f262873bd4168e754302d11a167339ed7b1c3a5b18009e
Public key : 03[53]fd655009b51646098106cf4d70081c9ed8255e74abcde0f6aea4c62c99f9d4


Enter a 2-character hex pattern: 54

Private key: e62f12f7778b85ee250cdaec62d3137eb19472f1c799262466600084f6f85622
Public key : 02[54]c33f24382926fc346fb524594217164b95d5f7ad9c6aafb8388e4ed4963b20

4. Create a 4-of-4 multisig address using these 4 public keys and send some sats to the address. This UTXO can only be spent when all the 4 keys sign the transaction and all the public keys combined will give us the message: TEST.

Note: This is just an experiment. Don’t try it on mainnet.

[stwenhao]

Create a 4-of-4 multisig address using these 4 public keys and send some sats to the address

In that case, all you need, is just the simplest 2-of-2 multisig. The first public key can be set to anything, and the second one can have the private key, set to the hash of the message. Which means:

Code:

SHA-256("TEST")=94ee059335e587e501cc4bf90613e0814f00a7b08bc7c648fd865a2af6a22cc2
d=94ee059335e587e501cc4bf90613e0814f00a7b08bc7c648fd865a2af6a22cc2
Q=03DD3E1A26D56446C4D09D1A72D545599603519B34165352054D0DF2F6D453F93D

And then, if you want to use some multisig, you can just do that:

Code:

2 <yourPubkey> 03DD3E1A26D56446C4D09D1A72D545599603519B34165352054D0DF2F6D453F93D 2 OP_CHECKMULTISIG

However, in that case, it can be even simplified to a single signature: https://gnusha.org/pi/bitcoindev/ZVcdKupXU+wjawRI@erisian.com.au/

Code:

Sign-to-contract looks like:

 * generate a secret random nonce r0
 * calculate the public version R0 = r0*G
 * calculate a derived nonce r = r0 + SHA256(R0, data), where "data"
   is what you want to commit to
 * generate your signature using public nonce R=r*G as usual

And then, for any existing public key, you can commit to any message, by just tweaking your R-value, so all interested parties can see, that you signed this transaction, and committed to a given message, at the same time.

However, this is not the end goal, because then, how do you want to meet some use cases of OP_CHECKSIGFROMSTACK? One of them is allowing to move your coins, if a given message is signed. Which means, that you have for example some transaction:

Code:

SHA-256("txdata")=6c25cd565b52a36694c131a9ec0385dd2854532c8cbbe05c574a73eea6fe6268
SHA-256(6c25cd565b52a36694c131a9ec0385dd2854532c8cbbe05c574a73eea6fe6268)=f98412627d319e88ca3b80540a9c94338cd6bea9d39e0ff07377f3d1757b0cdd
z=f98412627d319e88ca3b80540a9c94338cd6bea9d39e0ff07377f3d1757b0cdd

And then, you want to make your coins spendable, only if someone will sign a transaction, where z-value is set to f98412627d319e88ca3b80540a9c94338cd6bea9d39e0ff07377f3d1757b0cdd, with a given public key. How do you want to use multisig tricks, or R-value tweaking tricks, to get there? Because the whole point of OP_CHECKSIGFROMSTACK is to allow spending a given coin, if some arbitrary message with a given z-value is signed. Which means, that you want to put for example f98412627d319e88ca3b80540a9c94338cd6bea9d39e0ff07377f3d1757b0cdd as a message in OP_CHECKSIGFROMSTACK, which then would be hashed, would give us f98412627d319e88ca3b80540a9c94338cd6bea9d39e0ff07377f3d1757b0cdd, and would be checked for ECDSA correctness for a given public key.

In the meantime, I figured out, how to make a chain of public key recovery operations:

Code:

+--------+----------------------------------------------------------------+------------------------------------+
| Sigops | Address                                                        | Script                             |
+--------+----------------------------------------------------------------+------------------------------------+
|      1 | tb1qae4ms66yxwfe9whxx8y0v8wc7qyjg0rrttdtx0qtyzfr5fu5hu3qv5lwmj | ac                                 |
+--------+----------------------------------------------------------------+------------------------------------+
|      2 | tb1qlp50wauhzxnn05km0sz7hhpu636v28a4gezl77hf2t0gtc3caepswac0k3 | 6ead757c                        ac |
+--------+----------------------------------------------------------------+------------------------------------+
|      3 | tb1qasxq9f4t9m9udu0ykm7g8t7qhrk32k75mxlg62cvr78a7208282qrhccmv | 6ead757c 6ead77                 ac |
+--------+----------------------------------------------------------------+------------------------------------+
|      4 | tb1qkwv68xranw4hzs0vd2d4dqmgk5ktw6ezc2aeeggtlkp6mt7tj6es0hcndm | 6ead757c 6ead77 6ead757c        ac |
+--------+----------------------------------------------------------------+------------------------------------+
|      5 | tb1qqjjya57d88tc8gzl8jhmmpzg5tg0lkydnvn6r65p2vewwk0y3etqd5hy5t | 6ead757c 6ead77 6ead757c 6ead77 ac |
+--------+----------------------------------------------------------------+------------------------------------+
|      6 | tb1q9430nrfs7w4k8y3kk9snvf5xn9hu2sg9773tnhhx4dpp08mlu60s33w8w3 | 6ead757c 6ead77 6ead757c 6ead77    |
|        |                                                                | 6ead757c                        ac |
+--------+----------------------------------------------------------------+------------------------------------+
|      7 | tb1q9dhhr3vk42gz8q3fugyy5fkh4d9jr00t8yq2uus7jw4j78xgryfqjcz2gz | 6ead757c 6ead77 6ead757c 6ead77    |
|        |                                                                | 6ead757c 6ead77                 ac |
+--------+----------------------------------------------------------------+------------------------------------+
|      8 | tb1qd34ywwtlsu0gmqugfu6jqyk47ztrdtrjj483yn5sdhk3ewge89qq70dw5q | 6ead757c 6ead77 6ead757c 6ead77    |
|        |                                                                | 6ead757c 6ead77 6ead757c        ac |
+--------+----------------------------------------------------------------+------------------------------------+
|      9 | tb1quumhtnq5xafms4dwls582vspvqhwa5nzywmcsag7dk296g9kvkyq6gz6p8 | 6ead757c 6ead77 6ead757c 6ead77    |
|        |                                                                | 6ead757c 6ead77 6ead757c 6ead77 ac |
+--------+----------------------------------------------------------------+------------------------------------+
|     10 | tb1qw7a6954v45jk3kawdx0m6z8ycjs0w9x3445hhva2hz8zpymgv00sqd8pew | 6ead757c 6ead77 6ead757c 6ead77    |
|        |                                                                | 6ead757c 6ead77 6ead757c 6ead77    |
|        |                                                                | 6ead757c                        ac |
+--------+----------------------------------------------------------------+------------------------------------+

And here is how it can be decoded for five sigops:

Code:

decodescript 6ead757c6ead776ead757c6ead77ac
{
  "asm": "OP_2DUP OP_CHECKSIGVERIFY OP_DROP OP_SWAP OP_2DUP OP_CHECKSIGVERIFY OP_NIP OP_2DUP OP_CHECKSIGVERIFY OP_DROP OP_SWAP OP_2DUP OP_CHECKSIGVERIFY OP_NIP OP_CHECKSIG",
  "desc": "raw(6ead757c6ead776ead757c6ead77ac)#8lv7zd9x",
  "type": "nonstandard",
  "p2sh": "2MyDk9pDzL17MXvFHydFdAEKNwFhauqza4z",
  "segwit": {
    "asm": "0 04a44ed3cd39d783a05f3cafbd8448a2d0ffd88d9b27a1ea815332e759e48e56",
    "desc": "addr(tb1qqjjya57d88tc8gzl8jhmmpzg5tg0lkydnvn6r65p2vewwk0y3etqd5hy5t)#zrvc4p8m",
    "hex": "002004a44ed3cd39d783a05f3cafbd8448a2d0ffd88d9b27a1ea815332e759e48e56",
    "address": "tb1qqjjya57d88tc8gzl8jhmmpzg5tg0lkydnvn6r65p2vewwk0y3etqd5hy5t",
    "type": "witness_v0_scripthash",
    "p2sh-segwit": "2N7uvJnvanFT2L4jEAuanbhM9FbFaygTWvb"
  }
}

Any witness stack push can take up to 520 bytes, which means, that the upper limit is something like 149 sigops. However, the shorter the chain, the cheaper it is, so I am trying to make it smaller, to not consume hundreds of sigops for a simple OP_CHECKSIGFROMSTACK.

Edit:

What if we could combine message and public key?

In post-quantum world, it could be possible in Taproot: Spending "OP_SHA256 OP_CHECKSIG" as a TapScript

Then, if all public keys could be trivially converted to corresponding private keys, people could push any message on the stack, hash it with OP_SHA256 (or any other opcode, which would give us 256-bit result, like OP_HASH256), and then, by providing a matching signature, it will be signed by the quantum-broken private key.

However, as long as this is not the case, other methods are needed.