By Joop van de Pol

We found a vulnerability in a threshold signature scheme that allows an attacker to recover the signing key of threshold ECDSA implementations that are based on Oblivious Transfer (OT). A malicious participant of the threshold signing protocols could perform selective abort attacks during the OT extension subprotocol, recover the secret values of other parties, and eventually recover the signing key. Using this key, the attacker could assume the identities of users, gain control over critical systems, or pilfer financial assets. While we cannot yet disclose the client software affected by this vulnerability, we believe it is instructive for other developers implementing MPC protocols.

Protecting against this vulnerability is straightforward: since the attack relies on causing selective aborts during several protocol rounds, punishing or excluding participants that cause selective aborts is sufficient. Still, it’s a good example of a common problem that often leads to severe or even critical issues: a disconnect between assumptions made by academics and the implementers trying to build these protocols efficiently in real systems.

Threshold signature schemes

Threshold signature schemes (TSS) are powerful cryptographic objects that allow decentralized control of the signing key for a digital signature scheme. They are a specific application of the more general multi-party computation (MPC), which aims to decentralize arbitrary computation. Each TSS protocol is typically defined for a specific digital signature scheme because different signature schemes require different computations to create signatures.

Current research aims to define efficient TSS protocols for various digital signature schemes. The target for efficiency includes both computation and communication between the different participants. Typically, TSS protocols rely on standard techniques used in MPC, such as secret sharing, zero-knowledge proofs, and multiplicative-to-additive conversion

Threshold ECDSA

The ECDSA signature scheme is widely used. However, threshold schemes for ECDSA are generally more complicated than those for other signature schemes. This is because an ECDSA signature requires the computation of the modular inverse of a secret value.

Various MPC techniques can be used to distribute the computation of this modular inverse. Currently, one line of work in threshold signature schemes for ECDSA uses the homomorphic Paillier encryption scheme for this purpose, as shown in work by Lindell et al., Gennaro et al., and following works. This blog post will focus on schemes that rely on oblivious transfer (OT), such as the work by Doerner et al. and following works, or Cait-Sith.

Before explaining what OT is, it should be noted that the basic variant is relatively inefficient. To mitigate this issue, researchers proposed something called OT extension, where a small number of OTs can efficiently be turned into a larger number of OTs. This feature is eagerly used by the creators of threshold signature schemes, as you can run the setup of the small number of OTs once, and then extend arbitrarily many times.

Oblivious transfer

Oblivious transfer is like the setup of a magician’s card trick. A magician has a bunch of cards and wants you to choose one of them, so they can show off their magic prowess by divining which card you chose. To this end, it is important that the magician does not know which card you chose, but also that you choose exactly one card and cannot claim later that you actually chose another card.

In real life, the magician could let you write something on the card that you chose, forcing you to choose exactly one card. However, this would not be good enough for the cryptographic setting, because the magician could afterwards just look at all the cards (using their impressive sleight of hand to hide this fact) and pick out the card that has text on it. A better solution would be to have the magician write a random word on each card, such that you can choose a card by memorizing this word. Now, in real life the magician might allow you to look at multiple cards before choosing one, whereas in the cryptographic case you have to choose a card blindly such that you only learn the random word written on the card that you chose.

After choosing the card and giving it back to the magician (randomly shuffling the cards to ensure they cannot directly pick out the card that you returned), they can now try to figure out which card you chose. In real life, the magician will use all kinds of tricks to try and pick out your card, whereas in the cryptographic setting, they actually should not be able to.

So, in a nutshell, OT is about a sender (the magician) who wants to give a receiver (you, the mark) a choice between some values (cards). The sender should not learn the receiver’s choice, and the receiver should not learn any other values than the chosen one.

It turns out that OT is a very powerful MPC primitive, as it can be used as a building block to construct protocols for any arbitrary multi-party computation. However, implementing OT without any special assumptions requires asymmetric cryptography, which is relatively expensive. Using expensive building blocks will lead to an inefficient protocol, so something more is needed to be able to use OT in practice.

OT extension

OT requires either asymmetric cryptography or “special assumptions.” This means that OT is possible when the two parties already have access to something called correlated randomness. Even better, this correlated randomness can be created from the output of an OT protocol.

As a result, it is possible to run the expensive OT protocol a number of times, and then to extend these “base” OTs into many more OTs. This extension is possible using only symmetric cryptography (such as hash functions and pseudo-random generators), which makes it more efficient than the expensive asymmetric variants.

For this blog post, we will focus on a particular line of work in OT extension, starting with this paper by Ishai et al. It is a bit too complicated to explain in detail how this scheme works, but the following points are important:

What does this last point mean? The extended OT receiver can cheat and learn the original choice bits belonging to the extended OT sender. Ishai et al. proposed a solution, but it is not very efficient. Therefore, followup works such as by Asharov et al. and by Keller et al. add a kind of consistency check, where the extended OT receiver has to provide some additional information. The extended OT sender can then use this information to verify that the receiver did not cheat.

These consistency checks restrict how much the receiver can learn about the sender’s secret choices, but they are not perfect. The check that the sender performs to verify the receiver’s information depends on their own secret choices. Therefore, the receiver can still cheat in specific places such that they learn some bits of the sender’s secret choices based on whether or not the sender aborts. This is known as a selective abort attack, as the receiver can selectively try to cause an abort and learns some information from the sender as a result.

The aforementioned papers acknowledge that this kind of leakage can happen for a cheating receiver. However, the authors choose the parameters of the scheme such that the receiver can never learn enough about the sender’s original choice bits when running the protocol once. Problem solved, right?

How the vulnerability works

Recall that in the context of threshold signature schemes based on OT, you want to perform the base OTs once during a set-up phase and reuse this set-up arbitrarily many times to perform OT extension. Since this improves efficiency, implementers will jump on it. What is not mentioned very explicitly, and what caused the vulnerability that we found, is that you can reuse the set-up arbitrarily many times only if the OT extension receiver does not cheat.

