Ariadne's Space

QEMU is primarily known as the software which provides full system emulation under Linux’s KVM.  Also, it can be used without KVM to do full emulation of machines from the hardware level up.  Finally, there is qemu-user, which allows for emulation of individual programs.  That’s what this blog post is about.

The main use case for qemu-user is actually not reverse-engineering, but simply running programs for one CPU architecture on another.  For example, Alpine developers leverage qemu-user when they use dabuild(1) to cross-compile Alpine packages for other architectures: qemu-user is used to run the configure scripts, test suites and so on.  For those purposes, qemu-user works quite well: we are even considering using it to build the entire riscv64 architecture in the 3.15 release.

However, most people don’t realize that you can run a qemu-user emulator which targets the same architecture as the host.  After all, that would be a little weird, right?  Most also don’t know that you can control the emulator using gdb, which is possible and allows you to debug binaries which detect if they are being debugged.

You don’t need gdb for this to be a powerful reverse engineering tool, however.  The emulator itself includes many powerful tracing features.  Lets look into them by writing and compiling a sample program, that does some recursion by calculating whether a number is even or odd inefficiently:

#include <stdbool.h> 
#include <stdio.h> 

bool isOdd(int x); 
bool isEven(int x); 

bool isOdd(int x) { 
   return x != 0 && isEven(x - 1); 
} 

bool isEven(int x) { 
   return x == 0 || isOdd(x - 1); 
} 

int main(void) { 
   printf("isEven(%d): %d\n", 1025, isEven(1025)); 
   return 0; 
}

Compile this program with gcc, by doing gcc -ggdb3 -Os example.c -o example.

The next step is to install the qemu-user emulator for your architecture, in this case we want the qemu-x86_64 package:

$ doas apk add qemu-x86_64
(1/1) Installing qemu-x86_64 (6.0.0-r1)
$

Normally, you would also want to install the qemu-openrc package and start the qemu-binfmt service to allow for the emulator to handle any program that couldn’t be run natively, but that doesn’t matter here as we will be running the emulator directly.

The first thing we will do is check to make sure the emulator can run our sample program at all:

$ qemu-x86_64 ./example 
isEven(1025): 0

Alright, all seems to be well.  Before we jump into using gdb with the emulator, lets play around a bit with the tracing features.  Normally when reverse engineering a program, it is common to use tracing programs like strace.  These tracing programs are quite useful, but they suffer from a design flaw: they use ptrace(2) to accomplish the tracing, which can be detected by the program being traced.  However, we can use qemu-user to do the tracing in a way that is transparent to the program being analyzed:

$ qemu-x86_64 -d strace ./example 
22525 arch_prctl(4098,274903714632,136818691500777464,274903714112,274903132960,465) = 0 
22525 set_tid_address(274903715728,274903714632,136818691500777464,274903714112,0,465) = 22525 
22525 brk(NULL) = 0x0000004000005000 
22525 brk(0x0000004000007000) = 0x0000004000007000 
22525 mmap(0x0000004000005000,4096,PROT_NONE,MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED,-1,0) = 0x0000004000005000 
22525 mprotect(0x0000004001899000,4096,PROT_READ) = 0 
22525 mprotect(0x0000004000003000,4096,PROT_READ) = 0 
22525 ioctl(1,TIOCGWINSZ,0x00000040018052b8) = 0 ({55,236,0,0}) 
isEven(1025): 0 
22525 writev(1,0x4001805250,0x2) = 16 
22525 exit_group(0)

But we can do even more.  For example, we can learn how a CPU would hypothetically break a program down into translation buffers full of micro-ops (these are TCG micro-ops but real CPUs are similar enough to gain a general understanding of the concept):

$ qemu-x86_64 -d op ./example
OP: 
ld_i32 tmp11,env,$0xfffffffffffffff0 
brcond_i32 tmp11,$0x0,lt,$L0 

---- 000000400185eafb 0000000000000000 
discard cc_dst 
discard cc_src 
discard cc_src2 
discard cc_op 
mov_i64 tmp0,$0x0 
mov_i64 rbp,tmp0 

---- 000000400185eafe 0000000000000031 
mov_i64 tmp0,rsp 
mov_i64 rdi,tmp0 

---- 000000400185eb01 0000000000000031 
mov_i64 tmp2,$0x4001899dc0 
mov_i64 rsi,tmp2 

---- 000000400185eb08 0000000000000031 
mov_i64 tmp1,$0xfffffffffffffff0 
mov_i64 tmp0,rsp 
and_i64 tmp0,tmp0,tmp1 
mov_i64 rsp,tmp0 
mov_i64 cc_dst,tmp0 

---- 000000400185eb0c 0000000000000019 
mov_i64 tmp0,$0x400185eb11 
sub_i64 tmp2,rsp,$0x8 
qemu_st_i64 tmp0,tmp2,leq,0 
mov_i64 rsp,tmp2 
mov_i32 cc_op,$0x19 
goto_tb $0x0 
mov_i64 tmp3,$0x400185eb11 
st_i64 tmp3,env,$0x80 
exit_tb $0x7f72ebafc040 
set_label $L0 
exit_tb $0x7f72ebafc043
[...]

If you want to trace the actual CPU registers for every instruction executed, that’s possible too:

