Something went wrong. Try again.
forked from tailscale/tailscale
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623// Copyright (c) Tailscale Inc & contributors// SPDX-License-Identifier: BSD-3-Clause
package tka
import ( "bytes" "fmt" "strings" "testing" "time"
"github.com/google/go-cmp/cmp" "tailscale.com/tstest" "tailscale.com/util/must")
// getSyncOffer returns a SyncOffer for the given Chonk.func getSyncOffer(t *testing.T, storage Chonk) SyncOffer { t.Helper()
a, err := Open(storage) if err != nil { t.Fatal(err) } offer, err := a.SyncOffer(storage) if err != nil { t.Fatal(err) }
return offer}
func TestSyncOffer(t *testing.T) { fakeState := &State{ Keys: []Key{{Kind: Key25519, Votes: 1}}, DisablementValues: [][]byte{bytes.Repeat([]byte{1}, 32)}, }
checkpointTemplate := optTemplate("checkpoint", AUM{MessageKind: AUMCheckpoint, State: fakeState})
// If we have a small chain with just a handful of AUMs, the SyncOffer // contains the current HEAD and the first checkpoint. t.Run("short-chain", func(t *testing.T) { c := newTestchain(t, `A1 -> A2 -> A3 -> A4 -> A5`) got := getSyncOffer(t, c.Chonk())
// A SyncOffer includes the first checkpoint. want := SyncOffer{ Head: c.AUMHashes["A5"], Ancestors: []AUMHash{ c.AUMHashes["A1"], }, }
if diff := cmp.Diff(want, got); diff != "" { t.Errorf("SyncOffer diff (-want, +got):\n%s", diff) } })
// If the chain contains multiple checkpoints, the SyncOffer includes // all of them. t.Run("chain-with-multiple-checkpoints", func(t *testing.T) { c := newTestchain(t, ` A1 -> A2 -> A3 -> A4 -> A5 -> A6 -> A7 -> A8 -> A9 -> A10 A10 -> A11 -> A12 -> A13 -> A14 -> A15 -> A16 -> A17 -> A18 A18 -> A19 -> A20 -> A21 -> A22 -> A23 -> A24 -> A25 -> A26 A26 -> A27 -> A28 -> A29 -> A30 -> A31 -> A32 -> A33 -> A34 A34 -> A35 -> A36 -> A37 -> A38 -> A39 -> A40 -> A41 -> A42 A42 -> A43 -> A45 -> A46 -> A47 -> A48 -> A49 -> A50 -> A51 A51 -> A52 -> A53 -> A54 -> A55
A1.template = checkpoint A11.template = checkpoint A21.template = checkpoint A31.template = checkpoint A41.template = checkpoint A51.template = checkpoint `, checkpointTemplate) got := getSyncOffer(t, c.Chonk())
// A SyncOffer includes the first checkpoint. want := SyncOffer{ Head: c.AUMHashes["A55"], Ancestors: []AUMHash{ c.AUMHashes["A51"], c.AUMHashes["A41"], c.AUMHashes["A31"], c.AUMHashes["A21"], c.AUMHashes["A11"], c.AUMHashes["A1"], }, }
if diff := cmp.Diff(want, got); diff != "" { t.Errorf("SyncOffer diff (-want, +got):\n%s", diff) } })
// The size of a SyncOffer does not grow without bound as the number of AUMs increases. t.Run("long-chain-size-is-bounded", func(t *testing.T) { size := 1800
// Build a template string with a checkpoint every 50 AUMs. var sb strings.Builder sb.WriteString("A") for i := range size { sb.WriteString(fmt.Sprintf(" -> A%d", i)) } for i := range size { if i%50 == 0 { sb.WriteString(fmt.Sprintf("\nA%d.template = checkpoint", i)) } }
c := newTestchain(t, sb.String(), checkpointTemplate) got := getSyncOffer(t, c.Chonk())
// We expect the SyncOffer to include: // // - the latest AUM as the HEAD // - the checkpoints from the last 1000 AUMs (maxSyncHeadIntersectionIter) // - the oldest AUM in storage // want := SyncOffer{ Head: c.AUMHashes["A1799"], Ancestors: []AUMHash{ c.AUMHashes["A1750"], c.AUMHashes["A1700"], c.AUMHashes["A1650"], c.AUMHashes["A1600"], c.AUMHashes["A1550"], c.AUMHashes["A1500"], c.AUMHashes["A1450"], c.AUMHashes["A1400"], c.AUMHashes["A1350"], c.AUMHashes["A1300"], c.AUMHashes["A1250"], c.AUMHashes["A1200"], c.AUMHashes["A1150"], c.AUMHashes["A1100"], c.AUMHashes["A1050"], c.AUMHashes["A1000"], c.AUMHashes["A950"], c.AUMHashes["A900"], c.AUMHashes["A850"], c.AUMHashes["A800"], c.AUMHashes["A"], }, }
if diff := cmp.Diff(want, got); diff != "" { t.Errorf("SyncOffer diff (-want, +got):\n%s", diff) } })}
func TestComputeSyncIntersection_FastForward(t *testing.T) { // Node 1 has: A1 -> A2 // Node 2 has: A1 -> A2 -> A3 -> A4 c := newTestchain(t, ` A1 -> A2 -> A3 -> A4 `) a1H, a2H := c.AUMHashes["A1"], c.AUMHashes["A2"]
chonk1 := c.ChonkWith("A1", "A2") offer1 := getSyncOffer(t, chonk1)
chonk2 := c.Chonk() // All AUMs offer2 := getSyncOffer(t, chonk2)
// Node 1 only knows about the first two nodes, so the head of n2 is // alien to it. t.Run("n1", func(t *testing.T) { got, err := computeSyncIntersection(chonk1, offer1, offer2) if err != nil { t.Fatalf("computeSyncIntersection() failed: %v", err) } want := &intersection{ tailIntersection: &a1H, } if diff := cmp.Diff(want, got, cmp.AllowUnexported(intersection{})); diff != "" { t.Errorf("intersection diff (-want, +got):\n%s", diff) } })
// Node 2 knows about the full chain, so it can see that the head of n1 // intersects with a subset of its chain (a Head Intersection). t.Run("n2", func(t *testing.T) { got, err := computeSyncIntersection(chonk2, offer2, offer1) if err != nil { t.Fatalf("computeSyncIntersection() failed: %v", err) } want := &intersection{ headIntersection: &a2H, } if diff := cmp.Diff(want, got, cmp.AllowUnexported(intersection{})); diff != "" { t.Errorf("intersection diff (-want, +got):\n%s", diff) } })}
func TestComputeSyncIntersection_ForkSmallDiff(t *testing.T) { // The number of nodes in the chain is longer than ancestorSkipStart, // so that during sync both nodes are able to find a common ancestor // which was later than A1.
c := newTestchain(t, ` A1 -> A2 -> A3 -> A4 -> A5 -> A6 -> A7 -> A8 -> A9 -> A10 | -> F1 // Make F1 different to A9. // hashSeed is chosen such that the hash is higher than A9. F1.hashSeed = 7 `) // Node 1 has: A1 -> A2 -> A3 -> A4 -> A5 -> A6 -> A7 -> A8 -> F1 // Node 2 has: A1 -> A2 -> A3 -> A4 -> A5 -> A6 -> A7 -> A8 -> A9 -> A10 f1H, a9H := c.AUMHashes["F1"], c.AUMHashes["A9"]
if bytes.Compare(f1H[:], a9H[:]) < 0 { t.Fatal("failed assert: h(a9) > h(f1H)\nTweak hashSeed till this passes") }
chonk1 := c.ChonkWith("A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "F1") offer1 := getSyncOffer(t, chonk1)
chonk2 := c.ChonkWith("A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "A10") offer2 := getSyncOffer(t, chonk2)
// Node 1 only knows about the first eight nodes, so the head of n2 is // alien to it. t.Run("n1", func(t *testing.T) { // n2 has 10 nodes, so the first common ancestor is the genesis AUM wantIntersection := c.AUMHashes["A1"]
got, err := computeSyncIntersection(chonk1, offer1, offer2) if err != nil { t.Fatalf("computeSyncIntersection() failed: %v", err) } want := &intersection{ tailIntersection: &wantIntersection, } if diff := cmp.Diff(want, got, cmp.AllowUnexported(intersection{})); diff != "" { t.Errorf("intersection diff (-want, +got):\n%s", diff) } })
// Node 2 knows about the full chain but doesn't recognize the head. t.Run("n2", func(t *testing.T) { // n1 has 9 nodes, so the first common ancestor is the genesis AUM wantIntersection := c.AUMHashes["A1"]
got, err := computeSyncIntersection(chonk2, offer2, offer1) if err != nil { t.Fatalf("computeSyncIntersection() failed: %v", err) } want := &intersection{ tailIntersection: &wantIntersection, } if diff := cmp.Diff(want, got, cmp.AllowUnexported(intersection{})); diff != "" { t.Errorf("intersection diff (-want, +got):\n%s", diff) } })}
func TestMissingAUMs_FastForward(t *testing.T) { // Node 1 has: A1 -> A2 // Node 2 has: A1 -> A2 -> A3 -> A4 c := newTestchain(t, ` A1 -> A2 -> A3 -> A4 A1.hashSeed = 1 A2.hashSeed = 2 A3.hashSeed = 3 A4.hashSeed = 4 `)
chonk1 := c.ChonkWith("A1", "A2") n1, err := Open(chonk1) if err != nil { t.Fatal(err) } offer1, err := n1.SyncOffer(chonk1) if err != nil { t.Fatal(err) }
chonk2 := c.Chonk() // All AUMs n2, err := Open(chonk2) if err != nil { t.Fatal(err) } offer2, err := n2.SyncOffer(chonk2) if err != nil { t.Fatal(err) }
// Node 1 only knows about the first two nodes, so the head of n2 is // alien to it. As such, it should send history from the newest ancestor, // A1 (if the chain was longer there would be one in the middle). t.Run("n1", func(t *testing.T) { got, err := n1.MissingAUMs(chonk1, offer2) if err != nil { t.Fatalf("MissingAUMs() failed: %v", err) }
// Both sides have A1, so the only AUM that n2 might not have is // A2. want := []AUM{c.AUMs["A2"]} if diff := cmp.Diff(want, got); diff != "" { t.Errorf("MissingAUMs diff (-want, +got):\n%s", diff) } })
// Node 2 knows about the full chain, so it can see that the head of n1 // intersects with a subset of its chain (a Head Intersection). t.Run("n2", func(t *testing.T) { got, err := n2.MissingAUMs(chonk2, offer1) if err != nil { t.Fatalf("MissingAUMs() failed: %v", err) }
want := []AUM{ c.AUMs["A3"], c.AUMs["A4"], } if diff := cmp.Diff(want, got); diff != "" { t.Errorf("MissingAUMs diff (-want, +got):\n%s", diff) } })}
func TestMissingAUMs_Fork(t *testing.T) { // Node 1 has: A1 -> A2 -> A3 -> F1 // Node 2 has: A1 -> A2 -> A3 -> A4 c := newTestchain(t, ` A1 -> A2 -> A3 -> A4 | -> F1 A1.hashSeed = 1 A2.hashSeed = 2 A3.hashSeed = 3 A4.hashSeed = 4 `)
chonk1 := c.ChonkWith("A1", "A2", "A3", "F1") n1, err := Open(chonk1) if err != nil { t.Fatal(err) } offer1, err := n1.SyncOffer(chonk1) if err != nil { t.Fatal(err) }
chonk2 := c.ChonkWith("A1", "A2", "A3", "A4") n2, err := Open(chonk2) if err != nil { t.Fatal(err) } offer2, err := n2.SyncOffer(chonk2) if err != nil { t.Fatal(err) }
t.Run("n1", func(t *testing.T) { got, err := n1.MissingAUMs(chonk1, offer2) if err != nil { t.Fatalf("MissingAUMs() failed: %v", err) }
// Both sides have A1, so n1 will send everything it knows from // there to head. want := []AUM{ c.AUMs["A2"], c.AUMs["A3"], c.AUMs["F1"], } if diff := cmp.Diff(want, got); diff != "" { t.Errorf("MissingAUMs diff (-want, +got):\n%s", diff) } })
t.Run("n2", func(t *testing.T) { got, err := n2.MissingAUMs(chonk2, offer1) if err != nil { t.Fatalf("MissingAUMs() failed: %v", err) }
// Both sides have A1, so n2 will send everything it knows from // there to head. want := []AUM{ c.AUMs["A2"], c.AUMs["A3"], c.AUMs["A4"], } if diff := cmp.Diff(want, got); diff != "" { t.Errorf("MissingAUMs diff (-want, +got):\n%s", diff) } })}
func TestSyncSimpleE2E(t *testing.T) { pub, priv := testingKey25519(t, 1) key := Key{Kind: Key25519, Public: pub, Votes: 2}
c := newTestchain(t, ` G1 -> L1 -> L2 -> L3 G1.template = genesis `, genesisTemplate(key), optKey("key", key, priv), optSignAllUsing("key"))
nodeStorage := ChonkMem() node, err := Bootstrap(nodeStorage, c.AUMs["G1"]) if err != nil { t.Fatalf("node Bootstrap() failed: %v", err) } controlStorage := c.Chonk() control, err := Open(controlStorage) if err != nil { t.Fatalf("control Open() failed: %v", err) }
// Control knows the full chain, node only knows the genesis. Let's see // if they can sync. nodeOffer, err := node.SyncOffer(nodeStorage) if err != nil { t.Fatal(err) } controlAUMs, err := control.MissingAUMs(controlStorage, nodeOffer) if err != nil { t.Fatalf("control.MissingAUMs(%v) failed: %v", nodeOffer, err) } if err := node.Inform(nodeStorage, controlAUMs); err != nil { t.Fatalf("node.Inform(%v) failed: %v", controlAUMs, err) }
if cHash, nHash := control.Head(), node.Head(); cHash != nHash { t.Errorf("node & control are not synced: c=%x, n=%x", cHash, nHash) }}
// TestSyncFromFarBehind checks that nodes with compacted state can still find// a common ancestor when the remote is significantly ahead.//// We simulate a node that has compacted its early history and is now ~500 AUMs// behind the control plane, a distance that previously caused exponential sampling// in SyncOffer to skip the node's entire local history.//// Regression test for http://go/corp/40404func TestSyncFromFarBehind(t *testing.T) { pub1, priv1 := testingKey25519(t, 1) signer1 := signer25519(priv1)
key1 := Key{Kind: Key25519, Public: pub1, Votes: 2}
// Setup: persistentAuthority (control plane) vs compactingAuthority (client node). state := State{ Keys: []Key{key1}, DisablementValues: [][]byte{DisablementKDF([]byte{1, 2, 3})}, }
persistentStorage, compactingStorage := ChonkMem(), ChonkMem() persistentSize := func() int { return len(must.Get(persistentStorage.AllAUMs())) } compactingSize := func() int { return len(must.Get(compactingStorage.AllAUMs())) }
// Backdate the clock on the compactingStorage so all AUMs will be old enough // to be considered for compacting. clock := tstest.NewClock(tstest.ClockOpts{ Start: time.Now().Add(-(CompactionDefaults.MinAge + 24*time.Hour)), }) compactingStorage.SetClock(clock)
persistentAuthority, genesisAUM := must.Get2(Create(persistentStorage, state, signer1)) compactingAuthority := must.Get(Bootstrap(compactingStorage, genesisAUM))
// 1. Generate enough history to trigger checkpoints. persistentNode := CreateSeedNode(t, persistentAuthority, persistentStorage) compactingNode := CreateSeedNode(t, compactingAuthority, compactingStorage) SeedAUMs(t, SeedAUMConfig{ Count: checkpointEvery * 2, Signer: signer1, Nodes: []SeedNode{persistentNode, compactingNode}, })
t.Logf("genesis and first batch of AUMs: persistent = %d, compacting = %d", persistentSize(), compactingSize())
// 2. Compact the node state. // // It now has a different 'oldestAncestor' than the control plane. beforeCompacting := compactingSize() must.Do(compactingAuthority.Compact(compactingStorage, CompactionDefaults)) afterCompacting := compactingSize()
if beforeCompacting == afterCompacting { t.Errorf("expected Compact to reduce the number of AUMs, but unchanged: size = %d", afterCompacting) }
// 3. Advance the control plane far beyond the node. // // As of 2026-04-17, the largest TKA has ~750 AUMs. // // If you keep increasing this number, eventually the sync will fail because you // hit the hard-coded limits on iteration during the sync process. SeedAUMs(t, SeedAUMConfig{ Count: compactingSize() - persistentSize() + 800, Signer: signer1, Nodes: []SeedNode{persistentNode}, })
t.Logf("post-compacting and extra AUMs: persistent = %d, compacting = %d", persistentSize(), compactingSize())
// 4. Verify Intersection. // The node should find an intersection even with a 500-AUM gap. persistentOffer := must.Get(persistentAuthority.SyncOffer(persistentStorage)) compactingOffer := must.Get(compactingAuthority.SyncOffer(compactingStorage))
if _, err := compactingAuthority.MissingAUMs(compactingStorage, persistentOffer); err != nil { t.Errorf("node failed to find intersection with far-ahead control plane: %v", err) }
// 5. Check that the persistent authority can find an intersection with the // compacting authority, and has missing AUMs to send it. missing, err := persistentAuthority.MissingAUMs(persistentStorage, compactingOffer) if len(missing) == 0 { t.Errorf("control plane did not find any missing AUMs for node") } if err != nil { t.Errorf("control plane failed to find missing AUMs for node: %v", err) }}
// TestSyncFromFarBehindFork checks that nodes with compacted state that have// also branched from the active chain can still find a common ancestor when// the remote is significantly ahead of the inersection point.//// We simulate a node that has compacted its early history and is now ~500 AUMs// behind the control plane, plus a few AUMs extra, a distance that previously// caused exponential sampling in SyncOffer to skip the node's entire local history.//// Regression test for http://go/corp/40404func TestSyncFromFarBehindFork(t *testing.T) { // Set up two signing keys. They have a different number of votes, so if there's // a fork, the chain with the winning key will take precedence. majorityPub, majorityPriv := testingKey25519(t, 1) losingPub, losingPriv := testingKey25519(t, 2) winningSigner := signer25519(majorityPriv) losingSigner := signer25519(losingPriv)
losingKey := Key{Kind: Key25519, Public: majorityPub, Votes: 1} winningKey := Key{Kind: Key25519, Public: losingPub, Votes: 2}
// Setup: persistentAuthority (control plane) vs compactingAuthority (client node). state := State{ Keys: []Key{losingKey, winningKey}, DisablementValues: [][]byte{DisablementKDF([]byte{1, 2, 3})}, }
persistentStorage, compactingStorage := ChonkMem(), ChonkMem() persistentSize := func() int { return len(must.Get(persistentStorage.AllAUMs())) } compactingSize := func() int { return len(must.Get(compactingStorage.AllAUMs())) }
// Backdate the clock on the compactingStorage so all AUMs will be old enough // to be considered for compacting. clock := tstest.NewClock(tstest.ClockOpts{ Start: time.Now().Add(-(CompactionDefaults.MinAge + 24*time.Hour)), }) compactingStorage.SetClock(clock)
persistentAuthority, genesisAUM := must.Get2(Create(persistentStorage, state, winningSigner)) compactingAuthority := must.Get(Bootstrap(compactingStorage, genesisAUM))
// 1. Generate enough history to trigger checkpoints. persistentNode := CreateSeedNode(t, persistentAuthority, persistentStorage) compactingNode := CreateSeedNode(t, compactingAuthority, compactingStorage) SeedAUMs(t, SeedAUMConfig{ Count: checkpointEvery * 2, Signer: winningSigner, Nodes: []SeedNode{persistentNode, compactingNode}, })
t.Logf("genesis and first batch of AUMs: persistent = %d, compacting = %d", persistentSize(), compactingSize())
// 2. Compact the node state. // // It now has a different 'oldestAncestor' than the control plane. beforeCompacting := compactingSize() must.Do(compactingAuthority.Compact(compactingStorage, CompactionDefaults)) afterCompacting := compactingSize()
if beforeCompacting == afterCompacting { t.Errorf("expected Compact to reduce the number of AUMs, but unchanged: size = %d", afterCompacting) }
// 2. Advance the node state slightly beyond the control plane, using the // losing signer. SeedAUMs(t, SeedAUMConfig{ Count: 1, Signer: losingSigner, Nodes: []SeedNode{compactingNode}, })
// 3. Advance the control plane far beyond the node, using the winning signer. // // Now the node is forked from the control plane state, and the control plane's // chain will win because its chain was signed by a key with more votes. // // As of 2026-04-17, the largest TKA has ~750 AUMs. // // If you keep increasing this number, eventually the sync will fail because you // hit the hard-coded limits on iteration during the sync process. SeedAUMs(t, SeedAUMConfig{ Count: compactingSize() - persistentSize() + 800, Signer: winningSigner, Nodes: []SeedNode{persistentNode}, })
t.Logf("post-compacting and extra AUMs: persistent = %d, compacting = %d", persistentSize(), compactingSize())
// 4. Verify Intersection. // The node should find an intersection even with a 500-AUM gap. persistentOffer := must.Get(persistentAuthority.SyncOffer(persistentStorage)) compactingOffer := must.Get(compactingAuthority.SyncOffer(compactingStorage))
if _, err := compactingAuthority.MissingAUMs(compactingStorage, persistentOffer); err != nil { t.Errorf("node failed to find intersection with far-ahead control plane: %v", err) }
// 5. Check that the persistent authority can find an intersection with the // compacting authority, and has missing AUMs to send it. missing, err := persistentAuthority.MissingAUMs(persistentStorage, compactingOffer) if len(missing) == 0 { t.Errorf("control plane did not find any missing AUMs for node") } if err != nil { t.Errorf("control plane failed to find missing AUMs for node: %v", err) }}