# Efficient verifiable cut and choose for Glock

Alpen's [Glock](https://eprint.iacr.org/2025/1485) design conditions the validity of a bitcoin transaction on the result of a computation evaluated using a garbled circuit on authenticated input.

A fundamental requirement in such a design is to assure the garbled circuit evaluator that the garbler has honestly garbled a known circuit. The approach we are interested in is _cut and choose_, where multiple garbling tables are generated and fully opened in an interactive process prior to eventual evaluation. The eventual evaluation requires us to embed the labels, or some data from which the labels can be derived, directly in bitcoin. In our case, we need to do this in a way that minimizes the on-chain footprint and, ideally, avoids scaling linearly with the number of evaluations we need to perform.

In this document, we extend a method of [Lindell](https://eprint.iacr.org/2010/284.pdf) to meet this goal. Our technique uses verifiable Shamir secret sharing to derive both input and output garbling table labels. The specific construction is designed to be used with adaptor signatures to allow the garbler to efficiently communicate labels in a secure manner.

# Problems

In cut and choose, $n$ garbling tables are generated, a subset of $k$ garbling tables is opened, and the remaining $n - k$ garbling tables are used for evaluation.

Because evaluation is done in an authenticated manner as part of a Glock on-chain game, the garbler needs to make his input labels known to the evaluator in a manner compatible with bitcoin script.

The following problems arise:

- Input labels for $n - k$ garbling tables need to be posted on bitcoin. This is a linear increase of on-chain footprint.
- A single common output label cannot be used as a secret in the transaction graph, since some garbling tables are opened. The secret must be revealed by a single evaluation of one of the remaining garbling tables.

# Solutions

We use VSSS (verifiable Shamir secret sharing) to solve both problems.

Overall, we do the following:

1. Each input wire label is derived from a degree-$k$ polynomial $f$ that is evaluated at the circuit index. For example, the value of label 1 in circuit 1 is $f_1(1)$, the value for label 2 in circuit 1 is $f_2(1)$, the value for label 3 in circuit 2 is $f_3(2)$, and so on.
2. A designated output wire label is derived from a degree-$k$ polynomial $g$ that is evaluated at the circuit index. For example, the value in circuit 1 is $g(1)$, the value in circuit 2 is $g(2)$, and so on. The actual secret is $g(0)$.

Note that because of our intended use case, we consider here a circuit with only one output wire, for which we only care about the false label.

# Terminology

- there are 2 **truth values** per wire
- there is a **polynomial** per truth value
- polynomials are generated from random **coefficients**
- polynomials are defined on the scalar field of secp256k1
- **shares** are polynomial evaluations
- shares are secp256k1 scalars
- there is one share per truth value
- **input labels** are truncated shares
- serialize a share and take the first 16 bytes
- input labels are strings of 16 bytes
- there is one label per truth value
- **output labels** are (untruncated) shares
- output labels are strings of 32 bytes
- there is one label per truth value

# Protocol

Polynomials are generated for each input label and for the designated output label. The generation of each polynomial is the same: The garbler generates a degree-$k$ polynomial by randomly choosing coefficients $c_j$ from the scalar field $\Bbb{S}$ of the group $\Bbb{G}$.

$$
f(x) := \sum^{k}_{j = 0} c_j x^j \quad c_j \overset{\$}{\leftarrow} \Bbb{S}
$$

The garbler creates a commitment $C_j \in \Bbb{G}$ for each coefficient $c_j$.

$$
C_j := c_j G \quad 0 \leq j \leq k
$$

The garbler sends the coefficient commitments $\{C_j\ |\ 0 \leq j \leq k \}$ to the evaluator.

## Input Labels

### Initialization

The garbler evaluates the polynomial at the circuit index to obtain a share. He multiplies the share with the generator $G \in \Bbb{G}$ to obtain a share commitment.

$$
\begin{align}
s_i &:= f(i) &&\quad 1 \leq i \leq n \\
S_i &:= s_i G = f(i)G &&\quad 1 \leq i < n
\end{align}
$$

The garbler sends the share commitments $\{ S_i\ |\ 1 \leq i \leq n \}$ to the evaluator. The evaluator uses the the commitments to the coefficients and group homomorphism to verify each commitment. The evaluator aborts immediately if verification fails; there are no rewinds. _(Completeness follows from the protocol. Soundness follows from the Schwartz-Zippel lemma.)_

$$
\sum^{k}_{j = 0} C_j \cdot i^j \overset{?}{=} S_i \quad 1 \leq i \leq n
$$

### Garbling Table Opening

The garbler generates $n$ garbling tables and sends a commitment to each table to the evaluator. The evaluator selects $k$ garbling tables at random, and sends its index sampling to the garbler.

The garbler sends garbling tables and input shares corresponding to both truth values of all input wires at the $k$ selected indices to the evaluator. The evaluator asserts that the input labels of the garbling table are derived from the corresponding shares and that the garbling table matches its commitment.

After $k$ garbling tables are opened in this manner, the evaluator knows shares from $k$ garbling tables. He needs to learn one more share to interpolate the respective polynomial and recover the corresponding secret.

### Authenticated Input

To authenticate input, one of the remaining $n - k$ garbling tables is selected (arbitrary but fixed). For each input wire, there are two share commitments. The evaluator makes two adaptors, one for each share commitment $S_i$ for the wire (true and false). He uses a key pair $(P, x)$ that is unique for the input wire. Message $m$ is the sighash of the transaction that the garbler will later post. The transaction requires one signature for each input wire in its transaction input.

$$
\begin{align}
\hat{r} &\overset{\$}{\leftarrow} \Bbb{S} \\
\hat{R} &= \hat{r} G \\
R &= \hat{R} + S_i \\
e &= \text{Hash}(R \| P \| m) \\
\hat{s} &= \hat{r} + ex
\end{align}
$$

The evaluator sends the adaptor $(\hat{s}, \hat{R}, S_i)$ to the garbler, who verifies it.

$$
\begin{align}
R &= \hat{R} + S \\
e &= \text{Hash}(R \| P \| m) \\
\hat{s}G &\overset{?}{=} \hat{R} + eP
\end{align}
$$

For each input wire, there are two shares. The garbler combines the adaptor with the corresponding share to make a valid signature $(s, R)$.

$$
s = \hat{s} + s_i
$$

The input of the transaction is essentially owned by the evaluator. The garbler cannot create a valid signature unless he uses the adaptors that the evaluator provided. The adaptors give restricted access to the garbler, as long as he reveals the corresponding shares.

Note, however, that this provides authentication, since only the garbler knows $s_i$.

The garbler posts the completed transaction on bitcoin. The transaction input includes one signature per input wire. The evaluator extracts the share $s_i$ by combining the adaptor $(\hat{s}, \hat{R}, S_i)$ with the signature $(s, R)$.

$$
s_i = s - \hat{s}
$$

The evaluator interpolates the corresponding polynomial, using the $k$ shares that he learned from the table openings and the $(k+1)$-th share that he learned from the adaptor. Exactly one polynomial per input wire can be interpolated. The evaluator evaluates the polynomials at the respective circuit index and truncates the resulting shares into labels to obtain input labels for all garbling tables. The evaluator proceeds to evaluate the $n - k$ remaining garbling tables to obtain a correct output label from one of them.

The locking script gives the evaluator full control over the input of the transaction (minus covenant restrictions). Nothing stops him from posting the transaction himself. However, the evaluator doesn’t know any input shares, so he cannot evaluate the garbled circuits. Obviously, he also cannot extract the input shares from his signatures. After a timelock, the garbler can post a transation that punishes the evaluator.

## Output Label

Unlike for input wires, we only care about the output wire truth value that signals evaluator success for our use case.

### Garbling Table Opening

After $k$ garbling tables are opened in cut and choose, the evaluator knows shares for $k$ garbling tables. He needs to learn one more share to interpolate the output polynomial $g$.

### Conditional Transaction Validity

The garbler sends to the evaluator the commitment $C_0$ to the zeroth coefficient of the false output polynomial $g$, which is checked homomorphically for validity. The commitment $C_0$ is used as a public key in the input to a bitcoin transaction that signals evaluator success and garbler failure via a signature check.

### Evaluation

The evaluator only requires a single garbling table evaluation to produce the designated output share correctly. This share can be used to interpolate the output polynomial $g$. The evaluator computes $c_0 = g(0)$ and uses it to make a valid signature for the conditional transaction.

# Wide Labels

So far, we have generically discussed input wires and labels without directly examining how they correspond to input data required by the circuit.

We can group multiple input data bits into a bit string for more efficient on-chain operations. For example, let us consider 8-bit strings (bytes). In this model, each wire represents a byte with 256 possible values. Each value is encoded with a label, so there are 256 labels per wire. Each input wire has 256 polynomials that each produce a share from which a label is obtained.

Exactly one signature per input byte is posted on chain. Therefore, the on-chain footprint is reduced by a factor of 8 (8 signatures per byte → 1 signature per byte). The downside is that the total number of labels / shares / polynomials is increased by a factor of 16 (16 labels per byte → 256 labels per byte).

This label construction concerns only the input. The remaining circuit keeps using standard labels. Each input wire that carries a byte value needs to go into a translation gate that maps 8-bit labels into 8 1-bit labels.

This technique generalizes further to longer bit strings, flexibly decreasing on-chain size.