00:07:26bramc:ebfull, snarks is quite an amazing thing but so far even with its amazingness appears to be quite impractical.
00:25:01prodatalab_:prodatalab_ is now known as prodatalab
00:27:34amiller:bramc, i dunno that seems like an awful summary to me
00:28:23amiller:ebfull, here's a short run down.... microsoft research and the scipr team keep going neck and neck with new systems
00:29:49amiller:microsoft research made a very practical system called gepetto, that has two layers of recursion (snarks proofs that another snark proof is valid, which can give better efficiency but im at a loss for a simple metaphor to explain why) https://eprint.iacr.org/2014/976.pdf
00:30:14bramc:amiller, I have yet to see a proposal for doing something in the real world with snarks which I actually believe can function
00:31:13amiller:the scipr team has found a set of parameters that allow for aribtrary layers of snark recursion, which is theoretically great but a) a bit slower than gepetto, b) not a good enough security level, so this is a proof-of-feasilbiyt more than anything else https://eprint.iacr.org/2014/595
00:32:27amiller:the scipr team has announced a paper (acepted to oakland15, but draft isnt anywhere online yet i guess) about a good way to do the trusted setup as amultiparty computation with a large number of parties http://www.ieee-security.org/TC/SP2015/program.html
00:36:03amiller:some guy made a small language for writing snark systems thats an alternative to the pinocchio c-to-circuits compiler and i guess is better, i haven't looked carefully http://comments.gmane.org/gmane.comp.encryption.general/22047 https://github.com/jancarlsson/snarkfront
00:39:41amiller:i updated my nonoutsourceable puzzle paper with more explanation of a concrete multi-tier reward system, there's an implementation using libsnark and pincochio (libsnark was better) but that's the same as the previous version http://cs.umd.edu/~amiller/nonoutsourceable.pdf
00:40:55amiller:gmaxwell says he implemented a snark circuit that can be used with bitcoin today, it proves that the preimage of some hash is the solution to a bunch of a sudoku puzzles or something
00:44:06amiller:finally, zerocash is practical and is being actively developed
00:44:17amiller:ok, that's a short "the past three months in SNARKs"
00:53:10ebfull:thanks amiller :)
01:00:44bramc:Whether zerocash is practical remains to be seen
01:05:33bramc:Somewhat off topic: It turns out that the failing of a black market backed by bitcoin is the accumulation of databases of shipping addresses: http://aeon.co/magazine/technology/on-the-high-seas-of-the-hidden-internet/
01:54:36AnxiousGarlic:AnxiousGarlic has left #bitcoin-wizards
02:12:14andytoshi:adam3us1: so a cool way to think about about your ring signature scheme is to consider the hashes as DL-labelled vertices on a connected directed graph with an edge between A->B whenever B is a hash of some function of A. then the signing algo is: (1) pick a vertex V and compute its hash; (2) for each edge V->W where V has had its hash computed, compute W. if W is already computed, you have to know
02:12:16andytoshi:its discrete log else you lose
02:12:36andytoshi:(i hope that makes sense serialized to text). in the sig scheme as described your graph is always just a single hamilton cycle
02:13:18andytoshi:we can define an "admissible DL set" as one where if you know all the DLs in the set, you can do the signing algo, and the result is a ring signature which proves you know an admissible DL set but hides which one
02:14:09andytoshi:this leads to the question (which i am just investigating now in the last 5 minutes), what if you don't just do hamilton cycles? if we do weirdly shaped graphs how creative can we make the admissible sets?
02:14:53andytoshi:(for a hamilton cycle, each DL by itself constitutes an admissible set, i.e. you need to know one DL to compute the signature)
02:20:15bramc:Well this is an interesting result: In my pos system, if one attacker tries to do withholding attacks they might be able to get favorable forks a little more often from it, but if two attackers do withholding attacks the amount they screw each other from lack of cooperation is greater than the amount they can get ahead from it
02:23:47andytoshi:oops, the algo is not actually that simple. each vertex actually has four states "c_i (un)computed" × "s_i (un)computed", and the algo is: for each edge A->B, if A is "c_i uncomputed" set it to "c_i computed"; then if A is "s_i uncomputed" set B "c_i computed" (if it is already, you need to know B's DL else you fail), else if A is "s_i computed" and B "c_i computed" (if it already is, you fail)
02:26:24andytoshi:i think, but unsure, what this means is: every irreducible cycle requires you to know an arbitrary DL on the cycle; additionally every vertex with in-degree N requires you to know an arbitrary (N-1) of the N DL's corresponding to its inputs
02:37:08andytoshi:above i meant "you need to know A's DL else you fail", not B's DL; also the last "and" should be "set"
03:04:22andytoshi:i am assuming each hash is H(L, m, y_i^{s_i} g^{c_i}) where i runs through all the input nodes (so you get a bunch of simultaneous equations), not sure that doing anything else is worth how much harder it makes this to analyze
03:56:43bramc:Writing a better sim than I had before, it turns out that the attacker's bonus from pooling in the simple case was worse than I thought
03:56:54bramc:That said, using nth best helps a lot
05:28:53bramc:Making very pessimistic assumptions about an attacker's other possibilities, an attacker gets a lot more pooling advantage than I'd like
05:49:45bramc:I should throw in the requirement that the nth best has to be endorsed by all the ones below it. That makes the attacks work a lot less.
05:53:24bramc:Or maybe that the nth best has to list the ones below it. Need to work this out.
05:57:54bramc:Okay even the listing ones below it thing works well, but, *sigh*, doing better than that creates massive headaches for the protocol.
06:18:08bramc:The short of it is that setting n to 2 or 3 works best, and it's critically important that the nth best sign off on the ones below it. Things work better if the lower ones have to sign off on the higher ones as well, but I'll have to think about that some more, it creates awful edge cases when things don't get completed properly
06:22:25bramc:Grumble grumble. At least I've got things working somewhat acceptably. My n is either going to be 2 or 3, I'm fairly sure of that now.
06:23:45brisque:what happens if they refuse to "endorse"?
06:37:14bramc:brisque, then the next one lower will endorse and they won't get their share of the mining reward
06:38:23bramc:At least, that's the way it is in the case where the nth best has to list the ones better than it. In the case where there's mutual interconnected endorsement it gets a lot more complicated and the failure modes are much more of a headache.
06:41:45bramc:With full mutual endorsement required even n=2 works fairly well. That may turn out to be the way to go.
06:43:06bramc:It's possible than a fair number of people reading have no idea what I'm talking about
06:51:26gwillen:bramc: I don't suppose there's a summary somewhere
06:51:39gwillen:I'm curious enough to read it if there is
06:52:47bramc:gwillen, Unfortunately no, it's rather complicated and a bit of a moving target. A bunch of the blockstream people have an idea because I explained it to them in person
06:53:33gwillen:bramc: yeah, I am only recently a blockstream employee so I've heard bits and pieces from them, and bits and pieces in here, but unfortunately I missed hearing about it in person
06:54:46bramc:The too short summary is that I'm working on a cryptocurrency where the mining is based on proofs of storage, with a whole lot of crazy engineering resulting to avoid grinding
06:55:23gwillen:ahhh, okay, yes; the basic scheme was described to me, as of when you described it to the blockstream people
06:56:50bramc:There's some commentary in the stuff about proofs of stake systems that intuitively it seems like there should be no way of avoiding grinding but noone's found a rigorous proof of it. It turns out that it is avoidable (sort of, with limitations) but doing proofs of storage is vastly less problematic than proofs of stake.
06:59:31bramc:Right now I'm working on reducing the potential for what grinding potential remains in my scheme. It can't be completely eliminated, but it can be reduced. It's looking like I'll get down to something like if you have a 10% pool you'll be able to get a 1% or .1% bonus, and if you can make a 40% pool you can get a 10% or 1% bonus
06:59:40bramc:depending on how the parameters are set.
07:00:12bramc:There's also some tradeoffs to how much advantage someone with a faster spow can get
07:00:16gwillen:* gwillen nods
07:03:14bramc:The short of what I'm working on now is making it use the nth best match for determining the next challenge, where the n best have to be found collaboratively, so an attacker working on a fork is a lot less likely to have their fork get ahead.
08:41:58brisque:OT, but I thought I'd have a look into how various pinning systems are using OP_RETURN code messages to pin data into the Bitcoin blockchain (as it seems to be all the rage). there's some some reasonably compact encodings, some sort of weird things (did you really need an 21 byte magic number?), and then there's someone who had to multipart their data over three transactions because their encoding didn't fit in the 40 byte limit.
08:42:23brisque:6a257b2264657363223a2022416e67656c2048656c70696e672048616e64204d696e7574657322 + 6a252c20226e616d65223a202248484d696e75746573222c2022746f74616c223a203231383430 + 6a0a2031303030303030307d
09:05:16weber.freenode.net:topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
09:05:16weber.freenode.net:Users on #bitcoin-wizards: andy-logbot erasmosp_ delll_ Dr-G2 bramc lclc null_radix Mably bedeho arubi hktud0 dgenr8 moa p15_ NewLiberty cryptowest justanotheruser coiner copumpkin TheSeven brisque Cory ryanxcharles bigpup3 gmaxwell nuke1989 dc17523be3 espes__ flower d1ggy_ fanquake PRab antgreen amincd shesek adam3us1 zooko prodatalab oujh Emcy Grishnakh HaltingState koeppelmann Adlai c0rw1n hashtag_ melvster huseby jaekwon_ PaulCapestany GreenIsMyPepper sneak ebfull
09:05:16weber.freenode.net:Users on #bitcoin-wizards: pigeons SwedFTP weex kmels bepo MoALTz_ LarsLarsen CodeShark grandmaster epscy nanotube gavinandresen tromp cluckj Starduster binaryatrocity waxwing spinza andytoshi bliljerk101 pukie embicoin luny tromp__ wizkid057 starsoccer xabbix comboy nsh Taek iddo EasyAt maaku Logicwax Pan0ram1x helo bosma sipa btcdrak NikolaiToryzin s1w Visheate crescendo livegnik asoltys_ optimator gribble fluffypony Meeh cursive yoleaux dansmith_btc [d__d] berndj
09:05:16weber.freenode.net:Users on #bitcoin-wizards: Luke-Jr morcos nickler jgarzik Fistful_of_Coins dardasaba sl01 isis gwillen stonecoldpat BlueMatt face airbreather dasource smooth phantomcircuit ajweiss sdaftuar coryfields Xzibit17 yrashk artifexd Zouppen kumavis mariorz catcow Krellan michagogo forrestv Muis cfields platinuum Oizopower BananaLotus catlasshrugged Keefe JonTitor petertodd kanzure eric mappum jbenet wiz grubles midnightmagic heath gnusha warren Adrian_G Iriez lechuga_ dignork
09:05:16weber.freenode.net:Users on #bitcoin-wizards: kinlo jessepollak ahmed_ Graet ryan-c Eliel veox amiller warptangent indolering K1773R TD-Linux leakypat CryptOprah Apocalyptic guruvan Anduck paperbot fenn harrow a5m0 SubCreative d9b4bef9 DoctorBTC mr_burdell NeatBasis Hunger- davout Alanius brand0 @ChanServ throughnothing btc___ HM2 azariah MRL-Relay otoburb hguux__ so phedny roasbeef BrainOverfl0w wumpus jcorgan jaromil bbrittain
10:07:16adam3us:andytoshi: you might be able to make a threshold ringsig by committing to two c_i, c_j values with a degree two directed cycle. seems like in the obvious construction you would reveal the distance between the two known keys.
10:11:04wiz:wiz is now known as shroff
10:14:36shroff:shroff is now known as wiz
10:23:43fenn:zooko: any thoughts on this? http://archiveteam.org/index.php?title=INTERNETARCHIVE.BAK http://archiveteam.org/index.php?title=Talk:INTERNETARCHIVE.BAK
10:30:52brisque:brisque has left #bitcoin-wizards
10:31:41fluffypony:fenn: given a super-user-friendly wrapper to Tahoe-LAFS you could have something distributable quite easily
13:47:39andytoshi:adam3us: interesting. i think this works (as does committing to the sum say by H(g^{s_1}g^{s_2}y_1^{c_1}y_2^{c_2}) ) but in both cases each vertex corresponds to a pair of keys, so to really make it 2-of-n you'd need n^2 vertices; if you have only n vertices it's "any of these n pairs"
14:17:14zooko:fenn, fluffypony: interesting! Thanks for the link.
14:25:05zooko:Do you know if there is a mailing list or otherwise how I should contact those folks?
14:27:43adam3us:andytoshi: curiously i seem to have a size 2 ringsig. baffled. (assuming you know product of all public keys, and can query for random public keys from the utxo set)
14:28:15adam3us:andytoshi: you need to look at 4.2 scheme in https://eprint.iacr.org/2003/067.pdf
14:31:04adam3us:andytoshi: s is the index of the signer, pick a random j and compute all a_i values (for i!=j) as eg a_i=H^k(a_0) and R_i = g^a_i (forall i!=j again). finally observe you can compute R_j in the method they use to compute R_s, even the j != s. and so you get a size 3 ringsig (sig = R_j, a_0, s)
14:31:48adam3us:andytoshi: however looking at that for a while you realise you only need one R value. (in the above all a_i other than a_j are disclosed, you need to keep a_j private for security otherwise you leak your private key).
14:33:54andytoshi:adam3us: o.O incredible, you must be wrong ;) i'll check it out
14:34:13adam3us:andytoshi: the resulting signature for l=3 (3 public keys y_1=g^x_1 etc) is (R,s) signing for signer i=2, where R=g^a/(y_1*y_3)^H(m,R), s=a+x_2*H(m,R)
14:34:55adam3us:andytoshi: well i think i convinced myself the only way I am is if 4.2 signature in that paper is broken.
14:35:40adam3us:andytoshi: verification is to check g^s=?R*(y1*y2*y3)^H(m,R)
14:41:01andytoshi:adam3us: wow!
14:41:19adam3us:andytoshi: yeah
14:44:37andytoshi:their proof looks very simple to adapt, i will do that as a first step to see if anything breaks, then fill in the "can be shown ... in the extended paper" etc parts
14:44:55andytoshi:but just looking at your scheme, you can sorta see that it's just as secure as a schnorr sig
14:45:30adam3us:andytoshi: if this holds water it constitutes a trapdoor free discrete log accumulator with a fixed size standard schnorr signature sized set membership proof
14:46:57andytoshi:adam3us: yes, so, this does still seem too good to be true, so i will not let my heart race ... plus "why has nobody else thought of this, it's just multiplication?" ... but it seems to hold up
14:46:57adam3us:andytoshi: (spent the entire weekend trying to get variants to work:)
14:47:12andytoshi:oh, ok, if it's only obvious in retrospect i'm more confident :)
14:48:41adam3us:andytoshi: another way to look at it is well that signature form is a lot more amenable (4.2) its also size 2+n, but there are limited restrictions on a_i values. so then the problem is to choose random a_i values such that l-1 of them are from a CPRNG and the last is chosen at random, in such a way that you cant tell which is the random one
14:49:29andytoshi:i spent a long time thinking about "l-1 are CPRNG and you can't tell which is the lth" and couldn't get sublinearity
14:49:51andytoshi:ohh, i see, a is the sum, so that gives it to you ... and in this case you actually only need the sum
14:50:01adam3us:andytoshi: which is a double headache when you use that hash-ring ringsig. but here its much simpler construction, and that observation that you can sign using a R_i value where you are signing as j such that j!=i does the trick. the rest is an observation that wait what do we even need the l R_i values for.
14:50:02andytoshi:for verification
14:51:34adam3us:andytoshi: right. verifying a sum is clearly useless for convincing the verifier of anything.
14:53:23adam3us:andytoshi: also if l=1 this thing is a schnorr signature
14:53:28andytoshi:do you have a rigorous argument for why this doesn't reveal the signer's index? i think it is not statistically indistinguishable bc a appears in both cases, but maybe distinguishing reduces to DL or DDH or something?
14:54:23adam3us:andytoshi: i think any of the signers could generate the same signature equally likely at random.
14:56:07andytoshi:ah, yeah, that's correct in the RO model (i think: a and H both give results in {0,1}^n, together they span all {0,1}^{2n} sigs)
14:57:33andytoshi:oh, no, even for a fixed hash fn i think you are right
14:58:19andytoshi:s can be chosen uniformly at random, then this implies the same R for every signer (tho a will be different)
14:59:14adam3us:andytoshi: right. i believe that means it retains the unconditional privacy claimed in the paper.
15:00:44andytoshi:i think you still need an RO to argue it (because you want H(m,R) to be stat independent of R) but yes, i believe that's correct
15:01:19adam3us:andytoshi: yes there could be a little bias from the non-uniformity of the hash function.
15:03:25andytoshi:i have to sit through a 90-minute undergrad crypto lecture today, i will try to reduce schnorr to breaking this (because i'm not comfortable enough with forking lemma stuff to believe my own proof of such a consequential result, tho im ok with blindly believing schnorr is secure)
16:22:03kanzure:funny to see the european central bank talking about proof-of-stake http://www.ecb.europa.eu/pub/pdf/other/virtualcurrencyschemesen.pdf
16:30:33tromp:and further displaying their ignorance in "
16:30:34tromp:Currently, efforts are put
16:30:35kanzure:"... the Bitcoin protocol does not require or provide any identification or verification of the users, nor does it generate historical records of transactions"
16:30:36tromp:into using the X11 algorithm for reasons of higher cryptographic security and lower processing
16:30:37tromp:costs, so it is quite possible that the algorithms mentioned above will be replaced shortly.
16:30:57kanzure:this is an impressive level of ignorance
16:31:24fluffypony:* fluffypony shudders
16:31:49brisque:this is exactly why you should hire competent consultants.
16:31:53tromp:they also claim that no custom hardware is developed for scrypt:(
16:31:57fluffypony:"lower processing costs" is literally the stupidest thing I've ever heard
16:32:24fluffypony:"it doesn't use 100% of the CPU/GPU when mining, it must be because it's efficient!"
16:32:24brisque:fluffypony: it stems from the fact that X11 GPU miners have very low power draw due to poor optimisation.
16:32:39fluffypony:brisque: yes
16:33:10fluffypony:I mentioned that in an interview last week, that the "power savings" of X11 are fictitious, and as a result of bad optimisation
16:35:29kanzure:now here's what you should really be worried about: what if this is their default level of investigation into any topic, not just bitcoin?
16:38:20brisque:bitcoin in general is a pretty difficult concept to gather information about. there's very few authoritative sources of good information, few people who understand the concepts well enough to separate the signal from the noise. lots of the common knowledge about bitcoin is completely untrue as a result.
16:43:41fluffypony:so then why not approach the developers?
16:44:10andytoshi:fluffypony: the devs are very busy and it's not obvious a priori that they are the experts
16:44:53andytoshi:fluffypony: there is a problem in this space that if you don't understand the tech really well then it's basically "our word against andreas/drk/whoever" and those guys are paid more than us
16:44:59fluffypony:true on both counts, what I meant to wonder is if they even try
16:45:05brisque:fluffypony: it's difficult to tell a hack from a developer if you're not in this world.
16:45:23kanzure:brisque: the first step is to ask them if they are a developer
16:45:50tromp:for all we know they contacted the X11 devs believing they are experts
16:45:51fluffypony:I suppose Linus gets approached by fewer businesses than Canonical do
16:46:26fluffypony:tromp: I really hope not, but it's entirely possible
16:48:23fluffypony:in other news, how's Cuckoo Cycle going?
16:48:42tromp:some ppl told me they're planning a new coin using it
16:49:21zooko:I'm very interested in Cuckoo PoW.
16:49:44brisque:kanzure: maybe not. see while I might dismiss a crackpot blog that's ranting for pages on end about how secp256k was generated using the hash of hell and will cause us to burn as a result, it's hard for other people to make the distinction between that being nonsense and having a basis in reality. without the background knowledge that's a lot better than sipa almost single handedly writing headers first, isn't it?
16:49:52tromp:hi Zooko! any feedback from the scientists?
16:50:04zooko:Hi tromp! No, I haven't brought it up to them yet.
16:50:13zooko:* zooko makes a note to self to do that.
16:50:21tromp:you made that note before:)
16:51:13kanzure:brisque: this is all just extremely basic knowledge acquisition stuff though. if anything i would expect them to know how to do knowledge acquisition well.
16:51:14zooko:Well, not in these notes here I didn't. :-)
16:51:37kanzure:"first step to not breaking everything: be aware of prinicpal agent problems and epistemology, or sources of knowledge and why people claim to have certain knowledge"
16:51:49kanzure:*principal agent
16:52:11brisque:kanzure: knowledge acquisition will tell you the UTXO is stored in memory. there's published books on the matter, lots of reddit posts and people talking about it on bitcointalk. surely that's correct then?
16:52:13fluffypony:"PoS systems rarely have a SHA-256 algorithm"
16:53:03andytoshi:without reading this, it sounds like it's actually logically impossible to extract an implementation from it, so i suspect this is not something we need to worry about
16:54:10kanzure:brisque: no, that's not knowledge acquisition -___-
16:54:34kanzure:brisque: that's just reading reddit.. that's not how you know things.
16:54:52fluffypony:kanzure: but you may stumble on to Reddit comments / threads when Googling for stuff
16:55:27kanzure:googling for stuff is also not often how you know things.. that might tell you about the existence of certain ideas, concepts, or perspectives. but again that' not how you know something.
16:55:51brisque:kanzure: I read it in a published book, googled around and there's lots of people talking about it as fact. is that not due diligence?
16:56:01kanzure:that is definitely not due diligence
16:56:22kanzure:have you guys never verified anything ever?
16:56:40fluffypony:I read it on the interwebz
16:57:08sipa:i just trust what #bitcoin-wizards conclides
16:57:08brisque:given the relative importance of the "fact", I think it would be going overboard to research it further if you were trying to understand bitcoin.
16:57:57fluffypony:sipa: conclides...?
16:57:57andytoshi:kanzure: "not due diligence" sure but surely you can see expecting that to work, i mean, it can't be that 99% of everything published about bitcoin is lies, right? how would that even happen?
16:58:08andytoshi:(btw i am curious about the answer to "how did this even happen?")
16:58:21zooko:Perhaps you folks should apply these techniques of discerning principle/agent problems
16:58:28fluffypony:andytoshi: they used a "top tier consulting firm"
16:58:29fluffypony:(I guess)
16:58:31zooko:and why folks claim to know things, and all that
16:58:32sipa:fluffypony: concludes
16:58:43zooko:to the question of what purposes are served by that bank publishing that document.
16:58:51kanzure:andytoshi: no, i can't really believe that a central bank would have such a poor understanding of how knowledge works
16:58:52zooko:Maybe technical accuracy is useless or even an impediment to their goals.
16:59:00zooko:I don't know. I haven't done that exercise of trying to discern that stuff.
16:59:06fluffypony:sipa: ah, so follow-the-herd then, it just happens to be a particularly gifted herd :-P
16:59:23sipa:fluffypony: a herd that rarely actually comes to a consensus :)
16:59:29fluffypony:hah hah
16:59:43brisque:kanzure: look, neither can I, but that wasn't the point I was making, just that it's hard to work out right from wrong with this particular subject due to the tight clustering of knowledge.
17:00:22kanzure:brisque: yes but then the correct thing to do would be to *increase* carefulness, not *decrease* it
17:02:48Luke-Jr:andytoshi: it's actually not that surprising IMO
17:04:55brisque:andytoshi: I can't go into the details, but I did consult for a company who had an absolutely insane idea of what to do with bitcoin. unworkable expectations of fairy dust, the takeaway I got from them was that the problem was me, they'd find someone else to consult with who would tell them it's possible. it's always possible something like that happened.
17:05:35brisque:you say our idea is insane? we'll find someone who we can pay to say it isn't.
17:08:30kanzure:"Research perspectives and challenges for Bitcoin and cryptocurrencies" http://www.jbonneau.com/doc/BMCNKF15-IEEESP-bitcoin.pdf
17:09:39kanzure:oh wait, i didn't recognize this paper because it wasn't posted by amiller
17:10:17amiller:yes it was
17:10:56kanzure:well i'm out of ideas. i just didn't see you.
17:15:23brisque:I don't understand "turing complete scripting" being presented as a simply positive thing, with little regard to what it actually gives you and what it takes away. as far as I'm aware there's never been a case where someone has been obstructed by the lack of loops.
17:15:33brisque:(that's RE that paper)
17:16:03runeks:So, what do people think about the proposed "Lightning Network"? http://lightning.network/lightning-network-paper-DRAFT-0.5.pdf
17:28:42maaku:brisque: what does it take away?
17:29:27brisque:maaku: static analysis, or ease of it anyway.
17:29:50maaku:brisque: that's pretty orthogonal, unless there's a specific analysis you are talking about (e.g. runtime)
17:30:22maaku:but runtime analysis isn't a concern for bitcoin scripting -- the signer has that information
17:31:31brisque:halting problem means you end up with awkward solutions like Ethereum uses, where they burn fees rather than using them as a mining incentive.
17:31:57amiller:brisque, i dont think your criticism makes any sense yet
17:32:23brisque:amiller: I'll put them on the backburner for the moment then.
17:32:42maaku:brisque: I disagree. Ethereum's approach is awful, but that's their fault. Include execution statistics (e.g. opcode count) in the signature. If it doesn't match, invalidate the transaction
17:32:51amiller:first of all, in ethereum the fees aren't burned, they're given to miners
17:33:24maaku:brisque: please don't. i'm interested to hear what your critiques are
17:33:28sipa:the full node network ought to set the limits of what execution cost is acceptable
17:33:32sipa:not miners
17:34:03maaku:sipa: but that's an ideal we don't have now
17:34:05amiller:there's an auto adjusting of the gas limit per block, that's a different issue though
17:34:08brisque:amiller: are you sure about that? I would have sworn they burn them, reason being that otherwise they aren't really a denial of service limiter if you're a miner.
17:34:35sipa:maaku: we do; checksig limit per block and blocksize limit in bytes
17:34:41sipa:the limits may not be well-chosen, but they exist
17:35:02amiller:brisque, for now they're given to miners, there's been some talk about burning a portion of it to avoid some incentive misalignemnt, but that's really unrelated to turing completness
17:35:31sipa:i think turing completeness is mostly irrelevant
17:35:36sipa:harmless, and useless
17:35:47amiller:i think so too, it's a red herring of a phrase, really the point is just 'more expressive'
17:36:11sipa:my only real problem with is that it adds unnecessary complexity
17:36:25amiller:that seems subjective, its arguably not that complex
17:36:50sipa:i'll need to see a use case for it before i'm convinced :)
17:37:06maaku:sipa: I'm not sure how that is different? you could have hard limits no matter what scripting system is used
17:37:13sipa:maaku: yes
17:37:15amiller:the last thing i want to argue about with brisque is that static analysis isn't actually the issue
17:37:21sipa:which is why i say it's orthogonal
17:37:26amiller:"static analysis" is often about like denovo analysis of exisitng legacy code
17:37:35amiller:like i'm going to apply some static analysis to the big bucket o' openssl code
17:37:38brisque:amiller: wonder where I got that idea from, I thought that was mentioned authoritatively somewhere but seems not, sorry about that.
17:37:54amiller:but if you want to assert things about ethereum contracts, you can provides hints to the static analysis or a proof about whatever constraint holds
17:38:23amiller:(that's all theoretical i don't think anyone proposed concretely how to do that yet, but it's obvious from a pl persepctive)
17:39:00sipa:in general, i think the bitcoin scripting system ought to be something that allows signers to prove a particular pre-committed condition was fullfilled
17:39:04maaku:amiller brisque: it's a fair complaint that certain systems are not as amenable to static analysis as they could be. but imho it's a mostly orthogonal issue to turing completeness
17:39:11sipa:which doesn't need generalized execution
17:39:26sipa:and can be made significantly more efficient without
17:39:42sipa:(batch validation e.g.)
17:39:59maaku:sipa: the qustion is whether their exist constraints that are too difficult to represent without generalized computation
17:40:19sipa:of course those exist
17:40:38sipa:the question is whether they are useful :)
17:40:38sipa:(and i have no answer to that question)
18:05:03andytoshi:adam3us: i cant compute R in your scheme, it depends on H(m,R)
18:05:56andytoshi:(and i cant figure a way around this)
18:15:24adam3us:andytoshi: so I think the intermediate version works where R_k is computed as in the paper and R_i=g^a_i for all i!=k j is signer, k is random from 1..l. i think maybe i simplified one too many times, and it needs two R values. (with all l R values it is a size 3 sig vs a size 2; reducing number of R values is a computational not size saving)
18:15:45adam3us:andytoshi: but you are right about the size 2 version.. appears broken.
18:15:58adam3us:andytoshi: well non-functional!
18:26:24bramc:I'm utterly unconvinced that bitcoin's scripting language gains anything whatsoever from its expressivity. Having a list of things which can help unlock a utxo and an enumerated list of subsets which can do it successfully can accomplish everything I've seen seriously claimed the script has ever been used for.
18:27:49bramc:Does anybody have an opinion on my suggestion that a 'better' way of doing ANYONECANPAY is to make it so that in transactions with multiple inputs the individual signatures from the inputs can be either for the whole transaction or just for their specific input and the output?
18:28:14tromp:the other novelty Ethereum brings is having smart stateful contracts
18:28:55sipa:tromp: that's imho the only interesting thing about it
18:28:59tromp:which would be rather handicapped without an expressive script language
18:32:11dgenr8:sipa: why again, do miners need the full-node network?
18:33:23brisque:I might be thinking particularly narrowly here, but the use of stateful contracts seems limited, you're still stuck in the same position where you have no external inputs.
18:33:24sipa:dgenr8: ?
18:33:39sipa:dgenr8: miners are clients to the full node network
18:33:56sipa:they produce blocks that follow the rules mandated by the network
18:34:09sipa:and are paid by subsidy and fees in return
18:34:47dgenr8:sipa: why do they need non-miners? because they don't know the difference?
18:35:17sipa:dgenr8: because they are the ones that give the currency value
18:35:30dgenr8:sipa: how?
18:35:35sipa:withoit users of the system, there is no reason to produce blocks for it
18:35:50dgenr8:sipa: define user
18:36:38sipa:you me
18:36:43sipa:payment processors
18:36:47sipa:and miners themselvds
18:36:59sipa:i'm not saying that miners are not also users
18:37:05sipa:but they are not the only ones
18:37:12sipa:and they are not privileged
18:37:25sipa:they just provide a service the system needs
18:37:26dgenr8:sipa: would it be a problem if miners proved hashpower to each other, connected to themselves, and only looked to that network for transactions?
18:37:58dgenr8:ok that's what I was looking for
18:38:06sipa:it would mean they could give themselves as much money as they wanted
18:38:16sipa:if nobody could verify their correct operation
18:39:00dgenr8:so preserving the state where the network contains non-mining full nodes is critical
18:39:27dgenr8:do explain ;)
18:39:27sipa:it is critical that anyone who _wants_ is able to validate the system's correctness
18:39:52sipa:whether they actually do, or how many people do, or whether they are non-miners is not relevant
18:40:21dgenr8:who cares whether some random person thinks the all-miner network that receives all transactions is correct or not
18:40:59sipa:it's the only interesting thing in bitcoin imho
18:41:20sipa:a monetary system that works without needing to trust anyone, for almost all of its operation
18:41:36sipa:if i lose that abiloty, i'll gladly ise paypal instead
18:41:43sipa:*ability, use
18:41:57dgenr8:what good is having that ability unless miners need you for something?
18:42:15sipa:it's other way around
18:42:25sipa:me, and every other user of the currency, needs miners
18:42:39sipa:they need us for the btc they receive to have valie
18:42:52sipa:a currency that isn't used has no value
18:43:16dgenr8:today they need us
18:43:59dgenr8:because the transactions are submitted to the p2p network
18:44:08sipa:transactions are irrelevant
18:44:14sipa:they can be broadcast in any way
18:44:32sipa:they're not part of bitcoin's consensus model
18:44:35sipa:only blocks are
18:45:00sipa:and full nodes set the rules on what blocks are valid
18:45:12sipa:and miners create blocks obeying those rules
18:46:01dgenr8:they why would it be a problem if miners proved hashpower to each other, connected to themselves, and only looked to that network for transactions?
18:46:21sw:sw has left #bitcoin-wizards
18:46:23sipa:i may misunderstand the question
18:46:32sipa:where they look for transactions is totally irrelevant
18:46:44sipa:the question is whether people accept the blocks they produce
18:48:00dgenr8:in this reality, people = other miners
18:48:28sipa:assume miners decide among themselves that a 100 BTC reward is totally acceptable
18:48:35sipa:100% of miners agree about this
18:48:41sipa:what would happen?
18:49:08sipa:the rest of the network ignores their blocks, a new miners will pop up that produce blocks that the network accepts
18:49:12belcher:the 100btc would be valueless because no investor would want it, miners wouldnt make any money
18:49:27sipa:*and new
18:52:54maaku:bramc: there are use cases for which an expressive script is required. in particular conditions of spend which are forced-inhereted by child transactions
18:53:34bramc:maaku, What do you mean? Can you give an example?
18:53:37maaku:indeed that is the only category of conditions that i've so far discovered which absolutely benefits from expanded script
18:54:44maaku:bramc: e.g. redemption of IOUs -- a condition attached to an issued IOU which allows the issuer to replace it by its face value at any time, no matter its current ownership status
18:55:46maaku:i have so far found no other way of implementing that except by inhereted constraints (aka covenants), and no way of doing that neatly except by generalized execution
18:55:59bramc:dgenr8, Without mining you can verify transactions but you can't verify that a particular coin wasn't spent already. The entirety of bitcoin's mining and consensus model is a glorified distributed database whose only guarantee is that double spends don't happen. Or at least, double spends would require more than a certain amount of resources to be able to pull off.
18:56:42bramc:maaku, Do you have a link for that? I honestly don't know what you're talking about, and would like to read up on it.
18:57:20maaku:bramc: it is not written up anywhere, to my knowledge. i'd be happy to answer questions about it though
18:57:37bramc:Well for starters, what is an IOU?
18:57:46sipa:i owe you
18:58:05bramc:sipa, I know that, I meant more specifically and technically
18:59:11Adlai`:Adlai` is now known as adlai
18:59:15sipa:bramc: oh, sorry, no idea then
18:59:18maaku:bramc: asset issuance could be implemented any number of ways -- colored coins, natively validated assets with a fork, committed transactions, etc.
18:59:42maaku:but an IOU is just some issued asset that I, the issuer, promise to someday redeem for face value plus interest
19:00:37maaku:the trouble is that if there is interest, I can be held hostage by the owner so long as the interest I originally agreed to is above market rate
19:01:03maaku:the owner will just hold on collecting interest and refusing to let me take it back, at least until he fears I might default
19:02:36bramc:Not sure what you're saying. It's possible to have interest-bearing things in bitcoin, but they're unspendable until due, which isn't very useful.
19:03:03maaku:so you put a condition on it -- the IOU can be transferred to someone else by its owner, in which case the condition follows, OR anyone can replace it with its face value and accumulated interest, and the condition is dropped
19:03:31bramc:What is an IOU in bitcoin land? All there are are utxos.
19:03:52maaku:bramc: i'm not sure what you're saying either. it's prefectly possible to have interest-bearing things that continue to accumulate interest while being used
19:04:36bramc:Can you give an example of a utxo script to support this stuff?
19:04:59maaku:bramc: no, because bitcoin scripting language is not expressive enough to do this, which is rather the point
19:05:35bramc:Can you give an example of a script which could be made in an extended scripting language?
19:06:26maaku:bramc: are you familiar with the concept of a quine?
19:07:06bramc:I think i remember reading a hofstadter essay about them when I was in high school. Something about self-referencing sentences
19:07:32maaku:a computer program which takes no input and prints its own source code
19:08:24maaku:so the simplest version is - push my own code on the stack, push the output on the stack, check that the output script starts with my own code, yield
19:09:54maaku:it's known as a 'covenant' around here because it allows you to attach a condition to a coin which is carried over to whoever later owns it, and can only be removed (if it can be removed) under explicit conditions
19:10:32yoleaux:Mon, 02 Mar 2015 19:10:32 UTC
19:10:36yoleaux:CoinCovenants using SCIP signatures, an amusingly bad idea.
19:12:09maaku:an amusingly awesome idea. i wish gmaxwell didn't title it that way
19:13:02tromp:sounds like an amusingly controversial idea:)
19:13:06bramc:maaku, Isn't bitcoin script incapable of evaluating the output which a utxo is going to?
19:13:34maaku:bramc: in principle? no, that information is available in the transaction
19:13:57maaku:bitcoin script can't do that now because there is no opcode to access that information
19:14:09sipa:maaku: that we know of
19:14:11bramc:That's what I thought
19:14:19maaku:(and the other opcodes you'd need -- substr, etc., are disabled)
19:14:22sipa:i wouldn't claim it is provably impossible
19:14:36maaku:bramc: hence, the argument for more expressive script
19:16:09bramc:This covenants post is reminding me of how back in 2002 acadamics thought it was awesome to spend time studying XML for all the awesome things it would enable
19:16:26bramc:I made bencode and that was that.
19:16:38maaku:bramc: if checksig wasn't a monolithic opcode but rather implemented as push-tx-data, hash, ecdsaverify as separate opcodes, this would have been doable with bitcoin 0.1
19:18:09bramc:I'm with gmaxwell on this: "Any attempt to think of why someone might want to do this leaves me screaming in horror"
19:18:28bramc:It seems like an explicit violation of the doctrine of first sale
19:18:45sipa:it breaks fungibility of coins for starters
19:18:48maaku:bramc: I just gave you above a very valid reason for doing this -- IOU redemption at issuers request is otherwise impossible
19:19:17sipa:but the argument in favor is that there are very interesting applications, which, if supported in a generic way, almost certainly enable covenants as well
19:19:26maaku:not to mention that there are plenty of other constructs you can come up with -- e.g. spending limits
19:20:05bramc:Or transaction fees :-P
19:20:55bramc:With this, an exchange could start tacking covenants onto transactions which (a) block further covenants and (b) require a fee be paid to the original exchange every time the coin changes hands
19:21:49maaku:bramc: who would accept such a coin?
19:22:40bramc:maaku, Anyone whose wallet supported it
19:23:22tromp:such coins would be deemed practically worthless
19:24:35gwillen:bramc: wallet software right now will only recognize specific script templates as coins "paid to it"
19:24:57gwillen:so it would have to be specifically changed in order to recognize a convenanted coin as an inbound coin being paid to it
19:26:08gwillen:(which means that even if an exchange wrote in its ToS that it could send you convenanted coins, users would rebel if it did, since they would just see that they received no coins)
19:26:21maaku:covenants break fungibility when they are used. thankfully it's not something that can just be transparently added to someone's pubkey
19:26:40maaku:every wallet would have to be upgraded to specifically understand these new covenants
19:27:06bramc:I think the only reasonable policy is to automatically reject any covenanted transaction
19:27:31maaku:bramc: correct. accept only whitelisted covenants
19:27:48brisque:you can ignore but not reject
19:27:52maaku:attach anything not understood by the user base and you've effectively burnt the coins
19:28:05maaku:bramc: i assume that's what he meant..
19:31:16bramc:You can also, of course, encourage reasonable policies about covenants by not adding support for them to the scripting language to begin with
19:31:28bramc:Because, you know, doctrine of first sale.
19:32:06sipa:the problem, we have discovered, is that it is incredibly hard to make covenants impossible
19:32:15sipa:bitcoin itself barely avoided it
19:32:17sipa:very barely
19:32:41sipa:you don't need explicit support for them
19:33:58bramc:If you make it so that the output isn't available for the script to evaluate then there's no problem.
19:34:00maaku:that plus: they actually solve real problems that otherwise have no acceptable solution
19:34:22sipa:bramc: but you want outouts covered by the signatures
19:34:33sipa:which brings them implicitly into scope
19:34:44bramc:maaku, I still don't understand what you want your IOU covenant to do. Trying to parse what you wrote it sounds like an output which can be reclaimed at any time
19:35:05sipa:just the ability to request "what is the hash i would have to sign for this transaction" is enough to have a covenant
19:35:47bramc:oh right, you can make it so that the output has to be provided so you can verify it.
19:35:55maaku:bramc: you give me an IOU with 10% interest. I then decide to sit on it, because 10% annual interest is awesome. you want it back. how do you get it back?
19:36:24bramc:maaku, Do you mean how can I pay it off?
19:36:38maaku:the covenant lets you pay it off at any time
19:36:55bramc:Not sure what point there is to doing IOUs in bitcoin, because there's no enforcement mechanism. I can just, you know, not pay it.
19:38:17bramc:sipa, If you have a completely lobotomized signature system which doesn't allow anything even vaguely resembling scripts then avoiding covenants is straightforward.
19:38:49sipa:also not very interesting
19:38:57sipa:i agree, it is easy to avoid
19:39:17sipa:but not in any interesting system
19:39:28bramc:sipa, totally interesting, you can still have hash preimage reveals, hence simultaneous transfer
19:39:44sipa:sorry, too tired now :)
19:39:47sipa:sipa has left #bitcoin-wizards
19:40:38bramc:You can even have preimage length checking (you'd have to work extra hard to avoid it) which allows for gambling
19:44:43maaku:bramc: first-sale doctrine doesn't apply here
19:45:34bramc:the theory behind it does. First sale doctrine was created to stop a lot of predatory practices which vendors had
19:46:24maaku:*sigh*. the covenant solution *provides* first-sale doctrine rights
19:46:59maaku:otherwise if I wanted right to pay off at any time I'd have to have multisig control over the coins or something, and that's too granular a permission
19:48:17maaku:the covenant solution is saying "I give up any control over who gets this IOU. You can resell it to anyone at any time for any price. I reserve the right to pay it off at a time of my chosing, but claim no other rights beyond that."
19:51:01dgenr8:bramc: that's why miners are needed, but that wasn't my question
19:51:08dgenr8:sipa: if I may summarize you, miners need the validating p2p network because that's where users look. The fact that the transactions come from there is irrelevant.
19:52:29bramc:dgenr8, I have no idea what point you're trying to make
19:55:12dgenr8:just seeking to understand sipa's comment that the p2p network sets rules for miners
19:55:50brisque:the p2p network is sort of unrelated, it would work (though probably not quite as well) via smoke signals.
19:56:50dgenr8:i didn't say "the IP network"
19:57:30brisque:neither did I.
19:58:14skittylx:non-mining nodes would reject the blocks
19:58:27skittylx:wrong windows srry
19:58:37brisque:I may have missed the point, perhaps
20:06:46bramc:brisque, Smoke signals would have much longer latency, which would cause all kinds of problems
20:07:44brisque:so increase the block time? point was anyway that the p2p network doesn't have much do to with anything. in fact it's preferable to have other transports.
20:08:27bramc:You could do IP over smoke signals
20:13:12dgenr8:I could have said "I didn't say ethernet" but then I 'd get a whole different kind of nitpicking ;)
20:15:47brisque:it was hyperbole so undeserving of anything anyway.
20:52:48brisque:brisque has left #bitcoin-wizards
20:56:20andytoshi:adam3us: even the two-R version doesn't seem to work, no matter what i try i'm either (a) impossible to compute or (b) trivially forgeable, you can't just choose a random j and pretend it's the signer's index
20:57:35andytoshi:because in the scheme as written, you'd need to compute x_j*H(m, R_j) (which is impossible) ... if you calculate R_j as R_s in the paper (punching at s) then you have R_j depending on H(m, R_j)
21:04:56adam3us:andytoshi: so step one do you agree one can replace a_i where i!=j (they call s=j the signer in the paper) st a_i = H^i(a_0). (regardless that this identifies the signer as then you know a_j is the signer.
21:12:26andytoshi:adam3us: yes, agreed
21:30:10waxwing__:waxwing__ is now known as waxwing
21:39:22adam3us1:andytoshi: ok then if you try replace R_k for R_j and still make a sig where k !=j random 1..l
21:41:05adam3us1:andytoshi: hmm that may have a related problem. uh oh
23:23:38fenn:zooko> Do you know if there is a mailing list or otherwise how I should contact those folks? <- efnet channels #internetarchive.bak and #archiveteam-bs
23:24:13fenn:or just write stuff on the wiki, the password is "yahoosucks"
23:28:49fanquake_:fanquake_ is now known as fanquake
23:33:51zooko:fenn: thanks!
23:49:29bosma_:bosma_ is now known as bosma