Weiji Guo [ARCHIVE] / is on Nostr

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

Last Notes

2023-06-07 23:21:48

- reply

📅 Original date posted:2023-05-12
🗒️ Summary of this message: Weiji asks Robin about implementing a SNARK verifier on Bitcoin's base layer, while Robin introduces ZeroSync, a proof system addressing Bitcoin's scalability challenges with SNARKs.
📝 Original message:Hi Robin,
Could you please expand more on how you plan to "implement a SNARK verifier
on Bitcoin’s base layer"?
For your information, I happen to be the one proposing a new opcode OP_ZKP
to enable the Bitcoin network to verify zkp proofs. My proposal requires a
soft fork. You may find more information from the email archive here:
https://www.mail-archive.com/bitcoin-dev@lists.linuxfoundation.org/msg12601.html
We might be tackling similar issues and probably could benefit from each
other.
Thanks,
Weiji
On Fri, May 12, 2023 at 9:16 PM Robin Linus via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi all,
>
> Today we are publishing a summary of our research on "ZeroSync:
> Introducing Validity Proofs to Bitcoin".
>
>
> Here's the preface:
>
> *We introduce ZeroSync, the first-ever proof system addressing Bitcoin’s
> scalability challenges with Succinct Non-Interactive Argument of Knowledge
> (SNARKs). ZeroSync compresses the entire Bitcoin blockchain into a compact
> proof of validity, enabling instant verification and unlocking various
> innovative applications. We discuss our prototype implementation of a chain
> state proof, utilizing the Cairo language, Utreexo, and recursive STARKs.
> Our work enables diverse applications, including quick bootstrapping of
> full nodes, trustless light clients, enhanced Lightning Network privacy,
> and secure cross-chain bridges. Chain state proofs require no consensus
> changes, which is crucial as forks in Bitcoin are challenging to implement
> and achieve consensus for. Despite the existing bottleneck of prover
> performance, we present a range of optimization strategies and demonstrate
> the practicality of generating a complete chain state proof. *
> *Finally, we introduce zkCoins, a client-side validation protocol combined
> with zeroknowledge SNARKs, drastically improving privacy and throughput of
> token transactions. In combination with future Bitcoin features, such as
> Simplicity, zkCoins also enables private and more scalable BTC
> transactions. *
> *The groundbreaking compression capabilities of SNARKs initiated a
> paradigm shift in cryptocurrency design, and ZeroSync is pioneering their
> application to Bitcoin.*
>
>
> You can find the full paper here: https://zerosync.org/zerosync.pdf
> Happy to receive any comments and answer any questions the bitcoin dev
> community may have about the paper!
>
>
>
> Best regards,
> Robin Linus
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230512/108d3ca1/attachment.html>

2023-06-07 23:21:35

- reply

