How much evaluation does that scheme have?

One immediate thought after a scan is item 6 in the Digest Algorithm section:

Doesn't this add a new dependency on signature verification where the verifier must load one transaction for every input to look up the value? If so, that changes signature validation from "contextless" to requiring a transaction (or UTXO) index, which seems like a major change. Maybe there's a way around it by requiring the prevout values to be serialized next to the transaction?

Anyway, I need to think about this a lot more (as well as an alternative proposal from @str4d, and potentially others) before I feel comfortable with it.

How much evaluation does that scheme have?

AFAICT (hard to tell quickly because the SIGHASH_FORKID proposal copied and then changed the Markdown formatting), the only difference between this proposal and BIP 143 is the ORing of a 24-bit fork ID into the sighash type. Thus it has the entirety of SegWit evaluation behind it.

One immediate thought after a scan is item 6 in the Digest Algorithm section:

Doesn't this add a new dependency on signature verification where the verifier must load one transaction for every input to look up the value? If so, that changes signature validation from "contextless" to requiring a transaction (or UTXO) index, which seems like a major change. Maybe there's a way around it by requiring the prevout values to be serialized next to the transaction?

This lookup has always been necessary; the sighash change just changes where it happens. Currently, the only way to verifiably check the value balance for a transaction is to load the input transactions, and validate them. This is fine for full nodes, but a lot of overhead for e.g. hardware wallets (see this TREZOR blogpost). With this change, the hardware wallet can just be given the values, and know that they are authentic (because they are part of the signature, rather than a hop away through the prevouts). The value still needs to be looked up, but this can be done when a block arrives, and then cached for later use.

I outlined my proposal in #174 (comment), which is the parent for (1) in OP title.

We changed the title to use "adapt" because we need to change these parts on top of SIGHASH_FORKID:

• pick a better name (see next comment).
• require new transactions to use this scheme. It will no longer be possible for version 3 txns to use "legacy" quadratic hashing.
• specify how JoinSplits are covered by signatures.
• change the hashing scheme to blake2 with first-class personalization.
• add guidance for future upgrades about how to use the personalization field, especially when considering competing alternatives.

Also, let's pick a better name from SIGHASH_FORKID, which is confusing in a few ways:

• The hashing scheme for signature generation/validation applies to all SIGHASH_* types, such as SIGHASH_ALL.
• We wish to avoid the word fork due to various ambiguities.

Are we sure we want to fix quadratic hashing, value signing in NU0?
If we would just want replay protection it would be much simpler probably.

The simplest thing seems to be just to change nversion to something unique for the fork.
I mean, is someone really attacking any network with huge transactions with a lot of signatures? And they would have to keep it up for a lot of blocks to get any DOS effect.
Let's keep it simple so we can focus on deploying Sapling.

I mean, is someone really attacking any network with huge transactions with a lot of signatures? And they would have to keep it up for a lot of blocks to get any DOS effect.

We already see this happening non-maliciously: there are various exchanges trying to merge many UTXOs into more usable amounts. The first time this happened, individual blocks were taking between six and ten seconds to validate (see #2333), which broke many of the mining pools, and is why we implemented #2342 as a short-term fix. There are various other optimisations we need to pull in from upstream (#2333 (comment)), but it isn't going to be possible to noticeably decrease the size of the UTXO set for these exchanges without fixing the quadratic hashing problem.

Right, my mistake, I thought you need to create an artificial script with a lot of checksigs to run into this.
There's still the question, do we want to do replay protection with this signature type SIGHASH_FORKID, or just change the nversion for the fork?
And I'm curious with the short-term fix what num of inputs are miners allowing?
And is that interfering with mining pools' ability to make large transactions?

Here's my first attempt at adapting the linear hashing code from bitcoin https://github.com/arielgabizon/zcash/tree/fix-quadratic-hashing

Here's my second attempt, using cherry-pick instead of copy-paste as @str4d requested https://github.com/arielgabizon/zcash/tree/integrate-quadhash-fix
I have detailed notes about the process, with all the things I didn't cherry-pick on the way, that we may want to integrate.

The function signatureHash will be changed when we decide on our hardfork mechanism.

I think we should use BLAKE2b-256 rather than BLAKE2s. Section 3.3 of the BLAKE2 paper says that "a typical implementation of [BLAKE2s] in embedded software stores in RAM at least [168 bytes]. BLAKE2b only requires 336 bytes of RAM [...]".

The difference between 168 and 336 bytes is not material even for embedded implementations. For a hardware wallet you'll also want to be doing EdDSA signing, which also likely requires at least 336 bytes (and you don't need to do signing and hashing at the same time). For reference, Trezor uses a Cortex M3 with 128 KiB of RAM.

Therefore, we should choose the (significantly) faster BLAKE2b-256, to reduce the cost of hashing large transactions/blocks.

The Ledger Nano S uses an ST31H320 with 10 KiB of RAM. This is still sufficient that the difference in RAM usage between BLAKE2s and BLAKE2b is unlikely to be an obstacle.

Note that EdDSA requires a hash with 512-bit output for which we are going to use BLAKE2b (see #2853), and so an implementation of that will be required in any case for doing shielded spend authorisation signatures.

Let's call it "Replay-Protected Scalable Lightweight-wallet-friendly hashing" or "RPSL hashing".

"Overwinter signature hashing" will do fine.

Closed by #2903.