[[alloc] init]

PIPEs provide the cryptographic primitive for enforcing arbitrary conditions on Bitcoin without changing consensus. Programmable security vaults on the L1 use PIPEs to control native BTC, encrypting the ability to spend behind cryptographic conditions that can be satisfied with a zero-knowledge proof. Shielded Bitcoin builds on these vaults to enable private transfers, with protocol state derived directly from Bitcoin history.

Bitcoin PIPEs use cryptography to enforce arbitrary conditions on Bitcoin without changing consensus — enabling covenants, zero-knowledge proofs, and L1 security vaults.

Bitcoin PIPEs

Built with PIPEs, programmable vaults control native BTC using cryptographic conditions. Funds are released when those conditions are satisfied, including through proofs derived from shielded state reconstructed from Bitcoin history. 

Programmable Security Vaults

Encrypted notes and zero-knowledge proofs enable private transfers; nullifiers prevent double-spends. Programmable vaults control the L1 BTC, while shielded state is reconstructed from data published to Bitcoin.

Shielded Bitcoin

Private Transfers on the Bitcoin L1

Covenants and Pessimistic ZKPs on Bitcoin Without Soft Fork via Witness Encryption

Bitcoin PIPEs v2

Witness Encryption from Arithmetic Affine Determinant Programs

FEATURED

Research and updates from [[alloc] init].

Follow us on Twitter

Learn about PIPEs or contribute to our research.

Get in touch

Covenants and ZKPs on Bitcoin via Witness Encryption

Private Transfers on Bitcoin L1


Witness encryption is a powerful cryptographic primitive, which allows a ciphertext to be decrypted by anyone who holds a valid witness to a chosen NP statement, with no prior interaction between sender and receiver. A practical construction would unlock a wide set of applications, including time-lock and event-triggered disclosure, sealed-bid auctions, conditional on-chain payments, fair exchange, and access control gated by zero-knowledge proofs. Today, many of these are realized only with trusted parties or other workarounds.

Recently, we proposed a new witness encryption scheme that is more efficient than previous approaches and can be implemented in practice. It is based on an earlier construction from 2020, extending it to general arithmetic programs. However, in both the original construction and our adaptation, the cryptanalysis relies on heuristics rather than reductions of known hard problems.

In particular, since these constructions are of algebraic nature, cryptanalytic attacks like (re)linearization approaches and more specialized attacks on certain classes of instances seem to be the most promising directions. This is true both for the original construction and for our adaptation.

Although neither construction is broken and there have been extensive efforts in cryptography to optimize algebraic attacks (see, e.g., XSL approaches on the AES and recent research in Gröbner basis attacks), a better understanding of the security of AADPs is desirable, especially when using them in high-stakes settings like Bitcoin.

For this purpose, we designed cryptographic challenges given in the following. We welcome anyone to attempt to break small instances of our new scheme or to discover structural properties that were unknown before.

> ## Results
> 
> **27 May 2026**
> A commutator-based attack breaking both this scheme and original ADP for sparse circuits was submitted. We are aware of the mitigation that fixes this class of attacks in characteristic $2$ and are working on extending it to characteristic $p$.
> 
> Congratulations to the submitter, we will be in touch!

## Specification of the AADP Construction

We refer to our construction as the AADP (arithmetic affine determinant programs). It consists of a setup phase and an encryption/decryption phase. For the purpose of this description, we briefly recall the specification without going into the details. Interested readers are referred to our paper.

### Setup

We denote by $m$ the number of arithmetic gates (constraints) and by $n$ the number of variables. In our instances, $n \approx m$ (we emphasize that this condition is important in order to prevent certain classes of attacks).

Given a projectively safe constraint system $(A, B, C, D)$, the setup produces public matrices $M^{(0)}, \dots, M^{(n)} \in \mathbb{F}^{k \times k}$ with $k = 2m+1$. For each gate $i \in \{0, \dots, m-1\}$, we define the linear forms $a_i(\overline{X}), b_i(\overline{X}), c_i(\overline{X}), d_i(\overline{X})$ from the constraint system and a secret random linear form $\xi_i(\overline{X}) = \sum_j \xi_{i,j} X_j$ with $\xi_{i,j} \stackrel{\text{\$}}{\leftarrow} \mathbb{F}$. The $4 \times 4$ gate matrix is then defined as