📅 Original date posted:2023-05-10
🗒️ Summary of this message: The author proposes a new opcode, OP_ZKP, for Bitcoin's L2 to address transaction fee issues and enable more smart contracts, seeking feedback from the community.
📝 Original message:> I would like to point out that I'm not an advocate for doing anything at
this point aside from working on l2
Speaking of L2, I had recently proposed a new opcode OP_ZKP to enable
payments based on ZKP proof. I wonder if it has drawn enough attention but
it seems to me a viable way to address transaction fee issues, in addition
to enabling more smart contracts. And it will be a Bitcoin native L2, not a
side chain, not pegging.
scriptPubKey: <hash of the verification key> <scheme_id> OP_ZKP
scriptSig: <pubInput_1> <pubInput_2> ... <pubInput_n> <n>
<proof>
I haven't figured out how to use OP_ZKP to incentivize BRC-20, inscription
etc. to move to L2. But I like to bring it up here and I am open to your
feedback and comments.
Thanks,
Weiji
On Tue, May 9, 2023 at 8:51 PM Erik Aronesty via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> I would like to point out that I'm not an advocate for doing anything at
> this point aside from working on l2
>
> just to make it inconvenient for people
>
> I just think the discussion of outputs and fees is interesting and related
> to the game theory portion of Bitcoin
>
>
>
> On Tue, May 9, 2023, 8:23 AM Jaroslaw via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>>
>>
>> Ok, I need to highlight one important thing well proven by this
>> discussion (like it or not)...
>>
>> Not the spam itself is the real reason of feeling: "something must be
>> done"
>> The reason is: $30 fee per transaction (I hope you all agree)
>>
>>
>> Let me paraphrase some quotes used in this discussion, then:
>>
>> 1. Lack of block subsidy long term and necessity of $40 tx fee to
>> compensate it - "threaten the smooth and normal use of the Bitcoin network
>> as a peer-to-pear digital currency, as it was intended to be used as."
>>
>> 2. "the harmony of Bitcoin transactions is being disrupted right now" due
>> to lack of block subsidy and due to exorbitant $40 tx fees as an effect
>> necessary to keep the network security untouched
>>
>> 3. "Fee spikes aren't fun" and it's obvious that keeping the network
>> security only on enormous tx fees of active users and having passive users
>> as free-riders - isn't fun, too
>>
>> 4. by ignoring Bitcoin long-term security budget problem - "we indirectly
>> allowed this to happen, which previously wasn't possible before. So we also
>> have a responsibility to do something to ensure that this kind of
>> tremendous $40 tx fees can never happen again"
>>
>> 5. "Action against exorbitant fees should have been taken months ago.
>> (...) It's a mistake that the" tail emission or other necessary solution -
>> weren't implemented on time
>>
>> 6. "we need to find a solution for long-term horrible fees problem - that
>> fits everyone's common ground."
>>
>>
>> Yes, we need - instead of being still in a heavy denial state.
>>
>> No additional comment then, except this little one:
>> Delay of halving in case of 4 years long network difficulty regression
>> situation.
>>
>>
>> Regards,
>> Jaroslaw
>>
>>
>>
>>
>>
>> W dniu 2023-05-09 00:37:57 użytkownik Luke Dashjr via bitcoin-dev <
>> bitcoin-dev at lists.linuxfoundation.org> napisał:
>>
>> Action should have been taken months ago. Spam filtration has been a
>> standard part of Bitcoin Core since day 1. It's a mistake that the existing
>> filters weren't extended to Taproot transactions. We can address that, or
>> try a more narrow approach like OP_RETURN (ie, what "Ordisrespector" does).
>> Since this is a bugfix, it doesn't really even need to wait for a major
>> release.
>>
>> (We already have pruning. It's not an alternative to spam filtering.)
>>
>> Luke
>>
>>
>>
>>
>> On 5/7/23 13:22, Ali Sherief via bitcoin-dev wrote:
>> Hi guys,
>>
>>
>> I think everyone on this list knows what has happened to the Bitcoin
>> mempool during the past 96 hours. Due to side projects such as BRC-20
>> having such a high volume, real bitcoin transactions are being priced out
>> and that is what is causing the massive congestion that has arguable not
>> been seen since December 2017. I do not count the March 2021 congestion
>> because that was only with 1-5sat/vbyte.
>>
>>
>> Such justifiably worthless ("worthless" is not even my word - that's how
>> its creator described them[1]) tokens threaten the smooth and normal use of
>> the Bitcoin network as a peer-to-pear digital currency, as it was intended
>> to be used as.
>>
>>
>> If the volume does not die down over the next few weeks, should we take
>> an action? The bitcoin network is a triumvirate of developers, miners, and
>> users. Considering that miners are largely the entities at fault for
>> allowing the system to be abused like this, the harmony of Bitcoin
>> transactions is being disrupted right now. Although this community has a
>> strong history of not putting its fingers into pies unless absolutely
>> necessary - an example being during the block size wars and Segwit - should
>> similar action be taken now, in the form of i) BIPs and/or ii) commits into
>> the Bitcoin Core codebase, to curtail the loophole in BIP 342 (which
>> defines the validation rules for Taproot scripts) which has allowed these
>> unintended consequences?
>>
>>
>> An alternative would be to enforce this "censorship" at the node level
>> and introduce a run-time option to instantly prune all non-standard Taproot
>> transactions. This will be easier to implement, but won't hit the road
>> until minimum next release.
>>
>>
>> I know that some people will have their criticisms about this,
>> absolutists/libertarians/maximum-freedom advocates, which is fine, but we
>> need to find a solution for this that fits everyone's common ground. We
>> indirectly allowed this to happen, which previously wasn't possible before.
>> So we also have a responsibility to do something to ensure that this kind
>> of congestion can never happen again using Taproot.
>>
>>
>> -Ali
>>
>>
>> ---
>>
>>
>> [1]:
>> https://www.coindesk.com/consensus-magazine/2023/05/05/pump-the-brcs-the-promise-and-peril-of-bitcoin-backed-tokens/
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230510/fa7b3d30/attachment.html>

2023-06-07 23:21:06

- reply

📅 Original date posted:2023-05-05
🗒️ Summary of this message: An anonymous attacker can flood the network with non-aggregated transactions, then confirm a single aggregated transaction with lower feerate, potentially paying less. However, this attack is not feasible and unlikely to occur.
📝 Original message:Hi ZmnSCPxy,
> As the network is pseudonymous, an anonymous attacker can flood the
fullnode mempool network with large numbers of non-aggregated transactions,
then in cooperation with a miner confirm a single aggregated transaction
with lower feerate than what it put in the several non-aggregated
transactions.
Arguably this is hardly a feasible attack. Let's suppose the attacker
creates 1000 such transactions, and attaches each transaction with a small
amount of transaction fee X. The total fee will be 1000*X collectible by
the aggregation vendor, who pays the miner a fee Y. We can reasonably
assume that 1000*X is much larger than Y, yet X is much smaller than Y.
Note that Y is already much larger than the regular fee for other
transactions as the aggregated transaction should contain many inputs and
many outputs, thus very large in size.
Now, the attacker will have to generate proofs for these 1000 transactions,
which is non-trivial; and pay for 1000*X upfront. The aggregation vendor
has to spend more computing power doing the aggregation (or recursive
verification) and take (1000*X - Y) as profit. Miner gets Y.
Miners are unlikely to collude with the attacker. I don't think the vendor
would, given profit of 1000*X - Y. Or the attacker could play the vendor,
however, it is still not a trivial attack after spending lots of computing
power generating all the proofs and aggregation/recursion, and paying at
least Y, which is also non-trivial given the size.
All that being said, let's focus on the OP_ZKP for now and leave
aggregation or recursive verification for future discussion. I brought up
the scalability issue just to stress that there is potential room for
further improvements. The research and implementation might take much
longer. As far as I know, CISA (cross input signature aggregation) is still
experimental. Again, thank you very much for detailed analysis and replies.
Regards,
Weiji
On Fri, May 5, 2023 at 1:13 AM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Weiji,
>
> The issue here is that non-aggregated transaction are a potential attack
> vector.
>
> As the network is pseudonymous, an anonymous attacker can flood the
> fullnode mempool network with large numbers of non-aggregated transactions,
> then in cooperation with a miner confirm a single aggregated transaction
> with lower feerate than what it put in the several non-aggregated
> transactions.
> The attacker ends up paying lower for the single confirmed transaction,
> even though it cost the fullnode network a significant amount of CPU to
> process and validate all the non-aggregated transactions.
>
> Once the single aggregate transaction is confirmed, the fullnodes will
> remove the non-aggregated transactions from the mempool, clearing out their
> mempool limit.
> Then the attacker can once again flood the fullnode mempool network with
> more non-aggregated transactions, and again repeat with an aggregated
> transaction that pays below the total of the non-aggregated transactions,
> repeatedly increasing the load on the mempool.
>
> Thus, we should really make transactions that could appear in the mempool
> non-aggregatable with other transactions in the mempool.
> You should arrange for aggregation before the blockchain-level transaction
> hits the mempool.
>
> One can compare cross-input signature aggregation designs.
> Signature aggregation is only allowed within a single blockchain-level
> transaction, not across transactions, precisely so that a transaction that
> appears in the mempool cannot have its signatures aggregated with other
> transactions, and preventing the above attack.
> Anyone trying to take advantage of signature aggregation needs to
> cooperatively construct the blockchain-level transaction outside of the
> mempool with other cooperating actors, all of which perform the validation
> themselves before anything hits the mempool.
>
> Similarly I can imagine that cross-input ZKP aggregation would be
> acceptable, but not cross-transaction ZKP aggregation.
> (And if you want to push for ZKP aggregation, you should probably push for
> cross-input signature aggregation first, as you would probably need to
> solve similar problems in detail and I imagine signature aggregation is
> simpler than general ZKP aggregation.)
>
> Always expect that the blockchain and its supporting network is attackable.
> Do ***NOT*** focus on blocks --- focus on the load on the mempool (the
> block weight limit is a limit on the mempool load, not a limit on the block
> CPU load!).
> The mempool is a free service, we should take care not to make it abusable.
> On the other hand, blockspace is a paid service, so load on it is less
> important; it is already paid for.
> I strongly recommend **DISALLOWING** aggregation of ZKPs once a
> transaction is in a form that could potentially hit the mempool, and to
> require paid services for aggregation, outside of the unpaid, free mempool.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230506/68fe13b2/attachment.html>

2023-06-07 23:21:05

- reply

