Bitcoin Forum
December 18, 2017, 01:17:09 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Distributed Transaction Signing  (Read 1254 times)
AsymmetricInformation
Member
**
Offline Offline

Activity: 115


View Profile WWW
February 28, 2014, 09:47:07 PM
 #1

Hi,

I am attempting to design a piece of software which 1] uses a blockchain, 2] uses Bitcoin as a currency within this blockchain.

Unfortunately I have no crypto experience and low dev experience so the details of this are a little over my head. Does anyone know how a distributed piece of software might sign Bitcoin transactions? Is that possible somehow?

More details here (<2 pages): https://github.com/psztorc/Truthcoin/raw/master/docs/Development%20Plans/Design%20Question.pdf

I sketched up an idea where an application watches the longest valid chain of Blockchain 2 (B2), and (as new B2 blocks are discovered) takes the 'withdrawal requests' embedded in a "confirmed block" (say, 20 blocks beneath the current), and constructs/signs their Bitcoin transactions.

I have some questions about this:
* Can we derive (and use) private keys for an application such that they are never known to users? Can I prove that I don’t know/can’t use a private key?
* Can we hide private keys in an application that we widely distribute? To what extent could this application be open-source/trustworthy?
* Can we use randomness (chaotic inputs, or iterative randomness with block-hashes/nonce) to derive keys? Can such a piece of software copy itself or be copied?

* Is there a better way?

Thanks!

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
1513603029
Hero Member
*
Offline Offline

Posts: 1513603029

View Profile Personal Message (Offline)

Ignore
1513603029
Reply with quote  #2

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

Posts: 1513603029

View Profile Personal Message (Offline)

Ignore
1513603029
Reply with quote  #2

1513603029
Report to moderator
1513603029
Hero Member
*
Offline Offline

Posts: 1513603029

View Profile Personal Message (Offline)

Ignore
1513603029
Reply with quote  #2

1513603029
Report to moderator
1513603029
Hero Member
*
Offline Offline

Posts: 1513603029

View Profile Personal Message (Offline)

Ignore
1513603029
Reply with quote  #2

1513603029
Report to moderator
AsymmetricInformation
Member
**
Offline Offline

Activity: 115


View Profile WWW
March 04, 2014, 03:00:22 PM
 #2

Bump (it was buried after I posted last Friday afternoon).

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
andytoshi
Full Member
***
Offline Offline

Activity: 170

-


View Profile
March 04, 2014, 08:42:25 PM
 #3

Unfortunately I have no crypto experience and low dev experience so the details of this are a little over my head. Does anyone know how a distributed piece of software might sign Bitcoin transactions? Is that possible somehow?

You are playing with fire and for the sake of the community I strongly encourage you to stop.

Please read this document:
https://download.wpsoftware.net/bitcoin/alts.pdf
AsymmetricInformation
Member
**
Offline Offline

Activity: 115


View Profile WWW
March 04, 2014, 11:39:39 PM
 #4

Unfortunately I have no crypto experience and low dev experience so the details of this are a little over my head. Does anyone know how a distributed piece of software might sign Bitcoin transactions? Is that possible somehow?

You are playing with fire and for the sake of the community I strongly encourage you to stop.

Please read this document:
https://download.wpsoftware.net/bitcoin/alts.pdf


Hey thanks for your interest.

As can be seen directly from your quotation there, I am directly asking someone else to do the firefighting.

The document you listed made a number of claims, almost none of them true/related to what I am trying to do. One example (of many) is that the paper claims that one should avoid departing from the trusted path of the Bitcoin software, and that is exactly where I intend to remain (the system I have in mind is an exact copy of the Bitcoin system with different block validation rules). If you read anything about the project you would know it is more like Namecoin/Bitmessage, not a true "Altcoin".

I am simply asking about a type of Oracle (whose legitimacy has already been established by Gavin, Mike Hearn, and others), but also leaving the design open to a more general solution.

I also don't feel that you represent the community, as, to the contrary, other senior community members have encouraged me to continue.

With respect, you comment was completely ignorant and unhelpful. If you continue to make comments of this low quality I intend to use the forums 'Ignore' feature. I hope for your own sake you will apologize for your misunderstanding.

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2366



View Profile
March 04, 2014, 11:58:12 PM
 #5

I actually asked Andy to respond to you and point you to his paper because your post concerned me and I thought the caution and historical context his writeup provided was highly applicable.

