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_i
IF i=j THEN R_i=s_i*H(P_i) ELSE R_i=s_i*H(P_i)+w_i*I_j

c=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_i
IF 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_i
R_i'=r_i*H(P_i)+c_i*I_j
sum_{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 = random

c_{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_1

LINK: 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
6  Bitcoin / Development & Technical Discussion / could you be Satoshi - #1 did you learn about hashcash before bitcoin? on: December 28, 2014, 01:34:42 PM
see also second question of poll https://bitcointalk.org/index.php?topic=906867.0 #2 did it occur to you hashcash was like virtual gold

A recurring sub-topic in the who could Satoshi be debate is what knowledge would have been required and what communities discussed and were exposed to the required building blocks before bitcoin.

The assumption about the need to have known about b-money (because it is cited in the bitcoin paper), is seemingly invalid as from various Satoshi emails it seems he wasnt aware of b-money until after the paper was written and added the citation after it was pointed out to him (by me).  See eg https://www.gwern.net/docs/2008-nakamoto   Similarly bit-gold isnt cited, and the same Gwern post quotes Wei Dai saying Satoshi didnt seem to know about bit-gold either.  See also footnote 34 of gwern's blog article http://www.gwern.net/Bitcoin%20is%20Worse%20is%20Better  Similarly Hal Finney's RPOW wasnt cited either.  (b-money was announced originally in 1998 on the cypherpunks list.)

One of my contentions with people who asked me what I thought about that line of thinking (must have been on this or that mailing list) has been that well lots of people knew about hashcash before bitcoin, going back to 1997.  In the context of anti-spam (much tech news and tech magazines online and offline, discussion forum coverage existed at that time, probably suffered some bitrot since) and blog-spam (wp-hashcash) and namespace protection (in i2c tor-like FOSS competitor) and anti-DoS protection (in tangler, in interactive protocols etc) but I suspect that many 10,000s of internet programmers & technically minded people knew about it.  Eg. It was a fairly common experience for me to recognised by name at security conferences "hey you're the guy who did hashcash".

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!  That is topic of following poll.


It would be interesting to see if the assumption that many people heard about hashcash before bitcoin is valid.  The few people I asked informally said yes they'd heard of hashcash long before bitcoin.

Adam

ps the answer to what's hashcash http://en.wikipedia.org/wiki/Hashcash and https://en.bitcoin.it/wiki/Hashcash and http://hashcash.org
7  Bitcoin / Development & Technical Discussion / chaum, offline coins vs BGP & bitcoin on: November 13, 2014, 12:52:17 AM
Moving this question into a new thread:

How much did David Chaum have solved at Digicash/eCash?

Some of the notes on the relevant wikipedia pages suggest he had double-spending solved:

Quote
...
Depending on the payment transactions, one distinguishes between on-line and off-line electronic cash: If the payee has to contact a third party (e.g., the bank or the credit-card company acting as an acquirer) before accepting a payment, the system is called an on-line system.[2] In 1990, Chaum together with Naor proposed the first off-line e-cash system, which was also based on blind signatures.[3]

http://en.wikipedia.org/wiki/Ecash


Quote
In 1988, he extended this idea (with Amos Fiat and Moni Naor) to prevent double-spending.[13]

http://en.wikipedia.org/wiki/David_Chaum


Anyone have any more info on this? Was eCash's remaining problem merely initial-coin distribution, or was BGP actually not (practically) 'solved' despite the above?

not solved at that time, it was only online double spend protection that was robust with Chaums scheme, and that was with respect to a central server that was the authority on which coins were spent.  Good privacy, but weak survivability as very centralised.

The offline double spending protection of Chaum was kind of weak because what it boils down to is you could actually double spend, but if you did that eventually someone would learn your identity, which they hoped would be sufficient deterrent.  (Eventually the double spent coins would get deposited at the bank and a simultaneous equation in the double-spenders identity revealed).  How it works is the coin has embedded in it your identity in a way the bank can verify, but which is kept private so long as you do not double spend.  Chaums offline double spend is a bit space inefficient as it involves cut-and-choose a generic proof mechanism, also used by zerocoin and which is the primary cause of the zerocoin bloat.

Hal Finney did a write up on this Chaum cut-and-choose scheme for more detail: https://w2.eff.org/Privacy/Digital_money/?f=double_spending.articles.txt

Stefan Brands ecash system has more space efficient offline double spend protection because the coins support (without cut-and-choose) multiple attributes directly.  However the default scheme is just delayed deposit (not offline respendable).  Actually I guess Chaums offline scheme has that property also.

I reinvented an offline respendable variant of Brands around 2000/2001 but when I asked him about it he pointed me at a footnote in his thesis / book referring to someone's masters thesis.  How that works is people have multiple spare 0-denomination coins, so when you accept a coin you use this 0-denomination coin as the initial witness (random value chosen by recipient as part of the ZKP).  In this way if someone downstream offline respends and does a double spend, its their 0-denomination coin with their identity in it that gets identified as the first double-spend.  A downside of this is the coins grow on each respend.  Its a bit like bitcoin as the respends are also pseudonymous but linked in their spend history (which I viewed as a not ideal limitation of the approach) where as the online coins are anonymous but more vulnerable to traffic analysis as you had to race to deposit to be guaranteed to receive.

The other paper from 1999 was Sander & Ta-Shma's auditable anonymous electronic cash which is extended by zerocoin (its zero knowledge proof of set membership based - the list of unspent coins is public but to spend you prove in zero knowledge that your coin is one of the unspent ones, but not which one).  Its kind of interesting as the "bank" doesnt have a private key, so its clearly p2p compatible.  So kind of a zerocoin precursor existed before bitcoin, zerocoin refers to this paper.

I think the main missing bits from Chaum/Brands/Sander & Ta-Shma/b-money/bitgold were how to do inflation control without reference to any central party or network external information and sybil resistant solution to byzantine generals problem (double spend problem - which spend of many comes first).  Plus a bunch of implementation level detail. 

You can see that Wei Dai's b-money & Nick Szabo's bitgold both 1998 offered some directions on ideas to vote on or have a market effect setting inflation, and both included hashcash mining as bitcoin does, but they did not connect a p2p (no enrolment/no identity) solution to sybil attack on byzantine generals problem (double spending, which spend comes first) with mining, nor arrive at the elegant solution of having an engineered supply function that can be measured internal to the network that bitcoin introduces.

Adam
8  Bitcoin / Development & Technical Discussion / (space) efficient reusable addr via weil pairing IBE on: January 25, 2014, 02:34:12 PM
So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman, Mike Hearn, Bytecoin and others about reusable addresses.

There is a summary of the situation here http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03792.html and I had posed th question of whether it was possible to do better at all with Peter Todd:

Quote from: adam3us on bitcoin-dev
Now while it would be clearly a very nice win if reusable addresses could be  made SPV-like in network characteristics and privacy, but we dont have a plausible mechanism yet IMO.  Close as we got was Greg's enhancement of my/your "bloom bait"/"prefix" concept to make multiple candidate baits to provide some ambiguity (still allows elimination, just slightly less of it). 

If we can find some efficient crypto to solve that last one, we could even adopt them generally if it was efficient enough without needing interactive one-use address release

and Peter proposed also the related problem of proving something about that existence or not of a solution to that problem. 

I think I have a proof-of-concept solution that proves by example we can do better in space efficiency, linkability defense and non-interactivity than my bloom bait, Peter Todds related prefix; and Greg Maxwell's extended bloom bait described http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03705.html.

So the idea is to use an IBE scheme as a building block in analogous way to my 1996 problem statement for NIFS and 1998 observation that a novel use for an IBE scheme can provide a generic solution to NIFS, and the arrival in 2001 of the first efficient / sensible trapdoor steepness (*) IBE with the introduction of the Weil Pairing problem by Dan Boneh and Matt Franklin described here http://en.wikipedia.org/wiki/Boneh%E2%80%93Franklin_scheme.

Greg summarized IBE as follows on IRC:

Quote
(for those who may) not be familar with IBE stuff: The idea is that the user has a master private key, which results in a master public key. Anyone can take a prior block hash and combine it with the master public key to get a session pubkey which could be used to encrypt a chaincode included in an OP_RETURN.   Using the master private key the user can derrive the session private key, which can then be used to recognize transactions using the same session key. 

In IBE (identity based encryption) this is all used a bit differently: the master keys are held by a CA, and the session ID is your email address, and now anyone can make a public key for you— but you need the CA's help to get your private key)

Basically as Greg said your public key is your address (an email address, a block hash, whatever is convenient and unique) and from that and the master public key of the IBE server, the server can compute a private key corresponding to that.  The master public is usually considered to be a system-wide domain parameter.   Naturally enough because a side effect of this is that the IBE server can decrypt everyones email people were never too excited about the prospect.

However my 1998 NIFS observation is by acting as your own IBE server (each user creates their own master public server key) they can create a sequence (NIFS) or set (bitcoin reusable address) of public keys with interesting and publicly derivable properties!

It is my conclusion from 1996 that to solve this with DL directly at least in the NIFS case appears to be not possible.


So basically the reusable address becomes an IBE public key, the existing public derivation via DH or EC Elgamal/ECIES or whatever variant (bytecoins, mine, Peter Todd/Amir Taaki's) arrives at a factor that can be recovered.  So with my variant (random sender generated multiplication factor encrypted with ECIES) you could encrypt the factor with a pub=IBE-extract(master pub, id=previous block hash) using the previous block hash as the "identity" and the users own self-owned IBE "server". 

For Bytecoin & Peter Todd/Amir Taaki EC DH version using input or auxilliary addresses to save space its not even necessary to send the factor, its already sent.  So then you send a separate message to do with secure delegatable filtering, a more secure/more space efficient bloom filter/prefix replacement, and this is a more flexible structure.

So the secure delegatable filter is you separately add an encrypted bloom bait Greg suggested (eg 1byte prefix communicated with public address.)  And you can even combine that with Greg's extended bloom bait above to add anonymity set within the block.

Consequently you can now securely and very network/space efficiently securely delegate searching a block by computing the private key for the IBE pub key that any sender would use for that block, and sending it as a query to a random (or node-capture defended random selected node).  The node can decrypt the encrypted bloom baits with it, but remains powerless to correlate with bloom baits to other payments received by the same user in bother blocks.

(In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block).

About weil pairing, and new hardness crypto risk, this is also the hardness assumption under some ZK-SNARKs as I think used in zerocash, and while ZK-SNARK introduces its own complexity/crypto system risk on top; in my view weil pairing is slightly lower assurance/review not so widely used relative to EC DL problem.  Anyway the interesting thing to say about that is in the event this scheme got broken in the future it falls back to the scheme that is being proposed using prefix.  Ie its no worse than that from linkability and likely would retain some cost even if broken-- asymmetric crypto breaks are usually somewhat gradual.

This looks more expensive and non-indexable though I didnt look to see if there is any ciphertext only or batch precomputation that could be squeezed out of it.

Obviously its more CPU intensive and some eg fee mechanism to prevent node DoS could be nice, but it seems to demonstrate a proof by existence that it is possible to do better.


Finally I think it maybe within possibility to do further than this because it is not technically necessary to delegate decryption, only to delegate filtering, which can be a simpler requirement.

Adam

(*) There was an earlier scheme by Maurer et al if I recall, but to get a 1024-bit security margin you had to perform a discrete log attack on a 512-bit prime, so the key generation cost was immense, hence "sensible trapdoor steepness" thats very shallow in tems of work difference between setup cost and crypto system strength.
9  Bitcoin / Development & Technical Discussion / letstalkbitcoin on committed tx, homomorphic value, fungibility, privacy on: January 23, 2014, 09:22:15 AM
A podcast from letstalkbitcoin where I am talking with Andreas Antonopulous: maybe a better summary of the committed tx & homomorphic value, the threads here were full of crypto-math and perhaps hard to decipher, also fungibility/red-list & tx-cost and how that relates to indentity and privacy; also hashcash, decentralization, coinjoin/payment protocol, zerocoin/zerocash, some history.  1h45 of "light" listening Smiley

http://letstalkbitcoin.com/e77-the-adam-back-interview/

Some bitcoin talk links to the topics discussed:

Committed transactions (that really needs a summary top post, too much design evolution through it):
Quote
homomorphic values:
Quote

fungibility, identity & privacy
Quote

hashcash

Quote

coinjoin
Quote

zerocoin
Quote

Mentioned some 1998/1999 cypherpunks posts by Wei Dai, Hal Finney & anonymous (Satoshi or not unclear).  The links are at the bottom of this:
Quote
Enjoy Smiley

Adam
10  Bitcoin / Bitcoin Discussion / some 1998 possible satoshi cpunks-list posts on: December 16, 2013, 01:06:12 PM
I mentioned a few times that there were 1997 (hashcash) and 1998/1999 (b-money) posts and discussion about how to build digital scarcity and control inflation on the cypherpunks list.

I was just reading some of them, hadnt notice this one last time I looked and it is quite nice (anonymous):

http://marc.info/?l=cypherpunks&m=95279521221935&w=2

Quote from: Anon
The quantity of b-money in a mature system is, roughly speaking, constant.  (The quantity
may grow, but it will do so slowly, based on the increased demand for b-money.)

(Anon seems to take as a given that b-money would be able to technically solve inflation - the way Wei Dai described it the servers would vote on how much money to create and the cost of creating it per time-interval.  Personally I found that prone to human gaming & abuse, eg might people with limited money at stake vote for "lots" and "cheaply" for the two parameters)

So he is referring to the b-money property of supply being increasable by vote amongst servers, but assumes that will remain low and benign.  I am not sure this confidence is justifiable - it depends on the motives and interests of the server operators.  Maybe he is assuming server operators would be unlikely to agree on > 1% supply side inflation or greater than human population growth %, in a mature deployment.

This one also appears bullish that b-money can be improved:

Quote from: Anon
It's ironic for people to complain that b-money is inferior, in a world in which fiat money is universal.  Once the mathematics of b-money are better established and understood, and once the technical issues are clarified and problems solved, this appears to be a very attractive alternative to fiat money.  Unlike commodities such as gold, it can be easily exchanged electronically.  And unlike fiat money, it is immune to attempts to manipulate the money supply.

http://marc.info/?l=cypherpunks&m=95280154630156&w=2

Quote from: Anon
B-money is therefore highly resistant to inflation, and contains mechanisms to automatically adjust the size of the money supply to produce very stable prices over the long term.  It would be superior in this regard to virtually any other proposed form of money.

(Again as stated b-money would have allowed on-going supply side inflation according to an average of server voter-for rate at a creation cost based on average vote-for difficulty).

(Found those with search term b-money from http://marc.info/?l=cypherpunks which finds several threads).

Adam
11  Bitcoin / Development & Technical Discussion / towards air gap security: authenticated addresses or HD sub-wallet on: November 24, 2013, 10:26:03 AM
Bitcoin irrevocability & fungibility is cool and one of the main benefits of bitcoin.  However the cost is stealing them constitutes the perfect virtual crime, and so the level of APT attacks will surely rise to new proportions against both user machines, and bitcoin processors.

Now one step towards making bitcoins hard to steal is offline wallets (armory & trezor) where the remaining remote threat is almost removed (subject to very few lines of code in usb drivers and the attack vector of the protocoin sent to the offline device for verification and signing).  Given the stake the lines of critical code can be minimized and audited.  This is  robust starting point.

However the remaining issue is, while you can receive bitcoins securely over an air-gap, and pay from an offline wallet using usb or QR code, your ability to securely communicate addresses for receipt via the users online computer is questionable.  Targeted bitcoin malware can win this race (show you what you want to see, but send a different address to the sender via local SSL backdoor, app patches, OS patches etc).

Similarly security of the online payment processor's environment is in question.  They can use host security experts, best practices etc.  But still there is the 0-day and the APT attack, but surely it will escalate to a new level.  And the payment processor despite hot-wallet / cold-wallet trade-offs is an increasingly valuable target.  Malware on the payment processor can send users the attackers address for "deposit".  It can steal the hot-wallet.  It can replace users "withdraw" addresses.  They'll notice but it maybe too late.

The payment protocol https://en.bitcoin.it/wiki/BIP_0070 helps, however that has to be part of the online merchant app because its not just signing the merchant invoice address, its signing the transaction details also.  Likely it will be signed by the SSL web site, though it could be signed with a separate sub-domain.  Lack of a hard requirement for this to be the case makes that assurance weak - an attacker who gains control of the merchant site can sign with the SSL cert key and users wont consider anything amiss.

Also even without breaking into the merchant, SSL certs can and have been hacked, and absent cert pinning, the entire system is as weak as the weakest CA.

So what could we do about this.  

We need to rearchitect for the bitcoin offline wallet security model.  Its fine for the web app layer to best-effort sign the transaction, if one values it for what it is - an assertion by an at risk web app with at risk keys.  (Hardware security modules dont help that much, the app layer still obtains no-restriction signatures from the HSM).

So one more thing that could be done is to use hierarchical deterministic wallets to make a sub-wallet with a shared chain code between the user and the merchant.  For repeat custom or a bitcoin exchange this could make sense.  Then if both the merchant and user keep the chain code off the online machine they can at least be assured that the address is unique to them.  Use out of band security to set this up.  Or use TOFU (trust on first use) so that both sides abort of something changes about the security context.

Secondly it seems to me we could do with something end to end authenticated between the sender and the receiver.  Signed addresses?

Then the sender and the receiver dont need a secret (shared chain code of sub-wallet), they only need an authenticated signing address from the respective online wallet.

Maybe you derive identity assertion keys deterministically from the offline wallet, derived from the receiving parties identity (domain name, email address etc).  And send those to the receiving party during setup, or use out of band for one off.

Privacy, fungibility?  The signatures are not part of the bitcoin transaction, they are just to convince the relying party.  They are not receipts like payment request ack messages, they just show you that the person you expect is the owner of the address with offline hardware assurance.

Because the addresses are not user specific the merchant can upload batches of them from the offline computer.

Could you use abuse the payment request protocol to encapsulate a second signature on an address?  Probably but that seems like a protocol layering violation to me.  Payment protocol is an app level protocol, authenticated addresses are simple, have no external references and gives a stable public handle to authorize.  The hash of chain code of a sub-wallet could do something similar.

In terms of concepts and terminology you could consider the signing address (that signs the one-use addresses) to be an account number.  And the one-use addresses as transaction or invoice numbers that are signed to prove they are owned by the account number.  You can use a different signing address for each recipient to add privacy.  Or a different signing address for each time if its not an identified ongoing relationship.

You can wrap these signing addresses with X509, PGP, SSL, phone call to check, offline address signing key fingerprint on company business cards etc.

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.

Adam

ps 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 Smiley

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.)

Alternatively 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:
public params:

n=pq (primes p & q deleted at setup)
g=shared generator
e=2^(2^w)-1 ie a big, big number w is work factor
y=g^e mod n (generated cheaply at setup, or computable one-off cost afterwards)

blind:

m=message
b=random blinding factor
r=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
18  Bitcoin / Development & Technical Discussion / blind-hashcash, potential bitcoin applications using blind brands certs/ecash on: October 08, 2013, 09:25:10 PM
I had been musing on and off for a while now there ought to be a way to create and use to some useful effect in the bitcoin context a blind proof-of-work.  And that homomorphic value might open the way to some interesting not-forseen features.  This might be it.  With reference to this other thread on homomorphic values:

https://bitcointalk.org/index.php?topic=305791.msg3277431#msg3277431

at the end I quote an email to Chris Odom where I observe that the pederson commitments that are used for homomorphic values are actually the same encoding as the representation problem of an unblinded brands credential ecash.  So that leads to the question well can we use a blind form of hashcash instead of hashcash mining in bitcoin so that we use can somehow validate coin without seeing its spend history.

The morphcoin proofs are using Schnorr /EC Schnorr (ECS) also, so the proof of value & range proofs etc are all compatible with Brands blinding.selective disclosure and other proofs.  (Only his coins are signed).

However you might think, but how can you unblind a hash.  You could maybe include a random value in an additional hidden field like g^v*f^r*h^x and the miners challenge is to find a collision involving f, and then you could blind, still prove the coin contains v and adds up, and the right f value, have the miner do its work, the unblind.  That could work however then your coin is associated with a specific mined block reducing the anonymity set.

So ideally you need to have the work itself be unblindable hence blind-hashcash.  Turns out you can do that: it has to be signed, and there is no signing entity.  However the trick is as with the outline idea of one of Dwork & Naor's 1992 proof-of-work (4.2)  (see http://hashcash.org/papers/ ) model of constructing a signature forgery as the work.  In our case because we want no central trapdoor (unlike the RSA modulus in zerocoin and Dwork's use of Fiat-Fiege identity scheme).  So we just create a public key that we can prove no one knows.  eg hash2curve digits of pi (or in non EC public key is hash of seed of digits of pi or such things).  Now we cant compute the EC discrete log (prime field discrete log) and everyone can be convinced that no one knows it.  RSA based is bad for trap doors, discrete log-based good.

Recall a normal Schnorr signature is x is private key, signature is pair (a,r):

k=random, a=h^k, h0=h^x, r=k+cx

and the verification relation is to check: h^r=?a*h0^c
or equivalently a=?h^r*h0^-c.

Now for a forgery we dont know x but never the less we want those verification relations to work.

Here's how blind-hashcash works:

s=random salt, r=random, c=random mod 2^w
compute a=h^r*h0^-c
find i such that c=?H(s,i,a,m) mod 2^n

w is the work factor in bits, i is iterator a string to randomly increase, s is a salt so miner's dont accidentally or intentionally (as DoS) do the same work, a is the initial witness a, h0 is the public key.  m is the message that is signed, in bitcoin thats the coinbase.

The explanation is that we normally need to compute c=H(a,m) so we fix that up after the fact by doing the now shortened hash and using finding s,i such that c is still the same as the random value we guessed up front.

You can use this blind-hashcash protocol with your choice of hash: double SHA256 as H for bitcoin, or similarly with scrypt with iterator 1.  (Litecoin itself is using hashcash also, its just the hash function is replaced with scrypt(1)).

This is nicer than Dwork & Naor's weakened signature forgery based proof of work because the work core does not use big number operations.  (Well you could try to frustrate ASICs with such operations but thats what ppcoin is about, as a basic function you want simplicity).  Also unlike Dwork & Naor function has a trap-door that cant be removed.  Its also faster to verify, more compact, supports blind signatures.  We could allow a trap-door if desired by publishing a public key with an actual private key, or a threshold-held private key so k of n authorities need to collaborate to produce a proof-of-work with a short-cut.  However a short-cut in bitcoin means undo transactions, mint coins, killing the network (difficulty rockets to infinity unless real signatures and doesnt come down) etc.  Also its safer to use a separate signature for short-cuts so that it can be revoked, and detected, and ignored by users who dont trust the authority.  We wont be doing any of that for bitcoin, only mentioned for feature improvement of Dwork & Naor who focused on a central authority model, I tend to focus on eliminating such things!

You notice the core work function is slightly incompatible maybe enough to break existing double SHA256 hashcash ASICs.  We can fix that if desired by doing:

r=random, s=random
compute a=h^r*h0^-s
find i such that 0=?H(s,i,a,m) mod 2^n

on verification compute c=s+H(s,i,a,m)

Now the core work function of blind-hashcash is standard hashcash work function and so can reuse existing asm, C, GPU, FPGA and ASICs for normal hashcash with double SHA-256 or scrypt(1) as hash function.


Then back to bitcoin applications now we can do blind-hashcash (a blind forged signature for an unknown discrete log public key that incorporates a proof-of-work), we can maybe find a way to use that in place of the certificate authority/ecash bank in brands.  If we can do that we can get the advantage of blind ecash privacy with the lack of central authority and distributed mining that bitcoin has.

So if it can be made to work (some questions to check) we would optionally use a homomorphic value input (or a clear input though amounts tend to link if uncommon), blind it, the miners can validate the encrypted amounts add up, even though the coin is blinded (have to check that range-proofs work on blind representation).   Then the miners can make a forged blind signature that looks like they know the discrete log but in reality the forgery is created because we are using a malleable short hash (where you get to try lots of times).

We need to encode in an extra attribute of the coin a block counter j.  So then we'd have a blind-coin with and blinding factor b:

h0 = (g1^j*g^v*h^x)^b

that then can be blinded and disclose to the miners j, v still prove to the verifier you know x (and b).

The main tricky things to work out are the interactiveness as we can have no issuer interaction as there is no issuer, just a distributed forged signature.  Some of the brands mechanisms are resonsive to a server chosen initial witness.  There are some lower round variants but as I recall they were RSA.  Unless the forgery aspect can take care of it - ie e dont need an initial witness, only a self-chosen forged one.  Not sure about that.  And also server knowledge of discrete log of bases g1,g wrt g0 that cant work at least directly in a distributed environmnt.

Adam
19  Bitcoin / Development & Technical Discussion / bitcoins with homomorphic value (validatable but encrypted) on: October 01, 2013, 02:19:53 PM
I have been researching this for a few months on and off, because it seems like an interesting construct in its own right, a different aspect of payment privacy (eg from a user perspective or for auditable but commercially sensitive information if we expect commercial entities to use smart-contracts) but also that other than its obvious direct use it may enable the realization of some features that we have not thought of yet, or perhaps improve the efficiency of zerocoin like ideas (I dont see how yet, but it seems related).

The starting point is it is known in the literature that you can do additively homomorphic encryption, and there are also zero-knowldge proofs of less than.  (Proving E(a)+E(b)=E(a+b) is not enough you also have to prove that the attacker did not add n to his balance during the process as the addition is modulo n, the order of the group, not normal arithmetic.)  Its more efficient to do less than a power of 2, but arbitrary values are possible by composition (all values are buildable from power of 2 ranges after all).

Both of these (homomorphic add and ZK less than proofs) are based on established conservative crypto assumptions, however the generic ZKP of less than is big (number of digital signature sized proofs proportional to log(v) where v=log2(n/vmax)+1 = log2(n)-log2(vmax)+1, so in bitcoin log2(n) = 256, and vmax depends on the encoding, but there are 21million BTC < 2^51 satoshis.  And potentially also slow as it involves verifying v signatures.

Originally I was thinking that will work out to be embarrasingly slow and big (something like zerocoin) so I held of discussing if and until i could find a practical efficient method.  There is also an efficient approximate less than ZKP by Berry Schoenmakers (that he never bothered to write in a paper, natch).  However that seemed to me to be more non-standard assumption based on choosing non standard p & q for the Schnorr group and to also not work over elliptic curves and so not ECDSA (only Schnorr, of which DSA is a variant).

However finally I think I saw the missing step that the way bitcoin uses and validates coin values you only need to prove the two most significant bits of each coin is 0, and use an encoding which sets vmax<2^254 (ie increase bitcoin precision from 51 to 254 bits, less significant extra bits beyond the < 2^51 satoshis are the private key.  That gives encoding for 203 bits of security which is greater than the security of ECDSA over P256 which offers security of 128 bits.

And so there is then finally a non-embarrassing efficiency way to do it with EC-Schnorr signatures at the cost of only 2 ECS sigs (same cost and size as ECDSA) per input and output where #input < 4 and #output <4.  For #input>3 you nee to also show eg ZKPoK{(a+b+c,d):a+b+c<2^254,d<2^254} and same if #output>3.  So 2k+2log3(k) signatures for k inputs or outputs.  (3 because 2^254*3<n but 2^254*4>n.)

Btw there are good reasons to use ECS over ECDSA IMO its still conservative and simpler and anyway DSA is based on it.  Because its simpler (no *k^-1 step) its more flexible and easily supports multiparty (n of n) and even threshold signatures (k of n) which allows multisig in the space of one ECS signature (and without even disclosing the existance of k of n nor how big k or n is even), there are some arguments that ECS is more secure than ECDSA in its assumptions about hash properties.  To do multiparty with ECDSA is a research topic, even multiparty DSA is ridiculously complex and depends on the security of a homomorphic encryption instance big enough to hold temporary results involving powers of q eg the paillier cryptosystem with big keys, and threshold DSA on the even more complex Damgard-Jurik extended Paillier scheme.  The flexibility of ECS makes it more flexible for many things, eg the zero knowledge selective disclosure and blinding certification features of Brands certificates based on the representation problem (which is a kind of generalization of Pederson commitments, which is itself a generalization of schnorr).  There are a huge number of things you can do with Brands certificates towards smart contracts that preserve the privacy of the attributes of a person relying on smart contract by using ZK proofs of boolean formulae etc.  

Also for the cost of an extra signature per value you can even have unconditional value privacy.  (Ie a hypothetical all powerful entity able to perform discrete log with minimal effort still cannot tell how much money  you paid).  This is because like OTP all possible values are equally possible, eg with a pederson commitment two base points G, H then xG+yH there are n possible solutions for all possible values of x and y (where x is a secret key and y is a value you prove things about).  The powerful adversary can just solve and find all the possibilities but your public  recorded ZKPs do not show which x value you knew, nor which y was the value you transferred.

Will post more crypto level details and perhaps an openSSL based implementation presently.

Adam
20  Bitcoin / Development & Technical Discussion / synthetic USD & distributed auditable exchanges without a banking interface on: October 01, 2013, 12:12:50 PM
Hi

It occurred to me that one should be able to bootstrap a synthetic USD (or EUR etc) based only on an authenticated feed for the BTCUSD exchange rate (maybe validated against public order book, ideally with p2p blockchain settlement so you know MtGox et al aren't hacked or manipulating the rate) using conventional synthetic commodity financial mechanisms.

How synthetic commodities work is that it is possible to create eg synthetic gold or synthetic stock index without buying the underlying asset, with a matched option pair with exercise price at the current asset price: sell a call option to give away the rights to any upside, and use the proceeds to buy a put option for downside insurance (plus some commission/spread cost).  There are two types of options: american options (which can be exercised at anytime before expiry) and european options (which can only be exercised on the maturity date).  Other potential building blocks include CFDs (contract for difference).  Synthetic commodities work and are used in the financial world, the cost of creating them over buying the underlying asset is small provided there is a deep, liquid market in the options, and similarly they can track the underlying price closely with the same assumptions.  Now options have expiry dates, however the synthetic can be made ongoing by replacing expired, or exercised (in your disfavor) call options.  You do not actually lose in these events.  Similarly you can sell your synthetic back to bitcoin early at a small cost by reselling the put you bought (if not execised in as part of the sale) and buying back the call you sold.

Anyway read about how synthetic assets are created it in a financial reference tutorial or whatever.

The point for bitcoin is a liquid market in BTC denominated BTCUSD options you can hold BTC, and spend a few basis points/year to convert that into a synthetic USD holding (with enough option liquidity).

Such a liquid options market would have a second beneficial value for BTC in that people argue it would stabilize the BTCUSD exchange rate.

I cant imagine I'm the first to think of this, and I suspect bitshare and maybe mastercoin may be saying the same thing, however their financial terminology was non-standard to the point I couldnt understand if this is what they were saying for sure or not.

I would think smart-contracts can be written for the necessary options, so that the whole affair is digital and block chain settled and hence publicly auditable.  We do need more auditable block chain settled exchanges so that we can audit the BTCUSD order book directly, but that is something that needs to happen anyway.

Once you have a BTC backed synthetic USD with smart-contract options, you can do atomic trades for BTC.  Perhaps once it boot straps a bit you dont even need BTCUSD exchanges, you can p2p atomically and publicly auditably swap BTC for synthetic USD which trade itself can auditably define the exchange rate.

Of course I welcome any real financial wizards (or other) comments.

Adam
Pages: [1] 2 »
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!