If the receiver cheats, then they can learn a few bits of the secret set-up value of the OT extension sender. This does become a problem if you allow the receiver to do this multiple times over different executions of the protocol. Eventually, the receiver learns all secret sender bits, and the security is completely compromised. Typically, depending on the specific TSS, the receiver can now use the secret sender bits to recover sender shares corresponding to the ECDSA nonce. In a scheme with a threshold of two, this means that the receiver recovers the nonce, and they can recover the ECDSA signing key given a valid signature with this nonce. (In schemes with more parties, the attacker may have to repeat this attack for multiple parties.)

So what’s the issue here exactly? Selective abort attacks are known and explicitly discussed in OT extension papers, but those papers are not very clear on whether you can reuse the base OTs. Implementers and TSS protocol designers want to reuse the base OTs arbitrarily many times, because that’s efficient. TSS protocol designers know that selective abort attacks are an issue, so they even specify checks and consider the case closed, but they are not very clear on what implementers are supposed to do when checks fail. This kind of vagueness in academic papers invariably leads to attacks on real-world systems.

In this case, a clear solution would be to throw away the setup for a participant that has attempted to cheat during the OT extension protocol. Looking at some public repositories out there, most OT extension libraries will report something along the lines of “correlation check failed,” which does not tell a user what to do next. In fact, only one library added a warning that a particular check’s failure may represent an attack and that you should not re-run the protocol.

Bridging the gap between academia and implementations

Most academic MPC papers provide a general overview of the scheme and corresponding proof of security; however, they don’t have the detail required to constitute a clear specification and aren’t intended to be blueprints for implementations. Making wrong assumptions when interpreting academic papers to create real-world applications can lead to severe issues. We hope that the recent call from NIST for Multi-Party Threshold Cryptography will set a standard for specifications of MPC and TSS and prevent such issues in the future.

In the meantime, if you’re planning to implement threshold ECDSA, another TSS, or MPC in general, you can contact us to specify, implement, or review those implementations.

By Brent Pappas

Despite its use for refactoring and static analysis tooling, Clang has a massive shortcoming: the Clang AST does not provide provenance information about which CPP macro expansions a given AST node is expanded from; nor does it lower macro expansions down to LLVM Intermediate Representation (IR) code. This makes the construction of macro-aware static analyses and transformations exceedingly difficult and an ongoing area of research.¹ Struggle no more, however, because this summer at Trail of Bits, I created Macroni to make it easy to create macro-aware static analyses.

Macroni allows developers to define the syntax for new C language constructs with macros and provide the semantics for these constructs with MLIR. Macroni uses VAST to lower C code down to MLIR and uses PASTA to obtain macro-to-AST provenance information to lower macros down to MLIR as well. Developers can then define custom MLIR converters to transform Macroni’s output into domain-specific MLIR dialects for more nuanced analyses. In this post, I will present several examples of how to use Macroni to augment C with safer language constructs and build C safety analyses.

Stronger typedefs

C typedefs are useful for giving semantically meaningful names to lower-level types; however, C compilers don’t use these names during type checking and perform their type checking only on the lower-level types instead. This can manifest in a simple form of type-confusion bug when the semantic types represent different formats or measures, such as the following:

typedef double fahrenheit;
typedef double celsius;
fahrenheit F;
celsius C;
F = C; // No compiler error or warning

Figure 1: C type checking considers only typedef’s underlying types.

The above code successfully type checks, but the semantic difference between the types fahrenheit and celsius should not be ignored, as they represent values in different temperature scales. There is no way to enforce this sort of strong typing using C typedefs alone.

With Macroni, we can use macros to define the syntax for strong typedefs and MLIR to implement custom type checking for them. Here’s an example of using macros to define strong typedefs representing temperatures in degrees Fahrenheit and Celsius:

#define STRONG_TYPEDEF(name) name
typedef double STRONG_TYPEDEF(fahrenheit);
typedef double STRONG_TYPEDEF(celsius);

Figure 2: Using macros to define syntax for strong C typedefs

Wrapping a typedef name with the STRONG_TYPEDEF() macro allows Macroni to identify typedefs whose names were expanded from invocations of STRONG_TYPEDEF() and convert them into the types of a custom MLIR dialect (e.g., temp), like so:

%0 = hl.var "F" : !hl.lvalue<!temp.fahrenheit>
%1 = hl.var "C" : !hl.lvalue<!temp.celsius>
%2 = hl.ref %1 : !hl.lvalue<!temp.celsius>
%3 = hl.ref %0 : !hl.lvalue<!temp.fahrenheit>
%4 = hl.implicit_cast %3 LValueToRValue : !hl.lvalue<!temp.fahrenheit> -> !temp.fahrenheit
%5 = hl.assign %4 to %2 : !temp.fahrenheit, !hl.lvalue<!temp.celsius> -> !temp.celsius

Figure 3: Macroni enables us to lower typedefs to MLIR types and enforce strict typing.

By integrating these macro-attributed typedefs into the type system, we can now define custom type-checking rules for them. For instance, we could enforce strict type checking for operations between temperature values so that the above program would fail to type check. We could also add custom type-casting logic for temperature values so that casting a temperature value in one scale to a different scale implicitly inserts instructions to convert between them.

The reason for using macros to add the strong typedef syntax is that macros are both backwards-compatible and portable. While we could identify our custom types with Clang by annotating our typedefs using GNU’s or Clang’s attribute syntax, we cannot guarantee annotate()‘s availability across platforms and compilers, whereas we can make strong assumptions about the presence of a C preprocessor.

Now, you might be thinking: C already has a form of strong typedef called struct. So we could also enforce stricter type checking by converting our typedef types into structs (e.g., struct fahrenheit { double value; }), but this would alter both the type’s API and ABI, breaking existing client code and backwards-compatibility. If we were to change our typedefs into structs, a compiler may produce completely different assembly code. For example, consider the following function definition:

fahrenheit convert(celsius temp) { return (temp * 9.0 / 5.0) + 32.0; }

Figure 4: A definition for a Celsius-to-Fahrenheit conversion function

