Ethan Heilman [ARCHIVE]

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2014-06-03 to 2021-07-09
💬 Posted a total of 32 messages
📚 Participated in the following categories: Bitcoin-development, bitcoin-dev, Lightning-dev, was CheckSigFromStack for Arithmetic Values
🔇 Please do not DM this user as it's used for archive purposes only.

Public Key

npub1gaszwl7qd0tjmnwcaamgzzgsmzzjlvle6kz0td66pwa8z69vsxsqxgac47

Profile Code

nprofile1qqsywcp80lqxh4edehvw7a5ppygd3pf0k0uatp84kadqhwn3dzkgrgq8d3nrw

Author Public Key

npub1gaszwl7qd0tjmnwcaamgzzgsmzzjlvle6kz0td66pwa8z69vsxsqxgac47

Show more details

Last Notes

2023-06-09 12:57:49

- reply

📅 Original date posted:2019-12-18
📝 Original message:
>
> Responding below
The core idea is to modify Tapscript's `OP_CHECKSIG`. Instead of reading the
> signature as a single 64-bytes stack argument, let's add a small change to
> read
> the signature as two 32-bytes stack arguments: `R` first then `s`.
> Since Taproot already makes changes to this opcode, adding this small
> change
> seems to be quite simple and harmless (and this is the right time to
> propose
> such a change as we're still in the Taproot review process).
>
I very much in favor of a mechanism to enable outputs to enforce ECDSA
nonce reuse.
However I would argue against changing the behavior of OP_CHECKSIG. Subtly
changing the stack behavior of perhaps the most widely used and complex OP
code in Bitcoin is likely to result in bugs in systems that create and sign
transactions. Additionally making this new behavior only activate based on
context is even more likely to cause problems.
It would likely be safer to have this as a new OP code, say
OP_CHECKSPLITSIG.
Alternatively we could try to get OP_CAT approved. It is a very simple OP
code, which is easy to explain, generally useful and allows this feature
plus allows many other critical features.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20191218/e7a5abd2/attachment.html>

2023-06-09 12:57:48

- reply

📅 Original date posted:2019-12-17
📝 Original message:
>From where I'm sitting the fact that OP_CAT allows people to build
more powerful constructions in Bitcoin without introducing additional
complexity at the consensus layer is a positive not a negative. Using
OP_CAT or OP_SUBSTRING to enforce ECDSA nonce reuse is a very powerful
protocol tool for enforcing fairness in layer two protocols.
On Tue, Dec 17, 2019 at 11:27 AM ZmnSCPxj via Lightning-dev
<lightning-dev at lists.linuxfoundation.org> wrote:
>
> Good morning t-bast,
>
> Further, we can enforce that RBF is signalled for every spend of the output by:
>
> <0> OP_CHECKSEQUENCEVERIFY OP_DROP <R> OP_SWAP OP_CAT <ACINQ> OP_CHECKSIG
>
> Requiring that RBF is signalled gives a little more assurance.
> Suppose ACINQ becomes evil and double-spends the output.
> The transaction that is posted in the mempool must be marked by RBF due to the `OP_CHECKSEQUENCEVERIFY` opcode, since `nSequence` also doubles as RBF opt-in.
> Then anyone who notices the double-spend can RBF the double-spending transaction to themselves rather than ACINQ.
> This also further publishes ACINQ private key, until the winning transaction has an `OP_RETURN` output that pays the entire value as fees and nobody can RBF it further.
>
> This is a minor increase in the assurability of the construction, by making any output that is double-spent directly revocable in favor of the miners.
> Again, it requires `OP_CAT`, which is a very dangerous opcode, allowing such powerful constructions.
>
> Regards,
> ZmnSCPxj
>
>
> > Thanks a lot David for the suggestion and pointers, that's a really interesting solution.
> > I will dive into that in-depth, it could be very useful for many layer-2 constructions.
> >
> > Thanks ZmnSCPxj as well for the quick feedback and the `OP_CAT` construction,
> > a lot of cool tricks coming up once (if?) we have such tools in the future ;)
> >
> > Le mar. 17 déc. 2019 à 16:14, ZmnSCPxj <ZmnSCPxj at protonmail.com> a écrit :
> >
> > > Good morning David, t-bast, and all,
> > >
> > > > I'm not aware of any way to currently force single-show signatures in
> > > > Bitcoin, so this is pretty theoretical. Also, single-show signatures
> > > > add a lot of fragility to any setup and make useful features like RBF
> > > > fee bumping unavailable.
> > >
> > > With `OP_CAT`, we can enforce that a particular `R` is used, which allows to implement single-show signatures.
> > >
> > > # Assuming signatures are the concatenation of (R,s)
> > > <R> OP_SWAP OP_CAT <ACINQ> OP_CHECKSIG
> > >
> > > The above would then feed `s` only on the witness stack.
> > >
> > > Regards,
> > > ZmnSCPxj
>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

2023-06-09 12:56:27

- reply

