00:02:58zack-truthcoin:my design wont work at all. Thanks for the help. sorry to waste this precious place.
00:04:22zack-truthcoin:Truthcoin is really important: https://github.com/psztorc/Truthcoin Vitalik talked about it recently: https://blog.ethereum.org/2014/08/21/introduction-futarchy/ and I am attempting to implement it: https://github.com/zack-bitcoin/Truthcoin-POW
00:06:19phantomcircuit:so anyways
00:06:40justanotheruser:vitalek will endorse a lot of ideas that wont work
00:06:42phantomcircuit:petertodd suggested that using a radix tree would be a better way to do merged mining
00:07:02phantomcircuit:that seems to be right, i cant think of any downsides
00:07:07phantomcircuit:can anybody else?
00:08:56petertodd:phantomcircuit: agreed, that's one of the use-cases I had in mind for the so-called "merbinner" tree thing I've been working on
00:09:28phantomcircuit:lol @ name
00:09:34gmaxwell:phantomcircuit: thats a bit underdefined. How do you know there aren't two commitments at the same position. You mean a patricia trie with a key/value pair? If the keys are not required to be a hash of something you can have degenerate data that makes the tree unbalanced, which may or may not be an issue.
00:09:50petertodd:bsm117532: I
00:10:14phantomcircuit:gmaxwell, to expand more
00:10:20petertodd:bsm117532: I'm probably using somewhat wrong terminology then - what I've actually implemented is what you're thinking of
00:10:24phantomcircuit:yes a patricia trie with key/value pairs
00:10:35phantomcircuit:the key would be H(prev_block_hash|chain_id)
00:10:46phantomcircuit:value would be H(block)
00:11:14phantomcircuit:then you hash each node to get something very similar to a merkle tree root
00:12:00phantomcircuit:petertodd, ooh neat this is pretty close to being a real implementation :P
00:12:08zack-truthcoin:my_bundell: all 50% would have to let their coins get deleted on the main chain at the same time. A highly unlikely scenario.
00:12:15gmaxwell:phantomcircuit: okay, that likely has excellent properties. I'd have to think through the structural details.
00:12:17petertodd:bsm117532: my tree does what I guess you'd call "postfix" path compression, skipping the prefix part
00:12:58petertodd:phantomcircuit: yup, I need to add some serialization code to my library and do some more documentation, but for the purpose of merge-mining it's done
00:13:26gmaxwell:zack-truthcoin: IIRC I owned more than half of all PPC (or at least close to it) at one point, and my keys are no longer active in that chain.
00:13:54petertodd:phantomcircuit: er, I mean it's done enough with that serialization/deserialization
00:14:24zack-truthcoin:when such a vulnerability occurs, the entire community is instantly aware, and can do a hard-fork to repair
00:15:23gmaxwell:zack-truthcoin: how? you have no idea who knows what. You can't point out what ppc was mine, as it was under an assortment of different keys.
00:15:29phantomcircuit:petertodd, i get the strong feeling implementing this in c is going to be stupid annoying
00:15:49petertodd:bsm117532: heh, you know if anything my confusion over the exact name of what it's doing shows that making up a specific name for the exact algorithm was a good idea :)
00:16:10zack-truthcoin:in ppc, you can't tell the difference between burned and unburned coins. in my pos, since everyone has to pledge all the time, burned coins are very different.
00:16:28petertodd:phantomcircuit: I'm sure it will be, but then again, implementing any non-trivial tree in C can be like that
00:16:51phantomcircuit:petertodd, fortunately i have people i can assign to do things like this
00:16:53petertodd:phantomcircuit: of course, you can always simulate C++ classes/virtuals in C :)
00:17:00phantomcircuit:just need to given them a very detailed specification
00:17:45gmaxwell:zack-truthcoin: I think we're not making any progress in communicating here.
00:17:48petertodd:phantomcircuit: well, my unittests are/are going to be detailed enough for that - probaby best if there's a json'd version with well defined input and output vectors
00:18:12petertodd:phantomcircuit: I assume you don't need to implement any of the fancy pruning stuff right?
00:19:18phantomcircuit:petertodd, shouldn't have to no
00:19:51petertodd:phantomcircuit: good - the hashing of course doesn't know anything about pruning
00:20:15gmaxwell:petertodd: I assume you're using binary splits?
00:20:54petertodd:gmaxwell: yeah, each inner node has exactly two leaves, and either leaf may be empty if the keys collide at that level
00:21:51petertodd:gmaxwell: it's designed for short proof sizes when pruned of course
00:27:40pigeons:that ethereum blog post zack-truthcoin linked is kinda out there, but it got a comment from someone who might be wei dai of the b-money paper
00:27:55pigeons:or b-money email, whatever
00:29:46phantomcircuit:pigeons, appeals to apparent authority are lame
00:30:00phantomcircuit:especially when i've seen people running around on bitcoin sites pretending to be all kinds of people
00:30:01gmaxwell:phantomcircuit: thats not what that was. :)
00:30:14phantomcircuit:gmaxwell, i know im saying the comment itself probably is
00:32:22petertodd:phantomcircuit: here's a quick sketch of what a pure-C implementation would look like to hash a tree: https://github.com/petertodd/python-merbinnertree/blob/a04307adf6659db9668d2710cada04e1ba3426d3/sketch-implementation.c
00:32:26petertodd:phantomcircuit: not all that bad really
00:32:42gmaxwell:IIRC I've seen that comment and it was a "what is this I don't even" (well really some polite point on the whole idea not being sound)
00:34:37phantomcircuit:petertodd, hmm that is pretty compact
00:34:55petertodd:phantomcircuit: fleshing it out would be just another dozen lines of code, even including the bubblesort
00:36:12petertodd:phantomcircuit: helps that it's fixed purpose :) implementing the equiv of what the Python library is doing in a sane way would need at least a ref-counting GC implementation
05:17:27Luke-Jr:anyone awake?
05:36:56Dr-G2:Dr-G2 is now known as Dr-G
06:05:29devrandom:not here either
08:05:16holmes.freenode.net:topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
08:05:16holmes.freenode.net:Users on #bitcoin-wizards: andy-logbot RoboTedd_ grandmaster2 _ingsoc Guyver2 CoinHeavy pen [Derek] Graet p15 justanotheruser tromp TheSeven Ursium Dr-G sipa mortale RoboTeddy zenojis mapppum ebfull Adohgg mr_burdell copumpkin andytoshi bsm117532 nickler devrandom Sangheili melvster grubles MoALTz_ go1111111 GAit hollandais dgenr8 nsh Transisto HaltingState jchp Graftec starsoccer Luke-Jr Krellan_ kanzure samson_ spinza mikalv EasyAt BigBitz rfreeman_w|off fanquake
08:05:16holmes.freenode.net:Users on #bitcoin-wizards: Starduster phantomcircuit gwillen mappum nuke1989 BrainOverfl0w Dyaheon SDCDev HM_ otoburb realzies Guest95624 comboy postpre nsh- Alanius mkarrer_ CryptOprah_ DoctorBTC btc jgarzik Keefe waxwing smooth koshii quackgyver michagogo warren throughnothing_ Muis artifexd Fistful_of_coins azariah4 jaromil Hunger- zibbo tromp_ fierbuq pi07r wiretapp1d forrestv OneFixt harrow K1773R pigeons iddo cfields [\\\] bobke drawingthesun midnightmagic @ChanServ
08:05:16holmes.freenode.net:Users on #bitcoin-wizards: Apocalyptic lianj wumpus nkuttler roasbeef gribble phedny so kinlo wizkid057 UukGoblin petertodd ryan-c [d__d] jcorgan optimator_ burcin LaptopZZ_ danneu dansmith_btc amiller catcow tjopper a5m0 gmaxwell TD-Linux poggy_ jbenet davidlatapie rs0 nanotube bbrittain SomeoneWeird lechuga_ espes__ abc56889 Iriez weex sl01 digitalmagus7 BlueMatt berndj-blackout asoltys Guest50253 mmozeiko epscy crescendo helo Eliel zling_____ Anduck LarsLarsen1
08:05:16holmes.freenode.net:Users on #bitcoin-wizards: polyclef maaku Logicwax CodeShark
12:48:35andytoshi:dillpicklechips has an interesting idea for p2p coinjoin https://bitcointalk.org/index.php?topic=768499.msg8709627#msg8709627 rather than blinding all the outputs, having one party sign them, then anonymously unblind them, you just anonymously sign them with a ringsig of all participants
12:50:54andytoshi:ringsigs are more expensive than blinding (though probably not meaningfully so for coinjoin-many people) but it gives you a symmetry of all participants without making everybody blindsign everything
14:14:46zackary-truthcoi:multicellular life as a proof-of-stake solution to byzantine generals problem: https://github.com/zack-bitcoin/slasher/blob/master/cancer.txt
17:50:30sl01:zackary-truthcoi: sometimes the son of a super nice guy is a serial killer/torturer
18:32:54jgarzik:sl01, usually not
18:42:39sl01:i was just responding to a bad analogy with another bad analogy :P
19:33:23rdponticelli:rdponticelli has left #bitcoin-wizards
19:40:07zackary-truthcoi:sl01: in what way are the cells not in a byzantine fault-tolerant consensus of DNA? Are you suggesting a central 3rd party that controls all the cancer aspects of the cells?
19:42:10zackary-truthcoi:only the cancer-causing aspects of the DNA is under consensus.
19:47:21gmaxwell:andytoshi: it needs the BRS style ringsigs and not what tacotime currently has implemented.
19:47:30gmaxwell:I'm surprised you think thats non-obvious. :)
19:48:05gmaxwell:The result still depends on you having a good anonymization system.
19:52:47gmaxwell:(see https://bitcointalk.org/index.php?topic=139581.msg1488128 for a sketch of a more complete protocol before I dumbed it down for the coinjoin thread)
20:00:56andytoshi:gmaxwell: you don't need BRS-style ringsigs, if anyone tries double-signing, and everyone else confirms that their outputs are there before signing the final result, then the total output val will exceed the total input value
20:05:39andytoshi:it's nonobvious only because ring signatures are still a reasonable new idea to me :) don't wreck my youthful enthusiasm
20:11:02andytoshi:i like this reencryption mix thing, i'll try to find a non-dead link describing it...though itsm if you create a blind ringsig then just reconnect through tor to unblind, you can shunt a ton of complexity out of your protocol and into tor
20:14:51tacotime:you can do bytecoin-style simply from URS if you change the niZKP hash part from belonging to the message and privatekeys to just the private keys
20:14:53tacotime:i'm pretty sure
20:16:15tacotime:oh, it looks like the challenge is just related to the message for mine, sorry
20:17:35tacotime:but if you change it to the private key i think it should map to the private key. but i'm not sure how you verify that it's a hash of the private key and not some garbage, i think there's an explanation of how to do that in the bytecoin whitepaper.
20:17:51tacotime:if you modify it to do that, submit a PR and i'll make it into a flag.
20:26:31helo:* helo sets the flag on fire
21:18:02gmaxwell:andytoshi: yes, but tor's privacy properties are pretty weak in the context where one of the people trying to deanonymize you is communicating with you.
21:28:42kmels__:kmels__ is now known as kmels
22:16:43cpacia:cpacia has left #bitcoin-wizards
22:22:31sipa:gmaxwell, petertodd: better here i guess
22:23:13sipa:i'm certainly not up to date with all on txo/utxo commitments
22:23:49gmaxwell:petertodd: If you're only producing proof an output was mined, you also need proof that it wasn't spent yet. So in addition to an insertion ordered proof you need a balanced tree query for spentness. Vs with a utxo query you need only one balanced tree proof.
22:23:54petertodd:sipa: nothing interesting has changed since they were described AFAIK
22:25:37petertodd:gmaxwell: the TXO commitment tree is rewritten as things in it are spent; the proof that an output was mined is the proof that it was or was not spent yet (at a given height)
22:26:58gmaxwell:petertodd: How do you distinguish that from a utxo commitment then?
22:28:13petertodd:because a UTXO commitment tree removes items when spent and isn't insertion ordered
22:28:59gmaxwell:hm. insertion ordered makes it useless for validation without additional hint data.
22:29:50gmaxwell:petertodd: You need another index to find a particular txo by id in the insertion ordered list-- or otherwise you need to do a linear scan.
22:30:58gmaxwell:What purpose does not removing spent data serve?
22:32:16petertodd:why is that relevant? in the most pure version of TXO commitments spending a tx requires the spender to provide that index to everyone else as part of the proof - they don't need to know anything about it. in the less pure version where you still have a UTXO set the UTXO set itself contains that info for the unspent txo's
22:33:02sipa:petertodd: which is why gmaxwell said "without additional hint data"; in your pure version you always have that hint data
22:33:13sipa:but i'm still not clear on how that proves unspentness
22:33:17gmaxwell:just trying to understand what advantages the seemingly more resource intensive normaitive datastructure had.
22:33:22sipa:or how anyone proves unspentness at all, in the pure txo version
22:33:44gmaxwell:The 'pure version' usually implies the uninteresting bandwidth storage tradeoff.
22:34:10sipa:i'd like to understand the extreme first, without judging the tradeoffs
22:34:10gmaxwell:sipa: you can update a record without changing its position, the membership proof is everything you need to update the data too.
22:34:22petertodd:gmaxwell: obviously, hence having the UTXO set still
22:35:08gmaxwell:sipa: e.g. you prove membership in a big insertion ordered hash tree. the same path that shows membership is the records you need to update to change the value (e.g. add a spent bit)
22:35:16petertodd:basically in the impure version the UTXO set just becomes a pruned version of the true TXO commitment tree, pruning all spent TXOs, and unspent TXO's older than a certain date
22:35:51sipa:so the TXO set is really just a TXO + spentness structure, but ordered by insertion? ok
22:35:56sipa:TXO is a confusing name for that
22:36:05gmaxwell:yea, I was confused by that too! :)
22:36:25petertodd:sipa: it's a commitment of the state of every transaction output in bitcoin... didn't seem confusing to anyone the last time it was discussed
22:36:35petertodd:sipa: what's actually *stored* is orthogonal to what the commtiment is
22:37:03sipa:wait, it does not commit to the spentness?
22:37:34petertodd:it does commit to the spentness, that's what the state of a TXO is
22:37:55sipa:what do you mean by 'stored' then, and how is that different from the commitment?
22:38:22petertodd:sipa: your local copy of the tree can be pruned, while still committing to the same data
22:38:30sipa:oh sure
22:39:03sipa:i'm slowly starting to remember things :)
22:39:23gmaxwell:I am unsure of how you can produce a root update for your pruned copy without having a lot of storage overhead. E.g. the utxo set doesn't just need to have an index, it needs to have all the sister branches that would need to be changed to update that entry.
22:39:40sipa:but this (the pure version) requires wallets to keep track of their own txouts in the tree, and update their merkle paths as the txo state changes, so their proofs remain valid
22:40:25petertodd:gmaxwell: obviously you have something like log(n) overhead, not very interesting
22:40:41gmaxwell:sipa: I don't even think thats the most interesting downside of it. The interesting one is that every txin requires many kilobytes of proof transmitted. (in the 'pure' storgeless version).
22:41:22gmaxwell:petertodd: yea, but size a typical txout is ~= the size of a hash, it's non-trivial. E.g. on the order of a factor of 30 overhead. :(
22:41:46gmaxwell:(or really even worse, say 64... since the hight depends on the height of all history)
22:42:08petertodd:gmaxwell: given the huge difference between UTXO set size now and how fast it can grow with different usage patterns, that's not very interesting
22:42:15gmaxwell:I guess there is some common path compression that can be done... and it's necessary or every block requires O(utxo members) work to update the proofs.
22:43:01gmaxwell:petertodd: I think it's pretty interesting, especially since usage that bloats the utxo set can easily be softforked right out of the network. (e.g. block size limit on utxo growth)
22:43:36gmaxwell:talking about a utxo set size of tens of gigabytes is not very comforting.
22:44:02petertodd:lol, good luck coming to political consensus that any particular usage should be softforked out
22:44:17gmaxwell:(or even rather a _pruned_ size of tens of gigabytes, since the size bloat is related to the number of txo ever)
22:44:30petertodd:indeed, good luck even being able to identify such usage without collateral damage
22:45:31gmaxwell:dunno what you're thinking about "identify" ... it's just a simple incentives thing. If the a block can only create a maximum number of new utxo set increase then thats what fees correlate to and the market should optimize for efficient use of the resources.
22:46:26petertodd:if you have a set of people whose protocols have reasons to create new UTXO's, you just turned their usage into a DoS attack on everyone - good job
22:47:18gmaxwell:everyone creates utxos, users of bitcoin actually consume them too. In terms of resouce usage, utxo management is at least equally interesting to the blockchain history.
22:48:29petertodd:you're missing my point: if you have a subset of users who need to create UTXO's for a protocol, it's highly likely they'll outbid those whos transactions need to create UTXOs by default
22:50:32gmaxwell:I don't think you're thinking clearly about this. If you have a style of usage which is very inefficient and imposes costs on everyone else due to the inefficiency, and the system doesn't allow completely externalizing that cost... those inefficient users are going to be outbid by the efficient users that get more value per use.
22:50:46gmaxwell:Making a broken protocol makes the usage less valuable, not more.
22:51:11petertodd:you're assuming their usage is inefficient - from their point of view the cost may be a trivial part of the value of what they're doing
22:52:08gmaxwell:if they're going to outbid the other users, they're going to outbid the other users. Thats true independant of how much the true costs are hidden or distorted.
22:52:15sipa:so these high-value-application users will be paying me to spend my bitcoin utxos? sgtm
22:53:39petertodd:sipa: you'll end up with a blocksize limit, and a UTXO limit - the users for whome creating UTXOs is valuable will make creating UTXOs expensive, thus ending up in situations where there are bizzare limits on how many UTXOs blocks can create
22:54:29petertodd:sipa: note how any practical limit is going to be "a block can create ~k * UTXOs as it consumes" - which is a huge amount of UTXOs created every day
22:55:17sipa:i think it would be formulated as "each block may multiply the size of the UTXO set by 1.0xyz" or so
22:55:41sipa:so if there is really pressure for utxo space, people may end up paying others to consolidate their coins
22:55:43petertodd:sipa: no, it'd have to be an averaged limit, which makes it easy to DoS attack the network
22:56:14petertodd:sipa: because any sane k value for that multiple still lets the UTXO set grow rapidly
22:56:42sipa:each block may increase the UTXO set by N bytes
22:57:12sipa:if blockchain space growth is limited to linear, it makes sense to do the same for the UTXO set i guess
22:57:42petertodd:sipa: and that N bytes limit will have to be high enough to still grow the UTXO size rapidly, or you get situations where people's transactions are getting blocked
22:58:06sipa:then they'll have to pay more
22:58:08petertodd:equally, for anyone who needs a UTXO to be created, they can just as easily tack on some useless blockchain activity to get around that limit - again, "inefficiency" has nothing to do with it
22:58:47sipa:it's inevitable that if there is demand for a limited resource, that not everyone who would be able to get in at arbitrary price
22:58:57sipa:both for blockchain space and utxo set space
22:59:49petertodd:...which leads to pressure to have bigger limits, and now you're back to arguing for some very abstract "UTXO bloat is bad mkay!" political thing, ugh
23:00:24sipa:it's not abstract at all; it is directly correlated with verification efficiency
23:00:40petertodd:sorry, but to the average person that's an abstract argument
23:01:18sipa:i think the number of people to which this is an abstract argument is not significantly larger than the number of people to which blocksize limitation is an abstract argument
23:01:39sipa:there's just inertia
23:03:03petertodd:anyway, this discussion is a waste of time. If UTXO set commitments get implemented it's trivial for, say, ViaCoin to take that same codebase, tack on UTXO removal due to age, and combine it with TXO commitments and explore both scenarios. Meanwhile my advice to people using the Bitcoin protocol is always "Do what makes sense for your protocol and be deeply suspicious of anyone telling you to make your protocol less secure because it's 'good' ...
23:03:09petertodd:... for Bitcoin"
23:04:33sipa:would be a very interesting experiment to see in that case
23:04:45petertodd:in particular, if you make your protocol less secure now, you get attacked now, while if you make it secure now, the worst that happens is in the future you change it to work on a different chain, and the best that happens is you've done a lot less overall work