📅 Original date posted:2023-05-04
🗒️ Summary of this message: Specialized computing power vendors, potentially miners, could optimize ZKP computations. ZKP transactions could be put in mempool and open to aggregation. Off-chain transactions could be hosted by smart contract operators. Thousands of active smart contracts based on OP_ZKP could increase the effective TPS of the Bitcoin network.
📝 Original message:Hi ZmnSCPxj,
I do mean to have specialized computing power vendors, which could happen
to be miners, or not. Optiming ZKP computations is rather different from
Bitcoin mining so I expect those vendors to be from more research-driven
teams focused in cryptographic engineering.
I am open to whether to put those transactions in mempool or not. I
apologize for giving an inaccurate number earlier about the verification
cost. I just ran gnark-bench on my Mac M2, it turns out the cost for
Groth16 verification could be as fast as 1ms. For Plonk it is around 1.6ms.
So it seems even a common fullnode could handle thousands of OP_ZKP
transactions. In that case, the ZKP transactions could be put into mempool,
and be open to be aggregated by some vendor. Fullnodes should verify these
transactions as well. It does not seem a good idea to treat them with
special rules as there is no guarantee that certain OP_ZKP transactions
will be aggregated or recursively verified. Of course, the weighting should
be well benchmarked and calculated. The cost for those *standalone* OP_ZKP
transactions might be higher due to more data and/or higher weighting. This
incentivizes vendors to develop aggregation / recursive verification
services to drive down the fee requirements and profit from doing so (fee
extraction). I also expect to see an open market where various vendors can
compete against each other, so it makes sense to have these transactions
openly visible to all participants.
Meanwhile, some transactions are meant to be off-chain. For example, a
would-be smart contract can aggregate many related transactions in a OP_ZKP
transaction. Those aggregated transactions should *not* be transmitted
within the Bitcoin network. They could even be *not* valid Bitcoin
transactions. Usually the smart contract operator or its community could
host such a service.
Consider a potential situation in a few years: there are thousands of
active smart contracts based on OP_ZKP, and each block contains a few
hundred OP_ZKP transactions, each one of them aggregates / recursively
verifies many transactions. The effective TPS of the Bitcoin network could
far exceed the current value, reaching the range of thousands or even more.
Hope this clarifies.
Weiji
On Tue, May 2, 2023 at 11:01 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> Good morning Weiji,
>
> > Meanwhile, as we can potentially aggregate many proofs or recursively
> verify even more, the average cost might still be manageable.
>
> Are miners supposed to do this aggregation?
>
> If miners do this aggregation, then that implies that all fullnodes must
> also perform the **non**-aggregated validation as transactions flow from
> transaction creators to miners, and that is the cost (viz. the
> **non**-aggregated cost) that must be reflected in the weight.
> We should note that fullnodes are really miners with 0 hashpower, and any
> cost you impose on miners is a cost you impose on all fullnodes.
>
> If you want to aggregate, you might want to do that in a separate network
> that does ***not*** involve Bitcoin fullnodes, and possibly allow for some
> kind of extraction of fees to do aggregation, then have already-aggregated
> transactions in the Bitcoin mempool, so that fullnodes only need validate
> already-aggregated transactions.
>
> Remember, validation is run when a transaction enters the mempool, and is
> **not** re-run when an in-mempool transaction is seen in a block
> (`blocksonly` of course does not follow this as it has no mempool, but most
> fullnodes are not `blocksonly`).
> If you intend to aggregate transactions in the mempool, then at the worst
> case a fullnode will be validating every non-aggregated transaction, and
> that is what we want to limit by increasing the weight of heavy-validation
> transactions.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230504/ccc94da5/attachment.html>

2023-06-07 23:21:04

- reply

📅 Original date posted:2023-05-01
🗒️ Summary of this message: The writer agrees with ZmnSCPxj's suggestion to make verification keys consensus-critical and to weigh them higher. They will benchmark to determine a reasonable weight.
📝 Original message:Hi ZmnSCPxj,
Thank you very much for your insights. You are definitely right about
making the verification keys consensus-critical and about how the weight
units. I totally agree that the weighting of ZKP the witness should be
higher. We will carry out some benchmarking to recommend a reasonable
weight when we start to develop a GitHub PR.
Meanwhile, as we can potentially aggregate many proofs or recursively
verify even more, the average cost might still be manageable.
Regards,
Weiji
On Sun, Apr 30, 2023 at 10:16 AM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Weiji,
>
> Have not completed reading, but this jumped out to me:
>
>
>
> > 3. Dealing with system limitation: verification keys could be very long
> and exceed the MAX_SCRIPT_ELEMENT_SIZE (520 bytes). They could be put into
> configurations and only use their hash in the scriptPubKey. The
> configuration information such as new verification keys could be propagated
> through P2P messages (we might need a separate BIP for this);
>
> `scriptPubKey` is consensus-critical, and these new P2P messages would
> have to be consensus-critical.
>
> As all nodes need to learn the new verification keys, we should consider
> how much resources are spent on each node just to maintain and forever
> remember verification keys.
>
> Currently our resource-tracking methodology is via the synthetic "weight
> units" computation.
> This reflects resources spent on acquiring block data, as well as
> maintaining the UTXO database.
> For instance, the "witness discount" where witness data (i.e. modern
> equivalent of `scriptSig`) is charged 1/4 the weight units of other data,
> exists because spending a UTXO reduces the resources spent in the UTXO
> database, although still consumes resources in downloading block data
> (hence only a discount, not free or negative/rebate).
>
> Similarly, any propagation of verification keys would need a similar
> adjustment for weight units.
>
> As verification keys MUST be seen by all nodes before they can validate an
> `OP_ZKP`, I would suggest that it is best included in block data (which
> similarly needs to be seen by all nodes), together with some weight unit
> adjustment for that data, depending on how much resources verification keys
> would consume.
> This is similar to how `scriptPubKey`s and amounts are included in block
> data, as those data are kept in the UTXO database, which nodes must
> maintain in order to validate the blockchain.
>
> If verification keys are permanent, they should probably be weighted
> heavier than `scriptPubKey`s and amounts --- UTXOs can theoretically be
> deleted later by spending the UTXO (which reduces UTXO database size),
> while any data that must be permanently stored in a database must
> correspondingly be weighted higher.
>
> Similarly, my understanding is that the CPU resources needed by validation
> of generic ZKPs is higher than that required for validation of ECC
> signatures.
> Much of the current weight calculation assumes that witness data is
> primarily ECC signatures, so if ZKP witnesses translate to higher resource
> consumption, the weighting of ZKP witnesses should also be higher (i.e.
> greater than the 1/4 witness-discounted weight of current witness data).
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230501/b08ce64e/attachment.html>

2023-06-07 23:20:58

- reply

📅 Original date posted:2023-04-28
🗒️ Summary of this message: Proposal for a new opcode, OP_ZKP, to enable zero knowledge based spending authorization for Bitcoin. This will equip Bitcoin with Turing completeness and enable building of payment channels, stablecoin, decentralized exchange, DeFi, etc. through a soft fork. The proposal covers aspects such as how it works, security, dealing with system limitations, scalability, ZKP scheme and curve choices, potential uses, and ecology implications. Discussion and consensus building among developers and the community are needed before requesting a BIP.
📝 Original message:Hey everyone,
I am writing this email to propose a new opcode to enable zero knowledge
based spending authorization for Bitcoin. This new opcode OP_ZKP will
enable the Bitcoin network to authorize spending based on off-chain
computation, provided acceptable proof is supplied. This will not only
equip the Bitcoin script with Turing completeness, but also enable the
building of payment channels more flexible, stablecoin, decentralized
exchange, DeFi, etc. directly over the Bitcoin network, or even a layer 2.
All these could be accomplished with a soft fork (and follow-up building).
Before any BIP could be requested, I’d like to discuss all the aspects in
more detail, to cover as many corners as possible, and hopefully to build
consensus among developers and the community.
*### 0. Overview*
Here are what I am currently considering, listed as starting points for
discussion. I hope that I have covered all major issues, but please do feel
free to add more.
1. How it works: we add OP_ZKP and OP_ZKPVERIFY using some unused OP_NOP
codes. OP_ZKP works similarly to OP_MULTISIG, with a number parameter to
indicate how many public inputs are to be read;
2. Security: to bind the spending conditions to certain UTXO set,
amount, and recipients, the hash of all this information shall be used as
public input to the proof;
3. Dealing with system limitation: verification keys could be very long
and exceed the MAX_SCRIPT_ELEMENT_SIZE (520 bytes). They could be put into
configurations and only use their hash in the scriptPubKey. The
configuration information such as new verification keys could be propagated
through P2P messages (we might need a separate BIP for this);
4. Scalability: arrangement for miners or computing power vendors to
aggregate some proofs for scalability and fee reduction. Alternatively,
this could be accomplished with recursive proof.
5. ZKP scheme and curve choices.
6. Potential uses are unlimited, although there is no apparent secret
key (private key or seed) in play.
7. Ecology implications. Impacts on wallets, etc.
Below, I will introduce/discuss the above-listed item one by one. Mostly I
have to keep the discussion minimal and brief. It is still a bit lengthy,
please bear with me.
*### 1. How it works*
Consider below script:
scriptPubKey: <hash of the verification key> <Groth16_BN254> OP_ZKP
scriptSig: <pubInput_1> <pubInput_2> … <pubInput_n> <n> <proof>
<Groth16_BN254> is only an example in place of an indicator for the ZKP
scheme and curve parameters. Other combinations are possible. Further
discussion is provided in section 5.
<hash of the verification key> - the node implementation should look up a
verification key that hashed to this value. Verification keys tend to be
long and exceed the limitation imposed by MAX_SCRIPT_ELEMENT_SIZE (520
bytes). And for various schemes/circuits, the size might be different. So a
hash is used here. Further discussion is covered in section 3.
<proof> refers to the proof data to be verified. Its size is also subject
to MAX_SCRIPT_ELEMENT_SIZE. This might limit our choices of the ZKP scheme,
although proof data could be split into several parts.
<n> refers to how many public inputs are to be read. It should depend on
the circuit in use. However, this is *not* the actual number. There is also
an implicit public input, which is the hash of the transaction, calculated
according to the script context.
The evaluation is pretty straightforward. The implementation of OP_ZKP
reads in (and removes) all its parameters from the stack, calculates the
implicit public input from the transaction (UTXO inputs, amount,
recipients, etc.), and then leave a true or false in the stack after ZKP
verification. The security reason behind this implicit public input design
is discussed in the next section.
OP_ZKPVERIFY works the same except for the last step, where it leaves
nothing or fails the verification.
*### 2. Security: replay protection*
Proof should not be replayed to authorize spending of another set of UTXO.
Therefore it is critical to bind the proof to the transaction. This is
similar to OP_CHECKSIG: the transaction hash is needed to verify the proof
for OP_ZKP. To calculate the hash, just follow what the context requires.
For a SegWit transaction, BIP 0143 seems natural. And most of the time this
will be the case. But if those opcodes are indeed used outside of SegWit,
then the hashing algorithm before SegWit should be fine.
Binding proof to the transaction, especially the UTXO entries, also
protects from proof malleability, since once spent, the UTXO entries will
be removed from the available UTXO set.
On the other hand, since proof could be calculated by anybody given the
witness, circuit developers must take this into account. The private inputs
should be kept confidential. In some other uses, there might not be any
private inputs but only an authoritative signature, then it is the
authority’s responsibility to only sign valid information, and circuit
developers’ responsibility to ensure proper protection. Further discussion
is deferred for now.
*### 3. Dealing with system limitations: verification key*
The size of proof data or verification key could exceed the limitation
imposed by MAX_SCRIPT_ELEMENT_SIZE, which is 520 (bytes). In this section,
we discuss its implications for the verification key.
The size of a verification key varies with different schemes and circuits.
However, the number of total different circuits will be rather limited, at
least at the Bitcoin network level. Therefore, using the hash of the
verification key instead of the key itself renders fixed-size data, and
flexibility without worrying if the verification key gets too long.
Further, it is not advisable to hard code the verification key in the code
base of nodes, as new verification keys arise every few days or months.
Rather, P2P messaging seems a suitable way to propagate new verification
keys. Once received, a node could save it to a configuration file, and also
forward it to other nodes. If an unknown hash is encountered, the node
could also request it from its connected peers. If the node cannot gather a
new verification key in time, then it has to fail the transaction
verification. If too many nodes cannot get the new verification key in
time, the new block containing the offending transaction will not be
accepted by the Bitcoin network. It is suggested that a separate BIP be
requested to address these issues.
*### 4. Scalability*
ZKP verification usually costs at least tens of milli-seconds, and might
also cost more data size. So, it should be fine to have a few dozen ZKP
transactions in a block. But a few thousand will cost too much time to
verify and too much block space. In this section, we discuss how this could
be mitigated.
There are two options: proof aggregation (batching), and recursive
verification.
Some ZKP proofs are known to be capable of aggregation, however, with
certain limitations. For example, aggregating Groth16 proofs seems to
require that all proofs are of the same circuit, so that the value of γ and
δ remain the same across different proofs, as both parameters are from
phase 2 setup, thus circuit specific. We can also aggregate KZG polynomial
commitment scheme-based proofs. Still, the aggregator needs to ensure that
the hash of each transaction has been verified as well.
On the other hand, recursive verification can handle these transaction hash
verification, along with verifying the correctness of each proof. It might
be very computationally intensive to generate a recursive proof for a few
thousand proofs but there are lots of room for further optimization.
It is also possible to develop a hybrid strategy, that some proofs are
aggregated, with additional verification being proved, then both the
aggregation and additional proof could be verified by a recursive proof.
We might need a new SegWit version so that transactions can refer to its
proper proof once aggregated or recursively verified.
Replay protection: once aggregated or proved via recursion to the network,
a transaction cannot be played to the Bitcoin network again, as the UTXO
entries have been spent.
*### 5. ZKP scheme and curve choice*
A major concern is the size of the script, proof, cost of verification, and
the feasibility to aggregate/batching many proofs.
Groth16 checks out here with short proof size, cheap verification, and
feasibility to aggregate. For example, the standard draft here ([1]) shows
an implementation that can aggregate 1024 proofs in 2s and verifies them in
23ms. Although it seems to require that all proofs belong to the same
circuit ( due to γ and δ, which are circuit-specific). Still, the short
proof size and cheap verification cost make Groth16 suitable to verify
other proofs recursively. And when the upper layer proving schemes (and
setup) is the same, so are the verification circuits, therefore those
proofs could be aggregated.
On the other hand, KZG commitment supports batching. So the zkSnarks based
on KZG should support as well. Further, this paper by Boneh, etc. ([2])
enhances KZG commitment to allow one or two group element opening for
multiple polynomials each evaluated at a different set of points.
This is not an exhaustive list, not even a list. Overall, if we can
aggregate/batch many proofs together, then proof size is of smaller
concern. In this case, Plonk might be a better scheme than Groth16, if we
can implement a batching technique to batch proofs from different circuits
together. But still, in the beginning, there might not be many proofs to be
batched/aggregated at all.
We shall designate a parameter to OP_ZKP and OP_ZKPVERIFY to indicate which
scheme (and curve) to use.
For curve, BN254 is a natural choice as it has been adopted by many
blockchain projects. However, this is largely an open issue.
All being said, as a proposal, it is my opinion that we should support
Groth16-BN254 at the beginning. Based on that we could build recursive
verification circuits for other scheme, which does not require a soft fork.
Other schemes and curves, if much desired by the community, could be
included as well. Maybe we can designate a separate BIP for each
scheme-curve pair for direct support (instead of recursive verification).
*### 6. Potential uses*
The potential uses are unlimited: payment aggregation for a fee reduction
or anonymity, stablecoin, DeFi, decentralized exchange, DAO, NFT, etc.,
just to name a few. But still, we could take as an example some uses to
check if any issues arise and discuss how to address them.
A. ZKP-based smart contract. We could reasonably assume ZKP-based smart
contracts to be rather different from consensus-based smart contracts
(although OP_ZKP is part of a script). A notable difference is that with
Bitcoin’s UTXO model instead of account-model, account-balance type of
contracts are hard to build without involving external storage or state
management. And even with external storage involved to manage the states,
the security of the external storage is also a concern. Data might be lost
or corrupted. Bitcoin’s security does not extend to those contracts
automatically. It takes innovations to address these issues.
On the other hand, there could be smart contracts without a need for
explicit state management. This could be gaming or decentralized identity,
that a ZKP proof is used to prove ”something happens or exists according to
designated algorithm or criteria“.
B. Payment aggregation, or Bitcoin Layer 2. Every address can participate
in such a protocol by sending certain Bitcoin to the designated address
(the fund-holding address). Once signed up, participants can send Bitcoin
to each other with very little fee or pays a higher fee to send to Layer 1.
Bookkeeping each participant’s “balance” is a challenge, but might be
achievable via some complex circuits proving the ownership of certain UTXO
entries. Once proven, the fund-holding address can send Bitcoins to the
address as requested by the participant. It is another challenge to
maintain those UTXO entries off the Bitcoin network with high security. We
might also need to segregate those UXTOs from the Bitcoin network so that
no transaction can be replayed to the Bitcoin network or another Layer 2
protocol.
*### 7. Ecology implications*
Proof generation, computing power services/vendors. Some proof might be
very computationally intensive to generate, for example, recursive
verification of thousands of OP_ZKP transactions. In that case, computation
power services or vendors can work with miners to speed up the generation,
or simply propose a bundle of transactions to be included in a block. By
paying a higher fee miners are motivated to include the bundle, while the
service or vendor can still profit a lot. The immediate reward could
incentivize lots of efforts to further optimize the implementation,
engineering, algorithms, or even ZKP schemes.
Contract composability. We need to figure out a systematic way for one
smart contract to call another, either on-chain or assisted-off-chain. For
ZKP-based smart contracts, proof will have to be generated off-chain and
then used later to call the target contract. Off-chain vendors could
monitor closely related signals, generate the proof, and submit it to the
Bitcoin network. There should be incentives to ensure the proper running of
the system. It is still an open issue about how to define a cross-contract
API, how to signal the call, and how to incentivize computation power
vendors.
Impact on wallet applications. Generating proof to authorize spending seems
a heavy-duty computation task, and does not seem to fit into mobile
applications or hardware wallets, especially those with SoC and powered by
a small battery. However, we argue that this is not the case. If no secret
(private key or seed) is involved, there is no need to involve a wallet
that is tasked with safekeeping secrets. In such cases, the ZKP proof could
be proof that something has indeed happened or exists (including a
signature issued from a wallet), which makes up spending conditions.
That's it for now. I hope you are interested in this idea. I look forward
to your comments.
Thanks,
Weiji
[1] -
https://docs.zkproof.org/pages/standards/accepted-workshop4/proposal-aggregation.pdf
[2] - https://eprint.iacr.org/2020/081.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230428/8d114f17/attachment-0001.html>

