Trust, but verify. The paranoid are unsatisfied with the reassuring output of
dfx and web applications. It’s better to see with your own eyes that
everybody is following the advertised protocols.
But how do you understand the TCP dumps of canister requests? One way is to read the interface spec, which in turn mentions more specs that you’ll need.
Or, you could just read this page, which conveniently collects the bits and pieces of the many specs required to analyze Internet Computer traffic. In fact, we do one better: we show how to write an Internet Computer agent from scratch, and provide working demos of our code along the way.
We proceed in order of difficulty:
We’re serious about writing "from scratch": we have zero dependencies, relying only on JavaScript and WebAssembly found in standard browsers. We must implement our own hash functions, encoders, decoders, and so on.
For starters, we define some hex input and output routines:
hexit n = chr $ n + (if n <= 9 then ord '0' else ord 'a' - 10) xx c = hexit <$> [q, r] where (q, r) = divMod (ord c) 16 unxx [q, r] = chr $ 16*unhexit q + unhexit r chunksOf i ls = take i <$> go ls where go [] = [] go l = l : go (drop i l) unxxs = map unxx . chunksOf 2 xxs = concatMap xx unhexit c | '0' <= c && c <= '9' = ord c - 48 | 'A' <= c && c <= 'F' = ord c - 65 + 10 | 'a' <= c && c <= 'f' = ord c - 97 + 10
For example:
hexit <$> [7..11] xxs "ABC" unxxs "414243"
We also write a rudimentary parser combinator library, which the uninitiated can think of as concise notation for recursive descent parsing:
data Charser a = Charser { unCharser :: String -> Either String (a, String) }
instance Functor Charser where fmap f (Charser x) = Charser $ fmap (first f) . x
instance Applicative Charser where
pure a = Charser \s -> Right (a, s)
f <*> x = Charser \s -> do
(fun, t) <- unCharser f s
(arg, u) <- unCharser x t
pure (fun arg, u)
instance Monad Charser where
Charser f >>= g = Charser $ (good =<<) . f
where good (r, t) = unCharser (g r) t
return = pure
instance Alternative Charser where
empty = Charser \_ -> Left ""
(<|>) x y = Charser \s -> either (const $ unCharser y s) Right $ unCharser x s
sat f = Charser \case
h:t | f h -> Right (h, t)
_ -> Left "unsat"
eof = Charser \case
[] -> Right ((), "")
_ -> Left "want EOF"
charserBad = Charser . const . Left
anyChar = sat (const True)
char = sat . (==)
digitChar = sat $ \c -> '0' <= c && c <= '9'
hexitChar = digitChar
<|> sat (\c -> 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F')
hexcode = ord . unxx <$> replicateM 2 hexitChar
lowerChar = sat $ \c -> 'a' <= c && c <= 'z'
upperChar = sat $ \c -> 'A' <= c && c <= 'Z'
letterChar = lowerChar <|> upperChar
alphaNumChar = letterChar <|> digitChar
space = many (sat isSpace) *> pure ()
space1 = some (sat isSpace) *> pure ()
parse p _ = fmap fst . unCharser p
Anonymous query calls are the simplest case. We need little more than CBOR. As we’re doing our own stunts, we shun libraries and roll our own encoder.
Fundamental to CBOR is a cute serialization of a 3-bit type and a count less than 264. The 3 highest bits of the first byte hold the type. Counts below 24 can simply be stored in the lower 5 bits. Otherwise, the lower 5 bits are 24, 25, 26, or 27, and means the next 1, 2, 4, or 8 bytes (respectively) hold the count in big-endian.
everLE n = chr (fromIntegral r) : everLE q where (q, r) = divMod n 256 biggie k = reverse . take k . everLE unbiggie = foldl (\acc b -> 256*acc + fromIntegral b) 0 cborTC ty n | n < 24 = hdr n | n < 2^8 = hdr 24 . ch n | n < 2^16 = hdr 25 . (biggie 2 n++) | n < 2^32 = hdr 26 . (biggie 4 n++) | otherwise = hdr 27 . (biggie 8 n++) where hdr k = ch $ ty*32 + k ch n = (chr (fromIntegral n):)
Examples:
type = 0, count = 15: since 15 < 24, we can represent this as 0F.
type = 2, count = 24: this fits in 1 byte: 58 18
type = 5, count = 1234567: we need at least 4 bytes: BA 00 12 D6 87
xxs . ($"") $ cborTC 0 15 xxs . ($"") $ cborTC 2 24 xxs . ($"") $ cborTC 5 1234567
Naturals are encoded as counts of type 0.
A negative number n is encoded as the non-negative count -1 - n with type 1, but we have no need for this case.
For a blob, we encode its length as a count of type 2 then append the bytes of the blob itself. Text is similar, except the type is 3.
For an array, we encode its length as count of type 4 then append the encodings of the array elements.
For a map, that is, a list of key-value pairs, we encode the size as a count of type 5 then encode each key followed by the encoding of its associated value.
We can attach a numeric tag to an item by prefacing it with a count of type 6. It’s polite to tag CBOR messages with 55799 to clue in the receiver, which just means we often prefix a CBOR message with the bytes D9 D9 F7.
data CBOR
= CBORZ Integer
| CBORBlob [Int]
| CBORText String
| CBORArray [CBOR]
| CBORMap [(CBOR, CBOR)]
| CBORTag Integer CBOR
cborLookup k = asum . map go where
go (CBORText s, v) | k == s = Just v
go _ = Nothing
cborEncode = \case
CBORZ n
| n >= 0 -> cborTC 0 n
| otherwise -> cborTC 1 $ -1 - n
CBORBlob bs -> cborTC 2 (length bs) . (++) (chr <$> bs)
CBORText s -> cborTC 3 (length s) . (++) s
CBORArray a -> cborTC 4 (length a) . foldr (.) id (cborEncode <$> a)
CBORMap m -> cborTC 5 (length m) . foldr (.) id (map (\(k, v) -> cborEncode k . cborEncode v) m)
CBORTag n c -> cborTC 6 n . cborEncode c
We show CBOR values using human-friendly CBOR diagnostic notation:
instance Show CBOR where
showsPrec _ = \case
CBORZ n -> shows n
CBORBlob blob -> ("h'"++) . foldr (.) id ((++) . xx . chr <$> blob) . ("'"++)
CBORText s -> shows s
CBORArray a -> ('[':) . foldr (.) id (intersperse (", "++) $ shows <$> a) . (']':)
CBORMap m -> ('{':) . foldr (.) id (intersperse (", "++) $ map (\(k, v) -> shows k . (": "++) . shows v) m) . ('}':)
CBORTag n x -> shows n . ('(':) . shows x . (')':)
We whip up a parser for CBOR diagnostic notation:
cborme = item where
item = txt <|> blob <|> hblob <|> num <|> arr <|> kvs
num = do
n <- readInteger <$> some digitChar <* space
CBORTag n <$> (spch '(' *> item <* spch ')') <|> pure (CBORZ n)
txt = CBORText <$> (char '"' *> many (sat (/= '"')) <* spch '"')
blob = CBORBlob <$> (char '\'' *> many (ord <$> sat (/= '\'')) <* spch '\'')
hblob = CBORBlob <$> (char 'h' *> char '\'' *> many hexcode <* spch '\'')
arr = CBORArray <$> (spch '[' *> sepBy item (spch ',') <* spch ']')
kvs = CBORMap <$> (spch '{' *> sepBy kv (spch ',') <* spch '}')
kv = (,) <$> item <* spch ':' <*> item
spch = (<* space) . char
Hopefully our output agrees with https://cbor.me/ and https://cbor.nemo157.com/.
putStrLn $ either ("error: "++) (xxs . ($"") . cborEncode)
$ parse (space *> cborme <* eof) "" [r|
55799({"content":
{ "ingress_expiry" : 12345678901234567890
, "sender":h'04'
, "canister_id":h'1234'
, "request_type":"query"
, "method_name":"function"
, "arg":'parameter'
}})
|]
We encode an IC request as a CBOR map:
cborRequest rty can met arg sender t = CBORMap [ (CBORText "ingress_expiry", CBORZ t) , (CBORText "sender" , CBORBlob sender) , (CBORText "canister_id" , CBORBlob can) , (CBORText "request_type" , CBORText rty) , (CBORText "method_name" , CBORText met) , (CBORText "arg" , CBORBlob arg) ]
We set the sender to the byte 04 to make the call anonymous.
The ingress_expiry deadline is given in nanoseconds since the epoch.
For our purposes, request_type is query or call or read_state.
The canister_id is the raw canister ID, not the human-friendly version such
as fxa77-fiaaa-aaaae-aaana-cai, which we’ll call the cooked canister ID.
To uncook it to a raw canister ID, decode using base-32, ignoring the dashes,
then discard the initial 4-byte CRC checksum:
unbase32 :: String -> [Int]
unbase32 = go 0 0 . concatMap (maybe [] pure . (`lookup` tab)) where
go acc len rest
| 8 <= len = fromIntegral q : go r (len - 8) rest
| n:ns <- rest = go (acc*32 + n) (len + 5) ns
| otherwise = []
where (q, r) = divMod acc $ 2^(len - 8)
tab = zip (['a'..'z'] ++ ['2'..'7']) [0..]
uncook :: String -> [Int]
uncook = drop 4 . unbase32
For example:
concatMap (xx . chr) $ uncook "fxa77-fiaaa-aaaae-aaana-cai"
To send, we make a POST call to an URL such as
https://icp0.io/api/v2/canister/fxa77-fiaaa-aaaae-aaana-cai/query. To call a
local dev net instead, replace https://icp0.io with http://localhost:PORT
where PORT is the port chosen by dfx.
The body of the POST is the CBOR map containing a single key "content" whose value is the above map representing the IC request.
singleBody content = ($"") $ cborEncode $ CBORTag 55799 $ CBORMap [(CBORText "content", content)]
We set the Content-Type header to application/cbor. The canister ID and
request type in the path must match those in the CBOR message. This is mildly
irritating because it implies we must use both versions of the canister ID: the
cooked ID goes in the URL and the raw ID goes in the CBOR message. The request
type also appears in both places but thankfully it’s the same short string both
times.
Calling the management canister is a special case: instead of aaaaa-aa, the
URL path may need to contain the effective canister id, which is typically
the canister_id field in the arg. See the spec for details. This design
smell results from the system needing to know where a call originated from.
dump = putStr . xxs =<< jsEval "respblob;"
do
now <- readInteger <$> jsEval "Date.now();"
let
reqType = "query"
canid = "fxa77-fiaaa-aaaae-aaana-cai"
arg = ord <$> unxxs "4449444c036d7b6d6f6c04efd6e40271e1edeb4a71a2f5ed880400c6a4a19806010102012f034745540000"
content = cborRequest
reqType
(uncook canid)
"http_request"
arg
[4] -- Anonymous query.
((now + 120000) * 1000000)
body = xxs $ singleBody content
url = "https://icp0.io/api/v2/canister/" ++ canid ++ "/" ++ reqType
jsEval_ $ concat ["mkFetcher(runme_out, dumpRespBlob, ", show url, ", ", show body, ");"]
Life is easy when request_type is query. The HTTP response is a
CBOR-encoded map containing a status key. On success, the value is the blob
replied, and there will also be a reply field whose value is a map
containing an arg field that holds the reply blob. On failure, the status
field is rejected; see the spec for other fields present.
I’ve gotten away with demos which looked for the first occurrence of 0x63 0x61 0x72 0x67 (CBOR for the text "arg"), and called a one-off decoding routine that assumed the bytes immediately afterwards are a CBOR-encoded blob holding the reply. But the right way is to build a CBOR decoder.
Our decoder lacks support for payloads of indefinite length, which seem to be unused by the Internet Computer.
cborParser = do
(ty, r) <- (`divMod` 32) . ord <$> anyChar
when (r > 27) $ charserBad "bad count"
count <- if r < 24 then pure $ fromIntegral r else unbiggie . map ord <$> replicateM (2^(r - 24)) anyChar
let n = fromIntegral count
case ty of
0 -> pure $ CBORZ count
1 -> pure $ CBORZ -count
2 -> CBORBlob . map ord <$> replicateM n anyChar
3 -> CBORText <$> replicateM n anyChar
4 -> CBORArray <$> replicateM n cborParser
5 -> CBORMap <$> replicateM n (liftA2 (,) cborParser cborParser)
6 -> CBORTag count <$> cborParser
_ -> charserBad "unsupported type"
For example:
putStrLn $ either ("parse error: "++) show . parse cborParser "" . unxxs . filter (not . isSpace) $ [r|
d9d9f7a3667374617475736872656a65637465646b72656a6563745f636f6465046e72656a656374
5f6d6573736167656d756e696e697469616c697a6564
|]
When request_type is call, the HTTP response has an empty body, and the
status code is 202 on success, and 4xx/5xx on failure, though this code is not
entirely reliable because the Internet Computer requires consensus before
locking in answers.
For some applications, we can ignore this status code, solely relying on future
query replies to show the effects of a call. This has some drawbacks. For
example, the processing state seems impossible to report, and extra work is
needed to match up a particular call with its result. Thus we may prefer to
issue a read_state request to inquire about a specific call.
We need SHA-256 for this task. Later, we’ll need other members of the SHA-2
family so we implement them at the same time. These hash functions involve the
first 64 fractional bits of square roots and cube roots of primes. Most
implementations look up precomputed answers, but we figure out the h and k
constants ourselves, via fixed-point arithmetic and the Newton-Raphson method:
prec = 2^80 data Fixie = Fixie Integer deriving Eq instance Ring Fixie where Fixie a + Fixie b = Fixie (a + b) Fixie a - Fixie b = Fixie (a - b) Fixie a * Fixie b = Fixie (a * b `div` prec) fromInteger = Fixie . (prec *) instance Field Fixie where recip (Fixie f) = Fixie $ prec*prec `div` f truncate (Fixie f) = div f prec fracBits n = (`mod` 2^n) . agree . map (truncate . (2^n*)) where agree (a:t@(b:_)) = if a == b then a else agree t primes = sieve [2..] where sieve (p:t) = p : sieve [n | n <- t, n `mod` p /= 0] newton f f' = iterate $ \x -> x - f x / f' x rt2 n = newton (\x -> x^2 - fromIntegral n) (\x -> 2*x) 1 rt3 n = newton (\x -> x^3 - fromIntegral n) (\x -> 3*x^2) 1 h64 = fromIntegral . fracBits 64 . rt2 <$> take 8 primes :: [Word64] k64 = fromIntegral . fracBits 64 . rt3 <$> take 80 primes :: [Word64] h32 = fromIntegral . (`shiftR` 32) <$> h64 :: [Word] k32 = fromIntegral . (`shiftR` 32) <$> take 64 k64 :: [Word] h32_224 = fromIntegral . fracBits 64 . rt2 <$> take 8 (drop 8 primes) :: [Word]
The wordPad32 and wordPad64 functions pad the input and append its length,
and interpret it as a sequence of big-endian words; 32-bit words for SHA-224
and SHA-256 and 64-bit words for SHA-512.
The chunk32 and chunk64 functions take these words 16 at a time, and use
bitwise operations to blast their bits all over an array w of 64 words.
They call round32 and round64 which apply more bitwise operations together
with the k constants to mix the array into the current hash value, which is
initialized using the h constants.
The final hash value of 16 big-endian words is converted back to bytes.
Placing the SHA-224, SHA-256, and SHA-512 in close proximity makes their
differences obvious. SHA-224 is the same as SHA-256 except it discards the
last word of the hash and uses different h constants. SHA-512 encodes the
length in 128 bits rather than 64 bits, and operates on 64-bit words rather
than 32-bit words. SHA-512 also has 80 rounds of k constants rather than 64.
sha224 = concatMap (biggie 4) . init . foldl chunk32 h32_224 . chunksOf 16 . wordPad32
sha256 = concatMap (biggie 4) . foldl chunk32 h32 . chunksOf 16 . wordPad32
sha512 = concatMap (biggie 8) . foldl chunk64 h64 . chunksOf 16 . wordPad64
wordPad32 :: String -> [Word]
wordPad32 s = map unbiggie $ chunksOf 4 $ ord <$> s ++ pad
where
l = length s
pad = '\x80' : replicate (mod (-9 - l) 64) '\0' ++ biggie 8 (8*l)
wordPad64 :: String -> [Word64]
wordPad64 s = map unbiggie $ chunksOf 8 $ ord <$> s ++ pad
where
l = length s
pad = '\x80' : replicate (mod (-17 - l) 128) '\0' ++ biggie 16 (8*l)
chunk32 h c = zipWith (+) h $ foldl round32 h $ zipWith (+) k32 w where
w = c ++ foldr1 (zipWith (+)) [w, s0, drop 9 w, s1] where
s0 = foldr1 (zipWith xor) $ map (<$> tail w) [ror 7, ror 18, shr 3]
s1 = foldr1 (zipWith xor) $ map (<$> drop 14 w) [ror 17, ror 19, shr 10]
ror = flip rotateR
shr = flip shiftR
chunk64 h c = zipWith (+) h $ foldl round64 h $ zipWith (+) k64 w where
w = c ++ foldr1 (zipWith (+)) [w, s0, drop 9 w, s1] where
s0 = foldr1 (zipWith xor) $ map (<$> tail w) [ror 1, ror 8, shr 7]
s1 = foldr1 (zipWith xor) $ map (<$> drop 14 w) [ror 19, ror 61, shr 6]
ror = flip rotateR
shr = flip shiftR
round32 :: [Word] -> Word -> [Word]
round32 [a,b,c,d,e,f,g,h] kw = [t1 + t2, a, b, c, d + t1, e, f, g] where
s0 = foldr1 xor $ map (rotateR a) [2, 13, 22]
s1 = foldr1 xor $ map (rotateR e) [6, 11, 25]
ch = (e .&. f) `xor` (complement e .&. g)
t1 = h + s1 + ch + kw
maj = (a .&. b) `xor` (a .&. c) `xor` (b .&. c)
t2 = s0 + maj
round64 :: [Word64] -> Word64 -> [Word64]
round64 [a,b,c,d,e,f,g,h] kw = [t1 + t2, a, b, c, d + t1, e, f, g] where
s0 = foldr1 xor $ map (rotateR a) [28, 34, 39]
s1 = foldr1 xor $ map (rotateR e) [14, 18, 41]
ch = (e .&. f) `xor` (complement e .&. g)
t1 = h + s1 + ch + kw
maj = (a .&. b) `xor` (a .&. c) `xor` (b .&. c)
t2 = s0 + maj
For example:
putStrLn $ xxs $ sha256 "" putStrLn $ xxs $ sha256 "abc"
Rather than calling a canister’s method with an arg, a read_state request
asks for several path values. In CBOR the paths are present in the paths
field in the content map, where the value is an array of the items are being
read; each item itself is an arrays of blobs.
In the spec a path (array of blobs) often appears as strings separated by
forward slashes, like /request_status/<request_id>/reply.
Computing the request ID of a call is like to CBOR-encoding it, except we only need the hash of each field rather than the field itself:
Strings and blobs are easy to hash, as these are what hash functions were designed for in the first place.
Naturals such as ingress_expiry deadline are first LEB128-encoded before
hashing.
To hash a map, namely a list of key-value pairs, we recursively replace each key and value with the concatenation of their hashes, then sort this list of hashes, then concatenate them all and hash. The sorting guarantees we get the same map no matter how the key-value pairs were originally ordered.
To hash an array, we hash each item, then concatenate and hash.
The request ID is the hash of the content value (and not the map
containing this value) according to this scheme.
sort [] = [] sort (x:xt) = sort (filter (<= x) xt) ++ [x] ++ sort (filter (> x) xt) leb128 n | n < 128 = [chr $ fromIntegral n] | otherwise = chr (128 + fromIntegral r) : leb128 q where (q, r) = divMod n 128 cborHash = sha256 . \case CBORZ n -> leb128 n CBORBlob blob -> chr <$> blob CBORText s -> s CBORArray a -> concat $ cborHash <$> a CBORMap m -> concat $ sort $ map (\(k, v) -> cborHash k ++ cborHash v) m
Sending a read_state call is much like sending a query or call, though
the request_type is naturally read_state, and instead of a method and arg,
we have a paths field that holds an array of arrays, which we populate with
a singleton array whose entry is the array of two blobs: the blob
"request_status" followed by the request ID.
readStateBody paths sender t = singleBody $ CBORMap [ (CBORText "ingress_expiry", CBORZ t) , (CBORText "sender" , CBORBlob sender) , (CBORText "request_type" , CBORText "read_state") , (CBORText "paths" , CBORArray $ CBORArray . map CBORBlob <$> paths) ]
The response to a read_state request is a CBOR map with a certificate
field whose value is itself a CBOR map. This inner map has a field tree that
uses nested arrays to encode a state hash tree, and a field signature that
shows the IC approves of the given tree.
We name the format of the state hash tree wally, because it’s difficult to
find its specification.
data HashTree = TreeEmpty | TreeHash [Int] | TreeLeaf String | TreeLabel String HashTree | TreeFork HashTree HashTree deriving Show unwally (CBORArray a) = case a of [CBORZ 0] -> TreeEmpty [CBORZ 1, x, y] -> TreeFork (unwally x) (unwally y) [CBORZ 2, CBORBlob k, x] -> TreeLabel (chr <$> k) (unwally x) [CBORZ 3, CBORBlob v] -> TreeLeaf $ chr <$> v [CBORZ 4, CBORBlob v] -> TreeHash v
In the CBOR-decoded tree field, we seek a tree labeled by the request ID,
and within we seek a leaf labeled with status. If the bytes of this leaf are
replied then we seek a leaf labeled with reply that contains the reply.
This differs subtly to HTTP responses to query calls. There, we had a
CBOR-encoded map, with keys like status and reply. Here, we have a tree
that is encoded via a custom scheme into nested CBOR arrays, where keys like
status and reply are blobs in the middle of length-3 arrays of the
wally format.
There are multiple ways to encode a state tree, but it seems the Internet
Computer encodes the status and reply fields in certain ways that allow
the following function to pluck them out of the CBOR message:
hashTreePluck s = \case TreeFork x y -> hashTreePluck s x <|> hashTreePluck s y TreeLabel k (TreeLeaf v) | k == s -> Just v TreeLabel _ t -> hashTreePluck s t _ -> Nothing
The following demo that makes an anonymous call, then as the dfx tool does,
repeatedly issues read_state requests with its request ID until its status is
known. If "replied", then we show the reply, and also the returned state tree.
parseState = do
Right (CBORTag _ (CBORMap m)) <- parse cborParser "" <$> jsEval "respblob;"
let
Just (CBORBlob b) = cborLookup "certificate" m
Right (CBORTag _ (CBORMap certmap)) = parse cborParser "" $ chr <$> b
Just t = unwally <$> cborLookup "tree" certmap
case hashTreePluck "status" t of
Just s -> do
nextOut
putStrLn $ "status: " ++ s
when (s == "replied") $ case hashTreePluck "reply" t of
Just s -> putStr "reply:" *> print s *> print t
Nothing -> putStrLn "reply field missing!"
Nothing -> do
putStr "retry"
nextOut
putStrLn "no status field; retrying soon..."
demo_readState reqId canid = do
now <- readInteger <$> jsEval "Date.now();"
let
t = (now + 120000) * 1000000
body = xxs $ readStateBody [[ord <$> "request_status", ord <$> unxxs reqId]] [4] t
url = "https://icp0.io/api/v2/canister/" ++ canid ++ "/read_state"
putStr url
nextOut
putStr body
do
now <- readInteger <$> jsEval "Date.now();"
let
canid = "fxa77-fiaaa-aaaae-aaana-cai"
reqType = "call"
arg = "4449444c036d7b6d6f6c04efd6e40271e1edeb4a71a2f5ed880400c6a4a19806010102012f034745540000"
url = "https://icp0.io/api/v2/canister/" ++ canid ++ "/" ++ reqType
exampleContent = cborRequest
reqType
(uncook canid)
"http_request"
(ord <$> unxxs arg)
[4] -- Anonymous query.
((now + 120000) * 1000000)
body = xxs $ singleBody exampleContent
reqId = cborHash exampleContent
jsEval_ $ concat ["mkFetcher(runme_out, div => postCall(div, `", xxs reqId, "`, `", canid, "`), ", show url, ", ", show body, ");"]
Calls that are not anonymous are cryptographically signed.
The dfx tool uses ECDSA signatures on the secp256k1 curve, which is given by
\(y^2 = x^3 + 7\) over the field \(\mathbb{F}_p\) where \(p\) is:
pk1 = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 :: Integer
data Fpk1 = Fpk1 { unFpk1 :: Integer } deriving (Show, Eq)
instance Ring Fpk1 where
Fpk1 a + Fpk1 b = Fpk1 $ (a + b) `mod` pk1
Fpk1 a - Fpk1 b = Fpk1 $ (a - b) `mod` pk1
Fpk1 a * Fpk1 b = Fpk1 $ (a * b) `mod` pk1
fromInteger x = Fpk1 $ x `mod` pk1
instance Field Fpk1 where recip = (^(pk1-2))
There are:
orderk1 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
solutions, and this set of points forms a cyclic group with respect to a well-known operation involving finding the intersection between a straight line through given points and the curve.
One solution is designated the base point:
basek1x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 basek1y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
Like all other non-trivial points, the base point generates all the others.
Traditionally, mathematicians write the group operation with additive notation, so one speaks of point addition and point doubling. This causes some friction with cryptographers, who use multiplicative notation when discussing the discrete log problem and cryptosystems built upon its variants. We choose multiplicative notation in our code.
Computing the group operation needs nothing beyond high school mathematics. If the two given points are distinct, we write down the equation of the line through them and a little algebra reveals where it intersects the curve a third time. When the two inputs points are the same, a touch of differential calculus determines the slope of a tangent line instead.
Either way, we must also negate the y-coordinate of the intersection so that the operation satisfies the group axioms.
data Ek1Affine = Ek1Affine (Maybe (Fpk1, Fpk1)) deriving Show
instance Ring Ek1Affine where
(+) = undefined
(-) = undefined
Ek1Affine (Just a) * Ek1Affine (Just b) = Ek1Affine $ addEk1Affine a b
Ek1Affine a * Ek1Affine b = Ek1Affine $ a <|> b
fromInteger 1 = Ek1Affine Nothing
addEk1Affine (px, py) (qx, qy)
| px /= qx = slope $ (qy - py) / (qx - px)
| py == qy && py /= 0 = slope $ 3*px^2 / (2*py)
| otherwise = Nothing
where
slope t = Just (rx, ry) where
rx = t^2 - px - qx
ry = (px - rx)*t - py
basek1Affine = Ek1Affine $ Just (basek1x, basek1y)
In practice, divisions are expensive, so we postpone them as long as possible, replacing many frequent divisions into one single final division, at the cost of a few more multiplications. In other words, we use projective coordinates:
basek1 = Ek1 $ Just (basek1x, basek1y, 1) data Ek1 = Ek1 (Maybe (Fpk1, Fpk1, Fpk1)) deriving Show instance Ring Ek1 where (+) = undefined (-) = undefined Ek1 (Just a) * Ek1 (Just b) = Ek1 $ lineEk1 a b Ek1 a * Ek1 b = Ek1 $ a <|> b fromInteger 1 = Ek1 Nothing instance Field Ek1 where recip (Ek1 m) = Ek1 $ (\(x, y, z) -> (x, -y, z)) <$> m lineEk1 (px, py, pz) (qx, qy, qz) | u /= 0 = Just (u*w, t*(u0*u2 - w) - t0*u3, u3*v) | t == 0 = tanEk1 (px, py, pz) | otherwise = Nothing where sq a = a * a t0 = py*qz t1 = qy*pz t = t0 - t1 u0 = px*qz u1 = qx*pz u = u0 - u1 u2 = sq u v = pz*qz w = sq t*v - u2*(u0 + u1) u3 = u*u2 -- Assume y /= 0 since group has odd order. tanEk1 (x, y, z) = Just $ (u*w, t*(v - w) - 2*sq (u*y), sq u * u) where sq a = a*a t = 3*sq x u = 2*y*z v = 2*u*x*y w = sq t - 2*v normk1 (Ek1 m) = (\(x,y,z) -> let z1 = recip z in (x*z1, y*z1)) <$> m
A private key d is a positive integer less than the order. For example:
dZoo = 0xdd730a61f98fe573c7676e5957727c01cedf3c5a04beba39df92445e0bd2ec87
The corresponding public key is basek1^d. (If we had used additive notation,
instead of exponentiation, we would call this d times the base point.)
A popular representation of such a public key is the byte 04 followed
by the x- and y-coordinates in big-endian, both taking 32 bytes.
In this format, the public key corresponding to dZoo turns out to be:
04 3cc849c77d5ead3aeaf2ea821dc85d6bb10483bbe97875d010ada2629e4a863e 815793de69ae4ffce46d52c4b14ed1a3ae40e85b53b5cb6c7ed6de89d80c4305
This is an uncompressed point; the 04 indicates both coordinates are
present. In other contexts we might see a compressed point, where only the
y-coordinate is given, and the initial byte is 02 or 03 depending on the
parity of the x-coordinate so the recipient can recover the correct one.
To produce the DER encoding of an ECDSA public key, we prepend the magic string:
derECDSA = unxxs "3056301006072a8648ce3d020106052b8104000a034200" derECDSAFromXY x y = concat [derECDSA, "\x04", biggie 32 x, biggie 32 y]
We convert a DER public key to a principal IDs by computing its SHA224 hash then appending the byte 02, indicating a self-authenticating ID in Internet Computer parlance. Like other principal IDs, we can cook self-authenticating IDs by prepending a CRC32 checksum, encoding with base32, and inserting dashes. Some tools expect these.
crc :: String -> Word
crc = xor 0xffffffff . foldl go 0xffffffff where
go rem c = xor (shiftR rem 8) $ crcTable!!(fromIntegral $ xor (fromIntegral $ fromEnum c) (rem .&. 0xff))
crcTable :: [Word]
crcTable = [iterate inner n!!8 | n <- [0..255]] where
inner c
| c .&. 1 == 1 = xor 0xedb88320 bumped
| otherwise = bumped
where bumped = shiftR c 1
cook s = intercalate "-" . chunksOf 5 . base32 $ biggie 4 (crc s) ++ s
base32Alphabet = ['a'..'z'] ++ ['2'..'7']
base32 s = (base32Alphabet!!) . unbits <$> ws
where
ws = chunksOf 5 $ foldr ($) [] $ (bits 8 . ord) <$> s
unbits w = go 0 $ take 5 $ w <> repeat 0 where
go acc [] = acc
go acc (h:t) = go (acc*2 + h) t
bits k n
| k == 0 = id
| otherwise = bits (k - 1) q . (r:) where (q, r) = divMod n 2
The following takes a private key and shows corresponding public key in various formats. It is slow because of our simplistic arbitrary precision arithmetic implementation, but (barely) bearable on modern browsers.
privateKeyInfo d = case normk1 $ basek1^d of
Nothing -> "must avoid order of curve"
Just (Fpk1 x, Fpk1 y) -> let
der = derECDSAFromXY x y
prin = sha224 der ++ "\x02"
in unlines
[ "public key (point on y^2 = x^3 + 7): " ++ show (x, y)
, "DER public key: " ++ concatMap xx der
, "Principal ID (raw): " ++ (xx =<< prin)
, "Principal ID (cooked): " ++ cook prin
]
demo_publicKey = putStr $ privateKeyInfo $ unbiggie $ map ord $ unxxs
"dd730a61f98fe573c7676e5957727c01cedf3c5a04beba39df92445e0bd2ec87"
jsEval_ "slowMo('demo_publicKey');"
To sign a 256-bit message with ECDSA, we need a random 256-bit k
It is vital that k be distinct for each message and unpredictable. Famous
breaches have occurred due to failures to observe these rules.
An alternative to randomly choosing k is to use a keyed hash of the message.
For our demo we do so in an ad hoc manner: see RFC 6979 for the right way to do
it! (Or better yet, switch to Ed25519 signatures.)
The result is two 256-bit integers r and s. We write them in big-endian, so
each takes 32 bytes, and concatenate them to form the signature.
egcd a b | r == 0 = (b, (0, 1)) | (d, (x, y)) <- egcd b r = (d, (y, x - q*y)) where (q, r) = divMod a b signk1 d msg = biggie 32 =<< [r, s] where n = orderk1 k = unbiggie $ map ord $ sha256 $ biggie 32 d ++ msg kinv = if a < 0 then a + n else a where (_, (a, _)) = egcd k n Just r = unFpk1 . fst <$> normk1 (basek1^k) z = unbiggie $ ord <$> msg s = (z + r*d) `mod` n * kinv `mod` n
A signed call is like an anonymous call with a few extra fields.
We place the DER-encoded public key in the sender_pubkey field of the CBOR
map in the POST body.
We place the principal ID corresponding to the public key in the sender field
of the content map. (Yes, this is redundant, as it contains the same
information as sender_pubkey.)
We compute the request ID as above and append it to the domain separator
\x0Aic-request, then sign its SHA-256 hash (viewed as a big-endian 256-bit
number) with ECDSA to yield a 64-byte signature, which we place in the
sender_sig field.
signedCall der sig content = ($"") $ cborEncode $
CBORTag 55799 $ CBORMap
[ (CBORText "content", content)
, (CBORText "sender_pubkey", CBORBlob $ ord <$> der)
, (CBORText "sender_sig", CBORBlob $ ord <$> sig)
]
The following (eventually) makes signed calls just like dfx, except there’s
no nonce. (Speaking of which, the lower bits of the ingress_expiry field may
suffice as a nonce for some applications because it’s measured in nanoseconds!)
The sender is the example dZoo key.
demo_signedCall = do
now <- readInteger <$> jsEval "Date.now();"
let
Just (Fpk1 x, Fpk1 y) = normk1 $ basek1^dZoo
der = derECDSAFromXY x y
prin = sha224 der ++ "\x02"
t = (now + 120000) * 1000000
canid = "fxa77-fiaaa-aaaae-aaana-cai"
arg = ord <$> unxxs "4449444c036d7b6d6f6c04efd6e40271e1edeb4a71a2f5ed880400c6a4a19806010102012f034745540000"
reqType = "call"
url = "https://icp0.io/api/v2/canister/" ++ canid ++ "/" ++ reqType
content = cborRequest reqType (uncook canid) "http_request" arg (ord <$> prin) t
reqId = cborHash content
sig = signk1 dZoo $ sha256 $ "\x0aic-request" ++ reqId
body = xxs $ signedCall der sig content
putStr $ xxs reqId
nextOut
putStr url
nextOut
putStr canid
nextOut
putStr body
jsEval_ "clickGate('demo_signedCall', postSignedCall);"
We neglect to sign the read state calls, which would take even longer, so this demo should eventually result in a 403. (Thus even without a signature, we can distinguish between a pending call and a completed call.)
We follow along the client authentication protocol. Think of the NNS app: the user clicks a button which opens a new tab, where they authenticate themselves by, say, touching a security key. Afterwards they have power over their neurons thanks to requests that are signed with session keys that temporarily have the same power as the user’s private key.
I recommend Ed25519 session keys, because ECDSA is easy to mess up. Ed25519 takes place on the elliptic curve \(y^2 = x^3 + 486662 x^2 + x\) over \(\mathbb{F}_p\) where \(p\) is:
pEd = 2^255 - 19 :: Integer
data FpEd = FpEd { unFpEd :: Integer } deriving (Show, Eq)
instance Ring FpEd where
FpEd a + FpEd b = FpEd $ (a + b) `mod` pEd
FpEd a - FpEd b = FpEd $ (a - b) `mod` pEd
FpEd a * FpEd b = FpEd $ (a * b) `mod` pEd
fromInteger x = FpEd $ x `mod` pEd
instance Field FpEd where recip = (^(pEd-2))
Computing square roots modulo \(p\) happens to be easy:
sqrtFpEd :: FpEd -> FpEd sqrtFpEd x | t == x = candidate | t == -x = candidate * i where candidate = x^div(pEd + 3)8 t = candidate^2 i = 2^div(pEd - 1)4
The order of the curve turns out to be 8 times a large prime, given by:
orderEd = 2^252 + 27742317777372353535851937790883648493
We work in the subgroup whose order is this large prime.
Instead of working directly on this curve, a clever mapping transports us to a twisted Edwards curve:
\[ -x^2 + y^2 = 1 + d x^2 y^2 \]
where \(d = -121665/121666\) (in \(\mathbb{F}_p\)).
Here, the group operation is elegant: there is no need to distinguish between the line and tangent cases, nor between finite points and the point at infinity.
xFromYEd s y = if fromIntegral (unFpEd x' `mod` 2) == s then x' else -x' where
x' = sqrtFpEd $ (y^2 - 1) / (dEd * y^2 + 1)
dEd = -121665 / 121666 :: FpEd
data EdAffine = EdAffine FpEd FpEd deriving Show
instance Ring EdAffine where
EdAffine x1 y1 * EdAffine x2 y2 = EdAffine
((x1*y2 + x2*y1) / (1 + t))
((y1*y2 + x1*x2) / (1 - t))
where t = dEd*x1*x2*y1*y2
(+) = undefined
(-) = undefined
fromInteger = undefined
baseEdAffine = EdAffine (xFromYEd 0 y) y where y = 4 / 5
As before, this is too slow, so we introduce projective coordinates to replace all divisions with one final division. We also spot a chance to apply Karatsuba’s trick.
We ought to split off the squaring case after all, to shave off more multiplications. But the new code is already ugly enough.
data Ed = Ed FpEd FpEd FpEd deriving Show
instance Ring Ed where
Ed x1 y1 z1 * Ed x2 y2 z2 = Ed
(u*(x1y2 + x2y1) * u2m)
(u*((x1 + y1)*(x2 + y2) - x1y2 - x2y1) * u2p)
(u2m*u2p)
where
x1y2 = x1*y2
x2y1 = x2*y1
t = dEd*x1*x2*y1*y2
u = z1*z2
u2 = u*u
u2m = u2 - t
u2p = u2 + t
(+) = undefined
(-) = undefined
fromInteger = undefined
baseEd = Ed (xFromYEd 0 y) y 1 where y = 4 / 5
normEd (Ed x y z) = (x*z1, y*z1) where z1 = recip z
An Ed25519 seed should be 256 bits of entropy. Rather than use the seed directly to generate keys and message nonces, we first compute the SHA-512 hash of the seed. We generate the key pair from the first half of the hash, and the second half for signing.
We treat the first half of the hash as little-endian 256-bit number, which requires some processing before using it as a secret key. The cofactor is 8, that is, the order of the elliptic curve group is 8 times a large prime, so we clear the lower 3 bits. We also clear the highest bit and set the second-highest bit, avoiding any wackiness from bluntly reducing modulo the order of the curve.
The public key is the base point multiplied by the private key, and is encoded as a 256-bit number by writing its y-coordinate in little-endian then setting the highest bit to the parity of the x-coordinate.
unle = foldr (\c n -> 256 * n + fromIntegral (ord c)) 0 keypair seed = ((s, hiHalf), asBytesEd $ baseEd^s) where (loHead:loTail, hiHalf) = splitAt 32 $ sha512 seed (rh:rt) = reverse loTail s = unle $ chr (ord loHead .&. 248):reverse (chr (ord rh .&. 63 .|. 64):rt) asBytesEd p = reverse $ chr (ord rh .|. s) : rt where (FpEd x, FpEd y) = normEd p (rh:rt) = reverse $ take 32 $ everLE y s = ((fromInteger x :: Int) .&. 1) * 128 sign ((s, hiHalf), pub) message = bigR ++ (take 32 $ everLE $ (hram*s + r) `mod` orderEd) where r = unle (sha512 $ hiHalf ++ message) `mod` orderEd bigR = asBytesEd $ baseEd^r hram = unle (sha512 $ bigR ++ pub ++ message) `mod` orderEd
We DER-encode the session public key by appending it to the magic string:
derEd25519 = unxxs "302A300506032B6570032100"
Enter a hex seed below to see what Ed25519 derives from it. (Be patient!)
demo_ed25519Seed = putStr $ unlines
[ "s: " ++ show s
, "s, little-endian hex: " ++ xxs (take 32 $ everLE s)
, "public key: " ++ xxs pub
, "DER public key: " ++ xxs (derEd25519 <> pub)
, "HMAC key: " ++ xxs hi
]
where
((s, hi), pub) = keypair $ unxxs seed
seed = "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f"
jsEval_ "slowMo('demo_ed25519Seed');"
To communicate with the Internet Identity service, we add a listener for the
message event in this window. Initially a callback that does nothing, we
later change it to callbacks that suit different parts of the protocol.
When authorization is desired, we open the Internet Identity app in another
window, which should soon send this window an authorize-ready message. We
then pass the session key to the Internet Identity Service in an
authorize-client message.
In the happy case, we receive an authorize-client-success response
containing an delegation expiration time, the user’s public key, and
a signature authorizating the delegation.
Enter a seed to generate an Ed25519 for the Internet Identity service to sign.
Choose a good seed, or sign in with a test identity. (Again, be patient!)
isHexit c
| '0' <= c, c <= '9' = True
| 'a' <= c, c <= 'f' = True
| 'A' <= c, c <= 'F' = True
| otherwise = False
demo_auth = do
seed <- jsEval "iiseed.value;"
if all isHexit seed
then let
(_, pub) = keypair $ unxxs seed
js = "auth('" ++ seed ++ "','" ++ (xxs $ derEd25519 <> pub) ++ "');"
in do
putStr js
nextOut
putStrLn $ "seed: " ++ seed
putStrLn $ "calling " ++ js
else putStr "invalid seed"
jsEval_ "clickGate('demo_auth', postAuth);"
It’s now a matter of stuffing the keys and signatures in the right places.
The user’s public key goes in sender_pubkey, and its SHA-224
hash followed by 0x02 goes in the sender field of the content map.
The sender_sig is a signature produced by the session key on the request
ID prefixed with "\nic-request".
We also add a new sender_delegation field, whose value is a map containing
the session public key, expiration, and the signature authorizing the
delegation.
data Delegation = Delegation
{ _del_key :: String
, _del_sig :: String
, _del_exp :: Integer
} deriving Show
delegateCall del der sig content = ($"") $ cborEncode $ CBORTag 55799 $ CBORMap
[ (CBORText "content", content)
, (CBORText "sender_delegation", CBORArray [CBORMap
[ (CBORText "delegation", CBORMap
[ (CBORText "pubkey", CBORBlob $ ord <$> der)
, (CBORText "expiration", CBORZ $ _del_exp del)
])
, (CBORText "signature" , CBORBlob $ ord <$> _del_sig del)
]])
, (CBORText "sender_pubkey", CBORBlob $ ord <$> _del_key del)
, (CBORText "sender_sig", CBORBlob $ ord <$> sig)
]
Run the previous demo to authenticate a seed, then run the following demo to make a delegated call. Observe that code on this webpage signs the request using the Ed25519 key derived from a chosen seed, yet from the canister’s point of view, the user authenticated by the Internet Identity server made the call.
demo_delegateCall = do
let
rty = "call"
canid = "fxa77-fiaaa-aaaae-aaana-cai"
met = "http_request"
arg = ord <$> unxxs "4449444c036d7b6d6f6c04efd6e40271e1edeb4a71a2f5ed880400c6a4a19806010102012f034745540000"
now <- readInteger <$> jsEval "Date.now();"
del <- Delegation
<$> (unxxs <$> jsEval "xx(caller);")
<*> (unxxs <$> jsEval "xx(delegation_sig);")
<*> (readInteger <$> jsEval "delegation_expiry;")
ed@(_, pub) <- keypair . unxxs <$> jsEval "xx(seed);"
let
der = derEd25519 ++ pub
prin = sha224 (_del_key del) ++ "\x02"
t = (now + 120000) * 1000000
url = "https://icp0.io/api/v2/canister/" ++ canid ++ "/" ++ rty
content = cborRequest rty (uncook canid) met arg (ord <$> prin) t
reqId = cborHash content
sig = sign ed $ "\x0aic-request" ++ reqId
body = xx =<< delegateCall del der sig content
putStr url
nextOut
putStr body
nextOut
putStrLn $ "Request ID: " ++ (xxs reqId)
putStrLn $ "Body: " ++ body
jsEval_ "clickGate('demo_delegateCall', postDelegate);"
It is said "the nice thing about standards is that you have so many to choose from", but in our case, we’re forced to swallow a soup of standards due to choices made by others.
little-endian: Ed25519 favours little-endian. So does WebAssembly, and formats specific to the Internet Computer.
big-endian: Favoured by CBOR, secp256k1, and the SHA-2 family (SHA-224, SHA-256, SHA-512).
LEB128: This handy variable-length little-endian format pops up here and there.
SHA-224: Used to derive principal IDs from DER-encoded public keys, and to derive account IDs from principal IDs.
SHA-256: Used to compute request IDs.
SHA-512: Used by Ed25519 signatures, and canister ECDSA chain-derivation.
DER: A public-key encoding scheme. Luckily, we can largely ignore this format, and just know we must occasionally add annoying magic prefixes to public keys.
CBOR: Calls to the IC are HTTPS requests whose body are CBOR-encoded
messages. Also, I heard you like CBOR so we put CBOR in the CBOR: the
certificate field contains a blob that is actually a CBOR-encoded message.
secp256k1: Signature scheme used by dfx and canister ECDSA. Also features in Bitcoin.
Ed25519: We use this for delegation.
base32: Used to cook raw principal IDs to make them friendlier to humans.
base64: Arises somewhere in the certified data pipeline.
CRC32: Used to checksum principal IDs and account IDs to reduce the
likelihood of disastrous typos. There are multiple CRC32s out there; the
cooked ID checksum uses the same variant as gzip.
In addition, we should also be aware of several Internet Computer formats:
raw principal: Principals represent identities on the Internet Computer. The last byte indicates the kind of principal, for example, 01 = canister; 02 = public key (self-authenticating ID); 04 = anonymous.
cooked principal: A raw principal prepended with a CRC32 checksum and written in base32 with dashes inserted every 5 characters.
Candid: A format that may optionally be employed by arg fields to methods.
Canisters work just fine without Candid, though consider wrapping custom
formats in a minimal blob Candid buffer to avoid confusing various tools.
Also, responses to http_request should be a certain Candid buffer.
wally: I have no idea what the true name is. I’m referring to the format of the CBOR-within-a-CBOR certificate field whose specification is hard to find. (Spoiler: it’s here.)
reconstruct: Like wally, but it computes a hash of a state tree instead of encoding it. Used for certified data.
After slogging through spec after spec, I feel I’ve earned the right to rant about design smells.
CBOR: Do we need it? We already hash the call in a custom format to derive a request ID. Could we come up with a similar encoding format? Then we could simply hash a custom-encoded call to derive its request ID.
Nested CBOR maps, state trees, and Candid records seem to have a lot in common. Is there a way to have one format to rule them all?
URL path: A custom format could make it easy to pluck out the canister ID and request type from the body of an HTTP request, so there’d be no need to duplicate this information in the URL path.
Management canister: rather than the "effective canister ID" business, I’d
prohibit canisters from exporting methods beginning with #, and change those
management canister calls containing a canister_id field to built-in
per-canister primitive calls such as #update_settings.
If possible, I’d move some calls to the ic0 system API to allow tasks like
checking the caller is a controller before proceeding. (This is tricky with
the current design because of potential races.)
Methods: I wonder if it would make more sense to have at most one call
method and one update method with standard names, and essentially move the
method name to the arg. In the current system, no cycles are charged for
inspecting an incoming call to determine the method name, which might be
exploited.
For example, instead of a canister call that appends a given byte to some
string, it might be cheaper to have 256 specialized methods so the canister
can avoid analyzing an arg. Method names also open up potential
vulnerabilities: what if an adversary makes canisters with many similar long
method names, or method names with the same hash?
ECDSA: Why does the signer send s instead of its inverse? The verifier only needs the inverse of s.
DER: Interoperability is cool, but I can’t help feeling it’d be better to DER-encode keys outside the system.