00:20:27amiller:yeah all that's correct
00:21:54petertodd:amiller: how long do the proofs take to generate?
00:22:06petertodd:amiller: (I mean, with your best implementation?)
00:22:21amiller:petertodd, there is a "cheap plaintext" option that takes no time at all to produce
00:22:33petertodd:amiller: sure, I mean the non-plaintext version
00:22:35amiller:honest, hardworking, salt of the earth solo miners can take that route
00:22:47amiller:the best score i got (using Pinocchio, mind you) is 7 minutes
00:23:09amiller:that's assuming a lot of parallel power, we called it $45 in ec2 credit
00:23:29petertodd: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:57petertodd:damn, how parallel is that?!
00:25:18petertodd:adding a varience reduction mechanism is probably more plausible :)
00:25:52amiller:well you need both
00:26:03amiller:also the snark version is really only important for discouraging hosted minig
00:26:03petertodd:well, I mean just adding it
00:26:28amiller:the simpler "weak non-outsourceable" version is already a good way of making pools impractical
00:26:40petertodd:well, I suspect pools would just start asking for deposits - you do need the privacy
00:27:30amiller:yeah it's a good point
00:27:33petertodd: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:29petertodd:(actually, that doesn't need to be an explicit part of the protocol if coinbase outputs can be spent immediately)
00:33:47todays_tomorrow:todays_tomorrow has left #bitcoin-wizards
00:35:54andytoshi:are there plausible variance reduction mechanisms?
00:37:35petertodd: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:52amiller:i'm starting to worry that they might be incompatible with this long delay problem
00:38:17petertodd:amiller: long delay?
00:38:23amiller: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:11andytoshi: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:23petertodd: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:24andytoshi:i like treechains, though i don't have a concrete idea of what the incentives will look like
00:39:37amiller:i see
00:39:40amiller:yeah that could be, why not
00:39:48petertodd:andytoshi: treechains is really bizzare re: incentives, because multiple incentive systems can exist simultaneously on it
00:40:20petertodd: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:40andytoshi: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:38andytoshi:dropping variance by having a treechain system where every subchain has the same rules might be worth thinking about
00:43:11petertodd:andytoshi: yeah, but remember, that means the coins being created in the subchains have to be valuable - not a trivial prospect
00:44:48andytoshi: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:25andytoshi:the PoW difficulty on each chain would naturally equalize so they should all have equal value
00:45:28petertodd: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:47amiller:copy of the blockchain seems way less relevant
00:46:07petertodd:amiller: well, by that I mean if you can do work and get a share, why should you bother validating?
00:46:50amiller:yeah it's not a bad goal
00:46:53petertodd: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:40petertodd: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:30amiller:yeah sure i agree i can easily imagine a case where all of these things are eventually exploited by lazy people
00:48:40amiller:the mining system is basically the main carrot we have to steer this kind of decision
00:48:59petertodd:exactly, and not having to run a node is a pretty big incentive.
00:49:24petertodd:if you tie PoW to chain data posession it's not so bad, but then proving shares becomes harder/larger
00:52:58amiller:s/chain/utxo/ in my opinion
00:53:35amiller:i don't know if i can combine utxo posession proofs AND the nonoutsourceable snark efficiently enough
00:53:46amiller:maybe libsnark fixes all of this AND has room to spare for like the 1 minute thing etc
00:54:28petertodd: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:57amiller:ok well we need that separately
00:55:24petertodd: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:39amiller: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:03petertodd:oh, utxo space rental?
00:57:46amiller: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:05amiller: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:09Eliel: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:28petertodd: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:50petertodd:Eliel: this is -wizards - we want designs that work even if the resource usage matters
00:59:05andytoshi:so you'd have something like a merkle root of all utxos, then a fixed-size "live utxos" set
00:59:13petertodd:Eliel: I'm also very skeptical that you're right there, at least if the alternative is no resource usage
00:59:30petertodd:andytoshi: a merkle root of all *txos*, and a live utxos set
01:00:08andytoshi: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:40maaku:amiller: you have to get proving times down to <5s to be viable imho
01:00:49amiller:sheesh ok
01:01:06amiller:maaku, how many thosuands of cpu cores will you let me get away iwth??!!
01:01:11petertodd: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:14maaku:1 cpu core
01:01:27maaku:and maybe a low-end gpu
01:01:54amiller:maaku, well fuck that i'll be dead by then
01:02:08amiller:maaku, why so poor?
01:02:09amiller:i mean,
01:02:15petertodd: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:20gmaxwell:I don't agree that it needs to be quite that fast.
01:02:33amiller:maaku, petertodd if you can put up a "deposit" it would have to be on the order of 25btc.
01:02:49amiller:so i think the cost of the proof should be judged as proportional to that in some way
01:02:57andytoshi: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:29petertodd:amiller: well, specifically re: deposits, said deposit could be tied to real-world legal threats, which would be Really Badâ„¢
01:03:36amiller: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:58amiller:petertodd, yeah ok decent point
01:04:04maaku:amiller: every added second is money-losing
01:04:09maaku:and every added core is centralizing
01:04:20petertodd:andytoshi: why the two trees rather than a tree that you modify on the fly?
01:04:24andytoshi: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:29amiller: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:46petertodd:maaku: there's a non-snark "fast past" - the snarks are only the "anti-pool" option
01:04:54amiller:maaku, this is not relevant for "solo miners" who get a free pass
01:04:57amiller:a cheap plaintext option
01:05:11andytoshi: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:29maaku:amiller: "a cheap plaintext option"?
01:05:39petertodd: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:53maaku:if it's optional then no one will use it
01:06:08amiller:maaku, you would use it if you were on a pool, and using it let you get lucky and steal 25btc!
01:06:22amiller:maybe people would be so pessimistic they'd ever get that opportunity they wouldn't prepare for it.
01:06:24petertodd:andytoshi: I'm not sure modify-in-place semi-append-only isn't NIZK compatible
01:06:29amiller:some would
01:06:29gmaxwell: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:57gmaxwell:but if no one ever does then its clear enough to everyone that no one is.
01:07:00petertodd:gmaxwell: making theft blocks have a higher subsidy is a good option... but that's an economic change
01:07:14maaku:amiller: so the point is to kill pools but not actually use the ZKP version in production?
01:07:28gmaxwell:it being an economic change is probably not the biggest issue.
01:07:31petertodd:maaku: no, the ZKP has to be "production" if it's going to actually kill pools
01:07:49maaku:petertodd: i get that. i meant "in practice"
01:07:50amiller: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:28gmaxwell: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:13gmaxwell: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:38petertodd:gmaxwell: deeply ugly when the likes of ghash.io have >25% of actual hashing power in their hands...
01:09:44amiller:that's pretty interesting, not the slightest bit addessed by any of my definitions...
01:10:13maaku:probably >85% of current hashpower would go for a soft-fork ignoring the theft blocks
01:10:39petertodd: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:47maaku:amiller: I assumed earlier that this would be the *required* form of pow, since as noted, it's trivially soft-fork ignorable
01:11:00gmaxwell: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:14gmaxwell:maaku: it can't be, or you can't process transactions.
01:11:19maaku:hence, needs to be <5s on 1-2 cores or gpu to keep pow progress free
01:11:21gmaxwell:otherwise the transactions could watermark users.
01:11:28amiller:that's damned interesting and i have no idea how to prevent block discouragement / soft-fork attempts :p
01:11:36amiller:a stegonographic zero-knowledge proof or something
01:11:53amiller:gmaxwell, you can add transactions *after* finding the solution
01:11:54petertodd: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:57amiller:theft blocks still can contain transactions
01:12:28gmaxwell:amiller: they can't confirm them, however, because you can 'costlessly' replace a chain with theft blocks with alternative theft blocks.
01:12:45amiller:gmaxwell, i don't see what difference that makes
01:12:51petertodd:amiller: interesting to think about in relation to replace-by-fee scorched-earth...
01:12:55amiller:gmaxwell, think of this as adding 1 to the confirmation time everywhere
01:13:20gmaxwell:amiller: until your pool asks every user to work on a different height 1 fork.
01:13:40petertodd: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:58amiller: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:09petertodd:amiller: oh wait, that was a dumb statement I think because it's prevblockhash...
01:15:44andytoshi:gmaxwell: what is your concern re watermarking?
01:15:45petertodd:amiller: you know, an interesting option might be to build this into a zerocash chain and release as an alt-currency
01:15:59andytoshi:that a pool would boot people out after the fact?
01:16:33amiller:petertodd, yeah i'm... ambivalent about that idea but it may be a decent way to proceed anyway
01:18:16petertodd: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:06amiller:petertodd, interesting point
01:19:11gmaxwell:andytoshi: you can have your work watermarked by anything you must commit to in advance.
01:19:16amiller:break the snark, win a fabulous prize
01:19:44gmaxwell: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:52petertodd: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:28petertodd:gmaxwell: your hashing power can be signing the previous history only, rather than the block you are adding to that history
01:21:03gmaxwell: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:41petertodd:gmaxwell: that's fine so long as the previous block is a plaintext one (or one the pool didn't find...)
01:21:45gmaxwell:so it isn't quite as simple as "adds an extra confirm to the requirements"
01:22:00gmaxwell:petertodd: the context above as having no plaintext blocks.
01:22:04petertodd:which actually means a plausible option is to force plaintext/non-plaintext
01:22:10petertodd:gmaxwell: ah, yeah, that's an issue
01:22:36amiller:or blocks the pool didn't win.... if a non malleable snark is used which isn't so hard
01:22:58gmaxwell:the GGPR'12 snark is super-super malleable.
01:23:02amiller: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:24:05gmaxwell:(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:44amiller:so pools could discourage defectin whenever they're on a streak
01:24:45gmaxwell: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:07amiller:it's kinda all corner cases out here :)
01:25:34maaku:so this also allows rewriting history for as far back as you've managed to get consecutive blocks
01:25:45petertodd:amiller: it's not a spherical cow, it's a dodecahedron cow
01:25:52maaku:so you can opportunistically do finney attacks once you get 6 blocks in a row
01:26:16amiller:it's a hypercow with a semi-trusted dodecacow that's turned into sausage after setup
01:26:17petertodd:maaku: not if you require work to commit to the hash of the previous block in plaintext
01:26:30maaku:ah ok so just 1 block
01:26:50petertodd:amiller: I think I'll just eat it rather than watch the How It's Made! episode...
01:26:52amiller:yes only adds one block, still no more advntage to an attacker after that, even if they have a straek
01:28:36gmaxwell:if you keep working on it it'll be a rhombicuboctahedron-cow.
01:29:08petertodd: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:23petertodd:gmaxwell: if we add enough corner cases it'll approximate a spherical cow!
01:30:50amiller: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:00amiller:if you think you can get away with it, you might not send it to the pool
01:31:19amiller: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:59petertodd: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:12amiller:at least this provides a pretty good incentive to do so
01:32:43amiller: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:29petertodd:amiller: hmm, explain about how that works?
01:34:25amiller: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:22petertodd:right, so the alturistic vigilante frames people by not releasing plaintext?
01:35:23amiller: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:45amiller:i guess basically the vigilante just release zero-knowledge blocks and hopes for the best.
01:36:12petertodd:yeah, every zk block released is a potential false-positive for the pools - yet another reason to incentivize them
01:36:19amiller:right exactly
01:36:49amiller: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:56amiller:so general false positives is the best i can say
01:37:09petertodd:yeah, uncertainty about the running time of the zk-proof solvers will help
03:05:25maaku:maaku is now known as Guest41141
03:07:45Guest41141:Guest41141 is now known as maaku
04:02:41wallet421:wallet421 is now known as wallet42
05:41:56justanotheruser:justanotheruser is now known as justanotheruser2
05:42:20justanotheruser2:justanotheruser2 is now known as justanotheruser3
05:42:44justanotheruser3:justanotheruser3 is now known as pikman
05:43:07pikman:pikman is now known as justanotheruser
06:20:27maaku:gmaxwell amiller: the zkp setup considered for non-outsourcable puzzles involves trusted setup / CRS parameters, right?
06:20:42maaku:and the person holding these parameters is able to mint blocks on demand, no?
06:22:03maaku:k just making sure i'm not crazy
06:22:39gmaxwell:well I wouldn't go that far!
06:24:08maaku: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:58gmaxwell:right, no no I meant, concluding that you weren't crazy. :)
06:31:53maaku:ah ok
07:25:34sl01: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:31Vitalik_:Vitalik_ is now known as Vitalik__
08:33:13tomaw:[Global Notice] Hi all. I need to reroute some servers after that split otherwise we'll see significant lag across the network.
12:47:32Eliel:isn't there some way to somehow set the zkp parameters so that no-one knows the dangerous private parameters?
12:47:57Eliel:... that is, a way prove it I suppose.
13:56:47michagogo: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:07michagogo:And then pointing a blowtorch at the whole setup
13:58:59michagogo:Not sure how you prove the integrity of the software, though
14:00:11helo:a wink and nod suffices iirc
14:05:01michagogo:;;google spherical cow
14:05:01gribble: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:14maaku:michagogo: then generate a separate set of parameters and edit the video to show those
17:44:47michagogo:livestream it?
17:45:13maaku:Eliel: there are multi-party compute schemes, but this is orders of magnitude more complex than anything that has ever been run
17:45:56maaku:typical systems today are doing things like adding two integers in a multi-compute environment. this necessitates running giant pairing crypto operations
17:46:43Eliel:does that mean it's significantly more difficult to create a program for doing it?
17:47:53maaku: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:44maaku: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:52maaku:it's turtles all the way down
17:49:23Guyver2:Guyver2 has left #bitcoin-wizards
17:52:57Eliel:maaku: hmmh, entire google datacenter for months... that means anyone can do it in about 10 years then ;)
18:01:41zooko:zooko has left #bitcoin-wizards
18:01:43nsh:in 10 years, we'll be working for the google datacenter, not the other way around
18:13:22jtimon_:andytoshi I find your idea of committed TXO + STXO very interesting
18:13:22jtimon_: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:55jtimon_:maaku petertodd disadvantages of TXO + STXO over TXO + UTXO ?
18:17:19andytoshi: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:10andytoshi:(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:26jtimon_: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:27andytoshi: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:04andytoshi: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:33jtimon_: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:48maaku:that changes semantics of bitcoin in the case of a hash collision
18:21:24maaku:which is more of an fyi
18:21:44jtimon_: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:13andytoshi: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:35maaku:andytoshi: we're going that direction irregardless
18:22:39jtimon_:I'm not sure the expired-UTXO has enough value if you already have TXO + STXO
18:22:42maaku:(storageless mining)
18:23:51maaku:jtimon_: I'm not sure why you need TXO + STXO
18:23:53jtimon_: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:54maaku:TXO is STXO
18:24:17jtimon_:STXO is included in TXO
18:24:35jtimon_:TXO - STXO = UTXO
18:25:02andytoshi: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:35jtimon_:because that way you can produce SPV proofs equivalent of having a commited UTXO
18:25:35andytoshi: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:41maaku:STXO sounds like the worst aspects of both -- an ever growing data set which you need random access to
18:26:34jtimon_:why should the STXO data structure be any different from TXO's?
18:26:51andytoshi: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:19maaku: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:49jtimon_:so here you don't have commited UTXO
18:28:07maaku:jtimon_: commited STXO has all the same bad tradeoffs
18:28:13maaku:with none of the upside
18:28:19jtimon_:(1) STXO doesn't need storage of the data at all to create new outputs
18:28:41jtimon_:so how do you query the TXO ?
18:28:43maaku:jtimon_: what are you ordering by?
18:28:52maaku:insertion order? then you are talking about TXO
18:29:20jtimon_:yes, STXO, would be almost identical to TXO, just lacking the unspend outputs
18:29:45maaku:that's useless
18:30:15maaku:to know double-spend status you need to lookup by txid, or have all txouts
18:31:11jtimon_:now you can proof that output X is unspent on block H, just with block H's root
18:31:12jtimon_:Can you do that only with TXO?
18:31:31andytoshi:oh derp, i had thought merkle tries would let you do this without any storage but ofc not..
18:33:19jtimon_: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:24gmaxwell:STXO has an advantage that it also works nicely for anonymous transaction systems.
18:34:12jtimon_:is that useless?
18:34:19andytoshi:( http://himalia.it.jyu.fi/ffdoc/fenfire/dartboard/merkle_has_tries--benja/idea.gen.html for merkle tries btw)
18:35:58andytoshi: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:43jtimon_: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:26jtimon_:people should keep their parts of the TXO trie but nobody needs to have them all, am I wrong?
18:38:34andytoshi: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:31andytoshi: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:08jtimon_:ok, so someone has to have the full TXO to be able to expand it
18:41:14jtimon_: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:15andytoshi:well, the full STXO would be sufficient to create a STXO proof
18:42:43jtimon_: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:13jtimon_:I don't undesrtand maaku's objections
18:44:32andytoshi: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:53andytoshi:so it's not really storageless (if i understand right), you need the utxo set hanging around
18:45:10andytoshi:but insertion-ordering makes a proof of non-existence impossible
18:45:22jtimon_: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:49andytoshi:jtimon_: it's a difference of how you order the set, i should've been clearer when i said that
18:46:22andytoshi:with insertion ordering, insertion is easy (and therefore proof of presence is easy). but you can't do proof of non-presence
18:47:18andytoshi: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:23Luke-Jr:I'm not sure miners need to be catered to here
18:48:08jtimon_:ok, so let's say we have insertion ordering for both TXO and STXO
18:48:15Luke-Jr:unless the goal is to have the block template made faster
18:48:30jtimon_:what happens when I try to insert an element in STXO that already exists in STXO?
18:48:57andytoshi:jtimon_: it's in there twice, but only a person who knows of both inserts can prove this
18:49:26andytoshi:because the place that it gets inserted has nothing to do with the element itself. so you can't lookup by element
18:49:37jtimon_:doesn't a first addition modify the root of the trie?
18:50:13jtimon_:does a second insertion modify it too?
18:50:33andytoshi:yes, but you'd have to replay the whole history to notice this
18:50:50jtimon_:yes to which question?
18:51:06andytoshi:as opposed to verifying the modification is legit when it happens, then forgetting why because you don't want to store everything
18:51:18andytoshi:yes to both
18:51:42andytoshi: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:45jtimon_:ok, the second addition also modifies the root, that's a problem
18:52:07andytoshi:yeah, that's one way to look at it
18:52:35jtimon_: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:42andytoshi: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:11andytoshi:can we get the best of both worlds? it feels like no, there's a strong tension here, but idk..
18:54:24jtimon_:yep, that's why the UTXO is not allowed, so wouldn't work for the STXO either
18:57:49jtimon_:so in the case of the TXO, can you store only parts of it? like the proofs that your own utxo exist?
18:58:04andytoshi:ah, with UTXO you can remove elements tho
18:58:27andytoshi:so you never need a proof of non-presence, just a proof of presence (which is easy with an insertion-ordered tree)
18:59:42jtimon_:but is the insertion ordered trie compatible with removing elements? are you talking about maaku's structure?
18:59:45andytoshi:yeah, you can get away with storing none of TXO because you don't care if there are dupes
19:00:18andytoshi:jtimon_: i don't know
19:00:37jtimon_: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:09andytoshi: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:12jtimon_:exactly, that sounds like what maaku wanted to use for the txo, let me try to find his bip draft...
19:02:22andytoshi:hmm. it's not clear to me what the point of TXO is, actually, why is just UTXO not sufficient?
19:07:43jtimon_:here is his structure for the TXO https://github.com/maaku/bips/blob/master/drafts/auth-trie.mediawiki#Variation_2_Proofupdatable_hashing
19:08:48jtimon_:the point of the TXO is storageless mining
19:08:58jtimon_:of the committed TXO
19:10:26jtimon_: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:11andytoshi: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:20andytoshi:everyone only stores the UTXOs they care about
19:17:47andytoshi:as for maaku's auth-prefix-tree thing, it seems like you still need random access to insert new elements
19:18:32andytoshi: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:20andytoshi: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:15andytoshi:no, i'm being stupid. i'll shut up until i have something sensible
19:38:07Eliel:does someone have a link to an introduction about this TXO + STXO system?
19:44:37andytoshi: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:17andytoshi: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:01andytoshi: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:41Eliel:ah, right, to prove non-presence, you'd have to prove the direct neighbors exist and are neighbors.
19:50:27andytoshi: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:44andytoshi: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:52andytoshi:(TMTO is time/memory tradeoff)
20:03:19Eliel: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:33Eliel:(for offline backups)
20:07:22andytoshi: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:32andytoshi:i mean, all txouts which hashed to between SEED and SEED + N
20:23:24Eliel:Anduck: I think that's too simple. Used that way it has privacy implications.
20:23:54andytoshi:Eliel: yeah, you're right, i'd want to use all txes which are 0 mod N say
20:24:38Eliel:you need bigger areas to have reasonable chances of getting your outputs somewhere.
20:26:49andytoshi: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:31Eliel:200GB blockchain?
20:38:54andytoshi::P oh, i guess i meant 2kb, even better
20:45:51Eliel:yes, sounds feasible
20:46:43Eliel:by the way, is it the sender or receiver who needs to do this?
20:48:12andytoshi:the receiver, since it has to be done when creating new outputs
20:48:47andytoshi: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:31Eliel:wouldn't the proofs get out of date pretty fast?
20:51:05andytoshi:yeah, you'd have to maintain it as new blocks come in
20:51:30Eliel:and the side effect is to nicely decentralize the storage of the STXO set :)
21:53:02justanot1eruser:justanot1eruser is now known as justanotheruser
23:19:38Eliel:andytoshi: what data does the STXO set store in cryptonote's case? The key image for the TXO?
23:19:53andytoshi:Eliel: yup
23:20:16andytoshi:though i don't think there is any implementation of cryptonote that does this, bytecoin i think makes everyone store everything explicitly
23:24:47gmaxwell:in ram.
23:32:09Eliel: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:45Eliel:you could afford to spend minutes per output if you're just pregenerating.
23:33:57andytoshi: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:06Eliel:ah, so the bad habit people have in bitcoin of reusing addresses is not possible.
23:36:31andytoshi:well, you could enable it by adding a nonce to your outputs..but yeah, basically correct
23:38:13Eliel: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:44Eliel:hmmh... does this pose a problem for deterministic wallets by the way? I mean restoring them from the seed.
23:38:59andytoshi:well, you'd need to obtain a copy of the whole blockchain somehow whenever you generated more
23:40:10andytoshi: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:30Eliel:ah, true, just slows down the recovery from backup
23:44:01Eliel: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:10andytoshi: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:53Eliel:the system would be able to afford losing some of the set, no?
23:48:05Eliel: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:29andytoshi:yeah, it only matters to the people who want to spend those specific coins
23:50:31andytoshi:i guess if you lose the entire thing nobody can produce inclusion proofs, that'd probably be bad ;)
23:54:15Eliel:if everyone keeps their own part plus enough to comfortably brute force more, I'd think that's _very_ unlikely :D