2021-07-26 12:33:28 -07:00
<!DOCTYPE HTML>
2023-11-30 00:04:57 -08:00
< html lang = "en" class = "light" dir = "ltr" >
2021-07-26 12:33:28 -07:00
< head >
<!-- Book generated using mdBook -->
< meta charset = "UTF-8" >
< title > CommitIvk - The Orchard Book< / title >
<!-- Custom HTML head -->
< meta name = "description" content = "" >
< meta name = "viewport" content = "width=device-width, initial-scale=1" >
2023-11-30 00:04:57 -08:00
< meta name = "theme-color" content = "#ffffff" >
2021-07-26 12:33:28 -07:00
2022-04-28 09:45:52 -07:00
< link rel = "icon" href = "../../favicon.svg" >
< link rel = "shortcut icon" href = "../../favicon.png" >
< link rel = "stylesheet" href = "../../css/variables.css" >
< link rel = "stylesheet" href = "../../css/general.css" >
< link rel = "stylesheet" href = "../../css/chrome.css" >
< link rel = "stylesheet" href = "../../css/print.css" media = "print" >
2021-07-26 12:33:28 -07:00
<!-- Fonts -->
2022-04-28 09:45:52 -07:00
< link rel = "stylesheet" href = "../../FontAwesome/css/font-awesome.css" >
< link rel = "stylesheet" href = "../../fonts/fonts.css" >
2021-07-26 12:33:28 -07:00
<!-- Highlight.js Stylesheets -->
2022-04-28 09:45:52 -07:00
< link rel = "stylesheet" href = "../../highlight.css" >
< link rel = "stylesheet" href = "../../tomorrow-night.css" >
< link rel = "stylesheet" href = "../../ayu-highlight.css" >
2021-07-26 12:33:28 -07:00
<!-- Custom theme stylesheets -->
< / head >
2023-11-30 00:04:57 -08:00
< body class = "sidebar-visible no-js" >
< div id = "body-container" >
2021-07-26 12:33:28 -07:00
<!-- Provide site root to javascript -->
2023-11-30 00:04:57 -08:00
< script >
2022-04-28 09:45:52 -07:00
var path_to_root = "../../";
2021-07-26 12:33:28 -07:00
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
< / script >
<!-- Work around some values being stored in localStorage wrapped in quotes -->
2023-11-30 00:04:57 -08:00
< script >
2021-07-26 12:33:28 -07:00
try {
var theme = localStorage.getItem('mdbook-theme');
var sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') & & theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') & & sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
< / script >
<!-- Set the theme before any content is loaded, prevents flash -->
2023-11-30 00:04:57 -08:00
< script >
2021-07-26 12:33:28 -07:00
var theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
var html = document.querySelector('html');
html.classList.remove('light')
html.classList.add(theme);
2023-11-30 00:04:57 -08:00
var body = document.querySelector('body');
body.classList.remove('no-js')
body.classList.add('js');
2021-07-26 12:33:28 -07:00
< / script >
2023-11-30 00:04:57 -08:00
< input type = "checkbox" id = "sidebar-toggle-anchor" class = "hidden" >
2021-07-26 12:33:28 -07:00
<!-- Hide / unhide sidebar before it is displayed -->
2023-11-30 00:04:57 -08:00
< script >
var body = document.querySelector('body');
var sidebar = null;
var sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
2021-07-26 12:33:28 -07:00
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
2023-11-30 00:04:57 -08:00
} else {
sidebar = 'hidden';
2021-07-26 12:33:28 -07:00
}
2023-11-30 00:04:57 -08:00
sidebar_toggle.checked = sidebar === 'visible';
body.classList.remove('sidebar-visible');
body.classList.add("sidebar-" + sidebar);
2021-07-26 12:33:28 -07:00
< / script >
< nav id = "sidebar" class = "sidebar" aria-label = "Table of contents" >
< div class = "sidebar-scrollbox" >
2022-04-28 09:45:52 -07:00
< ol class = "chapter" > < li class = "chapter-item expanded affix " > < a href = "../../index.html" > Orchard< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../concepts.html" > < strong aria-hidden = "true" > 1.< / strong > Concepts< / a > < / li > < li > < ol class = "section" > < li class = "chapter-item expanded " > < a href = "../../concepts/preliminaries.html" > < strong aria-hidden = "true" > 1.1.< / strong > Preliminaries< / a > < / li > < / ol > < / li > < li class = "chapter-item expanded " > < a href = "../../user.html" > < strong aria-hidden = "true" > 2.< / strong > User Documentation< / a > < / li > < li > < ol class = "section" > < li class = "chapter-item expanded " > < a href = "../../user/keys.html" > < strong aria-hidden = "true" > 2.1.< / strong > Creating keys and addresses< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../user/creating-notes.html" > < strong aria-hidden = "true" > 2.2.< / strong > Creating notes< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../user/spending-notes.html" > < strong aria-hidden = "true" > 2.3.< / strong > Spending notes< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../user/integration.html" > < strong aria-hidden = "true" > 2.4.< / strong > Integration into an existing chain< / a > < / li > < / ol > < / li > < li class = "chapter-item expanded " > < a href = "../../design.html" > < strong aria-hidden = "true" > 3.< / strong > Design< / a > < / li > < li > < ol class = "section" > < li class = "chapter-item expanded " > < a href = "../../design/keys.html" > < strong aria-hidden = "true" > 3.1.< / strong > Keys and addresses< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/actions.html" > < strong aria-hidden = "true" > 3.2.< / strong > Actions< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/commitments.html" > < strong aria-hidden = "true" > 3.3.< / strong > Commitments< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/commitment-tree.html" > < strong aria-hidden = "true" > 3.4.< / strong > Commitment tree< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/nullifiers.html" > < strong aria-hidden = "true" > 3.5.< / strong > Nullifiers< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/signatures.html" > < strong aria-hidden = "true" > 3.6.< / strong > Signatures< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/circuit.html" > < strong aria-hidden = "true" > 3.7.< / strong > Circuit< / a > < / li > < li > < ol class = "section" > < li class = "chapter-item expanded " > < a href = "../../design/circuit/gadgets.html" > < strong aria-hidden = "true" > 3.7.1.< / strong > Gadgets< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/circuit/commit-ivk.html" class = "active" > < strong aria-hidden = "true" > 3.7.2.< / strong > CommitIvk< / a > < / li > < li class = "chapter-item expanded " > < a href = "../../design/circuit/note-commit.html" > < strong aria-hidden = "true" > 3.7.3.< / strong > NoteCommit< / a > < / li > < / ol > < / li > < / ol > < / li > < / ol >
2021-07-26 12:33:28 -07:00
< / div >
< div id = "sidebar-resize-handle" class = "sidebar-resize-handle" > < / div >
< / nav >
2023-11-30 00:04:57 -08:00
<!-- Track and set sidebar scroll position -->
< script >
var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox');
sidebarScrollbox.addEventListener('click', function(e) {
if (e.target.tagName === 'A') {
sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop);
}
}, { passive: true });
var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll');
sessionStorage.removeItem('sidebar-scroll');
if (sidebarScrollTop) {
// preserve sidebar scroll position when navigating via links within sidebar
sidebarScrollbox.scrollTop = sidebarScrollTop;
} else {
// scroll sidebar to current active section when navigating via "next/previous chapter" buttons
var activeSection = document.querySelector('#sidebar .active');
if (activeSection) {
activeSection.scrollIntoView({ block: 'center' });
}
}
< / script >
2021-07-26 12:33:28 -07:00
< div id = "page-wrapper" class = "page-wrapper" >
< div class = "page" >
2023-11-30 00:04:57 -08:00
< div id = "menu-bar-hover-placeholder" > < / div >
< div id = "menu-bar" class = "menu-bar sticky" >
2021-07-26 12:33:28 -07:00
< div class = "left-buttons" >
2023-11-30 00:04:57 -08:00
< label id = "sidebar-toggle" class = "icon-button" for = "sidebar-toggle-anchor" title = "Toggle Table of Contents" aria-label = "Toggle Table of Contents" aria-controls = "sidebar" >
2021-07-26 12:33:28 -07:00
< i class = "fa fa-bars" > < / i >
2023-11-30 00:04:57 -08:00
< / label >
2021-07-26 12:33:28 -07:00
< button id = "theme-toggle" class = "icon-button" type = "button" title = "Change theme" aria-label = "Change theme" aria-haspopup = "true" aria-expanded = "false" aria-controls = "theme-list" >
< i class = "fa fa-paint-brush" > < / i >
< / button >
< ul id = "theme-list" class = "theme-popup" aria-label = "Themes" role = "menu" >
2023-11-30 00:04:57 -08:00
< li role = "none" > < button role = "menuitem" class = "theme" id = "light" > Light< / button > < / li >
2021-07-26 12:33:28 -07:00
< li role = "none" > < button role = "menuitem" class = "theme" id = "rust" > Rust< / button > < / li >
< li role = "none" > < button role = "menuitem" class = "theme" id = "coal" > Coal< / button > < / li >
< li role = "none" > < button role = "menuitem" class = "theme" id = "navy" > Navy< / button > < / li >
< li role = "none" > < button role = "menuitem" class = "theme" id = "ayu" > Ayu< / button > < / li >
< / ul >
< button id = "search-toggle" class = "icon-button" type = "button" title = "Search. (Shortkey: s)" aria-label = "Toggle Searchbar" aria-expanded = "false" aria-keyshortcuts = "S" aria-controls = "searchbar" >
< i class = "fa fa-search" > < / i >
< / button >
< / div >
< h1 class = "menu-title" > The Orchard Book< / h1 >
< div class = "right-buttons" >
2022-04-28 09:45:52 -07:00
< a href = "../../print.html" title = "Print this book" aria-label = "Print this book" >
2021-07-26 12:33:28 -07:00
< i id = "print-button" class = "fa fa-print" > < / i >
< / a >
2023-11-30 00:04:57 -08:00
2021-07-26 12:33:28 -07:00
< / div >
< / div >
< div id = "search-wrapper" class = "hidden" >
< form id = "searchbar-outer" class = "searchbar-outer" >
2023-11-30 00:04:57 -08:00
< input type = "search" id = "searchbar" name = "searchbar" placeholder = "Search this book ..." aria-controls = "searchresults-outer" aria-describedby = "searchresults-header" >
2021-07-26 12:33:28 -07:00
< / form >
< div id = "searchresults-outer" class = "searchresults-outer hidden" >
< div id = "searchresults-header" class = "searchresults-header" > < / div >
< ul id = "searchresults" >
< / ul >
< / div >
< / div >
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
2023-11-30 00:04:57 -08:00
< script >
2021-07-26 12:33:28 -07:00
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
< / script >
< div id = "content" class = "content" >
< main >
< link rel = "stylesheet" href = "https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css" integrity = "sha384-AfEj0r4/OFrOo5t7NnNe46zW/tFgW6x/bCJG8FqQCEo3+Aro6EYUG4+cU+KJWu/X" crossorigin = "anonymous" >
2023-11-30 00:04:57 -08:00
< h1 id = "commitivk" > < a class = "header" href = "#commitivk" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.9334em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > Commit< / span > < / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9334em;" > < span style = "top:-3.1473em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > ivk< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / a > < / h1 >
< h2 id = "message-decomposition" > < a class = "header" href = "#message-decomposition" > Message decomposition< / a > < / h2 >
< p > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > SinsemillaShortCommit< / span > < / span > < / span > < / span > < / span > < / span > is used in the
< a href = "https://zips.z.cash/protocol/protocol.pdf#concretesinsemillacommit" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.9334em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > Commit< / span > < / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9334em;" > < span style = "top:-3.1473em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > ivk< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > function< / a > .
The input to < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > SinsemillaShortCommit< / span > < / span > < / span > < / span > < / span > < / span > is:< / p >
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1.3341em;vertical-align:-0.5841em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "mclose" > )< / span > < span class = "mord" > < span class = "mop" > < span class = "mspace" style = "margin-right:0.1em;" > < / span > < span class = "mord" > ∣ ∣ < / span > < span class = "mspace" style = "margin-right:0.1em;" > < / span > < / span > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < span class = "mclose" > )< / span > < span class
< p > where < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < / span > , < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span > are Pallas base field elements, and < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1.2683em;vertical-align:-0.3013em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.967em;" > < span style = "top:-2.3987em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-3.1809em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3013em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 255.< / span > < / span > < / span > < / span > < / p >
2021-07-26 12:33:28 -07:00
< p > Sinsemilla operates on multiples of 10 bits, so we start by decomposing the message into
chunks:< / p >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:6.4481em;vertical-align:-2.9741em;" > < / span > < span class = "mtable" > < span class = "col-align-r" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.4741em;" > < span style = "top:-5.6341em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "mclose" > )< / span > < / span > < / span > < span style = "top:-3.91em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-2.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vl
2021-07-26 12:33:28 -07:00
< p > Then we recompose the chunks into message pieces:< / p >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:6.04em;vertical-align:-2.75em;" > < / span > < span class = "mord" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.29em;" > < span style = "top:-5.25em;" > < span class = "pstrut" style = "height:5.25em;" > < / span > < span class = "mtable" > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Length < / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 250< / span > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 10< / span > < / span > < / span > < span style = "top:-1.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 240< / span > < / span > < / span > < span style = "top:-0.61em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 10< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:2.75em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-l" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Piece< / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > a< / span > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord" > < span class = "mop" > < span class = "mspace" style = "margin-right:0.1em;" > < / span > < span class = "mord" > ∣ ∣ < / span > < span class = "mspace" style = "margin-right:0.1em;" > < / span > < / span > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord" > < span class = "mop" > < span class = "mspace" style = "margin-right:0.1em;" > < / span > < span class = "mord" > ∣ ∣ < / span > < span class = "mspace" style = "margin-right:0.1em;" > < / span > < / span > < / span > < span class = "mord" > < span class = "mord mat
< p > Each message piece is constrained by < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > SinsemillaHash< / span > < / span > < / span > < / span > < / span > < / span > to its stated length. Additionally,
< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < / span > and < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span > are witnessed as field elements, so we know they are
2021-07-26 12:33:28 -07:00
canonical. However, we need additional constraints to enforce that:< / p >
< ul >
< li > The chunks are the correct bit lengths (or else they could overlap in the decompositions
2023-11-30 00:04:57 -08:00
and allow the prover to witness an arbitrary < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > SinsemillaShortCommit< / span > < / span > < / span > < / span > < / span > < / span > message).< / li >
< li > The chunks contain the canonical decompositions of < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < / span > and < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span >
(or else the prover could witness an input to < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > SinsemillaShortCommit< / span > < / span > < / span > < / span > < / span > < / span > that is
equivalent to < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < / span > and < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span > but not identical).< / li >
2021-07-26 12:33:28 -07:00
< / ul >
< p > Some of these constraints can be implemented with reusable circuit gadgets. We define a
2023-11-30 00:04:57 -08:00
custom gate controlled by the selector < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6721em;vertical-align:-0.2415em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.03588em;" > q< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.4585em;margin-left:-0.0359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Commit< / span > < / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8376em;" > < span style = "top:-2.8416em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > ivk< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2415em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > to hold the remaining constraints.< / p >
< h2 id = "bit-length-constraints" > < a class = "header" href = "#bit-length-constraints" > Bit length constraints< / a > < / h2 >
< p > Chunks < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.4306em;" > < / span > < span class = "mord mathnormal" > a< / span > < / span > < / span > < / span > and < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.4306em;" > < / span > < span class = "mord mathnormal" > c< / span > < / span > < / span > < / span > are directly constrained by Sinsemilla. For the remaining chunks, we
2021-07-26 12:33:28 -07:00
use the following constraints:< / p >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:7.24em;vertical-align:-3.35em;" > < / span > < span class = "mord" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.89em;" > < span style = "top:-5.85em;" > < span class = "pstrut" style = "height:5.85em;" > < / span > < span class = "mtable" > < span class = "vertical-separator" style = "height:7.2em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-3.35em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.85em;" > < span style = "top:-6.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Degree< / span > < / span > < / span > < / span > < span style = "top:-4.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-3.61em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-2.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-1.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < span style = "top:-0.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:3.35em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:7.2em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-3.35em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-l" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.85em;" > < span style = "top:-6.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Constraint< / span > < / span > < / span > < / span > < span style = "top:-4.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord text" > < span class = "mord texttt" > short_lookup_range_check< / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mpunct" > ,< / span > < span class = "mspace" style = "margin-right:0.1667em;" > < / span > < span class = "mord" > 4< / span > < / span > < span class = "mclose" > )< / span > < / span > < / span > < / span > < span style = "top:-3.61em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord text" > < span class = "mord texttt" > short_lookup_range_check< / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mpunct" > ,< / span > < span class = "mspace" style = "margin-right:0.1667em;" > < / span > < span class = "mord" > 5< / span > < / span > < span class = "m
< p > where < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1em;vertical-align:-0.25em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord texttt" > bool_check< / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord mathnormal" > x< / span > < / span > < span class = "mclose" > )< / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.4445em;" > < / span > < span class = "mord mathnormal" > x< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:1em;vertical-align:-0.25em;" > < / span > < span class = "mopen" > (< / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > − < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:1em;vertical-align:-0.25em;" > < / span > < span class = "mord mathnormal" > x< / span > < span class = "mclose" > )< / span > < / span > < / span > < / span > and < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1em;vertical-align:-0.25em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord texttt" > short_lookup_range_check< / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < / span > < span class = "mclose" > )< / span > < / span > < / span > < / span > < / span > is a
2021-07-26 12:33:28 -07:00
< a href = "../decomposition.html#short-range-check" > short lookup range check< / a > .< / p >
2023-11-30 00:04:57 -08:00
< h2 id = "decomposition-constraints" > < a class = "header" href = "#decomposition-constraints" > Decomposition constraints< / a > < / h2 >
2021-07-26 12:33:28 -07:00
< p > We have now derived or witnessed every subpiece, and range-constrained every subpiece:< / p >
< ul >
2023-11-30 00:04:57 -08:00
< li > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.4306em;" > < / span > < span class = "mord mathnormal" > a< / span > < / span > < / span > < / span > (< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 250< / span > < / span > < / span > < / span > bits) is witnessed and constrained outside the gate;< / li >
< li > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > (< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 4< / span > < / span > < / span > < / span > bits) is witnessed and constrained outside the gate;< / li >
< li > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > (< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 1< / span > < / span > < / span > < / span > bits) is witnessed and boolean-constrained in the gate;< / li >
< li > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > (< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 5< / span > < / span > < / span > < / span > bits) is witnessed and constrained outside the gate;< / li >
< li > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.4306em;" > < / span > < span class = "mord mathnormal" > c< / span > < / span > < / span > < / span > (< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 240< / span > < / span > < / span > < / span > bits) is witnessed and constrained outside the gate;< / li >
< li > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > (< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 9< / span > < / span > < / span > < / span > bits) is witnessed and constrained outside the gate;< / li >
< li > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > (< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 1< / span > < / span > < / span > < / span > bits) is witnessed and boolean-constrained in the gate.< / li >
2021-07-26 12:33:28 -07:00
< / ul >
< p > We can now use them to reconstruct both the (chunked) message pieces, and the original
field element inputs:< / p >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:6.0964em;vertical-align:-2.7982em;" > < / span > < span class = "mtable" > < span class = "col-align-r" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.2982em;" > < span style = "top:-5.4341em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < / span > < / span > < span style = "top:-3.91em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < / span > < / span > < span style = "top:-2.3859em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < span style = "top:-0.8618em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:2.7982em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "col-align-l" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.2982em;" > < span style = "top:-5.4341em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8641em;" > < span style = "top:-3.113em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 4< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8641em;" > < span style = "top:-3.113em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 5< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span cla
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:6.04em;vertical-align:-2.75em;" > < / span > < span class = "mord" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.29em;" > < span style = "top:-5.25em;" > < span class = "pstrut" style = "height:5.25em;" > < / span > < span class = "mtable" > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Degree< / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < / span > < / span > < span style = "top:-1.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < / span > < / span > < span style = "top:-0.61em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:2.75em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-l" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Constraint< / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.03588em;" > q< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.4585em;margin-left:-0.0359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Commit< / span > < / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8376em;" > < span style = "top:-2.8416em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > ivk< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2415em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mopen" > (< / span > < span class = "mord mathnormal" > b< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > − < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3
< h2 id = "canonicity-checks" > < a class = "header" href = "#canonicity-checks" > Canonicity checks< / a > < / h2 >
< p > At this point, we have constrained < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1.3341em;vertical-align:-0.5841em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "mclose" > )< / span > < / span > < / span > < / span > and
< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1.3341em;vertical-align:-0.5841em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < span class = "mclose" > )< / span > < / span > < / span > < / span > to be 255-bit values, with top bits < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span >
and < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > respectively. We have also constrained:< / p >
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:3.4481em;vertical-align:-1.4741em;" > < / span > < span class = "mtable" > < span class = "col-align-r" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:1.9741em;" > < span style = "top:-4.1341em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "mclose" > )< / span > < / span > < / span > < span style = "top:-2.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > <
< p > where < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.625em;vertical-align:-0.1944em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.03588em;" > q< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:-0.0359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > is the Pallas base field modulus. The remaining constraints will
2021-07-26 12:33:28 -07:00
enforce that these are indeed canonically-encoded field elements, i.e.< / p >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:3.4481em;vertical-align:-1.4741em;" > < / span > < span class = "mtable" > < span class = "col-align-r" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:1.9741em;" > < span style = "top:-4.1341em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "mclose" > )< / span > < / span > < / span > < span style = "top:-2.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > I2LEBSP< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ℓ < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.9797em;" > < span style = "top:-2.1528em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > base< / span > < / span > < / span > < / span > < / span > < span style = "top:-2.9837em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Orchard< / span > < span class = "mord rlap mtight" > < span class = "inner" > < span class = "mord mtight" style = "color:transparent;" > < span class = "mord mathsf mtight" style = "color:transparent;" > p< / span > < / span > < / span > < span class = "fix" > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3472em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.5841em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > <
< p > The Pallas base field modulus has the form < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.625em;vertical-align:-0.1944em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.03588em;" > q< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:-0.0359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8974em;vertical-align:-0.0833em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 254< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > , where
< span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6111em;" > < / span > < span class = "mord" > < span class = "mord mathtt" > 0x224698fc094cf91b992d30ed00000001< / span > < / span > < / span > < / span > < / span > < / span >
2021-07-26 12:33:28 -07:00
is 126 bits. We therefore know that if the top bit is not set, then the remaining bits
will always comprise a canonical encoding of a field element. Thus the canonicity checks
2023-11-30 00:04:57 -08:00
below are enforced if and only if < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 1< / span > < / span > < / span > < / span > (for < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < / span > ) or < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 1< / span > < / span > < / span > < / span > (for
< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span > ).< / p >
2021-07-26 12:33:28 -07:00
< blockquote >
2023-11-30 00:04:57 -08:00
< p > In the constraints below we use a base-< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 10< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > variant of the method used in libsnark
2021-07-26 12:33:28 -07:00
(originally from [< a href = "https://eprint.iacr.org/2012/598.pdf" > SVPBABW2012< / a > , Appendix C.1]) for
2023-11-30 00:04:57 -08:00
range constraints < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > x< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6151em;" > < / span > < span class = "mord mathnormal" > t< / span > < / span > < / span > < / span > :< / p >
2021-07-26 12:33:28 -07:00
< ul >
2023-11-30 00:04:57 -08:00
< li > Let < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7519em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > be the smallest power of < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 10< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > greater than < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6151em;" > < / span > < span class = "mord mathnormal" > t< / span > < / span > < / span > < / span > .< / li >
< li > Enforce < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > x< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7519em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > .< / li >
< li > Let < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7519em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > x< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6667em;vertical-align:-0.0833em;" > < / span > < span class = "mord mathnormal" > x< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8352em;vertical-align:-0.0833em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > − < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6151em;" > < / span > < span class = "mord mathnormal" > t< / span > < / span > < / span > < / span > .< / li >
< li > Enforce < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.791em;vertical-align:-0.0391em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > x< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7519em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > .< / li >
2021-07-26 12:33:28 -07:00
< / ul >
< / blockquote >
2023-11-30 00:04:57 -08:00
< h3 id = "ak-with-b11ak2254" > < a class = "header" href = "#ak-with-b11ak2254" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < / span > with < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8304em;vertical-align:-0.136em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≥< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 254< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < a name = "canonicity-ak" > < / a > < / h3 >
< p > In these cases, we check that < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord textsf" > ak< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 0..< / span > < span class = "mrel mtight" > =< / span > < span class = "mord mtight" > 253< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > :< / p >
2021-07-26 12:33:28 -07:00
< ol >
< li >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 0.< / span > < / span > < / span > < / span > < / p >
< p > Since < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 0..< / span > < span class = "mrel mtight" > =< / span > < span class = "mord mtight" > 253< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:1.0085em;vertical-align:-0.1944em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 126< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mpunct" > ,< / span > < / span > < / span > < / span > we know that
< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 126..< / span > < span class = "mrel mtight" > =< / span > < span class = "mord mtight" > 253< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8389em;vertical-align:-0.1944em;" > < / span > < span class = "mord" > 0< / span > < span class = "mpunct" > ,< / span > < / span > < / span > < / span > and in particular
< span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > :=< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 250..< / span > < span class = "mrel mtight" > =< / span > < span class = "mord mtight" > 253< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 0.< / span > < / span > < / span > < / span > < / span > < / p >
2021-07-26 12:33:28 -07:00
< / li >
< li >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > a< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord" > .< / span > < / span > < / span > < / span > < / p >
< p > To check that < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > a< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > , we use two constraints:< / p >
< p > a) < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > a< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 130< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > . This is expressed in the custom gate as
< span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7167em;vertical-align:-0.2861em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > a< / span > < span class = "mpunct mtight" > ,< / span > < span class = "mord mtight" > 13< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2861em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8389em;vertical-align:-0.1944em;" > < / span > < span class = "mord" > 0< / span > < span class = "mpunct" > ,< / span > < / span > < / span > < / span > < / span >
where < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7167em;vertical-align:-0.2861em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > a< / span > < span class = "mpunct mtight" > ,< / span > < span class = "mord mtight" > 13< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2861em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > is the index-13 running sum output by < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1em;vertical-align:-0.25em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > SinsemillaHash< / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord mathnormal" > a< / span > < span class = "mclose" > )< / span > < span class = "mord" > .< / span > < / span > < / span > < / span > < / p >
< p > b) < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6667em;vertical-align:-0.0833em;" > < / span > < span class = "mord mathnormal" > a< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8974em;vertical-align:-0.0833em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 130< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > − < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 130< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > . To check this, we decompose
< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7519em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > a< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6667em;vertical-align:-0.0833em;" > < / span > < span class = "mord mathnormal" > a< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8974em;vertical-align:-0.0833em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 130< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > − < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > into thirteen 10-bit words (little-endian) using
a running sum < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.5806em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.328em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > a< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.6828em;" > < span style = "top:-2.786em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > , looking up each word in a < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 10< / span > < / span > < / span > < / span > -bit lookup table. We then
2021-07-26 12:33:28 -07:00
enforce in the custom gate that
2023-11-30 00:04:57 -08:00
< span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7167em;vertical-align:-0.2861em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.328em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > a< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.6828em;" > < span style = "top:-2.786em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mpunct mtight" > ,< / span > < span class = "mord mtight" > 13< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2861em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 0.< / span > < / span > < / span > < / span > < / span > < / p >
2021-07-26 12:33:28 -07:00
< / li >
< / ol >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:6.04em;vertical-align:-2.75em;" > < / span > < span class = "mord" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.29em;" > < span style = "top:-5.25em;" > < span class = "pstrut" style = "height:5.25em;" > < / span > < span class = "mtable" > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Degree< / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < span style = "top:-1.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < / span > < / span > < span style = "top:-0.61em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:2.75em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-l" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Constraint< / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.03588em;" > q< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.4585em;margin-left:-0.0359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Commit< / span > < / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8376em;" > < span style = "top:-2.8416em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > ivk< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2415em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style
< h3 id = "nk-with-d11nk2254" > < a class = "header" href = "#nk-with-d11nk2254" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6944em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span > with < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8304em;vertical-align:-0.136em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≥< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 254< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < a name = "canonicity-nk" > < / a > < / h3 >
< p > In these cases, we check that < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord textsf" > nk< / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 0..< / span > < span class = "mrel mtight" > =< / span > < span class = "mord mtight" > 253< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > :< / p >
2021-07-26 12:33:28 -07:00
< ol >
< li >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 0< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 0.< / span > < / span > < / span > < / span > < / p >
< p > Since < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 0..< / span > < span class = "mrel mtight" > =< / span > < span class = "mord mtight" > 253< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:1.0085em;vertical-align:-0.1944em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 126< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mpunct" > ,< / span > < / span > < / span > < / span > we know that < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < spa
2021-07-26 12:33:28 -07:00
< / li >
< li >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6684em;vertical-align:-0.024em;" > < / span > < span class = "mord" > 1< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ⟹< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 5< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > c< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord" > .< / span > < / span > < / span > < / span > < / p >
< p > To check that < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 5< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > c< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > , we use two constraints:< / p >
< p > a) < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 5< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > c< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 140< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > . < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > is already constrained individually to
be a < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 5< / span > < / span > < / span > < / span > -bit value. < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7167em;vertical-align:-0.2861em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > c< / span > < span class = "mpunct mtight" > ,< / span > < span class = "mord mtight" > 13< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2861em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > is the index-13 running sum output by
< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:1em;vertical-align:-0.25em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > SinsemillaHash< / span > < / span > < / span > < span class = "mopen" > (< / span > < span class = "mord mathnormal" > c< / span > < span class = "mclose" > )< / span > < span class = "mord" > .< / span > < / span > < / span > < / span > By constraining < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7167em;vertical-align:-0.2861em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > c< / span > < span class = "mpunct mtight" > ,< / span > < span class = "mord mtight" > 13< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2861em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8389em;vertical-align:-0.1944em;" > < / span > < span class = "mord" > 0< / span > < span class = "mpunct" > ,< / span > < / span > < / span > < / span > < / span > we constrain
< span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 5< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.5782em;vertical-align:-0.0391em;" > < / span > < span class = "mord mathnormal" > c< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8532em;vertical-align:-0.0391em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 135< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 140< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord" > .< / span > < / span > < / span > < / span > < / p >
< p > b) < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.7804em;vertical-align:-0.136em;" > < / span > < span class = "mord" > 0< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > ≤< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 5< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6667em;vertical-align:-0.0833em;" > < / span > < span class = "mord mathnormal" > c< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8974em;vertical-align:-0.0833em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 140< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > − < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mathbb mtight" > P< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > < < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 140< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > . To check this, we
decompose < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.9019em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord" > < span class = "mord mathnormal" > c< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.7519em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8141em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 5< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6667em;vertical-align:-0.0833em;" > < / span > < span class = "mord mathnormal" > c< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > +< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.8974em;vertical-align:-0.0833em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8141em;" > < span style = "top:-3.063em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > 140< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > − < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7651em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > t< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3322em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 m
10-bit words (little-endian) using a running sum < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6807em;vertical-align:-0.2501em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3361em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3173em;" > < span style = "top:-2.357em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.143em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > c< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.6828em;" > < span style = "top:-2.786em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2501em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > , looking up each
word in a < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 10< / span > < / span > < / span > < / span > -bit lookup table. We then enforce in the custom gate that
< span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.8444em;vertical-align:-0.15em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.7167em;vertical-align:-0.2861em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.04398em;" > z< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3361em;" > < span style = "top:-2.55em;margin-left:-0.044em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3173em;" > < span style = "top:-2.357em;margin-left:0em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > 2< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.143em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mord mtight" > < span class = "mord mathnormal mtight" > c< / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.6828em;" > < span style = "top:-2.786em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > ′ < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mpunct mtight" > ,< / span > < span class = "mord mtight" > 14< / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2861em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < span class = "mrel" > =< / span > < span class = "mspace" style = "margin-right:0.2778em;" > < / span > < / span > < span class = "base" > < span class = "strut" style = "height:0.6444em;" > < / span > < span class = "mord" > 0.< / span > < / span > < / span > < / span > < / span > < / p >
2021-07-26 12:33:28 -07:00
< / li >
< / ol >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:6.04em;vertical-align:-2.75em;" > < / span > < span class = "mord" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.29em;" > < span style = "top:-5.25em;" > < span class = "pstrut" style = "height:5.25em;" > < / span > < span class = "mtable" > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Degree< / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < span style = "top:-1.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 2< / span > < / span > < / span > < span style = "top:-0.61em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > 3< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:2.75em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-2.75em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-l" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:3.25em;" > < span style = "top:-5.41em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord text" > < span class = "mord" > Constraint< / span > < / span > < / span > < / span > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.03588em;" > q< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.4585em;margin-left:-0.0359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Commit< / span > < / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8376em;" > < span style = "top:-2.8416em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > ivk< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2415em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mbin" > ⋅< / span > < span class = "mspace" style = "margin-right:0.2222em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > 1< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.15em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "mspace" style
< h2 id = "region-layout" > < a class = "header" href = "#region-layout" > Region layout< / a > < / h2 >
< p > The constraints controlled by the < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:0.6721em;vertical-align:-0.2415em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" style = "margin-right:0.03588em;" > q< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3448em;" > < span style = "top:-2.4585em;margin-left:-0.0359em;margin-right:0.05em;" > < span class = "pstrut" style = "height:2.7em;" > < / span > < span class = "sizing reset-size6 size3 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > Commit< / span > < / span > < span class = "msupsub" > < span class = "vlist-t" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.8376em;" > < span style = "top:-2.8416em;margin-right:0.0714em;" > < span class = "pstrut" style = "height:2.5em;" > < / span > < span class = "sizing reset-size3 size1 mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mtight" > < span class = "mord mathsf mtight" > ivk< / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:0.2415em;" > < span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > < / span > selector are arranged across 9
2021-07-26 12:33:28 -07:00
advice columns, requiring two rows.< / p >
2023-11-30 00:04:57 -08:00
< p > < span class = "katex-display" > < span class = "katex" > < span class = "katex-html" aria-hidden = "true" > < span class = "base" > < span class = "strut" style = "height:3.6em;vertical-align:-1.55em;" > < / span > < span class = "mord" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:2.05em;" > < span style = "top:-4.05em;" > < span class = "pstrut" style = "height:4.05em;" > < / span > < span class = "mtable" > < span class = "vertical-separator" style = "height:3.6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-1.55em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:2.05em;" > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > ak< / span > < / span > < / span > < / span > < / span > < span style = "top:-1.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord" > < span class = "mord mathsf" > nk< / span > < / span > < / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:1.55em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:3.6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-1.55em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:2.05em;" > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > a< / span > < / span > < / span > < span style = "top:-1.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > c< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:1.55em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:3.6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-1.55em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:2.05em;" > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < / span > < / span > < span style = "top:-1.81em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord mathnormal" > d< / span > < / span > < / span > < / span > < span class = "vlist-s" > < / span > < / span > < span class = "vlist-r" > < span class = "vlist" style = "height:1.55em;" > < span > < / span > < / span > < / span > < / span > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "vertical-separator" style = "height:3.6em;border-right-width:0.04em;border-right-style:solid;margin:0 -0.02em;vertical-align:-1.55em;" > < / span > < span class = "arraycolsep" style = "width:0.5em;" > < / span > < span class = "col-align-c" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:2.05em;" > < span style = "top:-4.21em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < / span > < / span > < span style = "top:-3.01em;" > < span class = "pstrut" style = "height:3em;" > < / span > < span class = "mord" > < span class = "mord" > < span class = "mord mathnormal" > b< / span > < span class = "msupsub" > < span class = "vlist-t vlist-t2" > < span class = "vlist-r" > < span class = "vlist" style = "height:0.3011em;" > < span style = "top:-2.55em;margin-left:0em;margin-right:0.05em;" > < span class = "pstrut"
2021-07-26 12:33:28 -07:00
< / main >
< nav class = "nav-wrapper" aria-label = "Page navigation" >
<!-- Mobile navigation buttons -->
2022-04-28 09:45:52 -07:00
< a rel = "prev" href = "../../design/circuit/gadgets.html" class = "mobile-nav-chapters previous" title = "Previous chapter" aria-label = "Previous chapter" aria-keyshortcuts = "Left" >
2021-07-26 12:33:28 -07:00
< i class = "fa fa-angle-left" > < / i >
< / a >
2023-11-30 00:04:57 -08:00
< a rel = "next prefetch" href = "../../design/circuit/note-commit.html" class = "mobile-nav-chapters next" title = "Next chapter" aria-label = "Next chapter" aria-keyshortcuts = "Right" >
2021-07-26 12:33:28 -07:00
< i class = "fa fa-angle-right" > < / i >
< / a >
< div style = "clear: both" > < / div >
< / nav >
< / div >
< / div >
< nav class = "nav-wide-wrapper" aria-label = "Page navigation" >
2022-04-28 09:45:52 -07:00
< a rel = "prev" href = "../../design/circuit/gadgets.html" class = "nav-chapters previous" title = "Previous chapter" aria-label = "Previous chapter" aria-keyshortcuts = "Left" >
2021-07-26 12:33:28 -07:00
< i class = "fa fa-angle-left" > < / i >
< / a >
2023-11-30 00:04:57 -08:00
< a rel = "next prefetch" href = "../../design/circuit/note-commit.html" class = "nav-chapters next" title = "Next chapter" aria-label = "Next chapter" aria-keyshortcuts = "Right" >
2021-07-26 12:33:28 -07:00
< i class = "fa fa-angle-right" > < / i >
< / a >
< / nav >
< / div >
2023-11-30 00:04:57 -08:00
< script >
2021-07-26 12:33:28 -07:00
window.playground_copyable = true;
< / script >
2023-11-30 00:04:57 -08:00
< script src = "../../elasticlunr.min.js" > < / script >
< script src = "../../mark.min.js" > < / script >
< script src = "../../searcher.js" > < / script >
2021-07-26 12:33:28 -07:00
2023-11-30 00:04:57 -08:00
< script src = "../../clipboard.min.js" > < / script >
< script src = "../../highlight.js" > < / script >
< script src = "../../book.js" > < / script >
2021-07-26 12:33:28 -07:00
<!-- Custom JS scripts -->
2023-11-30 00:04:57 -08:00
< / div >
2021-07-26 12:33:28 -07:00
< / body >
< / html >