What you're asking its not generally possible in an anonymous system.  A signature proves the knowledge of a secret. In an anonymous distributed system there can be no secret. (Ignoring the question of effective program obfuscation being possible— which is hotly debated, and is not currently practical in any case, and even assuming it is, it is if this task can be accomplished without trusted initialization in any case).

If your system was not anonymous but had predefined membership then you could have a distributed secret— but there is no known way to do an ECDSA threshold signature directly. You could however use multisig in an enumerated entity (non-anonymous) distributed (but not decenteralized) system, and you can find a lot of information on that.  Alternatively, in a non-anonymous system multiparty computation could be used to use a shared key which is known to no one— but again not practical at this time, and not really any better than just multisig for this sort of application.

(And I provide this advice in some fear that you'll continue heedlessly to the cautions provided here— but I also want to make it clear that the response to you is fully in good faith, and trying to be helpful)

Generally the questions you're asking indicate to me that you haven't done that basic reading just to understand what things in cryptography are hard/easy and/or dangerous vs safe and that you have a lot of learning left to do that goes beyond the scope of the limited questions you're asking here.

I think oracle work is pretty interesting, but talking about things that would be highly cutting edge cryptography (if possible at all) ... isn't necessary for basic oracle work and should only be done with heavy research and caution.

Bitcoin will not be compromised
AsymmetricInformation
Member
**
Offline Offline

Activity: 115


View Profile WWW
March 05, 2014, 12:34:29 AM
 #6

What you're asking its not generally possible in an anonymous system.  A signature proves the knowledge of a secret. In an anonymous distributed system there can be no secret. (Ignoring the question of effective program obfuscation being possible— which is hotly debated, and is not currently practical in any case, and even assuming it is, it is if this task can be accomplished without trusted initialization in any case).

Hey thanks for your response.

I know that I don't have a lot of specialized knowledge here, but here me out because I'm not sure you are understanding my question: my suggested solution proposes a separate blockchain which does NOT contain the secret. Perhaps my title is bad ("ambitious") because there is no 'distributed signing'.

The secret is in a separate bare-bones software which is watching the second blockchain, in the manner that Mike Hearn described a hypothetical piece of software watching Google. From this, I assumed that one could compile binaries such that the source code / private key could not be re-derived (an assumption I came here to check with experts). Moreover, in the longer description I mention possible obfuscation techniques such as using the hash of a block as a source of randomness.

I hope you don't feel I'm wasting anyone's time. If you can explain how:
a) an Oracle can sign a transaction upon Mike Hearn winning a gold medal as reported by Google...
...is fundamentally and unalterably different from...
b) an oracle can scan a blockchain and sign transactions embedded within it after certain criteria are met
...then I'll close this specific request.

I'm sorry to disagree with your friend but his essay contained the following "sections":

Quote from: Linked Paper
5 Cryptography of Bitcoin 1: transactions and signatures.
[explain how transactions, scripts, signatures work] [\list stupid shit alts have done to these things
and how they’re stupid
]
6 Cryptography of Bitcoin 2: distributed consensus.
[explain distributed consensus works, risk of forks, incentive issues, etc] [\list stupid shit alts have
done to these things and how they’re stupid]

Clearly that is a draft but that's hardly an excuse imho. I strongly feel that Altcoins are disrespectful to Satoshi and the work that is done here, but if you expect anyone to take a piece of writing like that seriously you are crazy.

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
andytoshi
Full Member
***
Offline Offline

Activity: 170

-


View Profile
March 05, 2014, 12:37:11 AM
 #7

I am simply asking about a type of Oracle (whose legitimacy has already been established by Gavin, Mike Hearn, and others), but also leaving the design open to a more general solution.

It is important to realize that in cryptography, arguments by authority have no validity. There have been cryptosystems created by experts, with mathematical proof of security and decades of use, which eventually failed nonetheless. To develop cryptosystems, it is important to have a deep understanding of the underlying primitives and the contexts in which they can be safely used. This in itself is a gargantuan task which will likely take you years of research, even without attempting to develop your own primitives. (And as I explained in my article, it is never necessary or wise to use home-baked primitives, though it is good practice to develop and break them in private.)

Further, Gavin and Mike's conception of oracles may not correspond to your own conception. In all areas of research there are massive concepts hidden behind small words, and cryptography is no exception.

Quote
I also don't feel that you represent the community, as, to the contrary, other senior community members have encouraged me to continue.

With respect, you comment was completely ignorant and unhelpful. If you continue to make comments of this low quality I intend to use the forums 'Ignore' feature. I hope for your own sake you will apologize for your misunderstanding.

I apologize for my terse tone. The fact is that this forum has thousands of users with more enthusiasm than understanding, and it can be overwhelming at times. I have only so much time in the day, and sadly I am not paid to post here (though I am paid to do cryptographic research). In fact I have been part of the bitcoin community for several years, and have been quite active in its research community for a good part of that.

My low post count and short replies reflect this situation. To compensate I have been developing several articles to correct and explain common misconceptions, including the one that I posted for you, which as you noticed is not yet finished. I'm glad that you took the time to read it and I hope that it provided some perspective about the nature of Bitcoin-related work.

If you'd like to learn more about modern cryptography, I encourage you to check out Matthew Green's blog (as a starting point, read every single post and reference), as well as some classic papers such as "Probablistic Encryption" by Goldwasser and Micali.

DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
March 05, 2014, 12:44:25 AM
 #8

Quote
From this, I assumed that one could compile binaries such that the source code / private key could not be re-derived (an assumption I came here to check with experts)

I will save you some time.  That is a completely false assumption.  Don't feel bad it has been made by people who should know better over and over throughout history.  DRM is an example of a secret hidden in the software (or media) such that the user can't gain access to the secret even though they have access to the media or software.  No form of DRM running on an open system has survived cryptoanlysis over an extended period of time.  To date the reward for breaking DRM has been the ability to duplicate a game or movie, here you are talking about increasing the reward to be stealing money.  I would put the over/under on timeframe to being broken wide open at a week (maybe a month if the implementation is particularly novel).

If you are talking about dedicated hardware devices the attack becomes more difficulty but not impossible.  Private keys have been recovered from smart card chips and even FIPS rated hardware security modules.  Once again if the system becomes widespread the reward could mean potentially millions of billions of stolen wealth so "difficult" is simply not good enough.  Furthermore those systems wouldn't be provably secure and would be highly centralized.

If the user has access to the software and the software has the secret the user has (or will eventually gain) access to the secret.  If that were not true the rate of software piracy would be approaching ~0% by now.  People have been working on this "solution" for decades.

Since this is an X-Y problem it is very likely novel use of cryptography could be used to achieve the goals you state but not through the method you describe.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2366



View Profile
March 05, 2014, 12:48:40 AM
 #9

The secret is in a separate bare-bones software which is watching the second blockchain, in the manner that Mike Hearn described a hypothetical piece of software watching Google.
Mike was describing a case where a system watching google is trusted to perform faithfully, or is a member of a collection of such identified semi-trusted systems where it is trusted that no more than some threshold will behave dishonestly.  This is normally what we're talking about when we talk about oracle mediated contracts.

Quote
Moreover, in the longer description I mention possible obfuscation techniques such as using the hash of a block as a source of randomness.
It is a hotly debated subject in theoretical cryptography if practically secure obfuscation is possible even in theory— even assuming many things which would make the effort insecure, impractical, or simply useless. It is not currently _practically_ possible in any case.

Quote
I hope you don't feel I'm wasting anyone's time. If you can explain how:
a) an Oracle can sign a transaction upon Mike Hearn winning a gold medal as reported by Google...
...is fundamentally and unalterably different from...
b) an oracle can scan a blockchain and sign transactions embedded within it after certain criteria are met
...then I'll close this specific request.
There isn't— but your question was unrelated to these points as far as I can tell.  There are actually secure ways to achieve the latter other than oracles, however, at least in theory (google coinwitness) but practice is another matter. (And, amusingly, not the former, because SSL doesn't provide non-repudiation)

Bitcoin will not be compromised
Crowex
Member
**
Offline Offline

Activity: 111


View Profile
March 05, 2014, 03:29:52 AM
 #10

If your system was not anonymous but had predefined membership then you could have a distributed secret— but there is no known way to do an ECDSA threshold signature directly.

http://oleganza.com/blind-ecdsa-draft-v2.pdf

