search

spruceid / ssi

Core library for decentralized identity.
https://spruceid.dev
Apache License 2.0
193 stars 61 forks source link

Ascertain degree of output length determinism for base58 encoding #95

Closed wyc closed 3 years ago

wyc commented 3 years ago

We should have the answer to this following riddle to ensure that our libraries are correct in all cases, not just the common ones. This is currently hard-coded in places like did-key's resolution fn.

When an arbitrary bytearray of length n is encoded as base58check, what is the length of bytearray output?

clehner commented 3 years ago

That length check refers to the length of the decoded data - the bytes before encoding with multibase/base58btc. did:key doesn't place limits on the size of the encoded string or the inner bytes. But some key types have specific-sized public keys. I've responded about the length of secp256k1 keys in https://github.com/spruceid/ssi/pull/93#discussion_r580304443.

The length of a byte string encoded into base58 would be: Math.ceil(byteString.length * 8 / Math.log2(58))

For example, a secp256k public key of 33 bytes, plus the 2-byte multicodec prefix is 35 bytes: Math.ceil(35 * 8 / Math.log2(58)) = 48. This corresponds to the length of "Q3shokFTS3brHcDQrn82RUDfCZESWL1ZdCEJwekUDPQiYBme" in the example did:key. Then adding the prefix "did:key:z" (z in multicodec indicating base58btc) gives the complete DID which is 57 characters in length.

wyc commented 3 years ago

I see we consider variable length base58 encoding here: https://github.com/spruceid/ssi/blob/0e16f72a2fea361ea5472bfa59dd9296135c6f80/did-key/src/lib.rs#L76

Thanks!