2023-06-07 18:15:15

- reply

📅 Original date posted:2018-11-09
📝 Original message:> Do you specifically want to support changing the language of seed
words, while keeping the bip32 root seed they generate unchanged?
What is the usecase for this?
Yes and no. Yes that the inter-operability will be much better if the
same seed could be recorded as in English and in other languages
as well. There could be a standalone 3rd party tool to convert
mnemonic sentences from one language to another so wallets
do not have to support all languages. This, in reality, does not make
any wallet more complicated or increase any dev costs.
No that I don't think anyone would switch language for fun.
And I think the symmetric function in SLIP-0039 is a good
idea to help with migration the existing wallets. So this will look like:
Chinese
English
Japanese <=> entropy <=> sym. KDF <==> BIP32 seed
......
Decimal numbers
>If changing the language of seeds is not a requirement, then look
into Electrum seeds. They are language/wordlist agnostic.
So, changing the language is not a requirement. However, the current BIP-39
makes the seed dependent on the language. And I'd like to see it changed.
The change will not further complicates the wallets as we can rely on 3rd
conversion tools to handle different languages.
One additional benefit multiple language support could bring up is, we can
write down the mnemonic sentence in two or more different languages
simultaneously, as a way to do checksum each other.
Regarding Jon's comments:
>lack of localized words for recovery phrase causes more money loss than
supporting it.
This also worries me.
Think of the situation that one day, crypto currencies are all over the
world.
Everyone has some coins. Among them many just cannot handle English.
We must provide a way for them to master their crypto assets. Therefore,
as Jon had stressed, it is very important to support multiple languages.
I really don't like it if only English could be used.
And then think of those who do not have a native language wordlist. Allowing
representing the seed in decimal numbers will be helpful.
Thanks,
Weiji
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20181109/8f432b2e/attachment.html>

