chore(tvix): move store golang bindings to tvix/store-go r/6844

Similar to the castore-go CL before, this also updates the store-go
bindings to the new layout.

Change-Id: Id73d7ad43f7d70171ab021728e303300c5db71f0
Reviewed-on: https://cl.tvl.fyi/c/depot/+/9788
Tested-by: BuildkiteCI
Reviewed-by: Connor Brewster <cbrewster@hey.com>

16 files changed, 2009 insertions, 0 deletions

diff --git a/tvix/store-go/LICENSE b/tvix/store-go/LICENSE
new file mode 100644
index 0000000000..2034ada6fd
--- /dev/null
+++ b/tvix/store-go/LICENSE
@@ -0,0 +1,21 @@
+Copyright © The Tvix Authors
+
+Permission is hereby granted, free of charge, to any person obtaining
+a copy of this software and associated documentation files (the
+“Software”), to deal in the Software without restriction, including
+without limitation the rights to use, copy, modify, merge, publish,
+distribute, sublicense, and/or sell copies of the Software, and to
+permit persons to whom the Software is furnished to do so, subject to
+the following conditions:
+
+The above copyright notice and this permission notice shall be
+included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
diff --git a/tvix/store-go/README.md b/tvix/store-go/README.md
new file mode 100644
index 0000000000..4cfa55a354
--- /dev/null
+++ b/tvix/store-go/README.md
@@ -0,0 +1,10 @@
+# store-go
+
+This directory contains generated golang bindings, both for the tvix-store data
+models, as well as the gRPC bindings.
+
+They are generated with `mg run //tvix:store-go-generate`.
+These files end with `.pb.go`, and are ensured to be up to date by Ci check.
+
+Additionally, code useful when interacting with these data structures
+(ending just with `.go`) is provided.
\ No newline at end of file
diff --git a/tvix/store-go/default.nix b/tvix/store-go/default.nix
new file mode 100644
index 0000000000..b559594a27
--- /dev/null
+++ b/tvix/store-go/default.nix
@@ -0,0 +1,25 @@
+{ depot, pkgs, ... }:
+
+(pkgs.buildGoModule {
+  name = "store-go";
+  src = depot.third_party.gitignoreSource ./.;
+  vendorHash = "sha256-WAYaIT3h3Cdvo1RB8T7DuoxeKvXfkq8vo/vdkhJQDs0=";
+}).overrideAttrs (_: {
+  meta.ci.extraSteps = {
+    check = {
+      label = ":water_buffalo: ensure generated protobuf files match";
+      needsOutput = true;
+      command = pkgs.writeShellScript "pb-go-check" ''
+        ${depot.tvix.store-go-generate}
+        if [[ -n "$(git status --porcelain -unormal)" ]]; then
+            echo "-----------------------------"
+            echo ".pb.go files need to be updated, run //tvix:store-go-generate"
+            echo "-----------------------------"
+            git status -unormal
+            exit 1
+        fi
+      '';
+      alwaysRun = true;
+    };
+  };
+})
diff --git a/tvix/store-go/export.go b/tvix/store-go/export.go
new file mode 100644
index 0000000000..889311efe7
--- /dev/null
+++ b/tvix/store-go/export.go
@@ -0,0 +1,273 @@
+package storev1
+
+import (
+	"fmt"
+	"io"
+	"path"
+
+	castorev1pb "code.tvl.fyi/tvix/castore/protos"
+	"github.com/nix-community/go-nix/pkg/nar"
+)
+
+type DirectoryLookupFn func([]byte) (*castorev1pb.Directory, error)
+type BlobLookupFn func([]byte) (io.ReadCloser, error)
+
+// Export will traverse a given root node, and write the contents in NAR format
+// to the passed Writer.
+// It uses directoryLookupFn and blobLookupFn to resolve references.
+func Export(
+	w io.Writer,
+	rootNode *castorev1pb.Node,
+	directoryLookupFn DirectoryLookupFn,
+	blobLookupFn BlobLookupFn,
+) error {
+	// initialize a NAR writer
+	narWriter, err := nar.NewWriter(w)
+	if err != nil {
+		return fmt.Errorf("unable to initialize nar writer: %w", err)
+	}
+	defer narWriter.Close()
+
+	// populate rootHeader
+	rootHeader := &nar.Header{
+		Path: "/",
+	}
+
+	// populate a stack
+	// we will push paths and directories to it when entering a directory,
+	// and emit individual elements to the NAR writer, draining the Directory object.
+	// once it's empty, we can pop it off the stack.
+	var stackPaths = []string{}
+	var stackDirectories = []*castorev1pb.Directory{}
+
+	// peek at the pathInfo root and assemble the root node and write to writer
+	// in the case of a regular file, we retrieve and write the contents, close and exit
+	// in the case of a symlink, we write the symlink, close and exit
+	if fileNode := rootNode.GetFile(); fileNode != nil {
+		rootHeader.Type = nar.TypeRegular
+		rootHeader.Size = int64(fileNode.GetSize())
+		rootHeader.Executable = fileNode.GetExecutable()
+		err := narWriter.WriteHeader(rootHeader)
+		if err != nil {
+			return fmt.Errorf("unable to write root header: %w", err)
+		}
+
+		// if it's a regular file, retrieve and write the contents
+		blobReader, err := blobLookupFn(fileNode.GetDigest())
+		if err != nil {
+			return fmt.Errorf("unable to lookup blob: %w", err)
+		}
+		defer blobReader.Close()
+
+		_, err = io.Copy(narWriter, blobReader)
+		if err != nil {
+			return fmt.Errorf("unable to read from blobReader: %w", err)
+		}
+
+		err = blobReader.Close()
+		if err != nil {
+			return fmt.Errorf("unable to close content reader: %w", err)
+		}
+
+		err = narWriter.Close()
+		if err != nil {
+			return fmt.Errorf("unable to close nar reader: %w", err)
+		}
+
+		return nil
+	} else if symlinkNode := rootNode.GetSymlink(); symlinkNode != nil {
+		rootHeader.Type = nar.TypeSymlink
+		rootHeader.LinkTarget = string(symlinkNode.GetTarget())
+		err := narWriter.WriteHeader(rootHeader)
+		if err != nil {
+			return fmt.Errorf("unable to write root header: %w", err)
+		}
+
+		err = narWriter.Close()
+		if err != nil {
+			return fmt.Errorf("unable to close nar reader: %w", err)
+		}
+	} else if directoryNode := rootNode.GetDirectory(); directoryNode != nil {
+		// We have a directory at the root, look it up and put in on the stack.
+		directory, err := directoryLookupFn(directoryNode.GetDigest())
+		if err != nil {
+			return fmt.Errorf("unable to lookup directory: %w", err)
+		}
+		stackDirectories = append(stackDirectories, directory)
+		stackPaths = append(stackPaths, "/")
+
+		err = narWriter.WriteHeader(&nar.Header{
+			Path: "/",
+			Type: nar.TypeDirectory,
+		})
+
+		if err != nil {
+			return fmt.Errorf("error writing header: %w", err)
+		}
+	} else {
+		panic("invalid type") // unreachable
+	}
+
+	// as long as the stack is not empty, we keep running.
+	for {
+		if len(stackDirectories) == 0 {
+			return nil
+		}
+
+		// Peek at the current top of the stack.
+		topOfStack := stackDirectories[len(stackDirectories)-1]
+		topOfStackPath := stackPaths[len(stackPaths)-1]
+
+		// get the next element that's lexicographically smallest, and drain it from
+		// the current directory on top of the stack.
+		nextNode := drainNextNode(topOfStack)
+
+		// If nextNode returns nil, there's nothing left in the directory node, so we
+		// can emit it from the stack.
+		// Contrary to the import case, we don't emit the node popping from the stack, but when pushing.
+		if nextNode == nil {
+			// pop off stack
+			stackDirectories = stackDirectories[:len(stackDirectories)-1]
+			stackPaths = stackPaths[:len(stackPaths)-1]
+
+			continue
+		}
+
+		switch n := (nextNode).(type) {
+		case *castorev1pb.DirectoryNode:
+			err := narWriter.WriteHeader(&nar.Header{
+				Path: path.Join(topOfStackPath, string(n.GetName())),
+				Type: nar.TypeDirectory,
+			})
+			if err != nil {
+				return fmt.Errorf("unable to write nar header: %w", err)
+			}
+
+			d, err := directoryLookupFn(n.GetDigest())
+			if err != nil {
+				return fmt.Errorf("unable to lookup directory: %w", err)
+			}
+
+			// add to stack
+			stackDirectories = append(stackDirectories, d)
+			stackPaths = append(stackPaths, path.Join(topOfStackPath, string(n.GetName())))
+		case *castorev1pb.FileNode:
+			err := narWriter.WriteHeader(&nar.Header{
+				Path:       path.Join(topOfStackPath, string(n.GetName())),
+				Type:       nar.TypeRegular,
+				Size:       int64(n.GetSize()),
+				Executable: n.GetExecutable(),
+			})
+			if err != nil {
+				return fmt.Errorf("unable to write nar header: %w", err)
+			}
+
+			// copy file contents
+			contentReader, err := blobLookupFn(n.GetDigest())
+			if err != nil {
+				return fmt.Errorf("unable to get blob: %w", err)
+			}
+			defer contentReader.Close()
+
+			_, err = io.Copy(narWriter, contentReader)
+			if err != nil {
+				return fmt.Errorf("unable to copy contents from contentReader: %w", err)
+			}
+
+			err = contentReader.Close()
+			if err != nil {
+				return fmt.Errorf("unable to close content reader: %w", err)
+			}
+		case *castorev1pb.SymlinkNode:
+			err := narWriter.WriteHeader(&nar.Header{
+				Path:       path.Join(topOfStackPath, string(n.GetName())),
+				Type:       nar.TypeSymlink,
+				LinkTarget: string(n.GetTarget()),
+			})
+			if err != nil {
+				return fmt.Errorf("unable to write nar header: %w", err)
+			}
+		}
+	}
+}
+
+// drainNextNode will drain a directory message with one of its child nodes,
+// whichever comes first alphabetically.
+func drainNextNode(d *castorev1pb.Directory) interface{} {
+	switch v := (smallestNode(d)).(type) {
+	case *castorev1pb.DirectoryNode:
+		d.Directories = d.Directories[1:]
+		return v
+	case *castorev1pb.FileNode:
+		d.Files = d.Files[1:]
+		return v
+	case *castorev1pb.SymlinkNode:
+		d.Symlinks = d.Symlinks[1:]
+		return v
+	case nil:
+		return nil
+	default:
+		panic("invalid type encountered")
+	}
+}
+
+// smallestNode will return the node from a directory message,
+// whichever comes first alphabetically.
+func smallestNode(d *castorev1pb.Directory) interface{} {
+	childDirectories := d.GetDirectories()
+	childFiles := d.GetFiles()
+	childSymlinks := d.GetSymlinks()
+
+	if len(childDirectories) > 0 {
+		if len(childFiles) > 0 {
+			if len(childSymlinks) > 0 {
+				// directories,files,symlinks
+				return smallerNode(smallerNode(childDirectories[0], childFiles[0]), childSymlinks[0])
+			} else {
+				// directories,files,!symlinks
+				return smallerNode(childDirectories[0], childFiles[0])
+			}
+		} else {
+			// directories,!files
+			if len(childSymlinks) > 0 {
+				// directories,!files,symlinks
+				return smallerNode(childDirectories[0], childSymlinks[0])
+			} else {
+				// directories,!files,!symlinks
+				return childDirectories[0]
+			}
+		}
+	} else {
+		// !directories
+		if len(childFiles) > 0 {
+			// !directories,files
+			if len(childSymlinks) > 0 {
+				// !directories,files,symlinks
+				return smallerNode(childFiles[0], childSymlinks[0])
+			} else {
+				// !directories,files,!symlinks
+				return childFiles[0]
+			}
+		} else {
+			//!directories,!files
+			if len(childSymlinks) > 0 {
+				//!directories,!files,symlinks
+				return childSymlinks[0]
+			} else {
+				//!directories,!files,!symlinks
+				return nil
+			}
+		}
+	}
+}
+
+// smallerNode compares two nodes by their name,
+// and returns the one with the smaller name.
+// both nodes may not be nil, we do check for these cases in smallestNode.
+func smallerNode(a interface{ GetName() []byte }, b interface{ GetName() []byte }) interface{ GetName() []byte } {
+	if string(a.GetName()) < string(b.GetName()) {
+		return a
+	} else {
+		return b
+	}
+}
diff --git a/tvix/store-go/export_test.go b/tvix/store-go/export_test.go
new file mode 100644
index 0000000000..6c33bdc901
--- /dev/null
+++ b/tvix/store-go/export_test.go
@@ -0,0 +1,134 @@
+package storev1_test
+
+import (
+	"bytes"
+	"io"
+	"os"
+	"testing"
+
+	castorev1pb "code.tvl.fyi/tvix/castore/protos"
+	storev1pb "code.tvl.fyi/tvix/store/protos"
+	"github.com/stretchr/testify/require"
+)
+
+func mustDirectoryDigest(d *castorev1pb.Directory) []byte {
+	dgst, err := d.Digest()
+	if err != nil {
+		panic(err)
+	}
+	return dgst
+}
+
+func TestSymlink(t *testing.T) {
+	node := &castorev1pb.Node{
+		Node: &castorev1pb.Node_Symlink{
+			Symlink: &castorev1pb.SymlinkNode{
+				Name:   []byte("doesntmatter"),
+				Target: []byte("/nix/store/somewhereelse"),
+			},
+		},
+	}
+
+	var buf bytes.Buffer
+
+	err := storev1pb.Export(&buf, node, func([]byte) (*castorev1pb.Directory, error) {
+		panic("no directories expected")
+	}, func([]byte) (io.ReadCloser, error) {
+		panic("no files expected")
+	})
+	require.NoError(t, err, "exporter shouldn't fail")
+
+	f, err := os.Open("testdata/symlink.nar")
+	require.NoError(t, err)
+
+	bytesExpected, err := io.ReadAll(f)
+	if err != nil {
+		panic(err)
+	}
+
+	require.Equal(t, bytesExpected, buf.Bytes(), "expected nar contents to match")
+}
+
+func TestRegular(t *testing.T) {
+	// The blake3 digest of the 0x01 byte.
+	BLAKE3_DIGEST_0X01 := []byte{
+		0x48, 0xfc, 0x72, 0x1f, 0xbb, 0xc1, 0x72, 0xe0, 0x92, 0x5f, 0xa2, 0x7a, 0xf1, 0x67, 0x1d,
+		0xe2, 0x25, 0xba, 0x92, 0x71, 0x34, 0x80, 0x29, 0x98, 0xb1, 0x0a, 0x15, 0x68, 0xa1, 0x88,
+		0x65, 0x2b,
+	}
+
+	node := &castorev1pb.Node{
+		Node: &castorev1pb.Node_File{
+			File: &castorev1pb.FileNode{
+				Name:       []byte("doesntmatter"),
+				Digest:     BLAKE3_DIGEST_0X01,
+				Size:       1,
+				Executable: false,
+			},
+		},
+	}
+
+	var buf bytes.Buffer
+
+	err := storev1pb.Export(&buf, node, func([]byte) (*castorev1pb.Directory, error) {
+		panic("no directories expected")
+	}, func(blobRef []byte) (io.ReadCloser, error) {
+		if !bytes.Equal(blobRef, BLAKE3_DIGEST_0X01) {
+			panic("unexpected blobref")
+		}
+		return io.NopCloser(bytes.NewBuffer([]byte{0x01})), nil
+	})
+	require.NoError(t, err, "exporter shouldn't fail")
+
+	f, err := os.Open("testdata/onebyteregular.nar")
+	require.NoError(t, err)
+
+	bytesExpected, err := io.ReadAll(f)
+	if err != nil {
+		panic(err)
+	}
+
+	require.Equal(t, bytesExpected, buf.Bytes(), "expected nar contents to match")
+}
+
+func TestEmptyDirectory(t *testing.T) {
+	// construct empty directory node this refers to
+	emptyDirectory := &castorev1pb.Directory{
+		Directories: []*castorev1pb.DirectoryNode{},
+		Files:       []*castorev1pb.FileNode{},
+		Symlinks:    []*castorev1pb.SymlinkNode{},
+	}
+	emptyDirectoryDigest := mustDirectoryDigest(emptyDirectory)
+
+	node := &castorev1pb.Node{
+		Node: &castorev1pb.Node_Directory{
+			Directory: &castorev1pb.DirectoryNode{
+				Name:   []byte("doesntmatter"),
+				Digest: emptyDirectoryDigest,
+				Size:   0,
+			},
+		},
+	}
+
+	var buf bytes.Buffer
+
+	err := storev1pb.Export(&buf, node, func(directoryRef []byte) (*castorev1pb.Directory, error) {
+		if !bytes.Equal(directoryRef, emptyDirectoryDigest) {
+			panic("unexpected directoryRef")
+		}
+		return emptyDirectory, nil
+	}, func([]byte) (io.ReadCloser, error) {
+		panic("no files expected")
+	})
+	require.NoError(t, err, "exporter shouldn't fail")
+
+	f, err := os.Open("testdata/emptydirectory.nar")
+	require.NoError(t, err)
+
+	bytesExpected, err := io.ReadAll(f)
+	if err != nil {
+		panic(err)
+	}
+
+	require.Equal(t, bytesExpected, buf.Bytes(), "expected nar contents to match")
+}
diff --git a/tvix/store-go/go.mod b/tvix/store-go/go.mod
new file mode 100644
index 0000000000..d56e2d9bc1
--- /dev/null
+++ b/tvix/store-go/go.mod
@@ -0,0 +1,26 @@
+module code.tvl.fyi/tvix/store/protos
+
+go 1.19
+
+require (
+	code.tvl.fyi/tvix/castore/protos v0.0.0-20231014122118-3fc2ade7dfb2
+	github.com/google/go-cmp v0.5.6
+	github.com/nix-community/go-nix v0.0.0-20231009143713-ebca3299475b
+	github.com/stretchr/testify v1.8.1
+	google.golang.org/grpc v1.51.0
+	google.golang.org/protobuf v1.31.0
+)
+
+require (
+	github.com/davecgh/go-spew v1.1.1 // indirect
+	github.com/golang/protobuf v1.5.2 // indirect
+	github.com/klauspost/cpuid/v2 v2.0.9 // indirect
+	github.com/pmezard/go-difflib v1.0.0 // indirect
+	golang.org/x/net v0.7.0 // indirect
+	golang.org/x/sys v0.5.0 // indirect
+	golang.org/x/text v0.7.0 // indirect
+	golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 // indirect
+	google.golang.org/genproto v0.0.0-20200526211855-cb27e3aa2013 // indirect
+	gopkg.in/yaml.v3 v3.0.1 // indirect
+	lukechampine.com/blake3 v1.1.7 // indirect
+)
diff --git a/tvix/store-go/go.sum b/tvix/store-go/go.sum
new file mode 100644
index 0000000000..c412d838e2
--- /dev/null
+++ b/tvix/store-go/go.sum
@@ -0,0 +1,105 @@
+cloud.google.com/go v0.26.0/go.mod h1:aQUYkXzVsufM+DwF1aE+0xfcU+56JwCaLick0ClmMTw=
+code.tvl.fyi/tvix/castore/protos v0.0.0-20231014122118-3fc2ade7dfb2 h1:Z5GS8OUe7L/hKDbb1amArY7QgX0DSD5xaBwWxmh4H3Y=
+code.tvl.fyi/tvix/castore/protos v0.0.0-20231014122118-3fc2ade7dfb2/go.mod h1:hj0y8RPthqn1QPj8u2jFe2vzH7NouUoclrwo1/CSbuc=
+github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
+github.com/census-instrumentation/opencensus-proto v0.2.1/go.mod h1:f6KPmirojxKA12rnyqOA5BBL4O983OfeGPqjHWSTneU=
+github.com/client9/misspell v0.3.4/go.mod h1:qj6jICC3Q7zFZvVWo7KLAzC3yx5G7kyvSDkc90ppPyw=
+github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/envoyproxy/go-control-plane v0.9.1-0.20191026205805-5f8ba28d4473/go.mod h1:YTl/9mNaCwkRvm6d1a2C3ymFceY/DCBVvsKhRF0iEA4=
+github.com/envoyproxy/protoc-gen-validate v0.1.0/go.mod h1:iSmxcyjqTsJpI2R4NaDN7+kN2VEUnK/pcBlmesArF7c=
+github.com/golang/glog v0.0.0-20160126235308-23def4e6c14b/go.mod h1:SBH7ygxi8pfUlaOkMMuAQtPIUF8ecWP5IEl/CR7VP2Q=
+github.com/golang/mock v1.1.1/go.mod h1:oTYuIxOrZwtPieC+H1uAHpcLFnEyAGVDL/k47Jfbm0A=
+github.com/golang/protobuf v1.2.0/go.mod h1:6lQm79b+lXiMfvg/cZm0SGofjICqVBUtrP5yJMmIC1U=
+github.com/golang/protobuf v1.3.2/go.mod h1:6lQm79b+lXiMfvg/cZm0SGofjICqVBUtrP5yJMmIC1U=
+github.com/golang/protobuf v1.4.0-rc.1/go.mod h1:ceaxUfeHdC40wWswd/P6IGgMaK3YpKi5j83Wpe3EHw8=
+github.com/golang/protobuf v1.4.0-rc.1.0.20200221234624-67d41d38c208/go.mod h1:xKAWHe0F5eneWXFV3EuXVDTCmh+JuBKY0li0aMyXATA=
+github.com/golang/protobuf v1.4.0-rc.2/go.mod h1:LlEzMj4AhA7rCAGe4KMBDvJI+AwstrUpVNzEA03Pprs=
+github.com/golang/protobuf v1.4.0-rc.4.0.20200313231945-b860323f09d0/go.mod h1:WU3c8KckQ9AFe+yFwt9sWVRKCVIyN9cPHBJSNnbL67w=
+github.com/golang/protobuf v1.4.0/go.mod h1:jodUvKwWbYaEsadDk5Fwe5c77LiNKVO9IDvqG2KuDX0=
+github.com/golang/protobuf v1.4.1/go.mod h1:U8fpvMrcmy5pZrNK1lt4xCsGvpyWQ/VVv6QDs8UjoX8=
+github.com/golang/protobuf v1.5.0/go.mod h1:FsONVRAS9T7sI+LIUmWTfcYkHO4aIWwzhcaSAoJOfIk=
+github.com/golang/protobuf v1.5.2 h1:ROPKBNFfQgOUMifHyP+KYbvpjbdoFNs+aK7DXlji0Tw=
+github.com/golang/protobuf v1.5.2/go.mod h1:XVQd3VNwM+JqD3oG2Ue2ip4fOMUkwXdXDdiuN0vRsmY=
+github.com/google/go-cmp v0.2.0/go.mod h1:oXzfMopK8JAjlY9xF4vHSVASa0yLyX7SntLO5aqRK0M=
+github.com/google/go-cmp v0.3.0/go.mod h1:8QqcDgzrUqlUb/G2PQTWiueGozuR1884gddMywk6iLU=
+github.com/google/go-cmp v0.3.1/go.mod h1:8QqcDgzrUqlUb/G2PQTWiueGozuR1884gddMywk6iLU=
+github.com/google/go-cmp v0.4.0/go.mod h1:v8dTdLbMG2kIc/vJvl+f65V22dbkXbowE6jgT/gNBxE=
+github.com/google/go-cmp v0.5.5/go.mod h1:v8dTdLbMG2kIc/vJvl+f65V22dbkXbowE6jgT/gNBxE=
+github.com/google/go-cmp v0.5.6 h1:BKbKCqvP6I+rmFHt06ZmyQtvB8xAkWdhFyr0ZUNZcxQ=
+github.com/google/go-cmp v0.5.6/go.mod h1:v8dTdLbMG2kIc/vJvl+f65V22dbkXbowE6jgT/gNBxE=
+github.com/klauspost/cpuid/v2 v2.0.9 h1:lgaqFMSdTdQYdZ04uHyN2d/eKdOMyi2YLSvlQIBFYa4=
+github.com/klauspost/cpuid/v2 v2.0.9/go.mod h1:FInQzS24/EEf25PyTYn52gqo7WaD8xa0213Md/qVLRg=
+github.com/nix-community/go-nix v0.0.0-20231009143713-ebca3299475b h1:AWEKOdDO3JnHApQDOmONEKLXbMCQJhYJJfJpiWB9VGI=
+github.com/nix-community/go-nix v0.0.0-20231009143713-ebca3299475b/go.mod h1:hHM9UK2zOCjvmiLgeaW4LVbOW/vBaRWFJGzfi31/slQ=
+github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
+github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
+github.com/prometheus/client_model v0.0.0-20190812154241-14fe0d1b01d4/go.mod h1:xMI15A0UPsDsEKsMN9yxemIoYk6Tm2C1GtYGdfGttqA=
+github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
+github.com/stretchr/objx v0.4.0/go.mod h1:YvHI0jy2hoMjB+UWwv71VJQ9isScKT/TqJzVSSt89Yw=
+github.com/stretchr/objx v0.5.0/go.mod h1:Yh+to48EsGEfYuaHDzXPcE3xhTkx73EhmCGUpEOglKo=
+github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
+github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU=
+github.com/stretchr/testify v1.8.1 h1:w7B6lhMri9wdJUVmEZPGGhZzrYTPvgJArz7wNPgYKsk=
+github.com/stretchr/testify v1.8.1/go.mod h1:w2LPCIKwWwSfY2zedu0+kehJoqGctiVI29o6fzry7u4=
+golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
+golang.org/x/exp v0.0.0-20190121172915-509febef88a4/go.mod h1:CJ0aWSM057203Lf6IL+f9T1iT9GByDxfZKAQTCR3kQA=
+golang.org/x/lint v0.0.0-20181026193005-c67002cb31c3/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=
+golang.org/x/lint v0.0.0-20190227174305-5b3e6a55c961/go.mod h1:wehouNa3lNwaWXcvxsM5YxQ5yQlVC4a0KAMCusXpPoU=
+golang.org/x/lint v0.0.0-20190313153728-d0100b6bd8b3/go.mod h1:6SW0HCj/g11FgYtHlgUYUwCkIfeOF89ocIRzGO/8vkc=
+golang.org/x/net v0.0.0-20180724234803-3673e40ba225/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
+golang.org/x/net v0.0.0-20180826012351-8a410e7b638d/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
+golang.org/x/net v0.0.0-20190213061140-3a22650c66bd/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
+golang.org/x/net v0.0.0-20190311183353-d8887717615a/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
+golang.org/x/net v0.7.0 h1:rJrUqqhjsgNp7KqAIc25s9pZnjU7TUcSY7HcVZjdn1g=
+golang.org/x/net v0.7.0/go.mod h1:2Tu9+aMcznHK/AK1HMvgo6xiTLG5rD5rZLDS+rp2Bjs=
+golang.org/x/oauth2 v0.0.0-20180821212333-d2e6202438be/go.mod h1:N/0e6XlmueqKjAGxoOufVs8QHGRruUQn6yWY3a++T0U=
+golang.org/x/sync v0.0.0-20180314180146-1d60e4601c6f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sync v0.0.0-20181108010431-42b317875d0f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sys v0.0.0-20180830151530-49385e6e1522/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
+golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
+golang.org/x/sys v0.5.0 h1:MUK/U/4lj1t1oPg0HfuXDN/Z1wv31ZJ/YcPiGccS4DU=
+golang.org/x/sys v0.5.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
+golang.org/x/text v0.7.0 h1:4BRB4x83lYWy72KwLD/qYDuTu7q9PjSagHvijDw7cLo=
+golang.org/x/text v0.7.0/go.mod h1:mrYo+phRRbMaCq/xk9113O4dZlRixOauAjOtrjsXDZ8=
+golang.org/x/tools v0.0.0-20190114222345-bf090417da8b/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
+golang.org/x/tools v0.0.0-20190226205152-f727befe758c/go.mod h1:9Yl7xja0Znq3iFh3HoIrodX9oNMXvdceNzlUR8zjMvY=
+golang.org/x/tools v0.0.0-20190311212946-11955173bddd/go.mod h1:LCzVGOaR6xXOjkQ3onu1FJEFr0SW1gC7cKk1uF8kGRs=
+golang.org/x/tools v0.0.0-20190524140312-2c0ae7006135/go.mod h1:RgjU9mgBXZiqYHBnxXauZ1Gv1EHHAz9KjViQ78xBX0Q=
+golang.org/x/xerrors v0.0.0-20191204190536-9bdfabe68543/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 h1:go1bK/D/BFZV2I8cIQd1NKEZ+0owSTG1fDTci4IqFcE=
+golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+google.golang.org/appengine v1.1.0/go.mod h1:EbEs0AVv82hx2wNQdGPgUI5lhzA/G0D9YwlJXL52JkM=
+google.golang.org/appengine v1.4.0/go.mod h1:xpcJRLb0r/rnEns0DIKYYv+WjYCduHsrkT7/EB5XEv4=
+google.golang.org/genproto v0.0.0-20180817151627-c66870c02cf8/go.mod h1:JiN7NxoALGmiZfu7CAH4rXhgtRTLTxftemlI0sWmxmc=
+google.golang.org/genproto v0.0.0-20190819201941-24fa4b261c55/go.mod h1:DMBHOl98Agz4BDEuKkezgsaosCRResVns1a3J2ZsMNc=
+google.golang.org/genproto v0.0.0-20200526211855-cb27e3aa2013 h1:+kGHl1aib/qcwaRi1CbqBZ1rk19r85MNUf8HaBghugY=
+google.golang.org/genproto v0.0.0-20200526211855-cb27e3aa2013/go.mod h1:NbSheEEYHJ7i3ixzK3sjbqSGDJWnxyFXZblF3eUsNvo=
+google.golang.org/grpc v1.19.0/go.mod h1:mqu4LbDTu4XGKhr4mRzUsmM4RtVoemTSY81AxZiDr8c=
+google.golang.org/grpc v1.23.0/go.mod h1:Y5yQAOtifL1yxbo5wqy6BxZv8vAUGQwXBOALyacEbxg=
+google.golang.org/grpc v1.27.0/go.mod h1:qbnxyOmOxrQa7FizSgH+ReBfzJrCY1pSN7KXBS8abTk=
+google.golang.org/grpc v1.51.0 h1:E1eGv1FTqoLIdnBCZufiSHgKjlqG6fKFf6pPWtMTh8U=
+google.golang.org/grpc v1.51.0/go.mod h1:wgNDFcnuBGmxLKI/qn4T+m5BtEBYXJPvibbUPsAIPww=
+google.golang.org/protobuf v0.0.0-20200109180630-ec00e32a8dfd/go.mod h1:DFci5gLYBciE7Vtevhsrf46CRTquxDuWsQurQQe4oz8=
+google.golang.org/protobuf v0.0.0-20200221191635-4d8936d0db64/go.mod h1:kwYJMbMJ01Woi6D6+Kah6886xMZcty6N08ah7+eCXa0=
+google.golang.org/protobuf v0.0.0-20200228230310-ab0ca4ff8a60/go.mod h1:cfTl7dwQJ+fmap5saPgwCLgHXTUD7jkjRqWcaiX5VyM=
+google.golang.org/protobuf v1.20.1-0.20200309200217-e05f789c0967/go.mod h1:A+miEFZTKqfCUM6K7xSMQL9OKL/b6hQv+e19PK+JZNE=
+google.golang.org/protobuf v1.21.0/go.mod h1:47Nbq4nVaFHyn7ilMalzfO3qCViNmqZ2kzikPIcrTAo=
+google.golang.org/protobuf v1.22.0/go.mod h1:EGpADcykh3NcUnDUJcl1+ZksZNG86OlYog2l/sGQquU=
+google.golang.org/protobuf v1.23.1-0.20200526195155-81db48ad09cc/go.mod h1:EGpADcykh3NcUnDUJcl1+ZksZNG86OlYog2l/sGQquU=
+google.golang.org/protobuf v1.26.0-rc.1/go.mod h1:jlhhOSvTdKEhbULTjvd4ARK9grFBp09yW+WbY/TyQbw=
+google.golang.org/protobuf v1.26.0/go.mod h1:9q0QmTI4eRPtz6boOQmLYwt+qCgq0jsYwAQnmE0givc=
+google.golang.org/protobuf v1.31.0 h1:g0LDEJHgrBl9N9r17Ru3sqWhkIx2NB67okBHPwC7hs8=
+google.golang.org/protobuf v1.31.0/go.mod h1:HV8QOd/L58Z+nl8r43ehVNZIU/HEI6OcFqwMG9pJV4I=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
+gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
+gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
+honnef.co/go/tools v0.0.0-20190102054323-c2f93a96b099/go.mod h1:rf3lG4BRIbNafJWhAfAdb/ePZxsR/4RtNHQocxwk9r4=
+honnef.co/go/tools v0.0.0-20190523083050-ea95bdfd59fc/go.mod h1:rf3lG4BRIbNafJWhAfAdb/ePZxsR/4RtNHQocxwk9r4=
+lukechampine.com/blake3 v1.1.7 h1:GgRMhmdsuK8+ii6UZFDL8Nb+VyMwadAgcJyfYHxG6n0=
+lukechampine.com/blake3 v1.1.7/go.mod h1:tkKEOtDkNtklkXtLNEOGNq5tcV90tJiA1vAA12R78LA=
diff --git a/tvix/store-go/pathinfo.go b/tvix/store-go/pathinfo.go
new file mode 100644
index 0000000000..8c0b94f200
--- /dev/null
+++ b/tvix/store-go/pathinfo.go
@@ -0,0 +1,99 @@
+package storev1
+
+import (
+	"bytes"
+	"crypto/sha256"
+	"encoding/base64"
+	"fmt"
+
+	"github.com/nix-community/go-nix/pkg/storepath"
+)
+
+// Validate performs some checks on the PathInfo struct, returning either the
+// StorePath of the root node, or an error.
+func (p *PathInfo) Validate() (*storepath.StorePath, error) {
+	// ensure References has the right number of bytes.
+	for i, reference := range p.GetReferences() {
+		if len(reference) != storepath.PathHashSize {
+			return nil, fmt.Errorf("invalid length of digest at position %d, expected %d, got %d", i, storepath.PathHashSize, len(reference))
+		}
+	}
+
+	// If there's a Narinfo field populated..
+	if narInfo := p.GetNarinfo(); narInfo != nil {
+		// ensure the NarSha256 digest has the correct length.
+		if len(narInfo.GetNarSha256()) != sha256.Size {
+			return nil, fmt.Errorf("invalid number of bytes for NarSha256: expected %d, got %d", sha256.Size, len(narInfo.GetNarSha256()))
+		}
+
+		// ensure the number of references matches len(References).
+		if len(narInfo.GetReferenceNames()) != len(p.GetReferences()) {
+			return nil, fmt.Errorf("inconsistent number of references: %d (references) vs %d (narinfo)", len(narInfo.GetReferenceNames()), len(p.GetReferences()))
+		}
+
+		// for each ReferenceName…
+		for i, referenceName := range narInfo.GetReferenceNames() {
+			// ensure it parses to a store path
+			storePath, err := storepath.FromString(referenceName)
+			if err != nil {
+				return nil, fmt.Errorf("invalid ReferenceName at position %d: %w", i, err)
+			}
+
+			// ensure the digest matches the one at References[i]
+			if !bytes.Equal(p.GetReferences()[i], storePath.Digest) {
+				return nil, fmt.Errorf(
+					"digest in ReferenceName at position %d does not match digest in PathInfo, expected %s, got %s",
+					i,
+					base64.StdEncoding.EncodeToString(p.GetReferences()[i]),
+					base64.StdEncoding.EncodeToString(storePath.Digest),
+				)
+			}
+		}
+	}
+
+	// ensure there is a (root) node present
+	rootNode := p.GetNode()
+	if rootNode == nil {
+		return nil, fmt.Errorf("root node must be set")
+	}
+
+	if err := rootNode.Validate(); err != nil {
+		return nil, fmt.Errorf("root node failed validation: %w", err)
+	}
+
+	// for all three node types, ensure the name properly parses to a store path.
+	// This is a stricter check as the ones already performed in the rootNode.Validate() call.
+	var rootNodeName []byte
+
+	if node := rootNode.GetDirectory(); node != nil {
+		rootNodeName = node.GetName()
+	} else if node := rootNode.GetFile(); node != nil {
+		rootNodeName = node.GetName()
+	} else if node := rootNode.GetSymlink(); node != nil {
+		rootNodeName = node.GetName()
+	} else {
+		// already caught by rootNode.Validate()
+		panic("unreachable")
+	}
+
+	storePath, err := storepath.FromString(string(rootNodeName))
+	if err != nil {
+		return nil, fmt.Errorf("unable to parse root node name %s as StorePath: %w", rootNodeName, err)
+	}
+
+	// If the Deriver field is populated, ensure it parses to a StorePath.
+	// We can't check for it to *not* end with .drv, as the .drv files produced by
+	// recursive Nix end with multiple .drv suffixes, and only one is popped when
+	// converting to this field.
+	if p.Deriver != nil {
+		deriverStorePath := storepath.StorePath{
+			Name:   string(p.Deriver.GetName()),
+			Digest: p.Deriver.GetDigest(),
+		}
+		if err := deriverStorePath.Validate(); err != nil {
+			return nil, fmt.Errorf("invalid deriver field: %w", err)
+		}
+	}
+
+	return storePath, nil
+}
diff --git a/tvix/store-go/pathinfo.pb.go b/tvix/store-go/pathinfo.pb.go
new file mode 100644
index 0000000000..b8296114f6
--- /dev/null
+++ b/tvix/store-go/pathinfo.pb.go
@@ -0,0 +1,460 @@
+// SPDX-License-Identifier: MIT
+// Copyright © 2022 The Tvix Authors
+
+// Code generated by protoc-gen-go. DO NOT EDIT.
+// versions:
+// 	protoc-gen-go v1.31.0
+// 	protoc        (unknown)
+// source: tvix/store/protos/pathinfo.proto
+
+package storev1
+
+import (
+	protos "code.tvl.fyi/tvix/castore/protos"
+	protoreflect "google.golang.org/protobuf/reflect/protoreflect"
+	protoimpl "google.golang.org/protobuf/runtime/protoimpl"
+	reflect "reflect"
+	sync "sync"
+)
+
+const (
+	// Verify that this generated code is sufficiently up-to-date.
+	_ = protoimpl.EnforceVersion(20 - protoimpl.MinVersion)
+	// Verify that runtime/protoimpl is sufficiently up-to-date.
+	_ = protoimpl.EnforceVersion(protoimpl.MaxVersion - 20)
+)
+
+// PathInfo shows information about a Nix Store Path.
+// That's a single element inside /nix/store.
+type PathInfo struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	// The path can be a directory, file or symlink.
+	Node *protos.Node `protobuf:"bytes,1,opt,name=node,proto3" json:"node,omitempty"`
+	// List of references (output path hashes)
+	// This really is the raw *bytes*, after decoding nixbase32, and not a
+	// base32-encoded string.
+	References [][]byte `protobuf:"bytes,2,rep,name=references,proto3" json:"references,omitempty"`
+	// see below.
+	Narinfo *NARInfo `protobuf:"bytes,3,opt,name=narinfo,proto3" json:"narinfo,omitempty"`
+	// The StorePath of the .drv file producing this output.
+	// The .drv suffix is omitted in its `name` field.
+	Deriver *StorePath `protobuf:"bytes,4,opt,name=deriver,proto3" json:"deriver,omitempty"`
+}
+
+func (x *PathInfo) Reset() {
+	*x = PathInfo{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[0]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *PathInfo) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*PathInfo) ProtoMessage() {}
+
+func (x *PathInfo) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[0]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use PathInfo.ProtoReflect.Descriptor instead.
+func (*PathInfo) Descriptor() ([]byte, []int) {
+	return file_tvix_store_protos_pathinfo_proto_rawDescGZIP(), []int{0}
+}
+
+func (x *PathInfo) GetNode() *protos.Node {
+	if x != nil {
+		return x.Node
+	}
+	return nil
+}
+
+func (x *PathInfo) GetReferences() [][]byte {
+	if x != nil {
+		return x.References
+	}
+	return nil
+}
+
+func (x *PathInfo) GetNarinfo() *NARInfo {
+	if x != nil {
+		return x.Narinfo
+	}
+	return nil
+}
+
+func (x *PathInfo) GetDeriver() *StorePath {
+	if x != nil {
+		return x.Deriver
+	}
+	return nil
+}
+
+// Represents a path in the Nix store (a direct child of STORE_DIR).
+// It is commonly formatted by a nixbase32-encoding the digest, and
+// concatenating the name, separated by a `-`.
+type StorePath struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	// The string after digest and `-`.
+	Name string `protobuf:"bytes,1,opt,name=name,proto3" json:"name,omitempty"`
+	// The digest (20 bytes).
+	Digest []byte `protobuf:"bytes,2,opt,name=digest,proto3" json:"digest,omitempty"`
+}
+
+func (x *StorePath) Reset() {
+	*x = StorePath{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[1]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *StorePath) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*StorePath) ProtoMessage() {}
+
+func (x *StorePath) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[1]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use StorePath.ProtoReflect.Descriptor instead.
+func (*StorePath) Descriptor() ([]byte, []int) {
+	return file_tvix_store_protos_pathinfo_proto_rawDescGZIP(), []int{1}
+}
+
+func (x *StorePath) GetName() string {
+	if x != nil {
+		return x.Name
+	}
+	return ""
+}
+
+func (x *StorePath) GetDigest() []byte {
+	if x != nil {
+		return x.Digest
+	}
+	return nil
+}
+
+// Nix C++ uses NAR (Nix Archive) as a format to transfer store paths,
+// and stores metadata and signatures in NARInfo files.
+// Store all these attributes in a separate message.
+//
+// This is useful to render .narinfo files to clients, or to preserve/validate
+// these signatures.
+// As verifying these signatures requires the whole NAR file to be synthesized,
+// moving to another signature scheme is desired.
+// Even then, it still makes sense to hold this data, for old clients.
+type NARInfo struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	// This size of the NAR file, in bytes.
+	NarSize uint64 `protobuf:"varint,1,opt,name=nar_size,json=narSize,proto3" json:"nar_size,omitempty"`
+	// The sha256 of the NAR file representation.
+	NarSha256 []byte `protobuf:"bytes,2,opt,name=nar_sha256,json=narSha256,proto3" json:"nar_sha256,omitempty"`
+	// The signatures in a .narinfo file.
+	Signatures []*NARInfo_Signature `protobuf:"bytes,3,rep,name=signatures,proto3" json:"signatures,omitempty"`
+	// A list of references. To validate .narinfo signatures, a fingerprint
+	// needs to be constructed.
+	// This fingerprint doesn't just contain the hashes of the output paths of
+	// all references (like PathInfo.references), but their whole (base)names,
+	// so we need to keep them somewhere.
+	ReferenceNames []string `protobuf:"bytes,4,rep,name=reference_names,json=referenceNames,proto3" json:"reference_names,omitempty"`
+}
+
+func (x *NARInfo) Reset() {
+	*x = NARInfo{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[2]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *NARInfo) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*NARInfo) ProtoMessage() {}
+
+func (x *NARInfo) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[2]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use NARInfo.ProtoReflect.Descriptor instead.
+func (*NARInfo) Descriptor() ([]byte, []int) {
+	return file_tvix_store_protos_pathinfo_proto_rawDescGZIP(), []int{2}
+}
+
+func (x *NARInfo) GetNarSize() uint64 {
+	if x != nil {
+		return x.NarSize
+	}
+	return 0
+}
+
+func (x *NARInfo) GetNarSha256() []byte {
+	if x != nil {
+		return x.NarSha256
+	}
+	return nil
+}
+
+func (x *NARInfo) GetSignatures() []*NARInfo_Signature {
+	if x != nil {
+		return x.Signatures
+	}
+	return nil
+}
+
+func (x *NARInfo) GetReferenceNames() []string {
+	if x != nil {
+		return x.ReferenceNames
+	}
+	return nil
+}
+
+// This represents a (parsed) signature line in a .narinfo file.
+type NARInfo_Signature struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	Name string `protobuf:"bytes,1,opt,name=name,proto3" json:"name,omitempty"`
+	Data []byte `protobuf:"bytes,2,opt,name=data,proto3" json:"data,omitempty"`
+}
+
+func (x *NARInfo_Signature) Reset() {
+	*x = NARInfo_Signature{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[3]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *NARInfo_Signature) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*NARInfo_Signature) ProtoMessage() {}
+
+func (x *NARInfo_Signature) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_store_protos_pathinfo_proto_msgTypes[3]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use NARInfo_Signature.ProtoReflect.Descriptor instead.
+func (*NARInfo_Signature) Descriptor() ([]byte, []int) {
+	return file_tvix_store_protos_pathinfo_proto_rawDescGZIP(), []int{2, 0}
+}
+
+func (x *NARInfo_Signature) GetName() string {
+	if x != nil {
+		return x.Name
+	}
+	return ""
+}
+
+func (x *NARInfo_Signature) GetData() []byte {
+	if x != nil {
+		return x.Data
+	}
+	return nil
+}
+
+var File_tvix_store_protos_pathinfo_proto protoreflect.FileDescriptor
+
+var file_tvix_store_protos_pathinfo_proto_rawDesc = []byte{
+	0x0a, 0x20, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2f, 0x70, 0x72, 0x6f,
+	0x74, 0x6f, 0x73, 0x2f, 0x70, 0x61, 0x74, 0x68, 0x69, 0x6e, 0x66, 0x6f, 0x2e, 0x70, 0x72, 0x6f,
+	0x74, 0x6f, 0x12, 0x0d, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76,
+	0x31, 0x1a, 0x21, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2f,
+	0x70, 0x72, 0x6f, 0x74, 0x6f, 0x73, 0x2f, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x70,
+	0x72, 0x6f, 0x74, 0x6f, 0x22, 0xbb, 0x01, 0x0a, 0x08, 0x50, 0x61, 0x74, 0x68, 0x49, 0x6e, 0x66,
+	0x6f, 0x12, 0x29, 0x0a, 0x04, 0x6e, 0x6f, 0x64, 0x65, 0x18, 0x01, 0x20, 0x01, 0x28, 0x0b, 0x32,
+	0x15, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76,
+	0x31, 0x2e, 0x4e, 0x6f, 0x64, 0x65, 0x52, 0x04, 0x6e, 0x6f, 0x64, 0x65, 0x12, 0x1e, 0x0a, 0x0a,
+	0x72, 0x65, 0x66, 0x65, 0x72, 0x65, 0x6e, 0x63, 0x65, 0x73, 0x18, 0x02, 0x20, 0x03, 0x28, 0x0c,
+	0x52, 0x0a, 0x72, 0x65, 0x66, 0x65, 0x72, 0x65, 0x6e, 0x63, 0x65, 0x73, 0x12, 0x30, 0x0a, 0x07,
+	0x6e, 0x61, 0x72, 0x69, 0x6e, 0x66, 0x6f, 0x18, 0x03, 0x20, 0x01, 0x28, 0x0b, 0x32, 0x16, 0x2e,
+	0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e, 0x4e, 0x41,
+	0x52, 0x49, 0x6e, 0x66, 0x6f, 0x52, 0x07, 0x6e, 0x61, 0x72, 0x69, 0x6e, 0x66, 0x6f, 0x12, 0x32,
+	0x0a, 0x07, 0x64, 0x65, 0x72, 0x69, 0x76, 0x65, 0x72, 0x18, 0x04, 0x20, 0x01, 0x28, 0x0b, 0x32,
+	0x18, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e,
+	0x53, 0x74, 0x6f, 0x72, 0x65, 0x50, 0x61, 0x74, 0x68, 0x52, 0x07, 0x64, 0x65, 0x72, 0x69, 0x76,
+	0x65, 0x72, 0x22, 0x37, 0x0a, 0x09, 0x53, 0x74, 0x6f, 0x72, 0x65, 0x50, 0x61, 0x74, 0x68, 0x12,
+	0x12, 0x0a, 0x04, 0x6e, 0x61, 0x6d, 0x65, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x04, 0x6e,
+	0x61, 0x6d, 0x65, 0x12, 0x16, 0x0a, 0x06, 0x64, 0x69, 0x67, 0x65, 0x73, 0x74, 0x18, 0x02, 0x20,
+	0x01, 0x28, 0x0c, 0x52, 0x06, 0x64, 0x69, 0x67, 0x65, 0x73, 0x74, 0x22, 0xe3, 0x01, 0x0a, 0x07,
+	0x4e, 0x41, 0x52, 0x49, 0x6e, 0x66, 0x6f, 0x12, 0x19, 0x0a, 0x08, 0x6e, 0x61, 0x72, 0x5f, 0x73,
+	0x69, 0x7a, 0x65, 0x18, 0x01, 0x20, 0x01, 0x28, 0x04, 0x52, 0x07, 0x6e, 0x61, 0x72, 0x53, 0x69,
+	0x7a, 0x65, 0x12, 0x1d, 0x0a, 0x0a, 0x6e, 0x61, 0x72, 0x5f, 0x73, 0x68, 0x61, 0x32, 0x35, 0x36,
+	0x18, 0x02, 0x20, 0x01, 0x28, 0x0c, 0x52, 0x09, 0x6e, 0x61, 0x72, 0x53, 0x68, 0x61, 0x32, 0x35,
+	0x36, 0x12, 0x40, 0x0a, 0x0a, 0x73, 0x69, 0x67, 0x6e, 0x61, 0x74, 0x75, 0x72, 0x65, 0x73, 0x18,
+	0x03, 0x20, 0x03, 0x28, 0x0b, 0x32, 0x20, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f,
+	0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e, 0x4e, 0x41, 0x52, 0x49, 0x6e, 0x66, 0x6f, 0x2e, 0x53, 0x69,
+	0x67, 0x6e, 0x61, 0x74, 0x75, 0x72, 0x65, 0x52, 0x0a, 0x73, 0x69, 0x67, 0x6e, 0x61, 0x74, 0x75,
+	0x72, 0x65, 0x73, 0x12, 0x27, 0x0a, 0x0f, 0x72, 0x65, 0x66, 0x65, 0x72, 0x65, 0x6e, 0x63, 0x65,
+	0x5f, 0x6e, 0x61, 0x6d, 0x65, 0x73, 0x18, 0x04, 0x20, 0x03, 0x28, 0x09, 0x52, 0x0e, 0x72, 0x65,
+	0x66, 0x65, 0x72, 0x65, 0x6e, 0x63, 0x65, 0x4e, 0x61, 0x6d, 0x65, 0x73, 0x1a, 0x33, 0x0a, 0x09,
+	0x53, 0x69, 0x67, 0x6e, 0x61, 0x74, 0x75, 0x72, 0x65, 0x12, 0x12, 0x0a, 0x04, 0x6e, 0x61, 0x6d,
+	0x65, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x04, 0x6e, 0x61, 0x6d, 0x65, 0x12, 0x12, 0x0a,
+	0x04, 0x64, 0x61, 0x74, 0x61, 0x18, 0x02, 0x20, 0x01, 0x28, 0x0c, 0x52, 0x04, 0x64, 0x61, 0x74,
+	0x61, 0x42, 0x28, 0x5a, 0x26, 0x63, 0x6f, 0x64, 0x65, 0x2e, 0x74, 0x76, 0x6c, 0x2e, 0x66, 0x79,
+	0x69, 0x2f, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2f, 0x70, 0x72, 0x6f,
+	0x74, 0x6f, 0x73, 0x3b, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x76, 0x31, 0x62, 0x06, 0x70, 0x72, 0x6f,
+	0x74, 0x6f, 0x33,
+}
+
+var (
+	file_tvix_store_protos_pathinfo_proto_rawDescOnce sync.Once
+	file_tvix_store_protos_pathinfo_proto_rawDescData = file_tvix_store_protos_pathinfo_proto_rawDesc
+)
+
+func file_tvix_store_protos_pathinfo_proto_rawDescGZIP() []byte {
+	file_tvix_store_protos_pathinfo_proto_rawDescOnce.Do(func() {
+		file_tvix_store_protos_pathinfo_proto_rawDescData = protoimpl.X.CompressGZIP(file_tvix_store_protos_pathinfo_proto_rawDescData)
+	})
+	return file_tvix_store_protos_pathinfo_proto_rawDescData
+}
+
+var file_tvix_store_protos_pathinfo_proto_msgTypes = make([]protoimpl.MessageInfo, 4)
+var file_tvix_store_protos_pathinfo_proto_goTypes = []interface{}{
+	(*PathInfo)(nil),          // 0: tvix.store.v1.PathInfo
+	(*StorePath)(nil),         // 1: tvix.store.v1.StorePath
+	(*NARInfo)(nil),           // 2: tvix.store.v1.NARInfo
+	(*NARInfo_Signature)(nil), // 3: tvix.store.v1.NARInfo.Signature
+	(*protos.Node)(nil),       // 4: tvix.castore.v1.Node
+}
+var file_tvix_store_protos_pathinfo_proto_depIdxs = []int32{
+	4, // 0: tvix.store.v1.PathInfo.node:type_name -> tvix.castore.v1.Node
+	2, // 1: tvix.store.v1.PathInfo.narinfo:type_name -> tvix.store.v1.NARInfo
+	1, // 2: tvix.store.v1.PathInfo.deriver:type_name -> tvix.store.v1.StorePath
+	3, // 3: tvix.store.v1.NARInfo.signatures:type_name -> tvix.store.v1.NARInfo.Signature
+	4, // [4:4] is the sub-list for method output_type
+	4, // [4:4] is the sub-list for method input_type
+	4, // [4:4] is the sub-list for extension type_name
+	4, // [4:4] is the sub-list for extension extendee
+	0, // [0:4] is the sub-list for field type_name
+}
+
+func init() { file_tvix_store_protos_pathinfo_proto_init() }
+func file_tvix_store_protos_pathinfo_proto_init() {
+	if File_tvix_store_protos_pathinfo_proto != nil {
+		return
+	}
+	if !protoimpl.UnsafeEnabled {
+		file_tvix_store_protos_pathinfo_proto_msgTypes[0].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*PathInfo); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+		file_tvix_store_protos_pathinfo_proto_msgTypes[1].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*StorePath); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+		file_tvix_store_protos_pathinfo_proto_msgTypes[2].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*NARInfo); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+		file_tvix_store_protos_pathinfo_proto_msgTypes[3].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*NARInfo_Signature); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+	}
+	type x struct{}
+	out := protoimpl.TypeBuilder{
+		File: protoimpl.DescBuilder{
+			GoPackagePath: reflect.TypeOf(x{}).PkgPath(),
+			RawDescriptor: file_tvix_store_protos_pathinfo_proto_rawDesc,
+			NumEnums:      0,
+			NumMessages:   4,
+			NumExtensions: 0,
+			NumServices:   0,
+		},
+		GoTypes:           file_tvix_store_protos_pathinfo_proto_goTypes,
+		DependencyIndexes: file_tvix_store_protos_pathinfo_proto_depIdxs,
+		MessageInfos:      file_tvix_store_protos_pathinfo_proto_msgTypes,
+	}.Build()
+	File_tvix_store_protos_pathinfo_proto = out.File
+	file_tvix_store_protos_pathinfo_proto_rawDesc = nil
+	file_tvix_store_protos_pathinfo_proto_goTypes = nil
+	file_tvix_store_protos_pathinfo_proto_depIdxs = nil
+}
diff --git a/tvix/store-go/pathinfo_test.go b/tvix/store-go/pathinfo_test.go
new file mode 100644
index 0000000000..9a329f0010
--- /dev/null
+++ b/tvix/store-go/pathinfo_test.go
@@ -0,0 +1,149 @@
+package storev1_test
+
+import (
+	"path"
+	"testing"
+
+	"github.com/nix-community/go-nix/pkg/storepath"
+	"github.com/stretchr/testify/assert"
+
+	castorev1pb "code.tvl.fyi/tvix/castore/protos"
+	storev1pb "code.tvl.fyi/tvix/store/protos"
+)
+
+const (
+	EXAMPLE_STORE_PATH = "00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p2017022118243"
+)
+
+var (
+	exampleStorePathDigest = []byte{
+		0x8a, 0x12, 0x32, 0x15, 0x22, 0xfd, 0x91, 0xef, 0xbd, 0x60, 0xeb, 0xb2, 0x48, 0x1a, 0xf8, 0x85,
+		0x80, 0xf6, 0x16, 0x00}
+)
+
+func genPathInfoSymlink() *storev1pb.PathInfo {
+	return &storev1pb.PathInfo{
+		Node: &castorev1pb.Node{
+			Node: &castorev1pb.Node_Symlink{
+				Symlink: &castorev1pb.SymlinkNode{
+					Name:   []byte("00000000000000000000000000000000-dummy"),
+					Target: []byte("/nix/store/somewhereelse"),
+				},
+			},
+		},
+		References: [][]byte{exampleStorePathDigest},
+		Narinfo: &storev1pb.NARInfo{
+			NarSize:        0,
+			NarSha256:      []byte{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
+			Signatures:     []*storev1pb.NARInfo_Signature{},
+			ReferenceNames: []string{EXAMPLE_STORE_PATH},
+		},
+	}
+}
+
+func genPathInfoSymlinkThin() *storev1pb.PathInfo {
+	pi := genPathInfoSymlink()
+	pi.Narinfo = nil
+
+	return pi
+}
+
+func TestValidate(t *testing.T) {
+	t.Run("happy symlink", func(t *testing.T) {
+		storePath, err := genPathInfoSymlink().Validate()
+		assert.NoError(t, err, "PathInfo must validate")
+		assert.Equal(t, "00000000000000000000000000000000-dummy", storePath.String())
+	})
+
+	t.Run("happy symlink thin", func(t *testing.T) {
+		storePath, err := genPathInfoSymlinkThin().Validate()
+		assert.NoError(t, err, "PathInfo must validate")
+		assert.Equal(t, "00000000000000000000000000000000-dummy", storePath.String())
+	})
+
+	t.Run("invalid nar_sha256", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		// create broken references, where the reference digest is wrong
+		pi.Narinfo.NarSha256 = []byte{0xbe, 0xef}
+
+		_, err := pi.Validate()
+		assert.Error(t, err, "must not validate")
+	})
+
+	t.Run("invalid reference digest", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		// create broken references, where the reference digest is wrong
+		pi.References = append(pi.References, []byte{0x00})
+
+		_, err := pi.Validate()
+		assert.Error(t, err, "must not validate")
+	})
+
+	t.Run("invalid reference name", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		// make the reference name an invalid store path
+		pi.Narinfo.ReferenceNames[0] = "00000000000000000000000000000000-"
+
+		_, err := pi.Validate()
+		assert.Error(t, err, "must not validate")
+	})
+
+	t.Run("reference name digest mismatch", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		// cause the digest for the reference to mismatch
+		pi.Narinfo.ReferenceNames[0] = "11111111111111111111111111111111-dummy"
+
+		_, err := pi.Validate()
+		assert.Error(t, err, "must not validate")
+	})
+
+	t.Run("nil root node", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		pi.Node = nil
+
+		_, err := pi.Validate()
+		assert.Error(t, err, "must not validate")
+	})
+
+	t.Run("invalid root node name", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		// make the reference name an invalid store path - it may not be absolute
+		symlinkNode := pi.Node.GetSymlink()
+		symlinkNode.Name = []byte(path.Join(storepath.StoreDir, "00000000000000000000000000000000-dummy"))
+
+		_, err := pi.Validate()
+		assert.Error(t, err, "must not validate")
+	})
+
+	t.Run("happy deriver", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		// add the Deriver Field.
+		pi.Deriver = &storev1pb.StorePath{
+			Digest: exampleStorePathDigest,
+			Name:   "foo",
+		}
+
+		_, err := pi.Validate()
+		assert.NoError(t, err, "must validate")
+	})
+
+	t.Run("invalid deriver", func(t *testing.T) {
+		pi := genPathInfoSymlink()
+
+		// add the Deriver Field, with a broken digest
+		pi.Deriver = &storev1pb.StorePath{
+			Digest: []byte{},
+			Name:   "foo2",
+		}
+		_, err := pi.Validate()
+		assert.Error(t, err, "must not validate")
+	})
+
+}
diff --git a/tvix/store-go/pick_next_node_test.go b/tvix/store-go/pick_next_node_test.go
new file mode 100644
index 0000000000..830c6cacc1
--- /dev/null
+++ b/tvix/store-go/pick_next_node_test.go
@@ -0,0 +1,51 @@
+package storev1
+
+import (
+	"testing"
+
+	castorev1pb "code.tvl.fyi/tvix/castore/protos"
+	"github.com/google/go-cmp/cmp"
+	"github.com/stretchr/testify/require"
+	"google.golang.org/protobuf/testing/protocmp"
+)
+
+func requireProtoEq(t *testing.T, expected interface{}, actual interface{}) {
+	if diff := cmp.Diff(expected, actual, protocmp.Transform()); diff != "" {
+		t.Errorf("unexpected difference:\n%v", diff)
+	}
+}
+
+func TestPopNextNode(t *testing.T) {
+	t.Run("empty directory", func(t *testing.T) {
+		d := &castorev1pb.Directory{
+			Directories: []*castorev1pb.DirectoryNode{},
+			Files:       []*castorev1pb.FileNode{},
+			Symlinks:    []*castorev1pb.SymlinkNode{},
+		}
+
+		n := drainNextNode(d)
+		require.Equal(t, nil, n)
+	})
+	t.Run("only directories", func(t *testing.T) {
+		ds := &castorev1pb.Directory{
+			Directories: []*castorev1pb.DirectoryNode{{
+				Name:   []byte("a"),
+				Digest: []byte{},
+				Size:   0,
+			}, {
+				Name:   []byte("b"),
+				Digest: []byte{},
+				Size:   0,
+			}},
+			Files:    []*castorev1pb.FileNode{},
+			Symlinks: []*castorev1pb.SymlinkNode{},
+		}
+
+		n := drainNextNode(ds)
+		requireProtoEq(t, &castorev1pb.DirectoryNode{
+			Name:   []byte("a"),
+			Digest: []byte{},
+			Size:   0,
+		}, n)
+	})
+}
diff --git a/tvix/store-go/rpc_pathinfo.pb.go b/tvix/store-go/rpc_pathinfo.pb.go
new file mode 100644
index 0000000000..8a3c10a821
--- /dev/null
+++ b/tvix/store-go/rpc_pathinfo.pb.go
@@ -0,0 +1,348 @@
+// SPDX-License-Identifier: MIT
+// Copyright © 2022 The Tvix Authors
+
+// Code generated by protoc-gen-go. DO NOT EDIT.
+// versions:
+// 	protoc-gen-go v1.31.0
+// 	protoc        (unknown)
+// source: tvix/store/protos/rpc_pathinfo.proto
+
+package storev1
+
+import (
+	protos "code.tvl.fyi/tvix/castore/protos"
+	protoreflect "google.golang.org/protobuf/reflect/protoreflect"
+	protoimpl "google.golang.org/protobuf/runtime/protoimpl"
+	reflect "reflect"
+	sync "sync"
+)
+
+const (
+	// Verify that this generated code is sufficiently up-to-date.
+	_ = protoimpl.EnforceVersion(20 - protoimpl.MinVersion)
+	// Verify that runtime/protoimpl is sufficiently up-to-date.
+	_ = protoimpl.EnforceVersion(protoimpl.MaxVersion - 20)
+)
+
+// The parameters that can be used to lookup a (single) PathInfo object.
+// Currently, only a lookup by output hash is supported.
+type GetPathInfoRequest struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	// Types that are assignable to ByWhat:
+	//
+	//	*GetPathInfoRequest_ByOutputHash
+	ByWhat isGetPathInfoRequest_ByWhat `protobuf_oneof:"by_what"`
+}
+
+func (x *GetPathInfoRequest) Reset() {
+	*x = GetPathInfoRequest{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[0]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *GetPathInfoRequest) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*GetPathInfoRequest) ProtoMessage() {}
+
+func (x *GetPathInfoRequest) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[0]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use GetPathInfoRequest.ProtoReflect.Descriptor instead.
+func (*GetPathInfoRequest) Descriptor() ([]byte, []int) {
+	return file_tvix_store_protos_rpc_pathinfo_proto_rawDescGZIP(), []int{0}
+}
+
+func (m *GetPathInfoRequest) GetByWhat() isGetPathInfoRequest_ByWhat {
+	if m != nil {
+		return m.ByWhat
+	}
+	return nil
+}
+
+func (x *GetPathInfoRequest) GetByOutputHash() []byte {
+	if x, ok := x.GetByWhat().(*GetPathInfoRequest_ByOutputHash); ok {
+		return x.ByOutputHash
+	}
+	return nil
+}
+
+type isGetPathInfoRequest_ByWhat interface {
+	isGetPathInfoRequest_ByWhat()
+}
+
+type GetPathInfoRequest_ByOutputHash struct {
+	// The output hash of a nix path (20 bytes).
+	// This is the nixbase32-decoded portion of a Nix output path, so to substitute
+	// /nix/store/xm35nga2g20mz5sm5l6n8v3bdm86yj83-cowsay-3.04
+	// this field would contain nixbase32dec("xm35nga2g20mz5sm5l6n8v3bdm86yj83").
+	ByOutputHash []byte `protobuf:"bytes,1,opt,name=by_output_hash,json=byOutputHash,proto3,oneof"`
+}
+
+func (*GetPathInfoRequest_ByOutputHash) isGetPathInfoRequest_ByWhat() {}
+
+// The parameters that can be used to lookup (multiple) PathInfo objects.
+// Currently no filtering is possible, all objects are returned.
+type ListPathInfoRequest struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+}
+
+func (x *ListPathInfoRequest) Reset() {
+	*x = ListPathInfoRequest{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[1]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *ListPathInfoRequest) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*ListPathInfoRequest) ProtoMessage() {}
+
+func (x *ListPathInfoRequest) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[1]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use ListPathInfoRequest.ProtoReflect.Descriptor instead.
+func (*ListPathInfoRequest) Descriptor() ([]byte, []int) {
+	return file_tvix_store_protos_rpc_pathinfo_proto_rawDescGZIP(), []int{1}
+}
+
+// CalculateNARResponse is the response returned by the CalculateNAR request.
+//
+// It contains the size of the NAR representation (in bytes), and the sha56
+// digest.
+type CalculateNARResponse struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	// This size of the NAR file, in bytes.
+	NarSize uint64 `protobuf:"varint,1,opt,name=nar_size,json=narSize,proto3" json:"nar_size,omitempty"`
+	// The sha256 of the NAR file representation.
+	NarSha256 []byte `protobuf:"bytes,2,opt,name=nar_sha256,json=narSha256,proto3" json:"nar_sha256,omitempty"`
+}
+
+func (x *CalculateNARResponse) Reset() {
+	*x = CalculateNARResponse{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[2]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *CalculateNARResponse) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*CalculateNARResponse) ProtoMessage() {}
+
+func (x *CalculateNARResponse) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[2]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use CalculateNARResponse.ProtoReflect.Descriptor instead.
+func (*CalculateNARResponse) Descriptor() ([]byte, []int) {
+	return file_tvix_store_protos_rpc_pathinfo_proto_rawDescGZIP(), []int{2}
+}
+
+func (x *CalculateNARResponse) GetNarSize() uint64 {
+	if x != nil {
+		return x.NarSize
+	}
+	return 0
+}
+
+func (x *CalculateNARResponse) GetNarSha256() []byte {
+	if x != nil {
+		return x.NarSha256
+	}
+	return nil
+}
+
+var File_tvix_store_protos_rpc_pathinfo_proto protoreflect.FileDescriptor
+
+var file_tvix_store_protos_rpc_pathinfo_proto_rawDesc = []byte{
+	0x0a, 0x24, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2f, 0x70, 0x72, 0x6f,
+	0x74, 0x6f, 0x73, 0x2f, 0x72, 0x70, 0x63, 0x5f, 0x70, 0x61, 0x74, 0x68, 0x69, 0x6e, 0x66, 0x6f,
+	0x2e, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x12, 0x0d, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f,
+	0x72, 0x65, 0x2e, 0x76, 0x31, 0x1a, 0x20, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x73, 0x74, 0x6f, 0x72,
+	0x65, 0x2f, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x73, 0x2f, 0x70, 0x61, 0x74, 0x68, 0x69, 0x6e, 0x66,
+	0x6f, 0x2e, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x1a, 0x21, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x63, 0x61,
+	0x73, 0x74, 0x6f, 0x72, 0x65, 0x2f, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x73, 0x2f, 0x63, 0x61, 0x73,
+	0x74, 0x6f, 0x72, 0x65, 0x2e, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x22, 0x47, 0x0a, 0x12, 0x47, 0x65,
+	0x74, 0x50, 0x61, 0x74, 0x68, 0x49, 0x6e, 0x66, 0x6f, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74,
+	0x12, 0x26, 0x0a, 0x0e, 0x62, 0x79, 0x5f, 0x6f, 0x75, 0x74, 0x70, 0x75, 0x74, 0x5f, 0x68, 0x61,
+	0x73, 0x68, 0x18, 0x01, 0x20, 0x01, 0x28, 0x0c, 0x48, 0x00, 0x52, 0x0c, 0x62, 0x79, 0x4f, 0x75,
+	0x74, 0x70, 0x75, 0x74, 0x48, 0x61, 0x73, 0x68, 0x42, 0x09, 0x0a, 0x07, 0x62, 0x79, 0x5f, 0x77,
+	0x68, 0x61, 0x74, 0x22, 0x15, 0x0a, 0x13, 0x4c, 0x69, 0x73, 0x74, 0x50, 0x61, 0x74, 0x68, 0x49,
+	0x6e, 0x66, 0x6f, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x22, 0x50, 0x0a, 0x14, 0x43, 0x61,
+	0x6c, 0x63, 0x75, 0x6c, 0x61, 0x74, 0x65, 0x4e, 0x41, 0x52, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e,
+	0x73, 0x65, 0x12, 0x19, 0x0a, 0x08, 0x6e, 0x61, 0x72, 0x5f, 0x73, 0x69, 0x7a, 0x65, 0x18, 0x01,
+	0x20, 0x01, 0x28, 0x04, 0x52, 0x07, 0x6e, 0x61, 0x72, 0x53, 0x69, 0x7a, 0x65, 0x12, 0x1d, 0x0a,
+	0x0a, 0x6e, 0x61, 0x72, 0x5f, 0x73, 0x68, 0x61, 0x32, 0x35, 0x36, 0x18, 0x02, 0x20, 0x01, 0x28,
+	0x0c, 0x52, 0x09, 0x6e, 0x61, 0x72, 0x53, 0x68, 0x61, 0x32, 0x35, 0x36, 0x32, 0xa0, 0x02, 0x0a,
+	0x0f, 0x50, 0x61, 0x74, 0x68, 0x49, 0x6e, 0x66, 0x6f, 0x53, 0x65, 0x72, 0x76, 0x69, 0x63, 0x65,
+	0x12, 0x41, 0x0a, 0x03, 0x47, 0x65, 0x74, 0x12, 0x21, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73,
+	0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e, 0x47, 0x65, 0x74, 0x50, 0x61, 0x74, 0x68, 0x49,
+	0x6e, 0x66, 0x6f, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x1a, 0x17, 0x2e, 0x74, 0x76, 0x69,
+	0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e, 0x50, 0x61, 0x74, 0x68, 0x49,
+	0x6e, 0x66, 0x6f, 0x12, 0x37, 0x0a, 0x03, 0x50, 0x75, 0x74, 0x12, 0x17, 0x2e, 0x74, 0x76, 0x69,
+	0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e, 0x50, 0x61, 0x74, 0x68, 0x49,
+	0x6e, 0x66, 0x6f, 0x1a, 0x17, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65,
+	0x2e, 0x76, 0x31, 0x2e, 0x50, 0x61, 0x74, 0x68, 0x49, 0x6e, 0x66, 0x6f, 0x12, 0x4a, 0x0a, 0x0c,
+	0x43, 0x61, 0x6c, 0x63, 0x75, 0x6c, 0x61, 0x74, 0x65, 0x4e, 0x41, 0x52, 0x12, 0x15, 0x2e, 0x74,
+	0x76, 0x69, 0x78, 0x2e, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e, 0x4e,
+	0x6f, 0x64, 0x65, 0x1a, 0x23, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65,
+	0x2e, 0x76, 0x31, 0x2e, 0x43, 0x61, 0x6c, 0x63, 0x75, 0x6c, 0x61, 0x74, 0x65, 0x4e, 0x41, 0x52,
+	0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x12, 0x45, 0x0a, 0x04, 0x4c, 0x69, 0x73, 0x74,
+	0x12, 0x22, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31,
+	0x2e, 0x4c, 0x69, 0x73, 0x74, 0x50, 0x61, 0x74, 0x68, 0x49, 0x6e, 0x66, 0x6f, 0x52, 0x65, 0x71,
+	0x75, 0x65, 0x73, 0x74, 0x1a, 0x17, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x73, 0x74, 0x6f, 0x72,
+	0x65, 0x2e, 0x76, 0x31, 0x2e, 0x50, 0x61, 0x74, 0x68, 0x49, 0x6e, 0x66, 0x6f, 0x30, 0x01, 0x42,
+	0x28, 0x5a, 0x26, 0x63, 0x6f, 0x64, 0x65, 0x2e, 0x74, 0x76, 0x6c, 0x2e, 0x66, 0x79, 0x69, 0x2f,
+	0x74, 0x76, 0x69, 0x78, 0x2f, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2f, 0x70, 0x72, 0x6f, 0x74, 0x6f,
+	0x73, 0x3b, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x76, 0x31, 0x62, 0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f,
+	0x33,
+}
+
+var (
+	file_tvix_store_protos_rpc_pathinfo_proto_rawDescOnce sync.Once
+	file_tvix_store_protos_rpc_pathinfo_proto_rawDescData = file_tvix_store_protos_rpc_pathinfo_proto_rawDesc
+)
+
+func file_tvix_store_protos_rpc_pathinfo_proto_rawDescGZIP() []byte {
+	file_tvix_store_protos_rpc_pathinfo_proto_rawDescOnce.Do(func() {
+		file_tvix_store_protos_rpc_pathinfo_proto_rawDescData = protoimpl.X.CompressGZIP(file_tvix_store_protos_rpc_pathinfo_proto_rawDescData)
+	})
+	return file_tvix_store_protos_rpc_pathinfo_proto_rawDescData
+}
+
+var file_tvix_store_protos_rpc_pathinfo_proto_msgTypes = make([]protoimpl.MessageInfo, 3)
+var file_tvix_store_protos_rpc_pathinfo_proto_goTypes = []interface{}{
+	(*GetPathInfoRequest)(nil),   // 0: tvix.store.v1.GetPathInfoRequest
+	(*ListPathInfoRequest)(nil),  // 1: tvix.store.v1.ListPathInfoRequest
+	(*CalculateNARResponse)(nil), // 2: tvix.store.v1.CalculateNARResponse
+	(*PathInfo)(nil),             // 3: tvix.store.v1.PathInfo
+	(*protos.Node)(nil),          // 4: tvix.castore.v1.Node
+}
+var file_tvix_store_protos_rpc_pathinfo_proto_depIdxs = []int32{
+	0, // 0: tvix.store.v1.PathInfoService.Get:input_type -> tvix.store.v1.GetPathInfoRequest
+	3, // 1: tvix.store.v1.PathInfoService.Put:input_type -> tvix.store.v1.PathInfo
+	4, // 2: tvix.store.v1.PathInfoService.CalculateNAR:input_type -> tvix.castore.v1.Node
+	1, // 3: tvix.store.v1.PathInfoService.List:input_type -> tvix.store.v1.ListPathInfoRequest
+	3, // 4: tvix.store.v1.PathInfoService.Get:output_type -> tvix.store.v1.PathInfo
+	3, // 5: tvix.store.v1.PathInfoService.Put:output_type -> tvix.store.v1.PathInfo
+	2, // 6: tvix.store.v1.PathInfoService.CalculateNAR:output_type -> tvix.store.v1.CalculateNARResponse
+	3, // 7: tvix.store.v1.PathInfoService.List:output_type -> tvix.store.v1.PathInfo
+	4, // [4:8] is the sub-list for method output_type
+	0, // [0:4] is the sub-list for method input_type
+	0, // [0:0] is the sub-list for extension type_name
+	0, // [0:0] is the sub-list for extension extendee
+	0, // [0:0] is the sub-list for field type_name
+}
+
+func init() { file_tvix_store_protos_rpc_pathinfo_proto_init() }
+func file_tvix_store_protos_rpc_pathinfo_proto_init() {
+	if File_tvix_store_protos_rpc_pathinfo_proto != nil {
+		return
+	}
+	file_tvix_store_protos_pathinfo_proto_init()
+	if !protoimpl.UnsafeEnabled {
+		file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[0].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*GetPathInfoRequest); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+		file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[1].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*ListPathInfoRequest); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+		file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[2].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*CalculateNARResponse); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+	}
+	file_tvix_store_protos_rpc_pathinfo_proto_msgTypes[0].OneofWrappers = []interface{}{
+		(*GetPathInfoRequest_ByOutputHash)(nil),
+	}
+	type x struct{}
+	out := protoimpl.TypeBuilder{
+		File: protoimpl.DescBuilder{
+			GoPackagePath: reflect.TypeOf(x{}).PkgPath(),
+			RawDescriptor: file_tvix_store_protos_rpc_pathinfo_proto_rawDesc,
+			NumEnums:      0,
+			NumMessages:   3,
+			NumExtensions: 0,
+			NumServices:   1,
+		},
+		GoTypes:           file_tvix_store_protos_rpc_pathinfo_proto_goTypes,
+		DependencyIndexes: file_tvix_store_protos_rpc_pathinfo_proto_depIdxs,
+		MessageInfos:      file_tvix_store_protos_rpc_pathinfo_proto_msgTypes,
+	}.Build()
+	File_tvix_store_protos_rpc_pathinfo_proto = out.File
+	file_tvix_store_protos_rpc_pathinfo_proto_rawDesc = nil
+	file_tvix_store_protos_rpc_pathinfo_proto_goTypes = nil
+	file_tvix_store_protos_rpc_pathinfo_proto_depIdxs = nil
+}
diff --git a/tvix/store-go/rpc_pathinfo_grpc.pb.go b/tvix/store-go/rpc_pathinfo_grpc.pb.go
new file mode 100644
index 0000000000..10d8a7ffa4
--- /dev/null
+++ b/tvix/store-go/rpc_pathinfo_grpc.pb.go
@@ -0,0 +1,308 @@
+// SPDX-License-Identifier: MIT
+// Copyright © 2022 The Tvix Authors
+
+// Code generated by protoc-gen-go-grpc. DO NOT EDIT.
+// versions:
+// - protoc-gen-go-grpc v1.3.0
+// - protoc             (unknown)
+// source: tvix/store/protos/rpc_pathinfo.proto
+
+package storev1
+
+import (
+	protos "code.tvl.fyi/tvix/castore/protos"
+	context "context"
+	grpc "google.golang.org/grpc"
+	codes "google.golang.org/grpc/codes"
+	status "google.golang.org/grpc/status"
+)
+
+// This is a compile-time assertion to ensure that this generated file
+// is compatible with the grpc package it is being compiled against.
+// Requires gRPC-Go v1.32.0 or later.
+const _ = grpc.SupportPackageIsVersion7
+
+const (
+	PathInfoService_Get_FullMethodName          = "/tvix.store.v1.PathInfoService/Get"
+	PathInfoService_Put_FullMethodName          = "/tvix.store.v1.PathInfoService/Put"
+	PathInfoService_CalculateNAR_FullMethodName = "/tvix.store.v1.PathInfoService/CalculateNAR"
+	PathInfoService_List_FullMethodName         = "/tvix.store.v1.PathInfoService/List"
+)
+
+// PathInfoServiceClient is the client API for PathInfoService service.
+//
+// For semantics around ctx use and closing/ending streaming RPCs, please refer to https://pkg.go.dev/google.golang.org/grpc/?tab=doc#ClientConn.NewStream.
+type PathInfoServiceClient interface {
+	// Return a PathInfo message matching the criteria specified in the
+	// GetPathInfoRequest message.
+	Get(ctx context.Context, in *GetPathInfoRequest, opts ...grpc.CallOption) (*PathInfo, error)
+	// Upload a PathInfo object to the remote end. It MUST not return until the
+	// PathInfo object has been written on the the remote end.
+	//
+	// The remote end MAY check if a potential DirectoryNode has already been
+	// uploaded.
+	//
+	// Uploading clients SHOULD obviously not steer other machines to try to
+	// substitute before from the remote end before having finished uploading
+	// PathInfo, Directories and Blobs.
+	// The returned PathInfo object MAY contain additional narinfo signatures,
+	// but is otherwise left untouched.
+	Put(ctx context.Context, in *PathInfo, opts ...grpc.CallOption) (*PathInfo, error)
+	// Calculate the NAR representation of the contents specified by the
+	// root_node. The calculation SHOULD be cached server-side for subsequent
+	// requests.
+	//
+	// All references (to blobs or Directory messages) MUST already exist in
+	// the store.
+	//
+	// The method can be used to produce a Nix fixed-output path, which
+	// contains the (compressed) sha256 of the NAR content representation in
+	// the root_node name (suffixed with the name).
+	//
+	// It can also be used to calculate arbitrary NAR hashes of output paths,
+	// in case a legacy Nix Binary Cache frontend is provided.
+	CalculateNAR(ctx context.Context, in *protos.Node, opts ...grpc.CallOption) (*CalculateNARResponse, error)
+	// Return a stream of PathInfo messages matching the criteria specified in
+	// ListPathInfoRequest.
+	List(ctx context.Context, in *ListPathInfoRequest, opts ...grpc.CallOption) (PathInfoService_ListClient, error)
+}
+
+type pathInfoServiceClient struct {
+	cc grpc.ClientConnInterface
+}
+
+func NewPathInfoServiceClient(cc grpc.ClientConnInterface) PathInfoServiceClient {
+	return &pathInfoServiceClient{cc}
+}
+
+func (c *pathInfoServiceClient) Get(ctx context.Context, in *GetPathInfoRequest, opts ...grpc.CallOption) (*PathInfo, error) {
+	out := new(PathInfo)
+	err := c.cc.Invoke(ctx, PathInfoService_Get_FullMethodName, in, out, opts...)
+	if err != nil {
+		return nil, err
+	}
+	return out, nil
+}
+
+func (c *pathInfoServiceClient) Put(ctx context.Context, in *PathInfo, opts ...grpc.CallOption) (*PathInfo, error) {
+	out := new(PathInfo)
+	err := c.cc.Invoke(ctx, PathInfoService_Put_FullMethodName, in, out, opts...)
+	if err != nil {
+		return nil, err
+	}
+	return out, nil
+}
+
+func (c *pathInfoServiceClient) CalculateNAR(ctx context.Context, in *protos.Node, opts ...grpc.CallOption) (*CalculateNARResponse, error) {
+	out := new(CalculateNARResponse)
+	err := c.cc.Invoke(ctx, PathInfoService_CalculateNAR_FullMethodName, in, out, opts...)
+	if err != nil {
+		return nil, err
+	}
+	return out, nil
+}
+
+func (c *pathInfoServiceClient) List(ctx context.Context, in *ListPathInfoRequest, opts ...grpc.CallOption) (PathInfoService_ListClient, error) {
+	stream, err := c.cc.NewStream(ctx, &PathInfoService_ServiceDesc.Streams[0], PathInfoService_List_FullMethodName, opts...)
+	if err != nil {
+		return nil, err
+	}
+	x := &pathInfoServiceListClient{stream}
+	if err := x.ClientStream.SendMsg(in); err != nil {
+		return nil, err
+	}
+	if err := x.ClientStream.CloseSend(); err != nil {
+		return nil, err
+	}
+	return x, nil
+}
+
+type PathInfoService_ListClient interface {
+	Recv() (*PathInfo, error)
+	grpc.ClientStream
+}
+
+type pathInfoServiceListClient struct {
+	grpc.ClientStream
+}
+
+func (x *pathInfoServiceListClient) Recv() (*PathInfo, error) {
+	m := new(PathInfo)
+	if err := x.ClientStream.RecvMsg(m); err != nil {
+		return nil, err
+	}
+	return m, nil
+}
+
+// PathInfoServiceServer is the server API for PathInfoService service.
+// All implementations must embed UnimplementedPathInfoServiceServer
+// for forward compatibility
+type PathInfoServiceServer interface {
+	// Return a PathInfo message matching the criteria specified in the
+	// GetPathInfoRequest message.
+	Get(context.Context, *GetPathInfoRequest) (*PathInfo, error)
+	// Upload a PathInfo object to the remote end. It MUST not return until the
+	// PathInfo object has been written on the the remote end.
+	//
+	// The remote end MAY check if a potential DirectoryNode has already been
+	// uploaded.
+	//
+	// Uploading clients SHOULD obviously not steer other machines to try to
+	// substitute before from the remote end before having finished uploading
+	// PathInfo, Directories and Blobs.
+	// The returned PathInfo object MAY contain additional narinfo signatures,
+	// but is otherwise left untouched.
+	Put(context.Context, *PathInfo) (*PathInfo, error)
+	// Calculate the NAR representation of the contents specified by the
+	// root_node. The calculation SHOULD be cached server-side for subsequent
+	// requests.
+	//
+	// All references (to blobs or Directory messages) MUST already exist in
+	// the store.
+	//
+	// The method can be used to produce a Nix fixed-output path, which
+	// contains the (compressed) sha256 of the NAR content representation in
+	// the root_node name (suffixed with the name).
+	//
+	// It can also be used to calculate arbitrary NAR hashes of output paths,
+	// in case a legacy Nix Binary Cache frontend is provided.
+	CalculateNAR(context.Context, *protos.Node) (*CalculateNARResponse, error)
+	// Return a stream of PathInfo messages matching the criteria specified in
+	// ListPathInfoRequest.
+	List(*ListPathInfoRequest, PathInfoService_ListServer) error
+	mustEmbedUnimplementedPathInfoServiceServer()
+}
+
+// UnimplementedPathInfoServiceServer must be embedded to have forward compatible implementations.
+type UnimplementedPathInfoServiceServer struct {
+}
+
+func (UnimplementedPathInfoServiceServer) Get(context.Context, *GetPathInfoRequest) (*PathInfo, error) {
+	return nil, status.Errorf(codes.Unimplemented, "method Get not implemented")
+}
+func (UnimplementedPathInfoServiceServer) Put(context.Context, *PathInfo) (*PathInfo, error) {
+	return nil, status.Errorf(codes.Unimplemented, "method Put not implemented")
+}
+func (UnimplementedPathInfoServiceServer) CalculateNAR(context.Context, *protos.Node) (*CalculateNARResponse, error) {
+	return nil, status.Errorf(codes.Unimplemented, "method CalculateNAR not implemented")
+}
+func (UnimplementedPathInfoServiceServer) List(*ListPathInfoRequest, PathInfoService_ListServer) error {
+	return status.Errorf(codes.Unimplemented, "method List not implemented")
+}
+func (UnimplementedPathInfoServiceServer) mustEmbedUnimplementedPathInfoServiceServer() {}
+
+// UnsafePathInfoServiceServer may be embedded to opt out of forward compatibility for this service.
+// Use of this interface is not recommended, as added methods to PathInfoServiceServer will
+// result in compilation errors.
+type UnsafePathInfoServiceServer interface {
+	mustEmbedUnimplementedPathInfoServiceServer()
+}
+
+func RegisterPathInfoServiceServer(s grpc.ServiceRegistrar, srv PathInfoServiceServer) {
+	s.RegisterService(&PathInfoService_ServiceDesc, srv)
+}
+
+func _PathInfoService_Get_Handler(srv interface{}, ctx context.Context, dec func(interface{}) error, interceptor grpc.UnaryServerInterceptor) (interface{}, error) {
+	in := new(GetPathInfoRequest)
+	if err := dec(in); err != nil {
+		return nil, err
+	}
+	if interceptor == nil {
+		return srv.(PathInfoServiceServer).Get(ctx, in)
+	}
+	info := &grpc.UnaryServerInfo{
+		Server:     srv,
+		FullMethod: PathInfoService_Get_FullMethodName,
+	}
+	handler := func(ctx context.Context, req interface{}) (interface{}, error) {
+		return srv.(PathInfoServiceServer).Get(ctx, req.(*GetPathInfoRequest))
+	}
+	return interceptor(ctx, in, info, handler)
+}
+
+func _PathInfoService_Put_Handler(srv interface{}, ctx context.Context, dec func(interface{}) error, interceptor grpc.UnaryServerInterceptor) (interface{}, error) {
+	in := new(PathInfo)
+	if err := dec(in); err != nil {
+		return nil, err
+	}
+	if interceptor == nil {
+		return srv.(PathInfoServiceServer).Put(ctx, in)
+	}
+	info := &grpc.UnaryServerInfo{
+		Server:     srv,
+		FullMethod: PathInfoService_Put_FullMethodName,
+	}
+	handler := func(ctx context.Context, req interface{}) (interface{}, error) {
+		return srv.(PathInfoServiceServer).Put(ctx, req.(*PathInfo))
+	}
+	return interceptor(ctx, in, info, handler)
+}
+
+func _PathInfoService_CalculateNAR_Handler(srv interface{}, ctx context.Context, dec func(interface{}) error, interceptor grpc.UnaryServerInterceptor) (interface{}, error) {
+	in := new(protos.Node)
+	if err := dec(in); err != nil {
+		return nil, err
+	}
+	if interceptor == nil {
+		return srv.(PathInfoServiceServer).CalculateNAR(ctx, in)
+	}
+	info := &grpc.UnaryServerInfo{
+		Server:     srv,
+		FullMethod: PathInfoService_CalculateNAR_FullMethodName,
+	}
+	handler := func(ctx context.Context, req interface{}) (interface{}, error) {
+		return srv.(PathInfoServiceServer).CalculateNAR(ctx, req.(*protos.Node))
+	}
+	return interceptor(ctx, in, info, handler)
+}
+
+func _PathInfoService_List_Handler(srv interface{}, stream grpc.ServerStream) error {
+	m := new(ListPathInfoRequest)
+	if err := stream.RecvMsg(m); err != nil {
+		return err
+	}
+	return srv.(PathInfoServiceServer).List(m, &pathInfoServiceListServer{stream})
+}
+
+type PathInfoService_ListServer interface {
+	Send(*PathInfo) error
+	grpc.ServerStream
+}
+
+type pathInfoServiceListServer struct {
+	grpc.ServerStream
+}
+
+func (x *pathInfoServiceListServer) Send(m *PathInfo) error {
+	return x.ServerStream.SendMsg(m)
+}
+
+// PathInfoService_ServiceDesc is the grpc.ServiceDesc for PathInfoService service.
+// It's only intended for direct use with grpc.RegisterService,
+// and not to be introspected or modified (even as a copy)
+var PathInfoService_ServiceDesc = grpc.ServiceDesc{
+	ServiceName: "tvix.store.v1.PathInfoService",
+	HandlerType: (*PathInfoServiceServer)(nil),
+	Methods: []grpc.MethodDesc{
+		{
+			MethodName: "Get",
+			Handler:    _PathInfoService_Get_Handler,
+		},
+		{
+			MethodName: "Put",
+			Handler:    _PathInfoService_Put_Handler,
+		},
+		{
+			MethodName: "CalculateNAR",
+			Handler:    _PathInfoService_CalculateNAR_Handler,
+		},
+	},
+	Streams: []grpc.StreamDesc{
+		{
+			StreamName:    "List",
+			Handler:       _PathInfoService_List_Handler,
+			ServerStreams: true,
+		},
+	},
+	Metadata: "tvix/store/protos/rpc_pathinfo.proto",
+}
diff --git a/tvix/store-go/testdata/emptydirectory.nar b/tvix/store-go/testdata/emptydirectory.nar
new file mode 100644
index 0000000000..baba558622
--- /dev/null
+++ b/tvix/store-go/testdata/emptydirectory.nar
Binary files differdiff --git a/tvix/store-go/testdata/onebyteregular.nar b/tvix/store-go/testdata/onebyteregular.nar
new file mode 100644
index 0000000000..b8c94932bf
--- /dev/null
+++ b/tvix/store-go/testdata/onebyteregular.nar
Binary files differdiff --git a/tvix/store-go/testdata/symlink.nar b/tvix/store-go/testdata/symlink.nar
new file mode 100644
index 0000000000..7990e4ad5b
--- /dev/null
+++ b/tvix/store-go/testdata/symlink.nar
Binary files differ