If we define our strong typedefs using macro-attributed typedefs, then Clang emits the following LLVM IR for the convert(25) call. The LLVM IR representation of the convert function matches up with its C counterpart, accepting a single double-typed argument and returning a double-typed value.

tail call double @convert(double noundef 2.500000e+01)

Figure 5: LLVM IR for convert(25), with macro-attributed typedefs used to define strong typedefs

Contrast this to the IR that Clang produces when we define our strong typedefs using structs. The function call now accepts four arguments instead of one. That first ptr argument represents the location where convert will store the return value. Imagine what would happen if client code called this new version of convert according to the calling convention of the original.

call void @convert(ptr nonnull sret(%struct.fahrenheit) align 8 %1,
                   i32 undef, i32 inreg 1077477376, i32 inreg 0)

Figure 6: LLVM IR for convert(25), with structs used to define strong typedefs

Weak typedefs that ought to be strong are pervasive in C codebases, including critical infrastructure like libc and the Linux kernel. Preserving API- and ABI-compatibility is essential if you want to add strong type checking to a standard type such as time_t. If you wrapped time_t in a struct (e.g., struct strict_time_t { time_t t; }) to provide strong type checking, then not only would all APIs accessing time_t-typed values need to change, but so would the ABIs of those usage sites. Clients who were already using bare time_t values would need to painstakingly change all the places in their code that use time_t to instead use your struct to activate stronger type checking. On the other hand, if you used a macro-attributed typedef to alias the original time_t (i.e., typedef time_t STRONG_TYPEDEF(time_t)), then time_t‘s API and ABI would remain consistent, and client code using time_t correctly could remain as-is.

Enhancing Sparse in the Linux Kernel

In 2003, Linus Torvalds built a custom preprocessor, C parser, and compiler called Sparse. Sparse performs Linux kernel–specific type checking. Sparse relies on macros, such as __user, sprinkled around in kernel code, that do nothing under normal build configurations but expand to uses of __attribute__((address_space(...))) when the __CHECKER__ macro is defined.

Gatekeeping the macro definitions with __CHECKER__ is necessary because most compilers don’t provide ways to hook into macros or implement custom safety checking … until today. With Macroni, we can hook into macros and perform Sparse-like safety checks and analyses. But where Sparse is limited to C (by virtue of implementing a custom C preprocessor and parser), Macroni applies to any code parseable by Clang (i.e., C, C++, and Objective C).

The first Sparse macro we’ll hook into is __user. The kernel currently defines __user to an attribute that Sparse recognizes:

# define __user     __attribute__((noderef, address_space(__user)))

Figure 7: The Linux kernel’s __user macro

Sparse hooks into this attribute to find pointers that come from user space, as in the following example. The noderef tells Sparse that these pointers must not be dereferenced (e.g., *uaddr = 1) because their provenance cannot be trusted.

u32 __user *uaddr;

Figure 8: Example of using the __user macro to annotate a variable as coming from user space

Macroni can hook into the macro and expanded attribute to lower the declaration down to MLIR like this:

%0 = hl.var "uaddr" : !hl.lvalue<!sparse.user<!hl.ptr<!hl.elaborated<!hl.typedef<"u32">>>>>

Figure 9: Kernel code after being lowered to MLIR by Macroni

The lowered MLIR code embeds the annotation into the type system by wrapping declarations that come from user space in the type sparse.user. Now we can add custom type-checking logic for user-space variables, similar to how we created strong typedefs previously. We can even hook into the Sparse-specific macro __force to disable strong type checking on an ad hoc basis, as developers do currently:

raw_copy_to_user(void __user *to, const void *from, unsigned long len)
{
   return __copy_user((__force void *)to, from, len);
}

Figure 10: Example use of the __force macro to copy a pointer to user space

We can also use Macroni to identify RCU read-side critical sections in the kernel and verify that certain RCU operations appear only within these sections. For instance, consider the following call to rcu_dereference():

rcu_read_lock();
rcu_dereference(sbi->s_group_desc)[i] = bh;
rcu_read_unlock();

Figure 11: A call to rcu_derefernce() in an RCU read-side critical section in the Linux kernel

The above code calls rcu_derefernce() in a critical section—that is, a region of code beginning with a call to rcu_read_lock() and ending with rcu_read_unlock(). One should call rcu_dereference() only within read-side critical sections; however, there is no way to enforce this constraint.

With Macroni, we can use rcu_read_lock() and rcu_read_unlock() calls to identify critical sections that form implied lexical code regions and then check that calls to rcu_dereference() appear only within these sections:

kernel.rcu.critical_section {
 %1 = macroni.parameter "p" : ...
 %2 = kernel.rcu_dereference rcu_dereference(%1) : ...
}

Figure 12: The result of lowering the RCU-critical section to MLIR, with types omitted for brevity

The above code turns both the RCU-critical sections and calls to rcu_dereference() into MLIR operations. This makes it easy to check that rcu_dereference() appears only within the right regions.

Unfortunately, RCU-critical sections don’t always bound neat lexical code regions, and rcu_dereference() is not always called in such regions, as shown in the following example:

__bpf_kfunc void bpf_rcu_read_lock(void)
{
       rcu_read_lock();
}

Figure 13: Kernel code containing a non-lexical RCU-critical section

static inline struct in_device *__in_dev_get_rcu(const struct net_device *dev)
{
   return rcu_dereference(dev->ip_ptr);
}

Figure 14: Kernel code calling rcu_dereference() outside of an RCU-critical section

We can use the __force macro to permit these sorts of calls to rcu_dereference(), just as we did to escape type checking for user-space pointers.

Rust-like unsafe regions

It’s clear that Macroni can help strengthen type checking and even enable application-specific type-checking rules. However, marking types as strong means committing to that level of strength. In a large codebase, such a commitment might require a massive changeset. To make adapting to a stronger type system more manageable, we can design an “unsafety” mechanism for C akin to that of Rust: within the unsafe region, strong type checking does not apply.

#define unsafe if (0); else