📅 Original date posted:2019-10-03
📝 Original message:
I hope you are having an great afternoon ZmnSCPxj,
You make an excellent point!
I had thought about doing the following to tag nodes
|| means OP_CAT
`node = SHA256(type||SHA256(data))`
so a subnode would be
`subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
and a leaf node would be
`leafnode = SHA256(0||SHA256(leafdata))`
Yet, I like your idea better. Increasing the size of the two inputs to
OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
size of object on the stack seems sensible and also doesn't special
case the logic of OP_CAT.
It would also increase performance. SHA256(tag||subnode2||subnode3)
requires 2 compression function calls whereas
SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
function calls (due to padding).
>Or we could implement tagged SHA256 as a new opcode...
I agree that tagged SHA256 as an op code that would certainty be
useful, but OP_CAT provides far more utility and is a simpler change.
Thanks,
Ethan
On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> Good morning Ethan,
>
>
> > To avoid derailing the NO_INPUT conversation, I have changed the
> > subject to OP_CAT.
> >
> > Responding to:
> > """
> >
> > - `SIGHASH` flags attached to signatures are a misdesign, sadly
> > retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> > par with:
> > [..]
> >
> > - `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > [..]
> > """
> >
> > OP_CAT is an extremely valuable op code. I understand why it was
> > removed as the situation at the time with scripts was dire. However
> > most of the protocols I've wanted to build on Bitcoin run into the
> > limitation that stack values can not be concatenated. For instance
> > TumbleBit would have far smaller transaction sizes if OP_CAT was
> > supported in Bitcoin. If it happens to me as a researcher it is
> > probably holding other people back as well. If I could wave a magic
> > wand and turn on one of the disabled op codes it would be OP_CAT. Of
> > course with the change that size of each concatenated value must be 64
> > Bytes or less.
>
> Why 64 bytes in particular?
>
> It seems obvious to me that this 64 bytes is most suited for building Merkle trees, being the size of two SHA256 hashes.
>
> However we have had issues with the use of Merkle trees in Bitcoin blocks.
> Specifically, it is difficult to determine if a hash on a Merkle node is the hash of a Merkle subnode, or a leaf transaction.
> My understanding is that this is the reason for now requiring transactions to be at least 80 bytes.
>
> The obvious fix would be to prepend the type of the hashed object, i.e. add at least one byte to determine this type.
> Taproot for example uses tagged hash functions, with a different tag for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-before-you-SHA256.
>
> This seems to indicate that to check merkle tree proofs, an `OP_CAT` with only 64 bytes max output size would not be sufficient.
>
> Or we could implement tagged SHA256 as a new opcode...
>
> Regards,
> ZmnSCPxj
>
>
> >
> > On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> > bitcoin-dev at lists.linuxfoundation.org wrote:
> >
> >
> > > Good morning lists,
> > > Let me propose the below radical idea:
> > >
> > > - `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> > > - 1 RETURN
> > > - higher-`nSequence` replacement
> > > - DER-encoded pubkeys
> > > - unrestricted `scriptPubKey`
> > > - Payee-security-paid-by-payer (i.e. lack of P2SH)
> > > - `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > - transaction malleability
> > > - probably many more
> > >
> > > So let me propose the more radical excision, starting with SegWit v1:
> > >
> > > - Remove `SIGHASH` from signatures.
> > > - Put `SIGHASH` on public keys.
> > >
> > > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> > > `OP_CHECKSIG` and friends then look at the public key to determine sighash algorithm rather than the signature.
> > > As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> > > However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > I propose also the addition of the opcode:
> > >
> > > <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > >
> > >
> > > - `sighash` must be one byte.
> > > - `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> > > - `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> > > - `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> > > - If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > >
> > > This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> > > This is done by using the script:
> > >
> > > <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > >
> > >
> > > Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> > > This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
> > > However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
> > > Would this not be a superior solution?
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev at lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > Lightning-dev mailing list
> > Lightning-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>

2023-06-09 12:56:25

- reply

📅 Original date posted:2019-10-03
📝 Original message:
To avoid derailing the NO_INPUT conversation, I have changed the
subject to OP_CAT.
Responding to:
"""
* `SIGHASH` flags attached to signatures are a misdesign, sadly
retained from the original BitCoin 0.1.0 Alpha for Windows design, on
par with:
[..]
* `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
[..]
"""
OP_CAT is an extremely valuable op code. I understand why it was
removed as the situation at the time with scripts was dire. However
most of the protocols I've wanted to build on Bitcoin run into the
limitation that stack values can not be concatenated. For instance
TumbleBit would have far smaller transaction sizes if OP_CAT was
supported in Bitcoin. If it happens to me as a researcher it is
probably holding other people back as well. If I could wave a magic
wand and turn on one of the disabled op codes it would be OP_CAT. Of
course with the change that size of each concatenated value must be 64
Bytes or less.
On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Good morning lists,
>
> Let me propose the below radical idea:
>
> * `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> * 1 RETURN
> * higher-`nSequence` replacement
> * DER-encoded pubkeys
> * unrestricted `scriptPubKey`
> * Payee-security-paid-by-payer (i.e. lack of P2SH)
> * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> * transaction malleability
> * probably many more
>
> So let me propose the more radical excision, starting with SegWit v1:
>
> * Remove `SIGHASH` from signatures.
> * Put `SIGHASH` on public keys.
>
> Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> `OP_CHECKSIG` and friends then look at the *public key* to determine sighash algorithm rather than the signature.
>
> As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
>
> I propose also the addition of the opcode:
>
> <sighash> <pubkey> OP_SETPUBKEYSIGHASH
>
> * `sighash` must be one byte.
> * `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> * `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> * `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> * If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
>
> This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> This is done by using the script:
>
> <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
>
> Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
>
> However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
>
> This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
>
> Would this not be a superior solution?
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-09 12:56:24

- reply

📅 Original date posted:2019-10-01
📝 Original message:
>I don't find too compelling the potential problem of a 'bad wallet designer', whether lazy or dogmatic, misusing noinput. I think there are simpler ways to cut corners and there will always be plenty of good wallet options people can choose.
I want to second this. The most expensive part of wallet design is
engineering time. Writing code that uses a new sighash or a custom
script with a OP_CODE is a very large barrier to use. How many wallets
support multisig or RBF? How much BTC has been stolen over the entire
history of Bitcoin because of sighash SIGHASH_NONE or SIGHASH_SINGLE
vs ECDSA nonce reuse?
On Tue, Oct 1, 2019 at 9:35 AM Richard Myers <rich at gotenna.com> wrote:
>
> Thanks Christian for pulling together this concise summary.
>
>> 1. General agreement on the usefulness of noinput / anyprevoutanyscript /
>> anyprevout.
>
>
> I certainly support the unification and adoption of the sighash_noinput and anyprevoutput* proposals to enable eltoo, but also to make possible better off-chain protocol designs generally.
>
> Among the various advantages previously discussed, the particular use case benefits from eltoo I want to take advantage of is less interactive payment channel negotiation.
>
> In talking with people about eltoo this summer, I found most people generally support adding this as an option to Lightning. The only general concern I heard, if any, was the vague idea that rebindable transactions could be somehow misused or abused.
>
> I believe when these concerns are made more concrete they can be classified and addressed.
>
> I don't find too compelling the potential problem of a 'bad wallet designer', whether lazy or dogmatic, misusing noinput. I think there are simpler ways to cut corners and there will always be plenty of good wallet options people can choose.
>
> Because scripts signed with no_input signatures are only really exchanged and used for off-chain negotiations, very few should ever appear on chain. Those that do should represent non-cooperative situations that involve signing parties who know not to reuse or share scripts with these public keys again. No third party has any reason to spend value to a multisignature script they don't control, whether or not a no_input signature exists for it.
>
>> 2. Is there strong support or opposition to the chaperone signatures
>> introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
>> formulate a concrete set of pros and contras, rather than talk about
>> abstract dangers or advantages.
>
>
> As I mentioned before, I don't think the lazy wallet designer advantage is enough to justify the downsides of chaperone signatures. One additional downside is the additional code complexity required to flag whether or not a chaperone output is included. By comparison, the code changes for creating a no_input digest that skips the prevout and prevscript parts of a tx is much less intrusive and easier to maintain.
>
>> 3. The same for output tagging / explicit opt-in. What are the advantages and
>> disadvantages?
>
>
> I see the point ZmnSCPxj makes about tagged outputs negatively impacting the anonymity set of taproot transactions. The suggested work around would impose a cost to unilateral closes of an additional translation transaction and not using the work around would cause a hit to anonymity for off-chain script users. I feel both costs are too high relative to the benefit gained of preventing sloppy reuse of public keys.
>
>> 4. Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>> confusion and make for simpler discussions in the end.
>
>
> I believe they should be merged. I also think both chaperone signatures and output tagging should become part of the discussion of security alternatives, but not part of the initial specification.
>
> I understand the desire to be conservative with protocol changes that could be misused. However, with just taproot and taproot public key types the anyprevout functionality is already very opt-in and not something that might accidentally get used. Belt-and-suspender protections like chaperone signatures and tagged outputs have their own impacts on code complexity, on-chain transaction sizes and transaction anonymity that also must be considered.
>
> I believe efforts like descriptors will help people follow best practices when working with complex scripts without pushing extra complexity for safety into the consensus layer of bitcoin. Anywhere we can make core code simpler, and handle foot-guns in higher level non-consensus code, the better.
>
> _______________________________________________
>>
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

2023-06-07 22:56:54

- reply

📅 Original date posted:2021-07-09
📝 Original message:>To implement Winternitz we need some kind of limited-repeat construct, which is not available in SCRIPT, but may be emulatable with enough `OP_IF` and sheer brute force.
But what you gain in smaller signatures, you lose in a more complex
and longer SCRIPT, and there are limits to SCRIPT size (in order to
limit the processing done in each node).
Using depth 4 Winternitz would increase the number of instructions in
SCRIPT by 4*(signature bits/2) instructions, but decrease the
signature size by (signature bits/2) hash preimages. Given that
instructions are significantly smaller in size than the hash preimages
used, it seems like this would significantly reduce total size.
>Merkle signatures trade off shorter pubkeys for longer signatures (signatures need to provide the hash of the *other* preimage you are not revealing), but in the modern post-SegWit Bitcoin context both pubkeys and signatures are stored in the witness area, which have the same weight, thus it is actually a loss compared to Lamport.
I wasn't proposing using plain merkle signatures, rather I was
thinking about something where if particular chunks of the message fit
a pattern you could release a seed higher in the commitment tree. For
instance 1,1,1 could be signed as by releasing H(01||H(01||H(01||x))),
H(11||H(11||H(11||x))), H(21||H(21||H(21||x))), or by releasing X.
However, you would want to only release X in that one specific case
(1,1,1) but no others. Again this would bloat the SCRIPT and decrease
signature size but at a favorable ratio.
I am not convinced anyone should do these things, but they are fun to
think about and I suspect with more thought such signature sizes and
SCRIPT sizes could be even further reduced.
On Fri, Jul 9, 2021 at 6:38 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> Good morning Ethan,
>
> > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple kilobytes)... blocksize increase cough
> >
> > Couldn't you significantly compress the signatures by using either
> > Winternitz OTS or by using OP_CAT to build a merkle tree so that the
> > full signature can be derived during script execution from a much
> > shorter set of seed values?
>
> To implement Winternitz we need some kind of limited-repeat construct, which is not available in SCRIPT, but may be emulatable with enough `OP_IF` and sheer brute force.
> But what you gain in smaller signatures, you lose in a more complex and longer SCRIPT, and there are limits to SCRIPT size (in order to limit the processing done in each node).
>
> Merkle signatures trade off shorter pubkeys for longer signatures (signatures need to provide the hash of the *other* preimage you are not revealing), but in the modern post-SegWit Bitcoin context both pubkeys and signatures are stored in the witness area, which have the same weight, thus it is actually a loss compared to Lamport.
>
>
> So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy refers to), Merkle not so much.
>
> Regards,
> ZmnSCPxj
>
> > On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
> > bitcoin-dev at lists.linuxfoundation.org wrote:
> >
> > > Good morning Jeremy,
> > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple kilobytes)... blocksize increase cough
> > > Since a quantum computer can derive the EC privkey from the EC pubkey and this scheme is resistant to that, I think you can use a single well-known EC privkey, you just need a unique Lamport keypair for each UTXO (uniqueness being mandatory due to Lamport requiring preimage revelation).
> > > Regards,
> > > ZmnSCPxj
> > >
> > > > Dear Bitcoin Devs,
> > > > As mentioned previously, OP_CAT (or similar operation) can be used to make Bitcoin "quantum safe" by signing an EC signature. This should work in both Segwit V0 and Tapscript, although you have to use HASH160 for it to fit in Segwit V0.
> > > > See my blog for the specific construction, reproduced below.
> > > > Yet another entry to the "OP_CAT can do that too" list.
> > > > Best,
> > > >
> > > > Jeremy
> > > >
> > > > -------
> > > >
> > > > I recently published a blogpost about signing up to a5 byte value using Bitcoin script arithmetic and Lamport signatures.
> > > > By itself, this is neat, but a little limited. What if we could sign longer
> > > > messages? If we can sign up to 20 bytes, we could sign a HASH160 digest which
> > > > is most likely quantum safe...
> > > > What would it mean if we signed the HASH160 digest of a signature? What the
> > > > what? Why would we do that?
> > > > Well, as it turns out, even if a quantum computer were able to crack ECDSA, it
> > > > would yield revealing the private key but not the ability to malleate the
> > > > content of what was actually signed. I asked my good friend and cryptographer
> > > > Madars Virza if my intuition was correct, and he
> > > > confirmed that it should be sufficient, but it's definitely worth closer
> > > > analysis before relying on this. While the ECDSA signature can be malleated to a
> > > > different, negative form, if the signature is otherwise made immalleable there
> > > > should only be one value the commitment can be opened to.
> > > > If we required the ECDSA signature be signed with a quantum proof signature
> > > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing scheme
> > > > we discussed previously is a Lamport signature, which is quantum secure.
> > > > Unfortunately, we need at least 20 contiguous bytes... so we need some sort of
> > > > OP\_CAT like operation.
> > > > OP\_CAT can't be directly soft forked to Segwit v0 because it modifies the
> > > > stack, so instead we'll (for simplicity) also show how to use a new opcode that
> > > > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a string
> > > > for equality.
> > > >
> > > > ... FOR j in 0..=5
> > > > <0>
> > > > ... FOR i in 0..=31
> > > > SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <2**i> ADD ELSE <H(K_j_i_0)> EQUALVERIFY ENDIF
> > > > ... END FOR
> > > > TOALTSTACK
> > > > ... END FOR
> > > >
> > > > DUP HASH160
> > > >
> > > > ... IF CAT AVAILABLE
> > > > FROMALTSTACK
> > > > ... FOR j in 0..=5
> > > > FROMALTSTACK
> > > > CAT
> > > > ... END FOR
> > > > EQUALVERIFY
> > > > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> > > > ... FOR j in 0..=5
> > > > FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
> > > > ... END FOR
> > > > DROP
> > > > ... END IF
> > > >
> > > > <pk> CHECKSIG
> > > >
> > > >
> > > > That's a long script... but will it fit? We need to verify 20 bytes of message
> > > > each bit takes around 10 bytes script, an average of 3.375 bytes per number
> > > > (counting pushes), and two 21 bytes keys = 55.375 bytes of program space and 21
> > > > bytes of witness element per bit.
> > > > It fits! `20*8*55.375 = 8860`, which leaves 1140 bytes less than the limit for
> > > > the rest of the logic, which is plenty (around 15-40 bytes required for the rest
> > > > of the logic, leaving 1100 free for custom signature checking). The stack size
> > > > is 160 elements for the hash gadget, 3360 bytes.
> > > > This can probably be made a bit more efficient by expanding to a ternary
> > > > representation.
> > > >
> > > > SWAP hash160 DUP <H(K_j_i_0)> EQUAL IF DROP ELSE <3**i> SWAP DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_i_1)> EQUALVERIFY ADD ENDIF ENDIF
> > > >
> > > >
> > > > This should bring it up to roughly 85 bytes per trit, and there should be 101
> > > > trits (`log(2**160)/log(3) == 100.94`), so about 8560 bytes... a bit cheaper!
> > > > But the witness stack is "only" `2121` bytes...
> > > > As a homework exercise, maybe someone can prove the optimal choice of radix for
> > > > this protocol... My guess is that base 4 is optimal!
> > > >
> > > > Taproot?
> > > >
> > > > ---------
> > > >
> > > > What about Taproot? As far as I'm aware the commitment scheme (`Q = pG + hash(pG || m)G`) can be securely opened to m even with a quantum computer (finding `q`
> > > > such that `qG = Q` might be trivial, but suppose key path was disabled, then
> > > > finding m and p such that the taproot equation holds should be difficult because
> > > > of the hash, but I'd need to certify that claim better). Therefore this
> > > > script can nest inside of a Tapscript path -- Tapscript also does not impose a
> > > > length limit, 32 byte hashes could be used as well.
> > > > Further, to make keys reusable, there could be many Lamport keys comitted inside
> > > > a taproot tree so that an address could be used for thousands of times before
> > > > expiring. This could be used as a measure to protect accidental use rather than
> > > > to support it.
> > > > Lastly, Schnorr actually has a stronger non-malleability property than ECDSA,
> > > > the signatures will be binding to the approved transaction and once Lamport
> > > > signed, even a quantum computer could not steal the funds.
> > > > --
> > > > @JeremyRubin
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev at lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

2023-06-07 22:56:52

- reply

📅 Original date posted:2021-07-09
📝 Original message:>Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple kilobytes)... blocksize increase *cough*
Couldn't you significantly compress the signatures by using either
Winternitz OTS or by using OP_CAT to build a merkle tree so that the
full signature can be derived during script execution from a much
shorter set of seed values?
On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>
> Good morning Jeremy,
>
> Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple kilobytes)... blocksize increase *cough*
>
> Since a quantum computer can derive the EC privkey from the EC pubkey and this scheme is resistant to that, I think you can use a single well-known EC privkey, you just need a unique Lamport keypair for each UTXO (uniqueness being mandatory due to Lamport requiring preimage revelation).
>
> Regards,
> ZmnSCPxj
>
>
> > Dear Bitcoin Devs,
> >
> > As mentioned previously, OP_CAT (or similar operation) can be used to make Bitcoin "quantum safe" by signing an EC signature. This should work in both Segwit V0 and Tapscript, although you have to use HASH160 for it to fit in Segwit V0.
> >
> > See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for the specific construction, reproduced below.
> >
> > Yet another entry to the "OP_CAT can do that too" list.
> >
> > Best,
> >
> > Jeremy
> > -----
> >
> > I recently published [a blog
> > post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about signing up to a
> > 5 byte value using Bitcoin script arithmetic and Lamport signatures.
> >
> > By itself, this is neat, but a little limited. What if we could sign longer
> > messages? If we can sign up to 20 bytes, we could sign a HASH160 digest which
> > is most likely quantum safe...
> >
> > What would it mean if we signed the HASH160 digest of a signature? What the
> > what? Why would we do that?
> >
> > Well, as it turns out, even if a quantum computer were able to crack ECDSA, it
> > would yield revealing the private key but not the ability to malleate the
> > content of what was actually signed. I asked my good friend and cryptographer
> > [Madars Virza](https://madars.org/) if my intuition was correct, and he
> > confirmed that it should be sufficient, but it's definitely worth closer
> > analysis before relying on this. While the ECDSA signature can be malleated to a
> > different, negative form, if the signature is otherwise made immalleable there
> > should only be one value the commitment can be opened to.
> >
> > If we required the ECDSA signature be signed with a quantum proof signature
> > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing scheme
> > we discussed previously is a Lamport signature, which is quantum secure.
> > Unfortunately, we need at least 20 contiguous bytes... so we need some sort of
> > OP\_CAT like operation.
> >
> > OP\_CAT can't be directly soft forked to Segwit v0 because it modifies the
> > stack, so instead we'll (for simplicity) also show how to use a new opcode that
> > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a string
> > for equality.
> >
> > ```
> > ... FOR j in 0..=5
> > <0>
> > ... FOR i in 0..=31
> > SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <2**i> ADD ELSE <H(K_j_i_0)> EQUALVERIFY ENDIF
> > ... END FOR
> > TOALTSTACK
> > ... END FOR
> >
> > DUP HASH160
> >
> > ... IF CAT AVAILABLE
> > FROMALTSTACK
> > ... FOR j in 0..=5
> > FROMALTSTACK
> > CAT
> > ... END FOR
> > EQUALVERIFY
> > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> > ... FOR j in 0..=5
> > FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
> > ... END FOR
> > DROP
> > ... END IF
> >
> > <pk> CHECKSIG
> > ```
> >
> > That's a long script... but will it fit? We need to verify 20 bytes of message
> > each bit takes around 10 bytes script, an average of 3.375 bytes per number
> > (counting pushes), and two 21 bytes keys = 55.375 bytes of program space and 21
> > bytes of witness element per bit.
> >
> > It fits! `20*8*55.375 = 8860`, which leaves 1140 bytes less than the limit for
> > the rest of the logic, which is plenty (around 15-40 bytes required for the rest
> > of the logic, leaving 1100 free for custom signature checking). The stack size
> > is 160 elements for the hash gadget, 3360 bytes.
> >
> > This can probably be made a bit more efficient by expanding to a ternary
> > representation.
> >
> > ```
> > SWAP hash160 DUP <H(K_j_i_0)> EQUAL IF DROP ELSE <3**i> SWAP DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_i_1)> EQUALVERIFY ADD ENDIF ENDIF
> > ```
> >
> > This should bring it up to roughly 85 bytes per trit, and there should be 101
> > trits (`log(2**160)/log(3) == 100.94`), so about 8560 bytes... a bit cheaper!
> > But the witness stack is "only" `2121` bytes...
> >
> > As a homework exercise, maybe someone can prove the optimal choice of radix for
> > this protocol... My guess is that base 4 is optimal!
> >
> > ## Taproot?
> >
> > What about Taproot? As far as I'm aware the commitment scheme (`Q = pG + hash(pG
> > || m)G`) can be securely opened to m even with a quantum computer (finding `q`
> > such that `qG = Q` might be trivial, but suppose key path was disabled, then
> > finding m and p such that the taproot equation holds should be difficult because
> > of the hash, but I'd need to certify that claim better). Therefore this
> > script can nest inside of a Tapscript path -- Tapscript also does not impose a
> > length limit, 32 byte hashes could be used as well.
> >
> > Further, to make keys reusable, there could be many Lamport keys comitted inside
> > a taproot tree so that an address could be used for thousands of times before
> > expiring. This could be used as a measure to protect accidental use rather than
> > to support it.
> >
> > Lastly, Schnorr actually has a stronger non-malleability property than ECDSA,
> > the signatures will be binding to the approved transaction and once Lamport
> > signed, even a quantum computer could not steal the funds.
> >
> > --
> > @JeremyRubin
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:22:09

- reply

📅 Original date posted:2019-12-28
📝 Original message:I'm only going to talk about cashfusion and not the knapsack paper.
The language they use to describe the cashfusion protocol is very
broad and could describe many things. Because it is hard so vague I
don't want to dismiss the cashfusion approach out of hand. For
instance they say: "inputs of arbitary amounts in the neighborhood of
~0.1 BCH" what exactly does this mean?
Attack 1:
If we assume arbitrary means any precision then a trivial attack is
possible. Consider the case where one of the inputs has more precision
than any other input. This allows an attacker to trivially break the
privacy of that input:
Lets look at a toy example that takes 12 inputs and creates 3 outputs
inputs:
0.1525
0.1225
0.1145
0.1443
0.1144111
0.1001
0.1124
0.1093
0.1113
0.1134
0.1029
0.1206
Outputs:
0.4648111
0.5185
0.4349
Clearly output output 0.4648111 contains input 0.1144111.
Attack 2:
Let's say you attempt to address this problem this by limiting the
precision of inputs to two decimal places i.e. 0.1X where 0<=X<=9.
Consider the case of 10 users where each user is always joining sets
of 10 inputs to create 1 output. Thus in total you would have 100
inputs and 10 outputs in the coinjoin. If one of those outputs is 2
then you know its inputs must all be 0.2. Using this method you can
start eliminate input output pairs far faster brute force. How much
faster is hard to say without adding additional assumptions for
instance are these inputs amounts drawn from a uniform distribution?
I want to be clear. I'm not saying cashfusion is broken or that this
more inputs than outputs technique is a dead end. However the
description given is vague and could be interpreted to describe a
broken protocol. Is this actively being used?
On Fri, Dec 27, 2019 at 8:29 PM nopara73 via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> The CashFusion research came out of the Bitcoin Cash camp, thus this probably went under the radar of many of you. I would like to ask your opinions on the research's claim that, if non-equal value coinjoins can be really relied on for privacy or not.
>
> (Btw, there were also similar ideas in the Knapsack paper in 2017: https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf )
>
> https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#avoiding-amount-linkages-through-combinatorics
>
> I copy the most relevant paragraphs here:
>
> ---------BEGIN QUOTE ---------
>
>
> Consider a transaction where 10 people have each brought 10 inputs of arbitary amounts in the neighborhood of ~0.1 BCH. One input might be 0.03771049 BCH; the next might be 0.24881232 BCH, etc. All parties have chosen to consolidate their coins, so the transaction has 10 outputs of around 1 BCH. So the transaction has 100 inputs, and 10 outputs. The first output might be 0.91128495, the next could be 1.79783710, etc.
>
> Now, there are 100!/(10!)^10 ~= 10^92 ways to partition the inputs into a list of 10 sets of 10 inputs, but only a tiny fraction of these partitions will produce the precise output list. So, how many ways produce this exact output list? We can estimate with some napkin math. First, recognize that for each partitioning, each output will typically land in a range of ~10^8 discrete possibilities (around 1 BCH wide, with a 0.00000001 BCH resolution). The first 9 outputs all have this range of possibilities, and the last will be constrained by the others. So, the 10^92 possibilies will land somewhere within a 9-dimensional grid that cointains (10^8)^9=10^72 possible distinct sites, one site which is our actual output list. Since we are stuffing 10^92 possibilties into a grid that contains only 10^72 sites, then this means on average, each site will have 10^20 possibilities.
>
> Based on the example above, we can see that not only are there a huge number of partitions, but that even with a fast algorithm that could find matching partitions, it would produce around 10^20 possible valid configurations. With 10^20 possibilities, there is essentially no linkage. The Cash Fusion scheme actually extends this obfuscation even further. Not only can players bring many inputs, they can also have multiple outputs.
>
> ---------END QUOTE ---------
> --
> Best,
> Ádám
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:20:53

- reply

📅 Original date posted:2019-10-03
📝 Original message:I hope you are having an great afternoon ZmnSCPxj,
You make an excellent point!
I had thought about doing the following to tag nodes
|| means OP_CAT
`node = SHA256(type||SHA256(data))`
so a subnode would be
`subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
and a leaf node would be
`leafnode = SHA256(0||SHA256(leafdata))`
Yet, I like your idea better. Increasing the size of the two inputs to
OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
size of object on the stack seems sensible and also doesn't special
case the logic of OP_CAT.
It would also increase performance. SHA256(tag||subnode2||subnode3)
requires 2 compression function calls whereas
SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
function calls (due to padding).
>Or we could implement tagged SHA256 as a new opcode...
I agree that tagged SHA256 as an op code that would certainty be
useful, but OP_CAT provides far more utility and is a simpler change.
Thanks,
Ethan
On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> Good morning Ethan,
>
>
> > To avoid derailing the NO_INPUT conversation, I have changed the
> > subject to OP_CAT.
> >
> > Responding to:
> > """
> >
> > - `SIGHASH` flags attached to signatures are a misdesign, sadly
> > retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> > par with:
> > [..]
> >
> > - `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > [..]
> > """
> >
> > OP_CAT is an extremely valuable op code. I understand why it was
> > removed as the situation at the time with scripts was dire. However
> > most of the protocols I've wanted to build on Bitcoin run into the
> > limitation that stack values can not be concatenated. For instance
> > TumbleBit would have far smaller transaction sizes if OP_CAT was
> > supported in Bitcoin. If it happens to me as a researcher it is
> > probably holding other people back as well. If I could wave a magic
> > wand and turn on one of the disabled op codes it would be OP_CAT. Of
> > course with the change that size of each concatenated value must be 64
> > Bytes or less.
>
> Why 64 bytes in particular?
>
> It seems obvious to me that this 64 bytes is most suited for building Merkle trees, being the size of two SHA256 hashes.
>
> However we have had issues with the use of Merkle trees in Bitcoin blocks.
> Specifically, it is difficult to determine if a hash on a Merkle node is the hash of a Merkle subnode, or a leaf transaction.
> My understanding is that this is the reason for now requiring transactions to be at least 80 bytes.
>
> The obvious fix would be to prepend the type of the hashed object, i.e. add at least one byte to determine this type.
> Taproot for example uses tagged hash functions, with a different tag for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-before-you-SHA256.
>
> This seems to indicate that to check merkle tree proofs, an `OP_CAT` with only 64 bytes max output size would not be sufficient.
>
> Or we could implement tagged SHA256 as a new opcode...
>
> Regards,
> ZmnSCPxj
>
>
> >
> > On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> > bitcoin-dev at lists.linuxfoundation.org wrote:
> >
> >
> > > Good morning lists,
> > > Let me propose the below radical idea:
> > >
> > > - `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> > > - 1 RETURN
> > > - higher-`nSequence` replacement
> > > - DER-encoded pubkeys
> > > - unrestricted `scriptPubKey`
> > > - Payee-security-paid-by-payer (i.e. lack of P2SH)
> > > - `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > - transaction malleability
> > > - probably many more
> > >
> > > So let me propose the more radical excision, starting with SegWit v1:
> > >
> > > - Remove `SIGHASH` from signatures.
> > > - Put `SIGHASH` on public keys.
> > >
> > > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> > > `OP_CHECKSIG` and friends then look at the public key to determine sighash algorithm rather than the signature.
> > > As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> > > However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > I propose also the addition of the opcode:
> > >
> > > <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > >
> > >
> > > - `sighash` must be one byte.
> > > - `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> > > - `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> > > - `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> > > - If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > >
> > > This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> > > This is done by using the script:
> > >
> > > <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > >
> > >
> > > Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> > > This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
> > > However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
> > > Would this not be a superior solution?
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev at lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > Lightning-dev mailing list
> > Lightning-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>

2023-06-07 18:20:52

- reply

📅 Original date posted:2019-10-03
📝 Original message:To avoid derailing the NO_INPUT conversation, I have changed the
subject to OP_CAT.
Responding to:
"""
* `SIGHASH` flags attached to signatures are a misdesign, sadly
retained from the original BitCoin 0.1.0 Alpha for Windows design, on
par with:
[..]
* `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
[..]
"""
OP_CAT is an extremely valuable op code. I understand why it was
removed as the situation at the time with scripts was dire. However
most of the protocols I've wanted to build on Bitcoin run into the
limitation that stack values can not be concatenated. For instance
TumbleBit would have far smaller transaction sizes if OP_CAT was
supported in Bitcoin. If it happens to me as a researcher it is
probably holding other people back as well. If I could wave a magic
wand and turn on one of the disabled op codes it would be OP_CAT. Of
course with the change that size of each concatenated value must be 64
Bytes or less.
On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Good morning lists,
>
> Let me propose the below radical idea:
>
> * `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> * 1 RETURN
> * higher-`nSequence` replacement
> * DER-encoded pubkeys
> * unrestricted `scriptPubKey`
> * Payee-security-paid-by-payer (i.e. lack of P2SH)
> * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> * transaction malleability
> * probably many more
>
> So let me propose the more radical excision, starting with SegWit v1:
>
> * Remove `SIGHASH` from signatures.
> * Put `SIGHASH` on public keys.
>
> Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> `OP_CHECKSIG` and friends then look at the *public key* to determine sighash algorithm rather than the signature.
>
> As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
>
> I propose also the addition of the opcode:
>
> <sighash> <pubkey> OP_SETPUBKEYSIGHASH
>
> * `sighash` must be one byte.
> * `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> * `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> * `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> * If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
>
> This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> This is done by using the script:
>
> <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
>
> Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
>
> However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
>
> This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
>
> Would this not be a superior solution?
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:20:50

- reply

📅 Original date posted:2019-10-01
📝 Original message:>I don't find too compelling the potential problem of a 'bad wallet designer', whether lazy or dogmatic, misusing noinput. I think there are simpler ways to cut corners and there will always be plenty of good wallet options people can choose.
I want to second this. The most expensive part of wallet design is
engineering time. Writing code that uses a new sighash or a custom
script with a OP_CODE is a very large barrier to use. How many wallets
support multisig or RBF? How much BTC has been stolen over the entire
history of Bitcoin because of sighash SIGHASH_NONE or SIGHASH_SINGLE
vs ECDSA nonce reuse?
On Tue, Oct 1, 2019 at 9:35 AM Richard Myers <rich at gotenna.com> wrote:
>
> Thanks Christian for pulling together this concise summary.
>
>> 1. General agreement on the usefulness of noinput / anyprevoutanyscript /
>> anyprevout.
>
>
> I certainly support the unification and adoption of the sighash_noinput and anyprevoutput* proposals to enable eltoo, but also to make possible better off-chain protocol designs generally.
>
> Among the various advantages previously discussed, the particular use case benefits from eltoo I want to take advantage of is less interactive payment channel negotiation.
>
> In talking with people about eltoo this summer, I found most people generally support adding this as an option to Lightning. The only general concern I heard, if any, was the vague idea that rebindable transactions could be somehow misused or abused.
>
> I believe when these concerns are made more concrete they can be classified and addressed.
>
> I don't find too compelling the potential problem of a 'bad wallet designer', whether lazy or dogmatic, misusing noinput. I think there are simpler ways to cut corners and there will always be plenty of good wallet options people can choose.
>
> Because scripts signed with no_input signatures are only really exchanged and used for off-chain negotiations, very few should ever appear on chain. Those that do should represent non-cooperative situations that involve signing parties who know not to reuse or share scripts with these public keys again. No third party has any reason to spend value to a multisignature script they don't control, whether or not a no_input signature exists for it.
>
>> 2. Is there strong support or opposition to the chaperone signatures
>> introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
>> formulate a concrete set of pros and contras, rather than talk about
>> abstract dangers or advantages.
>
>
> As I mentioned before, I don't think the lazy wallet designer advantage is enough to justify the downsides of chaperone signatures. One additional downside is the additional code complexity required to flag whether or not a chaperone output is included. By comparison, the code changes for creating a no_input digest that skips the prevout and prevscript parts of a tx is much less intrusive and easier to maintain.
>
>> 3. The same for output tagging / explicit opt-in. What are the advantages and
>> disadvantages?
>
>
> I see the point ZmnSCPxj makes about tagged outputs negatively impacting the anonymity set of taproot transactions. The suggested work around would impose a cost to unilateral closes of an additional translation transaction and not using the work around would cause a hit to anonymity for off-chain script users. I feel both costs are too high relative to the benefit gained of preventing sloppy reuse of public keys.
>
>> 4. Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>> confusion and make for simpler discussions in the end.
>
>
> I believe they should be merged. I also think both chaperone signatures and output tagging should become part of the discussion of security alternatives, but not part of the initial specification.
>
> I understand the desire to be conservative with protocol changes that could be misused. However, with just taproot and taproot public key types the anyprevout functionality is already very opt-in and not something that might accidentally get used. Belt-and-suspender protections like chaperone signatures and tagged outputs have their own impacts on code complexity, on-chain transaction sizes and transaction anonymity that also must be considered.
>
> I believe efforts like descriptors will help people follow best practices when working with complex scripts without pushing extra complexity for safety into the consensus layer of bitcoin. Anywhere we can make core code simpler, and handle foot-guns in higher level non-consensus code, the better.
>
> _______________________________________________
>>
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

2023-06-07 18:19:49

- reply

📅 Original date posted:2019-08-02
📝 Original message:Attack 1:
I partition (i.e. eclipse) a bunch of nodes from the network this partition
contains no mining power . I then mine 145 blocks for this partition. I
don't even need 51% of the mining power because I'm not competing with any
other miners. Under this rule this partition will hardfork from the network
permanently. Under current rules this partition will be able to rejoin the
network as the least weight chain will be orphaned.
Attack 2:
I pre-mine 145 blocks. A node goes offline for 24 hours, when it rejoins I
feed it 145 blocks which fork off from the consensus chain. I have 24+24
hours to mine these 145 blocks so I should be able to do this with 25% of
the current hash rate at the time the node went offline. Under your rule
each of these offline-->online nodes I attack this way will hardfork
themselves from the rest of the network.
I believe a moving-checkpoint rule as describe above would make Bitcoin
more vulnerable to 51% attacks.
A safer rule would be if a node detects a fork with both sides of the split
having length > 144 blocks, it halts and requests user intervention to
determine which chain to follow. I don't think 144 blocks is a great
number to use here as 24 hours is very short. I suspect you could improve
the security of the rule by making the number of blocks a fork most reach
to halt the network proportional to the difference in time between the
timestamp in the block prior to the fork and the current time. I am **NOT**
proposing Bitcoin adopt such a rule.
NXT has a fundamentally different security model as it uses Proof-of-stake
rather than Proof-of-Work.
On Wed, Jul 31, 2019 at 2:37 PM Kenshiro [] via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> P.S.: To be clearer, in this example I set an N value of 144 blocks, which
> is approximately 24 hours.
>
> ------------------------------
> *From:* Kenshiro [] <tensiam at hotmail.com>
> *Sent:* Wednesday, July 31, 2019 16:40
> *To:* Alistair Mann <al at pectw.net>; Bitcoin Protocol Discussion <
> bitcoin-dev at lists.linuxfoundation.org>
> *Subject:* Re: [bitcoin-dev] Add a moving checkpoint to the Bitcoin
> protocol
>
> >>> How would a (potentially, state-sponsored) netsplit lasting longer
> than N be
> handled?
>
> It would be detected by the community much before reaching the reorg limit
> of N blocks (it's 24 hours) so nodes could stop until the netsplit is
> fixed.
>
> In the extreme case no one notice the network split during more than N
> blocks (24 hours) and there are 2 permanent forks longer than N, nodes
> from one branch could delete their local history so they would join the
> other branch.
>
> Regards,
>
>
> ------------------------------
> *From:* Alistair Mann <al at pectw.net>
> *Sent:* Wednesday, July 31, 2019 15:59
> *To:* Kenshiro [] <tensiam at hotmail.com>; Bitcoin Protocol Discussion <
> bitcoin-dev at lists.linuxfoundation.org>
> *Subject:* Re: [bitcoin-dev] Add a moving checkpoint to the Bitcoin
> protocol
>
> On Wednesday 31 Jul 2019 12:28:58 Kenshiro [] via bitcoin-dev wrote:
>
> > I would like to propose that a "moving checkpoint" is added to the
> Bitcoin
> > protocol. It's a very simple rule already implemented in NXT coin:
> >
> > - A node will ignore any new block under nodeBlockHeight - N, so the
> > blockchain becomes truly immutable after N blocks, even during a 51%
> attack
> > which thanks to the moving checkpoint can't rewrite history older than
> the
> > last N blocks.
>
> How would a (potentially, state-sponsored) netsplit lasting longer than N
> be
> handled?
> --
> Alistair Mann
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190802/9071fcc3/attachment-0001.html>

2023-06-07 18:17:42

- reply

📅 Original date posted:2019-04-19
📝 Original message:Good morning to you as well ZmnSCPxj,
My above email contains an error. The SPV client needs to only
download S+1, not S+1 and S+2.
I agree with you that a weakness of this approach is a miner can make
SPV clients do substantially more work. However:
1. Mining a block which will never be accepted is an expensive way to
make SPV clients download, validate and discard ~2-4 megabytes of
data. There are far less expensive ways of wasting the resources of
SPV clients. Its unclear why someone would want to do this instead of
just packeting full nodes or SPV servers like we saw with the recent
DDoS attacks against electrum servers.
2. SPV clients may not even learn about these splits because it
requires that someone relay the split to them. Honest full nodes
should not relay such splits. To their bitcoin's worth the attacker
must also connect to lots of SPV clients.
3. Having SPV clients slow down or become full nodes when a malicious
miner with significant mining power is attempting to disrupt the
network is probably a best case outcome. I would prefer this failure
mode to the current SPV behavior which is to just go with the
"longest" chain.
Thanks,
Ethan
On Thu, Apr 18, 2019 at 10:53 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> Good morning Ethan,
>
> Thank you for clarifying, I understand better now.
>
> It seems that minority miners can disrupt SPV clients such that SPV clients will download 2 blocks for every block the minority miner can find, not 1.
>
> This can be done by simply making multiple 1-block chainsplits, rather than a single persistent chainsplit, and alternating split-off and non-split-off.
>
> For instance, such a minority miner might split at S+1, forcing SPV clients to download S+1 and S+2.
> Then the minority miner splits at S+3, forcing SPV clients to download S+3 and S+4.
> With a mere 33% hashrate, this can force SPV clients to download every block, i.e. become a fullnode anyway.
>
> Since there exist pools with >33% hashrate, the above attack is possible so the only solution is to become a fullnode anyway.
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Friday, April 19, 2019 9:13 AM, Ethan Heilman <eth3rs at gmail.com> wrote:
>
> > Hi ZmnSCPxj,
> >
> > Let's see if I understand what you are saying. In your scenario chain
> > A consists of honest miners (10% of the hash rate) and chain B (90%
> > of the hash rate) consists of dishonest miners who are inflating the
> > coin supply.
> >
> > Chain A: S, S+1
> > Chain B: S, S+1 (invalid), S+2, S+3, S+4, S+5, S+6, S+7, S+8, S+9
> >
> > Chain B S+1 has a invalid coinbase
> >
> > > At around height S+9, the minority miners generate an alternate block at height S+1. So SPV nodes download S+9 and S+8 on the longer chain, and see nothing wrong with those blocks.
> >
> > What I am suggesting is that when the minority miners generate an
> > alternate block at S+1 (chain A) the SPV node would download blocks
> > S+1 and S+2 from chain B (the dishonest chain). Since S+1 has the
> > invalid coinbase the SPV node would learn that chain B is invalid and
> > abandon it.
> >
> > Bitcoin is in big trouble if a malicious party controls 90% of the
> > mining power. The malicious miners can spend +11% of their mining
> > power ensuring that the honest chain never reaches consensus by
> > continuously forking it. The malicious miners can then extend their
> > favored chain using the other 79% of the mining power. This would
> > produce a scenario in which users are forced to choose between a
> > stable chain that violates a consensus rule and an unstable honest
> > chain that is completely unusable and which never pays out mining
> > rewards. I agree that SPV nodes and many wallets would make this even
> > worse especially in their current condition where they just trust the
> > hash rate/wallet provider and there are no fraud proofs.
> >
> > On Thu, Apr 18, 2019 at 8:25 PM ZmnSCPxj ZmnSCPxj at protonmail.com wrote:
> >
> > > Good morning Ethan,
> > > Sent with ProtonMail Secure Email.
> > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > > On Friday, April 19, 2019 4:12 AM, Ethan Heilman eth3rs at gmail.com wrote:
> > >
> > > > I'm probably repeating a point which has been said before.
> > > >
> > > > > I suppose a minority miner that wants to disrupt the network could simply create a valid block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
> > > >
> > > > If this minority miner has > 10% of network hashrate, then the rule of
> > > > thumb above would, on average, give it the ability to disrupt the
> > > > SPV-using network.
> > > > Proposed rule:
> > > > Whenever a chainsplit occurs SPV clients should download and validate
> > > > the "longest chain" up to more than one block greater than the height
> > > > of the losing chain.
> > > > Lets say a block split causes chain A and chain B: Chain A is N blocks
> > > > long, chain B is M blocks long, and N < M. Then the SPV client should
> > > > download all the block data of N+1 blocks from Chain B to verify
> > > > availability of chain B. Once the SPV client has verified that chain B
> > > > is available they can use fraud proofs determine if chain B is valid.
> > >
> > > Let us then revert to the original scenario.
> > > Suppose a supermajority (90%) of miners decide to increase inflation of the currency.
> > > They do this by imposing the rule:
> > >
> > > 1. For 1 block, the coinbase is 21,000,000 times the pre-fork coinbase value.
> > > 2. For 9 blocks, the coinbase is the pre-fork value.
> > > 3. Repeat this pattern every 10 blocks.
> > >
> > > The above is a hardfork.
> > > However, as they believe that SPV nodes dominate the economy, this mining supermajority believes it can take over the network hashpower and impose its will on the network.
> > > At height S+1, they begin the above rule.
> > > This implies that at heights S+1, S+11, S+21, s+31... the coinbase violates the pre-hardfork rules.
> > > At around height S+9, the minority miners generate an alternate block at height S+1.
> > > So SPV nodes download S+9 and S+8 on the longer chain, and see nothing wrong with those blocks.
> > > At around height S+18, the minority miners generate an alternate block at height S+2.
> > > So SPV nodes download S+18, S+17, S+16 and again see nothing wrong with those blocsk.
> > > This can go on for a good amount of time.
> > > With a "rare enough" inflation event, miners may even be able to spend some coinbases on SPV nodes that SPV nodes become unwilling to revert to the minority pre-hardfork chain, economically locking in the post-hardfork inflation.
> > > Again: every rule is an opportunity to loophole.
> > > Regards,
> > > ZmnSCPxj
> > >
> > > > An attacker could use this to force SPV clients to download 1 block
> > > > per block the attacker mines. This is strictly weaker security than
> > > > provided by a full-node because chain B will only be validated if the
> > > > client knows chain A exists. If the SPV client's view of the
> > > > blockchain is eclipsed then the client will never learn that chain A
> > > > exists and thus never validate chain B's availability nor will the
> > > > client be able to learn fraud proofs about chain B. A full node in
> > > > this circumstance would notice that the chain B is invalid and reject
> > > > it because a full node would not depend on fraud proofs. That being
> > > > said this rule would provide strictly more security than current SPV
> > > > clients.
> > > > On Thu, Apr 18, 2019 at 3:08 PM ZmnSCPxj via bitcoin-dev
> > > > bitcoin-dev at lists.linuxfoundation.org wrote:
> > > >
> > > > > Good morning Ruben,
> > > > > Sent with ProtonMail Secure Email.
> > > > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > > > > On Thursday, April 18, 2019 9:44 PM, Ruben Somsen via bitcoin-dev bitcoin-dev at lists.linuxfoundation.org wrote:
> > > > >
> > > > > > Simplified-Payment-Verification (SPV) is secure under the assumption
> > > > > > that the chain with the most Proof-of-Work (PoW) is valid. As many
> > > > > > have pointed out before, and attacks like Segwit2x have shown, this is
> > > > > > not a safe assumption. What I propose below improves this assumption
> > > > > > -- invalid blocks will be rejected as long as there are enough honest
> > > > > > miners to create a block within a reasonable time frame. This still
> > > > > > doesn’t fully inoculate SPV clients against dishonest miners, but is a
> > > > > > clear improvement over regular SPV (and compatible with the privacy
> > > > > > improvements of BIP157[0]).
> > > > > > The idea is that a fork is an indication of potential misbehavior --
> > > > > > its block header can serve as a PoW fraud proof. Conversely, the lack
> > > > > > of a fork is an indication that a block is valid. If a fork is created
> > > > > > from a block at height N, this means a subset of miners may disagree
> > > > > > on the validity of block N+1. If SPV clients download and verify this
> > > > > > block, they can judge for themselves whether or not the chain should
> > > > > > be rejected. Of course it could simply be a natural fork, in which
> > > > > > case we continue following the chain with the most PoW.
> > > > >
> > > > > I presume you mean a chain split?
> > > > >
> > > > > > The way Bitcoin currently works, it is impossible to verify the
> > > > > > validity of block N+1 without knowing the UTXO set at block N, even if
> > > > > > you are willing to assume that block N (and everything before it) is
> > > > > > valid. This would change with the introduction of UTXO set
> > > > > > commitments, allowing block N+1 to be validated by verifying whether
> > > > > > its inputs are present in the UTXO set that was committed to in block
> > > > > > N. An open question is whether a similar result can be achieved
> > > > > > without a soft fork that commits to the UTXO set[0][1].
> > > > > > If an invalid block is created and only 10% of the miners are honest,
> > > > > > on average it would take 100 minutes for a valid block to appear.
> > > > > > During this time, the SPV client will be following the invalid chain
> > > > > > and see roughly 9 confirmations before the chain gets rejected. It may
> > > > > > therefore be prudent to wait for a number of confirmations that
> > > > > > corresponds to the time it may take for the conservative percentage of
> > > > > > miners that you think may behave honestly to create a block (including
> > > > > > variance).
> > > > >
> > > > > I suppose a minority miner that wants to disrupt the network could simply create a valid block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
> > > > > If this minority miner has > 10% of network hashrate, then the rule of thumb above would, on average, give it the ability to disrupt the SPV-using network.
> > > > >
> > > > > > 10% of network hashrate to disrupt the SPV-using nodes would be a rather low bar to disruption.
> > > > > > Consider that SPV-using nodes would be disrupted, without this rule, only by >50% network hashrate.
> > > > >
> > > > > It is helpful to consider that every rule you impose is potentially a loophole by which a new attack is possible.
> > > > > Regards,
> > > > > ZmnSCPxj
> > > > > bitcoin-dev mailing list
> > > > > bitcoin-dev at lists.linuxfoundation.org
> > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

2023-06-07 18:17:41

- reply

📅 Original date posted:2019-04-18
📝 Original message:Hi ZmnSCPxj,
Let's see if I understand what you are saying. In your scenario chain
A consists of honest miners (10% of the hash rate) and chain B (90%
of the hash rate) consists of dishonest miners who are inflating the
coin supply.
Chain A: S, S+1
Chain B: S, S+1 (invalid), S+2, S+3, S+4, S+5, S+6, S+7, S+8, S+9
Chain B S+1 has a invalid coinbase
>At around height S+9, the minority miners generate an alternate block at height S+1. So SPV nodes download S+9 and S+8 on the longer chain, and see nothing wrong with those blocks.
What I am suggesting is that when the minority miners generate an
alternate block at S+1 (chain A) the SPV node would download blocks
S+1 and S+2 from chain B (the dishonest chain). Since S+1 has the
invalid coinbase the SPV node would learn that chain B is invalid and
abandon it.
Bitcoin is in big trouble if a malicious party controls 90% of the
mining power. The malicious miners can spend +11% of their mining
power ensuring that the honest chain never reaches consensus by
continuously forking it. The malicious miners can then extend their
favored chain using the other 79% of the mining power. This would
produce a scenario in which users are forced to choose between a
stable chain that violates a consensus rule and an unstable honest
chain that is completely unusable and which never pays out mining
rewards. I agree that SPV nodes and many wallets would make this even
worse especially in their current condition where they just trust the
hash rate/wallet provider and there are no fraud proofs.
On Thu, Apr 18, 2019 at 8:25 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> Good morning Ethan,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Friday, April 19, 2019 4:12 AM, Ethan Heilman <eth3rs at gmail.com> wrote:
>
> > I'm probably repeating a point which has been said before.
> >
> > > I suppose a minority miner that wants to disrupt the network could simply create a valid block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
> >
> > If this minority miner has > 10% of network hashrate, then the rule of
> > thumb above would, on average, give it the ability to disrupt the
> > SPV-using network.
> >
> > Proposed rule:
> > Whenever a chainsplit occurs SPV clients should download and validate
> > the "longest chain" up to more than one block greater than the height
> > of the losing chain.
> >
> > Lets say a block split causes chain A and chain B: Chain A is N blocks
> > long, chain B is M blocks long, and N < M. Then the SPV client should
> > download all the block data of N+1 blocks from Chain B to verify
> > availability of chain B. Once the SPV client has verified that chain B
> > is available they can use fraud proofs determine if chain B is valid.
>
> Let us then revert to the original scenario.
> Suppose a supermajority (90%) of miners decide to increase inflation of the currency.
>
> They do this by imposing the rule:
>
> 1. For 1 block, the coinbase is 21,000,000 times the pre-fork coinbase value.
> 2. For 9 blocks, the coinbase is the pre-fork value.
> 3. Repeat this pattern every 10 blocks.
>
> The above is a hardfork.
> However, as they believe that SPV nodes dominate the economy, this mining supermajority believes it can take over the network hashpower and impose its will on the network.
>
> At height S+1, they begin the above rule.
> This implies that at heights S+1, S+11, S+21, s+31... the coinbase violates the pre-hardfork rules.
>
> At around height S+9, the minority miners generate an alternate block at height S+1.
> So SPV nodes download S+9 and S+8 on the longer chain, and see nothing wrong with those blocks.
>
> At around height S+18, the minority miners generate an alternate block at height S+2.
> So SPV nodes download S+18, S+17, S+16 and again see nothing wrong with those blocsk.
>
> This can go on for a good amount of time.
> With a "rare enough" inflation event, miners may even be able to spend some coinbases on SPV nodes that SPV nodes become unwilling to revert to the minority pre-hardfork chain, economically locking in the post-hardfork inflation.
>
> Again: every rule is an opportunity to loophole.
>
> Regards,
> ZmnSCPxj
>
> > An attacker could use this to force SPV clients to download 1 block
> > per block the attacker mines. This is strictly weaker security than
> > provided by a full-node because chain B will only be validated if the
> > client knows chain A exists. If the SPV client's view of the
> > blockchain is eclipsed then the client will never learn that chain A
> > exists and thus never validate chain B's availability nor will the
> > client be able to learn fraud proofs about chain B. A full node in
> > this circumstance would notice that the chain B is invalid and reject
> > it because a full node would not depend on fraud proofs. That being
> > said this rule would provide strictly more security than current SPV
> > clients.
> >
> > On Thu, Apr 18, 2019 at 3:08 PM ZmnSCPxj via bitcoin-dev
> > bitcoin-dev at lists.linuxfoundation.org wrote:
> >
> > > Good morning Ruben,
> > > Sent with ProtonMail Secure Email.
> > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > > On Thursday, April 18, 2019 9:44 PM, Ruben Somsen via bitcoin-dev bitcoin-dev at lists.linuxfoundation.org wrote:
> > >
> > > > Simplified-Payment-Verification (SPV) is secure under the assumption
> > > > that the chain with the most Proof-of-Work (PoW) is valid. As many
> > > > have pointed out before, and attacks like Segwit2x have shown, this is
> > > > not a safe assumption. What I propose below improves this assumption
> > > > -- invalid blocks will be rejected as long as there are enough honest
> > > > miners to create a block within a reasonable time frame. This still
> > > > doesn’t fully inoculate SPV clients against dishonest miners, but is a
> > > > clear improvement over regular SPV (and compatible with the privacy
> > > > improvements of BIP157[0]).
> > > > The idea is that a fork is an indication of potential misbehavior --
> > > > its block header can serve as a PoW fraud proof. Conversely, the lack
> > > > of a fork is an indication that a block is valid. If a fork is created
> > > > from a block at height N, this means a subset of miners may disagree
> > > > on the validity of block N+1. If SPV clients download and verify this
> > > > block, they can judge for themselves whether or not the chain should
> > > > be rejected. Of course it could simply be a natural fork, in which
> > > > case we continue following the chain with the most PoW.
> > >
> > > I presume you mean a chain split?
> > >
> > > > The way Bitcoin currently works, it is impossible to verify the
> > > > validity of block N+1 without knowing the UTXO set at block N, even if
> > > > you are willing to assume that block N (and everything before it) is
> > > > valid. This would change with the introduction of UTXO set
> > > > commitments, allowing block N+1 to be validated by verifying whether
> > > > its inputs are present in the UTXO set that was committed to in block
> > > > N. An open question is whether a similar result can be achieved
> > > > without a soft fork that commits to the UTXO set[0][1].
> > > > If an invalid block is created and only 10% of the miners are honest,
> > > > on average it would take 100 minutes for a valid block to appear.
> > > > During this time, the SPV client will be following the invalid chain
> > > > and see roughly 9 confirmations before the chain gets rejected. It may
> > > > therefore be prudent to wait for a number of confirmations that
> > > > corresponds to the time it may take for the conservative percentage of
> > > > miners that you think may behave honestly to create a block (including
> > > > variance).
> > >
> > > I suppose a minority miner that wants to disrupt the network could simply create a valid block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
> > > If this minority miner has > 10% of network hashrate, then the rule of thumb above would, on average, give it the ability to disrupt the SPV-using network.
> > >
> > > > 10% of network hashrate to disrupt the SPV-using nodes would be a rather low bar to disruption.
> > > > Consider that SPV-using nodes would be disrupted, without this rule, only by >50% network hashrate.
> > >
> > > It is helpful to consider that every rule you impose is potentially a loophole by which a new attack is possible.
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev at lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

2023-06-07 18:17:40

- reply

📅 Original date posted:2019-04-18
📝 Original message:I'm probably repeating a point which has been said before.
>I suppose a minority miner that wants to disrupt the network could simply create a *valid* block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
If this minority miner has > 10% of network hashrate, then the rule of
thumb above would, on average, give it the ability to disrupt the
SPV-using network.
Proposed rule:
Whenever a chainsplit occurs SPV clients should download and validate
the "longest chain" up to more than one block greater than the height
of the losing chain.
Lets say a block split causes chain A and chain B: Chain A is N blocks
long, chain B is M blocks long, and N < M. Then the SPV client should
download all the block data of N+1 blocks from Chain B to verify
availability of chain B. Once the SPV client has verified that chain B
is available they can use fraud proofs determine if chain B is valid.
An attacker could use this to force SPV clients to download 1 block
per block the attacker mines. This is strictly weaker security than
provided by a full-node because chain B will only be validated if the
client knows chain A exists. If the SPV client's view of the
blockchain is eclipsed then the client will never learn that chain A
exists and thus never validate chain B's availability nor will the
client be able to learn fraud proofs about chain B. A full node in
this circumstance would notice that the chain B is invalid and reject
it because a full node would not depend on fraud proofs. That being
said this rule would provide strictly more security than current SPV
clients.
On Thu, Apr 18, 2019 at 3:08 PM ZmnSCPxj via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Good morning Ruben,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Thursday, April 18, 2019 9:44 PM, Ruben Somsen via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> > Simplified-Payment-Verification (SPV) is secure under the assumption
> > that the chain with the most Proof-of-Work (PoW) is valid. As many
> > have pointed out before, and attacks like Segwit2x have shown, this is
> > not a safe assumption. What I propose below improves this assumption
> > -- invalid blocks will be rejected as long as there are enough honest
> > miners to create a block within a reasonable time frame. This still
> > doesn’t fully inoculate SPV clients against dishonest miners, but is a
> > clear improvement over regular SPV (and compatible with the privacy
> > improvements of BIP157[0]).
> >
> > The idea is that a fork is an indication of potential misbehavior --
> > its block header can serve as a PoW fraud proof. Conversely, the lack
> > of a fork is an indication that a block is valid. If a fork is created
> > from a block at height N, this means a subset of miners may disagree
> > on the validity of block N+1. If SPV clients download and verify this
> > block, they can judge for themselves whether or not the chain should
> > be rejected. Of course it could simply be a natural fork, in which
> > case we continue following the chain with the most PoW.
>
> I presume you mean a chain split?
>
> >
> > The way Bitcoin currently works, it is impossible to verify the
> > validity of block N+1 without knowing the UTXO set at block N, even if
> > you are willing to assume that block N (and everything before it) is
> > valid. This would change with the introduction of UTXO set
> > commitments, allowing block N+1 to be validated by verifying whether
> > its inputs are present in the UTXO set that was committed to in block
> > N. An open question is whether a similar result can be achieved
> > without a soft fork that commits to the UTXO set[0][1].
> >
> > If an invalid block is created and only 10% of the miners are honest,
> > on average it would take 100 minutes for a valid block to appear.
> > During this time, the SPV client will be following the invalid chain
> > and see roughly 9 confirmations before the chain gets rejected. It may
> > therefore be prudent to wait for a number of confirmations that
> > corresponds to the time it may take for the conservative percentage of
> > miners that you think may behave honestly to create a block (including
> > variance).
>
> I suppose a minority miner that wants to disrupt the network could simply create a *valid* block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
> If this minority miner has > 10% of network hashrate, then the rule of thumb above would, on average, give it the ability to disrupt the SPV-using network.
>
> >10% of network hashrate to disrupt the SPV-using nodes would be a rather low bar to disruption.
> Consider that SPV-using nodes would be disrupted, without this rule, only by >50% network hashrate.
>
> It is helpful to consider that every rule you impose is potentially a loophole by which a new attack is possible.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:04:45

- reply

📅 Original date posted:2017-08-11
📝 Original message:Dear All,
The Call for Proposals (CFP) for 'Scaling Bitcoin 2017: Stanford' is now
open.
Please see https://scalingbitcoin.org for details
*Important Dates*
Sept 25th - Deadline for submissions to the CFP
Oct 16th - Applicant acceptance notification
Hope to see you in California (Nov 4-5 2017)
Full CFP can be found at https://scalingbitcoin.org/event/stanford2017#cfp
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170811/da36bbbb/attachment.html>

2023-06-07 18:01:20

- reply

📅 Original date posted:2017-05-22
📝 Original message:My OP_CAT usecase only needs to glue together hash outputs, so two 32
Bytes inputs generating a 64 Byte output. However increasing this
would enable additional space savings. I would push for an OP_CAT
which can generate an output of no greater than 512 Bytes. Is there
are maximum byte vectors size for script?
The ideal instruction for this usecase be an instruction that pops N
vectors of the stack, concatenates them together and hashes them.
OP_CATHASH256(N) --> OP_HASH256(v1||v2||..||vN)
where || denotes concatenation. You could do this in a streaming
fashion so that memory usage would never exceed 32 Bytes regardless of
the size of the input vectors.
However I recognize that OP_CAT is more generally useful and it
already in scripts but just disabled.
On Mon, May 22, 2017 at 12:14 PM, Peter Todd <pete at petertodd.org> wrote:
> On Mon, May 22, 2017 at 10:41:40AM -0400, Ethan Heilman wrote:
>> >It'd help your case if you gave us some examples of such scripts being
>> used.
>>
>> I want OP_CAT so that I can securely and compactly verify many hashes and
>> hash preimages. This would shrink offchain Tumblebit transactions
>> significantly.
>>
>> For instance if I want a transaction TxA which checks that a transaction
>> TxB releases preimages x1,x2,...,x10 such that
>> y1=H(x1), y2=H(x2),...,y10=H(x10). Currently I just put y1,...y10 and check
>> that the preimahes hash correctly. With OP_CAT I would only have to store
>> one hash in TxA, yhash
>>
>> ytotal = H(OP_CAT(H(OP_CAT(y1, y2)),y3)...y10)
>>
>> TxA could then just hash all the preimages supplied by TxB and confirm they
>> hash to TxA. This would reduce the size of TxA from approx 10*32B to
>> 32+10*16B. I have a version which improves this further but it is more
>> complex.
>>
>> Most of the math OP codes aren't particularly helpful due to their 32bit
>> nature and their strange overflow behavior.
>
> Great! That's exactly the type of justifying use-case we need for a BIP.
>
> An OP_CAT will have to have limits on maximum output size; how big an output
> does your application need?
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org

2023-06-07 18:01:20

- reply

📅 Original date posted:2017-05-22
📝 Original message:>It'd help your case if you gave us some examples of such scripts being
used.
I want OP_CAT so that I can securely and compactly verify many hashes and
hash preimages. This would shrink offchain Tumblebit transactions
significantly.
For instance if I want a transaction TxA which checks that a transaction
TxB releases preimages x1,x2,...,x10 such that
y1=H(x1), y2=H(x2),...,y10=H(x10). Currently I just put y1,...y10 and check
that the preimahes hash correctly. With OP_CAT I would only have to store
one hash in TxA, yhash
ytotal = H(OP_CAT(H(OP_CAT(y1, y2)),y3)...y10)
TxA could then just hash all the preimages supplied by TxB and confirm they
hash to TxA. This would reduce the size of TxA from approx 10*32B to
32+10*16B. I have a version which improves this further but it is more
complex.
Most of the math OP codes aren't particularly helpful due to their 32bit
nature and their strange overflow behavior.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170522/7a13e539/attachment.html>

2023-06-07 17:56:46

- reply

📅 Original date posted:2017-02-25
📝 Original message:I strongly encourage Bitcoin to move from 80-bit collision resistance
(RIPEMD-160) to 128-bit collision resistance (SHA-256).
On Sat, Feb 25, 2017 at 5:14 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>
> On Feb 25, 2017 14:09, "Steve Davis via bitcoin-dev" <bitcoin-dev at lists.
> linuxfoundation.org> wrote:
>
> Hi Peter,
>
>
> I really, really don’t want to get into it but segwit has many aspects
> that are less appealing, not least of which being the amount of time it
> would take to reach the critical mass.
>
> Surely there's a number of alternative approaches which could be explored,
> even if only to make a fair assessment of a best response?
>
>
> Any alternative to move us away from RIPEMD160 would require:
> * A drafting of a softfork proposal, implementation, testing, review.
> * A new address format
> * Miners accepting the new consensus rules
> * Wallets adopting the new address format, both on the sender side and
> receiver side (which requires new signatures).
>
> I.e., exactly the same as segwit, for which most of these are already
> done. And it would still only apply to wallets adopting it.
>
> --
> Pieter
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170225/7fecc6c7/attachment.html>

2023-06-07 17:56:43

- reply

📅 Original date posted:2017-02-25
📝 Original message:>You have to not only produce a ripemd160 collision, you have to produce a
collision that is also a valid sha-256 hash - and that's much much much
more difficult.
I agree that merely finding a collision in RIPEMD-160 will be hard to use
in Bitcoin.
However finding a collision in RIPEMD-160(SHA-256(msg)) via bruteforce
(2^80 queries) is not particular more difficult than finding a collision in
RIPEMD-160 via brute force. Furthermore if you find a collision in
RIPEMD-160(SHA-256(msg)) you also get a valid SHA-256 hash for which you
know the preimage.
On Sat, Feb 25, 2017 at 1:19 PM, Alice Wonder via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> On 02/25/2017 08:10 AM, Ethan Heilman via bitcoin-dev wrote:
>
>> SHA1 is insecure because the SHA1 algorithm is insecure, not because
>>>
>> 160bits isn't enough.
>>
>> I would argue that 160-bits isn't enough for collision resistance.
>> Assuming RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random
>> oracle), collisions can be generated in 2^80 queries (actually detecting
>> these collisions requires some time-memory additional trade-offs). The
>> Bitcoin network at the current hash rate performs roughly SHA-256 ~2^78
>> queries a day or 2^80 queries every four days.
>>
>
> You have to not only produce a ripemd160 collision, you have to produce a
> collision that is also a valid sha-256 hash - and that's much much much
> more difficult.
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170225/11c54e30/attachment.html>

2023-06-07 17:56:41

- reply

📅 Original date posted:2017-02-25
📝 Original message:>SHA1 is insecure because the SHA1 algorithm is insecure, not because
160bits isn't enough.
I would argue that 160-bits isn't enough for collision resistance. Assuming
RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions
can be generated in 2^80 queries (actually detecting these collisions
requires some time-memory additional trade-offs). The Bitcoin network at
the current hash rate performs roughly SHA-256 ~2^78 queries a day or 2^80
queries every four days. Without any break in RIPEMD-160(SHA-256(msg)) the
US could build an ASIC datacenter and produce RIPEMD-160 collisions for a
fraction of its yearly cryptologic budget.
The impact of collisions in RIPEMD-160(SHA-256(msg)) according to "On
Bitcoin Security in the Presence of Broken Crypto Primitives"(
https://eprint.iacr.org/2016/167.pdf):
>Collisions are similar, though in this case both public keys are under the
adversary’s control, and again the adversary does not have access to the
private keys. In both scenarios, there is a question of nonrepudiation
external to the protocol itself: by presenting a second pre-image of a key
used to sign a transaction, a user/adversary can claim that his coins were
stolen.
How would such an event effect the price of Bitcoin when headlines are
"Bitcoin's Cryptography Broken"? How much money could someone make by
playing the market in this way?
For both reasons of credibility and good engineering (safety
margins) Bitcoin should strive to always use cryptography which is beyond
reproach.
On Sat, Feb 25, 2017 at 9:50 AM, Leandro Coutinho via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Google recommeds "migrate to safer cryptographic hashes such as SHA-256
> and SHA-3"
> It does not mention RIPEMD-160
>
> https://security.googleblog.com/2017/02/announcing-first-
> sha1-collision.html?m=1
>
>
> Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev" <bitcoin-dev at lists.
> linuxfoundation.org> escreveu:
>
>
> > On Feb 24, 2017, at 7:01 PM, Peter Todd <pete at petertodd.org> wrote:
> >
> > On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev
> wrote:
> >> If the 20 byte SHA1 is now considered insecure (with good reason), what
> about RIPEMD-160 which is the foundation of Bitcoin addresses?
> >
> > SHA1 is insecure because the SHA1 algorithm is insecure, not because
> 160bits isn't enough.
> >
> > AFAIK there aren't any known weaknesses in RIPEMD160,
>
> …so far. I wonder how long that vacation will last?
>
> > but it also hasn't been
> > as closely studied as more common hash algorithms.
>
> ...but we can be sure that it will be, since the dollar value held in
> existing utxos continues to increase...
>
> > That said, Bitcoin uses
> > RIPEMD160(SHA256(msg)), which may make creating collisions harder if an
> attack
> > is found than if it used RIPEMD160 alone.
>
> Does that offer any greater protection? That’s not so clear to me as the
> outputs (at least for p2pkh) only verify the public key against the final
> 20 byte hash. Specifically, in the first (notional) case the challenge
> would be to find a private key that has a public key that hashes to the
> final hash. In the second (realistic) case, you merely need to add the
> sha256 hash into the problem, which doesn’t seem to me to increase the
> difficulty by any significant amount?
>
>
> /s
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170225/99b5f0a3/attachment.html>

2023-06-07 17:54:59

- reply

📅 Original date posted:2016-12-15
📝 Original message:I assume this has been well discussed in at some point in the Bitcoin
community, so I apologize if I'm repeating old ideas.
Problem exploitable nodes:
It is plausible that people running these versions of bitcoind may not
be applying patches. Thus, these nodes may be vulnerable to known
exploits. I would hope none of these nodes are gateway nodes for
miners, web wallets or exchanges. How difficult would it be to crawl
the network to find vulnerable nodes and exploit them? What percentage
of the network is running vulnerable versions of bitcoind?
Problem eclipsable nodes:
Currently a bitcoind node disconnects from any node with a version
below MIN_PEER_PROTO_VERSION. Such nodes become be ripe for an eclipse
attack because they are partitioned from the newer nodes, especially
when they are "freshly obsolete". I have not examined how protocol
versioning works in detail so I could be missing something.
One option could be that after a grace period:
1. to still connect to obsolete nodes and even to transmit blockheaders,
2. but to stop sending the full-blocks and transactions to these
nodes, thereby alerting the operator that something is wrong and
causing them to upgrade.
It may make sense to create this as a rule, if your longest chain
consists of only blockheaders and no one will tell you the
transactions for over 1000 blocks you are obsolete, spit out an error
message and shutdown.
This would not address the issue of alt-coins which are forked from
old vulnerable versions of bitcoind, but that is probably out of
scope.
On Thu, Dec 15, 2016 at 1:48 PM, Jorge Timón via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
> On Thu, Dec 15, 2016 at 4:38 AM, Juan Garavaglia via bitcoin-dev
> <bitcoin-dev at lists.linuxfoundation.org> wrote:
>> Older node versions may generate issues because some upgrades will make
>> several of the nodes running older protocol versions obsolete and or
>> incompatible. There may be other hard to predict behaviors on older versions
>> of the client.
>
> Hard to predict or not, you can't force people to run newer software.
>
>> In order to avoid such wide fragmentation of "Bitcoin Core” node versions
>> and to help there be a more predictable protocol improvement process, I
>> consider it worth it to analyze introducing some planned obsolescence in
>> each new version. In the last year we had 4 new versions so if each version
>> is valid for about 1 year (52560 blocks) this may be a reasonable time frame
>> for node operators to upgrade. If a node does not upgrade it will stop
>> working instead of participating in the network with an outdated protocol
>> version.
>
> When you introduce anti-features like this in free software they can
> be trivially removed and they likely will.
>
>> These changes may also simplify the developer's jobs in some cases by
>> avoiding them having to deal with ancient versions of the client.
>
> There's a simpler solution for this which is what is being done now:
> stop maintaining and giving support for older versions.
> There's limited resources and developers are rarely interested in
> fixing bugs for very old versions. Users shouldn't expect things to be
> backported to old versions (if developers do it and there's enough
> testing, there's no reason not to do more releases of old versions, it
> is just rarely the case).
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 17:51:35

- reply

📅 Original date posted:2016-06-29
📝 Original message:Just to clarify in BIP-0151 when it says:
>It is important to include the cipher-type into the symmetric cipher key to avoid weak-cipher-attacks.
the cipher-type here refers to the ECDH negotiation parameters?
On Wed, Jun 29, 2016 at 2:58 AM, Pieter Wuille <pieter.wuille at gmail.com> wrote:
> On Jun 29, 2016 07:05, "Ethan Heilman via bitcoin-dev"
> <bitcoin-dev at lists.linuxfoundation.org> wrote:
>>
>> >It's also not clear to me why the HMAC, vs just
>> > SHA256(key|cipher-type|mesg). But that's probably just my crypto
>> > ignorance...
>>
>> SHA256(key|cipher-type|mesg) is an extremely insecure MAC because of
>> the length extension property of SHA256.
>
> This property does technically not apply here, as the output of the hash is
> kept secret, and the possible messages are constants (which are presumably
> chosen in such a way that one is never an extension of another).
>
> However, this is a good example of why you can't generically use a hash
> function in places where you want a MAC (aka "a hash with a shared secret").
> Furthermore, if you already have a hash function anyway, HMAC is very easy
> construct on top of it.
>
> --
> Pieter

2023-06-07 17:51:34

- reply

📅 Original date posted:2016-06-28
📝 Original message:>It's also not clear to me why the HMAC, vs just SHA256(key|cipher-type|mesg). But that's probably just my crypto ignorance...
SHA256(key|cipher-type|mesg) is an extremely insecure MAC because of
the length extension property of SHA256.
If I have a tag y = SHA256(key|cipher-type|mesg), I can without
knowing key or msg compute a value y' such that
y' = SHA256(key|cipher-type|mesg|any values I want).
Thus, an attacker can trivially forge a tag protected by
SHA256(key|cipher-type|mesg).
For more details see:
https://web.archive.org/web/20141029080820/http://vudang.com/2012/03/md5-length-extension-attack/
On Tue, Jun 28, 2016 at 9:00 PM, Rusty Russell via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
> Jonas Schnelli <dev at jonasschnelli.ch> writes:
>>> To quote:
>>>
>>>> HMAC_SHA512(key=ecdh_secret|cipher-type,msg="encryption key").
>>>>
>>>> K_1 must be the left 32bytes of the HMAC_SHA512 hash.
>>>> K_2 must be the right 32bytes of the HMAC_SHA512 hash.
>>>
>>> This seems a weak reason to introduce SHA512 to the mix. Can we just
>>> make:
>>>
>>> K_1 = HMAC_SHA256(key=ecdh_secret|cipher-type,msg="header encryption key")
>>> K_2 = HMAC_SHA256(key=ecdh_secret|cipher-type,msg="body encryption key")
>>
>> SHA512_HMAC is used by BIP32 [1] and I guess most clients will somehow
>> make use of bip32 features. I though a single SHA512_HMAC operation is
>> cheaper and simpler then two SHA256_HMAC.
>
> Good point; I would argue that mistake has already been made. But I was
> looking at appropriating your work for lightning inter-node comms, and
> adding another hash algo seemed unnecessarily painful.
>
>> AFAIK, sha256_hmac is also not used by the current p2p & consensus layer.
>> Bitcoin-Core uses it for HTTP RPC auth and Tor control.
>
> It's also not clear to me why the HMAC, vs just
> SHA256(key|cipher-type|mesg). But that's probably just my crypto
> ignorance...
>
> Thanks!
> Rusty.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 17:49:13

- reply

📅 Original date posted:2016-02-22
📝 Original message:"*Abstract: *Digital currencies like Bitcoin rely on cryptographic
primitives to operate. However, past experience shows that cryptographic
primitives do not last forever: increased computational power and advanced
cryptanalysis cause primitives to break frequently, and motivate the
development of new ones. It is therefore crucial for maintaining trust in a
crypto currency to anticipate such breakage.
We present the first systematic analysis of the effect of broken primitives
on Bitcoin. We identify the core cryptographic building blocks and analyze
the various ways in which they can break, and the subsequent effect on the
main Bitcoin security guarantees. Our analysis reveals a wide range of
possible effects depending on the primitive and type of breakage, ranging
from minor privacy violations to a complete breakdown of the currency.
Our results lead to several observations on, and suggestions for, the
Bitcoin migration plans in case of broken cryptographic primitives."
https://eprint.iacr.org/2016/167
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160222/f19be77c/attachment.html>

2023-06-07 17:47:58

- reply

📅 Original date posted:2016-01-19
📝 Original message:I believe libsecp256k1 just performs Elliptic Curve operations
required by Bitcoin. OpenSSL is used for all other crypto.
For instance the PRNG appears to be OpenSSL:
https://github.com/bitcoin/bitcoin/blob/master/src/random.h
On Mon, Jan 18, 2016 at 8:39 PM, Andrew C via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
> In the release notes for 0.12, it says that we have moved from using OpenSSL
> to libsecp256k1 for signature validation. So what else is it being used for
> that we need to keep it as a dependency?
>
> Thanks,
> Andrew
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

2023-06-07 17:47:41

- reply

📅 Original date posted:2016-01-07
📝 Original message:Based on current GH/s count of 775,464,121 Bitcoin tests 2^80 every 19 days.
log2(775464121*(1000*1000*1000*60*60*24*19)) = ~80.07
I don't fully understand the security model of segwit, so my analysis
will assume that any collision is bad.
>But it also requires O(2^80) storage, which is utterly infeasible
You don't store all 2^80 previous hashes, instead you just hash a seed
value 2^80 times, then look for a cycle.
seed = {0,1}^160
x = hash(seed)
for i in 2^80:
....x = hash(x)
x_final = x
y = hash(x_final)
for j in 2^80:
....if y == x_final:
........print "cycle len: "+j
........break
....y = hash(y)
If at any point x collides with a prior value of x it will form a
cycle. Thus y will also cycle and collide with x_final. j gives you
the cycle length, which allows you find the collision:
hash^(2^80-j)(seed) == hash^(j)(hash^(2^80-j)(seed)).
Worst case:
First loop costs 2**80, second loop costs 2**80=j, finding the
colliding value is 2**80. Total cost 2**80+2**80+2**80 = 2**81.5 and
requires storing less than a kilobyte.
This is a toy example, does not exploit parallelism, time memory trade
offs, can be easily made better, etc...
On Thu, Jan 7, 2016 at 2:02 PM, Gavin Andresen via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
> I'm hoisting this from some private feedback I sent on the segregated
> witness BIP:
>
> I said:
>
> "I'd also use RIPEMD160(SHA256()) as the hash function and save the 12
> bytes-- a successful preimage attack against that ain't gonna happen before
> we're all dead. I'm probably being dense, but I just don't see how a
> collision attack is relevant here."
>
> Pieter responded:
>
> "The problem case is where someone in a contract setup shows you a script,
> which you accept as being a payment to yourself. An attacker could use a
> collision attack to construct scripts with identical hashes, only one of
> which does have the property you want, and steal coins.
>
> So you really want collision security, and I don't think 80 bits is
> something we should encourage for that. Normal pubkey hashes don't have that
> problem, as they can't be constructed to pay to you."
>
> ... but I'm unconvinced:
>
> "But it is trivial for contract wallets to protect against collision
> attacks-- if you give me a script that is "gavin_pubkey CHECKSIG
> arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just
> ignore that arbitrary data" a wallet can just refuse. Even more likely, a
> contract wallet won't even recognize that as a pay-to-gavin transaction.
>
> I suppose it could be looking for some form of "gavin_pubkey
> somebody_else_pubkey CHECKMULTISIG ... with the attacker using
> somebody_else_pubkey to force the collision, but, again, trivial contract
> protocol tweaks ("send along a proof you have the private key corresponding
> to the public key" or "everybody pre-commits pubkeys they'll use at protocol
> start") would protect against that.
>
> Adding an extra 12 bytes to every segwit to prevent an attack that takes
> 2^80 computation and 2^80 storage, is unlikely to be a problem in practice,
> and is trivial to protect against is the wrong tradeoff to make."
>
> 20 bytes instead of 32 bytes is a savings of almost 40%, which is
> significant.
>
> The general question I'd like to raise on this list is:
>
> Should we be worried, today, about collision attacks against RIPEMD160 (our
> 160-bit hash)?
>
> Mounting a successful brute-force collision attack would require at least
> O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin
> POW has computed more SHA256 hashes than that). But it also requires O(2^80)
> storage, which is utterly infeasible (there is something on the order of
> 2^35 bytes of storage in the entire world). Even assuming doubling every
> single year (faster than Moore's Law), we're four decades away from an
> attacker with THE ENTIRE WORLD's storage capacity being able to mount a
> collision attack.
>
>
> References:
>
> https://en.wikipedia.org/wiki/Collision_attack
>
> https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/
>
>
> --
> --
> Gavin Andresen
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

2023-06-07 17:47:39

- reply

📅 Original date posted:2016-01-07
📝 Original message:>Ethan: your algorithm will find two arbitrary values that collide. That isn't useful as an attack in the context we're talking about here (both of those values will be useless as coin destinations with overwhelming probability).
I'm not sure exactly the properties you want here and determining
these properties is not an easy task, but the case is far worse than
just two random values. For instance: (a). with a small modification
my algorithm can also find collisions containing targeted substrings,
(b). length extension attacks are possible with RIPEMD160.
(a). targeted cycles:
target1 = "str to prepend"
target2 = "str to end with"
seed = {0,1}^160
x = hash(seed)
for i in 2^80:
....x = hash(target1||x||target2)
x_final = x
y = hash(tartget1||x_final||target2)
for j in 2^80:
....if y == x_final:
........print "cycle len: "+j
........break
....y = hash(target1||y||target2)
If a collision is found, the two colliding inputs must both start with
"str to prepend" and end with the phrase "str to end with". As before
this only requires 2^81.5 computations and no real memory. For an
additional 2**80 an adversary has an good change of finding two
different targeted substrings which collide. Consider the case where
the attacker mixes the targeted strings with the hash output:
hash("my name is=0x329482039483204324423"+x[1]+", my favorite number
is="+x) where x[1] is the first bit of x.
(b). length extension attacks
Even if all the adversary can do is create two random values that
collide, you can append substrings to the input and get collisions.
Once you find two random values hash(x) = hash(y), you could use a
length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).
Now the bitcoin wiki says:
"The padding scheme is identical to MD4 using Merkle–Damgård
strengthening to prevent length extension attacks."[1]
Which is confusing to me because:
1. MD4 is vulnerable to length extension attacks
2. Merkle–Damgård strengthening does not protect against length
extension: "Indeed, we already pointed out that none of the 64
variants above can withstand the 'extension' attack on the MAC
application, even with the Merkle-Damgard strengthening" [2]
3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
using a non-standard version of RIPEMD-160.
RIPEMD160(SHA256()) does not protect against length extension attacks
on SHA256, but should protect RIPEMD-160 against length extension
attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
should be very careful here. Research has been done that shows that
cascading the same hash function twice is weaker than using HMAC[3]. I
can't find results on cascading RIPEMD160(SHA256()).
RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
should not rest on the notion that an attacker requires 2**80 memory,
many targeted collision attacks can work without much memory.
[1]: https://en.bitcoin.it/wiki/RIPEMD-160
[2]: "Merkle-Damgard Revisited: How to Construct a Hash Function"
https://www.cs.nyu.edu/~puniya/papers/merkle.pdf
[3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf
On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
> Maybe I'm asking this question on the wrong mailing list:
>
> Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
> before SHA256?
> And do you have some reason to think that they will be so broken that the
> nested hash construction RIPEMD160(SHA256()) will be vulnerable?
>
> Adam: re: "where to stop" : I'm suggesting we stop exactly at the current
> status quo, where we use RIPEMD160 for P2SH and P2PKH.
>
> Ethan: your algorithm will find two arbitrary values that collide. That
> isn't useful as an attack in the context we're talking about here (both of
> those values will be useless as coin destinations with overwhelming
> probability).
>
> Dave: you described a first preimage attack, which is 2**160 cpu time and no
> storage.
>
>
> --
> --
> Gavin Andresen
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

2023-06-07 17:31:33

- reply

2023-06-07 17:31:30

- reply

2023-06-07 15:36:22

- reply

📅 Original date posted:2015-06-02
📝 Original message:I second this, I don't have time to read the large number of emails
generated every day from the block size debate. A summary of the various
positions and arguments would be extremely helpful.
On Mon, Jun 1, 2015 at 11:02 PM, gabe appleton <gappleto97 at gmail.com> wrote:
> Also, can we try to get a wiki page for the debate? That way we could
> condense the information as much as possible. I'll be willing to assist if
> the page gets approval.
> On Jun 1, 2015 6:41 PM, "Mats Henricson" <mats at henricson.se> wrote:
>
>> Hi!
>>
>> My fingers have been itching many times now, this debate
>> drives me nuts.
>>
>> I just wish all posters could follow two simple principles:
>>
>> 1. Read up. Yes. All of what has been written. Yes, it will
>> take many hours. But if you're rehashing what other
>> smarter people have said over and over before, you're
>> wasting hundreds of peoples time. Please don't.
>>
>> 2. Be helpful. Suggest alternatives. Just cristizising is
>> just destructive. If you want no change, then say so.
>>
>> Mats
>>
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development at lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150601/223152c1/attachment.html>

2023-06-07 15:32:12

- reply

📅 Original date posted:2015-03-23
📝 Original message:Hi All,
There has been much discussion lately on the dev list about
misbehaving peers and attacks on the P2P network. We'd like to share
our research on partitioning Bitcoind nodes from the rest of the
network.
Eclipse Attacks on Bitcoin’s Peer-to-Peer Network
Abstract: We present eclipse attacks on bitcoin's peer-to-peer
network. Our attack allows an adversary controlling a sufficient
number of IP addresses to monopolize all connections to and from a
victim bitcoin node. The attacker can then exploit the victim for
attacks on bitcoin's mining and consensus system, including
N-confirmation double spending, selfish mining, and adversarial forks
in the blockchain. We take a detailed look at bitcoin’s peer-to-peer
network, and quantify the resources involved in our attack via
probabilistic analysis, Monte Carlo simulations, measurements and
experiments with live bitcoin nodes. Finally, we present
countermeasures, inspired by botnet architectures, that are designed
to raise the bar for eclipse attacks while preserving the openness and
decentralization of bitcoin’s current network architecture.
Full paper available here:
http://cs-people.bu.edu/heilman/eclipse/
Thanks,
Ethan

2023-06-07 15:30:38

- reply

📅 Original date posted:2015-02-15
📝 Original message:Hi All,
I am currently running some tests on the peering system in Bitcoind for a
research paper. We hope to develop improvements which we can share with the
community. A wide diversity of real peers.dat files would be very helpful.
If you are willing, please email me your peers.dat.
Thanks,
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150215/eec6b08a/attachment.html>

2023-06-07 15:22:13

- reply

📅 Original date posted:2014-06-03
📝 Original message:An attack on the mining difficulty algorithm does not imply violation of
the typical security properties of a cryptographic hash function*.
Assume someone discovers a method which makes it far easier to discover new
blocks, this method: may or may not be implementable by the current SHA256
ASIC hardware.
1. If it is usable by the mining hardware, then there will be brief period
of overproduction and then difficulty will adjust. If the attack is so bad
that difficulty can't scale and we run out of a leading zero's, then the
SHA256 collision resistance is broken and we have bigger problems. Under
this scenario, everyone would see the need to immediately switch to new
hardware as people could create cycles and irreconcilable forks in the
block chain
2. If the attack is not usable by the mining hardware, then the miners will
need to switch to new ASICs anyways and the hash function can be changed
without resistance.
But lets ignore all that and say, for some unspecified reason, the bitcoin
community wants to switch hash functions and has some lead time to do so.
One could require that miners find two blocks, one computed using SHA256
and one computed using the new hash function. We could then slowly shift
the difficulty from SHA256 to the new hash function. This would allow
miners a semi-predicable roadmap to switch their infrastructure away from
SHA256.
* It would be a distinguisher which would be bad, but collision resistance
could be merely weakened.
On Tue, Jun 3, 2014 at 12:52 AM, Luke Dashjr <luke at dashjr.org> wrote:
> On Tuesday, June 03, 2014 4:29:55 AM xor wrote:
> > Hi,
> >
> > I thought a lot about the worst case scenario of SHA256d being broken in
> a
> > way which could be abused to
> > A) reduce the work of mining a block by some significant amount
> > B) reduce the work of mining a block to zero, i.e. allow instant mining.
>
> C) fabricate past blocks entirely.
>
> If SHA256d is broken, Bitcoin as it is fails entirely.
>
> Luke
>
>
> ------------------------------------------------------------------------------
> Learn Graph Databases - Download FREE O'Reilly Book
> "Graph Databases" is the definitive new guide to graph databases and their
> applications. Written by three acclaimed leaders in the field,
> this first edition is now available. Download your free book today!
> http://p.sf.net/sfu/NeoTech
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20140603/5a51bf30/attachment.html>