| 00:15:23 | bramc: | Hey everybody |
| 00:16:50 | bramc: | Last time I was in here, I forgot to explain how to make sequential proofs of work deterministic, and how this fixes a huge number of problems |
| 00:18:59 | bramc: | It turns out they can be made very compact in a way which is either lame trick or an elegant solution, depending on how you look at it. |
| 00:21:24 | bramc: | It's quiet in here |
| 00:21:37 | kanzure: | not many people in here respond to leading statements |
| 00:22:24 | kanzure: | speak your mind and then answers will be typed eventually (no quality of service guarantees, yo) |
| 00:22:49 | bramc: | Oh good, there's at least one person here |
| 00:24:13 | ajweiss: | what is a sequential proof of work? |
| 00:24:15 | bramc: | So there are three things I would like to discuss - (1) the spow stuff (2) possibilities for squeezing more performance when proof of storage, and (3) possibilities for gaming in my mixed pos/spow system |
| 00:24:54 | bramc: | A sequential proof of work is a proof of work which requires a certain amount of time to do, basically a proof that time passed between two events |
| 00:25:34 | bramc: | most pow is heavily parallelizable of course |
| 00:26:23 | bramc: | for the protocol I was talking about, it's very important that the spow be canonical on what it's operating on, because its hash is used as the beginning of the next generation |
| 00:27:08 | bramc: | So anyway, my idea for a spow goes like this: |
| 00:27:29 | bramc: | You start with a thing you want to do a spow on, and a work factor K. |
| 00:29:16 | op_mul: | gmaxwell: I'd like to think that for most cases, a SPV stepping stone is enough to cover up the initial sync time for wallet users. |
| 00:29:32 | bramc: | You then repeatedly hash your start thing K times, then take a single bit of the final value and append it to your initial string |
| 00:29:38 | kanzure: | sequential proof of work is http://diyhpl.us/~bryan/papers2/bitcoin/Publicly%20verifiable%20proofs%20of%20sequential%20work.pdf |
| 00:29:40 | phantomcircuit: | bramc, time lock puzzle |
| 00:30:12 | gmaxwell: | op_mul: I'd like that too, but it's not implemented anywhere yet. |
| 00:30:21 | bramc: | (hash functions don't generally operate on strings which aren't a bit length which isn't a multiple of 8, but that can easily be papered over) |
| 00:30:24 | op_mul: | gmaxwell: interestingly, an altcoin has it. |
| 00:31:06 | phantomcircuit: | bramc, give me a time lock puzzle in which a solver can cheaply prove that they solved the puzzle and the setup is non trusted (ie there is definitely a solution) and i will be your bestest friend |
| 00:31:10 | op_mul: | it's on a 0.6 branch or something, so I doubt portable upstream, but interesting it exists to begin with. |
| 00:31:26 | bramc: | phantomcircuit, no time lock puzzles are different. Those have a challenger set something up to be unlocked later. A spow is more like a slow hash which operates on something which was set up non-interactively |
| 00:31:47 | phantomcircuit: | maybe you have done that |
| 00:31:55 | bramc: | phantomcircuit, I have one but I'm 'cheating' a bit, bear with me |
| 00:32:37 | gmaxwell: | op_mul: one of the advantages of headers first is that it makes that 'easy'. |
| 00:33:08 | phantomcircuit: | if you can construct something as i've described above i suspect you can achieve a certain degree of censorship resistance which isn't vulnerable to witholding attacks at low cost by utilizing the ordering provided byt he bitcoin chain |
| 00:33:37 | bramc: | So you've now appended a single bit which took some amount of time to calculate to your initial string. You then hash that and repeat, adding one bit at a time until you've put together, let's say, 1k of bits. That's your spow |
| 00:33:37 | op_mul: | gmaxwell: of course. |
| 00:35:17 | bramc: | So this spow has the benefit of being nice and small, and can be spot checked quickly, but fully checking it requires as much CPU as doing the initial work did. But the checking can be done in parallel where the generation can't |
| 00:37:20 | bramc: | phantomcircuit, There's a subtly different thing which is a spow which isn't completely canonical but where the proofs can be checked quickly. I figured out some improvements to the paper kanzure linked to and have gotten the proof sizes down to around 100k. I probably won't be using that myself, but am happy if someone else can get some use out of it. |
| 00:37:44 | bramc: | Even have it implemented, in fact. |
| 00:39:53 | bramc: | Anyway, for my more compact spow the idea is that everybody when they get one spot checks it, then redistributes if it passes spot check. Peers can tell you if it failed their spot check, and if so you double-check the spot which they claim failed and then notify everybody you know about it. That way wrong proofs of work can't get far, and the fixes will inevitably converge on a truly fixed one. Also if you get two diffe |
| 00:39:53 | bramc: | rent alleged spows, comparing them is very easy: Take the first divergence between the two and check it. |
| 00:40:31 | kanzure: | are these trusted peers or what |
| 00:41:12 | bramc: | If you make the spow 1k long, that's around 8000 bits, so if it's a proof of, say, 200 seconds, checking a single bit only takes 50 milliseconds |
| 00:41:44 | bramc: | kanzure, untrusted peers, although sending out an invalid spow is considered a bit rude. |
| 00:42:47 | phantomcircuit: | 2015-01-15 00:41:58 UpdateTip: new best=00000000000000000cddde53e529a27518f219772827330232b52135ace13a31 height=328820 log2_work=81.362307 tx=50725654 date=2014-11-06 14:41:40 progress=0.837653 cache=4104599 |
| 00:42:51 | phantomcircuit: | 2015-01-14 23:57:37 UpdateTip: new best=00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048 height=1 log2_work=33.000022 tx=2 date=2009-01-09 02:54:25 progress=0.000000 cache=1 |
| 00:42:57 | bramc: | And checking bits can be done in parallel |
| 00:43:07 | bramc: | phantomcircuit, what? |
| 00:43:15 | gmaxwell: | bramc: context is before you joined. |
| 00:43:24 | kanzure: | http://gnusha.org/logs/2015-01-14.log |
| 00:43:25 | gmaxwell: | phantomcircuit: what did you fix? |
| 00:43:48 | phantomcircuit: | gmaxwell, i forced fCheckScript = false |
| 00:43:53 | phantomcircuit: | and have perf records |
| 00:44:19 | sipa: | phantomcircuit: that'd be interesting |
| 00:44:23 | gmaxwell: | hm. So really the last chunk there was actually scriptsl but in the small span at the end? hm. an hour of them? |
| 00:44:40 | gmaxwell: | your prior run was 4836 seconds, right? |
| 00:44:43 | phantomcircuit: | gmaxwell, the day wrapped around |
| 00:45:42 | gmaxwell: | I know, I can date math, it was about 45 minutes this run. vs 80. |
| 00:45:50 | phantomcircuit: | no you're right |
| 00:45:54 | phantomcircuit: | 2661 seconds |
| 00:45:59 | gmaxwell: | 35 minutes of signature checking is surprising. |
| 00:46:05 | phantomcircuit: | the only thing i changed was fScriptchck=false |
| 00:46:13 | gmaxwell: | I believe you. |
| 00:46:16 | phantomcircuit: | well that and perf |
| 00:46:17 | sipa: | how many cores? |
| 00:46:23 | gmaxwell: | infinity |
| 00:46:24 | phantomcircuit: | i cant imagine perf made it faster... |
| 00:46:33 | phantomcircuit: | sipa, on this system 8 cores |
| 00:46:46 | gmaxwell: | oh this isn't one of the 40 core hosts or whatever? okay. |
| 00:46:50 | sipa: | probably... around 100us for a validation? |
| 00:46:51 | phantomcircuit: | the run before had a checkpoint at 338856 |
| 00:46:55 | gmaxwell: | in any case the prior run had a checkpoint at 338856. |
| 00:47:11 | sipa: | 100 wall-us, that is not 100 cpu-us |
| 00:47:13 | gmaxwell: | so it would have only verified about 120 blocks worth of signatures. |
| 00:47:36 | gmaxwell: | we should probably move to #bitcoin-dev |
| 00:47:37 | sipa: | 35 minutes of sigchecks at 100us per check: 10M transactions |
| 00:48:05 | kanzure: | whoops my last link was wrong, i meant http://gnusha.org/bitcoin-wizards/2015-01-14.log |
| 00:48:55 | bramc: | gmaxwell, I looked into the possible types of attacks you asked about, it turns out that there's some pooling advantage to be had but not much, and there's a neat trick which can effectively double storage proof size but it may be impractical |
| 00:50:57 | bramc: | The doubling is a neat trick. Let's say you have a trillion locations to store keys in and doing a million key generations is fast. |
| 00:55:06 | bramc: | When evaluating a single salt you can instead of deriving one key from it derive two. and view the buckets of places you would like to be closest to as being arranged in a square. For a given salt, let's say that the locations it generates keys for are (x, y) and (z, w). You put that salt in either (x, w) or (y, z) |
| 00:55:24 | bramc: | Whichever one happens to not already be filled. |
| 00:59:40 | bramc: | Then when you need to find a nearest match for a particular hash root, check everything in its row and column. That's 2 million things to check, which should be fast, and it merely double the amount of cpu necessary to fill all of storage. This comes with some headaches of course. Everything has to be bucket sorted very precisely, instead of merely sorted. And the real killer is all the seeks it has to do, that's likely |
| 00:59:40 | bramc: | to make it utterly impractical on physical hard drives. |
| 01:03:22 | bramc: | You can mitigate all the seeking by pooling things up a bit. For each salt derive a thousand keys from it. If we subdivide the terabyte into a million separate pools, each two of those keys will probably be of the same pool. We then apply the same trick within each pool, organizing into a thousand by thousand square and positioning the found key appropriately. |
| 01:05:21 | bramc: | The total number of operations to check keys will still be two million, and if the number of high level pools is set high enough then you should be able to pull the whole pool into memory and not have to deal with all those seeks. It still requires more accessing though, and dramatically increases the setup time of everything (a factor of a thousand in the example I gave) still it might be worthwile for some setups |
| 01:06:11 | bramc: | The good news is that this all stops working above a factor of two, or if not there then at some small constant factor. |
| 01:06:49 | bramc: | phantomcircuit, I'm happy to help you out with the improvements in that paper if you're interested. |
| 01:07:45 | phantomcircuit: | bramc, interested but otherwise occupied :) |
| 01:10:25 | bramc: | Okay. It's hard to gauge what reaction people are having when I'm monologing |
| 01:22:44 | amiller: | im looking into cryptonote a bit today, i have two observations |
| 01:23:25 | amiller: | first, when selecting 'fake' transactions, it seems to choose uniformly at random throughout history (among txouts with the right denomination) |
| 01:23:36 | amiller: | seems like /join #cryptonote |
| 01:23:37 | amiller: | asdlfkjlsdkfj |
| 01:24:21 | amiller: | seems like that's suboptimal because, there is probably some natural distribution of how long someone waits before moving their coins, and i imagine it's in general pretty short |
| 01:24:43 | amiller: | so i think it would be better to sample from some distribution where more recent coins are more likely to be chosen |
| 01:25:01 | MRL-Relay: | [othe] yeah we are working on that, its indeed "suboptimal" |
| 01:25:22 | amiller: | oh yeah, monero research labs, hi |
| 01:25:35 | smooth: | exactly, we have a paper on that literally in progress |
| 01:25:45 | smooth: | and some other such issues |
| 01:26:00 | amiller: | the second is, you can probably use authenticated data structures to have a light client |
| 01:26:06 | amiller: | regardless of what sampling policy you choose |
| 01:28:25 | smooth: | btw for bitcoin, the average move time (weighted by quantity, which isn't exactly the same thing) is about 7 days |
| 01:28:36 | smooth: | so yes entire history is way off |
| 01:29:13 | amiller: | this means that in general it's pretty likely that for most transactions, the *most recent* among the mixins is the 'real' one and older ones are fake. |
| 01:29:20 | smooth: | correct |
| 01:29:24 | amiller: | if you have real data, it seems like fitting a distribution to that and sampling from it is optimal |
| 01:29:50 | smooth: | there are some ways of doing that but there is a risk of poisoning |
| 01:29:59 | amiller: | poisoning? |
| 01:30:36 | smooth: | if you are sampling from the blockchain, someone could put in a lot of transations that spend at a certainly rate, encouring you to change your distribution |
| 01:30:42 | smooth: | *certain rate |
| 01:31:01 | amiller: | oh, yeah that counts as 'not real data' in what i meant, i guess i wouldn't recommend actually doing that based on real time data |
| 01:31:16 | smooth: | then its hard to have 'read data' |
| 01:31:21 | smooth: | *real |
| 01:35:16 | amiller: | ok well, the basic idea for a light client would be to have an authenticated data structure for the txos |
| 01:35:43 | amiller: | where you can query the number of outputs for a given amount, |
| 01:36:26 | amiller: | then, the client picks random indices of fake outputs (and adds in the index of its own coin, which it should know already), and queries the public key associated with those outputs |
| 01:38:08 | amiller: | a pure/functional data structure that does that would be a search tree (or trie, i dont care!!) for amounts, and each of those leaves would be the root of a tree in index order, where each node also stores the number of elements in its child |
| 01:41:20 | amiller: | so the merkleized version of that would let the client check that any results returned match the root hash committed in the block or coinbase signed by a trusted person or whatever |
| 03:10:08 | Pan0ram1x: | Pan0ram1x is now known as Guest18727 |
| 03:26:49 | bramc: | Nobody wants to talk about the squeezing more out of storage tricks? They're so much fun. |
| 03:28:34 | gmaxwell: | Sorry! busy week for me, I've only had a few moments to glance in. (Actually I came up with some very neat optimizations in this space; which you might have thought of or come up with too.. but no time to talk now) |
| 03:33:18 | bramc: | gmaxwell, Happy to talk when you can. The short of it is that cstos (CPU space tradeoffs) are possible but they get you maybe a factor of 2 of space, and there's a cheesy but serviceable way of doing spows which makes them canonical which blunts most of the attacks based on doing multiple spows. |
| 04:04:00 | maaku: | gmaxwell is such a tease |
| 06:59:16 | fluffypony: | amiller: do you mean, then, that the only thing the hypothetical lightweight client needs to retain is a list of output denominations for which there are available utxo's it can mix with? |
| 06:59:44 | amiller: | fluffypony, even that could probably be dispensed with, but yes |
| 07:00:13 | fluffypony: | doesn't that mean it still has to trust nodes it connects to to provide it with valid utxo's? |
| 07:01:31 | amiller: | no, that's the point of utxo commitments |
| 07:02:07 | amiller: | imagine that each block header contains the merkle root of a tree containing all the txos (in cryptonote there's no way to tell apart a utxo from a spent txo so just txos) |
| 07:04:52 | fluffypony: | (although tangentially to that we have discussed a scenario where we may want to blacklist certain utxos from being used for mixing in future, for whatever reason) |
| 07:05:36 | amiller: | yeah, merkle data structures are pretty flexible so that's probably doable |
| 07:43:54 | DougieBot5000_: | DougieBot5000_ is now known as DougieBot5000 |
| 09:05:15 | verne.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 |
| 09:05:15 | verne.freenode.net: | Users on #bitcoin-wizards: andy-logbot bepo|afk vdo coiner adam3us vmatekole go1111111 HaltingState waxwing delll iddo benten tlrobinson nanotube cletus11 justanotheruser [7] Guest18727 d1ggy_ qwopqwop Dr-G3 Dizzle Tjopper Shiftos huseby cryptowest PaulCapestany PRab hktud0 weex jgarzik dasource mortale Xzibit17 c0rw1n rasengan prodatalab Oizopower d9b4bef9 earlz zooko lclc shesek mbelshe devrandom EasyAt BigBitz hashtagg op_mul forrestv lnovy Emcy Logicwax nsh Transisto |
| 09:05:15 | verne.freenode.net: | Users on #bitcoin-wizards: wiz null_radix samson_ copumpkin yoleaux Luke-Jr btc__ artifexd OneFixt hguux_ Muis jbenet Taek42 pi07r mappum coryfields_ CryptOprah kumavis BrainOverfl0w wumpus midnightmagic Graftec nick1234abcd__ Krellan yrashk LarsLarsen MRL-Relay michagogo kyletorpey ahmed_ phedny warptangent asoltys_ isis HM2 berndj sadgit maaku tacotime so fanquake harrow` kanzure crescendo sneak azariah Guest38445 comboy K1773R heath helo jaromil eric btcdrak |
| 09:05:16 | verne.freenode.net: | Users on #bitcoin-wizards: Apocalyptic espes__ v3Rve petertodd @gmaxwell sdaftuar lechuga_ amiller roasbeef Anduck BananaLotus bobke jcorgan s1w Meeh nuke1989 epscy atgreen Fistful_of_Coins poggy_ tromp__ starsoccer optimator throughnothing wizkid057 fluffypony livegnik gribble kinlo andytoshi gwillen @ChanServ gnusha hollandais burcin luny spinza Nightwolf a5m0 phantomcircuit fenn warren nickler brand0 mr_burdell otoburb sl01 morcos Keefe JonTitor Graet ajweiss cluckj |
| 09:05:16 | verne.freenode.net: | Users on #bitcoin-wizards: NikolaiToryzin thrasher` jaekwon_ bbrittain SubCreative mkarrer_ brad___ cfields ebfull tripleslash grandmaster Eliel catlasshrugged xabbix_ cjc DoctorBTC bosma dgenr8 BlueMatt [d__d] Iriez Hunger- gavinandresen dansmith_btc Cory Dyaheon- pigeons tromp AdrianG Alanius smooth ryan-c TD-Linux catcow |
| 09:16:22 | fluffypony: | http://www.theregister.co.uk/2015/01/14/nsa_sorry_we_borked_nist_encryption_well_sorry_we_got_caught/ |
| 12:17:33 | fluffypony: | also this was an excellent talk: http://media.ccc.de/browse/congress/2014/31c3_-_6240_-_en_-_saal_g_-_201412271400_-_reproducible_builds_-_mike_perry_-_seth_schoen_-_hans_steiner.html#video |
| 13:24:57 | NewLiberty_: | NewLiberty_ is now known as NewLiberty |
| 14:30:51 | op_mul: | I've seen the topic of output selection come up a few times here, and the general answer is that there's no answer that's *ideal*. |
| 14:31:48 | op_mul: | I came up with a mildly novel attack against some forms out output selection (used by a few wallets), where the software just orders all UTXO by their age and then consumes them sequentially. |
| 14:34:10 | op_mul: | given two transactions, you can work out if they are maybe related or not just by the age of the outputs they consume. if a later transaction consumed outputs older than an earlier one, they aren't made by the same wallet. |
| 14:35:46 | op_mul: | only works if you have some other hints about the users software (human leaks, other features of a transaction that might reveal it), but a bit of fun none the less. |
| 15:09:00 | earlz: | Would it be useful if teh block Nonce field was upgraded from 32bit to 64bit? |
| 15:09:31 | earlz: | There is extranonce, but it seems like a bit of a hack and requires recalculating the merkelhash and is generally more complicated |
| 15:32:24 | bosma_: | bosma_ is now known as bosma |
| 16:13:54 | kanzure: | op_mul: i think there are ideal answers for output selection depending on the particular use... and i'd agree with you that it's unlikely that there's an ideal single solution that works across all possible uses. |
| 16:15:15 | op_mul: | * op_mul nods |
| 16:15:26 | op_mul: | I'd just never thought of it as a privacy risk before |
| 16:30:40 | hearn: | op_mul: i wrote an article on the topic some time ago: http://www.coindesk.com/merge-avoidance-privacy-bitcoin/ |
| 16:30:51 | hearn: | bitcoinj is one of the wallets that just works through utxos in age order, mostly |
| 16:31:16 | hearn: | the idea was to maximise priority so transactions could be free as often as possible, but of course that never really happened, free txns are pretty broken at the moment |
| 16:32:23 | op_mul: | hearn: oh good to know |
| 16:32:53 | hearn: | i'd like to bring free txns back at some point because it's a big selling point for bitcoin, the difference between "tiny fee" and "free" psychologically is huge |
| 16:32:59 | hearn: | but it needs a bunch of changes |
| 16:35:01 | op_mul: | when does bitcoinj not use oldest first selection? |
| 17:19:59 | justanotheruser: | Given that we have a UTXO merkle tree in a block, is it possible for a thin client to pay to a think client without a server? It is pretty obvious how a full node could pay to a thin client and tell them which block and which branch the transaction is, or how a thin client could pay a full node without a server. Is there a way to do it where both the payer and the receiver are serverless thin clients? |
| 17:47:16 | hearn: | op_mul: it can be customised by the app |
| 17:47:46 | hearn: | op_mul: the default selector is pretty dumb though. we never implemented anything as complicated as satoshi's knapsack solver. |
| 17:48:12 | hearn: | my original plan was to investigate using general constraint solvers, but in the end people just ended up attaching a fee for every tx. the amounts are so small that it wasn't the lowest hanging fruit |
| 17:48:14 | hearn: | people have other concerns |
| 17:51:18 | zz_lnovy: | zz_lnovy is now known as lnovy |
| 18:31:13 | samson2: | samson2 is now known as samson_ |
| 21:57:16 | nsh: | does anyone have a proof-of-existence service that uses OP_RETURN yet? |
| 22:37:35 | justanotheruser: | nsh: the first result for proof of existence does |
| 22:39:12 | nsh: | \o/ (sorry for lazyasking) |
| 22:39:48 | nsh: | * nsh wonders if there's one that will host the file so it's google indexable too |