Repository: chainguard-dev/apko
Pull request #1610 (2025-04-10 14:08:45)

Do not retry with jitter when discoveringKeys in offline mode.
Addresses: https://github.com/chainguard-dev/apko/issues/1330

Apko in offline mode was attempting to fetch keys... The code in case of
offline mode was doing a shortcut to check whether a file exists.
But the code was wrapped in a retryable http wrapper that introduced ~(4 x 30s) jitter
into the process.

In this PR -> in offline mode -> we turn off the retries around the fetch.
This way -> if file exists in the cache -> we use it.
If it doesn't - we accept it. And most likely we will use key provided explicitly using --extra_keys flag.


After fix the process finishes instantly: 
```
apko % go run . build --offline ../../container-images/bazel/gcbi/baseimages/static_glibc.apko.yaml foo /tmp
2025/04/10 15:44:18 WARN ignoring missing keys for https://{redacted}/artifactory/development-apk.cgr.dev-virtual: failed to perform key discovery: Get "https://{redacted}/artifactory/development-apk.cgr.dev-virtual/apk-configuration": failed to read "/Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory/development-apk.cgr.dev-virtual/apk-configuration" in offline cache: open /Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory/development-apk.cgr.dev-virtual/apk-configuration: no such file or directory
2025/04/10 15:44:18 WARN ignoring missing keys for https://{redacted}/artifactory/development-wolfi-virtual/os: failed to perform key discovery: Get "https://{redacted}/artifactory/development-wolfi-virtual/os/apk-configuration": failed to read "/Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory%2Fdevelopment-wolfi-virtual/os/apk-configuration" in offline cache: open /Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory%2Fdevelopment-wolfi-virtual/os/apk-configuration: no such file or directory
Error: locking config: initializing apk: failed to initialize apk keyring: failed to fetch apk key: Get "https://{redacted}/artifactory/api/security/keypair/public/repositories/development-alpine-virtual": listing "/Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory%2Fapi%2Fsecurity%2Fkeypair%2Fpublic/repositories" for offline cache: open /Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory%2Fapi%2Fsecurity%2Fkeypair%2Fpublic/repositories: no such file or directory
2025/04/10 15:44:18 INFO error during command execution: locking config: initializing apk: failed to initialize apk keyring: failed to fetch apk key: Get "https://{redacted}/artifactory/api/security/keypair/public/repositories/development-alpine-virtual": listing "/Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory%2Fapi%2Fsecurity%2Fkeypair%2Fpublic/repositories" for offline cache: open /Users/{redacted}/Library/Caches/dev.chainguard.go-apk/https%3A%2F%2F{redacted}%2Fartifactory%2Fapi%2Fsecurity%2Fkeypair%2Fpublic/repositories: no such file or directory
exit status 1
```


Patch:
diff --git a/README.md b/README.md
index c777832..b81bf90 100644
--- a/README.md
+++ b/README.md
@@ -56,7 +56,7 @@ entrypoint:
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 ```
 We can build this with apko from any environment with apk tooling:
 
diff --git a/docs/apko_file.md b/docs/apko_file.md
index 58c7f9e..555e735 100644
--- a/docs/apko_file.md
+++ b/docs/apko_file.md
@@ -21,7 +21,7 @@ entrypoint:
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 ```
 
 Running `apko build` on this file will produce a tar file containing an Alpine base container image.
@@ -68,7 +68,7 @@ accounts:
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 
 # optional path mutations
 paths:
