Re: [bitcoin-dev] Ordinals BIP PR

[Tim Ruffing via bitcoin-dev]

On Mon, 2023-10-23 at 15:35 +, Peter Todd via bitcoin-dev wrote:
> Thus
> we should limit BIP assignment to the minimum possible: _extremely_
> widespread
> standards used by the _entire_ Bitcoin community, for the core
> mission of
> Bitcoin.

BIPs are Bitcoin Improvement *Proposals*. What you suggest would imply
that someone needs to evaluate them even before they become proposals.
And this raises plenty of notoriously hard to answers questions:
 * Who is in charge?
 * How to predict if a proposal will be a widespread standard?
 * What is the core mission of Bitcoin?
 * How to measure if something is for the core mission?
 * Who and what is the _entire_ Bitcoin community?

Best,
Tim
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Refreshed BIP324

[Tim Ruffing via bitcoin-dev]

Hello,

We'd like to announce two recent updates to BIP324 ("Version 2 P2P
Encrypted Transport Protocol"). Some of these changes affect semantics
and some are backwards-incompatible.

While we are not aware of any implementations of BIP324 except the one
in Bitcoin Core (see https://github.com/bitcoin/bitcoin/issues/27634 ),
the purpose of the email is to inform anyone involved in other
implementation efforts. At this point, we don't expect any further
backwards-incompatible changes.

https://github.com/bitcoin/bips/pull/1496 did multiple small changes:
 * Incoming v1 connections are now detected based on first 16 bytes
   they sent (instead of 12), which improves accuracy. If the incoming
   v1 connection appears to come from a wrong network (due to non-
   matching "network magic" bytes), responders may now drop the
   connection immediately.
 * The BIP330 message types have been dropped from the short encodings
   list in the BIP. It feels like it shouldn't be BIP324's goal to
   predict future protocol improvements.

https://github.com/bitcoin/bips/pull/1498 introduced a backwards-
incompatible change:
 * The garbage authentication packet is removed by merging it with the
   version packet. This simplifies the protocol implementation by
   consolidating the states and removing the special case of "ignoring
   the ignore bit." The freedom to choose the contents of the garbage
   authentication packet has also been removed, leading to easier
   testing and implementation.

We also did some editorial improvements. The most recent revision of
the BIP324 can be found at: 

https://github.com/bitcoin/bips/blob/master/bip-0324.mediawiki

Best,
Dhruv, Tim, and Pieter

On Sat, 2022-10-08 at 12:59 +, Dhruv M wrote:
> Hi all,
> 
> We have refreshed the proposal for BIP324, a new bitcoin P2P protocol
> featuring opportunistic encryption, a mild bandwidth reduction, and
> the
> ability
> to negotiate upgrades before exchanging application messages. We'd
> like
> to invite community members to review the BIP[1] and the related
> Bitcoin
> Core
> code[2].
> 
> The proposal has a rich history[3]. The big changes since the last
> public
> appearance[4] are:
> 
> * Elligator-swift encoding for the pubkeys in the ECDH exchange to
> obtain a pseudorandom bytestream
> * x-only ECDH secret derivation
> * Transport versioning that allows for upgradability
> * Trafic shapability using decoy packets and a shapable handshake
> * Complete rewrite of the BIP text
> 
> We look forward to your review and comments.
> 
> -Dhruv, Tim and Pieter
> 
> 
> [1] BIP Pull Request: https://github.com/bitcoin/bips/pull/1378
> 
> [2] All historical and current PRs:
> https://bip324.com/sections/code-review/
> 
> [3] https://bip324.com/sections/bip-review/
> 
> [4] https://gist.github.com/dhruv/5b1275751bc98f3b64bcafce7876b489
> 
> 
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] libsecp256k1 0.3.2 released

[Tim Ruffing via bitcoin-dev]

Hello,

We'd like to announce the release of version 0.3.2 of libsecp256k1:

  https://github.com/bitcoin-core/secp256k1/releases/tag/v0.3.2

This is a bugfix release after 0.3.1. The impetus for this release is
the discovery that GCC 13 became smart enough to optimize out a
specific timing side-channel protection mechanism in the ECDH code that
could leave applications vulnerable to a side-channel attack. This has
been fixed in 0.3.2 [1].

For the full changelog, see
  https://github.com/bitcoin-core/secp256k1/blob/master/CHANGELOG.md

We strongly recommend any users of the library to upgrade if their code
may end up being compiled with GCC >=13. Bitcoin Core is not affected
because it does not use libsecp256k1's ECDH module.

Note: The underlying side-channel issue is very similar to the issue
that lead to the previous 0.3.1 release. Unfortunately, there is no
generic way to prevent compilers from "optimizing" code by adding
secret-dependent branches (which are undesired in cryptographic
applications), and it is hard to predict what optimizations future
compiler versions will add. There's ongoing work [2] to test on
unreleased development snapshots of GCC and Clang, which would make it
possible to catch similar cases earlier in the future.

[1]: https://github.com/bitcoin-core/secp256k1/pull/1303
[2]: https://github.com/bitcoin-core/secp256k1/pull/1313

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Tim Ruffing via bitcoin-dev]

Hi aj,

I think there's another workaround for the x-only issue with
TAPLEAF_UPDATE_VERIFY.

So the opcode will need a function f that ensures that the new internal
key f(P'), where P' = P + X, has even y. You describe what happens for
the canonical choice of
f(P') = if has_even_y(P') then P' else -P'.

This leads to issues because negation turns around the signs of A and B
if say P' = A + B. Or more generally, negation is multiplicative
tweaking with a tweak -1, and that changes the coefficients of A und B.

But what if we use additive tweaking, which won't change the
coefficients? For example, you could try adding the generator until you
hit an even point, i.e., 
f(P') = if has_even_y(P') then P' else f(P' + G).

Then you may get a chain like
 * Pabc = A + B + C
 * Pab  = A + B      + 2G
* Pa = A + 2G + 1G = A + 3G

Pool members will simply need to track the accumulated tweak t and take
the tweak into account when signing. For example, A and B would sign
with t = 2 and A alone would sign with t = 3. 

This choice of f will succeed after 1 addition on average. (I don't
know if this can be proven but even if not, experiments show that it's
true and that's good enough.) So the actual running time is
probabilistic. I don't think that's an issue but if it is an issue,
other choices of f are possible, e.g., let the spender provide the
tweak t explicitly and set
f(P',t) = if 0 <= t < 128 and has_even_y(P'+tG) then P'+tG else fail.

This workaround is not exactly elegant either but it may be better than
the other suggestions.

Best,
Tim

On Thu, 2021-09-09 at 16:53 +1000, Anthony Towns via bitcoin-dev wrote:
> Moving on to the pooled scheme and actually updating the internal
> pubkey
> is, unfortunately, where things start to come apart. In particular,
> since taproot uses 32-byte x-only pubkeys (with implicit even-y) for
> the
> scriptPubKey and the internal public key, we have to worry about what
> happens if, eg, A,B,C and A+B+C all have even-more elegy, but
> (A+B)=(A+B+C)-C does
> not have even-y. In that case allowing C to remove herself from the
> pool,
> might result in switching from the scriptPubKey Qabc to the
> scriptPubKey
> Qab as follows:
> 
>  Qabc = (A+B+C) + H(A+B+C, (Sa, (Sb, Sc)))*G
>  Qab = -(A+B) + H( -(A+B), (Sa, Sb)*G
> 
> That's fine so far, but what happens if B then removes himself from
> the
> pool? You take the internal public key, which turns out to be -(A+B)
> since (A+B) did not have even y, and then subtract B, but that gives
> you
> -A-2B instead of just A. So B obtains his funds, but B's signature
> hasn't
> been cancelled out from the internal public key, so is still required
> in order to do key path spends, which is definitely not what we want.
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Sum of the keys attack on taproot

[Tim Ruffing via bitcoin-dev]

On Sat, 2021-05-15 at 12:21 +0200, vjudeu via bitcoin-dev wrote:


>  All that is needed is producing a signature matching the sum of the
> public keys used in taproot, which is "(a+b-a)*G", 

This is simply not true.

Taproot does not enable this, or any other form of "cross-input
aggregation", i.e., spending multiple UTXOs with a single signature. 


Tim

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Tim Ruffing via bitcoin-dev]

On Mon, 2021-03-22 at 10:24 -0400, Erik Aronesty via bitcoin-dev wrote:
> 
> Does anyone think it would it be useful to write up a more official,
> and even partly functional plan for Bitcoin to use zero-knowledge
> proofs to transition to quantum resistance?

Yes, for sure. This is certainly something that the community should
discuss. Looking into this problem is also on my (too long) list of
research problems.

I think IF we arrive at the conclusion that this is a good idea (which
is possible but not at all clear to me at this point), then one of the
questions is whether it's desirable to use something more efficient
than a zero-knowledge proof, at the potential cost of committing to a
real public key of a simple post-quantum signature scheme. This could
for example be a hash-based one-time signature scheme (but something
more efficient than the often mentioned Lamport signatures, e.g.,
Winternitz or W-OTS+ signatures).


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] An alternative to BIP 32?

[Tim Ruffing via bitcoin-dev]

On Sat, 2021-03-20 at 21:25 +0100, vjudeu via bitcoin-dev wrote:
> So, things have to be complicated to be secure?

Not at all. But we first need to spend some thoughts on what "secure"
means before we can tell if something is secure.

>  By definition, using some private key, calculating some public key
> from it and incrementing that key is secure (it is definitely no
> worse than address reuse). 

If secure means that it does not hurt the unforgeability of ECDSA, then
I believe you're right.

> The only problem with using "privKey", "(privKey+1) mod n",
> "(privKey+2) mod n" and so on is that all of those public keys could
> be easily linked together. If that is the only problem, then by
> making offset deterministic but less predictable, it should be secure
> enough, right? So, instead of simple incrementation, we would have
> "privKey" (parent), "(privKey+firstOffset) mod n" (first child),
> "(privKey+secondOffset) mod n" (second child) and so on. And as long
> as this offset is not guessed by the attacker, it is impossible to
> link all of those keys together, right?

I believe this intuition is also a good first approach. So let's have a
look:  You say that offset = SHA256(masterPublicKey || nonce). Is this
predictable by the attacker? 

I can't really answer that question because it's not specified how
"nonce" is obtained.  Since this is supposed to be a deterministic
scheme, I see two basic ways: Either the master private key is involved
in the derivation of "nonce" (then "nonce" may be unpredictable) or
it's not (then "nonce" is predictable).  

Another fact that may or not be a problem is that it may be possible to
compute a parent private key from the a private key. Again, I can't
tell because I don't know how nonce is obtained.

Taking a step back, BIP 32 addresses all of these concerns. I agree it
could be simpler but I don't see a practical necessity to invent a new
scheme. In any application where this proposal could potentially be
used, BIP 32 could also be used and it's just good enough.

Tim 


