Доказательство обязательств

Кастодиан должен каждому клиенту баланс. Эта программа доказывает, что сумма балансов не превышает опубликованного кастодианом значения резерва, при этом ни один баланс и ни итоговая сумма не публикуются. Каждый клиент может проверить несколькими строками на Python, без специальных инструментов, что его собственный баланс был учтён.

В разделе Примеры программ описана подготовка, общая для всех четырёх страниц с примерами.

1. Что доказывается

Кастодиан строит дерево Меркла с суммами. Лист соответствует одному счёту: это хеш идентификатора клиента и баланса, рядом с которым хранится сам баланс. Узел — это хеш двух своих потомков и их сумм, рядом с которым хранится сумма этих двух сумм. Поэтому корень несёт итог всех балансов под ним.

Дерево строится внутри программы из закрытого списка счетов. Вызов доказывает, что:

1. корень, опубликованный в квитанции, является корнем дерева сумм по счетам, которые предоставил кастодиан;
2. каждая сумма в нём равна истинной сумме двух нижележащих, без переполнения;
3. итог в корне не превышает значение резерва, зафиксированное при развёртывании.

Пункт 2 — то, чего не может дать дерево сумм, опубликованное без доказательства. Известная атака на голое дерево сумм состоит в том, что кастодиан записывает сумму родителя меньшей, чем суммы его потомков, и ни один клиент не может заметить это по одному пути. Здесь суммы вычисляет программа, а доказательства какой-либо другой арифметики не существует.

Доказательство не покрывает полноту: кастодиан сам выбирает, какие счета включить. Этот пробел закрывают клиенты. Каждый из них проверяет, что лист с его идентификатором и его балансом находится под опубликованным корнем (раздел 7). Пропущенный счёт обнаружит его владелец.

2. Интерфейс

Значение резерва находится в публичном сегменте, а не в выходных данных, по двум причинам. Во-первых, там нет места: статус, счётчик и 160-битный корень занимают все слоты. Во-вторых, оно формулирует утверждение до появления доказательства: развёртывание программы публикует «резервы R, снимок S», а вызов затем либо доказывает, что балансы укладываются в R, либо возвращает статус 2.

Хеши, точно:

leaf  = SHA-256( be32(0) ‖ id (16 bytes) ‖ be64(balance) )                                  28 bytes
node  = SHA-256( be32(1) ‖ left hash ‖ be64(left sum) ‖ right hash ‖ be64(right sum) )      84 bytes
empty = leaf with id 0 and balance 0

В дереве всегда 32 листа. Счета заполняют его слева, остальные листья пустые. Ведущие 0 и 1 не позволяют прочитать лист как узел.

Порядок байтов. SHA-256 везде использует big-endian, а системный вызов SHA256 принимает свой 64-байтовый блок как шестнадцать слов big-endian. Поэтому эта программа читает идентификатор как четыре слова big-endian и публикует корень как слова big-endian: выход 2, выведенный в шестнадцатеричном виде, — это первые восемь шестнадцатеричных цифр корня. Это обратное соглашение по сравнению с программой на Keccak, потому что два этих хеша определены на противоположных порядках байтов.

3. Гостевая программа

my-guests/solvency/src/main.rs, полностью:

#![no_std]
#![no_main]

use guest_sdk::{halt, read_input, read_public, sha256_compress, write_output};

/// The tree always has 32 leaves. Accounts fill it from the left; the rest are empty leaves.
const LEAVES: usize = 32;

const SOLVENT: u32 = 1;
const INSOLVENT: u32 = 2;
const TOO_MANY: u32 = 3;
const OVERFLOW: u32 = 4;

const LEAF_TAG: u32 = 0;
const NODE_TAG: u32 = 1;

/// SHA-256's initial state (FIPS 180-4 §5.3.3).
const IV: [u32; 8] = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
];

#[derive(Clone, Copy)]
struct Node {
    hash: [u32; 8],
    sum: u64,
}