diff --git a/docs/build-process.md b/docs/build-process.md
index 045a6d5..ce6b0ce 100644
--- a/docs/build-process.md
+++ b/docs/build-process.md
@@ -32,7 +32,6 @@ As described above, after everything is setup, the actual build occurs inside th
 The build is in [`build.Context.BuildLayer()`](../pkg/build/build.go#L80-109), which consists of:
 
 1. `Context.BuildImage()`: building the image
-1. `Context.BuildTarball()`: build the tarball for the layer
 1. `Context.GenerateSBOM()` optionally generate the SBoM
 
 The actual building of the image via `BuildImage()` just wraps [`buildImage()`](../pkg/build/build_implementation.go#L195-247).
diff --git a/examples/alpine-base-rootless.yaml b/examples/alpine-base-rootless.yaml
index 31a56de..0aa3e64 100644
--- a/examples/alpine-base-rootless.yaml
+++ b/examples/alpine-base-rootless.yaml
@@ -17,7 +17,7 @@ cmd: /bin/sh -l
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 
 archs:
   - amd64
diff --git a/examples/alpine-base.yaml b/examples/alpine-base.yaml
index 7e230ef..d34e0ee 100644
--- a/examples/alpine-base.yaml
+++ b/examples/alpine-base.yaml
@@ -8,7 +8,7 @@ cmd: /bin/sh -l
   
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 
 archs:
   - amd64
diff --git a/examples/alpine-python3.yaml b/examples/alpine-python3.yaml
index de03b62..5caaeff 100644
--- a/examples/alpine-python3.yaml
+++ b/examples/alpine-python3.yaml
@@ -9,7 +9,7 @@ cmd: /bin/sh -l
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 
 archs:
   - amd64
diff --git a/examples/alpine-slim.yaml b/examples/alpine-slim.yaml
index 0e2a5c0..9392dd3 100644
--- a/examples/alpine-slim.yaml
+++ b/examples/alpine-slim.yaml
@@ -8,7 +8,7 @@ contents:
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 
 cmd: /bin/sh -l
 
diff --git a/examples/nginx-rootless.yaml b/examples/nginx-rootless.yaml
index 5bf125d..639e112 100644
--- a/examples/nginx-rootless.yaml
+++ b/examples/nginx-rootless.yaml
@@ -21,7 +21,7 @@ accounts:
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 
 # optional path mutations
 paths:
diff --git a/examples/nginx.yaml b/examples/nginx.yaml
index cf19619..cd79256 100644
--- a/examples/nginx.yaml
+++ b/examples/nginx.yaml
@@ -14,7 +14,7 @@ entrypoint:
 
 # optional environment configuration
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin
 
 # optional user mutations
 accounts:
diff --git a/examples/wolfi-go.yaml b/examples/wolfi-go.yaml
index 544689e..f62b773 100644
--- a/examples/wolfi-go.yaml
+++ b/examples/wolfi-go.yaml
@@ -9,7 +9,7 @@ contents:
     - go
 
 environment:
-  PATH: /usr/sbin:/sbin:/usr/bin:/bin:/root/go/bin
+  PATH: /usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin:/root/go/bin
 
 archs:
 - x86_64
diff --git a/pkg/apk/README.md b/pkg/apk/README.md
index 0c25206..03c62fc 100644
--- a/pkg/apk/README.md
+++ b/pkg/apk/README.md
@@ -9,7 +9,6 @@ Also includes supporting utilities for working with filesystems, including:
 read-write, chmod/chown, devices, and symlinks capabilities
 * an implementation of that FS in memory, i.e. a memfs
 * an implementation of that FS on top of a directory, which uses the memfs for features the underlying disk does not support
-* tarball features
 
 Documentation is available at [https://pkg.go.dev/chainguard.dev/apko/pkg/apk](https://pkg.go.dev/chainguard.dev/apko/pkg/apk).
 
@@ -59,11 +58,6 @@ It also provides two implementations of that interface:
 * `memfs` is an in-memory implementation of `FullFS`. It is fully functional, but remember that it uses memory, so loading very large files into it will hit limits.
 * `rwosfs` is an on-disk implementation of `FullFS`. It is fully functional, including capabilities that may not exist on the underlying filesystem, like symlinks, devices, chown/chmod and case-sensitivity. The metadata for every file on disk also is in-memory, enabling those additional capabilities. Contents are not stored in memory.
 
-### Tarball
-
-`chainguard.dev/apko/pkg/apk/tarball` provides a utility to write an [fs.FS](https://pkg.go.dev/io/fs#FS) to a tarball. It is implemented on a `tarball.Context`, which lets
-you provide overrides for timestamps, UID/GID, and other features.
-
 ### apk
 
 `chainguard.dev/apko/pkg/apk/apk` is the heart of this library. It provides a native go
diff --git a/pkg/apk/apk/cache.go b/pkg/apk/apk/cache.go
index 59c415b..ab6a183 100644
--- a/pkg/apk/apk/cache.go
+++ b/pkg/apk/apk/cache.go
@@ -431,6 +431,13 @@ func (t *cacheTransport) retrieveAndSaveFile(ctx context.Context, request *http.
 	if err != nil {
 		return "", fmt.Errorf("unable to create a temporary cache file: %w", err)
 	}
+	// Now that symlinks are used to advertise cached files,
+	// CreateTemp permissions are no longer suitable default,
+	// update to world readable, group/user writable.
+	err = tmp.Chmod(os.FileMode(0664))
+	if err != nil {
+		return "", fmt.Errorf("unable to chmod temporary cache file: %w", err)
+	}
 	if err := func() error {
 		defer tmp.Close()
 		defer resp.Body.Close()
diff --git a/pkg/apk/apk/implementation.go b/pkg/apk/apk/implementation.go
index 763fc68..f795227 100644
--- a/pkg/apk/apk/implementation.go
+++ b/pkg/apk/apk/implementation.go
@@ -581,7 +581,7 @@ func (a *APK) ResolveAndCalculateWorld(ctx context.Context) ([]*APKResolved, err
 }
 
 // FixateWorld force apk's resolver to re-resolve the requested dependencies in /etc/apk/world.
-func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error {
+func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) ([]*Package, error) {
 	log := clog.FromContext(ctx)
 	/*
 		equivalent of: "apk fix --arch arch --root root"
@@ -598,7 +598,7 @@ func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error
 	// 1. Get the apkIndexes for each repository for the target arch
 	allpkgs, conflicts, err := a.ResolveWorld(ctx)
 	if err != nil {
-		return fmt.Errorf("error getting package dependencies: %w", err)
+		return nil, fmt.Errorf("error getting package dependencies: %w", err)
 	}
 
 	// 3. For each name on the list:
@@ -611,10 +611,10 @@ func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error
 	for _, pkg := range conflicts {
 		isInstalled, err := a.isInstalledPackage(pkg)
 		if err != nil {
-			return fmt.Errorf("error checking if package %s is installed: %w", pkg, err)
+			return nil, fmt.Errorf("error checking if package %s is installed: %w", pkg, err)
 		}
 		if isInstalled {
-			return fmt.Errorf("cannot install due to conflict with %s", pkg)
+			return nil, fmt.Errorf("cannot install due to conflict with %s", pkg)
 		}
 	}
 	// Cast []*RepositoryPackage into []InstallablePackage.
@@ -626,7 +626,7 @@ func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error
 	return a.InstallPackages(ctx, sourceDateEpoch, allInstPkgs)
 }
 
-func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, allpkgs []InstallablePackage) error {
+func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, allpkgs []InstallablePackage) ([]*Package, error) {
 	// TODO: Consider making this configurable option.
 	jobs := runtime.GOMAXPROCS(0)
 
@@ -710,7 +710,7 @@ func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, a
 	}
 
 	if err := g.Wait(); err != nil {
-		return fmt.Errorf("installing packages: %w", withCause(ctx, err))
+		return nil, fmt.Errorf("installing packages: %w", withCause(ctx, err))
 	}
 
 	// update the installed file
@@ -737,11 +737,11 @@ func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, a
 		})
 
 		if err := a.AddInstalledPackage(pkg, files); err != nil {
-			return fmt.Errorf("unable to update installed file for pkg %s: %w", pkg.Name, err)
+			return nil, fmt.Errorf("unable to update installed file for pkg %s: %w", pkg.Name, err)
 		}
 	}
 
-	return nil
+	return infos, nil
 }
 
 type NoKeysFoundError struct {
@@ -850,10 +850,7 @@ func DiscoverKeys(ctx context.Context, client *http.Client, auth auth.Authentica
 		return nil, err
 	}
 
-	rc := retryablehttp.NewClient()
-	rc.HTTPClient = client
-	rc.Logger = clog.FromContext(ctx)
-	discoveryResponse, err := rc.StandardClient().Do(discoveryRequest)
+	discoveryResponse, err := client.Do(discoveryRequest)
 	if err != nil {
 		return nil, fmt.Errorf("failed to perform key discovery: %w", err)
 	}
@@ -934,6 +931,13 @@ func (a *APK) DiscoverKeys(ctx context.Context, repository string) ([]Key, error
 	if a.cache != nil {
 		client = a.cache.client(client, false)
 
+		if !a.cache.offline {
+			rc := retryablehttp.NewClient()
+			rc.HTTPClient = client
+			rc.Logger = clog.FromContext(ctx)
+			client = rc.StandardClient()
+		}
+
 		return a.cache.shared.discoverKeys.Do(repository, func() ([]Key, error) {
 			return DiscoverKeys(ctx, client, a.auth, repository)
 		})
@@ -1211,7 +1215,7 @@ func expandPackage(ctx context.Context, a *APK, pkg InstallablePackage) (*expand
 	return a.cachePackage(ctx, pkg, exp, cacheDir)
 }
 
-func packageAsURI(pkg InstallablePackage) (uri.URI, error) {
+func packageAsURI(pkg LocatablePackage) (uri.URI, error) {
 	u := pkg.URL()
 
 	if strings.HasPrefix(u, "https://") || strings.HasPrefix(u, "http://") {
@@ -1221,7 +1225,7 @@ func packageAsURI(pkg InstallablePackage) (uri.URI, error) {
 	return uri.New(u), nil
 }
 
-func packageAsURL(pkg InstallablePackage) (*url.URL, error) {
+func packageAsURL(pkg LocatablePackage) (*url.URL, error) {
 	asURI, err := packageAsURI(pkg)
 	if err != nil {
 		return nil, err
@@ -1230,7 +1234,7 @@ func packageAsURL(pkg InstallablePackage) (*url.URL, error) {
 	return url.Parse(string(asURI))
 }
 
-func (a *APK) FetchPackage(ctx context.Context, pkg InstallablePackage) (io.ReadCloser, error) {
+func (a *APK) FetchPackage(ctx context.Context, pkg FetchablePackage) (io.ReadCloser, error) {
 	log := clog.FromContext(ctx)
 	log.Debugf("fetching %s", pkg)
 
diff --git a/pkg/apk/apk/package.go b/pkg/apk/apk/package.go
index 99251f6..2603958 100644
--- a/pkg/apk/apk/package.go
+++ b/pkg/apk/apk/package.go
@@ -60,6 +60,40 @@ func PackageToInstalled(pkg *Package) (out []string) {
 	return
 }
 
+// LocatablePackage represents a minimal set of information needed to locate a
+// package for retrieval over a network.
+type LocatablePackage interface {
+	URL() string
+}
+
+// FetchablePackage represents a minimal set of information needed to fetch a package.
+type FetchablePackage interface {
+	URL() string
+	PackageName() string
+}
+
+type fetchablePackage struct {
+	pkgName string
+	url     string
+}
+
+func (f fetchablePackage) URL() string {
+	return f.url
+}
+
+func (f fetchablePackage) PackageName() string {
+	return f.pkgName
+}
+
+// NewFetchablePackage creates and returns a minimal implementation of
+// FetchablePackage.
+func NewFetchablePackage(pkgName, url string) FetchablePackage {
+	return &fetchablePackage{
+		pkgName: pkgName,
+		url:     url,
+	}
+}
+
 // InstallablePackage represents a minimal set of information needed to install a package within an Image.
 type InstallablePackage interface {
 	URL() string
diff --git a/pkg/apk/apk/repo.go b/pkg/apk/apk/repo.go
index 9da904f..bad47e6 100644
--- a/pkg/apk/apk/repo.go
+++ b/pkg/apk/apk/repo.go
@@ -34,7 +34,7 @@ import (
 
 var (
 	parsedVersions    sync.Map // map[string]Version
-	parsedConstraints sync.Map // map[string]parsedConstraint
+	parsedConstraints sync.Map // map[string]ParsedConstraint
 )
 
 // NamedIndex an index that contains all of its packages,
@@ -268,7 +268,7 @@ func newPkgResolver(ctx context.Context, indexes []NamedIndex) *PkgResolver {
 	for _, pkgVersions := range allPkgs {
 		for _, pkg := range pkgVersions {
 			for _, provide := range pkg.Provides {
-				name := cachedResolvePackageNameVersionPin(provide).name
+				name := cachedResolvePackageNameVersionPin(provide).Name
 				pkgNameMap[name] = append(pkgNameMap[name], pkg)
 			}
 		}
@@ -311,7 +311,7 @@ func (p *PkgResolver) nextPackage(packages []string, dq map[*RepositoryPackage]s
 // Disqualify anything that provides "constraint". This is used for !foo style constraints.
 func (p *PkgResolver) disqualifyProviders(constraint string, dq map[*RepositoryPackage]string) {
 	parsed := cachedResolvePackageNameVersionPin(constraint)
-	providers, ok := p.nameMap[parsed.name]
+	providers, ok := p.nameMap[parsed.Name]
 	if !ok {
 		return
 	}
@@ -328,7 +328,7 @@ func (p *PkgResolver) disqualifyProviders(constraint string, dq map[*RepositoryP
 	}
 }
 
-func (p *PkgResolver) conflictingVersion(constraint parsedConstraint, conflict *repositoryPackage) bool {
+func (p *PkgResolver) conflictingVersion(constraint ParsedConstraint, conflict *repositoryPackage) bool {
 	// If the constraint is not a virtual, everything will conflict with it.
 	// TODO: Figure out if this logic is actually equivalent to how apk disqualifies virtual.
 	if constraint.version != "" {
@@ -337,13 +337,13 @@ func (p *PkgResolver) conflictingVersion(constraint parsedConstraint, conflict *
 
 	// From here on, "the same version" really means it's a virtual, but let's keep the diff small until we revisit.
 
-	if conflict.Name == constraint.name {
+	if conflict.Name == constraint.Name {
 		return conflict.Version != constraint.version
 	}
 
 	for _, confProv := range conflict.Provides {
 		confConstraint := cachedResolvePackageNameVersionPin(confProv)
-		if confConstraint.name != constraint.name {
+		if confConstraint.Name != constraint.Name {
 			// Not the constraint we're looking for.
 			continue
 		}
@@ -363,7 +363,7 @@ func (p *PkgResolver) conflictingVersion(constraint parsedConstraint, conflict *
 func (p *PkgResolver) disqualifyConflicts(pkg *RepositoryPackage, dq map[*RepositoryPackage]string) {
 	for _, prov := range pkg.Provides {
 		constraint := cachedResolvePackageNameVersionPin(prov)
-		providers, ok := p.nameMap[constraint.name]
+		providers, ok := p.nameMap[constraint.Name]
 		if !ok {
 			continue
 		}
@@ -383,7 +383,7 @@ func (p *PkgResolver) disqualifyConflicts(pkg *RepositoryPackage, dq map[*Reposi
 				continue
 			}
 
-			p.disqualify(dq, conflict.RepositoryPackage, pkg.Filename()+" already provides "+constraint.name)
+			p.disqualify(dq, conflict.RepositoryPackage, pkg.Filename()+" already provides "+constraint.Name)
 		}
 	}
 }
@@ -402,8 +402,8 @@ func (p *PkgResolver) pick(pkg *RepositoryPackage) error {
 
 	for _, prov := range pkg.Provides {
 		constraint := cachedResolvePackageNameVersionPin(prov)
-		if conflict, ok := p.selected[constraint.name]; ok {
-			return fmt.Errorf("selecting package %s conflicts with %s on %q", pkg.Filename(), conflict.Filename(), constraint.name)
+		if conflict, ok := p.selected[constraint.Name]; ok {
+			return fmt.Errorf("selecting package %s conflicts with %s on %q", pkg.Filename(), conflict.Filename(), constraint.Name)
 		}
 
 		// We don't care about virtuals, actually.
@@ -411,7 +411,7 @@ func (p *PkgResolver) pick(pkg *RepositoryPackage) error {
 			continue
 		}
 
-		p.selected[constraint.name] = pkg
+		p.selected[constraint.Name] = pkg
 	}
 
 	return nil
@@ -437,7 +437,7 @@ func (p *PkgResolver) constrain(constraints []string, dq map[*RepositoryPackage]
 			continue
 		}
 
-		providers, ok := p.nameMap[parsed.name]
+		providers, ok := p.nameMap[parsed.Name]
 		if !ok {
 			continue
 		}
@@ -449,7 +449,7 @@ func (p *PkgResolver) constrain(constraints []string, dq map[*RepositoryPackage]
 		}
 
 		for _, provider := range providers {
-			if provider.Name == parsed.name {
+			if provider.Name == parsed.Name {
 				actualVersion, err := cachedParseVersion(provider.Version)
 				// skip invalid ones
 				if err != nil {
@@ -463,7 +463,7 @@ func (p *PkgResolver) constrain(constraints []string, dq map[*RepositoryPackage]
 			} else {
 				for _, provides := range provider.Provides {
 					pp := cachedResolvePackageNameVersionPin(provides)
-					if pp.name != parsed.name {
+					if pp.Name != parsed.Name {
 						continue
 					}
 					actualVersion, err := cachedParseVersion(pp.version)
@@ -608,7 +608,7 @@ func (p *PkgResolver) GetPackageWithDependencies(ctx context.Context, pkgName st
 			for _, subDep := range installIfPkg.InstallIf {
 				// two possibilities: package name, or name=version
 				constraint := cachedResolvePackageNameVersionPin(subDep)
-				name, version := constraint.name, constraint.version
+				name, version := constraint.Name, constraint.version
 				// precise match of whatever it is, take it and continue
 				if _, ok := added[subDep]; ok {
 					matchCount++
@@ -638,7 +638,7 @@ func (p *PkgResolver) GetPackageWithDependencies(ctx context.Context, pkgName st
 // returns multiple in case you need to see all potential matches.
 func (p *PkgResolver) ResolvePackage(pkgName string, dq map[*RepositoryPackage]string) ([]*RepositoryPackage, error) {
 	constraint := cachedResolvePackageNameVersionPin(pkgName)
-	name, version, compare, pin := constraint.name, constraint.version, constraint.dep, constraint.pin
+	name, version, compare, pin := constraint.Name, constraint.version, constraint.dep, constraint.pin
 	pkgsWithVersions, ok := p.nameMap[name]
 	if !ok {
 		return nil, fmt.Errorf("nothing provides %q", name)
@@ -664,7 +664,7 @@ func (p *PkgResolver) ResolvePackage(pkgName string, dq map[*RepositoryPackage]s
 // This is like ResolvePackage but we only care about the best match and not all matches.
 func (p *PkgResolver) resolvePackage(pkgName string, dq map[*RepositoryPackage]string) (*RepositoryPackage, error) {
 	constraint := cachedResolvePackageNameVersionPin(pkgName)
-	name, version, compare, pin := constraint.name, constraint.version, constraint.dep, constraint.pin
+	name, version, compare, pin := constraint.Name, constraint.version, constraint.dep, constraint.pin
 
 	pkgsWithVersions, ok := p.nameMap[name]
 	if !ok {
@@ -719,7 +719,7 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 	myProvides := make(map[string]bool, 2*len(pkg.Provides))
 	// see if we provide this
 	for _, provide := range pkg.Provides {
-		name := cachedResolvePackageNameVersionPin(provide).name
+		name := cachedResolvePackageNameVersionPin(provide).Name
 		myProvides[provide] = true
 		myProvides[name] = true
 	}
@@ -747,7 +747,7 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 
 			// this package might be pinned to a version
 			constraint := cachedResolvePackageNameVersionPin(dep)
-			name, version, compare := constraint.name, constraint.version, constraint.dep
+			name, version, compare := constraint.Name, constraint.version, constraint.dep
 			// see if we provide this
 			if myProvides[name] || myProvides[dep] {
 				// we provide this, so skip it
@@ -787,6 +787,33 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 					return nil, nil, err
 				}
 
+				// See if any virtual packages of packages we've already
+				// selected satisfy this contraint.
+				satisfiedByProvide := false
+				for _, provide := range picked.Provides {
+					prostraint := cachedResolvePackageNameVersionPin(provide)
+					pname, pversion, pcompare := prostraint.Name, prostraint.version, prostraint.dep
+					if pname != name {
+						continue
+					}
+					// If this virtual package is unversioned, it can't
+					// satisfy a versioned constraint
+					if pversion == "" {
+						continue
+					}
+					prover, err := cachedParseVersion(pversion)
+					if err != nil {
+						return nil, nil, err
+					}
+					if pcompare.satisfies(prover, requiredVersion) {
+						satisfiedByProvide = true
+						break
+					}
+				}
+				if satisfiedByProvide {
+					continue
+				}
+
 				// We do care which version and they match.
 				if compare.satisfies(actualVersion, requiredVersion) {
 					continue
@@ -833,7 +860,7 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 		}
 
 		pkgs := options[lowest]
-		name := cachedResolvePackageNameVersionPin(lowest).name
+		name := cachedResolvePackageNameVersionPin(lowest).Name
 
 		// Remove this from our constraints.
 		constraints = slices.DeleteFunc(constraints, func(s string) bool {
@@ -892,13 +919,13 @@ func cachedParseVersion(version string) (Version, error) {
 	return parsed, nil
 }
 
-func cachedResolvePackageNameVersionPin(pkgName string) parsedConstraint {
+func cachedResolvePackageNameVersionPin(pkgName string) ParsedConstraint {
 	cached, ok := parsedConstraints.Load(pkgName)
 	if ok {
-		return cached.(parsedConstraint)
+		return cached.(ParsedConstraint)
 	}
 
-	pin := resolvePackageNameVersionPin(pkgName)
+	pin := ResolvePackageNameVersionPin(pkgName)
 
 	parsedConstraints.Store(pkgName, pin)
 	return pin
@@ -1043,7 +1070,7 @@ func (p *PkgResolver) getDepVersionForName(pkg *repositoryPackage, name string)
 	}
 	for _, prov := range pkg.Provides {
 		constraint := cachedResolvePackageNameVersionPin(prov)
-		pName, pVersion := constraint.name, constraint.version
+		pName, pVersion := constraint.Name, constraint.version
 		if pVersion == "" {
 			pVersion = pkg.Version
 		}
diff --git a/pkg/apk/apk/version.go b/pkg/apk/apk/version.go
index 185dbf7..e03077c 100644
--- a/pkg/apk/apk/version.go
+++ b/pkg/apk/apk/version.go
@@ -349,24 +349,56 @@ func (v versionDependency) satisfies(actualVersion, requiredVersion Version) boo
 	}
 }
 
-type parsedConstraint struct {
-	name    string
+type ParsedConstraint struct {
+	Name    string
 	version string
 	dep     versionDependency
 	pin     string
 }
 
-func resolvePackageNameVersionPin(pkgName string) parsedConstraint {
+func (p ParsedConstraint) SatisfiedBy(v Version) (bool, error) {
+	if p.version == "" {
+		return true, nil
+	}
+	pv, err := cachedParseVersion(p.version)
+	if err != nil {
+		return false, err
+	}
+	return p.dep.satisfies(v, pv), nil
+}
+
+var endsWithReleaseStr = regexp.MustCompile(`-r\d+$`)
+
+func ResolvePackageNameVersionPin(pkgName string) ParsedConstraint {
+	// Due to https://github.com/chainguard-dev/melange/pull/1871,
+	// we have to treat shared library depends/provides
+	// differently.
+	//
+	// If a shared library's depends/provides has an explicitly
+	// version, and if the version does NOT end with a release
+	// substring (`-rN`), then we tweak its version to sort
+	// *after* the ones that end with `-rN`.
+	//
+	// We only care if the version string ends with a release
+	// substring (`-rN`), as that indicates that it has a proper
+	// versioned depends/provides containing the package version.
+	if strings.HasPrefix(pkgName, "so:") {
+		onlyPkgName, pkgVersion, found := strings.Cut(pkgName, "=")
+		if found && !endsWithReleaseStr.MatchString(pkgVersion) {
+			pkgName = onlyPkgName + "=0." + pkgVersion
+		}
+	}
+
 	parts := packageNameRegex.FindAllStringSubmatch(pkgName, -1)
 	if len(parts) == 0 || len(parts[0]) < 2 {
-		return parsedConstraint{
-			name: pkgName,
+		return ParsedConstraint{
+			Name: pkgName,
 			dep:  versionAny,
 		}
 	}
 	// layout: [full match, name, =version, =|>|<, version, @pin, pin]
-	p := parsedConstraint{
-		name:    parts[0][1],
+	p := ParsedConstraint{
+		Name:    parts[0][1],
 		version: parts[0][4],
 		pin:     parts[0][6],
 		dep:     versionAny,
diff --git a/pkg/apk/passwd/doc.go b/pkg/apk/passwd/doc.go
deleted file mode 100644
index 44de0fa..0000000
--- a/pkg/apk/passwd/doc.go
+++ /dev/null
@@ -1,17 +0,0 @@
-// Copyright 2022, 2023 Chainguard, Inc.
-//
-// 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.
-
-// Package passwd implements simple functions to parse and manipulate
-// /etc/passwd and /etc/group files
-package passwd
diff --git a/pkg/apk/passwd/group.go b/pkg/apk/passwd/group.go
deleted file mode 100644
index db0755c..0000000
--- a/pkg/apk/passwd/group.go
+++ /dev/null
@@ -1,148 +0,0 @@
-// Copyright 2022, 2023 Chainguard, Inc.
-//
-// 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.
-
-package passwd
-
-import (
-	"bufio"
-	"fmt"
-	"io"
-	"io/fs"
-	"os"
-	"strconv"
-	"strings"
-
-	apkfs "chainguard.dev/apko/pkg/apk/fs"
-)
-
-// GroupEntry describes a single line in /etc/group.
-type GroupEntry struct {
-	GroupName string
-	Password  string
-	GID       uint32
-	Members   []string
-}
-
-// GroupFile describes an entire /etc/group file's contents.
-type GroupFile struct {
-	Entries []GroupEntry
-}
-
-// ReadOrCreateGroupFile parses an /etc/group file into a GroupFile.
-// An empty file is created if /etc/group is missing.
-func ReadOrCreateGroupFile(fsys apkfs.FullFS, filePath string) (GroupFile, error) {
-	gf := GroupFile{}
-
-	file, err := fsys.OpenFile(filePath, os.O_RDONLY|os.O_CREATE, 0o644)
-	if err != nil {
-		return gf, fmt.Errorf("failed to open %s: %w", filePath, err)
-	}
-	defer file.Close()
-
-	if err := gf.Load(file); err != nil {
-		return gf, err
-	}
-
-	return gf, nil
-}
-
-// ReadGroupFile parses an /etc/group file into a GroupFile.
-// If /etc/group is missing, returns an error
-func ReadGroupFile(fsys fs.FS, filePath string) (GroupFile, error) {
-	gf := GroupFile{}
-
-	file, err := fsys.Open(filePath)
-	if err != nil {
-		return gf, fmt.Errorf("failed to open %s: %w", filePath, err)
-	}
-	defer file.Close()
-
-	if err := gf.Load(file); err != nil {
-		return gf, err
-	}
-
-	return gf, nil
-}
-
-// Load loads an /etc/passwd file into a GroupFile from an io.Reader.
-func (gf *GroupFile) Load(r io.Reader) error {
-	scanner := bufio.NewScanner(r)
-	for scanner.Scan() {
-		ge := GroupEntry{}
-
-		if err := ge.Parse(scanner.Text()); err != nil {
-			return fmt.Errorf("unable to parse: %w", err)
-		}
-
-		gf.Entries = append(gf.Entries, ge)
-	}
-
-	if err := scanner.Err(); err != nil {
-		return fmt.Errorf("unable to parse: %w", err)
-	}
-
-	return nil
-}
-
-// WriteFile writes an /etc/passwd file from a GroupFile.
-func (gf *GroupFile) WriteFile(fsys apkfs.FullFS, filePath string) error {
-	file, err := fsys.Create(filePath)
-	if err != nil {
-		return fmt.Errorf("unable to open %s for writing: %w", filePath, err)
-	}
-	defer file.Close()
-
-	return gf.Write(file)
-}
-
-// Write writes an /etc/passwd file into an io.Writer.
-func (gf *GroupFile) Write(w io.Writer) error {
-	for _, ge := range gf.Entries {
-		if err := ge.Write(w); err != nil {
-			return fmt.Errorf("unable to write group entry: %w", err)
-		}
-	}
-
-	return nil
-}
-
-// Parse parses an /etc/group line into a GroupEntry.
-func (ge *GroupEntry) Parse(line string) error {
-	line = strings.TrimSpace(line)
-
-	parts := strings.Split(line, ":")
-	if len(parts) != 4 {
-		return fmt.Errorf("malformed line, contains %d parts, expecting 4", len(parts))
-	}
-
-	ge.GroupName = parts[0]
-	ge.Password = parts[1]
-
-	gid, err := strconv.Atoi(parts[2])
-	if err != nil {
-		return fmt.Errorf("failed to parse UID %s", parts[2])
-	}
-	ge.GID = uint32(gid)
-
-	ge.Members = strings.Split(parts[3], ",")
-
-	return nil
-}
-
-// Write writes an /etc/group line into an io.Writer.
-func (ge *GroupEntry) Write(w io.Writer) error {
-	members := strings.Join(ge.Members, ",")
-	_, err := fmt.Fprintf(w, "%s:%s:%d:%s\n", ge.GroupName, ge.Password, ge.GID, members)
-	return err
-}
diff --git a/pkg/apk/passwd/passwd.go b/pkg/apk/passwd/passwd.go
deleted file mode 100644
index b6479a3..0000000
--- a/pkg/apk/passwd/passwd.go
+++ /dev/null
@@ -1,159 +0,0 @@
-// Copyright 2022, 2023 Chainguard, Inc.
-//
-// 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.
-
-package passwd
-
-import (
-	"bufio"
-	"fmt"
-	"io"
-	"io/fs"
-	"os"
-	"strconv"
-	"strings"
-
-	apkfs "chainguard.dev/apko/pkg/apk/fs"
-)
-
-// UserEntry contains the parsed data from an /etc/passwd entry.
-type UserEntry struct {
-	UserName string
-	Password string
-	UID      uint32
-	GID      uint32
-	Info     string
-	HomeDir  string
-	Shell    string
-}
-
-// UserFile contains the entries from an /etc/passwd file.
-type UserFile struct {
-	Entries []UserEntry
-	fsys    apkfs.FullFS
-}
-
-// ReadOrCreateUserFile parses an /etc/passwd file into a UserFile.
-// An empty file is created if /etc/passwd is missing.
-func ReadOrCreateUserFile(fsys apkfs.FullFS, filePath string) (UserFile, error) {
-	uf := UserFile{fsys: fsys}
-
-	file, err := fsys.OpenFile(filePath, os.O_RDONLY|os.O_CREATE, 0o644)
-	if err != nil {
-		return uf, fmt.Errorf("failed to open %s: %w", filePath, err)
-	}
-	defer file.Close()
-
-	if err := uf.Load(file); err != nil {
-		return uf, err
-	}
-
-	return uf, nil
-}
-
-// ReadUserFile parses an /etc/passwd file into a UserFile.
-// If it is missing, returns an error.
-func ReadUserFile(fsys fs.FS, filePath string) (UserFile, error) {
-	uf := UserFile{}
-
-	file, err := fsys.Open(filePath)
-	if err != nil {
-		return uf, fmt.Errorf("failed to open %s: %w", filePath, err)
-	}
-	defer file.Close()
-
-	if err := uf.Load(file); err != nil {
-		return uf, err
-	}
-
-	return uf, nil
-}
-
-// Load loads an /etc/passwd file into a UserFile from an io.Reader.
-func (uf *UserFile) Load(r io.Reader) error {
-	scanner := bufio.NewScanner(r)
-	for scanner.Scan() {
-		ue := UserEntry{}
-
-		if err := ue.Parse(scanner.Text()); err != nil {
-			return fmt.Errorf("unable to parse: %w", err)
-		}
-
-		uf.Entries = append(uf.Entries, ue)
-	}
-
-	if err := scanner.Err(); err != nil {
-		return fmt.Errorf("unable to parse: %w", err)
-	}
-
-	return nil
-}
-
-// WriteFile writes an /etc/passwd file from a UserFile.
-func (uf *UserFile) WriteFile(filePath string) error {
-	file, err := uf.fsys.Create(filePath)
-	if err != nil {
-		return fmt.Errorf("unable to open %s for writing: %w", filePath, err)
-	}
-	defer file.Close()
-
-	return uf.Write(file)
-}
-
-// Write writes an /etc/passwd file into an io.Writer.
-func (uf *UserFile) Write(w io.Writer) error {
-	for _, ue := range uf.Entries {
-		if err := ue.Write(w); err != nil {
-			return fmt.Errorf("unable to write passwd entry: %w", err)
-		}
-	}
-
-	return nil
-}
-
-// Parse parses an /etc/passwd line into a UserEntry.
-func (ue *UserEntry) Parse(line string) error {
-	line = strings.TrimSpace(line)
-
-	parts := strings.Split(line, ":")
-	if len(parts) != 7 {
-		return fmt.Errorf("malformed line, contains %d parts, expecting 7", len(parts))
-	}
-
-	ue.UserName = parts[0]
-	ue.Password = parts[1]
-
-	uid, err := strconv.Atoi(parts[2])
-	if err != nil {
-		return fmt.Errorf("failed to parse UID %s", parts[2])
-	}
-	ue.UID = uint32(uid)
-
-	gid, err := strconv.Atoi(parts[3])
-	if err != nil {
-		return fmt.Errorf("failed to parse GID %s", parts[3])
-	}
-	ue.GID = uint32(gid)
-
-	ue.Info = parts[4]
-	ue.HomeDir = parts[5]
-	ue.Shell = parts[6]
-
-	return nil
-}
-
-// Write writes an /etc/passwd line into an io.Writer.
-func (ue *UserEntry) Write(w io.Writer) error {
-	_, err := fmt.Fprintf(w, "%s:%s:%d:%d:%s:%s:%s\n", ue.UserName, ue.Password, ue.UID, ue.GID, ue.Info, ue.HomeDir, ue.Shell)
-	return err
-}
diff --git a/pkg/apk/tarball/write.go b/pkg/apk/tarball/write.go
deleted file mode 100644
index 7a1f461..0000000
--- a/pkg/apk/tarball/write.go
+++ /dev/null
@@ -1,166 +0,0 @@
-// Copyright 2022, 2023 Chainguard, Inc.
-//
-// 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.
-
-package tarball
-
-import (
-	"archive/tar"
-	"context" //nolint:gosec
-	"fmt"
-	"io"
-	"io/fs"
-	"os"
-
-	"go.opentelemetry.io/otel"
-	"golang.org/x/sys/unix"
-
-	apkfs "chainguard.dev/apko/pkg/apk/fs"
-	"chainguard.dev/apko/pkg/apk/passwd"
-)
-
-const xattrTarPAXRecordsPrefix = "SCHILY.xattr."
-
-func writeTar(ctx context.Context, tw *tar.Writer, fsys apkfs.FullFS, users, groups map[int]string) error { //nolint:gocyclo
-	buf := make([]byte, 1<<20)
-
-	if err := fs.WalkDir(fsys, ".", func(path string, d fs.DirEntry, err error) error {
-		if err := ctx.Err(); err != nil {
-			return err
-		}
-		// skip the root path, superfluous
-		if path == "." {
-			return nil
-		}
-
-		if err != nil {
-			return err
-		}
-
-		info, err := d.Info()
-		if err != nil {
-			return err
-		}
-
-		var (
-			link         string
-			major, minor uint32
-			isCharDevice bool
-		)
-		if info.Mode()&os.ModeSymlink == os.ModeSymlink {
-			if link, err = fsys.Readlink(path); err != nil {
-				return err
-			}
-		}
-
-		if info.Mode()&os.ModeCharDevice == os.ModeCharDevice {
-			isCharDevice = true
-			dev, err := fsys.Readnod(path)
-			if err != nil {
-				return err
-			}
-			major = unix.Major(uint64(dev))
-			minor = unix.Minor(uint64(dev))
-		}
-
-		header, err := tar.FileInfoHeader(info, link)
-		if err != nil {
-			return err
-		}
-		// devices
-		if isCharDevice {
-			header.Devmajor = int64(major)
-			header.Devminor = int64(minor)
-		}
-		// work around some weirdness, without this we wind up with just the basename
-		header.Name = path
-
-		header.ModTime = info.ModTime()
-
-		if name, ok := users[header.Uid]; ok {
-			header.Uname = name
-		}
-		if name, ok := groups[header.Gid]; ok {
-			header.Gname = name
-		}
-
-		if link != "" {
-			header.Typeflag = tar.TypeSymlink
-		}
-
-		if header.PAXRecords == nil {
-			header.PAXRecords = map[string]string{}
-		}
-
-		// only capture xattrs for real objects in the FS
-		if header.Typeflag == tar.TypeReg || header.Typeflag == tar.TypeDir {
-			xattrs, err := fsys.ListXattrs(path)
-			// we can ignore errors
-			if err == nil && xattrs != nil {
-				for name, value := range xattrs {
-					header.PAXRecords[xattrTarPAXRecordsPrefix+name] = string(value)
-				}
-			}
-		}
-
-		if err := tw.WriteHeader(header); err != nil {
-			return err
-		}
-
-		if info.Mode().IsRegular() && header.Size > 0 {
-			data, err := fsys.Open(path)
-			if err != nil {
-				return err
-			}
-
-			defer data.Close()
-
-			if _, err := io.CopyBuffer(tw, data, buf); err != nil {
-				return err
-			}
-		}
-
-		return nil
-	}); err != nil {
-		return err
-	}
-
-	return nil
-}
-
-// WriteTar writes a tarball to the provided io.Writer from the provided fs.FS.
-// The etc/passwd and etc/group file provide username and group name mappings for the tar.
-func WriteTar(ctx context.Context, dst io.Writer, src apkfs.FullFS) error {
-	ctx, span := otel.Tracer("go-apk").Start(ctx, "WriteTar")
-	defer span.End()
-
-	tw := tar.NewWriter(dst)
-	defer tw.Close()
-
-	// get the uname and gname maps
-	usersFile, _ := passwd.ReadUserFile(src, "etc/passwd")
-	groupsFile, _ := passwd.ReadGroupFile(src, "etc/group")
-	users := map[int]string{}
-	groups := map[int]string{}
-	for _, u := range usersFile.Entries {
-		users[int(u.UID)] = u.UserName
-	}
-	for _, g := range groupsFile.Entries {
-		groups[int(g.GID)] = g.GroupName
-	}
-	if err := writeTar(ctx, tw, src, users, groups); err != nil {
-		return fmt.Errorf("writing TAR archive failed: %w", err)
-	}
-
-	return nil
-}
diff --git a/pkg/build/build.go b/pkg/build/build.go
index a7972a4..4bdf7de 100644
--- a/pkg/build/build.go
+++ b/pkg/build/build.go
@@ -17,11 +17,11 @@ package build
 import (
 	"compress/gzip"
 	"context"
-	"encoding/hex"
 	"errors"
 	"fmt"
 	"io"
 	"os"
+	"path/filepath"
 	"runtime"
 	"strconv"
 	"strings"
@@ -94,7 +94,7 @@ func (bc *Context) BuildImage(ctx context.Context) error {
 	ctx, span := otel.Tracer("apko").Start(ctx, "BuildImage")
 	defer span.End()
 
-	if err := bc.buildImage(ctx); err != nil {
+	if _, err := bc.buildImage(ctx); err != nil {
 		log.Debugf("buildImage failed: %v", err)
 		b, err2 := yaml.Marshal(bc.ic)
 		if err2 != nil {
@@ -134,20 +134,16 @@ func (bc *Context) BuildLayers(ctx context.Context) ([]v1.Layer, error) {
 	ctx, span := otel.Tracer("apko").Start(ctx, "BuildLayers")
 	defer span.End()
 
-	// build image filesystem
-	if err := bc.BuildImage(ctx); err != nil {
-		return nil, err
-	}
-	if err := bc.postBuildSetApk(ctx); err != nil {
-		return nil, err
-	}
+	if bc.ic.Layering == nil {
+		_, layer, err := bc.BuildLayer(ctx)
+		if err != nil {
+			return nil, err
+		}
 
-	_, layer, err := bc.ImageLayoutToLayer(ctx)
-	if err != nil {
-		return nil, err
+		return []v1.Layer{layer}, nil
 	}
 
-	return []v1.Layer{layer}, nil
+	return bc.buildLayers(ctx)
 }
 
 // ImageLayoutToLayer given an already built-out
@@ -161,31 +157,34 @@ func (bc *Context) ImageLayoutToLayer(ctx context.Context) (string, v1.Layer, er
 		return "", nil, err
 	}
 
-	layerTarGZ, diffid, digest, size, err := bc.BuildTarball(ctx)
-	// build layer tarball
+	var (
+		outfile *os.File
+		err     error
+	)
+
+	if bc.o.TarballPath != "" {
+		outfile, err = os.Create(bc.o.TarballPath)
+	} else {
+		outfile, err = os.Create(filepath.Join(bc.o.TempDir(), bc.o.TarballFileName()))
+	}
 	if err != nil {
-		return "", nil, err
+		return "", nil, fmt.Errorf("creating tarball file: %w", err)
 	}
+	bc.o.TarballPath = outfile.Name()
+	defer outfile.Close()
 
-	h := v1.Hash{
-		Algorithm: "sha256",
-		Hex:       hex.EncodeToString(digest.Sum(make([]byte, 0, digest.Size()))),
+	lw := newLayerWriter(outfile)
+
+	if err := writeTar(ctx, lw.w, bc.fs); err != nil {
+		return "", nil, fmt.Errorf("generating tarball: %w", err)
 	}
 
-	l := &layer{
-		filename: layerTarGZ,
-		desc: &v1.Descriptor{
-			Digest:    h,
-			Size:      size,
-			MediaType: v1types.OCILayer,
-		},
-		diffid: &v1.Hash{
-			Algorithm: "sha256",
-			Hex:       hex.EncodeToString(diffid.Sum(make([]byte, 0, diffid.Size()))),
-		},
+	l, err := lw.finalize()
+	if err != nil {
+		return "", nil, fmt.Errorf("finalizing layer: %w", err)
 	}
 
-	return layerTarGZ, l, nil
+	return outfile.Name(), l, nil
 }
 
 func (bc *Context) checkPaths(ctx context.Context) error {
diff --git a/pkg/build/build_implementation.go b/pkg/build/build_implementation.go
index a134006..a67836f 100644
--- a/pkg/build/build_implementation.go
+++ b/pkg/build/build_implementation.go
@@ -15,26 +15,27 @@
 package build
 
 import (
+	"archive/tar"
 	"bufio"
 	"context"
 	"crypto/sha256"
+	"encoding/hex"
 	"encoding/json"
 	"fmt"
-	"hash"
 	"io"
 	"os"
 	"path/filepath"
 	"runtime"
 	"sync"
 
+	v1 "github.com/google/go-containerregistry/pkg/v1"
+	v1types "github.com/google/go-containerregistry/pkg/v1/types"
 	gzip "github.com/klauspost/pgzip"
 	"github.com/sigstore/cosign/v2/pkg/oci"
-	"go.opentelemetry.io/otel"
 
 	"github.com/chainguard-dev/clog"
 
 	"chainguard.dev/apko/pkg/apk/apk"
-	"chainguard.dev/apko/pkg/apk/tarball"
 	"chainguard.dev/apko/pkg/lock"
 	"chainguard.dev/apko/pkg/options"
 )
@@ -78,59 +79,79 @@ func pooledBufioWriter(w io.Writer) *bufio.Writer {
 	return bw
 }
 
-// BuildTarball takes the fully populated working directory and saves it to
-// an OCI image layer tar.gz file.
-func (bc *Context) BuildTarball(ctx context.Context) (string, hash.Hash, hash.Hash, int64, error) {
-	log := clog.FromContext(ctx)
-
-	ctx, span := otel.Tracer("apko").Start(ctx, "BuildTarball")
-	defer span.End()
-
-	var outfile *os.File
-	var err error
-
-	if bc.o.TarballPath != "" {
-		outfile, err = os.Create(bc.o.TarballPath)
-	} else {
-		outfile, err = os.Create(filepath.Join(bc.o.TempDir(), bc.o.TarballFileName()))
-	}
-	if err != nil {
-		return "", nil, nil, 0, fmt.Errorf("opening the build context tarball path failed: %w", err)
-	}
-	bc.o.TarballPath = outfile.Name()
-	defer outfile.Close()
+// layerWriter allows lazily writing files to a tarball instead
+// of doing everything in one pass, this is necessary for multi-layer
+// images where we are writing to multiple layers at the same time.
+type layerWriter struct {
+	w        *tar.Writer
+	stack    []*file // only used by multi-layer builds
+	finalize func() (*layer, error)
+}
 
+// newLayerWriter wraps a file with a gzipping tar writer that computes
+// everything we need to know to implement a v1.Layer, which it will
+// produce when finalize() is called.
+func newLayerWriter(out *os.File) *layerWriter {
 	digest := sha256.New()
 
-	buf := pooledBufioWriter(outfile)
-	defer bufioPool.Put(buf)
+	buf := pooledBufioWriter(out)
 
 	gzw := pooledGzipWriter(io.MultiWriter(digest, buf))
-	defer pgzipPool.Put(gzw)
 
 	diffid := sha256.New()
 
-	if err := tarball.WriteTar(ctx, io.MultiWriter(diffid, gzw), bc.fs); err != nil {
-		return "", nil, nil, 0, fmt.Errorf("failed to generate tarball for image: %w", err)
-	}
-	if err := gzw.Close(); err != nil {
-		return "", nil, nil, 0, fmt.Errorf("closing gzip writer: %w", err)
-	}
+	w := tar.NewWriter(io.MultiWriter(diffid, gzw))
 
-	if err := buf.Flush(); err != nil {
-		return "", nil, nil, 0, fmt.Errorf("flushing %s: %w", outfile.Name(), err)
-	}
+	// Just capturing everything in a closure here is more straightforward
+	// to read (as a translation from what used to implement this) than
+	// adding a bunch of fields to layerWriter.
+	return &layerWriter{
+		w: w,
+		finalize: func() (*layer, error) {
+			defer pgzipPool.Put(gzw)
+			defer bufioPool.Put(buf)
 
-	stat, err := outfile.Stat()
-	if err != nil {
-		return "", nil, nil, 0, fmt.Errorf("stat(%q): %w", outfile.Name(), err)
-	}
+			if err := w.Close(); err != nil {
+				return nil, fmt.Errorf("closing tar writer: %w", err)
+			}
 
-	log.Infof("built image layer tarball as %s", outfile.Name())
-	return outfile.Name(), diffid, digest, stat.Size(), nil
+			if err := gzw.Close(); err != nil {
+				return nil, fmt.Errorf("closing gzip writer: %w", err)
+			}
+
+			if err := buf.Flush(); err != nil {
+				return nil, fmt.Errorf("flushing %s: %w", out.Name(), err)
+			}
+
+			stat, err := out.Stat()
+			if err != nil {
+				return nil, fmt.Errorf("statting %s: %w", out.Name(), err)
+			}
+
+			h := v1.Hash{
+				Algorithm: "sha256",
+				Hex:       hex.EncodeToString(digest.Sum(make([]byte, 0, digest.Size()))),
+			}
+
+			l := &layer{
+				filename: out.Name(),
+				desc: &v1.Descriptor{
+					Digest:    h,
+					Size:      stat.Size(),
+					MediaType: v1types.OCILayer,
+				},
+				diffid: &v1.Hash{
+					Algorithm: "sha256",
+					Hex:       hex.EncodeToString(diffid.Sum(make([]byte, 0, diffid.Size()))),
+				},
+			}
+
+			return l, nil
+		},
+	}
 }
 
-func (bc *Context) buildImage(ctx context.Context) error {
+func (bc *Context) buildImage(ctx context.Context) ([]*apk.Package, error) {
 	log := clog.FromContext(ctx)
 
 	// When using base image for the build, apko adds new layer on top of the base. This means
@@ -143,34 +164,39 @@ func (bc *Context) buildImage(ctx context.Context) error {
 		for index := range basePkgs {
 			err := bc.apk.AddInstalledPackage(&basePkgs[index].Package, basePkgs[index].Files)
 			if err != nil {
-				return err
+				return nil, err
 			}
 		}
 	}
 
+	var (
+		pkgs []*apk.Package
+		err  error
+	)
 	if bc.o.Lockfile != "" {
 		lock, err := lock.FromFile(bc.o.Lockfile)
 		if err != nil {
-			return fmt.Errorf("failed to load lock-file: %w", err)
+			return nil, fmt.Errorf("failed to load lock-file: %w", err)
 		}
 		if lock.Config == nil {
 			log.Warnf("The lock file does not contain checksum of the config. Please regenerate.")
 		} else if bc.o.ImageConfigChecksum != "" && bc.o.ImageConfigChecksum != lock.Config.DeepChecksum {
-			return fmt.Errorf("checksum in the lock file '%v' does not matches the original config: '%v' "+
+			return nil, fmt.Errorf("checksum in the lock file '%v' does not matches the original config: '%v' "+
 				"(maybe regenerate the lock file)",
 				bc.o.Lockfile, bc.o.ImageConfigFile)
 		}
 		allPkgs, err := installablePackagesForArch(lock, bc.Arch())
 		if err != nil {
-			return fmt.Errorf("failed getting packages for install from lockfile %s: %w", bc.o.Lockfile, err)
+			return nil, fmt.Errorf("failed getting packages for install from lockfile %s: %w", bc.o.Lockfile, err)
 		}
-		err = bc.apk.InstallPackages(ctx, &bc.o.SourceDateEpoch, allPkgs)
+		pkgs, err = bc.apk.InstallPackages(ctx, &bc.o.SourceDateEpoch, allPkgs)
 		if err != nil {
-			return fmt.Errorf("failed installation from lockfile %s: %w", bc.o.Lockfile, err)
+			return nil, fmt.Errorf("failed installation from lockfile %s: %w", bc.o.Lockfile, err)
 		}
 	} else {
-		if err := bc.apk.FixateWorld(ctx, &bc.o.SourceDateEpoch); err != nil {
-			return fmt.Errorf("installing apk packages: %w", err)
+		pkgs, err = bc.apk.FixateWorld(ctx, &bc.o.SourceDateEpoch)
+		if err != nil {
+			return nil, fmt.Errorf("installing apk packages: %w", err)
 		}
 	}
 
@@ -179,40 +205,40 @@ func (bc *Context) buildImage(ctx context.Context) error {
 	// If one wants to add a support for adding additional users they would need to look into this piece of code.
 	if bc.ic.Contents.BaseImage == nil {
 		if err := mutateAccounts(bc.fs, &bc.ic); err != nil {
-			return fmt.Errorf("failed to mutate accounts: %w", err)
+			return nil, fmt.Errorf("failed to mutate accounts: %w", err)
 		}
 	}
 
 	if err := bc.WriteEtcApkoConfig(ctx); err != nil {
-		return fmt.Errorf("failed to install apko config: %w", err)
+		return nil, fmt.Errorf("failed to install apko config: %w", err)
 	}
 
 	if err := mutatePaths(bc.fs, &bc.o, &bc.ic); err != nil {
-		return fmt.Errorf("failed to mutate paths: %w", err)
+		return nil, fmt.Errorf("failed to mutate paths: %w", err)
 	}
 
 	if err := bc.s6.WriteSupervisionTree(ctx, bc.ic.Entrypoint.Services); err != nil {
-		return fmt.Errorf("failed to write supervision tree: %w", err)
+		return nil, fmt.Errorf("failed to write supervision tree: %w", err)
 	}
 
 	// add busybox symlinks
 	installed, err := bc.apk.GetInstalled()
 	if err != nil {
-		return fmt.Errorf("getting installed packages: %w", err)
+		return nil, fmt.Errorf("getting installed packages: %w", err)
 	}
 
 	if err := installBusyboxLinks(bc.fs, installed); err != nil {
-		return err
+		return nil, err
 	}
 
 	// add necessary character devices
 	if err := installCharDevices(bc.fs); err != nil {
-		return err
+		return nil, err
 	}
 
 	log.Debug("finished building filesystem")
 
-	return nil
+	return pkgs, nil
 }
 
 func (bc *Context) WriteEtcApkoConfig(_ context.Context) error {
diff --git a/pkg/build/layers.go b/pkg/build/layers.go
new file mode 100644
index 0000000..baf1cb3
--- /dev/null
+++ b/pkg/build/layers.go
@@ -0,0 +1,416 @@
+// Copyright 2025 Chainguard, Inc.
+//
+// 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.
+
+package build
+
+import (
+	"archive/tar"
+	"cmp"
+	"context"
+	"fmt"
+	"io"
+	"maps"
+	"os"
+	"path"
+	"slices"
+
+	"chainguard.dev/apko/pkg/apk/apk"
+	apkfs "chainguard.dev/apko/pkg/apk/fs"
+
+	"github.com/chainguard-dev/clog"
+	v1 "github.com/google/go-containerregistry/pkg/v1"
+)
+
+func (bc *Context) buildLayers(ctx context.Context) ([]v1.Layer, error) {
+	log := clog.FromContext(ctx)
+
+	if strategy := bc.ic.Layering.Strategy; strategy != "origin" {
+		return nil, fmt.Errorf("unrecognized layering strategy %q", strategy)
+	}
+
+	if bc.ic.Contents.BaseImage != nil {
+		return nil, fmt.Errorf("layering with %q is unsupported", "baseimage")
+	}
+
+	// Build a single fs.FS, the normal way (this writes to bc.fs).
+	pkgs, err := bc.buildImage(ctx)
+	if err != nil {
+		return nil, fmt.Errorf("building filesystem: %w", err)
+	}
+
+	// Use our layering strategy to partition packages into a set of Budget groups.
+	groups, err := groupByOriginAndSize(pkgs, bc.ic.Layering.Budget)
+	if err != nil {
+		return nil, fmt.Errorf("grouping packages: %w", err)
+	}
+	log.Infof("Building %d layers with budget %d", len(groups), bc.ic.Layering.Budget)
+
+	for i, g := range groups {
+		log.Infof("  layer[%d]:", i)
+
+		for _, pkg := range g.pkgs {
+			log.Infof("    - %s=%s", pkg.Name, pkg.Version)
+		}
+	}
+
+	// Then partition that single fs.FS into multiple layers based on our layering strategy.
+	return splitLayers(ctx, bc.fs, groups, bc.o.TempDir())
+}
+
+func replacesGroup(rep string, g *group) (bool, error) {
+	constraint := apk.ResolvePackageNameVersionPin(rep)
+
+	// Look for the package to make sure the version satisfies Replaces.
+	for _, pkg := range g.pkgs {
+		if pkg.Name != constraint.Name {
+			// This is not the package we're looking for.
+			continue
+		}
+
+		ver, err := apk.ParseVersion(pkg.Version)
+		if err != nil {
+			return false, fmt.Errorf("parsing %s version %s: %w", pkg.Name, pkg.Version, err)
+		}
+
+		ok, err := constraint.SatisfiedBy(ver)
+		if err != nil {
+			return false, fmt.Errorf("checking %s satisfies %s: %w", pkg.Version, constraint.Name, err)
+		}
+
+		if ok {
+			return true, nil
+		}
+	}
+
+	return false, nil
+}
+
+func groupByOriginAndSize(pkgs []*apk.Package, budget int) ([]*group, error) {
+	// First, we're going to group packages by their origin.
+	byOrigin := map[string]*group{}
+	for _, pkg := range pkgs {
+		origin := pkg.Origin
+		if _, ok := byOrigin[origin]; !ok {
+			byOrigin[origin] = &group{}
+		}
+
+		g, ok := byOrigin[origin]
+		if !ok {
+			panic(fmt.Errorf("byOrigin[%q] missing", origin))
+		}
+
+		g.pkgs = append(g.pkgs, pkg)
+	}
+
+	// Then we need to merge any packages that replace each other.
+	byPackage := map[string]*group{}
+	for _, g := range byOrigin {
+		for _, pkg := range g.pkgs {
+			byPackage[pkg.Name] = g
+		}
+	}
+
+	replaceMap := map[string][]string{}
+	for _, g := range byPackage {
+		for _, pkg := range g.pkgs {
+			if len(pkg.Replaces) == 0 {
+				continue
+			}
+
+			replaceMap[pkg.Name] = pkg.Replaces
+		}
+	}
+
+	for pkg, replaces := range replaceMap {
+		for _, rep := range replaces {
+			constraint := apk.ResolvePackageNameVersionPin(rep)
+
+			replacee, ok := byPackage[constraint.Name]
+			if !ok {
+				// Whatever this package replaces is not in the image, that's normal.
+				continue
+			}
+
+			if ok, err := replacesGroup(rep, replacee); err != nil {
+				return nil, fmt.Errorf("checking %s replaces %s: %w", pkg, constraint.Name, err)
+			} else if !ok {
+				continue
+			}
+
+			g, ok := byPackage[pkg]
+			if !ok {
+				panic(fmt.Errorf("byPackage[%q] missing", pkg))
+			}
+
+			// If they're already merged, nothing to do.
+			if replacee == g {
+				continue
+			}
+
+			// Otherwise, we need to merge the two groups.
+			merged := merge(g, replacee)
+
+			// Update our maps so we can test identity above.
+			for _, pkg := range merged.pkgs {
+				byPackage[pkg.Name] = merged
+				byOrigin[pkg.Origin] = merged
+			}
+		}
+	}
+
+	// Now we need to pick the best groups to keep.
+	// First pass we'll set the size of each group to the sum of the installed size of all its packages.
+	groups := make([]*group, 0, budget)
+	seen := map[*group]struct{}{}
+	for v := range maps.Values(byOrigin) {
+		if _, ok := seen[v]; ok {
+			continue
+		}
+		seen[v] = struct{}{}
+		groups = append(groups, v)
+	}
+	for _, g := range groups {
+		for _, pkg := range g.pkgs {
+			g.size += pkg.InstalledSize
+			g.tiebreaker = max(g.tiebreaker, pkg.Name)
+		}
+	}
+
+	// Then we'll sort by the size and take the top $budget, merging the remainders.
+	slices.SortFunc(groups, func(a, b *group) int {
+		return cmp.Or(
+			cmp.Compare(b.size, a.size),             // Descending size.
+			cmp.Compare(a.tiebreaker, b.tiebreaker)) // In the rare case where we have identical sizes.
+	})
+
+	if len(groups) > budget {
+		cutoff := max(budget-1, 0) // Even if budget == 0, we want 1 group.
+
+		remainder := groups[cutoff:]
+		groups = groups[:cutoff]
+
+		groups = append(groups, merge(remainder...))
+	}
+
+	// Sort packages too just so they're in a consistent order.
+	for _, g := range groups {
+		slices.SortFunc(g.pkgs, func(a, b *apk.Package) int {
+			return cmp.Compare(a.Name, b.Name)
+		})
+	}
+
+	return groups, nil
+}
+
+type group struct {
+	pkgs []*apk.Package
+
+	size uint64
+
+	// This is silly but in the event that two groups have identical size,
+	// we want a predictable sort order _somehow_.
+	tiebreaker string
+}
+
+func merge(groups ...*group) *group {
+	merged := &group{}
+	for _, g := range groups {
+		merged.pkgs = slices.Concat(merged.pkgs, g.pkgs)
+		merged.size += g.size
+		merged.tiebreaker = max(merged.tiebreaker, g.tiebreaker)
+	}
+	return merged
+}
+
+func splitLayers(ctx context.Context, fsys apkfs.FullFS, groups []*group, tmpdir string) ([]v1.Layer, error) {
+	buf := make([]byte, 1<<20)
+
+	// We'll create a writer for each layer and a map to quickly access the writer given a package or group.
+	packageToWriter := map[string]*layerWriter{}
+	groupToWriter := map[*group]*layerWriter{}
+
+	for _, g := range groups {
+		f, err := os.CreateTemp(tmpdir, "layer-*.tar.gz")
+		if err != nil {
+			return nil, err
+		}
+		defer f.Close()
+
+		w := newLayerWriter(f)
+		groupToWriter[g] = w
+
+		for _, pkg := range g.pkgs {
+			packageToWriter[pkg.Name] = w
+		}
+	}
+
+	// The top layer holds anything that doesn't belong to a package.
+	f, err := os.CreateTemp(tmpdir, "layer-*.tar.gz")
+	if err != nil {
+		return nil, err
+	}
+	defer f.Close()
+
+	top := newLayerWriter(f)
+
+	// In a tar file, it is customary to include directories before files in those directories.
+	// In order to know which directories we need to include, we maintain a directory stack for each layer.
+	// We compare those stacks to the full FS that we're walking whenever we create a new tar entry.
+	// If the main stack doesn't match the layer's stack, we update the layer's stack and add
+	// any missing directory entries to the layer before we write the actual file entry.
+	stack := []*file{}
+
+	for f, err := range walkFS(ctx, fsys) {
+		if err != nil {
+			return nil, err
+		}
+
+		// Maintain our "main" stack.
+		if f.header.Typeflag == tar.TypeDir {
+			// Pop off any directories that are not parents of the current file's directory.
+			for i := len(stack) - 1; i >= 0; i-- {
+				if stack[i].path == path.Dir(f.path) {
+					break
+				}
+
+				stack = stack[:i]
+			}
+
+			// Push the current file onto the stack.
+			stack = append(stack, f)
+		}
+
+		// By default, all files go into the top layer.
+		w := top
+
+		// However, if a file implements an extension interface that tells us what package owns it,
+		// we can use that to determine which layer it belongs to (if any).
+		if pkger, ok := f.info.(interface {
+			Package() *apk.Package
+		}); ok {
+			if pkg := pkger.Package(); pkg != nil {
+				w, ok = packageToWriter[pkg.Name]
+				if !ok {
+					panic(fmt.Errorf("packageToWriter[%q] missing", pkg.Name))
+				}
+			}
+		}
+
+		// As described above, bring the layer's stack up to date with the main stack.
+		for _, todo := range w.alignStacks(stack) {
+			// We need to write any missing directories returned by alignStacks.
+			// But sometimes the result of alignStacks will include the file we're
+			// about to write (f) after this loop. In those cases, make sure we
+			// don't write it twice by skipping over it here.
+			if todo.header == f.header {
+				continue
+			}
+
+			if err := w.w.WriteHeader(todo.header); err != nil {
+				return nil, fmt.Errorf("writing header %s: %w", todo.header.Name, err)
+			}
+		}
+
+		// Now we're back to normal tar stuff.
+		if err := w.w.WriteHeader(f.header); err != nil {
+			return nil, fmt.Errorf("writing header %s: %w", f.header.Name, err)
+		}
+
+		if f.header.Typeflag == tar.TypeReg && f.header.Size > 0 {
+			data, err := fsys.Open(f.path)
+			if err != nil {
+				return nil, fmt.Errorf("opening %s: %w", f.path, err)
+			}
+
+			if _, err := io.CopyBuffer(w.w, data, buf); err != nil {
+				return nil, fmt.Errorf("copying %s: %w", f.path, err)
+			}
+
+			// Should never fail in practice.
+			if err := data.Close(); err != nil {
+				return nil, fmt.Errorf("closing %s: %w", f.path, err)
+			}
+		}
+	}
+
+	// Once we're done walking the FS, we need to finalize each layer...
+	layers := make([]v1.Layer, 0, len(groups)+1)
+	for i, g := range groups {
+		w := groupToWriter[g]
+		l, err := w.finalize()
+		if err != nil {
+			return nil, fmt.Errorf("finalizing group[%d] layer: %w", i, err)
+		}
+		layers = append(layers, l)
+	}
+
+	// ...including the top layer.
+	topLayer, err := top.finalize()
+	if err != nil {
+		return nil, fmt.Errorf("finalizing top layer: %w", err)
+	}
+
+	layers = append(layers, topLayer)
+
+	return layers, nil
+}
+
+// alignStacks ensures that w.stack is aligned with the passed in "main" stack
+// by updating w.stack and returning any directories w hasn't already seen written.
+// This relies on the fact that WalkDir iterates in lexicographic order, so we will
+// only ever write a tar entry the first time we see a dir (for a given layer).
+//
+// Examples...
+//
+// stack:   [etc]
+// w.stack: []
+// return:  [etc]
+//
+// stack:   [usr, usr/lib]
+// w.stack: [etc, etc/apk, etc/apk/keys]
+// return:  [usr, usr/lib]
+//
+// stack:   [usr, usr/lib]
+// w.stack: [usr]
+// return:  [usr/lib]
+//
+// stack:   [usr, usr/lib]
+// w.stack: [usr, usr/bin]
+// return:  [usr/lib]
+
+// stack:   [usr, usr/lib]
+// w.stack: [usr, usr/lib, usr/lib/foo]
+// return:  []
+func (w *layerWriter) alignStacks(stack []*file) []*file {
+	for i := 0; i < max(len(w.stack), len(stack)); i++ {
+		// The layer's stack is taller than the main stack, truncate layer's stack.
+		if i >= len(stack) {
+			w.stack = w.stack[:i]
+			return nil
+		}
+
+		// Otherwise skip over any entries that are the same.
+		if i < len(w.stack) && w.stack[i] == stack[i] {
+			continue
+		}
+
+		// For anything left that's not the same, we'll truncate w.stack,
+		// then append the main stack and return the difference.
+		w.stack = w.stack[:i]
+		w.stack = append(w.stack, stack[i:]...)
+		return w.stack[i:]
+	}
+
+	return nil
+}
diff --git a/pkg/build/oci/image.go b/pkg/build/oci/image.go
index c1ab992..fcb6bf5 100644
--- a/pkg/build/oci/image.go
+++ b/pkg/build/oci/image.go
@@ -52,6 +52,12 @@ func BuildImageFromLayers(ctx context.Context, baseImage v1.Image, layers []v1.L
 		return nil, err
 	}
 
+	comment := "This is an apko single-layer image"
+	if len(layers) > 1 {
+		// TODO: Consider plumbing per-layer info here?
+		comment = ""
+	}
+
 	adds := make([]mutate.Addendum, 0, len(layers))
 	for _, layer := range layers {
 		digest, err := layer.Digest()
@@ -71,9 +77,9 @@ func BuildImageFromLayers(ctx context.Context, baseImage v1.Image, layers []v1.L
 			Layer: layer,
 			History: v1.History{
 				Author:    "apko",
-				Comment:   "This is an apko single-layer image", // TODO: Update this once we confirm no other changes.
+				Comment:   comment,
 				CreatedBy: "apko",
-				Created:   v1.Time{Time: created},
+				Created:   v1.Time{Time: created}, // TODO: Consider per-layer creation time?
 			},
 		})
 	}
@@ -153,7 +159,7 @@ func BuildImageFromLayers(ctx context.Context, baseImage v1.Image, layers []v1.L
 		env = map[string]string{}
 	}
 	for k, v := range map[string]string{
-		"PATH":          "/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin",
+		"PATH":          "/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin",
 		"SSL_CERT_FILE": "/etc/ssl/certs/ca-certificates.crt",
 	} {
 		if _, found := env[k]; !found {
diff --git a/pkg/build/sbom.go b/pkg/build/sbom.go
index 557bf13..331ecf8 100644
--- a/pkg/build/sbom.go
+++ b/pkg/build/sbom.go
@@ -95,14 +95,10 @@ func (bc *Context) GenerateImageSBOM(ctx context.Context, arch types.Architectur
 		return nil, fmt.Errorf("getting %s manifest: %w", arch, err)
 	}
 
-	if bc.baseimg == nil && len(m.Layers) != 1 {
-		return nil, fmt.Errorf("unexpected layers in %s manifest: %d", arch, len(m.Layers))
-	}
-
 	s := newSBOM(ctx, bc.fs, bc.o, bc.ic, bde)
 	log.Debug("Generating image SBOM")
 
-	s.ImageInfo.LayerDigest = m.Layers[0].Digest.String()
+	s.ImageInfo.Layers = m.Layers
 
 	info, err := readReleaseData(bc.fs)
 	if err != nil {
diff --git a/pkg/build/tarball.go b/pkg/build/tarball.go
new file mode 100644
index 0000000..50d3a06
--- /dev/null
+++ b/pkg/build/tarball.go
@@ -0,0 +1,188 @@
+// Copyright 2022, 2023 Chainguard, Inc.
+//
+// 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.
+
+package build
+
+import (
+	"archive/tar"
+	"context" //nolint:gosec
+	"fmt"
+	"io"
+	"io/fs"
+	"iter"
+	"os"
+
+	"go.opentelemetry.io/otel"
+	"golang.org/x/sys/unix"
+
+	apkfs "chainguard.dev/apko/pkg/apk/fs"
+	"chainguard.dev/apko/pkg/passwd"
+)
+
+const xattrTarPAXRecordsPrefix = "SCHILY.xattr."
+
+// writeTar writes a tarball to the provided io.Writer from the provided fs.FS.
+// The etc/passwd and etc/group file provide username and group name mappings for the tar.
+func writeTar(ctx context.Context, tw *tar.Writer, fsys apkfs.FullFS) error { //nolint:gocyclo
+	ctx, span := otel.Tracer("go-apk").Start(ctx, "writeTar")
+	defer span.End()
+
+	buf := make([]byte, 1<<20)
+
+	for f, err := range walkFS(ctx, fsys) {
+		if err != nil {
+			return err
+		}
+		if err := tw.WriteHeader(f.header); err != nil {
+			return err
+		}
+
+		if f.info.Mode().IsRegular() && f.header.Size > 0 {
+			data, err := fsys.Open(f.path)
+			if err != nil {
+				return err
+			}
+			defer data.Close()
+
+			if _, err := io.CopyBuffer(tw, data, buf); err != nil {
+				return err
+			}
+		}
+	}
+
+	if err := tw.Close(); err != nil {
+		return fmt.Errorf("closing tar writer: %w", err)
+	}
+	return nil
+}
+
+// file holds all the info we need to yield from walkFS.
+//
+// We need both Header and info because the fs.DirEntry.Info()
+// implementation is controlled by our tarfs implementation,
+// and we use that as a sidechannel to propagate package ownership.
+type file struct {
+	path   string
+	info   fs.FileInfo
+	header *tar.Header
+}
+
+func walkFS(ctx context.Context, fsys apkfs.FullFS) iter.Seq2[*file, error] {
+	return func(yield func(*file, error) bool) {
+		usersFile, _ := passwd.ReadUserFile(fsys, "etc/passwd")
+		groupsFile, _ := passwd.ReadGroupFile(fsys, "etc/group")
+		users := map[int]string{}
+		groups := map[int]string{}
+		for _, u := range usersFile.Entries {
+			users[int(u.UID)] = u.UserName
+		}
+		for _, g := range groupsFile.Entries {
+			groups[int(g.GID)] = g.GroupName
+		}
+
+		if err := fs.WalkDir(fsys, ".", func(path string, d fs.DirEntry, err error) error {
+			if err := ctx.Err(); err != nil {
+				return err
+			}
+			// skip the root path, superfluous
+			if path == "." {
+				return nil
+			}
+
+			if err != nil {
+				return err
+			}
+
+			info, err := d.Info()
+			if err != nil {
+				return err
+			}
+
+			var link string
+			if info.Mode()&os.ModeSymlink == os.ModeSymlink {
+				if link, err = fsys.Readlink(path); err != nil {
+					return err
+				}
+			}
+
+			header, err := tar.FileInfoHeader(info, link)
+			if err != nil {
+				return err
+			}
+
+			if info.Mode()&os.ModeCharDevice == os.ModeCharDevice {
+				dev, err := fsys.Readnod(path)
+				if err != nil {
+					return err
+				}
+				header.Devmajor = int64(unix.Major(uint64(dev)))
+				header.Devminor = int64(unix.Minor(uint64(dev)))
+			}
+
+			// tar.FileInfoHeader sets Name to the base name of the file,
+			// which is weird, because tar.Header.Name is the full path.
+			// In some cases, that does make sense, because fs.FileInfo.Name()
+			// is only the basename, but in tar.FileInfoHeader, it populates
+			// many of the fields based on the fs.FileInfo.Sys() method returning
+			// a tar.Header, which _does_ have the full path!
+			//
+			// Regardless, we want to override the name with the full path, here,
+			// because this path represents the full path _as written into this fs_,
+			// which might be different from the original tar.Header's full path.
+			header.Name = path
+
+			header.ModTime = info.ModTime()
+
+			if name, ok := users[header.Uid]; ok {
+				header.Uname = name
+			}
+			if name, ok := groups[header.Gid]; ok {
+				header.Gname = name
+			}
+
+			if link != "" {
+				header.Typeflag = tar.TypeSymlink
+			}
+
+			if header.PAXRecords == nil {
+				header.PAXRecords = map[string]string{}
+			}
+
+			// only capture xattrs for real objects in the FS
+			if header.Typeflag == tar.TypeReg || header.Typeflag == tar.TypeDir {
+				xattrs, err := fsys.ListXattrs(path)
+				// we can ignore errors
+				if err == nil && xattrs != nil {
+					for name, value := range xattrs {
+						header.PAXRecords[xattrTarPAXRecordsPrefix+name] = string(value)
+					}
+				}
+			}
+
+			if !yield(&file{
+				path:   path,
+				info:   info,
+				header: header,
+			}, nil) {
+				return fs.SkipAll
+			}
+
+			return nil
+		}); err != nil {
+			if !yield(nil, err) {
+				return
+			}
+		}
+	}
+}
diff --git a/pkg/build/types/image_configuration.go b/pkg/build/types/image_configuration.go
index b6b6f53..65d7b21 100644
--- a/pkg/build/types/image_configuration.go
+++ b/pkg/build/types/image_configuration.go
@@ -119,6 +119,9 @@ func (ic *ImageConfiguration) MergeInto(target *ImageConfiguration) error {
 	if target.WorkDir == "" {
 		target.WorkDir = ic.WorkDir
 	}
+	if target.Layering == nil {
+		target.Layering = ic.Layering
+	}
 	if len(target.Archs) == 0 {
 		target.Archs = ic.Archs
 	}
diff --git a/pkg/build/types/schema.json b/pkg/build/types/schema.json
index 6ba79e7..f652cf5 100644
--- a/pkg/build/types/schema.json
+++ b/pkg/build/types/schema.json
@@ -130,6 +130,10 @@
           },
           "type": "array",
           "description": "Optional: A list of volumes to configure\n\nThis is _not_ the same as Paths, but refers to the OCI spec \"volumes\"\nfield used by some container runtimes (docker) to create volumes at\nruntime. For most use cases, this is not needed, but consider using this\nwhen the image requires special volume configuration at runtime for\nsupported container runtimes."
+        },
+        "layering": {
+          "$ref": "#/$defs/Layering",
+          "description": "Experimental: Optional: Configuration to control layering of the OCI image."
         }
       },
       "additionalProperties": false,
@@ -197,6 +201,18 @@
       "additionalProperties": false,
       "type": "object"
     },
+    "Layering": {
+      "properties": {
+        "strategy": {
+          "type": "string"
+        },
+        "budget": {
+          "type": "integer"
+        }
+      },
+      "additionalProperties": false,
+      "type": "object"
+    },
     "PathMutation": {
       "properties": {
         "path": {
diff --git a/pkg/build/types/types.go b/pkg/build/types/types.go
index cb5b51b..68ac758 100644
--- a/pkg/build/types/types.go
+++ b/pkg/build/types/types.go
@@ -193,6 +193,9 @@ type ImageConfiguration struct {
 	// when the image requires special volume configuration at runtime for
 	// supported container runtimes.
 	Volumes []string `json:"volumes,omitempty" yaml:"volumes,omitempty"`
+
+	// Experimental: Optional: Configuration to control layering of the OCI image.
+	Layering *Layering `json:"layering,omitempty" yaml:"layering,omitempty" apko:"experimental"`
 }
 
 // Architecture represents a CPU architecture for the container image.
@@ -407,3 +410,8 @@ type SBOM struct {
 	Format string
 	Digest v1.Hash
 }
+
+type Layering struct {
+	Strategy string `json:"strategy,omitempty" yaml:"strategy,omitempty"`
+	Budget   int    `json:"budget,omitempty" yaml:"budget,omitempty"`
+}
diff --git a/pkg/sbom/generator/spdx/spdx.go b/pkg/sbom/generator/spdx/spdx.go
index 23c441f..f1fe895 100644
--- a/pkg/sbom/generator/spdx/spdx.go
+++ b/pkg/sbom/generator/spdx/spdx.go
@@ -25,6 +25,7 @@ import (
 	"unicode/utf8"
 
 	"github.com/charmbracelet/log"
+	v1 "github.com/google/go-containerregistry/pkg/v1"
 	purl "github.com/package-url/packageurl-go"
 	"sigs.k8s.io/release-utils/version"
 
@@ -71,13 +72,21 @@ func stringToIdentifier(in string) (out string) {
 	})
 }
 
+// Returns ":" otherwise :(
+func hashToString(h v1.Hash) string {
+	if h == (v1.Hash{}) {
+		return ""
+	}
+	return h.String()
+}
+
 // Generate writes an SPDX SBOM in path
 func (sx *SPDX) Generate(opts *options.Options, path string) error {
 	// The default document name makes no attempt to avoid
 	// clashes. Ensuring a unique name requires a digest
 	documentName := "sbom"
-	if opts.ImageInfo.LayerDigest != "" {
-		documentName += "-" + opts.ImageInfo.LayerDigest
+	if hash := hashToString(opts.ImageInfo.Layers[0].Digest); hash != "" {
+		documentName += "-" + hash
 	}
 	doc := &Document{
 		ID:      "SPDXRef-DOCUMENT",
@@ -97,21 +106,32 @@ func (sx *SPDX) Generate(opts *options.Options, path string) error {
 		Relationships:  []Relationship{},
 		LicensingInfos: []LicensingInfo{},
 	}
-	var imagePackage *Package
-	layerPackage := sx.layerPackage(opts)
-
-	doc.DocumentDescribes = []string{layerPackage.ID}
 
+	var imagePackage *Package
 	if opts.ImageInfo.ImageDigest != "" {
 		imagePackage = sx.imagePackage(opts)
-		doc.DocumentDescribes = []string{imagePackage.ID}
 		doc.Packages = append(doc.Packages, *imagePackage)
+	}
+
+	for _, layer := range opts.ImageInfo.Layers {
+		layerPackage := sx.layerPackage(opts, layer)
+
 		// Add to the relationships list
-		doc.Relationships = append(doc.Relationships, Relationship{
-			Element: imagePackage.ID,
-			Type:    "CONTAINS",
-			Related: layerPackage.ID,
-		})
+		if imagePackage != nil {
+			doc.Relationships = append(doc.Relationships, Relationship{
+				Element: imagePackage.ID,
+				Type:    "CONTAINS",
+				Related: layerPackage.ID,
+			})
+		} else {
+			doc.DocumentDescribes = []string{layerPackage.ID}
+		}
+
+		doc.Packages = append(doc.Packages, *layerPackage)
+	}
+
+	if imagePackage != nil {
+		doc.DocumentDescribes = []string{imagePackage.ID}
 	}
 
 	if opts.ImageInfo.VCSUrl != "" {
@@ -120,14 +140,26 @@ func (sx *SPDX) Generate(opts *options.Options, path string) error {
 		}
 	}
 
-	doc.Packages = append(doc.Packages, *layerPackage)
-
 	for _, pkg := range opts.Packages {
 		// add the package
 		p := sx.apkPackage(opts, pkg)
-		// Add the layer to the ID to avoid clashes
+
+		nonce := "thismakestestspass"
+
+		// Add the image ID to the package ID to avoid clashes.
+		// NB: imagePackage.ID here is actually not important.
+		// The important thing is that p.ID is different from the package ID we
+		// would find in the corresponding APK SBOM. The ProcessInternalApkSBOM
+		// logic does a "JOIN" against the APK SBOM and replaces references to
+		// this ID with references to the APK's SBOM's Package ID, which means
+		// that logic falls over if they match. Removing imagePackage.ID makes
+		// them match, so we have to have _something_. You could replace
+		// imagePackage.ID with a UUID or "" and this would still be correct.
+		if imagePackage != nil {
+			nonce = imagePackage.ID
+		}
 		p.ID = stringToIdentifier(fmt.Sprintf(
-			"SPDXRef-Package-%s-%s-%s", layerPackage.ID, pkg.Name, pkg.Version,
+			"SPDXRef-Package-%s-%s-%s", nonce, pkg.Name, pkg.Version,
 		))
 
 		doc.Packages = append(doc.Packages, p)
@@ -495,8 +527,8 @@ func (sx *SPDX) apkPackage(opts *options.Options, pkg *apk.InstalledPackage) Pac
 }
 
 // LayerPackage returns a package describing the layer
-func (sx *SPDX) layerPackage(opts *options.Options) *Package {
-	layerPackageName := opts.ImageInfo.LayerDigest
+func (sx *SPDX) layerPackage(opts *options.Options, layer v1.Descriptor) *Package {
+	layerPackageName := hashToString(layer.Digest)
 	mainPkgID := stringToIdentifier(layerPackageName)
 
 	return &Package{
@@ -514,9 +546,9 @@ func (sx *SPDX) layerPackage(opts *options.Options) *Package {
 				Category: ExtRefPackageManager,
 				Type:     ExtRefTypePurl,
 				Locator: purl.NewPackageURL(
-					purl.TypeOCI, "", opts.ImagePurlName(), opts.ImageInfo.LayerDigest,
+					purl.TypeOCI, "", opts.ImagePurlName(), hashToString(layer.Digest),
 					nil, "",
-				).String() + "?" + opts.LayerPurlQualifiers().String(),
+				).String() + "?" + opts.LayerPurlQualifiers(layer).String(),
 			},
 		},
 	}
diff --git a/pkg/sbom/options/options.go b/pkg/sbom/options/options.go
index a74a26f..1ed0033 100644
--- a/pkg/sbom/options/options.go
+++ b/pkg/sbom/options/options.go
@@ -68,8 +68,8 @@ type ImageInfo struct {
 	Tag             string
 	Name            string
 	Repository      string
-	LayerDigest     string
 	ImageDigest     string
+	Layers          []v1.Descriptor
 	VCSUrl          string
 	IndexMediaType  ggcrtypes.MediaType
 	ImageMediaType  ggcrtypes.MediaType
@@ -149,16 +149,9 @@ func (pq PurlQualifiers) String() string {
 
 // LayerPurlQualifiers reurns the qualifiers for the purl, they are based
 // on the image with the corresponding mediatype
-func (o *Options) LayerPurlQualifiers() (qualifiers PurlQualifiers) {
+func (o *Options) LayerPurlQualifiers(layer v1.Descriptor) (qualifiers PurlQualifiers) {
 	qualifiers = o.ImagePurlQualifiers()
-	switch o.ImageInfo.ImageMediaType {
-	case ggcrtypes.OCIManifestSchema1:
-		qualifiers["mediaType"] = string(ggcrtypes.OCILayer)
-	case ggcrtypes.DockerManifestSchema2:
-		qualifiers["mediaType"] = string(ggcrtypes.DockerLayer)
-	default:
-		qualifiers["mediaType"] = ""
-	}
+	qualifiers["mediaType"] = string(layer.MediaType)
 	return qualifiers
 }
 
diff --git a/pkg/tarfs/fs.go b/pkg/tarfs/fs.go
index 079dcec..c0a0073 100644
--- a/pkg/tarfs/fs.go
+++ b/pkg/tarfs/fs.go
@@ -1033,3 +1033,12 @@ func (m *memFileInfo) Sys() any {
 
 	return th
 }
+
+// This is a bit janky, but we need a way to know who owns this.
+func (m *memFileInfo) Package() *apk.Package {
+	if m.node.te == nil {
+		return nil
+	}
+
+	return m.node.te.pkg
+}


Test patch:
diff --git a/internal/cli/publish_test.go b/internal/cli/publish_test.go
index 8d73c6f..fed9831 100644
--- a/internal/cli/publish_test.go
+++ b/internal/cli/publish_test.go
@@ -91,7 +91,7 @@ func TestPublish(t *testing.T) {
 
 	// This test will fail if we ever make a change in apko that changes the image.
 	// Sometimes, this is intentional, and we need to change this and bump the version.
-	want := "sha256:df086c6b126032e9ed1b4aa6fecdb6988b45d86d9c1e8d2eb81dea647f4c7a7f"
+	want := "sha256:d560dbda76a5ebd8912e1ca149cd3ee6440d5c05c0d278c0159abf1ac3b31b2e"
 	require.Equal(t, want, digest.String())
 
 	sdst := fmt.Sprintf("%s:%s.sbom", dst, strings.ReplaceAll(want, ":", "-"))
@@ -109,7 +109,7 @@ func TestPublish(t *testing.T) {
 
 	// This test will fail if we ever make a change in apko that changes the SBOM.
 	// Sometimes, this is intentional, and we need to change this and bump the version.
-	swant := "sha256:d1faff2316aa480d1400e6c86af431402cee84f980b97a06f096bdab9a52075f"
+	swant := "sha256:37eb4a91f379b6af66e54c5e7a4c7abf7e6cd9f60e845eb281abbdca6fc41c2c"
 	require.Equal(t, swant, got)
 
 	im, err := idx.IndexManifest()
@@ -118,8 +118,8 @@ func TestPublish(t *testing.T) {
 	// We also want to check the children SBOMs because the index SBOM does not have
 	// references to the children SBOMs, just the children!
 	wantBoms := []string{
-		"sha256:c483478580314a253c2170b32de7686d1664ec936be3a4df51ef2bba92c46261",
-		"sha256:18d9c631ac5656d52d2595bc80195ad1c68c517db8bded1ec229f775ee682d98",
+		"sha256:beecfa84788ff5dbb05bce3554699fd0d2a5831f2a4cad5fcd56455d3531b2a8",
+		"sha256:8db959d01870f2d64d8ad84817368ae56e28b3c266d41e70c379620946b73688",
 	}
 
 	for i, m := range im.Manifests {
@@ -151,3 +151,74 @@ func (s *sentinel) RoundTrip(in *http.Request) (*http.Response, error) {
 	in.Header.Set("Magic", "SecretValue")
 	return s.rt.RoundTrip(in)
 }
+
+func TestPublishLayering(t *testing.T) {
+	ctx := context.Background()
+	tmp := t.TempDir()
+
+	// Set up a registry that requires we see a magic header.
+	// This allows us to make sure that remote options are getting passed
+	// around to anything that hits the registry.
+	r := registry.New()
+	h := http.HandlerFunc(func(w http.ResponseWriter, req *http.Request) {
+		require.Equal(t, req.Header.Get("Magic"), "SecretValue")
+		r.ServeHTTP(w, req)
+	})
+	s := httptest.NewServer(h)
+	defer s.Close()
+	u, err := url.Parse(s.URL)
+	require.NoError(t, err)
+
+	st := &sentinel{s.Client().Transport}
+	dst := fmt.Sprintf("%s/test/publish", u.Host)
+
+	config := filepath.Join("testdata", "layering.yaml")
+
+	outputRefs := ""
+	archs := types.ParseArchitectures([]string{"amd64", "arm64"})
+	ropt := []remote.Option{remote.WithTransport(st)}
+	opts := []build.Option{
+		build.WithConfig(config, []string{}),
+		build.WithTags(dst),
+		build.WithSBOMFormats(sbom.DefaultOptions.Formats),
+		build.WithAnnotations(map[string]string{"foo": "bar"}),
+	}
+	publishOpts := []cli.PublishOption{cli.WithTags(dst)}
+
+	sbomPath := filepath.Join(tmp, "sboms")
+	err = os.MkdirAll(sbomPath, 0o750)
+	require.NoError(t, err)
+
+	err = cli.PublishCmd(ctx, outputRefs, archs, ropt, sbomPath, opts, publishOpts)
+	require.NoError(t, err)
+
+	ref, err := name.ParseReference(dst)
+	require.NoError(t, err)
+
+	idx, err := remote.Index(ref, ropt...)
+	require.NoError(t, err)
+
+	// Not strictly necessary, but this will validate that the index is well-formed.
+	require.NoError(t, validate.Index(idx))
+
+	digest, err := idx.Digest()
+	require.NoError(t, err)
+
+	// This test will fail if we ever make a change in apko that changes the image.
+	// Sometimes, this is intentional, and we need to change this and bump the version.
+	want := "sha256:e4854bdd74aca1534a30da899edef2ad46b9a7e088ceae2094d85a287a20891a"
+	require.Equal(t, want, digest.String())
+
+	im, err := idx.IndexManifest()
+	require.NoError(t, err)
+
+	for _, m := range im.Manifests {
+		child, err := idx.Image(m.Digest)
+		require.NoError(t, err)
+
+		cm, err := child.Manifest()
+		require.NoError(t, err)
+
+		require.Equal(t, 2, len(cm.Layers))
+	}
+}
diff --git a/pkg/apk/tarball/testdata/bar/bar.txt b/internal/cli/testdata/bar/bar.txt
similarity index 100%
rename from pkg/apk/tarball/testdata/bar/bar.txt
rename to internal/cli/testdata/bar/bar.txt
diff --git a/pkg/apk/tarball/testdata/foo/foo.txt b/internal/cli/testdata/foo/foo.txt
similarity index 100%
rename from pkg/apk/tarball/testdata/foo/foo.txt
rename to internal/cli/testdata/foo/foo.txt
diff --git a/internal/cli/testdata/golden/blobs/sha256/0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea b/internal/cli/testdata/golden/blobs/sha256/265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a
similarity index 67%
rename from internal/cli/testdata/golden/blobs/sha256/0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea
rename to internal/cli/testdata/golden/blobs/sha256/265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a
index fb6d92e..18f9603 100644
--- a/internal/cli/testdata/golden/blobs/sha256/0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea
+++ b/internal/cli/testdata/golden/blobs/sha256/265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a
@@ -1,1 +1,1 @@
-{"schemaVersion":2,"mediaType":"application/vnd.oci.image.manifest.v1+json","config":{"mediaType":"application/vnd.oci.image.config.v1+json","size":593,"digest":"sha256:5e0be8f8dbc1497d60148df3be08869342df17c951370416999e19cda0d36624"},"layers":[{"mediaType":"application/vnd.oci.image.layer.v1.tar+gzip","size":3272,"digest":"sha256:89c9e3bd4d4968247bdf82182560718f22427628a3c112902377fa7ff897f9f7"}],"annotations":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}
\ No newline at end of file
+{"schemaVersion":2,"mediaType":"application/vnd.oci.image.manifest.v1+json","config":{"mediaType":"application/vnd.oci.image.config.v1+json","size":593,"digest":"sha256:b6a1c21a1f4d0acb07d009f1575fdb08493e5b7c52be31516a5dd3f2944abd4a"},"layers":[{"mediaType":"application/vnd.oci.image.layer.v1.tar+gzip","size":3272,"digest":"sha256:89c9e3bd4d4968247bdf82182560718f22427628a3c112902377fa7ff897f9f7"}],"annotations":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}
\ No newline at end of file
diff --git a/internal/cli/testdata/golden/blobs/sha256/cff7a34bf75690ef289b741fd026cb52cac94ff0f057996c829ac546f6819c75 b/internal/cli/testdata/golden/blobs/sha256/9bccf6af34ef37de4434628c487e0492e3b6411627be773b921e64a4ef5fd65d
similarity index 75%
rename from internal/cli/testdata/golden/blobs/sha256/cff7a34bf75690ef289b741fd026cb52cac94ff0f057996c829ac546f6819c75
rename to internal/cli/testdata/golden/blobs/sha256/9bccf6af34ef37de4434628c487e0492e3b6411627be773b921e64a4ef5fd65d
index 45e4124..6fb029c 100644
--- a/internal/cli/testdata/golden/blobs/sha256/cff7a34bf75690ef289b741fd026cb52cac94ff0f057996c829ac546f6819c75
+++ b/internal/cli/testdata/golden/blobs/sha256/9bccf6af34ef37de4434628c487e0492e3b6411627be773b921e64a4ef5fd65d
@@ -1,1 +1,1 @@
-{"architecture":"arm64","author":"github.com/chainguard-dev/apko","created":"1970-01-01T00:00:00Z","history":[{"author":"apko","created":"1970-01-01T00:00:00Z","created_by":"apko","comment":"This is an apko single-layer image"}],"os":"linux","rootfs":{"type":"layers","diff_ids":["sha256:ae5eac0428855226d637f784d90664e537cb40a42871dc7e58daabf93cfe86ca"]},"config":{"Entrypoint":["/bin/sh","-l"],"Env":["PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin","SSL_CERT_FILE=/etc/ssl/certs/ca-certificates.crt"],"Labels":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}}
\ No newline at end of file
+{"architecture":"arm64","author":"github.com/chainguard-dev/apko","created":"1970-01-01T00:00:00Z","history":[{"author":"apko","created":"1970-01-01T00:00:00Z","created_by":"apko","comment":"This is an apko single-layer image"}],"os":"linux","rootfs":{"type":"layers","diff_ids":["sha256:ae5eac0428855226d637f784d90664e537cb40a42871dc7e58daabf93cfe86ca"]},"config":{"Entrypoint":["/bin/sh","-l"],"Env":["PATH=/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin","SSL_CERT_FILE=/etc/ssl/certs/ca-certificates.crt"],"Labels":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}}
\ No newline at end of file
diff --git a/internal/cli/testdata/golden/blobs/sha256/5e0be8f8dbc1497d60148df3be08869342df17c951370416999e19cda0d36624 b/internal/cli/testdata/golden/blobs/sha256/b6a1c21a1f4d0acb07d009f1575fdb08493e5b7c52be31516a5dd3f2944abd4a
similarity index 75%
rename from internal/cli/testdata/golden/blobs/sha256/5e0be8f8dbc1497d60148df3be08869342df17c951370416999e19cda0d36624
rename to internal/cli/testdata/golden/blobs/sha256/b6a1c21a1f4d0acb07d009f1575fdb08493e5b7c52be31516a5dd3f2944abd4a
index 3f08755..15faf11 100644
--- a/internal/cli/testdata/golden/blobs/sha256/5e0be8f8dbc1497d60148df3be08869342df17c951370416999e19cda0d36624
+++ b/internal/cli/testdata/golden/blobs/sha256/b6a1c21a1f4d0acb07d009f1575fdb08493e5b7c52be31516a5dd3f2944abd4a
@@ -1,1 +1,1 @@
-{"architecture":"amd64","author":"github.com/chainguard-dev/apko","created":"1970-01-01T00:00:00Z","history":[{"author":"apko","created":"1970-01-01T00:00:00Z","created_by":"apko","comment":"This is an apko single-layer image"}],"os":"linux","rootfs":{"type":"layers","diff_ids":["sha256:8f9c734d8ec1cd189067042886090e052d1e32c6622124061dd7baf8be1c1e56"]},"config":{"Entrypoint":["/bin/sh","-l"],"Env":["PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin","SSL_CERT_FILE=/etc/ssl/certs/ca-certificates.crt"],"Labels":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}}
\ No newline at end of file
+{"architecture":"amd64","author":"github.com/chainguard-dev/apko","created":"1970-01-01T00:00:00Z","history":[{"author":"apko","created":"1970-01-01T00:00:00Z","created_by":"apko","comment":"This is an apko single-layer image"}],"os":"linux","rootfs":{"type":"layers","diff_ids":["sha256:8f9c734d8ec1cd189067042886090e052d1e32c6622124061dd7baf8be1c1e56"]},"config":{"Entrypoint":["/bin/sh","-l"],"Env":["PATH=/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin","SSL_CERT_FILE=/etc/ssl/certs/ca-certificates.crt"],"Labels":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}}
\ No newline at end of file
diff --git a/internal/cli/testdata/golden/blobs/sha256/2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7 b/internal/cli/testdata/golden/blobs/sha256/f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b
similarity index 67%
rename from internal/cli/testdata/golden/blobs/sha256/2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7
rename to internal/cli/testdata/golden/blobs/sha256/f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b
index 13030a9..8fbdee4 100644
--- a/internal/cli/testdata/golden/blobs/sha256/2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7
+++ b/internal/cli/testdata/golden/blobs/sha256/f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b
@@ -1,1 +1,1 @@
-{"schemaVersion":2,"mediaType":"application/vnd.oci.image.manifest.v1+json","config":{"mediaType":"application/vnd.oci.image.config.v1+json","size":593,"digest":"sha256:cff7a34bf75690ef289b741fd026cb52cac94ff0f057996c829ac546f6819c75"},"layers":[{"mediaType":"application/vnd.oci.image.layer.v1.tar+gzip","size":3273,"digest":"sha256:fab53f6bbeb155d8f33acb6e7a1d961317ffb6352fc775b133b1af8656a6d0bb"}],"annotations":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}
\ No newline at end of file
+{"schemaVersion":2,"mediaType":"application/vnd.oci.image.manifest.v1+json","config":{"mediaType":"application/vnd.oci.image.config.v1+json","size":593,"digest":"sha256:9bccf6af34ef37de4434628c487e0492e3b6411627be773b921e64a4ef5fd65d"},"layers":[{"mediaType":"application/vnd.oci.image.layer.v1.tar+gzip","size":3273,"digest":"sha256:fab53f6bbeb155d8f33acb6e7a1d961317ffb6352fc775b133b1af8656a6d0bb"}],"annotations":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}
\ No newline at end of file
diff --git a/internal/cli/testdata/golden/index.json b/internal/cli/testdata/golden/index.json
index 24596be..cfdaffd 100755
--- a/internal/cli/testdata/golden/index.json
+++ b/internal/cli/testdata/golden/index.json
@@ -1,1 +1,1 @@
-{"schemaVersion":2,"mediaType":"application/vnd.oci.image.index.v1+json","manifests":[{"mediaType":"application/vnd.oci.image.manifest.v1+json","size":476,"digest":"sha256:0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea","platform":{"architecture":"amd64","os":"linux"}},{"mediaType":"application/vnd.oci.image.manifest.v1+json","size":476,"digest":"sha256:2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7","platform":{"architecture":"arm64","os":"linux"}}],"annotations":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}
\ No newline at end of file
+{"schemaVersion":2,"mediaType":"application/vnd.oci.image.index.v1+json","manifests":[{"mediaType":"application/vnd.oci.image.manifest.v1+json","size":476,"digest":"sha256:265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a","platform":{"architecture":"amd64","os":"linux"}},{"mediaType":"application/vnd.oci.image.manifest.v1+json","size":476,"digest":"sha256:f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b","platform":{"architecture":"arm64","os":"linux"}}],"annotations":{"org.opencontainers.image.created":"1970-01-01T00:00:00Z"}}
\ No newline at end of file
diff --git a/internal/cli/testdata/golden/sboms/sbom-aarch64.spdx.json b/internal/cli/testdata/golden/sboms/sbom-aarch64.spdx.json
index 1b8787c..0e89b2a 100644
--- a/internal/cli/testdata/golden/sboms/sbom-aarch64.spdx.json
+++ b/internal/cli/testdata/golden/sboms/sbom-aarch64.spdx.json
@@ -13,13 +13,13 @@
   "dataLicense": "CC0-1.0",
   "documentNamespace": "https://spdx.org/spdxdocs/apko/",
   "documentDescribes": [
-    "SPDXRef-Package-sha256-2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7"
+    "SPDXRef-Package-sha256-f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b"
   ],
   "packages": [
     {
-      "SPDXID": "SPDXRef-Package-sha256-2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7",
-      "name": "sha256:2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7",
-      "versionInfo": "sha256:2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7",
+      "SPDXID": "SPDXRef-Package-sha256-f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b",
+      "name": "sha256:f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b",
+      "versionInfo": "sha256:f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b",
       "filesAnalyzed": false,
       "description": "apko container image",
       "downloadLocation": "NOASSERTION",
@@ -28,13 +28,13 @@
       "checksums": [
         {
           "algorithm": "SHA256",
-          "checksumValue": "2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7"
+          "checksumValue": "f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b"
         }
       ],
       "externalRefs": [
         {
           "referenceCategory": "PACKAGE-MANAGER",
-          "referenceLocator": "pkg:oci/golden@sha256%3A2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7?arch=arm64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
+          "referenceLocator": "pkg:oci/golden@sha256%3Af01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b?arch=arm64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
           "referenceType": "purl"
         }
       ]
@@ -96,7 +96,7 @@
   ],
   "relationships": [
     {
-      "spdxElementId": "SPDXRef-Package-sha256-2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7",
+      "spdxElementId": "SPDXRef-Package-sha256-f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b",
       "relationshipType": "CONTAINS",
       "relatedSpdxElement": "SPDXRef-Package-sha256-fab53f6bbeb155d8f33acb6e7a1d961317ffb6352fc775b133b1af8656a6d0bb"
     }
diff --git a/internal/cli/testdata/golden/sboms/sbom-index.spdx.json b/internal/cli/testdata/golden/sboms/sbom-index.spdx.json
index a3be7ab..1a6d10a 100644
--- a/internal/cli/testdata/golden/sboms/sbom-index.spdx.json
+++ b/internal/cli/testdata/golden/sboms/sbom-index.spdx.json
@@ -1,6 +1,6 @@
 {
   "SPDXID": "SPDXRef-DOCUMENT",
-  "name": "sbom-sha256:8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544",
+  "name": "sbom-sha256:c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043",
   "spdxVersion": "SPDX-2.3",
   "creationInfo": {
     "created": "1970-01-01T00:00:00Z",
@@ -13,13 +13,13 @@
   "dataLicense": "CC0-1.0",
   "documentNamespace": "https://spdx.org/spdxdocs/apko/",
   "documentDescribes": [
-    "SPDXRef-Package-sha256-8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544"
+    "SPDXRef-Package-sha256-c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043"
   ],
   "packages": [
     {
-      "SPDXID": "SPDXRef-Package-sha256-8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544",
-      "name": "sha256:8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544",
-      "versionInfo": "sha256:8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544",
+      "SPDXID": "SPDXRef-Package-sha256-c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043",
+      "name": "sha256:c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043",
+      "versionInfo": "sha256:c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043",
       "filesAnalyzed": false,
       "description": "Multi-arch image index",
       "downloadLocation": "NOASSERTION",
@@ -29,21 +29,21 @@
       "checksums": [
         {
           "algorithm": "SHA256",
-          "checksumValue": "8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544"
+          "checksumValue": "c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043"
         }
       ],
       "externalRefs": [
         {
           "referenceCategory": "PACKAGE-MANAGER",
-          "referenceLocator": "pkg:oci/golden@sha256%3A8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544?mediaType=application%2Fvnd.oci.image.index.v1%2Bjson",
+          "referenceLocator": "pkg:oci/golden@sha256%3Ac293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043?mediaType=application%2Fvnd.oci.image.index.v1%2Bjson",
           "referenceType": "purl"
         }
       ]
     },
     {
-      "SPDXID": "SPDXRef-Package-sha256-0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea",
-      "name": "sha256:0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea",
-      "versionInfo": "sha256:0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea",
+      "SPDXID": "SPDXRef-Package-sha256-265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a",
+      "name": "sha256:265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a",
+      "versionInfo": "sha256:265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a",
       "filesAnalyzed": false,
       "downloadLocation": "NOASSERTION",
       "supplier": "Organization: Chainguard, Inc.",
@@ -51,21 +51,21 @@
       "checksums": [
         {
           "algorithm": "SHA256",
-          "checksumValue": "0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea"
+          "checksumValue": "265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a"
         }
       ],
       "externalRefs": [
         {
           "referenceCategory": "PACKAGE-MANAGER",
-          "referenceLocator": "pkg:oci/golden@sha256%3A0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea?arch=amd64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
+          "referenceLocator": "pkg:oci/golden@sha256%3A265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a?arch=amd64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
           "referenceType": "purl"
         }
       ]
     },
     {
-      "SPDXID": "SPDXRef-Package-sha256-2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7",
-      "name": "sha256:2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7",
-      "versionInfo": "sha256:2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7",
+      "SPDXID": "SPDXRef-Package-sha256-f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b",
+      "name": "sha256:f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b",
+      "versionInfo": "sha256:f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b",
       "filesAnalyzed": false,
       "downloadLocation": "NOASSERTION",
       "supplier": "Organization: Chainguard, Inc.",
@@ -73,13 +73,13 @@
       "checksums": [
         {
           "algorithm": "SHA256",
-          "checksumValue": "2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7"
+          "checksumValue": "f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b"
         }
       ],
       "externalRefs": [
         {
           "referenceCategory": "PACKAGE-MANAGER",
-          "referenceLocator": "pkg:oci/golden@sha256%3A2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7?arch=arm64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
+          "referenceLocator": "pkg:oci/golden@sha256%3Af01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b?arch=arm64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
           "referenceType": "purl"
         }
       ]
@@ -87,14 +87,14 @@
   ],
   "relationships": [
     {
-      "spdxElementId": "SPDXRef-Package-sha256-8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544",
+      "spdxElementId": "SPDXRef-Package-sha256-c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043",
       "relationshipType": "VARIANT_OF",
-      "relatedSpdxElement": "SPDXRef-Package-sha256-0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea"
+      "relatedSpdxElement": "SPDXRef-Package-sha256-265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a"
     },
     {
-      "spdxElementId": "SPDXRef-Package-sha256-8d9ac8b5cdf43d1d65837f5c947c2ef573ba65bffa9c41aa86afefb5fcd72544",
+      "spdxElementId": "SPDXRef-Package-sha256-c293300dab5afc3a936f462302aa7f5c788383ab5a5715a9506ed2fde68de043",
       "relationshipType": "VARIANT_OF",
-      "relatedSpdxElement": "SPDXRef-Package-sha256-2daa2a0b7c784bbda06b9a342d2b70e72d4f213642f488250fdb62ccd65a4ba7"
+      "relatedSpdxElement": "SPDXRef-Package-sha256-f01f5d7403958377a306ba0295cfd092e58d5e4bca12c0245df51d1a6cace72b"
     }
   ]
 }
diff --git a/internal/cli/testdata/golden/sboms/sbom-x86_64.spdx.json b/internal/cli/testdata/golden/sboms/sbom-x86_64.spdx.json
index aa2762b..419d79b 100644
--- a/internal/cli/testdata/golden/sboms/sbom-x86_64.spdx.json
+++ b/internal/cli/testdata/golden/sboms/sbom-x86_64.spdx.json
@@ -13,13 +13,13 @@
   "dataLicense": "CC0-1.0",
   "documentNamespace": "https://spdx.org/spdxdocs/apko/",
   "documentDescribes": [
-    "SPDXRef-Package-sha256-0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea"
+    "SPDXRef-Package-sha256-265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a"
   ],
   "packages": [
     {
-      "SPDXID": "SPDXRef-Package-sha256-0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea",
-      "name": "sha256:0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea",
-      "versionInfo": "sha256:0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea",
+      "SPDXID": "SPDXRef-Package-sha256-265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a",
+      "name": "sha256:265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a",
+      "versionInfo": "sha256:265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a",
       "filesAnalyzed": false,
       "description": "apko container image",
       "downloadLocation": "NOASSERTION",
@@ -28,13 +28,13 @@
       "checksums": [
         {
           "algorithm": "SHA256",
-          "checksumValue": "0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea"
+          "checksumValue": "265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a"
         }
       ],
       "externalRefs": [
         {
           "referenceCategory": "PACKAGE-MANAGER",
-          "referenceLocator": "pkg:oci/golden@sha256%3A0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea?arch=amd64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
+          "referenceLocator": "pkg:oci/golden@sha256%3A265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a?arch=amd64\u0026mediaType=application%2Fvnd.oci.image.manifest.v1%2Bjson\u0026os=linux",
           "referenceType": "purl"
         }
       ]
@@ -96,7 +96,7 @@
   ],
   "relationships": [
     {
-      "spdxElementId": "SPDXRef-Package-sha256-0c3a3431cb3d08f1de9b3ebd19671fe54c227a6cfd33c1164cb8f67a86baadea",
+      "spdxElementId": "SPDXRef-Package-sha256-265ff2e0ff15a1cffd0d9dfd0a56357fa991441d148a18430e74a5d920ee312a",
       "relationshipType": "CONTAINS",
       "relatedSpdxElement": "SPDXRef-Package-sha256-89c9e3bd4d4968247bdf82182560718f22427628a3c112902377fa7ff897f9f7"
     }
diff --git a/internal/cli/testdata/layering.yaml b/internal/cli/testdata/layering.yaml
new file mode 100644
index 0000000..4b7b66c
--- /dev/null
+++ b/internal/cli/testdata/layering.yaml
@@ -0,0 +1,18 @@
+contents:
+  keyring:
+    - ./testdata/melange.rsa.pub
+  repositories:
+    - ./testdata/packages
+  packages:
+    - replayout
+
+entrypoint:
+  command: /bin/sh -l
+
+archs:
+- x86_64
+- aarch64
+
+layering:
+  strategy: origin
+  budget: 2
diff --git a/pkg/apk/apk/install_test.go b/pkg/apk/apk/install_test.go
index d47975a..5eba3c7 100644
--- a/pkg/apk/apk/install_test.go
+++ b/pkg/apk/apk/install_test.go
@@ -171,7 +171,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0o755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.Error(t, err, "some double-write error")
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -200,7 +200,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -229,7 +229,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0o755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -257,7 +257,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0o755, false, originalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -286,7 +286,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
diff --git a/pkg/apk/apk/repo_test.go b/pkg/apk/apk/repo_test.go
index 146ae3b..60e18d8 100644
--- a/pkg/apk/apk/repo_test.go
+++ b/pkg/apk/apk/repo_test.go
@@ -870,6 +870,39 @@ func TestSameProvidedVersion(t *testing.T) {
 	}
 }
 
+// If a package has a provides with a different version than the real
+// package (here libcurl-openssl4=8.12.1-r1 provides libcurl-abi=8.12.1),
+// both should be allowed in the same DAG
+func TestDepWithProvidesOfDiffVersion(t *testing.T) {
+	providers := map[string][]string{
+		"libcurl-openssl4=8.12.1-r1": {
+			"libcurl-abi=8.12.1", "so:libcurl.so.4=4",
+		},
+	}
+	dependers := map[string][]string{
+		"foo=1":                      {}, // an extra dep level needed to trigger bug
+		"libcurl-openssl4=8.12.1-r1": {"foo"},
+		"curl=8.12.1-r1":             {"libcurl-abi=8.12.1", "so:libcurl.so.4"},
+		"curl-dev=8.12.1-r1":         {"so:libcurl.so.4"},
+	}
+
+	resolver := makeResolver(providers, dependers)
+	pkgs, _, err := resolver.GetPackagesWithDependencies(context.Background(), []string{"curl-dev", "curl"}, nil)
+	require.NoError(t, err)
+
+	wantPkgs := []string{
+		"foo-1.apk",
+		"libcurl-openssl4-8.12.1-r1.apk",
+		"curl-dev-8.12.1-r1.apk",
+		"curl-8.12.1-r1.apk",
+	}
+
+	require.Len(t, pkgs, len(wantPkgs))
+	for i, pkg := range pkgs {
+		require.Equal(t, pkg.Filename(), wantPkgs[i])
+	}
+}
+
 func TestHigherProvidedVersion(t *testing.T) {
 	providers := map[string][]string{
 		"ld-linux=2.38-r10": {"so:ld-linux-aarch64.so.1=1.1"},
@@ -954,12 +987,12 @@ func makeResolver(provs, deps map[string][]string) *PkgResolver {
 	packages := make(map[string]*Package, max(len(provs), len(deps)))
 
 	for pkgver := range provs {
-		parsed := resolvePackageNameVersionPin(pkgver)
-		packages[pkgver] = &Package{Name: parsed.name, Version: parsed.version}
+		parsed := ResolvePackageNameVersionPin(pkgver)
+		packages[pkgver] = &Package{Name: parsed.Name, Version: parsed.version}
 	}
 	for pkgver := range deps {
-		parsed := resolvePackageNameVersionPin(pkgver)
-		packages[pkgver] = &Package{Name: parsed.name, Version: parsed.version}
+		parsed := ResolvePackageNameVersionPin(pkgver)
+		packages[pkgver] = &Package{Name: parsed.Name, Version: parsed.version}
 	}
 
 	for pkgver, pkgProvs := range provs {
diff --git a/pkg/apk/apk/version_test.go b/pkg/apk/apk/version_test.go
index 1e99665..7edefa4 100644
--- a/pkg/apk/apk/version_test.go
+++ b/pkg/apk/apk/version_test.go
@@ -935,12 +935,14 @@ func TestResolverPackageNameVersionPin(t *testing.T) {
 		{"name<=1.2.3", "name", "1.2.3", versionLessEqual, ""},
 		{"name@edge=1.2.3", "name@edge=1.2.3", "", versionAny, ""}, // wrong order, so just returns the whole thing
 		{"name=1.2.3@community", "name", "1.2.3", versionEqual, "community"},
+		{"so:libfoo.so.6=6", "so:libfoo.so.6", "0.6", versionEqual, ""},
+		{"so:libfoo.so.6=1.0-r3", "so:libfoo.so.6", "1.0-r3", versionEqual, ""},
 	}
 
 	for _, tt := range tests {
 		t.Run(tt.input, func(t *testing.T) {
-			constraint := resolvePackageNameVersionPin(tt.input)
-			require.Equal(t, tt.name, constraint.name)
+			constraint := ResolvePackageNameVersionPin(tt.input)
+			require.Equal(t, tt.name, constraint.Name)
 			require.Equal(t, tt.version, constraint.version)
 			require.Equal(t, tt.dep, constraint.dep)
 			require.Equal(t, tt.pin, constraint.pin)
diff --git a/pkg/apk/passwd/group_test.go b/pkg/apk/passwd/group_test.go
deleted file mode 100644
index a48c05d..0000000
--- a/pkg/apk/passwd/group_test.go
+++ /dev/null
@@ -1,58 +0,0 @@
-// Copyright 2022, 2023 Chainguard, Inc.
-//
-// 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.
-
-package passwd
-
-import (
-	"bytes"
-	"testing"
-
-	"github.com/stretchr/testify/require"
-
-	apkfs "chainguard.dev/apko/pkg/apk/fs"
-)
-
-func TestGroupParser(t *testing.T) {
-	fsys := apkfs.DirFS("testdata")
-	gf, err := ReadOrCreateGroupFile(fsys, "group")
-	require.NoError(t, err)
-
-	for _, ge := range gf.Entries {
-		if ge.GID == 0 {
-			require.Equal(t, "root", ge.GroupName, "gid 0 is not root")
-		}
-
-		if ge.GID == 65534 {
-			require.Equal(t, "nobody", ge.GroupName, "gid 65534 is not nobody")
-		}
-	}
-}
-
-func TestGroupWriter(t *testing.T) {
-	fsys := apkfs.DirFS("testdata")
-	gf, err := ReadOrCreateGroupFile(fsys, "group")
-	require.NoError(t, err)
-
-	w := &bytes.Buffer{}
-	require.NoError(t, gf.Write(w))
-
-	r := bytes.NewReader(w.Bytes())
-	gf2 := &GroupFile{}
-	require.NoError(t, gf2.Load(r))
-
-	w2 := &bytes.Buffer{}
-	require.NoError(t, gf2.Write(w2))
-
-	require.Equal(t, w.Bytes(), w2.Bytes())
-}
diff --git a/pkg/apk/passwd/passwd_test.go b/pkg/apk/passwd/passwd_test.go
deleted file mode 100644
index 737d050..0000000
--- a/pkg/apk/passwd/passwd_test.go
+++ /dev/null
@@ -1,71 +0,0 @@
-// Copyright 2022, 2023 Chainguard, Inc.
-//
-// 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.
-
-package passwd
-
-import (
-	"bytes"
-	"os"
-	"testing"
-
-	"github.com/stretchr/testify/require"
-
-	apkfs "chainguard.dev/apko/pkg/apk/fs"
-)
-
-func TestParser(t *testing.T) {
-	fsys := apkfs.NewMemFS()
-	passwd, err := os.ReadFile("testdata/passwd")
-	require.NoError(t, err)
-	err = fsys.MkdirAll("etc", 0o755)
-	require.NoError(t, err)
-	err = fsys.WriteFile("etc/passwd", passwd, 0o600)
-	require.NoError(t, err)
-	uf, err := ReadOrCreateUserFile(fsys, "etc/passwd")
-	require.NoError(t, err)
-
-	for _, ue := range uf.Entries {
-		if ue.UID == 0 {
-			require.Equal(t, "root", ue.UserName, "uid 0 is not root")
-		}
-
-		if ue.UID == 65534 {
-			require.Equal(t, "nobody", ue.UserName, "uid 65534 is not nobody")
-		}
-	}
-}
-
-func TestWriter(t *testing.T) {
-	fsys := apkfs.NewMemFS()
-	passwd, err := os.ReadFile("testdata/passwd")
-	require.NoError(t, err)
-	err = fsys.MkdirAll("etc", 0o755)
-	require.NoError(t, err)
-	err = fsys.WriteFile("etc/passwd", passwd, 0o600)
-	require.NoError(t, err)
-	uf, err := ReadOrCreateUserFile(fsys, "etc/passwd")
-	require.NoError(t, err)
-
-	w := &bytes.Buffer{}
-	require.NoError(t, uf.Write(w))
-
-	r := bytes.NewReader(w.Bytes())
-	uf2 := &UserFile{}
-	require.NoError(t, uf2.Load(r))
-
-	w2 := &bytes.Buffer{}
-	require.NoError(t, uf2.Write(w2))
-
-	require.Equal(t, w.Bytes(), w2.Bytes())
-}
diff --git a/pkg/apk/passwd/testdata/group b/pkg/apk/passwd/testdata/group
deleted file mode 100644
index 13cc89f..0000000
--- a/pkg/apk/passwd/testdata/group
+++ /dev/null
@@ -1,54 +0,0 @@
-root:x:0:root
-bin:x:1:root,bin,daemon
-daemon:x:2:root,bin,daemon
-sys:x:3:root,bin,adm
-adm:x:4:root,adm,daemon
-tty:x:5:
-disk:x:6:root,adm
-lp:x:7:lp
-mem:x:8:
-kmem:x:9:
-wheel:x:10:root
-floppy:x:11:root
-mail:x:12:mail
-news:x:13:news
-uucp:x:14:uucp
-man:x:15:man
-cron:x:16:cron
-console:x:17:
-audio:x:18:
-cdrom:x:19:
-dialout:x:20:root
-ftp:x:21:
-sshd:x:22:
-at:x:25:at
-tape:x:26:root
-video:x:27:root
-netdev:x:28:
-readproc:x:30:
-squid:x:31:squid
-gdm:x:32:gdm
-xfs:x:33:xfs
-kvm:x:34:kvm
-games:x:35:
-named:x:40:named
-mysql:x:60:
-postgres:x:70:
-cdrw:x:80:
-apache:x:81:
-nut:x:84:
-usb:x:85:
-avahi:x:86:
-vpopmail:x:89:
-users:x:100:games
-ntp:x:123:
-nofiles:x:200:
-qmail:x:201:
-postfix:x:207:
-postdrop:x:208:
-smmsp:x:209:smmsp
-slocate:x:245:
-abuild:x:300:
-utmp:x:406:
-nogroup:x:65533:
-nobody:x:65534:
diff --git a/pkg/apk/passwd/testdata/passwd b/pkg/apk/passwd/testdata/passwd
deleted file mode 100644
index 55a6296..0000000
--- a/pkg/apk/passwd/testdata/passwd
+++ /dev/null
@@ -1,42 +0,0 @@
-root:x:0:0:root:/root:/bin/ash
-bin:x:1:1:bin:/bin:/bin/false
-daemon:x:2:2:daemon:/sbin:/bin/false
-adm:x:3:4:adm:/var/adm:/bin/false
-lp:x:4:7:lp:/var/spool/lpd:/bin/false
-sync:x:5:0:sync:/sbin:/bin/sync
-shutdown:x:6:0:shutdown:/sbin:/sbin/shutdown
-halt:x:7:0:halt:/sbin:/sbin/halt
-mail:x:8:12:mail:/var/spool/mail:/bin/false
-news:x:9:13:news:/usr/lib/news:/bin/false
-uucp:x:10:14:uucp:/var/spool/uucppublic:/bin/false
-operator:x:11:0:operator:/root:/bin/sh
-man:x:13:15:man:/usr/man:/bin/false
-postmaster:x:14:12:postmaster:/var/spool/mail:/bin/false
-cron:x:16:16:cron:/var/spool/cron:/bin/false
-ftp:x:21:21::/var/lib/ftp:/bin/false
-sshd:x:22:22:sshd:/dev/null:/bin/false
-at:x:25:25:at:/var/spool/cron/atjobs:/bin/false
-squid:x:31:31:Squid:/var/cache/squid:/bin/false
-gdm:x:32:32:GDM:/var/lib/gdm:/bin/false
-xfs:x:33:33:X Font Server:/etc/X11/fs:/bin/false
-games:x:35:35:games:/usr/games:/bin/false
-named:x:40:40:bind:/var/bind:/bin/false
-mysql:x:60:60:mysql:/var/lib/mysql:/bin/false
-postgres:x:70:70::/var/lib/postgresql:/bin/sh
-apache:x:81:81:apache:/var/www:/bin/false
-nut:x:84:84:nut:/var/state/nut:/bin/false
-cyrus:x:85:12::/usr/cyrus:/bin/false
-vpopmail:x:89:89::/var/vpopmail:/bin/false
-ntp:x:123:123:NTP:/var/empty:/bin/false
-alias:x:200:200::/var/qmail/alias:/bin/false
-qmaild:x:201:200::/var/qmail:/bin/false
-qmaill:x:202:200::/var/qmail:/bin/false
-qmailp:x:203:200::/var/qmail:/bin/false
-qmailq:x:204:201::/var/qmail:/bin/false
-qmailr:x:205:201::/var/qmail:/bin/false
-qmails:x:206:201::/var/qmail:/bin/false
-postfix:x:207:207:postfix:/var/spool/postfix:/bin/false
-smmsp:x:209:209:smmsp:/var/spool/mqueue:/bin/false
-guest:x:405:100:guest:/dev/null:/dev/null
-nobody:x:65534:65534:nobody:/:/bin/false
-distcc:x:240:2:distccd:/dev/null:/bin/false
diff --git a/pkg/build/build_test.go b/pkg/build/build_test.go
index c663cc1..388b6d8 100644
--- a/pkg/build/build_test.go
+++ b/pkg/build/build_test.go
@@ -30,7 +30,24 @@ import (
 	"chainguard.dev/apko/pkg/build/types"
 )
 
-func TestBuildLayer(t *testing.T) {
+func TestBuildLayers(t *testing.T) {
+	ctx := context.Background()
+
+	opts := []build.Option{
+		build.WithConfig("layering.yaml", []string{"testdata"}),
+	}
+
+	bc, err := build.New(ctx, fs.NewMemFS(), opts...)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	layers, err := bc.BuildLayers(ctx)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	require.Len(t, layers, 2)
 }
 
 func TestBuildImage(t *testing.T) {
diff --git a/pkg/build/layers_test.go b/pkg/build/layers_test.go
new file mode 100644
index 0000000..96ed748
--- /dev/null
+++ b/pkg/build/layers_test.go
@@ -0,0 +1,226 @@
+// Copyright 2025 Chainguard, Inc.
+//
+// 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.
+
+package build
+
+import (
+	"fmt"
+	"slices"
+	"testing"
+
+	"chainguard.dev/apko/pkg/apk/apk"
+)
+
+func size(pkgs ...*apk.Package) uint64 {
+	var total uint64
+	for _, pkg := range pkgs {
+		total += pkg.InstalledSize
+	}
+	return total
+}
+
+func TestGroupByOriginAndSize(t *testing.T) {
+	crane := &apk.Package{Name: "crane", Origin: "crane", InstalledSize: 100}
+
+	glibc := &apk.Package{Name: "glibc", Origin: "glibc", InstalledSize: 6113087}
+	posix := &apk.Package{Name: "glibc-locale-posix", Origin: "glibc", InstalledSize: 417444}
+
+	libcrypt1 := &apk.Package{Name: "libcrypt1", Origin: "glibc", Version: "2.38-r14", InstalledSize: 23508}
+	libxcrypt := &apk.Package{Name: "libxcrypt", Origin: "libxcrypt", InstalledSize: 235761, Replaces: []string{"libcrypt1<2.38-r15"}}
+
+	newcrypt1 := &apk.Package{Name: "libcrypt1", Origin: "glibc", Version: "2.38-r16", InstalledSize: 23508}
+
+	repxcrypt := &apk.Package{Name: "libxcrypt", Origin: "libxcrypt", InstalledSize: 235761, Replaces: []string{"libcrypt1"}}
+	for _, tc := range []struct {
+		pkgs   []*apk.Package
+		budget int
+		want   []*group
+		err    error
+	}{{
+		pkgs:   []*apk.Package{crane},
+		budget: 1,
+		want:   []*group{{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"}},
+	}, {
+		// glibc and glibc-locale-posix should be grouped by origin
+		pkgs:   []*apk.Package{crane, glibc, posix},
+		budget: 2,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix}, size: size(glibc, posix), tiebreaker: "glibc-locale-posix"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// reasonable default if budget is unspecified
+		pkgs: []*apk.Package{crane, glibc, posix},
+		want: []*group{
+			{pkgs: []*apk.Package{crane, glibc, posix}, size: size(crane, glibc, posix), tiebreaker: "glibc-locale-posix"},
+		},
+	}, {
+		// libxcrypt replace libcrypt1, so it should be merged into the glibc origin
+		pkgs:   []*apk.Package{crane, glibc, posix, libcrypt1, libxcrypt},
+		budget: 5,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, libcrypt1, libxcrypt}, size: size(glibc, libcrypt1, libxcrypt, posix), tiebreaker: "libxcrypt"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// libxcrypt replaces does not match the version constraint for "newcrypt1", so it doesn't get merged.
+		pkgs:   []*apk.Package{crane, glibc, posix, newcrypt1, libxcrypt},
+		budget: 5,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, newcrypt1}, size: size(glibc, newcrypt1, posix), tiebreaker: "libcrypt1"},
+			{pkgs: []*apk.Package{libxcrypt}, size: size(libxcrypt), tiebreaker: "libxcrypt"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// "repxcrypt" replaces has no version, so it _does_ merge with "newcrypt1".
+		pkgs:   []*apk.Package{crane, glibc, posix, newcrypt1, repxcrypt},
+		budget: 5,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, newcrypt1, repxcrypt}, size: size(glibc, newcrypt1, posix, repxcrypt), tiebreaker: "libxcrypt"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// should be 3 groups but budget constricts that to 2
+		pkgs:   []*apk.Package{crane, glibc, posix, newcrypt1, libxcrypt},
+		budget: 2,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, newcrypt1}, size: size(glibc, newcrypt1, posix), tiebreaker: "libcrypt1"},
+			{pkgs: []*apk.Package{crane, libxcrypt}, size: size(crane, libxcrypt), tiebreaker: "libxcrypt"},
+		},
+	}} {
+		got, err := groupByOriginAndSize(tc.pkgs, tc.budget)
+		if err != nil && tc.err != nil {
+			continue
+		}
+
+		if err != nil && tc.err == nil {
+			t.Errorf("groupByOriginAndSize(%v, %d) unexpected error: %v", tc.pkgs, tc.budget, err)
+		} else if err == nil && tc.err != nil {
+			t.Errorf("groupByOriginAndSize(%v, %d) expected error: %v", tc.pkgs, tc.budget, tc.err)
+		}
+
+		if err := compareGroups(got, tc.want); err != nil {
+			t.Errorf("groupByOriginAndSize(%v, %d) mismatch: %v", tc.pkgs, tc.budget, err)
+
+			for i, g := range got {
+				t.Logf("got[%d]: %v", i, g.pkgs)
+			}
+			for i, g := range tc.want {
+				t.Logf("want[%d]: %v", i, g.pkgs)
+			}
+		}
+	}
+}
+
+func compareGroups(a, b []*group) error {
+	if len(a) != len(b) {
+		return fmt.Errorf("len(a) = %d; len(b) = %d", len(a), len(b))
+	}
+	for i := range a {
+		aa, bb := a[i], b[i]
+		if len(aa.pkgs) != len(bb.pkgs) {
+			return fmt.Errorf("len(a[%d].pkgs) = %d; len(b[%d].pkgs) = %d", i, len(aa.pkgs), i, len(bb.pkgs))
+		}
+
+		for j := range aa.pkgs {
+			if aa.pkgs[j].Name != bb.pkgs[j].Name {
+				return fmt.Errorf("a[%d].pkgs[%d] = %s; b[%d].pkgs[%d] = %s", i, j, aa.pkgs[j].Name, i, j, bb.pkgs[j].Name)
+			}
+		}
+
+		if aa.size != bb.size {
+			return fmt.Errorf("a[%d].size = %d; b[%d].size = %d", i, aa.size, i, bb.size)
+		}
+		if aa.tiebreaker != bb.tiebreaker {
+			return fmt.Errorf("a[%d].tiebreaker = %s; b[%d].tiebreaker = %s", i, aa.tiebreaker, i, bb.tiebreaker)
+		}
+	}
+
+	return nil
+}
+
+func TestAlignStacks(t *testing.T) {
+	usr := []*file{{
+		path: "usr",
+	}, {
+		path: "usr/lib",
+	}}
+	etc := []*file{{
+		path: "etc",
+	}, {
+		path: "etc/apk",
+	}, {
+		path: "etc/apk/key",
+	}}
+	for i, tc := range []struct {
+		stack  []*file
+		before []*file
+		diff   []*file
+		after  []*file
+	}{{
+		stack:  usr,
+		before: usr,
+		after:  usr,
+	}, {
+		stack: usr,
+		after: usr,
+		diff:  usr,
+	}, {
+		stack:  usr,
+		before: etc,
+		after:  usr,
+		diff:   usr,
+	}, {
+		stack:  etc,
+		before: usr,
+		after:  etc,
+		diff:   etc,
+	}, {
+		stack:  etc[:2],
+		before: etc,
+		after:  etc[:2],
+	}, {
+		stack:  etc,
+		before: etc[:2],
+		after:  etc,
+		diff:   etc[2:],
+	}} {
+		t.Run(fmt.Sprintf("case_%d", i), func(t *testing.T) {
+			// clone to avoid mutating the usr and etc slices directly
+			w := &layerWriter{stack: slices.Clone(tc.before)}
+
+			if err := compareStacks(w.alignStacks(tc.stack), tc.diff); err != nil {
+				t.Errorf("alignStacks() mismatch: %v", err)
+			}
+			if err := compareStacks(w.stack, tc.after); err != nil {
+				t.Errorf("w.stack mismatch: %v", err)
+			}
+		})
+	}
+}
+
+// NB: this only cares about path
+func compareStacks(a, b []*file) error {
+	if len(a) != len(b) {
+		return fmt.Errorf("len(a) = %d; len(b) = %d", len(a), len(b))
+	}
+
+	for i := range len(a) {
+		if a[i].path != b[i].path {
+			return fmt.Errorf("a[%d] = %s; b[%d] = %s", i, a[i].path, i, b[i].path)
+		}
+	}
+
+	return nil
+}
diff --git a/pkg/build/oci/image_test.go b/pkg/build/oci/image_test.go
index eef3ce4..3d25aa7 100644
--- a/pkg/build/oci/image_test.go
+++ b/pkg/build/oci/image_test.go
@@ -58,7 +58,7 @@ func TestBuildImageFromLayer(t *testing.T) {
 			RootFS:  v1.RootFS{Type: "layers", DiffIDs: []v1.Hash{diffID}},
 			Config: v1.Config{
 				Env: []string{
-					"PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin",
+					"PATH=/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin",
 					"SSL_CERT_FILE=/etc/ssl/certs/ca-certificates.crt",
 				},
 				Labels: map[string]string{
@@ -87,7 +87,7 @@ func TestBuildImageFromLayer(t *testing.T) {
 			Config: v1.Config{
 				Env: []string{
 					"FOO=bar",
-					"PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin",
+					"PATH=/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin",
 					"SSL_CERT_FILE=/etc/ssl/certs/ca-certificates.crt",
 				},
 				Labels: map[string]string{
@@ -100,7 +100,7 @@ func TestBuildImageFromLayer(t *testing.T) {
 		cfg: types.ImageConfiguration{
 			Environment: map[string]string{
 				"FOO":  "bar",
-				"PATH": "/something/else:/another/one:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin",
+				"PATH": "/something/else:/another/one:/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin",
 			},
 		},
 		want: &v1.ConfigFile{
@@ -117,7 +117,7 @@ func TestBuildImageFromLayer(t *testing.T) {
 			Config: v1.Config{
 				Env: []string{
 					"FOO=bar",
-					"PATH=/something/else:/another/one:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin",
+					"PATH=/something/else:/another/one:/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/sbin:/sbin:/bin",
 					"SSL_CERT_FILE=/etc/ssl/certs/ca-certificates.crt",
 				},
 				Labels: map[string]string{
diff --git a/pkg/apk/tarball/write_test.go b/pkg/build/tarball_test.go
similarity index 95%
rename from pkg/apk/tarball/write_test.go
rename to pkg/build/tarball_test.go
index b1bfbfc..cad9958 100644
--- a/pkg/apk/tarball/write_test.go
+++ b/pkg/build/tarball_test.go
@@ -1,4 +1,4 @@
-package tarball
+package build
 
 import (
 	"archive/tar"
@@ -29,7 +29,7 @@ func TestWriteTar(t *testing.T) {
 	err = m.SetXattr(file, "user.file", []byte("bar"))
 	require.NoError(t, err, "error setting xattr on %s", file)
 	tw := tar.NewWriter(&buf)
-	err = writeTar(context.TODO(), tw, m, nil, nil)
+	err = writeTar(context.Background(), tw, m)
 	require.NoError(t, err, "error writing tar")
 	err = tw.Close()
 	require.NoError(t, err, "error closing tar writer")
diff --git a/pkg/sbom/generator/spdx/spdx_test.go b/pkg/sbom/generator/spdx/spdx_test.go
index 99c4fe0..2de2f82 100644
--- a/pkg/sbom/generator/spdx/spdx_test.go
+++ b/pkg/sbom/generator/spdx/spdx_test.go
@@ -24,6 +24,7 @@ import (
 	"testing"
 
 	"github.com/google/go-cmp/cmp"
+	v1 "github.com/google/go-containerregistry/pkg/v1"
 	"github.com/stretchr/testify/require"
 	"sigs.k8s.io/release-utils/command"
 
@@ -34,6 +35,9 @@ import (
 
 // TODO: clean this up and make consistent with the other test cases
 var testOpts = &options.Options{
+	ImageInfo: options.ImageInfo{
+		Layers: []v1.Descriptor{{}},
+	},
 	OS: options.OSInfo{
 		Name:    "unknown",
 		ID:      "unknown",
@@ -78,6 +82,9 @@ func TestSPDX_Generate(t *testing.T) {
 		{
 			name: "custom-license",
 			opts: &options.Options{
+				ImageInfo: options.ImageInfo{
+					Layers: []v1.Descriptor{{}},
+				},
 				OS: options.OSInfo{
 					Name:    "unknown",
 					ID:      "unknown",
@@ -97,6 +104,9 @@ func TestSPDX_Generate(t *testing.T) {
 		{
 			name: "no-supplier",
 			opts: &options.Options{
+				ImageInfo: options.ImageInfo{
+					Layers: []v1.Descriptor{{}},
+				},
 				OS: options.OSInfo{
 					Name:    "Apko Images, Plc",
 					ID:      "apko-images",
@@ -116,6 +126,9 @@ func TestSPDX_Generate(t *testing.T) {
 		{
 			name: "package-deduplicating",
 			opts: &options.Options{
+				ImageInfo: options.ImageInfo{
+					Layers: []v1.Descriptor{{}},
+				},
 				OS: options.OSInfo{
 					Name:    "unknown",
 					ID:      "unknown",