LNPBP: 0002
Vertical: Bitcoin protocol
Title: Deterministic embedding of cryptographic commitments into bitcoin
transaction output
Authors: Dr Maxim Orlovsky <orlovsky@protonmail.ch>,
Giacomo Zucco,
Martino Salvetti,
Federico Tenga,
Sosthène
Comments-URI: https://github.com/LNP-BP/lnpbps/issues/4
Status: Proposal
Type: Standards Track
Created: 2019-10-27
License: CC0-1.0
- Abstract
- Background
- Motivation
- Design
- Specification
- Compatibility
- Rationale
- Continuing support for P2PK outputs
- Support OP_RETURN type of outputs
- Unification with OP_RETURN-based commitments
- Custom serialization of public keys in OP_RETURN
- Support for pre-SegWit outputs
- Committing to the sum of all public keys present in the script
- Deterministic public key extraction for a Bitcoin script
- Use of Taproot intermediate public key
- Reference implementation
- Acknowledgements
- References
- License
- Appendix A. Test vectors
The standard defines an algorithm for deterministic embedding and verification
of cryptographic commitments based on elliptic-curve public key tweaking
procedure defined in LNPBP-1 standard
inside scriptPubkey
script for existing types of Bitcoin transaction output.
Cryptographic commitments embedded into bitcoin transactions is a widely-used practice. Its application include timestamping [1], single-use seals [2], pay-to-contract settlement schemes [3], sidechains [4], blockchain anchoring [5], Taproot, Graftroot proposals [6, 7, 8], Scriptless scripts [9] and many others.
A number of cryptographic commitment (CC) use cases require the commitment to be
present within non-P2(W)PK(H) outputs,which may contain multiple public keys and
need a clear definition of how the public key that contain the commitment can be
found within the bitcoin script itself. For instance, embedding CC into
Lightning Network (LN) payment channel state updates in the current version
requires the modification of an offered HTLC and received HTLC transaction
outputs[10], and these transactions contain only a single P2WSH output. With the
use of option_anchor_outputs
[11] all outputs in the LN commitment transaction
becomes P2WSH outputs, also leading to a requirement for a standard and secure
way of making CC inside P2(W)SH outputs.
At the same time, P2(W)SH and other non-standard outputs (like explicit bare script outputs, including OP_RETURN type) are not trivial to use for CC, since CC requires deterministic definition of the actual commitment case. Normally, one of the most secure and standard CC scheme uses homomorphic properties of the public keys [12]; however multiple public keys may be used within non-P2(W)PK(H) output. Generally, these outputs present a hash of the actual script, hiding the used public keys or their hashes. Moreover, it raises the question of how the public key within Bitcoin Script may be defined/detected, since it is possible to represent the public key in a number of different ways within bitcoin script itself (explicitly or by a hash, and it's not trivial to understand where some hash stands for a public key or other type of preimage data). All this raises a requirement to define a standard way and some best practices for CC in non-P2(W) PK(H) outputs. This proposal tries to address the issue by proposing a common standard on the use of public-key based CC [12] within all possible transaction output types.
The protocol requires that exactly one public key of all keys present or
referenced in scriptPubkey
and redeemScript
must contain the commitment
(made with LNPBP-1 procedure) to a given message. This commitment is
deterministically singular, i.e. it can be proven that there is no other
alternative message that the given transaction output commits to under this
protocol. The singularity is achieved by committing to the sum of all original
(i.e. before the message commitment procedure) public keys controlling the
spending of a given transaction output. Thus, the given protocol covers all
possible options for scriptPubkey
transaction output types.
The commitment consists of the updated scriptPubkey
value, which may be embed
into the transaction output, and an extra-transaction proof (ETP), required
for the verification of the commitment. The structure and information in the
proof depends on the actual scriptPubkey
type.
The protocol includes an algorithm for deterministic extraction of public keys from a given Bitcoin script, based on Miniscript [16].
The committing party, having a message msg
, must:
- Collect all public keys instances (named original public key set)
related to the given transaction output, defined as:
- a single public key for P2PK, P2PKH, P2WPK, P2WPK/WSH-in-P2SH type of outputs;
- If
OP_RETURN
scriptPubkey
is used, it must contain a single public key serialized in BIP-340 xcoordonly form right afterOP_RETURN
opcode; for all other forms ofOP_RETURN
data algorithm must fail; - an internal public key for a Taproot output (P2TR);
- all public keys from a
redeemScript
(for P2(W)SH and P2WSH-in-P2SH, which in case of SegWit is contained withinwitnessScript
) orscriptPubkey
(for custom bare script outputs), extracted according to the algorithm. - In case of witness version > 1 the procedure must fail.
Let's call this set of n keys
P
.
- Select a single public key
Po
from the set of the original public keys, which will contain the commitment. It is advised that the corresponding private key being controlled by the committing party, which will simplify future spending of the output. - Run LNPBP-1 commitment procedure
on message
msg
, the set of original public keysP
, the selected public keyPo
and a protocol-specifictag
, provided by the upstream protocol using this standard. The procedure returns a tweaked public keyT
. - Construct necessary scripts and generate
scriptPubkey
of the required type. If OP_RETURNscriptPubkey
format is used, it MUST be serialized according to the following rules:- only a single
OP_RETURN
code MUST be present in thescriptPubkey
and it MUST be the first byte of it; - it must be followed by 32-byte push of the public key value
P
from the step 2 of the algorithm, serialized according to the rules from [15]; - if the tweaked public key serialized with bitcoin consensus serialization rules does not start with 0x02 as it's first (least significant) byte, the procedure must fail; or it may be repeated with a new public key picked at step 1.
- only a single
- Construct and store an extra-transaction proof (ETP), which structure
depends on the generated
scriptPubkey
type: a) value ofPo
, corresponding to:- the original intermediary public key for V1 witness Taproot output;
- single original public key used in the tweak procedure before the tweak was applied; b) deterministic script reconstruction data, i.e.:
- untweaked
redeemScript
(for P2SH outputs), orwitnessScript
(for P2WSH SegWit v0 native or P2WSH-in-P2SH SegWit legacy outputs), constructed using set of the original public keys; - the "taptweak" hash (i.e. the tagged hash of the Merkle root of the TapScript branches) for v1 witness output (Taproot);
- for other types of outputs no other data are required for the ETP.
The reveal protocol is usually run between the committing and verifying parties; however it may be used by the committing party to make the proofs of the commitment public. These proofs include:
scriptPubkey
from the transaction output containing the commitment;- original message
msg
to which the committing party has committed; - extra-transaction proof (ETP), constructed at the 5th step of the commitment protocol;
- (optional) proofs that the
scriptPubkey
is a part of a transaction included into the bitcoin chain containing the largest known amount of work at depth satisfying a verifying party security policy (these proofs may be reconstructed/verified by the verifying party itself using its trusted Bitcoin Core server);
The verification process runs by repeating steps of the commitment protocol using the information provided during the reveal phase and verifying the results for their internal consistency; specifically:
- Original public key set reconstruction:
- if extra-transaction proof (ETP) provides script data (pt. 5.b from the commitment procedure) parse it according to deterministic key collection algorithm and collect all the original public keys from it; fail the verification procedure if parsing fails;
- otherwise use an original public key provided as a part of ETP as a single- element set
- Run LNPBP-1 verification procedure repeating step 3 from the commitment procedure, using original public key value from the extra-transaction proof
- Construct
scriptPubkey'
, matching the type of thescriptPubkey
in the transaction and matching extra-transaction proof data using the tweaked version of the public key in the same way as was perfomed at step 4 of the commitment procedure. If there can be multiple matchingscriptPubkey
types for a given data, construct a variant for each of them. - Make sure that one of the
scriptPubkey'
values generated at the previous step, matches byte by byte thescriptPubkey
provided during the reveal phase; otherwise fail the verification.
- The provided script MUST be parsed with Miniscript [16] parser; if the parser fails the procedure MUST fail.
- Iterate over all branches of the abstract syntax tree generated by the
Miniscript parser, running the following algorithm for each node:
- if a public key hash is met (
pk_h
Miniscript command) and it can't be resolved against known public keys or other public keys extracted from the script, fail the procedure; - if a public key is found (
pk
) add it to the list of the collected public keys; - for all other types of Miniscript commands iterate over their branches.
- if a public key hash is met (
- Select unique public keys (i.e. if some public key is repeated in different parts of the script/in different script branches, pick a single instance of it). Compressed and uncompressed versions of the same public key must be treated as the same public key under this procedure.
- If no public keys were found fail the procedure; return the collected keys otherwise.
By "miniscript" we mean usage of rust-miniscript
library v2.0.0 (commit
463fc1eadac2b46de1cd5ae93e8255a2ab34b906
) which may be found at
https://github.com/LNP-BP/rust-miniscript/commit/463fc1eadac2b46de1cd5ae93e8255a2ab34b906
The proposed cryptographic commitment scheme is fully compatible, and works with LNPBP-1 standard [12] for constructing cryptographic commitments with a set of public keys.
The standard is not compliant with previously used OP_RETURN-based cryptographic commitments, like OpenTimestamps [1], since it utilises plain value of the public key with the commitment for the OP_RETURN push data.
The author is not aware of any P2(W)SH or non-OP_RETURN cryptographic commitment schemes existing before this proposal, and it is highly probable that the standard is not compatible with ones if they were existing.
The proposed standard is compliant with current Taproot proposal [14], since it can use intermediate Taproot key to store the commitment.
Standard also should be interoperable with Schnorr's signature proposal [15], since it uses miniscript supporting detection of public keys serialized with new BIP-340 rules.
While P2PK outputs are considered obsolete and are vulnerable to a potential quantum computing attacks, it was decided to include them into the specification for unification purposes.
OP_RETURN was originally designed to reduce the size of memory-kept UTXO data; however it is not recommended to use it since it bloats blockchain space usage. This protocol provides support for this type of outputs only because some hardware (like HSM modules or hardware wallets) can't tweak public keys inside outputs and produce a correct signature after for their spending, and keeping the commitment in OP_RETURN's can be an only option. For all other cases it is highly recommended not to use OP_RETURN outputs for the commitments and use tweaking of other types of outputs instead.
While it is possible to put a deterministic CC commitments into OP_RETURN-based outputs like with [1], their format was modified for unification purposes with the rest of the standard. This will help to reduce the verification and commitment code branching, preventing potential bugs in the implementations.
This saves one byte of data per output, which is important in case of blockchain space.
While we could pick a new BIP340-based rules for public key serialization [15], this will require software to support new versions of the secp256k1 libraries and language-specific wrappers, which may be a big issue for legacy software usually used by hardware secure modules, which require presence of OP_RETURN's (see rationale points above).
These types of outputs are still widely used in the industry and it was decided to continue their support, which may be dropped in a higher-level requirements by protocols operating on top of LNPBP-2.
Having some of the public keys tweaked with the message digest, and some left intact will make it impossible to define a simple and deterministic commitment scheme for an arbitrary script and output type that will prevent any potential double-commitments.
We use determinism of the proposed Miniscript standard to parse the Bitcoin script in an implementation-idependet way and in order to avoid the requirement of the full-fledged Bitcoin Script interpreter for the commitment verification.
The procedure fails on any public key hash present in the script, which prevents
multiple commitment vulnerability, when different parties may be provided with
different extra-transaction proof (ETP) data, such that they will use
different value for the S
public key matching two partial set of the public
keys (containing and not containing public keys for the hashed values).
The algorithm does not require that all of the public keys will be used in
signature verification for spending the given transaction output (i.e. public
keys may not be prefixed with [v]c:
code in Miniscript [16]), so the
committing parties may have a special public key shared across them for
embedding the commitment, without requiring to know the corresponding private
key to spend the output.
With Taproot we can't tweak the public key contained in the scriptPubkey
directly since it will invalidate its commitment to the Tapscript and to the
intermediate key, rendering output unspendable. Thus, we put tweak into the
underlying intermediate public key as the only available option.
https://github.com/LNP-BP/rust-lnpbp/blob/master/src/bp/dbc/lockscript.rs
Authors would like to thank:
- Giacomo Zucco and Alekos Filini for their initial work on the commitment schemes as a part of early RGB effort [13];
- Dr Christian Decker for pointing out on Lightning Network incompatibility with all existing cryptographic commitment schemes.
- Peter Todd. OpenTimestamps: Scalable, Trust-Minimized, Distributed Timestamping with Bitcoin. https://petertodd.org/2016/opentimestamps-announcement
- Peter Todd. Preventing Consensus Fraud with Commitments and Single-Use-Seals. https://petertodd.org/2016/commitments-and-single-use-seals
- Eternity Wall's "sign-to-contract" article
- Adam Back, Matt Corallo, Luke Dashjr, et al. Enabling Blockchain Innovations with Pegged Sidechains (commit5620e43). Appenxix A. https://blockstream.com/sidechains.pdf.
- https://exonum.com/doc/version/latest/advanced/bitcoin-anchoring/
- Pieter Wuille. Taproot proposal. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html
- Gregory Maxwell. Taproot: Privacy preserving switchable scripting. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html
- Gregory Maxwell. Graftroot: Private and efficient surrogate scripts under the taproot assumption. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html
- Andrew Poelstra. Scriptless scripts. http://diyhpl.us/wiki/transcripts/layer2-summit/2018/scriptless-scripts/
- Lightning Network BOLT-3 standard, version 1.0. Sections ["Offered HTLC Outputs"] https://github.com/lightningnetwork/lightning-rfc/blob/v1.0/03-transactions.md#offered-htlc-outputs and ["Received HTLC Outputs"] https://github.com/lightningnetwork/lightning-rfc/blob/v1.0/03-transactions.md#received-htlc-outputs.
- BOLT-3 Lightning network specification
- Maxim Orlovsky, et al. Key tweaking: collision-resistant elliptic curve-based commitments (LNPBP-1 Standard). https://github.com/LNP-BP/lnpbps/blob/master/lnpbp-0001.md
- RGB Protocol Specification, version 0.4. "Commitment Scheme" section. https://github.com/rgb-org/spec/blob/old-master/01-rgb.md#commitment-scheme
- Pieter Wuille. Taproot: SegWit version 1 spending rules. https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
- Pieter Wuille. Schnorr Signatures for secp256k1. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
- Pieter Wuille, Andrew Poelsta. Miniscript. http://bitcoin.sipa.be/miniscript/
This document is licensed under the Creative Commons CC0 1.0 Universal license.
TBD
TBD
TBD