$$
U_i(\overline{X}) =
\begin{pmatrix}
a_i(\overline{X}) & c_i(\overline{X}) & -\xi_i(\overline{X}) & 0 \\
d_i(\overline{X}) & b_i(\overline{X}) & 0 & \xi_i(\overline{X}) \\
0 & 0 & b_i(\overline{X}) & c_i(\overline{X}) \\
0 & 0 & d_i(\overline{X}) & a_i(\overline{X}) \\
\end{pmatrix}.
$$

Secret random masking matrices $L_i \stackrel{\$}{\leftarrow} \mathbb{F}^{k \times 4}$ and $R_i \stackrel{\$}{\leftarrow} \mathbb{F}^{4 \times k}$ are sampled, and the public matrix is then defined as a sum over the gates s.t.

$$
M(\overline{X}) = \sum_{i=0}^{m-1} L_i \cdot U_i(\overline{X}) \cdot R_i.
$$

If $x$ is a valid witness, each $U_i(x)$ has rank $2$ and $M(x)$ has rank $2m$, so $\det(M(x)) = 0$. Otherwise, $M(x)$ has full rank with high probability.

### Encryption and Decryption

To encrypt a message $\texttt{msg} \in \mathbb{F}$, we set the ciphertext to

$$
\widehat{M} \leftarrow M + \texttt{msg} \cdot \underbrace{x_0}_{= 1} \cdot (0, \dots, 0, 1)^\top \cdot (0, \dots, 0, 1),
$$

i.e., the message is added to the bottom-right entry of $M^{(0)}$. Decryption with a valid witness $\overline{x}$ evaluates $\widehat{M}$ at $(x_0, \overline{x}) = (1, \overline{x})$ and recovers $\texttt{msg}$ as the unique root $t$ of $\det(\widehat{M}(1, \overline{x}) - t \cdot (0, \dots, 0, 1)^\top (0, \dots, 0, 1)) = 0$, which is linear in $t$.

## Rules for the Challenges

Before defining the challenges, we fix a set of rules in the following.

- We exclude attacks based on guessing finite field elements, since our target field will be cryptographically large. However, we encourage the use of smaller fields (for $p \geq 2^{32}$) to facilitate the implementation of attacks (e.g., in cases where an otherwise qualifying attack hits the memory limit on a certain machine).
- Attacks must be implemented and verified in practice. Both the attack code and a detailed description of the approach must be submitted as part of the solution.
- Submissions must be made public within 2 months after confirmation.
- We generally follow a first-come-first-serve basis if there are multiple qualifying submissions. However, we may abstain from following this rule verbatim if two submitted attacks differ largely in their approach.
- A single approach breaking multiple challenges at once only qualifies for the highest-paid challenge.
- People from [[alloc] init] are excluded from the challenges and are not allowed to send any submissions.
- External committee members are allowed to submit results, but in this case they are excluded from the judging process.

## External Committee

To ensure fairness, we have an external committee of domain experts that help with the evaluation of the challenge process. In particular, this includes overseeing key decisions and offering neutral perspectives on the submissions. All committee members are serving in an unpaid capacity.

- Carlos Cid
- Lorenzo Grassi
- Morten Øygarden
- Akin Ünal

## Cryptographic Challenges

We now present the cryptographic challenges.

### Full Instances

Our first set of challenges focuses on full instances of the AADP construction with small setup parameters. As we expect the security of the construction to scale with the number of gates $m$, we choose small values for $m$ to reduce the cryptographic complexity of the challenges.

#### Circuit Definition

The circuit is designed such that no valid witness exists, while preserving the AADP structure that the cryptanalytic challenges target. The reason is that, otherwise, a solution could simply be found by finding a valid witness (which is trivial with small $m$).

