Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Ethan Heilman via bitcoin-dev]

If there is sufficient interest in enabling OP_CAT on Bitcoin and
there is a strong desire in the community for using OP_SUCCESS126
rather than OP_SUCCESS80 then I'd be happy to switch to OP_SUCCESS126.
I don't have any particular affinity for OP_SUCCESS80.

Is there anyone who objects to using OP_SUCCESS126 rather than OP_SUCCESS80?

On Tue, Oct 24, 2023 at 4:12 PM Steven Roose via bitcoin-dev
 wrote:
>
> I agree that there is no reason not to use OP_SUCCESS126, i.e. the original 
> OP_CAT opcode 0x7e. In many codebases, for example in Core, there might be 
> two OP_CAT constants than which might be confusing.
>
> On 10/22/23 09:58, vjudeu via bitcoin-dev wrote:
>
> > This opcode would be activated via a soft fork by redefining the opcode 
> > OP_SUCCESS80.
>
> Why OP_SUCCESS80, and not OP_SUCCESS126? When there is some existing opcode, 
> it should be reused. And if OP_RESERVED will ever be re-enabled, I think it 
> should behave in the same way, as in pre-Taproot, so it should "Mark 
> transaction as invalid unless occuring in an unexecuted OP_IF branch". Which 
> means, " OP_VERIFY" should be equivalent to " OP_NOTIF 
> OP_RESERVED OP_ENDIF".
>
>
>
> On 2023-10-21 07:09:13 user Ethan Heilman via bitcoin-dev 
>  wrote:
>
> Hi everyone,
>
> We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode.
> https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki
>
> OP_CAT was available in early versions of Bitcoin. It was disabled as
> it allowed the construction of a script whose evaluation could create
> stack elements exponential in the size of the script. This is no
> longer an issue in the current age as tapscript enforces a maximum
> stack element size of 520 Bytes.
>
> Thanks,
> Ethan
>
> ==Abstract==
>
> This BIP defines OP_CAT a new tapscript opcode which allows the
> concatenation of two values on the stack. This opcode would be
> activated via a soft fork by redefining the opcode OP_SUCCESS80.
>
> When evaluated the OP_CAT instruction:
> # Pops the top two values off the stack,
> # concatenate the popped values together,
> # and then pushes the concatenated value on the top of the stack.
>
> OP_CAT fails if there are less than two values on the stack or if a
> concatenated value would have a combined size of greater than the
> maximum script element size of 520 Bytes.
>
> ==Motivation==
> Bitcoin tapscript lacks a general purpose way of combining objects on
> the stack restricting the expressiveness and power of tapscript. For
> instance this prevents among many other things the ability to
> construct and evaluate merkle trees and other hashed data structures
> in tapscript. OP_CAT by adding a general purpose way to concatenate
> stack values would overcome this limitation and greatly increase the
> functionality of tapscript.
>
> OP_CAT aims to expand the toolbox of the tapscript developer with a
> simple, modular and useful opcode in the spirit of Unix[1]. To
> demonstrate the usefulness of OP_CAT below we provide a non-exhaustive
> list of some usecases that OP_CAT would enable:
>
> * Tree Signatures provide a multisignature script whose size can be
> logarithmic in the number of public keys and can encode spend
> conditions beyond n-of-m. For instance a transaction less than 1KB in
> size could support tree signatures with a thousand public keys. This
> also enables generalized logical spend conditions. [2]
> * Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport
> signatures merely requires the ability to hash and concatenate values
> on the stack. [3]
> * Non-equivocation contracts [4] in tapscript provide a mechanism to
> punish equivocation/double spending in Bitcoin payment channels.
> OP_CAT enables this by enforcing rules on the spending transaction's
> nonce. The capability is a useful building block for payment channels
> and other Bitcoin protocols.
> * Vaults [5] which are a specialized covenant that allows a user to
> block a malicious party who has compromised the user's secret key from
> stealing the funds in that output. As shown in A. Poelstra, "CAT
> and Schnorr Tricks II", 2021,
> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html
> OP_CAT is sufficent to build vaults in Bitcoin.
> * Replicating CheckSigFromStack  A. Poelstra, "CAT and Schnorr
> Tricks I", 2021,
> https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298
>  which would allow the creation of simple covenants and other
> advanced contracts without having to presign spending transactions,
> possibly reducing complexity and the amount of data that needs to be
> stored. Originally shown to work with Schnorr signatures, thi

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Ethan Heilman via bitcoin-dev]

