|
Title: Provably fair puzzle for N-bit public keys Post by: garlonicon on August 05, 2023, 03:56:20 PM Recently, I started generating elliptic curves with less than 256 bits. I tried to reach secp256k1 bit-by-bit, by starting from the smallest elliptic curves, and going the whole way up to the full 256-bit version, to recreate the whole process. It is still work in progress, and I am currently trying to reach 40-bit curve.
However, I also thought of using that result for a different purpose: as a range proof. If some elliptic curve has for example 32-bit coordinates, then it is guaranteed that all private keys are just some 32-bit numbers. And then, I started to wonder, if it is possible to somehow map those public keys from the puzzle, to confirm that they are in a given ranges. Of course, the whole puzzle could be recreated in a provably fair way, if we assign x-value of the base point as a result of SHA-256 for empty string, shortened into N-bit value (or just modulo p-value, whatever), and then make a puzzle, where the goal will be to make a valid signature for some public key with unknown private key, for example where x-value is the smallest possible value, or another hash, for example double SHA-256 of the empty string (modulo p-value, or trimmed to N-bit value, does not matter). However, to execute it on Bitcoin, one piece is missing: the mapping between public keys. I know it could be done by some complex TapScript, but it is probably better to just reveal some P2TR address, with key-path only, and then reveal all details, how such public key was generated. Also, in case of elliptic curves, if you can generate some curve, it does not mean you can break it. If you can count all points, and get n-value, based on p-value, it does not mean you have to visit all of them. So, the whole purpose is to create some puzzle, where the creator could demonstrate, how keys were generated, and where the creator could not take those coins, without solving the puzzle by himself. So, the question is: how to make it provably fair, and execute it on Bitcoin? Because the current solution is to for example reveal "p=0xfffff9af, n=0xfffe390b, base=(0x1,0x3cad5d2d)", and then ask people to make a valid signature for "(0xbadc0df0,0x4ff3705d)" public key (or maybe "03 badc0df0" in compressed form, this is the nearest valid point, if you start with x=0xbadc0ded). Then, I assume if someone can do that for provably fair generator, and some other provably fair point, then that person can break any point on this 32-bit curve. But I wonder, if it is possible to map existing keys into other curves, especially all public keys from 160-bit to 255-bit range, which were revealed where the puzzle creator moved them into lower keys. To sum up: is it possible to take for example "02 e0a8b039282faf6fe0fd769cfbc4b6b4cf8758ba68220eac420e32b91ddfa673" public key, that is supposed to have 160-bit private key, and convert it from secp256k1 into secp160k1, to confirm that this key has only 160 bits? Or is it possible to attach some range proofs for each key in the puzzle, to confirm that all keys are in correct ranges? Or maybe it is somehow possible to take a secp256k1 generator, and create some 160-bit public key, in a publicly auditable way, where the creator could not take those coins without solving the puzzle? When it comes to range proofs, I still didn't fully explore the topic, but I heard they are used in Monero, to proof that all amounts are added correctly. So, maybe it could be possible to demonstrate, how such proofs could look like for all keys that are already known, and then the creator could visit the thread, and add proofs for other keys? What do you think? Title: Re: Provably fair puzzle for N-bit public keys Post by: gmaxwell on August 05, 2023, 08:18:21 PM google DLEQ.
Title: Re: Provably fair puzzle for N-bit public keys Post by: mamuu on August 06, 2023, 10:10:44 PM Recently, I started generating elliptic curves with less than 256 bits. I tried to reach secp256k1 bit-by-bit, by starting from the smallest elliptic curves, and going the whole way up to the full 256-bit version, to recreate the whole process. It is still work in progress, and I am currently trying to reach 40-bit curve. However, I also thought of using that result for a different purpose: as a range proof. If some elliptic curve has for example 32-bit coordinates, then it is guaranteed that all private keys are just some 32-bit numbers. And then, I started to wonder, if it is possible to somehow map those public keys from the puzzle, to confirm that they are in a given ranges. Of course, the whole puzzle could be recreated in a provably fair way, if we assign x-value of the base point as a result of SHA-256 for empty string, shortened into N-bit value (or just modulo p-value, whatever), and then make a puzzle, where the goal will be to make a valid signature for some public key with unknown private key, for example where x-value is the smallest possible value, or another hash, for example double SHA-256 of the empty string (modulo p-value, or trimmed to N-bit value, does not matter). However, to execute it on Bitcoin, one piece is missing: the mapping between public keys. I know it could be done by some complex TapScript, but it is probably better to just reveal some P2TR address, with key-path only, and then reveal all details, how such public key was generated. Also, in case of elliptic curves, if you can generate some curve, it does not mean you can break it. If you can count all points, and get n-value, based on p-value, it does not mean you have to visit all of them. So, the whole purpose is to create some puzzle, where the creator could demonstrate, how keys were generated, and where the creator could not take those coins, without solving the puzzle by himself. So, the question is: how to make it provably fair, and execute it on Bitcoin? Because the current solution is to for example reveal "p=0xfffff9af, n=0xfffe390b, base=(0x1,0x3cad5d2d)", and then ask people to make a valid signature for "(0xbadc0df0,0x4ff3705d)" public key (or maybe "03 badc0df0" in compressed form, this is the nearest valid point, if you start with x=0xbadc0ded). Then, I assume if someone can do that for provably fair generator, and some other provably fair point, then that person can break any point on this 32-bit curve. But I wonder, if it is possible to map existing keys into other curves, especially all public keys from 160-bit to 255-bit range, which were revealed where the puzzle creator moved them into lower keys. To sum up: is it possible to take for example "02 e0a8b039282faf6fe0fd769cfbc4b6b4cf8758ba68220eac420e32b91ddfa673" public key, that is supposed to have 160-bit private key, and convert it from secp256k1 into secp160k1, to confirm that this key has only 160 bits? Or is it possible to attach some range proofs for each key in the puzzle, to confirm that all keys are in correct ranges? Or maybe it is somehow possible to take a secp256k1 generator, and create some 160-bit public key, in a publicly auditable way, where the creator could not take those coins without solving the puzzle? When it comes to range proofs, I still didn't fully explore the topic, but I heard they are used in Monero, to proof that all amounts are added correctly. So, maybe it could be possible to demonstrate, how such proofs could look like for all keys that are already known, and then the creator could visit the thread, and add proofs for other keys? What do you think? I've run into a similar issue before. On a curve at p^6 about x3 +7 He was explaining that it includes x3+4 and how a point in x3+7 is mapped to x3+4. I am an amateur researcher I think you should have a look at this link https://crypto.stackexchange.com/questions/83542/how-to-convert-coordinates-o-a-point-from-y2-x37-to-y2-x34 |