Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Exploring Trustless zk-SNARKs for Monero's payment protocol #100

Open
sethforprivacy opened this issue May 2, 2022 · 114 comments
Open

Exploring Trustless zk-SNARKs for Monero's payment protocol #100

sethforprivacy opened this issue May 2, 2022 · 114 comments

Comments

@sethforprivacy
Copy link

sethforprivacy commented May 2, 2022

The goal of this meta issue is to build a go-to place for links, information, and opportunities for building trustless zk-SNARKs as a potential future protocol building-block for Monero.

Disclaimer: I am not a cryptographer or a dev, so please provide corrections and context if I have missed key details here. I am merely seeking to pull people together who are, provide resources, and ensure we take as close of a look as necessary at zk-SNARKs as a potential upgrade for Monero in the future.

Why zk-SNARKs?

Monero has iterated over the years to continue in leading the way in building out a cryptocurrency that puts user's privacy and security above all else. The Monero community has done this through finding the gaps and flaws in the protocol, watching external projects and researchers work, and implementing both internal and external developments over time to improve the holistic privacy provided to every user of the Monero network.

The weakest aspects of Monero's current approach to privacy is that of ring signatures, the approach that is taken to hide the true spend in each transaction among a set of potential signing inputs. These ring signatures have been an excellent tool for Monero so far, allowing us to build stable, efficient, and trustless privacy into each transaction, and are greatly strengthened by the added privacy of one-time addresses and confidential amounts.

While these three building blocks provide strong privacy today and show no signs of causing broad issues, they have noted weaknesses, especially for targeted threat models or those where multiple entities collude to form a transaction graph via EAE attacks or similar. This key weakness, combined with the ability to build probabilistic transaction graphs with off-chain data, should push us to keep seeking how we can mitigate the issue entirely.

The proposed Seraphis protocol allows us to greatly reduce the chances of successful probabilistic tracing, but is not necessarily a complete solution for targeted attacks or those aided by off-chain metadata. I do not want to prevent the further exploration of Seraphis with this effort, and a migration to Seraphis could even simplify a potential future migration to zk-SNARKs thanks to the modularity of Seraphis approach to the payment protocol.

zk-SNARKs allow us to move from obfuscating the true spend to truly hiding it, a large step forward in preventing even targeted attacks from building a transaction graph, while doing so in a way that remains trustless and efficient.

While it is outside of the scope of this issue, zk-SNARKs can also be used to build out much more advanced protocol features such as colored coins, smart contracts, etc. like currently being built out by DarkFi. This flexibility can pave the way for greater use-cases being built out on Monero in the future, and could be an extremely useful building block.

Why now?

With the advent of trustless and relatively efficient zk-SNARKs via advances like PLONK and implementations of it like Halo 2, zk-SNARKS are finally at a state where we can truly explore what an implementation of them in Monero's broader transaction protocol would look like, the implications it would have, the leg-work required, etc.

While Seraphis will bring much greater per-transaction graph obfuscation, it still provides some attack vectors for targeted attacks. As such, we should keep looking to the future and find ways that we can continue improving the Monero protocol over time.

Proposed efforts

While I know this is a major shift in the approach Monero has taken to output hiding in the past, there are some unique opportunities available to us today thanks to the wealth of effort being poured into zk-SNARKs across the cryptocurrency and privacy ecosystem today.

  1. Amir Taaki (@narodnik) of Dark.fi has offered to contribute whatever education/bootcamping is necessary to get Monero developers up to speed on implementing zk-SNARKs in a payment protocol
    1. Amir's estimate is ~2wks of full-time bootcamping to get up to speed and implement a PoC in a simple language
    2. I would love to see developers that are familiar with cryptography/math jump in on this and will help in crafting a CCS proposal for funding if necessary
  2. If necessary, I will organize a meeting of the MRL to discuss the viability of zk-SNARKs in the Monero protocol
  3. I will write up a blog post further outlining in laymen's terms why exploring zk-SNARKs as a replacement for ring-signatures (and likely confidential amounts) is an interesting and worthwhile topic to explore for the community (can publish on my own blog or getmonero.org if suitable)
  4. Collect feedback on ways that a migration to zk-SNARKs would effect current ecosystem participants, atomic swaps development, etc.

Open research questions

There are many open questions that we would need to (or should) answer in the process of exploring what an implementation of trustless zk-SNARKs would look like in Monero. If you want to take on one of these open questions, please open a new issue/gist and provide the link so I can update it here.

  • Can zk-SNARKs offer improvements to specific functions in the Monero payments protocol, i.e. just membership proofs?
  • What are the practical implications to user privacy with ring-signatures vs a zk-SNARK approach to input hiding?
    • What attacks or flaws in ring-signatures are mitigated by zk-SNARKs?
    • What new attacks or flaws are created by zk-SNARKs?
  • What would the potential transaction size, generation, and verification times look like for a Halo 2-like payment system in Monero?
    • How would transaction verification be affected by batching? How about multithreading?
    • Can mobile devices easily and quickly generate transactions?
  • Can existing hardware wallets (Trezor/Ledger) support a zk-SNARK system for Monero?
  • What is the quantum-resistance offered by zk-SNARKs as opposed to ring signatures + RingCT?
  • What effects would a migration to zk-SNARKs have on atomic swaps with Bitcoin and Ethereum?
  • What advantage or disadvantage would the elliptic curves used in a zk-SNARK implementation have on interoperability between Monero and other networks/chains?
  • What functionality extensions can zk-SNARKs bring to Monero's base layer?
    • Layer-two networks?
    • Smart contracts?
    • Colored coins?

Extra notes

  • We do not need to leverage any of Zcash's existing code for this, and can (and should!) explore a from-scratch implementation in C++ that better fits our broader payment protocol
  • I hope that we can see past the "Monero v Zcash" ongoing drama and approach this from a research and technology perspective, especially as much of the technology and research here was invented or improved upon by researchers and developers entirely outside of the Zcash space
  • zk-SNARKs have a lot of weight behind them in the privacy space, layer-two developments space, Zcash space, and other places, making them a great option to explore as we can benefit greatly from the broad academic and development work ongoing around the concept of trustless zk-SNARKs

Helpful links

Educational resources and explainers

Existing implementations and code examples

P.S. -- if you come across helpful research that could be applicable to zk-SNARKs in Monero, please consider submitting it for inclusion on https://moneroresearch.info.

@sethforprivacy sethforprivacy changed the title [WIP] Exploring Trustless zk-SNARKs for Monero's payment protocol Exploring Trustless zk-SNARKs for Monero's payment protocol May 2, 2022
@jstkdng
Copy link

jstkdng commented May 2, 2022

Hey man, blink if you've been compromised by any 3 letter agencies.

@sethforprivacy
Copy link
Author

sethforprivacy commented May 2, 2022

Hey man, blink if you've been compromised by any 3 letter agencies.

Exploring broadly used and researched tech has nothing to do with any 3 letter agencies. Take your spam elsewhere, please, this is supposed to be a place for on-topic discussion into research topics, not pointless harassment.

The topic of zero-knowledge proofs (and zk-SNARKs) is much broader than Zcash, so don't let your animosity (for good or bad reasons) towards them cloud your judgement on the broader technology.

@narodnik
Copy link

narodnik commented May 2, 2022

