18:14 UTC

< June 2015 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

- Console
- #amber
- #apicula
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #buildbot
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #lowempire
- #maemo-leste
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- ##moved_to_libera
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #openwrt-devel
- #panfrost
- ##panfrost-offtopic
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #river
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #stellar
- #stellar-dev
- ##stm32-rs
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #videocore
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

wumpus changed the topic of #bitcoin-wizards to: This channel is is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja

<shen_noe>
what if we change this to check that the blinding factors don't add exactly to zero, but rather the sum of inputs and outputs commitments leaves zG

<shen_noe>
now, take a ring signature over C_1, ..., C_s, ..., C_n where C_i are possible input commitments taken ad-hoc from blockchain

<shen_noe>
after this, proceed as in normal CT (proving outputs are commitments to positive values), using boromean sigs if that helps,, etc

<andytoshi>
shen_noe: i'm not quite sure what you gain here .. you need that every `inputs - outputs` is zero, so proving that 1/n of them are seems like it'd just be wasteful

<andytoshi>
and what it gets you is that you can ring-sign with arbitrary input sets, and not care about their sizes

<andytoshi>
yeah, the exact scheme is not so important, what i'm trying to get is the high-level .. you have (a) a ringsignature over several inputs which proves you own one of them, (b) a "ring-CT proof" that one of these inputs is the right size

<andytoshi>
so, you need to link these two signatures somehow to make sure the input you're spending and the input whose value you're using are the same one

<shen_noe>
so you need to link the two sigs: I think you can include all the original C_in's so a verifier can recreate the original sig themselves

<andytoshi>
then if you are able to prove that `input - outputs == 0` this also proves you own the input

<andytoshi>
so, let's think how this would work for a one-input-one-output tx, with a ringsize of one

<andytoshi>
so there is no ring sig magic here, i'm just trying to figure out when/how the pubkey is determined

<andytoshi>
with the current CT setup you've got something like an output value of `rG + vH` where r is secret and v is the hidden value

<andytoshi>
so my question is: what is the output? a value commitment (x + z)G + aH as well as a verification key zG?

<andytoshi>
i was like "how do you prove you know the input" but that's not the commitment-proof's job in the original system

<andytoshi>
kk so now i need to think for a few mins about if you can game this somehow .. i guess not if zG is in the output and can't be changed

<andytoshi>
ok, so i think i can choose {z, zG} then spend any output like this by taking the input point and adding zG to it to get my output point

<andytoshi>
(i'll let you work thru this, meanwhile i think i have a fix, tho it's a little bigger than a single sig)

<andytoshi>
is zG part of the output that's being spent? or is the idea is it's only computed as C_in - C_out?

<andytoshi>
then i can choose C_in from an arbitary output, choose z randomly, and produce a tx whose output is C_out = C_in + zG

<andytoshi>
so if i have a signature for xG on m, can i mar this into a sig for (x + z)G on m, knowing only z?

<andytoshi>
(x is just an arbitrary secret value, it doesn't correspond to anything we've mentioned so far)

<andytoshi>
being unable to do this is -not- a standard security property that i'm aware of, i doubt it holds for any standard sig system

<andytoshi>
i think you can't do this because x is gonna be different for each bit of the range-proof in the output

<andytoshi>
ok, so, you ringsign with (C_i, C_i - H) to proof either 0 or 1, and there are always multiple random C_i's

<andytoshi>
and you set things up so that you know the DL of (C_1 + zG) even tho i don't know z or the DL of C_1

<andytoshi>
-but- i think you're screwed now because you have to produce a signature with z on top of this right?

<andytoshi>
cuz you always have to sign with (a) z and (b) z + r, where r is some randomness from the input's rangeproof

<andytoshi>
you don't know r unless you own the output, so you can't do both unless you own the output

<shen_noe>
so.. I think outputs = inputs is guaranteed by commitment to zero of the original summation

<shen_noe>
gmaxwell invented ct also: so I was thinking of modifying the summation equation (In1 + In2 + In3 + plaintext_input_amount*H...) -

