Something went wrong. Try again.
forked from tailscale/tailscale
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324// Copyright (c) Tailscale Inc & contributors// SPDX-License-Identifier: BSD-3-Clause
//go:build !ts_omit_tailnetlock
package tka
import ( "errors" "fmt" "os"
"tailscale.com/util/testenv")
// ErrNoIntersection is returned when a shared AUM could// not be determined when evaluating a remote sync offer.var ErrNoIntersection = errors.New("no intersection")
// SyncOffer conveys information about the current head & ancestor AUMs,// for the purpose of synchronization with some remote end.//// Ancestors should contain a subset of the ancestors of the chain.// The last entry in that slice is the oldest-known AUM in the chain.type SyncOffer struct { Head AUMHash Ancestors []AUMHash}
// ToSyncOffer creates a SyncOffer from the fields received in// a [tailcfg.TKASyncOfferRequest].func ToSyncOffer(head string, ancestors []string) (SyncOffer, error) { var out SyncOffer if err := out.Head.UnmarshalText([]byte(head)); err != nil { return SyncOffer{}, fmt.Errorf("head.UnmarshalText: %v", err) } out.Ancestors = make([]AUMHash, len(ancestors)) for i, a := range ancestors { if err := out.Ancestors[i].UnmarshalText([]byte(a)); err != nil { return SyncOffer{}, fmt.Errorf("ancestor[%d].UnmarshalText: %v", i, err) } } return out, nil}
// FromSyncOffer marshals the fields of a SyncOffer so they can be// sent in a [tailcfg.TKASyncOfferRequest].func FromSyncOffer(offer SyncOffer) (head string, ancestors []string, err error) { headBytes, err := offer.Head.MarshalText() if err != nil { return "", nil, fmt.Errorf("head.MarshalText: %v", err) }
ancestors = make([]string, len(offer.Ancestors)) for i, ancestor := range offer.Ancestors { hash, err := ancestor.MarshalText() if err != nil { return "", nil, fmt.Errorf("ancestor[%d].MarshalText: %v", i, err) } ancestors[i] = string(hash) } return string(headBytes), ancestors, nil}
// SyncOffer returns an abbreviated description of the current AUM// chain, which can be used to synchronize with another (untrusted)// Authority instance.//// The returned SyncOffer structure should be transmitted to the remote// Authority, which should call MissingAUMs() using it to determine// AUMs which need to be transmitted. This list of AUMs from the remote// can then be applied locally with Inform().//// This SyncOffer + AUM exchange should be performed by both ends,// because it's possible that either end has AUMs that the other needs// to find out about.func (a *Authority) SyncOffer(storage Chonk) (SyncOffer, error) { oldest := a.oldestAncestor.Hash()
out := SyncOffer{ Head: a.Head(), Ancestors: make([]AUMHash, 0, 6), // 6 chosen arbitrarily. }
// We send all our checkpoints to help the remote find a // more-recent 'head intersection'. curs := a.Head() for range maxSyncHeadIntersectionIter { parent, err := storage.AUM(curs) if err != nil { if err != os.ErrNotExist { return SyncOffer{}, err } break }
// We add the oldest later on, so don't duplicate. if parent.Hash() == oldest { break }
if parent.MessageKind == AUMCheckpoint { out.Ancestors = append(out.Ancestors, curs) }
copy(curs[:], parent.PrevAUMHash) }
out.Ancestors = append(out.Ancestors, oldest) return out, nil}
// intersection describes how to synchronize AUMs with a remote// authority.type intersection struct { // if true, no exchange of AUMs is needed. upToDate bool
// headIntersection is the latest common AUM on the remote. In other // words, we need to send all AUMs since this one. headIntersection *AUMHash
// tailIntersection is the oldest common AUM on the remote. In other // words, we diverge with the remote after this AUM, so we both need // to transmit our AUM chain starting here. tailIntersection *AUMHash}
// computeSyncIntersection determines the common AUMs between a local and// remote SyncOffer. This intersection can be used to synchronize both// sides.func computeSyncIntersection(storage Chonk, localOffer, remoteOffer SyncOffer) (*intersection, error) { // Simple case: up to date. if remoteOffer.Head == localOffer.Head { return &intersection{upToDate: true, headIntersection: &localOffer.Head}, nil }
// Case: 'head intersection' // If we have the remote's head, it's more likely than not that // we have updates that build on that head. To confirm this, // we iterate backwards through our chain to see if the given // head is an ancestor of our current chain. // // In other words: // <Us> A -> B -> C // <Them> A -> B // ∴ their head intersects with our chain, we need to send C var hasRemoteHead bool _, err := storage.AUM(remoteOffer.Head) if err != nil { if err != os.ErrNotExist { return nil, err } } else { hasRemoteHead = true }
if hasRemoteHead { curs := localOffer.Head for range maxSyncHeadIntersectionIter { parent, err := storage.AUM(curs) if err != nil { if err != os.ErrNotExist { return nil, err } break }
if parent.Hash() == remoteOffer.Head { h := parent.Hash() return &intersection{headIntersection: &h}, nil }
copy(curs[:], parent.PrevAUMHash) } }
// Case: 'tail intersection' // So we don't have a clue what the remote's head is, but // if one of the ancestors they gave us is part of our chain, // then there's an intersection, which is a starting point for // the remote to send us AUMs from. // // We iterate the list of ancestors in order because the remote // ordered them such that the newer ones are earlier, so with // a bit of luck we can use an earlier one and hence do less work / // transmit fewer AUMs. for _, a := range remoteOffer.Ancestors { state, err := computeStateAt(storage, maxSyncIter, a) if err != nil { if err != os.ErrNotExist { return nil, fmt.Errorf("computeStateAt: %v", err) } continue }
end, _, err := fastForward(storage, maxSyncIter, state, func(curs AUM, _ State) bool { return curs.Hash() == localOffer.Head }) if err != nil { return nil, err } // fastForward can terminate before the done condition if there are // no more children left, so we check again before considering this // an intersection. if end.Hash() == localOffer.Head { return &intersection{tailIntersection: &a}, nil } }
return nil, ErrNoIntersection}
// MissingAUMs returns AUMs a remote may be missing based on the// remotes' SyncOffer.func (a *Authority) MissingAUMs(storage Chonk, remoteOffer SyncOffer) ([]AUM, error) { localOffer, err := a.SyncOffer(storage) if err != nil { return nil, fmt.Errorf("local syncOffer: %v", err) } intersection, err := computeSyncIntersection(storage, localOffer, remoteOffer) if err != nil { return nil, fmt.Errorf("intersection: %v", err) } if intersection.upToDate { return nil, nil } out := make([]AUM, 0, 12) // 12 chosen arbitrarily.
if intersection.headIntersection != nil { state, err := computeStateAt(storage, maxSyncIter, *intersection.headIntersection) if err != nil { return nil, err }
_, _, err = fastForward(storage, maxSyncIter, state, func(curs AUM, _ State) bool { if curs.Hash() != *intersection.headIntersection { out = append(out, curs) } return false }) return out, err }
if intersection.tailIntersection != nil { state, err := computeStateAt(storage, maxSyncIter, *intersection.tailIntersection) if err != nil { return nil, err }
_, _, err = fastForward(storage, maxSyncIter, state, func(curs AUM, _ State) bool { if curs.Hash() != *intersection.tailIntersection { out = append(out, curs) } return false }) return out, err }
panic("unreachable")}
// SeedNode is an authority-chonk pair that can be seeded by [SeedAUMs].type SeedNode struct { authority *Authority storage Chonk}
// CreateSeedNode creates a node for use with [SeedAUMs].func CreateSeedNode(t testenv.TB, authority *Authority, storage Chonk) SeedNode { t.Helper() return SeedNode{authority, storage}}
type SeedAUMConfig struct { Count int Signer Signer Nodes []SeedNode}
// SeedAUMs generates many AUMs by repeatedly adding and removing keys// from the TKA.//// The AUMs are written to all the supplied nodes, so if you pass more// than one, you can build up a long sync history.//// This is only for use in testing.func SeedAUMs(t testenv.TB, config SeedAUMConfig) { t.Helper()
if len(config.Nodes) == 0 { panic("called SeedAUMs without any nodes") } primaryNode := config.Nodes[0]
// The key that we'll repeatedly add/remove in the TKA. key := Key{Kind: Key25519, Public: []byte{1, 1, 1}, Votes: 1}
for i := 0; i < config.Count/2; i++ { for _, action := range []string{"add", "remove"} { updater := primaryNode.authority.NewUpdater(config.Signer) if action == "add" { if err := updater.AddKey(key); err != nil { t.Fatalf("error from updater.AddKey: %v") } } else { if err := updater.RemoveKey(key.MustID()); err != nil { t.Fatalf("error from updater.RemoveKey: %v") } } aum, err := updater.Finalize(primaryNode.storage) if err != nil { t.Fatalf("error from authority.Finalize: %v", err) }
for _, n := range config.Nodes { if err := n.authority.Inform(n.storage, aum); err != nil { t.Fatalf("error from authority.Inform: %v", err) } } } }}