The circuit is built as follows. First, we have $w$ bit check gates that enforce that $b_0, b_1, \dots, b_{w-1} \in \{0, 1\}$. The circuit's input is the linear form $x = \sum_{i=0}^{w-1} 2^i b_i$, so $x \in \{0, 1, \dots, 2^w - 1\}$. Secondly, we have $s$ gates that compute a squaring chain, resulting in $x^{(2^s)}$. The last of these gates is also meant as an equality check against the target. Finally, we have a public target value $y \in \mathbb F_p$ fixed during the setup phase by sampling $y$ uniformly at random from the quadratic non-residues in $\mathbb F_p^*$. The circuit then asserts $x^{2^s} = y$.

Since $x^{2^s}$ is always a quadratic residue in $\mathbb F_p^*$, picking $y$ to be a non-residue rules out any $\mathbb F_p$ witness with certainty. The bit check gadget is needed to pin $x$ into $\mathbb F_p$. Indeed, the gate $b_i^2 = b_i$ has roots $\{0, 1\}$ in every extension of $\mathbb F_p$, so the bit check prevents an attacker from working in some extension $\mathbb F_{p^k}$ in which $y$ does admit a $2^s$-th root and using the resulting extension field witness to decrypt.

Scaling to (moderately) larger $m$ is easy by keeping $w = 3$ and setting $s = m - 3$, so the relation becomes $x^{2^{m-3}} = y$ with $x$ still in $\{0, \dots, 7\}$.

#### Challenges

Two different approaches qualify as solutions here.

1. **Full Randomness Recovery:** A full randomness recovery, i.e., all setup parameters that lead to the public matrices given as part of the challenge. This particularly consists of valid values for $R_i$, $L_i$, and $\xi_{i, j}$.
2. **Decryption:** Decryption of the message contained in the bottom-right entry of $M^{(0)}$.

| $m$ | $n$ | Prize |
| --- | --- | --- |
| ~~8~~ | ~~7~~ | ~~$3,000~~ |
| ~~16~~ | ~~15~~ | ~~$6,000~~ |
| ~~32~~ | ~~31~~ | ~~$20,000~~ |

#### Submission

For full randomness recovery, the submission consists of concrete values for all secrets, namely $L_i \in \mathbb{F}^{k \times 4}$, $R_i \in \mathbb{F}^{4 \times k}$, and $\xi_{i,j} \in \mathbb{F}$ for $i \in \{0, \dots, m-1\}$ and $j \in \{0, \dots, n\}$. A submission qualifies if

$$
\sum_{i=0}^{m-1} L_i \cdot U_i(\overline{X}) \cdot R_i = M(\overline{X})
$$

holds as an identity of matrix polynomials in $\overline{X} = (X_0, \dots, X_n)$, i.e., if the claimed secrets reproduce each public matrix $M^{(j)}$ coefficient-wise. We note that any valid tuple qualifies, hence we do not require the submitted values to match the specific randomness used during setup.

Partial randomness recovery also qualifies. The challenge instances are published in canonical form, so every secret entry has a unique value. A submission qualifies if it satisfies both of the following.

1. It lists specific entries of $L_i$, $R_i$, or $\xi_{i,j}$ together with their claimed values in $\mathbb{F}$. Alternatively, an entry may be replaced by any low-degree polynomial in the secrets. We compare each claim against the secret used during setup.
2. It includes an argument that the claimed values do not trivially follow from public information alone (i.e., the constraint system $A, B, C, D$ and the public matrices $M^{(j)}$).

Prizes for partial randomness recovery are scaled according to how much of the secret state is revealed. In both cases, the submission must additionally include the attack code and a detailed description of the approach used to obtain the secrets, consistent with the rules in the previous section.

#### Challenge Files

We provide the generation code for the challenges and the binary files of the public matrices for each challenge set here. The binary files contain the target of the squaring chain (a quadratic non-residue), followed by the public matrices in row-major order, where each value is stored as a 32-byte big-endian unsigned integer. The field is the BN254 scalar prime and there are $n+1=m$ matrices each of size $k \times k$, where $k = 2m + 1$.

### Structural Observations

Submissions reporting structural properties of the ciphertexts are also encouraged, regardless of whether they result in a full attack. Awards and prizes for such observations are granted at our discretion and are essentially based on their impact.