fahrenheit convert(celsius C) {
 fahrenheit F;
 unsafe {
         F = (C * 9.0 / 5.0) + 32.0;
 }
 return F;
}

Figure 15: C code snippet presenting macro-implemented syntax for unsafe regions

This snippet demonstrates our safety API’s syntax: we call the unsafe macro before potentially unsafe regions of code. All code not listed in an unsafe region will be subject to strong type checking, while we can use the unsafe macro to call out regions of lower-level code that we deliberately want to leave as-is. That’s progressive!

The unsafe macro provides the syntax only for our safety API, though, and not the logic. To make this leaky abstraction watertight, we would need to transform the macro-marked if statement into an operation in our theoretical safety dialect:

...
"safety.unsafe"() ({
   ...
}) : () -> ()
...

Figure 16: With Macroni, we can lower our safety API to an MLIR dialect and implement safety-checking logic.

Now we can disable strong type checking on operations nested within the MLIR representation of the unsafe macro.

Safer signal handling

By this point, you may have noticed a pattern for creating safer language constructs: we use macros to define syntax for marking certain types, values, or regions of code as obeying some set of invariants, and then we define logic in MLIR to check that these invariants hold.

We can use Macroni to ensure that signal handlers execute only signal-safe code. For example, consider the following signal handler defined in the Linux kernel:

static void sig_handler(int signo) {
       do_detach(if_idx, if_name);
       perf_buffer__free(pb);
       exit(0);
}

Figure 17: A signal handler defined in the Linux kernel

sig_handler() calls three other functions in its definition, which should all be safe to call in signal-handling contexts. However, nothing in the above code checks that we call signal-safe functions only inside sig_handler()‘s definition—C compilers don’t have a way of expressing semantic checks that apply to lexical regions.

Using Macroni, we could add macros for marking certain functions as signal handlers and others as signal-safe and then implement logic in MLIR to check that signal handlers call only signal-safe functions, like this:

#define SIG_HANDLER(name) name
#define SIG_SAFE(name) name


int SIG_SAFE(do_detach)(int, const char*);
void SIG_SAFE(perf_buffer__free)(struct perf_buffer*);
void SIG_SAFE(exit)(int);


static void SIG_HANDLER(sig_handler)(int signo) { ... }

Figure 18: Token-based syntax for marking signal handlers and signal-safe functions

The above code marks sig_handler() as a signal handler and the three functions it calls as signal-safe. Each macro invocation expands to a single token—the name of the function we want to mark. With this approach, Macroni hooks into the expanded function name token to determine if the function is a signal handler or signal-safe.

An alternative approach would be to define these macros to magic annotations and then hook into these with Macroni:

#define SIG_HANDLER __attribute__((annotate("macroni.signal_handler")))
#define SIG_SAFE __attribute__((annotate("macroni.signal_safe")))


int SIG_SAFE do_detach(int, const char*);
void SIG_SAFE perf_buffer__free(struct perf_buffer*);
void SIG_SAFE exit(int);


static void SIG_HANDLER sig_handler(int signo) { ... }

Figure 19: Alternative attribute syntax for marking signal handlers and signal-safe functions

With this approach, the macro invocation looks more like a type specifier, which some may find more appealing. The only difference between the token-based syntax and the attribute syntax is that the latter requires compiler support for the annotate() attribute. If this is not an issue, or if __CHECKER__-like gatekeeping is acceptable, then either syntax works fine; the back-end MLIR logic for checking signal safety would be the same regardless of the syntax we choose.

Conclusion: Why Macroni?

Macroni lowers C code and macros down to MLIR so that you can avoid basing your analyses on the lackluster Clang AST and instead build them off of a domain-specific IR that has full access to types, control flow, and data flow within VAST’s high-level MLIR dialect. Macroni will lower the domain-relevant macros down to MLIR for you and elide all other macros. This unlocks macro-sensitive static analysis superpowers. You can define custom analyses, transformations, and optimizations, taking macros into account at every step. As this post demonstrates, you can even combine macros and MLIR to define new C syntax and semantics. Macroni is free and open source, so check out its GitHub repo to try it out!

Acknowledgments

I thank Trail of Bits for the opportunity to create Macroni this summer. In particular, I would like to thank my manager and mentor Peter Goodman for the initial idea of lowering macros down to MLIR and for suggestions for potential use cases for Macroni. I would also like to thank Lukas Korencik for reviewing Macroni’s code and for providing advice on how to improve it.

¹ See Understanding code containing preprocessor constructs, SugarC: Scalable Desugaring of Real-World Preprocessor Usage into Pure C, An Empirical Analysis of C Preprocessor Use, A Framework for Preprocessor-Aware C Source Code Analyses, Variability-aware parsing in the presence of lexical macros and conditional compilation, Parsing C/C++ Code without Pre-processing, Folding: an approach to enable program understanding of preprocessed languages, and Challenges of refactoring C programs.

By Benjamin Samuels

Many security-critical off-chain applications use a simple block delay to determine finality: the point at which a transaction becomes immutable in a blockchain’s ledger (and is impossible to “undo” without extreme economic cost). But this is inadequate for most networks, and can become a single point of failure for the centralized exchanges, multi-chain bridges, and L2 scaling solutions that rely on transaction finality. Without proper consideration of a blockchain’s finality criteria, transactions that appear final can be expunged from the blockchain by a malicious actor in an event called a re-org, leading to double-spend attacks and value stolen from the application.

We researched several off-chain applications and L2 networks and discovered two L2 clients, Juno and Pathfinder, that either were not checking for finality or incorrectly used block delays to detect whether Ethereum blocks were finalized. We disclosed our findings to each product team, and fixes were published shortly after disclosure in version v0.4.0 for Juno and v0.6.2 for Pathfinder. This blog post gathers the knowledge and insights we gained from this research. It explains the dangers of reorgs, the differences between distinct finality mechanisms, and how to prevent double-spend attacks when writing applications that consume data from different kinds of blockchains.

Understanding re-orgs

