Implementing the rangeproof part is challenging. Here are some notes about the use of rangeproofs in grin-wallet. It can contain faults or inconsistencies and it is certainly incomplete.
Related work
There is some previous work done on rangeproofs in Monero
There is a publication on a Monero Trezor implementation
See:
- https://eprint.iacr.org/2020/281.pdf
- GitHub - ph4r05/monero-tx-paper: Repository related to the paper "Privacy-friendly Monero transaction signing on a hardware wallet"
Monero has switched to BP++.
There is also the Beam HW wallet implementation.
I haven’t studied these implementation in depth yet.
If someone knows related work regarding implementations of Bulletproofs on Ledger/Trezor, let me know.
In the following, I will give some comments on the rangeproof code, as it is used in Grin.
Rangeproof
-
Rangeproof signing is calculated by the HW. Note that Rangeproof validation will happen by the host.
-
“A rangeproof is therefore attached to every output and proves that its value isn’t negative and that its size is restricted so it doesn’t overflow”. Mimblewimble - Grin Documentation Rangeproof creating is done in the receiver action.
-
The Rangeproof field in the struct Output is here defined: grin/transaction.rs at f51b6e13761ac4c3c8e57904618ef431c14c6227 · mimblewimble/grin · GitHub
-
(Here the proof is verified. pub fn verify_proof(&self) → Result<(), Error>: grin/transaction.rs at f51b6e13761ac4c3c8e57904618ef431c14c6227 · mimblewimble/grin · GitHub )
-
The build::output() method fn output<K, B>(value: u64, key_id: Identifier) is defined here. It calls the proof::create function. grin/build.rs at 1b8acee72e7a4236cdf8561a7af5f894bfe11985 · mimblewimble/grin · GitHub
-
This creates the rangeproof/bulletproof itself: grin/proof.rs at 1b8acee72e7a4236cdf8561a7af5f894bfe11985 · mimblewimble/grin · GitHub
-
An output with a given rangeproof (created in the previous method) is created here: grin/transaction.rs at f51b6e13761ac4c3c8e57904618ef431c14c6227 · mimblewimble/grin · GitHub This method is used in the output function above: tx.with_output(Output::new(OutputFeatures::Plain, commit, proof)),
-
The previous is then used in the receive action., using tx::add_output_to_slate() (grin-wallet/tx.rs at 8547f4a162b466a1dacef63df2282b34c3964e78 · mimblewimble/grin-wallet · GitHub), which then calls build::output grin/build.rs at f51b6e13761ac4c3c8e57904618ef431c14c6227 · mimblewimble/grin · GitHub
Other interesting parts in the Wallet layer:
- test_rewind_range_proof(): grin-wallet/libwallet.rs at bdc5bd748a4e399e6febc5e3c4974e569ee39638 · mimblewimble/grin-wallet · GitHub
Now for the bulletproof algorithm itself:
-
It derives a secret key, using the secp256k1 curve. (grin/proof.rs at 1b8acee72e7a4236cdf8561a7af5f894bfe11985 · mimblewimble/grin · GitHub) This should happen on the HW.
-
Private nonce is created using this method: grin/proof.rs at 1b8acee72e7a4236cdf8561a7af5f894bfe11985 · mimblewimble/grin · GitHub Likely this must happen on the HW (I’m not sure).
-
It then call the secp.bullet_proof(), using the FFI and the secp256k1 library. GitHub - mimblewimble/rust-secp256k1-zkp: ZKP fork for rust-secp256k1, adds wrappers for range proofs, pedersen commitments, etc
-
pub fn range_proof() rust-secp256k1-zkp/pedersen.rs at 4128f64505143859c48fab04158c25127a2a9858 · mimblewimble/rust-secp256k1-zkp · GitHub
-
ffi::secp256k1_rangeproof_sign() called: rust-secp256k1-zkp/pedersen.rs at 4128f64505143859c48fab04158c25127a2a9858 · mimblewimble/rust-secp256k1-zkp · GitHub
-
int secp256k1_rangeproof_sign() (secp256k1-zkp/main_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub) acts mainly as a checker for the arguments, to call secp256k1_rangeproof_prove(). blind is here the secret key. The normal case, with tau_x, t_one, t_two and commits equal to NULL, seems to be the simplest case.
-
secp256k1_rangeproof_prove() is here: secp256k1-zkp/main_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub
-
Beginning, lots of checks that the arguments are correct
-
Commitment is calculated from Blindingfactor, must happen on the device I think.
-
Main functions called seem to be these two:
- secp256k1_pedersen_commitment_load: secp256k1-zkp/main_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub But this is in the multi party case.
- secp256k1_bulletproof_rangeproof_prove_impl call: secp256k1-zkp/main_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub
-
Parameters: blind: 32-byte blinding factor used by commit. nonce: 32-byte secret nonce used to initialize the proof (value can be reverse-engineered out of the proof if this secret is known.)
-
This is part of the BP normal case. Code in this block should be done on the HW, as it uses the blinding factor. secp256k1-zkp/main_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub This requires EC multiplication, for which I’ve seen example code, not using secp256k1, but the Ledger SDK.
-
secp256k1_bulletproof_rangeproof_prove_impl implementation: secp256k1-zkp/rangeproof_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub
-
This secp256k1_lr_generator_init methods needs to be done on the HW, as it uses the secret nonce: secp256k1-zkp/rangeproof_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub
-
I don’t understand the usage of gen and blinding gen at the moment
-
This needs to be done on the HW, uses blind: secp256k1-zkp/rangeproof_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub
-
This method (inner product proof secp256k1_bulletproof_inner_product_prove_impl) doesn’t use nonce or blind, so it doesn’t need in principle the HW?: secp256k1-zkp/rangeproof_impl.h at 8d1f5bb152580446a3438cd705caebacc2a5d850 · mimblewimble/secp256k1-zkp · GitHub
-
This note is certainly incomplete, especially the analysis of the Bulletproof algorithm itself.
The question I have is how to offload the part which uses the secret nonce and blinding factor to the HW. Perhaps studying related work will help here. If there are suggestions, they are very welcome.