> 
> > On 2021-03-20 11:08:30 user Tim Ruffing 
> > wrote:
> > > On Fri, 2021-03-19 at 20:46 +0100, vjudeu via bitcoin-dev wrote:
> > > > is it safe enough to implement it and use in practice?
> > > 
> > > This may be harsh but I can assure you that a HD wallet scheme
> > > that can
> > > be specified in 3 lines (without even specifying what the
> > > security
> > > goals are) should not be assumed safe to implement.
> > > 
> > > Tim 
> > > 
> > > 
> > 
> 
> 
> 
> ___
> 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] An alternative to BIP 32?

[Tim Ruffing via bitcoin-dev]

On Fri, 2021-03-19 at 20:46 +0100, vjudeu via bitcoin-dev wrote:
> is it safe enough to implement it and use in practice?

This may be harsh but I can assure you that a HD wallet scheme that can
be specified in 3 lines (without even specifying what the security
goals are) should not be assumed safe to implement.

Tim 

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing via bitcoin-dev]

Hi Dustin,

That sounds interesting but I can't follow your email to be honest.

On Mon, 2020-03-23 at 07:38 -0700, Dustin Dettmer via bitcoin-dev
wrote:
> This mitigates, I believe, all leak vectors besides k/R hacking and
> prechosen entropy.

Hm, so what vectors is this supposed to mitigate? Leaking through the
generated public keys? Anything else?

Here are a few questions:
 - What are you trying to achieve? You seem to describe how you get
from the setup to the goal in four steps but I don't understand what
the setup is or what the goal is. (What's a storage solution?)
 - "all SW being compromised" do you mean "SW and HW compromised"? Note
that SW and HW are parties in Pieter's writeup, not just abbreviations
for software and hardware. 
 - Where are the two stages? You mention four steps.
 - Where do you run the external software? On a second SW? Is this the
second stage?
 - Do you use unhardened derivation?
 - What's a k commitment?


Best,
Tim


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] RFC: Deterministic Entropy From BIP32 Keychains

[Tim Ruffing via bitcoin-dev]

I think your proposal is simply to use BIP32 for all derivations and
the observation that you can work with derived keys with the
corresponding suffixes of the path. I believe that this is a good idea.

But I don't think that simply writing a standard will help. It's just
one step. If all your wallets support incompatible formats, we should
work on fixing this because that's the root of the issue. Otherwise you
end up converting keys back and forth manually (as Chris pointed out),
and this can't be the goal. 

But then you need to reach out to wallet devs explicitly and get them
involved in creating the standard. Otherwise they won't use it. That's
a hard process, and it's even harder to make sure that the resulting
proposal isn't way too complex because everyone brings their special
case to the table. 

Tim 

On Sun, 2020-03-22 at 11:58 +, Ethan Kosakovsky via bitcoin-dev
wrote:
> I have completely revised the wording of this proposal I hope to be
> clearer in explaining the motivation and methodology.
> 
> https://gist.github.com/ethankosakovsky/268c52f018b94bea29a6e809381c05d6
> 
> Ethan
> 
> ‐‐‐ Original Message ‐‐‐
> On Friday, March 20, 2020 4:44 PM, Ethan Kosakovsky via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > I would like to present a proposal for discussion and peer review.
> > It aims to solve the problem of "too many seeds and too many
> > backups" due to the many reasons stipulated in the proposal text.
> > 
> > https://gist.githubusercontent.com/ethankosakovsky/f7d148f588d14e0bb4f70bb6afc509d0/raw/6da51e837b0e1f1b2b21f3d4cbc2c5a87969ffd5/bip-entropy-from-bip32.mediawiki
> > 
> > 
> > BIP:
> > Title: Deterministic Entropy From BIP32 Keychains
> > Author: Ethan Kosakovsky ethankosakov...@protonmail.com
> > Comments-Summary: No comments yet.
> > Comments-URI:
> > Status: Proposed
> > Type: Standards Track
> > Created: 2020-03-20
> > License: BSD-2-Clause
> > OPL
> > 
> > 
> > ==Abstract==
> > 
> > This proposal provides a way to derive entropy from a HD keychain
> > path in order to deterministically derive the initial entropy used
> > to create keychain mnemonics and seeds.
> > 
> > ==Motivation==
> > 
> > BIP32 uses some initial entropy as a seed to deterministically
> > derive a BIP32 root for hierarchical deterministic keychains. BIP39
> > introduced a method of encoding initial entropy into a mnemonic
> > phrase which is used as input to a one way hash function in order
> > to deterministically derive a BIP32 seed. The motivation behind
> > mnemonic phrases was to make it easier for humans to backup and
> > store offline. There are also other variations of this theme.
> > 
> > The initial motivation of BIP32 was to make handling of large
> > numbers of private keys easier to manage and backup, since you only
> > need one BIP32 seed to cover all possible keys in the keychain. In
> > practice however, due to various wallet implementations and
> > security models, the average user may be faced with the need to
> > handle an ever growing number of seeds/mnemonics. This is due to
> > incompatible wallet standards, hardware wallets (HWW), seed formats
> > and standards, as well as, the need to used a mix of hot and cold
> > wallets depending on the application and environment.
> > 
> > Examples would span wallets on mobile phones, online servers
> > running protocols like Join Market or Lightning, and the difference
> > between Electrum and BIP39 mnemonic seed formats. The reference
> > implementation of Bitcoin Core uses BIP32, while other
> > cryptocurrencies like Monero use different mnemonic encoding
> > schemes.
> > 
> > We must also consider the different variety of physical backups
> > including paper, metal and other physical storage devices, as well
> > as the potentially splitting backups across different geographical
> > locations. This complexity may result in less care being taken with
> > subsequently generated seeds for new wallets need to be stored and
> > it ultimately results in less security. In reality, the idea of
> > having "one seed for all" has proven to be more difficult in
> > practice than originally thought.
> > 
> > Since all these derivation schemes are deterministic based on some
> > initial entropy, this proposal aims to solve the above problems by
> > detailing a way to deterministically derive the initial entropy
> > used for new root keychains using a single BIP32 style "master root
> > key". This will allow one root key or mnemonic to derive any
> > variety of different root keychains in whatever format is required
> > (like BIP32 and BIP39 etc).
> > 
> > ==Specification==
> > 
> > Input starts with a BIP32 seed. Derivation scheme uses the format
> > `m/83696968'/type'/index'` where `type` is the final seed type, and
> > `index` in the key index of the hardened child private key.
> > 
> > type
> > 
> > bits
> > 
> > output
> > 
> > 0
> > 
> > 128
> > 
> > 12 word BIP39 mnemonic
> > 
> > 1
> > 
> > 256
> > 
> > 24 word 

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing via bitcoin-dev]

On Sun, 2020-03-22 at 11:30 -0400, Russell O'Connor wrote:
> Your claim is that if we don't fix the pubkey issue there is no point
> in fixing the signature issue.  I disagree.  While I think both
> issues need to be fully addressed, the issues around the original
> proposed non-deterministic signature scheme are far more severe. The
> proposal would move us from a deterministic scheme, where spot checks
> are possible, with all the caveats that entails, to a non-
> deterministic scheme where spot checks are impossible.  My hope is
> that we can standardise a scheme that has the advantages of non-
> determinism without the threat of covert channels.

I think we agree that both issues should be addressed, and this is all
what matters in the end. Now that we have a proposal for Schnorr
signatures, it's indeed a good time to work on these issues.

Tim

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing via bitcoin-dev]

On Sat, 2020-03-21 at 12:59 -0400, Russell O'Connor wrote:
> Public keys are deterministic and can be spot checked.  In fact,
> AFAIU if hardened HD key derivations are not used, then spot checking
> is very easy.
> 
> While spot checking isn't ideal, my original concern with the
> synthetic none standard proposal was that it is inherently non-
> deterministic and cannot ever be spot checked.  This is why anti-
> covert signing protocols are so important if we are going to use
> synthetic nonces.

If spot checking means checking a few instances, then I think this is a
pretty weak defense. What if the device starts to behave differently
after a year?

On Sat, 2020-03-21 at 21:29 +0100, Marko Bencun wrote:
> Practically speaking, most hardware wallets allow you to import your
> own BIP39 seed, so you can work around key generation attacks today,
> with a one time inconvenience at the start. However, with the signing
> nonce attacks, a user today has no protection.
> 

How do you know that the device really uses your seed? This can only be
done by comparing the public keys output by the HW with a second
computation. Even if you use only non-hardened derivation, you need to
check the master (root) public key and that means you need compute the
master root public key once from the seed. You can't do this manually
on a sheet of paper after you rolled a few dice to generate your seed.
So you need to store the seed on a second device (if only for a short
time). And I think this defeats the purpose of a HW wallet.

And even if assume that spot checking and importing the seed works, the
problem is not solved. We still need a clearly specified full protocol
that we can analyze. 

Best,
Tim

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing via bitcoin-dev]

Hi Pieter, 

That's a really nice overview.

Let's take a step back first. If we believe that malicious hardware
wallets are big enough of a concern, then signing is only part of the
problem. The other issue is key generation. The PRG from which the seed
is derived can be malicious, e.g., just H(k_OO,counter) for a key k_OO
chosen by the hardware manufacturer. I haven't seen an argument why
attacks during the signing model should more realistic than attacks
during key generation, so I'd be very hesitant to deploy anti-covert
channel singing protocols without deploying protocols for key
generation that are secure in the same attacker model.

While there's a bunch of protocols for signing, there's not much
research for key generation. One simple idea is a simple commit-and-
reveal protocol to generate a master (elliptic curve) public key pair
with entropy contributions from both HW and SW (similar to the
protocols here for generating R). Then use BIP32 public derivation for
all other keys in order to make sure that SW can verify the derivation
of the public kyes. The corresponding master secret key would replace
the seed, i.e., there's no "symmetric" seed. That idea comes with other
drawbacks however, most importantly this is not compatible with
hardened derivation, which creates a new security risk. If we want
(something like) hardened derivation, zero-knowledge proofs of correct
derivation could maybe used but they again come with other issues
(efficiency, complexity). 

By the way, here's a paper that considers a similar setting where the
hardware wallet is also malicious during key generation: 
https://fc19.ifca.ai/preproceedings/93-preproceedings.pdf
This model goes a step further and assumes threshold signatures but
interestingly here the human user (instead of the SW) is the trusted
party interacting with the HW. In this model the human user has a low-
entropy password.

Now back to the signing process: I think yet another security property
to look at is security against a malicious SW with parallel signing
sessions. I think it's reasonable to restrict a single HW device to a
single session but what if the same seed is stored in two or more HW
wallets? That's plausible at least. Taking this additional security
property into account, it appears that Scheme 4 is vulnerable to
Wagner's attack because SW can influence R by choosing t after seeing
R0. (This can be fixed, e.g., by using Scheme 5 instead.) 


On Tue, 2020-03-03 at 21:35 +, Pieter Wuille via bitcoin-dev wrote:
> 2.d) Statefulness
> 
> We're left with Schemes 4 and 5 that protect against all listed
> issues. Both
> need two interaction rounds, with state that needs to be kept by HW
> between
> the rounds (the k0 value). While not a problem in theory, this may be
> hard to
> implement safely in simple APIs.

