OP_CHECKGROTH16VERIFY
An ultralightweight, softforkable solution to trustlessly scale and add smart contractlike functionality to Dogecoin
Highlights:
 Allows for building complex applications like decentralized exchanges and smart contracts on Doge
 Allows Doge to be trustlessly scaled virtually adinfinitum without increasing the block size or the barrier of entry to running a Doge full node
 Fully soft forkable
 Older versions of Doge can interpret OP_CHECKGROTH16VERIFY as OP_NOP as the stack is unmodified by our proposed op code
 Does not require increasing/modifying any limits (stack depth, stack item size, transaction size, block size, etc)
 Fully functional zk Rollups enabling smart contracts/trustless rollups can be built using existing P2PKH + P2SH transactions
 Does not require modifying any existing code in Dogecoin other than adding an op code handler to script/interpreter.cpp
 Our team has already built a working reference rollup which demonstrates how OP_CHECKGROTH16VERIFY can be used to scale dogecoin and build complex applications, such as CityRollup
Summary:
We propose adding an op code to dogecoin which verifies a Groth16 zero knowledge proof over BLS12381, OP_CHECKGROTH16VERIFY.
In particular, we propose that the op code verify a Groth16 proof with two public inputs, and support two modes of operation controlled by the stack:

Mode 0: Verify a proof with 2 public inputs and verifier key, all of which are stored on the stack, marking the transaction if the proof is invalid and behaving like OP_NOP otherwise

Mode 1: Verify a proof with 2 public inputs and verifier key, where the verifier key and first public input are stored on the stack, and the second public input is the transaction's SIGHASH.
By adding this op code (specifically mode 1), it makes it possible to verify any trustless computation on Dogecoin, build recursive covenants and design smart contract functionality via sighash introspection.
A working roughdraft implementation of OP_CHECKGROTH16VERIFY can be found in our fork, and you can also test it out with a docker image we built that includes a local testnet (regtest), block explorer (fork of blockstream electrs):
docker run p 1337:1337 it rm qedprotocol/bitidedoge:latest
To test, you can visit http://localhost:1337 for BitIDE with OP_CHECKGROTH16VERIFY enabled, http://localhost:1337/explorer/ to view a block explorer and http://devnet:devnet@localhost:1337/bitcoinrpc to interact with the local testnet via RPC.
Usage
In order to maintain backwards compatibility, we propose:
 Redefining an available OP_NOP instruction such as 0xb3
 Implementing OP_CHECKGROTH16VERIFY such that it verifies the proof and leave the stack unchanged (softforkable)
 Mark the transaction as invalid if and only if the proof is invalid
The stack parameters accessed by OP_CHECKGROTH16VERIFY are as follows:
Mode 0 (Two public inputs)
<π_A_x> // (Proof) Fp > 48 bytes
<π_A_y> // (Proof) Fp > 48 bytes
<π_B_x_A0> // (Proof) Fp > 48 bytes
<π_B_x_A1> // (Proof) Fp > 48 bytes
<π_B_y_A0> // (Proof) Fp > 48 bytes
<π_B_y_A1> // (Proof) Fp > 48 bytes
<π_C_x> // (Proof) Fp > 48 bytes
<π_C_y> // (Proof) Fp > 48 bytes
<public input 0> // the first public input of the proof (32 bytes/Fr)
<public input 1> // the second public input of the proof (32 bytes/Fr)
<VERIFIER_DATA[0:80]> // bytes 080 of the verifier data
<VERIFIER_DATA[80:160]> // bytes 80160 of the verifier data
<VERIFIER_DATA[160:240]> // bytes 160240 of the verifier data
<VERIFIER_DATA[240:320]> // bytes 240320 of the verifier data
<VERIFIER_DATA[320:400]> // bytes 320400 of the verifier data
<VERIFIER_DATA[400:480]> // bytes 400480 of the verifier data
OP_0 // mode 0
OP_CHECKGROTH16VERIFY
Mode 1 (Public Input 0 == user defined public input, Public Input 1 == SIGHASH)
<π_A_x> // (Proof) Fp > 48 bytes
<π_A_y> // (Proof) Fp > 48 bytes
<π_B_x_A0> // (Proof) Fp > 48 bytes
<π_B_x_A1> // (Proof) Fp > 48 bytes
<π_B_y_A0> // (Proof) Fp > 48 bytes
<π_B_y_A1> // (Proof) Fp > 48 bytes
<π_C_x> // (Proof) Fp > 48 bytes
<π_C_y> // (Proof) Fp > 48 bytes
<public input 0> // the first public input of the proof (32 bytes/Fr)
<VERIFIER_DATA[0:80]> // bytes 080 of the verifier data
<VERIFIER_DATA[80:160]> // bytes 80160 of the verifier data
<VERIFIER_DATA[160:240]> // bytes 160240 of the verifier data
<VERIFIER_DATA[240:320]> // bytes 240320 of the verifier data
<VERIFIER_DATA[320:400]> // bytes 320400 of the verifier data
<VERIFIER_DATA[400:480]> // bytes 400480 of the verifier data
OP_1 // mode 1
OP_CHECKGROTH16VERIFY
Deep Dive: How Groth16 + Sighash enables trustless scaling and smart contract functionality on Dogecoin
To better explain how the OP_CHECKGROTH16VERIFY can help scale Dogecoin, it is necessary to first examine how zero knowledge proofs enable the verification of arbitrary computation from a birds eye view.
In general, zkSNARK based zero knowledge proving backends allow a prover to succintly prove that a program described as an arithmetic constraint system is satisfied.
Consider the program:
void multiply(int a, int b, int c){
assert(a * b == c);
}
if we wanted to prove that prover knows two numbers a
and b
which when multiplied equal c
we could represent this program with the following diagram:
One could then take such a circuit and generate a corresponding verifier key which is unique to the program, and can be used to verify arbitrary executions of the program by utilizing a proving backend such as Groth16:
The verifier key of such a circuit can then be encoded in the spend script of a P2SH UTXO, and require a valid proof in order to be spent. One can then utilize a zk proving backend such as Groth16 to generate a valid proof:
The prover could then spend the UTXO by providing the proof in the witness of the P2SH spend transaction to successfully spend the UTXO:
Crucially, the size and complexity of verifying a Groth16 proof does not depend on the complexity or size of the computation being verified, meaning that OP_CHECKGROTH16VERIFY can verify an arbitrary amount of computation performed off chain without increasing the workload on Dogecoin nodes.
This enables Doge to validate new kinds of transactions like smart contract state machines and complex stateful without requiring any further changes to dogecoin, all while still respecting all existing limitations imposed on P2SH spends:
To enable trustless smart contractlike functionality without any additional burden on the network, we can use one of the public inputs as the spend transaction's SIGHASH and use the other public input to store the merkelized state of an application such as a smart contract:
Via the SIGHASH, we can allow the smart contract to be aware of any deposits of Doge made into the contract as well as any withdrawals or outputs that must be made in order to spend the UTXO:
To learn more about this sighash introspection technique, check out our reference implementation in CityRollup
Script Example
Ideally we would like to store the verifier data and current state root in the P2SH redeem script of the UTXO so that the UTXO can only be spent if we provide a valid state transition proof for given logic. Due to script limitations, stack elements must be at most 80 bytes and since the the verifier key is a total size of 480 bytes we can split it up to into 6 80byte chunks.
In this case, our ideal script would look something like the following:
<public input 0> // the merkle root of the current state of the application (32 bytes)
<VERIFIER_DATA[0:80]> // bytes 080 of the verifier data
<VERIFIER_DATA[80:160]> // bytes 80160 of the verifier data
<VERIFIER_DATA[160:240]> // bytes 160240 of the verifier data
<VERIFIER_DATA[240:320]> // bytes 240320 of the verifier data
<VERIFIER_DATA[320:400]> // bytes 320400 of the verifier data
<VERIFIER_DATA[400:480]> // bytes 400480 of the verifier data
OP_1 // mode 1
OP_CHECKGROTH16VERIFY // verify the proof and mark the transaction as invalid if the proof is invalid
OP_2DROP // clean up the stack data
OP_2DROP
OP_2DROP
OP_2DROP
OP_2DROP
OP_2DROP
OP_1 // successful spend
However, since the redeem script is limited to 520 bytes, we cannot directly use this approach. Instead we can hash the first 80 bytes of the verifier data, store the hash in the redeem script and provide the first 80 byte of the verifier key in the spend witness instead:
<public input 0> // the merkle root of the current state of the application
OP_SWAP // move the first 80 bytes of the verifier data to the top of the stack
OP_DUP // duplicate the first 80 bytes of the verifier data on the stack
OP_SHA256 # hash the first 80 bytes of verifier data
<SHA256(VERIFIER_DATA[0:80])> // hard coded, known sha256 hash of the first 80 bytes of verifier data
OP_EQUALVERIFY // ensure the first 80 bytes of verifier data have the correct hash
// now the first 80 bytes of the verifier data are known to be correct and are at the top of the stack
<VERIFIER_DATA[80:160]> // bytes 80160 of the verifier data
<VERIFIER_DATA[160:240]> // bytes 160240 of the verifier data
<VERIFIER_DATA[240:320]> // bytes 240320 of the verifier data
<VERIFIER_DATA[320:400]> // bytes 320400 of the verifier data
<VERIFIER_DATA[400:480]> // bytes 400480 of the verifier data
OP_1 // mode 1
OP_CHECKGROTH16VERIFY // verify the proof and mark the transaction as invalid if the proof is invalid
OP_2DROP // clean up the stack data
OP_2DROP
OP_2DROP
OP_2DROP
OP_2DROP
OP_2DROP
OP_1 // successful spend
To spend the UTXO, we provide the following witness:
<π_A_x> // (Proof) Fp > 48 bytes
<π_A_y> // (Proof) Fp > 48 bytes
<π_B_x_A0> // (Proof) Fp > 48 bytes
<π_B_x_A1> // (Proof) Fp > 48 bytes
<π_B_y_A0> // (Proof) Fp > 48 bytes
<π_B_y_A1> // (Proof) Fp > 48 bytes
<π_C_x> // (Proof) Fp > 48 bytes
<π_C_y> // (Proof) Fp > 48 bytes
<VERIFIER_DATA[0:80]> // bytes 080 of the verifier data