Spiral Ratchet
Backwards-secret deterministic versioning
Every node in the private tree is encrypted with a different key. This is done randomly for child nodes (along the y-axis), and deterministically with a cryptographic ratchet for increasing versions (along the z-axis).
The basic idea for cryptographic ratchets is that repeatedly hashing a value creates a kind of backwards-secret clock. When you start watching the clock, you can generate the hash for any arbitrary future steps, but not steps from prior to observation since that requires computing the SHA3 preimage.
Source: https://www.quora.com/What-is-exactly-backward-secrecy-property-in-cryptography-attribute-based-encryption
SHA3-256 is native to the WebCypto API, is a very fast operation, and commonly hardware accelerated. Anecdotally, Firefox on an Apple M1 completes each SHA3 ~3μs (100k/300ms). The problem with a single hash counter is threefold:
1. The root of the unencrypted tree updates with with every atomic operation, and thus accrues a lot of changes 2. An actor may be many months since their last sync, and need to fast forward their clock by some huge number of elements 3. Seeking ahead by 100ks or millions takes very noticeable time 4. It should be cheaper to fast forward than for an attacker to build a large history
We still want small step changes to be very fast, but also be able to deterministically tune how quickly we jump ahead, without revealing previous counter hashes, while maintaining the same security properties as a single ratchet counter.
Positional counting does exactly this in the most common numeral systems. Our design involves three positions, two of which are bounded. We call these the large (or epoch), medium, and small numbers.
Positionally this looks like:
1
large medium small
2
l*2^16 m*2^8 s*2^0
3
4
l = 0x600b56e66b7d12e08fd58544d7c811db0063d7aa467a1f6be39990fed0ca5b33
5
m = 0x5d58264a09dce1f2676e729d0ea1db4bf90b9be463d7fc1aa9b43b358e514599
6
s = 0xc8633540cabdf591e07918a2595964cc1b692d0f9392f079f2f110c08b67c6f4
Copied!
The large and small are bounded at 256 elements. We achieve this by keeping a record of the max bound of these numbers. This is found by hashing that number 255 times (0 is the unchanged value). As we increment each number by taking its SHA3-256, we check if it matches the max bound. If it does, we increment the next-highest value, and reset the smaller values.
The metaphor is a spiral. You can ratchet one at a time, or deterministically skip to the start of the next ring in the spiral.
https://commons.wikimedia.org/wiki/File:Ulam_spiral_howto_all_numbers.svg
1
data SpiralRatchet = SpiralRatchet
2
{ large :: Digest SHA3_256
3
4
, medium :: Digest SHA3_256
5
, mediumMax :: Digest SHA3_256
6
7
, small :: Digest SHA3_256
8
, smallMax :: Digest SHA3_256
9
}
10
11
exampleSR = SpiralRatchet
12
{ large = 0x600b56e66b7d12e08fd58544d7c811db0063d7aa467a1f6be39990fed0ca5b33
13
14
, medium = 0x5d58264a09dce1f2676e729d0ea1db4bf90b9be463d7fc1aa9b43b358e514599
15
, mediumMax = 0x5aae7b2b881d21863292a1556eafd2a3b21527f64f33c6fcc2beaa9d9cf1fe5f
16
17
, small = 0xc8633540cabdf591e07918a2595964cc1b692d0f9392f079f2f110c08b67c6f4
18
, smallMax = 0xb95c5d8851daff6204eb227f56d8c6af1c11a80d46d17eb0aa219a9d2ec109af
19
}
Copied!
Incrementing a larger value resets all smaller values. This is done by taking the SHA3-256 of the (one's) complement. This cascades from larger to all smaller positions.
Please note that JavaScript's basic inverse function behaves unexpectedly. The ~ operator casts values to their one's compliment integer. This means that ~0b11 !== 0b00, but rather ~0b11 === -4. -4 can not be directly expressed in JS binary, since it interprets binary notation as being a natural number only (rather than its two's compliment). To keep this from happening, use a toggle mask of equal length: val ^ b1111....
The small and medium values are base-256. This means that the first position increments in ones (2^0), the second position increments in 256s (2^8), and the third position by 65,536s (2^16). Looking at a triple does not admit which number it is, only which number relative to the max bounds of the medium and small numbers. It is not possible to determine which of epoch (large number) you are in. Here is an example of a spiral ratchet being constructed from a seed value.
1
seed = 0x600b56e66b7d12e08fd58544d7c811db0063d7aa467a1f6be39990fed0ca5b33
2
large = sha3_256 seed -- e.g. 0x8e2023cc8b9b279c5f6eb03938abf935dde93be9bfdc006a0f570535fda82ef8
3
4
mediumSeed = sha3_256 $ Binary.complement seed
5
medium = sha3_256 mediumSeed
6
mediumMax = iterate sha3_256 medium !! 255
7
8
smallSeed = sha3_256 $ Binary.complement mediumSeed
9
small = sha3_256 smallSeed
10
smallMax = iterate sha3_256 small !! 256
Copied!
Here is how to increment the ratchet by one:
1
-- large (0..), medium (0-255), small (0-255)
2
3
toVersionHash :: SHA3_256
4
toVersionHash SpiralRatchet {..} = sha3_256 (large `xor` medium `xor` small)
5
6
advance :: SpiralRatchet -> SpiralRatchet
7
advance SpiralRatchet {..} =
8
case (nextSmall == smallCeiling, nextMedium == mediumCeiling) of
9
(False, _) -> advanceSmall
10
(True, False) -> advanceMedium
11
(_, True) -> advanceLarge
12
(False, True) -> error "Not possible"
13
14
where
15
nextSmall = sha3_256 small
16
nextMedium = sha3_256 medium
17
18
advanceSmall :: SpiralRatchet
19
advanceSmall = SpiralRatchet {small = nextSmall, ..}
20
21
advanceMedium :: SpiralRatchet
22
advanceMedium =
23
let
24
resetSmall = sha3_256 $ compliment nextMedium
25
resetMedium = sha3_256 $ compliment nextLarge
26
27
in
28
SpiralRatchet
29
{ large = large
30
31
, medium = nextMedium
32
, mediumCeil = recursiveSHA 256 nextMedium
33
34
, small = resetSmall
35
, smallCeil = recursiveSHA 256 resetSmall
36
}
37
38
advanceLarge :: SpiralRatchet
39
advanceLarge =
40
let
41
nextLarge = sha3_256 large
42
resetMedium = sha3_256 $ compliment nextLarge
43
resetSmall = sha3_256 $ compliment resetMedium
44
45
in
46
SpiralRatchet
47
{ large = nextLarge
48
49
, medium = resetMedium
50
, mediumCeil = recursiveSHA 256 resetMedium
51
52
, small = resetSmall
53
, smallCeil = recursiveSHA 256 resetSmall
54
}
Copied!
Many files will have few revisions. To prevent leaking this information, we take advantage of the fact that the setup starts at a random point in the ratchet:
1
setup :: SpiralRatchet
2
setup = do
3
largePre <- random -- ratchet seed
4
mediumSkip <- randomBetween 0 254
5
smallSkip <- randomBetween 0 254
6
7
let
8
large = sha3_256 largePre
9
10
mediumPre = sha3_256 $ compliment largePre
11
medium = recursiveSHA mediumSkip mediumPre
12
mediumMax = recursiveSHA 255 mediumPre
13
14
smallPre = sha3_256 $ compliment mediumPre
15
small = recursiveSHA smallSkip smallPre
16
smallMax = recursiveSHA 255 smallPre
17
18
return SpiralRatchet {..}
Copied!

Canonical Serialization

The spiral ratchet is byte aligned, which makes for straightforward binary serialization. The usual case is to increment the smallest digit, followed by the next largest, and so on. As such, it is more efficient to encode as little-endian:
1
serialize SpiralRatchet {..} =
2
[small, smallMax, medium, mediumMax, large] -- [Digest AES256]
3
|> fmap toByteString -- [ByteString]
4
|> concat -- ByteString
Copied!
We then flag the encoding. The default encoding is base64URL-unpadded (signified with u) and SHA-256 (0x16), so:
1
uFuGha07m3EEs2-3_oP14Sy4aJPztz0bBdnPFUqQw9Y2lsqQoKhJ2BAjcXrxSTFLmbb2lICSq12ac14hIV6rI43byk2vrXaM6eW4K8ucJWLJeSz-EObY3VF7Nbat_rDY5tz4Xt-J--WPF_o3LSf85kpdL8PsNmDNlpYXk2Bzte2tcL_DdgV4bhUNSA20PKLKisazdR-Bq2YaxWPhb85RgzFs
Copied!

Generalized Spiral Ratchet

There is nothing special about a 3xAES256 spiral ratchet. The digits don't even need to be the same length or hashing algorithm (though this is strongly recommended to lower cognitive overhead). It is "merely" a positional number system implemented with hashing to avoid unary counting overhead. To provide some consistency, here is the formula for constructing a spiral ratchet up to n digits:
  • An unbounded hash to represent the largest digit (or "epoch")
  • Each digit is accompanied by its ceiling, to indicate how much room is left
    • This may also be implemented as the number of remaining increments
  • A hashing algorithm

Example Implementation

1
data SpiralDigit algo = SpiralDigit
2
{ current :: Digest algo
3
, max :: Digest algo
4
}
5
6
data GeneralSpiralRatchet algo = GSR
7
{ epoch :: Digest algo
8
, digits :: [SpiralDigit]
9
}
Copied!
Here, the digits field correlates the index with the digit exponent. In the familiar base 10, index 0 = 10^0 = 1s-digit, index 5 = 10^5 = 100,000s-digit.
Last modified 8mo ago