A generic way to make one party (HW in this case) stateless is to let
it encrypt and authenticate its state, e.g., using AEAD. In our
particular case I think that the state does not need to be
confidential, and a simple MAC suffices. For simplicity let's assume we
have another hash function H' (modeled as a random oracle) used as MAC.
We can (ab)use d as a MAC key.

If we don't want to spend an entire signature verification on the side
of HW to protect against fault attacks, we can additionally let SW
compute and send the challenge hash e=H(R,Q,m) and let HW only verify
the computation of e. This helps against fault-attacks in the
computation of R and e because now SW needs to commit to e, which is a
commitment to the exact computation fault that HW will suffer from. But
I'm not sure yet if this is weaker or stronger or incomparable to
verifying the signature. I guess it's weaker [1]. If we don't drop
signature verification, this technique does not hurt at least.  

[Scheme 7: synthetic nonce, two interactions, stateless using MAC,
verifying e]

First interaction:
 * SW generates a random t, computes h=H(t), and requests the R0 point
   that HW would use by sending (Q,m,h) to HW.
 * HW uses a global counter c (or fresh randomness c), and computes
   k0=H(d,m,c,h), R0=k0G, mac=H'(d,m,c,h) and sends R0,c,mac to SW.

Second interaction:
 * SW computes R=R0+tG, e=H(R,Q,m) and requests a signature by sending
   (Q,m,t,e,c,mac) to HW
 * HW verifies mac=H'(d,m,c,H(t)), recomputes k0=H(d,m,c,H(t)), k=k0+t,
   computes R=kG, verifies e=H(R,Q,m), and if all is good computes
   s=k+H(R,Q,m)d and sends s to SW.
 * SW verifies that sG=R+eQ and publishes (R,s) if all is good.

One last observation: Since the inputs to H and H' are the same, we
could even use H'(x)=H(H(x)). Not sure if that's useful.

Best,
Tim

[1] In the (admittedly weird) case that faults in two runs of the
executions are independent and can be made highly likely (say
probability almost 1), verifying e could indeed be stronger than
verifying the signature: When verifying the signature, the fault attack
is successful if  the *same* fault happens during signing and
verification 

Re: [bitcoin-dev] Hash function requirements for Taproot

[Tim Ruffing via bitcoin-dev]

Hi Lloyd,

This is great research, thanks for this effort!

Here are some comments:

On Wed, 2020-03-04 at 18:10 +1100, Lloyd Fournier via bitcoin-dev
wrote:
> 
> Property (2) is more difficult to argue as it depends on the multi-
> party key generation protocol. Case in point: Taproot is completely
> broken when combined with a proof of knowledge key generation
> protocol where along with their public keys each party provides a
> proof of knowledge of the secret key. Where X_1 is the key of the
> honest party, the malicious party can choose their key X_2 to be
> G*H(X_1 || m) where m is a malicious Merkle root. Clearly the
> malicious party has a covert Taproot for X = X_1 + X_2 and can
> produce a proof of knowledge for X_2.

I mean, the good thing is that there's a general method to defend
against this, namely always adding a Merkle root on top. Maybe it's
useful to make the warning here a litte bit more drastic:
https://github.com/sipa/bips/blob/bip-taproot/bip-0341.mediawiki#cite_ref-22-0
Maybe we could actually mention this in BIP340, too, when we talk about
key generation,

> 
> Poelstra presented a proof in the ROM for the security of Taproot
> [3]. It frames Taproot as a way of combining two signature schemes
> into one public key (in our case Schnorr and Tapscript). He uses a
> similar line of reasoning to what I have just presented in his proof
> (Lemma 1, step 3) but this approach brings in many other
> considerations that I think can be avoided by modelling it as a
> commitment scheme. Note that this proof only shows that Taproot
> forgeries are hard i.e. property (1).

I agree that modeling it as a commitment scheme is more natural. But I
think an optimal model would capture both worlds, and would give the
attacker signing oracles for the inner and the outer key, and an
commitment opening oracle That is, it would capture that 
 * the ability to obtain signatures for the inner key does not help you
   to forge for the outer key
 * the ability to obtain signatures for the outer key does not help you
   to open the commitment, and --- if already opened --- do not help
   you to forge for the inner key
 * the ability to obtain an opening does not help you to forge for
   either key... 
 * etc

I believe that all these properties hold, and I believe this even
without a formal proof. 

Still, it would be great to have one. The problem here is really that
things get complex so quickly. For example, how do you model key
generation in the game(s) that I sketched above? The traditional way or
with MuSig. The reality is that we want to have everything combined:
 * BIP32
 * MuSig (and variants of it)
 * Taproot (with scripts that refer to the inner key)
 * sign-to-contract stuff (e.g., to prevent covert channels with
   hardware wallets)
 * scriptless scrips
 * blind signatures
 * threshold signtures
 * whatever you can imagine on top of this

It's very cumbersome to come up with a formal model that includes all
of this. One common approach to protocols that are getting too complex
is to switch to simpler models, e.g., symbolic models/Dolev-Yao models
but that's hard here given that we don't have clear layering. Things
would be easier to analyze if Taproot was really  just a commitment to
a verification key. But it's more, it's something that's both a
verification and a commitment. Taproot interferes with Schnorr
signatures on an algebraic level (not at all black-box), and that's
actually the reason why it's so powerful and efficient. The same is
true for almost everything in the list above, and this puts Taproot
outside the scope of proof assistants for cryptographic protocols that
work on a symbolic level of abstraction. I really wonder how we can
handle this better. This would improve our understanding of the
interplay between various crypto components better, and make it easier
to judge future proposals on all levels, from consensus changes to new
multi-signature protocols, etc.

> 
> In my opinion, the cost of Taproot is mostly borne by theoreticians.
> They can no longer treat a a public key ideally but have to consider
> the implications of it also being a commitment. For the user and
> Bitcoin as a whole it seems to offer an overwhelming benefit. In
> exchange for the complexity it adds to making security claims in the
> GGM (if using Taprscript and MuSig), it offers exciting new
> opportunities for non-interactivity and fungibility over what just
> what Schnorr would provide.

I agree with this overall statement. I'm confident in Taproot, and I
guess what say above really applies to the cost for theoreticians.
(Let's just make sure that we don't forget how theory is relevant to
security in practice.) 

Tim

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Composable MuSig

[Tim Ruffing via bitcoin-dev]

The only thing that matters is the number of parallel sessions. If you
bound this to something like 2 or 3, then the resulting scheme may be
secure. But you need to the actual math of Wagner's attack, and who
knows how efficient it can be implemented in practice. 

Timeouts on top of this won't help. And who needs 2 or 3 parallel
sessions? If you need parallel sessions (or not), use 3-round MuSig and
the entire issue is simply eliminated.

Tim  

On Mon, 2020-02-24 at 10:30 -0500, Erik Aronesty wrote:
> Basically just some mechanism for preventing repeated signings of the
> same message, and using a "validity" time window so that the amount
> of
> state you need to enquire about isn't unbounded.
> 
> The Drijvers, et al paper is specifically concerned with parallel and
> aborted signings, where ksums can be used.  In general, the more
> variables that an attacker can control ,the more "k" lists they can
> form, and the more likely they can find collisions.
> 
> If signers refused to sign "stale" messages, refused to sign in
> parallel beyond a certain limit, and refused to sign the same message
> twice, it should help reduce the attack surface.
> 
> On Mon, Feb 24, 2020 at 6:41 AM Tim Ruffing via bitcoin-dev
>  wrote:
> > On Sun, 2020-02-23 at 02:27 -0500, Erik Aronesty via bitcoin-dev
> > wrote:
> > > > Thus, two-phase MuSig is potentially unsafe.
> > > > https://eprint.iacr.org/2018/417.pdf describes the argument.
> > > 
> > > One solution is to add a signature timeout to the message (say a
> > > block height) .
> > > 
> > > A participant refuses to sign if that time is too far in the
> > > future,
> > > or is at all in the past, or if a message M is the same as any
> > > previous message within that time window.
> > > 
> > > Seems to resolve the attacks on 2 round musig.
> > 
> > I don't understand this. Can you elaborate?
> > 
> > Best,
> > Tim
> > 
> > ___
> > 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] Composable MuSig

[Tim Ruffing via bitcoin-dev]

On Sun, 2020-02-23 at 02:27 -0500, Erik Aronesty via bitcoin-dev wrote:
> > Thus, two-phase MuSig is potentially unsafe.
> > https://eprint.iacr.org/2018/417.pdf describes the argument.
> 
> One solution is to add a signature timeout to the message (say a
> block height) .  
> 
> A participant refuses to sign if that time is too far in the future,
> or is at all in the past, or if a message M is the same as any
> previous message within that time window.
> 
> Seems to resolve the attacks on 2 round musig.

I don't understand this. Can you elaborate?

Best,
Tim

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Overhauled BIP151

[Tim Ruffing via bitcoin-dev]

On Fri, 2018-09-07 at 02:31 +, Gregory Maxwell wrote:
> Currently, Tor provides _no confidentiality at all_ in that threat
> model.  Part of why I think this enhancement is interesting is
> because
> without it BIP151 doesn't actually add anything for those p2p
> connections running over Tor, but with it -- it at least adds some
> long term confidentiality hedge.
> 
Okay, sure, I was assuming that Tor will deploy it at some point. No
idea what the status is.

> > It's not worth the hassle, would hinder adoption,
> 
> Why do you say this?
My assumption is that NewHope is harder to implement. If you just 
drop-in existing code, it's not. And I've neither implemented NewHope
nor Elligator Squared, so I may just be wrong.

> 
> > impression of "bulletproof" security. Even worse, there will be too
> > many people that will suddenly
> > assume that Bitcoin is post-quantum secure.
> 
> People already make that claim with respect to public key hashing.  I
> don't think "we shouldn't improve security because someone will
> mistake an improvement for perfection" is an an especially
> interesting
> argument.

I don't like the argument either but I think it's real.

> (Blockstream  previously wrote the SW forward transform for asset
> generation, but this requires the inverse too, as well as glue code.
> It also isn't clear to me if it's possible to make this construction
> constant time, which would be okay for BIP151 purposes but if we
> wanted to have a generic uniform encoder in libsecp256k1 I think we'd
> prefer it be constant time? maybe?)
No idea if it can be made constant time but yeah I think it's not
crucial in this case.

> 
> I don't believe that indistinguishable keys are actually useful
> outside of the context of things like stegnographic embedding-- cases
> where protocol 'metadata' doesn't tell you that a key is there
> regardless.

I wasn't specific but my point is that these are indeed interesting
future directions. You can easily make the traffic look like any other
protocol which uses encryption. That's a really useful property if you
want to avoid censorship, even if traffic analysis still works. That's
true even if this it's not in the scope of this BIP, which is of course
the case.

If you ask me, that is more interesting than protecting against
potential decryption of P2P connections in a few decades. But I don't
have a definitive argument for this of course.


