New crypto features support

[tarakby]

Issue To Be Solved

• add new features to the crypto contract, as required by the upcoming Flow protocol epoch features:
  • validation of public keys
  • support the signature scheme BLS and its corresponding hashing algorithm.

Suggest A Solution

This is modified version of the file crypto.cdc. Many functions are copied from the original code but I pasted the entire file for a better clarity, as there a few changes here and there. I've added some comments in the code to help understand the changes.

This code is a starting point to discuss and improve, I'm open to all suggestions making the APIs easier to use while keeping all the features needed for the epoch switch implementation in Flow protocol.

// the functions outside the crypto contract are meant to be implemented by the fvm 
// in Go. I can implement/support implementing these functions.

// the first 2 functions could be part of a same interface 
//(as they are both related to signature algos)

// verify is a low level signature verification function,
// that uses a signature scheme to verify a signature under hash(tag, data) and a public key.
pub fun verify(
    signature: [UInt8],
    tag: String,
    signedData: [UInt8],
    publicKey: [UInt8],
    signatureAlgorithm: String,
    hashAlgorithm: String
): Bool

// validatePublicKey is a low level function that checks if the input array 
// is a valid serialization of a public key of the given signature scheme.
pub fun validatePublicKey(
    publicKey: [UInt8],
    algorithm: String
): Bool

// low level hash function that computes hash(tag, data). 
// tag is mixed with data in a way dependent of the hash algo, this can be detailed in a doc later. 
// for instance, sha2(tag, data) = sha2(tag || data)
pub fun hash(
        data: [UInt8],
        tag: String,
        algorithm: String
    ): [UInt8] 


pub contract Crypto {

    // SignatureAlgorithm 
    pub struct SignatureAlgorithm {
        pub let name: String
        init(name: String) {       }
        
        // a method to validate a public key serialization
        pub fun validatePublicKey(publicKey: [UInt8]): Bool {
            return validatePublicKey(publicKey: publicKey, algorithm:self.name)
        }
        
        // a method to verify a signature
        pub fun verify(        
            signature: [UInt8],
            tag: String,
            signedData: [UInt8],
            publicKey: [UInt8],
            hashAlgorithm: HashAlgorithm ): Bool {

            return verify( 
                signature: signature, 
                tag: tag, 
                signedData: signedData, 
                publicKey: publicKey, 
                signatureAlgorithm:self.name, 
                hashAlgorithm: hashAlgorithm.name) 
        }

    }
    
   // supported SignatureAlgorithm
    
    // ECDSA  
    pub let ECDSA_P256: SignatureAlgorithm
    pub let ECDSA_Secp256k1: SignatureAlgorithm
    // BLS
    // why is it called BLS_BLS12381? 
    //   - BLS is the signature scheme, just like ECDSA
    //   - bls12381 is the name of the curve, just like P256 or Secp256k1
    //   - B, L and S in the scheme and the curve are not referring to the same people, and hence the redundancy :)  
    pub let BLS_BLS12381: SignatureAlgorithm 
    // with BLS being declared here, users could verify BLS signatures, only using the hasher KMAC_128_BLS_BLS12381 though (the Go implementation will enforce it).
    // But most importantly :
    //     - the staking contract can verify BLS public keys are valid.
    //     - the staking contract can verify a BLS proof of possession, required in the future 
    // for the BFT support


    // HashAlgorithm 
    pub struct HashAlgorithm {
        pub let name: String 
        init(name: String) {     }

        // tag is required for KMAC. 
        // sha2/sha3(tag, data) called with tag="" is equivalent to calling the standard sha2/sha3(data)
        pub fun hash(_ data: [UInt8], tag: String): [UInt8] {
            return hash(data: data, tag: tag, algorithm: self.name) 
        }
    }

    // supported HashAlgorithm 
    
    pub let SHA2_256: HashAlgorithm
    pub let SHA3_256: HashAlgorithm
    // KMAC_128_BLS_BLS12381 is an instance of KMAC_128 that this customized to be used with BLS and the curve BLS12381
    // why not declaring the generic KMAC_128? KMAC requires more customization inputs compared to a standard hash function, 
    // so it can't be supported by "HashAlgorithm". I already added "tag" to support the customized KMAC.
    pub let KMAC_128_BLS_BLS12381: HashAlgorithm 
    // could be added in another contract if considered too specific, the other contract would then also contain
    // the signature algo BLS_BLS12381


    // PublicKey is a structure with bytes and a signature algorithm
    pub struct PublicKey {
        pub let publicKey: [UInt8]
        pub let signatureAlgorithm: SignatureAlgorithm
        priv let valid: Bool
        // we could add: priv let valicationChecked: Bool to cash the validation result

        init(publicKey: [UInt8], signatureAlgorithm: SignatureAlgorithm) {
            self.publicKey = publicKey
            self.signatureAlgorithm = signatureAlgorithm
            self.valid = false
        }
        
        // not sure this getter in needed
        pub fun GetValidity(): Bool {
            return self.valid
        }

        // this is needed to verify ECDSA or BLS public keys are valid, 
        // which is required for the staking contract, but is also useful for other cases (there are many scenarios
        // where validating public keys is a must)
        pub fun Validate(): Bool {
            // we could check validationChecked here, to avoid re-validating
            self.valid = self.signatureAlgorithm.validatePublicKey(publicKey: self.publicKey)
            return self.valid
        }

        pub fun isValid(
            signature: [UInt8],
            signedData: [UInt8],
            domainSeparationTag: String,
            hashAlgorithm: HashAlgorithm
        ): Bool {
            // if we use valicationChecked, we can call self.Validate() here
            // to make sure self.valid is updated, without re-computating the result

            // Ensure the key is valid
            if !self.valid {
                return false
            }

            // Ensure the signature is valid
            return self.signatureAlgorithm.verify(
                signature: signature,
                tag: domainSeparationTag,
                signedData: signedData,
                publicKey: self.publicKey,
                hashAlgorithm: hashAlgorithm
            )
        }
    }

    // KeyListEntry is a structure representing one public key with other data
    pub struct KeyListEntry {
        pub let keyIndex: Int
        pub let publicKey: PublicKey
        pub let hashAlgorithm: HashAlgorithm
        pub let weight: UFix64
        pub let isRevoked: Bool

        init(
            keyIndex: Int,
            publicKey: PublicKey,
            hashAlgorithm: HashAlgorithm,
            weight: UFix64,
            isRevoked: Bool
        ) {
            self.keyIndex = keyIndex
            self.publicKey = publicKey
            self.hashAlgorithm = hashAlgorithm
            self.weight = weight
            self.isRevoked = isRevoked
        }
    }

    // KeyList is a list of KeyListEntry
    pub struct KeyList {
        priv let entries: [KeyListEntry]

        init() {
            self.entries = []
        }

        /// Adds a new key with the given weight
        pub fun add(
            _ publicKey: PublicKey,
            hashAlgorithm: HashAlgorithm,
            weight: UFix64
        ): KeyListEntry {

            let keyIndex = self.entries.length
            let entry = KeyListEntry(
                keyIndex: keyIndex,
                publicKey: publicKey,
                hashAlgorithm: hashAlgorithm,
                weight: weight,
                isRevoked: false
            )
            self.entries.append(entry)
            return entry
        }

        /// Returns the key at the given index, if it exists.
        /// Revoked keys are always returned, but they have `isRevoked` field set to true
        pub fun get(keyIndex: Int): KeyListEntry? {
            if keyIndex >= self.entries.length {
                return nil
            }

            return self.entries[keyIndex]
        }

        /// Marks the key at the given index revoked, but does not delete it
        pub fun revoke(keyIndex: Int) {
            if keyIndex >= self.entries.length {
                return
            }
            let currentEntry = self.entries[keyIndex]
            self.entries[keyIndex] = KeyListEntry(
                keyIndex: currentEntry.keyIndex,
                publicKey: currentEntry.publicKey,
                hashAlgorithm: currentEntry.hashAlgorithm,
                weight: currentEntry.weight,
                isRevoked: true
            )
        }

        /// Returns true if the given signatures are valid for the given signed data
        pub fun isValid(
            signatureSet: [KeyListSignature],
            signedData: [UInt8]
        ): Bool {
            var validWeights: UFix64 = 0.0
            let seenKeyIndices: {Int: Bool} = {}

            for signature in signatureSet {
                // Ensure the key index is valid
                if signature.keyIndex >= self.entries.length {
                    return false
                }

                // Ensure this key index has not already been seen
                if seenKeyIndices[signature.keyIndex] ?? false {
                    return false
                }

                // Record the key index was seen
                seenKeyIndices[signature.keyIndex] = true

                // Get the actual key
                let key = self.entries[signature.keyIndex]

                // Ensure the key is not revoked
                if key.isRevoked {
                    return false
                }

                // Ensure the signature is valid
                if !key.publicKey.isValid(
                    signature: signature.signature,
                    signedData: signedData,
                    domainSeparationTag: Crypto.domainSeparationTagUser,
                    hashAlgorithm: key.hashAlgorithm
                ) {
                    return false
                }

                validWeights = validWeights + key.weight
            }
            return validWeights >= 1.0
        }
    }

    // one signature entry
    pub struct KeyListSignature {
        pub let keyIndex: Int
        pub let signature: [UInt8]

        init(keyIndex: Int, signature: [UInt8]) {
            self.keyIndex = keyIndex
            self.signature = signature
        }
    }


    priv let domainSeparationTagUser: String

    init() {

        // Initialize constants

        self.ECDSA_P256 = SignatureAlgorithm(name: "ECDSA_P256")
        self.ECDSA_Secp256k1 = SignatureAlgorithm(name: "ECDSA_Secp256k1")
        self.BLS_BLS12381 = SignatureAlgorithm(name: "BLS_BLS12381")

        self.SHA2_256 = HashAlgorithm(name: "SHA2_256")
        self.SHA3_256 = HashAlgorithm(name: "SHA3_256")
        self.KMAC_128_BLS_BLS12381 = HashAlgorithm(name: "KMAC_128_BLS_BLS12381")

        self.domainSeparationTagUser = "user"
    }
}

[tarakby]

@SupunS @turbolent , I've updated the suggestion above following the new changes in Cadence. A lot of the changes are described in comments since most of it will need to be implemented in Go, and not in Cadence anymore. Please have a look at the comments and let me know if you have any changes.
I can support/help implementing the FVM changes of course.

// low level hash function that computes hash(tag, data). 
// tag is mixed with data in a way dependent of the hash algo, this can be detailed in a doc later. 
// for instance, sha2(tag, data) = sha2(tag || data) 
pub fun hashWithTag(
        data: [UInt8],
        tag: String,
        algorithm: HashAlgorithm
): [UInt8] 

// the "usual" hash function that only requires the data to hash
pub fun hash( 
    data: [UInt8],
    algorithm: HashAlgorithm
): [UInt8] {
    return hashWithTag(data: data, tag: "", algorithm: algorithm) 
}


// supported HashAlgorithm 
// - SHA2_256: HashAlgorithm, already defined in Cadence
// - SHA3_256: HashAlgorithm, already defined in Cadence
// New:  KMAC_128_BLS_BLS12381 is an instance of KMAC_128 that this customized to be used with BLS and the curve BLS12381
// why not declaring the generic KMAC_128? KMAC requires more customization inputs compared to a standard hash function, 
// so it can't be supported by "HashAlgorithm". I already added "tag" to support the customized KMAC, but KMAC_128 would 
// require even more parameters.
// - KMAC_128_BLS_BLS12381: HashAlgorithm 

// supported SigningAlgorithm 
// - ECDSA_P256: already defined in Cadence
// - ECDSA_Secp256k1: already defined in Cadence
// New: pub let BLS_BLS12381: SignatureAlgorithm 
// why is it called BLS_BLS12381? 
//   - BLS is the signature scheme, just like ECDSA
//   - bls12381 is the name of the curve, just like P256 or Secp256k1
//   - B, L and S in the scheme and the curve are not referring to the same people, and hence the redundancy :)  
// with BLS being declared here, users could verify BLS signatures, only using the hasher KMAC_128_BLS_BLS12381 though (the Go implementation will enforce it).
// But most importantly :
//     - the staking contract can verify BLS public keys are valid.
//     - the staking contract can verify a BLS proof of possession, required in the future 
// for the BFT support



