lightning_snark_test.txt

Hi all,

An obvious privacy limitation with lightning is that even with onion
routing, differents hops can be associated as being part of the same
transaction due to sharing a common R value. So if you see a HTLC from
Alice to Bob, paying $5 to Bob on receipt of R where SHA(R)=12345..;
and you see another HTLC from Carol to Dave, paying $4.95 to Bob on
receipt of R under the same condition, SHA(R)=12345..., then you know
it's part of the same transaction.

If you could change R at each step in the route, this would go away,
improving payment anonymity and making it harder to attack the system in
general.

That's hard, because as a forwarding node, if you receive a HTLC payable
on R1, then to send a HTLC payable on R2, you need to be able to
calculate R1 from R2 or you'll be out of pocket. But you also can't be
able to calculate R1 *without* R2, or you could just rip off whoever's
making the payment. And, of course you have to know SHA(R2) to forward the
payment at all. And if you only know SHA(R1) and SHA(R2) it's hard to
say anything at all about R1 and R2 because cryptographic hash functions
are designed to make any structural relationships go away.

BUT! I think the magic of SNARKs [0] lets you do this!

With a SNARK, you can "prove" that you have some secrets (ie, R1 and R2)
that satisfy some programmable condition (ie, SHA(R1)=H1 and SHA(R2)=H2
and R1=R2 XOR X), based on public inputs (H1, H2 and X), without revealing
those secrets.

I think that's pretty safe, because if you receive an HTLC asking for a
preimage for H1, along with instructions in the onion saying ask Bob for
a preimage for H2, and here's X and a proof, then either:

 - your forwarded HTLC will fail, and everything's fine

 - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1)=H1 as
   expected, and everything's fine

 - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1) != H1,
   which is only possible if the cryptography behind SNARKs are broken

 - you'll receive RX, such that H2=SHA(RX) but RX being too
   long or too short. If SNARKs aren't broken, this means that you know
   R2alt and someone else knows R2 that are different but hash to the
   same value, meaning SHA has been broken.

It seems like there are research-level tools out there that actually
make this practical to try out. I've had a go at implementing this using
snarkfront [1]. Using it looks like:

1) initial setup of proof/verification keys

 $ ./test_lightning -m keygen > keygen.txt  # global setup

2) generate a proof, using a 32 byte secret, and XOR key (64 hex digits)

 $ SECRET="the quick brown fox jumps lazily"
 $ XOR=$(echo "she sells sea shells" | sha256sum | head -c64)
 $ cat keygen.txt |
     ./test_lightning -m proof -s "$SECRET" -x "$XOR" > proof.txt
   m: proof.
   f: .
   b: .
   x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
   F: 74686520717569636b2062726f776e20666f78206a756d7073206c617a696c79
   B: 221fb676bda3964ad9b6c4e5166a7eba716c2d5ea1c9985b3c18b8d7faece56b
   #F: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
   #B: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
   generate proof
   (6) ..................................................
   (5) ..................................................
   (4) ..................................................
   (3) ..................................................
   (2) ..................................................
   (1) ..................................................

3) Verify the proof:

 $ F=ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
 $ B=166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
 $ cat keygen.txt proof.txt |
     ./test_lightning -m verify -h "$F" -b "$B" -x "$XOR"
   m: verify.
   f: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
   b: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
   x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
   verify proof (6) (5) (4) (3) (2) (1) 
   proof is verified

4) Verify it doesn't report a valid proof with different inputs:

  $ cat keygen.txt proof.txt |
     ./test_lightning -m verify -h "$B" -b "$F" -x "$XOR"
   m: verify.
   f: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
   b: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
   x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
   verify proof (6) (5) (4) (3) (2)
   proof is rejected

