Topic: Pay to contract with forgability (using a chameleon hash) (Read 5510 times)

Need to update this - found a problem a week back, but lost part edited tab:


There is a flaw in the logic in the last para.  If Bob is coerced into revealing c" and hence d is recovered (or he is coerced to reveal d directly), then anyone can do n^2 analysis of the n signatures (one real and n-1 forged) pairwise and see that all the forgeries derive from Alice's deterministically with the private key, but Alice's key cant be derived from any, and hence Alice's is correct.  Also Bob's only deterence to doing that at any time without coercion is revealing his private key.  The root cause of the failure is there is no new randomness in the process of forging chameleon hashes by Bob.

To the extent its still interesting if we change this much more, I think that might be repairable by having Alice not publish s (send it out of band to Bob, dont commit to it in the spend).  Then the chameleon hash becomes (r,c).  Alice cant find a different s that signs commits to a different message because she doesnt know d.  And Bob can recover k as sR=H(m)G+rcQ => sk=H(m)+rd so k = s^-1(H(m)+rd), and armed with k Bob can create s' for any signature.  Whats more this time those are all symmetric.  With d he can as plausibly recover k from (r,c),s' so Alice's message is indistinguishable as desired.

Not sure that overall is ECDSA like enough to be interesting and the schnorr method in
https://bitcointalksearch.org/topic/m.3417729 seems a lot simpler!

Adam

Perfectly put. The internet itself is basically a giant experiment in crypto-anarchy, as all but the very "worst of the worst" online bad guys are ignored by national governments, leaving it up to individuals and organisations to fend for themselves. My entire job at Google for the last 3+ years could be summed up as walling off Google's userbase from online anarchy, through cryptography and software (spam filters, obfuscated code, anti-hacking risk analysis etc).

So if someone wants to see what life is like in a crypto-anarchist "utopia", just go take a look at your ssh or postfix logs ...

I'm not complaining, by the way. The internet wasn't really intended to be a vast experiment in societal organisation, but I think it's the perfect place for trying such things out - it's a place where (by and large) a total failure of law enforcement and the state doesn't cause anyone to get hurt, just inconvenienced. So it's a pretty safe place to try out new things. Some of these things have worked and other things haven't. At the moment I'd say anarchy is winning - despite huge investments by private sector actors the internet is still flooded with hacking, scamming, disease, spam, trolling and sockpuppetry. Research like this work by gmaxwell is key to finding a way to make things work better, without falling back on the old blunt weapon of state intervention.

Catching up the thread from #bitcoin-wizards (plus some fixes and new observations) gmaxwell posed the question if you could make a chameleon hash that is also a valid ECDSA signature (with the added benefit being its a bit more bitcoin integratable).  Curiously it seems that you can and here's how:

ECDSA: R=kG, r=R.x, s=k^-1(H(m)+rd) where d is private key Q is public key Q=dG, G is base point, k is random; signature is (r,s).  A verification relation is: sR =? H(m)*G+rQ

Alice is using the hash, Bob is the owner of the private key able to forge hashed values.

Work backwards, choose r' random, compute point R=[r',f(r')] from curve equation f(x), then calculate T=H(m)*G+rQ.  Choose random s, compute R=s^-1*T so that sR=T, then can write sR=H(m)*G+r'Q however now r=R.x and r != r' (because R is some random point) so the r value is inconsistent with point R, adjust for that by finding Q'=cQ such that sR=H(m)*G+rQ', so c=r'/r, ie Q'=r'/rQ (then rQ'=r'Q as required).

Now we have a standard completely forged by Alice signature but not on Bobs public key but on a different public key Q' which is a known multiple c=r'/r of Q: Q'=cQ.  This key is mismatched with The ECDSA signature is (r,s), and the chameleon hash is (r,s,c) the secret value which allow Bob to modify the chameleon hash is c (the factor for modifying the public key Q'=cQ).

To reveal the hash in event of dispute Alice shows c (Q is anyway computable from r,s; and Q'=cQ).  Then anyone can check r,s is a signature of m with public key Q'=cQ.  The signature is verifiable without revealing c, but meaningless as no one knows who's key Q' corresponds to, not even Bob.

To forge different hashes Bob finds m' and Q" such that sR=?H(m')*G+rQ" so he has to find Q" such that H(m)*G+rQ'=H(m')*G+rQ" and as he knows d this can be written [H(m)+dr'/r]*G = [H(m')+dc"]*G where Q"=c"Q.  So solve to find c"=[H(m)-H(m')+dr'/r]/d and therefore Q"=c"Q.  Bob can show (r,s,c") and anyone can check r,s is a signature of m' with public key Q"=c"Q.

One comment in the paper Greg referenced in OP is Bob forging reveals his private key in some protocols (which is obviously no good, its more than an inconvenience as it also destroys the non-transferability if his private key leaks people can check which hash the private key can be computed from to know which is the forgery).  In this case as c'=[H(m)-H(m')+dr'/r]/d = [H(m)-H(m')]/d+r'/r so d can be recovered d=[H(m)-H(m')]/(c"-r'/r).

However its rather easy to fix this, instead of revealing Bob revealing c" or Alice revealing c they can prove knowledge of a discrete log of Q" or Q' in base Q using... an ECDSA signature with base Q and public key Q" or Q' respectively.

However even that does not quite work the same way as the other chameleon hash because Alice can reveal c also to create a strong proof (where a signature involving c but not disclosing c is a weak proof) and it can be seen that it does not solve to d.  

While its different thats actually a feature, as if Alice reveals a strong proof, Bob's forgery is not plausible as he cant make strong proofs - if he does it reveals his private key which makes it obvious his messages are forgeries.  (In the paper and the above Schnorr related scheme, in fact even if Alice does reveal her proof, an arbitrator cant tell which message was Alice's and which was Bob's, so in theory Alice could falsely claim to have made one of Bob's forged messages, though it assumed this is not generally a threat).

Conversely Bob could be coerced into proving that a forgery he makes is not authentic, by showing c" (instead of a DL proof of knowledge of c") which then allows his private key to be recovered.  However Alice doesnt give Bob c, so Bob cant prove that Alice's message was not his, he could be lieing and actually have c.

So overall that seems like a slightly stronger chameleon hash property. So we get the new benefit of no forgery ability for Bob if Alice reveals a strong proof, and yet no ability for Bob in the normal case to transfer proof of what Alice said.  He could reveal weak forgeries, and Alice's message is indistinguishable from them.  He could make a strong forgery (reveal c") which reveals his private key, but that still doesnt prove that Alice's weak forgery was authentic - they could both be Bob's and he could be lieing about not knowing the secret value c (discrete log of Q' wrt to Q).

Adam

Yes this is very true and a big potential for smart-contracts.  It is possible smart-contracts maybe more important than bitcoin itself.  Its a pre-singularity AI that can automatically and perfectly fairly apriori avoid disputes resulting from reneging, aborting and extorting virtual good exchanges.  Surely its better to mathematically avoid the possibility of a dispute occurring than to pay a lawyer $500+/hr and court fees to try sort it out after the inevitable happens when you rely on reputation (like ebay) and trust etc.

Smart-contracts also have huge potential in financial disintermediation, think about the trillions per year spent into the financial intermediaries for doing nothing but writing, and acting as middle man in contracts for financial products, and holding escrow funds, matching orders; with smart-contracts you could write your own structured product, and it does not need escrow and its self-enforcing and executing and survives the financial institution going bankrupt so less systemic risk also.


Yes.  I would say abstractly that the more of law and contract law is implemented in mathematically enforced code with pre-emptive impossibility of crimes, the less reliance on courts which are unreliable, biased or subject to political interference, uneven enforcement etc its a huge financial and human capital cost saving and a reduction in the need for and influence of governments in human existence.  And that is good because governments have inherent systemic problems, so less government is better.  All roads lead to Rome

Adam

Indeed, the provider of the public key used it the chameleon hash could be entirely independent of the parties making the transaction.  I don't doubt that it would even be possible to construct a threshold chameleon hash, where some N of M parties were required.

Thank you for the excellent explanation too.

One thing that I'd like to add is that the methods of crypto-anarchy are still useful in the context of a society which is largely politically dissimilar. For example, some contracts people form are _too low value_ to effectively use the kinds of tools to ensure honest dealing in wider western societies today (e.g. courts) or the easy centralized alternatives facilitate rent seeking (e.g. having to pay to use a game server in order to play a game with your friends, you all have network access and powerful computers, what do you need the server for?).  If mathematical tools exist that allow cheat proof interacting they are often inherently scalable— we can apply them to high value things and low value things alike, because once they're coded they're nearly free.

Having good tools at our disposal allow societies to pick appropriate tools for appropriate situations, and we can all only benefit from that.

Another analogy, its rather similar to why Ian Brown & I wrote the non-transferable PGP signatures draft (1998) and why Ian Goldberg's OTR (off-the-record) encrypted messaging protocol involves non-transferable signatures: you want the protocol to have properties that are aligned with the users interests, and to not have unintended and negative to you side-effects.

When you're chatting in IM or email, its probably not your intention to create a legally binding non-repudiable permanent quotable provable record.  Really its not, and there are many people who got burnt for saying off the cuff things, that even ended up in court to their pain, so anything that increases the unintended consequences of making that unintentionally non-repudiable is BAD for the user.

Its in your interest to be sure that the party you are talking with is who you think it is, and not an impostor, and if you dont sign messages anyone can pretend to be anyone even with PGP encryption; but if you sign non-repudiable PGP signatures, the person you are talking with can renege on the implied confidentiality of a personal message and transfer that signature and show it to other people against your will, as the signature is verifiable by anyone.  A non-transferable signature evaporates when its shown.  

In the non-transferable PGP sense its very simple you sign a random (session) symmetric encryption key, and MAC the message with it, and encrypt the key for the recipient.  Now he can write any message he wants with that MAC key, but he knows he didnt write it himself and so he knows its authentic as you signed it.  k=random, SIG(k), c=MAC(k,m), PKENC(B,k,c) something like that.  OTR is doing something similar but interactive.

The Chameleon hash signature has the same kind of designed to be aligned with user's interests design objective.

Adam

I think you maybe dont understand the concept of smart contracts and anarcho-capltalism (as embodied by crypto-anarchy where crypto means cryptography, and I guess not anarchy also, just an egalitarian society without a force monopoly form of government).  Basically the idea is using new crypto concepts its possible to contract without threat of violence/imprisonment as a disincentive to cheating, because the contracts are atomically self-enforcing.

