* Re: [bitcoin-dev] Fast Merkle Trees
@ 2017-09-07 1:59 Russell O'Connor
2017-09-07 2:20 ` Mark Friedenbach
2017-09-07 5:55 ` Peter Todd
0 siblings, 2 replies; 9+ messages in thread
From: Russell O'Connor @ 2017-09-07 1:59 UTC (permalink / raw)
To: Mark Friedenbach, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 832 bytes --]
The fast hash for internal nodes needs to use an IV that is not the
standard SHA-256 IV. Instead needs to use some other fixed value, which
should itself be the SHA-256 hash of some fixed string (e.g. the string
"BIP ???" or "Fash SHA-256").
As it stands, I believe someone can claim a leaf node as an internal node
by creating a proof that provides a phony right-hand branch claiming to
have hash 0x80000..0000100 (which is really the padding value for the
second half of a double SHA-256 hash).
(I was schooled by Peter Todd by a similar issue in the past.)
On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> Fast Merkle Trees
> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
>
[-- Attachment #2: Type: text/html, Size: 1497 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 1:59 [bitcoin-dev] Fast Merkle Trees Russell O'Connor @ 2017-09-07 2:20 ` Mark Friedenbach 2017-09-07 15:43 ` Russell O'Connor 2017-09-07 5:55 ` Peter Todd 1 sibling, 1 reply; 9+ messages in thread From: Mark Friedenbach @ 2017-09-07 2:20 UTC (permalink / raw) To: Russell O'Connor; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1169 bytes --] This design purposefully does not distinguish leaf nodes from internal nodes. That way it chained invocations can be used to validate paths longer than 32 branches. Do you see a vulnerability due to this lack of distinction? > On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream•io> wrote: > > The fast hash for internal nodes needs to use an IV that is not the standard SHA-256 IV. Instead needs to use some other fixed value, which should itself be the SHA-256 hash of some fixed string (e.g. the string "BIP ???" or "Fash SHA-256"). > > As it stands, I believe someone can claim a leaf node as an internal node by creating a proof that provides a phony right-hand branch claiming to have hash 0x80000..0000100 (which is really the padding value for the second half of a double SHA-256 hash). > > (I was schooled by Peter Todd by a similar issue in the past.) > >> On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: >> Fast Merkle Trees >> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a >> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree [-- Attachment #2: Type: text/html, Size: 2032 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 2:20 ` Mark Friedenbach @ 2017-09-07 15:43 ` Russell O'Connor 2017-09-07 17:42 ` Mark Friedenbach 0 siblings, 1 reply; 9+ messages in thread From: Russell O'Connor @ 2017-09-07 15:43 UTC (permalink / raw) To: Mark Friedenbach; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 3928 bytes --] In that case, you may as well remove all references to leaves and double SHA-256 from your BIP since your design has no method for distinguishing between internal nodes and leaves. I think that if this design stands, it will play a role in some future CVEs. The BIP itself is too abstract about its data contents to specifically say that it has a vulnerability; however, I believe it is inviting vulnerabilities. For example, I might agree with a counterparty to a design of some sort of smart contract in the form of a MAST. My counterparty has shown me all the "leaves" of our MAST and I can verify its Merkle root computation. After being deployed, I found out that one of the leaves wasn't really a leaf but is instead a specially crafted "script" with a fake pubkey chosen by my couterparty so that this leaf can also be interpreted as a fake internal node (i.e. an internal node with a right branch of 0x8000...100). Because the Fast Merkle Tree design doesn't distinguish between leaves and internal nodes my counter party gets away with building an Inclusion Proof through this "leaf" to reveal the evil code that they had designed into the MAST at a deeper level. Turns out my counterparty was grinding their evil code to produce an internal node that can also be parsed as an innocent script. They used their "pubkey" to absorb excess random data from their grinding that they cannot eliminate. (The counterparty doesn't actually know the discrete log of this "pubkey", they just claimed it was their pubkey and I believed them). Having ambiguity about whether a node is a leaf or an internal node is a security risk. Furthermore, changing the design so that internal node and leaves are distinguishable still allows chained invocations. Arbitrary data can be stored in Fast Merkle Tree leaves, including the Merkle root of another Fast Merkle Tree. Applications that are limited to proof with paths no longer than 32 branches can still circumvent this limit by staging these Fast Merkle Trees in explicit layers (as opposed to the implicit layers with the current design). By storing a inner Fast Merkle Tree root inside the (explicit) leaf of an outer Fast Merkle Tree, the application can verify a Inclusion Proof of the inner Fast Merkle Tree Root in the outer Fast Merkle Tree Root, and then verify a second Inclusion Proof of the desired data in the inner Faster Merkle Tree Root. The application will need to tag their data to distinguish between inner Fast Merkle Tree Roots and other application data, but that is just part of the general expectation that applications not store ambiguous data inside the leaves of Fast Merkle Trees. On Wed, Sep 6, 2017 at 10:20 PM, Mark Friedenbach <mark@friedenbach•org> wrote: > This design purposefully does not distinguish leaf nodes from internal > nodes. That way it chained invocations can be used to validate paths longer > than 32 branches. Do you see a vulnerability due to this lack of > distinction? > > On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream•io> > wrote: > > The fast hash for internal nodes needs to use an IV that is not the > standard SHA-256 IV. Instead needs to use some other fixed value, which > should itself be the SHA-256 hash of some fixed string (e.g. the string > "BIP ???" or "Fash SHA-256"). > > As it stands, I believe someone can claim a leaf node as an internal node > by creating a proof that provides a phony right-hand branch claiming to > have hash 0x80000..0000100 (which is really the padding value for the > second half of a double SHA-256 hash). > > (I was schooled by Peter Todd by a similar issue in the past.) > > On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> Fast Merkle Trees >> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a >> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree >> > [-- Attachment #2: Type: text/html, Size: 5320 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 15:43 ` Russell O'Connor @ 2017-09-07 17:42 ` Mark Friedenbach 2017-09-07 18:55 ` Russell O'Connor 0 siblings, 1 reply; 9+ messages in thread From: Mark Friedenbach @ 2017-09-07 17:42 UTC (permalink / raw) To: Russell O'Connor; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 6087 bytes --] I've been puzzling over your email since receiving it. I'm not sure it is possible to perform the attack you describe with the tree structure specified in the BIP. If I may rephrase your attack, I believe you are seeking a solution to the following: Want: An innocuous script and a malign script for which double-SHA256(innocuous) is equal to either fast-SHA256(double-SHA256(malign) || r) or fast-SHA256(r || double-SHA256(malign)) where r is a freely chosen 32-byte nonce. This would allow the attacker to reveal the innocuous script before funds are sent to the MAST, then use the malign script to spend. Because of the double-SHA256 construction I do not see how this can be accomplished without a full break of SHA256. The trick of setting r equal to the padding only works when a single SHA256 is used for leaf values. This is why double-SHA256 is specified in the BIP, and I will edit the text to make that more clear. Which brings us to the point that I think your original request of separating the hash function of leaves from internal nodes is already in the specification. I misunderstood your request at first to be that MERKLEBRANCHVERIFY should itself perform this hash, which I objected to as it closes of certain use cases such as chained verification of proofs. But it is explicitly the case that leaf values and internal updates are calculated with different hash functions. I'm not intrinsicly opposed to using a different IV for fast-SHA256 so as to remove the incompatability with single-SHA256 as the leaf hash function, if that is the consensus of the community. It just adds complication to implementations and so I want to make sure that complication is well justified. Sincerely, Mark Friedenbach > On Sep 7, 2017, at 8:43 AM, Russell O'Connor <roconnor@blockstream•io> wrote: > > In that case, you may as well remove all references to leaves and double SHA-256 from your BIP since your design has no method for distinguishing between internal nodes and leaves. > > I think that if this design stands, it will play a role in some future CVEs. The BIP itself is too abstract about its data contents to specifically say that it has a vulnerability; however, I believe it is inviting vulnerabilities. > For example, I might agree with a counterparty to a design of some sort of smart contract in the form of a MAST. My counterparty has shown me all the "leaves" of our MAST and I can verify its Merkle root computation. > After being deployed, I found out that one of the leaves wasn't really a leaf but is instead a specially crafted "script" with a fake pubkey chosen by my couterparty so that this leaf can also be interpreted as a fake internal node (i.e. an internal node with a right branch of 0x8000...100). > Because the Fast Merkle Tree design doesn't distinguish between leaves and internal nodes my counter party gets away with building an Inclusion Proof through this "leaf" to reveal the evil code that they had designed into the MAST at a deeper level. > > Turns out my counterparty was grinding their evil code to produce an internal node that can also be parsed as an innocent script. They used their "pubkey" to absorb excess random data from their grinding that they cannot eliminate. > (The counterparty doesn't actually know the discrete log of this "pubkey", they just claimed it was their pubkey and I believed them). > > > Having ambiguity about whether a node is a leaf or an internal node is a security risk. Furthermore, changing the design so that internal node and leaves are distinguishable still allows chained invocations. > Arbitrary data can be stored in Fast Merkle Tree leaves, including the Merkle root of another Fast Merkle Tree. > Applications that are limited to proof with paths no longer than 32 branches can still circumvent this limit by staging these Fast Merkle Trees in explicit layers (as opposed to the implicit layers with the current design). > > By storing a inner Fast Merkle Tree root inside the (explicit) leaf of an outer Fast Merkle Tree, the application can verify a Inclusion Proof of the inner Fast Merkle Tree Root in the outer Fast Merkle Tree Root, and then verify a second Inclusion Proof of the desired data in the inner Faster Merkle Tree Root. The application will need to tag their data to distinguish between inner Fast Merkle Tree Roots and other application data, but that is just part of the general expectation that applications not store ambiguous data inside the leaves of Fast Merkle Trees. > > > On Wed, Sep 6, 2017 at 10:20 PM, Mark Friedenbach <mark@friedenbach•org <mailto:mark@friedenbach•org>> wrote: > This design purposefully does not distinguish leaf nodes from internal nodes. That way it chained invocations can be used to validate paths longer than 32 branches. Do you see a vulnerability due to this lack of distinction? > > On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream•io <mailto:roconnor@blockstream•io>> wrote: > >> The fast hash for internal nodes needs to use an IV that is not the standard SHA-256 IV. Instead needs to use some other fixed value, which should itself be the SHA-256 hash of some fixed string (e.g. the string "BIP ???" or "Fash SHA-256"). >> >> As it stands, I believe someone can claim a leaf node as an internal node by creating a proof that provides a phony right-hand branch claiming to have hash 0x80000..0000100 (which is really the padding value for the second half of a double SHA-256 hash). >> >> (I was schooled by Peter Todd by a similar issue in the past.) >> >> On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org <mailto:bitcoin-dev@lists•linuxfoundation.org>> wrote: >> Fast Merkle Trees >> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a <https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a> >> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree <https://github.com/maaku/bitcoin/tree/fast-merkle-tree> > [-- Attachment #2: Type: text/html, Size: 9042 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 17:42 ` Mark Friedenbach @ 2017-09-07 18:55 ` Russell O'Connor 2017-09-07 20:04 ` Mark Friedenbach 0 siblings, 1 reply; 9+ messages in thread From: Russell O'Connor @ 2017-09-07 18:55 UTC (permalink / raw) To: Mark Friedenbach; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 2308 bytes --] On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark@friedenbach•org> wrote: > I've been puzzling over your email since receiving it. I'm not sure it > is possible to perform the attack you describe with the tree structure > specified in the BIP. If I may rephrase your attack, I believe you are > seeking a solution to the following: > > Want: An innocuous script and a malign script for which > > double-SHA256(innocuous) > > is equal to either > > fast-SHA256(double-SHA256(malign) || r) or > fast-SHA256(r || double-SHA256(malign)) > or fast-SHA256(fast-SHA256(double-SHA256(malign) || r1) || r0) or fast-SHA256(fast-SHA256(r1 || double-SHA256(malign)) || r0) or ... > where r is a freely chosen 32-byte nonce. This would allow the > attacker to reveal the innocuous script before funds are sent to the > MAST, then use the malign script to spend. > > Because of the double-SHA256 construction I do not see how this can be > accomplished without a full break of SHA256. > The particular scenario I'm imagining is a collision between double-SHA256(innocuous) and fast-SHA256(fast-SHA256(fast-SHA256(double-SHA256(malign) || r2) || r1) || r0). where innocuous is a Bitcoin Script that is between 32 and 55 bytes long. Observe that when data is less than 55 bytes then double-SHA256(data) = fast-SHA256(fast-SHA256(padding-SHA256(data)) || 0x8000...100) (which is really the crux of the matter). Therefore, to get our collision it suffices to find a collision between padding-SHA256(innocuous) and fast-SHA256(double-SHA256(malign) || r2) || r1 r1 can freely be set to the second half of padding-SHA256(innocuous), so it suffices to find a collision between fast-SHA256(double-SHA256(malign) || r2) and the first half of padding-SHA256(innocuous) which is equal to the first 32 bytes of innocuous. Imagine the first opcode of innocuous is the push of a value that the attacker claims to be his 33-byte public key. So long as the attacker doesn't need to prove that they know the discrete log of this pubkey, they can grind r2 until the result of fast-SHA256(double-SHA256(malign) || r2) contains the correct first couple of bytes for the script header and the opcode for a 33-byte push. I believe that is only about 3 or 4 bytes of they need to grind out. [-- Attachment #2: Type: text/html, Size: 3539 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 18:55 ` Russell O'Connor @ 2017-09-07 20:04 ` Mark Friedenbach 2017-09-12 11:44 ` Johnson Lau 0 siblings, 1 reply; 9+ messages in thread From: Mark Friedenbach @ 2017-09-07 20:04 UTC (permalink / raw) To: Russell O'Connor; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 5551 bytes --] TL;DR I'll be updating the fast Merkle-tree spec to use a different IV, using (for infrastructure compatability reasons) the scheme provided by Peter Todd. This is a specific instance of a general problem where you cannot trust scripts given to you by another party. Notice that we run into the same sort of problem when doing key aggregation, in which you must require the other party to prove knowledge of the discrete log before using their public key, or else key cancellation can occur. With script it is a little bit more complicated as you might want zero-knowledge proofs of hash pre-images for HTLCs as well as proofs of DL knowledge (signatures), but the basic idea is the same. Multi- party wallet level protocols for jointly constructing scriptPubKeys should require a 'delinearization' step that proves knowledge of information necessary to complete each part of the script, as part of proving the safety of a construct. I think my hangup before in understanding the attack you describe was in actualizing it into a practical attack that actually escalates the attacker's capabilities. If the attacker can get you to agree to a MAST policy that is nothing more than a CHECKSIG over a key they presumably control, then they don't need to do any complicated grinding. The attacker in that scenario would just actually specify a key they control and take the funds that way. Where this presumably leads to an actual exploit is when you specify a script that a curious counter-party actually takes the time to investigate and believes to be secure. For example, a script that requires a signature or pre-image revelation from that counter-party. That would require grinding not a few bytes, but at minimum 20-33 bytes for either a HASH160 image or the counter-party's key. If I understand the revised attack description correctly, then there is a small window in which the attacker can create a script less than 55 bytes in length, where nearly all of the first 32 bytes are selected by the attacker, yet nevertheless the script seems safe to the counter-party. The smallest such script I was able to construct was the following: <fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL This is 56 bytes and requires only 7 bits of grinding in the fake pubkey. But 56 bytes is too large. Switching to secp256k1 serialized 32-byte pubkeys (in a script version upgrade, for example) would reduce this to the necessary 55 bytes with 0 bits of grinding. A smaller variant is possible: DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160 <preimage> EQUAL This is 46 bytes, but requires grinding 96 bits, which is a bit less plausible. Belts and suspenders are not so terrible together, however, and I think there is enough of a justification here to look into modifying the scheme to use a different IV for hash tree updates. This would prevent even the above implausible attacks. > On Sep 7, 2017, at 11:55 AM, Russell O'Connor <roconnor@blockstream•io> wrote: > > > > On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark@friedenbach•org <mailto:mark@friedenbach•org>> wrote: > I've been puzzling over your email since receiving it. I'm not sure it > is possible to perform the attack you describe with the tree structure > specified in the BIP. If I may rephrase your attack, I believe you are > seeking a solution to the following: > > Want: An innocuous script and a malign script for which > > double-SHA256(innocuous) > > is equal to either > > fast-SHA256(double-SHA256(malign) || r) or > fast-SHA256(r || double-SHA256(malign)) > > or fast-SHA256(fast-SHA256(double-SHA256(malign) || r1) || r0) > or fast-SHA256(fast-SHA256(r1 || double-SHA256(malign)) || r0) > or ... > > where r is a freely chosen 32-byte nonce. This would allow the > attacker to reveal the innocuous script before funds are sent to the > MAST, then use the malign script to spend. > > Because of the double-SHA256 construction I do not see how this can be > accomplished without a full break of SHA256. > > The particular scenario I'm imagining is a collision between > > double-SHA256(innocuous) > > and > > fast-SHA256(fast-SHA256(fast-SHA256(double-SHA256(malign) || r2) || r1) || r0). > > where innocuous is a Bitcoin Script that is between 32 and 55 bytes long. > > Observe that when data is less than 55 bytes then double-SHA256(data) = fast-SHA256(fast-SHA256(padding-SHA256(data)) || 0x8000...100) (which is really the crux of the matter). > > Therefore, to get our collision it suffices to find a collision between > > padding-SHA256(innocuous) > > and > > fast-SHA256(double-SHA256(malign) || r2) || r1 > > r1 can freely be set to the second half of padding-SHA256(innocuous), so it suffices to find a collision between > > fast-SHA256(double-SHA256(malign) || r2) > > and the first half of padding-SHA256(innocuous) which is equal to the first 32 bytes of innocuous. > > Imagine the first opcode of innocuous is the push of a value that the attacker claims to be his 33-byte public key. > So long as the attacker doesn't need to prove that they know the discrete log of this pubkey, they can grind r2 until the result of fast-SHA256(double-SHA256(malign) || r2) contains the correct first couple of bytes for the script header and the opcode for a 33-byte push. I believe that is only about 3 or 4 bytes of they need to grind out. > [-- Attachment #2: Type: text/html, Size: 9261 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 20:04 ` Mark Friedenbach @ 2017-09-12 11:44 ` Johnson Lau 0 siblings, 0 replies; 9+ messages in thread From: Johnson Lau @ 2017-09-12 11:44 UTC (permalink / raw) To: Mark Friedenbach, bitcoin-dev > On 8 Sep 2017, at 4:04 AM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > If I understand the revised attack description correctly, then there > is a small window in which the attacker can create a script less than > 55 bytes in length, where nearly all of the first 32 bytes are > selected by the attacker, yet nevertheless the script seems safe to > the counter-party. The smallest such script I was able to construct > was the following: > > <fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL > > This is 56 bytes and requires only 7 bits of grinding in the fake > pubkey. But 56 bytes is too large. Switching to secp256k1 serialized > 32-byte pubkeys (in a script version upgrade, for example) would > reduce this to the necessary 55 bytes with 0 bits of grinding. A > smaller variant is possible: > > DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160 <preimage> EQUAL > > This is 46 bytes, but requires grinding 96 bits, which is a bit less > plausible. > > Belts and suspenders are not so terrible together, however, and I > think there is enough of a justification here to look into modifying > the scheme to use a different IV for hash tree updates. This would > prevent even the above implausible attacks. > I think you overestimated the difficulty. Consider this MAST branch (an example in BIP114) "Timestamp" CHECKLOCKTIMEVERIFY <fake-pubkey> CHECKSIGVERIFY This requires just a few bytes of collision. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 1:59 [bitcoin-dev] Fast Merkle Trees Russell O'Connor 2017-09-07 2:20 ` Mark Friedenbach @ 2017-09-07 5:55 ` Peter Todd 2017-09-07 15:51 ` Russell O'Connor 1 sibling, 1 reply; 9+ messages in thread From: Peter Todd @ 2017-09-07 5:55 UTC (permalink / raw) To: Russell O'Connor, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 720 bytes --] On Wed, Sep 06, 2017 at 09:59:54PM -0400, Russell O'Connor via bitcoin-dev wrote: > The fast hash for internal nodes needs to use an IV that is not the > standard SHA-256 IV. Instead needs to use some other fixed value, which > should itself be the SHA-256 hash of some fixed string (e.g. the string > "BIP ???" or "Fash SHA-256"). Note that in general, designs should *not* create new hash functions by using custom IVs, but rather use bog-standard SHA256, and make a fixed first block. That allows unoptimised implementations to just hash a block with the second initialization value, and optimized implementations to start with the fixed midstate. -- https://petertodd.org 'peter'[:-1]@petertodd.org [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 455 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Fast Merkle Trees 2017-09-07 5:55 ` Peter Todd @ 2017-09-07 15:51 ` Russell O'Connor 0 siblings, 0 replies; 9+ messages in thread From: Russell O'Connor @ 2017-09-07 15:51 UTC (permalink / raw) To: Peter Todd; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1138 bytes --] On Thu, Sep 7, 2017 at 1:55 AM, Peter Todd <pete@petertodd•org> wrote: > On Wed, Sep 06, 2017 at 09:59:54PM -0400, Russell O'Connor via bitcoin-dev > wrote: > > The fast hash for internal nodes needs to use an IV that is not the > > standard SHA-256 IV. Instead needs to use some other fixed value, which > > should itself be the SHA-256 hash of some fixed string (e.g. the string > > "BIP ???" or "Fash SHA-256"). > > Note that in general, designs should *not* create new hash functions by > using > custom IVs, but rather use bog-standard SHA256, and make a fixed first > block. > That allows unoptimised implementations to just hash a block with the > second > initialization value, and optimized implementations to start with the fixed > midstate. I 100% agree. With SHA256 every final state is also a valid midstate. Therefore, using a custom IV of the SHA256 hash of some fixed string results in a hash of data that is functionally equivalent to prefixing the data with the padded version of the fixed string and using a regular SHA256 hash of the combined data. This is important and I should have explicitly pointed it out. [-- Attachment #2: Type: text/html, Size: 1564 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2017-09-12 11:45 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-09-07 1:59 [bitcoin-dev] Fast Merkle Trees Russell O'Connor 2017-09-07 2:20 ` Mark Friedenbach 2017-09-07 15:43 ` Russell O'Connor 2017-09-07 17:42 ` Mark Friedenbach 2017-09-07 18:55 ` Russell O'Connor 2017-09-07 20:04 ` Mark Friedenbach 2017-09-12 11:44 ` Johnson Lau 2017-09-07 5:55 ` Peter Todd 2017-09-07 15:51 ` Russell O'Connor
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox