Editing Atomic cloud storage (section)

= The download contract =

Renters have to pay to store files on Farmers and there shouldn’t be any way for either party to cheat. As a renter – I should only have to pay to retrieve content that I actually uploaded – and I shouldn’t be able to withdraw my money after a farmer graciously provided me with those services. Further more – the farmer should only get paid for providing such services.

<span id="forming-the-download-contract"></span>
== Forming the download contract: ==

# The renter and the farmer build an ECDSA key pair and exchange hashes of the public keys.
# They then reveal the public keys for the corresponding hashes.
# The public keys are added together using elliptic curve addition.
# This results in a new ECDSA public key whose private key can only be found by adding together both private keys from the renter and farmer.
# The renter generates an AES private key and encrypts their content with that.
# The renter uploads the resulting ciphertext to the farmer.
# The farmer and the renter encrypt their copy of the ciphertext (producing a new ciphertext) with the additive key from step 3. This can be done with something like ElGamal [8].
# The farmer gives back the SHA 256 hash of the resulting ciphertext.
# The renter checks the hash matches the hash of their own “ECDSA encrypted” content and saves a copy of the hash.
# If the content matches their hash – the renter makes a payment to a special Bitcoin address that requires the Farmer to reveal their private key from step 1 (details given later) to spend the coins.

<span id="to-download-a-file-the-process-looks-like-this-9-10"></span>
== To download a file the process looks like this [9] [10]: ==

# The renter downloads the content back from the farmer.
# The renter checks that the returned content matches the hash.
# The renter and farmer sign a series of special transactions that allow the renter’s funds to be claimed by the farmer by revealing his private key.
# When the farmer broadcasts his transactions it simultaneously reveals the secrets needed for the renter to decrypt her file.

'''What’s interesting about this is that its atomic:''' the renter either pays to store a file which can be downloaded back in the future or the process fails and they get their money back. The problem is: how do you build a Bitcoin transaction that forces the farmer to reveal their private key?

There certainly are no OP_CODES that are capable of doing that . . . (well – there are some but it requires brute forcing a special ECDSA private key which is computationally expensive for both parties [12].) Instead, we’re going to do something kind of special. We’re going to build a transaction scheme that involves signing a chain of transactions in such a way that the signatures that the farmer uses are … provably insecure.

The farmer ''must'' use these insecure signatures if they want to claim their coins – and the act of doing so is enough to allow the renter to derive their private key. But how is this done? Well, its based on doing something that you should normally never do – reuse the same number used for an ECDSA signature – and as long as the renter knows what the farmer signed they have the information needed to reconstruct the private key [13].

There’s only one problem with that – the renter needs to know that a serialized transaction actually contains these weak ECDSA signatures before signing the transaction chain … and ''without'' knowing what the signatures actually are when they sign the transaction (because otherwise they could use this to derive the key before they should know it in the protocol.)

<span id="zero-knowledge-proofs-to-the-rescue"></span>
== Zero-knowledge proofs to the rescue ==

In Bitcoin, the transaction isn’t signed directly – only the hash of the inputs and outputs based on the SIGHASH settings. This is the key to this protocol. Here’s what’s going to happen. The farmer is going to construct a special transaction template containing their signatures but they are only going to reveal part of the transaction – specifically – they are going to reveal everything except the second half of their signatures [14].

Now what the renter does with this knowledge is create a zero-knowledge SHA 256 proof for the transaction ID (preimage since its double SHA256 hashed) that asserts that a given SHA 256 resulted from using that partial transaction. The preimage for the hash is only partial – the renter doesn’t know the second half of the signature – they only care that the farmer has reused the same R value for two signatures in the same transaction.

Thus - if the farmer can prove that a given hash satisfies these constraints - the renter and the farmer can proceeded with the protocol to create the download contract without either party cheating the other.

Ah yes … but then what’s to stop the farmer from simply changing their signatures after the renter signs, you ask? Well, did I mention the transaction goes to an output that requires the signature of both farmer and renter to redeem – and that further – this requires that the TXID for the transaction containing the weak signatures not to be mutated?

And that previously – the outputs that the weak signature transaction are redeeming requires that the signatures be valid? This is how you force someone to reveal private keys as part of a smart contract scheme without doing anything crazy like producing a zero-knowledge proof validating an entire ECDSA key-generation process (my original idea.)
[[File:1.png|thumb]]
# The renter creates a new transaction TX1 that can be claimed by either: A 3 of 3 multi-sig address OR a time-locked output + the renter’s signature (refund fail-safe.) The multi-signature uses the same public key twice that the farmer previous generated and one of the renters – meaning the farmer must give two signatures to redeem the outputs.
# The farmer generates TX2 that spends the outputs of TX1 to another multi-signature address controlled by the renter and the farmer. This multi-signature address uses totally different ECDSA key pairs to what has been previously generated. (TX2 can also be redeemed after the contract expires by the renter in case the farmer only partially completes the protocol.)
# The farmer signs TX2 using duplicate R values for the signature but ''does not'' reveal the transaction content to the renter.
# The renter signs TX2 and gives the signature to the farmer.
# The farmer now has a complete copy of TX2 and could broadcast it if they wanted. However they don’t since they don’t currently have the renter’s signature for TX3 (which would guarantee payment back to them.) Instead, the farmer reveals the SHA 256 hash of the full serialized transaction + the R value used for both signatures. ''Note: This is not a double SHA 256 hash – just the result of hashing the full serialized transaction once.''
# The renter generates a zero-knowledge key pair [15] that validates the serialized transaction format. The proof assets that the weak ECDSA signatures were used in the serialized transaction that resulted in the given SHA 256 hash. The renter gives the proving pair to the farmer.
# The farmer produces a zero-knowledge proof for their SHA 256 hash and gives it to the renter.
# The renter validates the proof – if the proof is valid - the renter SHA 256 hashes the hash to produce a TXID. The TXID is used as the input for TX3 which the renter signs, giving the signature to the farmer.
# The farmer validates the signature. If it’s correct – the farmer now has enough information to generate a valid TX3.
# The farmer broadcasts TX2 which outputs to TX3. When TX2 is confirmed, TX3 will allow the farmer to claim there money. Note: that the process of releasing TX2 gives the renter all the information necessary to decrypt their file.

<span id="generating-zero-knowledge-proofs"></span>
== Generating zero-knowledge proofs ==

Generating zero-knowledge proofs is tedious in practice and we’re not going to write any of the code to do this directly. Instead, we’ll just adapt the code that Snarkfront [16] uses for their test_sha.cpp file [17].

Would you believe it – the code already does exactly what we need – it allows us to validate that a preimage matches a given SHA 256 hash as well as assert custom constraints on the preimage – which then become part of the proving and verification key pair.

The way that it does the additional custom constraints is also quite simple: you have a preimage – say the word “test” and you can specify a pattern – lets say eq = t??t. This would work if the preimage really did include a word starting and ending with the letter “t” (plus producing the expected hash of course - the most important part.)

<syntaxhighlight lang="shell"># Zero knowledge proof with satisfied constraints (should pass)

$ echo "hello" | ./test_sha -b 1 -p BN128 -d f572d396fae9206628714fb2ce00f72e94f2258f -e ??ll -n a?a

# Note – the code may need to be modified to accept binary data as hex
# strings but that would be trivial for any C++ programmers.</syntaxhighlight>
This software can then be used to create a preimage template for the serialized hash. We don’t actually care what the second half of the signature is so that just becomes ''????? …'' in the equal string. What we care about is that the R values in the signatures are duplicates and that this preimage matches the expected SHA 256 hash.

There’s no need to even worry about validating the sigs directly because if the farmer uses invalid signatures then the transaction won’t confirm and the renter is only signing the next transaction that has that invalid signature TX2 as the input – so Bitcoin does the ECDSA sig validation for us [18].

And … with that we just created a provably insecure signature scheme and then used it directly in a chain of transactions that indirectly pay someone to reveal their ECDSA private keys by reusing R values in signatures [13]. The process now serves to reconstruct the secrets needed to be exchanged to complete a homomorphic encryption scheme for the download based on ECC addition which we then adapted to use ElGamel type stuff [8] [19] to turn it into a public key crypto scheme. Next up: auditing contracts.

<span id="the-audit-contract"></span>