Vertical: Client-validated data (3)
Title: Multi-message commitment scheme with zero-knowledge provable unique properties
Author: Dr Maxim Orlovsky <[email protected]>
Type: Standards Track
Finalized: not yet
The standard defines a way to commit to a multiple independent messages with a single digest such that the fact of each particular commitment, and a protocol under which the commitment is made may be proven without exposing the information about the other messages and used protocols.
LNPBP-3 defines a standard for embedding cryptographic commitment into bitcoin transaction in a deterministic & provable way . The standard is based on LNPBP-1 public key tweaking procedure , which prevents multiple commitments inside a tweak. However, this may result in two potential problems.
First, there could be two different protocols willing to put different commitments into a single transaction output; and only one of the protocols will succeed due to the LNPBP-2 & LNPBP-1 design.
Second, it is possible that some protocol may require committing to a number of messages within a single transaction and public key with the requirement that some dedicated information from these messages (like the message type) should be unique across the whole message set. For instance, this is required for state updates, where such updates separated into different blocks (messages) and should be kept private, such that a single party will know information about a single update and should not be disclosed any information about the rest. However, in such case, there should be a proof that the other state updates do not affect the state of the analyzed update, excluding state collisions. In such a setup, each state may be assigned a unique integer identifier (like cryptographic digest), and a special form of zero-knowledge proof should be utilized to proof the fact that all the states are different without exposing the actual state ids.
While both cases are impossible at the level of LNPBP-3 & LNPBP-1 standards, the current proposal defines a procedure for structuring multiple independent messages in a privacy-preserving (zero-knowledge) way, allowing that some properties of the committed messages may be proven in a zero-knowledge way, i.e. without revealing any information about the source messages or the properties themselves.
The protocol follows dea of Bloom filters , which are already used for keeping confidentiality of the information requested from Bitcoin Core by SPV clients .
Multiple commitments under different protocols are identified with a unique per-protocol 256-bit identifiers (like tagged hashes of protocol name and/or characteristic parameters) and serialized into 256-bit slots within
N * 32byte buffer such as
N >> M, where
Mis the number of the individual commitments. The rest of the slots is filled with random data deterministically generated from a single entropy source. The position
nfor a commitment with the identifier
idis computed as
n = id mod N, guaranteeing that no two commitments under the same protocol with a given
idmay be simultaneously present.
For a given set of
msgMunder protocols with corresponding unique ids
idMthe commitment procedure runs as follows:
- 1.Pick 64 bits of entropy from uniform entropy source (like the same which is used for generating private keys). This entropy will be identified with
- 2.Pick a 16-bit number
N >> M, for instance
N = M * 2and allocate
32*Nbyte buffer (such that the maximum buffer length MUST not exceed 2^21, i. e 2 MB).
- 3.For each of the messages:
- create a corresponding cryptographic commitment
cIaccording to the per-message protocol,
n = idI mod N(if the protocol identifier is a hash, it should be converted into unsigned integer of appropriate dimensionality using little- endian notation),
- if the slot
nis not used, serialize a
cIhash into it using bitcoin-style hash serialization format; otherwise go to step 3 and generate a new
N' >> N.
- 4.For each of the slots that remain empty (the slot number is represented by
- compute SHA256-tagged hash of
seed_entropy || j, where both values are serialized as little-endian byte strings (the total length of resulting byte string for hashing should be 272 bits). The tagged hash procedure must run according to BIP-340  using UTF-8 representation of
LNPBP4:entropystring as the tag.
- 5.Compute commitment to the resulting buffer with LNPBP-1 , LNPBP-2  or other protocol using
LNPBP4as the protocol-specific tag.
A party needing to reveal the proofs for the commitment to the message
msgAunder this scheme and conceal the rest of the messages and protocols participating in the commitment has to publish the following data:
- 1.A source of the message
msgAand information about its protocol with id
A party needing to reveal the proofs for all commitments to all the messages and prove that there were no other commitments made must publish the following data:
- 1.A source of the messages
msgMand information about their protocols with id
A party provided with the data from the partial reveal procedure and wishing to verify the commitment to the message MUST use the following procedure:
n = idA mod N, where
idAis the message-specific protocol id and
Nis the length of the commitment buffer in bytes divided on 32.
- 2.Compute commitment to the message by following the procedure from the step 3 of the commitment scheme
- 3.Verify that the resulting 32-bit commitment is equal to the commitment stored in
n's 32-byte slot of the commitment buffer; fail verification otherwise.
A party provided with the data from the reveal with full disclosure procedure may verify that the provided commitment buffer contains only commitment to the provided messages (and no other commitments) by allocating a new empty (all bytes set to
0x00) commitment buffer of the same length as the revealed commitment buffer, and re-running steps 4-6 from the commitment procedure . If the new buffer match per-byte the revealed commitment buffer, then the verification succeeded; otherwise it has failed.
The maximum buffer size defines the potential size of the data provided for client-side-validation, and may represent a form of DoS attack vector, when the party allocating/creating buffer defines a storage and network data transfer requirements for all the future verifying parties. From the other side, the maximum buffer size defines the upper bound for the maximum number of commitments that may be embedded within a single transaction output. We have selected a 16-bit limit for the number of slots, limiting the maximum buffer size to 2 MBs, and maximum theoretical number of simultaneous commitments under the same transaction output to 2^16. However, in practice, the latter limit will never be reached, because assuming the uniform distribution of protocol-specific identifier hashes a committing party will be able to produce simultaneous commitment under
1^8different protocols in average.
Reference implementation can be found inside client-side-validation foundation rust library <https://github.com/LNP-BP/client_side_validation/blob/master /commit_verify/src/multi_commit.rs> and represents integral part of this standard.
- 1.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
- 2.Maxim Orlovsky, et al. Deterministic embedding of LNPBP1-type commitments into
scriptPubkeyof a transaction output (LNPBP-2 Standard). https://github.com/LNP-BP/lnpbps/blob/master/lnpbp-0002.md
- 3.Giacomo Zucco, et al. Deterministic definition of transaction output containing cryptographic commitment (LNPBP-3 Standard). https://github.com/LNP-BP/lnpbps/blob/master/lnpbp-0003.md
- 4.Pieter Wuille, et al. BIP-340: Schnorr Signatures for secp256k1. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
- 5.Bloom, Burton H. (1970), "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 13 (7): 422–426, doi:10. 1145/362686.362692. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.641.9096
- 6.Mike Hearn, Matt Corallo. BIP-37: Connection Bloom filtering. https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki
This document is licensed under the Creative Commons CC0 1.0 Universal license.