Re: The use of Guy Fawkes Signature

[qrius1111]

i like the simplicity of the guy fawkes signature algorithm but i have some questions. firstly, is this how it would work?

1) i generate some private keys (just large random alphanumeric strings)
2) the corresponding public keys are just a hashes of the private keys and the addresses are just the base58 encoded public keys
3) i create a transaction string (tx1) which has:
- input scripts consisting of private keys which evaluate to the previous transaction's output addresses
- hashes and indexes for each txin to locate the previous txouts
- output elements containing bitcoin values and recipient addresses
4) i hash tx1 to get tx1hash. now create tx2 = tx1. remove all private keys from the input scripts of tx2, place tx1hash somewhere in tx2 - probably as the first input script. maybe place something like op_nop for the remaining input scripts in tx2 (to conserve space).
5) i broadcast tx2 to the network. nobody yet knows whether it is valid.
6) i wait for a safe number of blocks to be confirmed on top of tx2 then broadcast tx1 with the private keys fully visible to all.
7) miners confirm that the hash of tx1 indeed evaluates to the input script of the first input of tx2 and so they include tx1 in the blockchain aswell

if this is how it would work then:

- would step (5) create the possibility for ddos on the network? it seems that nodes should relay the transaction without knowing whether it is valid. there is no way to check whether tx2 is valid or not until tx1 is broadcast at a later date. with bitcoin at the moment this validation is handled by scriptsigs, but this would not be possible with fawkes signatures i think?

- i'm not too familiar with the protocol, so hopefully this isn't a dumb question, but would any code changes be necessary to get this working as bitcoin currently stands? what are the criteria for a miner to include a transaction into the block? this seems like the critical aspect.

[gmaxwell]

Please don't bump many months old threads with new posts that are only partially related. The prior post was about using the fact that (rarely, sadly) the public key is not known, but only its hash to provide some recovery in the event of a serious advance in ECDSA.

You're asking how a Guy Fawkes signature would work generally.

By itself, this kind of scheme has significant problems with denial of service attacks. Potentially you could invoke POW to help, but doing so likely just shifts around the denial of service problems.

If you're actually just looking for hash based alternatives for signing, what you want is a lamport signature. Also note that if you mine a lamport signature but tree-structure the transaction so that you can prune the bulk of the signature the long term result left in the chain is the same as a Guy Fawkes signature... but you have instant verifiability, greatly simplifying the DOS situation.

Separately, it's possible to instead use a zero knoweldge signature of knowledge to prove you know the pre-image of a hash without revealing it. But all the schemes for this that I know of which have proof size competitive with a lamport signature also require asymmetric cryptographic constructs which might fall based on the same compromise as ECDSA.

The criteria to include a transaction?  It has to satisfy the rules specified in the scriptPubKeys in the coins that it is spending. There is no way for a past scriptpubkey to impose constraints on future script pubkeys (doing so can have some pretty negative results if used poorly), so I don't believe there is any straightforward way to implement a Guy Fawkes signature in Bitcoin without at least soft-forking changes to the protocol... but that no loss without a way to prevent DOS.

[qrius1111]

my bad. i'm new to the forum and i probably got the etiquette wrong. actually i thought i had posted in the wrong place but probably someone moved my post here haha

i'm also new to cryptography and bitcoin so i was mainly just checking that my understanding of how a guy fawkes signature would be implemented for bitcoin was correct. ecdsa is obviously fine for the next few years at least but if by that time bitcoin's market cap is in the trillions then the incentive to crack ecdsa private keys in under 10 minutes will be very great. is sure seems unlikely from where i stand, but i'd rest easier knowing there were post-quantum alternatives available at any time.

as you say, two possible fixes for the guy fawkes dos attacks are proof of work and zero knowledge signatures. for the pow i'm guessing this would have to be easy enough for a mobile device to implement, yet also difficult enough that a powerful computer could still not do dos attacks. i can see no solution using pow.

zero knowledge may offer some promise though. apparently there is a zero knowledge proof for a hash pre-image which does not involve disclosing the pre-image - http://crypto.stackexchange.com/questions/1767/proving-knowledge-of-a-preimage-of-a-hash-without-disclosing-it  i'm not sure if this is the type of zero-knowledge proof you mention, which relies on the same public key properties as ecdsa though.

finally regarding lamport signatures - this sounds like a good option but for the additional size requirements. if the blockchain were distributed in chunks across many nodes with much redundancy then this would open a lot of doors to implementing signature schemes which take up more space.

[qrius1111]

a couple more thoughts on proof-of-work and zero-knowledge-proofs for hash functions.

previously i was thinking that proof-of-work might be unfeasible because of the computational power differences between smartphones and large computers (eg botnets). however i wonder if this could not be substantially eliminated, if not fully eliminated by carefully choosing the proof-of-work method. for example, litecoin's hashcash-scrypt has properties which give all machines roughly the same computing power. sure there is variability but its no way near as big as sha256 where a single asic can be many orders of magnitude faster than a cpu.

so maybe careful selection of the pow algorithm could level the playing-field between devices and make this a valid method of cutting down on network dos attacks when using fawkes signatures. hashcash-scrypt does this by introducing memory into the algorithm, but another way might be to introduce milestones into the algorithm. for example, if we wanted to make it so that the proof of work always took 5 seconds to complete then maybe we could make it so that the algorithm had to fetch 5 consecutive pieces of information to complete the proof of work - one each second - as they come available on the network. i'm no cryptographer and i can already see exploits for such a thing, but maybe some algorithm like this exists. or maybe hashcash-scrypt would be sufficient for the purposes of such a cryptocurrency?

as for the zero knowledge proof of the hash function, i finally found the video which is mentioned in the crypto-stackexchange answer previously mentioned, however this seems to be specific for sha1. still, that might be a feasible algorithm and method

[qrius1111]

i think i have come up with a way to prevent dos attacks on a fawkescoin network. the private key in the txout being spent must consist of two components which are then hashed separately and concatenated. then one of these can be revealed when broadcasting the transaction hash to the network, while keeping the other secret for the transaction validation after the safe number of blocks.

so the new steps are:

1) i generate some private keys (just large random alphanumeric strings)
2) each address is derived from two private keys, like so: addr = base58(hash(pk1) + hash(pk2)) where "+" is just concatenation.
3) i create a transaction string (tx1) which has:
- input scripts consisting of private keys (pk1 only) which evaluates to the first half of the previous transaction's output addresses
- hashes and indexes for each txin to locate the previous txouts
- output elements containing bitcoin values and recipient addresses
4) i hash tx1 to get tx1hash. now create tx2 = tx1. replace all private keys (pk1) in the input scripts of tx2 with pk2, place tx1hash at some known location in tx2 - probably using opcodes to specify it within the first input script.
5) i broadcast tx2 to the network. miners confirm that it is valid because the now fully visible private keys (pk2) in the input scripts of this transaction each reveal half of every output address in the specified txouts from past transactions. so this transaction gets added to the blockchain.
6) i wait for a safe number of blocks to be confirmed on top of tx2 then broadcast tx1 with the private keys (pk1) fully visible to all.
7) miners confirm that the hash of tx1 indeed evaluates to the input script of the first input of tx2 and so they include tx1 in the blockchain aswell
as per standard bitcoin procedure, the recipient(s) of the funds from this transaction should wait a safe number of blocks before spending to ensure their received funds exist on the main blockchain