Tim Ruffing [ARCHIVE]

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2014-08-06 to 2023-05-14
💬 Posted a total of 47 messages
📚 Participated in the following categories: Bitcoin-development, bitcoin-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Public Key

npub1cmt6gqyfw3sdngkq0wadtpe3kmgyyeld6ad0g2h5tar3kpzcrmpqddwkls

Profile Code

nprofile1qqsvd4ayqzyhgcxe5tq8hwk4sucmd5zzvlkawkh59t6973cmq3vpasspzpmhxue69uhkummnw3ezumrpdejq9xv5sx

Publishing to

nostr.land

Author Public Key

npub1cmt6gqyfw3sdngkq0wadtpe3kmgyyeld6ad0g2h5tar3kpzcrmpqddwkls

Show more details

Last Notes

2023-06-07 23:11:21 GMT

- reply

📅 Original date posted:2022-07-08
📝 Original message: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.
>

2023-06-07 18:31:00 GMT

- reply

📅 Original date posted:2021-03-21
📝 Original message: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 <crypto at timruffing.de>
> > 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:30:59 GMT

- reply

📅 Original date posted:2021-03-20
📝 Original message: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

2023-06-07 18:30:57 GMT

- reply

📅 Original date posted:2021-03-23
📝 Original message: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).

2023-06-07 18:23:25 GMT

- reply