// PublicKey is the Cadence built-in type.
// It would need to support a new field "valid" , and new methods. 
//
// - Fields:
// struct PublicKey {
//    let publicKey: [UInt8]
//    let signatureAlgorithm: SignatureAlgorithm
//    let valid: Bool
//}
//
// Methods:
// isValid validates a signature. It returns false if !self.valid. The hashing is done by calling the hash version 
// with a tag parameter.
//  - isValid(
//         signature: [UInt8],
//         signedData: [UInt8],
//         domainSeparationTag: String,
//         hashAlgorithm: HashAlgorithm
//     ): Bool 
// Validate is needed to verify ECDSA or BLS public keys are valid, 
// which is required for the staking contract, but is also useful for other cases (there are many scenarios
// where validating public keys is a must).
// The function sets the internal field "isValid".
// - pub fun Validate(): Bool
// We could also a getter for "isValid" not sure this getter in needed
//  - pub fun GetValidity(): Bool 
// 
// The methods implementation should be implemented in Go I guess, after "PublicKey" became a native type. 


pub contract Crypto {

    pub struct KeyListEntry {
        pub let keyIndex: Int
        pub let publicKey: PublicKey
        pub let hashAlgorithm: HashAlgorithm
        pub let weight: UFix64
        pub let isRevoked: Bool

        init(
            keyIndex: Int,
            publicKey: PublicKey,
            hashAlgorithm: HashAlgorithm,
            weight: UFix64,
            isRevoked: Bool
        ) {
            self.keyIndex = keyIndex
            self.publicKey = publicKey
            self.hashAlgorithm = hashAlgorithm
            self.weight = weight
            self.isRevoked = isRevoked
        }
    }

    pub struct KeyList {

        priv let entries: [KeyListEntry]

        init() {
            self.entries = []
        }

        /// Adds a new key with the given weight
        pub fun add(
            _ publicKey: PublicKey,
            hashAlgorithm: HashAlgorithm,
            weight: UFix64
        ): KeyListEntry {

            let keyIndex = self.entries.length
            let entry = KeyListEntry(
                keyIndex: keyIndex,
                publicKey: publicKey,
                hashAlgorithm: hashAlgorithm,
                weight: weight,
                isRevoked: false
            )
            self.entries.append(entry)
            return entry
        }

        /// Returns the key at the given index, if it exists.
        /// Revoked keys are always returned, but they have `isRevoked` field set to true
        pub fun get(keyIndex: Int): KeyListEntry? {
            if keyIndex >= self.entries.length {
                return nil
            }

            return self.entries[keyIndex]
        }

        /// Marks the key at the given index revoked, but does not delete it
        pub fun revoke(keyIndex: Int) {
            if keyIndex >= self.entries.length {
                return
            }
            let currentEntry = self.entries[keyIndex]
            self.entries[keyIndex] = KeyListEntry(
                keyIndex: currentEntry.keyIndex,
                publicKey: currentEntry.publicKey,
                hashAlgorithm: currentEntry.hashAlgorithm,
                weight: currentEntry.weight,
                isRevoked: true
            )
        }

        /// Returns true if the given signatures are valid for the given signed data
        pub fun isValid(
            signatureSet: [KeyListSignature],
            signedData: [UInt8]
        ): Bool {

            var validWeights: UFix64 = 0.0

            let seenKeyIndices: {Int: Bool} = {}

            for signature in signatureSet {

                // Ensure the key index is valid

                if signature.keyIndex >= self.entries.length {
                    return false
                }

                // Ensure this key index has not already been seen

                if seenKeyIndices[signature.keyIndex] ?? false {
                    return false
                }

                // Record the key index was seen

                seenKeyIndices[signature.keyIndex] = true

                // Get the actual key

                let key = self.entries[signature.keyIndex]

                // Ensure the key is not revoked

                if key.isRevoked {
                    return false
                }

                // Ensure the signature is valid

                if !key.publicKey.isValid(
                    signature: signature.signature,
                    tag: Crypto.domainSeparationTagUser,
                    signedData: signedData,
                    hashAlgorithm:key.hashAlgorithm
                ) {
                    return false
                }

                validWeights = validWeights + key.weight
            }

            return validWeights >= 1.0
        }
    }

    pub struct KeyListSignature {
        pub let keyIndex: Int
        pub let signature: [UInt8]

        pub init(keyIndex: Int, signature: [UInt8]) {
            self.keyIndex = keyIndex
            self.signature = signature
        }
    }

    priv let domainSeparationTagUser: String

    init() {
        // Initialize constants
        self.domainSeparationTagUser = "user"
    }
}

[turbolent]

@tarakby Thanks for the update, this looks good.

A couple of questions:

• In the hashWithTag function, the tag parameter is named tag. In the isValid function, the tag parameter is named domainSeparationTag. Are there semantic differences between the two, or are they the same, and thus should maybe be named the same?
• I assume PublicKey's constructor function would stay as it is now, i.e. have the parameters publicKey: [UInt8] and signatureAlgorithm: SignatureAlgorithm, the new field isValid: Bool would be computed and not stored, correct?

[tarakby]

• It makes more sense to use a different name in each. Btw, customizer and customHash may be better names than tag and hashWithTag. The reason is that a hash or a MAC function provides this customization feature but applications can use that feature for different purposes (authentication, customization, domain separation..).
  In our case, we're using the feature as a domain separation tag in signatures, so the isValid api sees that parameter as domainSeparationTag.

• The constructor of PublicKey should initialize isValid to false, unless we want Validate() to be called inside the constructor and initialize the field with the correct value. We can decide if we should allow creating a PublicKey with a false isValid, or to never create such keys and make the constructor fail instead.
  There are many option on how to implement this, I'm open to better suggestions!

[turbolent]

It would be nice if isValid would be properly initialized. Is validation expensive?

I guess the question is: Do we want to make it impossible to have invalid public keys? Or should it be possible to construct an invalid public key, and then users have to ensure to always check isValid before using it? Are there use-cases for working with invalid public keys?

@dete any thoughts?

[tarakby]

• An invalid key must never result in a signature verification being valid. So the options here are either:
  • to allow constructing a public key (isValid set by default to false, or to the output of Validate()) but the signature verification function returns false if the key isValid field is false. I've suggested this in the first Cadence implementation
  • OR to not allow constructing an invalid key.

I have a preference for option 1, because of an API extension I'm thinking of for when we support BFT measures (verify proof of possession for BLS keys), which works better with option 1.

The validation function is not very expensive. But it would be better to avoid re-validation.

[turbolent]

Yeah, I asked if validation is expensive because I was thinking of just setting isValid to the outcome of validation. That way there is no chance of a user forgetting to validate the instance.

We could also make isValid internally lazy and compute it and re-use the result (memoize it).

Always validating in the constructor and initializing isValid to the outcome of validation, and making it a stored would make it a bit easier to make the type storable, importable, and exportable.

[tarakby]

Just adding that we still need a way to export the isValid field somehow, that's the information the staking contract would need.

[turbolent]

With import and export here is meant interaction between Cadence and the outside world, e.g. a script argument is imported as a Cadence value, and a value returned from a script is exported from Cadence.

Is the isValid flag going to be read off-chain?

The field doesn't need to be exportable if it's only accessed on-chain, e.g. by the staking contract.

[tarakby]

Is the isValid flag going to be read off-chain?

I'm not sure what are the off-chain cases, do you have examples?

Btw, the value on-chain must be only accessible for reads not writes (the value should not be settable to true for instance after it got set to false).

[turbolent]

what are the off-chain cases, do you have examples?

I don't know about them either, that's why I was asking. I guess it's not important then

the value on-chain must be only accessible for reads not writes

Right, we'll make the field let, i.e. constant / read-only

[SupunS]

I'm curious as to why do we need both the isValid field and validate() method exposed to the user.

So validate() method caches it result in the isValid field. The next time the validate() is called, we can simply return the value of isValid I guess.
If we always call the validate() method inside the constructor, then even if someone calls the validate() method, they will always get the value from isValid field. Could we only expose the isValid then?

Are there any cases where we need to call validate() explicitly?

[turbolent]

@SupunS Yes, like I mentioned a little bit further up in the comments, users should only see a let isValid: Bool field (i.e. read-only), no validate() function.

[turbolent]

I had missed this in the last PR (#829), sorry about the confusion!

[SupunS]

Oh, sorry I was under the impression that we expose both. Thanks for the clarification.

I can clean it up when doing the changes for adding the valid field.
(btw I think we have to name the field it as valid, because there's a function with the same name isValid)