[[alloc] init]

ABOUT US

TECHNOLOGY

VISION

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

Bitcoin PIPEs v2

Witness Encryption from Arithmetic Affine Determinant Programs

Covenants and ZKPs on Bitcoin Without Soft Fork

Bitcoin PIPEs

FEATURED

We are hiring across several technical roles

Join our team

Learn about PIPEs or contribute to our research.

Get in touch


# Introduction

This post introduces Bitcoin PIPEs (covenants via Polynomial Inner Product Encryption (FH-MIPE)) as an approach to implementing covenants on for Bitcoin without requiring a soft fork.

Covenants provide a way to enhance Bitcoin’s capabilities by allowing users to set specific rules on how their coins can be spent in the future.

With covenants, Bitcoin can unlock a range of advanced features:

* Advanced spending rules: Users could restrict coins to be spent only at specific addresses or after certain conditions, such as a delay in time.
* New use cases: Covenants, for example, enable the native verification of Zero-Knowledge Proofs (ZKPs), native tokens with complex behaviors, and even restaking mechanisms to pool Bitcoin and help secure other networks.

Covenants can make Bitcoin much more versatile but require upgrades to the network, making them increasingly unlikely.

Polynomial Inner Product Encryption (PIPE (QFE over FH-MIPE)) is an encryption scheme that enables developers to implement advanced covenants without altering Bitcoin’s core protocol. This means it is possible to emulate missing opcodes (e.g. `OP_CAT` or `OP_CTV`) via establishing a PIPE for a particular opcode desired, avoiding the need for a soft fork or the use of trusted solutions.

With PIPEs, Bitcoin can support:

* Complex transaction conditions: Enabling multiple steps or conditions before transaction is processed/funds are released.
* Efficient batch transactions: Predefining transaction templates to save space and reduce fees.
* Scalable cryptographic proofs: Facilitating Zero-Knowledge Proofs, which improve Bitcoin's scalability and performance.

This way Bitcoin PIPEs offer a way to introduce new features to Bitcoin without the risks of a soft fork or changing its core protocol.

# Preliminaries

Bitcoin’s scripting language is known for its simplicity and security. Unfortunately this simplicity comes with limitations, particularly when it comes to handling complex transaction types or advanced cryptographic operations.

To address these limitations, covenants have been proposed as a way to extend Bitcoin's scripting capabilities. Covenants allow users to impose specific conditions on how bitcoins can be spent in the future, offering greater flexibility and control.

Covenants enhance Bitcoin's functionality by enabling more complex transaction rules, allowing for use cases that are currently impossible to implement with the existing scripting language.

Covenants can be applied to various scenarios, both simple and complex, to enhance security, privacy, and functionality in the Bitcoin ecosystem.

* Advanced Transaction Structuring with `OP_CAT`: `OP_CAT` allows for the concatenation of two or more elements on the stack, enabling more complex transaction structures (and the verification of Merkle tree paths). For example, `OP_CAT` could be used to combine a user’s address with a unique identifier, ensuring that the transaction is only valid if the combined data matches a specific pattern.
* Batch Payments and Congestion Control with `OP_CTV`: The CheckTemplateVerify (`OP_CTV`) opcode allows users to predefine a specific set of transaction outputs, ensuring that a transaction can only be executed if it matches this predefined template. This reduces the need for multiple individual transactions, lowering fees and reducing network congestion.
* Restaking Mechanisms: Covenants could be used to enable restaking, where users can lock up their bitcoins to participate in staking-like mechanisms without needing to move their funds off-chain. For example, a covenant could be designed to define a slashing condition for a protocol - a withdrawal can be enabled only in case the covenant is not satisfied.
* ZKP Verification (zkRollup Support): Zero-Knowledge Rollups (zkRollups) are a scaling solution that submits a bunch of unexecuted transactions into an L1 and proves its correctness with a state transition proof. Covenants could be designed to enforce that only transactions within a zkRollup are valid, ensuring that large numbers of transactions can be processed off-chain while maintaining security on-chain.

# Bitcoin PIPE: Covenants via Polynomial Inner Product Encryption

Polynomial Inner Product Encryption (PIPE) presents itself as an efficient solution to unlocking the benefits of covenants without requiring any changes to the network’s consensus rules.

One of the challenges in enhancing Bitcoin’s scripting capabilities is the absence of certain opcodes that would enable more complex and powerful transaction logic. Bitcoin PIPEs (Polynomial Inner Product Encryption) emulates these missing opcodes without requiring changes to Bitcoin’s core protocol, allowing developers to create sophisticated covenants without the need for soft forks or increased trust assumptions.

### What is Bitcoin PIPE?

Polynomial Inner Product Encryption (PIPE) is a FH-MIPE (full-hiding multi-input inner product encryption) scheme that enables the computation of inner products, which with certain modifications (being turned into QFE with Schnorr signing and IPA-based proof system verification embedded) can sign Bitcoin transactions using the encrypted signing key in case certain logic is satisfied (the proof verification is successful) without revealing the key itself.

By embedding IPA-based proof system verifier inside of FH-MIPE inner product computation process, it is, for example, possible to enforce the execution of complex logic and emulate the behavior of missing opcodes, such as `OP_CAT` (which concatenates elements on the stack) or `OP_CTV` (which predefines specific transaction templates).

Bitcoin PIPEs allows transactions to be signed with Schnorr signatures (Taproot signatures), without the need for protocol upgrades or new opcodes in case the verification was completed successfully.

Besides emulating opcodes, Bitcoin PIPEs can be defined to be much more complicated than trivial opcode’s logic:

* Application-Specific Covenants: Through defining a PIPE, developers can craft covenants tailored to specific applications, like enforcing cryptographic proofs (e.g., zero-knowledge proofs) within transactions.
* Enhancing Bitcoin's Programmability: A key advantage of Bitcoin PIPEs is that it enhances the Bitcoin programmability without the need for protocol changes or additional trust assumptions. This means that developers can introduce more sophisticated logic and conditions into their transactions without waiting for consensus on new opcodes or the use of less secure solutions (sidechains).

### Bitcoin PIPEs Architecture

Bitcoin PIPE acts as an off-chain FH-MIPE-based processor of an encrypted transaction signing key, which yields a signature in case the predicate logic is satisfied (e.g. a zk-proof is verified or a concatenation is done correctly).

### Bitcoin PIPE Setup

1. Define a functionality desired to be executed before the transaction happens.
2. Create a zero-knowledge proof (ZKP) to prove execution of computations desired.
3. Perform a DKG/Encryption phase for the address which a PIPE (Covenant) is supposed to restrict.
4. Submit PIPE ciphertext as a Taproot transaction into Bitcoin (inscription-alike mechanics).

### Bitcoin PIPE Usage

1. Retrieve a ciphertext and a decryption key from a PIPE inscription.
2. Prepare the transaction data for signing.
3. Put the transaction through the PIPE decryption functionality execution.
4. If a transaction doesn’t violate the application logic desired, then a PIPE will produce a signed Taproot transaction.
5. Submit the transaction to Bitcoin.

A PIPE being set up this way (as an example) represents non-custodial storage for Bitcoin which allows withdrawals in case certain application logic conditions are satisfied.

### Security Assumptions

Since existing conceptual frameworks for enhancing Bitcoin’s functionality and enabling complex, programmable transactions rely on trust-minimized (not fully trustless) systems or social consensus for protocol changes, it is important to further minimize trust assumptions for Bitcoin PIPEs.

Given the need to eliminate trust assumptions as much as possible, Bitcoin PIPEs become effectively trustless after completion of a one-time trusted setup (DKG), which brings trust assumptions to 1-out-of-n for each new covenant creation. In other words, so long as one participant behaves honestly the system is secure. To clarify, Bitcoin PIPEs do not rely on moving assets off-chain (i.e. no required use of bridging or sidechains), custodians (or custodian chains), or multi-signatures.

# Conclusion

Bitcoin covenants, made possible by PIPEs, represent an attempt to push forward Bitcoin programmability by providing a method to introduce complex, secure, and flexible transaction rules without the need for consensus on new opcodes or soft forks. This approach not only preserves Bitcoin's foundational principles, but also broadens its functional horizon, making it ready for more advanced financial and contractual applications while maintaining its core security and simplicity.


Covenants and ZKPs on Bitcoin With out Soft Fork


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.


Blogs

Bitcoin PIPEs

Cryptographic Challenges for AADP WE

AADP WE Commutator Attack & Patch