📅 Original date posted:2020-03-24
📝 Original message: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 +0000, 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 at 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
> >
> > <pre>
> > BIP:
> > Title: Deterministic Entropy From BIP32 Keychains
> > Author: Ethan Kosakovsky ethankosakovsky at protonmail.com
> > Comments-Summary: No comments yet.
> > Comments-URI:
> > Status: Proposed
> > Type: Standards Track
> > Created: 2020-03-20
> > License: BSD-2-Clause
> > OPL
> > </pre>
> >
> > ==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 BIP39 mnemonic
> >
> > 2
> >
> > 128
> >
> > 12 word Electrum mnemonic
> >
> > 3
> >
> > 256
> >
> > 24 word Electrum mnemonic
> >
> > 4
> >
> > 256
> >
> > WIF for Bitcoin Core
> >
> > 5
> >
> > 256
> >
> > 25 word Monero mnemonic
> >
> > Entropy is calculated from the HMAC-SHA512(key=k, msg='bip-entropy-
> > from-bip32') of the derived 32 byte private key (k). Entropy is
> > taken from the result according to the number of bits required.
> > This entropy can then be used as input to derive a mnemonic, wallet
> > etc according to the`type` specified.
> >
> > ==Compatibility==
> >
> > In order to maintain the widest compatibility, the input to this
> > function is a BIP32 seed, which may or may not have been derived
> > from a BIP39 like mnemonic scheme. This maintains the original
> > motivation that one backup can store any and all child derivation
> > schemes depending on the user's preference or hardware signing
> > devices. For example, devices that store the HD seed as a BIP39
> > mnemonic, Electrum seed, or BIP32 root key would all be able to
> > implement this standard.
> >
> > ==Discussion==
> >
> > This proposal could be split into multiple discrete BIPs in the
> > same way that BIP32 described the derivation mechanics, BIP39 the
> > input encoding with mnemonics, and the derivation paths like BIP44,
> > BIP49 and BIP84. This has been avoided to reduce complexity. The
> > resulting private key processed with HMAC-SHA512 and truncated as
> > necessary. HMAC-SHA512 was chosen because it may have better
> > compatibility in embedded devices as it's already required in
> > devices supporting BIP32.
> >
> > ==Test Vectors==
> >
> > ===Test case 1===
> >
> > MASTER BIP39 SEED INPUT: angle fabric town envelope music diet bind
> > employ giant era attitude exit final oval one finger decorate pair
> > useless super method float toddler dance
> > MASTER BIP32 ROOT KEY:
> > xprv9s21ZrQH143K2xNoceSiUtx8Wb8Fcrk9FUfzD3MLT4eFx5NbBuof9Mwrf7CCbfG
> > JNehNRHvrXnWvy9FtWVaeNggsSKT57GNk7jpk1PRzZDp
> > PATH: m/83696968'/0'/0'
> > BITS REQUIRED: 128
> >
> > DERIVED CHILD
> > WIF=L3cefeCHyo8jczVjckMxaiPBaPUunc3D8CsjRxYbYp3FhasGpsV3
> > DERIVED CHILD
> > k=bed343b04ba0216d9eeebff0366b61c4179d90d44b61c716ef6d568836ba4d23
> > CHILD ENTROPY=6458698fae3578b48a64124ea3514e12
> > CONVERT ENTROPY TO
> > WIF=KwDiBf89QgGbjEhKnhXJuH7T2Vv72UKQA8KRkmNwVFS2znAS5xb9
> > CHILD BIP39 MNEMONIC=gold select glue fragile fiscal fog civil
> > liquid exchange box fatal caught
> > CHILD BIP39
> > SEED=2a2720e5590d4ec3140e51ba1b0b0a5183222c1668977c8a57572b0ea55d23
> > 8cd8e899b3b1870e48894ca837e41e5d0db07554715efb21556fdde27f9f7ba153
> > CHILD BIP32 ROOT
> > KEY=xprv9s21ZrQH143K2ZH5qacptquLGvcYpHSNeyFVCU8Ur4u9kocajbBgcaCbHkG
> > bwDsBR661H29F54j5mz14kwXbY9PZKdNRdjgRcGfshBK9XXb
> >
> > ===Test case 2===
> >
> > MASTER BIP39 SEED INPUT: angle fabric town envelope music diet bind
> > employ giant era attitude exit final oval one finger decorate pair
> > useless super method float toddler dance
> > MASTER BIP32 ROOT KEY:
> > xprv9s21ZrQH143K2xNoceSiUtx8Wb8Fcrk9FUfzD3MLT4eFx5NbBuof9Mwrf7CCbfG
> > JNehNRHvrXnWvy9FtWVaeNggsSKT57GNk7jpk1PRzZDp
> > PATH: m/83696968'/1'/0'
> > BITS REQUIRED: 256
> >
> > DERIVED CHILD
> > WIF=L1zCbtnDWUN4vJA3De4sxmJnoRim57CQUuBb4KBoRNs2EMEq2Brg
> > DERIVED CHILD
> > k=8e3ca6054a6303f4a6a1bcbda6134c9802f4f0a0d76b0ee6b69b06b1e80b2192
> > CHILD
> > ENTROPY=ec4e2f7e2c3fca9a34fa29747bf8ba0ab7f05136f37e134e2457e9e5363
> > 9670b
> > CONVERT ENTROPY TO
> > WIF=L594JSCygt2wBaB9mCpXjiLkkxkEojpBdNXG8UrrdLd2LvPBRMUs
> > CHILD BIP39 MNEMONIC=unable imitate test flash witness escape
> > stadium early inner thank company betray lecture chuckle swift hurt
> > battle illness bicycle stable fat bronze order high
> > CHILD BIP39
> > SEED=73509b0e847ee66bddeb098a55063d73e8c6dd5f1c1db6969c668bb54c19bd
> > e6eae8acc29a81118d1d9719fa1bc620fee7edd7c15a17bcaf70b0fdfc0c0c3803
> > CHILD BIP32 ROOT
> > KEY=xprv9s21ZrQH143K4PfLyyjYLVmKbnUTNFK6Y7jPKWfRZB3iSw1Gy9qowEzkYHf
> > etVabfmjHEEPrcTJbh7chae33Sm9uAjuXzhSL6Li8dcwM9Bm
> >
> > ===Test case 3===
> >
> > MASTER BIP39 SEED INPUT: angle fabric town envelope music diet bind
> > employ giant era attitude exit final oval one finger decorate pair
> > useless super method float toddler dance
> > MASTER BIP32 ROOT KEY:
> > xprv9s21ZrQH143K2xNoceSiUtx8Wb8Fcrk9FUfzD3MLT4eFx5NbBuof9Mwrf7CCbfG
> > JNehNRHvrXnWvy9FtWVaeNggsSKT57GNk7jpk1PRzZDp
> > PATH: m/83696968'/4'/0'
> > BITS REQUIRED: 256
> >
> > DERIVED CHILD
> > WIF=KwdD5PYnCU3xQDfFJ6XBf6UDaLrTUxrKmBpdjRuuavWyqAQtpaA2
> > DERIVED CHILD
> > k=0c169ce2c17bea08512a7519769e365242a1562bd63c4c903daef516000efbf2
> > CHILD
> > ENTROPY=25573247f8a76799f7abc086b9286b5a7ccb03cb8d3550f48ac1e71d908
> > 32974
> > CONVERT ENTROPY TO
> > WIF=KxUJ8VzMk7uWDEcwYjLRzRMGE6sSpwCfQxkE9GEwAvXhFSDNba9G
> > CHILD BIP39 MNEMONIC=census ridge music vanish island smooth team
> > job mammal sing bracket reject smile limit comfort pluck extend
> > picture race soda suit dose place obtain
> > CHILD BIP39
> > SEED=4e5c82be6455ecf0884d9475435e29a9afb9acf70b07296d7e5039c866e4d5
> > 4647706918b9d14909dfbd7071a4b7aee8a4ad0ac2bf48f0a09a8899dd28564418
> > CHILD BIP32 ROOT
> > KEY=xprv9s21ZrQH143K2kekJsK9V6t4ZKwHkY1Q3umxuaAhdZKGxCMpHiddLdYUQBo
> > ynszpwnk5upoC788LiT5MZ5q1vUABXG7AMyZK5UjD9iyL7Am
> >
> > ==References==
> >
> > BIP32, BIP39
> >
> > ==Copyright==
> >
> > This BIP is dual-licensed under the Open Publication License and
> > BSD 2-clause license.
> >
> > bitcoin-dev mailing list
> > bitcoin-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:23:14 GMT

- reply

📅 Original date posted:2020-03-24
📝 Original message: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

2023-06-07 18:23:13 GMT

- reply

📅 Original date posted:2020-03-22
📝 Original message: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

2023-06-07 18:23:12 GMT

- reply

📅 Original date posted:2020-03-22
📝 Original message: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

2023-06-07 18:23:11 GMT

- reply

📅 Original date posted:2020-03-21
📝 Original message: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 +0000, 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 (birthday collision!). When verifying e instead, the
attack is successful if the attacker predicts the fault correctly. But
I guess if faults can be made very likely, there's no hope anyway.

2023-06-07 18:23:02 GMT

- reply

📅 Original date posted:2020-02-24
📝 Original message: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
> <bitcoin-dev at lists.linuxfoundation.org> 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 at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:23:01 GMT

- reply

📅 Original date posted:2020-02-24
📝 Original message: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

2023-06-07 18:14:34 GMT

- reply

📅 Original date posted:2018-09-07
📝 Original message:On Fri, 2018-09-07 at 02:31 +0000, 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:
A M B
-- 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 covered
> > by the MAC.
>
> It's AAD data in the mac, unless I misunderstand the protocol.
Oh nevermind.
> Personally I'd prefer that we used a ciphersuite that effectively
> "rekeyed" every message-- along the lines of the constructions
> described https://blog.cr.yp.to/20170723-random.html Unfortunately
> I
> was unable to find _any_ well analyized authenticated encryption
> mode
> that has the fast erasure property. It's too bad because it would
> be
> trivial to adhoc one (e.g. use the extra 32 bytes from the poly1305
> chacha run to update the keys for the next message).
That adhoc construction is a very interesting idea. Hm... Just fyi, the
closest that comes to my mind is:
https://core.ac.uk/download/pdf/20880831.pdf
> The norm in Bitcoin is to ignore messages you don't know how to parse
> anyways, so there is no complexity that arises from "may negotiate"
> itself-- only from actually making use of that possibility in the
> future, so the merits of any particular usage could be decided when
> something wants to actually use it. The purpose of pointing out "may
> negotiate" is, I think, primarily to avoid a debate about who would
> assign numbers from this limited space in the future-- and the answer
> just is that they're implementation defined (e.g. by the BIPs using
> them).
Yeah, my point was not to write the entire list in stone. That was not
really clear from my message, sorry. Of course, new message types can
be added later. But I don't see a big advantage in allowing both ASCII
strings and short IDs. So I wanted to say that the usage of short IDs
should be written stone.
On Fri, 2018-09-07 at 10:34 +0200, Jonas Schnelli wrote:
>
> > 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.)
>
> I think a new message type that could contain message + pad would be
> trivial.
> Would this again be to obfuscate traffic patterns? Anti DPI is not
> the scope of BIP151.
Well, it's indeed to obfuscate traffic patterns but primarily for
confidentiality. If I see the length of the message, I can guess the
message type fairly well for example. (That's not no matter if my goal
as an attacker is to break your privacy or to censor your connection.
Of course more confidentiality helps also against DPI/censorship but
that was not my point here.)
> I was under the false impression that it is obvious to disconnect in
> those cases.
Yeah I think it's by far the most natural thing to do but it may be
better to make it explicit.
Tim