Hey, so I wrote the first implementations of coinjoin and stealth addresses, and implementations of all the major anon algos: ring sigs, mimblewimble, lelantus, bulletproofs, and the major zk algos: groth16, sonic, plonk, halo1, halo2, ... and a ton of experiments.

I did a ton of optimization on ring sigs, and got 100k keys verification down to a few secs, but that still isn't good enough since the glowies can put in fake duds to compromise the anon set. Lelantus/jens groth 1 out of n proofs are decent, but Zk is the best. Verification is only a few ms, and the anonymity set is practically infinite (2^32).

For your implementation, you don't need orchard since you should write your own zk contracts (called "circuits"), which is trivial enough to do. If halo2 being in rust is a problem, then you should look at aztec's plonk implementation which is in C++.

ZK proofs are two parts:

  • Arithmetization which is turning your contract into a mathematical arithmetic operators add and multiply. This part is relatively simple and straightforward to grasp.
  • Polynomial commitment proof, which is given a commitment A = commit(a(x)) to a polynomial, you can make a proof pi = prove(A, s, a(x)) which then a verifier can prove that z = a(s) like this: verify(pi, A, s, z) which doesn't reveal a(x) itself.
halo2 = plonk arithmetization + bulletproofs polynomial commitment proof

So basically Monero already contains the core component of zk-snarks (which is used for rangeproofs).

For the arithmetization, we can talk to aztec. Ariel Gabizon invented plonk which is actually what halo2 is really, the zcash team replaced the polynomial commitments with bulletproofs instead of the KZG scheme which has a trusted setup. Happy to make that intro. Their plonk implementation is in C++ iirc.

From our side, we're happy to work with a team of focused Monero devs to step them through the algo and get them up to speed, and then follow their development doing code reviews and offering feedback. We have several devs in our team writing zk contracts and who are familiar with zk algos.

Monero is the backbone of the crypto minecraft markets, and our community deserves the very best. Self defense of the people is crucial in this coming dawn of the new era.

@parazyd
Copy link

parazyd commented May 2, 2022

On top of this, I've written a VM and a language + compiler for prototyping ZK circuits/contracts with Halo2: https://darkrenaissance.github.io/darkfi/zkas/

And indeed, we're happy to help with advice and guidance if there is proper focus and commitment.

@sethforprivacy
Copy link
Author

Thanks for the comments and details, @narodnik, demistifying the approaches taken in something like Halo 2 is extremely helpful. Very grateful for the offer of help and the quick input, and am hopeful this exploration can be meaningful and lead to a potential future implementation for Monero.

I've also tracked down and added the link to the Aztec PLONK implementation in C++ to the Helpful Links section.

@UkoeHB
Copy link

UkoeHB commented May 2, 2022

I did a ton of optimization on ring sigs, and got 100k keys verification down to a few secs, but that still isn't good enough since the glowies can put in fake duds to compromise the anon set. Lelantus/jens groth 1 out of n proofs are decent, but Zk is the best. Verification is only a few ms, and the anonymity set is practically infinite (2^32). @narodnik

Am I reading this correctly, and you know how to implement a membership proof ('ring sig') with Zk (a Halo2 circuit)? I already have a full transaction protocol (Seraphis) that just wants a better membership proof (ideally one that can just plug-and-play with the rest of the protocol, even if a different underlying curve than ed25519 is required). My confusions with this Halo2 stuff are whether anyone actually knows how to make a membership proof with it, what the design of that circuit would look like (some kind of oblivious Merkle or Verkle proof?), and what requirements it would impose on the surrounding protocol (curves, ways of building points, prerequisites to build and verify proofs, etc.).

@kayabaNerve
Copy link

kayabaNerve commented May 2, 2022

Zcash's circuits are Merkle tree based, from my understanding. Instead of key images, you specify nullifier hashes, and the ZK proof says it's some member of the merkle tree (whose root hash is referred to as the anchor) which is appended to with each output.

Regarding Seraphis, it's important to note an isolated ZK proof for membership would be incredibly inefficient. You'd want one proof for both membership and validity. It'd effectively be two BPs to have it as an isolated proof when they'd be mergeable to just one.

I'd be personally interested in shadowing these discussions.

@UkoeHB
Copy link

UkoeHB commented May 2, 2022

To clarify, a Seraphis membership proof needs to say the following:

  • we have a vector of points V = {Q_1, Q_2, ... Q_n}
  • I have a commitment Q' = xG + Q_l for some l
  • the membership proof shows that Q' is a commitment to a member of V but doesn't show which one
  • after the membership proof is done, I can do whatever normal EC ops with Q' that I want (ideally, in ed25519)

After discussing with @kayabaNerve, the above proof seems possible with existing techniques (it is the simplest possible zk proof that we could use). Stuff like recursive proofs, nullifier hashes, etc... don't really get me excited. Batch verification would get me excited (specifically batching with BP+ proofs - can we share generators? please yes please). Combining range proofs with the membership proofs in one zk proof is an interesting idea iff the efficiency gains are well understood and non-trivial. Combining them is not necessary, and could easily be rolled out in an update after the one that implements the simple membership proof (if deemed worthwhile).

@kayabaNerve
Copy link

kayabaNerve commented May 3, 2022

I did agree to put forth a demo of the above in Rust when I have the time, based on discussions on Matrix. That isn't a pivot within Seraphis, to either ZK-SNARKS nor Rust, yet it's a comment on potential API/flow/performance. I may use either Dalek's Bulletproofs (which would likely be the easiest to move from a PoC to something actually in C++ in Monero, guaranteeing ed25519 and batch verification) or Halo 2, or another PLONK system, and have yet to decide.

@narodnik
Copy link

narodnik commented May 3, 2022

Aha so Seraphis is based off of Jens Groth 1 out of N commitment to 0? That's also a solid anonymity scheme.

Yes, we have the membership proofs working. They are quite easy to do. You provide the pathway in a merkle tree then inside the zk proof, you do:

current = X
for i in range(32):
    left = current
    right, is_right = merkle_path[i]
    # since is_right is a bool, you can do this:
    #     is_right * left + (1 - is_right) * right
    #     is_right * right + (1 - is_right) * left
    left, right = if is_right { left, right } else { right, left }
    current = hash(left, right)

The basic ZK payment scheme is the following:

Mint:

private serial = random_scalar()
private blind = random_scalar()
public C = hash(serial, blind)

Then the coin C gets added in the merkle tree.

Burn:

public nullifier = hash(serial)
private C = hash(serial, blind)
assert C in merkle_root
make_public(merkle_root)

In practice we add more attributes to the coin C such as a public key (so nullifier can only be constructed by secret key), a value (so we hide amounts with CT), a token ID, and other attributes (such as permissions or owners).

@kayabaNerve
Copy link

kayabaNerve commented May 3, 2022

Right. I am sufficiently familiar with the Zcash side of things to know the algorithm to use for this.

I also do understand Zcash is just one of many players in the field, yet they're the one I'm most familiar with and they do use merkle trees to store their outputs (with the Sapling input proof containing merkle tree pathing). I've also reviewed Tornado Cash which has its own merkle tree work and understand the multiplication used to achieve constraint definitions successfully. I only expect it to take a few hours to a couple of days, personally, I'm just busy for a bit.

@narodnik
Copy link

narodnik commented May 3, 2022

You guys don't need to code the zk contracts (circuits). Here is the code for halo2:

https://github.com/darkrenaissance/darkfi/blob/master/src/zk/circuit/mint_contract.rs

https://github.com/darkrenaissance/darkfi/blob/master/src/zk/circuit/burn_contract.rs

It's more if you want to make your own plonk/halo2 prover/verifier system instead of using aztec or halo2 lib. That would be the work that actually takes time.

@kayabaNerve
Copy link

kayabaNerve commented May 3, 2022

narodnik: That isn't the point. At all.

koe is specifically requesting a simple membership proof which is a trivial circuit to write. I am personally interested in providing such a demonstration so not only can they get a feel for it in a very self contained box, yet I can finally say I've successfully written a circuit. If your goal is to encourage Monero developers to move from the theoretical to the implementation, I'd hope you agree with my goal. If you'd rather simply post a Rust demo which handles membership and lets us do feasibility analysis, and be the Monero developer, you can also do that. I can't exactly complain in that case.

I will note your examples include nullifiers which is not what koe is requesting. While I advocated for the input ZK proofs as an equivalence to the modern CLSAG, Seraphis has a distinct design which separates membership proofs from linkability from range proofs. Personally, I can see why that might have an advantage. If we're able to define an accumulator which solely contains outputs, and only ever have to prove membership in it, we can change our membership proof (say, from Bulletproofs to Halo 2 or from Halo 2 to Halo 3 or from Halo 3 to Halo Reach) without needing to define a new transaction pool as the linkability proof would remain constant and consistently formed. While it should also be possible without issue for such a limited output definition to produce consistent nullifier hashes across such proof formats, I am trying to note the potential advantages of a flexible and concise design and the considerations desired. The other important items are the distinction between spend authorization and spend detection (outgoing view keys, which I know plenty of existing SNARK systems offer, yet a distinct linkability proof may simplify), and the feasibility of multisig.

While I don't know the full details of how this may play out, I will say the immediate task is solely the membership proof as that serves a drop in role to the currently designed next protocol with no further considerations needed. From there, it's a discussion on evolution and moving more items over as proper. I'm also more interested in a BP+ design than a Halo 2 design at this point so Monero can more easily integrate it, as unfortunately there may be an aversion to Rust, not to mention the fact we already have BPs available (so we'd also not require adding an entirely external cryptsetup we haven't reviewed).

This is a very experimental topic opened by @sethforprivacy. koe, who's effectively leading the next transaction protocol, didn't want to immediately start a potentially not used idea with reformatting back to the existing system (membership + linkability as a single proof), and instead just wants a simple membership proof as a demo. I, as a developer who can probably write a basic circuit and was here to comment, offered to. This change won't happen overnight. You're welcome to post a series of ZK circuits based on Halo 2 and say Monero should move to it and leave it at that. The discussion being had here is taking it one step at a time. We have the option for a more efficient membership proof (one which is vastly more private). Once we have that proven, we'll see how else we can improve along this path.

You're obviously someone who has more experience than anyone who has commented thus far (except maybe parazyd who's with you :p ) and I'd appreciate your help as I work on a PoC, as I need it, and your help as we discuss protocol boundaries and further movements from there if we continue the discussion. I just, at least personally, don't appreciate being dumped full setups and being told we don't need to do anything. Seraphis is the future privacy protocol for Monero and accordingly needs to be the perfect fit for Monero. If an existing protocol is that perfect fit and has the most efficient code, I would see no issue with adopting it. If we were willing to accept something potentially good enough because it already existed... we probably wouldn't have made RingCTs and would still have public amounts :p

The important part is there needs to be a process here instead of a statement. Any process is going to be based off the current plan, which is Seraphis. koe's statement on the next step for bringing SNARKS into Seraphis is just a membership proof. If it legitimately is more efficient and it's believed to be feasibly integrateable... then it needs to be discussed with other developers from a variety of standpoints (extending our own BP+ impl to include programs, implementing another system, grabbing a C++ library, officially introducing Rust to the toolchain...). It's just a process.

EDIT: I will also note the provided code is AGPL which means we can't even use it in a proof of concept without the proof of concept being AGPL and... while I have no issue with AGPL in the right place, and a PoC should be an isolated PoC which means it shouldn't be an issue, I would like to avoid any licensing issues while this is prototyped and worked with.

@narodnik
Copy link

narodnik commented May 3, 2022

lmk then what you need.

I would proceed like this:

  • Learn plonk algo
  • Learn halo2 algo
  • Write simple circuits such as mimc or poseidon hash functions
  • Implement your merkle proof

You can also start with the merkle proof then go backwards. You might want to do all of this in sage/python.

@UkoeHB
Copy link

UkoeHB commented May 3, 2022

In practice we add more attributes to the coin C such as a public key (so nullifier can only be constructed by secret key), a value (so we hide amounts with CT), a token ID, and other attributes (such as permissions or owners). @narodnik

It sounds like a lot of the work put into these zk circuits focuses on building a large transaction protocol within the circuit (i.e. proving many kinds of statements within a single proof). Unfortunately, there are always design and efficiency consequences to coupling proof statements. In Cryptonote/RingCT, we had multiplicative inefficiency in the ring signatures in addition to a clumsy key image construction. In all privacy protocols that couple 'ledger membership' of inputs with 'ownership/authorization' and 'unspentness', it is impossible to build transactions in a modular fashion. We are stuck building an entire transaction in one pass (or preparing a full tx context before doing a full construction pass).

With Seraphis I am trying to break away from that past common sense. Every piece of the protocol is as loosely coupled as possible. Txos (I call them enotes) can be constructed in isolation (no related tx context). Membership proofs don't need to be constructed until right before a tx is submitted to the ledger (letting you chain transactions together completely off-chain, and/or hide timing information about when a tx started being built). Input proofs of ownership and unspentness can be individually and separately constructed (allowing multiple parties to contribute funds to a tx), are only coupled to the set of outputs (another requirement for tx chaining), and the linking tags (key images) can be proven valid without a membership proof (allowing senders/recipients of funds in an off-chain environment to be fully confident about balance changes). Range proofs and the balance proof can be defined as soon as the set of inputs and outputs are known (another requirement for tx chaining: you should be able to chain off txs that are completely valid within the protocol rules as soon as membership proofs for inputs are added - which can be trivially mocked, letting you easily validate partial txs).

Given the advantages of tx modularity, I really am looking forward to the simplest solution zk circuits can offer - just the membership proof piece. If there are non-trivial advantages to moving other pieces within the circuit (probably just the range proofs, which are the bulk of verification and tx size cost next to membership proofs), then absolutely let's consider it. One step at a time :)

@sethforprivacy
Copy link
Author

As the conversation is referring to Seraphis quite a bit, just linking the protocol and current code here for reference and clarity:

https://github.com/UkoeHB/Seraphis
https://github.com/UkoeHB/monero/tree/seraphis_lib
https://github.com/UkoeHB/monero/tree/seraphis_perf

@mckibbinusa
Copy link

Intriguing idea, but is the idea implemented? I read, "zk-SNARKs allow us to move from obfuscating the true spend to truly hiding it, a large step forward in preventing even targeted attacks from building a transaction graph, while doing so in a way that remains trustless and efficient." I am eager to see how one 'hides' the true spend within a deterministic algorithm. Such a method could create vast risks beyond the known and measurable risks of obfuscation outcomes.

@kayabaNerve
Copy link

kayabaNerve commented May 8, 2022

It's not anymore deterministic than rings are. rings used exposed members, randomly selected from a larger subset, and then creates a signature with 11 decoy responses. The actual response then replaces its decoy, itself combined with a random value to prevent private key recovery.

With circuits, every member is exposed, because that's how outputs work. That said, we use every member, not just a subset. Randomness isn't needed here, as it wouldn't be if we created a ring of every single output. Same amount of randomness.

The distinction is there's no decoy responses. "So if I see your actual response and it alone I'll instantly know your actual spend!" Well... no. This is because the response, a variable, is combined with a random value just as regular signatures are. Sure, we eliminate decoys, but the response given looks the same as a response for any other member proof, which is all decoys needed to do (look identical to the actual to hide the actual). Since the actual looks identical to any other actual, and we never actually reveal any of the variables... it works.

Now if you want to ask how we can verify variables we don't know... magic. ZK circuit magic. I honestly can't say I know enough of to sit and write it out at an academic level. I know enough to work with it though and am here to do exactly that.

To provide an extremely basic explanation, every variable is composed of two things. The actual variable and a blinding factor (random value). These are combined via a Pedersen commitment (which we use to hide output amounts). Then, we can provide a proof that for a theoretical variable, it was executed according to this code, and we can verify that because we can provide data constructed from the variables and blinding factors as needed (yet not the actual blinding factors as that would remove the blinds and reveal everything). If we executed different code, the blinding factors wouldn't line up, and...

@baro77
Copy link

baro77 commented May 9, 2022

halo2 = plonk arithmetization + bulletproofs polynomial commitment proof

so does halo2 ultimately rely on Fiat-Shamir heuristic (instead of legacy SNARKs' CRS/trusted setup) to gain non-interactiveness?
I'm speaking about things I don't still really know, anyway just to have a bird's-eye view of the whole context, what about any implementation of Groth-Sahai NIZK flavour ?

@kayabaNerve
Copy link

When discussing implementation into Monero, I'm mainly interested in keeping with the existing technology (Bulletproofs) available rather than distinct systems, especially for the initial circuit we consider deploying. Potentially more efficient systems, such as Halo 2 as a whole, or other systems, seem a bit much given the immediate discussion, and resources, at hand (in my opinion).

@baro77
Copy link

baro77 commented May 10, 2022

@kayabaNerve I understand your point. If your message has been inspired by mine, I have to explain that my question was just to take advantage of @narodnik knowledge about the field (which seems to me the highest here) to sketch the context...

There's hype about halo2 'cause it doesn't need trusted setup, but if it avoids CRS by use of Fiat-Shamir heuristic it's important to be known because it's weaker than a non-interactiveness by trusted setup under standard assumptions... It's true that Fiat-Shamir it's also used in Schnorr signature and Bulletproof so ROM is an already accepted ideal-model someway, but I asked about Groth-Sahai NIZK flavour because I have read that -if I'm not wrong- it could offer non-interactiveness without trusted setup but under assumption provable in the standard model.

So let's say I was trying to have an idea of the widespread context, believing it's useful to be more aware of choices and their tradeoffs. That said, you are right that maybe it's a bit much given the purpose of the discussion, I have ventured 'cause anyway there's not a lot of traffic here

@baro77
Copy link

baro77 commented May 19, 2022

BTW I think I have to withdraw my question to narodnik 'cause in my day-by-day learning I think to have understood that Groth-Sahai NIZKs do not avoid CRS

@narodnik
Copy link

narodnik commented Dec 31, 2022

Basically gave up on this thread. Not much actual desire to learn or do anything, just make up random excuses. Adding arithmetization on top of the existing bulletproofs for a set inclusion proof is perfectly doable and not difficult. I already linked the 300 line sage script above but nobody actually bothered to look or try to understand.

I'm cross posting a benchmark I shared elsewhere here in case it's useful for people in the future.

use darkfi::{
    zk::{
        proof::{Proof, ProvingKey, VerifyingKey},
        vm::{Witness, ZkCircuit},
        vm_stack::empty_witnesses,
    },
    zkas::decoder::ZkBinary,
    Result,
};
use darkfi_serial::Encodable;
use darkfi_sdk::{
    crypto::{
        pedersen::pedersen_commitment_u64, poseidon_hash, MerkleNode, PublicKey, SecretKey, TokenId,
        constants::MERKLE_DEPTH, Nullifier
    },
    incrementalmerkletree,
    incrementalmerkletree::{bridgetree::BridgeTree, Hashable, Tree},
    pasta::{
        arithmetic::CurveAffine,
        group::{
            ff::{Field, PrimeField},
            Curve,
        },
        pallas,
    },
};
use halo2_proofs::circuit::Value;
use rand::rngs::OsRng;

type MerkleTree = BridgeTree<MerkleNode, { MERKLE_DEPTH }>;

fn main() -> Result<()> {
    let mut tree = MerkleTree::new(100);

    // Add 10 random things to the tree
    for i in 0..10 {
        let random_leaf = pallas::Base::random(&mut OsRng);
        let node = MerkleNode::from(random_leaf);
        tree.append(&node);
    }

    let leaf = pallas::Base::random(&mut OsRng);
    let node = MerkleNode::from(leaf);
    tree.append(&node);

    let leaf_position = tree.witness().unwrap();

    // Add 10 more random things to the tree
    for i in 0..10 {
        let random_leaf = pallas::Base::random(&mut OsRng);
        let node = MerkleNode::from(random_leaf);
        tree.append(&node);
    }

    let root = tree.root(0).unwrap();

    // Now begin zk proof API

    let bincode = include_bytes!("../proof/inclusion_proof.zk.bin");
    let zkbin = ZkBinary::decode(bincode)?;

    // ======
    // Prover
    // ======
    // Bigger k = more rows, but slower circuit
    // Number of rows is 2^k
    let k = 11;
    println!("k = {}", k);

    // Witness values
    let merkle_path = tree.authentication_path(leaf_position, &root).unwrap();
    let leaf_position: u64 = leaf_position.into();

    let prover_witnesses = vec![
        Witness::Base(Value::known(leaf)),
        Witness::Uint32(Value::known(leaf_position.try_into().unwrap())),
        Witness::MerklePath(Value::known(merkle_path.clone().try_into().unwrap())),
    ];

    // Create the public inputs
    let merkle_root = {
        let position: u64 = leaf_position.into();
        let mut current = MerkleNode::from(leaf);
        for (level, sibling) in merkle_path.iter().enumerate() {
            let level = level as u8;
            current = if position & (1 << level) == 0 {
                MerkleNode::combine(level.into(), &current, sibling)
            } else {
                MerkleNode::combine(level.into(), sibling, &current)
            };
        }
        current
    };

    let public_inputs = vec![leaf, merkle_root.inner()];

    // Create the circuit
    let circuit = ZkCircuit::new(prover_witnesses, zkbin.clone());

    let now = std::time::Instant::now();
    let proving_key = ProvingKey::build(k, &circuit);
    println!("ProvingKey built [{} s]", now.elapsed().as_secs_f64());
    let now = std::time::Instant::now();
    let proof = Proof::create(&proving_key, &[circuit], &public_inputs, &mut OsRng)?;
    println!("Proof created [{} s]", now.elapsed().as_secs_f64());

    // ========
    // Verifier
    // ========

    // Construct empty witnesses
    let verifier_witnesses = empty_witnesses(&zkbin);

    // Create the circuit
    let circuit = ZkCircuit::new(verifier_witnesses, zkbin);

    let now = std::time::Instant::now();
    let verifying_key = VerifyingKey::build(k, &circuit);
    println!("VerifyingKey built [{} s]", now.elapsed().as_secs_f64());
    let now = std::time::Instant::now();
    proof.verify(&verifying_key, &public_inputs)?;
    println!("proof verify [{} s]", now.elapsed().as_secs_f64());

    let mut data = vec![];
    proof.encode(&mut data)?;
    println!("proof size: {}", data.len());

    Ok(())
}
constant "InclusionProof" {
}

contract "InclusionProof" {
	Base leaf,
	Uint32 leaf_pos,
	MerklePath path,
}

circuit "InclusionProof" {
	constrain_instance(leaf);

	# Merkle root
	root = merkle_root(leaf_pos, path, leaf);
	constrain_instance(root);
}

k = 11
ProvingKey built [1.393294228 s]
Proof created [1.105254593 s]
VerifyingKey built [1.240241996 s]
proof verify [0.018967216 s]

This is using bulletproofs for inner product proof, so there's no trusted setup.
It proves that $leaf has a pathway to $root without revealing the exact path.
Verification takes 0.019 secs and proof size is 6403 bytes.
This tree has a anon size of 2^32, while Seraphis current ring size is 128 and ~800 bytes.
So an 8x proof size increase for 33554432x increase in anonymity set.

It's pretty much just defining a polynomial relation to prove the merkle tree inclusion, then committing to that using the bulletproofs scheme. Given a and b are boolean ints, you can arithmetize them as so:

a AND b = ab
a OR b = a + b - ab
NOT a = 1 - a

then we convert our algo to that format, and we construct polynomials that interpolate those points, then commit and open it using bulletproofs.

Literally the main critique of monero is anon set size. Imagine if that is solved. then monero would solve the biggest issue, and might become finally a large mcap project if it could pull this off.

@baro77
Copy link

baro77 commented Dec 31, 2022

thanks for your code and ideas @narodnik !

@kayabaNerve
Copy link

kayabaNerve commented Dec 31, 2022

I have a few comments, and I'm a bit annoyed by the above presentation, so please forgive me for any extraneous snark.

  1. I don't believe anyone made up random excuses.

  2. A circuit meeting Seraphis's needs must do elliptic point addition in the circuit. It's not feasible to do Ed25519 point addition in a Ed25519 Bulletproof. You need a curve that towers down to Ed25519.

  3. There is such a curve. I have a (rather slow) impl and was working on a bellman circuit in my spare time.

  4. Dev bandwidth is, as usual, a problem. I have no objection to that point.

  5. The above circuit does not do point addition to blind the member. It is a (presumably) valid Merkle tree inclusion proof. While I appreciate the... contribution, it adds nothing to the conversation. It was already known we'd need a merkle tree-based proof. You quickly being able to write one with your SDK and the Halo 2 libs is a great comment on how far this problem has come, yet doesn't contribute to Monero. It fails to exhibit any new contribution to the protocol unless we moved completely over to Halo 2. Else, we have to rewrite all of this tooling, returning to the previous point.

  6. We can move to Halo 2 by using COPZ's discrete-log equality proof, which would have the cost of BP(+)s + some misc 512-bit arithmetic ops. Prior to COPZ's publication, the DLEq proof took an eighth of a second to verify and was completely infeasible. I'm not sure switching curves is sufficiently beneficial when compared to tower considerations. It'd depend on how much BPs fail to recursive proofs like Halo 2.

  7. We can't have a fixed size merkle tree and also need to handle things at that.

  8. I believe more efficient constructions than Poseidon have been put forth. While I'm not against Poseidon, I'd want to review options like Reinforced Concrete before building a full impl of anything.

@narodnik
Copy link

narodnik commented Jan 7, 2023

Thanks for your works and commitment to Monero, which is an important service. Monero preserves the original spirit of crypto. I can imagine the frustration of having an outsider come and start being pushy.

Privacy is likely to become a big issue within crypto. The ring size is the achilles heel for Monero, and biggest source of doubt. If it gets fixed, then the project can claim its position within the markets. Otherwise as it stands, the project will leak a lot of value which translates to a smaller shrinking community. It's the time to expand rather than consolidate since an opportunity is beginning to open up ahead, and for the project to succeed it must be ready.

As an alternative, here's some code for curve trees which is an alternative to merkle proofs:

import hashlib
from collections import namedtuple

# Your Funds Are Safu

p = [
    0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001,
    0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001
]

# Pallas, Vesta
K = [GF(p_i) for p_i in p]
E = [EllipticCurve(K_i, (0, 5)) for K_i in K]
# Scalar fields
Scalar = [K[1], K[0]]

base_G = [E_i.gens()[0] for E_i in E]
assert all(base_G_i.order() == p_i for p_i, base_G_i in zip(reversed(p), base_G))

E1, E2 = 0, 1

gens = [
    [E[E1].random_point() for _ in range(5)],
    [E[E2].random_point() for _ in range(5)],
]

def hash_nodes(Ei, P1, P2, r):
    G1, G2, G3, G4, H = gens[Ei]

    (P1_x, P1_y), (P2_x, P2_y) = P1.xy(), P2.xy()

    v1G1 = int(P1_x) * G1
    v2G2 = int(P1_y) * G2
    v3G3 = int(P2_x) * G3
    v4G4 = int(P2_y) * G4
    rH   = int(r)    * H

    return v1G1 + v2G2 + v3G3 + v4G4 + rH

def hash_point(Ei, P, b):
    G1, G2, G3, G4, H = gens[Ei]
    x, y = P.xy()
    return int(x)*G1 + int(y)*G2 + int(b)*H

# You can ignore this particular impl.
# Just some rough code to illustrate the main concept.
# The proofs enforce these relations:
#
#   σ ∈ {0, 1}
#   C = x1  G1  + y1  G2 + x2 G3 + y2 G4 + rH
#   Ĉ = x_i G1  + y_i G2                 + bH
#
# where
#
#   x_i = { x0  if  σ = 0
#         { x1  if  σ = 1
#
#   y_i = { y0  if  σ = 0
#         { y1  if  σ = 1
#
# It is just a quick hackjob proof of concept and horribly inefficient
load("curve_tree_proofs.sage")
test_proof()

# Our tree is a height of D=3

def create_tree(C3):
    assert len(C3) == 2**3

    # j = 2
    C2 = []
    for i in range(4):
        C2_i = hash_nodes(E2, C3[2*i], C3[2*i + 1], 0)
        C2.append(C2_i)

    # j = 1
    C1 = []
    for i in range(2):
        C1_i = hash_nodes(E1, C2[2*i], C2[2*i + 1], 0)
        C1.append(C1_i)

    # j = 0 (root)
    C0 = hash_nodes(E2, C1[0], C1[1], 0)
    return C0

def create_path(C3):
    # To make things easier, we assume that our coin is
    # always on the left hand side of the tree.

    X3 = C3[1]
    X2 = hash_nodes(E2, C3[2], C3[3], 0)

    X1 = hash_nodes(
        E1,
        hash_nodes(E2, C3[4], C3[5], 0),
        hash_nodes(E2, C3[6], C3[7], 0),
        0
    )

    return (X3, X2, X1)

def main():
    coins = [E[E1].random_point() for _ in range(2**3)]
    root = create_tree(coins)

    path = create_path(coins)

    # Test the path works
    X3, X2, X1 = path
    C3 = coins[0]
    C2 = hash_nodes(
        E2,
        C3,
        X3,
        0
    )
    C1 = hash_nodes(
        E1,
        C2,
        X2,
        0
    )
    C0 = hash_nodes(
        E2,
        C1,
        X1,
        0
    )
    assert C0 == root

    # E1 point
    C3 = coins[0]

    Ĉ0 = root
    r0 = 0
    # Same as this:
    # Ĉ0 = hash_nodes(E1, C2, X2, 0)

    # j = 1
    b1 = int(Scalar[E2].random_element())
    Ĉ1 = hash_point(E2, C1, b1)

    C1_x, C1_y = C1.xy()
    X1_x, X1_y = X1.xy()

    proof1, public1 = make_proof(
        E2,
        ProofWitness(
            C1_x,
            C1_y,
            X1_x,
            X1_y,
            r0,
            b1,
            0
        )
    )
    public1.C = Ĉ0
    public1.D = Ĉ1

    assert verify_proof(E2, proof1, public1)

    # j = 2

    # Now we know that Ĉ1 is the root of a new subtree
    # But Ĉ1 ∈ E2, whereas we need to produce a blinded
    # Ĉ1 ∈ E1.
    # The reason this system uses curve cycles is because
    # EC arithmetic is efficient to represent.
    # We skip this part so assume these next to lines are
    # part of the previous proof.
    r1 = int(Scalar[E1].random_element())
    Ĉ1 = hash_nodes(E1, C2, X2, r1)
    ################################

    b2 = int(Scalar[E1].random_element())
    Ĉ2 = hash_point(E1, C2, b2)

    C2_x, C2_y = C2.xy()
    X2_x, X2_y = X2.xy()

    proof2, public2 = make_proof(
        E1,
        ProofWitness(
            C2_x,
            C2_y,
            X2_x,
            X2_y,
            r1,
            b2,
            0
        )
    )
    public2.C = Ĉ1
    public2.D = Ĉ2

    assert verify_proof(E1, proof2, public2)

    # j = 3

    # Same as before. We now have a randomized C2
    r2 = int(Scalar[E2].random_element())
    Ĉ2 = hash_nodes(E2, C3, X3, r2)
    #################################

    b3 = int(Scalar[E2].random_element())
    Ĉ3 = hash_point(E2, C3, b3)

    C3_x, C3_y = C3.xy()
    X3_x, X3_y = X3.xy()

    proof3, public3 = make_proof(
        E2,
        ProofWitness(
            C3_x,
            C3_y,
            X3_x,
            X3_y,
            r2,
            b3,
            0
        )
    )
    public3.C = Ĉ2
    public3.D = Ĉ3

    assert verify_proof(E2, proof3, public3)

    # Now just unblind Ĉ3

main()

Check here for the code. It works by using a 2 cycle of EC curves where the scalar field is the base field of each one. There are a number of simple curves with this property. This enables fast EC calculation inside ZK, so you'd still need a bulletproofs circuit. Check the code comments for more info.

@chaserene
Copy link

chaserene commented Apr 24, 2024

it's funny how this issue has been dormant while the biggest developments were taking place in the past month.

documenting the most important resources, as discussed in the 2024-04-24 MRL meeting:

@tevador
Copy link

tevador commented Apr 24, 2024

This gist is also closely related to the current FCMP effort: Elliptic curve tower-cycle for Curve25519

@kayabaNerve
Copy link

kayabaNerve commented Oct 23, 2024

Initially discussed in monero-project/meta#1098.


MAX_OUTPUTS = 16 is because a Bulletproof for 17 outputs wastes 15*64 gates (960). A FCMP++ uses 256+128 gates. That means if we have 5 inputs (in a single BP), we use 1280+640 gates, wasting 768+384 (1152).

This implies per the existing MAX_OUTPUTS, we should limit MAX_INPUTS to 4. I don't support MAX_INPUTS < MAX_OUTPUTS at this time due to the creation rate exceeding accumulation rate (though you can achieve a logarithmic time bound regardless). I also don't support MAX_OUTPUTS < 4. MAX_OUTPUTS = 2 requires perfect planning to make a tree of payments with only a logarithmic delay, and may be incompatible with Carrot as you wouldn't have change outputs in your own TXs.

Accordingly, with the hard fork, I'd support MAX_INPUTS = MAX_OUTPUTS = 4, which leads nicely into padding input/output count for privacy reasons (#96, #114). To minimize the disruption of so drastically limiting in/outs at this time, my proposal is 8/4. I'd accept 8/8 as well but I believe the end goal should be 4/4 (or 2/2 if we're extremely aggressive and have sufficient wallet protocol logic).


Elaborating on why I don't support MAX_OUTPUTS = 2: If a user has to make 128 payments, they can take an aggregated master output and make a transaction with:

  • One change output
  • The sum value of all 128 payments (plus fees), denoted the tree root

They can then spend the tree root, creating 0_1, 64_1. They can then spend 0_1 creating 0_2, 32_2 and spend 64_1, creating 64_2 and 96_2. This continues until there is outputs for all even indexes at generation 8 (0_8, 2_8, 4_8...). Finally, 0_8 is used to fulfill payments 0/1, 2_8 is used to fulfill payments 2/3, etc. This works and is the exact logic seen in Serai. The issue is it requires perfection (for a batch of payments, you must always make a payment tree and never waste an output in it, not being allowed a change output) and it's in violation of Carrot.

7.8.3 Mandatory self-send enote rule

Every transaction that spends funds from the wallet must produce at least one self-send (not necessarily internal) enote, typically a change enote. If there is no change left, an enote is added with a zero amount. This ensures that all transactions relevant to the wallet have at least one output. This allows for remote-assist "light weight" wallet servers to serve only the transactions relevant to the wallet, including any transaction that has spent key images. This rule also helps to optimize full wallet multi-threaded scanning by reducing state reuse.

4 outputs isn't in violation of Carrot, allowing a change output with each TX, and requires much fewer generations to fulfill a payment tree.


I'm not firm on not allowing MAX_INPUTS to be less than MAX_OUTPUTS. Since one can always achieve a logarithmic depth bound for the accumulation of received outputs, it's arguably a needless bound. Outputs are also much, much, cheaper than input. Resolving to 2/4 may make the most sense per that view and my commentary above on not setting MAX_OUTPUTS = 2. I leave this to be further discussed.

@Rucknium
Copy link

Tabulation of Monero transaction inputs and outputs

Here is a tabulation of the number of inputs and outputs of each Monero transaction during a five-year period (2019-03-04 to 2024-03-04).

R code to reproduce:

# Run https://github.com/Rucknium/misc-research/blob/main/Monero-Effective-Ring-Size/xmr-ring-gathering.R
# Then:

# install.packages("knitr")

beginning.height <- 1784324  # 2019-03-04 15:20:22 UTC
start.spam.height <- 3097764 # 2024-03-04 15:21:24 UTC


n.inputs <- xmr.rings[ beginning.height < block_height_ring &
  block_height_ring < start.spam.height, 
  .(number_of_inputs = max(input_num)), by = c("tx_hash")]

n.inputs <- as.data.frame(prop.table(table(n.inputs$number_of_inputs)) * 100)
n.inputs$cumulative <- cumsum(n.inputs$Freq)
names(n.inputs) <- c("Number of inputs", "Share (percentage)", "Cumulative share")

knitr::kable(n.inputs, format = "pipe", row.names = FALSE,
  digits = 5)


n.outputs <- output.index[beginning.height < block_height &
  block_height < start.spam.height &
    output_amount == 0 & tx_num != 1, 
  .(number_of_outputs = max(number_of_outputs)), by = c("tx_hash")]

n.outputs <- as.data.frame(prop.table(table(n.outputs$number_of_outputs)) * 100)
n.outputs$cumulative <- cumsum(n.outputs$Freq)
names(n.outputs) <- c("Number of outputs", "Share (percentage)", "Cumulative share")

knitr::kable(n.outputs, format = "pipe", row.names = FALSE,
  digits = 5)

Number of inputs

Number of inputs Share (percentage) Cumulative share
1 54.06724 54.06724
2 38.98393 93.05116
3 1.91450 94.96566
4 0.97294 95.93861
5 0.62223 96.56084
6 0.46069 97.02153
7 0.35652 97.37805
8 0.29441 97.67246
9 0.24665 97.91911
10 0.24168 98.16079
11 0.18053 98.34133
12 0.15063 98.49196
13 0.13002 98.62198
14 0.11427 98.73625
15 0.10234 98.83859
16 0.09614 98.93473
17 0.07834 99.01306
18 0.06833 99.08139
19 0.06239 99.14378
20 0.05884 99.20263
21 0.04949 99.25212
22 0.04272 99.29484
23 0.03846 99.33330
24 0.03545 99.36875
25 0.03390 99.40265
26 0.02823 99.43088
27 0.02553 99.45641
28 0.02386 99.48027
29 0.02166 99.50193
30 0.02229 99.52422
31 0.03664 99.56086
32 0.01672 99.57758
33 0.01513 99.59271
34 0.01453 99.60724
35 0.01326 99.62051
36 0.01264 99.63315
37 0.01123 99.64438
38 0.01048 99.65485
39 0.00992 99.66478
40 0.01008 99.67485
41 0.00909 99.68395
42 0.00821 99.69215
43 0.00784 99.69999
44 0.00746 99.70745
45 0.00718 99.71463
46 0.00687 99.72150
47 0.00649 99.72798
48 0.00627 99.73425
49 0.00613 99.74038
50 0.00717 99.74755
51 0.00541 99.75296
52 0.00510 99.75806
53 0.00502 99.76308
54 0.00465 99.76773
55 0.00435 99.77208
56 0.00418 99.77626
57 0.00407 99.78033
58 0.00417 99.78450
59 0.00393 99.78843
60 0.00606 99.79449
61 0.00404 99.79853
62 0.00363 99.80215
63 0.00356 99.80571
64 0.00373 99.80945
65 0.00326 99.81271
66 0.00337 99.81608
67 0.00302 99.81910
68 0.00321 99.82230
69 0.00315 99.82545
70 0.00425 99.82970
71 0.00278 99.83248
72 0.00287 99.83535
73 0.00309 99.83844
74 0.00272 99.84116
75 0.00180 99.84296
76 0.00166 99.84463
77 0.00165 99.84628
78 0.00170 99.84798
79 0.00164 99.84962
80 0.00169 99.85131
81 0.00162 99.85293
82 0.00155 99.85448
83 0.00154 99.85602
84 0.00160 99.85761
85 0.00144 99.85905
86 0.00144 99.86050
87 0.00154 99.86204
88 0.00150 99.86354
89 0.00146 99.86499
90 0.00138 99.86638
91 0.00141 99.86778
92 0.00128 99.86907
93 0.00137 99.87044
94 0.00126 99.87169
95 0.00128 99.87297
96 0.00116 99.87413
97 0.00114 99.87527
98 0.00125 99.87652
99 0.00124 99.87776
100 0.00131 99.87907
101 0.00117 99.88024
102 0.00111 99.88135
103 0.00104 99.88239
104 0.00097 99.88336
105 0.00106 99.88442
106 0.00107 99.88549
107 0.00096 99.88646
108 0.00090 99.88736
109 0.00095 99.88831
110 0.00092 99.88923
111 0.00101 99.89024
112 0.00088 99.89112
113 0.00094 99.89206
114 0.00085 99.89292
115 0.00078 99.89369
116 0.00089 99.89459
117 0.00089 99.89548
118 0.00090 99.89638
119 0.00422 99.90060
120 0.00596 99.90656
121 0.00076 99.90733
122 0.00064 99.90797
123 0.00057 99.90853
124 0.00057 99.90910
125 0.00068 99.90978
126 0.00056 99.91034
127 0.00059 99.91092
128 0.00055 99.91148
129 0.00060 99.91207
130 0.00058 99.91265
131 0.00056 99.91321
132 0.00053 99.91375
133 0.00060 99.91434
134 0.00058 99.91493
135 0.00054 99.91547
136 0.00049 99.91596
137 0.00059 99.91655
138 0.00054 99.91709
139 0.00052 99.91762
140 0.00050 99.91812
141 0.00044 99.91855
142 0.00050 99.91905
143 0.00064 99.91970
144 0.00055 99.92025
145 0.00078 99.92102
146 0.03634 99.95736
147 0.00160 99.95896
148 0.00096 99.95992
149 0.00080 99.96072
150 0.00087 99.96160
151 0.00077 99.96237
152 0.00065 99.96302
153 0.00040 99.96342
154 0.00020 99.96362
155 0.00019 99.96382
156 0.00018 99.96400
157 0.00024 99.96424
158 0.00022 99.96445
159 0.00022 99.96467
160 0.00017 99.96485
161 0.00014 99.96499
162 0.00017 99.96517
163 0.00020 99.96537
164 0.00021 99.96558
165 0.00017 99.96575
166 0.00020 99.96595
167 0.00018 99.96613
168 0.00016 99.96629
169 0.00017 99.96646
170 0.00016 99.96663
171 0.00017 99.96679
172 0.00021 99.96701
173 0.00021 99.96721
174 0.00018 99.96739
175 0.00016 99.96755
176 0.00018 99.96773
177 0.00020 99.96793
178 0.00013 99.96805
179 0.00021 99.96826
180 0.00014 99.96841
181 0.00015 99.96856
182 0.00013 99.96869
183 0.00017 99.96885
184 0.00017 99.96902
185 0.00179 99.97081
186 0.00015 99.97096
187 0.00009 99.97105
188 0.00013 99.97118
189 0.00013 99.97132
190 0.00468 99.97600
191 0.00016 99.97615
192 0.00019 99.97634
193 0.00336 99.97971
194 0.01854 99.99824
195 0.00031 99.99855
196 0.00013 99.99869
197 0.00005 99.99873
198 0.00007 99.99880
199 0.00006 99.99887
200 0.00006 99.99893
201 0.00006 99.99899
202 0.00005 99.99903
203 0.00004 99.99907
204 0.00005 99.99912
205 0.00003 99.99915
206 0.00003 99.99919
207 0.00003 99.99922
208 0.00005 99.99927
209 0.00002 99.99930
210 0.00003 99.99933
211 0.00004 99.99937
212 0.00004 99.99941
213 0.00005 99.99945
214 0.00003 99.99948
215 0.00002 99.99951
216 0.00002 99.99952
217 0.00001 99.99953
218 0.00002 99.99954
219 0.00001 99.99955
220 0.00001 99.99956
221 0.00001 99.99957
222 0.00001 99.99958
223 0.00002 99.99960
224 0.00001 99.99961
225 0.00001 99.99961
226 0.00001 99.99962
227 0.00002 99.99965
228 0.00002 99.99966
229 0.00001 99.99967
230 0.00002 99.99968
231 0.00002 99.99970
232 0.00002 99.99972
233 0.00000 99.99973
234 0.00001 99.99973
235 0.00001 99.99974
236 0.00001 99.99975
237 0.00001 99.99976
238 0.00002 99.99977
239 0.00002 99.99979
240 0.00002 99.99981
241 0.00001 99.99982
242 0.00001 99.99983
243 0.00000 99.99983
244 0.00002 99.99984
245 0.00001 99.99985
247 0.00002 99.99987
248 0.00001 99.99987
249 0.00002 99.99989
250 0.00001 99.99990
251 0.00001 99.99991
252 0.00001 99.99991
253 0.00001 99.99993
254 0.00002 99.99994
255 0.00001 99.99995
259 0.00001 99.99995
261 0.00000 99.99996
264 0.00001 99.99996
265 0.00000 99.99997
266 0.00001 99.99997
267 0.00000 99.99998
268 0.00000 99.99998
270 0.00000 99.99998
272 0.00000 99.99998
273 0.00000 99.99999
274 0.00001 99.99999
277 0.00000 100.00000
282 0.00000 100.00000

Number of outputs

Some transactions in 2019 have only one output. Those transactions were produced before the two-output-minimum blockchain consensus rule.

Number of outputs Share (percentage) Cumulative share
1 0.00609 0.00609
2 94.16030 94.16639
3 1.43294 95.59933
4 0.88349 96.48282
5 0.46521 96.94803
6 0.33533 97.28336
7 0.24259 97.52595
8 0.18496 97.71091
9 0.25809 97.96901
10 0.09523 98.06423
11 0.25446 98.31869
12 0.05823 98.37693
13 0.05679 98.43371
14 0.04863 98.48234
15 0.04930 98.53164
16 1.46836 100.00000

@kayabaNerve
Copy link

Please note a 16-output transactions becomes 16 2-output transactions, even if done with logarithmic depth via a binary tree structure. Those additional transactions incur FCMPs which may be more expensive than simply biting the bullet on giving all transactions 4 outputs (even if 96% won't use all of them).

@kayabaNerve
Copy link

Curve Forests is a derivative of the Curve Trees scheme by the same authors. It removes permissibility with a similar trick to the one tevador proposed (adding a generator with a fixed coefficient). It also collapses the the amount of scalar multiplications necessary in-circuit from O(n + n log s) to O(n + log s) when proving for n members at once (with a set size of s).

It does this by building n trees, where n is the maximum amount of elements which can be proven with a single batch. In the worst-case (adding a single element outside of a batch), this causes n log(s) point scalings and additions. The notable distinction is in-circuit scalar multiplications are much more expensive that out-of-circuit scalar multiplications.

We use elliptic curve divisors to efficiently verify in-circuit scalar multiplications. We still have two Pedersen Commitments per scalar multiplication in our proof data, which means verifying those requires two point scalings. This immediately makes each in-circuit mul twice as expensive as the out-of-circuit muls, without mentioning the bandwidth savings.

Curve Forests also only publishes log s commitments for the branches. We publish n log s commitments. This means Curve Forests would notably decrease bandwidth in the multi-input case (from + ~600 bytes to + ~ 200 bytes per additional input). Those decreased commitments also further benefit our computational savings.

It does require a low MAX_INPUTS however. If we set MAX_INPUTS=16, we have to maintain 16 different trees (5 GB each). 16 log s scalarmuls per output may not save computational complexity if effectively no transactions actually use so many inputs at once (paying back the cost).

There's also IO cost to the additional trees, which can be discussed. When we're done with the current scheme (either due to having a more efficient scheme or due moving to PQ cryptography), the trees could be pruned. The larger proofs can not (trivially, technically they can with a recursive proof scheme) as they'll be part of the blockchain however.

There's also notably decreased prover time. Proving the scalarmuls are the majority of the complexity for the prover. Wallets would be screwed over however, as they don't benefit from the faster verification time and now have to build additional trees when they're already more resource-constrained than nodes.

I first made some initial notes in MRL on this a week ago. It fits quite nicely into the current discussion on an input limit. I don't support adopting Curve Forests now yet it'd make sense to potentially improve with in a future hard fork. While @jberman is noting the tree calculation is expensive, this should pay for itself for nodes. For wallets, we'd need to verify they can pay the computational cost (potentially requiring SIMD/GPU implementations of tree building). It also enables discussing having wallets download trees again yet I'm very strongly against that idea. Another option would be to discuss PIR so paths can be ad-hoc privately downloaded?

Also, at some point we need to decide if the tree root is going in the header (or at least hashed into the header).

@kayabaNerve
Copy link

@kayabaNerve
Copy link

cc @Rucknium What percentage of blocks include at one TX with >= 8 inputs? What percent include two? (etc)

I maintain my advocacy for 8/4 on a premise of reasonable UX/tolerable performance (though the full set of data hasn't been presented yet), but will likely encourage 4/4 with the most to Curve Forests.

@Rucknium
Copy link

cc @Rucknium What percentage of blocks include at one TX with >= 8 inputs? What percent include two? (etc)

Below is a table of this. An example interpretation: The share of blocks with at least two txs with 8 or more inputs is 14.38%.

Number of qualifying txs in block Share of blocks Reverse cumulative share (percentage)
1 18.09951 32.48107
2 6.95244 14.38156
3 3.40785 7.42912
4 1.63593 4.02128
5 0.89011 2.38534
6 0.50950 1.49524
7 0.34223 0.98573
8 0.21250 0.64350
9 0.13468 0.43101
10 0.09448 0.29632
11 0.06510 0.20184
12 0.03700 0.13674
13 0.02771 0.09974
14 0.01896 0.07202
15 0.01363 0.05307
16 0.01043 0.03944
17 0.00944 0.02901
18 0.00449 0.01957
19 0.00396 0.01507
20 0.00274 0.01112
21 0.00206 0.00837
22 0.00152 0.00632
23 0.00114 0.00480
24 0.00076 0.00365
25 0.00053 0.00289
26 0.00023 0.00236
27 0.00038 0.00213
28 0.00015 0.00175
29 0.00015 0.00160
30 0.00008 0.00145
31 0.00023 0.00137
33 0.00015 0.00114
36 0.00023 0.00099
37 0.00023 0.00076
38 0.00008 0.00053
40 0.00008 0.00046
43 0.00008 0.00038
45 0.00008 0.00030
47 0.00008 0.00023
53 0.00008 0.00015
54 0.00008 0.00008

A work-in-progress analysis of the storage and computational cost of different MAX_OUTPUT parameter values with very preliminary results is here: https://gist.github.com/Rucknium/784b243d75184333144a92b3258788f6

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests