New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Invalidating existing SHA3 hardware with a goofy PoW #71

Open
chjj opened this Issue Oct 25, 2018 · 4 comments

Comments

Projects
None yet
3 participants
@chjj
Copy link
Contributor

chjj commented Oct 25, 2018

So, we're going to be dropping Cuckoo Cycle in favor of a simple hashcash PoW. SHA3 is the obvious choice, but it's likely that vanilla SHA3 ASICs already exist somewhere. In order to create a level playing field for hardware manufacturers right out of the gate, we need to do some funky stuff.

Both SHA3 and BLAKE2b are customizable. BLAKE2b is probably "more" customizable in the sense that adding a key alters the hash state in such a way that it can't be replicated by concatenating data with a preimage. Keccak's cSHAKE is a different story. Someone with an existing SHA3 ASIC just needs to prepend a few bytes and change the final padding -- the latter part may be possible to do with a chip's microcontrollers.

Here's a very simple idea which should break any existing ASIC:

X = BLAKE2b256(H, K="HNS")
Y = cSHAKE256(H, N="HNS", S="")
Z = SHA3(X || Y)

Where Z is the final PoW hash.

We could also XOR X and Y with the previous block hash or something like that. Whatever we do, it should probably be changed slightly before mainnet. Maybe move the nonce itself into the key and personalization string:

H = header without nonce
P = previous blockhash
X = BLAKE2b256(H, K=nonce)
Y = cSHAKE256(H, N="HNS", S=nonce)
X = X xor P
Y = Y xor P
Z = SHA3(X || Y)

Ideas are welcome. Anything sufficiently convoluted enough to break existing ASICs is useful.

@DavidVorick

This comment has been minimized.

Copy link

DavidVorick commented Oct 30, 2018

I think it would be helpful to clearly specify a list of things that you do want, and a list of things that you don't want, and the reasons why as well.