> I also prefer the contributory key model, but Pieter proved me on IRC
> last week that the attack form that I was concerned about was not
> possible.
> 
> Do you actually have an attack in mind that you can spell out
> here?  I
> don't see a harm in changing that, but given that I'd already twice
> talked myself out of proposing the same thing, I'd like to understand
> if I'm missing something. :)

I don't have a harmful example but here is harmless one (that you
probably know because it's really the simplest one can think of):

A M B 
   -- aG -->
 <-- bG --
  -- aG -->
  <-- bG --

Now A and B share the same session id but any attempt to communicate
will fail because they both think that they're the initiator. Of course
that's not a big deal because M is in neither of those sessions. So
it's not an attack but it's a weird property of the key exchange. But I
think it's desirable to avoid such things if the cost to do so is very
low.

Also, here is a better argument:

A M B 
   -- aG -->
 <-- bG --
  <-- xG --
  -- yG -->

After B's message, M's goal is create a collision of the session ids.
Since M can freely choose x and y, that's a birthday attack on the hash
function and needs 2^(l/2) work if the session id is l bits long.

Telegram has (had?) the same issue:
https://www.alexrad.me/discourse/a-264-attack-on-telegram-and-why-a-super-villain-doesnt-need-it-to-read-your-telegram-chats.html

With the other variant, M cannot collect both aG and bG upfront:

A M B 
   -- aG -->
  -- yG -->
 <-- bG --
  <-- xG --

Now M can only choose x, so this is a second-preimage attack and takes
2^l work. So with the this variant, you can have a session id that's
only half the size. That's a real difference if session ids are meant
to be comparable by humans, e.g., over the phone. 

(I think) it's possible to even go further with a 3-way handshake:
AMB 
   -- H(aG) -->
-- H(yG) -->
   <--  bG   --
  <--  xG   --
   --  aG   -->
--  yG   -->

Here M has no flexibility at all, so the probability of a successful
attack against a single key exchange is just 2^(-l). This is similar to
ZRTP. I'm not saying that we should do this, it's something worth
noting that.

  
> 
> > Re-keying
> > =
> > The problem with signalling re-keying in the length field is that
> > the length field is not 

Re: [bitcoin-dev] Overhauled BIP151

[Tim Ruffing via bitcoin-dev]

Hi Jonas,

Great to see progress in this area. I have quite a few comments.

Post-quantum key exchange
=
I think that's overkill. Bitcoin has huge problems in the presence of a quantum 
computer, and the
confidentiality of the P2P messages is the most minor one. If there is a 
quantum computer and
Bitcoin remains in its current form, then people should probably stop using it.

Now you can argue that the attacker is storing encrypted traffic today to 
decrypt it later. Sure,
but if that's your threat model then Bitcoin is probably not the right tool for 
you. (And if
you insist that Bitcoin is the right tool, then you can and probably should use 
it over Tor
anyway.) Given the fact that essentially all information in Bitcoin will be 
public in some way,
there are probably cheaper attacks (MITM, traffic analysis).

It's not worth the hassle, would hinder adoption, and it has the potential to 
create a wrong
impression of "bulletproof" security. Even worse, there will be too many people 
that will suddenly
assume that Bitcoin is post-quantum secure.

Key exchange indistinguishable from random
==
I would rather love to see a simple ECDH key exchange as currently used but 
with an encoding of
public key that provides indistinguishability from random bitstrings. 
"Elligator" does not work
but "Elligator Squared" [1] does the job for secp256k1 -- it just doubles the 
size of the public
key. Together with the encrypted packet lengths, the entire data stream looks 
like random then,
which is pretty useful against censorship resistance for example. (The only 
exception is that the
stream will never start with the magic bytes.)

Key derivation
==
The key derivation can be improved. It should include each peer's understanding 
of its role,
i.e., requester (or "initiator" is the more common term) or responder. At the 
moment, an attacker
can create a situation where two peers think they're in the same session (with 
the same session
id) but they're actually not. Also, it's possible for an attacker to 
rerandomize the public keys.
That's nothing bad by itself but anything which restricts the flexibility of 
the attacker without
adding complexity is a good idea. Something like
   "salt = BitcoinSharedSecret||INITIATOR_PUBKEY||RESPONDER_PUBKEY" should just 
avoid this issue.

Re-keying
=
The problem with signalling re-keying in the length field is that the length 
field is not covered
by the MAC. So the attacker can flip the signalling bit. The resulting protocol 
is probably still
secure but the malleability is certainly not desirable.

Deterministic rekeying rules may be better. Otherwise there will be 
implementations that rekey
every 10 seconds and implementations that just don't rekey at all (rendering 
the 10 s rekeying
interval in the opposite direction useless). Different policies also make it 
possible to
fingerprint implementations. Another problem is that people will set their 
policies arbitrarily.
What's better: 5 min or 30 min? I don't know, but both are reasonable choices. 
(Thats's very much
like discussions about ciphers... What's better AES-GCM or ChaCha20/Poly1305? I 
don't know, but
again both are reasonable choices.)

Symmetric crypto

You call it chacha20-poly1305@bitcoin but what's the difference to the openssh 
then? Is the
idea to save a call to chacha here as you mentioned?

I didn't think about this in detail: maybe there are a few meaningful cases 
where padding could
hide the message length without too much overhead. (I'm not convinced, just a 
random thought.)

Misc

"The ID/string mapping is a peer to peer arrangement and MAY be negotiated 
between the
requesting and responding peer." I think that's overly complicated. I suggest 
it should just be
written in stone, again to avoid complexity and to avoid fingerprinting. New 
implementations are
necessary anyway, so maybe just use IDs for anything? ASCII is nice if you want 
to debug your code
or some random network failure but that's hard anyway when encryption is used.

In general, the entire thing is a little bit underspecified. (I'm aware it's 
just a draft.)
A few examples:
 - What should a peer do if the MAC verification fails?
 - What should a peer do if it receives an even key?
 - "Processing the message before the authentication succeeds (MAC verified) 
MUST not be done."
 That should also apply to the ciphertext. (Or: What is a "message"?). It may 
be a good idea to
 to refer to the openssh document or steal from it; it does a pretty good job.
 - "Both peers MUST keep track of the message sequence number (uint32) of sent 
and received
 messages for building a 64-bit symmetric cipher IV." I think you mean nonce 
when you say IV?
 - What is the initial value of the sequence number?
 - How is a 64-bit nonce formed from one (two?) uint32?
 - What if the uint32 overflows?
 - "Re-Keying interval is a peer policy with a minimum timespan 

Re: [bitcoin-dev] Schnorr signatures BIP

[Tim Ruffing via bitcoin-dev]

Is it intentional that the encoding of public (and private) keys is
unspecified? I'd consider at least the encoding of the public key to be
part of the signature scheme, so ideally it should be specified already
in this BIP. On the other hand, there may be good arguments against it,
but I'm not aware of any.

This issue leads to a discrepancy between the specification and the
test vectors because the data fields of test vectors "are given as byte
arrays", including public and secret key. As a consequence, even the
Python reference implementation in the BIP draft doesn't work on test
vectors (in a strict sense).

Best,
Tim


On Fri, 2018-07-06 at 11:08 -0700, Pieter Wuille via bitcoin-dev wrote:
> Hello everyone,
> 
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> 
> It is simply a draft specification of the signature scheme itself. It
> does not concern consensus rules, aggregation, or any other
> integration into Bitcoin - those things are left for other proposals,
> which can refer to this scheme if desirable. Standardizing the
> signature scheme is a first step towards that, and as it may be
> useful
> in other contexts to have a common Schnorr scheme available, it is
> its
> own informational BIP.
> 
> If accepted, we'll work on more production-ready reference
> implementations and tests.
> 
> This is joint work with several people listed in the document.
> 
> Cheers,
> 

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Multiparty signatures

[Tim Ruffing via bitcoin-dev]

Hi Erik,

On Sun, 2018-07-08 at 10:19 -0400, Erik Aronesty via bitcoin-dev wrote:
> Consider changing the "e" term in the schnorr algorithm to hash of
> message (elligator style) to the power of r, rather than using
> concatenation.  

How do you compute s = x*e if e is an element of group G?
(Similar question: How do you verify if e is element of G?)

Are you aware of 
 http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps ?
This is a threshold signature scheme for Schnorr signatures, so what
you want is possible already with Schnorr signatures.

Best,
Tim
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Tim Ruffing via bitcoin-dev]

What you're saying makes sense.

By the way, an even stronger reason why you shouldn't be able to
"repurpose" just a Graftroot signature as a transaction: You may want
to reveal to others that you've delegated. But if an observer sees the
delegation (literally the Graftroot signature), this observer could
send the Graftroot signature to the network (and lock out the other
delegates and the initial owner). So you would need to keep the
signature itself secret, otherwise we can't call this delegation.

So it may sense to consider the idea of an implicit transaction for the
case when one really solves the delegated script (as you mentioned) but
only in this case.

Tim


On Wed, 2018-06-06 at 10:04 -0700, Pieter Wuille wrote:
> On Wed, Jun 6, 2018 at 5:48 AM, Tim Ruffing via bitcoin-dev
>  wrote:
> > On Thu, 2018-05-31 at 17:25 -0700, Pieter Wuille via bitcoin-dev
> > wrote:
> > > The best argument for why Graftroot does not need to be optional
> > > I
> > > think was how Greg put it: "since the signer(s) could have signed
> > > an
> > > arbitrary transaction instead, being able to delegate is strictly
> > > less
> > > powerful.".
> 
> ...
> 
> > So
> > I think Graftroot delegation is not "strictly less powerful" than
> > just
> > using a normal transaction: Graftroot enables to delegate in a way
> > such
> > that the delegation itself cannot be fixed in the chain. I think
> > this
> > is not possible currently. (Okay, you can just pass around the
> > secret
> > keys but has other problems obviously).
> > 
> > Does this have practical implications?
> > I don't see any but maybe this helps someone to identify an
> > undesirable
> > implication.
> 
> Interesting point; I don't see any relevant implications to this
> either, but it's indeed good to point out this as a distinction.
> 
> > One way to be on the safe side and probably make Greg's argument go
> > through is to just define the semantics such that (*) is allowed,
> > i.e.,
> > call g-sig a "Graftroot transaction" and give it transaction
> > semantics.
> > This provides a new perspective on Graftroot: Then Graftroot does
> > not
> > introduce new semantics but (*) is just an optimized version of
> > (**)
> > that uses fewer bytes and may be better for privacy.
> 
> So you're saying: the Graftroot signature data could be made
> identical
> to the signature hash of an implicit 1-input-1-output transaction
> spending the coin and creating a new output with the delegated script
> as sPK, and the same amount.
> 
> I like that idea, but I don't think it can be *exactly* that. If it's
> possible to take a Graftroot signature and instead construct a
> transaction with it, you have inherently introduced a malleability.
> The created outpoint will be different in both cases (different
> txid),
> meaning that a chain of dependent unconfirmed transactions may be
> broken by giving one participant the ability to choose between
> Graftroot delegation or actual spending.
> 
> Two points here: (1) the implicit transaction would be 0 fee (unless
> we somehow assign a portion of the fee to the delegation itself for
> purposes of sighash computing), and (2) this sounds very similar to
> the issue SIGHASH_NOINPUT is intended to solve. About that...
> 
> > Interestingly Andrew's blind-sig example and Johnson's fix (g-sig
> > signs
> > the outpoint) are just a special case. If g-sig has transaction
> > semantics, it must sign the outpoint (and other stuff).
> 
> You're right when you're comparing with existing transaction sighash
> semantics, but not when SIGHASH_NOINPUT would exist. If that were the
> case, the only real difference is your point above of not being able
> to commit the implicit transaction separately. In other words, we're
> back to something Johnson pointed out earlier: some of the perceived
> problems with Graftroot are also issues with SIGHASH_NOINPUT.
> 
> I wonder if we can make this explicit: Graftroot spending becomes a
> special sighash flag (which possibly is only allowed at the top
> level)
> - it builds an implicit transaction which moves all the coins to a
> newly provided script, computes the sighash of that transaction
> (taking all of the Graftroot signature's sighash flags into account -
> including potentially SIGHASH_NOINPUT), and requires a signature with
> that. The delegated script is then evaluated in the context of that
> implicit transaction.
> 
> However, in order to avoid the malleability issue I think the actual
> signature should still be different - possibly by simply passing
> through the Graftroot sighash flag into the sighash being computed.
> 
> Cheers,
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Tim Ruffing via bitcoin-dev]

I haven't read the original Graftroot thread, so maybe all of this has
b
een discussed already or is just wrong... Please correct me if this
is
the case.

On Thu, 2018-05-31 at 17:25 -0700, Pieter Wuille via bitcoin-dev wrote:
> The best argument for why Graftroot does not need to be optional I
> think was how Greg put it: "since the signer(s) could have signed an
> arbitrary transaction instead, being able to delegate is strictly
> less
> powerful.".

I'm trying to get a more abstract view of the problem. One issue with
Greg's argument is the following:

If g-script is a script (containing a public key) that allows for
Graftroot spending, then the following "flow" of coins is valid: 

  g-script --g-sig--> script1 ---tx2---> script2

Here, g-sig is a Graftroot signature on script1 and tx2 is a
transaction that fulfills script1 and sends to script2. In other words,
the only transaction involved here is tx2; it provides g-sig, script1,
and a solution for tx1, and it spends to script2.

Now Greg's argument (as I understand it) is that this can be already
done without Grafroot with two transactions, namely a normal
transaction tx1 that spends g-script normally and tx2 that spends tx1
to script1.

  g-script ---tx1---> script1 ---tx2---> script2.

So far, so good. A difference however is that g-sig *alone* can't be
committed to the chain but tx1 alone can be committed to the chain.
That means

  g-script --g-sig--> script1 (*)

is "incomplete" but

  g-script ---tx1---> script1 (**)

is a perfectly valid transaction that can be committed to the chain. So
I think Graftroot delegation is not "strictly less powerful" than just
using a normal transaction: Graftroot enables to delegate in a way such
that the delegation itself cannot be fixed in the chain. I think this
is not possible currently. (Okay, you can just pass around the secret
keys but has other problems obviously).

Does this have practical implications?
I don't see any but maybe this helps someone to identify an undesirable
implication.

One way to be on the safe side and probably make Greg's argument go
through is to just define the semantics such that (*) is allowed, i.e.,
call g-sig a "Graftroot transaction" and give it transaction semantics.
This provides a new perspective on Graftroot: Then Graftroot does not
introduce new semantics but (*) is just an optimized version of (**)
that uses fewer bytes and may be better for privacy. 

Interestingly Andrew's blind-sig example and Johnson's fix (g-sig signs
the outpoint) are just a special case. If g-sig has transaction
semantics, it must sign the outpoint (and other stuff).

Now you can say that this is not really useful: if g-sig is essentially
a full transaction that can committed to the blockchain, then it needs
to specify inputs, outputs etc. So all the optimizations are lost and
those were the reason we want to introduce Grafroot in the first place.

But one observation here is that g-sig only needs to be a full
transaction if it's used standalone as in (*). If we want to have 

  g-script --g-sig--> script1 ---tx2---> script2

(and this should be the common case) then just the bare signature  and
script1 suffices, as in the Graftroot proposal. In some sense, inputs
and outputs of the Graftroot transaction are just implicit in this
case.

Another way to look at this that instead of providing a transaction
with g-sig, script1, and a solution for script1, you can also choose to
provide a transaction with only g-sig and script1 (and don't solve
script1), which then just sends to script1.

I'm not saying that it's worth the hassle to add this possibility
without being aware of a problem that arises if we don't add it -- but
maybe my thoughts provide another perspective on the issue.

Best,
Tim


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Bulletproof CT as basis for election voting?

[Tim Ruffing via bitcoin-dev]

You're right that this is a simple electronic voting scheme. The thing
is that cryptographers are working on e-voting for decades and the idea
to use homomorphic commitments (or encryption) and zero-knowledge
proofs is not new in this area. It's rather the case that e-voting
inspired a lot of work on homomorphic crypto and related zero-knowledge 
proofs. For example, range proofs are overkill in e-voting. You just
need to ensure that the sum of all my votes (over all candidates) is 1.
 
E-voting protocols typically require some "bulletin board", where
ballots are stored. A blockchain could indeed be helpful in specific
cases (but not in all cases)...

If you're interested in that stuff, I'd suggest you to read some
literature about e-voting. (For example, 
https://arxiv.org/pdf/1801.08064 looks interesting for the connection
to blockchains -- I haven't read it though). There are pretty
sophisticated protocols in the literature. And I think that this
mailing list may not be the best place to discuss these.

Best,
Tim 



On Sun, 2018-03-11 at 13:44 +0100, JOSE FEMENIAS CAÑUELO via bitcoin-
dev wrote:
> If I understand Bulletproof Confidential Transactions properly, their
> main virtue is being able to hide not the senders/receivers of a coin
> but the amount transferred.
> That sounds to me like a perfect use case for an election.
> For instance, in my country, every citizen is issued a National ID
> Card with a digital certificate. 
> So, a naive implementation could simply be that the Voting Authority,
> sends a coin (1 coin = 1 vote) to each citizen above 18. This would
> be an open transaction, so it is easily auditable.
> Later on, each voter sends her coin to her preferred party, as part
> of a Bulletproof CT, along with 0 coins to other parties to disguise
> her vote.
> In the end, each party will accrue as may votes as coins received.
> 
> Is there any gotcha I’m missing here? Are there any missing features
> required in Bulletproof to support this use 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] Transition to post-quantum

[Tim Ruffing via bitcoin-dev]

On Thu, 2018-02-15 at 23:44 +0100, Natanael wrote:
> If your argument is that we publish the full transaction minus the
> public key and signatures, just committing to it, and then revealing
> that later (which means an attacker can't modify the transaction in
> advance in a way that produces a valid transaction);

Almost. Actually we reveal the entire transaction later. 

> 
> [...] while *NOT* allowing expiration makes it a trivial DoS target. 
> 
> Anybody can flood the miners with invalid transaction commitments. No
> miner can ever prune invalid commitments until a valid transaction is
> finalized which conflicts with the invalid commitments. You can't
> even rate limit it safely. 

Yes, that's certainly true. I mentioned that issue already. 

You can rate limit this: The only thing I see is that one can require
transaction fees even for commitments. That's super annoying, because
you need a second (PQ-)UTXO just to commit. But it's not impossible.

You can call this impractical and this may well be true. But what will
be most practical in the future depends on many parameters that are
totally unclear at the moment, e.g., the efficiency of zero-knowledge
proof systems. Who knows?

If you would like to use zero-knowledge proofs to recover an UTXO with
an P2PKH address, you need to prove in zero-knowledge that you know
some secret key x such that H(g^x)=addr. That seems plausible. But
P2PKH is by far the simplest example. For arbitrary scripts, this can 
become pretty complex and nasty, even if our proof systems and machines
are fast enough.

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Transition to post-quantum

[Tim Ruffing via bitcoin-dev]

On Thu, 2018-02-15 at 21:27 +0100, Natanael wrote:
> I addressed this partially before, and this is unfortunately
> incomplete.
> 
> Situation A: Regardless of expiration of commitments, we allow
> doubles. (Or no doubles allowed, but commitments expire.) 
> 
> If I can block your transaction from confirming (censorship), then I
> can make my own commitment + transaction. The miners will see two
> commitments referencing the same UTXO - but can see only one
> transaction which match a valid challenge and spends them, which is
> mine. You gained nothing from the commitment.

Yes, I assume situation A: 
  * commitments never expire
  * and there is no limit on the number of commitment for the same UTXO

As I understand, you mean "decommitment" when you say "transaction".
Please correct me if I'm wrong. I'll stick with "decommitment".

Let's assume the attacker blocks the decommitment by the honest user,
inserts his own malicious commitment and his own decommitment, which
should be valid for the malicious commitment. Then the miners will see
two commitments (the earlier commitment by the honest user and the
later one by the attacker).

Also, the miners will indeed see one valid decommitment. This
decommitment may have been sent by the attacker but it's the preimage
chal of the address, because otherwise it's not valid for the malicious
commitment. But if the decommitment is chal, then this decommitment is
also valid for the commitment of the honest user, which is earliest
additionally. So the honest commitment wins. The attacker does not
succeed and everything is fine.

The reason why this works:
There is only one unique decommitment for the UTXO (assuming H_addr is
collision-resistant). The decommitment does not depend on the
commitment. The attacker cannot send a different decommitment, just
because there is none.

Maybe I'm wrong and I just don't understand your attack. In this case,
please explain it more detail.

Regards,
Tim
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Transition to post-quantum

[Tim Ruffing via bitcoin-dev]

First of all, there is indeed an issue in my proposal:

The idea was to include a classic signature to make sure that, if (for
whatever reason) you have revealed classic_pk already.

However, the problem is that if you have revealed classic_pk, then
everybody can effectively prevent you from spending the funds as you
wish by just including the first commit entry with an arbitrary tx in
the blockchain. That's bad obviously.

Here is a fixed variant, which does not only work with normal P2PKH but
1) supports basically with any (hash-based) addresses, for which the
preimage has not been revealed and 2) does not change the conditions
under which a UTXO can be spent.

Setup
=
We will need multiple hash functions KDF, H, and authenticated
symmetric encryption Enc/Dec.

Let's assume we have an UTXO with address addr = H_addr(chal), where
chal is a challenge, i.e., typically a scriptPubKey (what I called
classic_pk initially) and H_addr is the hash function used to form
addresses. (If there are multiple UTXO sharing the same address, they
can be spent simultaneously with this approach.) To spend this UTXO
with a transaction tx, the user performs the following two steps.

Note that -- in contrast to my earlier emails -- tx is assumed to
include a solution to the challenge in its input, i.e., a string which
proves that you are allowed to spend the UTXO (typically a scriptSig). 

Commit step
===
Derive a symmetric key k = KDF(chal).

Create and publish a commitment in the blockchain that references the
UTXO as inputs and contains the following data: 
  c = Enc(k, tx)

Wait until c is confirmed. (If it does not confirm, send it again as
usual.)

Decommit step
=
Create and publish a decommitment with the following data:
  d = chal

Consensus rules
===
A decommitment d = chal spends a UTXO with address H_addr(chal), if
there exists a commitment c in the blockchain which references the UTXO
and which is the first commitment (among all referencing the UTXO) in
the blockchain such that
1. k = KDF(chal) correctly decrypts Dec(k, c)
and
2. tx = Dec(k, c) is a valid transaction to spend UTXO 

The UTXO is spent as described by tx.
Commitments never expire.

The second condition covers that tx contains a classic signature under
the public key specified in chal in normal P2PKH addresses.

The trick here is that the encryption ensures that the user commits to
tx (including the classic signature) already in the commit step, while
still keeping the decommitment unique. If I'm not mistaken, this scheme
is a variant of Adam Back's proposal for committed transactions from
2013, which he invented for an entirely different goal, namely
censorship resistance:
https://bitcointalk.org/index.php?topic=206303.msg2162962#msg2162962

(Adam noted the similarity of the problems on Twitter recently:
https://twitter.com/adam3us/status/948219461345075201)

The above variant is pretty simple. If it really works and is secure,
it has the advantage over Adam's proposal that it does not rely on
ECDSA specifically and can be used for any address type. 

The aforementioned thread in the Bitcoin forum discusses the main
problem of an approach like that: Everybody can flood the blockchain
with commitments. Of course, one can require fees to create
commitments, but that's pretty ugly: If this UTXO is the only money you
have, then you need to borrow some to pay the transaction fees upfront.
But this may be the price you need to pay for recovery. This can be
acceptable, because recovery should be the exception (see below).

On Tue, 2018-02-13 at 21:06 +1100, Tristan Hoy via bitcoin-dev wrote:
> The worst-case outcome is that ECDSA is broken before PQ addresses
> are 
> rolled out. There is no reactive response to this - all the existing 
> ECDSA addresses will be compromised. A proactive measure is
> required, 
> and it should be deployed sooner rather than later.

The proposal above does not require any changes to existing ECDSA
addresses, so there is no need to change something now already. 

At some point in the future, PQ addresses will be deployed. And at some
(potentially different) point in the future, we should deploy a
solution to recover UTXOs. But there's no need to do this today. A
recovery solution can be deployed even when DLOG has been broken
already -- not optimal but possible.

> 
> Any two-step approach adopted now as a proactive measure will not
> only 
> bloat the blockchain, it will also double the effective confirmation 
> time - for all transactions between now and when PQ addresses are
> rolled 
> out, which seems unlikely to happen in the next 5 years. The bloat
> will 
> be permanent.
> 

I don't think that's true due to the situation I describe above. We
don't need to act now.

And even if we act now, i.e., even if we enable the above proposal (or
any other protocol that enables recovery of UTXOs with addresses)
today, people are not forced to use it. As long as ECDSA and the other

Re: [bitcoin-dev] Transition to post-quantum

[Tim Ruffing via bitcoin-dev]

On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote:
> In a post-quantum world, your second "d" type transaction is
> completely forgeable, which means it is vulnerable to front-running.
> An adversary capable of breaking ECDSA needs only listen for these
> transactions, obtain "classic_sk" and then use a higher fee (or
> relationship with a miner) to effectively turn your original "d"
> transaction into a double-spend, with the forged transaction sending
> all your funds to the adversary.

That's not true. The d(ecommit) transaction, or better let's call it
"decommit step" of a two-step transaction does not specify the effects
(output script). This is what I denote by "tx" in the writeup, and it's
already fixed by the c(ommit) step.

So yes, if the user finally reveals
  d  = classic_pk||Sign(classic_sk, tx)
a quantum attacker can indeed forge
  d' = classic_pk||Sign(classic_sk, tx') 
for tx' != tx of his choice. But that won't help him, because the first
valid c step in the chain is for tx and not for tx'.

> The other issue with your approach is that if it is rolled out today,
> it will effectively double transaction volumes - this is what I tried
> to solve in solutions 2 and 3 in my article by instead modifying the
> address generation process.

Yep, it needs two entries in the blockchain, and that does not mean
that it doubles the data. It will need some more bytes in the
blockchain but also proper PQ-transactions could need more bytes in the
blockchain, so I don't think that's the major issue.


> 
> Regards,
> 
> Tristan
> 
> On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev  -d...@lists.linuxfoundation.org> wrote:
> > Hi Tristan,
> > 
> > Regarding the "Post-Quantum Address Recovery" part (I haven't read
> > the
> > other parts), you may be interested in my message to the list from
> > last
> > month and the rest of the thread:
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar
> > y/015659.html
> > 
> > This is an approach which aims to avoid the issues that you've
> > mentioned in your blog post.
> > 
> > Best,
> > Tim
> > 
> > On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev
> > wrote:
> > > Hi all,
> > >
> > > Recently I've been exploring what a post-quantum attack on
> > Bitcoin
> > > would actually look like, and what options exist for mitigating
> > it.
> > >
> > > I've put up a draft of my research here: https://medium.com/@tris
> > tanh
> > > oy/11271f430c41
> > >
> > > In summary:
> > > 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
> > > scalable
> > > 2) This is a rapidly advancing space and committment to a
> > specific
> > > post-quantum DSA now would be premature
> > > 3) I've identified a strategy (solution 3 in the draft) that
> > > mitigates against the worst case scenario (unexpectedly early
> > attack
> > > on ECDSA) without requiring any changes to the Bitcoin protocol
> > or
> > > total committment to a specific post-quantum DSA that will likely
> > be
> > > superseded in the next 3-5 years
> > > 4) This strategy also serves as a secure means of transferring
> > > balances into a post-quantum DSA address space, even in the event
> > > that ECDSA is fully compromised and the transition is reactionary
> > >
> > > The proposal is a change to key generation only and will be
> > > implemented by wallet providers.
> > >
> > > Feedback would be most appreciated.
> > >
> > > Regards,
> > >
> > > Tristan
> > > ___
> > > 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] Transition to post-quantum

[Tim Ruffing via bitcoin-dev]

Hi Tristan,

Regarding the "Post-Quantum Address Recovery" part (I haven't read the
other parts), you may be interested in my message to the list from last
month and the rest of the thread:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015659.html

This is an approach which aims to avoid the issues that you've
mentioned in your blog post.

Best,
Tim

On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote:
> Hi all,
> 
> Recently I've been exploring what a post-quantum attack on Bitcoin
> would actually look like, and what options exist for mitigating it.
> 
> I've put up a draft of my research here: https://medium.com/@tristanh
> oy/11271f430c41 
> 
> In summary:
> 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
> scalable
> 2) This is a rapidly advancing space and committment to a specific
> post-quantum DSA now would be premature
> 3) I've identified a strategy (solution 3 in the draft) that
> mitigates against the worst case scenario (unexpectedly early attack
> on ECDSA) without requiring any changes to the Bitcoin protocol or
> total committment to a specific post-quantum DSA that will likely be
> superseded in the next 3-5 years
> 4) This strategy also serves as a secure means of transferring
> balances into a post-quantum DSA address space, even in the event
> that ECDSA is fully compromised and the transition is reactionary
> 
> The proposal is a change to key generation only and will be
> implemented by wallet providers.
> 
> Feedback would be most appreciated.
> 
> Regards,
> 
> Tristan
> ___
> 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] Recovery of old UTXOs in a post-quantum world

[Tim Ruffing via bitcoin-dev]

(changing the subject... ;))

My proposal does not include any form of expiration, so I don't see how
it should be vulnerable to the described attack.

To make this a little bit more detailed:

The user has one or more single standard UTXOs all with ECDSA public
key classic_pk and thus address SHA256(RIPEMD160((classic_pk)). The
corresponding secret key is classic_sk. Let MAC be a quantum-secure
message-authentication code, e.g., MAC(k,x)=H(k||x) for a suitable hash
function, e.g, BLAKE2 or SHA3.

The idea is to (ab)use the public key classic_pk as a key for the MAC. 

To spend an UTXO with a transaction tx, the user does the following:
   1. Create and publish a "transaction" c that references the address
  SHA256(RIPEMD160((classic_pk)) and contains the following data: 
  MAC(classic_pk,tx))||tx
   2. Wait until c is confirmed. (If it does not confirm, send it again as
  usual).
   3. Create and publish a "transaction" d with the following data:
  classic_pk||Sign(classic_sk, tx)

Consensus rules:
A transaction d=classic_pk||sig spends all UTXOs with
address SHA256(RIPEMD160(classic_pk)), applying the effects of tx, if
there exists a transaction c=mac||tx in the blockchain such that 
   1. c is the first transaction (among all referencing the address) in
  the blockchain where mac is a valid MAC for message tx under correct
  key classic_pk
   2. sig is valid ECDSA signature over tx under public key classic_pk

c-transactions never expire. 

If the user has not published classic_pk before, this should be secure
against quantum attackers:
Before step 2, the MAC key k=classic_pk is only known to the user. So
the only valid c that the attacker can produce has the real transaction
tx, because a different transaction tx' requires the attacker to forge
the MAC. Since the user waits for confirmation, the first c in the
blockchain fulfilling conditions 1 and 2 has been created by the user.

Even if classic_pk is known, this is no less secure than "classic
spending", because we require an ECDSA signature on tx.

I'm pretty confident that I'm not overlooking an obvious attack. If I'm
wrong then please describe exactly the steps of the user and the
attacker. 

Best,
Tim 


On Thu, 2018-01-25 at 01:09 +0100, Natanael wrote:
> 
> Den 25 jan. 2018 00:22 skrev "Tim Ruffing via bitcoin-dev"  e...@lists.linuxfoundation.org>:
> > I think you misread my second proposal. The first step is not only
> > to
> > publish the hash but to publish a *pair* consisting of the hash and
> > the
> > transaction.
> > 
> > If the attacker changes the transaction on the wire, the user does
> > not
> > care and will try again.
> 
> I guess I assumed you meant it otherwise because I didn't assume you
> intended a commitment to the full transaction just without the
> asymmetric key material. 
> 
> You could treat it the same way as in my suggestion, let it expire
> and prune it if the key material isn't published in time. 
> 
> However... A sufficiently powerful attacker can deploy as soon as he
> sees your published signature and key, delay its propagation to the
> miners, force expiration and then *still* repeat the attack with his
> own forgery. 
> 
> Honestly, as long as we need to allow any form of expiry + relying on
> publication of the vulnerable algorithms result for verification, I
> think the weakness will remain. 
> 
> No expiration hurts in multiple ways like via DoS, or by locking in
> potentially wrong (or straight up malicious) transactions.
> 
> ---
> 
> There's one way out, I believe, which is quantum safe Zero-knowledge
> proofs. Currently STARK:s are one variant presumed quantum safe. It
> would be used to completely substitute the publication of the public
> key and signatures, and this way we don't even need two-step
> commitments. 
> 
> It does however likely require a hardfork to apply to old
> transactions. (I can imagine an extension block type softfork method,
> in which case old UTXO:s get locked on the mainchain to create
> equivalent valued extension block funds.)
> 
> Without practical ZKP,  and presuming no powerful QC attackers with
> the ability to control the network (basically NSA level attackers), I
> do think the Fawkes signature scheme is sufficient. Quantum attacks
> are likely to be very expensive anyway, for the foreseeable future. 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing via bitcoin-dev]

On Wed, 2018-01-24 at 19:51 +0100, Natanael wrote:
> 
> That's not the type of attack I'm imagining. Both versions of your
> scheme are essentially equivalent in terms of this attack. 
> 
> Intended steps: 
> 1: You publish a hash commitment. 
> 2: The hash ends up in the blockchain. 
> 3: You publish the transaction itself, and it matches the hash
> commitment. 
> 4: Because it matches, miners includes it. It's now in the
> blockchain. 

I think you misread my second proposal. The first step is not only to
publish the hash but to publish a *pair* consisting of the hash and the
transaction.

If the attacker changes the transaction on the wire, the user does not
care and will try again.

By the way: As described here, everybody could do this first step and
flood the blockchain with it. We cannot immediately subtract a fee,
because it's not clear that some transaction will take place at all. So
we need to take the fee from somewhere else or do something else to
prevent spam. But that's entirely different issue...
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing via bitcoin-dev]

On Wed, 2018-01-24 at 13:51 +0100, Natanael via bitcoin-dev wrote:
> Sidenote: There's a risk here with interception, insertion of a new
> commitment and getting the new transaction into the blockchain first.
> However, I would suggest a mining policy here were two known
> conflicting transactions with commitments are resolved such that the
> one with the oldest commitment wins. How to address detection of
> conflicting transactions with commitments older than confirmed
> transactions isn't obvious. Some of these may be fully intentional by
> the original owner, such as a regretted transaction.

Okay, I think my proposal was wrong...

This looks better (feel free to break again):
1. Commit (H(classic_pk, tx), tx) to the blockchain, wait until confirmed
2. Reveal classic_pk in the blockchain

Then the tx in the first valid commitment wins. If the attacker
intercepts classic_pk, it won't help him. He cannot create the first
valid commitment, because it is created already. (The reason is that
the decommitment is canonical now; for all commitments, the
decommitment is just classic_pk.)

By the way, maybe I'm stating the obvious but Taproot (or similar) is
indeed very nice for outputs generated in the future: You can have a
path for a classical signature scheme and a path for a quantum-secure
scheme.

Best,
Tim
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing via bitcoin-dev]

On Wed, 2018-01-24 at 01:52 +, Andrew Poelstra via bitcoin-dev
wrote:
> 
> > They are. But I don't believe that is relevant; the attacker would
> > simply steal the coins on spend.
> 
> 
> Then the system would need to be hardforked to allow spending through
> a
> quantum-resistant ZKP of knowledge of the hashed public key. I expect
> that in a post-quantum world there will be demand for such a fork,
> especially if we came into such a world through surprise evidence of
> a discrete log break.
> 

There are simpler ways using consensus / waiting instead of zero-
knowledge, e.g., 

1. Include H(classic_pk, tx) to blockchain, wait until confirmed.
2. Reveal classic_pk, tx

This is taken from my tweet [1] but now I realize that these are
basically Guy Fawkes "signatures" [2]. Joseph Bonneau and Andrew Miller
 [3] had the idea to use this for cryptocurrency without asymmetric
cryptography.

Best,
Tim

[1] https://twitter.com/real_or_random/status/948226830166786048
[2] https://www.cl.cam.ac.uk/~rja14/Papers/fawkes.pdf
[3] http://www.jbonneau.com/doc/BM14-SPW-fawkescoin.pdf

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Bitcoin Assistance

[Tim Ruffing via bitcoin-dev]

Oh nevermind. I had a look at the history but missed that commit and
assumed the change was introduced when adding the text to
contrib/debian/copyright

Tim

On Wed, 2017-09-27 at 22:21 +, Gregory Maxwell wrote:
> On Wed, Sep 27, 2017 at 9:54 PM, Tim Ruffing via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > Also, even the old version lists some icons "based on Stephan
> > Hutchings
> > Typicons" as "License: MIT", which could be a violation of CC BY-SA 
> > if
> > I'm not mistaken.
> 
> Relicensed by the copyright holder:
> 
> https://github.com/bitcoin/bitcoin/commit/dae0a89d4b66f08c83ccc8c20cf
> 37521084b6257
> 
> (For future reference, git log -p  makes it easy to go find
> where some string was last in a file, so you can look at the commit
> that changed it.)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Bitcoin Assistance

[Tim Ruffing via bitcoin-dev]

On Wed, 2017-09-27 at 17:20 -0400, Cory Fields via bitcoin-dev wrote:
> > Creative Commons Attribution Share Alike 3.0
> 
> I didn't manage to find any CC-licensed files. The match probably
> comes from our gui svg icons, which contain an xml tag with a link to
> creativecommons.org. This seems to be the default behavior of
> inkscape, which was used to create those icons. Any icons that we
> have not created ourselves are listed in contrib/debian/copyright
> (they're all expat/public domain).

This is somewhat weird. Back in 2014, most of icons were listed as
"CC BY-SA" (which is the correct license according to the original
source):
https://github.com/bitcoin/bitcoin/blob/31aac02446472ec5bfc4676ab190ec9d37056503/doc/assets-attribution.md

However the current docs list them as "Expat". A mistake?
https://github.com/bitcoin/bitcoin/blob/master/contrib/debian/copyright

Also, even the old version lists some icons "based on Stephan Hutchings
Typicons" as "License: MIT", which could be a violation of CC BY-SA if
I'm not mistaken.

Best,
Tim


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Properties of an ideal PoW algorithm & implementation

[Tim Ruffing via bitcoin-dev]

On Tue, 2017-04-18 at 12:34 +0200, Natanael via bitcoin-dev wrote:
> To prove that an implementation is near optimal, you would show
> there's a minimum number of necessary transistor activations per
> computed hash, and that your implementation is within a reasonable
> range of that number. 

I'm not an expert on lower bounds of algorithms but I think proving
such properties is basically out of reach for mankind currently.

> 
> We also need to show that for a practical implementation you can't
> reuse much internal state (easiest way is "whitening" the block
> header, pre-hashing or having a slow hash with an initial whitening
> step of its own). This is to kill any ASICBOOST type optimization.
> Performance should be constant, not linear relative to input size. 

Yes, a reasonable thing in practice seems to use a slower hash function
(or just iterating the hash function many times), see also this thread:
 https://twitter.com/Ethan_Heilman/status/850015029189644288 .

PoW verification will still be fast enough. That's not the bottleneck
of block verification anyway.

Also, I don't agree that a PoW function should not rely on memory.
Memory-hard functions are the best we have currently.


Tim
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Transaction signalling

[Tim Ruffing via bitcoin-dev]

I don't have an opinion on whether signaling is a good idea in general.

However I don't think that using addresses is a good idea, because this
has privacy implications. For example, it makes it much easier to link
the addresses, e.g., inputs with change address. (The change address
votes for the same proposal as the input address.)

Tim

On Tue, 2017-04-18 at 18:07 +, Christian Decker via bitcoin-dev
wrote:
> I really like the idea of extending signalling capabilities to the
> end-users. It gives stakeholders a voice in the decisions we take in
> the network, and are a clear signal to all other involved parties. It
> reminds me of a student thesis I supervised some time ago [1], in
> which we explored various signalling ideas.
> 
> I think we have a number of fields that may be used for such a
> signalling, e.g., OP_RETURN, locktime, and output scripts. I think
> OP_RETURN is probably not the field you'd want to use though since it
> adds data that needs to be transferred, stored for bootstrap, and
> outputs in the UTXO would need to be tagged with additional
> information. Locktime has the advantage of being mostly a freeform
> field for values in the past, but it clashes with other uses that may
> rely on it. Furthermore, it is the transaction creator that specifies
> the locktime, hence the signal trails one hop behind the current
> owner, i.e., the actual stakeholder.
> 
> I think probably the best field to signal would be the output
> script. It is specified by the recipient of the funds, i.e., the
> current owner, and is already stored in the UTXO, so a single pass
> can
> tally up the votes. We could for example use the last 4 bits of the
> pubkey/pubkeyhash to opt in (3 leading 0 bits) and the vote (0/1
> depending on the stakeholders desired signal). We'd need to define
> similar semantics for other script types, but getting the standard
> scripts to be recognized should be simple.
> 
> In the spirit of full disclosure I'd like to also mention some of the
> downsides of voting this way. Unlike the OP_RETURN proposal, users
> that do not intend to signal will also be included in the tally. I'd
> expect the signals of these users to be random with a 50% chance of
> either outcome, so they should not influence the final result, but
> may
> muddy the water depending on what part of the population is
> signalling. The opt-in should make sure that the majority of votes
> are
> actually voluntary votes, and not just users that randomly select a
> pubkey/pubkeyhash, and can be adjusted as desired, though higher
> values require more grinding on behalf of the users.
> 
> The grinding may also exacerbate some problems we already have with
> the HD Wallet lookahead, since we now skip a number of addresses, so
> we should not require too many opt-in bits.
> 
> So there are some problems we'd need to tackle, but I'm really
> excited
> about this, as it could provide data to make informed decisions, and
> should put an end to the endless speculation about the will of the
> economic majority.
> 
> Cheers,
> Christian
> 
> [1] http://pub.tik.ee.ethz.ch/students/2015-HS/SA-2015-30.pdf
> ___
> 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] Inquiry: Transaction Tiering

[Tim Ruffing via bitcoin-dev]