<shen_noe>
now take a ring sig over (C_1 - \sum outputs, ..., C_s - \sum outputs, ..., C_n - \sum outputs)

<gmaxwell>
shen_noe: adam proposed in his original thread that showing knowedlge of the discrete log of the blinding factor as a replacement for the normal signature (so long as you don't mind losing all the useful script properties)

<gmaxwell>
shen_noe: but if I send you coins I also know your blinding factors, so the send is not a payment (as I can claw the funds back) unless we use an interactive proptocol to have you generate the blinded coins.

<gmaxwell>
so it didn't really seem like a big gain, also since the rangeproofs can often be omitted.

<andytoshi>
well, the gain was really for monero, so you could ringsign over inputs of varying values

<shen_noe>
the reason I was considering this, is if you modify for CryptoNote, then you need someway tto hide the input index

<gmaxwell>
Adam actually had a proposal to for a ringsig version, but I'm not sure if it was complete or correct.

<gmaxwell>
I think the ringsig is not very exciting though since coninjoin works so will with the CT approach... and the ringsig has other costs.

<shen_noe>
yeah, it was more of a thought exercise, since the size with ring sigs included makes it fairly large

<gmaxwell>
shen_noe: they can't do that or you can spend their coins. Rather the reciever has to create two outputs and their range proofs and tell you their blinding factor sum and value sum.

<gmaxwell>
then you can create a transaction which includes their outputs where only you know the discrete log of the sum of the blinding factors.

<andytoshi>
shen_noe: yeah, the LWW paper has a really generic way of making key images, you just have another generator H, then the key image of xG is xH, and you provide a proof-of-equal-discrete-logs

<gmaxwell>
(but then you get into problems where you have to prohibit spending those two coins in the same transaction and other stupidity.)

<CodeShark>
are many of the insights in partially homomorphic crypto using the discrete log problem applicable to lattice-based crypto?

<andytoshi>
CodeShark: lattice crypto is about having a secret basis in which matrices can be efficiently manipulated in sorta ad-hoc ways, i'm not aware of something similar to this "have two generators so given aG + bH nobody can know its discrete log"

<gmaxwell>
shen_noe: double spending is not an issue there; the problem is the symmetry of the reciever and the senders knoweldge. It can be broken, with a cost, but the benefit is pretty small.

<CodeShark>
my understanding (which admittedly isn't as good as I would like) is that lattice based homomorphic encryption is based on ideals

<shen_noe>
gmaxwell, right, I was momentarily confused - so makes the transaction with the coins first wins

<shen_noe>
so maybe it would need a "coins" received function where receiver scans blockchain and when they find their coins, send it to a new address.. I'm not sure what that implies

<shen_noe>
yeah: there is a much simpler method (but not as good) which already works in monero actually

<shen_noe>
although I think you could get away with not full interaction: receiver only interacts by scanning blockchain and "accepting" their transaction

<CodeShark>
so you can compress many levels of sha256 into a single proof whose size does not depend on the number of levels in a tree?

<CodeShark>
creating the proof is expensive - but in principle verification could be made much simpler than just brute force hashing

<gmaxwell>
CodeShark: yes, you can, so long as you're willing to take on a whole host of new strong cryptographic assumptions; and a long (like 30 seconds to minutes) proving time. And verification that runs on the order of 200 proofs per second.

<gmaxwell>
___pairing___ crypto; though it has many more assuptions than just the hardness of discrete logs in bilinar groups and the normal stuff for most pairing crypto.

<CodeShark>
are the other assumptions largely surrounding statistical vs. computational zero knowledge?

<gmaxwell>
No succinect proof system for genral NP can have better than computational security in any case (owing to a counting argument).

<gmaxwell>
but I'm not talking just about the hardness, I mean there are new strong assumptions; e.g. that certant functions cannot be efficiently computed; for which no proof currently exists that reduces them to an existing prior known strong assumption. (like the hardness of the computational discrete log problem in a bilinear group). They sound plausable and fortunately its an interesting enough area t

<gmaxwell>
The papers go over them, though unless you're a current postdoc in that subfield you'll probably (like me) mostly just shrug at them. :)

<CodeShark>
this whole zkSNARK thing does seem too good to be true...so yeah, there's a price for that magic

<gmaxwell>
There are proposals to potentially use multiparty computation for it, so the trusted setup gets some threshold security.

<gmaxwell>
People are also working on other schemes for NP proofs with a totally different cryptographic basis which won't have that problem; but their proofs will be less efficient.

<CodeShark>
by totally different cryptographic basis you're referring to something other than bilinear crypto or pairing crypto?

<gmaxwell>
PCP theorem plus fiat shamir tell us that at least in principle there are efficient computationally sound, statstically private proof systems for NP; that have no strong assumptions except the RO used for the fiat shamir. Though making them pratical is hard.

<gmaxwell>
(as the most direct routes require you to e.g. build a hashtree over a set of bits with substantially more entries than atoms in the universe)

<gmaxwell>
andytoshi: do you see any obvious way to do an ___efficient___ proof of polysig equivilence. E.g. say there is a set of keys for a polysig, and some unknown permutation, and I want to prove to you that a given polysig series corresponds to that set without revealing the permutation?

<andytoshi>
gmaxwell: (a) no, and (b) i think this is pretty hard actually, adam and i ran repeatedly into a related problem (proving a sum of keys was actually computed using the keys, without eg adding r to one and -r to another) when we were trying to make constant-size ringsigs. i don't remember the details but it was related to permutations (since the real key had to occupy a specific "slot" or something

<andytoshi>
but what was killing us was not so much our efficiency requirements, it was that you can't do much of anything to aggregate keys except adding them together, and that loses a ton of information

<kanzure>
would there be any value in limiting the number of transactions in each block? rather than block size.

<nsh>
[even if there exist privacy-enhancing coalitions, you can bet dollars to donuts they will be sparse among the types of coalition that emerge when you incentizive them]

<kanzure>
"Secure proxy signature schemes for delegation of signing rights" https://eprint.iacr.org/2003/096.pdf

<kanzure>
i want to send 100k payments and have each of my 100k different receivers also send 10k payments, and none of the intermediate transactions should need to be on the blockchain itself

<kanzure>
and also, it would be nice if there could be arbitrarily-deep transaction chains that bridge the history of an even larger transaction chain

<maaku>
kanzure: lightning is much more than a bidirectional channel, which is why it needs so many changes

<kanzure>
as you increase the number of people on each side of the channel, you increase the probability that one of them will want to throw the transaction into the blockchain to close the channel

<maaku>
now you move an insane amount of money around in one direction at once, it is true you will saturate one direction of a channel

<maaku>
if you have 100k people receiving payments, and 15 of them decide to close their channel, 15 transactions hit the chain

<kanzure>
the idea was to abridge transaction history, not "hope that they all collectively decide to close their channels after transacting in a way that happens to reduce the total number of transactions"

<maaku>
kanzure: where I'm being dense is I don't understand the concern. closing a channel is not an externalized cost, due to fees

<kanzure>
so you believe that large quantities of transactions- perhaps billions- will have users that choose to use software that tries to find ways to close the channels in a way that minimizes the number of fees and number of transactions that get into the blockchain?

<nsh>
no, i imagine the people paying the users will be strongly incentivized to minimise the overhead for the recipients

<andytoshi>
kanzure: OWAS is slow and depends on pairing. it hasn't been implemented 'til now because it'd be a controversial hardfork for bitcoin plus it'd have bad scaling consequences (why there has been no "pairing-crypto alt" idk, nobody here has done it because there are better uses of our time)

<andytoshi>
but given gmax's comments above about how OWAS interacts with CT, and adam's periodic musings on a "BDH-secure sidechain" (meaning one where pairing crypto's security assumptions are considered sufficient), i'm sure something will crop up in this area sooner or later..

<nsh>
well, i think once alpha proves the sidechains concept is feasible [assuming it does], then there might be a cambrian explosion

<maaku>
maybe-interesting observation : with onion routing of lightning payments you can have "hidden" payment addresses