Skip Ratchet: Massive Hash Chains Without All The Waiting

⚙ The Skip Ratchet ⏭ Massive Hash Chains Without All the Waiting Or: An Encrypted Counting Scheme https://eprint.iacr.org/2022/1078 github.com/fission-codes

Where’s Quinn? @wilton_quinn GET WELL SOON 🙏

Brooklyn Zelenka @expede

Brooklyn Zelenka @expede • Cofounder & CTO at Fission • https://fission.codes • @FissionCodes • Infra & SDK for edge apps • PLT, VMs, DSys — IANYC! • Standards: UCAN, EIPs, FVM, Multiformats, &c

Brooklyn Zelenka @expede • Cofounder & CTO at Fission • https://fission.codes • @FissionCodes • Infra & SDK for edge apps • PLT, VMs, DSys — IANYC! • Standards: UCAN, EIPs, FVM, Multiformats, &c https://eprint.iacr.org/2022/1078.pdf

Motivation At a High Level 💭

Motivation 💭 Uses

Motivation 💭 Uses Local-first data WNFS: distributed private file system Implemented in at least TypeScript, Rust, Golang Electric coins, streaming payment channels HD wallets (key management) Long-running, asymmetric channels

Motivation 💭 Deterministic Keys in WNFS / Header / Header / Content /Docs/ Header / Header / Content /Docs/ Header /Docs/ Content /stl.md Header /Docs/ Header /Docs/ Content /stl.md Header /stl.md Content / Content /Docs/ Content /stl.md Header /stl.md Content /stl.md Content

Motivation 💭 A Tale As Old as Time

Motivation 💭 A Tale As Old as Time PLT cross-pollination driving innovation in cryptography Really simple idea with lots of applications Interesting way of arriving at it / analogies to other areas Let’s talk number systems & applied cryptography!

Fundamentals Hash Chains, Lamport OTP, & More! ⛓

Fundamentals ⛓ Hash Chains

Fundamentals ⛓ Hash Chains Seed

Fundamentals ⛓ Hash Chains Hash Seed Hash Seed Hash(seed)

Fundamentals ⛓ Hash Chains Hash Seed Hash Hash Hash Seed Seed Hash(seed) Hash Hash(Hash(seed))

Fundamentals ⛓ Hash Chains Hash Seed Hash Hash Hash Hash Hash Hash Seed Seed Seed Hash(seed) Hash Hash(Hash(seed)) Hash Hash(Hash(Hash(seed)))

Fundamentals ⛓ Hash Chains Hash Seed Hash Hash Hash Hash Hash Hash Seed Seed Seed Hash(seed) Hash Hash(Hash(seed)) Hash Hash(Hash(Hash(seed))) H3(seed)

Fundamentals ⛓ Pseudoradom Stream

Fundamentals ⛓ Pseudoradom Stream Seed (ECDH)

Fundamentals ⛓ Pseudoradom Stream ✉A ✉B ✉C Seed (ECDH) Reset ✉A ✉B ✉C

Fundamentals ⛓ Lamport OTP, S/KEY

Fundamentals ⛓ Lamport OTP, S/KEY Seed

Fundamentals ⛓ Lamport OTP, S/KEY Seed Hash H(Seed)

Fundamentals ⛓ Lamport OTP, S/KEY Seed Hash H(Seed) Hash H2(Seed)

Fundamentals ⛓ Lamport OTP, S/KEY Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed)

Fundamentals ⛓ Lamport OTP, S/KEY Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed) Hash H4(Seed)

Fundamentals ⛓ Lamport OTP, S/KEY Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed) Hash H4(Seed) Prover Verifier

Fundamentals ⛓ Lamport OTP, S/KEY Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed) Hash H4(Seed) Prover Hx(Seed) Verifier

Fundamentals ⛓ Lamport OTP, S/KEY Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed) Hash H4(Seed) Prover Hx(Seed) Verifier x H

Fundamentals ⛓ Lamport OTP, S/KEY Preimage Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed) Hash H4(Seed) Prover Hx(Seed) Verifier x H

Fundamentals ⛓ Lamport OTP, S/KEY Preimage Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed) Hx-1(Seed) Hash ✅ Hash H4(Seed) Prover Hx(Seed) Verifier x H

Fundamentals ⛓ Lamport OTP, S/KEY Preimage Seed Hash H(Seed) Hash H2(Seed) Hash H3(Seed) Hx-1(Seed) x-1 H Hash ✅ Hash H4(Seed) Prover Hx(Seed) Verifier x H

Fundamentals ⛓ Lamport OTP, S/KEY Preimage Seed Hash H(Seed) Hash H2(Seed) Hash Preimage H3(Seed) Hx-1(Seed) x-1 H Hash ✅ Hash H4(Seed) Prover Hx(Seed) Verifier x H

Fundamentals ⛓ Lamport OTP, S/KEY Preimage Seed Hash H(Seed) Hash H2(Seed) Hx-2(Seed) Hash ✅ Hash Preimage H3(Seed) Hx-1(Seed) x-1 H Hash ✅ Hash H4(Seed) Prover Hx(Seed) Verifier x H

Fundamentals ⛓ Lamport OTP, S/KEY Preimage Seed Hash H(Seed) Hash H2(Seed) Hx-2(Seed) x-2 H Hash ✅ Hash Preimage H3(Seed) Hx-1(Seed) x-1 H Hash ✅ Hash H4(Seed) Prover Hx(Seed) Verifier x H

Fundamentals ⛓ Lamport OTP, S/KEY Preimage Seed Hash H(Seed) Hash H2(Seed) Latest message takes O(n) to catch up One PITM (can be) very bad Hx-2(Seed) Hash ✅ Hash Preimage H3(Seed) Hx-1(Seed) Hash ✅ Hash H4(Seed) Prover Hx(Seed) Verifier Eventually run out of hashes x-2 H x-1 H x H

Fundamentals ⛓ Samy Kamkar’s Drive it like you Hacked it https://www.youtube.com/watch?v=UNgvShN4USU

Fundamentals ⛓ Micropayments (Simplified PayWord)

Fundamentals ⛓ Micropayments (Simplified PayWord) 🪙 Seed H(Seed) H2(Seed) H3(Seed) H4(Seed)

Analogy From Counting One Hash, Two Hash… 🔢

“Can you do Addition?” the White Queen said. “What’s one and one and one and one and one and one and one and one and one and one?” “I don’t know,” said Alice. “I lost count.” “She can’t do Addition,” the Red Queen interrupted. — Lewis Carroll, Through the Looking Glass

Analogy From Counting 🔢 The Ishango Bone Ishango Bone Congo ~20,000 years 🌾 Agriculture ~ 11.5k years 🐷 Herding ~ 10k years Lebombo Bone South Africa ~44,000 years Joeykentin CC-BY-SA 4.0 https://commons.wikimedia.org/wiki/File:Ishango_bone.jpg

Analogy From Counting 🔢 Unary Counting

Analogy From Counting 🔢 Unary Counting | || ||| |||| ||||| |||||| ||||||| |||||||| ||||||||| ||||||||||

Analogy From Counting 🔢 Unary Counting | || ||| |||| | || ||| |||| ||||| |||||| ||||||| |||||||| ||||||||| ||||||||||

Analogy From Counting 🔢 Unary Counting | || ||| |||| ||||| |||||| ||||||| |||||||| ||||||||| |||||||||| | || ||| |||| |||| |||| | |||| || |||| ||| |||| |||| |||| ||||

Analogy From Counting 🔢 Unary Counting | || ||| |||| ||||| |||||| ||||||| |||||||| ||||||||| |||||||||| | || ||| |||| |||| |||| | |||| || |||| ||| |||| |||| |||| |||| || ||||

Analogy From Counting 🔢 Unary Constructors data Peano = Zero | Succ Peano

Analogy From Counting 🔢 Unary Constructors data Peano = Zero | Succ Peano Zero

Analogy From Counting 🔢 Unary Constructors data Peano = Zero | Succ Peano Succ Zero +1 Zero

Analogy From Counting 🔢 Unary Constructors data Peano = Zero | Succ Peano Succ Zero +1 Succ Succ Zero Zero +1

Analogy From Counting 🔢 From Constructors to Functions 0 λf x → x

Analogy From Counting 🔢 From Constructors to Functions 0 λf x → x 1 λf x → f x

Analogy From Counting 🔢 From Constructors to Functions 0 λf x → x 1 λf x → f x 2 λf x → f (f x)

Analogy From Counting 🔢 From Constructors to Functions 0 λf x → x 1 λf x → f x 2 λf x → f (f x) 3 λf x → f (f (f x))

Analogy From Counting 🔢 From Constructors to Functions 0 λf x → x 1 λf x → f x 2 λf x → 3 λf x → f (f (f x)) f (f x)

Analogy From Counting 🔢 From Constructors to Functions 0 λf x → x 1 λf x → f x 2 λf x → 3 λf x → f (f (f x)) 3 h f (f x) x → h (h (h x))

Analogy From Counting 🔢 Naive ||| Succ (Succ (Succ Zero)) λf x → f (f (f x)) h (h (h x))

Positional Numerals Abstraction By Symbolic Juxtaposition 🧮

Mathematics is only the art of saying the same thing in different words — Bertrand Russell

Positional Numerals 🧮 Positional Systems

Positional Numerals 🧮 Positional Systems Image Credit: National Numismatic Collection at the Smithsonian Institution, CC BY-SA 3.0

Positional Numerals 🧮 Positional Systems 9 Image Credit: National Numismatic Collection at the Smithsonian Institution, CC BY-SA 3.0

Positional Numerals 🧮 Positional Systems 100 ↔ 壹佰 1000 ↔ 壹仟 9 Image Credit: National Numismatic Collection at the Smithsonian Institution, CC BY-SA 3.0

Positional Numerals 🧮 Positional Digits

Positional Numerals 🧮 Positional Digits Numeral X 100 X 10 X1

Positional Numerals 🧮 Positional Digits Numeral X 100 X 10 X1 0 0 0 0

Positional Numerals 🧮 Positional Digits Numeral X 100 X 10 X1 0 0 0 0 11 0 1 1

Positional Numerals 🧮 Positional Digits Numeral X 100 X 10 X1 0 0 0 0 11 0 1 1 582 5 8 2

Positional Numerals 🧮 Positional Digits Numeral X 10010 X 1010 X 110 0 0 0 0 11 0 1 1 582 5 8 2

Positional Numerals 🧮 Mixed-Radix 🥴 Numeral X 12111 X 412 X 14 0 0 0 0 11 0 2 3 582 44 1 2

Positional Numerals 🧮 Mixed-Radix

Positional Numerals 🧮 Mixed-Radix 2022 Sept 22 11:22:03.987 60 minutes / hour 24 hours / day 7 days / week 52 weeks / year

Positional Numerals 🧮 Compound Hash

Positional Numerals 🧮 Compound Hash Numeral “hundreds” “tens” “ones”

Positional Numerals 🧮 Compound Hash Numeral “hundreds” “tens” “ones” X + 0 “hundreds” “tens” “ones”

Positional Numerals 🧮 Compound Hash Numeral “hundreds” “tens” “ones” X + 0 “hundreds” “tens” “ones” h(“tens”) h(“ones”) X + 11 “hundreds” 523c079f58465edb79c834fbf460809 d413f65286221536df21b59e5d29215 9cf864039bb511c072beb35c568c80e e2817d8cc70a1d6ef4273e7c63c6b1a df 08

Positional Numerals 🧮 Compound Hash Numeral “hundreds” “tens” “ones” X + 0 “hundreds” “tens” “ones” h(“tens”) h(“ones”) X + 11 X + 582 “hundreds” h5(“hundreds”) 523c079f58465edb79c834fbf460809 d413f65286221536df21b59e5d29215 9cf864039bb511c072beb35c568c80e e2817d8cc70a1d6ef4273e7c63c6b1a df 08 h8(“tens”) h2(“ones”) b7fee5aff5d93be282a3826766c8f4a 6d00cd80a2f03d126077401fa4b9512 e6f92be646346875e815ebd95fbc0e3 3af7a35e620e78b300c5a8fd8791e77 9d4e79ec3f4ea7ae36099af5a39478e b2412e2d630b2325decdbdb4a0eeb34 cb f7 01

Positional Numerals 🧮 Denominated PayWord https://sci-hub.ru/https://link.springer.com/article/10.1007/s10623-003-1162-6

Positional Numerals 🧮 Denominated PayWord L H(L) H2(L) https://sci-hub.ru/https://link.springer.com/article/10.1007/s10623-003-1162-6

Positional Numerals 🧮 Denominated PayWord L H(L) H2(L) M H(M) H2(M) https://sci-hub.ru/https://link.springer.com/article/10.1007/s10623-003-1162-6 H3(M) H4(M)

Positional Numerals 🧮 Denominated PayWord L H(L) H2(L) M H(M) H2(M) H3(M) S H(S) H2(S) H3(S) https://sci-hub.ru/https://link.springer.com/article/10.1007/s10623-003-1162-6 H4(M)

Positional Numerals 🧮 Denominated PayWord $20s L H(L) H2(L) $5s M H(M) H2(M) H3(M) $1s S H(S) H2(S) H3(S) https://sci-hub.ru/https://link.springer.com/article/10.1007/s10623-003-1162-6 H4(M)

Positional Numerals 🧮 Denominated PayWord 🙈 👀 $20s L H(L) H2(L) $5s M H(M) H2(M) H3(M) $1s S H(S) H2(S) H3(S) https://sci-hub.ru/https://link.springer.com/article/10.1007/s10623-003-1162-6 H4(M)

Analogy From Data Structures Who Doesn’t Love DAGs In Their Crypto? 🌲

Analogy From Data Structures 🌲 Deterministic Skip List

Analogy From Data Structures 🌲 Deterministic Skip List Nil A B C D E F G H

Analogy From Data Structures 🌲 Deterministic Skip List Nil D H B A F C E G

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L M S

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L M S 0002

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L L M M S 0002 +1 h(S) 0012

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L L L M M h(M) S 0002 +1 h(S) 0012 +1 S’ 0102

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L L L M M h(M) S 0002 +1 h(S) 0012 Next M +1 S’ 0102

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L L L L M M h(M) h(M) S 0002 +1 h(S) 0012 Next M +1 S’ 0102 +1 h(S’) 0112

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L L L L h(L) M M h(M) h(M) M’ S 0002 +1 h(S) 0012 Next M +1 S’ 0102 +1 h(S’) 0112 +1 S” 1002

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet L L L L h(L) M M h(M) h(M) M’ S 0002 +1 h(S) 0012 Next M +1 S’ 0102 +1 h(S’) 0112 Next M +1 S” 1002

Analogy From Data Structures 🌲 Simplified Binary Skip Ratchet Next L Next L Next L Next L L L L L h(L) M M h(M) h(M) M’ S 0002 +1 h(S) 0012 Next M +1 S’ 0102 +1 h(S’) 0112 Next M +1 S” 1002

Analogy From Data Structures 🌲 Deriving Secrets L L ⊕ M M ⊕ S → S OUT

Analogy From Data Structures 🌲 Deriving Secrets With Secrets Seed +1 State 1 +1 State 2 +1 State 3 +1 State 4 +1 State 5

Analogy From Data Structures 🌲 Deriving Secrets With Secrets Seed +1 State 1 ⊕ Secret 1 +1 State 2 ⊕ Secret 2 +1 State 3 ⊕ Secret 3 +1 State 4 ⊕ Secret 4 +1 State 5 ⊕ Secret 5

Analogy From Data Structures 🌲 Deriving Secrets With Secrets Seed +1 State 1 +1 ⊕ Secret 1 State 2 ⊕ ❌ Secret 2 +1 State 3 ⊕ Secret 3 +1 State 4 ⊕ Secret 4 +1 State 5 ⊕ Secret 5

Security Who Hashes the Hashers? 🔐

Security 🔐 Zeroing & Epochs

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 …

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10 Zero 0

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10 Zero +1 0 1

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10 Zero +1 0 1 8

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10 Zero +1 0 +1 1 8 9

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10 2x10 Zero +1 0 +1 1 8 9

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10 2x10 Zero Zero +1 0 +1 1 8 9 0

Security 🔐 Zeroing & Epochs 10 11 … 18 19 20 21 22 … 1x10 2x10 Zero Zero +1 0 +1 1 8 9 0 +1 1

Security 🔐 Zeroing & Epochs L hash h(L) M hash h(M)

Security 🔐 Zeroing & Epochs L Salt hash h(L) M hash h(M)

Security 🔐 Zeroing & Epochs L Salt Merge hash h(L) M hash h(M)

Security 🔐 Zeroing & Epochs L Salt Merge hash hash h(L) M hash h(M)

Security 🔐 Zeroing & Epochs L Merge Salt M-1 🔐 h(M-1) hash hash h(L) M hash h(M)

Security 🔐 Setup Seed hash hash pre-L Merge hash pre-M L @ 1/2 hash L @ 1/2 L @ 1/2 M @ 1/2 M @ 1/2 hash Merge Salt Merge hash S @ 1/2 hash S @ 2/2 M @ 2/2 hash S’ @ 1/2

Security 🔐 Random Start 🙈🎲

Security 🔐 Random Start 🙈🎲 L

Security 🔐 Random Start 🙈🎲 L-1 +1 L

Security 🔐 Random Start 🙈🎲 L-1 +1 L M

Security 🔐 Random Start 🙈🎲 🎲5 L-1 +1 L M

Security 🔐 Random Start 🙈🎲 🎲5 L-1 +1 L M +4

Security 🔐 Random Start 🙈🎲 🎲5 L-1 +1 L M +4 M+4

Security 🔐 Random Start 🙈🎲 🎲5 L-1 +1 L M +4 M+4 +1 M+5

Security 🔐 Random Start 🙈🎲 🎲5 L-1 +1 L M +4 M+4 M+5 +1 S

Security 🔐 Random Start 🙈🎲 🎲5 L-1 🎲 42 +1 L M +4 M+4 M+5 +1 S

Security 🔐 Random Start 🙈🎲 🎲5 L-1 🎲 42 +1 L M +4 M+4 M+5 +1 S +42 S+42

Security 🔐 Unary + Positional

Security 🔐 Unary + Positional L-1 h(M) h(S) L+1 L M S’ h(M) h(S’) S” M’ h2(M) h(S”) S”’ h(S”’) S”” h(M) h(S””) S””’ h(S)

Security 🔐 Unary + Positional Unary L-1 h(M) h(S) L+1 L M S’ h(M) h(S’) S” M’ h2(M) h(S”) S”’ h(S”’) S”” h(M) h(S””) S””’ h(S)

Security 🔐 Unary + Positional Unary L-1 h(M) h(S) L+1 L M S’ h(M) h(S’) S” M’ h2(M) h(S”) S”’ Positional h(S”’) S”” h(M) h(S””) S””’ h(S)

Security 🔐 Limiting Ranges 🗜

Security 🔐 Limiting Ranges 🗜 G L M S

Security 🔐 Limiting Ranges 🗜 G L G+L M S

Security 🔐 Limiting Ranges 🗜 G G G G L L L L G+L G+L G+L G+L M M h(M) h(M) S h(S) S’ h(S’)

Security 🔐 Limiting Ranges 🗜 G G G G G G L L L L h(L) h(L) G+L G+L G+L G+L G + h(L) G + h(L) M M h(M) h(M) M’ M’ S h(S) S’ h(S’) S” h(S”)

Security 🔐 Range Access G+(L-1) h(M) h(S) G+(L+1) G+L M S’ h(M) h(S’) S” M’ h2(M) h(S”) S”’ h(S”’) S”” h(M) h(S””) S””’ h(S)

Wrap Up 🎁

Wrap Up 🎁 Skip Ratchet Seed +1 State 1 ⊕ Secret 1 +1 State 2 ⊕ Secret 2 +1 State 3 ⊕ Secret 3 +1 State 4 ⊕ Secret 4 +1 State 5 ⊕ Secret 5

Wrap Up 🎁 Takeaways

Wrap Up 🎁 Takeaways Really fast secrets thanks to positional structure In production in several systems, still finding more uses Very disparate ideas share some common core Many ways to tackle a problem There’s still tons of low hanging fruit out there!

Wrap Up 🎁 WNFS: Skip Ratchet In Situ B C A Z W X Y

Wrap Up 🎁 WNFS: Skip Ratchet In Situ PB PC PA PZ PW PX B PY C A Z W X Y

🎉 Thank You, Strange Loop @expede brooklyn@fission.codes https://eprint.iacr.org/2022/1078.pdf

Skip Ratchet: Massive Hash Chains Without All The Waiting

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75