You might find sci-fi "Snow Crash" by Neal Stephenson interesting, and "Cyphernomicon" by Tim May a kind of crypto-anarchist manifesto (online http://www.cypherpunks.to/faq/cyphernomicron/cyphernomicon.html) (not to be confused with "Cryptonomicon" another sci fi work by Neal Stephenson, also fun but long and somewhat related).

To quote Wei Dai from his motivation section intro to B-money (one of the main bitcoin precursors):

http://www.weidai.com/bmoney.txt


I am not sure if Satoshi had crypto-anarchy in mind but folks like Tim May (cypherpunks co-founder/cyphernomicon), most of the cypherpunks, and people working on ecash like myself (Hashcash, distributed mining), Wei Dai (b-money) / Nick Szabo (bitgold), Hal Finney (RPOW), and most of the digicash tech guys (David Chaum long defunct payer anonymous ecash company), zero-knowledge systems guys (pre-Tor privacy networking) and others working on ecash 1995-2005 certainly did have that in mind as their burning motivation.  I am also guessing Chris Odom (open transactions) who seems to enjoy distributed Chaum servers, with voting pool backing, though I cant speak for him.

Since that time finally I also see some hope of political progress in the form of the meteoric rise of Rick Falkvinge & the pirate party (and the Libertarian party eg folks like Ron Paul to the extent the LP was slowly rising towards having a chance of being elected), but previously (eg back in 1995 - 2005) it seemed almost the only hope for humanity was a new wave of technological progress led shifts.  In the same way that the internet tends to topple undemocratic states, non-state controlled free money tends weaken the grip of to varying degrees systemically corrupt and difficult to reform governments.

[EDIT: btw other than the internet, another example of technological led power shift was the discovery of public key encryption and the ready availability of PGP, and later other communication security/privacy iike OTR, Tor etc.  The fact that many governments tried to control access to and restrict encryption, before giving up, should tell you that you need to be using it: they were worried they can less control a populace with cryptographic free speech and cryptographic freedom of association, even those are legal rights in most countries, cryptographic enforced rights are more strongly held than legal rights, because as we see from Snowden, legal rights arent worth the paper they are written on.  The reason they gave up is it became an untenable position for a notionally free democracy to enforce.  More restrictive regimes tend to have more restrictive crypto usage regulations.]

Anyway you can use bitcoin without caring about libertarian politics or its technical adjunct crypto-anarchy eg because its technically cool, or because you dislike governments doing money printing/quantitative easing to the benefit of connected banks, and detriment of individuals, or bank deposit seizures (like in Cyprus) or as a speculative investment, or because its faster and cheaper, or available in all countries, even without banking infrastructure and onwards  And by doing so, in a neutral non-political way, you are also helping build the crypto-anarchic future, in the same way that promoting internet use indirectly helps topple dictators.

But I do recommend anyone to read the Cyphernomicon and Snow Crash it might just open your mind to a new view point or even convert you.  [EDIT I guess Assange et al's book "Cypherpunks" is probably on the money though I havent read it myself.]

Circling back to why forge a contract, thats not the point: the point is the contracting parties should be free to contract without interference from outside parties (criminal or government) and the point of a chameleon hash based signature (or nearly equivalent designated verifier signature) is that the evidence evaporates because its intentionally non-transferable - they cant renege even if they wanted to.  Designated verifier is a bit different as that means it convinces the recipient (Bob), but neither Alice nor Bob can prove/transfer the signature as either party could forge; with chameleon hash signatures only Bob can forge.  

Also bear in mind that other than the fact of shaming a pseudonym (Bob) and tarnishing his reputation that's may not be much of a disincentive, and another model is for the parties to agree on an arbitrator who has 3rd vote in 2 of 3 multisig.  Probably you can use two designated verifier signatures so the the arbitrator could also have forged the contract.

Adam

Man, I'm certainly glad to not live in Sweden!
This doesn't achieve the goal. We want Alice to be able to prove to the world that bob is behaving in an untrustworthy way, but we do not want Alice or Bob to be more vulnerable to being coerced into making their private arrangements proven to the public than they would be otherwise. I don't think it's too much to ask that when we adopt a security measure to protect against one thing that we not become weaker against different attacks.

Under the scheme presented here after Alice and Bob are thoroughly happy that things are settled, if they are concerned about coercion risk they could even publish the chameleon hash key... then anyone could produce a fake invoice and thus the pay-to-contract would no longer be persuasive of the specifics of their arrangement.

In that case, even if you lived in a place with terrible inhumane people who would punish you for acting to save your life against a threat of immediate death you still wouldn't have to have been the person to have made a forged contract.

How do you mean here? Normally, in most societies, its frowned upon presenting a forged contract. For example here in sweden, its illegal to present a forged contract, even if you do it in a response to a threat or coercion.
Even if a gangster member puts a pistol to your forehead, making up a forged contract and presenting it to the gangster member can get you in prison. The correct way to do it, is to present the original contract and then reporting the threat to the local authorities.


Normally, the safeguard when handling contracts, is that you should NEVER EVER put anything that you want to keep for yourself, into a legal contract.
In sweden, we handle secrets by referring to attachs.
For example: "This buy contract obligies Sebastian to pay XX SEK to a bank account number. This bank account number is referred to in attach #1".

attach #1 is then kept a secret, so if the contract gets into a Court, the attach #1 is never revealed to the public, only the contract and the judge's decision is revealed.
Same is done for example in a Court if someone here in sweden has a protected identity, for example a important witness.
Then they refer it to "Party A", "Party B" etc.

And then in a secret attachment which is only accessible to the police, it says like:
"Party A: name namesson, avenue street 12, 123-12 BigCity"
"Party B: Test Testsson, Home street 9, 999-12, SmallCity"


Of course, the attach's also needs to be a such way so they don't affect the outcome of the contract, eg you cannot keep a price or important parts of the agreement secret or something like that.




Same could be done here, eg put a reference mark, like "attach #1" in the contract to refer to secret data.

Occurs to me it can be even simpler and use EC discrete log for more compact keys (RSA keys are 3072-bit for security equal to 256-bit EC): relabelling t to be k to be more Schnorr like:

A=kG+mQ where recipient knows d from dG=Q.

now recipient can compute A=k'G+m'Q as he knows k and m, and x: r=k+md mod n (r is same as from Schnorr signature in fact) and then k' = r - m'd = k+(m-m')d mod n.  m would probably be H(msg).

(A real schnorr signature is A=kG, r=k+cd, c=H(a,m); verify: rG=?A+cQ).

Adam

btw a simpler chameleon hash involving conventional crypto can be seen as part of this indistinguishable shortcut hashcash variant based on RSA.  https://bitcointalksearch.org/topic/m.3307636

Just replace the search for t =? h( s, i, a, m ) mod 2^k (where i is an iterator, s salt, a initial witness, m message to sign) with t=h(m).  Then make random c, chameleon hash a=c^t mod n. Chameleon hash is (c,t=H(m)a).  Bob has p & q so he can compute different t'-th root, for (c',t'=H(m'),a) from c'=a^(1/t') mod n where t'=H(m'), where as Alice can only go in the forward direction choose c, hash mesage to make t, raise c to power of t. 