When a user submits a transaction to a blockchain, it follows a lifecycle that is nearly identical across all blockchains. First, their transaction is gossiped across the blockchain’s peer-to-peer network to a block proposer. Once a block proposer receives the transaction and includes it in a block, the block is broadcast across the network.

Here is where the problems begin: some blockchains don’t explicitly define who the next block proposer should be, and the ones that do need a way to recover if that proposer is offline. These conditions lead to situations where there are two or more valid ways for the blockchain to proceed (a fork), and the network has to figure out which fork should be canonical.

Figure 1: Two miners on a PoW network propose a valid block for slot 4 at the same time.

Blockchains are designed with these issues in mind and define a fork choice rule to determine which fork should be considered canonical. Forks can sometimes last for multiple blocks, where different portions of the network consider a different chain to be canonical.

Figure 2: A PoW network where block candidates for slots 4, 5, and 6 were mined in quick succession and built on different parents, leading to a fork.

Assuming there is no bug in the network’s software, the fork will eventually be reconciled, leading to a single fork becoming canonical. The other forks, their blocks, and their transactions are expunged from the blockchain’s history, called a re-org.

When a transaction is expunged from the chain via a re-org, that transaction may either be re-queued for inclusion in a new block, or otherwise have its ordering or block number changed to whatever it is in the canonical chain. Attackers can leverage these changes to modify a transaction’s behavior or cancel the transaction entirely based on which fork it is included on.

Figure 3: A network after a three-block re-org. Transactions in blocks 4a, 5a, and 6a are no longer part of the canonical chain.

Re-orgs are a normal part of a blockchain’s lifecycle, and can happen regularly due to factors like block production speed, network latency, and network health. However, attackers can take advantage of (and even orchestrate!) re-orgs to perform double-spend attacks, a category of attack where an attacker submits a deposit transaction, waits for it to be included in a block, then orchestrates a re-org to expunge their transaction from the canonical chain while still receiving credit for their deposit on the off-chain application.

It is for this reason that finality considerations are important. If a centralized exchange or bridge indexes a deposit transaction that is not final, it is vulnerable to double-spend attacks by way of an attacker causing a re-org of the blockchain.

Blockchains use a variety of different consensus algorithms and thus have a variety of different finality conditions that should be considered for each chain.

Probabilistic finality

Examples: Bitcoin, Binance Smart Chain (pre-BEP-126), Polygon PoS, Avalanche – or generally any PoW-based blockchain

Chains using probabilistic finality are unique in that their blocks are never actually finalized—instead, they become probabilistically final, or more “final” as time goes on. Given enough time, the probability that a previous block will be re-orged off the chain approaches zero, and thus the block becomes final.

In most probabilistically final chains, the fork choice rule that determines the canonical chain is based on whichever fork has the most blocks built on top of it, called Nakamoto consensus. Under Nakamoto consensus, the chain may re-org if a longer chain is broadcast to the network, even if the longer chain excludes blocks/transactions that were already included in the shorter chain.

Double-spend attacks on probabilistic proof-of-work networks

The classic attack against proof-of-work networks is a 51% re-org attack. This attack requires an off-chain exchange, bridge, or other application that indexes deposit transactions very quickly, ideally indexing blocks as soon as they are produced or with an exceedingly short delay.

The attacker must accumulate, purchase, or rent enough computing resources so the attacker controls the majority of the hash power on the network. This means the attacker has enough resources to privately mine a chain that’s longer than the honest canonical chain. Note that this is a probabilistic attack; control over 51% of the network’s hash power makes the attack an eventual certainty. An attacker could theoretically perform double-spend attacks with much less than 51% of the network’s hash power, but it may require many attempts before the attack succeeds.

Once the mining resources are ready, the attacker submits a transaction on the public, canonical chain to deposit funds from their wallet to the exchange/bridge.

Immediately afterward, the attacker must create a second, conflicting transaction that transfers funds from their wallet to another attacker-controlled address. The attacker configures their mining resources to mine a new fork that includes the transfer transaction instead of the deposit transaction.

Figure 4: The attacker creates a private fork that includes their transfer transaction instead of the deposit transaction.

Given that the attacker controls the majority of the hash power on the network, eventually their private fork will have more blocks than the canonical fork. Once they have received credit for the deposit transaction and their private fork has more blocks than the canonical chain, the attacker instructs their network to publish the private chain’s blocks to the honest nodes following the canonical chain.

The honest nodes apply the “longest chain” fork choice rule, triggering a re-org around the attacker’s longer chain and excluding the blocks that contained the attacker’s deposit transaction.

Figure 5: Once the attacker publishes their private fork, the network reorgs and expunges the fork that includes their deposit transaction.

In effect, this allows the attacker to “double-spend” their coins: the exchange or bridge credits the attacker for the coins, while the coins are still present in an attacker-controlled wallet.

Measuring probabilistic finality

Since probabilistically final chains don’t define finality conditions, finality must be measured probabilistically based on the number of blocks that have elapsed since the target transaction/ancestor block. The more blocks that have been built on top of a given ancestor, the higher the cost of a re-org is for an attacker.

The correct block delay should be based on both historical factors and economic factors, selecting the greater of the two for the application’s indexing delay.

Among historical factors, off-chain application developers should consider how often the chain has reorgs and how large the reorgs typically are. If block production is probabilistic (as in Proof-of-work networks), then a larger delay should be factored in to compensate for the chance that many blocks are created in an unusually short period of time.

Among economic factors, one should consider the cost to execute a re-org attack for a transaction of a given economic value. Given the probabilistic nature of 51% attacks, engineers should build in a safety margin and consider the cost of a 25% attack instead of 51%. For example, if it costs a minimum of $500k USD to execute a 25% attack, six-block re-org attack against Bitcoin, then an off-chain application that receives a $500k deposit should wait for at least six blocks before considering the transaction final and indexing it.

Using Crypto51, we can calculate the block delays required for deposits and withdrawals of $75k with a 25% attack threshold (as of June 2023).