2023-06-07 18:15:08

- reply

📅 Original date posted:2018-11-22
📝 Original message:Hi Everyone,
Thank you very much in this thanks giving day for the detailed and well
thought out responses. :)
Steven Hatzakis via bitcoin-dev <bitcoin-dev at
lists.linuxfoundation.org
<https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>>:
>* *Option 2*: Perhaps a revision is needed to how the BIP39 seed is
*>* generated in the first place, such as by hashing the entropy instead of the
*>* words. Any thoughts on how viable that could be where the initial entropy
*>* is fed into the PBKDF2 function and not the words?*
If we go this direction, I'd suggest that we pull Shamir's Secret Sharing
into the game. Trezor's
SLIP-0039 proposal is great and has many security aspects already covered.
However, it does
not allow any language other than English and Trezor team clearly stated
that no other language
will be supported.
While I really want to keep the language independent design. So in the
revision, I'd like to see
a language id (allocated to each one having a defined wordlist) in the SSS
share, as well as
share id, threshold, index, share value, checksum etc.
Regarding checksum scheme, SLIP-0039 proposals a 3-word Reed-Solomon
design. It has a very
good error checking capability but not very good at providing hints to
error recovery. Trezor team
opposes to the idea of providing hints to users regarding how to fix an
error. This could lead to
difficulties for some vendors, and in small probability, confusions to
users (when there is a 2-word
error)
I do agree with Trezor team that it should be users' responsibility to
recover from a detected error.
However, there is a better way than solely rely on checksum. That is, as in
our revision, we can
support mnemonic in multiple languages simultaneously, why don't we use two
languages, or one
language + numbers to check each other? In Steven's example (language id,
share id, etc. skipped)
we could record a SSS share (assuming it is one of the shares just for the
sake of example) like:
>* *In English*: minimum fee sure ticket faculty banana gate purse caught
*>* valley globe shift
*>* *In Spanish*: mercado faja soledad tarea evadir aries gafas peine búho
*>* tumor gerente reja*
Or
>* *In English*: minimum fee sure ticket faculty banana gate purse caught
*>* valley globe shift*
>* Word Indexes: 1128, 676, 1744, 1805, 653, 145, 770, 1396, 291, 1927,
794, 1582*
Then software will have to check checksum as well as to check if words
match each other. For
example, "minimum"'s index value in English wordlist should equal to "
*mercado*"'s in Spanish,
or should equal to 1128.
If any error is detected, combining the checksum value and dual-encoding
information, it is much
easier to figure out which word was handprinted incorrectly.
BTW, it is very error prone to handprint. Some study suggests about 0.9%
per word rate. See
http://panko.shidler.hawaii.edu/HumanErr/Basic.htm
Hotopf [1980]
W sample (written exam). Per word
0.9%
It is important to have an error recovery mechanism easy to understand and
implement.
Thanks,
Weiji
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20181123/883b184a/attachment-0001.html>