2023-06-07 18:14:33 GMT

- reply

📅 Original date posted:2018-09-06
📝 Original message: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 at 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 of 10 seconds." What if I receive
too many re-keying requests? Nothing or should I raise the DoS score?
- "The Re-Keying must be done after every 1GB of data sent or received" Hm, every peer updates its
own sending key, so this should just read "sent" instead of "sent or received"?
Pseudocode could probably help here.
[1] https://eprint.iacr.org/2014/043.pdf

2023-06-07 18:13:56 GMT

- reply

📅 Original date posted:2018-08-06
📝 Original message: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,
>

2023-06-07 18:13:40 GMT

- reply

📅 Original date posted:2018-07-08
📝 Original message: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

2023-06-07 18:12:35 GMT

- reply

📅 Original date posted:2018-06-06
📝 Original message: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
> <bitcoin-dev at lists.linuxfoundation.org> 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,
>

2023-06-07 18:12:34 GMT

- reply

📅 Original date posted:2018-06-06
📝 Original message: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

2023-06-07 18:11:10 GMT

- reply

📅 Original date posted:2018-03-12
📝 Original message: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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:10:40 GMT

- reply

📅 Original date posted:2018-02-15
📝 Original message: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.

2023-06-07 18:10:39 GMT

- reply

📅 Original date posted:2018-02-15
📝 Original message: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