Some results:

 * the proof/verification key data take up about 100MB -- in theory
   one set of this data can be used by everyone; the only catch is
   that everyone has to trust that nobody has kept the original random
   numbers used to generate it.

 * proof/verification key data takes about a minute to generate,
   and about 650MB of RAM.

 * the proof data itself (which would need to be sent to the node that's
   going to switch R's) is just 864 bytes; so it'd use up about 5 hops
   worth of onion routing at 192B per hop -- in a 4096 byte packet eg,
   you could have four hops, changing R each time; or you could have 9
   hops, changing R only three times.

 * generating the proof data for a given R1,X pair takes about 10
   seconds, and 260MB of RAM

 * verifying the proof is quick-ish -- it takes 0.5s on my laptop,
   and uses about 150MB of RAM.

For comparison, that last point makes a SNARK verification 500+ times
more expensive than an ECDH operation. If I got my maths right, you
can translate 3c for a linode CPU-hour into 2.5 satoshi for a linode
CPU-second (at $338/BTC), so you're probably looking at a minimum fee
of a few satoshi per SNARK verification, but that's still pretty okay
for transactions of 500 satoshi or more, ie anything more than about a
fifth of a US cent.

The 10s proof generation time is probably more of a limitation -- though
you could generate them in advance easily enough and just store them until
you need to use them, which would avoid lag being a problem at least. But
even then it's still essentially adding up to 30c of additional costs to
your transaction (ie 10s cpu time valued at up to 3c/s), which probably
isn't worthwhile for transactions smaller than a dollar or two.

A drawback is that you'd either (a) have to do all this on the merchant's
side (not just sending SHA(R) to whoever wants to pay you, but sending
SHA(R1), SHA(R2), SHA(R3), SHA(R4), X12, X23, X34, and three proofs,
which would be pretty painful; or (b) you'd have to generate all the
R secrets as a consumer, and you wouldn't get to use the fact that you
know R as evidence that you paid the merchant.

Anyway, it's obviously not ready for prime time today: SNARKs are still
pretty new as a concept; I'm definitely not familiar enough with SNARK
theory to be sure I'm not misusing the concept somehow; snarkfront may not
have implemented the theory fully correctly; and I might not have captured
everything I needed to in order for my "proof" to actually say what I
want it to. So not a great idea to use this to protect real money today.

But still, this seems like it's not all /that/ far from being practical,
and if the crypto's not fundamentally broken, seems like it goes a long
way to filling in the biggest privacy hole in lightning today [3]...

Code is at https://github.com/ajtowns/snarkfront/ or more directly at:
https://github.com/ajtowns/snarkfront/blob/lightning-sha/test_lightning.cpp

Cheers,
aj

[0] https://tahoe-lafs.org/trac/tahoe-lafs/wiki/SNARKs

[1] https://github.com/jancarlsson/snarkfront

[2] This would also improve privacy/anonymity for other applications of
    HTLCs, such as atomic swaps across chains:

     1 bitcoin, payable on R1 + Alice's sig or timeout + Bob's sig
     100 litecoin, payable on R2 + Robert's sig or timeout + Ally's sig

    Alice and Bob communicate privately, agreeing to trade 1 BTC for 100
    litecoin and revealing their aliases Robert and Ally; Alice generates
    R1, R2, and reveals SHA(R1), SHA(R2), R1^R2 and the SNARK proof and
    publishes the litecoin payment. Bob verifies the proof, and publishes
    the bitcoin payment. Alice claims the bitcoin payment, revealing R1;
    Bob calculates R2 and claims the litecoin payment. The swap can take
    place trustlessly because Bob knows the only way Alice can claim his
    bitcoin is by revealing enough info so he can claim the corresponding
    litecoin. But there isn't any on-chain information linking the two
    transactions, because R1 and R2 are independent (and could even be
    using different hash functions as well as different preimages).
    After the funds have been claimed, the private communication is
    also completely deniable, since anyone could generate R1^R2 and a
    corresponding SNARK proof just using the info on the blockchain.
    
//------------------------------------------------------------------------//
https://github.com/ajtowns/snarkfront/blob/lightning-sha/test_lightning.cpp
    
#include <array>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

#include "snarkfront.hpp"

using namespace snarkfront;
using namespace cryptl;
using namespace std;

void printUsage(const char* exeName) {
    cout << "usage: " << exeName
         << " -m keygen|input|proof|verify"
         << " -s secret"
         << " -h hash-of-secret"
         << " -b hash-of-secret_xor_delta"
         << " -x delta"
         << endl;

    exit(EXIT_FAILURE);
}

#if (CHAR_BIT != 8)
#error "large chars confuses me (CHAR_BIT != 8)"
#endif

template<typename T>
typename T::DigType do_digest(
        T hashAlgo,
        std::size_t n,
        const vector<uint8_t> &data,
        vector<typename T::WordType> &blessdata)
{
    typename T::MsgType msg; // 512 bit block as array of 16 uint32_t's, except snarked
    typename T::WordType::ValueType msg_int; // uint32_t

    assert(n % sizeof(msg_int) == 0);
    assert(n < msg.size() * sizeof(msg_int)); // n+padding actually has to equal this
    assert(blessdata.size() == 0);

    stringstream ss;
    std::size_t i = 0;
    for (const auto& c : data) {
        ss.put(c);
        i++;
    }
    while (i++ < n) {
        ss.put('\0');
    }

    bool padded = false;
    for (auto &m : msg) {
        if (!bless(msg_int, ss)) {
            if (!padded && ss.eof()) {
                std::size_t lengthBits = n * CHAR_BIT;
                ss.clear();
                T::padMessage(ss, lengthBits);
                assert(lengthBits == msg.size() * sizeof(msg_int) * CHAR_BIT);
                assert(!ss.eof());
                padded = true;
            }
            if (!bless(msg_int, ss)) {
                assert(padded); // should be padded by now
                assert(false); // ran out of input -- padding didn't work
                msg_int = ~0;
            }
        }
        bless(m, msg_int);

        // ensure proof validates correct padding
        if (padded)
            assert_true(m == msg_int);
        else
            blessdata.push_back(m);
    }

    hashAlgo.msgInput(msg);
    hashAlgo.computeHash();
    return hashAlgo.digest();
}

typedef BN128_FR FR;
typedef BN128_PAIRING PAIRING;

template <typename HC, typename HS, std::size_t N>
struct Algo {
    // secret/witness
    vector<uint8_t> preImageFwd;    // digest() only works on vectors
    vector<uint8_t> preImageBck;

    // actual input data (hash and xor)
    typename HC::DigType pubHashFwd;
    typename HC::DigType pubHashBck;
    array<typename HC::WordType, N/sizeof(typename HC::WordType)> pubXor;

    // pub input for circuit (hash and xor)
    typename HS::DigType pubVarsFwd;
    typename HS::DigType pubVarsBck;
    array<typename HS::WordType, N/sizeof(typename HC::WordType)> pubVarsXor;

    GenericProgressBar progress;

    static bool asc2hash(const std::string hash, typename HC::DigType &chkHash)
    {
        vector<uint8_t> v;
        const size_t digbytes = sizeof(typename HC::DigType);
        if (!asciiHexToVector(hash, v) || v.size() != digbytes)
            return false;

        stringstream ss;
        for (const auto& c : v)
                ss.put(c);
        for (auto& i : chkHash)
                bless(i, ss);
        return true;
    }

    void _init_pubXor(const vector<uint8_t> &PreXor) {
        stringstream ss;
        std::size_t i = 0;
        for (const auto &c : PreXor) {
            ss.put(c);
            i++;
        }
        while (i++ < N)
            ss.put('\0');
        for (auto &w : pubXor) {
            bless(w, ss);
        }
    }

    Algo(const vector<uint8_t> &PreXor, const std::string secret)
      : progress(cerr, 50)
    {
        auto xi = PreXor.begin();
        uint8_t x;
        for (const auto& c : secret) {
            x = (xi == PreXor.end() ? 0 : *(xi++));
            preImageFwd.push_back(c);
            preImageBck.push_back(c ^ x);
        }
        assert(preImageFwd.size() <= N);
        while(preImageFwd.size() < N) {
            x = (xi == PreXor.end() ? 0 : *(xi++));
            preImageFwd.push_back('\0');
            preImageBck.push_back(x);
        }
        assert(xi == PreXor.end());
        assert(preImageFwd.size() == N);
        assert(preImageBck.size() == N);

        _init_pubXor(PreXor);
        pubHashFwd = digest(HC(), preImageFwd);
        pubHashBck = digest(HC(), preImageBck);
    }

    Algo(vector<uint8_t> &PreXor,
         typename HC::DigType &chkHashFwd,
         typename HC::DigType &chkHashBck)
      : progress(cerr, 50)
    {
        _init_pubXor(PreXor);
        pubHashFwd = chkHashFwd;
        pubHashBck = chkHashBck;
    }

    void _input_step() {
        bless(pubVarsXor, pubXor);
        bless(pubVarsFwd, pubHashFwd);
        bless(pubVarsBck, pubHashBck);
        end_input<PAIRING>();
    }
    void _calc_step() {
        vector<typename HS::WordType> blessFwd, blessBck;
        assert_true(pubVarsFwd == do_digest(HS(), N, preImageFwd, blessFwd));
        assert_true(pubVarsBck == do_digest(HS(), N, preImageBck, blessBck));

        assert(blessFwd.size() == blessBck.size());
        assert(blessFwd.size() == pubXor.size());
        for (std::size_t i = 0; i < blessFwd.size(); i++) {
            assert_true(blessFwd[i] == (blessBck[i] ^ pubVarsXor[i]));
        }
    }

    void do_keygen(void) {
        // trusted key generation

        _input_step();
        _calc_step();

        // generate proving/verification key pair
        cerr << "generate key pair";
        cout << keypair<PAIRING>(progress); // expensive!
        cerr << endl;
    }

    void do_input(void) {
        _input_step();
        // publicly known input variables
        cout << input<PAIRING>();
    }

    void do_proof(Keypair<PAIRING> &keypair) {
        // generate a proof

        // check for marshalling errors
        assert(!keypair.empty());

        _input_step();
        _calc_step();

        // generate proof
        cerr << "generate proof";
        cout << proof(keypair, progress);
        cerr << endl;
    }

    void do_verify(Keypair<PAIRING> &keypair, Proof<PAIRING> &proof) {
        _input_step();
        Input<PAIRING> inp = input<PAIRING>();

        // check for marshalling errors
        assert(!keypair.empty() && !proof.empty());

        // verify proof
        cerr << "verify proof ";
        const bool valid = verify(keypair, inp, proof, progress);
        cerr << endl;
        cout << "proof is " << (valid ? "verified" : "rejected") << endl;
    }
};

int main(int argc, char *argv[])
{
    const std::size_t hashbytes = 32;
    Getopt cmdLine(argc, argv, "mshbx", "", "");
    if (!cmdLine || cmdLine.empty()) printUsage(argv[0]);

    const auto mode = cmdLine.getString('m');
    const auto prefwd = cmdLine.getString('s');
    const auto hashfwd = cmdLine.getString('h');
    const auto hashbck = cmdLine.getString('b');
    const auto prexor = cmdLine.getString('x');

    typedef Algo<cryptl::SHA256,snarkfront::SHA256<FR>, hashbytes> SHA256Algo;

    cryptl::SHA256::DigType chkHashFwd, chkHashBck;
    vector<uint8_t> PreXor;
    SHA256Algo *algo;

    cerr << "m: " << mode << "." << endl;
    cerr << "f: " << hashfwd << "." << endl;
    cerr << "b: " << hashbck << "." << endl;
    cerr << "x: " << prexor << "." << endl;

    if (mode != "keygen") {
        if (prexor == "") {
            cerr << "Must supply xor" << endl;
            return 1;
        }
        if (prefwd == "" && (hashfwd == "" || hashbck == "")) {
            cerr << "Must supply hashes or preimage" << endl;
            return 1;
        }

        if (!asciiHexToVector(prexor, PreXor) || PreXor.size() == 0) {
            cerr << "Invalid xor string: " << prexor << "." << endl;
            return 1;
        }
        if (PreXor.size() > hashbytes) {
            cerr << "Xor string is too long (max " << hashbytes << "bytes)" << endl;
            return 1;
        }
        if (prefwd.size() > hashbytes) {
            cerr << "preimage is too long (max " << hashbytes << " bytes)" << endl;
            return 1;
        }

        if (hashfwd != "") {
            if (!SHA256Algo::asc2hash(hashfwd, chkHashFwd)) {
                cerr << "Invalid hash string: " << hashfwd << "." << endl;
                return 1;
            }
        }
        if (hashbck != "") {
            if (!SHA256Algo::asc2hash(hashbck, chkHashBck)) {
                cerr << "Invalid hash string: " << hashbck << "." << endl;
                return 1;
            }
        }
    }

    // Barreto-Naehrig 128 bits
    init_BN128();

    if (prefwd == "") {
        algo = new SHA256Algo(PreXor, chkHashFwd, chkHashBck);
    } else {
        algo = new SHA256Algo(PreXor, prefwd);
        cerr << "F: " << asciiHex(algo->preImageFwd) << endl;
        cerr << "B: " << asciiHex(algo->preImageBck) << endl;
        cerr << "#F: " << asciiHex(algo->pubHashFwd) << endl;
        cerr << "#B: " << asciiHex(algo->pubHashBck) << endl;
        if (hashfwd != "") {
            if (chkHashFwd != algo->pubHashFwd) {
                cerr << "Supplied forward hash does not match preimage hash" << endl;
                return 1;
            }
        }
        if (hashbck != "") {
            if (chkHashBck != algo->pubHashBck) {
                cerr << "Supplied backward hash does not match calculated preimage hash" << endl;
                return 1;
            }
        }
    }

    if ("keygen" == mode) {
        algo->do_keygen();
    } else if ("input" == mode) {
        algo->do_input();
    } else if ("proof" == mode) {
        Keypair<PAIRING> keypair; // proving/verification key pair
        cin >> keypair;
        algo->do_proof(keypair);
    } else if ("verify" == mode) {
        // verify a proof
        Keypair<PAIRING> keypair; // proving/verification key pair
        Proof<PAIRING> proof;     // zero knowledge proof

        cin >> keypair >> proof;

        algo->do_verify(keypair, proof);
    } else {
        // no mode specified
        printUsage(argv[0]);
    }

    return EXIT_SUCCESS;
}