2023-06-07 18:15:07

- reply

📅 Original date posted:2018-11-06
📝 Original message:Hello everyone,
I just realized that BIP-0039 is language dependent. I was assuming the
other way till I looked closer. The way the seed is derived from a BIP-0039
entropy, as is shown below, depends on which language to generate the
mnemonic sentence:
Entropy <=> Mnemonic Sentence => PBKDF2 => BIP-0032 Seed
Therefore when a user choose a non-English mnemonic code he or she is stuck
with that language. Meanwhile only a few native languages are supported.
SLIP-0039 does not solve this issue in a user friendly way by providing
only an English wordlist. That's understandable as it aims to provide SSS
capability. However those users who do not speak English or recognize
English words will suffer.
What I am trying to bring to attention of the community is that, no matter
if we make a new version of BIP-0039, or a new BIP (with SSS support), or
to enhance SLIP-0039, we really need to address this language issue.
Here are what I propose:
1. The mnemonic code should be only a representation of underlying entropy
or (pre) master secret, seed, whatever. In this way, the same seed/secret
could be displayed in English or in Chinese or other languages. Then there
could be 3rd party conversion tools to support translations in case any
wallet software or device does not support all specified languages. Now it
looks like:
Mnemonic Sentence <=> Entropy => PBKDF2 => BIP-0032 Seed
2. Given that only 8 languages are supported in BIP-0039, we should allow
the seed/secret to be represented in decimal numbers, each ranging from 0
to 2047. So those who cannot find a native language support yet having
difficulty coping words in other languages could choose to just use numbers.
So far I don't have a preference how this should be implemented. I'd like
to hear from community first.
Thanks,
Weiji Guo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20181107/88677440/attachment.html>