As it is difficult to precisely describe the qualifying criteria, in the following we give two examples that are intended as illustrative guidance.

#### Unexpected Subspace Intersections with $R_i$

While the masking matrices $R_0, \dots, R_{m-1}$ are sampled uniformly at random during setup, they are not independent of the public matrices $M^{(j)}$, and tied together by the setup equations $\sum_i L_i U_i^{(j)} R_i = M^{(j)}$. Informally, the AADP construction heuristically relies on the row spans of the $R_i$ still “appearing” random from the attacker’s perspective. Identifying any non-generic correlation that is detectable using only public information is a violation of this assumption, even without a full attack.

In particular, assume we have the following two building blocks.

1. A static subspace $V \subseteq \mathbb F^k$ of dimension $d_1$, constructed from publicly available information only, i.e., the constraint system $A, B, C, D$ and the public matrices $M^{(j)}$ for $j \in \{0,\dots,n\}$. In particular, $V$ must not depend on the secret $R_i$.
2. A description of a subspace $W \subseteq \mathbb F^k$ of dimension $d_2$, given as a set of coefficient tuples $(c_{i,r}^{(\ell)})$, where $i \in \{0, \dots, m-1\},\, r \in \{0, 1, 2, 3\}$, for $\ell = 1, \dots, d_2$. The subspace $W$ is then defined as the span of the vectors
    
    $$
    w^{(\ell)} = \sum_{i=0}^{m-1} \sum_{r=0}^{3} c_{i,r}^{(\ell)} \cdot (\text{row } r \text{ of } R_i)
    $$
    

We expect it to be hard to find $V$ and $W$ such that

$$
\dim(V \cap W) > \max(0, d_1 + d_2 - k),
$$

i.e., where the intersection of $V$ and $W$ exceeds the (generic) expected dimension for two subspaces of dimensions $d_1, d_2$ that both live in $\mathbb{F}^k$ with $k = 2m + 1$. In other words, it should be hard to find $V$ and $W$ whose intersection is larger than what two random subspaces of those dimensions would typically share. This would suggest that public data leaks information about the row combinations of $R_i$. Here we exclude trivial correlations following from public data such as relations that can be derived directly from $A, B, C, D$. 

#### Partial Kernel Leakage

Consider the public matrices $M^{(0)}, M^{(1)}, \dots, M^{(n)} \in \mathbb{F}^{k \times k}$ together with $m$ entries of a target kernel vector $\alpha \in \mathbb{F}^k$ in specified positions (e.g., the first $m$ entries $\alpha_0, \dots, \alpha_{m-1}$), with $\alpha_{k-1} = 1$ fixed by normalization. We expect it to be hard to find $(1, x_1, \dots, x_n) \in \mathbb{F}^{n+1}$ and complete the remaining $m$ entries of $\alpha$ such that

$$
M(1, x) \cdot \alpha = 0, \qquad \text{where } M(1, x) = M^{(0)} + \sum_{j=1}^{n} x_j \, M^{(j)}
$$

for a construction where $m \geq 8$. In particular, we expect the complexity of solving this problem to grow exponentially in $m$, in line with the bilinear/Kipnis-Shamir Gröbner basis estimate.

## Submission Process

Following the details for qualifying submissions above, any results or observations should be sent to challenges@allocinit.xyz, including a detailed description of the approach, the challenge claimed to be solved (and an answer if applicable), and auxiliary files like source code.


Break It Bad!

Cryptographic Challenges for AADP WE


Few days ago, we have learned that our novel Witness Encryption scheme (https://eprint.iacr.org/2026/175) is not secure. The break is particularly severe - it affects not only our modifications but also the original ADP construction , and renders it unusable for sparse circuits.

Fortunately, we determined a patch that plausibly fixes the scheme and restores security. By a lucky coincidence (an optimization of the related scheme), we had worked on a generic transform that turns any projective circuit into a non-sparse one - though at that time, we only had the required modification available in characteristic 2. We have concentrated our efforts on extending the transform to characteristic $p$, too, and I am happy to share the results here.

## What are (A)ADPs

I will give a brief explanation of how AADPs work. A more detailed treatment can be found in our paper.

(Arithmetic) affine determinant program is a collection of square matrices, $M^0, …, M^n$ over a field $\mathbb{F}$. We will typically write it as a formal linear function $M(x) = \sum M^j x_j$. They are constructed from the circuits (via $AADP.Setup$ algorithm, defined further) and we have 2 desired properties:

1. If $w$ is a witness to the original circuit, $\det M(w) = 0$
2. Without knowing a satisfying $w$, the set of matrices $M_i$ is computationally indistinguishable from a collection of random matrices.

*Note:* hypothesis 2 might be too strong (in fact, it is not clear that such a strong requirement is needed for the safety of the derived witness encryption scheme), but we have consistently found that any “significant” break of 2 typically swiftly leads to an attack on the derived witness encryption scheme.

Let’s start with a circuit with $n+1$ variables and $m$ constraints. For each constraint, we construct a certain $2k \times 2k$ “gate matrix” $U(x)$, with the following properties:

1. $U(x)$ has rank $2k$ if the constraint does not hold.
2. $U(x)$ has rank $k$ if the constraint does hold, except with negligible probability.

AADP construction uses the constraints of the form $a(x) b(x) = c(x) d(x)$, and the matrix that we use is

$\begin{pmatrix} a(x) & c(x) & -\xi(x) & 0 \\ d(x) & b(x) & 0 & \xi(x) \\ 0 & 0 & b(x) & c(x) \\ 0 & 0 & d(x) & a(x) \end{pmatrix}$

Note: the linear function $\xi$ is generated randomly, and is needed to fulfill the second condition - i.e. even if all $a, b, c, d$ vanish at the same time, the rank does not drop below 2 except with negl. probability.

The original ADP construction is only capable of expressing the constraint $a(x)b(x) = 0$ and uses a simpler gate matrix $\begin{pmatrix} a(x) & \xi(x) \\ 0 & b(x) \end{pmatrix}$ (though the authors never formulated it in this form).

$AADP.Setup$ works simply as follows:

$L_i \overset{\$}\gets \mathbb{F}^{(k m + 1) \times 2k}$, $R_i \overset{\$}\gets \mathbb{F}^{2k \times (k m + 1)}$, $\xi_i(x) \overset{\$}\gets \mathbb{F}^{n+1}$

$U_i(x) := \begin{pmatrix} a_i(x) & c_i(x) & -\xi_i(x) & 0 \\ d_i(x) & b_i(x) & 0 & \xi_i(x) \\ 0 & 0 & b_i(x) & c_i(x) \\ 0 & 0 & d_i(x) & a_i(x) \end{pmatrix}$

$M = \sum\limits_{i=1}^m L_i U_i(x) R_i$

I don’t want to specifically talk about a WE scheme (the message is just added to a matrix cell of one of the matrices), because once again in our experience building a distinguisher is typically enough to break AADP, and it is conceptually easier to explain.

## The Attack

Before we explain the attack, it makes sense to give the intuition why this *might* be secure (at least in some cases). The baseline is the following:

*There is no (non correct witness) input $w$ such that  $\det M(w) = 0$ for non-negligible fraction of setups.*

The reason why this is true - each gate contribution $L_i U_i(x) R_i$ has rank $2$ if the gate holds, and rank $4$ if it does not. Because the total dimension is $2m+1$, the sum for any invalid witness will have a full rank except with negligible probability.

In general, the problem to detect the rank of $n \times (2m+1) \times (2m+1)$ tensor is considered hard in this regime, at least for random tensors. Question is, can someone exploit a specific structure of the setup?

The idea is the following. Consider an individual matrix $M^j$. One can notice that formula for it contains a lot of rank 2 terms of the form  $L_i^{12} \begin{pmatrix} -\xi_i^j & 0 \\ 0 & \xi_i^j \end{pmatrix} R_i^{34}$. However, if the circuit is sparse, most of the terms $L_i^{12} \begin{pmatrix}a_i^j & c_i^j \\ d_i^j & b_i^j \end{pmatrix} R_i^{12} + L_i^{34} \begin{pmatrix}b_i^j & c_i^j \\ d_i^j & a_i^j \end{pmatrix} R_i^{34}$ just vanish, because the variable $j$ does not participate in most of the gates $i$.

This suggests that all the matrices $M^j$ have a hidden structure - they diagonalize simultaneously up to a low rank error!

To make this precise, note that our construction has independent left and right gauge symmetry - we can simultaneously multiply all $L_i$-s by some global $L$, i.e. $L_i \mapsto L L_i$, and all $R_i$-s by a global $R$ as $R_i \mapsto R_i R$. Let’s choose such transforms that $L_i^{12} = (e_{2i-1}, e_{2i})$ , and $R_i^{34} = (L_i^{12})^\top$.

If we do, then a matrix $M^j$ has the following form: $\mathsf{Diag}(-\xi_1^j, \xi_1^j, -\xi_2^j, \xi_2^j, \ldots) + \mathsf{Err}$, where the rank of the error is related to $\deg(j)$ - the amount of gates that this variable participates in.

As a first step, we can consider a fraction of two such matrices, say $T_{ab} = (M^a)^{-1}M^b$. This will clear one part of the gauge symmetry - the result is now an honest linear operator, with symmetries acting as $T_{ab} \mapsto R^{-1} T_{ab} R$.

There is now a hidden basis where all $T_{ab}$-s are diagonal at the same time, up to low rank errors!

… and this is where analysis in the paper goes astray - we take two such matrices and construct a messy nonlinear system to analyze them, when actually building a distinguisher can be done in one shot:

“$[T_{ab}, T_{cd}] = T_{ab} T_{cd} - T_{cd}T_{ab}$ has a low rank”

Indeed, if two linear operators diagonalize in the same basis up to a low-rank error, their commutator is just low-rank. The details of the remaining part of the attack are circuit-specific, but the essence is that such commutators, specifically of the form $[T_{ab}, T_{ac}]$ have kernel spaces that are related to kernels of matrices $R_i^{34}$, which allows to eventually recover the hidden basis.

The attack was implemented against our repeated-squaring challenge circuit by tekkac, successfully decrypting the challenge value.

### Extent of the Attack

While this attack only works against specific class of circuits (sparse ones), practical circuits that we want to use typically *are* sparse. It is also worth mentioning that the original ADP (https://eprint.iacr.org/2020/889) is also subject to this attack.

## The Patch

The natural solution, of course, is to, given a constraint system $\mathcal C$, produce a new constraint system $\widetilde{C}$ such that it is equivalent, yet any invalid witness candidate $w$ to this new constraint system breaks some large fraction of the gates (say, at least half).

Apparently, there is no official name for such constraint systems (though the topic is definitely related to linear PCPs and gap problems in general); we call them **"pufferfishes"** because of a local brainrot meme.

### R1CS Example

Now, imagine for a moment that we work with R1CS circuits. Then, the solution to this problem is well-known, it is just QAPs. To quickly remind you, given a constraint system of the form $a_i(w) b_i(w) = c_i(w)$, one picks $m$ points $z_1, …, z_m$ and constructs interpolation polynomials satisfying $A_i(z_j) = a_i^j$.

Now, denote $A = \sum w_i A_i, B= \sum w_i B_i, C = \sum w_i C_i$. Then, the expression

$A(t)B(t) - C(t)$ vanishes on the set $z_1, \ldots z_m$, which can be expressed as the following condition (called QAP, quadratic arithmetic program):

$A(t)B(t) - C(t) = Z(t)H(t)$ where $Z(t) = \underset{i}\prod (t - z_i)$

Now, it is easy to explain how to construct a new constraint system which is a pufferfish: let’s say that our new witness is $\widetilde{w} = (w | H)$ (so it has a total size $n+m-1$) and evaluate the QAP in $4m$ different points $\tau_1, \ldots, \tau_{4m}$.

At each point, we will have an expression $A(\tau_j) B(\tau_j) = C(\tau_j) + Z(\tau_j) H(\tau_j)$, which is indeed a R1CS constraint on the extended witness. This is our new set of constraints

Moreover, any invalid solution is automatically forced to break at least half of all constraints (assuming $m \geq n$), because the polynomial $AB - C - Z H$ has the degree $\leq 2m$ and is evaluated in $4m$ points.

### Characteristic 2 Patch

The problem, of course, is that we do not work with R1CS circuits! Our circuits are *projective*, and this is a strictly necessary requirement for anything resembling AADP to work. The QAP is linear in the coefficients of $H$, so we need to invent a version of QAP with $H$ replaced with some quadratic expression. It is, apparently, very easy to do in characteristic 2, because we can write:

$A(t)B(t) - C^2(t) = Z(t) S^2(t^{1/2})$

Indeed, for any polynomial $H(t) = \sum h_i t^i$ there is its *inverse Frobenius twist* - a polynomial with coefficients that are square roots of coefficients of $H$, i.e. $S(t) = \sum h_i^{1/2} t^i$. Because in characteristic 2 squaring is a homomorphism, we have

$S^2(t^{1/2}) = (\sum h_i^{1/2} t^{i/2})^2 = \sum h_i t^i = H(t)$

This works pretty much as well as R1CS.

### Characteristic $p$ Patch

Situation for characteristic $p$ is much more complicated. There are few options, all quite bad and the only feasible one that we have found is to write:

$H(t) = S(t^{1/2})S(-t^{1/2})$

This can always be done over an algebraically closed field, but the interesting part is whether it can be done without leaving our field $\mathbb{F}$. Let’s rewrite this expression slightly.

Split $S$ into the sum of odd and even parts: $S(u) = P(u^2) + u Q(u^2)$

Then, we can rewrite:

$H(t) = (P(t) + t^{1/2} Q(t))(P(t) - t^{1/2} Q(t)) = P^2(t) - t Q^2(t)$

the existence of such $P$ and $Q$ is a well-known problem from number theory, and it is equivalent to $t$ being a square modulo $H(t)$.

Let’s assume $H$ decomposes into a product of $d$ irreducible polynomials,

$H(t) = H_1(t)\cdots H_d(t)$. 

We can, of course, solve the problem for each of those separately - and the probability of success for each factor is $1/2$ (because $\mathbb{F}[t]/H_i(t)$ is a field, so half of the elements are squares and half are not).

It can be shown that the probability of this happening in total is $\approx \frac{1}{\sqrt{\pi m}}$. So we can just regenerate the witness few times (using some free parameters deliberately injected into the circuit), and get such a witness that $H$ decomposes.

## Mitigation Cost and Optimization Tricks

Purely from the ciphertext size perspective we

1. Roughly double the amount of variables (we currently have $n \approx m$), so there is $2\times$ more matrices.
2. Roughly triple the amount of gates (the commutator structure fully disappears at $\sim 3m$ points). This is another $9\times$.
3. Need to use the gate matrix able to support the check of the form $ab - c^2 = ef$. We have obtained such 4x4 matrix, but without $\xi$-terms. Luckily, it turns out that $\xi$-terms are not necessary in the encoded construction.

So naively, this increases the ciphertext $18\times$ times.

There are some more aggressive tricks that could further offset this growth. Because we are in the QAP world already, it seems strange that we are telling the decryptor *in which points* do we evaluate our QAP - after all, it doesn’t really need this information! Then, it is plausible that the amount of points can be decreased - at least all known attacks do not really work if we query in just $m + O(\lambda)$ random hidden points. Under this optimistic regime, the fix would cost just $\sim2\times$.

Another related optimization is the structured matrices approach that we initially invented pufferfishes for. This is a story for another day - as for now we need to clear the baseline and make sure that our main scheme is not leaking; but generally moving to pufferfishes seems to enable various optimizations all around.


Our papers

Shielded Bitcoin

Cryptanalysis of ADP-based Witness Encryption

Bitcoin PIPEs v2

Witness Encryption from Arithmetic Affine Determinant Programs

Placeholder

zkLLVM Circuit Compiler

Bitcoin PIPEs