• Bitcoin: Two blocks for finality (~20 minutes)
• Litecoin/Dogecoin: 48 blocks for finality (~Two hours)
• Bitcoin Cash: 103 blocks for finality (~17 hours)
• Ethereum Classic: 3,031 blocks for finality (~11 hours)
• Ethereum PoW: 23,600 blocks for finality (~89 hours)
• Zcash: 1,881 blocks for finality (~40 hours)

These delays represent a single data point in time for a specific deposit amount. As the hash power on each network increases or decreases, the time-to-finality will change as well and must be updated accordingly. Mining hash power on each network correlates highly with the chain token price, so the amount of hash power can drop very quickly, requiring monitoring and fast response by integrating applications. Failure to adjust finality delays in a timely manner will lead to double-spending attacks.

Finality delays for proof-of-work chains may be reduced for certain exchange-like applications using on-chain monitoring, automated system halts, trading limits, and withdrawal delays. However, these mechanisms may overcomplicate the application’s logic and make it vulnerable to other forms of attack.

It should be noted that chains with extraordinarily low hash rates may easily be attacked with much more than 51% of the network’s hash rate. Existing services offer an easy-to-rent hashing capacity that may exceed a chain’s hash rate many times over. In cases like this, it is recommended to either avoid integration with the chain, or base finality calculations on the available-for-rent hashing capacity.

Probabilistic chains using proof-of-stake/proof-of-authority require slightly different considerations, since block proposers cannot freely enter the proposer set and may have different fork choice rules than proof-of-work networks.

• Binance Smart Chain: Blocks are considered final once the number of blocks that have passed is equal to two-thirds the number of validators in their validator set. Twenty blocks are required for finality (~60 seconds).
• Polygon PoS: Integrators should use L1 state root checkpoints as a measure of finality. When a state root checkpoint containing a given transaction is finalized on the L1, the Polygon transaction may be considered final. State root checkpoints occur roughly every 30 minutes.

Provable finality

Delayed finality examples: Ethereum PoS (Casper FFG), Polkadot (GRANDPA), Solana
Instant Finality Examples: Cosmos, Celestia, Algorand, Aptos

Systems using provable finality make special considerations for finality to ensure it happens more quickly and with better economic assurances than most probabilistically final chain constructions.

There are two types of provable finality: chains with instantly provable finality, and chains with delayed provable finality.

Chains with instant finality don’t need special finality considerations by off-chain applications. All blocks published by the network are immediately provably final by definition.

Chains with delayed finality have separate consensus mechanisms for newly produced vs. finalized blocks. These chains usually have superior liveness properties compared to instant finality chains, but at the cost of added complexity, vulnerability to re-orgs, and more complex integration considerations for off-chain applications.

Figure 6: A delayed-finality chain. Blocks to the right of the finality boundary may be re-orged and should not be indexed by exchanges or bridges.

Double-spend attacks on delayed finality chains

Historically, most blockchains haven’t had provable finality, so bridges, exchanges, and other off-chain applications would use a block delay for measuring the finality of any new chains they integrate with.

However, for chains with provable delayed finality, there are situations where the finality mechanism may stall or fail, as occurred in the May 2023 incident where Ethereum’s finality gadget, Casper FFG, stalled. When finality mechanisms fail, the chain may continue to produce blocks, creating long strings of unfinalized blocks that may be reorged by a bug or an attacker.

During the Ethereum incident, the chain’s finality mechanism was stalled by nine epochs—the equivalent of 139 blocks’ worth of confirmations (after controlling for missed slot proposals). At this time, most bridges/centralized exchanges used a block-delay rule to determine the finality of a transaction on Ethereum, with delays ranging from 14 blocks to 100 blocks.

Had the Ethereum finality incident been orchestrated by an attacker, the attacker may have been able to perform double-spend attacks against these bridges/exchanges by orchestrating exceedingly long re-orgs.

Checking for finality

For delayed-finality chains, as illustrated in the previous example, block delays are not an adequate way to “wait” for blocks to become final. Instead, applications must query the chain’s RPC for the exact finality condition to ensure the block being indexed is actually final.

Ethereum proof-of-stake

The Ethereum JSON RPC defines a “default block” parameter for various endpoints that should be set to “finalized” to query the most recent finalized block. To obtain the most recent finalized block, use eth_getBlockByNumber(“finalized”, ...). This parameter may be used for other endpoints, such as eth_call, eth_getBalance, and eth_getLogs.

Polkadot

Call chain.getFinalizedHead() to get the block hash of the latest finalized block, then use chain.getBlock() to get the block associated with the hash.

Solana

Use the getBlocks() RPC method with the commitment level set as finalized.

When provable finality lies

One major caveat of provable finality/proof-of-stake systems is they have no way to provide strong subjectivity guarantees. A blockchain’s subjectivity refers to whether a node syncing from genesis will always arrive at the same chain head and whether an attacker can manipulate the end state of the syncing node.

In proof-of-work blockchains, the cost of creating an alternate chain for partially synced nodes to follow is equal to all of the work performed by miners from genesis to the canonical chain head, making any subjectivity attack impractical against proof-of-work networks.

However, in proof-of-stake networks, the cost of creating an alternate chain has only one requirement with an unknown, and possibly zero cost: the private keys of the chain’s historical validators. The keys for historical validators may be acquired by a number of means; private keys may be leaked or brute-forced, or validators who no longer use their keys may offer them up for sale.

This re-use of old validator keys creates the possibility for long-range sync attacks, in which a newly synced node may behave as though a specific transaction is submitted and finalized when in reality, it was never submitted to the canonical chain in the first place.

To protect against long-range sync attacks, operations teams should always begin node sync from weak subjectivity checkpoints. These checkpoints are essentially used as genesis blocks, providing a trusted starting point for nodes to sync from. Weak subjectivity checkpoints may be acquired from already-synced nodes or via social processes.

The special case of L2s

Examples: Arbitrum, Optimism, StarkNet, Scroll, ZKSync, Polygon zkEVM