I know you commented on the original proposal of this but it was changed by the author and, as far as I can see, it now works. I just thought I'd link to it because I thought it was a clever idea that got buried in the forum.
In some sense it is a 2 of 2 threshold signature with one of the signatories blinded. However this signature could be performed unblinded and there may be ways to extend it to different threshold schemes.
 I don't know if this would be considered as doing an ECDSA threshold signature directly? and there might be problems with the idea that I don't understand but it is an interesting idea.

EDIT I realise that this isn't quite what you are talking about in terms of threshold signatures as the threshold is 100% so apologies if the link isn't too relevant.
andytoshi
Full Member
***
Offline Offline

Activity: 170

-


View Profile
March 05, 2014, 03:41:42 AM
 #11

If your system was not anonymous but had predefined membership then you could have a distributed secret— but there is no known way to do an ECDSA threshold signature directly.

http://oleganza.com/blind-ecdsa-draft-v2.pdf

I know you commented on the original proposal of this but it was changed by the author and, as far as I can see, it now works. I just thought I'd link to it because I thought it was a clever idea that got buried in the forum.
In some sense it is a 2 of 2 threshold signature with one of the signatories blinded. However this signature could be performed unblinded and there may be ways to extend it to different threshold schemes.
 I don't know if this would be considered as doing an ECDSA threshold signature directly? and there might be problems with the idea that I don't understand but it is an interesting idea.



That's a neat idea, to use oleganza's scheme as a threshold signature. However, you can't simply execute this scheme unblindedly. If the blindsigner knows all of a, b, c and d then he can determine the entire private key and create signatures all on his own. But if he doesn't know all of those, there is no way that he can be sure of what he is signing (or even of the public key that he is signing with). So this is a threshold signature in some sense... but a very unnatural sense.
Crowex
Member
**
Offline Offline

Activity: 111


View Profile
March 05, 2014, 04:28:12 AM
 #12



That's a neat idea, to use oleganza's scheme as a threshold signature. However, you can't simply execute this scheme unblindedly. If the blindsigner knows all of a, b, c and d then he can determine the entire private key and create signatures all on his own. But if he doesn't know all of those, there is no way that he can be sure of what he is signing (or even of the public key that he is signing with). So this is a threshold signature in some sense... but a very unnatural sense.

I haven't got time to really look into it at the moment so this might be incorrect but wouldn't you only have to reveal a and b and the original hash to unblind? and this wouldn't reveal t. You could keep c and d secret.
 
andytoshi
Full Member
***
Offline Offline

Activity: 170

-


View Profile
March 05, 2014, 04:34:14 AM
 #13

You can tell the blindsigner what a and b are, but he can't guarantee that you're not lying to him without also knowing c and d.

Also, there is another problem with using oleganza's scheme as an ordinary split-key scheme: it is not publically verifiable. That is, without revealing enough parameters to expose the private key, you cannot prove to others that the blind signer was actually involved in creating the signature.
AsymmetricInformation
Member
**
Offline Offline

Activity: 115


View Profile WWW
March 05, 2014, 06:11:46 AM
 #14

It is important to realize that in cryptography, arguments by authority have no validity.
If only all pursuits were so noble.

I apologize for my terse tone. The fact is that this forum has thousands of users with more enthusiasm than understanding, and it can be overwhelming at times. I have only so much time in the day, and sadly I am not paid to post here (though I am paid to do cryptographic research). In fact I have been part of the bitcoin community for several years, and have been quite active in its research community for a good part of that.
I understand completely. I have many friends, some of whom I might call "empty suits" behind their back. To their face I challenge them to be more self-critical.

Consider this: if someone were to pay for help, they'd be smart to ask for the free help first. And they might then know whom to hire.

My low post count and short replies reflect this situation. To compensate I have been developing several articles to correct and explain common misconceptions, including the one that I posted for you, which as you noticed is not yet finished. I'm glad that you took the time to read it and I hope that it provided some perspective about the nature of Bitcoin-related work.
It is pretty interesting. Ironically, I drafted an essay on Altcoins to basically the same purpose but from a completely different perspective, a microeconomic or even psychological one. I talked all about how "money is a network" obviating the need for a second Internet-Dollar, why exactly the market prices would always be so connected / non-diversified, how the cost of time to research an altcoin produced a completely sunk cost making it better to just buy every new thing reguardless of its non-utility (if you were rich enough and feared competition), how early miners were rewarded with purchasing power and want to "do that again" hence introduction of Litecoin (even though in steady state mining on more expensive hardware would increase centralization).
Then I just gave up and said anyone who doesn't get this by now can just enjoy their own funeral.

