<unnamed>

Public Key

npub1ae27kq6z802dkqw4ey4dgdx493szm8dpmcm76d7vt0ma9gf6fj4svz5t04

Profile Code

nprofile1qqswu40tqdprh4xmq82uj2k5xn2jccpdnksaudldxlx9ha7j5yaye2cpz3mhxue69uhhyetvv9ujuerpd46hxtnfduqs6amnwvaz7tmwdaejumr0ds7fdu54

Publishing to

relay.damus.io

nos.lol

Last Notes

2023-09-07 13:52:34 CEST

- reply

📅 Original date posted:2023-08-31
🗒️ Summary of this message: Tom Briar has developed a compression schema for bitcoin transactions that can be transmitted through low bandwidth channels without corruption.
📝 Original message:
On Thu, Aug 31, 2023 at 09:30:16PM +0000, Tom Briar via bitcoin-dev wrote:
> Hey everyone,
>
> I've been working on a way to compress bitcoin transactions for transmission throughsteganography, satellite broadcasting,
> and other low bandwidth channels with high CPU availability on decompression.
>
> [compressed_transactions.md](https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md)
>
> In the document I describe a compression schema that's tailored for the most common transactions single parties are likely to make.
> In every case it falls back such that no transaction will become malformed or corrupted.
> Here's a PR for implementing this schema.
>
> [2023 05 tx compression](https://github.com/TomBriar/bitcoin/pull/3)
Hey Tom,
Thank you for posting this. Could you put together a chart with some
size numbers so we can get a picture of how strong this compression is?
I understand that because this is targeted at stego/satellite
applications where the user is expected to "shape" their transaction,
that you won't get great numbers if you just look at the historical
chain or try to analyze "average" transactions. But it would be great to
post a chart with uncompressed/compressed sizes for "optimum"
transactions. At the very least, a 2-in-2-out wpkh transaction, and a
2-in-2-out Taproot transaction.
Since the scheme includes explicit support for p2sh-wpkh and p2pkh it
would also be great to see numbers for those, though they're less common
and less interesting.
Cheers
Andrew
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230901/1a0ba0e7/attachment.sig>

2023-07-27 02:26:33 CEST

- reply

📅 Original date posted:2023-07-26
🗒️ Summary of this message: POSK (proof of secret key) is not a perfect solution for preventing rogue key attacks and has logistical difficulties in implementation.
📝 Original message:
On Wed, Jul 26, 2023 at 12:09:41AM -0400, Erik Aronesty via bitcoin-dev wrote:
> personally, i think *any* time a public key is transmitted, it should come
> with a "proof of secret key". it should be baked-in to low level
> protocols so that people don't accidentally create vulns. alt discussion
> link: https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406
>
POSK is not a panacea. For example, if you were to try to eliminate
rogue key attacks in MuSig by using POSK rather than by rerandomizing
the keys, the last person to contribute a key could add a Taproot
commitment to their key, thereby modifying the final key to have a
Taproot spending path that other participants don't know about. If they
did this, they'd have no problem producing a POSK since Taproot
commitments don't affect knowledge of the secret key.
POSKs are also logistically difficult to produce in many contexts. They
essentially require an interactive challege-response (otherwise somebody
could just copy a POSK from some other source), meaning that all
participants need to be online and have secret key access at key setup
time.
In some contexts maybe it's sufficient to have a static POSK. Aside from
the complexity of determining this, you then need a key serialization
format that includes the POSK. There are standard key formats for all
widely used EC keys but none have a facility for this. If you are trying
to use already-published keys that do not have a POSK attached, you are
out of luck.
If your protocol requires POSKs to be provably published, you also run
into difficulties because they don't make sense to embed on-chain (since
blockchain validators don't care about them, and they're twice as big as
the keys themselves) so you need to establish some other publication
medium.
If you want to support nested multisignatures, you need to jointly
produce POSKs, which requires its own protocol complexity.
The MuSig and MuSig2 papers say essentially the same thing as the above;
it's why we put so much effort into developing a scheme which was
provably secure in the plain public key model, which means that POSKs
are superfluous and you don't need to deal with all these logistical
hurdles.
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230726/84e90df1/attachment.sig>

2023-06-09 14:49:37 CEST

- reply

📅 Original date posted:2018-03-19
📝 Original message:
Hi ZmnSCPxj,
Yep, I'm pretty sure this works the way you describe -- essentially replace
the hash challenges with adaptor signatures which are reblinded at each layer.
Because adaptor signatures can make arbitrary sets of signatures atomic (and
don't require any precommitments in the blockchain) it's easy to do multipath
stuff this way. And using discrete logs as challenges makes reblinding and
transferrable proof-of-payment easy.
It's also true that you can use BIP32 hardened keys for the challenges. You
might as well use HMAC rather than a hash for the sake of standardness, but
I don't think there's any particular reason to do this for key derivation.
Then Taproot can hide the non-cooperative cases as you mention.
I've been working on understanding Lightning and figuring out best way to
use the full power of scriptless scripts. I think we can do better than just
dropping TR+SS into the existing architecture. (Some of AJ's recent emails
to the list have been one-sided commentary on ideas I floated to him in
person recently, but I haven't had time to get everything straight enough
in my mind to reply.)
For example, with adaptor signatures + Graftroot [1], one party can make their
commit-tx signature atomic with a delegation to a timelock script; the other
party does the same but for a different timelock script. Then maybe both parties
can share the same commit tx rather than doing the symmetric thing, which would
save space and simplify the protocol a bit. And more generally, this "output
has different spend conditions depending on who publishes to the chain" primitive
seems like a really powerful thing, and AFAIK nobody has noticed this feature of
Graftroot until very recently.
Cheers
Andrew
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html
On Sun, Mar 18, 2018 at 08:25:13PM -0400, ZmnSCPxj via Lightning-dev wrote:
> Good morning list,
>
> I sketch here the idea, of making atomic multipath payment (AMP), with the properties:
>
> 1. Has a proof-of-payment.
> 2. Multipath decorrelation.
>
> Note: I am not a mathematician. Thus, it is likely, that there is a mistake here, and we cannot make this work.
>
> First, we look at BIP32 hierarchically derived (HD) keys by Wuille. Roughly, given a parent private key k_par, we can do derive k_i child keys for integer i by:
>
> k_i = H(i || k_par * G) + k_par
>
> where H(x) is a hash function and G is the generator point. (this it not quite how BIP32 does it, it uses HMAC, maybe that is safer for some reason that my non-mathematician self is unaware of...)
>
> The parent public key K_par = k_par * G. We can derive K_i public child keys for integer i by:
>
> K_i = H(i || K_par) * G + K_par
>
> (I think)
>
> Note that K_i = k_i * G still, as is usual for elliptic curve asymmetric cryptography:
>
> K_i = k_i * G = (H(i || k_par * G) + k_par) * G = H(i || k_par * G) * G + k_par * G = H(i || K_par) * G + K_par
>
> Of note is that if we know an i, a private child key k_i corresponding to that i, and the public parent key K_par, we can derive the private parent key k_par:
>
> k_i = H(i || K_par) + k_par
>
> k_par = k_i - H(i || K_par)
>
> Now all we need is to have a conditional payment, which can only be performed if the payee provides a private key which matches a public key, i.e. given x * G, the payee must provide x.
>
> Fortunately Poelstra has done this work beforehand in the Scriptless Script (SS) concept, where the payee provides a T = t * G, and the Scriptless Script construction requires that the payee reveal the t in order to claim the payment. I will not go into the math since there is a good chance I shall make a mistake; look up discussions by better mathematicians by me. Scriptless Script requires Bellare-Neven (BN) signatures to work.
>
> Note that Scriptless Script handles only the equivalent of hashlocking. We still need a timelock in case the payee refuses to reveal the proof-of-payment t.
>
> Fortunately, Maxwell has provided a construction, taproot (TR). This construction has two top-level branches: a Bellare-Neven n-of-n, or a Bitcoin Script. We know that Scriptless Script can make an equivalent to a hashlock from a Bellare-Neven n-of-n. The other branch of a taproot construction can now be a simple OP_CLTV+OP_CHECKSIG script, forming the timelock half of an HTLC.
>
> How would a multipath payment work? The invoice would contain the parent public key K_par. From this, the payer derives as many K_i, as it needs to split the payment to. It sets up conditional payments that require revelation of the private child key k_i for each K_i it derives.
>
> When the payee receives a partial payment, it is not incentivized to claim it immediately yet. This is because revelation of even one child key k_i will, in combination with the parent public key K_par, reveal the parent private key k_par, which serves as proof-of-payment. The payee will wait for the entire payment to reach it, and then claim all of them. This reveals all the private child keys k_i, any one of which will let the payer extract the parent private key k_par that serves as proof-of-payment.
>
> Each path has a different k_i, thus providing multipath decorrelation.
>
> (Please check my math --- I am not a mathematician and it is possible I have made a mistake somewhere)
>
> Regards,
> ZmnSCPXj
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
--
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"A goose alone, I suppose, can know the loneliness of geese
who can never find their peace,
whether north or south or west or east"
--Joanna Newsom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180319/b2f89db2/attachment-0001.sig>

2023-06-08 01:19:41 CEST

- reply

📅 Original date posted:2023-02-16
🗒️ Summary of this message: A proposed Bitcoin Improvement Proposal (BIP) aims to simplify hand computation for users, but its benefits over an existing standard are not substantial.
📝 Original message:On Thu, Feb 16, 2023 at 12:50:12PM +0100, Pavol Rusnak via bitcoin-dev wrote:
> Hi!
>
> The BIP states that its only advantage over SLIP-0039, which has been used
> in production for nearly three years (in at at least 3 SW/HW wallet
> implementations), is that it aims to be simple enough for hand computation.
> However, the BIP also indicates that "details of hand computation are
> outside the scope of this standard, and implementers do not need to be
> concerned with this possibility." Therefore, I am curious about how
> significant this advantage over SLIP-0039 really is. If hand computation is
> not straightforward and there are no other substantial advantages over
> SLIP-0039, I cannot help but feel that this BIP is simply a result of
> not-invented-here syndrome, but please correct me if I am wrong.
>
In my view, the hand computation is actually the main benefit of this
scheme. The process *is* straightforward, but tedious enough (and the
security benefits obscure enough, though they really shouldn't be...
"computers are opaque and untrustworthy" should be a common sentiment)
that it's hard to expect more than a small absolute number of users to
actually do it.
But for the purpose of the *standard*, what is important is that it is
possible to implement and use this within a normal hww workflow. This is
important for hand-computing users who know that their coins will not
die with them (since the 'standard' has fallen into obscurity), and
important for "normal" users who have the option to seamlessly switch
over to hand computation as the BTC price goes up or the world becomes
scarier.
For what it's worth, the draft lists several benefits over SLIP-0039.
I agree that none of them are particularly strong [1], and even together
they probably wouldn't meet the threshold to take the time to write a
standard, but I assure you the motivation was not NIH :).
> Keep in mind that the encoded shares in SLIP-0039 consist of exactly 200 or
> 330 bits, both of which are divisible by 5. This makes it straightforward
> to encode them as Bech32 strings.
>
This is true! And very convenient for people who may want to simply
"layer on" the codex32 checksum/splitting logic onto their SLIP39 words.
They can use a lookup table to do the conversion, spend years or
whataever doing hand-computation on them, and then use a lookup table
to go back.
[1] One listed reason is that "a SLIP is not a BIP". I have heard people
speculate that this is one reason SLIP-0039 is not nearly as
widespread as BIP-0039, even though it is objectively a far better
standard. I'm unsure whether I believe this, but "there is no other
BIP" does seem like a good reason for BIP-0039's continued
dominance.
At the very least, it means that on BIP-0039 itself we have nothing
that we could say "supercedes" or "is recommended instead of" the
BIP. See https://github.com/bitcoin/bips/pull/1413
So it's something of an aside, but I think it would probably be good
for the ecosystem (though maybe bad for this BIP's prospects :)) if
you would request a BIP number for SLIP-0039.
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230216/7f6aa147/attachment.sig>

2023-06-08 01:19:28 CEST

- reply

📅 Original date posted:2023-02-08
🗒️ Summary of this message: A potential bug in Taproot allows the same Tapleaf to be repeated multiple times in the same Taproot, which could incur different Tapfee rates.
📝 Original message:On Wed, Feb 08, 2023 at 09:34:57AM +0000, Michael Folkson wrote:
> Hi Andrew
>
> > There is a bug in Taproot that allows the same Tapleaf to be repeated multiple times in the same Taproot, potentially at different Taplevels incurring different Tapfee rates.
> >> The countermeasure is that you should always know the entire Taptree when interacting with someone's Tapspend.
>
> I wouldn't say it is a "bug" unless there is a remedy for the bug that wasn't (and retrospectively should have been) included in the Taproot design. In retrospect and assuming you could redesign the Taproot consensus rules again today would you prevent spending from a valid P2TR address if a repeated Tapleaf hash was used to prove that a spending path was embedded in a Taproot tree? That's the only thing I can think of to attempt to remedy this "bug" and it would only be a partial protection as proving a spending path exists within a Taproot tree only requires a subset of the Tapleaf hashes.
>
> I only point this out because there seems to be a push to find "bugs" and "accidental blowups" in the Taproot design currently. No problem with this if there are any, they should definitely be highlighted and discussed if they do exist. The nearest to a possible inferior design decision thus far that I'm aware of is x-only pubkeys in BIP340 [0].
>
I'm actually not certain what Russell's referring to, but if it's indeed
possible to construct TapTrees where the "same" leafhash appears multiple
times at different heights, that's something unintended and which we
could've fixed by changing the Merkle structure. I don't even think
there would've been an efficiency tradeoff.
So I think it's totally reasonable to call such a thing a "bug".
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230208/81f97b92/attachment.sig>

2023-06-08 01:19:26 CEST

- reply

📅 Original date posted:2023-02-07
🗒️ Summary of this message: Miniscript can help prevent an attack in multiparty transactions where the last input uses a larger signature to extract a fee from other parties. It allows participants to determine the maximum witness size and sign under specific conditions. Taproot also has a maximum signature size of 65 bytes, reducing the potential for this attack. However, there are still some cases where the attack can occur, but Miniscript provides tools to identify and mitigate the risk.
📝 Original message:On Tue, Feb 07, 2023 at 04:49:28AM +0200, Yuval Kogman via bitcoin-dev wrote:
>
> Since Taproot (more generally any kind of MAST) spends have variable size which
> depends on the path being used, the last such input to be signed in a multiparty
> transaction can always use a larger than estimated signature to unfairly extract
> a fee contribution from the other parties to the transaction (keeping the
> absolute fees the same and reducing the feerate for the transaction).
>
Using Miniscript [1] it is possible for all participants to determine
the maximum witness size of the tree, which can bound the size of this
attack. In fact, they can bound the size *given that their own signature
is used*, or subject to other whatever other conditions they would like,
and only sign under those conditions.
Furthermore, under Taproot individual signatures have a maximum size of
65 bytes; an "attacker" can reduce this to 64 by not including a sighash
flag, but he has one byte of play. (Pre-Taproot signatures could take up
to 73 bytes with significant room to reduce this by using crypto tricks
and/or grinding).
Peter Todd also suggests in this thread that the use of uncompressed
keys can cause "surprise" witness inflation, but (a) since segwit
uncompressed keys are also banned, so keys are a fixed 33 bytes (32 in
Taproot), and (b) we expect users of Miniscript to always know all the
keys used in a script that they're signing. Except perhaps in obscure
cases where, say, the "victim" is a somewhat passive countersigner of
a transaction, e.g. BitGo, ... in which case they're not the one putting
up fees or with an interest in the transaction going through.
With Miniscript, the problem is narrower:
* There is some more-expensive branch that could be taken without
Alice's signature. In which case Alice is only signing at all to
optimistically reduce the witness size... but she cannot assume
that she is going to be successful!
Notably, in this case Alice does not really have any interest in the
coins, in the sense that they can move entirely without her consent,
so it's hard to imagine that she has an interest in the transaction's
speedy confirmation.
* There is some more-expensive branch that could be taken by moving
Alice's signature. This is the case that you identify in the thread.
While the attack remains in both cases, fortunately Miniscript gives
Alice the tools to (a) determine which, if any, case applies to the
script under question, and (b) determine what the maximum witness size
might be, and just sign assuming that, treating any savings as "bonus".
[1] https://bitcoin.sipa.be/miniscript/
[2] In Taproot, if you want to prevent signatures migrating to another
branch or within a branch, you can use the CODESEPARATOR opcode
which was redisegned in Taproot for exactly this purpose... we
really did about witness malleation in its design!
If you want to prevent signatures from moving around *within* a
branch,
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230207/bd1c6f4e/attachment.sig>

2023-06-08 01:19:26 CEST

- reply

📅 Original date posted:2023-02-07
🗒️ Summary of this message: Andrew Poelstra discusses Taproot's CODESEPARATOR opcode and the prevention of signature migration between tapbranches in his recent email.
📝 Original message:Some people highlighted some minor problems with my last email:
On Tue, Feb 07, 2023 at 01:46:22PM +0000, Andrew Poelstra via bitcoin-dev wrote:
>
> <snip>
>
> [1] https://bitcoin.sipa.be/miniscript/
> [2] In Taproot, if you want to prevent signatures migrating to another
> branch or within a branch, you can use the CODESEPARATOR opcode
> which was redisegned in Taproot for exactly this purpose... we
> really did about witness malleation in its design!
In Taproot the tapleaf hash is always covered by the signature (though
not in some ANYONECANPAY proposals) so you can never migrate signatures
between tapbranches.
I had thought this was the case, but then I re-confused myself by
reading BIP 341 .... which has much of the sighash specified, but not
all of it! The tapleaf hash is added in BIP 342.
>
> If you want to prevent signatures from moving around *within* a
> branch,
>
And this sentence I just meant to delete :)
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230207/8d59f739/attachment.sig>

2023-06-08 01:18:55 CEST

- reply

📅 Original date posted:2023-02-01
🗒️ Summary of this message: A technical discussion on the efficiency of using OP_FALSE IF ... ENDIF versus OpPush <data> OpDrop for pushing large amounts of data into the Bitcoin blockchain.
📝 Original message:On Tue, Jan 31, 2023 at 09:07:16PM -0500, Peter Todd via bitcoin-dev wrote:
>
>
> On January 31, 2023 7:46:32 PM EST, Christopher Allen via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> >All other things being equal, which is better if you need to place a
> >64-bytes into the Bitcoin blockchain? A traditional OP_RETURN or a spent
> >taproot transaction such as:
> >
> >OP_FALSE
> >OP_IF
> >OP_PUSH my64bytes
> >OP_ENDIF
>
> What's wrong with OpPush <data> OpDrop?
>
This is a technical nit, but the reason is that <data> is limited to 520
bytes (and I believe, 80 bytes by standardness in Taproot), so if you
are pushing a ton of data and need multiple pushes, it's more efficient
to use FALSE IF ... ENDIF since you avoid the repeated DROPs.
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230201/4ed63515/attachment.sig>

2023-06-08 01:18:48 CEST

- reply

📅 Original date posted:2023-01-27
🗒️ Summary of this message: A developer is questioning the wisdom of allowing unlimited storage of NFT content as witness data on the Bitcoin blockchain, but there is no sensible way to prevent it. Arbitrary data storage in witnesses cannot be banned without incentivizing worse behavior or breaking legitimate use cases. While there is a reasonable argument that such data is toxic to the network, there is no principled way to stop it.
📝 Original message:On Fri, Jan 27, 2023 at 09:44:10AM -0300, Robert Dickinson via bitcoin-dev wrote:
> I'm curious what opinions exist and what actions might be taken by core
> developers regarding storing unlimited amounts of NFT (or other?) content
> as witness data (https://docs.ordinals.com/inscriptions.html). The ordinal
> scheme is elegant and genius IMHO, but when I think about the future disk
> use of all unpruned nodes, I question whether unlimited storage is wise to
> allow for such use cases. Wouldn't it be better to find a way to impose a
> size limit similar to OP_RETURN for such inscriptions?
>
> I think it would be useful to link a sat to a deed or other legal construct
> for proof of ownership in the real world, so that real property can be
> transferred on the blockchain using ordinals, but storing the property
> itself on the blockchain seems nonsensical to me.
Unfortunately, as near as I can tell there is no sensible way to prevent
people from storing arbitrary data in witnesses without incentivizing
even worse behavior and/or breaking legitimate use cases.
If we ban "useless data" then it would be easy for would-be data storers
to instead embed their data inside "useful" data such as dummy
signatures or public keys. Doing so would incur a ~2x cost to them, but
if 2x is enough to disincentivize storage, then there's no need to have
this discussion because they will will be forced to stop due to fee
market competition anyway. (And if not, it means there is little demand
for Bitcoin blockspace, so what's the problem with paying miners to fill
it with data that validators don't even need to perform real computation
on?).
But if we were to ban "useful" data, for example, saying that a witness
can't have more than 20 signatures in it, then we are into the same
problem we had pre-Taproot: that it is effectively impossible construct
signing policies in a general and composeable way, because any software
that does so will need to account for multiple independent limits. We
deliberately replaced such limits with "you need to pay 50 weight for
each signature" to makes this sort of analysis tractable.
There's a reasonable argument that this sort of data is toxic to the
network, since even though "the market is willing to bear" the price of
scares blockspace, if people were storing NFTs and other crap on the
chain, then the Bitcoin fee market would become entangled with random
pump&dump markets, undermining legitimate use cases and potentially
preventing new technology like LN from gaining a strong foothold. But
from a technical point of view, I don't see any principled way to stop
this.
--
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230127/1ca9b7cf/attachment.sig>

2023-06-07 20:14:30 CEST

- reply

📅 Original date posted:2018-09-13
📝 Original message:On Tue, Sep 11, 2018 at 01:37:59PM -0400, Erik Aronesty via bitcoin-dev wrote:
> - Musig, by being M of M, is inherently prone to loss.
>
It has always been possible to create M-of-N threshold MuSig signatures for any
M, N with 0 < M ≤ N. This is (a) obvious, (b) in our paper, (c) implemented at
https://github.com/apoelstra/secp256k1/blob/2018-04-taproot/src/modules/musig/main_impl.h
--
Andrew Poelstra
Research Director, Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"Make it stop, my love; we were wrong to try
Never saw what we could unravel in traveling light
Nor how the trip debrides like a stack of slides
All we saw was that time is taller than space is wide"
--Joanna Newsom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180913/ca7797a6/attachment.sig>

2023-06-07 20:14:28 CEST

- reply

📅 Original date posted:2018-09-05
📝 Original message:On Wed, Sep 05, 2018 at 08:26:14AM -0400, Erik Aronesty wrote:
> Why would you call it FUD? All the weird hemming and hawing about it is
> really strange to me. The more I look into it and speak to professors
> about i, the more it seems "so trivial nobody really talks about it".
>
> 1. Generate an M of N shared public key (done in advance of signing ....
> this gets you the bitcoin address)
> 2. Generate signature fragments (this can be done offline, with no
> communication between participants)
>
> Detailed explanation with code snippets:
>
> https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f
>
The hemming and hawing is because you've been repeatedly told that your
scheme doesn't work, and to please implement it in some computer algebra
system so that you can see that (or so we can see where your mistake is),
and you instead continue to post incomplete/incoherent copies of the same
thing across multiple mediums - Reddit, this list, Bitcointalk, Medium,
etc ad nauseum.
It's distracting and offensive to people who have spent a lot of time and
energy thinking about this stuff, and more importantly it causes confusion
in the public eye. Phrasings like "weird hemming and hawing" suggest that
we don't know/don't care about some insight you have, which is not true.
This is why your posts are FUD.
For example, in your linked post I looked at every single instance of the
character 'k' and *not one of them* defined the value 'k' from which 'R'
is derived in the signing procedure.
Of course there is no possible value, individual signers cannot learn 'R'
at signing time without interaction, and your whole scheme is broken. Given
the number of times you've been told this, I find it hard to believe that
this was an honest mistake.
Andrew
--
Andrew Poelstra
Research Director, Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"Make it stop, my love; we were wrong to try
Never saw what we could unravel in traveling light
Nor how the trip debrides like a stack of slides
All we saw was that time is taller than space is wide"
--Joanna Newsom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180905/8174ffbf/attachment.sig>

2023-06-07 20:12:24 CEST

- reply

📅 Original date posted:2018-05-23
📝 Original message:On Tue, May 22, 2018 at 11:17:42AM -0700, Pieter Wuille via bitcoin-dev wrote:
>
> Given the recent discussions about Taproot [1] and Graftroot [2], I
> was wondering if a practical deployment needs a way to explicitly
> enable or disable the Graftroot spending path. I have no strong
> reasons why this would be necessary, but I'd like to hear other
> people's thoughts.
>
Graftroot also break blind signature schemes. Consider a protocol such as [1]
where some party has a bunch of UTXOs all controlled (in part) by the same
key X. This party produces blind signatures on receipt of new funds, and can
only verify the number of signatures he produces, not anything about what he
is signing.
BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to include
a free "flags" byte or two in the witness?
(I also had the same concern about signature aggregation. It seems like it's
pretty hard to preserve the "one signature = at most one input" invariant of
Bitcoin, but I think it's important that it is preserved, at least for
outputs that need it.)
Or maybe, since it appears it will require a space hit to support optional
graftroot anyway, we should simply not include it in a proposal for Taproot,
since there would be no opportunity cost (in blockchain efficiency) to doing
it later.
[1] https://github.com/apoelstra/scriptless-scripts/pull/1
--
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"A goose alone, I suppose, can know the loneliness of geese
who can never find their peace,
whether north or south or west or east"
--Joanna Newsom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/fe3efcc5/attachment.sig>

2023-06-07 20:08:17 CEST

- reply

📅 Original date posted:2017-12-04
📝 Original message:To follow up on the remarkable work Greg announced from Benedikt Bünz (Stanford)
and Jonathan Bootle (UCL) on Bulletproofs: https://eprint.iacr.org/2017/1066
Summary
=========
Over the last couple weeks, along with Jonas Nick, Pieter Wuille, Greg Maxwell
and Peter Dettmann, I've implemented the single-output version of Bulletproofs
at https://github.com/ElementsProject/secp256k1-zkp/pull/16 and have some
performance numbers.
All of these benchmarks were performed on one core of an Intel i7-6820MQ
throttled to 2.00Ghz, and reflect verification of a single 64-bit rangeproof.
Old Rangeproof 14.592 ms
with endo 10.304 ms
Bulletproof 4.208 ms
with endo 4.031 ms
ECDSA verify 0.117 ms
with endo 0.084 ms
Here "with endo" refers to use of the GLV endomorphism supported by the curve
secp256k1, which libsecp256k1 (and therefore Bitcoin) supports but does not
enable by default, out of an abundance of caution regarding potential patents.
As we can see, without the endomorphism this reflects a 3.47x speedup over
the verification speed of the old rangeproofs. Because Bulletproof verification
scales with O(N/log(N)) while the old rangeproof scales with O(N), we can
extrapolate forward to say that a 2-output aggregate would verify with 4.10x
the speed of the old rangeproofs.
By the way, even without aggregation, we can verify two rangeproofs nearly 15%
faster than verifying one twice (so a 3.95x speedup) because the nature of the
verification equation makes it amenable to batch verification. This number
improves with the more proofs that you're verifying simultaneously (assuming
you have enough RAM), such that for example you can batch-verify 10000
bulletproofs 9.9 times as fast as you could verify 10000 of the old proofs.
While this is a remarkable speedup which greatly improves the feasibility of
CT for Bitcoin (though still not to the point where I'd expect a serious
proposal to get anywhere, IMHO), the concerns highlighted by Greg regarding
unconditional versus computational soundness remain. I won't expand on that
more than it has already been discussed in this thread, I just want to tamp
down any irrational exhuberance about these result.
People who only care about numbers can stop reading here. What follows is a
discussion about how this speedup is possible and why we weren't initially
sure that we'd get any speedup at all.
Details
=========
Section 6 of the linked preprint discusses performance vs our old rangeproofs. As
Greg mentioned, it is possible to fit two 64-bit bulletproofs into 738 bytes,
with logarithmic scaling. (So one proof would take 674 bytes, but eight proofs
only 866 bytes.)
However, this section does not give performance numbers, because at the time
the preprint was written, there was no optimized implementation on which to
benchmark. It was known that verification time would be roughly linear in the
size of the proof: 141 scalar-multiplies for a 64-bit proof, 270 for an
aggregate of two proofs, and so on [*]. Our old rangeproofs required only 128
multiplies for a 64-bit proof, then 256 for two, and so on. So naively we were
concerned that the new Bulletproofs, despite being fantastically smaller than
the original rangeproofs, might wind up taking a bit longer to verify.
For reference, an ordinary ECDSA signature verification involves 2 multiplies.
So roughly speaking, the naive expectation was that a N-bit rangeproof would
require N-many signature verifications' worth of CPU time, even with this new
research. Worse, we initially expected bulletproofs to require 1.5x this much,
which we avoided with a trick that I'll describe at the end of this mail.
As you can see in the above numbers, the old rangeproofs actually perform worse
than this expectation, while the new Bulletproofs perform significantly **better**.
These are for the same reason: when performing a series of scalar multiplications
of the form
a*G + b*H + c*I + ...
where G, H, I are curvepoints and a, b, c are scalars, it is possible to compute
this sum much more quickly than simply computing a*G, b*H, c*I separately and
then adding the results. Signature validation takes advantage of this speedup,
using a technique called Strauss' algorithm, to compute the sum of two multiplies
much faster than twice the multiple-speed. Similarly, as we have learned, the
141 scalar-multiplies in a single-output Bulletproof can also be done in a single
sum. To contrast, the old rangeproofs required we do each multiplication separately,
as the result of one would be hashed to determine the multiplier for the next.
libsecp256k1 has supported Strauss' algorithm for two points since its inception
in 2013, since this was needed for ECDSA verification. Extending it to many points
was a nontrivial task which Pieter, Greg and Jonas Nick took on this year as part
of our aggregate signatures project. Of the algorithms that we tested, we found
that Strauss was fastest up to about 100 points, at which point Pippenger's was
fastest. You can see our initial benchmarks here
https://user-images.githubusercontent.com/2582071/32731185-12c0f108-c881-11e7-83c7-c2432b5fadf5.png
though this does not reflect some optimizations from Peter Dettmann in the last
week.
It was a happy coincidence that the Bulletproofs paper was published at nearly
the same time that we had working multi-point code to test with.
Finally, the Bulletproof verification process, as written in the paper, is a
recursive process which does not appear to be expressible as a single multiproduct,
and in fact it appears to require nearly twice as many multiplications as I claim
above. I want to draw attention to two optimizations in particular which made this
possible.
1. By expanding out the recursive process, one can see that the inner-product argument
(Protocol 1 in the paper) is actually one multiproduct: you hash each (L_i, R_i)
pair to obtain logarithmically many scalars, invert these, and then each scalar in
the final multiproduct is a product containing either the inverse or original of
each scalar.
Peter Dettmann found a way to reduce this to one scalar inversion, from which
every single scalar was obtainable from a single multiplication or squaring of a
previous result. I was able to implement this in a way that cached only log-many
previous results.
2. Next, line (62) of the Bulletproofs paper appears to require N multiplications
beyond the 2N multiplications already done in the recursive step. But since
these multiplications used the same basepoints that were used in the recursive
step, we could use the distributive property to combine them. This sounds
trivial but took a fair bit of care to ensure that all the right data was still
committed to at the right stage of proof verification.
Further Work
=========
There are still a few open issues I plan to help resolve in the coming month:
- Bulletproof aggregation is not compatible with Confidential Assets, where each
output has a unique asset tag associated with it. There are a couple possible
solutions to this but nothing public-ready.
- Bulletproofs, as described in the paper, work only when proving 2^n-many bits.
I believe there is a straightforward and verifier-efficient way to extend it
to support non-powers-of-2, but this requires some work to modify the proof in
the paper.
- Bulletproofs are actually much more general than rangeproofs. They can be used
to prove results of arbitrary arithmetic circuits, which is something we are
very interested in implementing.
[*] By "and so on", I mean that N bits require 2N + 2log_2(N) + 6 scalar multiplies.
Cheers
Andrew
--
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"A goose alone, I suppose, can know the loneliness of geese
who can never find their peace,
whether north or south or west or east"
--Joanna Newsom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20171204/42dfe0d1/attachment.sig>

2023-06-07 20:00:52 CEST

- reply

📅 Original date posted:2017-05-10
📝 Original message:On Tue, May 09, 2017 at 09:59:06PM -0400, Russell O'Connor via bitcoin-dev wrote:
> I'm a bit amateur at this sort of thing, but let me try to argue that this
> proposal is in fact horribly broken ;)
>
> Suppose Alice has some UTXO with some money Bob wants to steal. Grant me
> that the public key P0 protecting Alice's UTXO is public (say because the
> public key has been reused elsewhere).
>
> Bob going to spend Alice's UTXO by generating random values s0, k0 and R0
> := k0*G and thus creating a random signature for it, [R0, s0]. Now clearly
> this signature isn't going to be valid by itself because it is just random.
> Bob's goal will be to make a transaction with other inputs such that, while
> the individual signatures are not valid, the aggregated signature will be
> valid.
>
If you seed the randomization with every R value (which would come for free
if you used, say, the witness root) then Wagner's attack no longer applies.
The idea is that no aggregation occurs until a miner produces a block. You
have a bunch of independent Schnorr sigs (s_i, R_i). Then the _miner_ multiples
each s_i by H(witness root || index) or whatever, sums up the s_i's, and commits
the sum somewhere where it doesn't affect the root.
Verifiers then multiply each R_i by the same multiplying factors and are able
to do a batch verification of them.
Verifiers who have seen a signature before and cached it as valid can save
themselves a bit of time by subtracting H(witness root || index)*s_i from
the summed s-value and then skipping R_i in the above step. These are scalar
operations and are extremely cheap.
They can recognize the signature given only the transaction it signs and R_i,
which uniquely determine a valid signature.
I believe this is what Tadge was referring to when he mentioned a talk of mine.
It's roughly what I've had in mind whenever I talk about non-interactive Schnorr
aggregation.
Cheers
Andrew
--
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"A goose alone, I suppose, can know the loneliness of geese
who can never find their peace,
whether north or south or west or east"
--Joanna Newsom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170510/ab8b75e7/attachment.sig>