--- Day changed Tue Mar 13 2018
02:42 -!- wump is now known as wumpus     
03:34 -!- benma [~benma@178.197.231.206] has joined #secp256k1     
03:34 -!- benma [~benma@178.197.231.206] has quit [Changing host]     
03:34 -!- benma [~benma@unaffiliated/benma] has joined #secp256k1     
03:44 < benma> hi. i'd like to play with bulletproofs - creating circuits, proving/verifying statements, etc. i'm looking at https://github.com/ElementsProject/secp256k1-zkp/pull/16, but having trouble getting started
03:44 < benma> does anyone have a simple demo program lying around that creates a circuit, produces a proof and verifies it
03:44 < benma> ?     
04:06 -!- benma [~benma@unaffiliated/benma] has quit [Read error: Connection reset by peer]     
04:07 -!- benma [~benma@178.197.231.206] has joined #secp256k1     
04:07 -!- benma [~benma@178.197.231.206] has quit [Changing host]     
04:07 -!- benma [~benma@unaffiliated/benma] has joined #secp256k1     
06:19 < maaku> benma: look at the tests for that pull request
06:24 < benma> thanks, looking
08:02 < andytoshi> i should probably rebase and push my current work
08:03 < andytoshi> still don't have a sensible way to load circuits, i've just been hardcoding strings. we have an overhaul of the circuit format in the pipeline, is why visible progress has been slow
08:09 < benma> thanks!
08:18 < andytoshi> lemme just fix the exhaustive test compilation issue then i'll push
08:22 < benma> great
08:26 < andytoshi> pushed
08:29 < benma> pulled, now i get this:
08:29 < benma>   CC       src/libsecp256k1_la-secp256k1.lo
08:29 < benma> In file included from src/secp256k1.c:32:0:
08:29 < benma> ./include/secp256k1_bulletproof.h:24:5: error: unknown type name ‘secp256k1_scratch_space’; did you mean ‘secp256k1_scalar’?
08:29 < benma>      secp256k1_scratch_space* scratch,
08:29 < benma>      ^~~~~~~~~~~~~~~~~~~~~~~
08:29 < benma>      secp256k1_scalar
08:29 < andytoshi> what is your config line?
08:29 < benma> $ ./configure --enable-exhaustive-tests=no --enable-module-bulletproof --enable-experimental --enable-module-generator
08:30 < andytoshi> thanks
08:31 < andytoshi> i see, dammit, i rebased and lost the scratch space stuff apparently
08:31 < andytoshi> i may have to rebase secp256k1-zkp on secp256k1 to get that back
08:36 < nsh> i have an old pull of -zkp. can check the commit. or i thought i had, hmm
08:37 < andytoshi> no, i've got all the code, i'm just not sure how best to expose it
08:37 < andytoshi> i can go back to the non-merging bulletproofs branch.. i guess for benma  i should just do that for now
08:37 < andytoshi> but properly, i should rebase -zkp on upstream and then rebase bulletproofs on -zkp, which i will do today, but i need to catch a train soon and also i need sipa to wake up to review it (it's not even 9am on the west coast)
08:38 < andytoshi> oh heh train is delayed now to 2:25 .. which may be the start of a series of indefinite delays
08:39 < nsh> eeps
08:48 < benma> thanks andytoshi, no need to rush
08:51 < benma> i'm interested in doing a zkp version of bip32 derivation, or a variation of it. since i haven't played much with circuits yet and have only vague ideas about how bulletproofs scale: do you think this would be feasible? what would be the ballpark time to construct a proof on a circuit implementing hmac-sha512?
08:55 < andytoshi> oof, a couple minutes
08:55 < andytoshi> hmac is 4 hashes right?
08:56 < benma> thought it was 2
08:56 < benma> with xors and concats
08:56 < benma> https://wikimedia.org/api/rest_v1/media/math/render/svg/4edcf0bd8b403c93564b8d7ea91338b3208dea03
08:56 < andytoshi> oh ok
08:57 < andytoshi> i'm gonna guess 90 seconds, it takes ~20 secs to do one sha256 compression
08:57 < andytoshi> per core
08:57 < andytoshi> err, 20 seconds on one core, is what i mean
08:58 < andytoshi> i have some prover optimizations up my sleeve, if you have a cool usecase i could maybe expedite that, but i don't think i can get more than, say, 20% out of it, so it'll be same order of magnitude
09:01 < benma> i'm working on a HW wallet, and the other day i had the idea that it would be cool if the HW could do a proof of derivation without showing the secret seed
09:02 < benma> in combination with user supplied entropy, this would mean that the user can be sure their entropy is mixed in
09:05 < benma> thinking if hmac-sha512 is too slow, maybe a simpler derivation could be feasible - eg no hashing, just addition
09:05 < benma> (and multiplication of course to get from a private key to a public key)
09:07 < benma> about the hashing: is you repeat the step with modified input (i.e. a derivation like m/44'/0'/0'), would that scale lineaerly?
09:08 < andytoshi> so, multiplication by G is super easy, as is multiplication by any point you know the discrete log of
09:08 < andytoshi> yeah
09:08 < andytoshi> so the HMACs i think you're not gonna be able to do on a HW wallet
09:10 < andytoshi> well, lemme think about that actually. you can outsource the inner product part of the bulletproof
09:10 < andytoshi> so if you're willing to stream a few megs of data from the HW device maybe this is feasible
09:13 < benma> i'd need to measure how fast i can stream, but if it is quick and would make it feasible, i don't see why not
09:14 < benma> i'm not yet familiar with how bullet proofs work under the hood, so i am a bit lost on what outsourcing the inner product means. i'll try to find time to study this
09:14 < benma> hopefully on the weekend
09:16 < andytoshi> there are two parts to a bulletproof, the actual proof part results in two vectors that are linear in the size of the problem (# of multiplication gates) and verification involves taking their inner product
09:17 < andytoshi> then there is an inner product proof, which is logarithmic in the size of the original vectors, and that's where the scaling comes from
09:17 < andytoshi> but that inner product proof isn't zero knowledge (nor is it a proof :) it's an argument) so there is no reason it has to be done on secure hardware
09:21 < benma> what does the inner product argument look like? also vectors with an inner product?
09:21 < benma> if that part is logarithmic, and the zk proof part linear, it seems like the bulk of it would still be on the hardware
09:22 < andytoshi> it's logarithmic in size. linear in computation
09:28 < benma> ok, that's helpful. how many multiplication gates are needed to perform sha2?
09:28 < benma> (about)
09:28 < andytoshi> 21000
09:28 < andytoshi> (about)
09:29 < andytoshi> so it'll be about 21000 x 2 scalars, or 21k * 64 = 1.3 MIB per sha2
09:34 < benma> hmm. are those numbers per hash block? ie for double the input length, it's double time/space
09:35 < andytoshi> yeah
09:35 < benma> though in hmac with bip32, one blocksize is enough if i'm not mistaken
09:35 < andytoshi> i think so
09:37 < benma> thanks a lot! i'll do a deepdive into bullet proofs and see how far i can get :)
09:39 < andytoshi> sipa: can you take a look at https://github.com/apoelstra/secp256k1-mw/tree/secp256k1-zkp-rebase ? i had to add commit b3e80b653ad52611a5de4a67dc65d19b91dfe8a3 (replace upstream ecmult_const with one that can do 64-bit ecmults, for pedersen commitments) but otherwise no nontrivial changes
09:39 < andytoshi> trivial changes were: add comments to the #endif's at the end of a couple files; rename sha256_t to sha256 in the generator module
09:41 < andytoshi> benma: updated PR to be based off of the rebase
09:45 < benma> thx. getting a different error now:
09:45 < benma>   CC       src/libsecp256k1_la-secp256k1.lo
09:45 < benma> In file included from ./src/modules/rangeproof/main_impl.h:13:0,
09:45 < benma>                  from src/modules/bulletproof/main_impl.h:13,
09:45 < benma>                  from src/secp256k1.c:624:
09:45 < benma> ./src/modules/rangeproof/borromean_impl.h: In function ‘secp256k1_borromean_hash’:
09:45 < benma> ./src/modules/rangeproof/borromean_impl.h:33:5: error: unknown type name ‘secp256k1_sha256_t’; did you mean ‘secp256k1_sha256’?
09:45 < benma> same config line
09:46 < sipa> benma: i have scripts around to convert program-like things to bulletproof gates/constraints, but it's too much of a mess to publish right now
09:51 < benma> hi sipa!
09:52 < benma> cool. i made sth like that too back when i played with zksnarks, was also a mess :P
09:53 < benma> hey, not sure if you have read the above stuff, but jonas asked you on bitcoin wizard about the same type of question: zk proof of user entropy presence in key derivation
09:54 < benma> you mentioned that another type of hash could be used with significantly less cost
09:55 < benma> did you mean that as a replacment for sha512 in bip32, or was that a different conversation?
09:56 < sipa> or just don't use bip32
09:56 < sipa> :)     
09:57 < benma> sure, a simple multiplication+addition is the easy way out, but HD and hardened derivations would still be nice!
09:58 < sipa> secp25k1 ec multiplication will be extremely hard
09:58 < sipa> inside a proof
09:58 < sipa> unless the bulletproofs are over the dual curve
10:02 < benma> oh, i wasn't aware of that.
10:02 < benma> what did andytoshi mean by 'so, multiplication by G is super easy' above?
10:04 < sipa> oh, let me think
10:04 < benma> now i def. need to read up fast. somehow i thought that bulletproofs are based on ecc, similar to CT was
10:04 < sipa> yes, i think it's easy
10:05 < andytoshi> benma: ok thanks, i'll check that out, i must have missed a couple _t's
10:05 < sipa> so: bulletproofs prove linear relations hold over miltiplications between secret values
10:05 < sipa> those secret values may either be actually secret, or they may be the values committed to by public pedersen commitments
10:07 < sipa> if you can treat your public keys as pedersen commitments (with 0 blinding factor), you can directly do math inside over the secret keys
10:07 < maaku> to be certain, I don't think actual deployments would have tools for making arbitrary arithmetic circuits
10:07 < maaku> i've been scratching my head for a while trying to come up for a reason you'd want one in a blockchain context, and haven't found one
10:07 < sipa> that's what you want for hardened derivation
10:07 < sipa> maaku: hmm, how do you mean?
10:08 < sipa> (re the first line above)
10:09 < maaku> sipa: zkp are useful for proving to the validator that the transaction meets some condition the validator cares about, without revealing information
10:09 < sipa> by "actual deployments" you mean blockchains?
10:09 < maaku> the applications talked about so far -- rangeproofs, nums assertions, hash equivalences, etc. -- are all proving consensus rules about tx validity
10:10 < maaku> yes i meant in a block chain context
10:10 < sipa> fully agree then
10:11 < sipa> i think it would be a neat (but unusable) proof of concept to have a chain where the outputs are bulletproof circuit hashes, and inputs are circuits + proof
10:12 < maaku> Yeah I thought about that but why not just have a single Schnorr signature for authorization?
10:13 < maaku> Or for things where there aren't fixed signer sets, like the two-way peg, you NEED knowledge to be explicit.
10:13 < maaku> Proving you have a peg-in in zero-knowledge is an anti-feature because no one can provide a reorg/fraud proof
10:13 < sipa> right
10:14 < maaku> If anyone can think of a counter example (a case where arbitrary circuits is useful and zero-knowledge doesn't get in the way) I'd like to hear it
10:14 < andytoshi> well, only the headers need to be public knowledge to support reorg proofs
10:14 < andytoshi> and if you can BP all the consensus rules, those would be the only 'fraud proofs'
10:14 < sipa> right, but that's completely unrealistic at this point
10:14 < andytoshi> yeah
10:17 < benma> thanks andytoshi, sipa, i'll noodle about it. need to sign off now, dinner time!
10:17 < maaku> Actually I think I just rubber ducked y'all to answer my own question: a zkp covenant would retain some fungibility by hiding the details of the covenant script
10:17 < maaku> That would be useful for some covenants, such as vaults, where public knowledge of the covenant is not required
10:17 -!- benma [~benma@unaffiliated/benma] has quit [Remote host closed the connection]     
10:18 < sipa> maaku: the circuit would reveal the covenant, no?
10:18 < sipa> unless you have a recursive zkp
10:18 < sipa> ("i know a secret circuit whose hash is X, and I ran the zkp verification algorithm on it with secret inputs"
10:18 < andytoshi> fwiw recursive zkps aren't too bad
10:19 < maaku> sipa: I was thinking recursively. The circuit would take the covenant to verify as (blinded) input
10:19 < andytoshi> at least, with BPs they aren't a _lot_ worse than BPs themselves :)
12:27 < andytoshi> sipa: fixed https://github.com/apoelstra/secp256k1-mw/tree/secp256k1-zkp-rebase -- there were some missing sha256_t's that i had to change to sha256's, and also the rangeproof benchmarks didn't compile
13:37 < waxwing> well this is all very wizardly :)
17:00 -!- weez17 [~isaac@unaffiliated/weez17] has quit [Read error: Connection reset by peer]     
17:00 -!- weez17 [~isaac@unaffiliated/weez17] has joined #secp256k1