03:50:09gmaxwell:Been talking about people getting scammed in another channel (geesh, some scammer on the forum just got 200 btc from a single person!) Posted this: https://bitcointalk.org/index.php?topic=398041.0 "
03:50:13gmaxwell:Cryptographically private loan risk management "
06:25:35andytoshi:gmaxwell: why can't alice just sybil that?
06:25:54andytoshi:if she wants to borrow more than her lenders want, just restart with a new tree
06:28:30andytoshi:or better, have a new tree for each lender -- then they all see a proof that their entry was added, and each sees only their own total
06:32:04gmaxwell:andytoshi: note the first line— assumption is that the reputation system is already preventing that.
06:32:23andytoshi:oh, derp, i read right through that
06:32:54gmaxwell:andytoshi: a common pattern we see on otc and bitcoin talk is that someone starts an account and makes boring breakeven trades for a year, gradually increasing the amounts, and then does tons of large loans all at once.
06:32:56andytoshi:the line "she publishes the root hash and the proofs in the rep system"
06:33:55gmaxwell:andytoshi: example https://bitcointalk.org/index.php?topic=393593.msg4274997#msg4274997 (thats just one post in a six page thread of people who were ripped off)
06:35:06gmaxwell:suggestions that people publish their loan amounts in OTC in the ratings list have generally been met with unwelcome sounds wrt privacy... though people do it sometimes, esp for smaller amounts with newer traders.
06:35:36andytoshi:ok, i see now, this is really cool .. i think it has the highest usefulness/computational hardness ratio of anything you've posted involving zk proofs
06:35:54gmaxwell:yes, also ... implementable outside of bitcoin.
06:36:19gmaxwell:(Any idea where step 1 is change bitcoin ... is just a lot harder to do, regardless of the details)
06:36:43andytoshi:i'm going to go post this in #coindev and see if anybody wants to implement it..
06:37:41gmaxwell:also, since it involve loss of currency, the CRS-assumption ZKP systems (where you trust that some key creator has thrown away a master key) aren't so bad.
06:38:08gmaxwell:e.g. you're trusting someone to not have kept data that would allow them to make fake loan accumulators. whoptiedo.
06:38:10andytoshi:i wonder if there's a stronger/simpler zk proof system for updating merkle trees like this
06:38:21andytoshi:which maybe doesn't work for general computations
06:38:55gmaxwell:maybe, though as soon as you need proofs for bitcoin thats right out.
06:40:37warren:I suppose this is why the credit agencies ding you for hard pulls.
06:40:50gmaxwell:in any case, proving a very simple function like this should actually be quite realistic, e.g. cpu time of tens of seconds.
06:41:15gmaxwell:warren: hah you could actually make number of proofs a metric that it tracks and extracts.
06:41:35gmaxwell:(e.g. to do a proof for someone they give you nonce, which you must insert into a pulls counter tree.)
06:42:19gmaxwell:it's not quite so cheap that my trivial NIZK would be useful, I expect.
06:42:35gmaxwell:but I guess I should go count how many AND-gates sha256 has.
09:55:04_ingsoc:_ingsoc is now known as Guest26930
09:55:22HobGoblin:HobGoblin is now known as Guest9007
11:07:38_ingsoc:_ingsoc is now known as Guest57212
11:49:39nsh:happy new year, wizards :)
11:49:59fluidjax:fluidjax has left #bitcoin-wizards
15:08:38tholenst:24 coins built there already...
15:08:49tholenst:and that's not even counting the ones which prefer to remain private
15:09:55Guest9007:Guest9007 is now known as UukGoblin
15:10:26nsh:* nsh considers a "proof of quality" based blockchain
15:10:49nsh:difficult, all involve voting i suppose
15:11:16nsh:e.g. new block whenever someone comes up with a joke that is considered funnier by >75% of people
15:16:29tholenst:The new scip paper http://eprint.iacr.org/2013/879 seems promising, but they still don't give a download link
15:30:47nsh:hmm, ty
15:32:41tholenst:How long does verification of a ECSDA signature take?
15:34:03nsh:depends on the library, etc.
15:34:11nsh:(and scheme)
15:35:46nsh:Wow, it's great.
15:35:46nsh:187us versus OpenSSL's 1008us, on my test laptop.
15:36:04nsh:-- sipa's implementation of sepk256k1, last July
15:38:34tholenst:So they talk of 5ms verification time for a program, but that's not on a lapt, so one would probably have to verify a few hundred signatures -- but they only run their program for 32'000 instructions, so it doens't seem quite useful for signature verification yet
15:39:42tholenst:also they talk of a 16 bit machine...
17:04:09luke-jr_:luke-jr_ is now known as Luke-Jr
17:06:04andytoshi:oh my god, the comments on BlueMatt's altgen thread..
17:09:56nsh:always wear appropriate protective eyewear. do not stare directly at derp
17:10:29adam3us:andytoshi: on bct?
17:10:58andytoshi:adam3us: yeah, https://bitcointalk.org/index.php?topic=396991.0 -- jtimon posted it a few hours ago
17:13:19adam3us:andytoshi: lol 'bulk discounts' etc
17:13:38jtimon:yeah, this was hilariously absurd: https://bitcointalk.org/index.php?topic=398272.0
17:14:25nsh:"We will hard fork you out, then we will have to continue with GPU without you." (imagines set to all your base graphics...)
17:17:26tholenst:It's awesome. It essentially says: "If you give me money, that'll help me to fraud people!"
17:17:35nsh:there's reductio ad absurdum and then there's straight out building a highway to absurdity.
17:30:33jtimon:hehe highway to absurdity...
17:40:30Luke-Jr:"Yes, it works fine and you do not end up on the wrong chain as long as you have a different network packet magic - as your node will never peer with another node with a different magic."
18:59:12jtimon:does anyone know if any of the results have been launched on the alts subforum already?
19:26:01Luke-Jr:nsh: can I quote you? [17:17:31] there's reductio ad absurdum and then there's straight out building a highway to absurdity.
19:26:11Luke-Jr:(I already did, but I forgot to ask first..)
19:31:27Luke-Jr:"hello, is there a way to set a permanent change address?"
19:31:31Luke-Jr:why do I get these PMs now?
19:32:44Luke-Jr:* Luke-Jr replies "No, because that would be broken and stupid."
20:13:04edulix:edulix is now known as Edulix
20:44:24_ingsoc:Does anyone mess around with Go?
20:45:37gmaxwell:tholenst: their scaling is nearly linear, so you can scale up the cycle count. Also, 32000 instructions is enough to do hash based signing. In any case, the tinyram stuff is always going to be less efficient (by ... 10 to 1000 fold) than direct circuits specialized for the task at hand.
20:58:17nsh:tinyram is just a didactic model though. there's no reason you couldn't adapt it to specialized problems
20:58:25nsh:(that i can think of, at least)
21:00:41gmaxwell:nsh: well kinda, there are ways of using this stuff where you want the circuit under evaluation to be a constant thing.
21:01:12gmaxwell:and with tinyram you could make it constant (or at least constant up to some execution length) and the hash of the program being run is just a public input.
21:01:41gmaxwell:so it really can be useful to have a fully generic circuit.
21:01:46nsh:* nsh nods
21:03:12gmaxwell:you could, of course, add extra instructions. e.g. for our applications a SHA256 operator would be super useful.
21:03:38nsh:hmm, good point
21:05:13tholenst:gmaxwell: yes, i know... i was trying to get a grasp of whether it would be useful for example just to batch all signature verifications... but I found it difficult to assess. Would be nice if there was an implementation available
21:06:32gmaxwell:tholenst: yea, I don't know why they haven't made it available. They're using the same backend math as pinocchio, so you could look that up.
21:06:51tholenst:I could just ask them :)
21:07:12gmaxwell:tholenst: IIRC only a few of the pairing operators are input specific, as I recall.
21:07:22gmaxwell:So I think that if your circut is constant you can precompute a fair bit.
21:08:06gmaxwell:(A few, being like two pairing operations I think)
21:08:12tholenst:i don't acutally have a specific application in mind...
21:11:08tholenst:I was thinking more about extending the scripting language recently anyhow :)
21:12:04tholenst:It should be like this: if you have a reserved opcode in the pubkey script, the script should automatically accept no matter what happened before.
21:14:04gmaxwell:tholenst: well it's not. Its easy to build extensions that work like that anyways.
21:14:33gmaxwell:e.g. just different OP_EVALs for new P2SHes that make transactions look hashlocked to the old nodes.
21:16:43tholenst:do you mean exactly the same as P2SH, but a different op-code instead of OP_HASH?
21:16:54tholenst:i don't see right now how you mean that
21:18:20Luke-Jr:tempting to revise Script in a P2SH^2
21:21:10gmaxwell:tholenst: effectively.
21:22:28tholenst:oh i see -- you can just take one which is effectively a NOP now
21:26:47_ingsoc:_ingsoc has left #bitcoin-wizards
21:47:29tholenst:btw i was thinking more about what it would need in scripting to implement the idea that you can have deposits for your transactions; i.e., if you double spend you lose money
21:47:39tholenst:i think it's reasonable
21:51:24sipa:that implies scriots can access state outside of the chain they operate on
21:51:35sipa:which is extremely jard to get right, i think
21:51:48sipa:scripts, hard
21:52:01tholenst:i don't need thta
21:52:16sipa:double spends don't exist within one chain
21:52:35sipa:if you're even using that word, it implies you're observing other state
21:53:14Luke-Jr:tholenst: double spending is not detectable technically really
21:53:32Luke-Jr:two signed transactions spending the same coin, is not necessarily "double spending"
21:53:43Luke-Jr:it can occur in legitimate circumstances too
21:53:44tholenst:well, the idea is different: I give you a transaction which essentially says: "If you find messages m_1 != m_2, signed with SecretKeyA, then you can have this money here"
21:54:18sipa:you'd need some higher order construxt in transactions
21:54:35sipa:but indeed, that doean't require access to other data
21:54:49tholenst:yes, you need improved scripting, but it suffices to look at the chain
21:54:52sipa:just means you need to embed the two different spending transactions inside your script
21:54:53nsh:interesting idea
21:55:03sipa:no it does not suffice to look at the chain
21:55:16sipa:within the chain double spends are impossible already
21:55:18tholenst:Luke; I know that; a bit more work is necessary for that
21:55:38tholenst:no you just need to embed the two signatures in the script; I can do that
21:55:57sipa:right, indeed
21:56:07tholenst:the chain will get two signatures, from the same secret key, which I assemble from the double spend; thus, the scripting doesn't look outside the chain
21:56:44sipa:but you need some meta construct
21:57:03sipa:where you embed the two previous conflicting signatures as proof that a double spend existed
21:57:09sipa:which is possible and sane
21:57:14sipa:but doesn't exist currently
21:57:31tholenst:actually, until here you don't need so much; you only need to be able to call ECDSA_CHECKSIG directly, and then you can do it similar to detecting a SHA256 collision
21:57:34sipa:(i'm also not convinced about the usefulness, but that's another matter)
21:58:56tholenst:but -- the problem is that the money which is supposed to back your transaction might be gone once you detect the double spend. For this you need more, and weirder opcodes
21:59:48sipa:well if it's gone, it's gone
22:00:16sipa:going beyond the basic rule of "a coin can only be spent once" is dark magic
22:00:29tholenst:i adhere to that basic rule
22:01:17tholenst:the basic idea is: if you spend a "backing coin", you can only spend it in such a way that for the next... say 100 blocks, it still remains a backing coin
22:01:45tholenst:and only after that it can become a usual coin
22:02:59sipa:mhmm... dark magic :)
22:03:35tholenst:i don't think there's anything dark there
22:03:35sipa:(not impossible, and not necessarily a problem, but i think the consequences become horrible to reason about)
22:04:04tholenst:no, why? will you be happy if i give a proof of some good properties?
22:04:13sipa:no need to convince me :)
22:04:22sipa:it's just interesting to think about
22:04:45tholenst:i seriously think it would be a good idea to have it implemented
22:04:53sipa:as in it means the the spending transaction, as long as the backing coin that can spend from under it, even confirmed, is not actually spendable
22:05:11sipa:or at least, losing fungibility
22:05:24sipa:(those coins would be worth less than other coins)
22:05:32sipa:as they're less certain
22:05:37tholenst:no, you can move them back to normal coins, it just takes 100 blocks
22:06:07sipa:you pay me, by spending coins C1, and sending me a coin C2
22:06:15nsh:so wait, we get complete anarchy with a BBC broadcast-loop that removes all the vulgarity and orgies?
22:06:16sipa:as long as C2 is buried less than 100 blocks deep
22:06:33sipa:C1 persists in some form
22:06:38tholenst:no no, I don't send you coin C2; I send you C1, and if I double spend C1, you get to destroy C2
22:06:55sipa:C1 belongs to you, it's the original coin you had
22:07:06sipa:there's nothing special with it, and it's buried 10000 blocks deep
22:07:09tholenst:I own both C1 and C2
22:07:20sipa:wait, what?
22:07:25sipa:i'm not following
22:08:00tholenst:the idea is: in order to pay you with C1, i need to back up the payment with C2. C2 has a different PKScript, which makes it a "backing coin"
22:08:26sipa:wait, let's talk about transactions instead
22:08:40sipa:you create a transaction which spends C1, and what else?
22:08:40tholenst:ok coin = txout
22:09:37tholenst:I give you a PubKey2-signature of "If you find 2 PK-1 signed messages you may destroy the txout C2"
22:10:09tholenst:"PK-1 signed" is supposed to mean "signed with the same key as C1 is"
22:17:59andytoshi:ok, and C2 needs to be a special invalid-for-100-blocks output?
22:18:23andytoshi:it'd be neat if you could mark outputs as "cannot be spent with fewer than N confirms"
22:19:05andytoshi:this is cool, i definitely think it changes coin properties too much to be bolted into bitcoin, but istm that it makes sense
22:20:20andytoshi:as sipa says, there are cases when a "double spend" is a legitimate thing to occur, so these would need to be special transactions
22:20:23andytoshi:it seems to me
22:21:16tholenst:yeah one has to be careful with it; note though that if you can wait a bit (100 blocks) with the double spend, you can first move C2
22:22:01andytoshi:yeah, the receiver of the funds would estimate how long the tx will take to confirm, and require C2 have that many "cannot spent until" ticks left
22:22:31tholenst:anyhow, I plan to write a detailed proposal... I think it's worth it even if it doesn't go into bitcoin. it would finally be some real selling point for an altcoin, imo
22:23:06andytoshi:that'd be great
22:23:20andytoshi:if you can, explore the consequences re fungibility of locking coins like this
22:23:49tholenst:can you elaborate what you mean by that?
22:24:09andytoshi:well, if some coins can be spent quickly and others can't, the quick-spendable ones are more useful
22:24:10nsh:we need an playpit/sandbox for alt-experimentation
22:24:26andytoshi:so rather than "a coin is a coin is a coin" different coins might have different values
22:24:43andytoshi:otoh if they are locked in place, it's hard to claim they have any value, so maybe it's fine
22:24:54andytoshi:nsh: perhaps BlueMatt's thing will give that to us :}
22:25:52nsh:mm, unfortunately as stands it only changes the (mostly) boring things
22:26:06tholenst:well, you just need 100 blocks to get the backing coins back into normal coins; that's not even a day wait.
22:26:21andytoshi:sure, but given that's apparently popular, i'm sure if you gave BlueMatt a patch he'd inject it into the alts for a few days
22:26:28tholenst:it seems people are already fascinated by BlueMatt's thing :)
22:26:49nsh:i suppose there's no shortage of volunteer test subjects
22:27:13andytoshi:tholenst: ok, another thing to think about is what happens if there is a reorg, and the block at which the coin becomes normal changes
22:27:15nsh:quick, before we end up with ethics panel!
22:27:28nsh:good point
22:27:56tholenst:yes, ok
22:28:22andytoshi:nsh: people releasing cryptographic software without understanding it, and then goading people into putting money into them, are evil, there's no ethical concern in fucking with them
22:28:59nsh:* nsh smiles
22:30:37Luke-Jr:andytoshi: evil is evil, even if the victim is guilty of evil things themselves
22:31:31andytoshi:Luke-Jr: fair enough
22:31:56andytoshi:tholenst: so, my specific concern is: suppose a coin becomes valid at block 300000, then i spend it in the next block
22:32:08andytoshi:some reorg happens and now the coin becomes valid at block 300005
22:32:12andytoshi:what happens to my spend?
22:32:33sipa:if the coin creation is reorganized, the spending of it is certainly reorganized too!
22:32:49tholenst:maybe bad things? but for that a 100 block reorg needs to happen, and then bad thing happen anyhow
22:32:55andytoshi:sipa: that's my thought, yeah, but it makes reorgs more complicated
22:33:08sipa:i doubt it
22:33:13Alanius:andytoshi: well, as long as they use the power of argument and not of coercion, I'm not sure "evil" is the right word
22:33:23sipa:let's not go there
22:33:43sipa:andytoshi: if everything is defined within one chain, there should be no problem with reorganizations
22:33:57sipa:but i'm not sufficiently understanding the scheme
22:34:27andytoshi:well, i spend something at block 300000, but suppose suddenly it is invalid until block 300500 (this is an extreme case)
22:34:50andytoshi:so suddenly my payment is invalid, and i have a window in which to double-spend
22:34:50sipa:that cannot happen without invalidating the spend as well
22:34:56sipa:as the spend happens after the creation
22:35:41andytoshi:yeah, so this complicates analysis and i think also has consequences for fungibility of recently-valid coins
22:36:09tholenst:I am not sure i understand your problem. Do you agree this only happens if the reorg is something like 100 blocks deep?
22:36:11andytoshi:but i also suspect this is fixable while still retaining the benefits of tholenst's trickery
22:36:29andytoshi:tholenst: yeah, it'd have to be deeper than the coin's invalid-until-N-blocks count
22:36:44andytoshi:so maybe we could require all transactions which do this to have N higher than 100
22:37:12tholenst:ok, i didn't think too much about that yet.
22:37:18andytoshi:or maybe, rather than saying "invalid until 100 confirms" you say "invalid until block 300000" and hardcode the 300000
22:37:30andytoshi:then you don't care about when the tx is actually mined, so there is no concern about reorgs
22:37:55tholenst:you could do that, but then you have to renew the backing txouts periodically; I don't like that
22:38:23andytoshi:well, you'd have to do this anyway i think
22:39:03tholenst:I think it makes sense at this point if I write down the proposal in more detail.
22:39:37andytoshi:yeah, it'd be good to have something precise to discuss
22:41:05tholenst:the input was useful to me anyhow :) more to think about, ty!
22:41:21nsh:what's the distribution of reorg heights?
22:41:51nsh:any theoretical basis for calculating that, or is it near-enough empirical?
22:43:52tholenst:for a theoretical basis, you need to have some kind of clue how fast the block distributes among the miners
22:43:56andytoshi:nsh: (a) hard to make precise, as generally only part of the network perceives a reorg as a reorg, while the rest of them saw the winning chain first, (b) the big ones occur by implementation bugs, which are hard to predict, (c) the small ones probably are also due to network flukes which are also hard to predict, thought they might have a nice distribution since they're frequent
22:44:30nsh:* nsh nods
22:44:45nsh:but it should be possible to put a 100-block reorg into an improbability bracket
22:46:25tholenst:agreed, using only mild assumptions that should be possible
23:34:57andytoshi:nsh, tholenst: my expectation is that if you can get any number assuming no horrific forking bitcoind bugs, it'd be like 1/googol or something
23:35:07andytoshi:way way way lower than the chance of a serious dev mistake
23:35:19andytoshi:so that's the probability you need to estimate, and good luck with that :)
23:35:53nsh:pft, i crunch graham's number for breakfast
23:36:09andytoshi:it's higher than 1/graham's number ;)
23:36:21nsh:maybe late lunch then :)