Signatures

Overview

BitVM requires restricting the usage of parameters in certain parts of the Bitcoin script, so that they can only be provided by the owner of a certain private key (denoted as the secret key in the code). To achieve this, it utilizes the Winternitz One-Time Signature Scheme. One-Time Signature Schemes allow one to publish a public key beforehand to confirm that a message sent later is signed by them. As the name suggests, signing multiple messages with the same private-public key pair can lead to forgery and security threats; for that reason, they are used with caution in BitVM.

Winternitz One-Time Signature Scheme

In order to sign a message consisting of $B$ bits, $m_0, m_1, \dots, m_{B - 1}$, where $( m_i \in {0, 1} )$ (which can also be written as $m \in \{0, 1\}^B$), an integer $1 \leq L \leq N$ (denoted as log_d in the code) and a trapdoor function $( F(x): H \to H )$ are chosen. Then, this message is split into chunks of length $L$ (If $L \nmid N$, the last chunk's missing bits are assumed to be zero). A private key $s_i$ consisting of $n_0 = \left\lceil \frac{B}{L} \right\rceil$ chunks, each being an element of $H$, is generated. Each chunk of the message is converted to an integer by interpreting the sequence as a binary representation, which is represented as $digit_i$. Public key $p_i$ and signature $sig_i$, each consisting of $n_0$ elements from $H$, are generated as follows: $p_i = F^{(2^L)}(s_i); \ sig_i = F^{(digit_i)}(s_i)$. A signature can be verified by applying the trapdoor function to each digit until they match the public key. Unfortunately, this approach by itself leaves a vulnerability: a malicious actor can forge a signature on a new message after seeing one from the actual signer by applying the function to a digit. Fortunately, this can be easily solved by adding the sum of the digits, negated, to the message (we can split it into chunks and shift the negative numbers to the allowed range $[0, 2^L) $), making the whole procedure secure for a single message.

Implementation of Winternitz in BitVM

Signing, checking and integration with hash functions of this procedure for Bitcoin script are implemented with minor changes in BitVM in various ways, as each approach is more efficient depending on the message size and the stack depth limit. For more details, you can refer to the comments in the code.