--- Log opened Fri Oct 25 00:00:42 2013
00:29 < adam3us> musing (again) about whether there is an inherent need to order transactions via miner voting and longest chain algorithm
00:31 < adam3us> that is because the semantic is defined as first transaction is correct (and there is not really a first in a distributed system with unreliable network and untrusted nodes) so then voting and longest chain creates a proxy for first with a sequence of votes from block lottery winners
00:33 < adam3us> consider an alternate semantic: absence of a double spend implies validity, presence of double-spend implies invalidity, transaction aborted, and eg sender loses money sent (and fee)
00:34 < adam3us> in a network with that semantic, security relies on unjammability
00:34 < adam3us> but bitcoin already relies on that (otherwise hacked routers that can selectively delete packets in front of big pools can create problems)
00:34 < adam3us> no one awake huh?
00:38 < Luke-Jr> adam3us: and what of a double spend that occurs hours later?
00:38 < adam3us> yeah so i guess that would be defined as invalid
00:38 < Luke-Jr> retroactively invalidating the current transaction?
00:38 < adam3us> it doesnt give as much user choice of how many confirms to expect
00:38 < adam3us> no ignored as too late
00:38 < Luke-Jr> "too late" won't come to a consensus
00:39 < adam3us> well i was thinking if the spend is mined into a block as now, then you have a timestamp on the spend
00:39 < adam3us> then say both parties agree to 6 confirms
00:40 < adam3us> and so long as there are no double spends on the network in that time the transaction is deemed valid
00:41 < adam3us> so rather than different views of which transaction came first in a double spend triggering orphans (if the conflicting blocks happen close enough to at the same time)
00:41 < adam3us> they are valid, they just invalidate the conflicting transaction (if hey happen within 6 blocks of the original transaction) say
00:43 < adam3us> the next block mined on top refers to both branch hashes, as they are no longer considered to conflict
13:10 < jgarzik> gmaxwell, amiller, anyone played around with CP-ABE + bitcoin, that we're aware of?
13:12 < sipa> cp-abe?
13:12 < petertodd> adam3us: re: double-spends, remember that the blockchain serves as proof-of-publication: by defining the blockchain as where transactions are stored, participants can use their knowledge of the blockchain to be sure they know of every valid transaction in existance, and thus they know about all double-spends.
13:13 < petertodd> adam3us: dealing with attacks via information hiding is something I'm been thinking about a lot lately re: ideas to "shard" the blockchain data so you only have to keep up to date with part of it
13:17 < petertodd> adam3us: (by "they know about all double-spends", remember that you could make a bitcoin-like system where double-spends *are* allowed in blocks, but are invalid and are just useless data! it's only an *optimization* that the bitcoin protocol doesn't allow double-spends to be in the blockchain!)
13:17 < jgarzik> sipa, https://en.bitcoin.it/wiki/Distributed_markets#Pay_to_policy_outputs
13:19 < adam3us> petertodd: well maybe (about optimization), tho Luke-Jr said well what if the spend comes in later, when do you declare it too late to add a double-spend (invalidating a transactoin)
13:20 < amiller> jgarzik, i don't know of anyone that's used it, no
13:20 < amiller> jgarzik, i think i understand it pretty well and it's not too complicated
13:20 < amiller> i mean i don't see any obstacle to using it except you'd have to support a diff signature type
13:21 < amiller> you'd have to have a trusted issuer anyway though
13:21 < petertodd> adam3us: oh, your proposing something where both transactions are invalid?
13:21 < amiller> so i can't imagine the setup model is something anyone would buy
13:22 < adam3us> petertodd: well musing about the implications of that model yes, if there would be any advantage to be had by exploring it
13:22 < amiller> it's a lot of extra effort and complexity for having a trusted third party that could just be online and sign the transactions anwyay
13:22 < adam3us> why is a block so big anyway that 1MB starts to be a problem?  doesnt it refer to the txids rather than include the text of the tx?
13:22 < petertodd> adam3us: right, problem there is it lets you grief anyone getting paid by the transaction. I've proposed stuff kinda like that, but only in the context of fidelity bonds
13:22 < jgarzik> amiller, true
13:22 < jgarzik> amiller, I was thinking of it in context of oracles and agents
13:23 < adam3us> cant a block therefore refer to a huge number  of txs relatively compactly in a merkle tree? w
13:23 < petertodd> adam3us: with a better scripting language you could have a system where proof-of-double-spend can be used to destory the bond
13:23 < adam3us> yes thats true
13:23 < sipa> adam3us: a block's size refers to header + tx body
13:23 < sipa> adam3us: that doean't mean it needs to be traferred that way
13:24 < sipa> but the rule for limiting block sizes uses that
13:24 < jgarzik> I want to play with sending block header + list of TXs via UDP
13:24 < jgarzik> er, header + coin base + list
13:24 < petertodd> adam3us: Yes, but miners still have to have the bandwidth to process every transaction; this leads to what I call the censorship problem: if mining can't be done in a low-bandwidth way, mining has to be done out in the open, hence it gets regulated. We can design Bitcoin so multiple low-bandwidth participants can collectively validate the blockchain, but unless they can colabborate to also mine blocks transactions can be censored.
13:24 < adam3us> petertodd: there are signatures that are one-show, show two signatures you reveal the private key, that might be some discouragement (though a one use private key is inherently fairly harmless once its spent)
13:26 < adam3us> sipa: so why the discussion of limiting block sizes to 1MB if its just a compact collection of references to already sent transactions?
13:26 < petertodd> adam3us: yeah, lots of possibilities. Note w/ fidelity bonds that they actually need a real-time proof-of-publication system - if you don't have that, you can't know if the total amount of transactions being done right now attempting to defraud people (guaranteed by the bond) greatly exceeds the value of the bond. :(
13:27 < sipa> adam3us: because the rule already exists, and changing it is a hard fork
13:27 < sipa> adam3us: btw, the current p2p mechanism does in fact send a block in full
13:27 < petertodd> adam3us: remember too that currently there's way to do partial validation of blocks, or to product short proofs that a block is invalid/fraudulnet. If the blocksize is much larger, it won't be possible to valiate the blockchain at all without a low-bandwidth internet conenction because you won't be able to keep up.
13:27 < adam3us> sipa: does that mean data gets sent over the wire twice?
13:27 < sipa> but it's not an actual requirement, and changing the protocol is easy
13:27 < sipa> adam3us: yes
13:28 < sipa> but even if the protocol is changes not to send duplicates (like bip37 does), the hard rule remains defined over the actual block size
13:28 < adam3us> sipa: doh :) but changing that would mean blocks can be as big as you want practically and so maybe reduce this need for mining fees, though other than block size, its also about throttling spam (low value tx)
13:28 < petertodd> adam3us: sending full blocks has some advantages though in that it removes incentives to play games with propagation to disadvantage smaller miners. makes the system more reliable too as the worst-case and average-case propagation times are closer
13:29 < sipa> i am very uncovinced that the p2p tx broadcast mechanism will remain the primary way of delivering transactions to miners
13:30 < petertodd> sipa: sadly your probably right... out-of-band payments is really nasty this way, because it could be a strong incentive for pools to remain large :(
13:30 < sipa> yup
13:30 < petertodd> sipa: like, imagine if the payment protocol is widely deployed, and merchants use out-of-band payments extensively to get their zero-fee payments from their customers mined: p2pool wouldn't be able to earn fees at all
13:31 < adam3us> petertodd, sipa: i was noticing when playing with committed transactions, that you dont need to send the values, nor recipients to the miners; only a commitment to them (hash) and a commitment to the senders address
13:31 < petertodd> sipa: I've got what appears to be a pretty good way to do decentralized out-of-band payments though, but it's way more complex than the centralized way :(
13:31 < amiller> jgarzik, uh, well i'm not exactly sure i understand what you mean by oracles / agents there
13:32 < amiller> jgarzik, i guess you just mean semi-trusted parties that aren't the end-users who the protocol actually benefits, but like a server with limited capabilities
13:32 < adam3us> petertodd, sipa: reduces attacks if the miners know as little as possible about what is going on
13:32 < jgarzik> amiller, pretty much
13:34 < amiller> i still feel like calling them autonomous agents or oracles is misleading language that deliberately conveys some kind of additionally trustworthiness that isn't warranted
13:34 < amiller> </monthlyscheduledrant>
13:34 < petertodd> adam3us: ooh, reminds me re: commited txs: I've got an idea where you'd make transactions have commitments of previous ones with a merkle-mountain-range-like scheme so you could efficiently reference any previous transaction up to the genesis block. This is easiest to understand if transactions can only have linear history, but a dag history is doable too. Anyway, wallet software would receive that history to know the coins are valid, thus pushing validation directly to the users. Obviously some way of pruning that history is important, SCIP is heavy-weight and complex but could work.
13:35 < sipa> thus pushing v[...]
13:35 < petertodd> adam3us: yes, but nothing other than intertia prevents miners from demanding that users reveal enough info to let them know what transactions actually are; again, it's easy to imagine governments regulating mining pools and forcing them to do this.
13:37 < petertodd> adam3us: you really need to keep it possible to mine by small parties to keep that balance towards decentralization - helps the larger pools resist regulation too if they can point out that the smaller miners that can't easily be regulated will just out-compete them if the government forces the larger ones to do things like 51% attack the non-censoring miners
13:37 < petertodd> *government tries to force
13:38 < adam3us> petertodd: it reduces bandwidth if you can send commitments only to the block chain, because ok to send previous tx history back to the last snapshot (or to genesis) is a bit of a privacy leak, its still better than now; and its more efficient to send that to each recipient than broadcast it to everyone
13:38 < adam3us> petertodd: yep, that was exactly the motivation for committed tx - users can yank a 51% miners chain causing him to lose money all day long
13:38 < petertodd> adam3us: yup, commitments with compact proofs of any part of the previous tx history are one form of sharding validation effort.
13:39  * petertodd needs to come up with a good directed acyclic graph version of merkle mountain ranges
13:41 < petertodd> adam3us: wait, explain to me how users "yank a 51% miners chain"?
13:41 < adam3us> petertodd; y'know with homomorphic encrypted values & committed transactions combined, at least the privacy invasion of the full tx history revealed to each recipient is less - you dont see how much money each user has
13:41 < petertodd> adam3us: good point
13:41 < adam3us> petertodd: ah so lets see how did that go, ah yes so you want to make a payment and you're wikileaks (canonical example of unpopular extra-legal blocking)
13:42 < adam3us> petertodd: so you make your payment, wait a few blocks, reveal it; now the 51% miner has to discard 2 blocks of profit and compete against himself; rinse & repeat
13:43 < petertodd> right, and my point is always the government response is to target public bitcoin users and first demand that even though the system is private, they use this new modification of the bitcoin protocol that also sends enough information along-side a transaction to always reveal the contents
13:43 < adam3us> petertodd: that assumes you ever reveal the tx to the network, you could let them circulate in committed form in which case no one not in the tx history knows who paid who
13:44 < amiller> adam3us, suppose you had aribtrary zero knowledge and two party computation or whatever
13:44 < amiller> can we come up with an idealized definition for a private public ledger?
13:44 < amiller> i've been trying to think of a good way to explain this, regardless of the actual implementation efficiency
13:44 < petertodd> then you start getting the pools you can control to apply preferential treatment to non-anonymous transactions, for isntance you only mine ones like that, but still extend blocks otherwise. rinse and repeat, until you get to the point where the pools can do direct 51% attacks on the ones that don't.
13:44 < amiller> no one should need to know anyone's transaction balances
13:44 < adam3us> petertodd: well its not that private in the sense that anyone in the payment chain can reveal stuff that came before, so they are free to make a subpoena, most random merchants and users have no incentive to protect privacy of an actual crime with victims
13:44 < petertodd> it's only the inability of government to control at least 50% of the hashing power that prevents that stuff
13:44 < amiller> a transaction between two people should change their balances in a way that both know, but neither should learn the balances of the other
13:45 < amiller> but everyone should learn the transaction is valid
13:45 < amiller> can you do that even abstractly?
13:45 < petertodd> adam3us: yup. the unhiding data could be done by requiring it to be broadcast encrypted to a government controlled pubkey
13:46 < petertodd> adam3us: "Nothing to fear! You're tx's are private unless a court-order is served and the priv-key is used to decrypt them."
13:46 < adam3us> amiller: maybe zerocoin with homomorphic values? (with fixed value is stupidly inefficient send 1,000,000 1c coins to send $10k?)
13:46 < amiller> btw there's a fully open source alternative to pinocchio/tinyram out https://github.com/srinathtv/pantry/
13:46 < adam3us> petertodd: screw that :)
13:47 < amiller> adam3us, well homomorphic values isn't enough i don't think
13:47 < amiller> because homomorphic encryption uses a single key
13:47 < adam3us> petertodd: we see where that ends, apriori wire tap and data fishing on everyone on the planet in utah; even the EU is right now voted to block SWIFT data sharing
13:48 < petertodd> adam3us: yes, but the only thing stopping it is that it's possible to mine outside of government control! Reality is with the current system, even with TXO commitments and fraud proofs, at some point a large blocksize will lead to that scenario.
13:48 < amiller> perhaps if i want to send you some money and we want ot prove it's valid to everyone else but we don't want to reveal our balances to each other, we could use a two-party computation that computes the homomorphic function or something
13:48 < adam3us> amiller: yes you can do that (encrypted values add up, without learning other balance) see thread on homomorphic value using schoenmakers range proof
13:49 < adam3us> amiller: it works because there are two values in a pederson commitment c1 = v1*G + x1*H
13:49 < adam3us> v1 is the value, x1 is a key that is not revealed
13:49 < adam3us> amiller: no one knows DL(G,H)
13:50 < adam3us> https://bitcointalk.org/index.php?topic=305791.msg3277431#msg3277431
13:51 < petertodd> adam3us: so how much larger would transactions be with this homeomorphic stuff?
13:51 < adam3us> its not really encrypted as such, just committed in a extened-schnorr provable form (bi DH form)
13:51 < adam3us> petertodd: well like I said on the thread best I got so far was 1K-2K per value depending n the precision of the coin vaue
13:52 < amiller> i still don't see how you get the range proof
13:52 < petertodd> petertodd: ok, so that's 1K-2K per txout then basically right? is that linear with the number of txouts?
13:52 < amiller> but i'll read more and try to undersatnd it
13:52 < petertodd> does it handle any combination of # of txins and # of txouts?
13:53 < adam3us> its 3+2m values where m is the number of bits of mantissa (precision) of the bitcoin value and a value is 256-bit/32-byte
13:53 < petertodd> (although I guess you could use a merkle-sum-tree to combine txin values and split txout values)
13:53 < adam3us> so I suggested eg 20-bits (1665bytes) or 27-bits 2016bytes
13:54 < amiller> ok so you do a range proof with roughly one value per bit
13:54 < adam3us> petertodd: amusingly i think you could even validate the entire ledger, add it all up and check it comes to however many coins issued so far
13:54 < adam3us> amiller: yes
13:54 < amiller> how do you communicate the value transferred to the other party?
13:54 < adam3us> no 2 values
13:55 < adam3us> 3+2m
13:55 < adam3us> just tell them
13:56 < adam3us> amiller: out-of-band or encrypted to public key if using the block as a store-and-forward channel
13:56 < amiller> okay
13:56 < adam3us> amiller: the fee is public, rest homomorphic
13:56 < amiller> (i apologize i have a hard time parsing all your posts but i think the idea works out)
13:57 < adam3us> amiller: well actually you can mix encrypted & clear values
13:57 < amiller> the pedersen commitments are only homomorphic with respect to addition aren't they
13:57 < adam3us> amiller: eg if you want to hide the value of your balance, but dont care much to hide the actual payment amount
13:57 < adam3us> amiller: yes... well and by a public constant multiplication
13:57 < adam3us> amiller: so you can actually do ratios also from that
13:58 < amiller> help me understand the range proof
13:58 < amiller> start with notation for like, one input and two outputs
13:59 < adam3us> amiller: its knarly :) the basic idea is you need to prove v from vG+xH with v < 2^m
14:00 < amiller> i'll be happy if i can understand that a) ZK proof that the sum of outputs = sum of inputs, without overflow, b) the receiver learns one of the output values, but not the other output or the input, and c) both outputs are in a form suitable to be used in subsequent transactions
14:00 < adam3us> amiller: its schoenmakers protocol, I just optimize the application of it
14:00 < adam3us> amiller: yes
14:00 < adam3us> amiller: so call the bits of v = v_m ... v_1
14:01 < adam3us> now you prove separately that v_i is either 0 or 1 using generic ZKP of OR which is to introduce a degree of flexibility where the prover can intentionally forge one of the two proofs (but not both) as c=H(params), c1 = random, c2 = c xor c1 prove wrt those 2 challenges
14:03 < amiller> ahhhhh
14:04 < adam3us> amiller: and the rest is basically to obscure it and then there's a verification relation involving 2^j and the random values committed to and showing sum xi = x and you're good to go :)
14:04 < amiller> i think i remember how to do ZK of OR...
14:04 < adam3us> amiller: then i optimized the heck out of the serialization, and what needs to be unique, can be derived from a seed, reused, computed (pub key from sig with schnorr) etc
14:05 < adam3us> yeah you just forge the one that is wrong and choose c1 as a result of that computation then set c2 = c-c1 mod n and do a real proof on that ne
14:08 < adam3us> amiller: the way you avoid the sender knowing too much about the receivers secrets is you create a null value 0G+x0*H aka x0*H (and prove that is true using a schnorr sig) and then the sener adds the payment to it, and yet the sender does not know x0
14:09 < adam3us> amiller: so eg the sender could send 5*G+x1*H and the result is 5*G+(x1+x0)*H and the sender doesnt know x0; sender has to send 5, x1 to recipient out of band or encrypted
14:11 < adam3us> amiller: you can also do proofs of equivalence of discrete log and auditable encryptin so I think you could probably validate that E(5),E(x1) matched the coin, though I didnt work out the details on that and it doesnt seem necessary because the recipient doesnt have to use the input
14:13 < adam3us> petertodd: "is that linear with the number of txouts?" yes; you do a range proof on each output, but you dont need to when you use teh output as the input to a following transaction as its already done
14:14 < adam3us> petertodd: "does it handle any combination of # of txins and # of txouts?" yes, and some of them can be unencrypted optionally (eg the fee)
14:16 < petertodd> adam3us: ok, sounds like this is a bit of an issue with large transactions, as there's a trade-off between "publish the whole tx" as your fraud proof, and having more complex merkle trees
14:16 < petertodd> see, we were thinking of doing merkle sum trees extending into the transaction txins and txouts, which is cheap with un-hidden values, not so cheap with a homeomorphic system
14:19 < adam3us> petertodd: "yes, but the only thing stopping it is that it's possible to mine outside of government control! Reality is with the current system, even with TXO commitments and fraud proofs, at some point a large blocksize will lead to that scenario." i think we have problems like that, and seemingly a number of people dont recognize it yet; I am also not sure such an asic friendly mining function is good either
14:20 < adam3us> petertodd: in an ideal world one could remove miners, and everyone with whatever power can direct mine for their respective tiny reward
14:20 < petertodd> yes, ASICs are very much the other part of that problem....
14:22 < adam3us> petertodd: you can do better than scrypt(iter=1) - I saw some folks on the forum were proposing a mix of 16 aes and 16 sha3 finalists to increase chip layout; also something dynamic could help; apparently dan kaminsky has some idea about a x86 proof of work which would be inefficient on non x86
14:23 < petertodd> adam3us: If I were to design bitcoin 2.0, I'd design a system where you lose 1% of the value of your coins every year to pay for security, mining can't be outsourced via some type of scheme where rewards can be stolen by whomever did the mining, mining could be done on a small scale, (aka what p2pool does for bitcoin, though probably not that mechanism) and the pow function was commodity hardware friendly (hopefully no worse than 2x or 3x less cost effective than custom asics)
14:23 < adam3us> petertodd: so about that (no mining pools) is there some way to rely only on a time-stamp server or beacon without having miners validate anything
14:23 < petertodd> yeah, I'm dubious about anythign that targets a chip architecture, too easy to just make an asic that optimizes the architecture, and archs change over time anyway
14:23 < petertodd> I think only mem-hard mining has any hope of working
14:24 < adam3us> petertodd: yes - i think the people who defend hashcash-sha256^2 have some point which is that hardware ALWAYs wins, and if its  complicated or dynamic algorithm the only people with the hw will be people with $100m+ to play with
14:25 < adam3us> petertodd: then we'll see centralization in an even harder to combat form - anther idea is to kick start a not-for-profit open hardware sha256 asic mining manufacturer
14:26 < petertodd> adam3us: see, I strongly disagree on principle because computer ram is stupidly optimized for it's task; design a good ram-hard pow and the custom part of a potential asic will be small enough that at worst it becomes a cottage industry where the custom parts are relatively easy parts like custom pcbs
14:26 < petertodd> adam3us: problem is I haven't figured out how to actually do that...
14:26 < adam3us> petertodd: i dont know much about hw but that seems like a good idea, as butterfly et al are suspected of premining or fatal incompetence
14:26 < adam3us> petertodd: apparently thre's another one called ROMix by the Scrypt author
14:26 < petertodd> adam3us: you mean an open hardware asic mining designer... we're probably never goign to have decentralized IC manufacturing due to the nature of the business
14:26 < petertodd> adam3us: having open designs doesn't help
14:27 < petertodd> *much
14:27 < adam3us> petertodd: Scrypt itself is time-memory tradeable as it was a non-requirement to fix it
14:27 < petertodd> adam3us: yup
14:27 < adam3us> petertodd: yes i agree its not so uch the openness as the ready availability shipped on payment (not 1 year later when its barely profitable)
14:28 < petertodd> See, at a high level, we can do interactive proof-of-storage, but we can't do non-interactive proof-of-storage. (specifically I mean you had some ram that was dedicated to a task for a given amount of time)
14:29 < petertodd> We can do proof-of-memory-bandwidth, but that doesn't appear to be ASIC hard: commodity ram *does* have various trade-offs between total storage, and bank bandwidth, and if you proof bandwidth * time, you can make an ASIC targetting that. (or your algorithm's constants become obsolete over time)
14:29 < petertodd> proof-of-memory-bandwidth also has the annoying habit of being symmetric, computation and validation are both expensive. (litecoin's been optimizing their scrypt implementation to speed up block header validation)
14:30 < adam3us> petertodd: i was wondering if many-ported ram could be a problem too (eg dual ported gfx ram to its logical conclusion eg 16-ports, 128ports)
14:31 < petertodd> adam3us: that's exactly what I mean! for instance I had a scheme for an asymmetricly validatable proof-of-work function with merkle trees where the size of the proofs was directly related to the parallelism possible, and commodity ram had way less parallelism than optimal
14:31 < adam3us> more high level though is there a way to base transaction ordering on a distributed timestamp server or distributed beacon without so much having the miners digging into the tx details
14:32 < petertodd> sure, but how do we keep the timestamp/beacon system secure?
14:32 < adam3us> yes; again hardware ALWAYS does better - its like a rule of physics or something
14:33 < adam3us> petertodd: well for example everyone mines timestamp commitments for reward
14:33 < adam3us> petertodd: thats nearly what committed tx looks like really
14:33 < petertodd> adam3us: no it's not! not pragmatically anyway, sure it'll always be at least some epsilon better, but we can live with ASICs being, say, 2x or 3x more cost efficient - basically that just makes tx's that people want to censor some reasonable amount more expensive. Not perfect, but we can live with that.
14:33 < adam3us> petertodd: the miner doesnt learn much except its ordering something opaque
14:34 < petertodd> As I've said over and over, those schemes are nice, but there is no way they can fully prevent censorship.
14:34 < petertodd> They're plausible deniability really.
14:34 < adam3us> petertodd: agree the scale is critical, 2-3x as you say would be fantastic compared to where we are now
14:34 < petertodd> adam3us: yes, right now we've got more like 1000x
14:36 < adam3us> petertodd: i was thinking one stepping stone towards reducing need for mining pools and miner understanding eg is that you could mine to get voting rights and then use the voting rights to vote on transactions
14:36 < petertodd> Also, keep in mind there's variations of this stuff too: assuming FPGA's are always available as commodity is a weaker assumption, but it's better than nothing. On that basis it might be a lot easier to make mem-hard work.
14:36 < adam3us> petertodd: eg you mine your public key repeatedly for 10mins, everyone does
14:37 < adam3us> petertodd: in the next round everyone gets as many votes as they have on their public key and the result defines which tx is first
14:37 < adam3us> (its all random anyway, it doesnt even matter which is first, just that one is chosen)
14:37 < petertodd> Interesting! That could be a decent way to reduce variance, although sounds like distributing the blocks for them to be voted on could be bandwidth intensive.
14:38 < adam3us> if the reward comes direct, maybe people can direct mine
14:39 < petertodd> (FWIW, fpga hardware is in the realm of 10x to 100x less efficient than ASICs depending on what you are trying to do; the FPGA's are commodity assumption is a lot easier to meet - maybe litecoin scrypt is already there)
14:39 < petertodd> adam3us: an idea I had was for the tx merkle tree to include pow
14:40 < petertodd> adam3us: like, every node on the tree would be able to include a specific pow, and you would sum total work
14:40 < petertodd> adam3us: makes it easy for anyone to do the pow for their own transactions, but the validation of the pow has to be reasonable efficient
14:42 < petertodd> (conveniently medium to high-end FPGAs these days all come with blockrams scattered over the die surface)
14:43 < petertodd> (sizes tend to be in the dozens to low hundreds of KiB per block ram, same size as litecoin scrypt assumes)
14:44 < petertodd> (the block rams however are themselves *not* as efficient as dedicated ASICs, because modern memory uses unique IC processes that verge on black magic; I'd have to investigate more to get an idea of what kinds of cost ratios are involved here and what they'd look like in the future)
14:49 < adam3us> petertodd: "an idea I had was for the tx merkle tree to include pow" did you see this paper http://hashcash.org/papers/merkle-proof.pdf by fabien coelho, i'm pretty sure you did maybe you were on the im thread when i heard a ref to it
14:49 < adam3us> "An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol based on Merkle Trees"
14:50 < adam3us> its just  space optimization and verification time optimization over sending n sub-puzzles, but its quite nice
14:50 < amiller> i bring up that paper a lot
14:50 < amiller> (but when i do, it never solves the problem i want it to)
14:50 < adam3us> amiller: it ws probably you i heard it from
14:52 < petertodd> right, that's where I got the idea
14:52 < adam3us> anyway in principle if you can earn voting rights by making disconnected proofs of work the proofs of work are not first past th post races and could even be deterministic (0 variance)
14:53 < adam3us> an end to luck, and you pick your own work size
14:54 < petertodd> Right, but how will that avoid the fastest miner wins problem?
14:54 < adam3us> petertodd: "sounds like distributing the blocks for them to be voted on could be bandwidth intensive." well they're broadcast already for spending
14:54 < adam3us> petertodd: well there is no winner, everyone collects voting power
14:55 < adam3us> petertodd: then you take a vote on which of double-spent tx are first
14:55 < adam3us> petertodd: tx with highest (or lowest) vote wins
14:55 < petertodd> Right, but think about the mechanics a bit more: how do you come to consensus on what block you're even going to vote on?
14:55 < adam3us> petertodd: like i say i dont think it even matters which is first, just that one wins - mining is quite random - the decision is made by a random node in proportion to power
14:57 < adam3us> petertodd:yes i get what you mean, but i this case as the voting rights are disconnected from the item voted on, ou can just vote on the few tx that have any conflict (maybe) individually or a sig on a list of them
14:57 < amiller> whta bout dakami's proof of x86?
14:57 < amiller> i wanna see that
14:58 < adam3us> amiller:  dont know i just saw something vague from peter vesennes(sp?) forwared from xgbtc (ex google bitcoin list) how exclusionary!
14:58 < amiller> it's like the corollary of the no-free-lunch theorem
14:58 < amiller> everyone's optimal at something
14:58 < adam3us> amiller: i think some people are still stuck at not realizing a GPU *is* a better cpu (for mining)
14:59 < petertodd> adam3us: right, but you have to be careful to make sure that people can't reassign their votes - maybe force the pow that creates the votes reference a blockhash for timestamp that hash
15:01 < Luke-Jr> amiller: give Intel a monopoly on bitcoin?
15:02 < amiller> Luke-Jr, i wouldn't have chosen x86, presumably if you can do it for x86 you could do it for anything else too like a TI dsp which has an open spec, or arm
15:02 < Luke-Jr> ARM is even more closed than x86
15:02 < Luke-Jr> I'm not aware of any open TI dsps
15:02 < amiller> i don't even think it's a desirable property, i think bitcoin mining *should* only run on dedicated hardware :/
15:02 < Luke-Jr> perhaps a subset of MIPS would work :p
15:03 < Luke-Jr> amiller: yes, but obviously this would be defining dedicated hardware as "x86"
15:03 < petertodd> amiller: that means control of bitcoin is centralized in the hands of the 2-3 chip fab companies in the world
15:03 < Luke-Jr> back in 2009, an ideal POW would have been one where RAM *was* the ASIC; but SHA256d has caught up
15:03 < amiller> build more chip fabs then
15:04 < petertodd> amiller: the entire world economy appears to be too small to do that. seriously
15:04 < amiller> meh
15:04 < petertodd> amiller: leading edge chip fabrication facilities are insanely expensive
15:04 < amiller> perhaps those don't even optimize for the kind of thing that makes a good bitcoin miner?
15:04 < amiller> i guess that doesn't make nsese
15:05 < petertodd> I understand your concern re: hash-reenting attackers, but understand it's a trade-off. It would be *very* easy for only a few governments (probably just one) to demand that all Bitcoin mining hardware be regulated in the future.
15:06 < Luke-Jr> frankly, POW is flawed unless over 50% of the world's electric production goes into mining at the most efficient way possible
15:06 < amiller> that is only if your attacker is that big
15:06 < Luke-Jr> frankly, POW is flawed unless over 50% of the world's electric production goes into mining at the most efficient way possible
15:06 < Luke-Jr> at some point, a replacement is needed
15:08 < petertodd> Luke-Jr: nah, that's a certificational flaw, not a pragmatic one :) The flaw really is more that the effort that goes into proof-of-work is only economically, say, 1% to 10% of the value of the system per year, which means any attacker gets a fairly large ratio of value destroyed to value spent, but there's nothing new about that... (box-cutters vs. the WTF)
15:08 < adam3us> petertodd: "adam3us: right, but you have to be careful to make sure that people can't reassign their votes - maybe force the pow that creates the votes reference a blockhash for timestamp that hash" yes there would have to be a timestamp chain included in the work to define the range of tx allowed for voting, and i suppose all previous round tx need to go in there also which comes back to how do you arrive at a serialization
15:08 < petertodd> s/WTF/WTC/...
15:09 < adam3us> amiller: re kaminksy this is what was forwarded to me email, posted by peter vessenes:
15:09 < petertodd> adam3us: yup, and it sounds like it'll be tricky to come up with a sufficiently simple system for that! though maybe just a direct timestamp chain would work, I'd have to think more...
15:09 < Luke-Jr> petertodd: I'm assuming the value goes up forever
15:09 < petertodd> it'd be really cool if a pure timestamp chain came out of this effort with a fairly short block interval...
15:09 < petertodd> Luke-Jr: ?
15:10 < adam3us> amiller: (on the ex google btc list) "   Kaminsky proposed to me a proof of execution architecture plan which
15:10 < adam3us>    sounds like it could guarantee it was running on Intel cores. I don't
15:10 < adam3us>    want to steal his thunder, but it would be a proof of work that could
15:10 < adam3us>    (provably?) disintermediate both botnet miners and ASIC companies.
15:10 < adam3us>  I've been trolling around for someone to lead a 'health of mining'
15:10 < adam3us>  committee for the Foundation, but haven't found someone willing to do the work of pulling the right folks together -- any volunteers here?"
15:10 < Luke-Jr> petertodd: at some point, it will become worthwhile to attack
15:10 < Luke-Jr> adam3us: ex google btc list?
15:12 < adam3us> sorry that was messed up, again: vesennes "Kaminsky proposed to me a proof of execution architecture plan which sounds like it could guarantee it was running on Intel cores.  I don't want to steal his thunder, but it would be a proof of work that could (provably?) disintermediate both botnet miners and ASIC companies. I've been trolling around for someone to lead a 'health of mining' committee for the Foundation, but haven't found someone wi
15:12 < Luke-Jr> sounds like something I'm already involved in, though not as a committee
15:12 < sipa> adam3us: the foundation hasn't really had much to do with development or technical stuff
15:13 < adam3us> petertodd: "it'd be really cool if a pure timestamp chain came out of this effort with a fairly short block interval..." (yeah I know you like your timestamp server;)
15:13 < sipa> also, what do you mean by 'ex google btc list' ?
15:13 < sipa> is there a bitcoin mailing list for ex-googlers? :p
15:14 < adam3us> luke-jr, amiller, sipa: yes when my buddy forwarded it to me (I dont know how he got it because he's not an ex-googler) I was like WTF? exclusive ex-google bitcoin list? how ugly and exclusionary
15:15 < adam3us>  could imagine vessenes got the wrong idea kaminsky likes to throw off the cuff thoughts and rants without thinking them through it maybe quite an unvalidated vague design idea
15:15 < Luke-Jr> adam3us: anyhow, health of mining is right up the avenue of things I've been doing for a long time
15:15 < amiller> former-marine silk-road squad
15:15 < petertodd> adam3us: ha! though it was a good learning experience re: worse-is-better
15:15 < amiller> i think it's a plausible idea
15:15 < Luke-Jr> maybe whoever-posted-that's problem is that they're only looking at ex-googlers
15:16 < amiller> would be hard to show it works for x86 without really well identifying x86
15:16 < amiller> you could do something where anything other than the given architecture uses slightly more power or something
15:16 < adam3us> petertodd: well i just think timestamping is a cleaner and simpler problem and bitcoin could do with dependencies untangling if its at all possible because the heavy cross design links make it nearly impossible to change anything significant
15:16 < petertodd> adam3us: WTF? the current POW algorithm already makes botnets unprofitable compared to ASICs :(
15:17  * Luke-Jr notes making a x86 POW effectively makes the entire x86 spec part of the bug-for-bug bitcoin protocol
15:17 < petertodd> adam3us: yes, although you have to be careful to make sure your system doesn't need proof-of-publication, or that to the extent it needs it, you have the incentives right so that POP is actually working
15:17 < adam3us> x86 mining: i tried to interest schnieir and kocher and kelsey and gilmore (people who worked on DES EFF cracker from some years back) if they would like to collab/ comment on making ASIC unfriendly design
15:18 < petertodd> Luke-Jr: and x86 POW becomes more and more attractive to ASICS as more features are added to x86, reducing the amount of silicon you are actually exercising...
15:18 < Luke-Jr> why are people obsessed with making this "ASIC unfriendly"?
15:18 < Luke-Jr> ASIC is the ideal
15:18 < petertodd> Luke-Jr: because if you are ASIC frieldly control of bitcoin is centralized in the hands of about 2 to 3 companies
15:18 < adam3us> x86 mining: kocher had some comments which were similar to this x86 concept basically do a lot of dynamic things relying at bit-level on x86 execution so the end result needs to understand that cpu
15:18 < Luke-Jr> petertodd: it's more centralised if it's ASIC unfriendly.
15:19 < petertodd> Luke-Jr: in theory, no, but those 2 to 3 companies are going to be rather unhappy to stop shipping commodity hardware for the sake of srewing over bitcoin
15:20 < petertodd> Luke-Jr: Government has a much harder time telling Samsung "from now on, RAM chips are a controlled good" than "yeah, just no more SHA256d ASICs unless they have the know-your-customer hardware in them"
15:21 < adam3us> this was kocher on something similar (email): "Of the various options for avoiding the "problem" of ASICs outperforming regular CPUs, the obvious option (ala litecoin at least to some degree) is to use a computations that utilize the full resources of a typical PC (e.g., DRAM intensive, use the multiplier a lot, large code image, etc.)  This tilts the equation away from dedicated hardware boards, but still favors people who are willing to ha
15:21 < Luke-Jr> petertodd: in all cases where government is the enemy, government wins by default.
15:22 < adam3us> luke-jr: thats why cryptography is good: its an immovable object they cant bend it to their will anymore than redefine pi to 3 (and they tried that too apparently)
15:22 < petertodd> Luke-Jr: right, so lets just give up... that's not a good position, especially when it looks like ASIC-resistant is viable
15:22 < petertodd> adam3us: that kind of thinking seems to often result in over-optimization for PC design now, rather than what it may be in the future; hard-forks are hard!
15:23 < Luke-Jr> petertodd: it doesn't look that way.
15:23 < Luke-Jr> ASIC-resistent is impossible in theory
15:23 < Luke-Jr> you can *always* specialise anything
15:23 < adam3us> luke-jr: " it's more centralised if it's ASIC unfriendly." that is an equally plausible argument - it just depends on how available ASICs are  - i think they suffer from market forces where anyone capable of making them miners them rather than sell (or are incompetent like butterfly)
15:24 < Luke-Jr> adam3us: don't forget that  self-mining is inherently competing against yourself
15:24 < petertodd> Luke-Jr: again, ASICs will always be some epsilon better, but we can live with it if the ratio is small - just makes transactions that people want to censor more expensive. 2x or 3x is reasonable, 1000x isn't
15:24 < adam3us> kocher contd: "miners occasionally unearth the right to publish puzzles to other miners (with rewards to those who solve these puzzles, as well as rewards to the puzzle issuer if puzzle solutions are neither too hard nor too easy)."
15:25 < Luke-Jr> selling mining hardware is more economically rational
15:25 < petertodd> Luke-Jr: I pointed out above how FPGAs may already meet that criteria w/ litecoin scrypt, and while assuming FPGAs are available is a weaker anti-censorship assumption, it's not an unreasonable one.
15:26 < adam3us> luke-jr: yes thats true (self-mining compete with self) but I am going to be super-pissed if when my march 2013 ordered miners turn up finally with adifficulty making it hard to recoup $5k spent, that they look burnt in with butterfly "test" keys preinstalled with 6mo of mining on the addresses
15:27 < Luke-Jr> adam3us: I expect the mining landscape to look very different a year from now.
15:27 < petertodd> adam3us: heh, I checked, butterfly hasn't shiped me any hardware that looks like it was tested at all :P
15:28 < adam3us> kocher last: " It'd also be entirely possible to design a new algorithm with extremely ASIC/FPGA-unfriendly elements, such as a gigantic piles of auto-generated code (= and growing faster than FPGAs) that gets changed periodically."
15:29 < adam3us> luke-jr: if he supply problems are smoothed out so anyone can place money and get working efficient 28nm hardware by return of post, I will be very happy as that is a valid (and simpler) solution
15:29 < Luke-Jr> adam3us: one time I pondered a POW that defined the subsequent POW from interpreting its hash a certain way
15:29 < Luke-Jr> adam3us: and the difficulty adjusted between the different POW algos by trying to make them equally rare
15:30 < petertodd> adam3us: fwiw I switched my 65nm outstanding order to 28nm monarchs
15:30 < Luke-Jr> yes, I think 28nm hardware available near cost to ship within a week, is a realistic expectation after difficulty catches up
15:30 < adam3us> luke-jr: the people on bitcoin forum who PM'd me with their 16 AES, 16 SHA3 finalist approach had some idea like the hash to use is derived from hash outputs and things like that
15:31 < adam3us> petertodd: is that butterfly?
15:31 < Luke-Jr> it'd be interesting to try some of these experiments in BFGMiner at some point
15:32 < Luke-Jr> woo, 20 GB of null data deleted XD
15:33 < Luke-Jr> problem is, as soon as anyone implements a new POW, the scammers jump on it
15:36 < adam3us> petertodd: think that is worth doing?  I have 130GH ordered (2x 50GH 2x 5GH) and could swap it to 600GH (it approx the same price) but it'll come later its "only" 4x faster / $ approx and maybe difficulty will jump by that in the period?
15:36 < adam3us> petertodd: they have a comically bad record at not shipping within 6mo-year of when they estimate which is punitive in mining terms with diffulty adjustment at super-moore's law rate
15:36 < petertodd> adam3us: my thinking re: mining is long-term, and 28nm is going to make break-even for longer I think
15:37 < petertodd> adam3us: they have a record of shipping late, but given that I work in the hardware industry I have a lot of symapthy for that :P
15:37 < adam3us> petertodd: well its getting longer term by the day thats for sure
15:37 < petertodd> adam3us: yup, right now 64nm has a payback time of ~1 year
15:37 < Luke-Jr> adam3us: 1 time does not make a record
15:37 < adam3us> petertodd: eg maybe i think it would've paid itself in a month at beginning i dont even know ok 1 year thats long
15:37 < Luke-Jr> unless we're talking in terms of "world record"
15:38 < adam3us> luke-jr: didnt they do that several times? their previous gen people were bitching about too?
15:38 < Luke-Jr> 1 year isn't long for most things
15:38 < Luke-Jr> adam3us: they've always been late, but not 6 months
15:38 < petertodd> adam3us: probably longer in practice. Which FWIW is still very good for most businesses, it's jut not the crazy profitability people are used too.
15:38 < Luke-Jr> adam3us: FPGA minirig was only like 1-3 weeks IIRC
15:38 < Luke-Jr> FPGA singles were a month or two IIRC
15:38 < adam3us> well i orered 17 mar the 50GH singles
15:38 < adam3us> and i havent seen it yet
15:39 < Luke-Jr> yeah, not doubting they screwed up big time with SC
15:39 < Luke-Jr> I'd expect a few weeks for Monarch personally
15:39 < adam3us> no sorry 17 april
15:39 < Luke-Jr> (late)
15:40 < adam3us> luke-jr: they said end of year, that might be ok
15:41 < petertodd> adam3us: oh, I ordered hardware in early march, so you're going to get that soon... but even then I'd still consder going to 28nm
15:41 < petertodd> adam3us: depends on what your cost structure is; I value quiet energy efficient hardware
15:42 < petertodd> Also, I'm not in it expecting to make money... mainly I have hardware because it's useful at times.
15:42 < adam3us> petertodd: their own page is even self-contradictory "However, we aren't shipping anytime soon.  This is a Pre-Order product, so if you're uncomfortable waiting an indeterminate length of time for the final phase, do NOT pre-order this product. With that in mind, our current schedule is on track for shippments to begin towards end of year.  " and higher up "jan/feb 2014"
15:43 < adam3us> petertodd: i figure for 6mo of the year you're gonna need a space heater anyway in canada, and your electricity is cheap also
15:43 < petertodd> adam3us: just means they don't have the units built and ready to ship - shit happens!
15:44 < petertodd> adam3us: exactly, and my parents live in the far north where the heating season is 8 months of the year
15:44 < adam3us> petertodd: its a cogeneration system: bitcoins & heat
15:44 < petertodd> yup!
15:47 < adam3us> luke-jr: "difficulty adjusted between the different POW algos by trying to make them equally rare" i was thinking you could have competing mining algos with independent dynamic difficulty targetting a chosen proportion of reward
15:47 < jgarzik> bitcoin water heaters.  the next million dollar idea.
15:50 < adam3us> luke-jr: eg allow scrypt(iter=1) or sha256^2 to coexist on bitcoin
15:50 < adam3us> start with say 5% scrypt, 95% sha256
15:50 < adam3us> have independent difficulty that ajdusts to keep the ratio
15:50 < adam3us> in that way runawy asic easyness is automatically adjusted for
15:52 < adam3us> luke-jr: eg if one day someone succeds in making an scrypt ASIC that is 1000 easier, th difficulty of scrypt would be increased to keep at the target % of reward for that mining function
15:53 < adam3us> luke-jr: so i think you could repeat that eg have 10 mining functions, with 10% each reward, all dynamically adjusted, then the ASIC people will not have as much fun because they will be competing more against themselves
16:06 < gmaxwell> adam3us: the scrypt pow stuff is a pretty poor idea. E.g. it's a performance problem with ltc chain sync
16:10 < gmaxwell> oh lots of backscroll to read.
16:22 < adam3us> gmaxwell: i agree scrypt verification cost sucks by orders of magnitude vs hashcash
16:23 < gmaxwell> 10:46 < amiller> btw there's a fully open source alternative to pinocchio/tinyram out https://github.com/srinathtv/pantry/
16:24 < gmaxwell> amiller: have you tried it?
16:24 < gmaxwell> wtf is with the dependencies?! KyotoCabinet, leveldb, fcgi?
16:24 < gmaxwell> also why PBC if they're using the seperate BN ate-paring library?
16:25 < sipa> PBC?
16:25 < sipa> ah
16:25 < sipa> pairing based crypto
16:27 < adam3us> gmaxwell: you might be able to design a better mem hard hash than scrypt  they didnt care much about verif speed, and its memory cpu tradeable as that was a non-requirement - eg using something like the "An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol based on Merkle Trees" http://hashcash.org/papers/merkle-proof.pdf by fabien coelho to verify in c*log2(n) instead of n for small c where n is the memory param
16:27 < gmaxwell> sipa: yea, there are basically two famlies of ways people are doing the backends for the general ZKP stuff. One is based on a pairing crypto knoweldge of exponent assumption and results in very small proofs (like .. 4 field elements which for the BN256 stuff are like 256 bits each), the other is a construction using fiat-shamir (hashtree based proof)
16:34 < odotan> hi
16:34 < gmaxwell> odotan: Hi.
16:37 < adam3us> gmaxwell: odotan and i were discussing timestamping, namespaces and relation to mining with the objective of reducing mining centralization or removing fees somehow (brainstorming) i suggeste we move it here as there was some discussion above... one sec pasting history for odotan
16:39 < warren> perhaps I shouldn't be amazed by the nut cases on the forum...
16:40 < gmaxwell> warren: hm?
17:03 < midnightmagic> oo I like reading stuff from nutcases. link?
17:03 < sipa> midnightmagic: bitcointalk.org :p
17:05 < midnightmagic> lol
17:07 < warren> midnightmagic: also http://www.theblaze.com/
17:36 < Luke-Jr> [21:03:24] <midnightmagic> oo I like reading stuff from nutcases. link? <-- PM "one" <.<
17:44 < midnightmagic> ah HAH. It was Bertrand Russell! I found him. http://www.youtube.com/watch?v=Il7Kxw9TDBc  what an amazing accent.
17:47 < midnightmagic> er.. woops, wrong channel. :( sorry about that
19:38 < amiller> midnightmagic, i remember when you were asking about that from a week ago!
19:46 < midnightmagic> amiller: :)
19:49 < midnightmagic> amiller: I've been looking for it for perhaps 6 months or so. I.. uh..  have trouble letting these sorts of things go.
--- Log closed Sat Oct 26 00:00:45 2013