/// SHA-256 of the 28 bytes `be32(0) ‖ id (16 bytes) ‖ be64(balance)`. The message, its `0x80`
/// terminator and its bit length fit one 64-byte block, so a leaf is one compression.
fn leaf(id: &[u32; 4], balance: u64) -> Node {
    let mut buf = [0u32; 24];
    buf[0] = LEAF_TAG;
    buf[1..5].copy_from_slice(id);
    buf[5] = (balance >> 32) as u32;
    buf[6] = balance as u32;
    buf[7] = 0x8000_0000;
    buf[15] = 28 * 8;
    buf[16..].copy_from_slice(&IV);
    sha256_compress(&mut buf);
    let mut hash = [0u32; 8];
    hash.copy_from_slice(&buf[16..]);
    Node { hash, sum: balance }
}

/// SHA-256 of the 84 bytes `be32(1) ‖ left hash ‖ be64(left sum) ‖ right hash ‖ be64(right sum)`:
/// two compressions. `None` when the two sums do not fit a u64.
fn parent(l: &Node, r: &Node) -> Option<Node> {
    let sum = l.sum.checked_add(r.sum)?;
    let mut buf = [0u32; 24];
    buf[16..].copy_from_slice(&IV);
    // Block 1: words 0..16 of the message.
    buf[0] = NODE_TAG;
    buf[1..9].copy_from_slice(&l.hash);
    buf[9] = (l.sum >> 32) as u32;
    buf[10] = l.sum as u32;
    buf[11..16].copy_from_slice(&r.hash[..5]);
    sha256_compress(&mut buf);
    // Block 2: the last five words, the terminator, zeros, the bit length.
    buf[..3].copy_from_slice(&r.hash[5..]);
    buf[3] = (r.sum >> 32) as u32;
    buf[4] = r.sum as u32;
    buf[5] = 0x8000_0000;
    buf[6..15].fill(0);
    buf[15] = 84 * 8;
    sha256_compress(&mut buf);
    let mut hash = [0u32; 8];
    hash.copy_from_slice(&buf[16..]);
    Some(Node { hash, sum })
}

/// Public segment, fixed at deploy: [reserves low word, reserves high word, snapshot label].
/// Private input: [n, then n accounts of (id: 4 words, balance low, balance high)].
/// Outputs: [status, n, root (first 5 words), 0].
#[no_mangle]
pub extern "C" fn main() -> ! {
    let reserves = read_public(0) as u64 | (read_public(1) as u64) << 32;

    let n = read_input(0) as usize;
    if n > LEAVES {
        write_output(0, TOO_MANY);
        halt();
    }

    let empty = leaf(&[0; 4], 0);
    let mut row = [empty; LEAVES];
    for (i, slot) in row.iter_mut().enumerate().take(n) {
        let at = 1 + 6 * i as u32;
        let id = [read_input(at), read_input(at + 1), read_input(at + 2), read_input(at + 3)];
        let balance = read_input(at + 4) as u64 | (read_input(at + 5) as u64) << 32;
        *slot = leaf(&id, balance);
    }

    // Fold the row in place, a level at a time, until one node is left.
    let mut width = LEAVES;
    while width > 1 {
        width /= 2;
        for i in 0..width {
            match parent(&row[2 * i], &row[2 * i + 1]) {
                Some(p) => row[i] = p,
                None => {
                    write_output(0, OVERFLOW);
                    halt();
                }
            }
        }
    }
    let root = row[0];

    write_output(0, if root.sum <= reserves { SOLVENT } else { INSOLVENT });
    write_output(1, n as u32);
    for k in 0..5 {
        write_output(2 + k as u32, root.hash[k]);
    }
    halt();
}

Дополнение записано вручную. guest_sdk::sha256 принимает любую строку байтов и копирует её побайтово. Здесь каждое сообщение состоит из целых слов известной длины, поэтому программа заполняет 16-словный блок напрямую: слова сообщения, затем 0x80000000, нули и длина в битах в последнем слове. Лист — это одно сжатие. 84 байта узла переходят во второй блок, поэтому узел — это два сжатия.

Балансы — u64, суммы проверяются. Баланс не может быть отрицательным, поскольку в этом типе нет отрицательных значений; так исключается другой классический способ уменьшить итог. checked_add превращает переполнение в статус 4 вместо свёрнутой суммы.

Неплатёжеспособный результат — тоже результат. Статус 2 — обычная остановка с опубликованным корнем. Кастодиан не может получить квитанцию со статусом 1 для балансов, превышающих значение резерва, а квитанция со статусом 2 — это именно доказательство такого превышения.

4. Сторона хоста

solvency.py использует только стандартную библиотеку Python:

solvency.py setup   <accounts.csv> <reserves> <snapshot label>   writes public.txt, prints the root
solvency.py witness <accounts.csv>                 prints the private words
solvency.py path    <accounts.csv> <row>           prints that account's inclusion proof (JSON)
solvency.py verify  <proof.json> <root prefix hex> checks a proof against a receipt's root

Два хеша в нём — это вся спецификация, которая нужна клиенту:

def leaf(ident: bytes, balance: int):
    return hashlib.sha256(struct.pack(">I", 0) + ident + struct.pack(">Q", balance)).digest(), balance

def parent(l, r):
    h = hashlib.sha256(struct.pack(">I", 1) + l[0] + struct.pack(">Q", l[1]) + r[0] + struct.pack(">Q", r[1]))
    return h.digest(), l[1] + r[1]

В демонстрации двенадцать счетов в demo-accounts.csv, по одной строке id,balance на счёт, с балансами в единицах 10⁻⁸ (точность, которую использует мостовой токен, например zUSD). В сумме они дают 100 215,185678. Кастодиан заявляет резервы в 101 000:

$ python3 solvency.py setup demo-accounts.csv 10100000000000 20260930
root 46b78564d60f75bdc9552d8ad1c4aadf411354054be3ffb80337b8549471a82c
root prefix 46b78564d60f75bdc9552d8ad1c4aadf41135405
root words 1186432356 3591337405 3377802634 3519326943 1091785733
liabilities 10021518567800
wrote public.txt
$ cat public.txt
2531887104 2351 20260930

2351 × 2³² + 2531887104 равно 10 100 000 000 000. Строка liabilities — собственное представление кастодиана. Она никогда не публикуется.

Идентификаторы должны быть уникальными и неугадываемыми. Если бы двум клиентам с одинаковым балансом выдали один и тот же лист, кастодиан мог бы засчитать одно обязательство за обоих. Идентификатор, который только его клиент может опознать как свой, предотвращает это, а неугадываемый идентификатор не даёт клиенту, увидевшему хеш соседнего узла, проверять догадки о балансе соседа. В демонстрации используются первые 16 байт хеша. В реальном развёртывании идентификатор следует выводить из счёта клиента и nonce снимка и показывать его клиенту.

5. Сборка и запуск

$ rand-guest build my-guests/solvency --max-words 65535
994 words against a cap of 65535 (fits); 0 ecall(s) with a non-static a7
OK
wrote my-guests/solvency/image.bin and its .sha256 (994 words, hc 5559791a05bd9269bf7fc4e893c05e8b21defe5ef966d831b49ea463fb4552d3, program id 697412b5db65647164c21b27e4b4feb0b5f0b9fce2381157cd0786bfecf1769f)
$ cd my-guests/solvency
$ python3 solvency.py witness demo-accounts.csv > witness.txt
$ rand-guest run image.bin --public $(cat public.txt) --input $(cat witness.txt) --tier 14
out[0] = 1
out[1] = 12
out[2] = 1186432356
out[3] = 3591337405
out[4] = 3377802634
out[5] = 3519326943
out[6] = 1091785733
out[7] = 0
cycles 7492
tier 14
tier 14: fits (cycles 7762 of 16383, Poseidon2 permutations 270 of 2048)

Статус 1, двенадцать счетов и пять слов корня, которые вывел скрипт. Свидетельство состоит из 73 слов: счётчик и по шесть слов на каждый счёт.

Если снизить значение резерва до 100 единиц (--public 100 0 1), те же счета дают out[0] = 2. Число счетов 33 даёт out[0] = 3. Два счёта, балансы которых в сумме превышают 2⁶⁴, дают out[0] = 4.

6. Бюджет

Число сжатий — это n листьев, один пустой лист (вычисляется один раз и копируется) и по два на каждый из 31 узла. Один вызов может использовать не более 128 сжатий, а уровень 14 — наивысший уровень, доступный вызову, поэтому 32 счёта — почти предел того, что один вызов может доказать в этой конструкции. Дереву из 64 листьев нужно 190 сжатий, и оно не укладывается.

Это демонстрационный размер. Чтобы выйти за него, нужно разделить дерево на несколько вызовов и передавать в итоговый вызов обязательство на корень и сумму каждого поддерева; этот шаблон описан в разделе Напишите программу для любой задачи, превышающей бюджет. Этот пример так не делает.

Начиная с chain 18 сжатие стоит 64 gas против 1 для обычного цикла. Кошелёк выводит точный gas запуска и объявленный им лимит:

gas: 12489 (declaring 16384, tier 14)

Каждая строка стоит 1 gas, а сжатие — ещё 63: 7 764 строки плюс 75 × 63 дают 12 489. Больше трети gas уходит на хеширование. (Кошелёк насчитывает на две строки больше, чем rand-guest run, из-за привязки транзакции, которую chain 18 добавляет в публичный сегмент вызова.)

7. Проверка клиента

Кастодиан выдаёт каждому клиенту его путь: хеш соседа и сумму соседа на каждом из пяти уровней.

$ python3 solvency.py path demo-accounts.csv 6 > proof6.json
$ head -12 proof6.json
{
 "id": "f8f4e4a0c855aad0d0f9ae5bab108333",
 "balance": 1820025000000,
 "path": [
  {
   "hash": "e39eaaabec5cca1fe4c76ce656692be631a39e807876f93bdd7baf8b057d6997",
   "sum": 6600000000,
   "sibling_is_left": false
  },
  {
   "hash": "4732f069886c966e6429ee9063f73429bf153eb2575cf2a28f00f27b7d0d89c6",
   "sum": 31500000000,

Клиент пересчитывает корень по своему идентификатору и балансу и сравнивает его первые 20 байт с выходами 2–6 квитанции:

$ python3 solvency.py verify proof6.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix 46b78564d60f75bdc9552d8ad1c4aadf41135405 MATCH

Путь для баланса, на единицу большего, чем в дереве, до корня не доходит:

$ python3 solvency.py verify tampered.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix e9a1b4cbe49e412214b97afe73348fa7c555fa7a DOES NOT MATCH

Вся проверка — это функции leaf и parent, приведённые выше, применённые пять раз. Клиент, который не хочет запускать скрипт кастодиана, может написать её сам.

Путь показывает клиенту суммы его соседей. Первый шаг приведённого выше пути раскрывает, что соседний лист содержит 6 600 000 000 единиц, а каждый следующий шаг раскрывает итог поддерева. Это неотъемлемое свойство обычного дерева сумм. Перемешивание листьев при каждом снимке ограничивает то, что клиент может узнать со временем, а полное сокрытие сумм требует обязательств вместо обычных чисел, чего этот пример не делает.

8. Развёртывание

$ rand fee deploy 994 --public-words 3
0.1007 RAND
$ rand program deploy image.bin --public public.txt
program id: fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0 (994 words, hc 1a7959556992bd05e8c47fbf8b5ec0935efede2131d866f963a49eb4d35245fb, public input 3 words, digest 70d5ae8935d646f7a0dd426c30aaf68e9bc382534d8a6ced90e363e129403608)
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 6.8s: tier 10, 1368908 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 116.7s: tier 14, 1500710 bytes
submitted deploy 39e8f35e0bdc7bc105ce942dc492b52f7a5efbb682ab6ebecc17cb310a161ada
  0 RAND out, 59.8545 RAND change, fee 0.1007 RAND, anchored at height 97831, proved in 116.7s (bundle) + 6.8s (auth)

Идентификатор программы связывает значение резерва и метку снимка с кодом. Новый снимок — это новое развёртывание, стоимостью около одной десятой RAND, а его идентификатор — публичное заявление о новом обязательстве.

9. Вызов

$ rand call fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0 \
    $(sed 's/[0-9][0-9]*/--input &/g' witness.txt)

proving the call locally (73 inputs stay private, over the program's 3-word public input)…
gas: 12489 (declaring 16384, tier 14)
fee 0.007487437 RAND (incl. two price steps of headroom)
proved in 122.9s: tier 14, 1911152 bytes, outputs [1, 12, 1186432356, 3591337405, 3377802634, 3519326943, 1091785733, 0]
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 6.8s: tier 10, 1375371 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 111.9s: tier 14, 1500198 bytes
submitted call 5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17
  0 RAND out, 59.709221126 RAND change, fee 0.007487437 RAND, anchored at height 98336, proved in 111.9s (bundle) + 6.8s (auth)
{
  "h_in": "b151f38fbbefd08c9f36e65da89f016ba7fc0ccdb52bddda6544e3d86372d331",
  "h_pub": "70d5ae8935d646f7a0dd426c30aaf68e9bc382534d8a6ced90e363e129403608",
  "height": 98574,
  "index": 0,
  "outputs": [
    1,
    12,
    1186432356,
    3591337405,
    3377802634,
    3519326943,
    1091785733,
    0
  ],
  "program": "fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0",
  "tier": 14,
  "tx": "5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17"
}
input transcript published; open it with `rand open-call 5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17`

Статус 1, двенадцать счетов и корень 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 в шестнадцатеричном виде. Ничто в транзакции не раскрывает ни баланс, ни итоговую сумму.

Это вызов уровня tier-14, поэтому медленнее всего строится доказательство вызова: 123 с, затем 7 с на авторизацию траты и 112 с на пакет, итого около пяти минут, с пиком 6,6 GB. Размер доказательства — 1 911 152 байта. На таблицу SHA-256 приходится около 0,4 MB.

10. Проверьте сами

1. Утверждение. rand_getProgramPublic по идентификатору программы возвращает величину резерва и метку. Действительно ли кастодиан держит этот резерв, это вне данного доказательства: это подтверждается балансом в сети, письмом аудитора или, для bridged-актива, собственным rand_getTokenSupply соответствующей сети.
2. Код. Пересоберите my-guests/solvency на том же коммите circuits и сравните hc с code_hash программы.
3. Квитанция. Статус 1, слот 7 не равен 3735928559, а program совпадает с идентификатором. Выходы с 2 по 6 — это корень, с которым сверяется каждый клиент.
4. Ваш собственный лист, как в разделе 7.

Любой может повторить вызов на демонстрационных счетах или изменить баланс и увидеть, как сдвигается корень.

Что доказательство вам не даёт

• Самих резервов. Доказательство касается обязательств относительно некоторого числа. Для этого числа нужны собственные подтверждения.
• Полноты без участия клиентов. Счёт, который кастодиан пропустил, обнаруживает только клиент, которому он принадлежит. Чем больше клиентов проверяют, тем меньше остаётся простора.
• Момента времени, совпадающего с моментом фиксации резервов. Кастодиан может занять средства на час снимка. Частые снимки в неанонсированное время сужают такую возможность.
• Скрытых соседей. Путь клиента показывает суммы соседних узлов (раздел 7).
• Более 32 счетов в одном вызове. См. бюджет.