4 ms·

To prevent that, the discussion started with an approach where you create your seed phrase with dices. Look at step 1: https://news.ycombinator.com/item?id=321

To prevent that, the discussion started with an approach where you create your seed phrase with dices. Look at step 1: https://news.ycombinator.com/item?id=32115693 https://news.ycombinator.com/item?id=32115693 The question was if it is at all possible to use Bitcoin in a trustless way. Several hard and maybe impossible to overcome challenges have come up in the thread. The fact that eliptic curve signatures are not deterministic seems to be the most fundamental.

matthewdgreen 4y ago
ECDSA signatures can be made deterministic by deriving the nonce deterministically, e.g., by hashing the secret key together with a challenge provided by the user. The problem now is that you need a way for the wallet to prove to the user that this has been done, without leaking the nonce or key. There are a bunch of ways to do this, but the most basic idea is to generate a zero-knowledge proof (probably a zkSNARK) that shows correctness of the signature w.r.t. the public key. The user would not put this zkSNARK onto the network -- it might contain a covert channel of its own! -- they would just check it locally and then dispose of that part. (Of course if the wallet was stolen by a malicious user the wallet might be able to exfiltrate the secret key to this thief through the zkSNARK portion.) I'm assuming that all other transaction information is chosen by the user, so there's no other latitude for the wallet to cheat.
- operator-name 4y ago
  RFC 6979 is followed by compliant bitcoin wallets. Statically proving an unknown and black box wallet requires a trusted computational (as would verifying any proof) device to perform the same calculated (after all the private key is loaded via dice). This computational could be a human, by hand. A zkSNARK wouldn't improve random exfiltration, so both of these proofs are statistical unless inputs are tested exhaustivally to result in the pigeonhole principle for some bounded internal state.
  - matthewdgreen 4y ago
    > RFC 6979 is followed by compliant bitcoin wallets. RFC 6979 uses HMAC, which would make the proofs pretty painful. You would probably want to swap this for some more efficient primitive. It wouldn't matter for compliance with the network. > Statically proving an unknown and black box wallet requires a trusted computational (as would verifying any proof) device Yes, but this trusted computing device does not need to be connected to any network. It can be an airgapped computer (or even several airgapped computers sourced from different vendors and retailers), each running different software. There is still "trust" here but the degree of trust can be arbitrarily reduced, provided that you're willing to spend money and effort. Verifying proofs using only human computation is pretty challenging. > A zkSNARK wouldn't improve random exfiltration, so both of these proofs are statistical unless inputs are tested exhaustivally to result in the pigeonhole principle for some bounded internal state. I'm not sure what you're saying. As I said up above in the thread, the zkSNARK is typically randomized and thus could be itself used as a covert channel, even if the signature is now (verifiably) deterministic. But that's ok: the model I'm working with assumes that the wallet owner is trustworthy, and that any local computers they use to verify the proof are properly (physically) airgapped. The zkSNARK would be verified by the user first -- using (multiple pieces) of airgapped, trusted hardware -- then discarded. Only the final signature would ever reach a computer connected to the Internet. If your concern is that the wallet owner and the network are both malicious,* then you're dead. (ETA: removed a note about deterministic ZK proofs, all that would let you do is detect that you're dead after the fact and only if you sent them to the network: it doesn't matter in this extreme threat model.) * By the time your attacker has stolen the Bitcoin wallet and can force it to make signatures, you're basically toast anyway. So this does not seem like a good threat model to waste time on.
operator-name 4y ago
How about something more fundimental. Consider bitcoin wallet M, that erases the private keys after n transactions? Either you trust your wallet does not do this, or you make copies and trust location/security/something else. Trustless is a misnomer and was originally applied in the context of 3rd parties, nor computational devices in your own control running code you can theoretically verify.

matthewdgreen 4y ago

ECDSA signatures can be made deterministic by deriving the nonce deterministically, e.g., by hashing the secret key together with a challenge provided by the user. The problem now is that you need a way for the wallet to prove to the user that this has been done, without leaking the nonce or key. There are a bunch of ways to do this, but the most basic idea is to generate a zero-knowledge proof (probably a zkSNARK) that shows correctness of the signature w.r.t. the public key. The user would not put this zkSNARK onto the network -- it might contain a covert channel of its own! -- they would just check it locally and then dispose of that part. (Of course if the wallet was stolen by a malicious user the wallet might be able to exfiltrate the secret key to this thief through the zkSNARK portion.) I'm assuming that all other transaction information is chosen by the user, so there's no other latitude for the wallet to cheat.

operator-name 4y ago
RFC 6979 is followed by compliant bitcoin wallets. Statically proving an unknown and black box wallet requires a trusted computational (as would verifying any proof) device to perform the same calculated (after all the private key is loaded via dice). This computational could be a human, by hand. A zkSNARK wouldn't improve random exfiltration, so both of these proofs are statistical unless inputs are tested exhaustivally to result in the pigeonhole principle for some bounded internal state.
- matthewdgreen 4y ago
  > RFC 6979 is followed by compliant bitcoin wallets. RFC 6979 uses HMAC, which would make the proofs pretty painful. You would probably want to swap this for some more efficient primitive. It wouldn't matter for compliance with the network. > Statically proving an unknown and black box wallet requires a trusted computational (as would verifying any proof) device Yes, but this trusted computing device does not need to be connected to any network. It can be an airgapped computer (or even several airgapped computers sourced from different vendors and retailers), each running different software. There is still "trust" here but the degree of trust can be arbitrarily reduced, provided that you're willing to spend money and effort. Verifying proofs using only human computation is pretty challenging. > A zkSNARK wouldn't improve random exfiltration, so both of these proofs are statistical unless inputs are tested exhaustivally to result in the pigeonhole principle for some bounded internal state. I'm not sure what you're saying. As I said up above in the thread, the zkSNARK is typically randomized and thus could be itself used as a covert channel, even if the signature is now (verifiably) deterministic. But that's ok: the model I'm working with assumes that the wallet owner is trustworthy, and that any local computers they use to verify the proof are properly (physically) airgapped. The zkSNARK would be verified by the user first -- using (multiple pieces) of airgapped, trusted hardware -- then discarded. Only the final signature would ever reach a computer connected to the Internet. If your concern is that the wallet owner and the network are both malicious,* then you're dead. (ETA: removed a note about deterministic ZK proofs, all that would let you do is detect that you're dead after the fact and only if you sent them to the network: it doesn't matter in this extreme threat model.) * By the time your attacker has stolen the Bitcoin wallet and can force it to make signatures, you're basically toast anyway. So this does not seem like a good threat model to waste time on.

operator-name 4y ago

How about something more fundimental. Consider bitcoin wallet M, that erases the private keys after n transactions? Either you trust your wallet does not do this, or you make copies and trust location/security/something else. Trustless is a misnomer and was originally applied in the context of 3rd parties, nor computational devices in your own control running code you can theoretically verify.