Hi Greg,

I didn't mean to imply this limit is a unique feature of tapescript, but
rather that:OP_CAT is a tapscript opcode and that tapscript enforces a 520
byte element size thus we don't have to worry about OP_CAT creating very
large stack elements.

Thanks for pointing this out, I didn't realize that this limit was added in
the same commit that removed OP_CAT. I thought it was more recent than
that. Reading through that commit it also appears that it also reduced the
size limit on inputs to arithmetic operations (nMaxNumSize) from 2064-bits
to 32-bits. I had always assumed it was 32-bits from the beginning. It
would have been wild to have math opcodes that support 2064-bit inputs and
outputs.

Thanks,
Ethan


On Sat, Oct 21, 2023 at 12:10 PM Greg Sanders  wrote:

> > This is no
> longer an issue in the current age as tapscript enforces a maximum
> stack element size of 520 Bytes.
>
> I don't think there's a new limit related to tapscript? In the very
> beginning there was no limit, but a 5k limit was put into place, then 520
> the same commit that OP_CAT was
> disabled: 4bd188c4383d6e614e18f79dc337fbabe8464c82
>
> On Sat, Oct 21, 2023 at 1:09 AM Ethan Heilman via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hi everyone,
>>
>> We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode.
>> https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki
>>
>> OP_CAT was available in early versions of Bitcoin. It was disabled as
>> it allowed the construction of a script whose evaluation could create
>> stack elements exponential in the size of the script. This is no
>> longer an issue in the current age as tapscript enforces a maximum
>> stack element size of 520 Bytes.
>>
>> Thanks,
>> Ethan
>>
>> ==Abstract==
>>
>> This BIP defines OP_CAT a new tapscript opcode which allows the
>> concatenation of two values on the stack. This opcode would be
>> activated via a soft fork by redefining the opcode OP_SUCCESS80.
>>
>> When evaluated the OP_CAT instruction:
>> # Pops the top two values off the stack,
>> # concatenate the popped values together,
>> # and then pushes the concatenated value on the top of the stack.
>>
>> OP_CAT fails if there are less than two values on the stack or if a
>> concatenated value would have a combined size of greater than the
>> maximum script element size of 520 Bytes.
>>
>> ==Motivation==
>> Bitcoin tapscript lacks a general purpose way of combining objects on
>> the stack restricting the expressiveness and power of tapscript. For
>> instance this prevents among many other things the ability to
>> construct and evaluate merkle trees and other hashed data structures
>> in tapscript. OP_CAT by adding a general purpose way to concatenate
>> stack values would overcome this limitation and greatly increase the
>> functionality of tapscript.
>>
>> OP_CAT aims to expand the toolbox of the tapscript developer with a
>> simple, modular and useful opcode in the spirit of Unix[1]. To
>> demonstrate the usefulness of OP_CAT below we provide a non-exhaustive
>> list of some usecases that OP_CAT would enable:
>>
>> * Tree Signatures provide a multisignature script whose size can be
>> logarithmic in the number of public keys and can encode spend
>> conditions beyond n-of-m. For instance a transaction less than 1KB in
>> size could support tree signatures with a thousand public keys. This
>> also enables generalized logical spend conditions. [2]
>> * Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport
>> signatures merely requires the ability to hash and concatenate values
>> on the stack. [3]
>> * Non-equivocation contracts [4] in tapscript provide a mechanism to
>> punish equivocation/double spending in Bitcoin payment channels.
>> OP_CAT enables this by enforcing rules on the spending transaction's
>> nonce. The capability is a useful building block for payment channels
>> and other Bitcoin protocols.
>> * Vaults [5] which are a specialized covenant that allows a user to
>> block a malicious party who has compromised the user's secret key from
>> stealing the funds in that output. As shown in A. Poelstra, "CAT
>> and Schnorr Tricks II", 2021,
>> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html
>> 
>> OP_CAT is sufficent to build vaults in Bitcoin.
>> * Replicating CheckSigFromStack  A. Poelstra, "CAT and Schnorr
>> Tricks I", 2021,
>> https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298
>>  which would allow the creation of simple covenants a

