1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
|
# Federation: a design
A design, not what the code does: none of this is built. It says how a swarm can be
kept by parties that don't trust each other, for a first use: the krebs registry of
users, their hosts, and the hosts' names, addresses and keys
([krebs/kartei](https://github.com/krebs/kartei)), today plain files in a git
repository that one maintainer merges into.
Claims about the code as it is are marked *(checked)* where they were read in the
code, *(docs)* where they are taken from the docs, and *(assumed)* otherwise; the last
section lists them. How sure each part of the design is, is said with the promises.
## Optional
A swarm is federated if its genesis change carries the federated policy (below).
Everything here holds under that policy, and nothing else changes:
* A swarm started as today has no such policy and stays as it is: its rules, its users
with their capabilities, its remakes of every kind, its tokens, and what its nodes
send and do.
* The code is apart where it would cost. Judging reads the policy as it does today and
takes the federated rules under the federated one only; the resolved registry is
kept there only; envelopes carry their new fields there only. The wire's version
goes up for every swarm, as with every change to it.
* Shown at every stage by the existing tests passing untouched, and by the cost of
judging a change (`bench_screening`) staying where it is for a swarm without a
policy and with today's.
## The parties and the adversary
A **party** is a user and the nodes that carry for it. The user holds SSH keys and
signs; its nodes commit what it signed and sync with the others' nodes. Some users
are the swarm's **roots**: at first whoever starts it. Nobody owns the swarm, and any
party may be malicious, alone or together with others, a root too.
What an adversary can do:
* run nodes, and once it is in, bring in users of its own;
* craft any change: under any actor, with any dependencies (so "made long ago", as
the document sees it), any operations;
* send different changes to different peers, send none, or pass on only some;
* delay or drop messages between any nodes for as long as it likes, short of forever
between honest nodes;
* choose its node keys, and so where its nodes fall among the members;
* steal a key of another party (a user's key, a node's key), as a case of its own.
What it can't: forge an Ed25519 signature, or find two changes with one hash.
Out of scope: keeping the registry from being read (every party reads all of it),
hiding who talks to whom, and a party's own machine taken over whole (then the
adversary is that party).
The design asks one thing: that an honest federation bears whatever the malicious
do. It rules nothing about what happens on a party's own nodes, which nobody could
enforce: whom an operator lets in, what it lets them do, what it leaves out when it
reads. What it sees to is that nothing coming from any node breaks a promise for
the others.
## What is promised
To an honest node, whatever the others do, with any number of them malicious (3 to 5
but for what the voters can do to a user, said with each and below):
1. **Only valid changes.** Every change it holds passed the rules, judged as its
writer saw the document (at its dependencies).
2. **The same document.** Two honest nodes holding the same changes hold the same
document, and resolve it (Resolving, below) to the same registry. A remake changes
nothing that counts, whoever makes it and from whatever base: every node builds the
next epoch itself, and carries over what it holds beyond the base.
3. **Signed by its user.** Whatever the resolved registry shows in a user's namespace
was signed with a key that was that user's when it signed, or is as the root
change has it. What it shows as held by a user, the user claimed with such a key,
or a rule keeps for it, or a decision gave it (7). A key is a user's by what its
own keys signed, or by a decision that gave it first keys anew.
4. **One holder.** The resolved registry gives each name of each kind to one user at
most, and each user name to one user.
5. **First come, first served, once a root saw it, and for good once the voters
did.** A claim is **settled** once a node of a root committed a change after
receiving it, with no other claim of that name standing there: every other claim
of it, whenever it shows up and whatever it says it saw, is late. A settled claim
is a root's word, and what a root can still do to it is not promised against
(below). It is **final** once a third of the voters' nodes saw it hold the name
for as long as the policy says: from then on nobody else holds that name,
whatever shows up, whatever a root does, whatever is cut off, until its user
releases it or is gone, its own key is cut off, or the voters deal with it (7).
6. **Nobody waits for anybody.** An honest user's valid write needs no vote and no
other party's consent; it counts at once, and reaches every honest node its nodes
reach.
And for what the swarm decides together, with the fractions the design recommends and
fewer than a third of the voters malicious (the voters are the users the genesis
change names, or the decision that holds on who votes; a voter is honest here if its
user is and the nodes that carry for it are):
7. **Decisions by two thirds.** A proposal (who votes, who the roots are, a number,
the policy, first keys for a user that lost its own, a name) is decided only once
more than two thirds of all the voters voted for it, and nodes of that many held
those votes together. So none is decided that no honest voter voted for, and a side
of a partition decides only with nodes of that many voters on it. Of the decisions
of one matter every node acts on the same one, the last. Nobody is moved against
its will: a decision is refused by choice.
What is not promised:
* **One history at all times.** Both sides of a partition go on. A name claimed on
both sides goes to the side a root was on, or is contested until one side releases
it or the voters decide.
* **That a name is never contested**, before it is final. Before a claim is settled,
a claim made out of its sight contests it. After, a root does, by saying it saw
another first; and so does anyone, through one honest node of a root or of the
claimant that hadn't received the claim yet and is given the other first.
* **A moved-in user against its root.** The root named to give its first keys, while
no other root's node has seen its creation (that day, or with no other root), signs
a twin of it: the two contest, and nothing signed with the keys of either counts
until the voters give first keys.
* **A settled name against the roots.** One root contests it. To take it, every root
that saw it first has to turn: each cuts off the node that saw it. A final name is
out of their reach.
* **A name another gave up**, before it is final: whoever released it, or let it go
down past its limit or by a cut of its own, takes it back by cutting off the key
that signed that, where a root's node had seen it hold the name (Claims).
* **Protection from a stolen key** before its user notices: what was signed with it
counts until a key above it cuts it off; then all of it stops counting (Cuts), and a
user it created or vouched for goes out as by an unvouch, its names waiting until it
is gone; but a user another vouches for stays in, with what it claimed: a thief's
accomplice keeps the thief's sock in, and so does a root's node that witnesses for
it after the cut, in the open. Past what became final meanwhile, and what stopped
counting for good, it stays.
* **Agreement in the classic sense, for what users write.** There is no quorum there,
so no n ≥ 3f+1: promises 1 to 4 and 6 hold against any number of malicious parties,
and 5 from when a root saw the claim. Only decisions take two thirds, and only the
voters make them.
* **A name against the voters.** Two thirds of them give a user's first keys anew.
Meant for a user that lost them, it hands a name to whoever they say: in the open,
over the days a vote takes. The same two thirds free the names of a user that is
out, or give them to another, say who has a contested name, and decide a policy
that covers a name no more. And a third of them, stamping as they like, make a
user that is out gone, a claim final, and what a policy uncovered dropped, at
once. A third is one where there are up to three voters: a few maintainers at the
start are each that third. And a limit lowered for a day gives the names claimed
meanwhile, in sight of what fell past it, to their claimants for good.
* **A name through a long partition.** A user unvouched on one side of a partition
that outlasts `gone` is gone, though someone vouched for it in time on the other.
Two claims that each became final on a side of one that outlasts `final` are
contested, until one is released or the voters say whose the name is.
* **That everyone follows a decision.** A party refuses one it won't bear, and goes
on without it, with those who think alike: two epochs, by choice (Refusing a
decision).
* **A user put out by the swarm.** Nobody is put out by a vote: a user is in while
one user that counts vouches for it (Unvouching). So a user is out when those who
vouched for it say so: one root, for a user only that root created.
* **Decisions against a third of the voters.** A third or more of them keep anything
from being decided, and by voting both ways get two proposals of one matter
decided and choose which is the later. So does a node that carries for a third of
them, until they name another (Decisions).
* **When a proposal is decided.** One that had the votes and lacks records of nodes
hangs over its matter: whoever holds the last record chooses the day. The voters end
that by deciding a later proposal of the matter (Decisions).
* **Decisions without the voters.** With a third of an epoch's voters not taking
part (gone, silent, without a node that carries for them), nothing more is decided
there; what users write goes on. Those left go apart (Going apart).
* **Anything of 7 with one voter.** A swarm that one user starts has that user as its
only root and voter until it decides on others: it decides alone, and what a third
of the voters see, it sees alone. And as the only root, its cut takes back a name
only its creation holds, final or not (Cuts).
* **A bound on what an epoch's document costs.** What is valid as written every node
holds until a remake: statements past a limit, writers started past
`limits.writers`, a change of a few bytes that holds a million operations, a
snapshot built for every remake a node is offered. Each costs memory and time, and
nothing bounds how many reach a node as part of others' histories: a limit and a
party's budget bound how fast a node takes them from the party itself. Who did it
shows, under its nodes' signatures.
* **How often the swarm remakes, and from what.** The alive peers commit a remake as
in every swarm, and a party that runs most of the alive nodes has them. It changes
nothing that counts, and comes no sooner than `remakeChanges` and `remakeWriters`
allow; but each
remake of an epoch a node is offered costs it a snapshot, the lowest ID first,
until one comes out to the ID it was committed for.
* **A swarm that never splits.** A node that forks its own actor (two changes with one
number) splits the honest nodes that took one from those that took the other, until
one side drops its own (Partitions). It is found, proven and named; it isn't
prevented.
How sure: 1 to 4 follow from how changes are judged today plus rules of the same
shape, and from Kleppmann's result that a hash-linked change graph whose validity
depends on a change and its history alone converges whatever the faulty nodes do
(*Making CRDTs Byzantine Fault Tolerant*, 2022): high, given the conditions under Why
it holds. 6: high. 5 is this design's own construction, argued below: medium for
settled, and for final as sure as the lengths of time are, which are read from the
nodes' stamps: medium, less where clocks are off. 7 is the two-thirds argument with
votes that take days: medium. 5 and 7 want the tests named under Attacks, and someone
trying to break them.
## The design
It builds on the strict policy ([`access.md`](access.md), Values signed by their
users): values as envelopes their users sign, which every node checks against the
registry as the writer saw it. What it adds: users come in by being vouched for, and
go by being unvouched; each has its namespace; names of declared kinds are held by one
user each; what a key signed can be cut off after the fact; and the swarm decides by
its voters' votes.
### The policy, in the genesis change
A federated swarm's policy is
`{"version": 2, "values": "signed", "users": "vouched"}`, with what the rules read
beside it in `_continuum/access`: the kinds of names (`claims`), the paths in
namespaces whose values are signed (`userSigned`, as today), and the **numbers**. All
of it is in the swarm's genesis change, with the roots, the voters, and the users it
starts with, naming for each that has no keys the root that gives them. ("Root" here
is always a user: an epoch's first change, the genesis change or a remake's snapshot,
is its **root change**.)
* Nothing is ever written before the policy, so nothing is judged by none.
* Every node is given a root change and takes no other: the genesis change
(`--genesis-root`), or, in a swarm that was remade, the ID of a later epoch. That
is what a party trusts, not what its seeds say.
* A node that doesn't know the policy doesn't sync at all. (Today it receives
without judging *(docs)*, which here would let anything in.)
The policy changes by a decision: each number by itself, the rest as a whole (The
policy changes by a decision).
**The numbers.** The quantities of this design are numbers of the policy. The design
recommends; the genesis policy sets each, and a decision changes any of them to any
value:
| Number | Recommended | What it says |
|---|---|---|
| `window` | 7 days | how long a vote runs |
| `gone` | 30 days | after how long seen out a user is gone; none: its names wait until a vouch or a decision |
| `final` | 30 days | after how long seen holding a name a claim is final; none: never |
| `uncovered` | 90 days | how long what a policy no longer covers stays aside before it is dropped; none: until its user takes it away |
| `archiveRetention` | 90 days | how long a node answers for an epoch it left, at least |
| `stamp` | 1 day | how often a node that is up renews its alive stamp |
| `remakeChanges` | 10000 | changes an epoch's history holds beyond its root change before a remake |
| `remakeWriters` | 1000 | writers an epoch's changes start before a remake |
| `witness` | 1 minute | how long a root's node lets a claim wait before it writes |
| `catchUp` | 10 minutes | how long a node that comes back waits to be caught up before it writes |
| `limits.keys` | 64 | keys a user has at once |
| `limits.nodes` | 64 | nodes carrying for a user at once |
| `limits.users` | 16 | users a user created that stand; a root: no limit |
| `limits.vouches` | 64 | vouches of a user that stand |
| `limits.proposals` | 8 | proposals of a user that are open |
| `limits.writers` | 64 | writers a user's nodes start in an epoch before more are put off |
| `limits.name` | 255 | bytes of a name |
| `limits.entry` | 4096 | bytes of a node's member entry |
| a kind's `limit` | none | names of the kind a user holds by a claim |
| `fractions.decide` | 2/3 | a decision takes more than this share of all the voters |
| `fractions.seen` | 1/3 | the share of the voters whose nodes must have seen a thing for long: a user out, a claim holding, a thing uncovered |
What today's genesis change sets for the swarm as a whole (how many neighbours, the
topology, the dissemination *(checked: `swarm::bootstrap`)*) are numbers of the policy
too. The relays aren't: in a federated swarm they are each node's configuration
(`--libp2p-relays`), addresses its operator lists, which come and go, nothing in the
document, which nobody may write plain.
Nothing constrains them, and a number that makes no sense has the result it has. A
time of nothing is "at once"; a limit of nothing lets nothing more in. Three end
deciding itself: a `fractions.decide` of 1, `limits.proposals` at 0, a `window` of
nothing. What is left then is refusing that decision, or going apart. A proposal that
leaves a number without a value where it needs one is no proposal. More than a share
is strictly more; a share of the voters, for what was seen for long, is the fewest
voters that are that share at least, and one at least.
Where this text says two thirds and a third, it means the two fractions as
recommended. What is promised of decisions is argued for those; a swarm that sets
others has what its numbers carry (Why it holds). What a node does for itself alone
(how fast it takes a party's changes) is its own setting.
### Users: statements, keys, nodes
`_continuum/users/<name>/<digest>` holds the **statements** about and by a user, each
an envelope kept under its SHA-256, never replaced or deleted: the register only
grows. A statement is signed by one user and says one thing:
| Statement | Signed by | Says |
|---|---|---|
| `create` | another user (the creator) | the name, its first keys |
| `vouch` | another user | "I vouch for this user too", naming it by its ID (no keys) |
| `unvouch` | the signer of a `create` or `vouch`; a root, for what is the seats' | that one taken back (Unvouching) |
| `key` | the user | one more key |
| `retire` | the user | a key, and the cut after which what it signed doesn't count |
| `node` | the user | a node that carries for it; or one that stops, with a cut |
| `release` | the user | a claim, a vote or a proposal of its own given up; or itself |
| `claim` | the user | a name it wants (Claims; in the name's own register) |
| `propose`, `vote` | a voter (a fork: any user) | Decisions |
* **A statement says where it was signed.** Its payload names the changes its signer
had seen, by their hashes (`seen`), as a cut does, and a change that carries it
must have them in its history. One statement is **in sight of** another if the
other is in the history of what it names. That, and not the change that happened
to carry it, is a statement's place wherever its place matters: carried a second
time, by anyone, it is where it was. Its envelope names the register as its path.
* **A user is its creation.** The `create` statement's digest is the **user ID**, and
every envelope the user signs names it, with the swarm and the epoch it was signed
in. Two creations of one name are two users with two sets of keys; which has the
name is decided below, and a key listed in both signs for the one its envelope
names.
* **A user the root change holds** has the ID given there, and needs no creation. It
may be there without keys (a registry moved in from elsewhere): then it is in, has
its name and what the root change holds in its name, and nobody signs for it, until
the root the root change names for it gives it its first keys, by a `create` for
that name. That is no other user, and no other root's `create` gives it keys. Should
that root sign two, they are claims of one thing, ordered as claims of a name are
(Two claims), with the other roots' nodes alone as their witnesses (a user's nodes
carry for it by its keys, which these decide; its root's nodes witness for its own):
one signed in sight of another that stands is refused, and one late against another
is late for good. Which one remains is read over all the changes, as for a name, and
not where each statement was signed: a twin on old dependencies gives keys nowhere.
Of two that contest each other (no other root's node saw one first, or two saw them
in two orders), neither gives keys, and nothing signed with the keys of either
counts, until the voters give first keys (Decisions); what was signed with the keys
they give counts then. No root releases its `create`: once one gives keys, they are
the user's, which gives itself up as any user does.
* **A user's own name, by its own key.** A user claims its own name as a name of the
kind `user`, signed with its own key: a claim of what it has already. It counts
toward no limit, a user has one at a time, and it holds the name on where its
creation no longer does (its creator's key cut off: Cuts). It is valid only where a
rule of the kind `user` would let the user itself create that name: a name kept for
one creator's creations goes with that creator's cut, and where only the roots
create users, a user's name rests on its creation, which a root's own cut takes back
only where no other root's node had seen it, and the voters' cut whoever saw it
(Cuts). A rule that changes by a decision uncovers own-name claims as it uncovers
any claim. A creation of the name in its sight is refused, as a claim is. Clients
make it right after a creation.
* **Keys form a tree.** A user's first keys are those its creation names. A `key`
statement adds one, signed with a key the user has, which is **above** the new one,
as are the keys above itself. Any number over time; at once as many as
`limits.keys` says. Use: the first keys stay offline, and add the keys of the
devices. Any key signs for its user, but for one thing: giving the user up takes a
first key.
* **A node carries for a user** once the user named it and the node agreed: the node
itself commits the `node` statement that names it, in a change that holds nothing
else but its member entry. A node commits changes only while it carries for a user,
and any node commits any user's statement but a `node` statement, which the node it
names commits: a node can choose when it commits one, and on what, but not what its
signer says it saw, so which node commits a statement, or whose, says nothing of it.
So every change is some party's: its node's signature proves the node
([`access.md`](access.md), signatures required), and the user's statement binds the
node to the user. At once as many nodes a user as `limits.nodes` says.
* **A user without a node** names another party's, which carries for it too if it
agrees. That node's changes witness for both, and it takes proposals up for both:
for the swarm, such a user is the party that carries for it. Nothing is signed in
its place. It names nodes of more than one party where it can: each records for it,
so no one of them alone keeps it from counting, nor chooses the day.
* **Writers.** A node writes as a writer (an Automerge actor), a fresh one each time
it starts, rejoins or drops *(docs)*, and when a change of its own writer that it
didn't make reaches it signed with its own key: a copy of its files writes as it
too. Unsigned, such a change is anyone's forgery, and switches nothing *(checked:
`access::screen`)*. Every writer costs every node memory while the epoch lasts, in
proportion to the document's history: about 4 bytes per change *(measured
upstream)*. So a federated node keeps its writer over a clean stop, and each node
counts the writers each user's nodes start in the epoch: past `limits.writers`, a
change that starts another is put off by every node that would take it from that
user's nodes, until a remake. A node's writers count for one user: the one its
member entry names, of those it carries for, where each writer starts (a writer
counts for the user it was counted for, until a cut leaves it out), its own word,
carried over a remake with the entry; naming none of them, the user of the `node`
statement naming it with the lowest digest, of those that count there, so that its
operator names one to choose. So a user past its limit puts off the nodes whose
writers count for it, and no other that carries for it too. It is never refused: put
off is each node's doing, its operator may take what it puts off
(`POST /admin/put-off/take`, naming the user), and a change that reaches a node
within another's history is taken. Writers a node started outside a cut it was
stopped with count for nobody: a thief's node costs its victim nothing once cut off,
and where the count falls back below the limit so, every node takes what it put off
for that user, read again from the changes, nobody acting: late, with what was built
on it. A writer is a run, not a write: 64 are a node restarting weekly for more than
a year. Each costs every node 4 bytes for every change of the epoch, those before it
started too *(measured upstream)*: 64 cost some 2.5 MB at `remakeChanges` changes.
Where epochs last long (few nodes, writing little), a user whose nodes restart often
reaches it first: such a swarm sets it higher. A node whose writers count for a user
past it is put off as a whole, with what it carries for others and its records of
proposals, until a remake or its operator takes what is put off; how many a user's
nodes started shows (`GET /registry/users`), for a remake to come first.
* **A party's budget.** A node takes changes from a party's nodes no faster than a
budget, its own setting (`--party-budget`): changes, their bytes and their
operations an hour, recommended 600 changes, 4 MiB and 100 000 operations a party.
What is over waits, and nothing is refused for it: a change larger than what is left
of the hour is taken once nothing of its party waits before it, and the party's next
changes wait until the hour it overdrew is paid. For a budget a party is a user with
the users below it that no line reaches but through it, as the graph stands where
the node reads it: creating users makes no second budget. A node's changes draw on
the party of the user its writers count for (above), whatever they carry: a
statement another party hands a node draws on the node's party, which takes it at
its own pace.
* **Past a limit.** A user's statements of one kind are counted from the first: each
has, and states, the number after the highest of those it was signed in sight of,
and of two with one number the one with the lower digest comes first. A statement is
past its limit if as many of that kind come before it as the limit allows (a user's
claims of one name count once: Two claims). What was given up (a key retired, a node
stopped, a claim released, a proposal decided or released) or is left out by a cut
comes before nothing, whenever that was: so what a thief signed with a stolen key
stands in nobody's way once the key is cut off. What comes to count that way, later
than it was signed, gets nothing by it: a claim gives way to what was claimed in
sight of it meanwhile (Claims). It doesn't count while it is past its limit. The
limit is the one that holds where the registry is read: lowered, it leaves out the
last. So for every limit: keys beyond the first, nodes, creations, vouches,
proposals, a kind's claims. Across a remake, what the snapshot holds comes first,
then what is carried over, by the numbers it states, then what is signed in the new
epoch (Remakes).
* **Names** of users are 1 to 64 of `A-Z a-z 0-9 . _ @ -`, as today, less the
top-level keys the swarm uses otherwise (`_continuum`). Which of them may be
created, and by whom, the kind `user` says (Claims).
### Vouching, lines, the roots
A user creates whom it likes, within a limit (`limits.users`), and vouches for whom it
likes, within another. The new user signs, claims and creates in turn from its
creation on: in any change that has the creation in its history.
Users and what they signed for each other form a graph, the roots at its top. A
**line** of a user is a chain of creations and vouches that count, from a root down
to it. A user is **vouched for**, and in, while it has a line. So rings away from the
roots hold nobody, and a vouch by a user whose own lines all pass through the one it
vouches for adds none. When its creator goes (unvouched, cut off, out), a user that
another vouched for stays in, by that line, without doing anything. When the last
goes, it is out (Unvouching).
A line says who is in, and nothing else. Who vouched for whom gives nobody a say
about another's names (the witnesses of a claim are its user's nodes and the roots':
Two claims), and says nothing about who connects to whom (Reaching the others). What
it does give: a creator's limit bounds how many users come in through it, and each
shows below it, for all to see, and goes with it when it goes.
Bringing someone in means handing over, out of the document, what a party needs to
connect and to start (the root change, some seeds, the swarm key where there is one),
and writing the `create`.
**The roots** are the users the genesis change names as such (the user who starts the
swarm, or those the file it starts from names), and then those a decision names
(Decisions). A user is a root where such a decision names it, and that is read where
each thing it does was done: its nodes' change witnesses as a root's where the
change's history has it a root, and what it signed is a root's where it was signed.
What sets a root apart:
* It is in by its seat: it needs nobody's vouch while it holds one, and nobody's
unvouch puts it out. A user that held a seat and holds none any more is in like
anyone, by a line: one that leaves its seat has someone vouch for it, or is out.
* The lines start at the roots. What a root signed for another (a `create`, a
`vouch`) counts while its signer holds a seat, and is the **seats'** after: it
counts while there are roots, whoever they are. A user the root change holds
without a creator is in by the seats too. Its signer takes back what it signed
while it holds a seat. What is the seats' the roots take back together: it is
taken back once each of them unvouched it. So where there are several, no root
alone puts out a user the root change holds.
* Its nodes' changes witness every claim, which is what settles one.
* It creates users without a limit. What is the seats' counts toward nobody's limit.
* It holds the names a rule gives to a root, while it holds its seat. A decision that
leaves a root out says which root has each of them from then on: its claim is
made over, and no such name is ever without a holder. What a user signed before it
was a root stays its own.
A root can't write in another's namespace, nor, where there are others, take a name
that is final. It can contest any name that isn't, in the open. With several roots,
any one that is up settles claims, any one that lies contests them, and none takes a
name alone. A root that is away, or turns on the others, the voters leave out
(Decisions); what is final stays as it is meanwhile.
### Lengths of time
The document orders what was written: a change's history is what its writer had
seen. It measures no time. The nodes' alive stamps do, each by its own node's clock
*(checked: `alive`, Unix ms)*. So a length of time is read between two stamps of one
node, and what that node had seen at each, from the stamps' histories.
A thing has been **seen for** a length of time, at a set of changes, once a third of
the voters (`fractions.seen`; the voters: Decisions) each have a node with two alive
stamps that far apart or more, the thing so at both and at every stamp of that node
between. The earlier stamp is in the later one's history, and between them are that
node's stamps that have the earlier in their history and are in the later's: so a
stamp that shows up afterwards, built on neither, lies between nothing. A thing is
so at a stamp as that stamp's own history resolves. A length of nothing takes one
stamp. A node counts for one voter in this, though it carry for several: as many
voters have seen a thing as can each be given a node of their own. It is read from
the changes alone: the stamps are changes in the history, each renewal one.
* A node that is up renews its stamp as often as `stamp` says, whatever else is
written or isn't. (Today the interval follows what members publish in their
entries *(checked: `swarm::members`)*; in a federated swarm it is the policy's.) So
nobody does anything to be seen, and there are always stamps to read time from.
While no node writes at all, no time passes: nothing is seen for longer by it.
* The length that counts is the number's as it holds in the later stamp's history.
What was seen for long stays so: gone, final and dropped never go away.
* A remake starts no length anew: the snapshot holds how far each had run, and the
nodes' stamps go on from there (Remakes).
No clock is compared with another. A third, because decisions are argued against
fewer than a third of the voters being malicious: so few show nothing by themselves,
whatever they stamp. And no more than a third, because everyone it takes must be
there: two thirds may have left, and the rest still see it.
### Unvouching
A user takes back a `create` or a `vouch` it signed: `unvouch`, naming it. Nobody else
can; what is the seats', the roots take back together (Vouching). What it does,
exactly:
* **From the unvouch on, as far as the user had been seen.** What the user signed
counts through this creation or vouch if the unvouch was signed in sight of it, or
if a node of the unvoucher or of a root committed a change with it in its history
and not the unvouch. Everything else it signs is past the point. So an unvouch
that says it saw little undoes nothing that its signer's own nodes, or a root's,
had seen.
* **Another vouch keeps the user.** With another line, the user stays in, with
everything it has.
* **Else the user is out, from there.** Nothing of it counts: its namespace doesn't,
its nodes witness nothing, and what they commit in sight of the unvouch is refused.
Its names **wait** for it, its user name among them: its claims stand, so nobody
else claims them, and nobody holds them. One thing it keeps: where it is a voter, it
votes on, and its nodes record proposals (Decisions). Who votes is the voters' word,
not its vouchers'.
* **Those it brought in go with it,** from the same point: a user all of whose lines
ran through it is out too, with the same consequences, unless another user that
counts vouches for it, before or after.
* **A vouch brings a user back,** with its names and what it signed in between, as
long as it isn't gone. What another claimed meanwhile, in sight of a claim of the
user's that didn't count then, stays the other's (Claims).
* **Out for long is gone.** A user is **gone** once it has been seen out for `gone`
(Lengths of time). Then its claims and its creation stand no more: whoever comes
first claims its names, and no vouch brings it back. It comes in again by being
created anew.
* **Or by a decision.** While a user is out, the voters free its names or give them
to another (Decisions), at once and whatever `gone` says. Where the policy sets no
`gone`, the names wait until a vouch or a decision.
* **What it did before stays done.** Releases it signed stand, and so does what
others built on them.
* **Out of sight.** What the user signs saying it saw nothing of the unvouch, or on
the far side of a partition, is valid as written, so nodes hold it; it is past the
point, and doesn't count. A node takes changes of an unvouched user's nodes only as
part of another party's history, never from those nodes, so they can't make it work;
but for their records of proposals and carry records, where the user is a voter
(Decisions).
So whoever relied on a user that is out has that long to find another who vouches:
for itself, and for those it brought in. Until then nothing it holds is taken, but
by a decision.
**Only who signed takes back.** A vouch is its signer's word, and nobody else takes
it back: not the users above the signer either, who answer for the signer, whom they
brought in. One of them that wants a user out unvouches whom it brought in itself.
That takes all below along, and those worth keeping get another's vouch while their
names wait. Were it otherwise, a root, above everyone, would put out whom it liked,
and for good: every line passes one.
**Nobody is put out by a vote.** A user is in while one user that counts vouches for
it, and no decision changes that. Against a user that keeps within the rules and
harms all the same (squats names up to its limits, gets others' names contested)
there is: the voters saying who has a contested name; its vouchers unvouching it;
and a root unvouching
the user it created above it, with all below, who then need other vouches. A vouch
from anyone brings it back.
A user gives itself up by a `release` of its own creation, signed with a first key.
That puts it out by its own word: its names wait, and it is gone once seen so for
`gone`. Until then a cut takes the release back like any other statement, the
voters' cut too, where the first key was stolen.
### Namespaces
A user's namespace is the top-level key with its name. One rule: below `<name>`, only
envelopes signed by a user of that name, at the depths `userSigned` lists (for the
registry, `["*", "hosts", "*"]`: a host is one signed value). A value there is
replaced as today, by an envelope naming the one it replaces (`prev`): the value that
shows there where it is signed. Where several count there (written at once), it names
any one of them, and replaces them all, as a write in the document does. Nothing plain
is written anywhere but a node's own member entry, its own records of proposals and
its carry record.
Delegating (another user writing below `<name>/shared`, say) would be a statement in
the user's register granting a capability within its namespace: for later; the rule
has room for it.
### Claims: names held by one user
What must be unique across users (a host's name, an address, a top-level domain) is
**claimed**. The swarm declares the kinds, as data in the policy:
```json
{ "name": { "chars": "a-z0-9-",
"rules": [ { "match": "**.{user}.*", "by": "{user}" },
{ "match": "*.*", "by": "{voters}" },
{ "match": "*", "by": "{root}" } ] },
"ip4": { "chars": "0-9",
"rules": [ { "match": "10.243.*.*", "by": "*" } ], "limit": 256 },
"user": { "chars": "a-z0-9_-",
"rules": [ { "match": "*", "by": "*" } ] } }
```
* **A name is written as it is used**: `toaster.tv.r`, `10.243.0.7`. It is one key in
the document, and a rule's `match` is written the same way. Both are split into
segments at the kind's `separator` (a dot, unless the kind names another) and
compared segment by segment: `*` fits any one segment, `**` one or more (once in a
rule), `{user}` one segment, taken as a user's name, anything else itself.
* **Structure, not meaning.** Continuum doesn't ask what a segment is:
`10.243.foo.bar` fits `10.243.*.*`. Nor does it know that two spellings mean one
thing (`::1`): names are compared as written. What a name means is the
application's, which claims one spelling and reads no other. A name is `limits.name`
bytes at most, and no path: it has no `/`.
* **Its characters.** A kind may say what its names' segments are made of (`chars`:
characters and ranges of them). A name with any other isn't one of the kind, so
the `10.243.foo.bar` above is none where `ip4` says digits. Recommended wherever
case means nothing: lower case only, so that `TV` is no name beside `tv`. The kind
`user` says so for the users' names, within what continuum takes for one.
* **The first rule whose `match` fits says who may hold the name** (`by`): a user, or
one of a list; anyone vouched for (`"*"`), first come, first served; the user whose
name stands where `{user}` does; a root (`"{root}"`); or whom the voters give it
to, by a decision (`"{voters}"`). No rule, no holder.
* A name a rule gives to `{user}` is **kept**: it is that user's without a claim,
since nobody else could claim it, and it is nobody's while there is no such user.
Its user may claim it all the same. Such a claim doesn't count toward the kind's
limit while the name is kept, and is what holds the name on if a policy stops
keeping it.
* So above: everything below `tv.<tld>` is tv's, for any top-level domain, whatever
tv claimed. A name right below a top-level domain (`wiki.r`) is given by the
voters. A top-level domain is a root's to claim. An address goes to whoever comes
first, 256 a user.
* The kind `user` is the users' names themselves: its rules say who may create which
(a swarm can keep names for one creator). Above, anyone creates a name of one
segment.
`_continuum/claims/<kind>/<name>/<digest>` holds the statements about one name, again
only growing: `claim` (by the user who wants it) and `release` (by that user, of its
claim: how a name is given up). A claim **stands** while it counts, isn't released,
its user isn't gone, a rule of the policy lets its user, and no decision freed the
name or gave it to another. The claims of a user that is out stand as they stood: a
rule that lets anyone lets anyone who isn't gone.
A claim is taken, as its writer saw the document, if a rule lets the user, the user
is within the kind's limit, and no claim of that name stands there. That is first
come, first served wherever one claim was made in sight of the other: the later one
is refused by every node.
**In sight of a claim that didn't stand.** A claim is taken where it was committed.
The registry asks again, among all the changes a node holds, whether the other stood
where the claim was signed: in the history of what the claim says its signer saw, with
the decisions and the witnesses there (an unvouch reaches only as far as its signer's
nodes and the roots' hadn't seen: Unvouching). If it stood, the claim gives way, as if
it had been refused. If it didn't only by an unvouch or a cut (its user's line, or the
key that signed it, left out there), the two are ordered as claims out of each other's
sight (Two claims), over all the changes, with the roots' nodes alone as their
witnesses: what the claimant says it saw is its to say, but not which witnesses it
saw, and the roots' nodes witness wherever they wrote. Neither the claimant's own
nodes nor the other's count here: the claimant saw the other, and the unvouch or the
cut, and said so. Else the other gives way, for good: whatever has it count or stand
again later (a limit raised, a rule that lets its user again) doesn't bring it back
over the claim.
One thing does bring an earlier claim back over a later one: it was down only by a
release, by a cut, or by statements past which it fell (its limit) that a cut has left
out since, and a root's node had seen it hold the name before it went down. It is then
read as never down, and the later one gives way, unless it is final (below). That is
what a user has against a thief who released its names, or claimed before them to push
them past their limit; and it holds for the user's own doing too: a name it gave up so
by its own key it takes back by cutting that key off. A claim that was cut off before
anyone saw it hold, to wait for someone to claim the name, comes back over nothing.
The registry shows such a later claim as held while a release, a cut, or the
statements past which the other fell stand; and one made in sight of a claim down by
an unvouch or a cut, as held while that stands, since a root's node may still witness
the other.
A claim says nothing else. What the name is for is in the namespace: a host's entry
names its addresses and names, and they count while its user holds them.
### Two claims out of each other's sight
Two users claim one name at once, or on two sides of a partition, or one of them
pretends to: it crafts a claim that says it saw nothing of the other's. No node can
tell these apart, and both claims are valid as their writers saw the document, so
every node holds both. What decides is who can be shown to have seen what. The
witnesses for a claim are its **side**: the nodes of its user and of the roots.
* Of two claims neither of which was signed in sight of the other, one is **late**
against the other if a change committed by a node of its side (one carrying for its
user or for a root when it committed it) has the other in its history, standing
there, while the claim itself wasn't there yet, or didn't stand there: the
claimant's side had seen the other hold the name while the claim didn't. Whether a
claim stood there is read from that history; one that was down there only by a
release or a cut that a cut took back since is read as standing. Where one was
signed in sight of the other, sight decides, or, where the other was down there only
by an unvouch or a cut, the roots' nodes alone (Claims).
* A claim that is late against another, and not the other against it, is late for
good: it doesn't stand, and its user claims anew. So nobody waits in line for a
name with a claim that says it saw nothing: when the holder releases it, is gone,
or the voters free it, whoever comes first then has it. Two claims that are each
late against the other both stand.
* A user's own claims of one name are one: they don't contest each other nor make each
other late, the name is the user's while any of them stands, they are ordered
against others by the first of them that stands (by the numbers they state, then the
digest), and they count once toward the kind's limit. A release gives up every claim
of that name of its user but those signed in sight of it, those committed after it
among them: to claim the name again, the user claims in sight of its release. So it
doesn't matter from which node, or whose, a user claims, nor how often.
* Of the claims of a name that stand, those remain that give way to none. If one
remains, its user holds the name, or has it wait while it is out. If none or
several do, the name is **contested**: nobody holds it, until releases leave one,
or the voters say whose it is (Decisions).
Being late is read from the changes alone, so every node finds the same. It goes
away only with its witness: where the node that committed the change is stopped with
a cut from before it (Cuts).
What this gives:
* **Settled.** Every node writes its member entry as often as `stamp` says, and a
root's node also once claims reach it that it hadn't seen: within `witness`, one
change for all that reached it meanwhile, so no more often than `witness` (with a
minute, 1 440 changes a day, within the budget recommended for its party). Such a
change has in its history everything the node had received. The roots' nodes are on
every side. So once a root's node wrote after receiving a claim, while it held no
other of that name that stood, every other claim of the name is late against it: one
surfacing later, however little it says it saw, and one that was there and comes to
count later. The claim is **settled**, within `witness` of reaching a root's node. A
node tells (`settled`, below).
* **Several roots.** Any one of them settles a claim. Two that received two claims in
different orders make each late against the other: contested, as two claims made
at once are, and one releases. So with more roots a claim is settled though one is
away, and two made within the same moment are contested more often.
* **A user that is up is bound by its own node**: after its node wrote once with a
claim in its history, it never holds that name against it, short of stopping that
node with a cut from before.
* **To take a name from a claim**, a rival needs the claim to be late and its own not
to be: a node of the claimant or of a root that wrote after receiving the rival
and before the claim, and no root's node that wrote after the claim and before the
rival. Once a root saw the claim, the second can't be, short of that root cutting
its node off.
* **Before a claim is settled**, a claim out of its sight contests it, or holds,
where a root's node received that one first. Honest users claiming at once see
"contested", and one releases. While no root's node is up, a claim isn't settled,
and whichever of two reaches one first when it is back holds.
* **A node that comes back** (started, or cut off for a while) writes nothing before
it caught up with the peers it keeps (its user's other nodes, its seeds): until it
holds the heads each of them had when it reached it, as the first STATUS says (past
32 heads, the sync that follows it), whatever they write after, or `catchUp` passed.
A peer that keeps sending keeps it silent no longer. So it is the harder to hand a
node a rival before the claim it would have seen first.
* **Final.** A claim is **final** once it has been seen holding the name for `final`
(Lengths of time). From then on no other claim of the name holds it or contests
it, whatever a witness says and whatever is cut off: not a rival that a root says
it saw first, not an earlier claim whose release is cut off, not one that shows up
with a witness of its own. It ends as a claim does (released, its user gone, by
the voters), and it doesn't count where the key that signed it is cut off from
before it. Final takes no root: a claim nobody contested for that long is final
though no root ever saw it. A final claim gives way to none and is late against
none, but for another final one: two final claims of one name contest each other,
however they came to be, until one is released or the voters say whose it is.
* **A name a root keeps contested** never becomes final by time: final takes holding
the name. The voters say whose it is (Decisions), name by name; or they end all of
that root's contests at once, by giving its first keys to someone who stops its
nodes with a cut from before them.
So within a minute a name is its claimant's against any claim that says it saw
nothing, as far as a root's node had the claim first. And within `final` against
everything else: until then a root can still contest it, in the open, and so can
whoever hands a node of a root or of the claimant a rival before the claim. The voters
leave out a root that does.
A user's name is claimed the same way: the `create` statement is the claim, its side
the nodes of its creator, of the new user and of the roots. Two creations of one
name out of each other's sight are decided as above; while it is contested, no user
has the name, and neither namespace counts.
A user that doesn't have its name still holds what it claimed where anyone may claim:
those claims stand, so contesting a user's name frees none of them. What a rule gives
to a name (a kept name, a name only `tv` claims) is nobody's while the name is.
### Cuts: what stops counting
A **cut** is a set of changes, named by their hashes: "as far as I saw". A statement
is within the cut if a change that carries it is in the history of the cut, or, for
one the epoch's snapshot holds, if the cut's list names it (below). Whether it is
doesn't depend on who asks or when: a change's history is fixed by its hash.
* **Retiring a key** names the key and a cut. What the key signed within the cut
counts as before; what it signed outside doesn't count, for anyone, whenever it
shows up. A statement signed with a retired key and offered later, saying it saw
little, is outside the cut. That is how retiring reaches a node that was away: it
needs no order of arrival.
* **Who retires what.** A key above another retires it with any cut: a user whose
device key was stolen cuts it off from before the theft. A key retires itself only
from where it stands (its cut must hold everything it signed that the retiring
change's history holds), and, since whoever commits the retirement chooses that
history, takes back nothing that a node of its user or of a root had in its history
without the retirement, as far as an unvouch reaches (Unvouching): rotating, not
rewriting. No key retires one beside or above it, so a stolen device key can't cut
off the keys above it, nor undo what it signed before.
* **What a cut keeps, it names.** Beside the cut, a `retire` lists by digest what it
keeps of what the key signed: what is within the cut of the epoch's own, which every
node checks where the statement is taken, as it checks a number; and what it keeps
of what the snapshot holds, which is in the history of every change after it, so the
list alone says. So what a retirement keeps holds also where the changes its cut
names aren't there: after a remake. A node's stop lists what its cut keeps the same
way, and so does a decision's cut of a user's first keys. A list is 32 bytes for
each statement and value kept that hasn't stopped counting for good.
* **A node that stops carrying** is named with a cut the same way, by the key that
named it or one above: its changes outside the cut witness nothing, and the writers
it started there count for nobody (Users). What it carried there counts as its
signers signed it: any node may carry a statement, so which one did says nothing of
it, and its stop takes none back.
* **A cut never reaches its own statement.** A `retire`, a stop and an `unvouch` count
by the key that signed them as it was where the statement was judged, and are left
out only by a cut of that key set by another statement. So a key retires itself, and
a node commits its own stop.
* **What a cut takes back.** Everything the key signed outside it: a claim, a release,
and also what that key cut off itself; a vouch and a creation as its signer's
unvouch would (below). The keys it retired and the nodes it stopped count again, and
a user it unvouched is in again. That user's claims from before stood all along, its
names waiting; what it signed while it was out comes to count later than it was
signed, so a claim of it gives way to what was claimed in sight of it meanwhile.
What became gone, and what a decision dealt with, stays so.
* **A vouch or a creation taken back.** A `vouch` or a `create` outside a cut stops
counting as an unvouch by its signer would, signed where the statement that set the
cut was (a decision's: its proposal): what the user signed counts through it where
that statement was signed in sight of it, or where a node of the signer or of a root
committed a change with it in its history and not that statement (Unvouching): a
signer that turns on what it created cuts as it would unvouch, and the roots' nodes
witness against both. A root's node that witnesses so for a thief's sock keeps the
sock in, in the open. With another vouch standing, the user stays in, with its keys,
its claims and the users it brought in. Without, it is out from there: its names
wait, final ones too, and it is gone once seen out for `gone`, unless a vouch comes.
* **A creation is also a claim.** A `create` outside a cut is taken back as the claim
of the user's name too; not as the user: its ID and first keys are what the creation
names, and a vouch names a user by its ID. A root's creation is not taken back by a
cut a user set (the root itself, or a thief of its key) where a node of another root
had it in its history and not the statement that set the cut: there it stays the
claim of its user's name, and, for a user the root change holds, its first keys. So
a root that turns takes back only a creation the other roots' nodes hadn't seen,
minutes old, never a name settled or final. The voters' cut, by first keys they give
a root (Decisions), takes back what the cut-off key created outside it, whoever saw
it: two thirds of the voters undo a stolen root key in one decision, and no root
does alone. With one root there is no other to have seen anything: its own cut takes
back what it created, a user's name with it where only the roots create users, final
or not. Its name the user keeps where it claimed it with its own key (Users), that
claim ordered from where it was signed; else it is without a name, as a user that
lost its name, and its namespace doesn't count until it has one.
What stops counting stays in the document, and every node holds the same. It is left
out when resolving. In a namespace, where a value that doesn't count replaced one
that does, the one that does is read again (Resolving).
**For good.** What doesn't count because it was given up, replaced, left out by a cut
or past its limit, and has been seen so for `final` (Lengths of time), has stopped
counting for good: no cut, no limit raised, nothing brings it back. Not so what
doesn't count only because its user is out, which waits until the user is gone, nor
what a policy no longer covers, which stays aside until it is dropped. A remake leaves
out what stopped counting for good (Remakes).
The price: a key above retiring one below with an early cut takes back what that key
signed since, a release among them, further back than an unvouch reaches; a vouch or a
creation no further than its signer's unvouch would, signed where the retirement was,
with the same witnesses, so a user brought in goes out, its names waiting. Whoever
relies on another's statement relies on that, until what it holds is final: a second
vouch is what keeps a user in, whatever becomes of its creator's keys. And a user's
first keys have none of its own above them: above those are the voters, who give a
user first keys anew by a decision (Decisions).
Any key of a user signs for it, so a device key in the wrong hands unvouches whom
the user brought in and releases its names. A key above takes all of that back with
a cut, as far as nothing final was built on it. Only giving the user itself up takes
a first key.
A cut reaches back as far as anything still counts or could: what stopped counting
for good, it doesn't bring back.
### Leaving a user out when reading
A side note, since it is no part of the design: nothing here lets the swarm bar a
user, and nobody is put out by a vote. What a party does about a user it can't
unvouch (one that squats, a root that contests its names) is its own: whoever reads
the registry may leave out whom it likes, from where it likes, and reads on without
them. That changes nothing any node takes or refuses, so it splits nothing; it also
means two parties that leave out differently read two registries where a name is
contested. A node bars no node for the swarm either: it stops its own with a cut,
and refuses as peers whom its operator says.
### Decisions
Some things are the swarm's to decide: its numbers and the rest of its policy, a
user's first keys where it lost its own, the names of a user that is out, whose a
contested name is, names the rules leave to the voters, who votes and who the roots
are. They are decided by votes of users, signed by them, over days.
**Who votes.** The **voters** are the users the genesis change names (the user who
starts the swarm, or those the file it starts from says), and from a decision on who
votes, those it lists, by their IDs. So who votes is decided by those who vote;
nothing that happens after a proposal is signed takes a user off its list or puts one
on; and a swarm that one user started is that one's to decide until it decides on
others. A voter votes with the keys the document has for it, whether it is in, out or
gone: who is in is its vouchers' word, who votes is the voters'.
What to weigh in a list:
* Every voter named counts toward what a decision takes, whether it takes part or not:
more than two thirds of all of them. One that never votes stands in the way like one
voting against. With a third of them not voting nothing is decided, a list naming
others neither.
* So a list names those who take part: recommended, the users who voted or signed
anything in the epoch, which a client makes from the document. All users may be
on it; in a registry of many of whom few care, that is the last thing decided.
* A swarm names its voters anew while two thirds of them still take part. Past that,
those left go apart, naming who votes among them (Going apart). So that the line is
seen coming, `GET /registry/decisions` shows for each voter when it last voted and
when a node of its last stamped.
* What is seen for long takes a third of the voters each with a node of their own.
A voter without one is whoever carries for it: where one node carries for a third
of a list, that node has the say a third has.
* Whoever brought users in brought voters in, where the list has them: a user that
created sixteen is seventeen of it.
The voters see a list before they vote for it (`GET /registry/decisions`), and
propose one of their own where they don't like it.
**The voters before.** A decision of voters that a decision on who votes replaced
counts only where that decision's proposal was signed in sight of it decided. So once
others vote, votes of before, kept back or made up with keys stolen later, decide
nothing; and what the voters before decided while the list that replaced them was
voted on, they propose again to those who vote now.
**How.**
1. A voter **proposes**: a statement naming its matter and what is to hold. A matter
is one thing that can be one way only: one number, the rest of the policy, one
user's first keys, one name. The proposals of a matter are numbered: each has, and
states, the number after the highest of its matter that it was signed in sight
of. Any number of proposals are open at a time, on one matter too;
`limits.proposals` of one voter's at most. A proposal is open until it is decided,
its proposer releases it, or one of its matter with a higher number is decided.
2. Voters **vote** for it: each a statement signed by the user, saying when the vote
runs out, `window` from signing unless the user says sooner; a node counts no vote
for longer than `window` from when it first held it. A voter has one vote on a
matter at a time; `release` takes one back, as far as it gets there first: a node
that holds the vote without its release counts it, and a proposal may be decided
with a vote whose release was on its way. A vote is meant when signed.
3. A node that carries for a voter **takes the proposal up** once it holds votes for
it by more than two thirds of all the voters (`fractions.decide`), none released,
each still running by the node's clock, and the proposal says its signer saw all
that the node held `window` before the proposal reached it. It records so, once,
under `_continuum/decisions/<proposal>/<node ID>`. It takes up only a proposal with
a higher number than any of the matter that it took up, or that it holds as taken
up by another node of its voters. Every node judges the record: its history must
hold votes for the proposal by that many voters, none released there. A record
counts for each voter its node carries for, and a voter once, however many of its
nodes record. The node of a voter that is out commits its records and its carry
record all the same, and nothing else, and peers take its changes for that: every
voter has nodes of its own, and nobody's record stands in for another's.
4. The proposal is **decided**, and is a **decision**, once a record of it has in its
history, itself among them, records that count for more than two thirds of all the
voters. Who carried for whom and what the fraction was are read where each record
was written, from its history. That is read from the document, the same by every
node, and never goes away while the epoch lasts.
**At once.** Nothing waits for a vote's days to end. With the votes there, the nodes
take the proposal up as it reaches them, and it is decided as fast as they sync.
**The last holds.** Several proposals of one matter can be open, and voted on, at a
time, and more than one can come to be decided: voters change their minds. Of the
decisions of a matter, the one with the highest number **holds** (across a remake,
those carried over come before those of the new epoch: Remakes). Two with the same
number, made out of each other's sight, are both decided only where the nodes of a
third of the voters took both up, which an honest node doesn't; then the one with the
lower digest holds. A decision closes the proposals of its matter with a lower number:
clients offer no vote on them. A decision that holds is **final** once it has been
seen holding for `final` (Lengths of time): from then on no decision of its matter
holds instead whose proposal wasn't signed in sight of it, whatever its number.
**A node carrying for many.** A record counts for every voter its node carries for.
So a node that carries for a third of the voters, and keeps its records back, holds
up every decision, and chooses the day of those it is needed for. Its voters end
that by naming another node, which commits the `node` statement naming it and
records for them; a voter carried by nodes of two parties depends on neither alone.
Nothing is lost meanwhile: the votes count, with the records of any node the voter
names after. `GET /registry/decisions` shows how many voters each node carries for.
**What hangs.** A proposal that had the votes and is short of records (nodes were
down, or keep theirs back) can still be decided, and whoever holds the last record
chooses the day: a record can be made to look as old as its maker likes, so no rule
ends its time. Two things bound it. A node takes up only what is higher than it took
up, so what is decided late changes what holds only where no proposal with a higher
number was decided since. And it shows: `GET /registry/decisions` has what was taken
up, by whose nodes, and how many it is short of. The voters end it by deciding a later
proposal of the matter, saying the same or something else: that one holds, whatever
comes after.
**Where a decision counts.** A change is judged by the decisions decided in its
history, so one made out of sight of a decision is valid as it was written, and
every node holds it. The registry is resolved by the decisions that hold among all
the changes a node holds: a limit that was lowered leaves out what is past it,
wherever that was signed. Every node acts on the decision that holds, the same from
the same changes, unless it refuses it (Refusing a decision).
**By any node.** A proposal, a vote and their release are taken in any node's change:
the signature is the voter's. So a voter votes at whatever node it reaches, or signs
a vote that someone carries to one. A vote kept back counts while it runs, as its
signer wrote, and no longer. What brings a vote from a person to a node (a client, a
page, paper) is the application's.
**From the past.** Votes kept back until they ran out, or crafted to look old, are
held while they run by no honest node, so nothing takes their proposal up but its
makers' nodes, and their records are judged like any: they need the votes of two
thirds of the voters. With that many keys stolen later, a decision of then is made up,
and holds if it gets the highest number of its matter, until the decision of that
matter that holds is final; the voters decide a later one. Of voters that others
replaced, it decides nothing (The voters before).
The votes are the users' own, signed with their keys, and take the days people take.
Taking up is their nodes', and takes as long as syncing does. One time is compared
across machines: a vote's end, written by the voter's client and read by the nodes'
clocks. A window of days bears clocks that are minutes apart.
**What is decided.**
* **A number**: any number of the policy, the fractions among them, to any value.
Each number is a matter of its own.
* **The policy**, the rest of it, as a whole (The policy changes by a decision).
* **A user's first keys**, for a user that lost them or had them stolen. The proposal
names the user, the first keys it is to have, and a cut for those it has: what
they signed outside the cut doesn't count, as with a key above them (Cuts). The
voters are above every user's first keys. A user that lost its keys comes in again
under another name, so that it has a voice and the voters know whom they give the
name back to. Decided, it signs under its name as before, with its names, its
lines and those it brought in, and releases the other name.
* **A name of a user that is out**, while it waits: each name a matter. The proposal
names the user and the name, and that it is free or who is to have it. A name
freed is anyone's to claim from the decision on; the user's own name freed, the
user is gone. A name given is the user's claim made over: the user the decision
names holds it where that claim was, releases it like its own, and it doesn't
count toward its limit. A user that is vouched for again has back what no decision
dealt with. What another claimed in sight of the claim while it didn't stand (the
user was gone meanwhile) stays the other's, as with anything that comes back.
* **Whose a name is**, where it is contested, by two final claims too. The proposal
names one of its claims: decided, every other claim of the name gives way to it,
final or not, and it is final.
* **A name the rules leave to the voters** (`"{voters}"`): given to a user, who holds
it as by a claim and releases it like one; it doesn't count toward its limit.
Released, it is given anew.
* **Who votes**: the list of voters, by their IDs, one matter. Recommended, as said
above, those who take part.
* **Who the roots are**: their IDs, one matter, and for each root it leaves out which
root has each name a rule gives a root, and which gives the first keys it was named
to give. One that names no root is no proposal: nobody would be in.
A decision stays, whatever is cut off after: a vote signed with a key that is retired
later, from before, stays in it. The days a vote takes are the time to cut a stolen
key off.
### Remakes
A federated swarm remakes as every swarm does ([`remakes.md`](remakes.md)): a node
proposes and coordinates, the alive peers ack, and every node builds the next epoch
itself and switches. Nothing the swarm decides goes through it, and nothing that counts
changes by it: it keeps the document small, and the nodes do it by themselves. What
the federated policy adds is when, what the snapshot holds, what comes along, and which
of two remakes the nodes go to.
* **Compaction only.** A node follows a remake of the kind `compact` alone: `replace`,
`import` and `strict` put content nobody signed, and start a new swarm.
* **When.** A node proposes a remake by itself once the epoch's history holds
`remakeChanges` changes beyond its root change, or its changes started
`remakeWriters` writers, after a random wait, unless one is under way; and acks one
whose proposal has that in its history. It follows only a remake whose base holds
that. So remakes come as the document grows, nobody asking, and no faster, whoever
proposes them.
* **Any base.** The base is the coordinator's heads when it commits, as in every swarm,
and the coordinator may be anyone's node. One that leaves out what others hold, or
is old, loses nothing: every node carries over what it holds beyond the base, with
what it held of it (below). A node that lacks the base syncs it from a peer that
keeps the epoch.
* **By its result.** Every node builds the snapshot itself from the base, and follows
only where it gets the epoch ID the remake was committed for (Continuum changing
under a swarm).
* **Two remakes of one epoch**, both committed: every node goes to the one with the
lower ID, a node in the other moving to it as one that comes back does (Coming back
after remakes), with what it holds there. No count of nodes decides, which a party
running many nodes would have.
* **The snapshot holds** the registry as it resolves at the base, and with it whatever
something signed later could still change:
* the policy that holds, with its numbers, and the decision that holds of each
matter, with its number and digest, and whether it is final;
* the users that count, and those out and not gone, each with its name (or that it
is contested, and with which), ID, keys, nodes, and who created and who vouches
for it, or that it is in by the seats;
* every statement and value that counts, as the envelope it is, with its signature;
* what doesn't count and could still come to: what was given up, replaced, left out
by a cut or past a limit, and hasn't stopped counting for good (Cuts), each as its
envelope, with what stopped it;
* what the order among claims rests on (creations among them, and a root's for a
user the root change holds): which claim gives way to which, which is late against
which, which is settled and which final, which statements count through an unvouch
or a cut; and for each claim not yet settled, the users whose nodes had it
standing in a change they committed;
* how far each length of time has run: for each thing being seen (a user out, a
claim holding its name, a decision holding, a thing uncovered), each node of a
voter with its first stamp, and that stamp's time, from which it has held the
thing so without a break;
* what is uncovered and not dropped;
* the proposals that are open, with their votes;
* the member entries of the nodes that carry for a user it holds, and the epochs'
metadata, as today;
* the digests of the envelopes the base holds that were signed in the epoch it
leaves.
* **What it leaves out**: the history, and what can never count again: a user gone;
what stopped counting for good, and the release, stop or unvouch that gave it up; a
proposal decided or closed, with its votes and the nodes' records. So after a remake
the document's size goes by what stands (users, their keys and nodes, names held,
values, members) and by what stopped counting within the last `final`, and for one
epoch by 32 bytes for each envelope signed in the one before; not by what ever
happened. Within an epoch nothing is removed: a release is a statement like any
other, signed, and a document keeps its history. The remake is what deletes.
* **Nothing it left out comes back.** An envelope is taken in the epoch it names and,
carried over, in the next. So that what the base held and the remake left out (a
stolen laptop's key and node, retired long since) can't be handed in again as signed
in the epoch before, the root change lists the digests of the envelopes the base
held that were signed there, and an envelope among them is refused. The epoch after
drops the list.
* **Carried over.** A node that switches first catches up with the peers it keeps in
the epoch it leaves, as a node that comes back does. Then, before it takes anything
in the new epoch, it commits its **carry record**, every node that switches, whoever
it carries for (out voters too), `_continuum/carried/<node ID>`: the digests of the
envelopes it holds that the base lacks, whoever signed them (statements, values,
proposals, votes and their releases), and what it held of them and of what the
snapshot holds: which claim it held as late against which, or as giving way to
which; which statements of a user since unvouched, or whose creation or vouch was
cut off, count through the unvouch or the cut; and which lengths of time, of those
the snapshot lists for the node, it saw broken after the base. One record a node and
epoch, of digests and of what the node held. Nothing tells it from a later change of
the node, and nothing has to: it witnesses by what it names, not by when it was
committed. A node that came to carry after the base commits, with its record, the
`node` statement that named it (rule 2).
* **Then the envelopes, once.** After its record the node takes from its peers, and
writes again, as they are, the envelopes its record names that the epoch doesn't
hold yet. Any node commits an envelope of the epoch before, as it commits any (a
`node` statement only the node it names). It is taken as it is signed, and never
refused for what stands in the new epoch: whether it counts is resolved. So an
envelope comes into the new epoch about once, and what each node witnessed comes as
32 bytes a node.
* **A carry record witnesses** as the node's changes did in the epoch before: as a
change with what it names in its history, standing or not as it says. Against a
claim, where a node of that claim's side committed it; for an unvouch, or a vouch or
a creation cut off, where a node of its signer or of a root did. So a claim that
turns up later as signed in the epoch before is late against what a root's node's
record names, and nothing rests on the order a node writes in.
* **Carried over, and held by the snapshot.** What a claim carried over says its
signer saw isn't there to look at, so it and a claim the snapshot holds are ordered
as two claims out of each other's sight: by the carry records, and by what the
snapshot says of the one it holds. A claim settled at the base has every claim
carried over late against it; one not yet settled, those of the users whose nodes
the snapshot lists as having had it standing.
* **Its order and its numbers.** Of a user's statements of one kind, and of the
proposals of a matter, those the snapshot holds come first, then those carried
over, by the numbers they state, then those signed in the new epoch. So a number
nobody could check (a statement signed after the switch as of the epoch before)
orders nothing but its own signer's statements among themselves, and a proposal
carried over never outranks one of the new epoch.
* **Its values.** A value carried over counts while no value its user signed in the
new epoch is at its place: whoever writes in the new epoch has the last word over
what the epoch before held, seen or not. Of several carried over to one place,
one that another replaces is left out (Resolving).
* **A cut carried over** is the list its statement carries (Cuts).
* **Decisions after the base** aren't in the snapshot. Their proposals and votes are
carried over, and a node that held one decided takes it up again in the new epoch,
whether its votes still run or not: it is decided there once the nodes of two thirds
of the voters switched. Until then the registry resolves without it, and what is
signed meanwhile with a key the decision cut off is outside that cut once it holds
again.
* **Lengths of time go on.** A node's stamps in the new epoch continue the one the
snapshot lists for it: a thing it held so there and at a stamp in the new epoch has
been so all the while, unless its carry record says it saw the thing broken after
the base. What its stamps in the epoch before showed after the base is read no other
way.
* **A node that was away** comes back as said below (Coming back after remakes).
* **A node that joins** is given a root change to start from, by whoever brings its
user in: the genesis change, or the ID of a later epoch.
**What a remake changes**, then, is nothing that counts, but for what it can't carry:
an envelope signed two epochs back comes no more (Coming back after remakes); what only
a node witnessed after the base, and named in no carry record because it never
switched and doesn't come back, is lost with it; a decision decided after the base
waits in the new epoch for the nodes of two thirds of the voters to take it up again.
Who remakes, when, and from what base changes none of it: that is why the alive peers
decide it, of whom a party running many nodes can be most.
What a remake bounds, and what everything costs, is said below (What it costs).
### Coming back after remakes
A node that was away holds an epoch the swarm left, one remake back or several. Its
peers name their epoch in the handshake and don't sync with it; `GET /admin/epochs`
shows the epochs they name, and which of them the roots' nodes are in. A federated
node never rejoins because peers advertise an epoch, however many do. It gets there
in one of two ways:
1. **By the archives, on nobody's word.** A peer answers for an epoch it left as long
as it keeps that epoch's document: `archiveRetention` at least, longer if its
operator says, and every epoch on a node kept as an archive. Peers say in the
handshake which epochs they keep. From such a peer the node syncs the rest of the
epoch it is in, judging every change; sees the remake committed (of two, the one
with the lower ID); builds the snapshot itself; and is in the next epoch, whose ID
is the snapshot's hash. So on, epoch by epoch, as far as peers keep them: with an
archive within reach, from any epoch to the swarm's, and for a node that joins,
from the genesis change. Where the walk ends short of the epoch the node's peers
are in (an archive can keep a remake's commit back), the node stops and shows it,
for its operator to give it the ID (below). Keeping an archive is an application's;
continuum answers for what a node keeps.
2. **By an ID, on its operator's word.** Where no peer keeps the epoch any more, the
node can't check how the swarm got from there to here. Its operator gives it the
ID of the epoch to go to (`POST /admin/epochs/rejoin`), from a party it trusts:
as when the node first joined, whoever brought its user in. The node rejoins as
today: it downloads that epoch's snapshot from any peer, checked against the ID,
and syncs what was written since.
Either way, what follows:
* **What it holds and the swarm never got.** What was signed in the epoch just before
the one the node arrives in is carried over: the node commits its carry record
when it arrives, and writes again what the epoch lacks. What was
signed further back isn't: an envelope is taken in its epoch and the next, no
later. Its own user's go to the quarantine, and the client lists them for the
user to sign again. A claim signed again is a new claim, after what was claimed
since.
* **What it finds of its user**, as the snapshot has it. There, with its keys, nodes
and names: the node carries for it as before, and writes its member entry anew. Or
out, its names waiting. Or gone, and so not in the snapshot: then no node takes the
node's changes, it shows why, and its user comes in again as anyone does.
* **As a voter or a root** the user is what the decisions that hold there name it.
* **Its old document** goes to the archive, as today.
A node in the other of two remakes of one epoch moves the same way, to the one with
the lower ID: it holds the epoch both came from, builds the snapshot from that base,
and carries over what it holds, envelopes signed in the epoch it leaves among them
(What every node judges). To any other epoch a node moves only by its operator's word
(`POST /admin/epochs/rejoin`, `POST /admin/fork`).
### The policy changes by a decision
The policy but for its numbers is one matter. A proposal carries it whole: the
version, the kinds with their rules, `userSigned`. As with every decision, a change
is judged by the policy decided in its history, and the registry is resolved by the
one that holds. No remake comes with it. A remake throws history away, a change of
policy changes the rules, and neither needs the other.
* **A policy a node doesn't know.** A node knows a policy if it knows everything in
it (Continuum changing under a swarm). One that doesn't can't take the proposal
up, so a policy is decided only once nodes of two thirds of the voters know it. A
node that doesn't know a policy that holds stops syncing, as under any policy it
doesn't know, says why, and goes on once it is upgraded. Or its operator refuses
the decision (below).
* **What the policy no longer covers** is **uncovered** where the decision holds: a
claim that no rule lets its user make any more (the kind is gone, or the rule, or
the name is now kept for another or left to the voters), a name a decision gave
that the rules no longer leave to the voters, a value at a path `userSigned` no
longer lists. It doesn't count. Every node shows it aside, under
`_continuum/uncovered/<user>/` at the path it had, and no longer where it was.
* **A kept name has no claim behind it.** Where a policy stops keeping a name for its
user and lets anyone claim it, it is the first comer's at once, unless its user
claimed it before: that claim stands like any other.
* **Only its user takes it away**, and nobody changes it: a value by an envelope
that puts nothing in its place (`null`), a claim by its `release`. Each names the
path the thing had. Nothing else is written there.
* **For as long as `uncovered` says.** Once it has been seen uncovered for that long
(Lengths of time) it is **dropped**: no node shows it any more, and nothing brings
it back. At 0 it is dropped at once. Until then, a later policy that covers it
again has it count again, where it was.
* **Where it is.** Within an epoch a rule moves nothing: a move is a change someone
has to write, and every node would have to write the same one. So what is
uncovered stays in the document where it was written, shown aside by every node
while the policy that holds doesn't cover it. A remake moves it: the snapshot
holds what is uncovered and not dropped under `_continuum/uncovered/<user>/`, and
leaves out what was dropped. Where a later policy covers it again, every node
shows it where it was, and the remake after puts it back.
* **Whole, not merged.** Two proposals of a policy are two policies, and the later
holds: what one changed isn't worked into the other.
### Going apart: a fork by choice
Whoever the swarm's decisions leave behind goes on apart, with those who want the
same: with an only root that went before it decided on others, with a third of the
voters gone so that nothing is decided, with two thirds of them turned against the
rest, or for a policy the others won't have. A fork is proposed, and binds nobody:
* Any user proposes it, one at a time: the policy to go on with (the one that
holds, or another), and, if it likes, who votes there and who the roots are.
Where it names none, they are as they hold. Voters may vote for it: that shows
who would go, and decides nothing.
* The proposer's node names the base in its record of the proposal, when its user says
so, votes or none.
* A node follows if its operator says so (`POST /admin/fork`, naming the proposal and
the base): it builds the snapshot at the base with what the proposal says, carries
over what it holds beyond the base, and goes on in that epoch. A node that doesn't
stays in the epoch it is in, which goes on as it was.
* Both sides have the same history up to the base and the same swarm ID, and from
there different epochs. Their nodes don't sync, and leave each other out as
neighbours. A statement signed on one side counts for nothing on the other: it
names its epoch. What was signed in the epoch both came from counts on both, and
a node carries for its user on a side only by writing there.
* On each side the voters are those its decisions name, the ones that went the other
way among them. A side that keeps two thirds of them decides on those who stayed. A
side with fewer decides nothing until it names its own, by a fork of its own.
It moves nobody, and takes nothing along but the history: each party chooses its
side.
### Refusing a decision
A decision binds the nodes that follow it, and no node has to. By default a node
follows every decision. Its operator has it refuse:
* **By bounds** (`--bounds`, a file; `GET` and `PUT /admin/bounds`): for any number of
the policy, the least and the most the node goes along with. A decision that
holds and sets a number outside them is refused. Bounds that the policy breaks as
the node starts with them refuse nothing: the node shows them.
* **By hand** (`POST /admin/decisions/refuse`, naming the proposal): any decision of
the epoch the node is in.
What refusing does:
* **Before.** While a proposal's votes run, a node whose bounds it breaks says so in
its member entry (`refuses`), so the voters see who would go
(`GET /registry/decisions`).
* **The epoch without it.** A node that refuses a decision moves to the epoch built
where its proposal was signed (at the changes the proposal says its signer saw,
which no honest node took it up without holding all it had held `window`
before):
the registry as it resolves there, the policy, the voters and the roots as they
are there, and the digest of the proposal refused, which makes it no other epoch
and no proposal there. Every node that refuses the same decision builds the same
epoch, whenever it does. So those who think alike meet there without arranging
it.
* **What it takes along.** As with a remake, the node carries over what it holds
beyond that base, decisions among it but the one refused. So refusing costs what
a remake costs whose base is a window older than the proposal was taken up, and
however long the decision hung after.
* **After**, as after any fork: the same swarm ID and the same history up to the base,
different epochs, no syncing between them. On each side the voters are those its
decisions name, and a side with too few of them names its own, by a fork. A node
moves to the other side by its operator's word.
So every number is the swarm's to set, and each party's to bear or not. A decision
that lets one voter decide for all is followed by those who don't mind.
This is how Bitcoin changes its rules. Nobody decides for anyone: nodes run the rules
their operators chose. A change comes into force once enough of those who count
signal that they run it, at a height named beforehand. Nodes that won't have it keep
their rules, and with them their chain, the same up to there. And a transaction that
would count on both chains is kept to one by naming its chain. Here the signalling is
the nodes taking a proposal up, which takes knowing its policy; refusing is keeping
one's rules; the height is the base; and the epoch in every envelope keeps a
statement on its side.
### What each payload holds
The fields each rule reads; a version adds none that a rule reads without a policy
saying so (Continuum changing under a swarm). Names of fields are the design's, the
encoding the first stage's.
**Every envelope** (a statement): `swarm` (the swarm's ID), `epoch` (the epoch it is
signed in), `path` (its register, under its own digest), `kind`, `userId` (its
signer's ID; a `create`'s signer is the creator), `seen` (the hashes of the changes
its signer had seen), `number` (the number of its kind among its user's statements:
Users), `signingKey` (the public key that signs) and the signature, over all the rest.
Beside those, by kind:
| Kind | Fields |
|---|---|
| `create` | `name`, `keys` (the first keys, public); a root's, for a user the root change holds: `for`, its ID there |
| `vouch` | `for`, the ID of the user vouched for |
| `unvouch` | `of`, the digest of the `create` or `vouch` taken back; or `for`, the ID of a user the root change holds without a creator, which the roots take back together |
| `key` | `added`, the key added (the signing key is above it) |
| `retire` | `retired`, the key retired; `cut`, change hashes; `keeps`, the digests it keeps (Cuts) |
| `node` | `node`, the node's ID; a stop: `stop`, with `cut` and `keeps` |
| `release` | `of`, the digest of the claim, vote or proposal given up (with a claim, the user's others of that name: Two claims); or `claimKind` and `name`, a name a decision gave or made over; or `self`, the user giving itself up (signed with a first key) |
| `claim` | `claimKind` and `name` |
| `propose` | `matter`, `holds` (below), `matterNumber` (its number among its matter's proposals: Decisions) |
| `vote` | `proposal`, its digest; `ends`, when it runs out |
**A value's envelope**: `swarm`, `epoch`, `path` (its place), `userId`, `signingKey`,
`prev` (the digest of a value that counts at its place where it is signed, or none),
the value (or `null`, putting nothing there), and the signature. It says nothing of
what its signer saw: where a value was signed, wherever a rule asks, is the change
that carries it.
A proposal's `matter` and what it `holds`:
| Matter | `holds` |
|---|---|
| `number`, naming it | the value |
| `policy` | the rest of the policy, whole |
| `firstKeys`, naming the user | the keys, and a `cut` with its `keeps` for those it has |
| `name`, naming an out user, a kind and a name | free, or the user ID it is given to |
| `whose`, naming a kind and a name | the digest of the claim that is to hold it |
| `votersName`, naming a kind and a name | the user ID it is given to |
| `voters` | the voters' IDs |
| `roots` | the roots' IDs, and for each root left out which root has each name a rule gives it and which gives the first keys it was named to give |
| `fork` | the policy to go on with, and, if it likes, `voters` and `roots` |
A fork is no matter: a vote for one counts toward nothing, shows who would go, and
leaves a voter's one vote a matter alone.
**What a node writes plain**, each signed by the change it is in, as a node's change
is:
* **A record of a proposal**, `_continuum/decisions/<proposal>/<node ID>`: `proposal`;
of a fork, `base`, the proposer's node.
* **A carry record**, `_continuum/carried/<node ID>`: `from` (the epoch it left),
`digests` (of the envelopes it holds that the base lacks), and what it held of them
and of what the snapshot holds: `late` and `givesWay` (pairs of claims' digests),
`through` (statements that count through an unvouch or a cut: their digests),
`broken` (lengths of time the snapshot lists for the node that it saw broken after
the base).
* **A member entry**, of the shape its policy's version gives it, within
`limits.entry`: what it is today (its addresses, what it reaches, whether it is
ready, its alive stamp), `writersFor` (the user its writers count for: Users),
`refuses` (the open proposals whose decision its bounds would refuse: Refusing a
decision) and `digest` (the registry as it resolves at the change's dependencies:
Continuum changing under a swarm).
### What every node judges
A change is first of all one that Automerge itself writes, or it is refused before
Automerge sees it, in every swarm *(checked: `document::changes::Written`)*: its bytes
are the ones Automerge encodes for it; its first operation is numbered one after the
highest of its dependencies; it is its actor's first, or builds on the one before;
every operation it names was made in its history and is what it is named as (the
object written into, the element of that list, a value or an object at that place);
and every operation is one Automerge's transactions write, but for tables and marks,
which continuum doesn't write and are refused too *(checked, and generated:
`what_passes_leaves_automerge_sound`)*. Automerge 0.12 applies changes that are none
of these, and then panics, saves a document that doesn't load, or holds another change
than it was given *(measured upstream)*. All of it is asked of the change and its
history, as the rules are.
A change is valid if, in the document at its dependencies:
1. It has no dependencies and is the root change the node was given (the genesis
change, or the epoch's snapshot). Else:
2. Its committer is a node that carries for a user there, one that isn't out and
hasn't stopped there, proven by the node's signature. Or the change is the one by
which a node comes to carry: it holds a `node` statement naming its committer, by a
user that isn't out there, the committer's member entry and, after a remake, its
carry record, and nothing else. Or it holds nothing but the committer's own record
of a proposal, or its carry record, and the committer carries for a voter that is
out there.
3. Apart from the node's own member entry (of the shape the policy's version gives it,
within `limits.entry`), its own records of proposals, its carry record, and what it
writes of a remake as in every swarm (its ack; a coordinator's proposal and
decision, of the kind `compact`), it writes only envelopes, each naming the swarm,
its epoch, its path and its user's ID, and for a statement what its signer saw
(`seen`, changes in this change's history) and, where statements of its kind are
numbered, the number that gives it, signed with a key that is that user's there and
not retired there. Any node commits it, but a `node` statement, which the node it
names does.
4. In a register (`_continuum/users/<name>`, `_continuum/claims/<kind>/<name>`): only
a new entry under its own digest. Under `_continuum/decisions/<proposal>`: only the
node's own record, once, of a proposal that is there: of a fork, its proposer's
node's own, naming the base, without votes; of any other, with votes for it in the
change's history by more than `fractions.decide` of the voters, none released
there. Under `_continuum/carried`: only the node's own carry record, once an epoch.
Nothing replaced, nothing deleted, nor anything that holds a register.
5. A `create`: its name is one the kind `user` takes, and neither a creation of it nor
a user's claim of it as its own name stands there, a rule of the kind lets the
signer, and the signer isn't past its limit there; or it is by the root named to
give a user the root change holds its first keys, for that user, which has none
there. `key`, `node`, `vouch`: not past their limits there; a `vouch` for a user
that isn't gone there. `unvouch`: by the signer of what it takes back, or by a root
for what is the seats'. `retire`, a node stopping: by a key above, or by the key
itself as said under Cuts, the cut in the change's history, and its list what the
key signed within it. `release`: by the user of what it releases; of the user
itself, with a first key; never of a root's `create` for a user the root change
holds.
6. A `claim`: of the kind `user`, only by the user of that name, of its own name,
while no claim of its own of it stands there, where a rule of the kind lets the
user create that name. Else the kind is declared, the name is one of it, a rule
lets the signer, the signer isn't past the kind's limit there, and no claim of that
name stands there. One that doesn't count there doesn't stand there.
7. In a namespace: at a listed depth, an envelope by a user of that name, replacing
what is there (`prev` naming one of the values that count there, where several do);
nothing within one, nothing replacing what holds one. At a place the policy no
longer covers: only its user's envelope that puts nothing there.
8. `propose`, `vote`: by a voter, with a key the document has for it (a fork: proposed
by any user that isn't gone there); a proposal not past its user's limit there (a
fork: the only one of its user that is open); a vote where the user has none on
that matter that isn't released.
9. `_continuum/access`, the swarm ID, the epochs, and what the root change sets for
the swarm as a whole: never.
**What is carried over**: an envelope naming the epoch before this one, or another
remake of that epoch, is held to less. Any node commits it, as any envelope (a `node`
statement only the node it names). What it says its signer saw isn't looked at, and
its number orders only among what is carried over. Of 5 to 8 only what the envelope
itself shows is asked: its signature by a key that is its user's there, its register,
for a value that its `prev` is a value the snapshot or another carried over holds
there, and that the root change doesn't list its digest. Whether it counts is
resolved.
Where a rule goes by a user's name (6, 7) and the name has several creations there, a
user that lost it, as far as the change's history shows (another remains, Two claims),
is refused; while none remains, each of them may write. So a user whose late creation
of a name is known can't scribble over the namespace, and one whose name a liar got
contested goes on writing, for those who leave the liar out to read.
Judging reads the registers at the change's dependencies, and nothing else: no cut is
applied beyond a retiring or an unvouch that is there; who is gone is as the stamps
there show; and the policy with its numbers, the first keys and the names freed or
given are as the decisions decided there leave them. A statement in a register was
valid when it was taken, so judging the next needs no look further back.
### Resolving
The **resolved registry** is a function of a set of changes that holds each change's
history. In five steps, each reading only
the steps before:
1. **Decisions.** Which proposals are decided, and which decision of each matter
holds (Decisions): the policy with its numbers, the first keys given, the names
freed, given or said to be someone's. A record is read where it was written: who
carried for whom, and the fraction, are as its own history has them, so this goes
back along the history and ends, and nothing below changes it.
2. **Who counts, and where.** The roots count, by their seats; a user the root change
holds without a creator is in by the seats. A user counts at a statement through a
`create` or `vouch` for it whose signer counts there by a line that doesn't pass
through the user (so this ends), where the statement is within what every `unvouch`
of that one leaves and, where that one is outside a cut, what the statement that
set the cut leaves, as an unvouch would (Cuts); what is the seats' is taken back
once every root unvouched it. A statement counts if its user counts at it (a
proposal and a vote: always, for a voter); its key was the user's where the
statement was signed (added by statements that count, up to its creation, which
gives its first keys whether or not it counts as a vouch; for a user the root
change holds, by the creation of its root that remains over all the changes, its
creations ordered by the other roots' nodes alone, and none while two contest; or
given by a decision); it is within every cut set for that key (by a `retire` that
counts, or a decision; a key's own retirement leaves in what a node of its user or
of a root had seen without it); and it isn't past its limit (Users), by the limit
that holds. A `retire`, a stop and an `unvouch` are never outside a cut they set
themselves. A user is **out** where it counts through no `create` or `vouch` any
more, or where it gave itself up. It is **gone** once seen out for `gone`, or where
a decision freed its name; and gone it stays, whatever is vouched or cut off after.
What stopped counting for good (Cuts) counts no more, whatever comes after.
3. **Users' names.** A creation stands while it counts, isn't released, its user isn't
gone, and a rule of the kind `user` lets its signer; a user's claim of its own name
stands with it, and on where the creation doesn't. Of what stands for a name: the
one that remains (Two claims, as in step 4) has the name, or has it wait while it
is out. Of the creations its root signed for a user the root change holds, the one
that remains gives its keys (read in step 2).
4. **Names.** A claim stands the same way, where a rule of the policy that holds lets
its user: anyone who isn't gone where the rule says `"*"`, a root where it says
`"{root}"`, else the user that has the name the rule gives; and a name the voters
gave stands as its decision says while the rule says `"{voters}"`. A claim that is
late against another, and not the other against it, doesn't stand. For each two
claims of a name that stand, one question is asked, the first that fits:
* one named by the decision that holds on whose the name is: the other gives way;
* both final: neither gives way, and they contest each other;
* one final: the other gives way;
* one carried over, the other held by the snapshot: as neither in sight of the
other, the snapshot saying whose nodes had the one it holds standing (Remakes);
* one signed in sight of the other: it gives way if the other stood where it was
signed, or is read as never down (Claims); else, where the other didn't stand
there only by an unvouch or a cut, as neither in sight of the other (the next
question), with the roots' nodes alone as witnesses of which is late (Claims);
else the other gives way;
* neither in sight of the other: each stands, late against the other or not.
Those that give way to none remain: one, and its user holds the name, or has it
wait while it is out; else the name is contested. A kept name is held by the user
that has the user name.
5. **Values.** A value in a namespace counts if its envelope does and its user has the
name. A value carried over is left out where its user signed one in the new epoch
at that place. Where the document holds several at one place (written at once,
or carried over by nodes that held different ones), one that another there
replaces, directly or along `prev`, is left out; of the rest, those that count,
in Automerge's order. Where the one there doesn't count, the last that does, back
along `prev` (read in the document at the dependencies of the change that
replaced it).
A node keeps the resolved registry as it goes (a statement changes it around its own
name), and answers from it:
* `GET /registry/users/<name>`: the user that has the name, its keys and nodes, who
created it and who vouches for it; or that it is contested, between whom; or out,
since where, and how long its names still wait; or gone. Also what is in the open:
which root's node keeps it in past an unvouch or a cut by a witness the signer's own
nodes didn't make, and, for a user the root change holds, whether its root's
creations contest its first keys.
* `GET /registry/claims/<kind>/<name>`: the holder, and whether the claim is settled,
and final; held "while a release, a cut, an unvouch or statements past a limit
stand" where it was made in sight of a claim that one could bring back or a root's
node could still witness, and isn't final; or contested, between whom, with the
changes that make each claim late and whose nodes committed them. A user whose nodes
showed both orders of two claims is marked, a root too: it lied, or its nodes were
apart.
* `GET /registry/decisions`: the roots, the voters, the policy and its numbers; what
is proposed, with its number, who voted, until when, whose nodes took it up, how
many it is short of, and which nodes would refuse it; what is decided, which
decision of each matter holds, what hangs, and what this node refuses.
* `GET /registry/uncovered/<user>`: what a policy no longer covers of that user's,
at the path it had, and how long it still stays.
* `GET /store`, as today, with a value that doesn't count marked, and the one that
counts in its place.
### Partitions, and coming back
Three things are "conflicting data", and are dealt with apart.
**Names claimed twice** are no partition: every node holds both claims and finds the
same holder, or contested. The users see it and one releases; nobody drops anything.
**Two epochs**, after a fork or a decision some refuse, are apart for good: each node
is where its operator put it (by word or by bounds), and moves to the other side by
being told to (it builds that side's snapshot from the base it holds, and carries over
what it holds). Two remakes of one epoch both committed are no such thing: every node
goes to the one with the lower ID (Remakes).
**Changes one side refuses** are a partition nobody chose. A node is cut off from the
others when it holds a change they refuse, as everything it writes after builds on
it. That happens by three things, and each shows:
* **Its own node broke a rule**, by a bug or on purpose. The others refuse the change
and, its signature proving it its own, the node as a whole: `GET /peers` (`refused`,
with the change and why), the dashboard, `sync.refusedPeers` *(docs)*.
* **The two sides judge differently**: versions that differ, a bug in a rule. Each
refuses what the other takes; a node told so judges what it holds again and logs
that the policies disagree *(docs)*. Where they only resolve differently, their
stamps show it (Continuum changing under a swarm).
* **An actor forked.** A node committed two changes under one actor and number and
gave each to some. Automerge holds one change per actor and number, so a node
holding one can't take the other, nor anything built on it *(checked upstream)*.
Both carry the same node's signature: a node offered the second holds proof, shows
it, and refuses the forking node from then on. (Today it refuses the second as
forged, by whoever brought it *(checked: `document::signatures`)*.)
Coming back is the side's own choice, never forced: an operator has the node **drop**
what the others refuse (`POST /admin/refused/drop`, naming the peer whose word it
takes). The node's document becomes what it would be without those changes and what
was built on them, as a drop does today *(checked: `AppState::drop_taken`)*. The
envelopes among them go to the quarantine and are written again as they are: an
envelope doesn't name the change that carried it, so it is as valid in a new one
that has in its history what its signer saw. Those that no longer fit stay there
for the user to sign again: one replacing a value that is gone, or naming a change
that was dropped.
Which side drops, for a fork of an actor? No rule can say: the forking node may have
ground the hash of the change it kept back, and a rule by hash would let it make
everyone drop a year's work. A node shows which of the two the roots' nodes hold,
and the operator follows them or doesn't. A node that just joined and got the lone
change from the forking node drops and loses nothing.
A side that doesn't want to come back stays as it is: the same swarm ID, another
history.
### Reaching the others
A node's neighbours come from the member list: a ring by key hash, and the pairs with
the lowest scores *(checked: `swarm::topology`)*. An adversary choosing its node keys
places its nodes around a victim, and then holds back what the victim writes, or what
it should receive: a claim that never reaches a root is never settled.
Who vouched for whom changes nothing in who connects to whom: a user's nodes needn't
reach its creator's. What a federated node has against being surrounded is its
operator's:
* it keeps as neighbours the other nodes of its user, and its seeds, whatever the
member list gives, and leaves out members that name another epoch;
* it shows what would tell: a claim of its user that isn't settled long after
`witness`, and how old the last change of the roots' nodes is that it holds.
Being surrounded costs time, not names: a claim that reached nobody is out of the
others' sight, and is contested or late like any such.
A member's entry is its node's own, and stays in the document for the epoch. A remake
takes along those of the nodes that carry for a user it holds.
### The API, tokens, reading
* **Writing** through a node is handing it envelopes: it commits them, anyone's,
judged before they leave, as today. `scripts/continuum-signed` signs them, votes
among them. Whether a node takes proposals and votes from someone who isn't logged
in (a page to vote from) is its operator's to say.
* **A node's API users** (`--htpasswd`, a proxy's header) are its party's: they read,
and use the node's admin endpoints. The registry gives nobody anything on another
party's node: a name of the node's own is the node's, whoever has that name in
the registry.
* **Whom a node lets in**, and what it lets them do, is its operator's. Having keys
in the registry gives a user nothing on anyone's node by itself. (Today a user
with keys in the registry logs in on any node *(docs)*.) What a user may write is
in its signature, whatever node it reaches.
* **Tokens** are taken only from the node itself and from the nodes its operator names
(`--token-nodes`, their node IDs): its party's others. (Today every node takes a
token any member signed *(docs)*: a party's node could let itself in anywhere.)
Ended sessions are each node's, as in a swarm without a registry.
* **Reading**: every party reads everything. The registry holds public keys, names
and addresses, nothing secret; a value only some should read is sealed for them, as
today.
* **What an operator says**, on its own node and nowhere else, each shown where the
node waits on it (`GET /admin/epochs`, the dashboard):
* `POST /admin/epochs/rejoin`, naming an epoch's ID: go there, where no peer keeps
the epochs between, or keeps them back (Coming back after remakes).
* `POST /admin/fork`, naming a fork's proposal and its base (Going apart).
* `POST /admin/decisions/refuse`, naming a proposal; `GET` and `PUT /admin/bounds`
(Refusing a decision).
* `POST /admin/refused/drop`, naming the peer whose word it takes (Partitions).
* `POST /admin/check/accept`: write again after a check of itself that differed
(Continuum changing under a swarm).
* `GET /admin/put-off`: what the node put off, by user; `POST /admin/put-off/take`,
naming a user: take what was put off for the writers past its limit (Users).
* **Who may connect** is outside this design. Today it is the swarm key, a secret all
nodes share: it keeps those who aren't parties from connecting and reading, as far
as every party keeps it, and is no boundary between the parties. Nothing here
rests on it.
### What it costs
What every node pays, per thing: in memory, on disk, on the wire and in time. Measured
where it says so; else from the design's own numbers. Automerge 0.12.0 holds a
document of small writes at about 0.2 KB of heap a change, its bytes besides, and 4
bytes for every change and writer of the epoch, whenever the writer started
*(measured upstream)*: the heap goes by changes × (0.2 KB + 4 B × writers), and both
factors grow with the epoch.
| What | What it costs every node |
|---|---|
| a change | its bytes, on disk and once on the wire; in memory 0.2 KB and its bytes, and 4 B for every writer of the epoch; when it was received, kept beside it |
| a writer | 4 B of heap for every change of the epoch, those before it too; a signature in every transfer of the whole history |
| a statement | under a KiB; 32 B in the next root change's list where it was signed in the epoch before, in each retirement's list that keeps it, in each carry record that names it |
| a value | its envelope, a few hundred bytes for a host; kept replaced while not stopped counting for good |
| a node | its member entry, `limits.entry` at most; a stamp each `stamp`, some 350 B; a writer a run; a record a proposal it takes up; a carry record a remake |
| a user at its limits | some 470 statements standing (keys, nodes, users created, vouches, proposals, a kind's claims), under half a MiB, and `limits.writers` writers |
| a claim | its statement; while it has a rival, what each witness had seen, kept as the node goes; until it is final, a length watched for each voter's node |
| a cut | 32 B for each statement and value it keeps |
| a root's node | a change a `witness` at most while claims reach it |
| a remake | the snapshot built by every node, the registry gone over once; 32 B in the root change for each envelope signed in the epoch left; a carry record a node, 32 B for each envelope beyond the base it holds; each such envelope written once more; the epoch left, on disk for `archiveRetention` |
| a signature | some 30 µs to check *(docs)* |
What bounds it:
* **Changes.** Stamps: nodes × days, at the recommended `stamp`. What users sign: what
stands by each user's limits, and what is signed and given up without end by each
party's budget at every node. A root's node's witness: one change a `witness`, 1 440
a day with a minute, whatever the parties do. An epoch: `remakeChanges`.
* **Writers.** A user's by `limits.writers`, a party's by its budget, an epoch's by
`remakeWriters`. With them, an epoch's heap stays under 10 000 × (0.2 KB + 4 B ×
1 000), some 42 MB, on every node.
* **What it doesn't bound.** What reaches a node within others' histories (statements
past a limit, writers past theirs, a change that holds a million operations) is held
until a remake; a remake of an epoch, and every other a party commits of it, costs
every node a snapshot (what is not promised).
What was measured, for a year of a hundred nodes stamping daily (36 500 changes): 23
MB of heap where the nodes keep their writers, 112 MB where each starts one every 90
days, 832 MB where each starts one a week, 491 MB with a writer for every change; one
user's 1 024 writers beside them, 143 MB more *(measured upstream)*. The remake numbers
recommended keep an epoch well below the second.
What is assumed cheap, and is to be measured as it is built (What was checked):
judging a change that says it saw little, resolving as the node goes, the digest with
every stamp, the lengths watched, the snapshot at a registry's size.
For the registry: a hundred nodes and a few thousand hosts make statements and values
of some MB, and a snapshot of as much; their stamps alone fill `remakeChanges` in about
a hundred days, and a remake follows.
### What to watch, and when to act
Each signal shows at the endpoint named and as a metric beside it, with the threshold
the design recommends; who acts, and how. A node shows each where it waits on it
(`GET /admin/epochs`, the dashboard).
**A node's operator:**
| Signal | Act when | What to do |
|---|---|---|
| the epoch's changes × writers × 4 B, beside the node's memory | over a quarter of it | ask the voters for lower `remakeChanges` or `remakeWriters`, or give the node memory |
| the writers of a user the node carries for (`GET /registry/users`) | half of `limits.writers` | find the node that restarts in a loop |
| what the node put off, by user (`GET /admin/put-off`) | anything | take it (`POST /admin/put-off/take`), or leave it to the next remake |
| what waits by a party's budget, by party | waiting an hour | a party that writes without end, or a budget too small |
| a claim of a user the node carries for, not settled (`GET /registry/claims`) | ten times `witness` | its neighbours and seeds; the roots' nodes' last change |
| the age of the last change of the roots' nodes the node holds | twice `stamp` | its seeds; tell the roots |
| peers in another epoch (`GET /peers`) | longer than a switch delay and `catchUp` | a peer that keeps the epoch, or the ID (`POST /admin/epochs/rejoin`) |
| a committed remake whose ID the node doesn't get | at once | versions differ: upgrade, or report it |
| a refused peer, a forked actor proven (`GET /peers`, `sync.refusedPeers`) | at once | drop (`POST /admin/refused/drop`), or not |
| two digests for the same changes; a check of itself that differed | at once | upgrade, or write on (`POST /admin/check/accept`) |
| a policy the node doesn't know | at once | upgrade, or refuse the decision |
| a proposal its bounds would refuse, or a policy that breaks them (`GET /registry/decisions`) | while the votes run | tell the voters; refuse it when decided, or change the bounds |
**A user**, through a node it trusts:
| Signal | Act when | What to do |
|---|---|---|
| out, and how long its names still wait (`GET /registry/users`) | at once | find another to vouch for it, within `gone` |
| a name of its own contested (`GET /registry/claims`) | at once | release it, or ask the voters whose it is |
| a claim held "while an unvouch or a cut stands" | until it is final | a second vouch, so that one voucher's keys don't decide |
| what was signed with its keys and not by it | at once | cut the key off from before (a key above; above the first keys, the voters), within `final` |
| what stopped counting after a cut, what is in the quarantine | at once | sign it again |
| what a policy no longer covers (`GET /registry/uncovered`) | before `uncovered` runs out | take it away, or move it |
**A voter:**
| Signal | Act when | What to do |
|---|---|---|
| when each voter last voted and a node of its last stamped (`GET /registry/decisions`) | a fifth not taking part | decide on a list of those who do, before a third stop |
| how many voters each node carries for | a tenth | those voters name another node, before one is a third |
| what hangs, how many records it is short of, who would refuse | at once | decide a later proposal of the matter |
| a moved-in user's first keys contested; a name contested; a root marked for both orders | at once | give first keys, say whose the name is, or leave the root out |
| a root's or a voter's key stolen | at once | first keys anew with a cut: one decision |
**A root:**
| Signal | Act when | What to do |
|---|---|---|
| a node of its own up: its last stamp | older than twice `stamp` | start one: while none is up, nothing settles |
| a moved-in user without keys that came to it | at once | give it its first keys |
| its own keys | stolen | ask the voters for first keys with a cut |
## Why it holds
**Promise 1**, by how a change is judged: every node judges a change before applying
it, at its dependencies, and refuses it with everything built on it *(checked:
`access::rules::judge_reading`, `access::screen`)*. The rules above read the document
at the change's dependencies alone.
**Promise 2.** Whether a change is valid depends on the change and its history; its
hash covers both. So honest nodes agree on every change, hold the same valid changes
once each has what the other has, and Automerge gives the same document for the same
changes. Resolving is a function of the changes. Everything it reads is fixed by
hashes: a statement's place is what it says it saw, a witness's word is its change's
history, and a proposal is decided by its records' histories. A node's clock, and the
order things reached it in, enter only into what its own node writes (its stamps,
taking a proposal up, its acks, and as a coordinator the base), never into what it
reads from the document. What must hold for this, and doesn't everywhere today:
* the root change given, never learned;
* no window without a policy (it is in the genesis change), and no syncing under a
policy the node doesn't know;
* a batch judged at heads that differ from a change's dependencies only where nothing
the rules read changed in between: what screening takes as read by rules *(checked:
`screen::relevant` lists members, users, remakes, votes, access and node bans)* must
have the registers of users and claims, the decisions and what is uncovered;
* nothing a node keeps a bounded number of decides validity: a change pushed out of
the waiting ones comes again *(checked: `MAX_WAITING`)*;
* a change being what Automerge itself writes. Automerge 0.12 applies some that
aren't, and then holds another change than the one it was given: under the hash
received it gives back a change with another hash, and its save doesn't load
*(measured upstream)*. Screening refuses those before Automerge sees them;
* a register made by two changes at once holding what both put there. Two claims of
a name nobody claimed yet each make its register, and after a remake every node
makes the same registers; reads show maps made at one key as one *(docs)*, and
judging and resolving must read them so;
* one change per actor and number. A forked actor breaks "hold the same changes"
until one side drops. Automerge names a change by actor and number where
Kleppmann's construction needs the hash.
**Promise 3.** A value counts only with an envelope whose signature checks against a
key that step 2 gives its user for the change that carries it. A key is a user's only
by statements signed with keys above it, up to its creation, signed by its creator,
and so on up to a root, in the root every node was given; or by a decision, which is
promise 7's. A node that carries doesn't sign in the user's place: the envelope names
its swarm, epoch, path and user ID *(checked for swarm, path and the user's name:
`access::envelope::check`)*, so it counts nowhere else and for nobody else. A name is
held by a claim so signed, by a rule, or by a decision. Across a remake: every node
builds the snapshot from changes it judged, so the snapshot holds only what counted or
could, as envelopes with their signatures, and what is carried over is signed as it
was.
**Promise 4.** Steps 3 and 4 name a holder only where exactly one claim remains.
**Promise 5.** Let c be a claim that stands, and w a change that a root's node
committed with c in its history, standing there, and no other claim of the name
standing there (c is settled). Let c' be any other claim of that name. In the history
of w it is missing, or doesn't stand. The roots' nodes are on every side, so w is a
change by the side of c' that saw c hold the name while c' didn't: c' is late against
c in every set of changes that holds w. A late claim never holds a name while the
other stands, and c stands until it is released, its user is gone, or a decision
deals with it. So nobody takes the name by another claim, whenever it surfaces,
whatever it says it saw, and whatever brings it to count.
What is left to an adversary while c isn't final, each in the open:
* making c late too, so that none remains. That takes a change by a node of c's user
or of a root with c' standing in its history and c not. An honest node that
received c first never commits one: everything it commits after has c in its
history. So it takes such a node that lies, or that truly received c' first. If it
also committed changes with c and not c', both orders are in the document under
its user's name, and the registry says so;
* taking w away: the root stops its node with a cut from before w. Then c is as it
was before that root saw it, and settled only if another root's node saw it too;
* bringing back a claim c was made after: its release, or the cut that left it out,
is cut off.
Final ends all three. c has been seen holding the name for `final`: a third of the
voters each have a node with two stamps that far apart, at which and between which
the registry as that node held it gave the name to c. One of them is honest: its
clock went that far, and all that while nothing it held took the name from c. From
then on step 4 has every other claim give way to c. What is left then: a claim that
became final the same way out of c's sight, which takes honest voters' nodes kept
apart from c for that long, and leaves the name contested; the voters (7); and c's
own key cut off from before c, which is its user's doing or the voters'.
Before a root saw c: a claim c' out of its sight isn't late unless its own side shows
otherwise, so the two contest each other, or, where a root's node got c' first, c'
is settled and c late. That is first come, first served as far as anyone can witness
it.
What the assumptions are: signatures and hashes hold; an honest node's changes build
on all it has received (Automerge does that); for settled, the changes the roots'
nodes commit count and the roots don't turn; for final, fewer than a third of the
voters are malicious, and the honest ones' nodes keep time.
**Promise 6.** No rule for what users write reads a vote or waits for another party;
a write is refused only by what its own history holds, and counts from the start.
**Promise 7.** Let V be the epoch's voters, n of them, fewer than a third malicious.
* *None that honest voters didn't vote for.* A record is valid only with votes for its
proposal in its history by more than 2n/3 of V, none released there: more than n/3
of them honest voters'. And a proposal is decided only with records that count for
more than 2n/3 of V, for more than n/3 of them written by honest nodes, each while
it held that many votes, running by its clock.
* *Not from the past.* So votes crafted later, or kept back until they ran out, bring
no honest node to take anything up, and the nodes of fewer than a third decide
nothing.
* *Not by the voters before.* A decision of voters that a decision on who votes
replaced counts only in sight of that decision's proposal, which was signed before
any key stolen later: the voters before decide nothing more. And a decision seen
holding for `final` by a third of the voters, an honest one among them, is replaced
only by one proposed in its sight: one of its matter made up later, with whatever
number, isn't.
* *The same one everywhere.* Whether a proposal is decided is read from its records
and their histories; which decision of a matter holds, from the proposals'
numbers, which follow from what each says its signer saw, and their digests. No
node's clock enters, nor who committed a proposal, nor how often.
* *Two of one matter.* A voter has one vote on a matter at a time. So two proposals
of one matter are both decided only where more than a third of V voted for both:
voters who changed their minds, or malicious ones, who are too few. The higher
number holds. More than a third of V have nodes that took both up, honest ones
among them, and an honest node takes the higher up after the lower: where voters
changed their minds, what holds is what they moved to. A proposal decided late
takes nothing from one with a higher number.
* *The sides of a partition.* A side decides only with nodes of more than two thirds
of V on it. Two sides both do only where more than a third of V have nodes, and
votes, on both: then two proposals are decided, and every node acts on the same
one once it holds both.
* *Seen for long.* What was seen for a length of time has a third of the voters each
with two stamps of one node that far apart: one of them honest, whose clock went
that far, and which held the thing so all the while. Fewer than a third, stamping
as they like, show nothing; and a node counts for one voter.
* *Nobody is moved.* A node refuses any decision by its operator's word or bounds, and
follows a fork by its operator's word alone.
* *With other fractions.* Write d for `fractions.decide` and s for `fractions.seen`.
A decision no honest voter voted for takes d of the voters malicious. Two
proposals of one matter both decided, with nobody changing their mind, take more
than 2d − 1 of them voting both ways, which at a half or less is nobody; the same
for two sides of a partition. What was seen for long holds against fewer than s
of the voters.
**A remake changes nothing** (promise 2). The snapshot is a function of the base,
which every node holds and judged itself, and holds whatever can still count: the next
epoch resolves at its root as the base did, and nothing it leaves out could have
counted again (For good, under Cuts). What a node holds beyond the base comes along
with what it held of it, by its carry record, whatever base the coordinator chose: an
honest node witnesses there as its changes would have. Lengths of time go on from the
stamps the snapshot lists. So a remake from any base, by any node, at any time, moves
nothing that counts; and of two, every node goes to the one with the lower ID, which
counts nobody's nodes.
**Unvouching** takes away no more than its signer could have kept from seeing: what
the unvouched user signed stays if a node of the unvoucher or of a root committed a
change that has it in its history and not the unvouch. Those changes are taken back
only with their node's witness, where the node is stopped with a cut from before them:
an unvoucher that stops its own nodes so undoes what they had seen, never what a
root's node had. So the point moves forward as more of them show up, and back only as
far as the roots' nodes' witness.
## Roads not taken
* **Agreement among the parties for every write** (PBFT and the like) would give one
order of claims, final at once. It needs a fixed set of voters of which fewer than
a third fail, halts the smaller side of a partition, and makes every claim wait for
a round. It works against what continuum is for: no node special, each working on
its own, both sides of a partition going on. Here only decisions take it, a few a
year.
* **A registrar**: every claim signed by a root before it counts. That is the roots'
witnessing made a condition: one order, but nothing counts while they are away,
and they decide alone. Here the same witness only orders what already counts, and
time makes it final without them.
* **Deciding by a hash or a timestamp** of the claims: whoever crafts later chooses
the lower hash and the earlier time.
* **Deciding by seniority** (the user nearer a root holds the name): always a
holder, but a senior user that kept silent takes a junior's name by backdating,
and a root that lies takes any. Contested, with `release` to give a name up, fails
safer: a name is blocked in the open, not taken.
* **The users above a user as witnesses of its claims** (those on its lines, down
from a root): they would witness while the roots are away. But whoever is above a
user would have a say about its names, a vouch would have to be accepted before
it gave one, and in a registry whose users the roots create nobody is above
anyone. The roots witness, and time makes final.
* **One root.** One user's nodes would settle every claim, nothing would be settled
while it is away, and it alone would stand between a claim and whoever backdates.
Several roots cost a contest where two of them saw two claims in two orders.
* **Roots for a whole epoch**, changed only by a remake: a root that turns would keep
its seat until one. A decision changes them, and whether a user is a root is read
where each thing it did was done: what a root settled and whom it created keep the
standing they had.
* **Votes by nodes**: a party runs as many nodes as it likes.
* **Voters by a rule** (the users a root itself created, whom nobody else can
multiply): who takes part and who doesn't is known to people, not to a rule. So
those who vote say who votes next.
* **Leaving out the voters that are away** (one whose nodes were silent for a time
neither votes nor counts): those who stay could go on deciding whoever left. But
silence is shown by stamps, and whoever stamps together shows the rest silent: a
majority would decide at once what is to take two thirds, and a proposal crafted
to look old would choose who counts. Every voter counts; a decision names those who
take part, and where a third are gone before one, those left go apart.
* **Recommending a majority, not two thirds**: a third that votes both ways must not
get two proposals of one matter decided, to choose between them. Two thirds stand
that against fewer than a third; a majority stands it against nobody.
* **One decision a matter, each node taking up the first it sees and no other**: two
would never both be decided. But two made at once split the nodes between them,
neither is, and the matter stands still until the next epoch. Letting both be
decided, and the higher number hold, never stops.
* **A proposal that lapses** (taken up no more, and its records void, once its votes
ran out): nothing would hang. But "once" is a time, and a record made to look as
if written in time can't be told from one that was. Nodes going up in numbers
only, and a later decision, end what hangs without a clock.
* **A node holding back a decision that comes late**, by its own clock, for its
operator to say: two nodes with the same changes would act on different
decisions, and one that joined later would never ask.
* **A decision counted where its proposal was made** (who votes, the numbers, a name
given, all as they were there): a proposal's place is its signer's to choose. It
is counted where it is decided, and the registry by what holds.
* **A clock of the swarm** (the latest time a third of the voters have stamped) for
how long something lasted: it sets one node's clock against another's. Two stamps
of one node measure a length of time by one clock, and the document says what
that node had seen at each.
* **A policy that changes only by going apart**, each operator saying yes: nobody
would be bound, and a swarm would split at every change. A decision binds those
who don't refuse it.
* **Unvouching by anyone above**: a user in between could put out one further down
without taking along all below. But a root is above everyone, and would put out
whom it liked, for good.
* **Neighbours by who vouched for whom** (a node keeping its creator's nodes): a
claim would reach a root whatever the member list gives, and a user would have
to reach whoever brought it in.
* **Rules that know what a name is** (an address's parts as numbers, two spellings
of one address): continuum would have to know every kind. The structure of a name
and the characters it is made of are the same for all of them; what it means is
the application's.
* **Numbers the design fixes**, the fractions above all: they would keep a swarm's
voters from deciding badly by rules none of them chose. Every number is the
swarm's; whoever won't bear a decision refuses it, and goes on with those who
think alike.
* **Users voting as soon as they are created**: whoever creates users carries every
decision.
* **Voters named by a remake**, the votes of before put out of reach by throwing
history away: the voters before would still decide "of then" within the epoch (the
first root alone, for the time it was the only one), and who votes would wait for a
remake. Sight of the proposal that replaced them puts it out of reach.
* **A snapshot of only what its users' own nodes write again**: every node carries
over what it holds, whoever signed it. Else what a root's node saw first after
the base would be nowhere in the next epoch, and whoever wrote first there would
have come first.
* **An unvouch undoing everything its user ever signed**: nothing to backdate, but it
takes back the user's releases, and no vouch brings the user back as it was. **Or
only what the user signs in sight of it**: the user goes on by never building on
it. **Or from where each node received it**: that is in no document, so two nodes
would resolve the same changes differently.
* **A user that was gone coming back by a vouch made in time**, out of the sight of
those who saw it gone: a vouch crafted to look old then blocks any name claimed
in good faith since.
* **A claim that didn't count coming back over one made in sight of it** (its user
vouched for again, its limit raised): whoever claimed a name that showed free
would lose it to a claim it had seen and rightly passed over.
* **First keys given by those who vouch for the user**: fewer to convince, but a
user's creator takes its name where nobody else vouched.
* **A registry of only what is signed**, from the start: nothing unsigned ever
counts, but it is incomplete for as long as users take to come, and what reads it
needs the repository beside it meanwhile.
* **An actor for every change, made from the change** (the hash of its bytes with the
actor left out, 32 bytes, number 1): two changes could never share an actor and a
number, so a fork of an actor would be two changes that every node holds, shown
and parting nobody. It is what Kleppmann's construction asks for, and a receiver
checks it with one hash. But Automerge 0.12 keeps a slot per actor in every clock
it caches, and moves its indices for every actor that comes, so memory and time
grow with the square of the changes: 10^4 changes take 32 to 257 MB of heap and 2
to 20 ms to apply one more, 10^5 take 2.7 GB at least and 0.16 s *(measured
upstream)*. A hundred nodes stamping daily write 10^4 changes in a hundred days.
So a fork of an actor is proven and named, and not prevented, for as long as
Automerge's clocks grow with its actors.
* **Saying what was held by the order of a node's first changes** after a remake: an
order says one thing, and what a node held of a claim, an unvouch and a value are
three. The node states them.
* **Every node writing again all it holds** after a remake, before taking anything:
each envelope since the base would come once for every node that held it, a
month's statements times the nodes after a remake from an old base. The nodes witness
by digest, and the envelopes come once.
* **Remakes the voters decide**: a remake would be one more decision, with a base every
node checks, votes naming that base, a time after which nodes no longer follow,
and a heal for the split that time makes. A remake that changes nothing needs none
of it: any base serves, and the nodes remake as the document grows, as any swarm
does.
* **Following the epoch most nodes are on**, as a swarm that isn't federated does
where two remakes of one epoch were committed: a party runs as many nodes as it
likes. The lower ID counts nobody.
* **A remake that makes final what its base holds**, a cut reaching no further back:
how far a cut reaches would depend on when the swarm last remade, and remakes come
as the document grows. What stopped counting for good is what was seen so for
`final`, remake or not.
* **The epoch for those who refuse built wherever a proposal says it was signed**:
its signer would choose what refusing costs, up to a whole epoch carried over.
Nobody takes up a proposal that says it saw less than its node held a window
before.
* **A late claim standing in wait** for the name: whoever signed, in time, a claim
that says it saw nothing would have the name the moment its holder lets go.
* **A limit on writers as a rule**: a change starting one writer too many would be
refused, and an honest user whose nodes crash too often would write nothing until
a remake. Put off by each node, nothing valid is refused, and what is bounded is
how fast.
* **Any node's record counting for a voter that is out**: one node, holding old
votes, would decide for all of them. Its own nodes record, and commit nothing
else.
* **A document per user**, each written by one party, a claim counted across them (as
in Secure Scuttlebutt's feeds). A fork of an actor then spoils only the forker's
own document, not the swarm, which is the one thing this design can't give. It
needs what continuum doesn't have: many documents, and what one had seen of the
others recorded by hand. One Automerge document records that by itself.
## What members are trusted with, then
[`trust.md`](trust.md) lists what a member can do today. In a federated swarm:
| Today | Then |
|---|---|
| Write or delete any user data | Only envelopes, signed by their users; nothing plain, nothing deleted from a register |
| Write as any user | An envelope needs the user's key |
| Edit the member and user registries | Its own member entry, of a shape and a size; users come and go by statements, which only add |
| Forge votes, commit a remake alone | Votes are users', signed; a decision takes two thirds of the voters, and every node judges the records. A remake it commits alone changes nothing that counts: every node builds the snapshot itself, and carries over what it holds |
| Make the swarm forget peers | A forget record of another's node is refused; whom a node talks to is its own |
| Advertise an epoch a rejoining node follows | A node follows a remake it sees committed, or an epoch its operator gave it |
| Be a joining node's first sync | Judged from the root change on, by the policy in it |
| Say it is ready, be a catch-up source | Still believed: it can hold changes back, not add any. A joiner syncs with the others after |
| Sign a token every node takes | Taken by the nodes whose operators named it |
| Let any user of the registry log in | The users it carries for, and those its operator names |
| Say whom it reaches, how stable it is | Still believed: it bends who syncs with whom; a node keeps its seeds and its user's other nodes whatever |
| Say when it was alive, and how often all should | Believed for itself only; it takes a third of the voters to show a user out, or a claim holding, for long. How often is the policy's |
"Member" stays the word for a node in the swarm; the unit that is trusted or not is
the party.
## Continuum, or the application
In continuum, as rules every node judges by and data that parametrizes them: users by
statements (creating, vouching and unvouching, lines, keys, cuts, nodes that carry),
the namespace rule, claims by kind with their rules and limits, late, contested,
settled and final, lengths of time read from the stamps, decisions by the voters (who
votes, the roots, the numbers, the policy, a user's first keys, names), remakes that
every node builds, going apart and refusing a decision, resolving and its API, the
drop an operator asks for. All of it is general: a swarm with other kinds, or none,
uses the same.
In the application, for the registry: which kinds there are and their rules (data in
the genesis change), what a host's entry holds, the client that signs (an extension of
`scripts/continuum-signed`), moving the repository in, and writing out the files the
consumers read. Whether a host's entry may use a name is the application's check
against the resolved registry, when it writes the files out. So are a node kept as
an archive of every epoch, and whatever brings a vote from a person to a node.
More policies later are more data where a rule has a parameter, and a new rule in
continuum, with a policy of its own, where it hasn't; either way a decision.
What changes in continuum besides the rules, under the federated policy only: policy
version 2; the envelope's payload names the user ID, the epoch, and for a statement
what its signer saw; a node is given its root change, syncs under no policy it doesn't
know, takes tokens and logins by key as its operator says, writes no sessions into the
document, keeps its writer over a clean stop, stamps as often as the policy says,
keeps its seeds and its user's other nodes as neighbours, keeps the document of an
epoch it left on disk and answers for it, keeps when it received each change (for
`window`, over a restart), keeps a quarantine on disk that holds envelopes, commits
its carry record after a remake and writes again what the epoch lacks, takes compact
remakes only, by `remakeChanges` or `remakeWriters`, and of two the lower ID, rejoins
no epoch because peers advertise it, and refuses what its bounds say. For every swarm:
the wire's version, with a handshake that says which epochs its node keeps, and a node
that speaks the wire version before its own too. [`trust.md`](trust.md),
[`access.md`](access.md), [`remakes.md`](remakes.md) and the glossary get the
federated case: party, statement, in sight of, line, root, the seats', voter, claim,
cut, late, giving way, contested, settled, final, out, gone, uncovered, seen for,
taking a proposal up, a decision that holds, what hangs, carried over, a carry record,
a party (for a budget), refusing a decision, bounds, the numbers.
## Continuum changing under a swarm
Parties upgrade when they like, so a federated swarm always runs several versions of
continuum. Given the same changes they must agree on three things: which are valid,
what the registry is, and, byte for byte, the snapshot a remake builds. Whether two
versions do can't be told by looking at them, and a version's number says what its
author remembered to say. So the design goes by what nodes compute:
* **Every stamp says what its node computes.** With its alive stamp a node records the
digest of the registry as it resolves at that change's dependencies: what a snapshot
would hold there, less the members' entries. A node that holds those changes
resolves there and compares: as it goes where it holds exactly those, else for the
latest stamp of each other party once in a while. Two digests for the same changes
prove that two nodes resolve differently, signed by both, at the first input where
they do: it shows (`GET /peers`, the dashboard) long before a remake would have sent
them to two epochs.
* **A remake is followed by its result.** A node follows a committed remake only where
the snapshot it builds from the base has the ID the remake was committed for. A node
that gets another stays where it is, and says so.
* **A node checks itself before it writes.** Started with a version it didn't run
before, a node judges and resolves again what it holds *(docs: a node told that
policies disagree does so today)*, and compares with the stamps it holds of the
voters' nodes. Where it differs from the nodes of more than two thirds of the other
voters (`fractions.decide`; a voter counted once, however many nodes it has), it
writes nothing, and shows it, until its operator says to go on
(`POST /admin/check/accept`). Where it differs from fewer it shows that and goes on.
So fewer than a third stamping nonsense stop nobody, with three voters too, and a
version that computes otherwise than the honest ones stops.
* **A change of the rules is a change of policy.** What a version judges or resolves
differently on purpose, it does under a policy of its own (a part of the policy
that versions before don't know), which the swarm decides. A change is judged by
the policy decided in its history, so a version judges what was written before as
it was judged then, and carries the rules of every policy that held in an epoch
it can still walk. A node knows a policy if it knows everything in it: it goes by
what the policy holds, not by its number, and takes up none that has a part it
doesn't know.
* **Vectors.** Continuum carries recorded inputs with what must come of them: changes
and whether they are valid, sets of changes and the snapshot they resolve to. Each
test named under Attacks leaves some. A release adds vectors and changes none,
and every version passes all of them: a rule changed without a policy fails there,
before it is released.
What can't change under a swarm, whatever is decided: how an envelope is read and what
its signature covers (a snapshot carries envelopes as they were signed, from epoch to
epoch); a statement's digest; a change's hash, and what Automerge makes of the same
changes; the bytes Automerge encodes a change to (screening refuses a change whose
bytes its own Automerge wouldn't write); a snapshot's bytes for the same base and
policy. A new form of any of them comes beside the old one, under a policy.
What changes freely: everything a node does for itself. Its API, its storage, how it
syncs and with whom. The wire is between two nodes, not the swarm's: a version
speaks its own and the one before, so that parties upgrade one after another. That
is new for every swarm *(checked: a message of another wire version is ignored
whole today, `transport::wire`)*, and comes before a federated swarm is used.
And a fork it is when nodes that hold the same changes don't come to the same, and
neither gives way. It shows by a change one takes and the other refuses, by two
digests for the same changes, or by two IDs for one base: by what was computed,
never by a number. Which of the two is the swarm's no rule says. The parties see how
many of them say which, and upgrade, drop, or go apart.
## Attacks
Each with what honest nodes do, the promise it touches, and what shows it: `unit` in
the module named (`access::statements`, `access::claims`, `access::resolve`,
`access::decisions` are new), `sim` a simulation in `src/simtest/federation.rs`,
`argued` where no test can. Each test leaves vectors (Continuum changing under a
swarm).
Statements and users:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 1 | Signs a statement with a key that isn't the user's | Refuse | 3 | unit, statements: `a_statement_needs_its_users_key` |
| 2 | Puts another user's statement into a change of its own node; a `node` statement naming another node | Take the first: any node commits any user's statement, and chooses when, not what its signer saw. Refuse the second: a `node` statement only the node it names commits | 3 | unit: `any_node_commits_a_statement` |
| 3 | Commits a user's claim, lets it settle, then stops its node with a cut from before that change, for an accomplice to claim the name | A node's cut takes back what it witnessed and the writers it started, never what it carried: the claim counts as its user signed it, and its root's witness stands | 5 | unit: `a_stop_takes_back_nothing_carried` |
| 4 | Replaces or deletes a statement, or what holds the register | Refuse | 2, 3 | unit: `a_register_only_grows` |
| 5 | Offers a statement again; or an envelope signed for another swarm, epoch, path or user ID | Nothing where it is there under its digest; refuse elsewhere | 3 | unit, exists for swarm and path: `what_an_envelope_must_be`; `signed_for_its_user_id_and_epoch` |
| 6 | Commits a statement a second time, in a change with other dependencies, to move it | A statement is where it says its signer was (`seen`), whoever carries it and how often: nothing moves | 2 | unit: `a_statement_carried_twice` |
| 7 | Creates a user listing a victim's public key beside its own | The victim's envelopes name the victim's ID: they count for no other | 3 | unit: `a_key_in_two_creations` |
| 8 | A root other than the one the root change names for a moved-in user signs a `create` for it, with keys of its own, saying it saw nothing of the first | Refuse: only the root named gives a moved-in user its keys | 3 | unit: `first_keys_by_the_named_root` |
| 9 | A root releases the `create` that gave a moved-in user its first keys, after the user signed with them, and gives it keys of its own | Refuse: no root releases its `create` for such a user; once one gives keys, they are the user's | 3, 5 | unit: `a_root_keeps_to_its_create` |
| 10 | The root named for a moved-in user makes its own `create` contested by a twin on old dependencies, or signs a release on old dependencies once it is final, then gives the user keys of its own | Refuse the release. The twin is late for good where another root's node had the first standing and not the twin; else the two contest, in the open, nothing signed with the keys of either counting, until the voters give first keys: what was signed with the keys they give counts then | 3, 5; not promised | unit: `a_root_keeps_to_its_create`, `a_twin_create_is_late` |
| 11 | With the keys of a twin `create` on old dependencies, signs as a moved-in user (hosts, claims, `node` statements, vouches), each in a change whose history holds the twin and not the first | A moved-in user's keys are those of its root's creation that remains over all the changes, not where each statement was signed: a twin late for good gives keys nowhere, and two that contest give none until the voters say | 3 | unit: `first_keys_by_the_creation_that_remains` |
| 12 | Users vouch for each other in a ring away from the roots; a user vouches for its creator | None is vouched for by it | 3 | unit, resolve: `no_line_no_user` |
| 13 | Creates a name in sight of its creation | Refuse | 4 | unit: `a_name_created_once` |
| 14 | Commits a user's claim on old dependencies, or holds it back, as a node of another party the user claimed through | Who commits a statement says nothing of it: what its signer saw is in its signature, and a claim committed late is late. A user's own claims of one name are one, from whatever node: ordered by the first that stands, counted once, released together | 4 | unit: `a_claim_through_any_node` |
| 15 | Holds back a duplicate of a user's claim, and commits it once the user released the name and another claimed it; or commits a user's duplicates to push its later claims past their limit | A release gives up the user's claims of that name but those signed in sight of it: the duplicate stands no more, and the other holds. A user's claims of one name count once toward the limit | 4, 5 | unit: `a_release_gives_up_a_users_claims_of_the_name`, `claims_of_one_name_count_once` |
| 16 | Creates a user of a name another user holds by its claim of its own name; or signs that claim again and again, each kept by every node | Refuse: a creation of a name where a user's claim of its own name stands, as a claim is refused; a user has one such claim at a time | 4 | unit: `a_users_own_name_claimed_once` |
| 17 | Creates a name another has, saying it saw nothing of it | Hold both; late once a root saw the first. Before: contested, or the first is late where a root's node got the other first | 4, 5 | unit: `a_backdated_creation_is_late` |
| 18 | Gets a user's name contested to free its names | Its claims stand without the name | 5 | unit: `claims_stand_without_the_name` |
| 19 | Creates many users, each claiming many names (sybils); creates them out of each other's sight to pass the limit | Refuse past the limits in sight; out of sight, those past them don't count. A limit bounds how many each user brings in itself, not how many come in below it: each shows below its creator, for all to see, and goes with it when it is unvouched | 6 | unit: `limits_on_creating`, `past_a_limit_out_of_sight` |
| 20 | Adds keys, nodes or statements without end; signs and gives up without end (vouch and unvouch, claim and release, key and retire) | Refuse past the limits. What is given up counts toward none: it is taken no faster than a budget per party (row of the budget, stage 8), and a remake leaves it out | 6 | unit: `limits_on_a_register` |
| 21 | Signs more than its limit out of each other's sight; another claims a name that so doesn't count; then gives the earlier ones up | What comes to count later than it was signed gives way to what was claimed in sight of it meanwhile | 5 | unit: `counting_late_gives_way` |
| 22 | With a stolen key, signs statements that come before its user's own (keys, creations, claims), to push those past their limits; an accomplice claims the names that so show free | Until the key is cut off they do. What a cut leaves out comes before nothing: the user's own count again, and a claim of theirs that a root's node had seen hold is read as never down, so the accomplice's gives way | 3, 5 | unit: `cut_off_comes_before_nothing`, `down_by_a_limit_comes_back` |
| 23 | Names another party's node as one that carries for it; offers that node a token of its own | A node carries only once it committed the statement naming it; an honest node takes tokens only from nodes its operator named | 3 | unit: `a_node_carries_by_its_own_word`, `a_token_of_ones_party` |
Unvouching:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 24 | Unvouches a user it didn't vouch for; a root unvouches the users the root change holds, or those a root before it created | Refuse the first. What is the seats' is taken back once every root unvouched it: one root puts nobody out, where there are several | 3 | unit: `only_the_voucher_unvouches`, `the_seats_take_back_together` |
| 25 | The roots unvouch the voters, and wait for them to be gone, to keep them from deciding | A voter votes for its epoch, in, out or gone, and the nodes of one that is out go on committing their records and carry records, and nothing else: who votes is the voters' word, not its vouchers' | 7 | unit: `a_voter_votes_for_its_epoch`, `an_out_voters_node_records` |
| 26 | Unvouches saying it saw little, to undo what the user did since | What its own nodes or a root's had seen of the user stays | as said under Unvouching | unit: `an_unvouch_undoes_nothing_seen` |
| 27 | The unvouched user signs on, saying it saw nothing of the unvouch, or across a partition | Hold it as part of another's history only; it doesn't count; once the partition is over every node finds the same | 2, 3 | unit: `past_an_unvouch`; sim: `an_unvouch_across_a_partition` |
| 28 | A user is unvouched: what of those it brought in, and its names? | One that another vouched for stays in, without doing anything. The others are out from the same point; a vouch after brings them back whole. Their names wait | 4 | unit: `a_second_line_keeps_it`, `those_it_brought_in`, `a_vouch_brings_back` |
| 29 | An unvouched user's nodes keep sending | Refused as peers; nothing taken from them | 6 | sim: `nothing_from_an_unvouched_node` |
| 30 | Claims a name of a user that is out, or creates its user name | Refuse: the names wait until the user is gone, or a decision frees them or gives them away | 5 | unit: `names_wait_while_out` |
| 31 | Has a user unvouched, then stamps its nodes `gone` apart at once, to free the names; carries for many voters to be many | Gone takes a third of the voters, each with a node, and a node counts for one | 5 | unit: `gone_by_a_third_of_the_voters`, `a_node_is_seen_for_one_voter` |
| 32 | Shows a stamp later that lies, by its time, between two that counted, with the thing not so there | Between goes by the stamps' histories, not their times: it lies between nothing, and gone, final and dropped stay | 5 | unit: `between_two_stamps` |
| 33 | Vouches for a gone user saying it saw nothing of that, over a name claimed since | Gone stays: no vouch brings it back | 4 | unit: `gone_stays_gone` |
| 34 | Out, signs a claim that doesn't count; another claims the name in sight of it; a vouch brings the user back | It is back with what it signed, but the claim made in sight of one that didn't count doesn't give way to it; nor does a settled one that never saw it | 5 | unit: `back_but_not_over_a_later_claim` |
Namespaces:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 35 | Writes into another's namespace, signed by itself | Refuse, and the node as a whole | 3 | unit: `a_namespace_is_its_users`; sim, as `a_member_writing_against_the_rules` today |
| 36 | Writes plain values, or protocol data but its own member entry | Refuse | 3 | unit: `nothing_plain` |
| 37 | Puts an old envelope back | Refuse: it doesn't replace what is there | 3 | unit, exists: `what_an_envelope_must_be` |
| 38 | A user with a late creation of a name writes in the namespace | Refuse where its change's history shows it lost the name; else hold it and leave it out | 3 | unit: `a_user_that_lost_its_name` |
Claims:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 39 | Claims a held name in sight of the claim | Refuse | 4 | unit, claims: `first_come_first_served` |
| 40 | Claims a settled name saying it saw nothing of the claim, long after | Hold both; it is late, the holder holds | 5 | unit: `a_backdated_claim_is_late`; sim: `a_backdated_claim_loses` |
| 41 | Two honest users claim on two sides of a partition | Hold both; every node finds the same: one holder, or contested; a release leaves one | 2, 4 | sim: `a_partition_heals_to_one_answer`; unit: `a_release_ends_a_contest` |
| 42 | Claims `x.tv.r` as another; claims a top-level domain as another than a root; claims `wiki.r`, which the rules leave to the voters | Refuse: the kind's rule. A kept name needs no claim; a claim by a user that doesn't have the name its rule gives doesn't count | 4 | unit: `a_kinds_rules`, `a_kept_name`, `a_rule_goes_by_who_has_the_name` |
| 43 | Claims past its limit, in sight or out of sight of its other claims | Refuse in sight; out of sight, those past the limit don't count | 4, 6 | unit: `a_limit_in_sight`, `past_a_limit_out_of_sight` |
| 44 | Claims `TV.r` beside `tv.r`, or `10.243.foo.bar`; claims one address in two spellings | Refuse what has characters the kind doesn't name. Else a name is compared as written: the application claims one spelling and reads no other | 4 | unit: `a_kinds_characters`; argued (Claims) |
| 45 | A root says it saw a rival first, after the claim is settled | The name is contested; the registry names the changes and the root, and marks it if it showed both orders. Once the claim is final: nothing | not promised; 5 once final | unit: `a_root_contests`; sim: `both_orders_show` |
| 46 | Hands an honest node of a root or of the claimant, back from a day off, a rival before the claim | A node that comes back catches up with the peers it keeps before it writes, for `catchUp` at most. Where it wrote all the same: contested, until one releases or the voters say. Once the claim is final: nothing | not promised; 5 once final | sim: `a_node_handed_the_rival_first` |
| 47 | Two claims made at once reach two roots' nodes in two orders | Each is late against the other: contested, and one releases | 4 | unit: `roots_that_saw_two_orders` |
| 48 | Keeps silent while no root's node is up, then claims saying it saw nothing | Before the claim is settled: contested, or whichever reaches a root's node first holds. After: late. Final: it gives way | 5 | unit: `silence_before_settling` |
| 49 | Releases a claim with a stolen key, an accomplice claims | Once the key is cut off the release doesn't count: the accomplice's claim, made in sight of the first, gives way, unless it is final by then | 3, 4 | unit: `a_release_cut_off` |
| 50 | Signs a claim and cuts its key off at once, so that the name shows free; another claims it; then cuts off the key that cut | It comes back over nothing: no root's node saw it hold the name before it was down | 5 | unit: `a_planted_claim_comes_back_over_nothing` |
| 51 | Signs claims of held names that say they saw nothing, to have each the moment its holder releases it, is gone, or the voters free it | A claim late against another that isn't late against it is late for good: it doesn't stand, and whoever comes first then has the name | 5 | unit: `late_for_good` |
| 52 | A limit is lowered and raised again, or a policy uncovers and covers again; someone claims in between a name that so showed free | The claim made in sight of one that didn't stand keeps the name: the other gives way, though a root's node had seen it first | 5 | unit: `sight_decides_alone` |
| 53 | Every root that saw a claim stops its node with a cut from before, and a rival is handed in | A final claim holds. One that isn't is as before the roots saw it: contested, or late | 5 once final; not promised before | unit: `final_against_the_roots` |
| 54 | Stamps its nodes `final` apart at once, to make a claim final that doesn't hold, or holds only as it sees it | Final takes a third of the voters, each having held the claim as the holder at both stamps and between | 5 | unit: `final_by_a_third_of_the_voters` |
| 55 | Keeps honest voters' nodes apart for longer than `final`, a claim of one name on each side | Both are final: contested, until one releases or the voters say whose it is | not promised | sim: `two_finals` |
Keys:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 56 | Steals a device key and signs with it | Take it until a key above cuts it off, then leave out what is outside the cut; a value it replaced is read again | 3 | unit: `a_retired_key_counts_within_its_cut`, `the_value_before_counts_again`; sim: `a_stolen_key_cut_off` |
| 57 | Signs with a retired key, saying it saw nothing of the retiring | Hold it (valid as written), leave it out | 3 | unit: `backdated_past_a_cut` |
| 58 | With a stolen device key, retires the keys above or beside it | Refuse | 3 | unit: `no_key_retires_one_above` |
| 59 | With a stolen device key, retires that key from long ago, on old dependencies, to undo what its user signed with it since | Valid as written, and it takes back nothing a node of its user or of a root had seen without it: what the user signed since stands. A key above cuts the theft off | 3 | unit: `a_key_retires_itself_forward`, `a_retirement_on_old_dependencies_keeps_what_was_seen` |
| 60 | A key retires itself; a node commits its own stop | Each counts: a cut never leaves out its own statement | 2 | unit: `a_cut_never_reaches_itself` |
| 61 | With a stolen key, retires the keys below it, stops nodes, unvouches, releases names | A key above cuts it off from before: all of it is taken back, but what became final on it | 3 | unit: `a_cut_takes_back_what_the_key_cut` |
| 62 | Is unvouched with a key that is then cut off from before, and claimed names while out | In again, its earlier claims having stood all along; what it claimed while out gives way to what was claimed in sight of it meanwhile. Gone stays gone | 5 | unit: `an_unvouch_cut_off` |
| 63 | Creates a user with a stolen key, under a name kept for its victim's creations, and has an accomplice vouch for it | Once the key is cut off, the creation no longer claims the name: the user stays in by the vouch, with its keys and claims, and without a name or a namespace | 3, 4 | unit: `a_creation_cut_off` |
| 64 | With a device key, releases the user itself; with a stolen first key, does so before the voters can cut that key off | Refuse the first: it takes a first key. The second puts the user out, its names waiting, and a cut takes it back within `gone` | 3 | unit: `giving_up_takes_a_first_key`, `given_up_is_out_first` |
| 65 | Steals a user's first key | The name is the thief's too, until a decision gives the user first keys anew, with a cut for the stolen one | 7 | unit: `first_keys_by_a_decision` |
| 66 | Cuts its own key off early to take back a vouch or a release | It is taken back, but for what is final; a vouch as by its signer's unvouch, from where the retirement was signed: without a second vouch the user is out, its names waiting until it is gone or a vouch comes | not promised | unit: `a_second_vouch_stands` |
| 67 | A key is retired on one side of a partition while it signs on the other | Once the partition is over, every node leaves out the same | 2 | sim: `a_cut_across_a_partition` |
| 68 | Steals a node's key: commits changes as a witness | They count until the node is stopped with a cut, then not | 5 | unit: `a_stopped_node_witnesses_nothing` |
Decisions and remakes:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 69 | Forges a vote; votes as a user that isn't a voter, or one that is gone | Refuse | 7 | unit, decisions: `a_vote_is_a_voters` |
| 70 | Brings in many users to vote, also while a list's votes run | They vote only if a decided list names them, which those who voted saw | 7 | unit: `who_votes` |
| 71 | A list of voters with the many users one user brought in; users put out between the votes and the decision, to shrink the list | The voters see the list, by IDs, before they vote for it, and propose one of their own instead. Nothing after the proposal changes it | 7 | unit: `voters_by_a_decision`, `a_list_is_fixed_when_signed` |
| 72 | Records taking a proposal up without the votes, or with released ones | Refuse: every node judges a record against the votes in its history. | 7 | unit: `a_record_needs_the_votes` |
| 73 | Carries for many voters that have no node, and records with votes that ran out | Taken: nobody but the recording node reads a vote's end. A voter without a node is the party that carries for it, for a record; what is seen for long counts that node once | not promised | unit: `a_record_counts_for_its_voters`; argued (Decisions) |
| 74 | Carries for a third of the voters, and keeps its records back: every decision waits, and comes on its day | The voters name another node, which records for them; their votes count meanwhile. A voter carried by nodes of two parties never waits for one. How many each node carries for shows | not promised | sim: `a_carrier_keeps_back` |
| 75 | Keeps votes back until they ran out, or crafts them to look old, then shows them | No honest node takes the proposal up, and fewer than a third decide nothing | 7 | unit: `taken_up_while_the_votes_run`; sim: `a_decision_from_the_past` |
| 76 | Keeps its node's record back, and shows it weeks later: a proposal decided late | It holds only where none of its matter with a higher number was decided since: a node takes up nothing lower than it took up. What hangs shows, and the voters end it with a later proposal | not promised | unit: `nothing_lower_is_taken_up`; sim: `decided_late` |
| 77 | Two proposals of one matter both decided: voters changed their minds, or a third voted both ways | Every node acts on the one with the higher number, the same from the same changes; the other shows as replaced | 7 | unit: `the_last_holds`; sim: `two_decided_one_holds` |
| 78 | Makes a proposal saying it saw little or much, for a number of its choosing; grinds its digest; commits another's a second time | A number brings nothing without the votes of two thirds and their nodes' records; who votes is the epoch's, wherever a proposal is made; a second carrier changes nothing | 7 | unit: `a_proposal_is_where_it_was_signed` |
| 79 | Stays away to hold decisions up | It counts on. A third staying away do hold them up: the rest go apart, naming who votes | 7 | unit: `two_thirds_of_all` |
| 80 | Asks the voters for another user's first keys, saying it is that user | It takes two thirds of them, and the days a vote takes, shown to all; the user signs on meanwhile | not promised | argued (Decisions) |
| 81 | Puts a voter's vote into a change of its own node; keeps one back; offers one again | Taken: the signature is the voter's. It counts while it runs; the register holds it once | 7 | unit: `a_vote_by_any_node` |
| 82 | Signs a vote that says it runs out in ten years | A node counts no vote for longer than `window` from when it first held it | 7 | unit: `a_vote_runs_a_window` |
| 83 | A decision lowers a limit; a user signs on saying it saw nothing of the decision. Or a decision lowers a limit for a day, and raises it again. Or it sets a number that makes no sense | Valid as written, and resolved by the limit that holds: what is past it doesn't count. Names claimed in sight of what fell past it are their claimants' for good. The number has the result it has | 6; not promised | unit: `a_lowered_limit_leaves_out_the_last` |
| 84 | Opens proposals without end | Refuse past `limits.proposals` | 6 | unit: `limits_on_proposals` |
| 85 | A proposal gives away the name of a user that is out; the user is gone and another claims the name before it is decided | The claim was made in sight of one that didn't stand: it doesn't give way to what the decision gives | 5 | unit: `given_too_late` |
| 86 | Contests a name, then asks the voters for it; or two claims of it are final | It takes two thirds of them; every other claim gives way to the one they name, final or not | not promised | unit: `whose_a_contested_name_is` |
| 87 | Claims `wiki.r`, which the rules leave to the voters; holds on to it against a later decision | Refuse the claim. The name is whose the decision that holds says | 4, 7 | unit: `a_name_by_the_voters` |
| 88 | A user is out and stays out: what of its names? | A decision frees them, or gives them to another, whatever `gone` says | 7 | unit: `a_decision_frees_or_gives` |
| 89 | The voters decide a policy that covers a user's names no more; another user writes over what is uncovered; a third of the voters stamp to drop it at once | It doesn't count where the policy holds, and shows aside. Only its user takes it away, nobody changes it; it is dropped once seen there for `uncovered` | not promised | unit: `what_a_policy_no_longer_covers`, `uncovered_is_only_taken_away` |
| 90 | The voters decide a policy that stops keeping names for their users | A kept name its user claimed stays its claim. One it didn't is the first comer's | not promised | unit: `a_kept_name_claimed` |
| 91 | Runs most of the alive nodes: commits remakes from bases of its choosing, as often as it may; serves a snapshot of its own | Nothing that counts changes: every node builds the snapshot itself, carries over what it holds beyond the base, and follows a remake only once its base holds `remakeChanges` changes or `remakeWriters` writers. Each costs every node a snapshot | 2; not promised (how often) | sim: `every_node_builds_the_snapshot`, `remakes_no_sooner_than_the_changes` |
| 92 | As a remake's coordinator, commits a base that leaves out a claim settled minutes before, and holds its accomplice's rival | The nodes that held the claim carry it over with what they held of it: a root's node's carry record has the rival late against it, as its change would have | 5 | sim: `a_base_that_leaves_out` |
| 93 | Commits a remake of another kind (`replace`, `import`, `strict`), with content of its own | No node follows it: a federated swarm compacts only | 3 | unit: `compaction_only` |
| 94 | A name is claimed and settled after a remake's base; after the switch a pretender signs a claim of it "in the epoch before" | A root's node named the real claim in its carry record, before it took anything in the new epoch: the pretender's claim is late against it | 5 | unit: `a_carry_record_witnesses`; sim: `a_pretender_after_a_remake` |
| 95 | Hands in, weeks into an epoch, envelopes of the epoch before that no node carried: a value its user since replaced, a statement its user never sent | Taken from any node, as within an epoch: a value carried over has no word against one its user signed in the new epoch, and is left out where another carried over replaces it; a claim is late against what a root's node's record named; a number orders only among what is carried over | 3 | unit: `carried_over_from_any_node`, `the_new_epoch_has_the_last_word` |
| 96 | Signs after the switch, as of the epoch before, statements and a proposal with numbers of its choosing | Carried over comes after what the snapshot holds and before what the new epoch signs: such a number orders only its signer's statements among what is carried over, and the proposal outranks none of the new epoch | 6, 7 | unit: `carried_over_in_between` |
| 97 | Writes a carry record naming what it likes, or several, or one of its own after taking from peers | One a node and epoch. What it names is its node's word, as a change of that node would have been: a contest where it is a root's or the claimant's, no more | 5 | unit: `one_carry_record_a_node` |
| 98 | Signs a claim on a branch of its own, retires the key that signed it from before the claim, and shows both together; another claims the name in sight of both; then cuts off the key that retired | The first comes back over nothing: no root's node saw it hold. The two are ordered by the roots' nodes alone, which had the later one standing and the first down: the first is late, for good, and its claimant's own old stamps count for nothing | 5 | unit: `a_claim_in_sight_past_a_cut_by_the_roots_alone` |
| 99 | Unvouched a user, then has a node of its own stamp, weeks later, a change that has the user's claim and not the unvouch, to bring the claim back over one made in sight of it | The two are ordered by the roots' nodes alone: the unvoucher's own node counts for nothing. A root's node doing so, on old heads, makes the later claim late against the first, in the open: a root's word, until the claim is final; where another root's node had the later one standing and not the first, the two contest | 5 | unit: `a_witness_after_the_fact` |
| 100 | Cuts its own device key off from before a user's creation it signed, to take the user's final name | The creation stops counting as its signer's unvouch would, from where the retirement was signed: what the user signed before counts, and its claim of its own name, with its own key, holds the name on. Without another vouch the user is out, its names waiting, final ones too, until it is gone or a vouch comes | 5 | unit: `a_users_own_name_by_its_own_key` |
| 101 | Creates a user nobody else vouches for, lets it claim names until they are final, then cuts off the key it created it with from before the creation, to take the names | The creation stops counting as its signer's unvouch would, from where the retirement was signed: the user is out from there, its names wait, final ones and its own name too, and it is gone after `gone` unless a vouch comes. Nobody claims them meanwhile | 5 | unit: `a_creation_cut_off_puts_its_user_out` |
| 102 | Creates a user, lets it settle names, then cuts the creation's key off from before it with a retirement that says it saw little, its own nodes silent, so that nothing the user signed counts through the creation, and an accomplice claims its names | The roots' nodes witness past a cut, as against an unvouch: what the user signed that a root's node had in its history counts, its settled names hold, and it is out from the retirement, its names waiting | 5 | unit: `a_cut_keeps_the_roots_witnesses` |
| 103 | Cuts the creation's key off from before it on old dependencies, then claims the user's settled names, or creates a user of its name, in a change whose history holds the user's claims and the cut and nothing else | Where the user's claim didn't stand there only by the cut, the two are ordered as claims out of each other's sight, over all the changes, with the roots' nodes alone as witnesses: they had the user's claim count first, so the new claim is late, for good, and the user keeps its names | 5 | unit: `a_claim_in_sight_past_a_cut_is_ordered_by_lateness` |
| 104 | A root cuts off the key it created users with, from before the creations, to take their names, final ones too, where only the roots create users; or a thief of a root's key gives a moved-in user first keys | A root's creation another root's node had seen stays the claim of the name, and its first keys, past a cut the root or a thief sets: a turned root takes back only what the other roots hadn't seen, never a settled or final name; the only root, all it created. The voters' cut of a stolen root key takes back what it created outside the cut, whoever saw it: one decision | 5; not promised (one root) | unit: `a_roots_creation_outlasts_its_cut_where_another_root_saw_it`, `the_voters_cut_takes_a_roots_creations` |
| 105 | A root's node, beside a thief, commits with a fresh writer on heads without the retirement a change holding what the thief's sock signed, to keep it in past the cut | A root's node witnesses past a cut, as against an unvouch: the sock stays in by it, in the open, shown with the root (`GET /registry/users/<name>`). An accomplice's vouch keeps it in too | not promised | unit: `a_cut_has_its_signers_witnesses` |
| 106 | A node that held only the older of two values its user wrote since the base carries it beside the newer one | Of several carried over to one place, one that another replaces is left out | 3 | unit: `a_replaced_value_is_left_out` |
| 107 | Signs a claim "in the epoch before" of a name the snapshot holds | It is late against the snapshot's claim where that was settled at the base, or where a node of its side had that standing; else the two contest, as claims out of each other's sight do | 5 | unit: `carried_over_against_the_snapshot` |
| 108 | Hands in again what a remake left out: a stolen laptop's `node` and `key` statements, retired since | Refuse: the root change lists the digests of the statements the base held | 3 | unit: `what_a_remake_dropped_stays_out` |
| 109 | Commits a remake from a base a month old | Every node goes there, and its carry record names what it holds beyond the base and what it held of it (who saw what first, decisions since); each envelope comes once. A key retired since keeps what its list names. Lengths of time go on from the stamps the snapshot lists, each node's record saying what it saw broken | 2 | sim: `a_remake_from_an_old_base`; unit: `a_retirement_lists_what_it_keeps` |
| 110 | Commits a second remake of an epoch beside another, its ID ground lower; or many | Every node goes to the one with the lower ID that it builds, carrying over what it holds, envelopes of the other among them: nothing is lost, and no count of nodes decides. Each costs every node a snapshot, lowest ID first, until one comes out | 2; not promised (how often) | sim: `two_remakes_go_to_the_lower` |
| 111 | A thief's statements are in the base of a remake | They are as they were: the snapshot holds them with their signatures, and a cut set after takes them back as it would have. A remake makes nothing final | 3 | unit: `a_cut_reaches_across_a_remake` |
| 112 | Releases a user's claim with a stolen key, and an accomplice claims; the user cuts the key off two months later | What was seen given up for `final` has stopped counting for good: the release stands, as the accomplice's claim does, final by then. A remake or none changes nothing of it | not promised (protection from a stolen key) | unit: `stopped_counting_for_good` |
| 113 | Tells a node that was away of an epoch that isn't the swarm's | The node rejoins no epoch that peers advertise: it finishes the old one from archives and builds the next itself, or takes the ID its operator gave | 1 | sim: `away_over_a_remake`, `back_by_an_id` |
| 114 | A node back after several remakes offers what its user signed epochs ago | Refuse: an envelope is taken in its epoch and the next. Quarantined, for the user to sign again | 3 | unit: `carried_over_one_epoch_only` |
| 115 | A version builds another snapshot from a remake's base | Its node gets another ID than the remake was committed for, stays, and says so: two IDs for one base show | 2 | sim: `a_remake_by_its_result` |
| 116 | A decision on the roots names its proposer the only root, or leaves a root out; the root left out signs on as one, and its node witnesses on | The voters see whom a proposal names before they vote for it. A root is one where the decision naming it holds, read where each thing it did was done: what it signs after it is left out is an ordinary user's, its node's changes after witness as no root's, and it is out unless someone vouches for it | 7 | unit: `roots_by_a_decision`, `a_root_where_it_is_one` |
| 117 | With the keys of two thirds of voters since replaced, stolen later, makes up a decision of then; or a list of voters of its own, with the number of the one that replaced them and a lower digest | What voters that others replaced decide counts only in sight of the proposal that replaced them: the first decides nothing. The second holds only until the list it would replace is final: no decision of its matter proposed out of sight of a final one holds | 7; not promised before final | unit: `the_voters_before`, `a_final_decision` |
| 118 | Two thirds of the voters turn on the rest | They name the roots and who votes, remake, set any number (a share of the voters that lets one decide for all), change the policy, give a user's first keys to another, deal with the names of a user that is out, and say whose a contested name is: a name taken, in the open. They forge no signature and move nobody to other rules; the rest refuse, or fork | not promised | argued (Going apart, Refusing a decision) |
| 119 | Offers a statement signed on the other side of a fork | Refuse: it names its epoch | 3 | unit: `signed_for_its_user_id_and_epoch` |
| 120 | A fork naming its proposer the only voter and root | A node follows only by its operator's word, which names the proposal; what that says shows | 7 | sim: `a_fork_by_choice` |
| 121 | A decision breaks a node's bounds: the voters let one of them decide for all | The node refuses it and moves to the epoch built without it, the same for every node that refuses, with what it held: they go on together | 7 | unit: `bounds_on_the_numbers`; sim: `those_who_refuse_meet` |
| 122 | Proposes saying it saw only the epoch's root, so that those who refuse carry the whole epoch over | No honest node takes up a proposal that says it saw less than the node held a window before: it isn't decided | 7 | unit: `a_proposal_says_it_saw_enough` |
| 123 | Says it refuses a decision, or hands out the ID of an epoch without it, to draw nodes there | A node goes there by its own bounds or its operator's word only | 1 | unit: `refusing_is_ones_own` |
Nodes and syncing:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 124 | Sends different changes to different peers, each under its own number | Take all: changes made at once | 2 | sim: `two_histories_merge` |
| 125 | Forks its node's actor | The nodes that took each split; one offered both holds proof and refuses the node; a side drops by its operator's choice | not promised | sim: `a_forked_actor_is_proven`, `a_side_drops_a_fork` |
| 126 | Holds changes back, or passes on some | They come by other nodes; a joiner caught up with it syncs on | 6 | sim: `withheld_changes_arrive` |
| 127 | Places its nodes around a victim by choosing their keys | The victim's node keeps its seeds and its user's other nodes as neighbours; a claim not settled for long shows. It costs time, not names | 5, 6 | sim: `around_a_victim` |
| 128 | Hands a joining node another root change, or changes from before the policy | Refuse the handshake; there is no before | 1 | sim: `a_joiner_takes_its_root_only` |
| 129 | Signs a token for any user with its node's key | Taken only by a node whose operator named the signing node | 3 | unit: `a_token_of_ones_party` |
| 130 | Logs in on another party's node with a key of the registry; has a name in the registry that the node's own users have | Keys in the registry give nothing on anyone's node by themselves: whom a node lets in is its operator's, and what a user may write is in its signature | 3 | unit: `registry_keys_open_no_node` |
| 131 | Lies in its member entry (ready, reached, stable); publishes a short window there to make every node stamp hourly; writes an entry of any size | Sync and trees bend; nothing gets in that way. How often nodes stamp is the policy's; an entry has a shape and a size, or the change is refused | 6 | unit: `an_entry_has_a_shape`, `stamps_by_the_policy`; argued (Reaching the others) |
| 132 | Sends envelopes that don't check, without end | Refuse each (a signature costs about 30 µs to check *(docs)*); the node is refused as a whole after the first of its own | 6 | sim: `a_refused_node_costs_little` |
| 133 | Writes its own member entry without end; signs and gives up without end; fills the waiting changes; sends changes that say they saw little, each to be judged far back | Take them no faster than a budget per party (changes, bytes and operations an hour): put off, never refused; a share of the waiting each | 6 | sim: `a_party_past_its_budget_waits` |
| 134 | Starts a writer with every change: each costs every node memory in proportion to the document's history | Past `limits.writers` a user and epoch, every node puts off the changes that start more of the nodes whose writers count for it: a node's, for the user its member entry names. Nothing is refused; what reaches a node within others' histories is held, and a remake leaves it out. A user below a root costs the root nothing, and one beside others on a node costs them nothing, but where the node's entry names it | 6; not bounded | sim: `writers_past_their_limit_wait` |
| 135 | One of the users a node carries for, besides the node's own, starts writers past its limit, from nodes of its own | The node's writers count for the user its member entry names, over a remake too, and nothing of it is put off for the others: the users beside it write on | 6 | sim: `writers_count_for_the_user_an_entry_names_beside_others` |
| 136 | Signs its `node` statement naming another party's node again and again until its digest is the lowest, so that the node's writers count for it after a remake, then starts writers past its limit | A node's writers count for the user its member entry names, the node's own word, carried over a remake; the digest decides only where the entry names none | 6 | unit: `writers_count_for_the_user_an_entry_names` |
| 137 | Sends a node a change of the node's own writer, another value, to make it start a writer | Refused as forged; the node switches only where its own key signed it (a copy of its files) | 6 | unit, exists: `another_writing_as_this_node` |
| 138 | Crafts a first change of another node's writer, authored as a third node, to sort before the writer's own in a batch, so that screening judges the writer's changes as the third node's | Screening names a change's node by its own author, or that of its actor's first change in its own history, never by another change of the batch: the writer's changes are vouched for by their own node's signature, and the crafted one, a second first change of the writer, is refused as forged | 1, 2 | unit, exists: `a_committer_from_its_own_history` |
| 139 | Sends a change of a few bytes that holds a million operations | Taken, at the cost of applying it, against its party's budget, which counts operations: the party's next changes wait until it is paid | 6; not promised (a bound on what an epoch's document costs) | argued; sim: `a_party_past_its_budget_waits` |
| 140 | Claims and releases a name a minute, by many users, to have every root's node write for each | A root's node writes once a `witness` at most, for all claims that reached it meanwhile, and takes the party's claims at its budget's pace | 6 | unit: `a_root_witnesses_once_a_witness` |
| 141 | Crafts a change Automerge won't take, or that writes in an object nowhere to be found | Refuse *(checked: the rules refuse the second today)*; only the message that brought it fails | 1 | unit: `a_change_writing_nowhere` |
| 142 | Crafts a change Automerge takes and shouldn't: bytes it wouldn't encode itself, operations numbered against its dependencies', a gap in its actor's changes, an operation named that is elsewhere or outside its history, an operation Automerge's transactions never write (an element written over naming the one inserted after it, an insert that replaces, a deletion or an increment inserted, a deletion named as replaced), a table written into, a value written at a mark's begin | Refuse before Automerge sees it, by the change and its own history alone: applied, such a change makes a node panic, save a document that doesn't load, or part from nodes it reached in another order | 1, 2 | unit, exist: `bytes_automerge_wouldnt_encode_are_refused`, `operations_numbered_against_their_dependencies_are_refused`, `a_gap_in_an_actors_changes_is_refused`, `operations_named_at_the_wrong_place_are_refused`, `operations_outside_a_changes_history_are_refused`, `only_what_transactions_write_passes`, `only_what_holds_a_value_is_replaced`, `no_table`, `no_mark`, `what_passes_leaves_automerge_sound`, `a_batch_is_checked_against_itself`, `a_change_refused_after_its_check_stands_in_for_nothing` |
Rules, and the swarm as it is:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 143 | A rule differs between versions (a bug) | Each side refuses what the other takes, or their stamps name two digests for the same changes: each logs and shows it. A node that finds itself apart from the nodes of more than two thirds of the other voters at its first start with a version writes nothing. One side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back`, `two_digests_one_history`; unit: `a_node_checks_itself` |
| 144 | Stamps a wrong digest, to keep the nodes that upgrade from writing; one of three voters does | A node stops only where it differs from the nodes of more than two thirds of the other voters; from fewer it shows it and goes on | 6 | unit: `one_wrong_digest_stops_nobody`, `of_three_voters` |
| 145 | A policy version a node doesn't know: in the root, or decided | It doesn't sync, and takes no such proposal up: a policy is decided only with two thirds of the voters' nodes knowing it | 1 | unit: `no_sync_under_an_unknown_policy`, `an_unknown_policy_isnt_taken_up` |
| 146 | A partition, for any length of time | A side decides only with nodes of two thirds of all the voters on it. Where a third of them have nodes and votes on both sides, both may: every node then acts on the higher number | 7 | sim: `one_side_decides`; unit: `the_last_holds` |
| 147 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` |
## The registry on it
```
_continuum/users/tv/<digest> statements about and by tv
_continuum/claims/ip4/10.243.0.7/<digest> tv's claim of 10.243.0.7
_continuum/claims/name/r/<digest> a root's claim of the top-level domain r
tv/hosts/toaster envelope: {"nets": {"retiolum": {
"ip4": "10.243.0.7", "ip6": "42:0:…",
"aliases": ["toaster.tv.r"],
"ed25519": "…" }}}
```
The kinds are those shown under Claims, each name written as the hosts use it, in
lower case. `toaster.tv.r` is kept for tv by the kind's rule and needs no claim; tv
claims it all the same if it wants it through a change of the rules. A name that is
no user's, right below the top-level domain (`wiki.r`), is the voters' to give: a
proposal names it and a user, and decided, that user holds it. An IPv6 address is
generated from the net, the user's name and the host's today; a kind `ip6` with the
separator `:`, first come, first served like `ip4`, holds whether or not anyone
generates honestly, for addresses written out in full. The export reads an address
or a name only in the one spelling it writes.
**Moving in.** The genesis change is made from the repository by a script
(`scripts/kartei-import`): the kinds and their rules; the maintainers as the roots and
the first voters, with their keys and nodes; and for each namespace of the repository
a user without keys, its hosts as they are, plain, and their addresses as claims in
its name. The genesis change is trusted as it is (every party is given its hash), so
what it holds counts without signatures: a host it holds counts until its user signs
over it, and a claim it holds is its user's. The root the genesis change names for
each user gives it its first keys as it comes; from then on the user signs its own,
and votes once a decision lists it. A namespace whose user never comes stays as the
genesis change has it.
What to weigh, moving in. With one maintainer as the only root and voter, that one
settles every claim, decides alone, and sees alone what a third of the voters see,
until it decides on others: more than one from the start is better, and a first
list of voters once the users that take part are there. A user that comes later is created
by one root, who takes that back alone; another's vouch makes it stand without that
root's word.
The limits in the genesis policy: 64 keys, 64 nodes and 256 addresses a user for a
start. The import may set keys and addresses to twice the most any user has in the
repository; a decision changes them after.
**Writing out.** `scripts/kartei-export` reads the resolved registry from a node its
operator trusts (its own) and writes the tree the consumers read
(`<user>/hosts/<host>/retiolum/{aliases,ip4,ip6,ed25519.key}`), leaving out what
doesn't count and any address or name its host's user doesn't hold. Run on each
change of the document (the store's stream), it replaces the merge button. An
operator that leaves users out when it reads writes other files than one that
doesn't, where a name is contested: what the network at large reads is whose node
it trusts for that.
## Stages
Each leaves the system working, and is a few patches with its tests, which leave
their vectors. At every stage the existing tests pass untouched (147).
1. **A federated swarm's frame.** `--genesis-policy` (a file, written into the genesis
change with the roots, the voters and the users it starts with); a federated node
is given its root change, syncs under no policy it doesn't know, takes no remake
yet, takes tokens and logins by key as its operator says, keeps ended sessions to
itself, stamps as the policy says, and writes a member entry of the policy's shape
and size. What the genesis change sets for the swarm as a whole is read from the
policy. Tests: 128 to 131, 138, 142, 145, 147, and the policy's existing tests
under a policy from the genesis change. Those of a crafted change, and of a crafted
committer, exist already: screening refuses those in every swarm.
2. **Statements.** The users' registers (`create`, `key`, `node`, `vouch`, `release`);
the user ID, the epoch and what its signer saw in an envelope; nodes carrying for
users by their own word, and the rule for committers by it; nothing plain; the
limits, and the order past them. First, the payloads: each statement's fields and
the member entry's shape, settled, so that tests leave vectors. Resolving, step 2
without cuts, and `GET /registry/users`. The client signs statements. Tests: 1 to
7, 9, 12, 13, 19, 20, 23, 36.
3. **Namespaces.** The rule, with `userSigned` below a name. Tests: 35, 37. From here
the registry runs with users and hosts, names not yet unique.
4. **Claims in sight.** Kinds, names as they are written, their characters, rules by
their structure, kept names and claims of them, limits, `claim` and `release`,
judged as written; resolving step 4 for claims in sight, and what comes back.
Tests: 21, 39, 42 to 44.
5. **Out of sight.** Late, contested and settled, for names and for users' names; a
claim's side; a root's node writing when a claim reaches it, and a node that comes
back catching up first. The voters as the root change names them; lengths of time
read from the stamps; final. `GET /registry/claims` with what makes a claim late;
values marked in `GET /store`. A node keeps its seeds and its user's other nodes as
neighbours, leaves out members that name another epoch, and shows a claim long
unsettled. Tests: 8, 10, 11, 14, 15, 17, 18, 38, 40, 41, 45 to 48, 51, 54, 55, 124,
126, 127.
6. **Cuts.** `retire` and the keys above, a node that stops, a cut never reaching its
own statement, what a cut takes back, what doesn't count left out, the value before
read again, what stopped counting for good, the client listing what stopped
counting. Tests: 16, 22, 49, 50, 53, 56 to 60, 67, 68, 112.
7. **Unvouching.** `unvouch`, a vouch or a creation cut off as by an unvouch, a user
giving itself up, one that another vouched for staying, those brought in going with
it, the names of a user that is out waiting, gone, nothing taken from an unvouched
user's nodes, what comes back with a vouch. Tests: 24, 26 to 31, 33, 34, 61 to 64,
66, 98 to 105.
8. **Coming back.** The drop an operator asks for, a forked actor proven and shown
with what the roots' nodes hold, the budget and the share per party, the writers
counted per user, for the one a node's member entry names, a node keeping its
writer over a clean stop. Tests: 125, 132 to 137, 139 to 141.
9. **The registry.** Import, export, and a federated swarm of the simulations with the
registry's kinds and a few hundred hosts. From here it can be tried: users, hosts,
names, a root that settles, names that become final. It isn't to be relied on yet.
The stages after change the rules, and until a policy changes by a decision a rule
changes only by every party upgrading at once: a swarm started here is started anew
after the last stage, by an import of what it holds.
10. **Decisions.** `propose` and `vote`, signed by the client and taken from any node,
the nodes' records and how they are judged, taking up, decided, the decision that
holds, what hangs; `GET /registry/decisions`. What is decided: who votes, who the
roots are, a number, a user's first keys, the names of a user that is out, whose a
contested name is, a name the rules leave to the voters; a decision of the voters
before counted only in sight of the list that replaced them; a final decision. The
simulations start from a root change naming several voters. Tests: 25, 65, 69 to
88, 116, 117, 146.
11. **Versions.** The digest with every stamp, a node checking itself before it
writes; for every swarm, a node that speaks the wire version before its own, and a
handshake that says which epochs its node keeps. Tests: 143, 144.
12. **Remakes.** Compaction only; a node proposing and acking by `remakeChanges` and
`remakeWriters`, and following such a remake only, by its result; the snapshot
every node builds, with whatever can still count and how far each length of time
ran, what it leaves out and what can't be written again; carrying over: every
node's carry record, then each envelope from any node, in its order, with the new
epoch's word last on values, and a claim carried over against the snapshot's; a
retirement's list as its cut; decisions over a remake; lengths of time going on;
two remakes of an epoch, to the lower ID. A node keeping the epochs it left on
disk, peers answering for them and saying which; a node walking them, or rejoining
by an ID its operator gave, and by none that peers advertise. Tests: 91 to 97, 106
to 111, 113 to 115.
13. **The policy by a decision.** The policy as a matter, a node that doesn't know it,
what it no longer covers: shown aside, taken away by its user only, dropped after
a time, moved at a remake. Tests: 32, 52, 89, 90, 145.
14. **Going apart, and refusing.** A fork followed by an operator's word, with who
votes and who the roots are on its side. Refusing a decision: a node's bounds, the
epoch without the decision, what a node takes along. Tests: 118 to 123. From here
it can be relied on: the rules change by decisions.
## What was checked, and what is assumed
Checked in the code:
* A change is judged at its dependencies, or at heads that hold the same for what
rules read, before it is applied; a refused change keeps out what builds on it; a
member whose own change broke a rule is refused as a whole (`access::rules`,
`access::screen`).
* What screening takes as read by rules is a list: members, users, remakes, votes,
access and bans (`screen::relevant`).
* An envelope is checked for its swarm, path, `prev`, signature, and its user's key
in the registry as the writer saw it (`access::envelope::check`).
* The genesis node writes the users it starts with and their keys, the swarm ID, and
what holds for the swarm as a whole (neighbours, topology, dissemination) in its
first change (`swarm::bootstrap`, `document::meta`), so the policy can be written
with them.
* A node writes anything below its own member entry (`access::rules`); readers bound
what they take of it, not what is stored (`swarm::members`); a snapshot copies
every entry there is (`remake::snapshot`). A shape and a size are new.
* A member's entry holds its alive stamp as Unix milliseconds. It is renewed every
seventh of the shortest window any member publishes in its entry, an hour at
least, which is daily by default (`swarm::members`). A renewal overwrites the
stamp, so two stamps of one node are two changes, found in the history; nothing
reads them so today.
* Screening names a change's node by the change's author, or that of its actor's first
change in its own history, never by another change of its batch, and counts no
actors (`access::screen`). A limit on writers is new.
* A drop exists and does what coming back needs (`AppState::drop_taken`); what is new
is an operator asking for one its own rules wouldn't make.
* Neighbours are computed from the member list by key hashes (`swarm::topology`); a
member that answers from another epoch isn't left out of them.
* A second change at an actor's number is refused as forged, by whoever brought it
(`document::signatures`, `access::screen`). Keeping both as proof is new.
* A message of another wire version is ignored whole (`transport::wire`).
* A node keeps the documents of the epochs it left in memory (`remake::local`).
Keeping them on disk is new.
* The quarantine is in memory, and holds paths and values of the node's own writes
(`docs/remakes.md`); a replay writes state by path, the last writer winning
(`remake::delta`). A quarantine on disk that holds envelopes, anyone's, and every
node writing again the envelopes it holds after a remake, are new.
* The relays are read from `_continuum/relays`, which an operator lists
(`document::meta`, `swarm::members`); the genesis change doesn't set them. A
federated node reads them from its configuration alone (`--libp2p-relays` exists).
* A snapshot records the highest number per actor in its base, by which a node tells
what it holds beyond it (`remake::snapshot`, `remake::delta`). A federated node tells it
from the changes beyond the base, which it holds.
Checked upstream, in Automerge 0.12: a second change at an actor's number is refused,
with the whole batch it came in (`DuplicateSeqNumber`); the change that made an
operation is found (`hash_for_opid`), so the change carrying a value is found from
the document.
Measured upstream, with Automerge 0.12.0 alone, on histories of small writes to a map:
* It applies a change that lists an actor none of its operations names, and then
gives back another change under that hash and saves a document that doesn't load;
where the document doesn't hold that actor, applying panics. It applies a change
whose first operation is numbered below its dependencies', and the save doesn't
load; one numbered 2^32 − 1, and the node's next write panics.
* Every writer costs heap in proportion to the history. A document of 10^5 changes
takes 42 MB with 10 writers, 79 MB with 100 and 435 MB with 1000, where the nodes
write in turn: a slot of 4 bytes per writer in every clock Automerge caches, which
there is one for most changes, and one for every 16th at best.
* With an actor for every change, heap and time grow with the square of the changes:
32 MB at 10^4 changes and 2.7 GB at 10^5 for a line of them, eight times that at
10^4 where each change also builds on its node's change before it; 2 to 20 ms to
apply one more change at 10^4, 0.16 s at 10^5. An actor that is the hash of its
change with the actor zeroed is made with the public API and checked with one
hash; two changes a node writes on the same change of its own are then both held,
with the same values in the same order whichever came first.
From the docs: a node under an unknown policy receives without judging; every node
takes a token any member signed, and lets in by key any user of the registry; where a
refused member shows; the cost of checking a signature; a node keeps the documents of
epochs it left for a while (`archiveRetention`: 2 epochs, 30 days), and every node
builds a remake's snapshot itself today; a coordinator fixes the electorate in its
proposal; a node that was away rejoins the epoch enough ready members advertise, and
has its own writes carried over within the replay window, the rest quarantined; a
member votes for one remake of its epoch at a time, and a compaction's base is fixed
by the coordinator when it commits.
Assumed, to be shown as it is built:
* Whether a change is in the history of a cut, of what a statement says its signer
saw, or of a witness's change, can be answered cheaply enough: per actor, the last
number within that history, kept per cut and per claim that has a rival.
Statements and rivals are few.
* Resolving kept as the node goes costs little per change. Judging a change that
says it saw little reads far back: the registers there, who was gone there, which
decisions were decided there (`document::at`), more than an envelope's check reads
today. Whoever makes others do that pays from its party's budget.
* Whether a claim stood in a witness's history is kept as the node goes, for the
claims that have a rival.
* Writing a quarantined statement again as it is works after a drop wherever what it
builds on still holds.
* A node can keep neighbours beside those the member list gives (its seeds, its
user's other nodes), and leave out members of another epoch.
* A limit counted at a change's dependencies (a kind's claims by one user) is read
fast enough from the register; an index kept beside it otherwise.
* Who lost a user name as a change's history shows it (judging, 6 and 7) is worked out
only where a name has several creations there, which is rare.
* The snapshot of a federated remake, built from the resolved registry, comes out
byte for byte the same on every node, as today's does from the document.
* A node can keep on disk, and answer sync for, an epoch it left.
* A node can commit its carry record (the digests of what it holds beyond a base, and
what it held of it) before it takes anything from a peer, at a registry's size.
* What was seen for long is kept as the node goes, per voter's node and per thing
watched (a user out, a claim holding its name, a decision holding, a thing
uncovered), costs little, and is built again from the changes and the snapshot at
a start; the snapshot holds it at a registry's size.
* The digest of the registry as it resolves is cheap enough to make with every stamp
at a registry's size, and to make at another node's stamp now and then.
* A version can speak the wire version before its own.
* A node can keep, with the document, when it received each change, at a registry's
size.
* A node counts the writers each user's nodes started in the epoch as it takes their
changes, cheaply enough: a count kept per user.
* What is asked of a change before Automerge sees it keeps out every change it applies
and shouldn't. Changes are generated against it
(`what_passes_leaves_automerge_sound`); batches, changes on older states and chunk
bytes only outside continuum so far.
|