L2 networks are unique in that they don’t have consensus mechanisms in the way a normal blockchain does. In a normal blockchain, the validator set must come to a consensus on the output of a state transition function. In an L2 network, it is the underlying L1 network that is responsible for verifying the state transition function. Ultimately, this means the finality condition for an L2 network is dependent on the finality condition of the underlying L1.

When an L2 sequencer or prover receives a transaction, it sequences/generates a proof for the transaction, then returns an L2 transaction receipt. Once the sequencer/prover has received enough transactions, it assembles the transactions into a batch that is submitted to the L1 network.

Figure 7: The flow of a user’s transaction on an L2 network. Notably, sequencers/provers provide users with transaction receipts far in advance of the transaction’s inclusion or finality on the L1.

For ZK-Rollups, the batch contains a proof representing the execution of every transaction in the batch. The L1 contract verifies the proof, and once the batch transaction is final, all of the L2 transactions included in the proof are final as well.

For Optimistic Rollups, the batch contains the calldata for every transaction in the batch. The L1 contract does not run any state transition function or verification that the calldata is valid. Instead, Optimistic Rollups use a challenge mechanism to allow L2 nodes to contest an L1 batch. This means a transaction submitted to an Optimistic Rollup may be considered final only once it’s been included in a batch on the L1, the batch and its parents are valid, and the L1 transaction is final.

Checking for finality

To determine the finality of an L2 transaction, one must verify that the commitment/proof transaction has both been included on and finalized by the L1. L2 providers often offer convenient RPC methods that off-chain integrators can use to determine the finality of a given L2 transaction.

Arbitrum Nitro/Optimism

Both Arbitrum and Optimism nodes implement the Ethereum JSON RPC, including the “finalized” block parameter. As a result, eth_getBlockByNumber(“finalized”, ...) can be used to determine finality.

StarkNet

StarkNet’s sequencer provider has a getTransactionStatus() function that reports the transaction’s status in the StarkNet transaction lifecycle. Transactions whose tx_status is ACCEPTED_ON_L1 may be considered final.

ZkSync Classic

ZkSync’s v0.2 API has several endpoints that accept finalization parameters.

• /accounts/{accountIdOrAddress}/{stateType} may have the stateType set to finalized.
• /blocks/{blockNumber} accepts lastFinalized as the blockNumber parameter.
• /blocks/{blockNumber}/transactions{?from,limit,direction} accepts lastFinalized as the blockNumber parameter.

Practicing safe finality

Like other recent innovations in the blockchain space, provable finality has drastically changed the kinds of security assurances a blockchain can provide. However, developers of off-chain or multi-chain applications must be cognizant of the specific finality requirements of different architectures and, where necessary, use the correct techniques to determine whether transactions are final.

Older techniques of determining finality, such as block delays, are not adequate for newer architectures, and using incorrect finality criteria may put applications at risk of double-spend attacks.

If you’re designing a new blockchain or off-chain application and have concerns about finality, please contact us.

By Artem Dinaburg

Trail of Bits has developed a suite of open-source libraries designed to streamline the creation and deployment of eBPF applications. These libraries facilitate efficient process and network event monitoring, function tracing, kernel debug symbol parsing, and eBPF code generation.

Previously, deploying portable, dependency-free eBPF applications posed significant challenges due to Linux kernel version disparities and the need for external tools for C-to-eBPF bytecode translation. We’ve addressed these issues with our innovative libraries, which use the latest eBPF and Linux kernel features to reduce external dependencies. These tools, ideal for creating on-machine agents and enabling cloud-native monitoring, are actively maintained and compatible with a variety of Linux distributions and kernel releases. Some are even integral to the functionality of osquery, the renowned endpoint visibility framework.

Our eBPF libraries

The libraries in this suite are linuxevents, ebpfpub, btfparse, and ebpf-common. Together they can be used to develop streamlined event monitoring with a high degree of accuracy and efficiency. Their applications range from network event monitoring, function tracing, and kernel debug symbol parsing to assisting in generating and using eBPF code.

linuxevents: A container-aware library for process monitoring with no runtime dependencies

The linuxevents library showcases how eBPF can monitor events without requiring accurate kernel headers or other external dependencies. No more shipping kernel headers, multiple copies of precompiled eBPF bytecode, or dependencies on BCC! The linuxevents library supports runtime code generation to create custom probes at runtime, not just during build. It is also much faster than traditional system-call-based hooking, an essential feature when monitoring events from multiple containers on a single machine. How does linuxevents do this?

First, linuxevents uses the Linux kernel’s BTF debugging data (via our btfparse library) to accurately identify function prototypes and kernel data structures. This allows linuxevents to automatically adjust to variances in data structure layout and to hook arbitrary non-public symbols in a way that greatly simplifies tracing.

This approach is faster than traditional system call based hooking not only because it has to hook fewer things (sched_process_exec vs execve, execveat, etc.) but also because it can avoid expensive correlations. For example, to trace which program on disk is executed via execve, one would normally have to correlate a file descriptor passed to execve with an open call and multiple chdir calls to get the full path of a program. The correlation is computationally expensive, especially on a machine with multiple active containers. The linuxevents library uses an accurate kernel data structure representation to hook just one function and simply extract the path from the kernel’s vfs layer.

A recording of the linuxevents library being used as a part of the execsnoop example that comes with the library

The linuxevents library is still a proof of concept; it is in use by osquery as a toggleable experiment. The library also has a canonical example of tracing executed processes with cross-container visibility.

ebpfpub: A function-tracing library for Linux

The ebpfpub library allows for monitoring system calls across multiple Linux kernel versions while relying on minimal external runtime dependencies. In ebpfpub, eBPF probes are autogenerated from function prototypes defined via a simple custom language, which can be created from tracepoint descriptors. This approach required proper headers for the running kernel and it came with performance penalties, such as the need to match file descriptors with system calls.

Depending on the desired target event, ebpfpub can use either kernel tracepoints, kprobes, or uprobes as the underlying tracing mechanism. The library includes the following examples:

• execsnoop: Shows how to use Linux kernel tracepoints to detect program execution via execve()
• kprobe_execsnoop: Like execsnoop, but uses a different hooking mechanism (kprobes instead of tracepoints)
• readline_trace: Uses uprobes to hook the user-mode readline library, which can enable use cases such as monitoring whenever a live shell is used on a machine
• sockevents: An example of how to trace sockets through a series of connect/accept/bind calls that establish connectivity to a remote machine
• systemd_resolved: Shows how to use uprobes to hook into systemd’s DNS service (systemd-resolved), which will show in real time the domains being looked up by your local machine

The ebpfpub library is currently used by osquery to capture process and socket events by tracing executed system calls. While ebpfpub is still maintained and useful in specific circumstances (like the need to support older kernels and use runtime code generation), new projects should use the linuxevents approach instead.

btfparse: A C++ library that parses kernel debug symbols in BTF format

BTF, or the Binary Type Format, is a compact binary format for representing type information in the Linux kernel. BTF stores data such as structures, unions, enumerations, and typedefs. Debuggers and other tools can use BTF data to enable richer debugging features by understanding complex C types and expressions. BTF was introduced in Linux 4.20 and is generated from source code and traditional debugging information like DWARF. BTF is more compact than DWARF, and it improves the debugging experience by conveying more semantic type information than was previously available. The standardized BTF format also allows new debugging tools to leverage type data across compilers, enabling more consistent quality of introspection across languages.

The btfparse library allows you to read BTF data in your C++ projects and generate header files directly in memory without any external application. The library also comes with a tool, called btf-dump, that serves both as an example of using btfparse and as a standalone tool that can dump BTF data present in a Linux kernel image.

ebpf-common: A C++ library to help write new eBPF-based tools

The ebpf-common library is a set of utilities that assist with generating, loading, and using eBPF code. It is the common substrate that underpins all of our eBPF-related tooling. Use epbf-common to create your own runtime, eBPF-based tools!

The ebpf-common library’s main job is to compile C code to eBPF bytecode and to provide helpful abstractions that make writing eBPF hooks easier. Here are some of the features ebpf-common provides:

• It uses LLVM and clang as libraries that write to in-memory scratch buffers.
• It includes abstractions to make accessing eBPF data structures (hash maps, arrays, ring buffers, etc.) simple. These data structures are used to exchange data between eBPF and your application.
• It includes abstractions to create and read perf outputs, another way eBPF can communicate with the tracing application.
• It allows for the management of events (like kprobes, uprobes, and tracepoints) that trigger the execution of eBPF programs.
• Finally, it includes functions that implement eBPF helpers and related functionality via LLVM.

The ebpf-common library is used as the core of all of our other eBPF tools, which serve as library clients and examples of use cases for ebpf-common for your applications. Refer to our blog post All your tracing are belong to BPF for additional guidance and examples for how to use ebpf-common.

Our eBPF tools

ebpfault: A Linux system call fault injector built on top of eBPF

ebpfault is a system-wide fault injector that does not require risky kernel drivers that could crash the system. It can start a specific program, target running processes, or target all processes except those on a specific list. A simple configuration file in JSON format lets you configure faults by using the syscall name, the probability of injecting a fault, and the error code that should be returned.

A recording of ebpfault running against the htop process and causing faults via a specific configuration

BPF deep-dives and talks

Most of the material available online is geared toward using the command-line sample tools that demonstrate eBPF, which work mostly as standalone demonstrations and not as reusable libraries. We wanted to fill in the gaps for developers and provide a step-by-step guide on how to actually integrate eBPF from scratch from the point of view of a developer writing a tracing tool. The documentation focuses on runtime code generation using the LLVM libraries.

The All your tracing belong to BPF blog post and our companion code guide show how to use epbf-common to create a tool that uses eBPF to count system calls, with each example increasing in complexity, starting from simple counting, to using maps to store data, to finally using perf events for outputs.

Monitoring Linux events is a talk by Alessandro Gario about using eBPF for event monitoring. Alessandro describes how to dynamically decide on what to monitor and to generate your own eBPF bytecode directly from C++. He touches on some of the intricacies of eBPF maps, perf events, and practical considerations for using our eBPF tools and libraries.

eBPF public contributions

The world of eBPF continues to expand and find applications in various domains. We have explored eBPF as it relates to interesting tasks beyond tracing and performance monitoring, such as improving CI/CD for eBPF bytecode, writing an eBPF-to-ARM64 JIT compiler for the Solana platform, and improving the experience of building eBPF projects on Windows.

ebpf-verifier: Sometimes it is necessary to bundle prebuilt eBPF programs. The Linux kernel “verifies” eBPF programs at load time and rejects any that it deems unsafe. Bundling eBPF bytecode is a CI/CD nightmare because every kernel’s verification is ever so slightly different. ebpf-verifier aims to eliminate that nightmare by executing the eBPF verifier outside of the running kernel and opens the door to the possibility of testing eBPF programs across different kernel versions.

Solana eBPF-to-ARM64 JIT compiler: eBPF makes an appearance in many surprising places! The Solana blockchain uses an eBPF virtual machine to run its smart contracts, and it uses a JIT compiler to compile the eBPF bytecode to native architectures. Trail of Bits ported the Solana eBPF JIT compiler to ARM64 to allow Solana applications to natively run on the now very popular ARM64 platforms like Apple Silicon.

Adding CMake support to eBPF for Windows: eBPF also works on Windows! To make Windows development easier, we ported the prior Visual Studio–based build system to CMake. The improvements include better handling of transitive dependencies and properties, better packaging, and enhanced build settings for a more efficient development experience.

Conclusion

We’ve used eBPF to provide rapid, high-quality monitoring data for system instrumentation agents like osquery. Our intention is that the frameworks and tools we’ve created will assist developers in integrating eBPF into their applications more seamlessly. eBPF is a useful technology with a bright future in a variety of fields, including increasingly in cloud-native monitoring and observation.

We plan to share more of our lessons learned from eBPF tool development in the near future, and we hope to apply some of these lessons to the problems of cloud-native monitoring and observability.