Add support for Keccak-256

MicahZoltu commented 5 years ago

I'm submitting a ... [ ] bug report [x] feature request [ ] question about the decisions made in the repository [ ] question about how to use this project
Summary Ethereum uses Secp256k1 for its ECC and Keccak256 (original submission, not final NIST SHA-3) for its hashing. While I know this is a bitcoin library, it would be great if it could be used in Ethereum as well by getting support for Keccak256 added.
Other information (e.g. detailed explanation, stacktraces, related issues, suggestions how to fix, links for us to have context, eg. StackOverflow, personal fork, etc.)

Q&A on Ethereum's hashing algorithm: https://ethereum.stackexchange.com/a/554/704

bitjson commented 5 years ago

Hey @MicahZoltu – thanks for opening an issue! I would definitely like to add support for Keccak-256: this might be a good thing for @ARitz-Cracker to chime in on (he made a related PR: https://github.com/bitauth/bitcoin-ts/pull/13, and has done a lot more work on related libraries).

@ARitz-Cracker: did you get WASM signing for Ethereum working?

ARitz-Cracker commented 5 years ago

Hello, @bitjson. Nice to hear from you! Yes I did get it working in the development branch of https://github.com/ARitz-Cracker/arc-web3. Combined with https://github.com/ARitz-Cracker/arc-web3-signable-accounts I also have https://github.com/ARitz-Cracker/arc-web3-keyring working so you can re-create metamask's mnemonic seed thing. The version currently uploaded to npm and GitHub does still use a JS implementation of keccak256, but I've created a WASM version here: https://github.com/ARitz-Cracker/keccak-wasm with the plans to link up my web3 libraries to it (And add better documentation with TS definitions). Unfortunately, I had to pause development on my ethereum stuffs cuz of... you know... life.

@MicahZoltu If you're looking for a web3 library that isn't ~~total garbage~~ ~~spaghetti hell~~ ~~bloated af~~ difficult to maintain, and uses wasm, then feel free to take a look what I've got so far.

I do fully intend to resume working on my wasm web3 stuffs when I can, but realistically speaking right now that's in the weeks-to-months range.

ARitz-Cracker commented 5 years ago

P.S. I still half-disagree with your approach to a mono-repo, @bitjson, but I respect you and your work too much to make a big fuss about it :^)

MicahZoltu commented 5 years ago

If a Rust keccak256 library is preferred then https://github.com/debris/tiny-keccak/blob/master/src/keccak.rs may work (CC0 license). If I'm following the chain correctly (my Rust knowledge is near 0) then that is the library that Parity (popular Ethereum client written in Rust) uses.

MicahZoltu commented 5 years ago

Would a PR that added keccak256 to the hashes folder (copied verbatim from tiny-keccak above) and then updated the Dockerfile by copy-pasting this block be welcome? I can probably hack together a PR that does that much, but I don't really know Rust or WASM so much work beyond that is probably out of my ability level.

Looks like I would also need to copy this file and update it for Keccak256, along with the accompanied spec and bench files. Presumably I would also have to update crypto.ts in that folder to export it....

I guess really the question is, are PRs welcome for this sort of thing, particularly from someone who is just going to be copy/pasting stuff around without really understanding how any of it works?

ARitz-Cracker commented 5 years ago

@MicahZoltu I've already linked you to a working wasm version of keccak256 along with a (mostly) feature complete web3 library. Is there anything else you need?

MicahZoltu commented 5 years ago

@ARitz-Cracker I'm trying to find an all-in-one library that provides secp256k1 + keccak256 + sha256 + sha512 + ripemd160, since Ethereum uses each in one way or another. Ideally it would also include pbkdf2, though that one is part of web Crypto so it isn't a big deal if it is missing. Also, I don't want a full web3 library. I want just the crypto primitives.

Essentially, the design goals of this project align closely with what I'm looking for, while most other projects in the space don't align. Either they are kitchen sink libraries (include too much) or million-modules (don't include enough).

Specifically for keccak-wasm, it also includes a transitive dependency which, while not insurmountable, adds complications to build processes. bitcoin-ts on the other hand has 0 transitive dependencies.

Side note, both of these projects don't have deterministic builds, which I think is a critical missing feature. bitcoin-ts does use docker, which goes a long way toward reproducible builds, but it uses a base image with tag latest rather than a sha tag. This means that if someone can compromise the deployment of that base image then this library would be compromised. keccak-wasm on the other hand appears to use tooling on the build server, which allows the build server to compromise the build (and there is no easy way to verify that the build server compromised the build).

With the docker build process, it is closer to a deterministic build, as all that needs to be changed is to switch from latest to a sha. I may press for that if keccak gets added.

bitjson commented 5 years ago

Hey guys –

@ARitz-Cracker thanks for the detailed info, glad to hear you got it working!

but I've created a WASM version here: https://github.com/ARitz-Cracker/keccak-wasm

This looks awesome! Nice work. Test coverage looks fantastic too.

I still half-disagree with your approach to a mono-repo

It has it’s downsides 😄(past discussion, for the curious).

In the context of this library, I’m most concerned about package management security, and having a single codebase makes vendoring just a little easier. That being said, it can be annoying to pull in 5MB of javascript (both commonjs and module builds) for a small Node.js utility. 😆 (I’m hoping better package managers and project bundlers will make that less-bad in the next few years.)

@MicahZoltu:

I guess really the question is, are PRs welcome for this sort of thing, particularly from someone who is just going to be copy/pasting stuff around without really understanding how any of it works?

Yes please! I’d love to include both Keccak and PBKDF2 (particularly for BIP-0039 support). And don’t worry about lack of familiarity with Rust – this is the only project where I’ve really used Rust myself 😅.

You can probably get it working with copy/paste and some fiddling – the hard/tedious part is actually just making sure the end-result is well-tested with proper test vectors. (You’ll be able to copy/paste most of your way there too.)

(Of the two, I'd recommend working on PBKDF2, since ARitz-Cracker/keccak-wasm already seems to be a great option for Keccak.)

Side note, both of these projects don't have deterministic builds

Ouch, the Secp256k1 build is deterministic, but you’re right about the Rust builds. Not sure how I missed locking down the sha256 in that Dockerfile, thanks for bringing it up.

Fortunately, my backups show which image is responsible for the current build: liuchong/rustup@sha256:57795147db06a7ebad574469fb1198cf36fc26dc74d504d128ae2160271b2b61. Fixed in https://github.com/bitauth/bitcoin-ts/commit/98b2a134c3f283521d4b1b999dfd8f8cba8f8663, thanks!

MicahZoltu commented 5 years ago

PBKDF2 is already part of Web Crypto, so I'm not really interested in a WASM version of that (I prefer browser native constructs to third party constructs when available). In fact, I already have a BIP39 implementation that uses that and is quite simple:

const password = new TextEncoder().encode(words.join(' '))
const salt = new TextEncoder().encode('mnemonic' + passphrase)
const baseKey = await crypto.subtle.importKey('raw', password, 'PBKDF2', false, ['deriveBits'])
const derivedKey = await crypto.subtle.deriveBits({ name: 'PBKDF2', hash: 'SHA-512', salt: salt, iterations: 2048 }, baseKey, 512)

I'll see if I can take a stab at creating a Keccak256 PR at some point in the near future.

MicahZoltu commented 5 years ago

I cloned the repo and yarn && yarn test works, but when I do docker image build --file wasm/docker/hashes.Dockerfile I get the following error:

Step 3/49 : RUN cargo +nightly install wasm-bindgen-cli
 ---> Running in 7c570d4169d5
    Updating registry `https://github.com/rust-lang/crates.io-index`
 Downloading wasm-bindgen-cli v0.2.50
error: failed to parse manifest at `/root/.cargo/registry/src/github.com-1ecc6299db9ec823/wasm-bindgen-cli-0.2.50/Cargo.toml`

Caused by:
  editions are unstable

Caused by:
  feature `edition` is required

consider adding `cargo-features = ["edition"]` to the manifest
The command '/bin/sh -c cargo +nightly install wasm-bindgen-cli' returned a non-zero code: 101

MicahZoltu commented 5 years ago

It is worth noting, for the same reason as using a digest for the base image is recommended, dependencies should probably also be vendored rather than fetched from a remote resource so the build can be deterministic. This includes (at a glance at this Dockerfile): wasm-bindgen-cli, wasm-pack, git, cmake, python, binaryen.

For the apt repositories, I believe it is possible to fetch a tarball of the dependency and then just apt-get install that directly, rather than fetching the tarball at execution time. You can commit the tarball to the reposo it is available at build time and the same for everyone who clones that git commit.

For the rust dependencies, I'm not sure how to vendor those, but I would imagine there is some way?

bitjson commented 5 years ago

This isn't necessarily related to the issue, but for building, try yarn compile:hashes or yarn compile:debug:hashes.

On determinism – you're definitely right. In fact, the Secp256k1 build isn't necessarily deterministic either, but it appears that even when the dependencies autoconf libtool build-essential are changed, the resulting binary is currently the same.

To get full determinism, I think the best strategy is maybe to have two Dockerfiles for each build, one to create the build environment, and one to run the compilation (and we can use --rm when running the second). For the first, we want to pin as many versions as possible (so it's a bit easier to verify), then I'll publish the "build image" to docker hub, and we'll also pin that sha256 in this repo.

It might be a few months before I'll be able to implement something like this, but if you'd be willing to take a swing at getting the determinism right, I'd love to take a PR!

(FYI: I just opened a related issue as I was responding to this.)

MicahZoltu commented 5 years ago

Finally got around to trying your suggestion. Unsurprisingly, running compile:hashes resulted in the same error (since all it does is execute the docker command I was executing manually).

yarn compile:debug:hashes doesn't work until after you run compile:hashes. It feels like the name is wrong, it should just be debug:hashes and debug:secp256k1 since neither of those actually compile anything.

hazae41 commented 1 year ago

bitauth / libauth

Add support for Keccak-256 #32