Non-committers can't keep authenticated forks updated

[45mg]

Hi Guix,

First of all, please spare me a few paragraphs to explain why I'm CC'ing
guix-devel on this bug report (I promise it's a good reason this time!).

Introduction
============

As has been mentioned many, MANY times on these lists, patch review is
erratic in Guix, and patches can be neglected for months. This can be
frustrating when you /need/ those patches on your own system (esp. when
you're patching anything under guix/, and not just adding or updating
packages). To avoid this frustration, as suggested by Felix Lechner [1],
one can fork Guix, apply patches in a separate branch, and `guix pull`
from that branch. Given that even a moderately active contributor will
probably have multiple open patches at any point in time, this needs to
work as a long-term arrangement - which means the fork needs to be kept
updated with upstream Guix.

Next, authentication. I'm sure I don't need to justify the need to
authenticate the code that our systems run on, especially since this
project has done so for years now. Especially for those of us that host
our forks remotely and pull over a network, pulling with
`--disable-authentication` becomes a security risk.

Now, finally, I can state the problem at hand - Unless you are
authorized to make authenticated commits into upstream Guix, /you cannot
keep an authenticated fork updated/. (Explanation to follow.)

This is a serious problem for anyone who's looking to become more active
in Guix; they must either give up security to use a fork, or wait months
before being able to benefit from their own work.

Explanation
===========

To the best of my knowledge, this problem was first mentioned on
Help-Guix by Tomas Volf [2], who patched `guix git authenticate` to work
around it [3]. Here's (a touched-up version of) the explanation of this
issue found in that patch's description:

--8<---------------cut here---------------start------------->8---
When authenticating merge commits, intersection of authorized keys from
all parents is used. That is fine in Guix proper, since all involved
commits are under the control of the Guix committers, however it does
not work that well for authenticating merge commits in forks.

When Guix fork is created (starting from Guix-proper commit A), new
commit (authorizing the fork creator's signing key K) is created (I).
Later, when update from Guix proper (U) is merged, new merge commit is
created (M):

     M
    / \
   I   U
    \ /
     A

The M is signed with the K. However since the K is allowed by only one
parent (I), it will not be in the set of authorized keys (intersection
of keys from I and U). So, commit M cannot be authenticated.

Thus, an authenticated fork cannot be kept updated.
--8<---------------cut here---------------end--------------->8---

A Prospective Solution
======================

I discovered Tomas's patch [3] more than a year later. I initially
wanted to contribute it upstream to solve this issue, but I discovered
that it leaves room for a rather serious attack [4]. So I had to rule it
out.

After some brainstorming, I thought of a solution. I'm paraphrasing the
relevant part of the mail in which I articulated it [5] below (this mail
should be a reply to that one):

--8<---------------cut here---------------start------------->8---
I think I may have an idea myself; one that seems reasonably clean,
would fix our use-case of authenticating our own personal Guix forks,
and would even allow pulling branches from other people's forks and
authenticating those.

We could allow users to specify additional channel introductions. So,
there's always one primary introduction, but there can also be one or
more additional ones.

Commits with only one parent are authenticated normally.

For commits that have multiple parents - ie. merge commits - we weaken
the authorization invariant [6] as follows:

1. If all parents have the primary introduction as their most recent
   ancestor, then the invariant holds as usual.
   
2. If one or more parents has the primary introduction as its most
   recent ancestor (call these the 'primary parents'), and the rest have
   any of the additional introductions, then the merge commit is
   authenticated if and only if:
   a) it's signed by a key authorized in all of the primary parents, AND
   b) the /first parent/ [^] of the merge commit is a primary parent.
   
3. If all parents have the same additional introduction as their most
   recent ancestor, then the invariant holds as usual.

4. If none of the parents have the primary introduction as their most
   recent ancestor, nor do they have the same additional introduction,
   then the merge commit cannot be authenticated.

[^] Quoting from the Pro Git book [7]:
> ...the first parent of a merge commit is from the branch you were on
> when you merged (frequently master), while the second parent of a
> merge commit is from the branch that was merged...

The idea is - the primary introduction is for the part of the tree under
YOUR control. When you fork Guix and create your own branch, you use the
initial commit on your branch as the primary channel introduction. You
add upstream Guix's primary channel introduction as an additional
channel introduction. If you add anyone else's fork as a remote and pull
one of their branches, you add their primary introduction as one of your
additional introductions.

Thus, any merge into one of YOUR branches (ie. any branch with the
primary introduction as the most recent ancestor) only needs to be
signed by a key that's authorized on that branch.

But you can't merge into a branch from upstream Guix or someone else's
authenticated fork (unless you're authorized to commit to those),
because the first parent of the merge commit would not be a primary
parent (see 2b) - it would be a commit on someone else's branch. And
people not authorized by you can't merge into your branch either,
because of 2a. And finally, you can't merge someone else's fork and
upstream, or anything like that. The merge commit would not be
authenticated in any of these cases.
--8<---------------cut here---------------end--------------->8---


So What Do You Want From Me Anyway, 45mg?
========================================

I've tried to think of ways in which this modification to the behaviour
of `guix git authenticate` could compromise security, but so far I
haven't been able to think of any attacks it might enable.

Of course, this only means that /I/ haven't been able to think of
anything wrong. You, dear reader, have the advantage of a unique
perspective and a fresh view on this idea. So, I'm hoping that you'll
be able to sniff out any fundamental issues with the design here.

I've actually started work on a patch series to implement this, but it's
going to be pretty slow going - I've spent several hours on it so far,
and I'm maybe a fifth of the way done. (Obviously, I'm going to have to
pace myself more; so don't hold your breath.)

In the meantime, if there's a fundamental problem with the approach I've
described, I hope you will be able to find it sooner rather than later,
before I sink even more time and energy into this endeavor.

Thanks for reading this far, and here's hoping we can achieve a better
experience for budding contributors!

45mg

[1] https://lists.gnu.org/archive/html/guix-devel/2025-01/msg00072.html
[2] https://lists.gnu.org/archive/html/help-guix/2023-09/msg00078.html
[3] 
https://git.wolfsden.cz/guix/tree/etc/0001-git-authenticate-Trust-all-keys-from-already-authent.patch
[4] https://lists.gnu.org/archive/html/help-guix/2025-01/msg00097.html
[5] https://lists.gnu.org/archive/html/help-guix/2025-01/msg00101.html
[6] From the 'Securing Updates' Guix blog post:
    > A commit is considered authentic if and only if it is signed by
    > one of the keys listed in the .guix-authorizations file of each of
    > its parents. This is the authorization invariant.
    https://guix.gnu.org/en/blog/2020/securing-updates/
[7] https://git-scm.com/book/en/v2/Git-Tools-Revision-Selection