Bitcoin Forum
March 29, 2024, 04:55:24 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 [4] 5 6 7 »  All
  Print  
Author Topic: Elliptic curve math question  (Read 13986 times)
mndrix
Michael Hendricks
VIP
Sr. Member
*
Offline Offline

Activity: 447
Merit: 258


View Profile
December 01, 2011, 12:50:38 AM
 #61

The above discussion suggests a technique for two-party escrow without transaction scripts.

  • Bob wants to sell Alice goods for Bitcoin payment.
  • Alice generates key pair (a,A) and sends A to Bob.
  • Bob generates key pair (b,B) and sends B to Alice.
  • Alice sends payment to the address corresponding to A+B.  At this point, neither Alice nor Bob can spend the funds.
  • Bob verifies payment was sent to address A+B and ships the goods to Alice.

If Alice receives the goods as expected, she sends 'a' to Bob.  He uses the private key a+b to sweep funds to his own address.  If Alice never receives the goods, she withholds a and the funds are permanently lost.  If Bob wants to refund the payment, he sends 'b' to Alice and she uses the private key a+b to sweep funds to her own address.

If the transaction goes well and all messages are public, third parties can verify that Alice fulfilled her part of the deal.  This could form an part of a p2p exchange with partially-provable reputations.
1711688124
Hero Member
*
Offline Offline

Posts: 1711688124

View Profile Personal Message (Offline)

Ignore
1711688124
Reply with quote  #2

1711688124
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1711688124
Hero Member
*
Offline Offline

Posts: 1711688124

View Profile Personal Message (Offline)

Ignore
1711688124
Reply with quote  #2

1711688124
Report to moderator
1711688124
Hero Member
*
Offline Offline

Posts: 1711688124

View Profile Personal Message (Offline)

Ignore
1711688124
Reply with quote  #2

1711688124
Report to moderator
1711688124
Hero Member
*
Offline Offline

Posts: 1711688124

View Profile Personal Message (Offline)

Ignore
1711688124
Reply with quote  #2

1711688124
Report to moderator
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1063


Gerald Davis


View Profile
December 01, 2011, 05:33:08 AM
 #62

mndrix I like it.   Clever use of partial keys. 
BTCurious
Hero Member
*****
Offline Offline

Activity: 714
Merit: 503


^SEM img of Si wafer edge, scanned 2012-3-12.


View Profile
December 01, 2011, 07:09:04 AM
 #63

Yeah, that would work pretty well, and can actually be done right now.
With the new changes (BIP0011) it will also be possible to include a 3rd party, who can give the coins to either A or B in a dispute.

partially-provable reputations
When coin-picking is implemented in most wallets, reputations can be proven fully, by sending from address X, where address X is well-known as being a reliable trader. Alternatively, during negotiations, one can just sign a message with his well known address' key, and the counterparty can verify that that's actually this guy. This can be done right now with 0.5 I think.

mndrix
Michael Hendricks
VIP
Sr. Member
*
Offline Offline

Activity: 447
Merit: 258


View Profile
December 01, 2011, 05:22:41 PM
 #64

partially-provable reputations.

I originally meant that observers have no way to verify that Bob sent the goods.  However, I realized last night that Alice publishing 'a' implies that she received the goods and therefore that Bob sent them.  If Bob's goods happened to be reversible, such as a PayPal payment, he could chargeback later, so I suppose it's still only partially provable in that case.

As BTCurious mentions, a signature mechanism is necessary to make sure the Alice and Bob in the transaction you watched are the same Alice and Bob you think they are.
Red Emerald
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500



View Profile WWW
December 01, 2011, 05:55:13 PM
 #65

The above discussion suggests a technique for two-party escrow without transaction scripts.

  • Bob wants to sell Alice goods for Bitcoin payment.
  • Alice generates key pair (a,A) and sends A to Bob.
  • Bob generates key pair (b,B) and sends B to Alice.
  • Alice sends payment to the address corresponding to A+B.  At this point, neither Alice nor Bob can spend the funds.
  • Bob verifies payment was sent to address A+B and ships the goods to Alice.

If Alice receives the goods as expected, she sends 'a' to Bob.  He uses the private key a+b to sweep funds to his own address.  If Alice never receives the goods, she withholds a and the funds are permanently lost.  If Bob wants to refund the payment, he sends 'b' to Alice and she uses the private key a+b to sweep funds to her own address.

If the transaction goes well and all messages are public, third parties can verify that Alice fulfilled her part of the deal.  This could form an part of a p2p exchange with partially-provable reputations.
I like it!  Reading stuff like this makes me want to delve deep into EC math, but I just don't have the time.