[bitcoin-dev] Proposed BIP for OP_CAT

[Ethan Heilman via bitcoin-dev]

Hi everyone,

We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode.
https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki

OP_CAT was available in early versions of Bitcoin. It was disabled as
it allowed the construction of a script whose evaluation could create
stack elements exponential in the size of the script. This is no
longer an issue in the current age as tapscript enforces a maximum
stack element size of 520 Bytes.

Thanks,
Ethan

==Abstract==

This BIP defines OP_CAT a new tapscript opcode which allows the
concatenation of two values on the stack. This opcode would be
activated via a soft fork by redefining the opcode OP_SUCCESS80.

When evaluated the OP_CAT instruction:
# Pops the top two values off the stack,
# concatenate the popped values together,
# and then pushes the concatenated value on the top of the stack.

OP_CAT fails if there are less than two values on the stack or if a
concatenated value would have a combined size of greater than the
maximum script element size of 520 Bytes.

==Motivation==
Bitcoin tapscript lacks a general purpose way of combining objects on
the stack restricting the expressiveness and power of tapscript. For
instance this prevents among many other things the ability to
construct and evaluate merkle trees and other hashed data structures
in tapscript. OP_CAT by adding a general purpose way to concatenate
stack values would overcome this limitation and greatly increase the
functionality of tapscript.

OP_CAT aims to expand the toolbox of the tapscript developer with a
simple, modular and useful opcode in the spirit of Unix[1]. To
demonstrate the usefulness of OP_CAT below we provide a non-exhaustive
list of some usecases that OP_CAT would enable:

* Tree Signatures provide a multisignature script whose size can be
logarithmic in the number of public keys and can encode spend
conditions beyond n-of-m. For instance a transaction less than 1KB in
size could support tree signatures with a thousand public keys. This
also enables generalized logical spend conditions. [2]
* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport
signatures merely requires the ability to hash and concatenate values
on the stack. [3]
* Non-equivocation contracts [4] in tapscript provide a mechanism to
punish equivocation/double spending in Bitcoin payment channels.
OP_CAT enables this by enforcing rules on the spending transaction's
nonce. The capability is a useful building block for payment channels
and other Bitcoin protocols.
* Vaults [5] which are a specialized covenant that allows a user to
block a malicious party who has compromised the user's secret key from
stealing the funds in that output. As shown in A. Poelstra, "CAT
and Schnorr Tricks II", 2021,
https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html
OP_CAT is sufficent to build vaults in Bitcoin.
* Replicating CheckSigFromStack  A. Poelstra, "CAT and Schnorr
Tricks I", 2021,
https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298
 which would allow the creation of simple covenants and other
advanced contracts without having to presign spending transactions,
possibly reducing complexity and the amount of data that needs to be
stored. Originally shown to work with Schnorr signatures, this result
has been extended to ECDSA signatures. [6]

The opcode OP_CAT was available in early versions of Bitcoin. However
OP_CAT was removed because it enabled the construction of a script for
which an evaluation could have memory usage exponential in the size of
the script.
For instance a script which pushed an 1 Byte value on the stack then
repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack
value whose size was greater than 1 Terabyte. This is no longer an
issue because tapscript enforces a maximum stack element size of 520
Bytes.

==Specification==

Implementation

  if (stack.size() < 2)
return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
  valtype vch1 = stacktop(-2);
  valtype vch2 = stacktop(-1);

  if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
  return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);

  valtype vch3;
  vch3.reserve(vch1.size() + vch2.size());
  vch3.insert(vch3.end(), vch1.begin(), vch1.end());
  vch3.insert(vch3.end(), vch2.begin(), vch2.end());

  popstack(stack);
  popstack(stack);
  stack.push_back(vch3);


The value of MAX_SCRIPT_ELEMENT_SIZE is 520 Bytes