One big thing should be that you want hardware to be definitely specific to Handshake. sha3 seems like a natural choice for a lot of projects (which is why it's highly likely that sha3 cryptocurrency ASICs already exist), and therefore you want to change to something that's not an obvious natural choice. This goofy pow is a good example of that - except for projects that are explicitly saying "I want to use the same PoW as handshake", I don't think anyone would use your goofy pow as their hashcash algorithm.

One thing you want to avoid is re-usable circuits. We ran into this issue with Sia's blake2b algorithm. The blake2b circuits were close enough to blake2s circuits that some ASICs were released that could target either one or the other. Which mean you could point a chip at one network or at the other network. This does come with both a performance and an area (cost) penalty, but the penalty was not great enough to stop people from making these dual purpose chips. Dual purpose chips undermine security in the same way that GPU-only can undermine security.

Something that it appears Decred has run into is circuit compatibility between sha256 and blake2s. They are both 32bit, and some of the timing profiles are the same between them. The highly optimized circuits of the whatsminer M10 seem to have been able to be migrated to blake2s, resulting an an unbelievably good blake2s miner. I find it unlikely that whatsminer would have released something that was 4x ahead of any competition if they hadn't been able to translate a lot of their impressive sha256 optimizations over.

I do believe that your goofy pow will be enough to break any existing ASIC vs. a fully custom asic pointed at your goofy pow, but manufacturers with existing blake2b circuits will have an advantage vs. someone starting from scratch. Between Sia and equihash, quite a few people will have blake2b circuits. And anyone with an eth asic probably has a sha3 circuit as well. Those aren't going to be so heavily optimized because those coins are less mature, so I don't think it's a big deal, but I wanted to point that out anyway.


From your perspective, what is the ideal launch in terms of ASIC availability and competition? I think that it's very likely you end up with a monopoly either way, because there's only enough room for 1 player at the most advanced tape-out (7nm) until the annual block reward is multiple hundreds of millions of dollars.

@chjj

This comment has been minimized.

Copy link
Contributor Author

chjj commented Dec 3, 2018

Thanks for the reply. I'm not a hardware expert, so this is really useful input.

I think it would be helpful to clearly specify a list of things that you do want, and a list of things that you don't want, and the reasons why as well.

Yeah, I jumped the gun with the initial post. I should explain the reasoning and timeline more clearly...

To start, I think mining hardware empires are probably unavoidable no matter which PoW is selected. I've made my peace with that fact. This is partly why I don't see Cuckoo Cycle as a very worthwhile option anymore. Cuckoo Cycle is also very fancy, and in my experience, fancy things tend to break easily.

That said, even though hardware empires do tend to take over, that doesn't mean we shouldn't try to offer manufacturers equal footing for competition initially. Choosing an algorithm without first considering this is unethical in my opinion, since you'd essentially be giving the game away to one vendor right from the jump.

Once I was convinced to drop Cuckoo Cycle, the focus shifted to Hashcash with SHA3.

Then another complication: I've heard whispers of SHA3 ASICs currently in the woodwork. On top of that, like you mentioned, Ethash vendors have some SHA3 hardware. So now we're back to the drawing board: How to use SHA3 (or another existing algorithm) in such a way that it offers a level playing field initially?

In short, I see hashcash as better for the long-term and Cuckoo Cycle better for the short-term. The "early monopoly" situation you mention at the end of your post seems to be in line with this. It's probably likely there's an early monopoly going the hashcash route, but I think it makes for a more robust network in the long run.

Anyway, point taken about reusable circuits. That's definitely something to consider.

Also a very good point about different vendors having existing BLAKE2/SHA3 chips. Either one of them does have an advantage. I think maybe that's fine. I don't think Handshake should be in the business of creating new PoW algorithms, and I don't think we should be looking to create a new Ethash. I was just hoping to do some kind of SHA3 PoW with minor modifications to mitigate the issue rather than avoiding it completely.

From your perspective, what is the ideal launch in terms of ASIC availability and competition?

I'm not aiming for ideal. We don't live in an ideal world, and I can't emphasize enough how much I don't want to fall down the rabbit hole of creating a new PoW algorithm to invalidate specialized hardware forever.

Scheduled PoW hardforks are also out of the question. I personally see them as a symptom of developer centralization. As an HNS contributor, I assume that pretty much everything is out of my hands post-mainnet. I think that's the way it should be in a decentralized system, and I think most of us are pretty averse to some kind of guaranteed hardfork schedule.

I see so many coins trying to utilize both of the above strategies to combat monopolies and they're almost always fighting a losing battle. I'd rather just let the hardware market operate the way they do than try to stay one step ahead of them all the time.

Maybe just a very minor change to an existing algorithm to make things sane in the beginning is appropriate. It doesn't need to be the perfect solution, just something that's decent. Whatever comes after is a consequence of the free market.

Anyway, I think we'll do another testnet soon now that the airdrop proofs have been implemented. If we're going to do hashcash, I'd like to get something in now, but it can still be up in the air for mainnet. We should definitely leave this open for more discussion.

As an aside to anyone reading: I think retargetting is up for debate too. The bitcoin cash retargetting algorithm seems to be holding up in production. Might be worth looking at as a possibility.

@chjj

This comment has been minimized.

Copy link
Contributor Author

chjj commented Jan 3, 2019

On the next branch this is what we've currently got now:

H = header without nonce
N = nonce
K = KMAC256(H, key=N, pers="")
D = BLAKE2b256(H, key=K)
verify D <= T

Pretty simple and the same amount of data hashed for both functions. I'm considering using KMAC with an output size of 512 bits since it matches blake2's internal state length and would become a truer initialization vector so to speak. Not sure if that has any benefits. Feels more secure in some way though. I suppose there's also no reason not to include the nonce in the message despite it being the key for both functions. I feel like that would hold up better in the case that SHA3 is somehow broken in the future.

@prestwich

This comment has been minimized.

Copy link

prestwich commented Jan 28, 2019

Hey, I was talking with @tynes this morning, and he recommended I chime in here.

One desirable property is efficient PoW verification on another blockchain. It enables much better cross-chain communication. For example, we can verify bitcoin's double-sha2 in Solidity easily. Instead of setting up an atomic swap or L2 construction, you can use a simple escrow contract that checks proof of work via SPV proof. Unfortunately, the EVM has a fairly limited toolbox to work with (keccak256, sha2, ripemd160, modular arithmetic, pairing ops, and ecrecover)

Possible usecases here would be transfer of Ether conditional on transfer of a name or the outcome of a covenant auction, and fast simple p2p handshake/ETH trading.

We run this in mainnet between Ether and Bitcoin using the toolbox here

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment