Tari Protocol Discussion 44
On Monday, the Tari community discussed a few technical things around proofs.
Join us for our next discussion on Freenode in #tari-dev.
Discussion times proposed by the Tari community:
Mondays: 6pm CAT (12pm EST)
Thursdays: 11am CAT (5am EST)
To keep up with the latest Tari developments, you can follow the project on Twitter.
Transcript of Monday discussion
17:51 <Hansie> Hi there 17:52 <Hansie> I thought we could open the floor tonight for any off the cuff or other tar-dev related matter to be discussed 17:55 <sarang> Hi, sarang here lurking and observing :) 17:59 <Hansie> Hi Sarang, watched a video on one of your talks at the Monero conference, was really good, about optimizations. 17:59 <sarang> Great, glad you enjoyed it 18:03 <Hansie> Maybe to throw something out there, could there possibly a way to compress MW kernels and provide some sort of ZK proof for that? Each kernel has unique signatures and contributes to verifying zero inflation. 18:04 <sarang> Compress in what way? 18:06 <Hansie> Let us say there is a MW block and we want to condense all inputs, outputs and excesses in the kernels into a single MW Tx 18:09 <sarang> So what's the statement you want to prove with a zk/wi proving system? 18:10 <sarang> If it's general but neatly algebraically defined, a bulletproof could be useful (but costly in verification) 18:10 <sarang> anything smaller/faster is going to be far more specialized or require trust 18:11 <sarang> (which I assume is an absolute no-go here) 18:11 <tar1b0t> [mattermost] <stringhandler> What's a use case hansie? 18:12 <Hansie> Ok, so a base node can validate a block by `sum(outputs) - sum(inputs) = sum(excesses in all kernels)` 18:12 <sarang> (purely looking at pedersen commitments, right?) 18:13 <Hansie> Yes 18:13 <sarang> Fortunately you can do nifty small proofs involving pedersen commitments... 18:13 <sarang> depending on what you wish to show 18:13 <Hansie> Use case stringhandler: Wondering if the block validation can be converted into a single Tx with a single kernel 18:15 <Hansie> Each Tx's excess can be proved by verifying the signature in its kernel, so this may involve some sort of a super kernel 18:16 <Hansie> Sarang, does my question make sense? Any ideas? 18:17 <Hansie> I do not think this use case is "neatly algebraically defined" as you out it 18:17 <Hansie> put^ 18:18 <sarang> I'm still not seeing the total picture of the formal statement you'd want to prove 18:19 <sarang> but I'm far less experienced in MW than others in this room 18:20 <sarang> I suspect this is not possible non-interactively, or without either knowledge of all input secret data or a suitable MPC 18:20 <sarang> (and those are notoriously tricky to get right while maintaining proper security) 18:21 <Hansie> Yep, the Schnorr signatures in the kernels have different challenges, specifically designed to guard against inflation. 18:22 <sarang> I see 18:26 <Blackwolfsa> What about if you have multiple commitments, that you have aggregated by summing them (vH+kG = v1H+k1G + v2H+k2G .. etc). If all those have valid commitments and bulletproofs. And you as prover only wants to give the aggregated commitment to a verifiy, is there someway you can provide a rangeproof of a kind to the verifier to prove that aggregared commitment is 0<v<2^n ? 18:29 <sarang> Are you assuming a single range proof by someone with knowledge of all commitment secret data? 18:29 <sarang> Or an MPC bulletproof 18:29 <sarang> Which has very tricky security properties 18:30 <Blackwolfsa> a singe rangeproof. 18:31 <Blackwolfsa> I am trying to see if there is a way to calculate such a rangeproof, without providing the verifier all the commitments and their individual rangeproofs 18:31 <sarang> Depends on how you want to aggregate the proof 18:31 <Blackwolfsa> is there a way? 18:32 <Blackwolfsa> I am trying to find a way that can be done. 18:32 <sarang> There's aggregation in the sense of proving range of separate commitments efficiently 18:32 <Blackwolfsa> The idea behind it is, that the prover only has the commitments with their bulletproofs (or some other rangeproof). He does not know the v's or the k's 18:32 <sarang> And aggregation in the sense of proving the range of a sum of commitments, which does not prove range for any of the subcommitments 18:33 <Blackwolfsa> aggregation is proving the sum of the commitments 18:33 <sarang> That shows nothing about the individual commitment ranges 18:33 <Blackwolfsa> the verifier does not need to know the individual commitments, or if possible that they even exists 18:33 <Blackwolfsa> the verifier does not care about the individual ones, he only cares about the aggregated one 18:36 <sarang> What does the prover know? 18:36 <sarang> If you sum a bunch of commitments and know _all_ secret data, you can of course construct a range proof showing the value sum is within a given range, but nothing more 18:36 <Blackwolfsa> he can see the individual commitments and their rangeproofs. 18:36 <sarang> If the prover only has the individual commitments and bulletproofs, you can't do anything 18:37 <sarang> The closest you can come is an MPC on the individual commitments, but it's interactive 18:37 <sarang> (and, again, perilous) 18:38 <Blackwolfsa> darn... 18:38 <Blackwolfsa> There is not some other rangeproof you can use? 18:39 <sarang> How inefficient do you want to be? =p 18:39 <sarang> Bulletproofs are the most efficient that I know of 18:39 <Blackwolfsa> well first I want it to be secure and useable... :P 18:39 <sarang> But no, I don't see a way it's possible to generate such a rangeproof with access to no secret data 18:40 <sarang> or interactivity among the original committers 18:43 <Blackwolfsa> darn it, because the prover should not have access to those values, since they become vulnerable. 18:45 <sarang> I would love such a technique for Monero too... 18:45 <sarang> even ignoring the idea of summing commitments, of course 18:45 <sarang> We have a whole block of bulletproofs 18:46 <sarang> FWIW the bulletproofs MPC was written with CoinJoin in mind (although the security model is a bit wonky) 18:47 <Blackwolfsa> mmm but thats interactive. we require something non-interactive 18:47 <sarang> yup 18:47 <sarang> and therein lies the problem 18:47 <sarang> If you ignore the interactivity (or handle it poorly) you break the zk property 18:48 <sarang> (and possibly WI too, dunno) 19:00 <Hansie> Thanks guys, we some really interesting discussions here! Thank you sarang, for humoring us. 19:01 <Blackwolfsa> yes thanks for the time