--- Log opened Thu Sep 12 00:00:29 2013 01:16 < gmaxwell> nanotube: exactly, we're short of short on onion peers. :( 08:39 < nanotube> there seems to be a decent list on https://en.bitcoin.it/wiki/Fallback_Nodes 10:03 < gmaxwell> petertodd: https://bitcointalk.org/index.php?topic=292857.0 someone proposes a composable signature scheme based on pairing crypto. 10:05 < gmaxwell> e.g. you have a bunch of pubkeys, and values signed... and you can't tell which signed which. bonus: they seem to be claiming the aggregate is constant size. 10:06 < gmaxwell> (though they make some claim about the security model essential to the size being constant and not linear in the number of signatures which I don't understand) 11:44 < petertodd> gmaxwell: broken link 11:45 < petertodd> Sounds promising though! 11:52 < gmaxwell> petertodd: sorry, I moved around some posts: https://bitcointalk.org/index.php?topic=290971.0 11:53 < gmaxwell> In any case, you start of with a bunch of {key, message, signature} and can aggregate one way into a {N x key, N x message, signature} such that you can't tell which key signed for which message. The final signature may be constant in length. 11:53 < gmaxwell> (may because they had some security handwave I didn't follow, otherwise its linear) 14:04 < amiller> i really think i've figured out the economics of bitcoin 14:04 < amiller> it has to be unprofitable for everyone 14:06 < amiller> we have to assume it's always more efficient for large corporations to mine, because of economies of scale etc etc 14:07 < amiller> this is the underlying reason why people panic about the trend of bitcoin towards centralized mining 14:07 < amiller> and it's compelling 14:08 < amiller> if it's unprofitable for some people to mine and profitable for others, then unfortunately it's likely to be profitable only for people with the biggest investments 14:08 < amiller> but this lottery theory is totally a way around that 14:09 < amiller> the solution is basically to make it unprofitable for everyone, including the potentially enormous miners 14:10 < amiller> and in fact the motivation to participate, despite it being unprofitable, is most applicable to the small users and not to the biggest players 14:11 < jgarzik> One argument I've always made is that larger corporations, if they decide to buy into bitcoin mining, will be willing to mine even at a loss 14:11 < amiller> i think the opposite 14:11 < amiller> maybe if they have some external reason as well, like political influence i suppose? 14:12 < jgarzik> amiller, you may obtain several opportunities of ancillary value from mining 14:12 < jgarzik> amiller, mining your own transactions, slowing down your competitors, strategic value, etc. 14:12 < jgarzik> amiller, general network security, lessening dominance of others 14:13 < jgarzik> amiller, laundering (the 110% PPS case) 14:13 < amiller> i see 14:13 < amiller> that's not detrimental, it doesn't necessarily imply the winner take all case 14:13 < jgarzik> agree 14:14 < jgarzik> not trying to rebut your argument, just noting all the value that may be extracted even if the mining itself is notionally unprofitable 14:14 < amiller> sure, fair enough 14:14 < amiller> some of that almost counts as altruistic model as well, basically you've described like a bitcoin stewarding company 14:15 < amiller> it would be disconcerting if a potentially strictly-greedy newtork-ambivalent cost-cutting company could get more and more profitable just by mining and accumulating compute power 14:16 < amiller> so i'm really comfortable now with this decision theory called Cumulative Prospect Theory 14:16 < amiller> it's a generalization of the standard Expected Utility version 14:16 < amiller> EU says that no one ever participates in lotteries, CPT accounts for that 14:17 < amiller> i'm really confident now that modeling bitcoin miners as CPT-rational agents is the way to go 14:19 < amiller> it's not inherently irrational to play a lottery with -ev 14:19 < amiller> which is a nice observation because we know that people do 14:19 < amiller> what's neat is that a lot of people of ordinary wealth may be very excited about the potential of winning like $2500 by mining a block 14:20 < amiller> when the potentially reward is tuned right, basically the most amount of people will participate and the ev will drop 14:21 < amiller> yet $2500 is nothing to a big company, and they're less and less likely to get a big enough jackpot to make it worth participating 14:24 < jgarzik> not necessarily stewarding -- I was thinking to myself of an idealized "bitcoin bank", or an HSBC/Goldman bank that wants to participate with bitcoin 14:24 < jgarzik> If you want to participate in the network, there is value in helping to defend it 14:25 < jgarzik> another thought, the most dfficult problem to solve: how to compensate people for joining the network and relaying transactions 14:26 < jgarzik> otherwise we quickly degenerate into only miners running full nodes (which, admittedly, Satoshi described as an end game) 14:37 < jgarzik> amiller, compare price of hardware versus likely expected payoff 14:37 < jgarzik> amiller, it's expensive hardware for a low-payoff lottery, right now 14:38 < jgarzik> any hardware within the reach of normal people will on average produce 1 block every 10 years or so 14:38 < jgarzik> and it seems like that trend will continue 14:38 < amiller> one thing i found is that the cost is totally dominated by equipment rather than power 14:38 < amiller> it surprises me whenver i do that calculation 14:38 < jgarzik> indeed 14:39 < jgarzik> though my $300/month power bill increase was painful today :) 14:39 < jgarzik> 2x Avalon, 2x BFL 14:39 < jgarzik> (need to get that other Av back up) 14:39 < gmaxwell> petertodd: https://bitcointalk.org/index.php?topic=290971.msg3139004#msg3139004 14:39 < amiller> i'm interested in the structure of bitcoin's reward 14:39 < amiller> like if there were bigger jackpots 14:40 < amiller> perhaps sometimes you could win a thousand bitcoin bonus 14:40 < amiller> that would change the way in which people participate 14:40 < amiller> even if somehow the expected profit was fixed 14:40 < amiller> that's my point overall i guess is that i'm moving away from an expected-profit-centric analysis of the rewards 14:40 < gmaxwell> 11:19 < amiller> what's neat is that a lot of people of ordinary wealth may be very excited about the potential of winning like $2500 by mining a block 14:41 < gmaxwell> ^ doesn't explain why most people won't solo mine,— even in small amounts... even with a positive ev. :P 14:42 < gmaxwell> amiller: a significant fraction of miners think mining is a race, and that you get super linear rewards from big aggregates. "So much for rational agents" .. so perhaps thats what explains the prevailance of pooling, it doesn't seem to explain the near absense of solomining. 14:42 < gmaxwell> jgarzik: 11:25 < jgarzik> another thought, the most dfficult problem to solve: how to compensate people for joining the network and relaying transactions 14:43 < gmaxwell> So, there was just a "anonymity" proposal that resolves that as a side effect. 14:43 < amiller> gmaxwell, i have two responses, one is that it could easily be something that happens later as people learn to understand the economics better, the other is that perhaps the $2500 is even too steep and people would like to have a small chance at winning like $20 or something 14:44 < amiller> there are tons of studies on lottery design, and its' well known that lottery designs typically have lots of different prizes 14:44 < jgarzik> Explaining the near absence of solo mining: There is a rather large chance you will /never/ get paid for that noisy, loud hardware you had to fight to obtain. 14:44 < amiller> i found one paper that looks at optimal lottery design for a market of CPT agents in partiuclar, and basically concludes that an optimal lottery has a continuous prize distribution, not just finite prizes 14:44 < jgarzik> The motivation to help the network is not nearly so strong. 14:44 < amiller> bitcoin has exactly one prize 14:44 < amiller> for bigger prizes, you have to go to satoshi dice 14:44 < amiller> for smaller prizes, you have to go to satoshi dice 14:45 < gmaxwell> jgarzik: I mean back when CPU mining was still profitable (postive EV over power costs) but not very, I had basically no luck convincing now gpu miners to spin up their cpus laying around solo mining. 14:45 < amiller> bitcoin mining competes directly for the same market as satoshi dice imo, and bitcoin's reward system is suboptimally designed by not having smaller scratchoff contests (but pooled mining makes up for that a bit) or larger prizes for that matter 14:46 < gmaxwell> amiller: with pooling you can get whatever variance tradeoff you want though, up to the pool size.. and its easy to have smaller variance when someone wants to buy pure variance. 14:46 < gmaxwell> No one wants to buy my eligius shelved shares. 14:46 < jgarzik> heh 14:46 < jgarzik> that would be a neat market 14:46 < gmaxwell> amiller: and yes, I've told people to mine instead of play a gambling game. 14:46 < gmaxwell> amiller: but they don't seem to believe it, I cannot explain why. 14:46 < jgarzik> gmaxwell, I guarantee you would sell them, if there was an automated interface for trading them 14:46 < amiller> that's interesting, it's straightforward to use pooling to make a smaller variance lotto out of a larger variance one 14:47 < amiller> it's less obvious that you can make a higher variance pool 14:47 < jgarzik> gmaxwell, it's like bad debt resale. just need to proper mechanism for price discovery -- and I think bitcoin makes that pretty easy. 14:47 < gmaxwell> jgarzik: yea, thats probably the missing piece. Luke and wiz aren't eager to do that because they don't want share reassignment to be a hacking target. 14:47 < jgarzik> selling digital property is, like, ya know, a forte. :) 14:48 < gmaxwell> amiller: it's really eager to make any sort of tradeoff you want, though some tradeoffs require counterparties willing to take the opposite side of the bet. 14:48 < jgarzik> $idea: offload it. transfer all shelved shares to an agent, who holds shelved shares or transfers them depending on signed message. the agent enables trading further, or handles shelved share payouts. 14:49 < gmaxwell> amiller: e.g. you can get ~zero variance mining from me, right now. Send me your hashpower, I'll extract a — say 10%— cut and just pay you for diff 1 shares exactly what their ev is. :P 14:50 < gmaxwell> jgarzik: yep, I think wizkid himself suggested a one time transfer to a market when we discussed this (uh, in the eligius development channel about two months ago) 14:50 < amiller> gmaxwell, it's easy to make an unenforceable contract like that 14:51 < amiller> gmaxwell, essentially you can't absorb all that risk unless you have deep enough pockets 14:51 < amiller> if you go bankrupt i get nothing 14:51 < gmaxwell> amiller: yes, but I pay you frequently. 14:51 < amiller> well again it's easier in the lowering-variance directoin 14:51 < gmaxwell> There are _tons_ of PPS pools, and some have fees low enough that they are mathmatically sure to go bankrupt eventually. Yet people mine one them in large numbers. 14:51 < amiller> but you could make the same contract with higher variance 14:51 < amiller> that's what satoshidice does basically right 14:52 < amiller> you could have a dozen people win the 64k prize 14:52 < amiller> and obviously they cannot pay out 14:52 < gmaxwell> who knows about SD, after it was "sold" its traffic dropped off ~99%. I don't know that its too useful to generalize anything from it 14:52 < jgarzik> Just-Dice is freakin' awesome. Not because they killed spam by off-blockchain betting, but because of an interesting innovation: insta-investing 14:53 < jgarzik> You can become an investor, or withdraw your investment, at any time. I predict that becomes a trend. 14:53 < amiller> i'm just saying abstractly, unless it has a big amount of money in escrow, you could get 'lucky' but it wouldn't be able to pay out 14:54 < jgarzik> also RE SD: blockchain.info's TX stream sure does show a lot of BetCoin transactions, sometimes more in a time period than SD 15:03 < gmaxwell> amiller: yes, for a higher variance you'd want the party providing it to be able to show they have the funds to back it. 15:11 < Luke-Jr> jgarzik: nice, but any idea what the US laws about investing in it are? 15:12 < jgarzik> Luke-Jr, if eligius just sells it, responsibility is transferred, I would think 15:12 < Luke-Jr> jgarzik: huh? 15:12 < Luke-Jr> I was talking about the investing in Just-Dice thing 15:12 < jgarzik> Luke-Jr, oh 15:12 < gmaxwell> luke was asking about the gambling site, jeff was answering about selling shelved shares. 15:13 < jgarzik> indeed 15:13 < Luke-Jr> oh 15:13 < jgarzik> Luke-Jr, most securities laws do not seem to punish investors for investing in [possibly illegal or fraudulent] securities, IIUC 15:14 < jgarzik> they mostly aim to punish issuers 15:14 < jgarzik> I would think being an investor is OK 15:14 < jgarzik> but dooglus should have his T's crossed, and I's dotted. 15:14 < maaku> jgarzik: well, ok until your investment goes south 15:14 < jgarzik> maaku, so? 15:14 < jgarzik> maaku, SEC will not prosecute you for that. 15:14 < Luke-Jr> maaku: meh, bad investment is distinct from going to jail for investing 15:16 < jgarzik> Luke-Jr, if you scroll up, some of the earlier discussion was about creating a market for shelved shares. Enable people to sell them -- which automatically creates a market 15:16 < jgarzik> there is -some- value in there, just like selling bad debt 15:16 < Luke-Jr> jgarzik: possibly - but there's a lot of complexity to it as well :/ 15:17 < jgarzik> and people might appreciate an opportunity to get paid $now 15:18 < gmaxwell> it would make eligius a true pps pool (at some price determined by the market) 15:19 < gmaxwell> it would also enable people to "gamble" in a way that is less objectively unfair— basically just making bets on eligius' future luck but at market rates instead of against the house. 15:19 < gmaxwell> it would also encourage people to help improve eligius, since the bigger and better eligius is, the greater the odds of big luck in the future. 15:20 < gmaxwell> but shelved shares are a weird asset. I dunno how you run a market for them. 15:20 < jgarzik> IMO the main complexity is what to do with existing shelved shares, RE property ownership 15:21 < gmaxwell> jgarzik: I think some signmessage thing to assign all your addresses current and future shelved shares to address X (which would be controlled by the exchange in an exchange case) solves that. 15:22 < jgarzik> an interesting case is that each share is more valuable, the closer to the top it is 15:22 < jgarzik> maybe run a Dutch auction weekly, for shelved shares 15:22 < gmaxwell> right, valuing them is tricky, but this means that you need to actually know the index of each of them. 15:23 < jgarzik> need to package them in blocks of X shares, for sanity's sake 15:25 < gmaxwell> I don't know how bad debt is normalized and sold. I assume it would be similar. 15:37 < jgarzik> It's ranked according to various generally agreed factors, which hopefully sum up to a value that predicts how likely the debt will be repaid: debt lifetime, time since last payment, credit score of holder, ... 15:37 < jgarzik> after rank, debts are grouped together and sold in packages 15:38 < jgarzik> occasionally you will have a company just want to dump everything, and bad debt investors must pick through the garbage themselves, but usually things are a bit sorted 15:38 < jgarzik> for shelved shares, probably sell in blocks of 50,000 shares or whatnot, each indicating an index or timestamp or some other ordering position in eligius payment queue 15:39 < jgarzik> on the eligius side, I guess the main thing would be reassigning shares to new owners 15:42 < gmaxwell> amiller: did you see the link I gave peter todd above for the aggregate signature stuff. It would have some interesting implications for relay incentives. 15:42 < gmaxwell> amiller: as it would allow relayers to take transaction fees. 16:18 < K1773R> Luke-Jr: did was your pull request "child pays for parent" rejected? 16:18 < K1773R> s/did // 16:22 < gmaxwell> K1773R: you should probably be asking about this in #bitcoin-dev ... sounds like bitcoin development discussion! 16:28 < K1773R> gmaxwell: uh yea, clicked a bit below #bitcoin-dev :P 16:35 < amiller> i like this paper. 16:35 < amiller> hm 16:35 < amiller> it's the first one that treats the ledger/utxo properly imo but that's not a big point 16:36 < amiller> still don't grok the actual idea yet though 16:36 < gmaxwell> the OWAS signatures? 16:37 < gmaxwell> It's really pretty simple. the signing scheme has a Genkey() Sign() Verify() Aggregate() Aggregate takes two signatures (or prior aggregates) and does a one way composition. So at the end you have a set of {public keys} {messages} and one signature and you don't know which key signed for which message. 16:38 < gmaxwell> they propose adding it to bitcoin by having a new output type that pays to an OWAS public key. When you spend from it you reference it by blockhash : public key the reason it has to be this way is if a public key gets reused in different blocks you need to know which one you're spending. 16:40 < amiller> i think it's like incremental coinjoin 16:40 < amiller> coinjoin works but all the outputs have to be constructed before anyone signs the tx 16:40 < amiller> here you can make your signature 16:40 < amiller> then give it to someone else in a coinjoin channel and they can add their signature and now it's unlinkable as long as they forget about it 16:41 < gmaxwell> It has a number of conseqneuces.. e.g. you can make the outputs sum to less than the inputs.. and then someone on the relay path can add an output with more value than the inputs to claim that value. 16:42 < gmaxwell> amiller: yea, it's a one-way incremental coinjoin. 16:43 < gmaxwell> It also has an anti-censorship property. If a miner recieves an aggregate signature and there are some blacklisted coins, his option is to ignore the whole aggregate (and hope that he gets resent the partials before some else mines it) or take it anyways. 16:45 < amiller> i don't know, i am not sure this makes any sense 16:45 < amiller> it says that the inputs are all linked together because they're in the same wallet 16:46 < amiller> that really isnt true, coinjoin makes use of the fact that's not true, you can sign a tx if you know one of the txinputs without knowing the other keys 16:46 < amiller> nor is it the case that the output is linked to the input 16:46 < amiller> coinjoin relies on that too 16:47 < gmaxwell> Yes, this was written by someone who didn't know about CoinJoin 16:47 < amiller> the only advantage of this thing is the incrementalness and that's kind of irrelevant 16:47 < gmaxwell> As a pure anonymity tool I think this is not very helpful over coinjoin. Agreed. 16:48 < gmaxwell> it's a little helpful because its more loosly coupled. 16:48 < gmaxwell> But the anti-censorship, pro-relaying, and compression properties are potentially more interesting. 16:49 < gmaxwell> my reply points out that its not that interesting for anonymity. 16:49 < gmaxwell> "I'm glad to see someone with an aggregate signatures proposal. From an anonymity perspective, I believe a cryptographic approach is unnecessary, and they are very difficulty to deploy, but still may useful in the future." 16:52 < gmaxwell> amiller: one sort of annoying property is that in some cases this can't achieve anonymity as good as coinjoin! 16:53 < gmaxwell> E.g. all the users for this block join a coinjoin, they use a SMPC sort to distribute their requested output addresses among each other. 16:54 < gmaxwell> There is no way to achieve that level of anonymity with this one way aggregation scheme. 16:56 < gmaxwell> amiller: you could reply to that thread and point out they got the linking stuff wrong. :) 16:56 < amiller> *am already doing so* 16:58 < gmaxwell> (I didn't even notice, I'm so used to _everyone_ getting that wrong) 17:01 < jgarzik> http://io9.com/a-new-digital-world-is-emerging-thats-too-fast-for-us-1286428447 17:01 < jgarzik> The problem, however, is that this new digital environment features agents that are not only making decisions faster than we can comprehend, they are also making decisions in a way that defies traditional theories of finance. In other words, it has taken on the form of a machine ecology — one that includes virtual predators and prey. … SEXPAND 17:01 < jgarzik> Consequently, computer scientists are taking an ecological perspective by looking at the new environment in terms of a competitive population of adaptive trading agents. 17:01 < jgarzik> " 17:03 < gmaxwell> jgarzik: did you ever see the textbook on amazon that was a billion dollars? 17:04 < jgarzik> heh, saw a screenshot 17:05 < jgarzik> one of the many Themes Garzik Harps On is that computer scientists should be looking at biology for models, theories, and correlations 17:06 < jgarzik> distributed computing, especially decentralized computing, is all about organic behaviors like herds, infections and inoculations, swarms, emergent behaviors, ... 17:07 < jgarzik> Just like human beings, they stop being purely predictable engineering systems behaving within set parameters and become organic feedback systems 17:08 < jgarzik> A really fun problem is decentralized auctions, eBay-style 17:08 < jgarzik> How to fairly handle the final few seconds of a real time auction? 17:09 < jgarzik> sniping is a DoS of sorts 17:09 < gmaxwell> yea, "don't hold that kind of auction" 17:09 < gmaxwell> if you do sealed bid auctions the problem goes away. 17:09 < jgarzik> or Dutch 17:13 * jgarzik wonders the name for this style of auction: wait X duration after last bid, then close auction. if someone bids, timeout clock resets to X. 17:18 < jgarzik> How to integrate bitcoin with a sealed bid auction, in a least-trust method? Is there any way to (a) prove you will spend the funds if you are the winner while (b) not spending the failed bids? 17:18 < gmaxwell> yes, make all the bid transactions conflict a single input. Only one can make it into the blockchain. 17:18 < jgarzik> Certainly an auction robot could accept bids, then refund the losers. Any way to avoid the robot stealing the funds from the failed bids? 17:19 < jgarzik> conflict? 17:19 < gmaxwell> They all spend input X. 17:19 < gmaxwell> (and other inputs to pay for their bid) 17:19 < jgarzik> seems vulnerable to griefing 17:20 < gmaxwell> easy to fix. 17:20 < gmaxwell> (I think). 17:21 < gmaxwell> The person selling the thing has 1 BTC. You are a bidder ... you write a transaction spending that 1 BTC and he signs for it. 17:21 < jgarzik> My naive scheme: robot announces "private key for 1 satoshi is $this" to channel, and everyone writes a transaction that spends a satoshi + their auction bid input 17:21 < gmaxwell> if the signature is a SIGHASH_SINGLE then he doesn't have to see your bid. 17:21 < jgarzik> but a griefer might just spend the bitcoin outside of the loop 17:22 < jgarzik> ah, duh 17:22 < jgarzik> no need to give out the private key, just have auctioneer sign it. understood. 17:23 < jgarzik> neat 17:23 < jgarzik> auctioneer announces the anchor transaction for the auction (the input everyone spends), and people bid from there 17:26 < jgarzik> This would be a fun demo to write. A little HTTP-based auction server, modeled after bittorrent trackers. Just keep track of abstract metadata on the auction, zero content (for privacy / deniability). 17:27 < gmaxwell> now a tricker thing to do is to make it into a secure _second price_ auction.. now that I don't know how to do. :P 17:27 < gmaxwell> (thats a sealed bit auction where the highest bidder pays the next highest price) 17:29 < jgarzik> I think the "bid-extends-timeout" solves the game theory motivation to DoS in the final seconds of the auction 17:30 < jgarzik> unfortunately, IIRC, bid-extends-timeout was also used on a couple notable click-lottery "buy a plasma TV for $75!" pseudo-auction sites. 17:31 < gmaxwell> I think either sealed bids or bid extends timeout solves the dos. sealed bids also discourage self dealing. (e.g. the seller bids up the bidders to try to get them to bid more, if he accidentally wins, oh well, no biggie) 17:32 < jgarzik> petertodd, I need to get a little demo website going, that helps people timestamp their SINs 17:32 < jgarzik> for a tiny fee, of course 17:32 < jgarzik> gmaxwell, good point 17:33 < jgarzik> gmaxwell, from my reading it sounds like sealed-bid and Dutch might tend towards a slightly lower final price than eBay style 17:33 < jgarzik> so economics might pull sellers towards ebay-style / bid-extends 17:34 < jgarzik> -EFAMILY. Might write that HTTP server tonight, hmmm :) *poof* 17:34 < gmaxwell> The economics wanks will tell you that the sealed bid second price auction is the optimal thing. They even gave someone a nobel prize for it. 17:35 < gmaxwell> But since I dunno how to make a direct bitcoin one of those... simpler is probably better. :P 17:59 < gmaxwell> This stanford pairing based crypto library is pretty nice. 18:30 < gmaxwell> Okay, I've successfully got that signature scheme working. 18:51 < maaku> jgarzik: except for some minor warts ebay is a Vickrey auction, which is ideal for both buyer and seller (the proof won Vickrey the nobel prize gmaxwell alluded to) 18:56 < maaku> jgarzik: you might also be intersted in : http://www.eecs.harvard.edu/~shieber/Biblio/Papers/icec06.pdf 19:04 < gmaxwell> maaku: hm? how is ebay a vickrey auction? it's not sealed, the winner is the highest price and pays their offered price. 19:05 < nanotube> gmaxwell: nope. you can set a max bid of 1000, but you'll only pay a bit above second highest. 19:05 < nanotube> and nobody will learn what your sealed bid is, until you're outbid. 19:05 < gmaxwell> oh! of course, that proxy biding makes it effectively second price (plus bid increment) 19:05 < nanotube> so you /could/ use it as a plain second-price sealed bid auction - just post your maximum, walk away. 19:06 < nanotube> that people don't and try to snipe and crap is just how people are. :P you don't have to join them. 19:06 < gmaxwell> maaku: nanotube: thanks, I didn't realize that before. (You can tell I haven't used ebay much ever and not at all recently) 19:07 < nanotube> mm :) 19:07 < gmaxwell> okay, well, I dunno how to do that with bitcoin without a trusted party or non-trival multiparty computation. 19:07 < gmaxwell> a simple auction where people throw out bids and only one happens is easy however. 19:08 < nanotube> what's your scheme, briefly, for doing th latter 19:10 < gmaxwell> nanotube: Alice holds an auction, alice advises everyone of some bitcoin she holds and an address to pay to. You want to bid. You write a transaction spending some of your coins and alice's coin that pays to alice (and if any chance back to you). You sign it and give it to alice. 19:10 < gmaxwell> all the other bidders do the same. 19:10 < gmaxwell> When alice gets bored, she signs and announce the transaction. 19:11 < nanotube> ah, cute! and obv there's no way to force alice to sign second highest bid rather than highest.... 19:12 < gmaxwell> well you want the highest bidder to pay the second price. :P 19:12 < gmaxwell> it's easy to do with a semitrusted oracle. 19:13 < gmaxwell> e.g. Oscar the observer watches the bids and his signature is required for the auction to be completed. 19:13 < gmaxwell> and then oscar can enforce whatever rules he likes. 19:13 < nanotube> well, the good part is that theory says (as i recall) that the expected proceeds are the same from a second price or a first price auction 19:13 < gmaxwell> I though first price encouraged bidders to underbid? 19:13 < nanotube> in expectation, in a second price auction people have the incentive to bid their true value. in first price, bidders shade their bids 19:14 < nanotube> but "on average" they should produce the same outcome, price-wise 19:14 < nanotube> at least if i recall my auction reading correctly. been a while :) 19:15 < gmaxwell> deciding a winner with multiparty computation is easy, and I can point you to sofware which you should just be able to run to do that.. but getting a transaction out of it is hard. 19:15 < maaku> nanotube: no, expected proceeds are lower for a first price auction 19:15 < gmaxwell> I don't know how to do that except by computing the signature under MPC and ... uh. hope you've got a while. 19:16 < maaku> yeah, if you figure out a truly efficient way to do that, let me know so I can co-author ;) 19:16 < maaku> the link i posted is the best i've found so far, but it's still hours or days of computation for the signature 19:17 < nanotube> http://en.wikipedia.org/wiki/Vickrey_auction#Revenue_equivalence_of_the_Vickrey_auction_and_sealed_first_price_auction 19:17 < maaku> (at least verification is fast though 19:17 < gmaxwell> Someone on BCT recently linked to a paper claiming massive MPC speedups and also security against active attackers with a only one partitipant required to be honest... but it was all moonmath not something I could run so.. :P 19:18 < gmaxwell> (computing the winner is easy, you just do a sort and only output the first guy and the second price… but doing a bunch of EC group operations under MPC sounds pretty painful) 19:19 < maaku> nanotube: the equivalence only holds if all bidders are using the same strategy 19:19 < maaku> with 2nd price they would be, if they are acting rationally 19:20 < maaku> with 1st price there are many pareto optimal solutions 19:20 < maaku> if their strategies are mismatched, then the result is worse off 19:24 < nanotube> mmm 19:40 * jgarzik reads scrollback 19:41 * sipa doesn't 19:41 < jgarzik> I'll probably just do sealed bid because it's easy and clearly works with bitcoin tech 19:41 < jgarzik> should be able to do a design where the HTTP server and bitcoind are both free of private keys 19:44 < jgarzik> one of the more difficult parts isn't writing the server, but getting some usable client thingamajigger 19:45 < jgarzik> command line bitcoind is decidedly sub-optimal (as TD noted earlier, on another channel and subject) 19:45 < jgarzik> need to: add an unsigned input, add a signed input, add an output to the auction, and add one or more other outputs (change or whatever the user needs) 19:46 < gmaxwell> jgarzik: it would be really not so hard to have an advanced send tab that let you pick your outputs, then calculate/pick inputs, then sign.. and at the bottom its displaying the in-progress raw transaction. 19:46 < jgarzik> certainly I can write a JS or python tool to do that, but it's still ugly CLI and Linux-only 19:46 < gmaxwell> So you'd just use this and not hit send, but instead copy out the transaction. 19:48 < jgarzik> yep 19:48 < jgarzik> the familiar problem of building and passing around an advanced transaction 19:49 * jgarzik had once pondered a PyQt tool, that could be a companion to bitcoind, for this 19:57 < maaku> jgarzik: i'd rather have that in Bitcoin-Qt 19:58 < gmaxwell> maaku: some advanced things really want a python interpeter. 19:58 < jgarzik> maaku, it would be nice in Bitcoin-Qt… but there is not necessarily a requirement to tie it tightly to the ref client 19:58 < jgarzik> having an external tool to sign transactions is nice 19:59 < jgarzik> (as I've seen with the command line txtool) 19:59 < gmaxwell> the one challenge with have an external tool is that you need to fetch the inputs to sign for them. 20:00 < gmaxwell> and so this basically requires something have access to the utxo set. 20:43 < petertodd> jgarzik: how do you intend for the timestamping to work? 21:09 < jgarzik> petertodd, to satisfy the SIN protocol, you may provide your MPK (hash of public key) to a third party provider, who timestamps the MPK into the chain in the specified manner 21:09 < jgarzik> petertodd, or do it yourself 21:09 < petertodd> jgarzik: what's the specified manner? 21:10 < jgarzik> petertodd, https://en.bitcoin.it/wiki/Identity_protocol_v1 21:10 < jgarzik> petertodd, announce/commit sacrifice 21:10 < petertodd> jgarzik: ah, so not just a timestamp then 21:11 < jgarzik> petertodd, "timestamp" was shorthand, sorry 21:12 < petertodd> jgarzik: so basically, what you really need is just a little script that creates a new address, and when sufficient funds are deposited makes the sacrifice, and has some mechanism to give you back the sacrifice data (email even?) 21:13 < jgarzik> txtool will handle the DIY part 21:13 < jgarzik> a website will work for the lazy 21:14 < petertodd> yup 21:24 < jgarzik> gmaxwell, I suppose a best-practice would be for bids to set nlocktime to auction expiration time 21:25 < jgarzik> and the tool should create a refund transaction (double-spend) at the same time it creates the bid transaction 21:25 < jgarzik> perhaps setting nlocktime=$expiration+30 minutes 21:25 < gmaxwell> jgarzik: I wondered about that but I actually think it doesn't matter. If you bid and the seller wants to accept a bid and close the auction early, the winning bidder surely doesn't mind 21:26 < jgarzik> true 21:26 < jgarzik> seems like an option people might want, for added fairness 21:38 < gmaxwell> sipa: I'm mildly excited about this pairing crypto aggregate signature idea. Not because of the anonymity stuff, but because it makes scalable relay fees viable. and can also reduce transaction sizes in the non-anonymous case. 21:45 < gmaxwell> (or even in the anonymous case when there are more inputs than outputs: basically this thing requires one pubkey per input (duh), one pubkey per anonymous (or added by a relayer) output, and one shared signature for the whole block. (and each of these are just of field element each, e.g. 256 bits) 21:45 < gavinandresen> gmaxwell: link? 21:46 < sipa> gmaxwell: i don't know anything about pairing crypto or what you're talking about 21:46 < gmaxwell> gavinandresen: They propose it as an anonymity thing, https://bitcointalk.org/index.php?topic=290971.0 21:48 < gmaxwell> sipa: signature algorithim that allows one way aggregation of signatures. e.g. {message1,key1,sig1} + {message2,key2,sig2} -> {{message1,key1},{message2,key2},agg sig} and they show how to use it to unlink inputs and outputs for privacy. 21:48 < gavinandresen> I'll always be interested in ways of making transactions smaller. 21:48 < gmaxwell> I say: the privacy use is not as exciting (coinjoin is sufficient): but this thing also gives you the ability to pay relayers, the ability to make blocks smaller, and a bit of anti-censorship. 21:49 < gmaxwell> (Anti-censorship because if someone has combined some transactions and gives them to you combined you can't uncombine them to only mine one) 21:53 < gmaxwell> But yea, I dunno much about pairing crypto. 22:25 < jgarzik> OK 22:26 < jgarzik> Decentralized auction protocol (json-rpc): https://gist.github.com/jgarzik/6546194 22:26 < jgarzik> Well, the protocol itself is not decentralized; it is decentralized in the sense that anyone may set up a server 22:28 < jgarzik> each bidder provides a common, unsigned input, guaranteeing that only one transaction in the auction will be valid 22:28 < jgarzik> inside their bid 22:28 < jgarzik> protocol users must be able to grok hex-encoded bitcoin transactions and txout's 22:30 < jgarzik> bitcoin addresses are used for identity 22:30 < jgarzik> (hopefully that gets migrated to SIN) --- Log closed Fri Sep 13 00:00:32 2013