$ qemu-x86_64 -d cpu ./example
RAX=0000000000000000 RBX=0000000000000000 RCX=0000000000000000 RDX=0000000000000000 
RSI=0000000000000000 RDI=0000000000000000 RBP=0000000000000000 RSP=0000004001805690 
R8 =0000000000000000 R9 =0000000000000000 R10=0000000000000000 R11=0000000000000000 
R12=0000000000000000 R13=0000000000000000 R14=0000000000000000 R15=0000000000000000 
RIP=000000400185eafb RFL=00000202 [-------] CPL=3 II=0 A20=1 SMM=0 HLT=0 
ES =0000 0000000000000000 00000000 00000000 
CS =0033 0000000000000000 ffffffff 00effb00 DPL=3 CS64 [-RA] 
SS =002b 0000000000000000 ffffffff 00cff300 DPL=3 DS   [-WA] 
DS =0000 0000000000000000 00000000 00000000 
FS =0000 0000000000000000 00000000 00000000 
GS =0000 0000000000000000 00000000 00000000 
LDT=0000 0000000000000000 0000ffff 00008200 DPL=0 LDT 
TR =0000 0000000000000000 0000ffff 00008b00 DPL=0 TSS64-busy 
GDT=     000000400189f000 0000007f 
IDT=     000000400189e000 000001ff 
CR0=80010001 CR2=0000000000000000 CR3=0000000000000000 CR4=00000220 
DR0=0000000000000000 DR1=0000000000000000 DR2=0000000000000000 DR3=0000000000000000 
DR6=00000000ffff0ff0 DR7=0000000000000400 
CCS=0000000000000000 CCD=0000000000000000 CCO=EFLAGS 
EFER=0000000000000500
[...]

You can also trace with disassembly for each translation buffer generated:

$ qemu-x86_64 -d in_asm ./example
---------------- 
IN:  
0x000000400185eafb:  xor    %rbp,%rbp 
0x000000400185eafe:  mov    %rsp,%rdi 
0x000000400185eb01:  lea    0x3b2b8(%rip),%rsi        # 0x4001899dc0 
0x000000400185eb08:  and    $0xfffffffffffffff0,%rsp 
0x000000400185eb0c:  callq  0x400185eb11 

---------------- 
IN:  
0x000000400185eb11:  sub    $0x190,%rsp 
0x000000400185eb18:  mov    (%rdi),%eax 
0x000000400185eb1a:  mov    %rdi,%r8 
0x000000400185eb1d:  inc    %eax 
0x000000400185eb1f:  cltq    
0x000000400185eb21:  mov    0x8(%r8,%rax,8),%rcx 
0x000000400185eb26:  mov    %rax,%rdx 
0x000000400185eb29:  inc    %rax 
0x000000400185eb2c:  test   %rcx,%rcx 
0x000000400185eb2f:  jne    0x400185eb21
[...]

All of these options, and more, can also be stacked.  For more ideas, look at qemu-x86_64 -d help.  Now, lets talk about using this with gdb using qemu-user’s gdbserver functionality, which allows for gdb to control a remote machine.

To start a program under gdbserver mode, we use the -g argument with a port number.  For example, qemu-x86_64 -g 1234 ./example will start our example program with a gdbserver listening on port 1234.  We can then connect to that gdbserver with gdb:

$ gdb ./example
[...]
Reading symbols from ./example... 
(gdb) target remote localhost:1234 
Remote debugging using localhost:1234 
0x000000400185eafb in ?? ()
(gdb) br isEven 
Breakpoint 1 at 0x4000001233: file example.c, line 12.
(gdb) c 
Continuing. 

Breakpoint 1, isEven (x=1025) at example.c:12 
12          return x == 0 || isOdd(x - 1);
(gdb) bt full 
#0  isEven (x=1025) at example.c:12 
No locals. 
#1  0x0000004000001269 in main () at example.c:16 
No locals.

All of this is happening without any knowledge or cooperation of the program.  As far as its concerned, its running as normal, there is no ptrace or any other weirdness.

However, this is not 100% perfect: a program could be clever and run the cpuid instruction and check for GenuineIntel or AuthenticAMD and crash out if it doesn’t see that it is running on a legitimate CPU.  Thankfully, qemu-user has the ability to spoof CPUs with the -cpu option.

If you find yourself needing to spoof the CPU, you’ll probably have the best results with a simple CPU type like -cpu Opteron_G1-v1 or similar.  That CPU type spoofs an Opteron 240 processor, which was one of the first x86_64 CPUs on the market.  You can get a full list of CPUs supported by your copy of the qemu-user emulator by doing qemu-x86_64 -cpu help.

There’s a lot more qemu-user emulation can do to help with reverse engineering, for some ideas, look at qemu-x86_64 -h or similar.

You have probably seen this post on Twitter by now:

God I wish there was an easier way to do this pic.twitter.com/8UrBNKdTRW

— Kat Maddox (@ctrlshifti) July 30, 2020

But actually, the way most people test whether a number is even is wrong.  It’s not your fault, computers think differently than we do.  And in most cases, the compiler fixes your mistake for you.  But it’s been a long day of talking about Alpine governance, so I thought I would have some fun.