(I'm not a lawyer...)

I'm not sure if I can make sense of your email.

On Mon, 2017-03-20 at 20:12 +, Martin Stolze via bitcoin-dev wrote:
> As a participant in the economy in general and of Bitcoin in
> particular, I desire an ability to decide where I transact. The
> current state of Bitcoin does not allow me to choose my place of
> business. As a consequence, I try to learn what would be the best way
> to conduct my business in good faith. [2]

Ignoring the rest, I don't think that the physical location /
jurisdiction of the miner has any legal implications for law applicable
to the relationship between sender and receiver of a payment. 

This is not particular to Bitcoin. We're both in Germany (I guess).
Assume we have a contract without specific agreements and I pay you in
Icelandic kronur via PayPal (in Luxembourg) and my HTTPS requests to
PayPal went via Australia and the US. Then German law applies to our
contract, nothing in the middle can change that.

Also ignoring possible security implications, there is just no need for
a mechanism that enables users to select miners. I claim that almost
nobody cares who will mine a transaction, because it makes no technical
difference. If you don't want a specific miner to mine your
transaction, then don't use Bitcoin.

Tim
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Currency/exchange rate information API

[Tim Ruffing via bitcoin-dev]

On Mon, 2017-03-06 at 17:30 -0500, Tim Ruffing via bitcoin-dev wrote:
> 
> That works but a standardized way of indicating that piece of
> information to the client is useful. Then the client can display a
> "connection status" to the user, e.g., an "possible out-of-date"
> warning like the warning sign in the Qt GUI when Bitcoin Core is
> catching up the network.

Wait, forget this reply, I mixed up the two issues of keepalive and
definition of low, high etc... -.-

1. Keepalive for longpolling:
As I said, this can be useful for an out-of-date warning. I don't know
if this is better solved with TCP keepalive or on the higher layer.

2. Definition of low, high:
My feeling is that there is nothing wrong with providing exact
definitions in the BIP, i.e.., giving up the flexibility does not too
hurt much. However all of this is a minor issue after all.

Tim

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Currency/exchange rate information API

[Tim Ruffing via bitcoin-dev]

On Mon, 2017-03-06 at 22:14 +, Luke Dashjr wrote:
> It would be a privacy leak to request only the specific timestamps,
> but I 
> suppose many wallets lack even basic privacy to begin with.
> 
> To address the bounds issue, I have specified that when from/to don't
> have an 
> exact record, that the previous/next (respectively) is provided.
> 
> Hopefully this addresses both concerns?
Yes, that solves it. You're right with the privacy concern however.

> 
> > In the current draft the client or the server cannot specify
> > granularity. If the clients only wants one value per day but for an
> > entire year, then it has to perform many requests or download and
> > process a very large response.
> 
> That's what the "timedelta" field solves, no?
> If you want one value per day, you'd put 86400.
Oh sure, I had overlooked that.

> 
> > Also, I think it's okay that the type field allows for arbitrary
> user-
> > defined values, but it should also have some precisely defined
> values
> > (e.g. the mentioned low/high/open/close/typical).
> > For example, it's not clear currently what "low" means for a
> timestamp
> > (as opposed to a time span). Is it the low of the entire day or the
> low
> > since the previous record or something different?
> 
> Is it not sufficient for the server to specify this in the
> description of the 
> given currency-pair feed?
That works but a standardized way of indicating that piece of
information to the client is useful. Then the client can display a
"connection status" to the user, e.g., an "possible out-of-date"
warning like the warning sign in the Qt GUI when Bitcoin Core is
catching up the network.


Tim
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Currency/exchange rate information API

[Tim Ruffing via bitcoin-dev]

On Mon, 2017-03-06 at 16:54 -0500, Tim Ruffing via bitcoin-dev wrote:
> 
> > Pushing is what longpolling does.
> > 
> 
> That makes a lot of sense, yes.
> 
Forgot one thing:
For longpolling, maybe we would like to have the possibility to request
some periodic message from the server. Otherwise clients cannot
distinguish between the situations 1. "value is still in the requested
bounds (minrate, maxrate)" and 2. "connection has dropped". So the user
may take a wrong decision because  he assumed that the value is still
in bounds holds but actually the server has died.

Tim 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Currency/exchange rate information API

[Tim Ruffing via bitcoin-dev]

I'm not sure if a BIP is the right thing in that case, given that the
provided functionality is not special to Bitcoin and can be used in
other contexts as well. 

But ignoring this, the server should be authenticated at a
minimum. Otherwise manipulating exchange rates seems to be a nice
way for the attacker on the wire to make money...

Apart from that, my feeling is that it could be simplified. Is 
longpolling useful? And is the historical rate thing really necessary
for typical applications?

If yes, the client should be allowed to decide on which time scale the
data should be. (tick, min, hour, day, ...) That goes together with
clearly defining the type field (something like low, high, open, close,
but without flexibility). Think of a candle-stick chart basically.

Also, pushing may be more appropriate for "current" rates than polling.
Then no polling interval is necessary. On the other hand, this adds
complexity in other places, e.g., state.

Tim  

On Sat, 2017-03-04 at 08:27 +, Luke Dashjr via bitcoin-dev wrote:
> Investigating what it would take to add fiat currency information to
> Bitcoin 
> Knots, I noticed Electrum currently has many implementations, one for
> each 
> exchange rate provider, due to lack of a common format for such data.
> 
> Therefore, I put together an initial draft of a BIP that could
> standardise 
> this so wallets (or other software) and exchange rate providers can
> simply 
> interoperate without a lot of overhead reimplementing the same thing
> many 
> ways.
> 
> One thing I am unsure about, is that currently this draft requires
> using XBT 
> (as BTC) for Bitcoin amounts. It would seem nicer to use satoshis,
> but those 
> don't really have a pseudo-ISO currency code to fit in nicely...
> 
> Current draft here:
> https://github.com/luke-jr/bips/blob/bip-xchgrate/bip-xchgrate.me
> diawiki
> 
> Thoughts? Anything critical missing? Ways to make the interface
> better?
> 
> Luke
> ___
> 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

[Tim Ruffing via bitcoin-dev]

On Fri, 2017-02-24 at 16:18 +0100, Aymeric Vitte via bitcoin-dev wrote:
> Not sure that you really read deeply what I sent, because stating
> that
> hashing files continuously instead of hashing the intermediate steps
> just gives more latitude to the attacker can't be true when the
> attacker
> has absolutely no control over the past files
What prevents the attacker to provide different past files when talking
to parties who are still in the initial state?

Then the question is: knowing the hash state, is it as easy to find a
> collision between two files that will be computed in the next round
> than
> finding a collision between two files only?
With the original usage of the hash function, the hash state is always
the initial state. Now that the attacker has some control over the hash
state even. In other words, if the original use of the hash function
was vulnerable, then your scheme is vulnerable for the initial state.

Concrete attack: If you can find x != y with H(x) = H(y), then you can
also find m, x != y, with H(m||x) = H(m||y), just by setting m = "". 

Not sure if this is the right place to discuss that issue though...

Best,
Tim
___
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

[Tim Ruffing via bitcoin-dev]

On Fri, 2017-02-24 at 00:57 +0100, Aymeric Vitte via bitcoin-dev wrote:
> 
> I have not worked on this since some time, so that's just thoughts,
> but maybe it can render things much more difficult
> than   computing two files until the same hash is found
> 

You basically rely on the idea that specific collisions are more
difficult to find. This trick or similar tricks will not help. (And
actually, the more files you add to the hash, the more freedom you give
the attacker.)

Even if certain collisions are more difficult to find today (which is
certainly true), the general rule is that someone will prove you wrong
in a year.

Even if ignore security entirely, switching to new hash function is
much simpler trying to fix the usage of a broken hash function.

Relying on SHA1 is hopeless. We have to get rid of it.

Best,
Tim



___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Implementing Covenants with OP_CHECKSIGFROMSTACKVERIFY

[Tim Ruffing via bitcoin-dev]

Not a covenant but interesting nevertheless: _One_ of OP_CAT and
OP_CHECKSIGFROMSTACKVERIFY alone is enough to implement "opt-in miner
takes double-spend" [1]:

You can create an output, which is spendable by everybody if you ever
double-spend the output with two different transactions. Then the next
miner will probably take your money (double-spending against your two
or more contradicting transactions again).

If you spend such an output, then the recipient may be willing to
accept a zero-conf transaction, because he knows that you'll lose the
money when you attempt double-spending (unless you are the lucky
miner). See the discussion in [1] for details. 

The implementation using OP_CHECKSIGFROMSTACKVERIFY is straight-
forward. You add a case to the script which allows spending if two
valid signatures on different message under the public key of the
output are given.

What is less known I think:
The same functionality can be achieved in a simpler way just using
OP_CAT, because it's possible to turn Bitcoin's ECDSA to an "opt-in
one-time signature scheme". With OP_CAT, you can create an output that
is only spendable using a signature (r,s) with a specific already fixed
first part r=x_coord(kG). Basically, the creator of this output commits
on r (and k) already when creating the output. Now, signing two
different transaction with the same r allows everybody to extract the
secret key from the two signatures.

The drawbacks of the implementation with OP_CAT is that it's not
possible to make a distinction between legitimate or illegitimate
double-spends (yet to be defined) but just every double-spend is
penalized. Also, it's somewhat hackish and the signer must store k (or
create it deterministically but that's a good idea anyway).

[1] 
https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07122.html

Best,
Tim

On Thu, 2016-11-03 at 07:37 +, Daniel Robinson via bitcoin-dev
wrote:
> Really cool!
> 
> How about "poison transactions," the other covenants use case
> proposed by Möser, Eyal, and Sirer? (I think
> OP_CHECKSIGFROMSTACKVERIFY will also make it easier to check fraud
> proofs, the other prerequisite for poison transactions.)
> 
> Seems a little wasteful to do those two "unnecessary" signature
> checks, and to have to construct the entire transaction data
> structure, just to verify a single output in the transaction. Any
> plans to add more flexible introspection opcodes to Elements, such as
> OP_CHECKOUTPUTVERIFY?
> 
> Really minor nit: "Notice that we have appended 0x83 to the end of
> the transaction data"—should this say "to the end of the signature"?
> 
> On Thu, Nov 3, 2016 at 12:28 AM Russell O'Connor via bitcoin-dev  coin-...@lists.linuxfoundation.org> wrote:
> > Right.  There are minor trade-offs to be made with regards to that
> > design point of OP_CHECKSIGFROMSTACKVERIFY.  Fortunately this
> > covenant construction isn't sensitive to that choice and can be
> > made to work with either implementation of
> > OP_CHECKSIGFROMSTACKVERIFY.
> > 
> > On Wed, Nov 2, 2016 at 11:35 PM, Johnson Lau  wrote:
> > > Interesting. I have implemented OP_CHECKSIGFROMSTACKVERIFY in a
> > > different way from the Elements. Instead of hashing the data on
> > > stack, I directly put the 32 byte hash to the stack. This should
> > > be more flexible as not every system are using double-SHA256
> > > 
> > > https://github.com/jl2012/bitcoin/commits/mast_v3_master
> > > 
> > > 
> > > 
> > > > On 3 Nov 2016, at 01:30, Russell O'Connor via bitcoin-dev  > > > oin-...@lists.linuxfoundation.org> wrote:
> > > > 
> > > > Hi all,
> > > > 
> > > > It is possible to implement covenants using two script
> > > > extensions: OP_CAT and OP_CHECKSIGFROMSTACKVERIFY.  Both of
> > > > these op codes are already available in the Elements Alpha
> > > > sidechain, so it is possible to construct covenants in Elements
> > > > Alpha today.  I have detailed how the construction works in a
> > > > blog post at  > > > lements-alpha.html>.  As an example, I've constructed scripts
> > > > for the Moeser-Eyal-Sirer vault.
> > > > 
> > > > I'm interested in collecting and implementing other useful
> > > > covenants, so if people have ideas, please post them.
> > > > 
> > > > If there are any questions, I'd be happy to answer.  
> > > > 
> > > > -- 
> > > > Russell O'Connor
> > > > ___
> > > > 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