2022 DeFi - Zokrates P2PKH

0rollup.zok

from "./common" import u8_to_bools, u8_to_field
from "./vm" import vm, emptyInitialStack, Context, MAX_STACK, MAX_OPS

/*
Sample argument for computing witness
118 170 76 184 85 21 15 28 0 104 44 142 218 184 158 115 6 120 21 76 202 167 81 100 214 76 30 125 210 94 123 21 40 125 59 47 136 172 76 38 179 111 37 50 120 145 7 219 194 188 19 95 33 104 143 170 119 14 53 228 164 173 121 166 166 81 237 54 0 123 36 76 0 205 79 77 188 55 22 128 25 145 43 31 216 144 86 220 184 236 189 91 137 174 83 36 112 66 142 122 170 17 236 175 76 9 83 22 81 252 204 173 20 37 221 161 14 122 87 32 252 42 111 154 66 109 144 10 228 43 38 189 94 122 178 241 176 76 4 8 82 119 222 136 35 12 91 99 146 114 97 181 165 210 192 99 82 145 104 59 46 208 76 119 79 188 61 243 148 130 124 213 43 70 108 216 146 69 24 240 113 114 192 248 198 149 198 76 15 119 193 19 87 180 97 215 135 239 49 134 74 22 63 57 149 723058736 1843701591 1072936076 3036496655 3339662838 129684144 3842486204 1060083354 1719969981 2671094214 3733828187 23882685 1040072389 2495891126 1627391694 1372194221
*/

def main(private u8[38] lockScript, private u8[167] unlockScript, private u32[8] M0, private u32[8] M1) -> bool:
    // The P2PKH tx in Bitcoin typically uses OP_HASH160 for public key hash,
    // but the standard library didn't have the required hashing function of RIPEMD-160.
    // Therefore, In this example, we use OP_HASH256 as the hashing function.
    // Since this is a special purpose VM, the first sha256 will only work for the special
    // data arrangement* as describe below: it reads first three stack items (without popping them)
    // and takes 24, 24, 17 bytes of the item, respectively.

    // lock script must be
    // OP_DUP OP_HASH256 OP_PUSHDATA1 PKHash(16 bytes) OP_PUSHDATA1 PKHash(16 bytes) OP_EQUALVERIFY OP_CHECKSIG
    assert(lockScript[0] == 118) // OP_DUP will be converted to noop in our vm as OP_SHA256 won't pop the stack
    assert(lockScript[1] == 170)
    assert(lockScript[2] == 76)
    assert(lockScript[19] == 76)
    assert(lockScript[36] == 136)
    assert(lockScript[37] == 172)
    field[2] pkHash = [
        u8_to_field([...[0; 16], ...lockScript[3..19]]),
        u8_to_field([...[0; 16], ...lockScript[20..36]])
    ]

    // The typical Bitcoin P2PKH unlock script is
    // OP_PUSHDATA47 signature(71 bytes) OP_PUSHDATA21 PubKey(33 bytes)
    // However, both signature and PubKey are in compressed form.
    // In this example, we simplified them by using the uncompress form and separate signature
    // into its original parameter of Rx, Ry and S
    // * The "field" data types can only holds 254 bits(or 31 bytes) of data but the uncompressed pubkey
    // has 65 bytes, so we separate it into 24, 24 and 17 bytes segment

    // Modified unlock script is
    // OP_PUSHDATA1 Rx(32bytes) OP_PUSHDATA1 Ry(32bytes) OP_PUSHDATA1 S(32bytes)
    // OP_PUSHDATA1 PubKey(24 bytes) OP_PUSHDATA1 PubKey(24 bytes) OP_PUSHDATA1 PubKey(17 bytes) *
    assert(unlockScript[0] == 76)
    assert(unlockScript[33] == 76)
    assert(unlockScript[66] == 76)
    assert(unlockScript[99] == 76)
    assert(unlockScript[124] == 76)
    assert(unlockScript[149] == 76)

    field[2] R = [u8_to_field(unlockScript[1..33]), u8_to_field(unlockScript[34..66])]
    field S = u8_to_field(unlockScript[67..99])
    field[3] rawPK = [
        u8_to_field([...[0; 8], ...unlockScript[100..124]]),
        u8_to_field([...[0; 8], ...unlockScript[125..149]]),
        u8_to_field([...[0; 15], ...unlockScript[150..167]])
    ]

    field[MAX_OPS] ops = [
        // unlockScript
        76, R[0],           // OP_PUSHDATA1 Rx
        76, R[1],           // OP_PUSHDATA1 Ry
        76, S,              // OP_PUSHDATA1 S
        76, rawPK[0],       // OP_PUSHDATA1 pk seg1
        76, rawPK[1],       // OP_PUSHDATA1 pk seg2
        76, rawPK[2],       // OP_PUSHDATA1 pk seg3
        // lockscript
        118,                // OP_DUP
        170,                // OP_SHA256
        76, pkHash[0],      // OP_PUSHDATA1 pkHash seg1
        76, pkHash[1],      // OP_PUSHDATA1 pkHash seg2
        136,                // OP_EUQLVERIFY
        172                 // OP_CHECKSIG
    ]
    Context ctx = Context {
        M0: M0,
        M1: M1,
    }
    field[MAX_STACK] stack, u32 stackIdx, bool reverted = vm(emptyInitialStack(), 0, ops, ctx)
    assert(!reverted)
    assert(stack[stackIdx-1] == 1)

    return stack[stackIdx-1] == 1

common.zok

import "utils/casts/u8_to_bits" as u8_to_bits
import "utils/casts/u8_from_bits" as u8_from_bits
import "utils/pack/bool/pack256" as pack256
import "utils/pack/bool/unpack256" as unpack256

def u8_to_bools(u8[32] input) -> bool[256]:
	bool[256] bits = [
	    ...u8_to_bits(input[0]),
	    ...u8_to_bits(input[1]),
	    ...u8_to_bits(input[2]),
	    ...u8_to_bits(input[3]),
	    ...u8_to_bits(input[4]),
	    ...u8_to_bits(input[5]),
	    ...u8_to_bits(input[6]),
	    ...u8_to_bits(input[7]),
	    ...u8_to_bits(input[8]),
	    ...u8_to_bits(input[9]),
	    ...u8_to_bits(input[10]),
	    ...u8_to_bits(input[11]),
	    ...u8_to_bits(input[12]),
	    ...u8_to_bits(input[13]),
	    ...u8_to_bits(input[14]),
	    ...u8_to_bits(input[15]),
	    ...u8_to_bits(input[16]),
	    ...u8_to_bits(input[17]),
	    ...u8_to_bits(input[18]),
	    ...u8_to_bits(input[19]),
	    ...u8_to_bits(input[20]),
	    ...u8_to_bits(input[21]),
	    ...u8_to_bits(input[22]),
	    ...u8_to_bits(input[23]),
	    ...u8_to_bits(input[24]),
	    ...u8_to_bits(input[25]),
	    ...u8_to_bits(input[26]),
	    ...u8_to_bits(input[27]),
	    ...u8_to_bits(input[28]),
	    ...u8_to_bits(input[29]),
	    ...u8_to_bits(input[30]),
	    ...u8_to_bits(input[31])
	]
    return bits

def u8_to_field(u8[32] input) -> field:
    return pack256(u8_to_bools(input))

def bools_to_u8(bool[256] input) -> u8[32]:
    return [
        u8_from_bits(input[0..8]),
        u8_from_bits(input[8..16]),
        u8_from_bits(input[16..24]),
        u8_from_bits(input[24..32]),
        u8_from_bits(input[32..40]),
        u8_from_bits(input[40..48]),
        u8_from_bits(input[48..56]),
        u8_from_bits(input[56..64]),
        u8_from_bits(input[64..72]),
        u8_from_bits(input[72..80]),
        u8_from_bits(input[80..88]),
        u8_from_bits(input[88..96]),
        u8_from_bits(input[96..104]),
        u8_from_bits(input[104..112]),
        u8_from_bits(input[112..120]),
        u8_from_bits(input[120..128]),
        u8_from_bits(input[128..136]),
        u8_from_bits(input[136..144]),
        u8_from_bits(input[144..152]),
        u8_from_bits(input[152..160]),
        u8_from_bits(input[160..168]),
        u8_from_bits(input[168..176]),
        u8_from_bits(input[176..184]),
        u8_from_bits(input[184..192]),
        u8_from_bits(input[192..200]),
        u8_from_bits(input[200..208]),
        u8_from_bits(input[208..216]),
        u8_from_bits(input[216..224]),
        u8_from_bits(input[224..232]),
        u8_from_bits(input[232..240]),
        u8_from_bits(input[240..248]),
        u8_from_bits(input[248..256])
    ]

def field_to_u8(field input) -> u8[32]:
    return bools_to_u8(unpack256(input))

pksha256.zok

import "utils/casts/u8_to_bits" as u8_to_bits
import "utils/casts/u32_from_bits" as u32_from_bits
import "hashes/sha256/1024bit" as sha2561024
import "hashes/sha256/256bitPadded" as sha256256
from "./common" import field_to_u8

def u8_to_u32(u8[4] input) -> u32:
    return u32_from_bits(\
        [...u8_to_bits(input[0]), ...u8_to_bits(input[1]), ...u8_to_bits(input[2]), ...u8_to_bits(input[3])]\
    )

def u8_to_u32_256(u8[32] input) -> u32[8]:
    return [
        u8_to_u32(input[0..4]),
        u8_to_u32(input[4..8]),
        u8_to_u32(input[8..12]),
        u8_to_u32(input[12..16]),
        u8_to_u32(input[16..20]),
        u8_to_u32(input[20..24]),
        u8_to_u32(input[24..28]),
        u8_to_u32(input[28..32])
    ]

// sha256 twice for public key
def pksha256(private u8[65] pk) -> u32[8]:
    u32[8] pk1 = u8_to_u32_256(pk[0..32])
    u32[8] pk2 = u8_to_u32_256(pk[32..64])
    u32[8] pk3 = [
        u8_to_u32([pk[64], 0x80 /* padding */, 0, 0]),
        0,
        0,
        0,
        0,
        0,
        0,
        0
    ]
    u32[8] pk4 = [
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        65 * 8  /* original message bits */
    ]
    
    return sha256256(sha2561024(pk1, pk2, pk3, pk4))

def main(private field[3] pk) -> u8[65]:
    u8[32] seg1 = field_to_u8(pk[0])
    u8[32] seg2 = field_to_u8(pk[1])
    u8[32] seg3 = field_to_u8(pk[2])
    u8[65] rawPK = [...seg1[8..32], ...seg2[8..32], ...seg3[15..32]]
    return rawPK

pubkey.zok

from "./common" import u8_to_field

def extractPublicKey(u8[65] rawA) -> field[2]:
    // must be uncompressed form
    // assert(rawA[0] == 4)
    return [u8_to_field(rawA[1..33]), u8_to_field(rawA[33..65])]

def main(private u8[65] rawPK, field[2] pk) -> field[2]:
    field[2] A = extractPublicKey(rawPK)
    assert(A[0] == pk[0])
    assert(A[1] == pk[1])
    return A

verifySig.zok

from "ecc/babyjubjubParams" import BabyJubJubParams
import "ecc/babyjubjubParams.code" as context
from "./pubkey" import extractPublicKey
import "utils/pack/u32/nonStrictUnpack256" as unpack256u
import "hashes/sha256/1024bitPadded" as sha256

// -- modified from verifyEddsa standard library by removing the assertion part
// import "ecc/edwardsScalarMult" as scalarMult
import "ecc/edwardsAdd" as add
// Function that implements scalar multiplication for a fixed base point
// Curve parameters are defined with the last argument
// The exponent is hard-coded to a 256bit scalar, hence we allow wrapping around the group for certain
// curve parameters.
// Note that the exponent array is not check to be boolean in this gadget
// Reference: https://github.com/zcash-hackworks/sapling-crypto/blob/master/src/jubjub/fs.rs#L555
def scalarMult(bool[256] exponent, field[2] pt, BabyJubJubParams context) -> field[2]:

    field[2] infinity = context.INFINITY

    field[2] doubledP = pt
    field[2] accumulatedP = infinity

    for u32 i in 0..256 do
        u32 j = 255 - i
        field[2] candidateP = add(accumulatedP, doubledP, context)
        accumulatedP = if exponent[j] then candidateP else accumulatedP fi
        doubledP = add(doubledP, doubledP, context)
    endfor

    // assert(onCurve(accumulatedP, context))

    return accumulatedP

// import "signatures/verifyEddsa" as verifyEddsa
import "utils/pack/bool/nonStrictUnpack256" as unpack256bool
import "ecc/edwardsOnCurve" as onCurve
import "ecc/edwardsOrderCheck" as orderCheck
import "utils/casts/u32_8_to_bool_256"
/// Verifies an EdDSA Signature.
///
/// Checks the correctness of a given EdDSA Signature (R,S) for the provided
/// public key A and message (M0, M1).
/// This python repo provides the tooling for creating valid signatures:
/// https://github.com/Zokrates/pycrypto
///
/// For more information see:
/// https://en.wikipedia.org/wiki/EdDSA
/// https://eprint.iacr.org/2015/677.pdf
///
/// Arguments:
///    R: Curve point. Hidden version of the per-message nonce.
///    S: Field element. Signature to be verified.
///    A: Curve point. Public part of the key used to create S.
///    M0: 256bit array. First 256bits of the message used to create S  .
///    M1: 256bit array. Trailing 256bits of the message used to create S  .
///    context: Curve parameters used to create S.
///
/// Returns:
///     Return true for S being a valid EdDSA Signature, false otherwise.
def verifyEddsa(private field[2] R, private field S, field[2] A, u32[8] M0, u32[8] M1, BabyJubJubParams context) -> bool:

    field[2] G = [context.Gu, context.Gv]

    // Check if R is on curve and if it is not in a small subgroup. A is public input and can be checked offline
    // assert(onCurve(R, context)) // throws if R is not on curve
    // assert(orderCheck(R, context))

    u32[8] Rx = unpack256u(R[0])
    u32[8] Ax = unpack256u(A[0])
    bool[256] hRAM = u32_8_to_bool_256(sha256(Rx, Ax, M0, M1))

    bool[256] sBits = unpack256bool(S)
    field[2] lhs = scalarMult(sBits, G, context)

    field[2] AhRAM = scalarMult(hRAM, A, context)
    field[2] rhs = add(R, AhRAM, context)

    bool out = rhs[0] == lhs[0] && rhs[1] == lhs[1]

    return out

def verifySig(field[2] R, field S, u8[65] rawPK, u32[8] M0, u32[8] M1) -> bool:
    BabyJubJubParams context = context()
    field[2] A = extractPublicKey(rawPK)
    bool isVerified = verifyEddsa(R, S, A, M0, M1, context)
    return isVerified

def main(private field[2] R, private field S, private u8[65] rawPK, private u32[8] M0, private u32[8] M1):
    assert(verifySig(R, S, rawPK, M0, M1))
    return

vm.zok

from "./common" import field_to_u8
from "./pksha256" import pksha256
from "./verifySig" import verifySig
import "utils/pack/u32/pack128" as pack128
// -- Parameters --
const u32 MAX_OPS = 20
const u32 MAX_STACK_ = 16
// workaround for not having short-circuit in the branch
const u32 STACK_OFFSET = 8
const u32 MAX_STACK = MAX_STACK_ + STACK_OFFSET
const u32 MAX_OPS_ = MAX_OPS + 1

struct Context {
  // message for checking signature
  u32[8] M0
  u32[8] M1
}

// --- OPs ---
const field OP_PUSHDATA1    =   76 // push next value into the stack
// const field OP_DUP          =   118
const field OP_HASH256      =   170
const field OP_CHECKSIG     =   172
const field OP_EQUALVERIFY  =   136

// --- instructions ---
// def opDupStack(field[MAX_STACK] stack, u32 idx, Context ctx) -> field[MAX_STACK]:
//   stack[idx] = stack[idx-1]
//   return stack

// def opDupIdx(u32 idx) -> u32:
//   return idx+1

def opHash256Stack(field[MAX_STACK] stack, u32 idx, Context ctx) -> field[MAX_STACK]:
  u8[32] seg1 = field_to_u8(stack[idx-3])
  u8[32] seg2 = field_to_u8(stack[idx-2])
  u8[32] seg3 = field_to_u8(stack[idx-1])
  u8[65] rawPK = [...seg1[8..32], ...seg2[8..32], ...seg3[15..32]]
  u32[8] hash = pksha256(rawPK)
  stack[idx] = pack128(hash[0..4])
  stack[idx+1] = pack128(hash[4..8])
  return stack

def opHash256Idx(u32 idx) -> u32:
  return idx+2