However, a quick note: for these examples, I am using ML, specifically the OCaml dialect of it.  Translating these expressions to your language however should not be difficult, and I will provide C-like syntax for the right answer below too.

Using the modulus operator and bitwise math

The usual way people test whether a number is even is the way they teach you in grade school: x mod 2 == 0.  In a C-like language, this would be represented as x % 2 == 0.  However, this is actually quite slow, as the div instruction is quite expensive on most CPUs.

There is a much faster way to check if a number is even or odd, but to understand why it is faster, we should discuss some number theory first.  Whether a number is even or odd ultimately comes down to a single number: 1.

There are two numbers in the entire universe that have the property that they are the same number in any number system we use today: 0 is always zero, and 1 is always one.  This holds true for binary (base 2), octal (base 8), decimal (base 10), and hexadecimal (base 16).

Accordingly, we can use binary logic to test whether a number is even or not by testing whether it ends in 1 when represented as binary.  But many programmers probably don’t actually know how to do this — it doesn’t usually come up when you’re writing a web app, after all.

The answer is to use logical and: x land 1 == 0 (or in C, x & 1 == 0).  We can prove that both expressions are functionally equivalent, by defining both testing functions and testing for the same output:

# let evenMod x = x mod 2 == 0;; 
val evenMod : int -> bool = <fun> 
# let evenAnd x = x land 1 == 0;; 
val evenAnd : int -> bool = <fun> 
# let evenMatches x = evenMod(x) == evenAnd(x);; 
val evenMatches : int -> bool = <fun>
# evenMatches(0);; 
- : bool = true 
# evenMatches(1);; 
- : bool = true 
# evenMatches(2);; 
- : bool = true 
# evenMatches(3);; 
- : bool = true

As you can see, both are equivalent.  And to be clear, this is the right way to test whether an integer is even.  The other ways below are intended to be a joke.  Also, most compilers will optimize x mod 2 == 0 to x land 1 == 0.

Using functional programming

The nice thing about math is that there’s always one way to prove something, especially when there’s more than one way.  Modulus operator?  Bitwise logic?  Please.  We’re going to solve this problem the way Alonzo Church intended.  But to do that, we need to think about what actually makes a number even.  The answer is simple, of course: an even number is one which is not odd.  But what is an odd number?  Well, one that isn’t even of course.

But can we really apply this circular logic to code?  Of course we can!

# let rec isEven x =  
   x = 0 || isOdd (x - 1) 
 and isOdd x = 
   x <> 0 && isEven (x - 1);; 
val isEven : int -> bool = <fun> 
val isOdd : int -> bool = <fun>
# isEven(0);; 
- : bool = true 
# isEven(1);; 
- : bool = false 
# isEven(2);; 
- : bool = true 
# isEven(3);; 
- : bool = false

As you can see, we’ve succeeded in proving that an even number is clearly not odd!

Using pattern matching

In 1962, Bell Labs invented pattern matching, as part of the SNOBOL language.  Pattern matching has become a popular programming language feature, being implemented in not just SNOBOL, but also Erlang, Elixir, Haskell, ML, Rust and many more.  But can we use it to determine if a number is even or odd?  Absolutely.

# let rec isEven x = 
    match x with 
      | 0 -> true 
      | 1 -> false 
      | 2 -> true 
      | x -> isEven(x - 2);; 
val isEven : int -> bool = <fun>
# isEven(0);; 
- : bool = true 
# isEven(1);; 
- : bool = false 
# isEven(2);; 
- : bool = true 
# isEven(3);; 
- : bool = false 
# isEven(4);; 
- : bool = true 
# isEven(5);; 
- : bool = false

As you can see, we have demonstrated many ways to test if a number is even or not.  Some are better than others, but others are more amusing.

Alpine as you may know uses the apk-tools package manager, which we built because pre-existing package managers did not meet the design requirements needed to build Alpine.  But what makes it different, and why does that matter?

apk add and apk del manipulate the desired state

In traditional package managers like dnf and apt, requesting the installation or removal of packages causes those packages to be directly installed or removed, after a consistency check.

In apk, when you do apk add foo or apk del bar, it adds foo or bar as a dependency constraint in /etc/apk/world which describes the desired system state.  Package installation or removal is done as a side effect of modifying this system state.  It is also possible to edit /etc/apk/world with the text editor of your choice and then use apk fix to synchronize the installed packages with the desired system state.

Because of this design, you can also add conflicts to the desired system state.  For example, we recently had a bug in Alpine where pipewire-pulse was preferred over pulseaudio due to having a simpler dependency graph.  This was not a problem though, because users could simply add a conflict against pipewire-pulse by doing apk add !pipewire-pulse.

Another result of this design is that apk will never commit a change to the system that leaves it unbootable.  If it cannot verify the correctness of the requested change, it will back out adding the constraint before attempting to change what packages are actually installed on the system.  This allows our dependency solver to be rigid: there is no way to override or defeat the solver other than providing a scenario that results in a valid solution.

Verification and unpacking is done in parallel to package fetching

Unlike other package managers, when installing or upgrading packages, apk is completely driven by the package fetching I/O.  When the package data is fetched, it is verified and unpacked on the fly.  This allows package installations and upgrades to be extremely fast.

