WInternitz One-time Signatures on Bitcoin using OP_CAT

winternitz.ts

// input witness stack:
// <h1> <b1>
// ...
// <h64> <b64>
// <ec_signature>


OP_DUP OP_TOALTSTACK // copy EC signature to alt stack
<G> OP_CHECKSIGVERIFY // verify EC signature matches TX


for i = 64; i > 0; i--:
  // starting stack:
  // <h_i> <b_i>

  OP_DUP OP_TOALTSTACK // copy message word <b_i> to alt stack

  // compute the number of hash iterations
  <15> OP_SWAP OP_SUB // <h_i> <15 - b_i>

  // 13 bytes
  OP_DUP <8> OP_GREATERTHANOREQUAL // <h_i> <15 - b_i> <true/false>
  OP_IF                            // <h_i> <15 - b_i>
    OP_SWAP                        // <15 - b_i> <h_i>
    {for 0..4 OP_HASH256 done}     // <15 - b_i> <sha256^8(h_i)>
    OP_SWAP                        // <sha256^8(h_i)> <15 - b_i>
    <8> OP_SUB                     // <sha256^8(h_i)> <15 - b_i - 8>
  OP_ENDIF

  // 11 bytes
  OP_DUP <4> OP_GREATERTHANOREQUAL  // <h_i> <15 - b_i> <true/false>
  OP_IF                             // <h_i> <15 - b_i>
    OP_SWAP                         // <15 - b_i> <h_i>
    OP_HASH256 OP_HASH256           // <15 - b_i> <sha256^4(h_i)>
    OP_SWAP                         // <sha256^4(h_i)> <15 - b_i>
    <4> OP_SUB                      // <sha256^4(h_i)> <15 - b_i - 4>
  OP_ENDIF

  // 10 bytes
  OP_DUP <2> OP_GREATERTHANOREQUAL  // <h_i> <15 - b_i> <true/false>
  OP_IF                             // <h_i> <15 - b_i>
    OP_SWAP                         // <15 - b_i> <h_i>
    OP_HASH256                      // <15 - b_i> <sha256(sha256(h_i))>
    OP_SWAP                         // <sha256(sha256(h_i))> <15 - b_i>
    <2> OP_SUB                      // <sha256(sha256(h_i))> <15 - b_i - 2>
  OP_ENDIF

  // 7 bytes
  OP_DUP               // <h_i> <15 - b_i> <15 - b_i>
  OP_IF                // <h_i> <15 - b_i>
    OP_SWAP            // <15 - b_i> <h_i>
    OP_SHA256          // <15 - b_i> <sha256(h_i)>
    OP_SWAP            // <sha256(h_i)> <15 - b_i>
    OP_1SUB            // <sha256(h_i)> <15 - b_i - 1>
  OP_ENDIF

  // Stack:      <h_i_tip> <0>
  OP_NOT         // <h_i_tip> <1>
  OP_VERIFY      // <h_i_tip>
  OP_TOALTSTACK  //


// Alt stack: <ec_signature> <b64> <h64_tip> ... <b1> <h1_tip>

OP_FROMALTSTACK  // <h1_tip>
OP_FROMALTSTACK  // <h1_tip> <b1>
OP_TUCK          // <b1> <h1_tip> <b1>
OP_SWAP          // <b1> <b1> <h1_tip>

// Hash each chain tip with the next one, creating an imbalanced merkle tree.
// Also add each message byte together to compute the WOTS checksum.
for 0..63:
  OP_FROMALTSTACK  // <b1> <b1> <h1_tip> <h2_tip>
  OP_CAT OP_SHA256 // <b1> <b1> <sha256(h1_tip || h2_tip)>
  OP_SWAP          // <b1> <hash_tip> <b1>
  OP_FROMALTSTACK  // <b1> <hash_tip> <b1> <b2>
  OP_TUCK OP_ADD   // <b1> <hash_tip> <b2> <b1+b2>
  OP_ROT           // <b1> <b2> <b1+b2> <hash_tip>
  // etc

// For example, the second iteration looks like:
  // OP_FROMALTSTACK  // <b1> <b2> <b1+b2> <hash_tip> <h3_tip>
  // OP_CAT OP_SHA256 // <b1> <b2> <b1+b2> <hash_tip_new>
  // OP_SWAP          // <b1> <b2> <hash_tip_new> <b1+b2>
  // OP_FROMALTSTACK  // <b1> <b2> <hash_tip_new> <b1+b2> <b3>
  // OP_TUCK OP_ADD   // <b1> <b2> <hash_tip_new> <b3> <b1+b2+b3>
  // OP_ROT           // <b1> <b2> <b3> <b1+b2+b3> <hash_tip_new>

// Eventually, we have:
// <b1> <b2> ... <b64> <b1+b2+...+b64> <hash_tip>

// Verify the recomputed WOTS chain tips match the given digest
<wots_pubkey_digest> OP_EQUALVERIFY // <b1> ... <b64> <b1+b2+...+b64>

// Verify the WOTS checksum equals a fixed value (to prevent forgery).
// 512 is the optimal checksum to make signing faster. Which checksum
// we choose has no effect on security, as long as it is consistent.
<512> OP_EQUALVERIFY // <b1> ... <b64>


// Concatenate the message words into bytes
for i in 0..32:
  // ... <b63> <b64>
  <0>     // ... <b63> <b64> <shifted>
  OP_ROT  // ... <b64> <shifted> <b63>

  // 10 bytes
  OP_DUP <8> OP_GREATERTHANOREQUAL OP_IF
    // ... <b64> <shifted> <b63>
    <8> OP_SUB   // ... <b64> <shifted> <b63 - 8>
    <1>          // ... <b64> <shifted> <b63 - 8> <1>
  OP_ELSE
    <0>          // ... <b64> <shifted> <b63> <0>
  OP_ENDIF

  OP_ROT OP_ROT // ... <b64> <0|1> <shifted> <b63>

  // 12 bytes
  OP_DUP <4> OP_GREATERTHANOREQUAL OP_IF
    // ... <b64> <0|1> <shifted> <b63>
    <4> OP_SUB   // ... <b64> <0|1> <b63-4> <shifted>
    OP_SWAP      // ... <b64> <0|1> <b63-4> <shifted>
    <64> OP_ADD  // ... <b64> <0|1> <b63-4> <shifted>
    OP_SWAP      // ... <b64> <0|1> <shifted> <b63-4>
  OP_ENDIF

  // 12 bytes
  OP_DUP <2> OP_GREATERTHANOREQUAL OP_IF
    // ... <b64> <0|1> <shifted> <b63>
    <2> OP_SUB   // ... <b64> <0|1> <b63-2> <shifted>
    OP_SWAP      // ... <b64> <0|1> <b63-2> <shifted>
    <32> OP_ADD  // ... <b64> <0|1> <b63-2> <shifted>
    OP_SWAP      // ... <b64> <0|1> <shifted> <b63-2>
  OP_ENDIF

  // 5 bytes
  OP_IF // At this point <b63> must be either 1 or 0
    <16> OP_ADD // ... <b64> <0|1> <shifted>
  OP_ENDIF

  OP_ROT // ... <0|1> <shifted> <b64>
  OP_ADD // ... <0|1> <sum>

  OP_SWAP               // <sum> <0|1>
  OP_IF                 // <sum>
    OP_DUP OP_0NOTEQUAL // <sum> <0|1>
    OP_IF               // <sum>
      OP_NEGATE         // <sum | 0x80>
    OP_ELSE
      OP_DROP <0x80>    // <0x80>
    OP_ENDIF
  OP_ENDIF

  OP_TOALTSTACK // ...

// alt stack: <ec_signature> <b64 + (b63 << 4)> .. <b2 + (b1 << 4)>

for 0..32:
  OP_FROMALTSTACK

// Raw message bytes are now on the stack
// <m1> ... <m32>

for 0..31:
  OP_CAT

// Raw message vector is now on the stack
// <m1 || m2 || ... || m32>

// Pop the EC sig from the alt stack and validate its hash was the
// message signed by the WOTS key.
OP_FROMALTSTACK // <m1 || m2 || ... || m32> <ec_signature>
OP_SHA256  // <m1 || m2 || ... || m32> <sha256(ec_signature)>
OP_EQUAL // <true/false>