== Reference Implementation ==
[Elements](https://github.com/ElementsProject/elements/blob/master/src/script/interpreter.cpp#L1043)

==References==

[1]: R. Pike and B. Kernighan, "Program design in the UNIX
environment", 1983,
https://harmful.cat-v.org/cat-v/unix_prog_design.pdf
[2]: P. Wuille, "Multisig on steroids using tree signatures", 2015,
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html
[3]: J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was
CheckSigFromStack for Arithmetic Values]", 2021,

Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[Ethan Heilman via bitcoin-dev]

>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  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@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
> > > > 

Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

[Ethan Heilman via bitcoin-dev]

>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
 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  EQUAL IF DROP <2**i> ADD ELSE 
> >  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
> >
> >  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  EQUAL  IF DROP  ELSE <3**i> SWAP DUP 
> >  EQUAL IF DROP SUB ELSE  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 

Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.

[Ethan Heilman via bitcoin-dev]

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
 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.0001 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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Ethan Heilman via bitcoin-dev]

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  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@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:
> > >
> > >   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 

[bitcoin-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Ethan Heilman via bitcoin-dev]

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
 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:
>
>   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:
>
>  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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[Ethan Heilman via bitcoin-dev]

>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  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-...@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
> ___
> Lightning-dev mailing list
> 

Re: [bitcoin-dev] Add a moving checkpoint to the Bitcoin protocol

[Ethan Heilman via bitcoin-dev]

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@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 [] 
> *Sent:* Wednesday, July 31, 2019 16:40
> *To:* Alistair Mann ; Bitcoin Protocol Discussion <
> bitcoin-dev@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 
> *Sent:* Wednesday, July 31, 2019 15:59
> *To:* Kenshiro [] ; Bitcoin Protocol Discussion <
> bitcoin-dev@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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs

[Ethan Heilman via bitcoin-dev]

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  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  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 zmnsc...@protonmail.com wrote:
> >
> > > Good morning Ethan,
> > > Sent with ProtonMail Secure Email.
> > > ‐‐‐ Original Message ‐‐‐
> > > On Friday, April 19, 2019 4:12 AM, Ethan Heilman eth...@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
> > > > 

Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs

[Ethan Heilman via bitcoin-dev]

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  wrote:
>
> Good morning Ethan,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On Friday, April 19, 2019 4:12 AM, Ethan Heilman  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.
> >
> 

Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs

[Ethan Heilman via bitcoin-dev]

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
 wrote:
>
> Good morning Ruben,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On Thursday, April 18, 2019 9:44 PM, Ruben Somsen via bitcoin-dev 
>  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] ScalingBitcoin 2017: Stanford - Call For Proposals Now Open

[Ethan Heilman via bitcoin-dev]

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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] A proposal to reintroduce the disabled script opcodes

[Ethan Heilman via bitcoin-dev]

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  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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] A proposal to reintroduce the disabled script opcodes

[Ethan Heilman via bitcoin-dev]

>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.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Ethan Heilman via bitcoin-dev]

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@lists.linuxfoundation.org> wrote:

>
>
> On Feb 25, 2017 14:09, "Steve Davis via bitcoin-dev"  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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Ethan Heilman via bitcoin-dev]

>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@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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by third-parties, not just repo maintainers

[Ethan Heilman via bitcoin-dev]

>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@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"  linuxfoundation.org> escreveu:
>
>
> > On Feb 24, 2017, at 7:01 PM, Peter Todd  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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Planned Obsolescence

[Ethan Heilman via bitcoin-dev]

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
 wrote:
> On Thu, Dec 15, 2016 at 4:38 AM, Juan Garavaglia via bitcoin-dev
>  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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP 151 use of HMAC_SHA512

[Ethan Heilman via bitcoin-dev]

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.wui...@gmail.com> wrote:
> On Jun 29, 2016 07:05, "Ethan Heilman via bitcoin-dev"
> <bitcoin-dev@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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP 151 use of HMAC_SHA512

[Ethan Heilman via bitcoin-dev]

>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
 wrote:
> Jonas Schnelli  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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] New paper: On Bitcoin Security in the Presence of Broken Crypto Primitives

[Ethan Heilman via bitcoin-dev]

"*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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] What is OpenSSL still used for?

[Ethan Heilman via bitcoin-dev]

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
 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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

[Ethan Heilman via bitcoin-dev]

>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
 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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

[Ethan Heilman via bitcoin-dev]

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
 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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev