diff --git a/build/binary_tarball/BUILD.bazel b/build/binary_tarball/BUILD.bazel
new file mode 100644
index 0000000..567c572
--- /dev/null
+++ b/build/binary_tarball/BUILD.bazel
@@ -0,0 +1,18 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_binary", "go_library")
+
+go_library(
+    name = "binary_tarball_lib",
+    srcs = ["main.go"],
+    importpath = "source.monogon.dev/build/binary_tarball",
+    visibility = ["//visibility:private"],
+    deps = [
+        "//build/binary_tarball/spec",
+        "@org_golang_google_protobuf//encoding/prototext",
+    ],
+)
+
+go_binary(
+    name = "binary_tarball",
+    embed = [":binary_tarball_lib"],
+    visibility = ["//visibility:public"],
+)
diff --git a/build/binary_tarball/def.bzl b/build/binary_tarball/def.bzl
new file mode 100644
index 0000000..c3dbf85
--- /dev/null
+++ b/build/binary_tarball/def.bzl
@@ -0,0 +1,67 @@
+#  Copyright 2020 The Monogon Project Authors.
+#
+#  SPDX-License-Identifier: Apache-2.0
+#
+#  Licensed under the Apache License, Version 2.0 (the "License");
+#  you may not use this file except in compliance with the License.
+#  You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+#  Unless required by applicable law or agreed to in writing, software
+#  distributed under the License is distributed on an "AS IS" BASIS,
+#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#  See the License for the specific language governing permissions and
+#  limitations under the License.
+
+def _binary_tarball_impl(ctx):
+    layer_spec = ctx.actions.declare_file(ctx.label.name + ".prototxt")
+    executable = ctx.attr.executable[DefaultInfo].files_to_run.executable
+    runfiles = ctx.attr.executable[DefaultInfo].default_runfiles
+    files = []
+    for file in runfiles.files.to_list():
+        layer_path = file.short_path
+
+        # Weird shenanigans with external repos
+        if layer_path.startswith("../"):
+            layer_path = "external/" + layer_path[3:]
+        files.append(struct(
+            path = layer_path,
+            src = file.path,
+        ))
+    ctx.actions.write(layer_spec, proto.encode_text(struct(file = files)))
+
+    layer_out = ctx.actions.declare_file(ctx.label.name + ".tar")
+    ctx.actions.run(
+        outputs = [layer_out],
+        inputs = [layer_spec, executable] + runfiles.files.to_list(),
+        tools = [ctx.executable._container_binary],
+        executable = ctx.executable._container_binary,
+        arguments = ["-out", layer_out.path, "-spec", layer_spec.path],
+    )
+
+    return [DefaultInfo(files = depset([layer_out]), runfiles = ctx.runfiles(files = [layer_out]))]
+
+binary_tarball = rule(
+    implementation = _binary_tarball_impl,
+    doc = """
+        Build a tarball from a binary given in `executable` and its runfiles. Everything will be put under
+        /app with the same filesystem layout as if run under `bazel run`. So if your executable works under bazel run,
+        it will work when packaged with this rule with the exception of runfile manifests, which this rule currently
+        doesn't support.
+    """,
+    attrs = {
+        "executable": attr.label(
+            mandatory = True,
+            executable = True,
+            allow_single_file = True,
+            cfg = "target",
+        ),
+        "_container_binary": attr.label(
+            default = Label("//build/binary_tarball"),
+            cfg = "exec",
+            executable = True,
+            allow_files = True,
+        ),
+    },
+)
diff --git a/build/binary_tarball/main.go b/build/binary_tarball/main.go
new file mode 100644
index 0000000..88f4cc3
--- /dev/null
+++ b/build/binary_tarball/main.go
@@ -0,0 +1,83 @@
+// Copyright The Monogon Project Authors.
+// SPDX-License-Identifier: Apache-2.0
+
+package main
+
+import (
+	"archive/tar"
+	"flag"
+	"io"
+	"log"
+	"os"
+	"path"
+	"strings"
+
+	"google.golang.org/protobuf/encoding/prototext"
+
+	"source.monogon.dev/build/binary_tarball/spec"
+)
+
+var (
+	specPath = flag.String("spec", "", "Path to the layer specification (spec.Spec)")
+	outPath  = flag.String("out", "", "Output file path")
+)
+
+func main() {
+	flag.Parse()
+	var spec spec.Spec
+	specRaw, err := os.ReadFile(*specPath)
+	if err != nil {
+		log.Fatalf("failed to open spec file: %v", err)
+	}
+	if err := prototext.Unmarshal(specRaw, &spec); err != nil {
+		log.Fatalf("failed to unmarshal spec: %v", err)
+	}
+	outFile, err := os.Create(*outPath)
+	if err != nil {
+		log.Fatalf("failed to open output: %v", err)
+	}
+	defer outFile.Close()
+	outTar := tar.NewWriter(outFile)
+	defer outTar.Close()
+	createdDirs := make(map[string]bool)
+	for _, file := range spec.File {
+		srcFile, err := os.Open(file.Src)
+		if err != nil {
+			log.Fatalf("failed to open input file: %v", err)
+		}
+		info, err := srcFile.Stat()
+		if err != nil {
+			log.Fatalf("cannot stat input file: %v", err)
+		}
+		var mode int64 = 0644
+		if info.Mode()&0111 != 0 {
+			mode = 0755
+		}
+		targetPath := path.Join("app", file.Path)
+		targetDirParts := strings.Split(path.Dir(targetPath), "/")
+		var partialDir string
+		for _, part := range targetDirParts {
+			partialDir = path.Join(partialDir, part)
+			if !createdDirs[partialDir] {
+				if err := outTar.WriteHeader(&tar.Header{
+					Typeflag: tar.TypeDir,
+					Name:     partialDir,
+					Mode:     0755,
+				}); err != nil {
+					log.Fatalf("failed to write directory: %v", err)
+				}
+				createdDirs[partialDir] = true
+			}
+		}
+		if err := outTar.WriteHeader(&tar.Header{
+			Name: targetPath,
+			Size: info.Size(),
+			Mode: mode,
+		}); err != nil {
+			log.Fatalf("failed to write header: %v", err)
+		}
+		if _, err := io.Copy(outTar, srcFile); err != nil {
+			log.Fatalf("failed to copy file into tar: %v", err)
+		}
+	}
+}
diff --git a/build/binary_tarball/spec/BUILD.bazel b/build/binary_tarball/spec/BUILD.bazel
new file mode 100644
index 0000000..bd02812
--- /dev/null
+++ b/build/binary_tarball/spec/BUILD.bazel
@@ -0,0 +1,36 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library")
+load("@io_bazel_rules_go//proto:def.bzl", "go_proto_library")
+load("@rules_proto//proto:defs.bzl", "proto_library")
+load("@rules_proto_grpc_buf//:defs.bzl", "buf_proto_lint_test")
+
+buf_proto_lint_test(
+    name = "spec_proto_lint_test",
+    except_rules = [
+        "PACKAGE_VERSION_SUFFIX",
+    ],
+    protos = [":spec_proto"],
+    use_rules = [
+        "DEFAULT",
+        "COMMENTS",
+    ],
+)
+
+proto_library(
+    name = "spec_proto",
+    srcs = ["spec.proto"],
+    visibility = ["//visibility:public"],
+)
+
+go_proto_library(
+    name = "spec_go_proto",
+    importpath = "source.monogon.dev/build/binary_tarball/spec",
+    proto = ":spec_proto",
+    visibility = ["//visibility:public"],
+)
+
+go_library(
+    name = "spec",
+    embed = [":spec_go_proto"],
+    importpath = "source.monogon.dev/build/binary_tarball/spec",
+    visibility = ["//visibility:public"],
+)
diff --git a/build/binary_tarball/spec/gomod-generated-placeholder.go b/build/binary_tarball/spec/gomod-generated-placeholder.go
new file mode 100644
index 0000000..ca2145c
--- /dev/null
+++ b/build/binary_tarball/spec/gomod-generated-placeholder.go
@@ -0,0 +1,4 @@
+// Copyright The Monogon Project Authors.
+// SPDX-License-Identifier: Apache-2.0
+
+package spec
diff --git a/build/binary_tarball/spec/spec.proto b/build/binary_tarball/spec/spec.proto
new file mode 100644
index 0000000..1e2e17e
--- /dev/null
+++ b/build/binary_tarball/spec/spec.proto
@@ -0,0 +1,32 @@
+// Copyright 2020 The Monogon Project Authors.
+//
+// SPDX-License-Identifier: Apache-2.0
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+syntax = "proto3";
+
+package build.binary_tarball.spec;
+
+// Spec is a spec of what goes into a binary_tarball
+message Spec {
+  repeated File file = 1;
+}
+
+// File is a single file in the tarball
+message File {
+  // src contains the path of the file on the build host
+  string src = 1;
+  // path contains the path in the tarball
+  string path = 2;
+}