| 00:20:27 | amiller: | yeah all that's correct |
| 00:21:54 | petertodd: | amiller: how long do the proofs take to generate? |
| 00:22:06 | petertodd: | amiller: (I mean, with your best implementation?) |
| 00:22:21 | amiller: | petertodd, there is a "cheap plaintext" option that takes no time at all to produce |
| 00:22:33 | petertodd: | amiller: sure, I mean the non-plaintext version |
| 00:22:35 | amiller: | honest, hardworking, salt of the earth solo miners can take that route |
| 00:22:47 | amiller: | the best score i got (using Pinocchio, mind you) is 7 minutes |
| 00:23:09 | amiller: | that's assuming a lot of parallel power, we called it $45 in ec2 credit |
| 00:23:29 | petertodd: | hmm, I was thinking about the feasibility of, say, implementing it on dogecoin given that doge has succesfully hardforked multiple times, and the community might be right for it... but 7 minutes is >> their 1 minute block time |
| 00:23:57 | petertodd: | damn, how parallel is that?! |
| 00:24:27 | amiller: | 120x |
| 00:25:18 | petertodd: | adding a varience reduction mechanism is probably more plausible :) |
| 00:25:52 | amiller: | well you need both |
| 00:26:03 | amiller: | also the snark version is really only important for discouraging hosted minig |
| 00:26:03 | petertodd: | well, I mean just adding it |
| 00:26:28 | amiller: | the simpler "weak non-outsourceable" version is already a good way of making pools impractical |
| 00:26:40 | petertodd: | well, I suspect pools would just start asking for deposits - you do need the privacy |
| 00:27:30 | amiller: | yeah it's a good point |
| 00:27:33 | petertodd: | you should also have the snark-using blocks give some small additional reward to the next miner building on them to give an incentive to not just mine on top of the first block seen |
| 00:28:29 | petertodd: | (actually, that doesn't need to be an explicit part of the protocol if coinbase outputs can be spent immediately) |
| 00:33:47 | todays_tomorrow: | todays_tomorrow has left #bitcoin-wizards |
| 00:35:54 | andytoshi: | are there plausible variance reduction mechanisms? |
| 00:37:35 | petertodd: | andytoshi: well, p2pool does it, treechains does it as a sideeffect - I'm sure they exist, although there may be some edge cases where you can mine invalid blocks and get credit for it - not sure if that's actually much of an issue though |
| 00:37:52 | amiller: | i'm starting to worry that they might be incompatible with this long delay problem |
| 00:38:17 | petertodd: | amiller: long delay? |
| 00:38:23 | amiller: | if you can incrementally build on top of small work, but there's a significant delay needed to make the zero knowledge proof, then people will have moved on |
| 00:39:11 | andytoshi: | sure, p2pool does it, but its scalability is limited so you need to be able to add an indefinite number of p2pools..can you create a PoW which supports that but where people are somehow forced to use p2pools? |
| 00:39:23 | petertodd: | amiller: oh, see, I was thinking for varience reduction it should be enough to just give out rewards to people who have proven they computed some share at some subdifficulty (obvs timestamped) |
| 00:39:24 | andytoshi: | i like treechains, though i don't have a concrete idea of what the incentives will look like |
| 00:39:37 | amiller: | i see |
| 00:39:40 | amiller: | yeah that could be, why not |
| 00:39:48 | petertodd: | andytoshi: treechains is really bizzare re: incentives, because multiple incentive systems can exist simultaneously on it |
| 00:40:20 | petertodd: | amiller: what's interesting there is it can be done as a soft-fork by forcing the coinbase txouts to be anyone-can-spends, where you spend them by providing those proofs |
| 00:41:40 | andytoshi: | with this ghash scenario we have this weird situation where people are applying zero thought to mining and donating hashpower to the first google result. so what i'd like to think about is, can you design a system where it's not sensible to blindly donate hashpower like this |
| 00:42:38 | andytoshi: | dropping variance by having a treechain system where every subchain has the same rules might be worth thinking about |
| 00:43:11 | petertodd: | andytoshi: yeah, but remember, that means the coins being created in the subchains have to be valuable - not a trivial prospect |
| 00:44:48 | andytoshi: | iirc your original treechain proposal had every txout landing in a different random sidechain, so the effect of the sidechains was to shard the PoW but not do anything else from a user's perspective |
| 00:45:25 | andytoshi: | the PoW difficulty on each chain would naturally equalize so they should all have equal value |
| 00:45:28 | petertodd: | amiller: so, the fundemental issues to solve with the share redemption scheme are the exact same issues threatening p2pool: a) how to handle fees, b) how to handle freeloaders who don't actually have a copy of the blockchain |
| 00:45:47 | amiller: | copy of the blockchain seems way less relevant |
| 00:46:07 | petertodd: | amiller: well, by that I mean if you can do work and get a share, why should you bother validating? |
| 00:46:50 | amiller: | yeah it's not a bad goal |
| 00:46:53 | petertodd: | andytoshi: and actually a stronger version of treechains is to force PoW to equalize by restricting what subchains can be made in what sequence, IE, right, left, right, left etc. |
| 00:47:40 | petertodd: | amiller: I suspect a SPV p2pool client could be the end of p2pool, equally any attempts to discourage doublespending by block blacklisting/coinbase reallocation |
| 00:48:30 | amiller: | yeah sure i agree i can easily imagine a case where all of these things are eventually exploited by lazy people |
| 00:48:40 | amiller: | the mining system is basically the main carrot we have to steer this kind of decision |
| 00:48:59 | petertodd: | exactly, and not having to run a node is a pretty big incentive. |
| 00:49:24 | petertodd: | if you tie PoW to chain data posession it's not so bad, but then proving shares becomes harder/larger |
| 00:52:58 | amiller: | s/chain/utxo/ in my opinion |
| 00:53:35 | amiller: | i don't know if i can combine utxo posession proofs AND the nonoutsourceable snark efficiently enough |
| 00:53:46 | amiller: | maybe libsnark fixes all of this AND has room to spare for like the 1 minute thing etc |
| 00:54:28 | petertodd: | amiller: we need limits on utxo growth though, so if it is prove utxo posession we need an expiry mechanism (with a txo commitments fallback so old stuff still can be spent) |
| 00:54:57 | amiller: | ok well we need that separately |
| 00:55:24 | petertodd: | it's a pity the subsidy declines to zero in the long run, or you could just make the snark option earn you less subsidy and not include a chain data proof |
| 00:55:39 | amiller: | i worked on this storage rental fee idea but couldn't figure out how to set the parameters automatically (though, at the moment, whining about magic global parameters has become less and less of a relevant concern to me) |
| 00:56:03 | petertodd: | oh, utxo space rental? |
| 00:57:46 | amiller: | yeah, we've talked about this before btw, if miners have to be prepared to check that utxos haven't already been spent, then the users who need those utxos should pay for the time * size of this data |
| 00:58:05 | amiller: | on the other hand if you use Merkle Mountain Range I'm all but convinced that miners don't actually need to store all this data so ymmv |
| 00:58:09 | Eliel: | petertodd: I don't think it's so much the resource usage of the full node that bothers people but more the trouble needed to get it running. For example, the wait time and such. |
| 00:58:28 | petertodd: | well I was thinking you'd have a fixed size utxo set, expire old stuff, and then the extra cost to spend a really old txo is just the extra bytes needed to prove it exists |
| 00:58:50 | petertodd: | Eliel: this is -wizards - we want designs that work even if the resource usage matters |
| 00:59:05 | andytoshi: | so you'd have something like a merkle root of all utxos, then a fixed-size "live utxos" set |
| 00:59:07 | andytoshi: | ? |
| 00:59:13 | petertodd: | Eliel: I'm also very skeptical that you're right there, at least if the alternative is no resource usage |
| 00:59:30 | petertodd: | andytoshi: a merkle root of all *txos*, and a live utxos set |
| 01:00:08 | andytoshi: | petertodd: ok, awesome, i had a similar idea independently when i was thinking about bytecoin scalability so (i think) i know what you're saying |
| 01:00:40 | maaku: | amiller: you have to get proving times down to <5s to be viable imho |
| 01:00:49 | amiller: | sheesh ok |
| 01:01:06 | amiller: | maaku, how many thosuands of cpu cores will you let me get away iwth??!! |
| 01:01:11 | maaku: | 1 |
| 01:01:11 | petertodd: | andytoshi: nice! an interesting question there is if a committed utxo set is actually a good thing or not - maybe it's not? you might be better off if the live utxo is something you have to get x GB worth of blocks to calculate |
| 01:01:14 | maaku: | 1 cpu core |
| 01:01:27 | maaku: | and maybe a low-end gpu |
| 01:01:54 | amiller: | maaku, well fuck that i'll be dead by then |
| 01:02:08 | amiller: | maaku, why so poor? |
| 01:02:09 | amiller: | i mean, |
| 01:02:15 | petertodd: | I'm not convinced at all that proving times have to be all that low for the idea to be valuable. For instance, even on doge if proving is 10minutes and block intervals are 1m you're still ripping off pools some % of the time |
| 01:02:20 | gmaxwell: | I don't agree that it needs to be quite that fast. |
| 01:02:33 | amiller: | maaku, petertodd if you can put up a "deposit" it would have to be on the order of 25btc. |
| 01:02:49 | amiller: | so i think the cost of the proof should be judged as proportional to that in some way |
| 01:02:57 | andytoshi: | petertodd: my feeling is that we could get away with a MMR of txos, and a MMR of spent txos, so to prove a txo exists you provide a merkle path in the txo-MMR and to prove it's unspent you check the merkle path *isn't* the spent-MMR. the point of the live-utxo set (a) optimization and (b) have something bounded we can force miners to have |
| 01:03:29 | petertodd: | amiller: well, specifically re: deposits, said deposit could be tied to real-world legal threats, which would be Really Bad™ |
| 01:03:36 | amiller: | to serve as a deterrent for cloud mining (which no one here is prepared to let me claim is solved for a whole host of reasons:) it's only important that a cloud provider can produce that proof quckly |
| 01:03:58 | amiller: | petertodd, yeah ok decent point |
| 01:04:04 | maaku: | amiller: every added second is money-losing |
| 01:04:09 | maaku: | and every added core is centralizing |
| 01:04:20 | petertodd: | andytoshi: why the two trees rather than a tree that you modify on the fly? |
| 01:04:24 | andytoshi: | in bytecoin you can't identify directly when a utxo is spent, you have a "key image" which will be repeated in case of double spends, so you're forced into such a design (a txo MMR and a key image MMR which represents spent coins) |
| 01:04:29 | amiller: | petertodd, i'm imagining now the threat consists of like 20 large miners that still join a big pool to be jerks, but they conference with each other in the bahamas every so often and do due diligence on each other, not sure what to do about that |
| 01:04:46 | petertodd: | maaku: there's a non-snark "fast past" - the snarks are only the "anti-pool" option |
| 01:04:54 | amiller: | maaku, this is not relevant for "solo miners" who get a free pass |
| 01:04:57 | amiller: | a cheap plaintext option |
| 01:05:11 | andytoshi: | petertodd: (a) because i'm still thinking in bytecoin, (b) i thought we were further along in getting efficient NIZKs for append-only structures |
| 01:05:29 | maaku: | amiller: "a cheap plaintext option"? |
| 01:05:39 | petertodd: | amiller: yeah, it'd be better if there was no plaintext option, so soft-forking away the non-plaintext version isn't feasible |
| 01:05:53 | maaku: | if it's optional then no one will use it |
| 01:06:08 | amiller: | maaku, you would use it if you were on a pool, and using it let you get lucky and steal 25btc! |
| 01:06:22 | amiller: | maybe people would be so pessimistic they'd ever get that opportunity they wouldn't prepare for it. |
| 01:06:24 | petertodd: | andytoshi: I'm not sure modify-in-place semi-append-only isn't NIZK compatible |
| 01:06:29 | amiller: | some would |
| 01:06:29 | gmaxwell: | I was thinking of that and thinking you could twiddle incentives a bit to make it so some fraction of the blocks were theft blocks. |
| 01:06:57 | gmaxwell: | but if no one ever does then its clear enough to everyone that no one is. |
| 01:07:00 | petertodd: | gmaxwell: making theft blocks have a higher subsidy is a good option... but that's an economic change |
| 01:07:14 | maaku: | amiller: so the point is to kill pools but not actually use the ZKP version in production? |
| 01:07:28 | gmaxwell: | it being an economic change is probably not the biggest issue. |
| 01:07:31 | petertodd: | maaku: no, the ZKP has to be "production" if it's going to actually kill pools |
| 01:07:49 | maaku: | petertodd: i get that. i meant "in practice" |
| 01:07:50 | amiller: | maaku, if by "in production" you mean, "most of the time" then yeah, it would have to always be active and well tested (hence wanting to ensure that at least occasiaionlly there's a hteft block out there) |
| 01:08:28 | gmaxwell: | yea, if it's the protocol but basically never used... (1) won't scare almost anyone until it is, and (2) its trivial to soft fork out. |
| 01:09:13 | gmaxwell: | It still may be trivial to soft fork out— e.g. if pools control >50% of the hashpower, then why wouldn't they just ignore zk blocks entirely. "They're a dos attack on the network, they deny transactions." |
| 01:09:38 | petertodd: | gmaxwell: deeply ugly when the likes of ghash.io have >25% of actual hashing power in their hands... |
| 01:09:44 | amiller: | that's pretty interesting, not the slightest bit addessed by any of my definitions... |
| 01:10:13 | maaku: | probably >85% of current hashpower would go for a soft-fork ignoring the theft blocks |
| 01:10:39 | petertodd: | maaku: hence my comments about why it'll take a crash to zero for *any* of this stuff to get implemented in Bitcoin |
| 01:10:47 | maaku: | amiller: I assumed earlier that this would be the *required* form of pow, since as noted, it's trivially soft-fork ignorable |
| 01:11:00 | gmaxwell: | maaku: sort of circularly: if >50% is at some place which can be identified as having >50% therefor they'd be opposed to this. :P |
| 01:11:14 | gmaxwell: | maaku: it can't be, or you can't process transactions. |
| 01:11:19 | maaku: | hence, needs to be <5s on 1-2 cores or gpu to keep pow progress free |
| 01:11:21 | gmaxwell: | otherwise the transactions could watermark users. |
| 01:11:28 | amiller: | that's damned interesting and i have no idea how to prevent block discouragement / soft-fork attempts :p |
| 01:11:36 | amiller: | a stegonographic zero-knowledge proof or something |
| 01:11:53 | amiller: | gmaxwell, you can add transactions *after* finding the solution |
| 01:11:54 | petertodd: | maaku: well, if it keeps pools from forming, it may be a stable equilibrium with everyone's incentives being to keep the mechanism working (remember, we can make those blocks pay more) |
| 01:11:57 | amiller: | theft blocks still can contain transactions |
| 01:12:28 | gmaxwell: | amiller: they can't confirm them, however, because you can 'costlessly' replace a chain with theft blocks with alternative theft blocks. |
| 01:12:45 | amiller: | gmaxwell, i don't see what difference that makes |
| 01:12:51 | petertodd: | amiller: interesting to think about in relation to replace-by-fee scorched-earth... |
| 01:12:55 | amiller: | gmaxwell, think of this as adding 1 to the confirmation time everywhere |
| 01:13:20 | gmaxwell: | amiller: until your pool asks every user to work on a different height 1 fork. |
| 01:13:23 | gmaxwell: | :P |
| 01:13:40 | petertodd: | amiller: well, if every block was a theft block and the hidden nonces leak it's not unlike proof-of-stake's failure modes... |
| 01:13:58 | amiller: | yeah yeah that's a good point and not captured by any of my formal definitions unfortunately.... at least that can only happen if the pool is already in dominance, so.... hopefully this is a stable equilibrium with small pools |
| 01:14:09 | petertodd: | amiller: oh wait, that was a dumb statement I think because it's prevblockhash... |
| 01:15:44 | andytoshi: | gmaxwell: what is your concern re watermarking? |
| 01:15:45 | petertodd: | amiller: you know, an interesting option might be to build this into a zerocash chain and release as an alt-currency |
| 01:15:59 | andytoshi: | that a pool would boot people out after the fact? |
| 01:16:33 | amiller: | petertodd, yeah i'm... ambivalent about that idea but it may be a decent way to proceed anyway |
| 01:18:16 | petertodd: | amiller: socially I think it has a chance of working (modulo the usual 51% attacks at birth) also it'd put all the dependency on SNARKS in one place |
| 01:19:06 | amiller: | petertodd, interesting point |
| 01:19:11 | gmaxwell: | andytoshi: you can have your work watermarked by anything you must commit to in advance. |
| 01:19:16 | amiller: | break the snark, win a fabulous prize |
| 01:19:44 | gmaxwell: | andytoshi: and for your work to be a signature-of-hashpower at all you must precommit to the things your hashpower is signing. |
| 01:19:52 | petertodd: | amiller: that'd be a hilarious use of 2-way-pegs: break the security on the chain and you can collect a big whack of pegged funds |
| 01:20:28 | petertodd: | gmaxwell: your hashing power can be signing the previous history only, rather than the block you are adding to that history |
| 01:21:03 | gmaxwell: | yes, thats correct, but now I'm the pool and I give every miner distinct work. (e.g. a distinct prev, utilizing the power to rebind transactions) |
| 01:21:41 | petertodd: | gmaxwell: that's fine so long as the previous block is a plaintext one (or one the pool didn't find...) |
| 01:21:45 | gmaxwell: | so it isn't quite as simple as "adds an extra confirm to the requirements" |
| 01:22:00 | gmaxwell: | petertodd: the context above as having no plaintext blocks. |
| 01:22:04 | petertodd: | which actually means a plausible option is to force plaintext/non-plaintext |
| 01:22:10 | petertodd: | gmaxwell: ah, yeah, that's an issue |
| 01:22:36 | amiller: | or blocks the pool didn't win.... if a non malleable snark is used which isn't so hard |
| 01:22:58 | gmaxwell: | the GGPR'12 snark is super-super malleable. |
| 01:23:02 | amiller: | it's not eaxctly "non-malleable" so i'm not sure whether anything rigorously says you cna't do that, but maybe you can't do it |
| 01:23:40 | amiller: | yeah |
| 01:24:05 | gmaxwell: | (the proof of zero knoweldge requires it to be malleable, in fact.. and anyone can rerandomize it.. but even ignoring that, you could always change transactions if your pool solved the prior block) |
| 01:24:26 | amiller: | yes |
| 01:24:44 | amiller: | so pools could discourage defectin whenever they're on a streak |
| 01:24:45 | gmaxwell: | which sounds kinda like a everyone use one pool advantage there. :P "This one can enforce the pooling without risk of theft more often"). I dunno how much this matters, its a corner case of a corner case. |
| 01:25:07 | amiller: | it's kinda all corner cases out here :) |
| 01:25:34 | maaku: | so this also allows rewriting history for as far back as you've managed to get consecutive blocks |
| 01:25:45 | petertodd: | amiller: it's not a spherical cow, it's a dodecahedron cow |
| 01:25:52 | maaku: | so you can opportunistically do finney attacks once you get 6 blocks in a row |
| 01:26:16 | amiller: | it's a hypercow with a semi-trusted dodecacow that's turned into sausage after setup |
| 01:26:17 | petertodd: | maaku: not if you require work to commit to the hash of the previous block in plaintext |
| 01:26:30 | maaku: | ah ok so just 1 block |
| 01:26:50 | petertodd: | amiller: I think I'll just eat it rather than watch the How It's Made! episode... |
| 01:26:52 | amiller: | yes only adds one block, still no more advntage to an attacker after that, even if they have a straek |
| 01:28:36 | gmaxwell: | if you keep working on it it'll be a rhombicuboctahedron-cow. |
| 01:29:08 | petertodd: | amiller: you know a pragmatic watermarking issue is simply timing, if I'm the pool and you gave me the winning share first, I can make a pretty good guess that you were the block thief |
| 01:29:23 | petertodd: | gmaxwell: if we add enough corner cases it'll approximate a spherical cow! |
| 01:30:50 | amiller: | petertodd, yeah so another subtlety entirely glossed over by my formalism, is that a defecting pool member, you can "steal" a solution and also submit the solution to the pool, in which case its a race |
| 01:31:00 | amiller: | if you think you can get away with it, you might not send it to the pool |
| 01:31:19 | amiller: | but if the pool double-checks all the work it sent to miners around the time of a winning block, you can get found out (and then prosecuted and beheaded i guess) |
| 01:31:59 | petertodd: | amiller: right, so basically one way to think about it is you need to be able to get away with block withholding attacks |
| 01:32:12 | amiller: | at least this provides a pretty good incentive to do so |
| 01:32:43 | amiller: | if the pool is *too* aggressive in enforcing this, it would be easy for an altruistic vigilante somewhere else to frame pool members |
| 01:33:29 | petertodd: | amiller: hmm, explain about how that works? |
| 01:34:25 | amiller: | what the puzzle (and indeed my formal but shitty definition guarantees) is that a stolen block is indistinguishable from a block that a solominer creates separately and "steals from himself" |
| 01:35:22 | petertodd: | right, so the alturistic vigilante frames people by not releasing plaintext? |
| 01:35:23 | amiller: | so... maybe this doesn't work as well as i wnated... what i had in mind was you could wait till the pool finds a solution and then release the stolen block, it wouldn't win the race then though |
| 01:35:45 | amiller: | i guess basically the vigilante just release zero-knowledge blocks and hopes for the best. |
| 01:36:12 | petertodd: | yeah, every zk block released is a potential false-positive for the pools - yet another reason to incentivize them |
| 01:36:19 | amiller: | right exactly |
| 01:36:49 | amiller: | it'd be better if pool members were afriad they'd get 'picked off' and victimized by this vigilante character but i guess there's no good way to do that |
| 01:36:56 | amiller: | so general false positives is the best i can say |
| 01:37:09 | petertodd: | yeah, uncertainty about the running time of the zk-proof solvers will help |
| 03:05:25 | maaku: | maaku is now known as Guest41141 |
| 03:07:45 | Guest41141: | Guest41141 is now known as maaku |
| 04:02:41 | wallet421: | wallet421 is now known as wallet42 |
| 05:41:56 | justanotheruser: | justanotheruser is now known as justanotheruser2 |
| 05:42:20 | justanotheruser2: | justanotheruser2 is now known as justanotheruser3 |
| 05:42:44 | justanotheruser3: | justanotheruser3 is now known as pikman |
| 05:43:07 | pikman: | pikman is now known as justanotheruser |
| 06:20:27 | maaku: | gmaxwell amiller: the zkp setup considered for non-outsourcable puzzles involves trusted setup / CRS parameters, right? |
| 06:20:42 | maaku: | and the person holding these parameters is able to mint blocks on demand, no? |
| 06:21:31 | gmaxwell: | yep |
| 06:22:03 | maaku: | k just making sure i'm not crazy |
| 06:22:39 | gmaxwell: | well I wouldn't go that far! |
| 06:24:08 | maaku: | well if i can fake the proof and not have to reveal the nonce & inner merkleroot, then that's all i need right? |
| 06:29:58 | gmaxwell: | right, no no I meant, concluding that you weren't crazy. :) |
| 06:31:53 | maaku: | ah ok |
| 07:25:34 | sl01: | richard dickie george giving backstory on dual ec drbg and claiming no backdoors in it -- http://vimeo.com/97891042#t=30m20s and http://vimeo.com/97891042#t=57m50s |
| 07:49:31 | Vitalik_: | Vitalik_ is now known as Vitalik__ |
| 08:33:13 | tomaw: | [Global Notice] Hi all. I need to reroute some servers after that split otherwise we'll see significant lag across the network. |
| 12:47:32 | Eliel: | isn't there some way to somehow set the zkp parameters so that no-one knows the dangerous private parameters? |
| 12:47:57 | Eliel: | ... that is, a way prove it I suppose. |
| 13:56:47 | michagogo: | Eliel: take a bunch of computer components out to the middle of the desert, film yourself building a computer, installing the OS, generating the parameters, and exporting the public parameters |
| 13:57:07 | michagogo: | And then pointing a blowtorch at the whole setup |
| 13:58:59 | michagogo: | Not sure how you prove the integrity of the software, though |
| 14:00:11 | helo: | a wink and nod suffices iirc |
| 14:05:01 | michagogo: | ;;google spherical cow |
| 14:05:01 | gribble: | Spherical cow - Wikipedia, the free encyclopedia: ; Consider a Spherical Cow: John Harte: 9780935702583: Amazon ...: ; What is up with the spherical cow? | Science Blogs | WIRED: |
| 17:44:14 | maaku: | michagogo: then generate a separate set of parameters and edit the video to show those |
| 17:44:47 | michagogo: | livestream it? |
| 17:44:50 | michagogo: | *shrug* |
| 17:45:13 | maaku: | Eliel: there are multi-party compute schemes, but this is orders of magnitude more complex than anything that has ever been run |
| 17:45:56 | maaku: | typical systems today are doing things like adding two integers in a multi-compute environment. this necessitates running giant pairing crypto operations |
| 17:46:43 | Eliel: | does that mean it's significantly more difficult to create a program for doing it? |
| 17:47:53 | maaku: | yes, with significantly more difficult meaning 'tying up an entire google data center for months' level of difficulty (rough numbers, but probably that order of magnitude) |
| 17:48:44 | maaku: | and anyway, the security of the MPC system itself is built on the same technology, meaning it has the same limitation -- whoever setup the MPC has access to a key that lets them cheat that setup |
| 17:48:52 | maaku: | it's turtles all the way down |
| 17:49:23 | Guyver2: | Guyver2 has left #bitcoin-wizards |
| 17:52:57 | Eliel: | maaku: hmmh, entire google datacenter for months... that means anyone can do it in about 10 years then ;) |
| 18:01:41 | zooko: | zooko has left #bitcoin-wizards |
| 18:01:43 | nsh: | in 10 years, we'll be working for the google datacenter, not the other way around |
| 18:13:22 | jtimon_: | andytoshi I find your idea of committed TXO + STXO very interesting |
| 18:13:22 | jtimon_: | Seems more interesting to me than a TXO + UTXO-with-expiry, since this way you can always have an SPV proof of ownership with the current block |
| 18:15:55 | jtimon_: | maaku petertodd disadvantages of TXO + STXO over TXO + UTXO ? |
| 18:17:19 | andytoshi: | jtimon_: you could do TXO + STXO + UTXO-with-expiry, where the expiry set is used to avoid the requirement of giving a whole merkle path into the TXO set for 'live' coins |
| 18:18:10 | andytoshi: | (i think) the only disadvantage is that with TXO + STXO, both sets are unbounded, so you can't assume anyone has the whole thing, so you need to provide merkle paths which are big |
| 18:18:26 | jtimon_: | I feel kind of lost on the anti-pool conversation, but sometimes comes to mind that some kind of protocol-enforced p2pool should make double-spends easier to predict due to the pertial proofs |
| 18:19:22 | maaku: | STXO? |
| 18:19:27 | andytoshi: | it's tough to achieve consensus on partial proofs for the usual jacking-up-the-blockrate reasons.. more stales, potential failure to converge |
| 18:20:04 | andytoshi: | maaku: "spent TXO", a merkle tree where you look up a txo (or key image in the case of bytecoin) and confirm it's -not- present to detect double-spends |
| 18:20:33 | jtimon_: | andytoshi I don't see why that would be a disadvantage, everybody should keep his own TXO proofs, if there's no TXO full centralized archives... |
| 18:20:48 | maaku: | that changes semantics of bitcoin in the case of a hash collision |
| 18:21:24 | maaku: | which is more of an fyi |
| 18:21:44 | jtimon_: | when a miner relays a block it relays all the proofs he needs to provide for the transactions, so he may expect them from the tx he considers to include |
| 18:22:13 | andytoshi: | jtimon_: right, but that makes transactions a fair bit bigger, today you just need a single hash to reference a utxo and it's assumed every validator has the full set available to do lookups |
| 18:22:35 | maaku: | andytoshi: we're going that direction irregardless |
| 18:22:39 | jtimon_: | I'm not sure the expired-UTXO has enough value if you already have TXO + STXO |
| 18:22:42 | maaku: | (storageless mining) |
| 18:23:51 | maaku: | jtimon_: I'm not sure why you need TXO + STXO |
| 18:23:53 | jtimon_: | andytoshi, the additional proofs aren't really part of the transaction, a miner with the full UTXO doesn't need them, only a stateless miner |
| 18:23:54 | maaku: | TXO is STXO |
| 18:24:17 | jtimon_: | STXO is included in TXO |
| 18:24:35 | jtimon_: | TXO - STXO = UTXO |
| 18:25:02 | andytoshi: | maaku: the reason i came up with TXO + STXO was for a bytecoin-style system where you have "key images" which uniquely specify TXOs but the mapping is not computable (this is how they prevent double-spends while anonymizing which utxos are being used) |
| 18:25:35 | jtimon_: | because that way you can produce SPV proofs equivalent of having a commited UTXO |
| 18:25:35 | andytoshi: | but it happens to involve both data structures being append-only, which might simplify our lives even if we don't have that problem |
| 18:25:41 | maaku: | STXO sounds like the worst aspects of both -- an ever growing data set which you need random access to |
| 18:26:34 | jtimon_: | why should the STXO data structure be any different from TXO's? |
| 18:26:51 | andytoshi: | you don't need random access, you just need a proof that your own TXOs are in the TXO-set and not in the STXO-set |
| 18:27:19 | maaku: | jtimon_: basically the only tradeoff with TXO vs UTXO is (1) TXO doesn't need storage of the data at all to create new outputs, UTXO does, (2) TXO does not support query-by-hash, UTXO does |
| 18:27:49 | jtimon_: | so here you don't have commited UTXO |
| 18:28:07 | maaku: | jtimon_: commited STXO has all the same bad tradeoffs |
| 18:28:13 | maaku: | with none of the upside |
| 18:28:19 | jtimon_: | (1) STXO doesn't need storage of the data at all to create new outputs |
| 18:28:41 | jtimon_: | so how do you query the TXO ? |
| 18:28:43 | maaku: | jtimon_: what are you ordering by? |
| 18:28:52 | maaku: | insertion order? then you are talking about TXO |
| 18:29:20 | jtimon_: | yes, STXO, would be almost identical to TXO, just lacking the unspend outputs |
| 18:29:45 | maaku: | that's useless |
| 18:30:15 | maaku: | to know double-spend status you need to lookup by txid, or have all txouts |
| 18:31:11 | jtimon_: | now you can proof that output X is unspent on block H, just with block H's root |
| 18:31:12 | jtimon_: | Can you do that only with TXO? |
| 18:31:31 | andytoshi: | oh derp, i had thought merkle tries would let you do this without any storage but ofc not.. |
| 18:33:19 | jtimon_: | in the same way that a miner holding only the hash of the TXO can mine if additional proofs are provided to him, an SPV user can be proven his balance at a given block |
| 18:33:24 | gmaxwell: | STXO has an advantage that it also works nicely for anonymous transaction systems. |
| 18:34:12 | jtimon_: | is that useless? |
| 18:34:19 | andytoshi: | ( http://himalia.it.jyu.fi/ffdoc/fenfire/dartboard/merkle_has_tries--benja/idea.gen.html for merkle tries btw) |
| 18:35:58 | andytoshi: | jtimon_: you can create proofs of nonexistence that require no STXO storage to verify, but to create them basically requires random access to the whole STXO set |
| 18:37:43 | jtimon_: | not really, in the same sense that you don't need random access to the TXO, nor a single person storing the whole chain |
| 18:38:26 | jtimon_: | people should keep their parts of the TXO trie but nobody needs to have them all, am I wrong? |
| 18:38:34 | andytoshi: | when you create a new output, its location in the STXO will be random, so you can't describe how to insert it (which is the same as proving it's not already in the tree) without knowing the full path |
| 18:39:31 | andytoshi: | if you know all your outputs before you ever build the STXO set you'd be ok..but that would basically require you reindexing every time you create a new one |
| 18:40:08 | jtimon_: | ok, so someone has to have the full TXO to be able to expand it |
| 18:41:14 | jtimon_: | but that's true already for the "only committed TXO to allow storageless mining" softfork proposal, so I don't see how the STXO can be any worse |
| 18:41:15 | andytoshi: | well, the full STXO would be sufficient to create a STXO proof |
| 18:42:43 | jtimon_: | maybe you can even somehow compress the storage taking advantage on the fact that any element that belongs to STXO also belongs to TXO |
| 18:43:13 | jtimon_: | I don't undesrtand maaku's objections |
| 18:44:32 | andytoshi: | with storageless mining, you need only prove that an output is in the TXO set, which is easy if it's insertion-ordered, you just keep the proof when you insert it |
| 18:44:53 | andytoshi: | so it's not really storageless (if i understand right), you need the utxo set hanging around |
| 18:45:10 | andytoshi: | but insertion-ordering makes a proof of non-existence impossible |
| 18:45:22 | jtimon_: | also maaku's "TXO doesn't need storage of the data at all to create new outputs" seems to conflict with andytoshi's " you can create proofs of nonexistence that require no STXO storage to verify, but to create them basically requires random access to the whole STXO set" |
| 18:45:49 | andytoshi: | jtimon_: it's a difference of how you order the set, i should've been clearer when i said that |
| 18:46:22 | andytoshi: | with insertion ordering, insertion is easy (and therefore proof of presence is easy). but you can't do proof of non-presence |
| 18:47:18 | andytoshi: | with hash ordering (as in merkle tries), insertion is hard (requires random access) but unique, so given a path to insert a new element, this is a proof that the element wasn't already present |
| 18:47:23 | Luke-Jr: | I'm not sure miners need to be catered to here |
| 18:48:08 | jtimon_: | ok, so let's say we have insertion ordering for both TXO and STXO |
| 18:48:15 | Luke-Jr: | unless the goal is to have the block template made faster |
| 18:48:30 | jtimon_: | what happens when I try to insert an element in STXO that already exists in STXO? |
| 18:48:57 | andytoshi: | jtimon_: it's in there twice, but only a person who knows of both inserts can prove this |
| 18:49:26 | andytoshi: | because the place that it gets inserted has nothing to do with the element itself. so you can't lookup by element |
| 18:49:37 | jtimon_: | doesn't a first addition modify the root of the trie? |
| 18:50:13 | jtimon_: | does a second insertion modify it too? |
| 18:50:33 | andytoshi: | yes, but you'd have to replay the whole history to notice this |
| 18:50:50 | jtimon_: | yes to which question? |
| 18:51:06 | andytoshi: | as opposed to verifying the modification is legit when it happens, then forgetting why because you don't want to store everything |
| 18:51:18 | andytoshi: | yes to both |
| 18:51:42 | andytoshi: | but to say "oh, a first insertion happened, here's where it modified the root" you'd have to replay the whole history |
| 18:51:45 | jtimon_: | ok, the second addition also modifies the root, that's a problem |
| 18:52:07 | andytoshi: | yeah, that's one way to look at it |
| 18:52:35 | jtimon_: | if the second didn't you could say "hey I added it and it didn't modified the root so it was already there" |
| 18:53:42 | andytoshi: | yeah, exactly. you get that with hash-ordering. but then you need to store the whole thing to figure out where to insert in the first place |
| 18:54:11 | andytoshi: | can we get the best of both worlds? it feels like no, there's a strong tension here, but idk.. |
| 18:54:24 | jtimon_: | yep, that's why the UTXO is not allowed, so wouldn't work for the STXO either |
| 18:57:49 | jtimon_: | so in the case of the TXO, can you store only parts of it? like the proofs that your own utxo exist? |
| 18:58:04 | andytoshi: | ah, with UTXO you can remove elements tho |
| 18:58:27 | andytoshi: | so you never need a proof of non-presence, just a proof of presence (which is easy with an insertion-ordered tree) |
| 18:59:42 | jtimon_: | but is the insertion ordered trie compatible with removing elements? are you talking about maaku's structure? |
| 18:59:45 | andytoshi: | yeah, you can get away with storing none of TXO because you don't care if there are dupes |
| 19:00:18 | andytoshi: | jtimon_: i don't know |
| 19:00:37 | jtimon_: | I mean, you may want to store some of the TXO to give it to storageless miners when you want to spend your coins |
| 19:01:09 | andytoshi: | right, you'd store the parts that had your outputs. but you wouldn't have to store more, and miners wouldn't have to story any |
| 19:02:12 | jtimon_: | exactly, that sounds like what maaku wanted to use for the txo, let me try to find his bip draft... |
| 19:02:22 | andytoshi: | hmm. it's not clear to me what the point of TXO is, actually, why is just UTXO not sufficient? |
| 19:07:43 | jtimon_: | here is his structure for the TXO https://github.com/maaku/bips/blob/master/drafts/auth-trie.mediawiki#Variation_2_Proofupdatable_hashing |
| 19:08:48 | jtimon_: | the point of the TXO is storageless mining |
| 19:08:58 | jtimon_: | of the committed TXO |
| 19:10:26 | jtimon_: | the problem with the committed UTXO are precisely the storage costs, that's why petertodd proposes a fixed size and make the oldest have an expiry |
| 19:17:11 | andytoshi: | it seems like if you allow remove elements from UTXO whenever you spend them (since you need to give a path to prove presence anyway) that should eliminate the storage costs |
| 19:17:20 | andytoshi: | everyone only stores the UTXOs they care about |
| 19:17:47 | andytoshi: | as for maaku's auth-prefix-tree thing, it seems like you still need random access to insert new elements |
| 19:18:32 | andytoshi: | the inclusions are 'local' in the sense that they require you know only nearby hash values. but since hash values are random so is 'nearby' |
| 19:33:20 | andytoshi: | maybe we could design a structure which used the blockchain to define a tree, so your merkle proofs would use a blockhash as a root. then everyone would have to store all the blockheaders, but those are reasonably cheap |
| 19:35:15 | andytoshi: | no, i'm being stupid. i'll shut up until i have something sensible |
| 19:38:07 | Eliel: | does someone have a link to an introduction about this TXO + STXO system? |
| 19:44:37 | andytoshi: | no, sorry, it was a half-baked idea i had for making cryptonote scalable. but now i think it requires some data structure that doesn't exist |
| 19:45:17 | andytoshi: | basically, TXO and STXO would both be merkle trees of some sort. to spend an output you'd prove it was present in TXO and -not- present in STXO (spent trasnaction outputs) |
| 19:46:01 | andytoshi: | the problem is that proof of non-presence requires that merkle paths be unique, and it seems like this forces the prover to have access to the whole set, which is what we're trying to avoid because it grows without bound |
| 19:47:41 | Eliel: | ah, right, to prove non-presence, you'd have to prove the direct neighbors exist and are neighbors. |
| 19:50:27 | andytoshi: | yeah. so here's a question: can you somehow control your neighbor set so that you know which parts of the tree you need to store on the initial index, before you create any outputs? |
| 19:51:44 | andytoshi: | i guess there's a simple TMTO here, you can easily grind through a few thousand hashes, so if you just stored a thousandth of the full set you'd be able to make proofs.. |
| 19:51:52 | andytoshi: | (TMTO is time/memory tradeoff) |
| 20:03:19 | Eliel: | you'd also need a way to compactly store which parts of the tree you chose to keep. I suppose you could store a random seed for that. |
| 20:03:33 | Eliel: | (for offline backups) |
| 20:07:22 | andytoshi: | you'd just store all hashes between SEED and SEED + N, yeah, where N is something like the total space divided by 10000 |
| 20:09:32 | andytoshi: | i mean, all txouts which hashed to between SEED and SEED + N |
| 20:23:24 | Eliel: | Anduck: I think that's too simple. Used that way it has privacy implications. |
| 20:23:53 | Anduck: | andytoshi* |
| 20:23:54 | andytoshi: | Eliel: yeah, you're right, i'd want to use all txes which are 0 mod N say |
| 20:24:38 | Eliel: | you need bigger areas to have reasonable chances of getting your outputs somewhere. |
| 20:26:49 | andytoshi: | eh, finding a random-seeming area is a solvable problem anyway (maybe, when you hash it alongside your random seed it's between 0 and some target). i was half-kidding when i suggested this but it's growing on me.. i can grind through 10mhashes in under a second with pretty dumb code on my laptop. one 10 millionth of the current blockchain is like 20kb. |
| 20:34:31 | Eliel: | 200GB blockchain? |
| 20:38:54 | andytoshi: | :P oh, i guess i meant 2kb, even better |
| 20:45:51 | Eliel: | yes, sounds feasible |
| 20:46:43 | Eliel: | by the way, is it the sender or receiver who needs to do this? |
| 20:48:12 | andytoshi: | the receiver, since it has to be done when creating new outputs |
| 20:48:47 | andytoshi: | when you create an address, you'd create an entire output along with the proof you'll later need to add it to the STXO set |
| 20:50:31 | Eliel: | wouldn't the proofs get out of date pretty fast? |
| 20:51:05 | andytoshi: | yeah, you'd have to maintain it as new blocks come in |
| 20:51:30 | Eliel: | and the side effect is to nicely decentralize the storage of the STXO set :) |
| 21:53:02 | justanot1eruser: | justanot1eruser is now known as justanotheruser |
| 23:19:38 | Eliel: | andytoshi: what data does the STXO set store in cryptonote's case? The key image for the TXO? |
| 23:19:53 | andytoshi: | Eliel: yup |
| 23:20:16 | andytoshi: | though i don't think there is any implementation of cryptonote that does this, bytecoin i think makes everyone store everything explicitly |
| 23:24:47 | gmaxwell: | in ram. |
| 23:32:09 | Eliel: | andytoshi: by the way, if you pregenerate addresses, couldn't you get by with much less than one ten millionth of the STXO set? |
| 23:32:45 | Eliel: | you could afford to spend minutes per output if you're just pregenerating. |
| 23:33:57 | andytoshi: | Eliel: yeah, you could store only your outputs' neighbors (and keep them up to date). but you're going to run out of outputs if you do this (you can't reuse them in this scheme) (cryptonote also has this 'problem', if you reuse an output you can only spend one, the other is lost) |
| 23:35:06 | Eliel: | ah, so the bad habit people have in bitcoin of reusing addresses is not possible. |
| 23:36:31 | andytoshi: | well, you could enable it by adding a nonce to your outputs..but yeah, basically correct |
| 23:38:13 | Eliel: | But what I was going for wasn't complete pregeneration but rather keeping a cache of perhaps 100 unused addresses, similar to bitcoin. |
| 23:38:44 | Eliel: | hmmh... does this pose a problem for deterministic wallets by the way? I mean restoring them from the seed. |
| 23:38:59 | andytoshi: | well, you'd need to obtain a copy of the whole blockchain somehow whenever you generated more |
| 23:40:10 | andytoshi: | yeah, it'd probably get screwed up for deterministic wallets.. not totally tho, you can grind within the deterministic chain to find addresses that are in your search area |
| 23:40:30 | Eliel: | ah, true, just slows down the recovery from backup |
| 23:44:01 | Eliel: | one more thing about only storing part of the STXO, it'd be beneficial for the network if the nodes were willing to share at least some of the range they're keeping. However, there's privacy implications in this case. |
| 23:45:10 | andytoshi: | well, you'd definitely need full archival nodes for people to do the inital sync (and to discover whatever of the set they're storing) |
| 23:46:53 | Eliel: | the system would be able to afford losing some of the set, no? |
| 23:48:05 | Eliel: | or more like, if a part of the set ends up being lost in the decentralized storage model, most likely it can be forgotten without problems. |
| 23:48:29 | andytoshi: | yeah, it only matters to the people who want to spend those specific coins |
| 23:50:31 | andytoshi: | i guess if you lose the entire thing nobody can produce inclusion proofs, that'd probably be bad ;) |
| 23:54:15 | Eliel: | if everyone keeps their own part plus enough to comfortably brute force more, I'd think that's _very_ unlikely :D |