Today we’re sharing a new preprint Duty-Free Bits: Projectivizing Garbling Schemes, a collaboration between Nakul Khambhati (UCLA & Alpen Labs), Anwesh Bhattacharya (UIUC), and David Heath (UIUC).
The paper introduces a technique that makes modern arithmetic garbling schemes compatible with Bitcoin without the large communication overhead that previous approaches incurred. Applied to recent constructions such as BABE and Argo, this reduces the size of state-of-the-art garbled locks by 20–45×, making these protocols even more practical on Bitcoin.
You can read the paper here: Duty-Free Bits: Projectivizing Garbling Schemes.
A line of recent work has explored how to enable more expressive protocols on Bitcoin without requiring changes to the base layer. One promising direction uses garbled circuits to move expensive verification logic off-chain while preserving the ability to produce fraud proofs if something goes wrong.
This paradigm has been formalized through garbled locks (glocks), which use garbled circuits to enforce correct execution of off-chain computations in Bitcoin-based protocols.
A key application is verifying SNARK proofs. Early approaches represented the SNARK verifier as a Boolean circuit. While straightforward, this leads to extremely large garbled circuits, on the order of tens of gigabytes, making the approach difficult to deploy in practice.
Recent work such as Argo and BABE observed that Groth16 verification is naturally an arithmetic computation over finite fields. By taking advantage of this structure and using efficient arithmetic garbling schemes, these constructions reduced the size of garbled circuits by more than three orders of magnitude.
This shift from Boolean to arithmetic garbling enabled dramatically smaller and more efficient designs.
Despite these advances, there was still an important obstacle.
For a garbling scheme to be Bitcoin-compatible, its input encodings must correspond to bitwise Lamport signatures. In the garbled circuit literature, this property is known as projectivity.
Arithmetic garbling schemes, however, typically encode inputs directly as field elements, not bits. Bridging this mismatch proved expensive.
Prior work addressed the problem using bit decomposition. A field element is decomposed into its binary representation, and each bit is encoded separately. While this works, it introduces a large communication overhead: the encoding size increases by roughly a factor of 254, one for each bit of the field element.
In practice, this meant that even highly efficient arithmetic garbling schemes still paid a substantial “communication tax” to become Bitcoin-compatible.
The main result of Duty-Free Bits is that this multiplicative overhead is not necessary.
The paper shows that any arithmetic garbling scheme with affine input encodings over a prime field can be transformed into a projective scheme with only a small additive overhead, rather than the large multiplicative cost incurred by bit decomposition.
The construction is proven secure under the circular correlation robust hash (CCRH) assumption—the same assumption underlying the widely used Free-XOR optimization in garbled circuit constructions.
In other words, we can make arithmetic garbling schemes Bitcoin-friendly without paying the communication duty that previous approaches required.
The paper applies this technique to two recent constructions.
Embryo is a drop-in replacement for the garbled scalar multiplication scheme used in BABE.
With Duty-Free Bits, the encoding size drops from:
22.16 MiB → 500 KiB
This is a 45× reduction, achieved without increasing computational cost.
The same technique can also replace the projectivization step used in Argo MAC.
Here, the encoding size decreases from:
6.8 MiB → 355 KiB
This yields roughly a 20× improvement, again without additional computational overhead.
Taken together, these results show three things:
For protocols built on garbled locks, this translates directly into smaller communication, lower storage requirements, and more practical deployments.
This work builds on a sequence of recent advances in optimistic protocol design for Bitcoin.
Argo and BABE demonstrated how to leverage arithmetic structure in SNARK verification to dramatically shrink garbled circuits. Duty-Free Bits extends this line of research by showing that making these schemes compatible with Bitcoin can be done efficiently as well.
We’re grateful to collaborate with researchers at UIUC on this work and excited to see how these ideas continue to evolve.
© 2025 Alpen Labs. All rights reserved.
.svg)