def opCheckSigStack(field[MAX_STACK] stack, u32 idx, Context ctx) -> field[MAX_STACK]:
  field[2] R = [stack[idx-6], stack[idx-5]]
  field S = stack[idx-4]
  u8[32] seg1 = field_to_u8(stack[idx-3])
  u8[32] seg2 = field_to_u8(stack[idx-2])
  u8[32] seg3 = field_to_u8(stack[idx-1])
  u8[65] rawPK = [...seg1[8..32], ...seg2[8..32], ...seg3[15..32]]
  stack[idx-6] = verifySig(R, S, rawPK, ctx.M0, ctx.M1) ? 1 : 0
  return stack

def opCheckSigIdx(u32 idx) -> u32:
  return idx-5

def opEqualVerifyStack(field[MAX_STACK] stack, u32 idx, Context ctx) -> field[MAX_STACK]:
  return stack

def opEqualVerifyIdx(u32 idx) -> u32:
  return idx-4

def opEqualVerifyReverted(field[MAX_STACK] stack, u32 idx, Context ctx) -> bool:
  return stack[idx-4] != stack[idx-2] || stack[idx-3] != stack[idx-1]

def exec(field op, field[MAX_STACK] stack, u32 idx, Context ctx) -> (field[MAX_STACK], u32, bool):
  bool reverted = false
  // stack = op == OP_DUP ? opDupStack(stack, idx, ctx) : stack
  // idx = op == OP_DUP ? opDupIdx(idx) : idx
  stack = op == OP_HASH256 ? opHash256Stack(stack, idx, ctx) : stack
  idx = op == OP_HASH256 ? opHash256Idx(idx) : idx
  stack = op == OP_CHECKSIG ? opCheckSigStack(stack, idx, ctx) : stack
  idx = op == OP_CHECKSIG ? opCheckSigIdx(idx) : idx
  // stack = op == OP_EQUALVERIFY ? opEqualVerifyStack(stack, idx, ctx) : stack // noop
  reverted = op == OP_EQUALVERIFY ? reverted || opEqualVerifyReverted(stack, idx, ctx) : reverted
  idx = op == OP_EQUALVERIFY ? opEqualVerifyIdx(idx) : idx
  return stack, idx, reverted

def opPushData1Stack(field[MAX_STACK] stack, u32 stackIdx, field[MAX_OPS_] data, u32 dataIdx) -> field[MAX_STACK]:
  stack[stackIdx] = data[dataIdx+1]
  return stack

def opPushData1Idx(u32 stackIdx) -> u32:
  return stackIdx+1

def execWithData(field op, field[MAX_STACK] stack, u32 stackIdx, field[MAX_OPS_] data, u32 dataIdx) -> (field[MAX_STACK], u32, u32):
  stack = op == OP_PUSHDATA1 ? opPushData1Stack(stack, stackIdx, data, dataIdx) : stack
  stackIdx = op == OP_PUSHDATA1 ? opPushData1Idx(stackIdx) : stackIdx
  u32 advance = 0
  advance = op == OP_PUSHDATA1 ? 1 : advance
  return stack, stackIdx, advance

def vm(field[MAX_STACK_] initialStack, u32 initialStackIdx, field[MAX_OPS] ops, Context ctx) -> (field[MAX_STACK], u32, bool):
  field[STACK_OFFSET] padding = [0; STACK_OFFSET]
  bool reverted = false
  field[MAX_STACK] stack = [...padding, ...initialStack]
  u32 stackIdx = initialStackIdx + STACK_OFFSET
  field[MAX_OPS_] ops_ = [...ops, 0]
  for u32 i in 0..MAX_OPS do
    bool opReverted = false
    field op = ops_[i]
    stack, stackIdx, opReverted = exec(op, stack, stackIdx, ctx)
    u32 dataAdvance = 0
    stack, stackIdx, dataAdvance = execWithData(op, stack, stackIdx, ops_, i)
    i = i + dataAdvance
    reverted = opReverted || reverted
  endfor
  return stack, stackIdx, reverted

// helper function
def emptyInitialStack() -> field[MAX_STACK_]:
  return [0; MAX_STACK_]

// return value: reverted, top stack value
def main(private field[MAX_STACK_] initialStack, private u32 initialStackIdx, field[MAX_OPS] ops, u32[8] M0, u32[8] M1) -> (bool, field):
  Context ctx = Context {
    M0: M0,
    M1: M1,
  }
  field[MAX_STACK] stack, u32 stackIdx, bool reverted = vm(initialStack, initialStackIdx, ops, ctx)
  return reverted, stack[stackIdx-1]