Adding support for different hash algos
|
Bos, M. van den (Matthijs)
Hi,
I am looking into replacing SHA256 with another hash algo, at least for creating the tx merkle tree.
I ran into the fact that `SecureHash`, which is used by the merkle tree (and everywhere else) seems to be quite hardcoded to be SHA256:
When I started to create a PR that introduces the interface/refactors this to an interface with an implementation for SHA256 I noticed that this change will probably create API breaks.
Would you be open to allowing me to introducing a SecureHash interface, with an implementation for SHA256? I would probably like to try to make this algo configurable in a similar way to the signature scheme. To make it work, we could probably make less use of all those static methods and instead call methods on (a singleton for) the configured hash algo.
Happy to hear your thoughts.
Kind regards, Matthijs van den Bos
-- ING Bank | Distributed Ledger Technology Team
----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- |
|
|
|
Hi,
It's intentionally not an interface. Apps aren't allowed to extend the platform with new hash functions, because of the centrality of hashing to the protocol and the need for global coordination. So making it an interface wouldn't be an accepted code change, though of course you can do whatever you like for local experimentation. Introducing a new hash function is very difficult to do in a way that doesn't break backwards compatibility. You'd introduce a new subtype of SecureHash and then new factory methods that run the algorithm and return the new sealed subtype. Most parts of the code pass around SecureHash, not SecureHash.SHA256, so should be oblivious to the change. In a few places there might be hard-coded uses of SHA256. In every place where a hash is calculated using the existing methods you'd need to consider a backwards compatibility strategy. For instance the right algorithm to use might depend on the algorithm used by other transactions, or the network parameters. For ZKP related experimentation, which I guess this is related to, you could just hack around and not worry about backwards compat for now. Then the work would have to be redone later in a compatible way, but the issues would have been fully explored. |
|
|
|
Bos, M. van den (Matthijs)
Hi Mike,
This is indeed related to ZKP. How did you guess? ;-)
And thanks for the quick reaction. I do understand the need for careful coordination on this, and the unforeseen impact a change of hash function might have on things like interoperability between business networks. It wasn’t my intention to make it an App level setting.
That said, I do expect that the hash function will have to change sooner or later and when that happens, I fear it might not be as simple as adding a subtype to SecureHash the way it is implemented right now. There seems no common interface between these subtypes: e.g. callers of SecureHash call the static `sha256()` methods directly and there is nothing like a `hash()` method. In some cases where it is a parameter, `SecureHash.SHA256` is often the type. Would you consider a change where the setup with the sealed class remains the same, but we do introduce an interface for SecureHash and its subtypes? This would open it up for adding alternate hash functions later, without giving up control to Apps. And it would allow us to proceed in a future-proof way.
Alternatively, if this is not an option: can we safely assume that if we solve/explore all our other problems and are ready to go beyond experimentation, that introducing support for other hash functions would be supported by R3? We prefer to invest our time in enriching Corda and not in a fork.
Regards, Matthijs
From: "corda-dev@groups.io" <corda-dev@groups.io> on behalf of "Mike Hearn via Groups.Io" <mike@...>
Hi, ----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- |
|
|
|
Certainly, we'd love to find a way to have this be a contribution.
I'm not involved in these sorts of decisions anymore so it'd be something to take up with Matthew, who I've CCd.
WRT sealed class vs interface, aren't they equivalent except that a sealed class can only be extended by the platform?
If there are places that are unnecessarily SHA2 specific then generalising them would be a good place to start. It should just be a case of SecureHash.SHA256 -> SecureHash in most places. I believe some places may be specific to SHA2 because they're sensitive
to width.
Putting the .sha256() method behind an interface is trickier because, as noted, you may often need to be picky about which implementation you use depending on various factors like network params, old data, interop with other nodes, etc. Context would get lost
behind the interface. For making an isolated Corda that just switches to a different hash algo completely, without worrying about interop, it's a reasonable way to do it. You could start by just replacing calls to .sha256() with calls to a generic .hash()
method for instance that takes the algo to use from the network parameters or a hard-coded setting (so there's only one line to fork).
Matthew may have more views on the right way to do this.
From: corda-dev@groups.io <corda-dev@groups.io> on behalf of Bos, M. van den (Matthijs) via Groups.Io <matthijs.van.den.bos@...>
Sent: Monday, February 24, 2020 17:28 To: corda-dev@groups.io <corda-dev@groups.io> Subject: Re: [corda-dev] Adding support for different hash algos Hi Mike,
This is indeed related to ZKP. How did you guess? ;-)
And thanks for the quick reaction. I do understand the need for careful coordination on this, and the unforeseen impact a change of hash function might have on things like interoperability between business networks. It wasn’t my intention to make it an App level setting.
That said, I do expect that the hash function will have to change sooner or later and when that happens, I fear it might not be as simple as adding a subtype to SecureHash the way it is implemented right now. There seems no common interface between these subtypes: e.g. callers of SecureHash call the static `sha256()` methods directly and there is nothing like a `hash()` method. In some cases where it is a parameter, `SecureHash.SHA256` is often the type. Would you consider a change where the setup with the sealed class remains the same, but we do introduce an interface for SecureHash and its subtypes? This would open it up for adding alternate hash functions later, without giving up control to Apps. And it would allow us to proceed in a future-proof way.
Alternatively, if this is not an option: can we safely assume that if we solve/explore all our other problems and are ready to go beyond experimentation, that introducing support for other hash functions would be supported by R3? We prefer to invest our time in enriching Corda and not in a fork.
Regards, Matthijs
From:
"corda-dev@groups.io" <corda-dev@groups.io> on behalf of "Mike Hearn via Groups.Io" <mike@...>
Hi, ----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- |
|
|
|
Bos, M. van den (Matthijs)
Good to hear. Thanks for your input so far.
@Matthew, is this also you opinion? In that case we will want to invest the time. All aligned with you of course. This is a quite fundamental change after all. Just for fun and games and to see what we would have to touch, I have hacked together the following change. No best practices, and no generic hash function at all yet, so bear with: - Add SHA-384 as alternative hash function to SecureHash (digest is longer, so good to see what that does) - Use SHA-384 only for tx hash (i.e. merkle tree hashes), all others, such as attachments, pubkeys, jars, signed data, etc., remain SHA-256. - Tried to only *add* things to the API, so CI won't break... All tests pass. Please see here for the diff: https://github.com/corda/corda/compare/release/os/4.5...mvdbos:feature/cleanup-replace-hash - There are a few places where SHA-256 is assumed implicitly. Just changing types to SecureHash.SHA256 -> SecureHash broke things. - Streams sometimes use Google Guava SHA-256 and are therefore not changeable to something else as is - Hash concat for NotaryChangeTx and ContractUpgradeTx components are different. Unclear why. Ideally identical and part of SecureHash or some base transaction type - A lot of schema upgrades necessary, because tx id columns are 32 bytes everywhere. Perhaps we should just make it 64 bytes immediately, so that most future digests (e.g. SHA-512) will fit? Otherwise it will need a code change (schemas/entities) and new liquibase script every time this is impacted by a digest length increase. I guess the performance impact is negligible? You could start by just replacing calls to .sha256() with calls to a generic .hash() method for instance that takes the algo to use from the network parameters or a hard-coded setting (so there's only one line to fork).Yes, this would be my approach too. Perhaps we should refine this further, to specify a hash function per thing to be hashed. The tx hash and merkle tree node/leaf hashes are the ones most impacted by any interop and/or ZKP. The other ones (attachments, pubkeys, jars, signed data, etc.) are more 'internal' to my mind, probably pubkey is an exception too. Perhaps we want to be able to set them independently. The different hash functions would then be configurable as part of network parameters. This would be a change without impact as longs as the hash functions remain what they are now, but allow flexibility for future cases (like ZKP, or interop with other platforms). WRT sealed class vs interface, aren't they equivalent except that a sealed class can only be extended by the platform?In many ways yes, and I can see that if you really wanted to prevent anyone else to implement it, a sealed class can have value. It does force the extending classes to be nested, which I don't really like. I would not be afraid to use an interface, because we would only allow hash function change as part of network params. It will make the code a lot cleaner. But in the end both will serve. ________________________________________ From: corda-dev@groups.io <corda-dev@groups.io> on behalf of Mike Hearn via Groups.Io <mike@...> Sent: Wednesday, 26 February 2020 17:44 To: Bos, M. van den (Matthijs) via Groups.Io; corda-dev@groups.io; Matthew Nesbit Subject: Re: [corda-dev] Adding support for different hash algos Certainly, we'd love to find a way to have this be a contribution. I'm not involved in these sorts of decisions anymore so it'd be something to take up with Matthew, who I've CCd. WRT sealed class vs interface, aren't they equivalent except that a sealed class can only be extended by the platform? If there are places that are unnecessarily SHA2 specific then generalising them would be a good place to start. It should just be a case of SecureHash.SHA256 -> SecureHash in most places. I believe some places may be specific to SHA2 because they're sensitive to width. Putting the .sha256() method behind an interface is trickier because, as noted, you may often need to be picky about which implementation you use depending on various factors like network params, old data, interop with other nodes, etc. Context would get lost behind the interface. For making an isolated Corda that just switches to a different hash algo completely, without worrying about interop, it's a reasonable way to do it. You could start by just replacing calls to .sha256() with calls to a generic .hash() method for instance that takes the algo to use from the network parameters or a hard-coded setting (so there's only one line to fork). Matthew may have more views on the right way to do this. ________________________________ From: corda-dev@groups.io <corda-dev@groups.io> on behalf of Bos, M. van den (Matthijs) via Groups.Io <matthijs.van.den.bos@...> Sent: Monday, February 24, 2020 17:28 To: corda-dev@groups.io <corda-dev@groups.io> Subject: Re: [corda-dev] Adding support for different hash algos Hi Mike, This is indeed related to ZKP. How did you guess? ;-) And thanks for the quick reaction. I do understand the need for careful coordination on this, and the unforeseen impact a change of hash function might have on things like interoperability between business networks. It wasn’t my intention to make it an App level setting. That said, I do expect that the hash function will have to change sooner or later and when that happens, I fear it might not be as simple as adding a subtype to SecureHash the way it is implemented right now. There seems no common interface between these subtypes: e.g. callers of SecureHash call the static `sha256()` methods directly and there is nothing like a `hash()` method. In some cases where it is a parameter, `SecureHash.SHA256` is often the type. Would you consider a change where the setup with the sealed class remains the same, but we do introduce an interface for SecureHash and its subtypes? This would open it up for adding alternate hash functions later, without giving up control to Apps. And it would allow us to proceed in a future-proof way. Alternatively, if this is not an option: can we safely assume that if we solve/explore all our other problems and are ready to go beyond experimentation, that introducing support for other hash functions would be supported by R3? We prefer to invest our time in enriching Corda and not in a fork. Regards, Matthijs From: "corda-dev@groups.io" <corda-dev@groups.io> on behalf of "Mike Hearn via Groups.Io" <mike@...> Reply to: "corda-dev@groups.io" <corda-dev@groups.io> Date: Monday, 24 February 2020 at 15:48 To: "corda-dev@groups.io" <corda-dev@groups.io> Subject: Re: [corda-dev] Adding support for different hash algos Hi, It's intentionally not an interface. Apps aren't allowed to extend the platform with new hash functions, because of the centrality of hashing to the protocol and the need for global coordination. So making it an interface wouldn't be an accepted code change, though of course you can do whatever you like for local experimentation. Introducing a new hash function is very difficult to do in a way that doesn't break backwards compatibility. You'd introduce a new subtype of SecureHash and then new factory methods that run the algorithm and return the new sealed subtype. Most parts of the code pass around SecureHash, not SecureHash.SHA256, so should be oblivious to the change. In a few places there might be hard-coded uses of SHA256. In every place where a hash is calculated using the existing methods you'd need to consider a backwards compatibility strategy. For instance the right algorithm to use might depend on the algorithm used by other transactions, or the network parameters. For ZKP related experimentation, which I guess this is related to, you could just hack around and not worry about backwards compat for now. Then the work would have to be redone later in a compatible way, but the issues would have been fully explored. ----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- ----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- |
|
|
|
Bos, M. van den (Matthijs)
The factory/service/ for hashing should probably be modeled after the CryptoService/SignOnlyCryptoService and CryptoServiceFactory
----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- |
|
|
|
Matthew Nesbit
Hi Matthijs,
toggle quoted message
Show quoted text
Unfortunately, with regard to hash agility we knew we had very limited agility in Corda 1.0, but we needed to define a stable platform model and as Mike said there were security risks associated with uncontrolled flexibility. Being able to deliver quickly was also key to us being able to get people building an ecosystem on Corda. However, it also means we now have a responsibility to all these live systems running on Corda. As a result all new code going into Corda has to apply some very strict compatibility rules. In particular, we promise to never intentionally break compatibility with pre-existing compiled cordapps, or ledger historic transactions, or between Corda Open Source and Corda Enterprise. We are allowed to gate new features based upon the agreed network version, so that the software could potentially be ready to turn on changes in hash function based upon the network minimum platform version. Assuming that a full backward compatibility solution exists that ensures old states can be consumed inside new transaction on the new format. So making changes to the hashing, which is a fundamental part of the transaction ID calculations is extremely challenging. I am happy to hear models of how this might be done, but I can foresee lots of trouble trying to pass our full compatibility suite and cross-version checks. There would also have to be consideration of database schema migrations to handle larger hash fields and possibly the performance impacts of such changes. I don't myself know how we would make to the hashing under current constraints. If you still wish to pursue this work, perhaps you could create some driver integration tests in which you prepare some transactions under the old code (probably as binary blobs manually provisioned into the test DB using a fixed identity key). Then confirm that you have a strategy to be able to consume these old transaction outputs into a new one with new hashing. Matthew -----Original Message-----
From: Bos, M. van den (Matthijs) <Matthijs.van.den.Bos@...> Sent: 27 February 2020 11:33 To: Mike Hearn via Groups.Io <mike@...>; Bos, M. van den (Matthijs) via Groups.Io <matthijs.van.den.bos@...>; corda-dev@groups.io; Matthew Nesbit <matthew.nesbit@...> Subject: Re: [corda-dev] Adding support for different hash algos Good to hear. Thanks for your input so far. @Matthew, is this also you opinion? In that case we will want to invest the time. All aligned with you of course. This is a quite fundamental change after all. Just for fun and games and to see what we would have to touch, I have hacked together the following change. No best practices, and no generic hash function at all yet, so bear with: - Add SHA-384 as alternative hash function to SecureHash (digest is longer, so good to see what that does) - Use SHA-384 only for tx hash (i.e. merkle tree hashes), all others, such as attachments, pubkeys, jars, signed data, etc., remain SHA-256. - Tried to only *add* things to the API, so CI won't break... All tests pass. Please see here for the diff: https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fcorda%2Fcorda%2Fcompare%2Frelease%2Fos%2F4.5...mvdbos%3Afeature%2Fcleanup-replace-hash&;data=02%7C01%7C%7C315939cc049844c4d3e208d7bb78c83a%7Ca4be1f2e2d10419587cd736aca9b672c%7C0%7C1%7C637183999768294290&sdata=iJk%2BXk4vSqerXYUJ7INN5itjzwkLiC6zsg%2FkuC4sCCE%3D&reserved=0 - There are a few places where SHA-256 is assumed implicitly. Just changing types to SecureHash.SHA256 -> SecureHash broke things. - Streams sometimes use Google Guava SHA-256 and are therefore not changeable to something else as is - Hash concat for NotaryChangeTx and ContractUpgradeTx components are different. Unclear why. Ideally identical and part of SecureHash or some base transaction type - A lot of schema upgrades necessary, because tx id columns are 32 bytes everywhere. Perhaps we should just make it 64 bytes immediately, so that most future digests (e.g. SHA-512) will fit? Otherwise it will need a code change (schemas/entities) and new liquibase script every time this is impacted by a digest length increase. I guess the performance impact is negligible? You could start by just replacing calls to .sha256() with calls to a generic .hash() method for instance that takes the algo to use from the network parameters or a hard-coded setting (so there's only one line to fork).Yes, this would be my approach too. Perhaps we should refine this further, to specify a hash function per thing to be hashed. The tx hash and merkle tree node/leaf hashes are the ones most impacted by any interop and/or ZKP. The other ones (attachments, pubkeys, jars, signed data, etc.) are more 'internal' to my mind, probably pubkey is an exception too. Perhaps we want to be able to set them independently. The different hash functions would then be configurable as part of network parameters. This would be a change without impact as longs as the hash functions remain what they are now, but allow flexibility for future cases (like ZKP, or interop with other platforms). WRT sealed class vs interface, aren't they equivalent except that a sealed class can only be extended by the platform?In many ways yes, and I can see that if you really wanted to prevent anyone else to implement it, a sealed class can have value. It does force the extending classes to be nested, which I don't really like. I would not be afraid to use an interface, because we would only allow hash function change as part of network params. It will make the code a lot cleaner. But in the end both will serve. ________________________________________ From: corda-dev@groups.io <corda-dev@groups.io> on behalf of Mike Hearn via Groups.Io <mike@...> Sent: Wednesday, 26 February 2020 17:44 To: Bos, M. van den (Matthijs) via Groups.Io; corda-dev@groups.io; Matthew Nesbit Subject: Re: [corda-dev] Adding support for different hash algos Certainly, we'd love to find a way to have this be a contribution. I'm not involved in these sorts of decisions anymore so it'd be something to take up with Matthew, who I've CCd. WRT sealed class vs interface, aren't they equivalent except that a sealed class can only be extended by the platform? If there are places that are unnecessarily SHA2 specific then generalising them would be a good place to start. It should just be a case of SecureHash.SHA256 -> SecureHash in most places. I believe some places may be specific to SHA2 because they're sensitive to width. Putting the .sha256() method behind an interface is trickier because, as noted, you may often need to be picky about which implementation you use depending on various factors like network params, old data, interop with other nodes, etc. Context would get lost behind the interface. For making an isolated Corda that just switches to a different hash algo completely, without worrying about interop, it's a reasonable way to do it. You could start by just replacing calls to .sha256() with calls to a generic .hash() method for instance that takes the algo to use from the network parameters or a hard-coded setting (so there's only one line to fork). Matthew may have more views on the right way to do this. ________________________________ From: corda-dev@groups.io <corda-dev@groups.io> on behalf of Bos, M. van den (Matthijs) via Groups.Io <matthijs.van.den.bos@...> Sent: Monday, February 24, 2020 17:28 To: corda-dev@groups.io <corda-dev@groups.io> Subject: Re: [corda-dev] Adding support for different hash algos Hi Mike, This is indeed related to ZKP. How did you guess? ;-) And thanks for the quick reaction. I do understand the need for careful coordination on this, and the unforeseen impact a change of hash function might have on things like interoperability between business networks. It wasn't my intention to make it an App level setting. That said, I do expect that the hash function will have to change sooner or later and when that happens, I fear it might not be as simple as adding a subtype to SecureHash the way it is implemented right now. There seems no common interface between these subtypes: e.g. callers of SecureHash call the static `sha256()` methods directly and there is nothing like a `hash()` method. In some cases where it is a parameter, `SecureHash.SHA256` is often the type. Would you consider a change where the setup with the sealed class remains the same, but we do introduce an interface for SecureHash and its subtypes? This would open it up for adding alternate hash functions later, without giving up control to Apps. And it would allow us to proceed in a future-proof way. Alternatively, if this is not an option: can we safely assume that if we solve/explore all our other problems and are ready to go beyond experimentation, that introducing support for other hash functions would be supported by R3? We prefer to invest our time in enriching Corda and not in a fork. Regards, Matthijs From: "corda-dev@groups.io" <corda-dev@groups.io> on behalf of "Mike Hearn via Groups.Io" <mike@...> Reply to: "corda-dev@groups.io" <corda-dev@groups.io> Date: Monday, 24 February 2020 at 15:48 To: "corda-dev@groups.io" <corda-dev@groups.io> Subject: Re: [corda-dev] Adding support for different hash algos Hi, It's intentionally not an interface. Apps aren't allowed to extend the platform with new hash functions, because of the centrality of hashing to the protocol and the need for global coordination. So making it an interface wouldn't be an accepted code change, though of course you can do whatever you like for local experimentation. Introducing a new hash function is very difficult to do in a way that doesn't break backwards compatibility. You'd introduce a new subtype of SecureHash and then new factory methods that run the algorithm and return the new sealed subtype. Most parts of the code pass around SecureHash, not SecureHash.SHA256, so should be oblivious to the change. In a few places there might be hard-coded uses of SHA256. In every place where a hash is calculated using the existing methods you'd need to consider a backwards compatibility strategy. For instance the right algorithm to use might depend on the algorithm used by other transactions, or the network parameters. For ZKP related experimentation, which I guess this is related to, you could just hack around and not worry about backwards compat for now. Then the work would have to be redone later in a compatible way, but the issues would have been fully explored. ----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- ----------------------------------------------------------------- ATTENTION: The information in this e-mail is confidential and only meant for the intended recipient. If you are not the intended recipient, don't use or disclose it in any way. Please let the sender know and delete the message immediately. ----------------------------------------------------------------- |
|
|
|
Thanks!
The diff is pretty much what I expected - lots of places with fixed width (aren't relational databases great ...) One thing we might want to discuss now up front is what new hash algorithm you actually want to use, if any. It makes a difference because it's not really correct to assume wider = always better when it comes to hashing. The mathematics of this are pretty fixed by the laws of physics and the birthday attack. That is, a 256 bit hash function that's operating correctly gives you 128 bits of security (i.e. can brute force a pre-image in 2^127 steps on average), which is beyond the ability of any attacker to breach, unless they're aliens who can violate the known laws of physics. Note this is true even with quantum computers, as Grovers algorithm + modern hashing functions is - with our current cryptographic understanding - a wash in which even optimistic assumptions about QC can yield no speedups over classical attacks. RDBMs require us to specify the hash width because they use it to lay out data more optimally. If we increase that width (or make it entirely variable) we may therefore sacrifice some performance. We also need to make sure that all such configurations are tested (i.e. both widths/functions) and there are ways to upgrade and possibly downgrade. Not impossible or anything, just some more work. So it's good to know if we really need to do this or if we can just leave the current fixed widths as they are. This very much depends on the details of the ZKP-tuned hash you'd like to use. If it still only needs 256 bits of width then oh happy days, we can reduce the amount of work required by a lot. |
|
|
|
Bos, M. van den (Matthijs)
The merkle root length will be 32 bytes, so that saves a lot of work.
We will be using two different hash functions: one for the leaves of the component group merkle trees and another for all nodes above that. While investigating how to add support for another hash function in Corda, I encountered something that strikes me as odd in the current SHA-256 based implementation of the compenent hash computation, but this may be due to ignorance. ;-) It seems the nonce for each tx component is hashed an extra time, which seems unnecessary to me. Perhaps you can help me understand why this is happening. BTW, I do not mean the extra hashing to prevent length extension attacks. Let me explain: When calculating the Merkle tree in WireTransaction, the following two methods are used: internal val availableComponentNonces: Map<Int, List<SecureHash>> by lazy { componentGroups.map { Pair(it.groupIndex, it.components.mapIndexed { internalIndex, internalIt -> componentHash(internalIt, privacySalt, it.groupIndex, internalIndex) }) }.toMap() } internal val availableComponentHashes: Map<Int, List<SecureHash>> by lazy { componentGroups.map { Pair(it.groupIndex, it.components.mapIndexed { internalIndex, internalIt -> componentHash(availableComponentNonces[it.groupIndex]!![internalIndex], internalIt) }) }.toMap() } These methods make use of the following functions from CryptoUtils.kt: fun componentHash(opaqueBytes: OpaqueBytes, privacySalt: PrivacySalt, componentGroupIndex: Int, internalIndex: Int): SecureHash = componentHash(computeNonce(privacySalt, componentGroupIndex, internalIndex), opaqueBytes) fun componentHash(nonce: SecureHash, opaqueBytes: OpaqueBytes): SecureHash = SecureHash.sha256Twice(nonce.bytes + opaqueBytes.bytes) fun computeNonce(privacySalt: PrivacySalt, groupIndex: Int, internalIndex: Int) = SecureHash.sha256Twice(privacySalt.bytes + ByteBuffer.allocate(8).putInt(groupIndex).putInt(internalIndex).array()) If I understand this code correctly, the computation of a component hash could be rewritten in pseudo code this way:
This raises two questions:
|
|
|
|
Matthew Nesbit
Hi,
This work was done originally by Kostas Chalkias who was our resident cryptographer at the time and I believe that the double hashing was intentionally to reduce pre-image attacks. I am not sure you are fully correct with regard to the structure. My own diagram of the structure is attached and I believe the nonce is not used at the component merkle tree level. The intent of the privacy salt is that we can have a separate hash for each terminal leaf that can revealed in a merkle proof and to inject entropy so that low entropy fields can’t be searched for using exhaustive search. However, I agree the code is very hard to follow which is part of the challenge with creating backward compatible changes in the future.
Matthew
From: corda-dev@groups.io <corda-dev@groups.io>
On Behalf Of Bos, M. van den (Matthijs) via Groups.Io
Sent: 10 March 2020 13:27 To: corda-dev@groups.io Subject: Re: [corda-dev] Adding support for different hash algos
The merkle root length will be 32 bytes, so that saves a lot of work.
I understand that even if both of these are turn out not to be necessary, it is now too late to change it for the default current Corda configuration. But it means we could do less hashing when using a new hash function. Especially if we can skip line 2 and choose a hash function that is resistant to length extension attacks. That would bring the number of hash operations per tx component down from 6 to 2. |
|
|
|
Benjamin Kimsiah Tan
Actually on the doc site diagram, there is mentioned of the nonce added to component hash (https://docs.corda.net/key-concepts-tearoffs.html#transaction-merkle-trees). The thing I didn’t check is how the nonce is deterministically computed as suggested.
From: corda-dev@groups.io <corda-dev@groups.io>
On Behalf Of Matthew Nesbit via Groups.Io
Sent: 10 March 2020 21:43 To: corda-dev@groups.io Subject: Re: [corda-dev] Adding support for different hash algos
Hi,
This work was done originally by Kostas Chalkias who was our resident cryptographer at the time and I believe that the double hashing was intentionally to reduce pre-image attacks. I am not sure you are fully correct with regard to the structure. My own diagram of the structure is attached and I believe the nonce is not used at the component merkle tree level. The intent of the privacy salt is that we can have a separate hash for each terminal leaf that can revealed in a merkle proof and to inject entropy so that low entropy fields can’t be searched for using exhaustive search. However, I agree the code is very hard to follow which is part of the challenge with creating backward compatible changes in the future.
Matthew
From:
corda-dev@groups.io <corda-dev@groups.io>
On Behalf Of Bos, M. van den (Matthijs) via Groups.Io
The merkle root length will be 32 bytes, so that saves a lot of work.
I understand that even if both of these are turn out not to be necessary, it is now too late to change it for the default current Corda configuration. But it means we could do less hashing when using a new hash function. Especially if we can skip line 2 and choose a hash function that is resistant to length extension attacks. That would bring the number of hash operations per tx component down from 6 to 2. |
|
|
|
Bos, M. van den (Matthijs)
It looks like we may misunderstand each other, or use different definitions. If you could help me clarify things further, that would help me greatly.
I believe that the double hashing was intentionally to reduce pre-image attacks.In the source comments, it mentions it is done to prevent length extension attacks, I think they are not the same. Can you confirm? My own diagram of the structure is attached and I believe the nonce is not used at the component merkle tree levelHow I read your attached diagram, is that the NONCE is used as part of the hash for ComponentGroup leaf hashes. This is also what I thought I wrote about the nonce in my earlier message. To be sure we are talking about the same thing, I have attached a part of your diagram, with the relevant part highlighted. In that diagram, you give the following definition for the ComponentGroup leaf hash:
If I understand your message correctly, you state that have seen it wrong and my step 2 doesn't exist. I could indeed be mistaken, but I still don't see how. Could you help me with clarifying that? I will try to pick apart the code I mentioned to show how I came to my conclusion. If you could help me by pointing out where I made a mistake I would be grateful. Assumption 1: WireTransaction#getAvailableComponentNonces is the one and only place the ComponentGroup leaf nonces are calculated body: internal val availableComponentNonces: Map<Int, List<SecureHash>> by lazy {This function does the following for each component within a component group, working inside out: Step 1: call componentHash(internalIt, privacySalt, it.groupIndex, internalIndex) compute the hash (nonce) for this component, salt, group index and index in the group Here is that function: fun componentHash(opaqueBytes: OpaqueBytes, privacySalt: PrivacySalt, componentGroupIndex: Int, internalIndex: Int): SecureHash = componentHash(computeNonce(privacySalt, componentGroupIndex, internalIndex), opaqueBytes)Step 1a: call computeNonce(privacySalt, componentGroupIndex, internalIndex) Here is that function: fun computeNonce(privacySalt: PrivacySalt, groupIndex: Int, internalIndex: Int) = SecureHash.sha256Twice(privacySalt.bytes + ByteBuffer.allocate(8).putInt(groupIndex).putInt(internalIndex).array())Step 1a1: return SHA256(SHA256(salt || group id || index)) NONCE = SHA256(SHA256(salt || group id || index)) Step 1b: call componentHash(NONCE, opaqueBytes) Here is that function: fun componentHash(nonce: SecureHash, opaqueBytes: OpaqueBytes): SecureHash = SecureHash.sha256Twice(nonce.bytes + opaqueBytes.bytes)Step 1b1: return SHA256(SHA256(NONCE, opaqueBytes) NONCE_HASH = SHA256(SHA256(NONCE, opaqueBytes), a.k.a: NONCE_HASH = SHA256(SHA256(SHA256(SHA256(salt || group id || index)), opaqueBytes) Step 1 (the call to componentHash within availableComponentNonces) returns: NONCE_HASH. As I read it, that means that availableComponentNonces contains for each component within a group: SHA256(SHA256(SHA256(SHA256(salt || group id || index)), opaqueBytes) Assumption 2: WireTransaction#getAvailableComponentHashes is the one and only place the ComponentGroup leaf hashes are calculated body: componentGroups.map { Pair(it.groupIndex, it.components.mapIndexed { internalIndex, internalIt -> componentHash(availableComponentNonces[it.groupIndex]!![internalIndex], internalIt) }) }.toMap()This function does the following for each component within a component group, working inside out: Step 1: availableComponentNonces[it.groupIndex]!![internalIndex] Get the nonce for this componentGroup. As shown above, this will be: SHA256(SHA256(SHA256(SHA256(salt || group id || index)), opaqueBytes) Step 2: call componentHash(nonce, internalIt) Compute the hash for this nonce and component. As we have seen above, that function will return SHA256(SHA256(nonce, opaqueBytes). And because the nonce from step 1 is SHA256(SHA256(SHA256(SHA256(salt || group id || index)), opaqueBytes), COMPONENT_HASH = SHA256(SHA256(SHA256(SHA256(SHA256(SHA256(salt || group id || index)), opaqueBytes), opaqueBytes) Apologies for this long piece of text, but I did not know any other way of clarifying how I interpreted the code. Looking forward to your interpretation. On another note, from your reply it is not yet clear to me yet why specifically the nonce generation should be resistant to length extension attacks. I understand why it adds security for the leaf hash creation. Can you comment on that? Thanks for your patience. |
|
|
|
Bos, M. van den (Matthijs)
To summarize all of that long message:
To get the nonce value, availableComponentNonces calls componentHash(opaqueBytes: OpaqueBytes, privacySalt: PrivacySalt, componentGroupIndex: Int, internalIndex: Int). That function is a combination of computeNonce(privacySalt: PrivacySalt, groupIndex: Int, internalIndex: Int) and componentHash(nonce: SecureHash, opaqueBytes: OpaqueBytes), both of which use SHA256d (double SHA256). As mentioned in the previous post, this results in NONCE = SHA256(SHA256(SHA256(SHA256(salt || group id || index)), opaqueBytes). I believe this is unintended and that it is better to call computeNonce from availableComponentNonces. In that case, NONCE = SHA256(SHA256(salt || group id || index), which is what we expect. Can anyone confirm this? Or is there a good reason after all to double hash the nonce twice? |
|
|
|
Bos, M. van den (Matthijs)
To conclude this long series: I have checked this with Kostas, the cryptographer who worked at R3 at the time and implemented this. He confirms that the current implementation is indeed unintentional and that availableComponentNonces should have been calling computeNonce . In that case, NONCE = SHA256(SHA256(salt || group id || index), which is what we expect.
|
|
|
|
chalkiaskostas@...
Indeed I can also confirm that as the doc-comments mention under availableComponentNonces, the expected functionality is to invoke computeNonce instead of componentHash. Thanks Matthijs for exploring that.
|
|
|
|
Thanks Kostas and thanks to Matthijs for digging into this, good detective work.
I guess I have two thoughts at this point. One is whether it's possible to introduce a parallel hash tree that uses different algorithms and a corrected calculation to avoid redundant hashing, which is calculated in addition to the existing one rather than instead of. The parallel tree would be used only as input to proof circuits. This would avoid at least two scary issues: 1. A justifiable lack of trust in new circuit-optimised hash functions. This paper came out in February and to my complete lack of surprise presented another breach of MiMC hashes: https://eprint.iacr.org/2020/188 ZKP optimised hash functions are departing from the road-most-trodden, and we know that hash function design is hard. SHA2 is extremely solid, based on well understood principles and there are no clouds on the horizon. So, any new exotic hash function would ideally limit the blast radius to only ZKPs and not other parts of the system. This is especially important because to whitelist new crypto on the Corda Network would require a change to the network parameters, which is controlled by the elected board, not R3. So they have to be convinced it's safe too. 2. How to do incremental rollout? The concern here isn't just the Corda node itself but app code and tooling that assumes the current hash width, and quite possibly, assumes SHA2. With a parallel tree code that just wants to check the ID of transaction bytes or check a Merkle tree for e.g. mobile signing can be left alone, it doesn't have to know other peers will never see the original hash tree. Otherwise anything that touches the tx format needs to be updated, which is an ever-growing pile of code. So the deployability aspect suggests some sort of parallel solution may also be desirable. Using a parallel tree opens up some new research questions. Does this idea actually work or is it just a pleasant dream, destined to vanish the moment we open our eyes? Let's say we have an entirely parallel API that computes a Merkle tree using a ZKP hash (ZKPH) - does it need to be stored in the tx itself, or not? I don't see why it does, because whoever receives the ZKP can just re-calculate it and then use the root as a public input to the circuit. There doesn't need to be a binding between the SHA2 root and the ZKPH root at all, maybe? If not the format can stay exactly the same except for a new tx component, which can be introduced in a way that's both backwards and forwards compatible. That would be a big win. |
|
|
|
Bos, M. van den (Matthijs)
I think this is a good idea. It will allow flexibility, without compromising current platform stability.
toggle quoted message
Show quoted text
I am doing a small PoC implementation to use as a discussion piece and to see if this is indeed more than a dream. The aim would be to make no API breaks, and only introduce new API. Which branch should I target with it? I ask because I used `release/os/4.5` until now, but when I check the API breaks with `.ci/check-api-changes.sh`, I already see a lot of changes on that branch, which makes it hard to determine what changes I am introducing. On Thu, Mar 12, 2020 at 06:54 AM, Mike Hearn wrote: So the deployability aspect suggests some sort of parallel solution may also be desirable. |
|
|
|
4.5 is a fine base, that's effectively the current master.
You can ignore the API checker for now. That would only become relevant if/when the work gets merged.
From: corda-dev@groups.io <corda-dev@groups.io> on behalf of Bos, M. van den (Matthijs) via Groups.Io <matthijs.van.den.bos@...>
Sent: Tuesday, March 17, 2020 10:24 To: corda-dev@groups.io <corda-dev@groups.io> Subject: Re: [corda-dev] Adding support for different hash algos I think this is a good idea. It will allow flexibility, without compromising current platform stability.
I am doing a small PoC implementation to use as a discussion piece and to see if this is indeed more than a dream. The aim would be to make no API breaks, and only introduce new API. Which branch should I target with it? I ask because I used `release/os/4.5` until now, but when I check the API breaks with `.ci/check-api-changes.sh`, I already see a lot of changes on that branch, which makes it hard to determine what changes I am introducing. On Thu, Mar 12, 2020 at 06:54 AM, Mike Hearn wrote: So the deployability aspect suggests some sort of parallel solution may also be desirable. |
|
|