If you'd like to learn more about modern cryptography, I encourage you to check out Matthew Green's blog (as a starting point, read every single post and reference), as well as some classic papers such as "Probablistic Encryption" by Goldwasser and Micali.
Will do.

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
Crowex
Member
**
Offline Offline

Activity: 111


View Profile
March 05, 2014, 06:18:31 AM
 #15

You can tell the blindsigner what a and b are, but he can't guarantee that you're not lying to him without also knowing c and d.

Also, there is another problem with using oleganza's scheme as an ordinary split-key scheme: it is not publically verifiable. That is, without revealing enough parameters to expose the private key, you cannot prove to others that the blind signer was actually involved in creating the signature.

 I agree, the public verification is a problem. But it seems so close to a threshold scheme I am wondering if a similar construction could be used to achieve this. Maybe revealing T and showing that it could only have been constructed with the knowledge of p and q. Probably needs a lot more thinking about.  Smiley
AsymmetricInformation
Member
**
Offline Offline

Activity: 115


View Profile WWW
March 05, 2014, 06:32:05 AM
 #16

I would put the over/under on timeframe to being broken wide open at a week (maybe a month if the implementation is particularly novel).

Ok, now we're talkin. I did not know this, so very helpful answer. Probably best to try a different approach rather than try to get blood from a stone.

However, you are saying that it IS possible, just only for one week, so I have a pretty bizarre idea: Can the obfuscated software spawn a "child", a newly obfuscated copy that wakes up and generates a new keypair? The "adult" then sends the money it is guarding to its child, and dies.

Blocks would have to include some ID or something of the child, which the parent could even sign. After its ID is stamped into a block "Child" becomes the new "Adult".

If the user has access to the software and the software has the secret the user has (or will eventually gain) access to the secret.  If that were not true the rate of software piracy would be approaching ~0% by now.
I was just assuming the developers leaked keys to their friends, or that people cut out the check-for-license part even if they couldn't fully read it.

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
andytoshi
Full Member
***
Offline Offline

Activity: 170

-


View Profile
March 05, 2014, 12:16:28 PM
 #17

I agree, the public verification is a problem. But it seems so close to a threshold scheme I am wondering if a similar construction could be used to achieve this. Maybe revealing T and showing that it could only have been constructed with the knowledge of p and q. Probably needs a lot more thinking about.  Smiley

But if the message-holding party knows p and q, then she can construct the entire private key and sign messages herself. Basically the problem is that only the message-holding party knows the public key that is being signed with, and as long as any of a, b, c or d is secret, she is welcome to lie about this, and she can use this lie to trick the blindsigner into signing something he doesn't want to.

I agree it seems close. But it's not Smiley It's a worthwhile exercise spending a few days trying to extend oleganza's scheme to do something other than his specific blind-escrow scenario. You will see that the security breaks every time you get it to do something interesting.

However, you are saying that it IS possible, just only for one week,

No, that is not at all what DeathAndTaxes is saying, and this kind of complete lack of understanding is exactly why I opened with my "don't roll your own crypto" article.

I added a 'Where do I go from here?' section to alts.pdf (and blocked in some ideas for what I want to talk about in the "stupid shit" sections). If you actually want to do cryptography you should go read that.
AsymmetricInformation
Member
**
Offline Offline

Activity: 115


View Profile WWW
March 05, 2014, 07:15:31 PM
 #18

However, you are saying that it IS possible, just only for one week,

No, that is not at all what DeathAndTaxes is saying, and this kind of complete lack of understanding is exactly why I opened with my "don't roll your own crypto" article.

As soon as I typed that I thought "that other guy is going to hate this". It was just a little idea, Andy, you can relax! Smiley

Moreover the secret-keeper-Oracle was just my guess at how to make the blockchain aware of an external state. I'm not surprised to learn that it didn't work, but I do expect something to work eventually. So far gmaxwell has proposed I investigate SNARK, for example. Others have suggested Etherium or MasterCoin but, precisely as was argued, these newer ideas can't be seriously considered yet. I also considered a true alt-currency which can just be moved around in two different ways (directly through transactions and indirectly through the contract mechanism), which might be at least a practical place to test everything out.

So I have all kinds of guesses, but I expected that, instead of taking them as proposals, someone would say "Don't do that, what you really need sounds more like X".

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!