peoplecoin

  1package coin
  2
  3import (
  4	"math"
  5	"math/big"
  6	"testing"
  7
  8	"peoplecoin/params"
  9)
 10
 11// powFloat computes x^n with big.Float at 256 bits of precision.
 12func powFloat(x *big.Float, n uint64) *big.Float {
 13	res := new(big.Float).SetPrec(256).SetInt64(1)
 14	base := new(big.Float).SetPrec(256).Set(x)
 15	for n > 0 {
 16		if n&1 == 1 {
 17			res.Mul(res, base)
 18		}
 19		base.Mul(base, base)
 20		n >>= 1
 21	}
 22	return res
 23}
 24
 25// Decay0 must be floor(2^63 × 0.983^(1/40320)): (Decay0/2^63)^40320 ≤ 0.983
 26// and ((Decay0+1)/2^63)^40320 > 0.983.
 27func TestDecay0IsFloor(t *testing.T) {
 28	two63 := new(big.Float).SetPrec(256).SetInt(new(big.Int).Lsh(big.NewInt(1), 63))
 29	target := new(big.Float).SetPrec(256).SetRat(big.NewRat(983, 1000))
 30
 31	ratio := func(d uint64) *big.Float {
 32		x := new(big.Float).SetPrec(256).SetUint64(d)
 33		return x.Quo(x, two63)
 34	}
 35	lo := powFloat(ratio(params.Decay0), params.SlotsPerPeriod)
 36	hi := powFloat(ratio(params.Decay0+1), params.SlotsPerPeriod)
 37	if lo.Cmp(target) > 0 {
 38		t.Fatalf("Decay0 too large: (Decay0/2^63)^40320 = %s > 0.983", lo.Text('g', 25))
 39	}
 40	if hi.Cmp(target) <= 0 {
 41		t.Fatalf("Decay0 too small: ((Decay0+1)/2^63)^40320 = %s ≤ 0.983", hi.Text('g', 25))
 42	}
 43	t.Logf("(Decay0/2^63)^40320 = %s", lo.Text('g', 20))
 44}
 45
 46func TestTableShape(t *testing.T) {
 47	for i := 1; i < DecayLen; i++ {
 48		if Decay[i] >= Decay[i-1] {
 49			t.Fatalf("Decay[%d] not decreasing", i)
 50		}
 51		// Decay[i] ≈ (Decay[i-1]/2^63)^2 × 2^63, within rounding.
 52		want := new(big.Int).Mul(new(big.Int).SetUint64(Decay[i-1]), new(big.Int).SetUint64(Decay[i-1]))
 53		want.Rsh(want, 63)
 54		if want.Uint64() != Decay[i] {
 55			t.Fatalf("Decay[%d] = %d, want %d", i, Decay[i], want.Uint64())
 56		}
 57	}
 58	// Decay[26] is the retention after 2^26 slots ≈ 1665 periods: ~2.5e-13.
 59	if f := float64(Decay[DecayLen-1]) / math.Ldexp(1, 63); f > 1e-11 || f < 1e-14 {
 60		t.Fatalf("Decay[26] = %g looks wrong", f)
 61	}
 62}
 63
 64// refEffective is the same squaring chain done with big.Int, as a check
 65// on the 128-bit arithmetic.
 66func refEffective(amount, tt uint64) uint64 {
 67	if tt >= 1<<DecayLen {
 68		return 0
 69	}
 70	x := new(big.Int).SetUint64(amount)
 71	for i := 0; i < DecayLen; i++ {
 72		if tt&(1<<uint(i)) != 0 {
 73			x.Mul(x, new(big.Int).SetUint64(Decay[i]))
 74			x.Rsh(x, 63)
 75		}
 76	}
 77	return x.Uint64()
 78}
 79
 80func TestSpecFigures(t *testing.T) {
 81	// One token after one period retains 98 299 996 (spec), i.e. the
 82	// demurrage on it equals the UBI within rounding.
 83	got := Effective(params.TOKEN, params.SlotsPerPeriod)
 84	if got != 98_299_996 {
 85		t.Errorf("decay(TOKEN, SlotsPerPeriod) = %d, spec says 98 299 996", got)
 86	}
 87	if got+params.UBIPerPeriod < params.TOKEN-10 || got+params.UBIPerPeriod > params.TOKEN {
 88		t.Errorf("system not neutral at one token: %d + %d vs %d", got, params.UBIPerPeriod, params.TOKEN)
 89	}
 90
 91	// The largest uint64 has decayed below one base unit by ~2 600 periods.
 92	if v := Effective(math.MaxUint64, 2600*params.SlotsPerPeriod); v != 0 {
 93		t.Errorf("MaxUint64 after 2600 periods = %d, want 0", v)
 94	}
 95	if v := Effective(math.MaxUint64, 2500*params.SlotsPerPeriod); v == 0 {
 96		t.Errorf("MaxUint64 after 2500 periods already 0")
 97	}
 98
 99	// A 1 UBI entry retains ~80% after a year (13 periods) and ~11% after ten.
100	year := 13 * params.SlotsPerPeriod
101	if r := float64(Effective(params.UBIPerPeriod, year)) / float64(params.UBIPerPeriod); r < 0.79 || r > 0.81 {
102		t.Errorf("1 UBI after a year retains %.3f, spec says ~80%%", r)
103	}
104	if r := float64(Effective(params.UBIPerPeriod, 10*year)) / float64(params.UBIPerPeriod); r < 0.10 || r > 0.12 {
105		t.Errorf("1 UBI after ten years retains %.3f, spec says ~11%%", r)
106	}
107
108	// Rent overtakes a 1 UBI entry after ~292 periods.
109	cross := uint64(0)
110	for p := uint64(1); p < 400; p++ {
111		if Prunable(params.UBIPerPeriod, p*params.SlotsPerPeriod) {
112			cross = p
113			break
114		}
115	}
116	if cross < 285 || cross > 300 {
117		t.Errorf("1 UBI becomes prunable at period %d, spec says ~292", cross)
118	}
119	t.Logf("decay(TOKEN, period) = %d; 1 UBI prunable from period %d", got, cross)
120}
121
122func TestEffectiveEdges(t *testing.T) {
123	if Effective(12345, 0) != 12345 {
124		t.Fatal("t=0 must be identity")
125	}
126	if Effective(0, 999) != 0 {
127		t.Fatal("zero stays zero")
128	}
129	if Effective(math.MaxUint64, 1<<DecayLen) != 0 || Effective(math.MaxUint64, math.MaxUint64) != 0 {
130		t.Fatal("t ≥ 2^27 must be zero")
131	}
132	if Effective(math.MaxUint64, (1<<DecayLen)-1) != 0 {
133		t.Fatal("t = 2^27−1 exceeds 2^27 periods worth of decay; must be zero")
134	}
135	// Small amounts: 1 base unit decays to 0 after one slot (floor).
136	if Effective(1, 1) != 0 {
137		t.Fatal("1 base unit after one slot should floor to 0")
138	}
139}
140
141// exactEffective is amount × Π Decay[i]/2^63 over the set bits of t,
142// without intermediate flooring.
143func exactEffective(amount, tt uint64) *big.Float {
144	x := new(big.Float).SetPrec(256).SetUint64(amount)
145	two63 := new(big.Float).SetPrec(256).SetInt(new(big.Int).Lsh(big.NewInt(1), 63))
146	for i := 0; i < DecayLen; i++ {
147		if tt&(1<<uint(i)) != 0 {
148			f := new(big.Float).SetPrec(256).SetUint64(Decay[i])
149			x.Mul(x, f.Quo(f, two63))
150		}
151	}
152	return x
153}
154
155// The chain floors after every multiplication, so the result is below the
156// unrounded product by less than one unit per multiplication — at most
157// DecayLen. That also means it is not strictly monotone in t for small
158// amounts (1 000 units after 1 023 slots, ten floors, come out below 1 000
159// units after 1 024 slots, one floor); the deviation is bounded the same way.
160func TestRoundingBoundAndReference(t *testing.T) {
161	amounts := []uint64{1, 1000, params.UBIPerPeriod, params.TOKEN, 1 << 40, math.MaxUint64}
162	ts := []uint64{0, 1, 2, 3, 1023, 1024, 40320, 40321, 13 * 40320, 1 << 20, (1 << 20) + 7, 1000 * 40320, (1 << 27) - 1} // ascending
163	for _, a := range amounts {
164		prev := a // Effective(a, 0) == a and nothing exceeds it
165		for _, tt := range ts {
166			got := Effective(a, tt)
167			if got != refEffective(a, tt) {
168				t.Fatalf("Effective(%d, %d) = %d, reference %d", a, tt, got, refEffective(a, tt))
169			}
170			if got > a {
171				t.Fatalf("value grew")
172			}
173			exact := exactEffective(a, tt)
174			diff := new(big.Float).Sub(exact, new(big.Float).SetPrec(256).SetUint64(got))
175			if d, _ := diff.Float64(); d < 0 || d >= DecayLen {
176				t.Fatalf("Effective(%d, %d) = %d is %.2f below exact; want within [0, %d)", a, tt, got, d, DecayLen)
177			}
178			if got > prev && got-prev > DecayLen {
179				t.Fatalf("Effective(%d, %d) = %d exceeds earlier value %d by more than rounding", a, tt, got, prev)
180			}
181			prev = got
182		}
183	}
184}
185
186func TestRentAndSpendable(t *testing.T) {
187	if Rent(1023) != 0 || Rent(1024) != 1 || Rent(params.SlotsPerPeriod) != 39 {
188		t.Fatalf("rent: %d %d %d", Rent(1023), Rent(1024), Rent(params.SlotsPerPeriod))
189	}
190	// A tiny UTXO expires: 100 base units are gone after 100×1024 slots.
191	tt := uint64(100 * 1024)
192	if Spendable(100, tt) != 0 || !Prunable(100, tt) {
193		t.Fatal("100 base units should be consumed by rent after 102 400 slots")
194	}
195	// A large one is negligibly affected over a period.
196	e := Effective(params.TOKEN, params.SlotsPerPeriod)
197	if s := Spendable(params.TOKEN, params.SlotsPerPeriod); s != e-39 {
198		t.Fatalf("spendable = %d, want effective−39 = %d", s, e-39)
199	}
200	if Prunable(params.TOKEN, params.SlotsPerPeriod) {
201		t.Fatal("a token is not prunable after a period")
202	}
203	if Elapsed(10, 5) != 0 || Elapsed(10, 15) != 5 {
204		t.Fatal("elapsed")
205	}
206}
207
208func BenchmarkEffective(b *testing.B) {
209	for i := 0; i < b.N; i++ {
210		Effective(params.TOKEN, uint64(i)&(1<<27-1))
211	}
212}