The only problem is if Alice receives the payment and doesn't transmit a, then Alice has the goods and Bob has no funds.  Alice doesn't have the funds either, at least.  I guess if you want that level of assurance, you can use scripts.

DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1063


Gerald Davis


View Profile
December 01, 2011, 06:11:10 PM
Last edit: December 01, 2011, 11:03:37 PM by DeathAndTaxes
 #66

The only problem is if Alice receives the payment and doesn't transmit a, then Alice has the goods and Bob has no funds.  Alice doesn't have the funds either, at least.  I guess if you want that level of assurance, you can use scripts.

And damaged rep and others can verify she hasn't paid.  There is no way to ensure a thief can't kill a payment without a human third party arbitrator.  Still I think that is somewhat unlikely.  Alice has the goods she gains nothing by witholding payment however she risks damaging her rep so it is a net loss to withhold payment.  If you are that concerned about that event then a true escrow w/ arbitrator is the only secure method but even that isn't a guarantee the human making the decision could either side against you or could be in collusion w/ Alice.  Undecided
PrintCoins
Hero Member
*****
Offline Offline

Activity: 533
Merit: 501


View Profile
December 01, 2011, 11:00:12 PM
 #67

Can anyone write up a simple python module for handling this?

I am guessing it would have two methods:
def combinePublic(pubA, pubB):
   //Person A creates a public address and private key. He gives the public address (pubA) to Person B
   //Person B creates a public address (pubB) and private key
   do some magic and return pubC


def combinePriv(privA, privB):
   //do basically the same with private keys (this should create the priv key for pubC)
   do some magic and return privC

It might be something that can all be done with one method. I am willing to admit I am way out of my depth though.

It would be great if Mike and I could basically co-sign each other's money this way. It would add to the cost, but the user would have little doubt that either of us have the private key. The double hologram would also mean that both would need to replicated to produce a useful counterfeit.

BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1129

All paid signature campaigns should be banned.


View Profile WWW
December 01, 2011, 11:12:25 PM
 #68

Mike knows exactly how to do this - he did it in the example above to prove the concept.

So you two should get together!

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
casascius (OP)
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1386
Merit: 1135


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
December 01, 2011, 11:17:42 PM
 #69

It would be great if Mike and I could basically co-sign each other's money this way. It would add to the cost, but the user would have little doubt that either of us have the private key. The double hologram would also mean that both would need to replicated to produce a useful counterfeit.

Rob, have you called or e-mailed the hologram guys yet?  Each of my last two orders took 5-6 weeks.  I would be willing to co-sign.

I am asking them to quote me on some rectangular holograms that would be perfect for bills.  Regardless of what I do, you could probably do them as well.

By the way, they of course aren't the only provider of holograms in town.  But the hologram adhesive (that shows honeycombs if you sneeze on it wrong) from these guys is so good, I don't dare go anywhere else.  Many of the other samples I have played with are too easy to peel off intact.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
PrintCoins
Hero Member
*****
Offline Offline

Activity: 533
Merit: 501


View Profile
December 02, 2011, 12:19:34 AM
Last edit: December 02, 2011, 12:40:30 AM by robkohr
 #70

It would be great if Mike and I could basically co-sign each other's money this way. It would add to the cost, but the user would have little doubt that either of us have the private key. The double hologram would also mean that both would need to replicated to produce a useful counterfeit.

Rob, have you called or e-mailed the hologram guys yet?  Each of my last two orders took 5-6 weeks.  I would be willing to co-sign.

I am asking them to quote me on some rectangular holograms that would be perfect for bills.  Regardless of what I do, you could probably do them as well.

By the way, they of course aren't the only provider of holograms in town.  But the hologram adhesive (that shows honeycombs if you sneeze on it wrong) from these guys is so good, I don't dare go anywhere else.  Many of the other samples I have played with are too easy to peel off intact.

Yep, and I can see why you charge the price you do for your coins. The holograms are more expensive than the metal by far. Since I have to do a double sided my bills may out cost you coins. I might have to consider some super adhesive cheap alternative backing to prevent scanning through the reverse side of the bill. Otherwise I might just have to switch to coins or plastic.

Edit : Maybe Gorilla Tape. It would be a pain to work with though. I can see my wife coming into the garage while I am working and me being on the floor with Ron Paul bills stuck all over me.

casascius (OP)
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1386
Merit: 1135


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
December 02, 2011, 01:03:32 AM
 #71

Holo's are cheap if you order a ton of them, it's the setup that costs so much.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
netrin
Sr. Member
****
Offline Offline

Activity: 322
Merit: 251


FirstBits: 168Bc


View Profile
December 02, 2011, 01:40:29 AM
 #72

Hey guys, thanks for all the input, particularly the http://www.certicom.com links. I intend to come up with a bunch of baby-step examples, perhaps over the weekend, that hopefully my mother could follow.

I once studied abstract algebra, so this isn't totally foreign to me, but I'd prefer to read (python) code rather than latek math notation, if anyone wants to donate some code to the cause.

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
netrin
Sr. Member
****
Offline Offline

Activity: 322
Merit: 251


FirstBits: 168Bc


View Profile
December 02, 2011, 01:48:27 AM
 #73

BTW, I had said earlier that I wouldn't trust this system, because then I'd have two entities who I'd have to trust not to screw up. However, this additive stuff should make it at least possible to verify each private/public pair - who screwed up. Out of curiosity, is it possible to combine many more pairs?

(privA + privB) + ... + (privY + privZ) --> (pubA + pubB) + ... + (pubY + pubZ)

And does doing so weaken the key strength? Is each component (A,B,C...Z) easier to crack than the additive result, or do they all contain just as many bits and are just as seemingly random?

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1063


Gerald Davis


View Profile
December 02, 2011, 02:35:28 AM
 #74

BTW, I had said earlier that I wouldn't trust this system, because then I'd have two entities who I'd have to trust not to screw up. However, this additive stuff should make it at least possible to verify each private/public pair - who screwed up. Out of curiosity, is it possible to combine many more pairs?

(privA + privB) + ... + (privY + privZ) --> (pubA + pubB) + ... + (pubY + pubZ)

And does doing so weaken the key strength? Is each component (A,B,C...Z) easier to crack than the additive result, or do they all contain just as many bits and are just as seemingly random?

Each private key can contains as many bits as the unified private key.  The entropy of each private key depends on the method used by the creator.  Even if one key is weaker due to flawed implementation it is still stronger than a single key because you will need all the sub-keys to construct the unified private key.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1129

All paid signature campaigns should be banned.


View Profile WWW
December 02, 2011, 02:44:24 AM
 #75

Just to answer your specific question about multiple key pairs.  You can add together as many public keys as you want to and the corresponding private key will be the sum of all the private keys.  I (and some others) are trying to come up with a way to use this property in a little side project we are working on.  In our project, depending on how popular it gets, we may be adding together hundreds or even thousands of public keys and the private key would then be the sum of all the corresponding hundreds (or thousands) of private keys.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
netrin
Sr. Member
****
Offline Offline

Activity: 322
Merit: 251


FirstBits: 168Bc


View Profile
December 02, 2011, 03:36:46 AM
 #76

Was anything secret that might be easier to compute with multiple public addresses, for example this 'G' value that is common among all key calculations?

* or was the G (base point) necessarily public anyway?

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1129

All paid signature campaigns should be banned.


View Profile WWW
December 02, 2011, 03:46:21 AM
Last edit: December 02, 2011, 07:37:14 AM by bwagner
 #77

G is a public published value.

In compressed form it is:

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

and in uncompressed form it is:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Each private key is secret but even if you have all but one of them you cannot calculate the last one you need to get to the final public key.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
casascius (OP)
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1386
Merit: 1135


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
December 02, 2011, 05:48:29 AM
 #78


G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8


Bitcoin only uses the uncompressed form.  It's worth pointing out that this number is actually a structure, because it represents a "point", not just a scalar value.

A "point" has an X and Y coordinate.  The first byte, 04, means this uncompressed format, and can be considered a constant.  The next 32 bytes are X, and the next 32 bytes are Y.

Constant = 04
X = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Y = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416
Merit: 277


View Profile
December 02, 2011, 06:35:27 AM
 #79

X = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Y = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

so in decimal

x=55066263022277343669578718895168534326250603453777594175500187360389116729240
y=32670510020758816978083085130507043184471273380659243275938904335757337482424
p=115792089237316195423570985008687907853269984665640564039457584007908834671663

y^2 = x^3 + 7 - p * 1442042049659660869506300006036683750029629333882594701370927246876626245108435 922902327776681700708714008192087431130951749952236093997894375239788520937

The equation of the curve is y^2=x^3+7 mod p

ByteCoin
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1129

All paid signature campaigns should be banned.


View Profile WWW
December 02, 2011, 06:58:18 AM
 #80

What I think would be interesting is to verify:

y^2 mod p = ( x^3 + 7 ) mod p for G:

1) Calculate y^2 mod p, get answer

2) Calculate ( x^3 + 7 ) mod p, get answer

I believe that answer from 1) should equal answer from 2)

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Pages: « 1 2 3 [4] 5 6 7 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!