How OP_CAT can reduce the dangers of quantum computing
Or “How to decipher the OP_CAT code”
Threats of Quantum Computing
Quantum computing poses a potential threat to the cryptographic algorithms underpinning the Bitcoin protocol's security.
The two main cryptographic schemes at risk are:
Public Key Cryptography: Bitcoin relies on public key cryptography for secure transactions. In particular, the Elliptic Curve Digital Signature Algorithm (ECDSA) creates and verifies digital signatures. Quantum computers have the potential to break such algorithms through an algorithm called Shor’s algorithm. Shor’s algorithm can efficiently factorize large numbers, which is crucial for breaking certain types of cryptographic schemes.
Hash Functions: Quantum computers could potentially undermine the security of Bitcoin’s cryptographic SHA-256-hash function through algorithms like Grover’s algorithm. Grover’s algorithm can search an unsorted database in square root time, which could be used to find pre-images of hash functions more quickly than classical algorithms.
Background on the Bitcoin Scripting Language
Bitcoin Script is a stack-based scripting language used in Bitcoin to define the conditions under which funds can be spent from a particular transaction output. It provides a way to set up customizable conditions for spending bitcoins.
Here are the key aspects of how the Bitcoin Scripting Language works:
ScriptPubKey and ScriptSig:
ScriptPubKey (Output Script): This script is part of a transaction output and defines the conditions that must be satisfied to spend the bitcoins sent to that output. It typically includes a locking script that specifies the public key or a hash of a public key (for P2PKH or P2SH transactions).
ScriptSig (Input Script): This script is part of the spending transaction’s input and provides the necessary data to satisfy the conditions set by the ScriptPubKey. It typically includes a script with a signature corresponding to the public key specified in the ScriptPubKey.
Stack-Based Execution:
Bitcoin Script uses a stack-based execution model. The script is processed from left to right, and data elements are pushed onto and popped off the stack.
Operations in the script can include pushing data onto the stack, popping data from the stack, performing arithmetic operations, and executing conditional statements.
Script Operations:
Bitcoin Script includes a set of predefined operations or opcodes that define the script’s behavior. Some common opcodes include arithmetic operations, cryptographic operations, and conditional operations. One example is OP_CHECKSIG which checks a digital signature against a public key.
Multisig and Script Types:
Bitcoin Script supports multi-signature transactions (multisig), where spending requires multiple private key signatures.
Various script types are used for different purposes. For example, Pay-to-Public-Key-Hash (P2PKH) and Pay-to-Script-Hash (P2SH) are common script types used in Bitcoin transactions.
Script Evaluation and Validation:
When a Bitcoin node receives a transaction, it evaluates the ScriptSig and ScriptPubKey to ensure that the spending conditions are met. If the conditions are satisfied, the transaction is considered valid.
Limitations:
Bitcoin Script intentionally has some limitations to ensure security and prevent certain types of attacks. It is not a Turing-complete language, meaning it does not support certain types of loops and recursion to avoid potential security vulnerabilities.
The history and current proposal of OP_CAT
OP_CAT was available in early versions of Bitcoin.
Satoshi Nakamoto disabled it on Aug 15, 2010 as it allowed the construction of a script whose evaluation could create stack elements exponentially in the size of the script.
This is no longer an issue in the current age as tapscript enforces a maximum stack element size (MAX_SCRIPT_ELEMENT_SIZE in the code below) of 520 Bytes.
Current BIP
OP_CAT pops two elements of the stack, concatenates them together in stack order, and pushes the resulting element onto the stack. The BIP adds MAX_SCRIPT_ELEMENT_SIZE and more specific error messages to the original code (see grey-shaded parts).
Let’s go through the code line-by-line:
(1) if (stack.size() < 2)
Checks if the size of the stack is less than 2. If it’s 1, there is nothing to concatenate.
(2) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
If the size of the stack is 1 (nothing to concatenate), it returns the error message “SCRIPT_ERR_INVALID_STACK_OPERATION” and returns from the script execution. Otherwise, the script continues in line (3).
(3) valtype& vch1 = stacktop(-2);
This line creates a reference (vch2) to the second element of the stack. -2 is an index relative to the top of the stack.
(4) valtype& vch2 = stacktop(-1);
This line creates a reference (vch1) to the top element of the stack. -1 is an index relative to the top of the stack.
(5) if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
This line checks if the combined size of vch1 and vch2 is above the maximum script element size of 520 bytes. This is not hard coded but implemented via the variable MAX_SCRIPT_ELEMENT_SIZE. It tries to minimize excessive memory usage or various potential attack vectors.
(6) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
Throws this error message if line (5) returns true, i.e., if the concatenated variables exceed 520 bytes, and returns from the script execution.
(7) vch1.insert(vch1.end(), vch2.begin(), vch2.end());
This line concatenates the contents of vch2 onto the end of vch1.
(8) stack.pop_back();
The final line removes vch2.
How OP_CAT can increase Quantum Resistance
According to the BIP, Bitcoin could use post-quantum Lamport signatures in Bitcoin transactions.
These signatures create a large set of hashes that OP_CAT would need to concatenate on the stack.
The Lamport signature scheme is a quantum-resistant cryptographic signature scheme based on the one-way nature of hash functions. It was proposed by Turing award winner Leslie Lamport in 1979 and is designed to be secure against attacks by quantum computers.
Key Generation:
The Lamport signature scheme uses a pair of key matrices, one for the private key and one for the public key.
The private key consists of two matrices, each containing randomly generated bits. For a security parameter n, the matrices are of size n×m, where m is the number of bits in the hash function output (e.g., 256 for SHA-256).
The public key is generated by revealing one of the matrices (either the top or bottom part of each column) while keeping the other secret.
Signing:
To sign a message, the signer hashes the message using a secure hash function (e.g., SHA-256) to obtain a hash digest.
For each bit in the hash digest, the corresponding bit in the revealed part of the private key matrix is used to select one of the rows from the other part of the private key matrix. This selected row forms the signature for that bit.
Verification:
To verify a signature, the verifier hashes the message using the same hash function to obtain a hash digest.
For each bit in the hash digest, the verifier uses the revealed part of the public key matrix to select the corresponding row. The selected row should match the signature for that bit.
Security:
The Lamport signature scheme's security relies on the hash function's one-way nature.
Given a hash digest, it is computationally infeasible to find pre-images (original messages) or collisions (different messages producing the same hash) efficiently.
Even if an attacker learns the entire private key for a single bit (due to the hash function’s one-way property), it provides no information about the private key for other bits.
Benefits of OP_CAT:
The major drawback of these signatures is the large number of key bits to achieve sufficient security, resulting in longer signatures compared to other signature schemes.
OP_CAT is a well-suited way to stack these longer signatures.