2023-06-07 18:10:38 GMT

- reply

📅 Original date posted:2018-02-15
📝 Original message: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
schemes we use today remain secure, people can and will continue to
perform conventional transactions. Ideally, people will need a recovery
protocol only for those UTXOs which they haven't touched for years and
have forgotten to convert to PQ in time.
You mentioned confirmation time. A nice thing is that the above
protocol does not double confirmation times. The sender needs to wait
for confirmation of the commitment. But as soon as the commitment is
confirmed, double-spending is excluded already, because the sender is
committed to the transaction. So the recipient does not need to wait
for confirmation of the decommitment. As soon as the recipient sees the
decommitment, everything is good. (If the decommitment is not
confirmed, the recipient can just re-broadcast it.)
In practice, we could even go further and call the transaction done
after the commitment is confirmed and the sender sends the data for the
second step to the recipient off-chain. Only when the recipient wants
to spend the funds again, the recipient will reveal this data.
The fact that double-spending is excluded after the first step is
confirmed, is exactly what makes the protocol secure against quantum
attackers who want to steal the money. As soon as the user reveals the
ECDSA public key, a quantum attacker has access to all secrets: The
attacker knows the preimage of the hash can compute the secret key.
So from this point on, there is no hope that we can distinguish the
honest user from the attacker. But since the correct transaction has
been committed to the blockchain, and cannot be changed anymore, we
don't need to distinguish the honest user from the attacker.
> Either way, would you mind if I included your approach in the
> article,
> with credit? I will seek your review before publishing.
Sure, feel free to include. You don't need to seek my review but I can
certainly have a look if desired.
Tim

2023-06-07 18:10:37 GMT

- reply

📅 Original date posted:2018-02-13
📝 Original message: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 <bitcoin
> -dev at 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 at lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

2023-06-07 18:10:36 GMT

- reply

📅 Original date posted:2018-02-12
📝 Original message: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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 18:10:12 GMT

- reply

📅 Original date posted:2018-01-26
📝 Original message:(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" <bitcoin-d
> ev at 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.

2023-06-07 18:10:10 GMT

- reply

📅 Original date posted:2018-01-24
📝 Original message: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...

2023-06-07 18:10:10 GMT

- reply

📅 Original date posted:2018-01-24
📝 Original message: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

2023-06-07 18:10:09 GMT

- reply

📅 Original date posted:2018-01-24
📝 Original message:On Wed, 2018-01-24 at 01:52 +0000, 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

2023-06-07 18:06:15 GMT

- reply

📅 Original date posted:2017-09-27
📝 Original message: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 +0000, Gregory Maxwell wrote:
> On Wed, Sep 27, 2017 at 9:54 PM, Tim Ruffing via bitcoin-dev
> <bitcoin-dev at 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 <file> makes it easy to go find
> where some string was last in a file, so you can look at the commit
> that changed it.)

2023-06-07 18:06:15 GMT

- reply

📅 Original date posted:2017-09-27
📝 Original message: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

2023-06-07 18:00:30 GMT

- reply

📅 Original date posted:2017-04-19
📝 Original message: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

2023-06-07 18:00:29 GMT

- reply

📅 Original date posted:2017-04-18
📝 Original message: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 +0000, 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 17:57:28 GMT

- reply

📅 Original date posted:2017-03-21
📝 Original message:(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 +0000, 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

2023-06-07 17:56:54 GMT

- reply

📅 Original date posted:2017-03-06
📝 Original message:On Mon, 2017-03-06 at 22:14 +0000, 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

2023-06-07 17:56:54 GMT

- reply

📅 Original date posted:2017-03-06
📝 Original message: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

2023-06-07 17:56:53 GMT

- reply

📅 Original date posted:2017-03-06
📝 Original message:On Mon, 2017-03-06 at 07:09 +0000, Luke Dashjr wrote:
> On Monday, March 06, 2017 5:37:24 AM Tim Ruffing via bitcoin-dev
> wrote:
> > 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...
>
> HTTPS would be used for that. It's not something that needs to be at
> a higher
> layer.
Sure, HTTPS is the way to go. But I think that should be required or at
least noted in the BIP, because people could miss easily, e.g., "I
don't need TLS, all the data is public anyway."
> When displaying historical transactions, it doesn't really make sense
> to use
> the current market rate, but rather the market rate at the time the
> payment
> was made. While wallets might simply cache it with the transaction,
> it would
> be perhaps nicer if it could be automatically restored for seed-only
> recoveries. In any case, if a service/wallet doesn't want to
> provide/use
> historical information, it can simply not implement that part.
>
Having the rate at the time of payment is indeed very useful, yes.
However that requires just a single value per payment, and there is no
query that tells the server "give me the value closest to timestamp t"
or similar.
Of course the client can download and keep a large part of history and
extract the information on its own but I can imagine that not every
clients wants to do that, and also the client does not know in advance
the bounds (from, to) that it must query.
> > 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.
>
> How is the current draft insufficient for this?
>
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.
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?
One has to be careful not to add too much complexity though. As soon as
one moves away from timestamps to something like hours or days, all
kind of issues with timezone, daylight saving time etc. appear. Maybe a
simple way to let the client ask "give me one value for every interval
of 3600 seconds" or similar.
> Pushing is what longpolling does.
>
That makes a lot of sense, yes.
Tim

2023-06-07 17:56:53 GMT

- reply

📅 Original date posted:2017-03-06
📝 Original message: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

2023-06-07 17:56:52 GMT

- reply

📅 Original date posted:2017-03-06
📝 Original message: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 +0000, 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 17:56:38 GMT

- reply

📅 Original date posted:2017-02-24
📝 Original message: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

2023-06-07 17:56:38 GMT

- reply

📅 Original date posted:2017-02-24
📝 Original message: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

2023-06-07 17:54:15 GMT

- reply

📅 Original date posted:2016-11-04
📝 Original message: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/[email protected]/msg07122.html
Best,
Tim
On Thu, 2016-11-03 at 07:37 +0000, 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 <bit
> coin-dev at 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 <jl2012 at xbt.hk> 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 <bitc
> > > > oin-dev at 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 <https://blockstream.com/2016/11/02/covenants-in-e
> > > > 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 at lists.linuxfoundation.org
> > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 15:31:42 GMT

- reply

📅 Original date posted:2015-03-04
📝 Original message:This is great to see.
On Monday 02 March 2015 11:48:24 Andrew Miller wrote:
> One of the main goals of our work is to build a bridge between the
> computer science research community and the cryptocurrency community.
> Many of the most interesting ideas and proposals for Bitcoin come from
> this mailing list and forums/wikis/irc channels, where many academic
> researchers simply don’t know to look!
This is indeed a problem in the research community. Often ideas from here are
just overlooked, and e.g., re-invented or not properly acknowledged. Of
course, this is (in almost all cases) not intentionally. It's just difficult to
keep track of everything.
Your paper is a definitely the right approach to bring the researchers closer
to the Bitcoin community.
Best,
Tim

2023-06-07 15:24:55 GMT

- reply

📅 Original date posted:2014-08-11
📝 Original message:Hmm, you are right. Lightweight clients are an interesting point, we have to
think about a policy for them.
As you said, the worst case is that the tx will not confirm. So the only
possible attack is DoS. For clients that rely on servers it's reasonable to
trust their servers not to perform DoS. (Anyway, the servers could do worse
attacks.)
For SPV-clients (without servers), I'm not sure at the moment. Something like
getUTXO seems to be a possibility. I think even SPV-clients can verify the
validity of the tx that created the input that is designated for mixing. Then
the only remaining reason why it could be invalid is that the input could have
been spent already otherwise. But in this case, only one honest client with
full information would suffice: a signed transaction that spends the money
would convince even SPV-clients that the participant with this inputs tries to
cheat. This transaction could even be provided by lightweight client that got
if from a server; the transaction is signed by the cheating participant
anyway.
Tim
On Monday 11 August 2014 02:30:16 Chris Pacia wrote:
> Actually getUTXO would probably work here as well. It isn't authenticated
> but it should be good enough for this purpose. The worst that would happen
> is the tx doesn't confirm.
>
> On Aug 11, 2014 2:25 AM, "Chris Pacia" <ctpacia at gmail.com> wrote:
> > One issue I do see is the protocol requires participants to check the
> > inputs submitted by others are valid. Lite clients (at least of the p2p
> > variety) cannot perform this check.
> >
> > You could skip the verification part and if the inputs turn out to be
> > invalid then you'll find out when it doesn't confirm. This would problem
> > open the protocol up to dos attacks and prevent part of the "blame" phase
> > from working properly.
> >
> > Alternatively you can have the participants submit the merkle proof for
> > the input. This would require inputs to have at least one confirmation,
> > however.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 648 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20140811/a827a309/attachment.sig>

2023-06-07 15:24:52 GMT

- reply

📅 Original date posted:2014-08-09
📝 Original message:You are raising valid questions and one goal of our posting here is indeed to
discuss exactly these system issues.
On Thursday 07 August 2014 15:00:11 you wrote:
> I think the description at your website leaves out the truly interesting
> part: How do you decentralize this securely?
> - How do Alice, Bob, Charlie and Dave communicate, i.e. which network is
> used for communication and how?
The simplest approach is obviously to use direct connections to a randomly
elected leader, who is also responsible for the broadcasts.
One advantage of CoinShuffle is that the unlinkability between input and
output addresses is guaranteed, no matter which underlying network you use.
(Still, it is a good idea in general to hide your IP address but we can let
the user decide here.)
Of course, there would be other possibilities, such as overlay networks.
Coinmux, a CoinJoin prototype by Michael Pearce (http://coinmux.com/) uses
TomP2P, a distributed hash table, for communication.
Do you have any hints regarding this point?
> - How does Alice know that Bob, Charlie and Dave are not the same person?
> (= how do you prevent a Sybil attack?)
>
> Because thats the real problem with mixing it seems - ensuring that your
> mixing partners are actually 100 people and not just 1 attacker. There are
> probably many mixing algorithms which work if you solve that problem, but I
> don't see how you offer a solution for it :(
It's true that there are a few proposals for mixing protocols which all have
their advantages and disadvantages. However, it's not true that the mixing
itself becomes simple if you solve the problem of Sybil attacks. Still, mixing
is difficult to get right: Even if there are no Sybil attacks, you have to
ensure that the participants (or a server) cannot break unlinkability or steal
money. Actually that's why there are several proposals for mixing protocols,
because there is no obvious perfect solution.
Regarding your question:
It is indeed very important to get this right. Fundamentally, there is nothing
that prevents the attacker from creating a lot of identities participating in
a lot of CoinJoins. However, there are ways that make it hard for the attacker
to put an honest user together only with malicious users.
For a moment, assume that you can reliably establish a pool of users that
would like to participate in the protocol. (I will discuss this later.)
You have to divide the users to individual groups, i.e., CoinJoins runs. If
the assignment cannot be influenced by the attacker, then the probability that
there are also honest users in a run is quite high. Of course, the attacker is
able to reduce your anonymity set but they cannot just put you together only
with their malicious identities.
Note that the attacker has to pay transaction fees for joining many
transaction. One could even increase the required fee depending on the number
of users in the pool (enforced by honest CoinShuffle participants that would
not accept CoinJoins that pay a lower transaction fee).
And making sure that the attacker cannot influence the assignment is simple:
One can use the hash of all users' public keys in the pool to determine the
assignment for example.
For the initial setup step, i.e., creating the pool of participants, you need
some kind of "bulletin board".
One possibility is to use an underlying peer-to-peer network. Bitcoin itself
is the first that comes to the mind but it does not allow arbitrary messages.
So if we do not want to change the Bitcoin protocol, chans in Bitmessage are a
very promising possibility. Bitmessage relies basically on the same broadcast
mechanism as Bitcoin. If you as a peer use enough outgoing connections to
other peers, it's very difficult for an attacker to ensure that your message
will not be spread among the network. (Btw, people have used this to do
CoinJoin manually already
https://forum.namecoin.info/viewtopic.php?f=2&t=1694 .)
Solutions like distributed hashtables (TomP2P again) are another possibility.
We are not sure which of those approaches provides the best robustness against
malicious nodes that try to stop single participants from reaching the
network. For the setup step, latency is not an issue, so Bitmessage is indeed
a promising candidate here.
I think that in general, P2P is the way to go here, but there are other
approaches as well:
- A possibility is to have a lot of servers acting as bulletin
boards. The user sends his announcement message to all of the servers and
the user waits until at some of the servers send back a guarantee to
include the user. After some time, the servers agree on the pool of the users
just by taking all the users that have registered with at least one of the
servers. There are well-understood protocols to achieve this goal or similar
goals, because essentially the same problem arises in e-voting (see
http://arxiv.org/pdf/1401.4151 for just one example. this paper provides also
a detailed discussion of related protocols in section 9).
Of course, the disadvantage of this approach is that the protocol is not
really decentralized anymore.
- If you really want to be on the safe side, you can include your
announcement messages in the Bitcoin blockchain, e.g., by adding your
announcement message to an unspendable output, at the cost of an additional
transaction. I know that putting data to the blockchain is discouraged but let
me explain why it is useful here: If you want to do several CoinJoins in a
row, you can include your announcement message for the second CoinJoin in the
transaction of the first CoinJoin, so your announcement is very robust but you
do not need an additional transaction, because you can piggy-back on the frist
transaction.
Additionally, it is possible to combine these approaches by joining several
pools.
Another interesting point that my co-author Aniket Kate mentioned is that you
can look at that problem as a social issue: You could combine this with
information from your friends. You can participate in a CoinJoin only if your
friends tell you that they also participate in the same run. They do not even
have to reveal their input address, they just have to reveal that their
address is in a particular run. Of course, this is not yet a technical
solution but a very interesting idea.
Don't get me wrong. We don't think that there is a perfect solution the
two issues that you mentioned but we are pretty sure there are several that
work well enough in practice if they are implemented correctly.
Tim
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 648 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20140809/65784dc2/attachment.sig>

2023-06-07 15:24:51 GMT

- reply

📅 Original date posted:2014-08-06
📝 Original message:Hey,
We (a group of researchers in Germany) propose a decentralized protocol for
CoinJoin, a way to mix coins among users to improve anonymity. Our protocol is
called CoinShuffle. We believe that CoinShuffle is a way to implement CoinJoin
in the original spirit of Bitcoin, i.e., decentralized and without trusted
third parties. (If you are not familiar with CoinJoin, the idea is explained
here: https://bitcointalk.org/index.php?topic=279249.0 )
The protocol is essentially a clever way to create a CoinJoin transaction.
Recall that the idea of CoinJoin is mixing with one SINGLE transaction that
has multiple input addresses and multiple fresh output addresses (i.e., one
pair of addresses per user). The advantage of CoinJoin over mixing with a
server or trusted party is that nobody can steal coins. Each user can check if
the single transaction sends enough coins to his fresh output address. If this
is not the case, the user can just refuse to sign the transaction and nothing
(bad) happens.
The difficulty in CoinJoin is to let the participants announce their fresh
output addresses without breaking anonymity: Of course, if a participant of
the protocol just announces "I have 1 BTC at address X now" and "I would like
to have it back at address Y", then everybody can link X and Y and mixing is
useless. A naive approach is to send these two messages via a secure channel
to a server that organizes the whole mixing. While the server cannot steal
coins, the server still has to be trusted for anonymity, because it knows
which input addresses belong to which output addresses.
We present the list of CoinShuffle's features at the end of this e-mail. An
overview over the technical details can be found on the project page:
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/
Moreover, for the full details, have a look at the research paper on
CoinShuffle that can be found here:
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/coinshuffle.pdf
The paper has been accepted at a major European academic conference on
security (ESORICS). We will present the idea there.
Our Proof-of-concept Implementation
-----------------------------------
There is a proof-of-concept implementation (written in Python) available on
our project page. It is really only a proof-of-concept and it implements only
the announcement of the addresses, not the creation of the transaction.
Moreover, the code is CERTAINLY INSECURE and not well-written; our only goal
was to demonstrate feasibility and estimate the performance of our approach.
Our Future Plans
----------------
Now we are planning a full, open-source implementation of the protocol. Of
course, we would like to build on top of an existing wide-spread client. Since
we do not have much experience in the design of existing Bitcoin clients, we
would appreciate any help in the process. In particular, we did not decide
which of the existing clients we would like to extend. Any hints towards this
decisions would very helpful. Help in design and coding would be great but we
also would like to hear your comments, criticism, and improvements for the
protocol itself.
CoinShuffle Features
--------------------
CoinShuffle has the following features:
- Decentralization / no third party:
There is no (trusted or untrusted) third party in a run of the protocol.
(Still, as in all mixing solutions, users need some way to gather together
before they can run the protocol. This can be done via a P2P protocol if a
decentralized solution is desired also for this step.)
- Unlinkability of input and output addresses:
Nobody, in particular no server (there is none!), can link input and output
addresses of a mixing transaction, as long as there are at least two honest
participants in run of the protocol.
(This is not a weakness: If there is only one honest participant, meaningful
mixing is just impossible, no matter how it is organized. If all the other
participants collude, they know all their input and output addresses and can
immediately determine the output address of the honest participant.)
- Security against thefts:
As explained above, nobody can steal coins during the mixing because of the
CoinJoin principle.
Every participant can verify that his money will not be stolen. Otherwise, he
refuses to sign the transaction and nothing will happen.
- Robustness against denial-of-service:
In CoinJoin, a single malicious (or malfunctioning) client suffices to stop
the whole protocol (e.g., by just refusing to sing the transaction without a
proper reason.) This can easily lead to DoS attacks but these can be countered
in CoinShuffle.
While in case of disruption, the current run of the protocol has to stop,
CoinShuffle addresses this problem as follows: In case of active disruption,
i.e., some participant sends wrong messages, the protocol provides a proof of
this misbehavior. Then the honest protocol parties can start a new run of the
protocol without the misbehaving participant. Also in case of passive
disruption, i.e., some participant does not respond (for whatever reason), the
remaining participants can agree on starting a new run without this
participant. This ensures that the protocol will finally succeed even in the
presence of malicious participant (although this can take quite a while then).
- Only public-key encryption and signatures:
The protocol requires only well-established cryptographic primitives. Besides
signatures and hash functions (that are already used by Bitcoin), only
standard public-key encryption is necessary.
- Efficiency:
A run of the protocol with 30 participants takes less than 100 seconds (in a
setting with reasonable bandwidth and delay). This is not much, given that 10
min (on average) are required to confirm the mixing transaction anyway.
The costs are almost completely caused by communication. The computation
overhead is minimal. (This is the main achievement actually. In theory, it is
clear that a protocol with all the properties can be built. However, generic
constructions cannot be used in practice yet, because the computation and
communication costs are huge.)
- Compatibility:
As CoinShuffle works on top of Bitcoin, it is fully compatible with the
current Bitcoin system. No changes to the Bitcoin protocol are required.
By the way: The NXT cryptocurrency picked up our idea and an implementation of
CoinShuffle for a part of NXT is under way. (
https://twitter.com/comefrombeyond/status/485429369268350977 )
TL,DR:
Mixing is the way to improve anonymity in Bitcoin now, as it does not require
changes to the Bitcoin protocol. We propose CoinShuffle, a decentralized
protocol to perform mixing in a secure way without trusted third parties, see
http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/ for a technical
overview. Our next step is to implement the protocol. Help in design and
coding would be great but we also would like to hear your comments, criticism,
and improvements for the protocol itself.
Best,
Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 648 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20140807/f43f0fc1/attachment.sig>