I use it to create a hashcash variant with an indistinguishable short-cut which you could think of as a chamleon proof of work (a chameleon much repeated hash, or a single exercise of the trap door holders private key).

I am guessing no one has thought of that particular chameleon hash construct for some reason because people do not usually reach for the esoterics gap DH or bi-linear DH unless they run out of flexibility with conventional hardness assumptions and need the extra degree of freedom.  I could be off base, but this also does not leak the private key, and that seems to be the implication of the paper you referenced with the improved Chameleon hash.

Adam

If Bob is known exclusively via his point— e.g. Bob is a well known trader who's activity is associated with that point, you're done.  Alice can show that what she paid to was contract + Bob's point.  Otherwise, you need PKI.

I guess the first step "publish the point" is critical. I don't see what stops Alice from simply running this protocol with herself, and then saying "Look, Bob agreed!". Then Bob says "I never heard of Alice" and we're back to step one.

If Bob has to publish his point for each transaction that takes place, how do we know it's Bob's point? It seems like we're back to square one ...

Motivation:

Alice wants to pay Bob according to some mutually agreed terms, and doesn't want Bob to be able to later claim that the terms were different.

One way that people have proposed to accomplish this is pay-to-contract:

Bob publishes an EC public point for which he knows the private key.
Alice computes H(contract) and adds this value to Bob's public point, we'll call the result a contract key.
Alice sends funds to 1 of 2 {Alice Pubkey, Contract Key}.
Bob, knowing both his private key and the contract can derive the private key and redeem the payment.

If the contract gets forgotten (or Bob decides that he didn't like Alice's last minute negotiations) Bob can fail to redeem it and Alice can retrieve the funds.

If Bob fails to make good on the deal, Alice can show people the contract and everyone can see that Bob agreed to it (by virtue of redeeming the coins).

Pay to contract reduces the importance of authentication in payment, because we know that necessarily anyone who redeemed the coins knew the contract.

One problem with pay-to-contract is that a third party could potentially coerce Alice or Bob into revealing the contract. The situation for pay to contract is worse than what you have if, instead,  Bob had just given Alice a regular signed invoice which specified the address for Alice to pay, because if someone attempted coercion to obtain the contract Bob could sign a forged contract and give them that instead.

This might not really be much of a problem in practice, and it could be solved with the simple expedient of always destroying contracts after they are fulfilled... but I thought it was worth making a note that it's possible to retain the forgability in the context of pay to contract.

Pay to contract with forgability:

Alice, and Bob agree on a contract. The message hash in the above basic pay-to-contract protocol is replaced with a chameleon hash (such as this one based on gap-DH, or really any other one this protocol doesn't need the secret preservation property). Bob additionally sends Alice a public key and random value for the chameleon hash, and the protocol proceeds as normal.

A chameleon hash is a hash function that takes a message, a pubkey, and a random value. The function is designed so that it works as a strong hash function but the holder of the corresponding private key can produce free collisions. E.g.  he can easily find an random2 for message2 such that CH(message,random,pubkey) == CH(message2,random2,pubkey).

So if someone attempts to coerce the parties into handing over their contract Bob can produce a forged contract that matches the pay to contract transaction and this forgery is indistinguishable.

If Bob cheats Alice, Alice can still publish the original contract and the public can be satisfied that Bob is behaving unreliably. (Even if Bob goes on to publish other forgeries, it doesn't matter which one is the original for the purpose of showing that Bob's behavior was unreliable).

This gets you back to the same security against coercion as a signed-invoice while allowing the use of pay-to-contract.

If stronger non-repudiation is required two chameleon hashes could be used— cascaded on top of each other— one keyed by Alice and one keyed by Bob so that both parties must cooperate to produce a forged contract.