To make this safe, package contents are initially unpacked to temporary files and then atomically renamed once the verification steps are complete and the package is ready to be committed to disk.

apk does not use a particularly advanced solver

Lately, traditional package managers have bragged about having advanced SAT solvers for resolving complicated constraint issues automatically.  For example, aptitude is capable of solving sudoku puzzles.  apk is definitely not capable of that, and I consider that a feature.

While it is true that apk does have a deductive dependency solver, it does not perform backtracking.  The solver is also constrained: it is not allowed to make changes to the /etc/apk/world file.  This ensures that the solver cannot propose a solution that will leave your system in an inconsistent state.

Personally, I think that trying to make a smart solver instead of appropriately constraining the problem is a poor design choice.  I believe the fact that apt, aptitude and dnf have all written code to constrain their SAT solvers in various ways proves this point.

To conclude, package managers can be made to go fast, and be safe while doing it, but require a careful design that is well-constrained.  apk makes its own tradeoffs: a less powerful but easy to audit solver, trickier parallel execution instead of phase-based execution.  These were the right decisions for us, but may not be the right decisions for other distributions.

Starting this past month, thanks to the generous support of Google and the Linux Foundation, instead of working on the usual Alpine-related consulting work that I do, I’ve had the privilege of working on various initiatives in Alpine relating to security that we’ve needed to tackle for a long time.  Some things are purely technical, others involve formulating policy, planning and recruiting volunteers to help with the security effort.

For example, my work to replace poorly maintained software with better replacements is a purely technical security-related effort, while building a security response team has social aspects as well as designing and building tools for the team to use.  Our security issue tracker has gone live and is presently being tested by the community, and with that work we’re already off to a great start at an organized security response.

If you didn’t know what Alpine Linux is already, it is a popular Linux system with over a billion installations on Docker alone.  By building on efficient building blocks, such as the musl C library and busybox, Alpine maintains a slim installation image size while also providing the conveniences of a general-purpose Linux distribution.  As a result, Alpine has been deployed as the base of many Docker images, has been ported to hundreds of devices as the basis of postmarketOS, has been used to build hundreds of appliances with LinuxKit and has been deployed everywhere from 5G networks to solar farms and oil rigs thanks to the work done by Zededa with Project EVE.  With all of this growth in the few years, it’s important to rethink a lot of things in the distribution including our approach to security.

Why having a security team matters

You might be wondering why distributions need a dedicated security team.  The answer is simple: having a dedicated security team helps to ensure that issues are fixed more quickly, and that the dissemination of security fix information is consistent.  The lack of consistent security fix information has been one of the major concerns for some potential users when evaluating Alpine for their projects, so improving upon this with a proper security team will hopefully assuage those concerns.

The other main benefit to having a dedicated security team is that the team can be a helpful resource for maintainers who need help figuring out how to fix their packages.  Sometimes figuring out which commits need to be backported in order to fix a vulnerability is tricky, because upstreams do not necessarily disclose what commits fix a problem.  Having more eyeballs that can be pinged to look at an issue is helpful here.

How Alpine has historically done security response

In the past, an anonymous user working under a pseudonym reported vulnerabilities to package maintainers by hand as she learned about them.  While this has worked out fairly well for us in the past, this has understandably not scaled very well as Alpine’s package count has grown.  Although the security tracker is not yet integrated into Gitlab, it will soon provide a familiar experience for anyone who has worked issues reported by the anonymous contributor.

Imagine my surprise when I found out that the account opening issues against packages with security vulnerabilities was not a bot, but instead an actual person doing the work by hand!  Needless to say, in 2021, it is time to come up with a better system, which is why I am working on starting an actual security team, and building tools for the security team to use like the security tracker.

Future directions for security-related work in Alpine

One of the main initiatives I have been working on the past few months has been getting Rust on all of Alpine’s release architectures.  At the moment, we are still missing s390x, mips64 and riscv64 (under consideration as a release architecture beginning with 3.15).  While I was not able to complete this work in the 3.14 release cycle, we have established a great working relationship with the Rust team, and have been working on detangling the musl port in Rust.  Once the musl port is detangled in Rust, it will be trivial to bring up support on new architectures we add in the future (such as loongarch, for example), and bootstrap.sh can already build a Rust cross compiler for the targets we support today.

Another initiative is replacing poorly maintained software with modern replacements.  I have a lot of plans in this area, for example, replacing GNU gettext with gettext-tiny, which will make container images smaller and allow Alpine to use musl’s native gettext routines which are considerably more robust than GNU libintl.  Similarly, I am looking into replacing GNU ncurses with netbsd’s implementation for the same reasons.  I am also planning to refactor apk-tools’ cryptographic code to allow using BearSSL as a backend instead of OpenSSL’s libcrypto.

We also want to harden Alpine’s supply chain from supply-chain attacks.  This work is largely going to be focused on two areas: integrating support into abuild for verifying signatures on downloaded source code and rebooting the reproducible builds effort.  The things we need to do to support reproducible builds however is a blog post in and of itself, so that will be coming soon as we are able to move onto working on that.

Getting involved

