Bitcoin Forum
July 04, 2022, 09:33:51 PM
 News: Latest Bitcoin Core release: 23.0 [Torrent]
 Home Help Search Login Register More
 Show Posts Pages: [1] 2
 1 Bitcoin / Development & Technical Discussion / bitcoin "unlimited" seeks review on: January 02, 2016, 05:58:17 PM The proposers of bitcoin unlimited said they would like to get some review which seems reasonable, if others would like to help.The proposal seems at first skim to be a copy of a few existing technologies from Bitcoin's roadmap and were first proposed by Greg Maxwell and others*: weak-blocks & network-compression/IBLT to reduce orphan risk, and flexcap (or a variant of it perhaps).Perhaps they could start by explaining what it is & how it works.  This might include unimplemented ideas, and a summary of what the code currently for download on the manifesto page does.To review it will be clearer if you state your assumptions, and claimed benefits, and why you think those benefits hold.  (Bear in mind if input assumptions are theoretical and known to not hold in practice, while that can be fine for theoretical results, it will be difficult to use the resulting conclusions in a real system).  Particularly claimed compatibilities with Bitcoin and how the dynamic block-size game-theory is expected to work and remain secure with SPV mining, selfish-mining, block-withholding and fair (progress-free) mining could also use explaining.I suggest the sensible thing is if there is something new or insightful, that Bitcoin consider adopting the technology and the BU proponents get behind that.Maintaining a new coin is a rather complex undertaking and screwing up, as something like 40% of projects that have tried it have done, is very expensive of other peoples money.To make progress on review it would be helpful to separate technical from political opinions.Adam* some citations seem to be notably missing, I trust this is unintentional.
 2 Bitcoin / Development & Technical Discussion / ring signature efficiency on: March 01, 2015, 12:19:30 PM The traceable ring signature used in cryptonote https://cryptonote.org/whitepaper.pdf looks like:KEYGEN: P_i=x_i*G, I_i=x_i*H(P_i) SIGN: as signer j; random s_i, w_i (I relabeled q_i as s_i to be more standard, and relabeled the signer s as signer j)IF i=j THEN L_i=s_i*G ELSE L_i=s_i*G+w_i*P_iIF i=j THEN R_i=s_i*H(P_i) ELSE R_i=s_i*H(P_i)+w_i*I_jc=h(m,L_1,...,L_n,R_1,...,R_n)IF i=j THEN c_i=c-sum_{i!=j}(c_i) ELSE c_i=w_iIF i=j THEN r_i=w_i-c_i*x_i ELSE r_i=w_i\sigma = (m,I_j,c_1,...,c_n,r_1,...,r_n)VERIFY:L_i'=r_i*G+c_i*P_iR_i'=r_i*H(P_i)+c_i*I_jsum_{1..n}( c_j ) =? h(m,L_1',...,L_n',R_1',...,R_n')LINK: reject duplicate I_j values.where H(.) is a hash2curve function (taking a value in Zn and deterministically mapping it to a curve point), and h(.) is a hash function with a hash output size very close to n the order of the curve, ie h(.)=SHA256(.) mod n.Towards finding a more compact ring signature I'd been trying to find a way to make c_i into a CPRNG generated sequence as they are basically arbitrary, though they must be bound to the rest of the signature (non-malleable) so that you can compute at most n-1 existential signature forgeries without knowing any private keys.  I found this paper "1-out-of-n Signatures from a Variety of Keys" by Abe, Ohkubo and Suzuki http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.363.3431&rep=rep1&type=pdf section 5.1 shows a way to do it.  I show here how to add traceability to it in a way that makes it compatible with crypto note:KEYGEN: P_i=x_i*G, I_i=x_i*H(P_i)SIGN: as signer j; \alpha = random, \forall_{i!=j} s_i = randomc_{j+1} = h(P_1,...,P_n,\alpha*G,\alpha*H(P_j))c_{j+2} = h(P_1,...,P_n,s_{j+1}*G+c_{j+1}*P_{j+1},s_{j+1}*H(P_{j+1})+c_{j+1}*I_j)...c_j = h(P_1,...,P_n,s_{j-1}*G+c_{j-1}*P_{j-1},s_{j-1}*H(P_{j-1})+c_{j-1}*I_j)so that defines c_1,...,c_n with j values taken mod l some number of signers.  Next find the s_j value:Now \alpha*G = s_j*G+c_j*P_j so \alpha = s_j+c_j*x_j so s_j = \alpha - c_j*x_j mod n.Similarly \alpha*H(P_j) = s_j*H(P_j)+c_j*I_j so \alpha works there too.\sigma = (m,I_j,c_1,s_1,...,s_n)VERIFY:\forall_{i=1..n} compute e_i=s_i*G+c_i*P_i and E_i=s_i*H(P_i)+c_i*I_j and c_{i+1}=h(P_1,...,P_n,e_i,E_i) check c_{n+1}=c_1LINK: reject duplicate I_j values.This alternate linkable ring signature tends to 1/2 the size of the crypto note ring signature as the signature is 3+n values vs 2+2n values.Adam
 3 Bitcoin / Development & Technical Discussion / would you buy a marked quantum scifi bitcoin for above par? on: January 02, 2015, 01:58:48 AM Lets conduct a scifi thought experiment, and talk about Bitcoin at a requirement level assuming some magical quantum scifi tech that can make it real sometime during the next 100 years: using the really high level definition that Bitcoin is a global process of converting electricity into some physical coin via transmogrification/energy to physical object or sufficiently advanced scifi to look like magic today, and its called a bitcoin and it can be easily inspected to see how many Joules it took to make (and the time at which it was made); and where all of these bitcoins are produced globally such that the process somehow magically knows (via non-local quantum communication?) the number of bitcoins created globally and the Joules/bitcoin consumed and which then adjusts the Joules/proof required to produce bitcoins over time to hold production interval on target at 10mins every 2016 blocks, starting with 50 bitcoins from its earlier incarnation before a few upgrades, origination back in 2009, and then halving every 4 years and currently running ag 11.921bits/per block.  Its all a bit scifi but maybe the coin contains a globally unique proof of work, its somehow magically turing universal and cryptographic AI and it doesnt matter what algorithm is used for the proof and any will be accepted, just the mining is an optimally efficient process, and what counts is the amount of electricity used, and the verifier can understand and easily verify any proof (and obviously the AI is going to see through any short-cuts).When you look at it like that, the 2015 bitcoin cant quite do that global non-local communication, universal cryptographic AI nor electricity to matter transmogrification, but thats really just an implementation limitation, that maybe we can fix with quantum sci-fi in the next 100 years future, and the current bitcoin is a pretty close facsimile.One day a fellow named Bob had an idea, he could stamp an F on the bitcoins and call them foocoins and persuade people they were better!  He choose some different interval of parameters and split the bitcoins into different sizes and stamped F on top them and talked up a good spiel so that others started playing too.However they were still fractions of actual bitcoins because the proof is universal due to the cryptographic AI, there was nothing Bob could do that could change that fact, no supply parameter changes, hash function used, software feature, not even a retro pacman game (loaded into the FHE processor in the coins), branding etc would change that because the universal cryptographic AI was measuring Joules expended, and unlike humans was not easily swayed by marketing and logos: a proof of joules mined is a proof joules mined, whatever letter or logo you stamp on the coin!  Because it started at difficulty 1 and ideal quantum processors are fast, foocoin difficulty adapted really fast (2016 blocks were over in a femtosecond), but as few found Bobs ruse plausible difficulty stabilised and by some creative marketing Bob found he could sell smaller and smaller fragments of bitcoins with F stamped on them and exchange them for whole bitcoin.  As this was profitable Bob and his friends ramped up production and used the proceeds to go on a marketing drive!One day some people started complaining that these coins were F crazy because they were the same material as bitcoin, in fact they were bitcoin, but Bob was selling them above par and they started demanding their money back.  Naturally Bob had spent a lot of the money on marketing and flashy objects.  The price crashed to true value, which unfortunately for the holders was really close to zero.  Bob made some money, but unfortunately he didnt hide his identity very well and he was convicted and given some community service and had to make reparations (it seems pyramid scams and stock pump & dump scams and currency skimming/debasement are still illegal in the 22nd century.)We have that same problem in current times.  The universal AI is called common sense: changing hash functions does not change the joules expended per coin, a hash with half the gate count results in a difficulty twice as high but the same Joules/coin.  A hash with a lower power density (say because it uses more RAM) can be run at a higher clock rate within thermal limits, and still use the same Joules/coin.  Changing the supply function to 2x as many coins doesnt change the value it halves the price expressed in 1/2 bitcoins.  Having a shorter halving schedule just makes the price change to 4x as many coins at price expressed in 1/4 bitcoin after the earlier halving etc.  The pacman game doesnt change things either because if it was useful to play pacman on bitcoin, someone would fork the code and add it; an arms race of cutting and pasting each others code doesnt create value.  Chances are the reason bitcoin doesnt have a pacman game is it isnt that useful or you dont need bitcoin to play pacman.  The 2015 Bitcoin doesnt yet know about users mining coins stamped with creative logos is because it lacks quantum non-local communication, we'll fix that one day, but in the mean time humans can convert one supply function to another with simple math and measure average electrical efficiency and when measured this way people are paying way over par, no rational entity would put money into marked coins, never mind a cryptographic universal AI.A bitcoin is a proof of Joules spent, no matter what branding or features you market with a bitcoin its still a bitcoin, and can no more change than a clump of gold atoms will cease to be gold atoms and start a floating price against gold if stamped with a letter F (assuming free instant assay like bitcoin has).Adam
 4 Bitcoin / Development & Technical Discussion / about price stability, lack of price/supply feedback & long run electrical cost on: December 29, 2014, 12:21:39 AM Some hypothetical thoughts about price stability, (lack of) price/supply feedback and long run electrical cost.Not a call to change anything just some thoughts.One observation people often make about the difference between bitcoin & gold is that gold reacts to price changes, by rate of supply increasing when price is high, and rate of supply decreasing when price is low.  This effect has some positive feedback loop in the direction of stabilising gold price.  Products with an inelastic supply function (like bitcoin or farming with long production lead times) result in gluts and shortages which take longer to self-correct than something with an elastic supply function.While bitcoin cant directly know its price as that is an externality, one related thing it does know is the rate of difficulty change.  An indication that supply is too high would be that difficulty is slowing, or similarly an indication that supply is too high difficulty increasing too fast.  So we could (hypothetically) change bitcoin to decrease subsidy per block if difficulty increase is above 10% per 2016 block period (2 week retarget).  What could we do with the unclaimed subsidy?  We could defer it so that bitcoin subsidy lasts for longer, and/or we could bring it forward again if difficulty slowed, eg for example increase the subsidy per block if difficulty increase falls below 0%.If subsidy is not deferred, just deleted, that saves electricity and reduces the supply.One might even speculate that the absence of price or rate of difficulty change feedback is currently causing price drops as mining difficulty is falling for the first time while the production cost (mining) is efficient (close to market price of coins) even for the most efficient operators.  Or put it another way miners in todays market would be happy to get another 5% at 13.125 btc/block over 12.5 btc/block.A second question is if bitcoin is $10,000/btc or$100k or $1mil which would be supported by various real-life uses eg see page 5 of report comparing to different aspects of gold ownership https://cdn.panteracapital.com/wp-content/uploads/Bitcoin-vs-Gold.pdf then at those prices, what happens to electrical use and mining investment. Is the result sustainable.Now one argument is more security is needed for higher market cap$21 tril?  And another argument is you cant have mining cost artificially pulled below market price or people will expend that amount of money anyway to bypass, bribe, hack etc the artificial factor.  (eg Paul Sztorc makes that argument in his blog post http://www.truthcoin.info/blog/pow-and-mining/)  I notice Nick Szabo made a similar point in an old blog post also.  The cynic may like to think of the lack of mining for USD (or other fiat) leading to huge expended effort for people to lobby, bribe etc to get access to government funds, where those funds partly come from inflation (which is a form of taxation) and also quantitative easing and bailouts.  The resources arent actually saved, they they just go into lobbying efforts and create cost via inefficient allocation of capital that arises as a cost of moral hazard.Maybe at these prices subsidy ends up being too high for the needed security and transaction fees cant go negative!  Anyway it would also be possible to voluntarily shrink subsidy per block (phased in over time to respect mining investments).Adam
 5 Bitcoin / Development & Technical Discussion / could you be Satoshi - #2 did it occur to you hashcash was like virtual gold on: December 28, 2014, 01:44:09 PM See also (continuing from) https://bitcointalk.org/index.php?topic=906865.msg9965116#msg9965116 first poll question #1 did you learn about hashcash before bitcoin?There is an implied secondary assumption about oh but who would think of using hashcash for electronic cash.  Well actually hashcash was proposed as a form of electronic cash and the announce itself compares features with Chaum's ecash http://hashcash.org/papers/announce.txt.  Also at the time of hashcash initial announce multiple people independently commented immediately that hashcash was like digital gold (and punned about bits) and then a number of people explored (unsuccessfully) how to control inflation which would run at moore's law etc.  The idea of trying to control inflation wasnt new either (but succeeding is!)  I discussed some hierarchical variant to  control inflation (eg a group of people could benchmark equipment and push out a new difficulty level via DNS), however that was unsatisfying as that would make them the central-bank.  In the end I opted to leave that to recipient policy (recipients would gradually increase their minimum stamp size over time so there was a decentralised consensus on what is appropriate to curtail spam).  This was possible because hashcash was mainly used to increase the non-spam score - lower required was fuzzy so you'd still receive the email with a lower than required (if it was relatively non-spammy).  Wei's b-money relates to that in proposing to make hashcash respendable and one of the inflation control proposals and Nick Szabo's bit-gold has a different inflation control proposal. Anyway I claim the hard part about bitcoin is the decentralised secure inflation control (and sybil resistant byzantine generals solution.)  But the idea that PoW is some kind of virtual gold and it would be useful to figure out how to control inflation to make it respendable seem to have been ideas that immediately reached out and grabbed many people.  Or thats my claim!What do you think, what do you recall your thought process being if you heard about hashcash before bitcoin.Adam
 12 Bitcoin / Bitcoin Discussion / Coin Validation misunderstands fungibility and could destroy bitcoin on: November 14, 2013, 05:30:51 PM http://www.forbes.com/sites/kashmirhill/2013/11/13/sanitizing-bitcoin-coin-validation/Its based on significant misunderstanding about bitcoins value proposition - destroy its fungibility and the costs float up to meet credit cards and paypal.It is also a ridiculous approach.  If they want to certify users, they should do that as optional KYC, AML certificates that regulated merchants in respective jurisdictions can request, which could be attached to wallets/identities, not to fully fungible coins.  The certificates should be non-transitive they attest to the identity of the user, not the coins.  They should be optionally sent - if the recipient does not request it, it is privacy destructive and a security risk to send identifying information to unregulated businesses and individuals.Their technical representatives of Coin Validation should be ashamed.  How can someone who doesnt understand a concept as basic as fungibility and its relation to transaction costs, and the difference between identity and coins hope to exist in this ecosystem.  What they are proposing so far at least as explained by the Forbes article is stupid, dangerous and just wrong.  I am also incensed frankly that someone would step into the market with such a muddle-headed thinking, and attempt to sabotage or destroy the core bitcoin feature that gives its value, where the value has been created by Satoshi and a cast of millions of man-hours of contributions of the community and technical wizards developing it mostly on volunteer time.  I am not someone prone to swearing, but this is astonishingly stupid and dangerous.   Please stop now.  In the article it is claimed they sought advice from the Winklevoss twins, if the twins value their estimated $30million bitcoin holding they should advise them to stop: if fungibility is destroyed bitcoins value as a transaction currency is impacted. I encourage anyone with technical skills to put their thinking caps on to find ways to increase fungibility in the short term like CoinJoin, coin control in wallets, helping less technical people migrate to better wallets, educating people about privacy practices that defend fungibility. And longer term privacy technologies like zero coin, homomorphic encrypted value and committed (hidden) transactions.I encourage all bitcoin businesses to shun Coin Validation unless we see some major U-turn or corrections. If your business depends on the success bitcoin, it depends on the fungibility of bitcoin, and Coin Validation seem to be set on destroying both.You can quote me on that.I welcome Coin Validations corrections of the claims in the Forbes article. Tell me you were misquoted.Adamps For people who have no idea who http://cypherspace.org/adam/ I am https://bitcointalk.org/index.php?topic=225463.msg237167 , my small part in bitcoin is I invented distributed mining in 1997 https://en.bitcoin.it/wiki/Hashcash (you can find the reference in Satoshi's paper) and worked on opensource ecash & crypto currency research & implementation for about a decade alongside Wei Dai & Hal Finney & others.  13 Bitcoin / Development & Technical Discussion / chaum cut-and-choose and physical cards (plastic card coins like bit-card.de) on: November 11, 2013, 01:17:53 PM So people are aware of physical coins with user chosen password security (against the manufacturer and people with unattended access to the stored coins).The simplified explanation basically the user generates password x, proto-coin P=xG, the manufacturer generates pub key Q=yP so the full coin private key is z=x*y mod n. And manufacturer generates check value B=yG. Now the user can see xB==Q so he knows his password was used.I gave a summary of the BIP 38 protocol here:https://bitcointalk.org/index.php?topic=311000.msg3342217#msg3342217(basically they have to move some stuff around to incorporate scrypt password stretching, and store a salt on the card for you to prevent scrypt rainbow tables).The BIP itself is confusingly hard to read https://en.bitcoin.it/wiki/BIP_0038 but says the same thing as the above.Now if you dont trust the manufacturer, and really you shouldnt, there remains a problem: they can grind your password becaue they know P = x*G. (And the fulls scheme includes a modest amount of scrypt KDF stretching to frustrate that). So that is easy to fix, use a computer generated random password, and print it out, put it in a safety deposit box with your bank.But there is another risk: extortion risk, (or bad batch due to software or other screw up) the manufacturer follows the protocol but prints something else on the card eg y'=E_m(y) where m is a master key he owns.To explain the motivation to protect against extortion: despite reputation risk for manufacturer on discovery: the manufacturer knows your street address and maybe has an idea you're thinking of the long term holding, and somehow knows you are Satoshi (or Winkelvoss or other big bitcoin holder) who is about to stash$100m of bitcoins physically for his grand children.  The investor is distrusting so he doesnt just give them unprotected form to his lawyer, nor due to business continuity risk and doubts about operational security to exante, bitcoin trust etc.   So if he wants to use physical coins  there is a low redemption and reputation risk for the printer to attack the investor because its long term storage.  Maybe they risk their business reputation for this once only low risk of discovery opportunity to attack $100m of bitcoins.Or maybe you're just paranoid and dont trust casascius or bit-card to not screw up their processes, because its a lot of bitcoin, and yet you like the physical coins they produce and their tamper evidence against people with unattended access to the coin storage area.(Obviously the investor can monitor the block chain for his address, the extortion attack comes into play much later, once the coin/card holder tries to redeem and finds the code is invalid and contacts the manufacturer. Maybe a rogue employee, long fired did it, or the manufacturer can plausibly claim so. In any case the news gets out, and the coin/card holder receives anonymous email demanding 10% of funds.)Your protection so far is once in a while people get curious or decide to redeem a physical coin, peel off the hologram etc. If they cant redeem it they're going to be complaining loudly in the forums, so you're fairly sure it hasnt happened. (The casacius ones cost a bit so redemption is probably less common than the nominal cost bit-card ones).But history of non-complaint is not a direct, personal proof that your physical coin is not from a bad batch, and actually has the private key printed on it. Maybe they should send you the sticker and you put it on yourself. However that has other problems - now you can peel stickers off high value coins, and empty them and have a new sticker. (Of course realistically anyone can print stickers, or do as in the demo of using a hypodermic needle and the right kind of solvent to get the sticker to slide off without damaging it Anyway so using Chaum's cut-and-choose crypto protocol (but done manually with paper (or plastic/metal) wallets) you can fix the extort/bad-batch risk. Order 128 bit-card.de password protected bit-cards (or cascius coins). Shuffle them, pull out 64 of them. Peel the stickers off, check they are valid, throw them away. Or put 0.01btc on each of the 64 and give them to your children to validate & redeem with smartphone as a fun exercise.Now take the remaining 64 cards scan the addresses, Q1,...Q64 and create a new address Q=Q1+...+Q64 the sum of them. Because of the permutations even with copy of Q (which is public on the block chain) if the manufacturer guessed your password (or just the bare private key if you didnt use the BIP38 password extension), he still cant compute your private key because there are C(128,64) > 2^128 permutations.You also have assurance there is a 1/C(128,64) < 2^-128 that none of the cards you used is defective or bad because of the cut-and-choose argument and you verified the other 64.Of course you could use smaller numbers eg C(80,40) > 2^76 but do remember that security of O(2^n) password plus O(2^k) has security O(2^n)+O(2^k) which is much less than O(2^(k+n)) so you cant rely much on the password, even if its really really good, it only adds 1-bit to security.Its a bit complex so you'd have to practice there were no operational screw ups. Like scratching the QR code off too vigorously when scraping of the sticker glue so you can read the qr.Or much simpler from operational mistakes, just use armory's upcoming k of n (optionally printer secure) paper wallets with no passwords.The bit-card approach has the arguable advantage that an internal threat the bank with your safety deposit box cant as easily see your private key without creating evidence with the tamper evident sticker. Its like being able to use the fancy printing technology they have and tamper evidence, but without trusting them due to Chaum's cut and choose, and it might be more durable than paper. Probably inkjets are not a good plan due to damp bleed. And you want color fast ink pen for the handwritten printed secure code.Adam  14 Bitcoin / Development & Technical Discussion / partially non-transferable coins (w. applications for physical coins?) on: November 02, 2013, 02:50:15 PM Towards reducing the manufacturer and hardware trust of physical coins it occurred to me that you can easily and voluntarily create a non-block-chain-transferable bitcoin. Its a bit like partially destroying a coin (by spending it to an invalid address) where you create a coin that is not blockchain spendable (by bitcoins rules), but where you can still prove you half-own it, and can hence half-transfer it. Because you can half-transfer it, it can still be transferred outside of blockchain rules (eg offline or by a group of clients respecting these alternate rules).To summarize existing methods that coins can be sacrificed or made permanently non-transferable: spend the bitcoin to an invalid address, eg to the address 0, or H(digits of pi) or to an address formed from a public key of form H(random).Now back on topic, to create a coin that is partly spendable is analogous: a 2 of 2 signature with one invalid address. Or requiring hash preimage of 0, or digits of pi.(I mentioned the idea of having a multisig with one invalid address in the thread about fixed public key coins, also about physical coins, but I did not see this use case at that time.)Quote from: adam3us on June 12, 2013, 11:34:19 PMAlternatively if the serial number were implemented as a demonstrably invalid optional second signing address added to a multisig, on each physical coin, probably tools could already index it; though invalid addresses are frowned on for frustrating compaction.The partially-transferable coin means you have intentionally created a coin that can not be transferred on the blockchain but the physical ownership can still be demonstrated if you have an electronic coin like firmcoin ( https://bitcointalk.org/index.php?topic=232898.0 ).How does that help physical bitcoin security? Well it ensures that someone cannot empty a coin of its value undetectably by removing the SD card under the tamper evident sticker, or spending the private key where its hidden under a tamper evident sticker, or trusting the coin manufacturer that the coin is even in there in the first place. And relative to firmcoin (which allows coins to be unloaded and reloaded, but deletes the private key on unload, you no longer have to trust the manufacturer to do that as much, because even if they have the private key in unloaded state on their computer, they still cant spend it on the block chain).To double spend a coin the attacker would need an extra empty physical coin, or the manufacturer could put the same private key in multiple coins (or the user if the user loaded the private key). And whats more if multiple people think they own the same coin it can be somewhat obvious in that the coin is spent at locations too far apart to physically move in the time frame. (And this is a topic of another post, tracking that).If its permanently non-block-chain transferable that creates two non-intercheangeable bitcoins a physical coin that can not be unloaded, and an online bitcoin, and the only way to trade them is to swap them 1 for 1.You might also consider variants where the 2nd element is not invalid but heavily time-locked eg 1 year. To time-lock the person loading the coin would create a 1 year time-lock and put the time-lock private key in the physical coin. In this way anyone can validate the address and see it wouldnt have been possible to spend it yet.Or where the 2nd signature allowing online redemption can be spent but only in cooperation with a somewhat-trusted entity, or a quorum of entities or users (k of n of them.)Adam  15 Bitcoin / Development & Technical Discussion / O(2^80) theoretical attack on P2SH on: November 02, 2013, 01:27:54 PM Unless I am misunderstanding something about the seralization, with pay to script hash, you create an address which is the hash of the script, and to claim you have to provide the script and the inputs to make it execute to true.A recurring pattern in cross-chain atomic swaps (litecoin for bitcoin) and atomic colored coin swaps, or fair-coin-toss / fair-roulette, CoinSwap etc like is use of "SIG(A) and SIG(B) and y=H(x)" where one party with-holds x and the other party builds a related transaction that he can see will become payable as a consequence of the counter-party spending the first transaction because both transactions rely on knowing x.One example is (to see what I mean about the two stage, this protocol was by iddo and optimized by myself, I think the y=H(x) idiom is used in multiple earlier protocols also):https://bitcointalk.org/index.php?topic=277048.msg3220019#msg3220019 The problem is hash output approach is only secure up to the birthday attack which is a generic brute-force O(2^80) attack, not bitcoins O(2^128) design target.Lets call the bitcoin address-hash AH(z) = RIPEMD160(SHA256(Q)) where Q is a public key or more generally a bitcoin script.This is because I can use the birthday attack to search for strings s="SIG(A) and y=H(x)" and s'="SIG(B)" such that AH(s)==AH(s'). That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work.Sounds expensive but bitcoin right now is doing O(2^62) every 10 minutes or about O(2^78) per year. Maybe in a few years bitcoin will be doing O(2^80) every 10 minutes and 14nm ultra-dense energy efficient ASIC miners will fill racks of data-centers.Also worth thinking about that there are O(2^64) birthday attacks on SHA1, and no one has probably tried to find analogous attacks on RIPEMD160 but that is not proof that RIPEMD160 is immune. But note the SHA1 birthday attacks need multi-hash-block inputs, and the inner SHA256 output fits in one SHA1 input block; and SHA1 birthday attacks work by choosing and steering bits; SHA256 output is one-block and random and frustrates that. Realistically given the constraints therefore even SHA1(SHA256(z)) for this purpose probably retains O(2^80) birthday strength. Designing hashes immune to that class of multi-block steering attacks is what the SHA3 NIST competition is about...Adam  16 Bitcoin / Development & Technical Discussion / unlinkable public deterministic wallet addresses on: October 25, 2013, 10:52:43 AM So in BIP 32 https://en.bitcoin.it/wiki/BIP_0032 (simplifying) the base private key is x, base public key Q=xG, then public derivation (BIP calls this function CKD) is Qi = m*G+Q where m = MAC(c,Q,i) and c is the public "chain code" (they use MAC HMAC-SHA512). The recipient can derive key x_i corresponding to Qi as x_i = m+x mod n (because m*G+x*G = (m+x)*G).Now this is good for security but not so good for privacy as any public derived address is linkable as an analyst can just repeat the derivation function and check which key Q it is for. In theory part of the reason to even use multiple receiving keys at all is to reduce linkability (unless there is an account benefit - one for each sender?)(With private derivation (also specified in BIP 32) conversely here x_i = m'+x where m'=MAC(C,x,i), and Qi=x_i*G so there is no linking but that can only be computed knowing the private key x, so it is not publicly computable, and does not interoperate ie for using public derivation both sender and recipient have to use the public derivation method; and for private derivation the recipient has to generate and send the address to the sender, you cant mix public & private derivation as they are incompatible).It seems to me you could make public derivation unlinkable eg by creating a random secret "chain code" and encrypting it for the recipient. So c' = random, Qi = c'G+Q, E( Q, c' ). Where E is public key encryption with Q public key, such as EC elgamal E(Q,c') = (A,B) where k=random, point C=[c',f(c')] where EC is defined by function f, A=C+kQ, B=kG. Decryption is c'=[A-xB].x. Now to receive transactions you need a full client and attempt to decrypt c" values and check if c"*Q=?Qi.With out of band coordination the sender and recipient could reduce the amount of full decryption the recipient needs to do. (Eg he can replace public key encryption function E by AES and a shared key)Adam  17 Bitcoin / Development & Technical Discussion / hardening brain-wallets with a useful blind proof of work on: October 15, 2013, 01:00:38 PM The risk with brain-wallets (eg BIP 038 with no EC multiply, or even with EC multiply if the manufacturer is not that trustworthy) where the ECSA private key is computed from password is that the passwords can be ground and if successful the funds can be stolen. So clearly its desirable to use key-stretching for brain-wallets and this is already done with Scrypt or PBKDF2. However a limitation with key stretching is it incurs computational load on the client, which maybe a smart-phone or single desktop class machine. eg 16384 scrypt iterations are suggested in BIP 038, chosen to be fast enough to tolerate in javascript.So it would be desirable to have a secure server offloadable KDF, which means a kind of blindable deterministic proof-of-work. I described one such proof-of-work in this post (relating to blind-hashcash a different but in hind-sight related topic, where you in addition need a transferable publicly auditable proof of work):An RSA based blindable (secure) work offload function:Quote from: adam3us on October 10, 2013, 04:30:18 PMpublic params:n=pq (primes p & q deleted at setup)g=shared generatore=2^(2^w)-1 ie a big, big number w is work factory=g^e mod n (generated cheaply at setup, or computable one-off cost afterwards)blind:m=messageb=random blinding factorr=g^b*m (broacast r to miners)work:s=r^e mod n (expensive because e is big and carm(n)=(p-1)(q-1)/2 is unknown)unblind:u=y^b (unblinding factor)m^e = s/u (as s/y^b=r^e/g^{be}=g^{be}*m^e/g^{be})So if we call that can be use as a blind deterministic password-based proof of work: we could set message = password, or H(password), blind by random factor g^b, and have the server compute blind-pbkdf( password ) for us with some large w that we cant afford to do on our smart-phone or laptop because itd be too slow.The above work function is basically a blinded version of Rivest et al's time-lock puzzle (the time-lock puzzle desires non-parallelizabiiity as the idea is to intentionally encrypt something for the future, where you cant speed it up by using multiple cores.) The fact that it is non-parallelizable is actually a disadvantage for a blind KDF, it means the speed up is limited to the fastest single-core offload server. Another simple parallelizable time-lock is proposed in the time-lock paper which is simply to symmetrically encrypt and discard say 40 of the key-bits (this is also the model used by Juels & Brainard for their client-puzzles proof of work which is somewhat hashcash-like but has no public auditability). However that is not blindable as its not an algebraic form.But it is easy to make an intentionally parallelizable instance by say 128 server cores (16x 8 core servers, or an even more impressive core count GPU server farm), use a smaller e value to take eg 10 minutes on a 1Ghz GPU core (whatever your transaction delay tolerance is), then stretch the password using eg PBKDF2 and 1 iterations, null salt, into 128-values worth of pseudo-random output call those m1..m128. ie (m1||..||m128)=PBDF2(1,"",password). Now create 128 cryptographically random (non-deterministic RNG) challenges b1...b128, the ECDSA key is x=m1^e+...+m128^e mod n, which is fast to compute when you know d (before deleting p, q, and d). Each offload message is r_i = g^b_i*m1 mod n, and the respective unblind u_i=y^b_i mod n. and the key is k = s1/u1+...+s128/u128 mod n.Unfortunately the user does need to retain g, y & n (or publish them in a hard to censor location, and keep the hash c=H(g,y,n) as a public fingerprint, or embed that in their coin on the block chain, because if the user relied on the offload server to provide g,y,n the server could provide a g,n where g has a small sub-group, allowing the search-space of blinding factor to be greatly reduced. The few remaining candidate password hashes could then be run through the KDF with the real n.The user can even create a pre-signed message transferring ownership from key Q1=x1*G to new key Q2=x2*G, with bigger work parameters on x2, that it requests the server operator, or trusted party to release when the available compute farm sizes increase and compute becomes cheaper. If locktime worked properly, you could even broadcast that transaction with a locktime 1 year into the future, and rely on the bitcoin network to automatically update your security margin over time.So a user protecting a$10,000 brain-wallet bitcoin investment might say use $10 worth of GPU time (at amazon prices of$2.10 per 400core tesla GPU hour thats 100,000 fermi core seconds or 714 fermi card seconds.  According to the bitcoin wiki mining comparison an S2070 is 4 tesla cores, and does 750MH so say 187.5MH/tesla second is about 37-bits in entropy compared to PBKDF2 rounds.  If you have a 40-bit entropy password that takes you from at risk of being GPU brain-wallet mined (\$80 worth of grinding) to implausibly uneconomical  border line not feasible with any resources for the mid-term.  Of course there are faster (AMD not Nvidia) and cheaper ways to grind than amazon.  Eg bitcoin mining pool payout probably charges a lot less.  Maybe it would be something for CPU & GPU miners to do as an alternative to vanity address mining or  primecoin/litecoin mining.So in summary you in a javascript client, or puny cell processor can create an arbitrarily hard to undo KDF with no practical CPU cost at setup time.  You can offload it securely later to a server, and you are not relying on the server to be around - the information is public (on the blockchain) the "server" is replaceable and stateless, and could even be a bitcoin core feature (pay CPU/GPU miners and other users small fees to help you decrypt your brainwallet).  This is parallelizable so it should be easy to add 40-bits of key-stretching or more that would be really expensive even on a high end PC with top of the line graphics card, to do that from a smart phone.Probably some more things that could be done eg combine with secret sharing so you can detect and eliminate defective work answers, or perhaps find a way to also have signed proof of work that somehow is easily verifiable without introducing a password verification crib.Adam