Branches as signed sequences Jonathan S. Shapiro (shap@eros-os.org)
Tue, 11 Apr 2000 23:04:43 -0400

While DCMS is distributed, the one place where an atomic commit is required is branch update. A "branch" is really a variable that names a configuration. The problem is that if two commits are allowed to occur in parallel on distinct servers, then the sequentiality of branch revisions may be violated.

There is a further problem: since the branch is really a variable, the cryptographic hash trick cannot be used to validate its content. It is therefore possible for a malicious server to forge and propagate a bad branch file unless something is done.

The solution is to borrow an idea from Xanadu (Mark Miller, Dean Tribble, et al.)

A branch is now a set, where each element is:

server-signature [ revisor signature [ (cur true name, new true name) ]]

That is, each entry is a pair consisting of the true name that the branch held prior to commit and the true name that it held after the commit. Provenance of the update is determined because the revisor signed it. Authenticity of the update is achieved by the server signing it. The correct sequence is recoverable by the obvious sort.

Before accepting an update, the server validates that the signer is authorized to update the branch by checking an access control list (of valid signatures) for that branch.

shap