If working on these kinds of problems interests you, I’d love to get you on board and working on these initiatives.  Feel free to ping me in IRC, or ping me in Alpine’s gitlab.  There is a literal mountain of security-related work to be done in Alpine, so the possibilities are basically endless.

Also, if you work for a company that is interested in funding work on Alpine, there are many initiatives that could be more quickly implemented with funding, such as Laurent Bercot’s planned OpenRC replacement.

Yesterday, Dermot Bradley brought up in IRC that gettext-tiny’s lack of an envsubst utility could be a potential problem, as many Alpine users use it to generate configuration from templates.  So I decided to look into writing a replacement, as the tool did not seem that complex.  That rewrite is now available on GitHub, and is already in Alpine testing for experimental use.

What envsubst does

The envsubst utility is designed to take a set of strings as input and replace variables in them, in the same way that shells do variable substitution.  Additionally, the variables that will be substituted can be restricted to a defined set, which is nice for reliability purposes.

Because it provides a simple way to perform substitutions in a file without having to mess with sed and other similar utilities, it is seen as a helpful tool for building configuration files from templates: you just install the cmd:envsubst provider with apk and perform the substitutions.

Unfortunately though, GNU envsubst is quite deficient in terms of functionality and interface.

Good tool design is important

When building a tool like envsubst, it is important to think about how it will be used.  One of the things that is really important is making sure a tool is satisfying to use: a tool which has non-obvious behavior or implies functionality that is not actually there is a badly designed tool.  Sadly, while sussing out a list of requirements for my replacement envsubst tool, I found that GNU envsubst has several deficiencies that are quite disappointing.

GNU envsubst does not actually implement POSIX variable substitution like a shell would

In POSIX, variable substitution is more than simply replacing a variable with the value it is defined to.  In GNU envsubst, the documentation speaks of shell variables, and then outlines the $FOO and ${FOO} formats for representing those variables.  The latter format implies that POSIX variable substitution is supported, but it’s not.

In a POSIX-conformant shell, you can do:

% FOO="abc_123"
% echo ${FOO%_*}
abc

Unfortunately, this isn’t supported by GNU envsubst:

% FOO="abc_123" envsubst
$FOO
abc_123
${FOO}
abc_123
${FOO%_*}
${FOO%_*}

It’s not yet supported by my implementation either, but it’s on the list of things to do.

Defining a restricted set of environment variables is bizzare

GNU envsubst describes taking an optional [SHELL-FORMAT] parameter.  The way this feature is implemented is truly bizzare, as seen below:

% envsubst -h
Usage: envsubst [OPTION] [SHELL-FORMAT]
...
Operation mode:
  -v, --variables             output the variables occurring in SHELL-FORMAT
...
% FOO="abc123" BAR="xyz456" envsubst FOO
$FOO
$FOO
% FOO="abc123" envsubst -v FOO
% FOO="abc123" envsubst -v \$FOO
FOO
% FOO="abc123" BAR="xyz456" envsubst \$FOO
$FOO
abc123
$BAR
$BAR
% FOO="abc123" BAR="xyz456" envsubst \$FOO \$BAR
envsubst: too many arguments
% FOO="abc123" BAR="xyz456" envsubst \$FOO,\$BAR
$FOO
abc123
$BAR
xyz456
$BAZ
$BAZ
% envsubst -v
envsubst: missing arguments
%

As discussed above, [SHELL-FORMAT] is a very strange thing to call this, because it is not really a shell variable substitution format at all.

Then there’s the matter of requiring variable names to be provided in this shell-like variable format.  That requirement gives a shell script author the ability to easily break their script by accident, for example:

% echo 'Your home directory is $HOME' | envsubst $HOME
Your home directory is $HOME

Because you forgot to escape $HOME as \$HOME, the substitution list was empty:

% echo 'Your home directory is $HOME' | envsubst \$HOME 
Your home directory is /home/kaniini

The correct way to handle this would be to accept HOME without having to describe it as a variable.  That approach is supported by my implementation:

% echo 'Your home directory is $HOME' | ~/.local/bin/envsubst HOME 
Your home directory is /home/kaniini

Then there’s the matter of not supporting multiple variables in the traditional UNIX style (as separate tokens).  Being forced to use a comma on top of using a variable sigil for this is just bizzare and makes the tool absolutely unpleasant to use with this feature.  For example, this is how you’re supposed to add two variables to the substitution list in GNU envsubst:

% echo 'User $USER with home directory $HOME' | envsubst \$USER,\$HOME 
User kaniini with home directory /home/kaniini

While my implementation supports doing it that way, it also supports the more natural UNIX way:

% echo 'User $USER with home directory $HOME' | ~/.local/bin/envsubst USER HOME 
User kaniini with home directory /home/kaniini

This is common with GNU software

This isn’t just about GNU envsubst.  A lot of other GNU software is equally broken.  Even the GNU C library has design deficiencies which are similarly frustrating.  The reason why I wish to replace GNU software in Alpine is because in many cases, it is defective by design.  Whether the design defects are caused by apathy, or they’re caused by politics, it doesn’t matter.  The end result is the same, we get defective software.  I want better security and better reliability, which means we need better tools.

We can talk about the FSF political issue, and many are debating that at length.  But the larger picture is that the tools made by the GNU project are, for the most part, clunky and unpleasant to use.  That’s the real issue that needs solving.

When you think of a configuration-defined image builder, most likely you think of Docker (which builds images for containers).  But before Docker, there were several other projects, all of which came out of a vibrant community of Debian-using sysadmins looking for better ways to build VM and container images, which lead to a series of projects that built off each other to build something better.

Before KVM, there was Xen

The Xen hypervisor is likely something you’ve heard of, and that’s where this story begins.  The mainstream desire to programmatically create OS images came about as Xen became a popular hypervisor in the mid 2000s.  The first development in that regard was xen-tools, which automated installation of Debian, Ubuntu and CentOS guests, by generating images for them using custom perl scripts.  The world has largely moved on from Xen, but it still sees wide use.

ApplianceKit and ApplianceKit-NG

The methods used in xen-tools, while generally effective, lacked flexibility.  Hosting providers needed a way to allow end-users to customize the images they deployed.  In my case, we solved this by creating ApplianceKit.  That particular venture was sold to another hosting company, and for whatever reason, I started another one.  In that venture, we created ApplianceKit-NG.

ApplianceKit and ApplianceKit-NG took different approaches internally to solve a basic problem, taking an XML description of a software image and reproducing it, for example:

<?xml version="1.0" standalone="yes"?>
<appliance>
  <description>LAMP appliance based on Debian squeeze</description>
  <author>
    <name>Ariadne Conill</name>
    <email>ariadne@dereferenced.org</email>
  </author>
  <distribution>squeeze</distribution>
  <packagelist>
    <package>apache2</package>
    <package>libapache2-mod-php5</package>
    <package>mysql-server</package>
    <package>mysql-client</package>
  </packagelist>
</appliance>

As you can see here, the XML description described a desired state for the image to be in at deployment time.  ApplianceKit did this through an actor model: different modules would act on elements in the configuration description.  ApplianceKit-NG instead treated this as a matter of compilation: first, a high-level pass converted the XML into a mid-level IR, then the mid-level IR was converted into a low-level IR, then the IR was converted into a series of commands that were evaluated like a shell script.  (Had I known about skarnet’s execline at that time, I would have used it.)

Docker

Another company that was active in the Debian community and experimenting with configuration-defined image building was dotCloud.  dotCloud took a similar evolutionary path, with the final image building system they made being Docker.  Docker evolved further on the concept outlined in ApplianceKit-NG by simplifying everything: instead of explicitly configuring a desired state, you simply use image layering:

FROM debian:squeeze
MAINTAINER ariadne@dereferenced.org
RUN apt-get update && apt-get install apache2 libapache2-mod-php5 mysql-server mysql-client

By taking a simpler approach, Docker has won out.  Everything is built on top of Docker these days, such as Kubernetes, and this is a good thing.  Even though some projects like Packer have further advanced the state of the art, Docker remains the go-to for this task, simply because its simple enough for people to mostly understand.

The main takeaway is that simply advancing the state of the art is not good enough to make a project compelling.  It must advance the state of simplicity too.

I’ve followed cryptocurrency for a long time.  The first concept I read about was Hashcash, which was a mechanism designed to reduce e-mail spam by acting as a sort of “stamp”.  The proof of work concept introduced by Hashcash of course lead to Bitcoin, which lead to Ethereum and the other popular Proof of Work consensus blockchain-based cryptocurrency platforms out in the world today.  In fact, in the very early days of Bitcoin I mined around 50k BTC total, and well, looking at the price of Bitcoin today, obviously I wish I had hung on to them.  With that said, I think Proof of Work consensus is a massively inefficient way to solve the problem of decentralized finance.  Hopefully this essay convinces you of that too.

Basic Concepts

Before we dive into the technical details of how these schemes work, I think it is important to discuss the basic concepts: there are unfortunately a lot of cryptocurrency advocates who fundamentally do not understand the technology.  I believe that if you are going to invest in an investment vehicle that you should be fully literate in the concepts used to build that investment vehicle.  If you disagree want want to just trade assets that you don’t understand, fine — but this blog will probably not be that helpful to you.

Most decentralized finance platforms, like Bitcoin and Ethereum, are built on top of a shared blockchain.  In technical terms, a blockchain is an append-only binary log that is content-addressable.  Content address-ability is achieved because the blockchain is composed in such a way that it acts as a merkle tree, which is a type of acyclic graph where each node has a distinct identity (derived from a hash function).  These nodes are grouped into blocks, which contain pointers to each element of the graph.  When the blocks in the append-only log are replayed, you can reconstruct the entire tree.  A good analogy for a blockchain would therefore be the ledger your bank uses to track all of its transactions, or the abstract for your house.  However, the use of a blockchain is not required to have a functional decentralized finance system, it is just a common optimization used to provide assayability.

An asset is considered assayable if a party can ascertain its value.  For example, I can assay the value of an options contract by examining the strike price and quantity of shares it covers.  You can assay the value of your purse or wallet by putting currency in only a purse or wallet you trust.  Blockchains are used in many decentralized finance systems to provide assayability: anybody can examine the contents of any purse to determine the value of that purse by walking through the transactions that purse has been involved in.

An asset is considered fungible if we can transfer it to others in exchange for goods and services.  For example, currency is a fungible asset: you exchange currency for goods and services.  However, the asset itself may hold direct value, or its value may simply be symbolic.  Currency that is itself made from precious metal, such as a gold coin, would be considered fungible, but not symbolic.  Paper money such as bank notes are considered both fungible and symbolic.  Cryptographic assets are available in both forms, depending on how they are underwritten.

A smart contract is a program which also acts as a financial instrument.  Most people erroneously believe smart contracts were an invention of Ethereum, but in reality, Mark S. Miller’s seminal work on the topic dates all the way back to 2000.  Bitcoin and other tokens like Ethereum and its subtokens are all the results of various forms of smart contract.  Other forms of smart contracts also exist such as NFTs.

The Current State of the World

At present, there are two main decentralized finance systems that most people have heard something about: Bitcoin and Ethereum.  These are proof of work consensus blockchains, meaning that participant nodes have to solve a cryptographic puzzle (the work) in order to gain authorization (the proof) to append a block to the chain.  Participants are rewarded for appending blocks to the chain by the program which maintains the chain.

As more participants join the network, contention over who is allowed to append to the chain increases.  This is reflected by the difficulty factor, which controls the complexity of the work needed for a cryptographic proof to be accepted as authorization to append a new block to the chain.

The benefit to this design is that it keeps the rate that blocks are appended to the chain at a mostly stable pace, which is desirable in systems where transactions are validated by their depth in the blockchain, as it allows for participants to estimate how long it will take for their transaction to be validated to the level they deem appropriate (e.g. a confirmation that the transaction is N blocks deep in the blockchain will take X minutes to obtain).

However, because these platforms reward appending new blocks to the chain with non-trivial amounts of currency, the competition over rights to append to these blockchains is increasing exponentially: the estimated energy consumption from Bitcoin mining now rivals that of Western Europe.  This obviously isn’t sustainable.

Proof of Stake Could Be A Solution

A different kind of blockchain governance model has emerged in recent history: proof of stake.  These platforms work by choosing a random stakeholder who meets the staking criteria to have rights to append the next block to the blockchain.  This mostly works well, but a lot of these blockchains still have other inefficiency problems, for example the staking requirements can effectively centralize authority in who can perform the appends if it is biased by size each stakeholder holds.

Proof of Stake, however, does get rid of traditional block mining and the energy consumption associated with it.  But these blockchains are still inefficient, because many of them store unnecessary data, which leads to slower lookups of data stored in the blockchain and slower tree building when the log is replayed.

There are many ways a proof of stake based platform can be optimized, including to not require a blockchain at all.  But even in a system where the basic functionality of the network does not require a blockchain, they can still be helpful as an optimization.

Ethereum 2.0 is an example of a credible proof of stake based platform that is still heavily tied to a blockchain.

Smart Contracts as Distributed Object Capabilities

Building on Mark S Miller’s seminal work on smart contracts, we can describe a decentralized finance system as a set of distributed object capabilities.  We will assume a PKI-based cryptographic system as the foundation of the network, such as djb’s Curve25519.  We also assume the presence of a distributed hash table running on participant nodes, such as Kademlia.

Each participant will have one or more keypairs which act as locators in the DHT, which act as pointers to opaque capabilities.  An opaque capability may itself be a contract or a validation proof generated by execution of a contract.

In order to keep participants honest, the network will choose other participants to act as validators.  These validators, when given a proof, will themselves re-execute the underlying contract with the inputs from the proof and validate that the output is the same.  If it is, they will sign the proof and give it back to the party which requested validation.

Given this architecture, lets consider a very simple purse for a token that exists on the network:

struct Purse {
    address_t m_owner;
    int64_t m_tokens;

    Purse(address_t p, int64_t t) : m_owner(p), m_tokens(t) {}

    pair<Purse> sendToAddress(address_t recipient, int64_t tokens) {
        if (tokens >= m_tokens)
            raise NotEnoughMoneyException();

        m_tokens -= tokens;
        return (Purse(m_owner, m_tokens), Purse(recipient, tokens));
    }

    Purse combineFromPurse(Purse p) {
        if (p.m_owner != m_owner)
            raise NotOwnerException();

        Purse newPurse = Purse(m_owner, m_tokens + p.m_tokens);
        m_tokens = p.m_tokens = 0;

        return newPurse;
    }
};

Given this library, we can write a smart contract which mints a purse for a given address with 100 initial tokens, and returns it as the output:

import Purse;

auto Contract::main(address_t owner) -> Purse {
    return Purse(owner, 100);
}

Given the output of this contract, we can send our friend some of our tokens:

import Purse;

auto Contract::main(Purse originalPurse,
                    address_t target, int64_t tokens) -> pair<Purse> {
    auto [ourNewPurse, theirPurse] =
        originalPurse.sendToAddress(target, tokens);
    return (ourNewPurse, theirPurse);
}

Now that we have minted a purse for our friend using some of our own tokens, we simply sign the output of that smart contract and send the message to our friend:

import SendToFriendContract;
import Purse;
import Message;
import Wallet;

auto Contract::main(address_t target, int64_t tokens) -> Message {
    // Get our wallet.
    auto wallet = Wallet.getOurWallet();

    // Get our purses from the wallet.
    auto ourPurses = Wallet.assetsFromIssuingContract(Purse);

    // Mint the new purse for our friend.
    auto [ourPurse, theirPurse] =
        SendToFriendContract(ourPurses[0], target, tokens);

    // Commit our purse to the top of the purse list in our wallet.
    wallet.prependAsset(ourPurse);

    // Seal the result of our execution in an opaque message.
    auto message =
        Message(wallet.address, target,
                [ourPurses[0], target, tokens],
                SendToFriendContract,
                [ourPurse, theirPurse]);

    return message;
}

When our friend receives the message, they can request its validation by forwarding it along to a validator:

import Message;
import ValidationContract;

auto Contract::main(Message input) -> Message {
    return ValidationContract(input);
}

The validator then can respond with a message confirming or denying the validity.  The validated message’s purse would then be used as an input for future transactions.

Note that I have yet to discuss a blockchain here.  In this case, a blockchain is useful for storing pointers to validations, which is helpful because it simplifies the need to maintain assayability by not needing to forward along a chain of previous validations as proof of custodianship.

While what I have outlined is a vast simplification of what is going on, there is a decentralized finance platform that operates like this: it’s name is Tezos and it operates basically under this principle.

Using Tezos is extremely efficient: compiling a smart contract on Tezos uses the same energy as compiling any other program of the same complexity.  Tezos is also capable of supporting sharding in the future should it become necessary, though the blockchain part itself is simply an optimization of how the network operates and Tezos could be adapted to operate without it.

Ultimately, I think if we are going to have decentralized finance, Tezos is the future, not Bitcoin and Ethereum.  But we can still do even better than Tezos.  Maybe I will write about that later.

Update (April 27): Please visit Laurent’s website on this issue for a more detailed proposal.  If you work at a company which has budget for this, please get in touch with him directly.

As many of you already know, Alpine presently uses an fairly modified version of OpenRC as its service manager.  Unfortunately, OpenRC maintenance has stagnated: the last release was over a year ago.

We feel now is a good time to start working on a replacement service manager based on user feedback and design discussions we’ve had over the past few years which can be simply summarized as systemd done right.  But what does systemd done right mean?

Our plan is to build a supervision-first service manager that consumes and reacts to events, using declarative unit files similar to systemd, so that administrators who are familiar with systemd can easily learn the new system.  In order to build this system, we plan to work with Laurent Bercot, a globally recognized domain expert on process supervision systems and author of the s6 software supervision suite.

This work will also build on the work we’ve done with ifupdown-ng, as ifupdown-ng will be able to reflect its own state into the service manager allowing it to start services or stop them as the network state changes.  OpenRC does not support reacting to arbitrary events, which is why this functionality is not yet available.

Corporate funding of this effort would have meaningful impact on the timeline that this work can be delivered in.  It really comes down to giving Laurent the ability to work on this full time until it is done.  If he can do that, like Lennart was able to, he should be able to build the basic system in a few months.

Users outside the Alpine ecosystem will also benefit from this work.  Our plan is to introduce a true contender to systemd that is completely competitive as a service manager.  If you believe real competition to systemd will be beneficial toward driving innovation in systemd, you should also want to sponsor this work.

Alpine has gotten a lot of mileage out of OpenRC, and we are open to contributing to its future maintenance while Alpine releases still include it as part of the base system, but our long-term goal is to adopt the s6-based solution.

If you’re interested in sponsoring Laurent’s work on this project, you can contact him via e-mail or via his Twitter account.

Earlier today, I was invited to sign the open letter calling for the FSF board to resign, which I did.  To me, it was obvious to sign the letter, which on it’s own makes a compelling argument for why RMS should not be an executive director at FSF.

But I believe there is an even more compelling reason.

When we started Alpine 15 years ago, we largely copied the way other distributions handled things… and so Alpine copied the problems that many other FOSS projects had as well.  Reviews were harsh and lacking empathy, which caused problems with contributor burnout.  During this time, Alpine had some marginal amount of success, Docker did eventually standardize on Alpine as platform of choice for micro-containers and postmarketOS was launched.

Due to burnout, I turned in my commit privileges, resigned from the core team and wound up taking a sabbatical from the project for almost a year.

In the time I was taking a break from Alpine, an amazing thing happened: the core team decided to change the way things were done in the project.  Instead of giving harsh reviews as the bigger projects did, the project pivoted towards a philosophy of collaborative kindness.  And as a result, burnout issues went away, and we started attracting all sorts of new talent.

Robert Hansen resigned as the GnuPG FAQ maintainer today.  In his message, he advocates that we should demand kindness from our leaders, and he’s right, it gets better results.  Alpine would not be the success it is today had we not decided to change the way the project was managed.  I want that level of success for FOSS as a whole.

Unfortunately, it is proven again and again that RMS is not capable of being kind.

He screams at interns when they do not do work to his exact specification (unfortunately, FSF staff are forced to sign an NDA that covers almost every minutia of their experience being an FSF staffer so this is not easy to corroborate).

He shows up on e-mail lists and overrides the decisions made by his subordinates, despite those decisions having strong community consensus.

He is a wholly ineffective leader, and his continued leadership will ultimately be harmful to FSF.

And so, that is why I signed the letter demanding his resignation yet again.