forked from BlockstreamResearch/codex32
-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathSSS32.ps
4167 lines (3835 loc) · 122 KB
/
SSS32.ps
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
%!PS-Adobe-3.0
%%Orientation: Portrait
%%Pages: 39
%%EndComments
%%BeginSetup
[(Shamir's Secret) (Sharing Codex)]
(revision alpha-4.6)
[
(MIT License)
()
(Copyright (c) 2020 Blockstream)
()
(Permission is hereby granted, free of charge, to any person obtaining a copy)
(of this software and associated documentation files (the "Software"), to deal)
(in the Software without restriction, including without limitation the rights)
(to use, copy, modify, merge, publish, distribute, sublicense, and/or sell)
(copies of the Software, and to permit persons to whom the Software is)
(furnished to do so, subject to the following conditions:)
()
(The above copyright notice and this permission notice shall be included in all)
(copies or substantial portions of the Software.)
()
(THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR)
(IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,)
(FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE)
(AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER)
(LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,)
(OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE)
(SOFTWARE.)
]
[
(WARNING: Seriously, this is a work in progress, and it is only a concept right now.)
(If you try to use this for your valuable data, I promise you will lose your data.)
(You will lose this document and come back here only to find that I have made incompatible changes,)
(and your data is lost forever. Even if you don't lose this document, there is no warranty or)
(guarantee of any kind that you will be able to recover successfully recover your data.)
]
%************************************************************************
%************************************************************************
%*
%* Section One: Preamble
%*
%************************************************************************
%************************************************************************
%******************
%* Front matter
%*
%* Define variables for the preceeding front matter text.
%*
/warning exch def
/MIT exch def
/ver exch def
/title exch def
% PHP detection
/phpOn false def
% <?php echo "\n/phpOn true def"; ?>
%******************
%* Main text content
%*
/allPageContent [
[ ] % dummy so we can 1-index the array
[
/section (Overview / Cheatsheet) /endsection
/notoc % turn off table of contents indexing
/dropcap (C) (ryptography is the art of hiding information. In particular, Shamir's)
(Secret Sharing Scheme (SSSS) is used to hide secrets in a distributed way.)
(A secret is split into multiple parts, called shares, that can be given)
(to different people or kept in separate places. The)
(shares can then be used to reconstruct the original secret. For the)
(wizards in the Bitcoin community, SSSS can be used to hide the single BIP32 master)
(seed from which all their private keys are derived.)
/paragraph
(This codex describes a way for users, assisted by paper computers in the)
(form of slide charts \(volvelles\) and circular slide rules, to perform)
(checksums and SSSS on Bitcoin secrets.)
/subsection (Assembly) /endsubsection
(*You will need*: craft knife, scissors, cardstock or heavy paper, brass fasteners, disc printouts) /linebreak
(Using the printouts from Module 0 \(which have pictographic instructions\),)
/startlist
/listitem1 (Cut out each disc with scissors. Cut out the windows on the top discs with the craft knife.) /endlistitem
/listitem1 (Cut out the small centre circle in each bottom disc.)
(Cut a slit along one of the small lines of the cross in each top disc.) /endlistitem
/listitem1 (Attach the discs with a brass fastener through the centre holes.) /endlistitem
/subsection (Initial \(First $k$\) Share Creation) /endsubsection
(*You will need*: Addition Volvelle, Random Character Worksheet, Checksum Worksheet, pencil and eraser)
/linebreak
(For each of your initial $k$ shares, you should)
/startlist
/listitem1 (Generate random data by rolling dice, following the instructions on the Random Character Worksheet.) /endlistitem
/listitem1 (Follow the instructions on the Checksum Worksheet to affix a checksum.) /endlistitem
/subsection (Derived \(Remaining\) Share Creation) /endsubsection
(*You will need*: Addition Volvelle, Multiplication/Translation Wheel, Translation Worksheet, pencil)
/startlist
/listitem1 (Translate the initial shares using the symbols in the Derived Shares section) /endlistitem
/listitem1 (Add the translated initial shares to get the new derived share.) /endlistitem
/subsection (Secret Recovery) /endsubsection
(*You will need*: Everything used for Derived Share Creation \(see above\), Recovery Wheel)
/linebreak
(To recover your secret you must have $k$ shares available. Then)
/startlist
/listitem1 (Look up their recovery symbols with the Recovery Wheel.) /endlistitem
/listitem1 (Multiply all the symbols for each share with the Multiplication Wheel to get)
(a single symbol for each share.) /endlistitem
/listitem1 (Translate the share by that symbol.) /endlistitem
/listitem1 (Add all the translated shares to get your secret.) /endlistitem
/toc % turn off table of contents indexing
] [ % pagebreak
/section (Part I: High-Level Introduction) /endsection
/notoc % turn off table of contents indexing
/dropcap (T) (he SSSS Codex describes a way, using circular paper computers)
(\(volvelles\), to perform checksumming and Shamir Secret Sharing on their)
(Bitcoin secrets. It defines an error-correcting code, *codex32*, and a)
(complete scheme for generating, checksumming, splitting and reconstructing)
(secret data.)
/paragraph
(Hand-computation comes with some practical limits: to generate random values)
(we rely on series of (de-biased) dice rolls. We do not support passphrases)
(or key hardening, so our security rests solely on the strength of this)
(randomness. With that said, assuming you can generate strong randomness,)
(you will find no cryptographic compromise in the design or implementation)
(of the Codex.)
/paragraph
(If you prefer the added security of passphrase-based key hardening, you)
(should instead use the more-popular SLIP39, which requires the use of electronic)
(computers.)
/subsection (Bitcoin and Seed Values) /endsubsection
/dropcap (W) (e assume that your secret is a 128-bit BIP32 master seed. Such)
(seeds are used to derive an effectively unlimited number of addresses from a)
(single secret value, eliminating the need for frequent backups.)
/paragraph
(Many users interact with BIP32 master seeds indirectly, for example by storing)
(a set of 12 or 24 BIP39 seed words. These seed words represent a 132- or)
(264-bit secret, which is converted in the BIP39 protocol to a pointlessly)
(large master seed by means of a needlessly complicated and irreversible)
(process. If your coins are stored using BIP39, we have provided a module to)
(assist converting the seed words to binary \(and back\) so they can be used)
(in the Codex in lieu of a master seed. The longer data greatly increases the)
(tedium and risk of mistakes, but the procedures are essentially unchanged.)
/paragraph
(In general, we encourage you to switch from BIP39 to Satoshi Labs' SLIP39,)
(or even better, to directly use the Codex to work with 128-bit BIP32 seeds.)
/subsection (Shamir's Secret Sharing Scheme) /endsubsection
/dropcap (T) (here is an inherent trade-off between the availability of a)
(secret and its risk of theft. If you make many copies of your seed words,)
(one of them may eventually fall into the wrong hands. But if you make too)
(few, they may all become lost, destroyed or misplaced. The consequence in)
(either case is a total loss of funds.)
/paragraph
(A more nuanced way to make this trade-off is Shamir's Secret Sharing Scheme)
(\(SSSS\), in which you split your secret into $n$ "shares", any $k$ of which)
(can be used to reconstruct the original secret. Here $n$ is typically five)
(or more, depending on your desire for redundancy, while $k$ is two or three,)
(reflecting your fear of individual shares being compromised.)
/paragraph
(Before continuing, we should mention some limitations of SSSS:)
/startlist
/listitem* (First, electronic computers or not, SSSS requires that the)
(complete secret be reconstructed in a single place before it can be used.)
(To avoid this, for most use-cases we recommend threshold)
(signatures instead.) /endlistitem
] [ % pagebreak
/startText
/listitem* (SSSS requires the generation of extra random data beyond the)
(original secret, which must be generated securely. If any share is corrupted,)
(the reconstructed secret will be wrong and it is impossible to determine)
(which share \(or how many shares\) was responsible.) /endlistitem
/paragraph
(We have addressed the latter issue by the clever use of error-correcting codes,)
(inspired by SLIP39, but the fact remains that SSSS involves a single point of)
(failure at the time that the secret key material is actually used. We emphasize)
(that SSSS is a *mechanism* *for* *storing* *backups* and not a mechanism for enforcing)
(a signing policy.)
/subsection (Computers and Trust) /endsubsection
/dropcap (I) (t is infeasible to sign Bitcoin transactions without the aid of)
(electronic computers. To do this, these computers need access to secret key)
(material, which puts you in an uncomfortable position: key material, if)
(misused or badly generated, can be used to steal all of your coins. And)
(there is no way to be assured of how, exactly, an electronic computer is)
(manipulating your keys.)
/paragraph
(General-purpose computers are so complex and exposed to adversarial input)
(\(in the form of Internet connections, arbitrary programs, and human beings\))
(that standard advice is to never expose your key material to such machines.)
(Instead, you should provide your keys only to hardware wallets, which)
(interact with general-purpose computers only through a narrow interface that)
(never exposes secret key data in any form.)
/paragraph
(However, even hardware wallets are opaque and inscrutable:)
/startlist
/listitem* (they may have bugs which cause key leakage, either now or as a)
(consequence of some future firmware update;) /endlistitem
/listitem* (they store key material in physical form which can be extracted)
(by an attacker with physical access, even if it the wallet has "deleted")
(it;) /endlistitem
/listitem* (they may expose data through sidechannels, such as the)
(electromagnetic waves emitted by processor activity, or by the varying)
(power draw from a USB hub;) /endlistitem
/listitem* (if tasked with generating random data, they may do so insecurely.) /endlistitem
/paragraph
(Furthermore, when working with secret shares, it is necessary to directly)
(export share data, violating the usual "never expose secret data" maxim.)
(This introduces more questions: how can the hardware wallet be sure that)
(it is communicating only with the correct user, and under correct)
(circumstances? It cannot.)
/paragraph
(These risks have varying degrees of plausibility, but the fact is that no)
(matter how trustworthy the hardware or its manufacturer, over the lifetime)
(of a Bitcoin secret \(which may, perhaps, exceed any one human's lifetime\),)
(even "trivial" risks add up to become very serious.)
/paragraph
(Unlike electronic computers, paper cannot remember or leak secrets, at least)
(when handled correctly and disposed of securely, and this can be done without special skills)
(or equipment. In this document, we have provided a paper-based means to)
/startlist
/listitem* (Securely generate random data from potentially biased dice rolls or coin flips) /endlistitem
/listitem* (Compute and verify very powerful checksums) /endlistitem
/listitem* (Split your secret into up to 31 "shares", of which some number are)
(needed to reconstruct the secret) /endlistitem
/listitem* (Recombine your secret, perhaps to redo the splitting if some old)
(shares are compromised) /endlistitem
] [ % pagebreak
/startText
(In this way, coins which do not need to be frequently spent may have their)
(secure storage refreshed or reorganized an unlimited number of times, without)
(ever introducing the uncertainty and risk associated with electronic computers.)
/subsection (Checksumming and Error Correction) /endsubsection
/dropcap (W) (hen you copy or transfer keys, or especially when you are doing)
(hand-computations on them, it is possible that errors may arise. Errors)
(might also crop up during long-term storage, for example if Cryptosteel)
(tiles are subjected to extreme heat which makes some letters unclear, or)
(if printer paper suffers water damage.)
/paragraph
(Both BIP39 and SLIP39, in addition to encoding the raw cryptographic data,)
(also store a checksum, which is a small amount of extra redundant data used)
(to detect such errors. BIP39's checksum is less than one word long, may fail)
(to detect even a single incorrect word, and is practically impossible to)
(compute by hand. Its primary effects are to cause your key data to be an)
(awkward length, and to prevent you from verifying your data's integrity by)
(hand.)
/paragraph
(SLIP39, by contrast, can detect up to 3 errors and correct up to one error)
(100% of the time, and will fail to detect other random errors with extremely)
(low probability. However, the SLIP39 checksum is also quite difficult to)
(compute or verify by hand.)
/paragraph
(In the Codex, we introduce a new checksum, *codex32*, which can detect up to 8)
(errors, correct up to 4, and has even lower probability than SLIP39 of failing)
(to detect other random errors. Most importantly \(for us\), codex32 checksums)
(can be computed and verified entirely by hand. It is even possible to $correct$)
(errors by hand, but you will need to consult a mathematician since we have not)
(found a simple worksheet-based method.)
/paragraph
(If error correction is needed, a later version of this document will explain)
(how to do so, with the assistance of an electronic computer which is never)
(given access to secret data.)
/subsection (Bech32 and the Alphabet) /endsubsection
/dropcap (I) (n order to store 128-bit secrets, we re-use the Bech32 alphabet)
(which provides 32 5-bit characters. These characters consist of the 26)
(letters of the Latin alphabet and 10 Arabic numerals, except B \(which looks)
(like 8\), O \(which looks like 0\), and I and 1 \(which look like many things,)
(including each other\).)
/paragraph
(We also use an alternate alphabet, consisting mostly of Greek letters, which)
(is used for intermediate computations. It is never used for storage, and)
(nothing represented in this alphabet is ever secret data. We have provided)
(a table of pronunciation, on the Reference page at the beginning of this)
(document, to help with its use.)
/paragraph
(The remainder of this document provides detailed, but mechanical,)
(instructions. If you are interested in learning the mathematical theory behind)
(this all, we encourage you to check out the mathematical companion, or to)
(contact Pearlwort at `pearlwort@wpsoftware.net`.)
/toc % turn on table of contents indexing
] [ % pagebreak
/section (Part II: Detailed Instructions) /endsection
/subsection (II.1. Tables or Volvelles) /endsubsection
/dropcap (H) (and computation for the procedures in this document can be)
(performed either by using the Principal Tables to look up values, or by)
(using volvelle wheels to look up values. While the volvelle wheels take)
(time to cut out and assemble, they are generally easier to use than the)
(tables when available.)
/paragraph
(There are three volvelles in this codex, which have slightly different usage)
(instructions.)
/paragraph
(*Addition.* To add two characters, turn the Addition Wheel to one of them,)
(and look through the window corresponding to the other. It does not matter)
(which character is which; addition is symmetric.)
/paragraph
(*Translation.* A common task is to "translate" share data by a given recovery)
(symbol. To do so, turn the Translation/Multiplication Wheel so that the window)
(on the Multiplication side is showing the correct symbol. Then turn the wheel)
(over; the Translation side will act like a decoder ring, mapping characters)
(to characters.)
/paragraph
(*Multiplication.* Sometimes you will need to translate a share by multiple)
(symbols at once. To do this, turn the Multiplication Wheel to the first symbol.)
(Find the next symbol on the inner wheel; whatever symbol it is pointing to,)
(turn the Multiplication Wheel to that symbol. Repeat for all the symbols you)
(need to multiply; the Multiplication Wheel will wind up at the final product.)
(You can now turn the Wheel over to translate by this symbol.)
/paragraph
(As with addition, it does not matter which order you take your original symbols)
(in.)
/paragraph
(*Recovery.* When recovering your secret, you will need to look up "Recovery)
(symbols" that will be used to. To do this with the Recovery Wheel, turn the)
(wheel to the share you want to translate. Mark down the symbols pointed to)
(by the $other$ shares' indices, and multiply these together.)
/paragraph
($Important:$ Unlike the other wheels, the Recovery Wheel can easily be used)
(in the wrong order. Be careful!)
/subsection (II.2. Share Format) /endsubsection
/dropcap (F) (or 128-bit secret seeds, each share is 48 characters long.)
(Shares begin with the three character prefix `MS1`. This is followed by a)
(six character header. The next 26-characters are the data portion. The last)
(13-characters are the checksum.)
/paragraph
(The header consists of:)
/startlist
/listitem* (The *threshold* which is the value $k$, a digit between)
(`2` and `9` inclusive, although the main document only supports $k$ values `2` and `3`. When)
(secret splitting is not used, a `0` digit is placed here instead.)
/endlistitem
/listitem* (The *identifier* which is four bech32 characters.) /endlistitem
/listitem* (The *share index* which is any bech32 character except for)
(`S`. The `S` index is the *secret* *index*. The data portion of the)
(secret index contains the secret seed.) /endlistitem
] [ % pagebreak
/startText
%| Human-readable Part | Threshold | Secret ID | Share Index | Secret data | Checksum |
%|---------------|--------|---------|--------|----------|----------|
%| 3 characters (`ms1`) | 1 character | 4 characters | 1 character | 26 characters | 13 characters |
/paragraph
/paragraph
/paragraph
/paragraph
(Shares of one secret all have the same threshold and identifiers. If you)
(have multiple secrets, you should use distinct identifiers for each secret)
(so as not to mix-up shares of different secrets with each other. The)
(identifiers are not considered secret themselves.)
/paragraph
(If the user merely wants to checksum her secret, and not use secret splitting,)
(she should use the same format, but with the digit `0` for the threshold value)
(and `S` for the share index.)
/subsection (II.3. New Secret Seed) /endsubsection
/dropcap (G) (enerating a $k$-of-$n$ scheme for a new random secret is most)
(easily done by generating fresh random shares directly. This process generates)
(a new random secret seed without directly revealing it.)
/paragraph
(The process for generating a new secret seed is as follows.)
/startText
/startlist
/listitem1 (Choose a threshold $k$ and total number of shares $n$ that suits)
(your needs. The threshold $k$ must be 2 or 3 and $n$ must be 31 or less.)
(\(For $k$ > 3 see Module 2, but we do not recommend this.\))
/endlistitem
/listitem1 (Choose a 4 character identifier for your new secret seed. The)
(identifier can be anything as long as it only uses the Bech32 character set.)
(The identifier itself is not secret. However, the identifier should be)
(unique for each secret seed.) /endlistitem
/listitem1 (Follow Section II.3.a to generate the first $k$ shares.) /endlistitem
/listitem1 (Follow Section II.3.b to generate the remaining $n$ - $k$ shares.) /endlistitem
/listitem1 (Load your shares into your BIP-????) /footnotemark (compliant wallet or use the)
(Recover Secret Seed procedure in Section II.4 to access your new secret seed)
(value.) /endlistitem
/listitem1 (Copy and distribute your $n$ shares into safe and secure locations.)
(Remember that you will need to recover at least $k$ of these shares to)
(recover your secret seed. Also remember that anyone else who recovers $k$ of)
(these shares can also recover your secret seed.) /endlistitem
/listitem1 (Securely dispose of all worksheets you used in the generation)
(procedure. If these worksheets are not securely disposed of, they could be)
(used to recover your secret seed.) /endlistitem
/subsubsection (II.3.a. New Secret Seed: Stage 1) /endsubsubsection
(Make 2$k$ copies of the Checksum Worksheet and save half of them for later.)
/paragraph
(Fill out the header portion of $k$ many Checksum Worksheets with your chosen)
(threshold $k$ and chosen ID. Place a unique share index on each worksheet)
(starting with share `A` on the first worksheet, `C` on the second worksheet,)
(and so on through the $k$ first characters from the Bech32 character set.)
(\(Note that `B` and `I` are not part of the Bech32 character set and are)
(omitted\). However, if you are not splitting your secret, \(i.e. $k$ = 1\))
(see the special instructions below.)
/footnotes
/footnotemark (Once we have a BIP number for codex32, we will replace "BIP-????" throughout the document.)
] [ % pagebreak
/startText
(Fill out the 26 character data portion of each Checksum Worksheet with random)
(characters. Use the Random Character Worksheet to generate each random)
(character.)
/paragraph
(Follow the Checksum Worksheet instructions to generate a checksum for each)
(worksheet.)
/paragraph
(*Critical Step:* Verify your checksum by copying each of the 48 characters)
(of the share onto an empty worksheet that you saved earlier. Follow the)
(checksum verification instructions to verify each checksum. If any checksum)
(fails to verify then make more copies of the Checksum worksheet and redo the)
(checksum generation and checksum verification steps again.)
/paragraph
(*Failure to verify each checksum may lead to irrecoverable loss of)
(the secret seed and funds.)
/paragraph
(*Special rules for $k$=1:* If you are not splitting your secret, then use)
(a `0` digit in the threshold place, and use the `S` character in the share)
(index place. Follow the same instructions for generating the data portion)
(and the checksum.)
/subsubsection (II.3.b. New Secret Seed: Stage 2) /endsubsubsection
(The remaining \($n$ - $k$\) shares are derived from the first $k$ shares using the)
(translation worksheet corresponding to the $k$ value you have chosen. Label)
(the entries of the translation worksheet with the share indices that you will)
(use. We recommend following the Bech32 character order following the)
(last index you generated in Stage 1.)
/paragraph
(Use the following procedure to derive a new share:)
/startlist
/listitem1 (Make a copy of the Translation Worksheet for the value of $k$ that)
(you are using and label the shares with the share indices from the shares)
(you have already generated, e.g. `A`, `C` and `D` if $k$ = 3. Label the final)
(Share Index with the new share index you want to derive.) /endlistitem
/listitem1 (In the derivation table for your value of $k$, find the column)
(corresponding to the new share index you want to derive. Fill in the symbols)
(on the Translation Worksheet with the symbols from that column next to the)
(share index for each row.) /endlistitem
/listitem1 (Follow the Translation Worksheet instructions to derive the new share.)
/endlistitem
/notoc /subsubsection (Derivation Table) /endsubsubsection /toc
(These values are used to translate your initial shares in order to compute)
(derived shares. Derivation tables for $k$ from 4 upto 8 can be found in Module 2,)
(along with instructions for generating the table for $k$ = 9. We re-iterate that)
(we strongly discourage large $k$ values.)
] [ % pagebreak
/subsection (II.4. Recover Secret Seed) /endsubsection
/dropcap (N) (ormally you would not recover a secret seed yourself, and)
(instead load shares into a BIP-???? compliant wallet. However, you can)
(recover the secret seed by hand if no compatible wallets are available)
(or you feel a need to demonstrate your conjuring ability.)
/paragraph
(The recovery procedure uses exactly $k$ many shares. If you have more than $k$)
(many shares, you can select any $k$ of them and set the other shares aside.)
/paragraph
(Use the following procedure to recover the share:)
/startlist
/listitem1 (For each share, fill in a Checksum Worksheet and verify the checksum.)
(If a checksum fails to verify, you may have made an error on your worksheet,)
(or there may be an error in your share data. If there is an error in your)
(share data, you can try substituting the share with a different one.)
(Otherwise you will need to perform the Error Correction Procedure on your)
(share, which will involve the assistance of a electronic computer.) /endlistitem
/listitem1 (Make a copy of the Translation Worksheet for the value of $k$ that you)
(are using and label the shares with the share indices from the shares you)
(have selected to recover from, and label the final Share Index as `S`.) /endlistitem
/listitem1 (You can fill in the symbols for each share on the Addition)
(Worksheet using either the table lookup, or the volvelle lookup:)
/paragraph
($Table lookup $k$ = 2:$ Fill in the symbol from the Recover table by)
(finding the column with the associated share, and the row for the other)
(share.)
/paragraph
($Volvelle lookup $k$ = 2:$ Turn the Recovery Wheel to point to the)
(share being considered. Find the symbol pointed to under the other share)
(index on the wheel and fill in that symbol next to the share we are)
(considering on the Translation Worksheet.)
/paragraph
($Table lookup $k$ = 3:$ Finding the column with the associated share.)
(Lookup the two symbols from the two rows corresponding to the two other)
(shares. Make a note of these two symbols on a scrap piece of paper. Use the)
(multiplication table to multiply the the two symbols and fill in that)
(share's symbol on the Translation Worksheet with the resulting product.)
/paragraph
($Volvelle lookup $k$ = 3:$ Turn the Recovery Wheel to point to the)
(share being considered. Find the two symbols pointed to under the other share)
(indices on the wheel. Turn the multiplication wheel to the first of these)
(two symbols. Find the second symbol on the lower ring, and lookup the symbol)
(it is pointing to. Fill that symbol next to the share we are considering on)
(the Translation Worksheet.)
/paragraph
(For $k$ > 3 the instructions are essentially the same as those for $k$ = 3,)
(except that you will have more symbols to multiply.)
/endlistitem
/listitem1 (Repeat step 3 for each share on the Addition worksheet.)
/endlistitem
/listitem1 (Follow the Translation Worksheet instructions recover the secret)
(share.) /endlistitem
] [ % pagebreak
/section (Random Character Worksheet) /endsection
(*You will need:* five $distinct$ dice, five dice markers \(e.g. pieces of paper, each labeled by)
/linebreak (which die it corresponds to\), this and the following page)
/startlist
/listitem1 (Choose a die track for each die. Place each die's marker on its Free Space.)
/endlistitem
/listitem1 (Roll all five dice. Move each die's marker to the Die Pad indicating)
/linebreak (its value.) /endlistitem
/listitem1 (Re-roll the same five dice again and set the $dice$ on the Die Pad)
/linebreak (indicating their second values.) /endlistitem
/listitem1 (For each die that showed the same value twice, move its marker)
/linebreak (back to the free space and repeat steps 2 and 3.)
/linebreak (*You must redo both rolls!*) /endlistitem
/listitem1 (Using your finger, follow the tree to the right according to)
/linebreak (the Die Tracks: take the first left branch if the first die is)
/linebreak (to the left of its marker, the right branch if it is to the)
/linebreak (right. Similarly, take the second branch based on the)
/linebreak (results on the second Die Track, and)
(so on, until) /linebreak (the bottom of the tree.) /endlistitem
/listitem1 (Repeat Steps 1-5 to generate more characters.) /endlistitem
] [ % blank page -- second page of dice worksheet
] [ % pagebreak
/section (Checksum Worksheet \(Generation Instructions\)) /endsection
(The Checksum Worksheet is used to generate and verify checksums. It is the)
(most frequently used and important worksheet of this codex.)
/linebreak
(*You will need:* Checksum Worksheet, Checksum Table, Addition Wheel)
/linebreak
/linebreak
(Generating a checksum:)
/startlist
/listitem1 (Fill in the top diagonal squares \(the bold ones\) with your random data; you should)
(have enough to fill the non-pink bolded squares) /endlistitem
/listitem1 (Add the first row to the second to fill in the third row, using the)
(Addition Wheel.) /endlistitem
/listitem1 (Look up the two leftmost underhanging hanging symbols from the third)
(row in the Checksum Table \(page 11-12\) to fill in the fourth row.) /endlistitem
/listitem1 (Repeat the above two steps, adding the third and fourth row, looking)
(up the fifth to fill in the sixth, and so on. You will be able to complete)
(the entire sheet except for the pink squares this way.) /endlistitem
/listitem1 (To complete the pink squares, work from the bottom up, adding each row)
(to the one above it until all the squares are filled.) /endlistitem
/linebreak
/linebreak
(The completed share can now be read from the top diagonal, including the checksum \(the pink bolded squares\).)
] [
/section (Checksum Worksheet \(Verification Instructions\)) /endsection
(Verifying a checksum:)
/startlist
/listitem1 (Fill in the top diagonal with your share data; you should have enough)
(to fill all the bolded squares) /endlistitem
/listitem1 (\(Optional.\) Fill the bottom diagonal, if you have access to this)
(data. It will help you catch mistakes.) /endlistitem
/listitem1 (Fill in the rest of the worksheet as you did when generating a checksum.)
(If your final row does not match `SECRETSHARE32`, or if any of your computed)
(bottom diagonal values don't match the expected values, there is a mistake in)
(the worksheet or your data has been corrupted.)
/endlistitem
/linebreak /linebreak
(In case of error, first recompute every value in the bad column; then check)
(that you copied all the share data correctly; then try redoing the worksheet)
(entirely. If the checksum is consistently bad your data is corrupt and you)
(need to attempt the online recovery process. \(Under construction; but try)
(contacting Pearlwort for help.\))
4 { ] [ } repeat % checksum tables and worksheet
/section (Translation Worksheet Instructions) /endsection
/notoc %% don't put all the translation worksheets into the ToC
(The translation worksheet is used to derive shares, when splitting keys, and)
(during key recovery. In all cases, the process is to translate a set of shares)
(using the Translation Wheel, then to add the translated results using the)
(Addition Wheel.)
/linebreak
/linebreak
(*You will need:* Translation Worksheet, Translation/Multiplication Wheel, Addition Wheel,)
(Recovery Wheel \(for key recovery\), Derivation Table \(page 7, for share derivation\))
/linebreak
/linebreak
(In all cases, the number of shares to combine is your k value, the number of)
(required shares to reconstruct the secret. The process is:)
/startlist
/listitem1 (Make sure that you have completed checksum worksheets for all input shares.) /endlistitem
/listitem1 (Look up the translation symbols for each share, either in the Derivation Table or)
(using the Recovery Wheel and Multiplication Wheel.) /endlistitem
/listitem1 (Mark down each share's index \(the sixth character of its header\))
(and translation symbol in the appropriate squares.) /endlistitem
/listitem1 (Character by character, translate each share from its Checksum Worksheet)
(to its row, using the Translation Wheel.) /endlistitem
/listitem1 (Using the Addition Wheel, add all rows together.) /endlistitem
/linebreak
/linebreak
(Notice that the resulting share will automatically have the correct share index in its header.)
(*If not, you have likely misread the instructions.*)
3 { ] [ } repeat % add a bunch of empty placeholder pages
/section (Module 0: Volvelles) /endsection
4 { ] [ } repeat
/section (Module 1: Share Booklet) /endsection
(In the common case that your threshold value k is 2, there is a much faster)
(way to generate shares rather than using the Translation Worksheet and the)
(volvelles.)
/paragraph
(In this case, your two initially generated shares will be `A` and `C`. To)
(generate further shares, go through the characters of your `A` share one by)
(one. For each character, find the table labeled by the character; then find)
(the row labeled by the corresponding character of your `C` share.)
/paragraph
(All of the corresponding characters for the `D`, `E`, `F`, etc., shares can)
(be read off this row in the correspondingly-labeled column.)
/paragraph
(We have removed the `S` share from these tables, since this share contains)
(your secret data. If you want to generate the `S` share, you must use the)
(Recovery process.)
9 { ] [ } repeat
/section (Module 2: Share Generation Tables) /endsection
(The main instructional section contains share derivation tables for $k$ values of)
(2 or 3, assuming that initially generated shares are `A`, `C`, and \(sometimes\))
(`D`. This page provides tables for higher $k$ values; the next provides tables)
(for the case where your `S` share is an initial one.)
/paragraph
(Even higher values of $k$ can be obtained by editing the PostScript source of)
(this document. Search for the text `EDITME` to find the right section.)
/paragraph
(We caution users that higher $k$ values, in our view, are a bad trade-off between)
(usability and robustness \(which are damaged\) and security \(which is improved\).)
] [
/startText
(These tables allow you to generate shares in the case that your `S` share is)
(an initial share. Ordinarily, you would generate the first few shares randomly,)
(and infer your `S` share form those; but in some cases, for example when using)
(and existing seed with this scheme, you need to generate the `S` share first.)
20 { ] [ } repeat % add a bunch of empty placeholder pages
]
] def
%******************
%* Helper Functions and Utilities
%*
% determinant : matrix -- det(matrix)
/determinant {
1 0 2 index dtransform
0 1 5 4 roll dtransform
3 1 roll mul
3 1 roll mul
exch sub
} bind def
% tan : angle -- tan(angle)
/tan {
dup sin exch cos div
} bind def
% arcsin: y h -- arcsin(y/h)
/arcsin {
dup mul 1 index dup mul sub sqrt
atan
} bind def
% arccos: x h -- arccos(x/h)
/arccos {
dup mul 1 index dup mul sub sqrt
exch atan
} bind def
% Given a rod of length 2r, what angle does it fit inside a w by h sized box so that
% the ends of the rod are equaldistant from the two sides making a corner with the box.
/angleinbox {
10 dict begin
{ /r /h /w } {exch def} forall
h w sub
2 2 sqrt r mul mul
arcsin 45 sub
end
} bind def
% Constructs a coordinate transformation used for the illustration of folding volvelles.
/foldprojection {
10 dict begin
/foldangle exch def
/squish 0.25 def
/squash 1 squish dup mul sub sqrt def % sqrt (1 - squish^2)
/rollangle squish neg 1 atan def
[rollangle cos squish mul
rollangle sin
dup neg squish mul foldangle cos mul foldangle sin squash mul add
rollangle cos foldangle cos mul
0 0 ]
end
} bind def
/concatstrings % (a) (b) -> (ab)
{ exch dup length
2 index length add string
dup dup 4 2 roll copy length
4 -1 roll putinterval
} bind def
%******************
%* Field Arthmetic
%*
%* Calculations within GF(32), extended with the "null element", represented by
%* numberic 32, which is displayed as a blank, and on which every operation
%* returns null again. Used to represent incomplete/unknown data.
%*
%* Our generator for GF(32) has minimum polynomial x^5 + x^3 + 1.
%*
/gf32add % x y -> x [+] y where [+] is addition in GF32.
% returns 32 if x or y is out of range.
% Note that x [+] y = x [-] y in GF32.
{ % x y
2 copy 32 ge % x y x (y >= 32)
exch 32 ge or % x y (y >= 32 || x >= 32)
{pop pop 32} % 32
{xor} % x [+] y
ifelse % if (y >= 32 || x >= 32) then 32 else (x [+] y)
} bind def
/gf32mulalpha % x -> x [*] alpha where [*] is multiplicaiton in GF32 and alpha is represted by 0b00010.
{ % x
2 mul % 2*x
dup 32 ge % 2*x (2*x >= 0b100000)
{ 41 xor } % 2*x `xor` 0b101001
if % if (2*x >= 0xb100000) then 2*x `xor` 0x0b101001 else 2*x
} bind def
/gf32mul % x y -> x [*] y where [*] is multiplication in GF32.
% returns 32 if x or y is out of range.
{ % x y
10 dict begin
{ /y /x } {exch def} forall
x 32 ge y 32 ge or % (y >= 32 || x >= 32)
{32} % 32
{
/xShift x def
/yAlpha y def
0 % 0
5 { % ((x & 0b001..1) [*] y) (x >> i) (y [*] alpha[^i])
xShift 1 and yAlpha mul xor % ((x & 0b001..1) [*] y [+] ((x >> i) & 1) * (y [*] alpha [^i]))
/xShift xShift -1 bitshift def
/yAlpha yAlpha gf32mulalpha def
} repeat % ((x & 0b11111) [*] y)
} ifelse % if (y >= 32 || x >= 32) then 32 else (x [*] y)
end
} bind def
/gf32inv % x -> x [^-1] where [^-1] is the inverse operation in GF32.
% returns 0 when given 0.
% returns 32 if x is out of range.
{ % x
dup dup gf32mul % x x[^2]
dup gf32mul gf32mul % x[^5]
dup dup gf32mul gf32mul % x[^15]
dup gf32mul % x[^30]
% x[^-1]
} bind def
/lagrange % x xj [x[0] .. x[k]] -> l[j](x)
% returns the lagrange basis polynomial l[j] evaluated at x for interpolation of coordinates [x[0] .. x[k]].
% Requires xj `elem` [x[0] ... x[k]]
{ % x xj [x[0] .. x[k]]
10 dict begin
{ /xs /xj /x } {exch def} forall
1 xs % 1 [x[0] .. x[k]]
{ % let P = product [(x [-] x[m]) [/] (xj [-] x[m]) | m <- [0..i-1], x[m] /= xj]
% P x[i]
/xi exch def % P
xi xj gf32add % P (xj [-] x[i])
dup 0 eq % P (xj [-] x[i]) (xj [-] x[i] == 0)
{ pop } % P
{ gf32inv gf32mul % (P [/] (xj [-] x[i])
xi x gf32add gf32mul % (P [*] (x [-] x[i]) [/] (xj [-] x[i]))
}
ifelse % (if xj == x[i] then P else (P [*] (x [-] x[i]) [/] (xj [-] x[i]))
} forall % x xj (product [(x [-] x[m]) [/] (xj [-] x[m]) | m <- [0..k], x[m] /= xj])
end
} bind def
/makeShare % sS sA i -> si
{ 3 2 roll 1 index permS 0 get permS 0 2 getinterval lagrange gf32mul
3 1 roll permS 1 get permS 0 2 getinterval lagrange gf32mul
xor
} bind def
/gf32mularray % x b -> x * b
{ [ 3 1 roll { 1 index gf32mul exch } forall pop ]
} bind def
/gf32addarray % a b -> a + b pointwise
{ [ 3 1 roll 0 1 2 index length 1 sub { 2 index 1 index get 2 index 2 index get gf32add exch pop 3 1 roll } for pop pop ]
} bind def
%******************
%* Code Parameters
%*
%* Data related to the representation of GF(32) elements
%*
/perm [29 24 13 25 9 8 23 18 22 31 27 19 1 0 3 16 11 28 12 14 6 4 2 15 10 17 21 20 26 30 7 5 ] def
/permS [16 29 24 13 25 9 8 23 18 22 31 27 19 1 0 3 11 28 12 14 6 4 2 15 10 17 21 20 26 30 7 5 ] def
/permV [22 11 10 29 31 28 17 24 27 12 21 13 19 14 20 25 1 6 26 9 0 4 30 8 3 2 7 23 16 15 5 18 ] def
/permId [ 0 1 31 {} for ] def
/code [/Q /P /Z /R /Y /nine /X /eight /G /F /two /T /V /D /W /zero /S /three /J /N /five /four /K /H /C /E /six /M /U /A /seven /L /space] def
/code2 [/multiply /aleph /alpha /beta /Gamma /Delta /epsilon /eta /Theta /Lambda /mu /Xi /Pi /rho /Sigma /Phi /Psi /Omega /at /numbersign /percent /cent /yen /Euro /currency /circleplus /dagger /daggerdbl /section /paragraph /diamond /heart /space ] def
/decode {
[ exch { <<
113 0
81 0
112 1
80 1
122 2
90 2
114 3
82 3
121 4
89 4
57 5
120 6
88 6
56 7
103 8
71 8
102 9
70 9
50 10
116 11
84 11
118 12
86 12
100 13
68 13
119 14
87 14
48 15
115 16
83 16
51 17
106 18
74 18
110 19
78 19
53 20
52 21
107 22
75 22
104 23
72 23
99 24
67 24
101 25
69 25
54 26
109 27
77 27
117 28
85 28
97 29
65 29
55 30
108 31
76 31
32 32
>> exch get } forall ]
} bind def
%******************
%* BCH
%*
%* Data and functions related to the error-correcting code.
%*
/polymodulus [25 27 17 8 0 25 25 25 31 27 24 16 16] def % coefficents from c12 to c0
/checksum [16 25 24 3 25 11 16 23 29 3 25 17 10] def
/checksumstring { polymodulus length array checksum 0 1 polymodulus length 1 sub {3 copy exch 1 index get code exch 1 getinterval putinterval pop } for pop } bind def
/polymod0 % array -> [ c5 c4 c3 c2 c1 c0 ]
{ [ polymodulus length {0} repeat ]
exch
{ [ exch 2 index 1 polymodulus length 1 sub getinterval aload pop polymodulus length dup 1 sub roll ] exch 0 get polymodulus gf32mularray gf32addarray } forall
} bind def
/polymodshift2 % c7 c6 -> [ c5 c4 c3 c2 c1 c0 ]
{ [ 3 1 roll polymodulus length {0} repeat ] polymod0
} bind def
/polymodhrp % string -> [ c5 c4 c3 c2 c1 c0 ]
{
[ exch 1 exch dup { dup dup 65 ge exch 90 le exch and { 32 add } if 32 idiv exch } forall 0 exch { 31 and } forall ] polymod0
} bind def
%************************************************************************
%************************************************************************
%*
%* Section Two: Graphics
%*
%************************************************************************
%************************************************************************
%******************
%* Helper Functions and Utilities
%*
/pgsize currentpagedevice /PageSize known
{ currentpagedevice /PageSize get
} {
[611.842163 791.842163] % letter size
} ifelse
def
20 dict dup /portraitPage exch def begin
pgsize aload pop [ /pageH /pageW ] { exch def } forall
/centerX pageW 2 div def
/centerY pageH 2 div def
/marginX1 36 def
/marginX2 pageW 36 sub def
/marginY1 pageH 48 sub def
/marginY2 48 def
/marginW marginX2 marginX1 sub def
/marginH marginY2 marginY1 sub def
% Draw a line indicating where the margins of the page are; can be used
% for debugging graphical output
/drawMargin {
gsave
0 setgray thin line
marginX1 marginY1 marginW marginH rectstroke
grestore
} bind def
% Draw the page number and any (TODO) content in the page content array
% Takes the pagenum as a numeric value
/drawPageContent {
10 dict begin
/pagenum exch def
% Page content
gsave
allPageContent pagenum get drawPageContentInner
grestore
% Footer
pagenum 0 gt {
gsave
/Times-Roman findfont 12 scalefont setfont
centerX marginY2 moveto
pagenum pagenum 10 lt { 1 } { 2 } ifelse string cvs show
grestore
} if
end
} bind def
end
% landscapePage is a modified copy of portraitPage
portraitPage dup 20 dict copy dup /landscapePage exch def begin
pgsize aload pop exch [ /pageH /pageW ] { exch def } forall
/centerX pageW 2 div def
/centerY pageH 2 div def
/marginX1 36 def
/marginX2 pageW 36 sub def
/marginY1 pageH 48 sub def
/marginY2 48 def
/marginW marginX2 marginX1 sub def
/marginH marginY2 marginY1 sub def
/pageW portraitPage /pageH get def
/pageH portraitPage /pageW get def
/drawPageContent {
90 rotate
0 pageH neg translate
portraitPage /drawPageContent get exec
} bind def
end
% line : width --
/line {
setlinewidth
1 setlinecap
1 setlinejoin
[] 0 setdash
} bind def
/verythin 0.2 def
/thin 0.4 def
/thick 1.4 def
/pen {
50 setlinewidth
1 setlinecap
1 setlinejoin
[] 0 setdash
} bind def
% Runs stroke under a uniformly scaled matrix.
% ps2pdf doesn't seem to handle strokes under a non-uniformly scaled matrix properly.
/resetstroke {